AFTD Auto-Formalizing Theoretical Domains

davenport_constant_support_four_int_box_three_ge_odd

theoremverifiedformalization

Theorem 3 of arXiv:2610.16562, odd m: for every odd m ≥ 2, the maximal length of a minimal zero-sum sequence over [[-m,m]]^3 with support of size 4 is at least 16m^3 - 16m^2 + 10m - 2.

Statement

theorem davenport_constant_support_four_int_box_three_ge_odd (m : ℕ) (hm : 2 ≤ m) (hodd : Odd m) :
    ((16 * m ^ 3 - 16 * m ^ 2 + 10 * m - 2 : ℕ) : ℕ∞) ≤
      davenport_constant_support 4 (int_box_three m)
Formalizes
arXiv:2610.16562 Theorem 3 (odd case).
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

The proof, explained

The Davenport constant with support size 4 for the box [[-m, m]]³ is bounded below by exhibiting an explicit witness sequence s = davenport_box_three_odd_sequence m of length 16m³ - 16m² + 10m - 2. The proof verifies that all vectors in s belong to [[-m, m]]³ and that its support consists of exactly 4 distinct vectors whose multiplicities are strictly positive. An existing theorem provides the minimality of s as a zero-sum sequence, and the lower bound follows by showing that this length belongs to the set whose supremum defines the Davenport constant.

  1. The target length 16m³ - 16m² + 10m - 2 belongs to the set of lengths of minimal zero-sum sequences in [[-m, m]]³ of support size 4, provided the witness sequence s satisfies the remaining subgoals.

    We define the witness sequence s = davenport_box_three_odd_sequence m. We refine the existential statement using s and supply davenport_box_three_odd_sequence_minimal to establish that s is a minimal zero-sum sequence, reducing the goal to three remaining requirements: elements of s lie in the box [[-m, m]]³, s has support size 4, and its length is the target polynomial.

    lines 4–8

    uses davenport_box_three_odd_sequence_minimal

      let s := davenport_box_three_odd_sequence m
      have hmem : ((16 * m ^ 3 - 16 * m ^ 2 + 10 * m - 2 : ℕ) : ℕ∞) ∈
          {n | ∃ s : Multiset (Fin 3 → ℤ), (∀ x ∈ s, x ∈ int_box_three m) ∧ multiset_is_minimal_zero_sum s ∧
            s.toFinset.card = 4 ∧ (Multiset.card s : ℕ∞) = n} := by
        refine ⟨s, ?_, davenport_box_three_odd_sequence_minimal m hm hodd, ?_, ?_⟩
  2. Every element of the sequence s belongs to [[-m, m]]³.

    Let x ∈ s. Unfolding s with Multiset.mem_add and Multiset.mem_replicate shows that x must be one of the four vectors v₁ = (-m, -m, -m), v₂ = (-m, m-1, m), v₃ = (m, -m, m-2), or v₄ = (m-1, m, -m). Casting m ≥ 2 to ℤ via Nat.cast_le.mpr, we check coordinate by coordinate (i ∈ {0, 1, 2}) that each component lies in [-m, m], which holds by linear integer arithmetic.

    lines 9–17

    uses Multiset.mem_add, Multiset.mem_replicate, Nat.cast_le.mpr

        · intro x hx
          dsimp [davenport_box_three_odd_sequence, s] at hx
          simp only [Multiset.mem_add, Multiset.mem_replicate] at hx
          have hmZ : (2 : ℤ) ≤ m := Nat.cast_le.mpr hm
          rcases hx with (((⟨_, rfl⟩ | ⟨_, rfl⟩) | ⟨_, rfl⟩) | ⟨_, rfl⟩)
          · intro i; fin_cases i <;> simp
          · intro i; fin_cases i <;> { simp; try omega }
          · intro i; fin_cases i <;> { simp; try omega }
          · intro i; fin_cases i <;> { simp; try omega }
  3. The multiplicities of the four vectors v₁, v₂, v₃, v₄ defining s are all non-zero.

    We define v₁ through v₄ and show that their coefficients k₁ = 4m³ - 8m² + 5m - 2, k₂ = 4m³ - 2m² + 2m, k₃ = 4m³ - 2m² + m, and k₄ = 4m³ - 4m² + 2m are non-zero. Since m ≥ 2, the leading term 4m³ dominates the quadratic terms (e.g. 8m² ≤ 4m³), making each polynomial strictly positive by non-linear arithmetic.

    lines 18–36

        · set v1 : Fin 3 → ℤ := ![-(m : ℤ), -m, -m]
          set v2 : Fin 3 → ℤ := ![-(m : ℤ), m - 1, m]
          set v3 : Fin 3 → ℤ := ![(m : ℤ), -m, m - 2]
          set v4 : Fin 3 → ℤ := ![(m : ℤ) - 1, m, -m]
          have hk1 : 4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2 ≠ 0 := by
            have : 8 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith
            have : 2 < 4 * m ^ 3 - 8 * m ^ 2 + 5 * m := by
              zify [this]
              nlinarith
            omega
          have hk2 : 4 * m ^ 3 - 2 * m ^ 2 + 2 * m ≠ 0 := by
            have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith
            omega
          have hk3 : 4 * m ^ 3 - 2 * m ^ 2 + m ≠ 0 := by
            have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith
            omega
          have hk4 : 4 * m ^ 3 - 4 * m ^ 2 + 2 * m ≠ 0 := by
            have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith
            omega
  4. The support of s equals the four-element set {v₁, v₂, v₃, v₄}.

    Expressing s as the sum of the replicated vectors and converting to a finset with Multiset.toFinset_add and Multiset.toFinset_replicate, the nonzeroness of the multiplicities (via if_neg) simplifies the support to {v₁} ∪ {v₂} ∪ {v₃} ∪ {v₄}. Extensionality confirms this is equal to {v₁, v₂, v₃, v₄}.

    lines 37–48

    uses Multiset.toFinset_add, Multiset.toFinset_replicate, if_neg

          have hS : s =
              Multiset.replicate (4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2) v1 +
              Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + 2 * m) v2 +
              Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + m) v3 +
              Multiset.replicate (4 * m ^ 3 - 4 * m ^ 2 + 2 * m) v4 := rfl
          rw [hS]
          simp only [Multiset.toFinset_add, Multiset.toFinset_replicate,
            if_neg hk1, if_neg hk2, if_neg hk3, if_neg hk4]
          have heq : ({v1} ∪ {v2} ∪ {v3} ∪ {v4} : Finset (Fin 3 → ℤ)) = {v1, v2, v3, v4} := by
            ext x
            simp
          rw [heq]
  5. The support of s has cardinality 4.

    We show that v₁, v₂, v₃, v₄ are pairwise distinct: for each of the six pairs, an equality between vectors would imply equality at a specific coordinate via congrFun, which contradicts m ≥ 2. Consequently, v₃ ∉ {v₄}, v₂ ∉ {v₃, v₄}, and v₁ ∉ {v₂, v₃, v₄}. Successive applications of Finset.card_insert_of_notMem and Finset.card_singleton establish that |{v₁, v₂, v₃, v₄}| = 4.

    lines 49–61

    uses congrFun, Finset.card_insert_of_notMem, Finset.card_singleton

          have h12 : v1 ≠ v2 := by intro h; have := congrFun h 1; simp [v1, v2] at this; omega
          have h13 : v1 ≠ v3 := by intro h; have := congrFun h 0; simp [v1, v3] at this; omega
          have h14 : v1 ≠ v4 := by intro h; have := congrFun h 1; simp [v1, v4] at this; omega
          have h23 : v2 ≠ v3 := by intro h; have := congrFun h 0; simp [v2, v3] at this; omega
          have h24 : v2 ≠ v4 := by intro h; have := congrFun h 2; simp [v2, v4] at this; omega
          have h34 : v3 ≠ v4 := by intro h; have := congrFun h 1; simp [v3, v4] at this; omega
          have h3 : v3 ∉ ({v4} : Finset (Fin 3 → ℤ)) := by simp [h34]
          have h2 : v2 ∉ ({v3, v4} : Finset (Fin 3 → ℤ)) := by simp [h23, h24]
          have h1 : v1 ∉ ({v2, v3, v4} : Finset (Fin 3 → ℤ)) := by simp [h12, h13, h14]
          rw [Finset.card_insert_of_notMem h1,
              Finset.card_insert_of_notMem h2,
              Finset.card_insert_of_notMem h3,
              Finset.card_singleton]
  6. The length of the multiset s is 16m³ - 16m² + 10m - 2.

    Rewriting by the lemma davenport_box_three_odd_sequence_card confirms that the multiset cardinality of s equals 16m³ - 16m² + 10m - 2, completing the verification of membership hypothesis hmem.

    line 62

    uses davenport_box_three_odd_sequence_card

        · rw [davenport_box_three_odd_sequence_card m hm]
  7. The Davenport constant with support 4 on [[-m, m]]³ is at least 16m³ - 16m² + 10m - 2.

    The Davenport constant is defined as the supremum of the lengths of all minimal zero-sum sequences in [[-m, m]]³ with support 4. Since the target length was proved in hmem to be achieved by s, le_sSup concludes that it is bounded above by the supremum.

    line 63

    uses le_sSup

      exact le_sSup hmem
davenport_box_three_odd_sequence_minimal
For every odd integer m ≥ 2, the sequence davenport_box_three_odd_sequence m is a minimal zero-sum sequence.
Multiset.mem_add
An element belongs to the sum of two multisets if and only if it belongs to at least one of the summands.
Multiset.mem_replicate
An element b belongs to the multiset formed by replicating a for n times if and only if n ≠ 0 and b = a.
Nat.cast_le.mpr
For natural numbers a and b, if a ≤ b then their casts to ℤ satisfy (a : ℤ) ≤ (b : ℤ).
Multiset.toFinset_add
The support (underlying finset) of the sum of two multisets is the union of their support finsets.
Multiset.toFinset_replicate
The support finset of n copies of a is {a} if n ≠ 0, and the empty set ∅ if n = 0.
if_neg
If a condition c is false, the expression (if c then t else e) evaluates to e.
congrFun
If two functions f and g are equal, their values f(a) and g(a) are equal for any input a.
Finset.card_insert_of_notMem
If an element a does not belong to a finset s, the cardinality of insert a s is |s| + 1.
Finset.card_singleton
A singleton finset {a} has cardinality 1.
davenport_box_three_odd_sequence_card
For m ≥ 2, the total length (cardinality) of davenport_box_three_odd_sequence m is 16m³ - 16m² + 10m - 2.
le_sSup
Any member of a set is less than or equal to the supremum of that set.

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 davenport_constant_support_four_int_box_three_ge_odd (m : ℕ) (hm : 2 ≤ m) (hodd : Odd m) :    ((16 * m ^ 3 - 16 * m ^ 2 + 10 * m - 2 : ℕ) : ℕ∞) ≤      davenport_constant_support 4 (int_box_three m) := by  let s := davenport_box_three_odd_sequence m  have hmem : ((16 * m ^ 3 - 16 * m ^ 2 + 10 * m - 2 : ℕ) : ℕ∞) ∈      {n | ∃ s : Multiset (Fin 3 → ℤ), (∀ x ∈ s, x ∈ int_box_three m) ∧ multiset_is_minimal_zero_sum s ∧        s.toFinset.card = 4 ∧ (Multiset.card s : ℕ∞) = n} := by    refine ⟨s, ?_, davenport_box_three_odd_sequence_minimal m hm hodd, ?_, ?_⟩    · intro x hx      dsimp [davenport_box_three_odd_sequence, s] at hx      simp only [Multiset.mem_add, Multiset.mem_replicate] at hx      have hmZ : (2 : ℤ) ≤ m := Nat.cast_le.mpr hm      rcases hx with (((⟨_, rfl⟩ | ⟨_, rfl⟩) | ⟨_, rfl⟩) | ⟨_, rfl⟩)      · intro i; fin_cases i <;> simp      · intro i; fin_cases i <;> { simp; try omega }      · intro i; fin_cases i <;> { simp; try omega }      · intro i; fin_cases i <;> { simp; try omega }    · set v1 : Fin 3 → ℤ := ![-(m : ℤ), -m, -m]      set v2 : Fin 3 → ℤ := ![-(m : ℤ), m - 1, m]      set v3 : Fin 3 → ℤ := ![(m : ℤ), -m, m - 2]      set v4 : Fin 3 → ℤ := ![(m : ℤ) - 1, m, -m]      have hk1 : 4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2 ≠ 0 := by        have : 8 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith        have : 2 < 4 * m ^ 3 - 8 * m ^ 2 + 5 * m := by          zify [this]          nlinarith        omega      have hk2 : 4 * m ^ 3 - 2 * m ^ 2 + 2 * m ≠ 0 := by        have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith        omega      have hk3 : 4 * m ^ 3 - 2 * m ^ 2 + m ≠ 0 := by        have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith        omega      have hk4 : 4 * m ^ 3 - 4 * m ^ 2 + 2 * m ≠ 0 := by        have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith        omega      have hS : s =          Multiset.replicate (4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2) v1 +          Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + 2 * m) v2 +          Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + m) v3 +          Multiset.replicate (4 * m ^ 3 - 4 * m ^ 2 + 2 * m) v4 := rfl      rw [hS]      simp only [Multiset.toFinset_add, Multiset.toFinset_replicate,        if_neg hk1, if_neg hk2, if_neg hk3, if_neg hk4]      have heq : ({v1} ∪ {v2} ∪ {v3} ∪ {v4} : Finset (Fin 3 → ℤ)) = {v1, v2, v3, v4} := by        ext x        simp      rw [heq]      have h12 : v1 ≠ v2 := by intro h; have := congrFun h 1; simp [v1, v2] at this; omega      have h13 : v1 ≠ v3 := by intro h; have := congrFun h 0; simp [v1, v3] at this; omega      have h14 : v1 ≠ v4 := by intro h; have := congrFun h 1; simp [v1, v4] at this; omega      have h23 : v2 ≠ v3 := by intro h; have := congrFun h 0; simp [v2, v3] at this; omega      have h24 : v2 ≠ v4 := by intro h; have := congrFun h 2; simp [v2, v4] at this; omega      have h34 : v3 ≠ v4 := by intro h; have := congrFun h 1; simp [v3, v4] at this; omega      have h3 : v3 ∉ ({v4} : Finset (Fin 3 → ℤ)) := by simp [h34]      have h2 : v2 ∉ ({v3, v4} : Finset (Fin 3 → ℤ)) := by simp [h23, h24]      have h1 : v1 ∉ ({v2, v3, v4} : Finset (Fin 3 → ℤ)) := by simp [h12, h13, h14]      rw [Finset.card_insert_of_notMem h1,          Finset.card_insert_of_notMem h2,          Finset.card_insert_of_notMem h3,          Finset.card_singleton]    · rw [davenport_box_three_odd_sequence_card m hm]  exact le_sSup hmem
See it in the graphDiscuss this resultChallenge it