AFTD Auto-Formalizing Theoretical Domains

integer_box_completion_card_le

theoremverified

An admissible integer vector family with the full-box completion property has at most r(n-1) terms.

Statement

theorem integer_box_completion_card_le {ι : Type*} [Fintype ι] [DecidableEq ι]
    (n r : ℕ) (hn : 1 < n) (a : ι → Fin r → ℤ)
    (ha : ∀ i, ∃ j, ¬ (n : ℤ) ∣ a i j)
    (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) :
    Fintype.card ι ≤ r * (n - 1)
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
Used by 2

The proof, explained

The proof establishes the cardinality bound |ι| ≤ r(n - 1) by reducing to finite_array_card_le_of_subset_square_mod_lt, a known bound for natural-number vector arrays. We construct non-negative vectors v by setting v i j = (-a i j) % n^2. The three required conditions—that coordinates are bounded by n, that each vector is non-zero, and that all subset sums modulo n^2 are strictly less than n—are verified using the admissibility condition ha together with the singleton and general cases of integer_box_completion_subset_emod_lt.

  1. Define a natural-number vector array v by v i j = (-a i j % n^2) and verify that its integer cast matches this remainder.

    We define v : ι → Fin r → ℕ by taking the remainder (-a i j) % n^2 and converting it to a natural number. Since 1 < n, n^2 is non-zero, so the integer remainder is non-negative by Int.emod_nonneg. Converting a non-negative integer to ℕ via Int.toNat_of_nonneg preserves its value, establishing that the integer cast of v i j is canonically equal to (-a i j) % n^2 (hcanon).

    lines 9–13

    uses Int.toNat_of_nonneg, Int.emod_nonneg

      let v : ι → Fin r → ℕ := fun i j => ((-a i j) % (n : ℤ) ^ 2).toNat
      have hnz : (1 : ℤ) < n := by exact_mod_cast hn
      have hcanon : ∀ i j, (v i j : ℤ) = (-a i j) % (n : ℤ) ^ 2 := by
        intro i j
        exact Int.toNat_of_nonneg (Int.emod_nonneg _ (by positivity))
  2. Each coordinate v i j satisfies v i j < n.

    Applying the helper lemma integer_box_completion_subset_emod_lt to the singleton subset {i} and coordinate j gives (-∑ k ∈ {i}, a k j) % n^2 < n. Simplifying the singleton sum with Finset.sum_singleton yields (-a i j) % n^2 < n. Replacing this remainder with the integer cast of v i j via hcanon and casting to ℕ establishes v i j < n.

    lines 14–19

    uses integer_box_completion_subset_emod_lt, Finset.sum_singleton

      have hsmall : ∀ i j, v i j < n := by
        intro i j
        have h := integer_box_completion_subset_emod_lt n r hn a hbad {i} j
        simp only [Finset.sum_singleton] at h
        rw [← hcanon i j] at h
        exact_mod_cast h
  3. For every index i, the sum of coordinates ∑ j, v i j is strictly positive.

    By the admissibility hypothesis ha, for each i there is a coordinate j such that n does not divide a i j. If v i j were zero, then (-a i j) % n^2 = 0 by hcanon, which implies n^2 ∣ -a i j by Int.dvd_of_emod_eq_zero. Since n ∣ n^2 (via pow_two and dvd_mul_right), transitivity dvd_trans would imply n ∣ -a i j, and hence n ∣ a i j by dvd_neg.mpr, a contradiction. Thus v i j > 0. Since every coordinate of v is non-negative (Nat.zero_le), Finset.single_le_sum and Finset.mem_univ show that the sum over all coordinates is bounded below by v i j > 0, giving strict positivity by lt_of_lt_of_le.

    lines 20–30

    uses Int.dvd_of_emod_eq_zero, pow_two, dvd_mul_right, dvd_neg.mpr, dvd_trans, lt_of_lt_of_le, Finset.single_le_sum, Nat.zero_le, Finset.mem_univ

      have hpos : ∀ i, 0 < ∑ j, v i j := by
        intro i
        obtain ⟨j, hj⟩ := ha i
        have hv : 0 < v i j := by
          by_contra h
          have hz : v i j = 0 := by omega
          have hem : (-a i j) % (n : ℤ) ^ 2 = 0 := by simpa [hz] using (hcanon i j).symm
          have hd : (n : ℤ) ^ 2 ∣ -a i j := Int.dvd_of_emod_eq_zero hem
          have hdn : (n : ℤ) ∣ (n : ℤ) ^ 2 := by simpa [pow_two] using (dvd_mul_right (n : ℤ) (n : ℤ))
          exact hj (by simpa using dvd_neg.mpr (dvd_trans hdn hd))
        exact lt_of_lt_of_le hv (Finset.single_le_sum (fun j _ => Nat.zero_le (v i j)) (Finset.mem_univ j))
  4. It suffices to show that for every subset s ⊆ ι and coordinate j, the subset sum modulo n^2 satisfies (∑ i ∈ s, v i j) % n^2 < n.

    We apply finite_array_card_le_of_subset_square_mod_lt. Having shown that 1 < n, that all coordinates satisfy v i j < n, and that each vector has a positive sum ∑ j, v i j > 0, this lemma reduces the goal Fintype.card ι ≤ r * (n - 1) to bounding the subset sums of v modulo n^2.

    line 31

    uses finite_array_card_le_of_subset_square_mod_lt

      apply finite_array_card_le_of_subset_square_mod_lt n r hn v hsmall hpos
  5. For any subset s ⊆ ι and coordinate j, the sum of v modulo n^2 equals the negation of the sum of a modulo n^2.

    We proceed by induction on s using Finset.induction_on. For the empty set, both sides are 0. For the inductive step insert i s with i ∉ s, the component v i j is congruent to -a i j modulo n^2 by definition and Int.emod_emod. Adding this congruence to the induction hypothesis and rewriting the sums using Finset.sum_insert and neg_add proves that the equality of remainders holds for insert i s.

    lines 32–42

    uses Finset.induction_on, Int.emod_emod, Finset.sum_insert, neg_add

      intro s j
      have he : (∑ i ∈ s, (v i j : ℤ)) % (n : ℤ) ^ 2 =
          (-∑ i ∈ s, a i j) % (n : ℤ) ^ 2 := by
        induction s using Finset.induction_on with
        | empty => simp
        | @insert i s hi ih =>
          have hi' : (v i j : ℤ) ≡ -a i j [ZMOD (n : ℤ) ^ 2] := by
            change (v i j : ℤ) % (n : ℤ) ^ 2 = (-a i j) % (n : ℤ) ^ 2
            rw [hcanon, Int.emod_emod]
          have hs' : (∑ i ∈ s, (v i j : ℤ)) ≡ -∑ i ∈ s, a i j [ZMOD (n : ℤ) ^ 2] := ih
          simpa only [Finset.sum_insert hi, neg_add] using (hi'.add hs').eq
  6. The subset sum of v modulo n^2 satisfies (∑ i ∈ s, v i j) % n^2 < n, completing the proof.

    The full-box completion property integer_box_completion_subset_emod_lt gives (-∑ i ∈ s, a i j) % n^2 < n. Replacing this with the sum of v using the modular equality just proved, and moving between ℤ and ℕ, gives the required bound (∑ i ∈ s, v i j) % n^2 < n.

    lines 43–48

    uses integer_box_completion_subset_emod_lt

      have hb := integer_box_completion_subset_emod_lt n r hn a hbad s j
      rw [← he] at hb
      have hc : (((∑ i ∈ s, v i j) % n ^ 2 : ℕ) : ℤ) =
          (∑ i ∈ s, (v i j : ℤ)) % (n : ℤ) ^ 2 := by simp
      rw [← hc] at hb
      exact_mod_cast hb
Int.toNat_of_nonneg
For any non-negative integer a, casting its non-negative conversion a.toNat back to ℤ yields a.
Int.emod_nonneg
For any integer a and non-zero integer b, the remainder a % b is non-negative.
integer_box_completion_subset_emod_lt
Under the full-box completion property, for any finite subset of indices s and coordinate j, the remainder (-∑ i ∈ s, a i j) % n^2 is strictly less than n.
Finset.sum_singleton
The sum of a function over a singleton set {a} equals the value of the function at a.
Int.dvd_of_emod_eq_zero
If the integer remainder of b modulo a is zero, then a divides b.
pow_two
The square of an element equals the element multiplied by itself (a ^ 2 = a * a).
dvd_mul_right
An element divides its product with any other element on the right (a ∣ a * b).
dvd_neg.mpr
If a divides b, then a divides -b.
dvd_trans
Divisibility is transitive: if a ∣ b and b ∣ c, then a ∣ c.
lt_of_lt_of_le
If a < b and b ≤ c, then a < c.
Finset.single_le_sum
In a finite sum of non-negative elements, any single summand is bounded above by the total sum.
Nat.zero_le
Every natural number is greater than or equal to zero.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
finite_array_card_le_of_subset_square_mod_lt
A family of non-negative vectors in ℕ^r indexed by a finite type ι has size at most r(n - 1), provided each coordinate is less than n, each vector has a positive sum, and every subset sum modulo n^2 is less than n.
Finset.induction_on
A property holds for all finite sets if it holds for the empty set and is preserved when inserting a new element.
Int.emod_emod
Taking the integer remainder modulo b is idempotent: (a % b) % b = a % b.
Finset.sum_insert
The sum of a function over insert a s equals f a + ∑ x ∈ s, f x, provided a ∉ s.
neg_add
The negation of a sum equals the sum of the negations: -(a + b) = -a + -b.

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_card_le {ι : Type*} [Fintype ι] [DecidableEq ι]    (n r : ℕ) (hn : 1 < n) (a : ι → Fin r → ℤ)    (ha : ∀ i, ∃ j, ¬ (n : ℤ) ∣ a i j)    (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) :    Fintype.card ι ≤ r * (n - 1) := by  let v : ι → Fin r → ℕ := fun i j => ((-a i j) % (n : ℤ) ^ 2).toNat  have hnz : (1 : ℤ) < n := by exact_mod_cast hn  have hcanon : ∀ i j, (v i j : ℤ) = (-a i j) % (n : ℤ) ^ 2 := by    intro i j    exact Int.toNat_of_nonneg (Int.emod_nonneg _ (by positivity))  have hsmall : ∀ i j, v i j < n := by    intro i j    have h := integer_box_completion_subset_emod_lt n r hn a hbad {i} j    simp only [Finset.sum_singleton] at h    rw [← hcanon i j] at h    exact_mod_cast h  have hpos : ∀ i, 0 < ∑ j, v i j := by    intro i    obtain ⟨j, hj⟩ := ha i    have hv : 0 < v i j := by      by_contra h      have hz : v i j = 0 := by omega      have hem : (-a i j) % (n : ℤ) ^ 2 = 0 := by simpa [hz] using (hcanon i j).symm      have hd : (n : ℤ) ^ 2 ∣ -a i j := Int.dvd_of_emod_eq_zero hem      have hdn : (n : ℤ) ∣ (n : ℤ) ^ 2 := by simpa [pow_two] using (dvd_mul_right (n : ℤ) (n : ℤ))      exact hj (by simpa using dvd_neg.mpr (dvd_trans hdn hd))    exact lt_of_lt_of_le hv (Finset.single_le_sum (fun j _ => Nat.zero_le (v i j)) (Finset.mem_univ j))  apply finite_array_card_le_of_subset_square_mod_lt n r hn v hsmall hpos  intro s j  have he : (∑ i ∈ s, (v i j : ℤ)) % (n : ℤ) ^ 2 =      (-∑ i ∈ s, a i j) % (n : ℤ) ^ 2 := by    induction s using Finset.induction_on with    | empty => simp    | @insert i s hi ih =>      have hi' : (v i j : ℤ) ≡ -a i j [ZMOD (n : ℤ) ^ 2] := by        change (v i j : ℤ) % (n : ℤ) ^ 2 = (-a i j) % (n : ℤ) ^ 2        rw [hcanon, Int.emod_emod]      have hs' : (∑ i ∈ s, (v i j : ℤ)) ≡ -∑ i ∈ s, a i j [ZMOD (n : ℤ) ^ 2] := ih      simpa only [Finset.sum_insert hi, neg_add] using (hi'.add hs').eq  have hb := integer_box_completion_subset_emod_lt n r hn a hbad s j  rw [← he] at hb  have hc : (((∑ i ∈ s, v i j) % n ^ 2 : ℕ) : ℤ) =      (∑ i ∈ s, (v i j : ℤ)) % (n : ℤ) ^ 2 := by simp  rw [← hc] at hb  exact_mod_cast hb
See it in the graphDiscuss this resultChallenge it