coprime_residue_small_rectangle
If a and b are each coprime to D, are smaller than D, and sum to more than D, then some nonzero k<D has (k*a) mod D<a and (k*b) mod D<=b. Multiplication by each coefficient permutes the residues, and two lower rank sets have intersection size at least two.
Statement
theorem coprime_residue_small_rectangle
(D a b : ℕ) (hD : 0 < D) (ha : a < D) (hb : b < D)
(hca : Nat.Coprime a D) (hcb : Nat.Coprime b D) (hs : D < a + b) :
∃ k : ℕ, k < D ∧ 0 < k ∧ (k * a) % D < a ∧ (k * b) % D ≤ b- Source
- Supporting modular proof for the two-dimensional cone atom bound, a standard fact described in Combinatorial Commutative Algebra, Example 7.19 (https://pages.uoregon.edu/njp/MS.pdf). Used toward the four-support reduction for OP-197, arXiv:2610.16562 Conjecture 1; no new research-level result is claimed.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- two_ray_integer_atom_coeff_sum_leLet x be an atom in the nonnegative part of an additive subgroup of integer-valued functions. If D*x=a*u+b*v for nonnegative subgroup…
The proof, explained
The proof applies the pigeonhole principle to residue classes modulo $D$ to find a nonzero witness $k$. Because $a$ and $b$ are coprime to $D$, multiplication by $a$ and by $b$ permutes the residues $\{0, \dots, D-1\}$. The sets of residues mapped to values $< a$ and $\le b$ have sizes $a$ and $b + 1$ respectively. By the principle of inclusion-exclusion, the size of their union plus the size of their intersection is $a + b + 1 > D + 1$, which forces their intersection to contain at least two elements since the ambient universe has size $D$. Because $0$ is always in the intersection, there must exist a strictly positive element $k < D$ in the intersection, which gives the required witness.
Classical reasoning is enabled and $D$ is established to be nonzero.
The proof opens classical reasoning (allowing excluded middle) and registers a typeclass instance stating $D \neq 0$, which is proved by linear arithmetic (`omega`) from the assumption $0 < D$.
classical letI : NeZero D := ⟨by omega⟩
For any $t$ coprime to $D$, the map $i \mapsto (i \cdot t) \bmod D$ defines a permutation of $\text{Fin } D$.
For a fixed $t$ coprime to $D$, define $f : \text{Fin } D \to \text{Fin } D$ by sending residue $i$ to $(i \cdot t) \bmod D$, which lies in $\text{Fin } D$ by `Nat.mod_lt`. To show $f$ is injective, suppose $f(i) = f(j)$. Taking underlying values via `congrArg` yields $(i \cdot t) \equiv (j \cdot t) \pmod D$. Because $t$ is coprime to $D$, `Nat.ModEq.cancel_right_of_coprime` cancels $t$ to give $i \equiv j \pmod D$. Since $i, j < D$, `Nat.mod_eq_of_lt` reduces this congruence to $i = j$, so by `Fin.ext` the residues are equal. On the finite type $\text{Fin } D$, injectivity implies surjectivity via `Finite.surjective_of_injective`. Therefore, `Equiv.ofBijective` promotes $f$ to a permutation $e$ of $\text{Fin } D$.
uses
Nat.mod_lt,Fin.ext,congrArg,Nat.ModEq.cancel_right_of_coprime,Nat.mod_eq_of_lt,Equiv.ofBijective,Finite.surjective_of_injectivehave make_perm : ∀ t : ℕ, Nat.Coprime t D → ∃ e : Equiv.Perm (Fin D), ∀ i, (e i).val = (i.val * t) % D := by intro t ht let f : Fin D → Fin D := fun i => ⟨(i.val * t) % D, Nat.mod_lt _ hD⟩ have hinj : Function.Injective f := by intro i j hij apply Fin.ext have hh : Nat.ModEq D (i.val * t) (j.val * t) := congrArg Fin.val hij have hc := Nat.ModEq.cancel_right_of_coprime ht.symm hh simpa only [Nat.ModEq, Nat.mod_eq_of_lt i.isLt, Nat.mod_eq_of_lt j.isLt] using hc exact ⟨Equiv.ofBijective f ⟨hinj, Finite.surjective_of_injective hinj⟩, fun _ => rfl⟩
Permutations $e$ and $f$ are obtained for $a$ and $b$, and the residue sets $A$ and $B$ are defined.
Applying `make_perm` to $a$ and $b$ (using their coprimality with $D$) yields permutations $e$ and $f$ of $\text{Fin } D$ corresponding to multiplication by $a$ and $b$ modulo $D$. The sets $A = \{i \in \text{Fin } D \mid e(i) < a\}$ and $B = \{i \in \text{Fin } D \mid f(i) < b + 1\}$ are then defined as the subsets of residues whose images fall into the respective small initial segments.
obtain ⟨e, he⟩ := make_perm a hca obtain ⟨f, hf⟩ := make_perm b hcb let A := univ.filter fun i : Fin D => (e i).val < a let B := univ.filter fun i : Fin D => (f i).val < b + 1
The set $A$ has cardinality $a$.
Since $e$ is a bijection, $A$ is the image under the embedding $e^{-1}$ of the initial segment $\{i \in \text{Fin } D \mid i < a\}$. An embedding preserves cardinality (`card_map`), and by `Fin.card_filter_val_lt` the number of elements in $\text{Fin } D$ strictly less than $a$ is $\min(D, a)$. Because $a < D$, `Nat.le_of_lt` and `min_eq_right` show that $\min(D, a) = a$.
uses
card_map,Fin.card_filter_val_lt,min_eq_right,Nat.le_of_lthave hA : A.card = a := by have hmap : A = (univ.filter fun i : Fin D => i.val < a).map e.symm.toEmbedding := by ext i simp [A] rw [hmap, card_map, Fin.card_filter_val_lt, min_eq_right (Nat.le_of_lt ha)]
The set $B$ has cardinality $b + 1$.
Analogously, $B$ is the image under $f^{-1}$ of the segment $\{i \in \text{Fin } D \mid i < b + 1\}$. By `card_map` and `Fin.card_filter_val_lt`, its size is $\min(D, b + 1)$. Since $b < D$, linear arithmetic shows $b + 1 \le D$, so `min_eq_right` evaluates the minimum to $b + 1$.
uses
card_map,Fin.card_filter_val_lt,min_eq_righthave hB : B.card = b + 1 := by have hmap : B = (univ.filter fun i : Fin D => i.val < b + 1).map f.symm.toEmbedding := by ext i simp [B] rw [hmap, card_map, Fin.card_filter_val_lt, min_eq_right (by omega)]
There exists a nonzero residue $i \in \text{Fin } D$ satisfying $e(i) < a$ and $f(i) \le b$.
Assume for contradiction (`by_contra`) that no such nonzero residue exists. Any residue $i \in A \cap B$ satisfies $e(i) < a$ and $f(i) < b + 1$ (so $f(i) \le b$); if $i \neq 0$, this would contradict the negation hypothesis, closing that case via `False.elim`. Hence $A \cap B \subseteq \{0\}$, which implies $|A \cap B| \le 1$ by `card_le_card`. Furthermore, $A \cup B \subseteq \text{Fin } D$, so $|A \cup B| \le D$ by `card_le_univ`. By the inclusion-exclusion identity `card_union_add_card_inter`, $|A \cup B| + |A \cap B| = |A| + |B| = a + b + 1$. Linear arithmetic (`omega`) deduces that $a + b + 1 \le D + 1$, hence $a + b \le D$, contradicting the hypothesis $D < a + b$.
uses
False.elim,card_le_card,card_le_univ,card_union_add_card_interhave hex : ∃ i : Fin D, i ≠ 0 ∧ (e i).val < a ∧ (f i).val ≤ b := by by_contra hnone have hsub : A ∩ B ⊆ {0} := by intro i hi have hiA := (mem_filter.mp (mem_inter.mp hi).1).2 have hiB := (mem_filter.mp (mem_inter.mp hi).2).2 by_cases hz : i = 0 · simp [hz] · exact False.elim (hnone ⟨i, hz, hiA, by omega⟩) have hint : (A ∩ B).card ≤ 1 := by simpa using card_le_card hsub have hunion : (A ∪ B).card ≤ D := by simpa using card_le_univ (A ∪ B) have hsum := card_union_add_card_inter A B omega
The integer $k = i.\text{val}$ satisfies $k < D$, $0 < k$, $(k \cdot a) \bmod D < a$, and $(k \cdot b) \bmod D \le b$.
Let $i \in \text{Fin } D$ be the nonzero witness from the previous step. Taking $k = i.\text{val}$, we have $k < D$ by construction of $\text{Fin } D$. Since $i \neq 0$, $i.\text{val} \neq 0$ (by `Fin.ext`), which implies $k > 0$ via `Nat.pos_of_ne_zero`. Rewriting $e(i)$ as $(k \cdot a) \bmod D$ and $f(i)$ as $(k \cdot b) \bmod D$ in the inequalities $e(i) < a$ and $f(i) \le b$ confirms that $(k \cdot a) \bmod D < a$ and $(k \cdot b) \bmod D \le b$.
uses
Nat.pos_of_ne_zero,Fin.extobtain ⟨i, hi, hiA, hiB⟩ := hex refine ⟨i.val, i.isLt, ?_, ?_, ?_⟩ · apply Nat.pos_of_ne_zero intro hz apply hi apply Fin.ext simpa using hz · rwa [he] at hiA · rwa [hf] at hiB
Nat.mod_lt- For any natural number $x$ and positive modulus $y$, the remainder $x \bmod y$ is strictly less than $y$.
Fin.ext- Two elements of $\text{Fin } n$ are equal if and only if their underlying natural values are equal.
congrArg- Applying a function to equal inputs yields equal outputs ($a_1 = a_2 \implies f(a_1) = f(a_2)$).
Nat.ModEq.cancel_right_of_coprime- If $c$ is coprime to $m$ and $a \cdot c \equiv b \cdot c \pmod m$, then the factor $c$ can be cancelled to obtain $a \equiv b \pmod m$.
Nat.mod_eq_of_lt- If $a < b$, then the remainder $a \bmod b$ equals $a$.
Equiv.ofBijective- A function that is both injective and surjective is a bijection (an equivalence between types).
Finite.surjective_of_injective- Any injective function from a finite type to itself is automatically surjective.
card_map- An embedding (injective map) between finite sets preserves cardinality: $|\text{map } f s| = |s|$.
Fin.card_filter_val_lt- The number of elements in $\text{Fin } n$ whose value is strictly less than $m$ is $\min(n, m)$.
min_eq_right- In a linear order, if $b \le a$ then $\min(a, b) = b$.
Nat.le_of_lt- If a natural number is strictly less than another, it is less than or equal to it ($n < m \implies n \le m$).
False.elim- From False (a contradiction), any proposition can be deduced (ex falso quodlibet).
card_le_card- If $s \subseteq t$ for finite sets $s$ and $t$, then $|s| \le |t|$.
card_le_univ- The cardinality of any finite subset of a type $\alpha$ is at most the total number of elements in $\alpha$.
card_union_add_card_inter- Principle of inclusion-exclusion for two finite sets: $|s \cup t| + |s \cap t| = |s| + |t|$.
Nat.pos_of_ne_zero- A natural number is strictly positive if and only if it is not equal to zero.
- The subset $B$ is defined using the strict inequality $< b + 1$ rather than $\le b$ so that its cardinality can be computed directly using `Fin.card_filter_val_lt`, which is formulated for strict upper bounds.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetset_option maxHeartbeats 2000000theorem coprime_residue_small_rectangle (D a b : ℕ) (hD : 0 < D) (ha : a < D) (hb : b < D) (hca : Nat.Coprime a D) (hcb : Nat.Coprime b D) (hs : D < a + b) : ∃ k : ℕ, k < D ∧ 0 < k ∧ (k * a) % D < a ∧ (k * b) % D ≤ b := by classical letI : NeZero D := ⟨by omega⟩ have make_perm : ∀ t : ℕ, Nat.Coprime t D → ∃ e : Equiv.Perm (Fin D), ∀ i, (e i).val = (i.val * t) % D := by intro t ht let f : Fin D → Fin D := fun i => ⟨(i.val * t) % D, Nat.mod_lt _ hD⟩ have hinj : Function.Injective f := by intro i j hij apply Fin.ext have hh : Nat.ModEq D (i.val * t) (j.val * t) := congrArg Fin.val hij have hc := Nat.ModEq.cancel_right_of_coprime ht.symm hh simpa only [Nat.ModEq, Nat.mod_eq_of_lt i.isLt, Nat.mod_eq_of_lt j.isLt] using hc exact ⟨Equiv.ofBijective f ⟨hinj, Finite.surjective_of_injective hinj⟩, fun _ => rfl⟩ obtain ⟨e, he⟩ := make_perm a hca obtain ⟨f, hf⟩ := make_perm b hcb let A := univ.filter fun i : Fin D => (e i).val < a let B := univ.filter fun i : Fin D => (f i).val < b + 1 have hA : A.card = a := by have hmap : A = (univ.filter fun i : Fin D => i.val < a).map e.symm.toEmbedding := by ext i simp [A] rw [hmap, card_map, Fin.card_filter_val_lt, min_eq_right (Nat.le_of_lt ha)] have hB : B.card = b + 1 := by have hmap : B = (univ.filter fun i : Fin D => i.val < b + 1).map f.symm.toEmbedding := by ext i simp [B] rw [hmap, card_map, Fin.card_filter_val_lt, min_eq_right (by omega)] have hex : ∃ i : Fin D, i ≠ 0 ∧ (e i).val < a ∧ (f i).val ≤ b := by by_contra hnone have hsub : A ∩ B ⊆ {0} := by intro i hi have hiA := (mem_filter.mp (mem_inter.mp hi).1).2 have hiB := (mem_filter.mp (mem_inter.mp hi).2).2 by_cases hz : i = 0 · simp [hz] · exact False.elim (hnone ⟨i, hz, hiA, by omega⟩) have hint : (A ∩ B).card ≤ 1 := by simpa using card_le_card hsub have hunion : (A ∪ B).card ≤ D := by simpa using card_le_univ (A ∪ B) have hsum := card_union_add_card_inter A B omega obtain ⟨i, hi, hiA, hiB⟩ := hex refine ⟨i.val, i.isLt, ?_, ?_, ?_⟩ · apply Nat.pos_of_ne_zero intro hz apply hi apply Fin.ext simpa using hz · rwa [he] at hiA · rwa [hf] at hiB