AFTD Auto-Formalizing Theoretical Domains

integer_box_completion_subset_emod_lt

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

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

    lines 8–10

      intro s j
      let c : Fin r → ℤ := fun j => (-∑ i ∈ s, a i j) % n
      have hnz : (1 : ℤ) < n := by exact_mod_cast hn
  2. 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.

    lines 11–13

    uses Int.emod_nonneg, Int.emod_lt_of_pos

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

    lines 14–17

    uses Int.mod_modEq, sub_neg_eq_add

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

    lines 18–22

    uses Int.modEq_iff_dvd.mpr, sub_neg_eq_add, Int.emod_eq_of_lt

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

    lines 23–24

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

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

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