AFTD Auto-Formalizing Theoretical Domains

coprime_residue_small_rectangle

theoremverified

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.

  1. 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$.

    lines 8–9

      classical
      letI : NeZero D := ⟨by omega⟩
  2. 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$.

    lines 10–20

    uses Nat.mod_lt, Fin.ext, congrArg, Nat.ModEq.cancel_right_of_coprime, Nat.mod_eq_of_lt, Equiv.ofBijective, Finite.surjective_of_injective

      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⟩
  3. 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.

    lines 21–24

      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
  4. 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$.

    lines 25–29

    uses card_map, Fin.card_filter_val_lt, min_eq_right, Nat.le_of_lt

      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)]
  5. 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$.

    lines 30–34

    uses card_map, Fin.card_filter_val_lt, min_eq_right

      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)]
  6. 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$.

    lines 35–47

    uses False.elim, card_le_card, card_le_univ, card_union_add_card_inter

      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
  7. 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$.

    lines 48–56

    uses Nat.pos_of_ne_zero, Fin.ext

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it