AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Non-Extremal Permutations of the Integers Modulo 105 Have at Most 40 Good Slopes

low tier2026-11-15OP-1027reviewed by Claude Code中文版

Abstract

Question 10.2 of arXiv:2611.04551 investigates the cardinality of the set of good slopes $D_n(f) = \{m \in \mathbb{Z}/n\mathbb{Z} : x \mapsto f(x) + mx \text{ is bijective}\}$ for permutations $f$ of the residue ring $\mathbb{Z}/n\mathbb{Z}$, where $n$ is an odd composite integer with at least two distinct prime divisors and $q$ is its largest prime divisor. A permutation is extremal when $|D_n(f)|$ reaches Euler's totient $\varphi(n)$. The paper asks whether every non-extremal permutation satisfies the gap bound $|D_n(f)| \le \varphi(n)\frac{q-2}{q-1}$, and names $n = 105$ (for which $q = 7$, $\varphi(105) = 48$, and the conjectured bound is 40) as the smallest modulus its results do not cover. We present a machine-checked proof in Lean 4 of the theorem good_slopes_gap_mod_105, establishing that every non-extremal permutation of $\mathbb{Z}/105\mathbb{Z}$ indeed satisfies $|D_{105}(f)| \le 40$. The proof combines a unit-translation certificate (good_slopes_unit_cover_mod105) that embeds the good slopes into the unit group $(\mathbb{Z}/105\mathbb{Z})^\times$ with a Chinese Remainder Theorem splitting $\mathbb{Z}/105\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$. A two-row fiber rigidity theorem (good_slopes_two_row_fiber_rigidity) shows that if the sum of the sizes of the two unit fibers modulo 35 exceeds 40, then every unit slope modulo 35 must be injective in both fibers. This forces the shifted set of good slopes to be the entire unit group of order 48, contradicting non-extremality. Since the paper shows the bound is attained for every odd composite modulus, 40 is the largest number of good slopes of a non-extremal permutation of $\mathbb{Z}/105\mathbb{Z}$.

1. Introduction

The papers arXiv:2611.01465 and arXiv:2611.04551 study how many affine perturbations of a permutation of the residue ring $\mathbb{Z}/n\mathbb{Z}$ remain permutations; the first is motivated by quantum Latin squares.

Central to this investigation is the notion of a good slope. For a natural number $n \ge 1$ and a permutation $f$ of $\mathbb{Z}/n\mathbb{Z}$, an element $m \in \mathbb{Z}/n\mathbb{Z}$ is called a good slope for $f$ if the affine perturbation $x \mapsto f(x) + mx$ remains a permutation of $\mathbb{Z}/n\mathbb{Z}$. The set of all good slopes of $f$ is denoted by $D_n(f)$. Since $f$ itself is a permutation, zero is always a good slope, so $D_n(f)$ is never empty.

Every permutation of $\mathbb{Z}/n\mathbb{Z}$ has at most $\varphi(n)$ good slopes, where $\varphi$ is Euler's totient function (arXiv:2611.01465). Permutations attaining this bound are called extremal; for them $D_n(f)$ is a translate $(\mathbb{Z}/n\mathbb{Z})^\times - a$ of the unit group.

A natural and delicate problem is to understand the distribution of $|D_n(f)|$ below the extremal threshold $\varphi(n)$. Does the quantity $|D_n(f)|$ drop discontinuously below $\varphi(n)$ for non-extremal permutations, or can it take values arbitrarily close to $\varphi(n)?$ Question 10.2 of arXiv:2611.04551 formulates this problem as a precise conjectural gap:

Let $n$ be an odd composite integer with at least two distinct prime divisors, and let $q$ be its largest prime divisor. Does every non-extremal permutation $f$ of $\mathbb{Z}/n\mathbb{Z}$ satisfy $$|D_n(f)| \le \varphi(n)\frac{q-2}{q-1}?$$

The paper shows (its Proposition 9.6) that the bound cannot be improved: for every odd composite $n$ some non-extremal permutation has exactly $\varphi(n)\frac{q-2}{q-1}$ good slopes. Two small instances are also checked in Lean. When $n = 15 = 3 \times 5$, the largest prime factor is $q = 5$, and $\varphi(15) = 8$. The conjectured bound is $8 \times (5-2)/(5-1) = 8 \times (3/4) = 6$. The result good_slopes_gap_tight_mod_15 confirms that this bound is attained: there exists a non-extremal permutation of $\mathbb{Z}/15\mathbb{Z}$ possessing exactly 6 good slopes. Similarly, for $n = 45 = 3^2 \times 5$, the largest prime factor is $q = 5$, $\varphi(45) = 24$, and the conjectured bound is $24 \times (3/4) = 18$. The result good_slopes_gap_tight_mod_45 shows that there exists a non-extremal permutation of $\mathbb{Z}/45\mathbb{Z}$ with exactly 18 good slopes, as in Example 9.17 of the paper.

The paper proves the bound for congruence-preserving permutations, for products of two distinct odd primes, and for several further families ($9q$ and $3q^e$ among them); its Table 3 lists the moduli up to 175 it leaves open, and it states that the smallest modulus not covered is $n = 105$. By its Corollary 9.5, a counterexample at the smallest possible modulus would preserve no nontrivial congruence, so the paper's reductions to smaller moduli do not apply. The integer $105 = 3 \times 5 \times 7$ is the product of the three smallest odd primes. Its largest prime factor is $q = 7$, and its totient is $$\varphi(105) = \varphi(3)\varphi(5)\varphi(7) = 2 \times 4 \times 6 = 48.$$ The conjectural gap bound for $n = 105$ evaluates to $$\varphi(105)\frac{q-2}{q-1} = 48 \times \frac{7-2}{7-1} = 48 \times \frac{5}{6} = 40.$$ Thus Question 10.2 conjectures that no permutation of $\mathbb{Z}/105\mathbb{Z}$ can have a number of good slopes strictly between 40 and 48. Proving this requires analyzing the full permutation space of a ring of order 105, which is far beyond brute-force enumeration since $105! \approx 1.08 \times 10^{168}$.

In this post, we report on the machine-checked resolution of this question in Lean 4. We discuss the proof of the theorem good_slopes_gap_mod_105, which establishes that every non-extremal permutation $f$ of $\mathbb{Z}/105\mathbb{Z}$ satisfies $|D_{105}(f)| \le 40$. The argument overcomes the computational intractability of modulus 105 by synthesizing a unit-covering translation lemma, a Chinese Remainder Theorem splitting $\mathbb{Z}/105\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$, and a two-row fiber rigidity theorem (good_slopes_two_row_fiber_rigidity). This rigidity theorem forces any permutation with more than 40 good slopes, after a shift, to have all 48 units as good slopes, making it extremal. With the paper's Proposition 9.6, 40 is therefore the exact maximum for non-extremal permutations of $\mathbb{Z}/105\mathbb{Z}$.

2. Preliminaries

We work in the setting of residue rings of integers modulo $n$, denoted $\mathbb{Z}/n\mathbb{Z}$, represented in Lean 4 by the type ZMod n. Throughout, permutations of $\mathbb{Z}/n\mathbb{Z}$ are represented by bijective maps from ZMod n to itself.

Definition 1 (Good Slopes, good_slopes). Let $n$ be a positive natural number satisfying the typeclass constraint [NeZero n]. For a permutation $f$ of $\mathbb{Z}/n\mathbb{Z}$, the set of good slopes of $f$, denoted $D_n(f)$ and defined in Lean as good_slopes n f, is the finite subset of $\mathbb{Z}/n\mathbb{Z}$ given by $$D_n(f) = \{m \in \mathbb{Z}/n\mathbb{Z} : x \mapsto f(x) + mx \text{ is bijective}\}.$$ In Lean, this is formalized as: ``lean def good_slopes (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) : Finset (ZMod n) := Finset.univ.filter (fun m => Function.Bijective (fun x => f x + m * x)) ` Remark. The definition requires [NeZero n] so that $\mathbb{Z}/n\mathbb{Z}$ is well-defined. While for any mapping from a finite type to itself injectivity, surjectivity, and bijectivity are logically equivalent, the definition specifies Function.Bijective`.

Definition 2 (Extremal Permutation, is_extremal_perm). Let $n$ be a natural number with [NeZero n]. A permutation $f$ of $\mathbb{Z}/n\mathbb{Z}$ is extremal if the cardinality of its set of good slopes attains the value of Euler's totient function $\varphi(n)$: $$|D_n(f)| = \varphi(n).$$ In Lean, this predicate is defined as: ``lean def is_extremal_perm (n : ℕ) [NeZero n] (f : Equiv.Perm (ZMod n)) : Prop := (good_slopes n f).card = Nat.totient n ` Remark. Here $\varphi(n)$ is represented by Nat.totient n. For $n = 105$, Nat.totient 105` evaluates to 48.

Definition 3 (CRT Coordinate Projections and Splitting for Modulus 105). Since $\gcd(3, 35) = 1$ and $3 \times 35 = 105$, the Chinese Remainder Theorem induces a canonical ring isomorphism between $\mathbb{Z}/105\mathbb{Z}$ and $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$. We define:

  • The canonical projection $\pi_3 : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z}$ mapping $x \pmod{105}$ to $x \pmod 3$.
  • The canonical projection $\pi_{35} : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/35\mathbb{Z}$ mapping $x \pmod{105}$ to $x \pmod{35}$.
  • The coordinate splitting bijection $\sigma : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ defined by $x \mapsto (\pi_3(x), \pi_{35}(x))$.
  • The Chinese Remainder reconstruction map $\sigma^{-1} : \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z} \to \mathbb{Z}/105\mathbb{Z}$.

Remark. The formalization groups the prime factors 5 and 7 into a composite factor 35, viewing $\mathbb{Z}/105\mathbb{Z}$ as $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ rather than a ternary product $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z} \times \mathbb{Z}/7\mathbb{Z}$. This structural choice is essential: the unit group of $\mathbb{Z}/3\mathbb{Z}$ contains only two elements, namely $1$ and $2$, allowing the unit slopes in the product ring to be partitioned into exactly two fibers (or rows) parameterized by $a \in \{1, 2\}$.

Definition 4 (Unit Direction Fibers modulo 35). Let $g : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/105\mathbb{Z}$ be a function. For each first-coordinate slope $a \in \mathbb{Z}/3\mathbb{Z}$, the fiber of good unit slopes in the second coordinate modulo 35 is the set $$R(a) = \left\{b \in (\mathbb{Z}/35\mathbb{Z})^\times : x \mapsto (\pi_3(g(x)) + a \pi_3(x), \pi_{35}(g(x)) + b \pi_{35}(x)) \text{ is injective}\right\}.$$

Remark. Since $\mathbb{Z}/105\mathbb{Z}$ is finite of cardinality 105, injectivity of this map into $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ (which also has cardinality $3 \times 35 = 105$) is equivalent to bijectivity. The set of units $(\mathbb{Z}/35\mathbb{Z})^\times$ has cardinality $\varphi(35) = \varphi(5)\varphi(7) = 4 \times 6 = 24$, so each fiber $R(a)$ satisfies $R(a) \subseteq (\mathbb{Z}/35\mathbb{Z})^\times$ and $|R(a)| \le 24$.

3. Main result

Theorem (good_slopes_gap_mod_105). Let $f$ be a permutation of the residue ring $\mathbb{Z}/105\mathbb{Z}$. If $f$ is not extremal, meaning that the number of its good slopes satisfies $|D_{105}(f)| \neq \varphi(105) = 48$, then $$|D_{105}(f)| \le 40.$$

The site shows the Lean formulation of the main theorem under this section: ``lean theorem good_slopes_gap_mod_105 (f : Equiv.Perm (ZMod 105)) (hf : ¬ is_extremal_perm 105 f) : (good_slopes 105 f).card ≤ 40 ` The Lean theorem good_slopes_gap_mod_105 takes as hypothesis a permutation f : Equiv.Perm (ZMod 105) and an assumption hf : ¬ is_extremal_perm 105 f, and concludes (good_slopes 105 f).card ≤ 40`, asserting that the cardinality of the finite set of good slopes of $f$ is at most 40.

What each further result adds: The material includes several supporting and contextual theorems that complement good_slopes_gap_mod_105:

- Modulus 15 tightness (good_slopes_gap_tight_mod_15): Demonstrates that the gap bound $\varphi(n)\frac{q-2}{q-1}$ is sharp for $n = 15$ ($q = 5$), producing an explicit non-extremal permutation of $\mathbb{Z}/15\mathbb{Z}$ with exactly 6 good slopes, matching $\varphi(15) \times (3/4) = 6$.

- Modulus 45 tightness (good_slopes_gap_tight_mod_45): Demonstrates sharpness for the composite modulus with a prime square $n = 45 = 3^2 \times 5$ ($q = 5$), producing a non-extremal permutation of $\mathbb{Z}/45\mathbb{Z}$ with exactly 18 good slopes, matching $\varphi(45) \times (3/4) = 18$.

- Unit-gap on 35 points (good_slopes_fiber35_unit_gap): Proves that for any configuration of 35 points over $\mathbb{Z}/35\mathbb{Z}$, if at least one of the 24 unit directions fails to be injective, then at most 20 of the unit directions can be injective, establishing a local drop of at least 4 directions.

- Colored unit-gap on 35 points (good_slopes_fiber35_colored_gap): Shows that if 35 points in $\mathbb{Z}/35\mathbb{Z}$ are partitioned into three color classes such that each color class is injective under all unit-direction forms $y + ax$, then either every unit direction is globally injective, or at most 16 unit directions are globally injective.

- Two-row fiber rigidity (good_slopes_two_row_fiber_rigidity): The key engine behind good_slopes_gap_mod_105, stating that on a set of $105 = 3 \times 35$ points, if the numbers of good unit directions in two rows (two slopes in $\mathbb{Z}/3\mathbb{Z}$) add up to more than 40, then every unit direction in both rows is injective.

Theorem good_slopes_gap_mod_105 (Lean 4, verified)
theorem good_slopes_gap_mod_105 (f : Equiv.Perm (ZMod 105)) (hf : ¬ is_extremal_perm 105 f) : (good_slopes 105 f).card ≤ 40

4. Proof

Proof Idea: The proof proceeds by contradiction. We assume that $f$ is a non-extremal permutation of $\mathbb{Z}/105\mathbb{Z}$ and that $|D_{105}(f)| > 40$. First, using good_slopes_unit_cover_mod105, we find a unit $c \in (\mathbb{Z}/105\mathbb{Z})^\times$ such that translating every good slope $m \in D_{105}(f)$ by $c$ produces a unit $m + c \in (\mathbb{Z}/105\mathbb{Z})^\times$. We then normalize $f$ by subtracting the linear term $cx$, setting $f_{\text{norm}}(x) = f(x) - cx$. The set of translated slopes $A = \{m + c : m \in D_{105}(f)\}$ consists entirely of units in $\mathbb{Z}/105\mathbb{Z}$, has size $|A| = |D_{105}(f)| > 40$, and satisfies the property that $u \in A$ if and only if $x \mapsto f_{\text{norm}}(x) + ux$ is bijective.

Next, we split $\mathbb{Z}/105\mathbb{Z}$ into $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ via the Chinese Remainder Theorem isomorphism $\sigma$. Because each $u \in A$ is a unit in $\mathbb{Z}/105\mathbb{Z}$, its projection $a = \pi_3(u)$ is a unit in $\mathbb{Z}/3\mathbb{Z}$, and its projection $b = \pi_{35}(u)$ is a unit in $\mathbb{Z}/35\mathbb{Z}$. The ring $\mathbb{Z}/3\mathbb{Z}$ has only two units: $1$ and $2$. This partitions the image of $A$ under $\sigma$ into two disjoint fibers, $(\{1\} \times R(1)) \cup (\{2\} \times R(2))$, where $R(a)$ consists of those unit slopes $b \in (\mathbb{Z}/35\mathbb{Z})^\times$ for which the map $x \mapsto (\pi_3(f_{\text{norm}}(x)) + a \pi_3(x), \pi_{35}(f_{\text{norm}}(x)) + b \pi_{35}(x))$ is injective.

The cardinality identity $|A| = |R(1)| + |R(2)|$ implies that $|R(1)| + |R(2)| > 40$. We then invoke the two-row fiber rigidity theorem good_slopes_two_row_fiber_rigidity with $a = 1$ and $a' = 2$. Because the total number of good unit pairs across the two rows exceeds 40, the rigidity theorem forces both fibers to be completely full: every unit $b \in (\mathbb{Z}/35\mathbb{Z})^\times$ belongs to both $R(1)$ and $R(2)$. Recombining via CRT shows that every unit $u \in (\mathbb{Z}/105\mathbb{Z})^\times$ belongs to $A$. Consequently, $A$ is the entire unit group $(\mathbb{Z}/105\mathbb{Z})^\times$, which has cardinality $\varphi(105) = 48$. This gives $|D_{105}(f)| = 48 = \varphi(105)$, showing that $f$ is extremal and providing the desired contradiction.

We now state the key lemmas used in the formalization:

Lemma 1 (good_slopes_unit_cover_mod105). For every permutation $f$ of $\mathbb{Z}/105\mathbb{Z}$, there exists a unit $c \in (\mathbb{Z}/105\mathbb{Z})^\times$ such that for all $m \in \text{good\_slopes } 105\ f$, the sum $m + c$ is a unit in $\mathbb{Z}/105\mathbb{Z}$: $$\exists c \in (\mathbb{Z}/105\mathbb{Z})^\times, \quad \forall m \in D_{105}(f), \quad m + c \in (\mathbb{Z}/105\mathbb{Z})^\times.$$ Proof. For each prime $p \in \{3, 5, 7\}$, some residue $a_p$ modulo $p$ is attained by no good slope. Since $0$ is a good slope, $a_p \neq 0$. Choose $c$ by the Chinese Remainder Theorem with $c \equiv -a_p \pmod p$ for each $p$; then $c$ is a unit, and for every good slope $m$ we have $m + c \not\equiv 0 \pmod p$ for all three primes, so $m + c$ is a unit.

Lemma 2 (CRT Bijectivity and Unit Splitting). Let $g : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/105\mathbb{Z}$ and $u \in \mathbb{Z}/105\mathbb{Z}$. 1. The map $x \mapsto g(x) + ux$ is bijective on $\mathbb{Z}/105\mathbb{Z}$ if and only if the coordinate map $$x \mapsto (\pi_3(g(x)) + \pi_3(u)\pi_3(x), \, \pi_{35}(g(x)) + \pi_{35}(u)\pi_{35}(x))$$ is bijective (or equivalently, injective) on $\mathbb{Z}/105\mathbb{Z}$. 2. The coordinate splitting map $\sigma : x \mapsto (\pi_3(x), \pi_{35}(x))$ is a bijection between $\mathbb{Z}/105\mathbb{Z}$ and $\mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$, with inverse given by Chinese Remainder reconstruction. 3. An element $a \in \mathbb{Z}/3\mathbb{Z}$ is a unit if and only if $a = 1$ or $a = 2$. 4. An element $u \in \mathbb{Z}/105\mathbb{Z}$ is a unit if and only if $\pi_3(u)$ is a unit in $\mathbb{Z}/3\mathbb{Z}$ and $\pi_{35}(u)$ is a unit in $\mathbb{Z}/35\mathbb{Z}$. Proof. Part 1 holds because $\pi_3$ and $\pi_{35}$ are ring homomorphisms and $\sigma$ is injective; part 2 is the Chinese Remainder Theorem; parts 3 and 4 are finite checks.

Lemma 3 (good_slopes_two_row_fiber_rigidity). Let $X$ be a finite type with cardinality $|X| = 3 \times 35 = 105$. Let $x_3, y_3 : X \to \mathbb{Z}/3\mathbb{Z}$ and $x_{35}, y_{35} : X \to \mathbb{Z}/35\mathbb{Z}$ be functions such that the input pair $x \mapsto (x_3(x), x_{35}(x))$ is injective. Let $a, a' \in \mathbb{Z}/3\mathbb{Z}$ be two slopes. Define for any slope $s \in \mathbb{Z}/3\mathbb{Z}$ the set of good unit slopes in $\mathbb{Z}/35\mathbb{Z}$: $$R(s) = \{b \in (\mathbb{Z}/35\mathbb{Z})^\times : x \mapsto (y_3(x) + s \cdot x_3(x), y_{35}(x) + b \cdot x_{35}(x)) \text{ is injective}\}.$$ If $|R(a)| + |R(a')| > 40$, then every unit $b \in (\mathbb{Z}/35\mathbb{Z})^\times$ satisfies $b \in R(a)$ and $b \in R(a')$. That is, both fibers are entirely full: $|R(a)| = 24$ and $|R(a')| = 24$. Proof. Each fiber has at most 24 elements, so both are nonempty, and each row $s \in \{a, a'\}$ has an anchor slope $b_0$ for which the map is injective, hence bijective. Fix a row $s$ with its anchor. For $t \in \mathbb{Z}/3\mathbb{Z}$, the points $x$ with $y_3(x) + s\,x_3(x) = t$ give a set $S_t$ of exactly 35 pairs $(x_{35}(x), y_{35}(x))$ in $\mathbb{Z}/35\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$, and a slope $b$ is good in row $s$ if and only if $y + bx$ is injective on each of $S_0, S_1, S_2$. Suppose some unit $b$ is bad in row $a$. Then it is bad on one of the sets $S_t$, and by good_slopes_fiber35_unit_gap that set has at most 20 injective unit directions, so $|R(a)| \le 20$. The same holds for row $a'$ if it has a bad unit, and then $|R(a)| + |R(a')| \le 40$; so every unit is good in row $a'$. Now colour each point of the bad set $S_t$ of row $a$ by the value $x_3$ of the point it comes from. Two points of one colour have the same $x_3$, and, lying on the same line $y_3 + a x_3 = t$, also the same $y_3$; since every unit is good in row $a'$, each form $y + bx$ with $b$ a unit is injective within a colour, and the first coordinate is injective within a colour because $(x_3, x_{35})$ is injective. So good_slopes_fiber35_colored_gap applies and bounds the number of injective unit directions on $S_t$, hence $|R(a)|$, by 16. Then $|R(a)| + |R(a')| \le 16 + 24 = 40$, a contradiction. By symmetry the same holds for row $a'$. The two 35-point lemmas carry the combinatorial weight: good_slopes_fiber35_unit_gap says that any 35 points of $\mathbb{Z}/35\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ with a non-injective unit direction have at least four of them, and good_slopes_fiber35_colored_gap raises this to eight under the colouring hypothesis.

Detailed Proof of good_slopes_gap_mod_105: We now follow the Lean proof of good_slopes_gap_mod_105 step by step.

1. Contradiction assumption: Assume for contradiction that the cardinality of good_slopes 105 $f$ is strictly greater than 40.

2. Shifting by the unit cover: By Lemma 1 (good_slopes_unit_cover_mod105), there exists a unit $c \in (\mathbb{Z}/105\mathbb{Z})^\times$ such that for all $m \in D_{105}(f)$, $m + c$ is a unit in $\mathbb{Z}/105\mathbb{Z}$. We define the normalized map $f_{\text{norm}} : \mathbb{Z}/105\mathbb{Z} \to \mathbb{Z}/105\mathbb{Z}$ by $x \mapsto f(x) - cx$. We define the set of shifted slopes: $$A = \{m + c : m \in D_{105}(f)\} \subseteq \mathbb{Z}/105\mathbb{Z}.$$ For any $u \in \mathbb{Z}/105\mathbb{Z}$, the proof shows: $$u \in A \iff x \mapsto f_{\text{norm}}(x) + ux \text{ is bijective}.$$ To prove the forward implication, let $u = m + c$ with $m \in D_{105}(f)$. Then $$f_{\text{norm}}(x) + ux = (f(x) - cx) + (m + c)x = f(x) + mx,$$ which is bijective because $m \in D_{105}(f)$. The reverse implication follows symmetrically by taking $m = u - c$. Every element $u \in A$ is a unit, because $u = m + c$ for some $m \in D_{105}(f)$, and $c$ was chosen to satisfy the unit cover property. Since addition of $c$ is an injective mapping, the cardinality is preserved: $$|A| = |D_{105}(f)| > 40.$$

3. Splitting into pairs modulo 3 and 35: Let $P \subseteq \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$ be the image of $A$ under the CRT splitting map $\sigma$. Since $\sigma$ is injective, $|P| = |A|$. For any $a \in \mathbb{Z}/3\mathbb{Z}$ and $b \in \mathbb{Z}/35\mathbb{Z}$, a pair $(a, b)$ belongs to $P$ if and only if the Chinese Remainder reconstruction of $(a, b)$ belongs to $A$. Combining this with the fact that all elements of $A$ are units and applying Lemma 2, we obtain the equivalence: $(a, b) \in P$ if and only if $a$ is a unit in $\mathbb{Z}/3\mathbb{Z}$, $b$ is a unit in $\mathbb{Z}/35\mathbb{Z}$, and the mapping $$x \mapsto (\pi_3(f_{\text{norm}}(x)) + a \pi_3(x), \, \pi_{35}(f_{\text{norm}}(x)) + b \pi_{35}(x))$$ is injective on $\mathbb{Z}/105\mathbb{Z}$.

4. Decomposing into two rows: Define $R : \mathbb{Z}/3\mathbb{Z} \to \text{Finset } (\mathbb{Z}/35\mathbb{Z})$ by $$R(a) = \{b \in (\mathbb{Z}/35\mathbb{Z})^\times : x \mapsto (\pi_3(f_{\text{norm}}(x)) + a \pi_3(x), \, \pi_{35}(f_{\text{norm}}(x)) + b \pi_{35}(x)) \text{ is injective}\}.$$ By Lemma 2, the units of $\mathbb{Z}/3\mathbb{Z}$ are precisely $1$ and $2$. Therefore, $P$ decomposes as: $$P = (\{1\} \times R(1)) \cup (\{2\} \times R(2)).$$ Since $1 \neq 2$ in $\mathbb{Z}/3\mathbb{Z}$, the sets $\{1\} \times R(1)$ and $\{2\} \times R(2)$ are disjoint. Taking cardinalities yields: $$|P| = |R(1)| + |R(2)|.$$ Combining with $|P| = |A| = |D_{105}(f)|$, we have: $$|R(1)| + |R(2)| = |D_{105}(f)| > 40.$$

5. Applying fiber rigidity: We apply Lemma 3 (good_slopes_two_row_fiber_rigidity) to: - The finite type $X = \mathbb{Z}/105\mathbb{Z}$, with $|X| = 105 = 3 \times 35$. - Input coordinate functions $x_3 = \pi_3$ and $x_{35} = \pi_{35}$. The pair $(x_3, x_{35}) = \sigma$ is injective. - Output coordinate functions $y_3(x) = \pi_3(f_{\text{norm}}(x))$ and $y_{35}(x) = \pi_{35}(f_{\text{norm}}(x))$. - The row slopes $a = 1$ and $a' = 2$ in $\mathbb{Z}/3\mathbb{Z}$. - The hypothesis $|R(1)| + |R(2)| > 40$. The theorem outputs: $$\forall b \in (\mathbb{Z}/35\mathbb{Z})^\times, \quad b \in R(1) \quad \text{and} \quad b \in R(2).$$

6. Deducing extremality and contradiction: Let $u \in \mathbb{Z}/105\mathbb{Z}$ be an arbitrary unit. Then $a = \pi_3(u)$ is a unit in $\mathbb{Z}/3\mathbb{Z}$, so $a \in \{1, 2\}$, and $b = \pi_{35}(u)$ is a unit in $\mathbb{Z}/35\mathbb{Z}$. By the rigidity conclusion, $b \in R(a)$. By definition of $R(a)$, the map $$x \mapsto (\pi_3(f_{\text{norm}}(x)) + a \pi_3(x), \, \pi_{35}(f_{\text{norm}}(x)) + b \pi_{35}(x))$$ is injective. Since $\mathbb{Z}/105\mathbb{Z}$ is finite, this map is also bijective. Applying Lemma 2, this bijectivity is equivalent to bijectivity of $x \mapsto f_{\text{norm}}(x) + ux$. This implies that $u \in A$. This holds for every unit $u$, so $A$ contains every unit of $\mathbb{Z}/105\mathbb{Z}$. Together with the fact that every element of $A$ is a unit, we obtain $A = U$, where $U = (\mathbb{Z}/105\mathbb{Z})^\times$. The cardinality of the unit group of $\mathbb{Z}/105\mathbb{Z}$ is: $$|U| = \varphi(105) = 48.$$ Thus $|D_{105}(f)| = |A| = |U| = 48 = \varphi(105)$. By Definition 2, this means $f$ satisfies is_extremal_perm 105 f. This directly contradicts the hypothesis that $f$ is not extremal. The contradiction establishes that the cardinality of good_slopes 105 $f$ is at most 40, completing the proof of good_slopes_gap_mod_105.

5. Discussion

The proof of good_slopes_gap_mod_105 resolves the gap conjecture of Question 10.2 in arXiv:2611.04551 for the smallest modulus not covered by the paper's results, namely $n = 105$. Modulus 105 represents a qualitative transition from earlier investigated cases: it is the smallest modulus that is the product of three distinct odd primes ($3 \times 5 \times 7$), rather than two distinct primes (such as $15 = 3 \times 5$ or $21 = 3 \times 7$) or a prime power times a prime ($45 = 3^2 \times 5$).

While the result establishes the upper bound $|D_{105}(f)| \le 40$ for all non-extremal permutations of $\mathbb{Z}/105\mathbb{Z}$, several open questions remain:

- Exact value: by Proposition 9.6 of arXiv:2611.04551, some non-affine permutation of $\mathbb{Z}/105\mathbb{Z}$ has exactly 40 good slopes, so together with good_slopes_gap_mod_105 the largest number of good slopes of a non-extremal permutation of $\mathbb{Z}/105\mathbb{Z}$ is exactly 40, and no permutation has between 41 and 47 good slopes. The Lean material does not contain this construction for $n = 105$.

- General odd composite moduli: Question 10.2 of arXiv:2611.04551 asks whether the bound $|D_n(f)| \le \varphi(n)\frac{q-2}{q-1}$ holds for every odd composite integer $n$ with at least two distinct prime divisors, where $q$ is the largest prime divisor of $n$. The theorem good_slopes_gap_mod_105 settles this question only for the specific instance $n = 105$. The other entries of the paper's Table 3 that it leaves open remain so: $n = 135 = 3^3 \times 5$ (bound 54), $n = 165 = 3 \times 5 \times 11$ (bound 72) and $n = 175 = 5^2 \times 7$ (bound 100). The argument here uses the splitting $\mathbb{Z}/105\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/35\mathbb{Z}$, in which the factor 3 has only two units, together with two finite 35-point lemmas; for $165 = 3 \times 55$ the same scheme would need the analogous lemmas on 55 points.

- Generalizing fiber rigidity: The proof presented here relies heavily on grouping the prime factors into $3$ and $35 = 5 \times 7$. This decomposition produces exactly two unit fibers indexed by the units $1$ and $2$ of $\mathbb{Z}/3\mathbb{Z}$. For moduli where the smallest prime divisor is larger (for example, $n = 35 = 5 \times 7$, where the factors are $5$ and $7$, or $n = 5 \times 7 \times 11 = 385$), splitting off the smallest prime produces $\varphi(p) = p - 1 \ge 4$ fibers rather than 2. Formulating multi-row fiber rigidity principles for $\varphi(p) > 2$ is an important avenue for extending these results to general odd composite moduli.

Why it is research-level

  • Proves the conjectured gap bound for modulus 105, the smallest case left unsettled by arXiv:2611.04551, using a checked CRT fiber reduction and finite-direction certificates

Lean declarations

  • good_slopes_gap_mod_105Every non-extremal permutation f of ℤ/105ℤ satisfies |D_{105}(f)| ≤ 40: (good_slopes 105 f).card ≤ 40.
  • good_slopes_unit_cover_mod105For every permutation modulo 105, a unit c exists such that adding c to each good slope yields a unit modulo 105.
  • good_slopes_two_row_fiber_rigidityLet X be a finite set of 105 elements with input and output coordinate functions over Z/3 and Z/35, and assume the pair of input…
  • good_slopes_gap_tight_mod_15There exists a non-extremal permutation f of ℤ/15ℤ with exactly 6 good slopes, demonstrating that the gap bound φ(15)(q - 2)/(q - 1) = 6…
  • good_slopes_gap_tight_mod_45There exists a non-extremal permutation f of ℤ/45ℤ with exactly 18 good slopes, demonstrating that the gap bound φ(45)(q - 2)/(q - 1) = 18…
  • good_slopesGiven a natural number n with n ≠ 0 (via [NeZero n]) and a permutation f of ℤ/nℤ, good_slopes n f is the finite set (Finset) of elements m…
  • is_extremal_permGiven n with [NeZero n], a permutation f of ℤ/nℤ is extremal if the number of its good slopes (the cardinality of good_slopes n f) equals…
  • good_slopes_fiber35_unit_gapFor any 35 points over the residues modulo 35, if at least one unit direction fails to be injective, then at most 20 of the 24 unit…
  • good_slopes_fiber35_colored_gapLet S be a set of 35 points over the residues modulo 35, colored with three colors. Suppose that within each color both the first…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2611.04551 — Good slopes, congruence preservation, and gaps over residue rings
  2. arXiv:2611.01465 — Extremal permutations of $\mathbb{Z}_n$ with many good slopes and applications to quantum Latin squares

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.