integer_box_completion_subset_emod_lt
If every subset completed by an integer vector in the box [0,n-1]^r that vanishes modulo n also vanishes modulo n squared, each negative subset-sum coordinate has residue below n modulo n squared.
Statement
theorem integer_box_completion_subset_emod_lt {ι : Type*} [DecidableEq ι] (n r : ℕ) (hn : 1 < n) (a : ι → Fin r → ℤ) (hbad : ∀ s : Finset ι, ∀ c : Fin r → ℤ, (∀ j, 0 ≤ c j ∧ c j < n) → (∀ j, (n : ℤ) ∣ c j + ∑ i ∈ s, a i j) → ∀ j, (n : ℤ) ^ 2 ∣ c j + ∑ i ∈ s, a i j) : ∀ s : Finset ι, ∀ j, (-∑ i ∈ s, a i j) % (n : ℤ) ^ 2 < n
- Source
- Supporting lemmas for OP-259, arXiv:2610.19965 Question 3.1, deep session IN-185. This is the restricted full-box completion route; no claim that an arbitrary long bad sequence contains such a box.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- integer_box_completion_card_leAn admissible integer vector family with the full-box completion property has at most r(n-1) terms.
The proof, explained
To show that (-∑ i ∈ s, a i j) % n^2 < n, we define a completing vector c whose coordinates are the standard remainders (-∑ i ∈ s, a i j') % n. By construction, c lies in the box [0, n - 1]^r and completes the subset sum to a multiple of n in every coordinate. The hypothesis hbad then elevates this to divisibility by n^2, which forces -∑ i ∈ s, a i j ≡ c(j) [ZMOD n^2]. Because 0 ≤ c(j) < n < n^2, c(j) is already reduced modulo n^2, so the residue modulo n^2 is equal to c(j) and therefore strictly less than n.
Fix a subset s and a coordinate index j, and define the candidate box vector c.
We introduce the arbitrary subset s and coordinate j. We then define the vector c : Fin r → ℤ coordinatewise by setting each coordinate c(j') to (-∑ i ∈ s, a i j') % n. We also record that 1 < n holds in the integers.
intro s j let c : Fin r → ℤ := fun j => (-∑ i ∈ s, a i j) % n have hnz : (1 : ℤ) < n := by exact_mod_cast hn
The vector c lies in the box [0, n - 1]^r, meaning 0 ≤ c(j') < n for all coordinates j'.
For each coordinate j', since n > 1 > 0, Int.emod_nonneg gives 0 ≤ c(j') and Int.emod_lt_of_pos gives c(j') < n. The positivity and non-zero conditions on n are proved from 1 < n by omega.
uses
Int.emod_nonneg,Int.emod_lt_of_poshave hc : ∀ j, 0 ≤ c j ∧ c j < n := by intro j exact ⟨Int.emod_nonneg _ (by omega), Int.emod_lt_of_pos _ (by omega)⟩
For every coordinate j', n divides the completed sum c(j') + ∑ i ∈ s, a i j'.
By Int.mod_modEq, (-∑ a) % n ≡ -∑ a [ZMOD n], so n divides the difference ((-∑ a) % n) - (-∑ a). By definition of c and sub_neg_eq_add, this difference is c(j') + ∑ i ∈ s, a i j'.
uses
Int.mod_modEq,sub_neg_eq_addhave hd : ∀ j, (n : ℤ) ∣ c j + ∑ i ∈ s, a i j := by intro j have h := (Int.mod_modEq (-∑ i ∈ s, a i j) (n : ℤ)).symm.dvd simpa [c, sub_neg_eq_add] using h
The residue (-∑ i ∈ s, a i j) % n^2 is equal to c(j).
Because c is in the box and c + ∑ a is coordinatewise divisible by n, the hypothesis hbad implies that n^2 divides c(j) + ∑ i ∈ s, a i j = c(j) - (-∑ i ∈ s, a i j). By Int.modEq_iff_dvd.mpr, this means -∑ i ∈ s, a i j ≡ c(j) [ZMOD n^2]. Since 0 ≤ c(j) < n and n > 1, we have c(j) < n^2, so c(j) % n^2 = c(j) by Int.emod_eq_of_lt. Congruence then implies (-∑ i ∈ s, a i j) % n^2 = c(j).
uses
Int.modEq_iff_dvd.mpr,sub_neg_eq_add,Int.emod_eq_of_lthave hd2 := hbad s c hc hd j have he : (-∑ i ∈ s, a i j) % (n : ℤ) ^ 2 = c j := by have hm : (-∑ i ∈ s, a i j) ≡ c j [ZMOD (n : ℤ) ^ 2] := Int.modEq_iff_dvd.mpr (by simpa [sub_neg_eq_add] using hd2) exact hm.eq.trans (Int.emod_eq_of_lt (hc j).1 (by have := (hc j).2; nlinarith))
The residue (-∑ i ∈ s, a i j) % n^2 is strictly less than n.
Replacing (-∑ i ∈ s, a i j) % n^2 with c(j) reduces the goal to c(j) < n, which was established when verifying that c belongs to the box.
rw [he] exact (hc j).2
Int.emod_nonneg- For integers a and b with b ≠ 0, the remainder a % b is non-negative (0 ≤ a % b).
Int.emod_lt_of_pos- For integers a and b with 0 < b, the remainder a % b is strictly less than b.
Int.mod_modEq- An integer a % n is congruent to a modulo n.
sub_neg_eq_add- Subtracting a negation is addition: a - (-b) = a + b.
Int.modEq_iff_dvd.mpr- If n divides b - a, then a is congruent to b modulo n (a ≡ b [ZMOD n]).
Int.emod_eq_of_lt- If an integer a satisfies 0 ≤ a and a < b, then its remainder modulo b is a itself (a % b = a).
- The arithmetic obligations n > 0 and c(j) < n^2 are closed automatically by omega and nlinarith using 1 < n and 0 ≤ c(j) < n.
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.
theorem integer_box_completion_subset_emod_lt {ι : Type*} [DecidableEq ι] (n r : ℕ) (hn : 1 < n) (a : ι → Fin r → ℤ) (hbad : ∀ s : Finset ι, ∀ c : Fin r → ℤ, (∀ j, 0 ≤ c j ∧ c j < n) → (∀ j, (n : ℤ) ∣ c j + ∑ i ∈ s, a i j) → ∀ j, (n : ℤ) ^ 2 ∣ c j + ∑ i ∈ s, a i j) : ∀ s : Finset ι, ∀ j, (-∑ i ∈ s, a i j) % (n : ℤ) ^ 2 < n := by intro s j let c : Fin r → ℤ := fun j => (-∑ i ∈ s, a i j) % n have hnz : (1 : ℤ) < n := by exact_mod_cast hn have hc : ∀ j, 0 ≤ c j ∧ c j < n := by intro j exact ⟨Int.emod_nonneg _ (by omega), Int.emod_lt_of_pos _ (by omega)⟩ have hd : ∀ j, (n : ℤ) ∣ c j + ∑ i ∈ s, a i j := by intro j have h := (Int.mod_modEq (-∑ i ∈ s, a i j) (n : ℤ)).symm.dvd simpa [c, sub_neg_eq_add] using h have hd2 := hbad s c hc hd j have he : (-∑ i ∈ s, a i j) % (n : ℤ) ^ 2 = c j := by have hm : (-∑ i ∈ s, a i j) ≡ c j [ZMOD (n : ℤ) ^ 2] := Int.modEq_iff_dvd.mpr (by simpa [sub_neg_eq_add] using hd2) exact hm.eq.trans (Int.emod_eq_of_lt (hc j).1 (by have := (hc j).2; nlinarith)) rw [he] exact (hc j).2