AFTD Auto-Formalizing Theoretical Domains

davenport_constant_support_four_int_box_three_ge_even

theoremverifiedformalization

Theorem 3 of arXiv:2610.16562, even m: for every even 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 + 8m - 1.

Statement

theorem davenport_constant_support_four_int_box_three_ge_even (m : ℕ) (hm : 2 ≤ m) (heven : Even m) :
    ((16 * m ^ 3 - 16 * m ^ 2 + 8 * m - 1 : ℕ) : ℕ∞) ≤
      davenport_constant_support 4 (int_box_three m)
Formalizes
arXiv:2610.16562 Theorem 3 (even case).
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

The proof, explained

The proof establishes the lower bound by exhibiting an explicit sequence s (defined as `davenport_box_three_even_sequence m`) of vectors in [[-m, m]]³. The sequence is composed of four distinct vectors with positive multiplicities that sum to 16m³ - 16m² + 8m - 1. With minimality of s supplied by a companion lemma, the proof verifies that each vector is in [[-m, m]]³, that all four multiplicities are non-zero, and that the vectors are pairwise distinct, showing that the support has size 4. Consequently, this length belongs to the set whose supremum defines the Davenport constant, yielding the desired lower bound.

  1. The candidate length 16m³ - 16m² + 8m - 1 belongs to the set of lengths of 4-supported minimal zero-sum sequences in [[-m, m]]³, provided the explicit sequence s satisfies the required conditions.

    We let s be the explicit multiset `davenport_box_three_even_sequence m` and show that 16m³ - 16m² + 8m - 1 is in the set of lengths defining the Davenport constant by witnessing it with s. Minimality of s as a zero-sum sequence is supplied by `davenport_box_three_even_sequence_minimal`, leaving three subgoals: showing all elements of s are in [[-m, m]]³, that s has support of size 4, and that the cardinality of s equals 16m³ - 16m² + 8m - 1.

    lines 4–8

    uses davenport_box_three_even_sequence_minimal

      let s := davenport_box_three_even_sequence m
      have hmem : ((16 * m ^ 3 - 16 * m ^ 2 + 8 * m - 1 : ℕ) : ℕ∞) ∈
          {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_even_sequence_minimal m hm heven, ?_, ?_⟩
  2. Every vector appearing in s has all coordinates in the interval [-m, m].

    Since s is a sum of replicate multisets, any element x ∈ s must be one of the four vectors defining s. For each of the four vectors, we check that each coordinate index i ∈ {0, 1, 2} has its value bounded between -m and m using coordinate case analysis and integer linear arithmetic.

    lines 9–17

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

        · intro x hx
          dsimp [davenport_box_three_even_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 four constituent vectors v₁, v₂, v₃, v₄ have strictly positive multiplicities in s.

    We name the four vectors v₁ = (-m, -m, -m), v₂ = (-m, m - 1, m), v₃ = (m, -(m - 1), m - 1), and v₄ = (m - 1, m, -m). For m ≥ 2, non-linear arithmetic shows that each of the four polynomial coefficients (4m³ - 6m² + 4m - 1, 4m³ - 4m² + 2m, 4m³ - 2m² + m, and 4m³ - 4m² + m) is strictly positive, hence non-zero.

    lines 18–36

        · set v1 : Fin 3 → ℤ := ![-(m : ℤ), -m, -m]
          set v2 : Fin 3 → ℤ := ![-(m : ℤ), m - 1, m]
          set v3 : Fin 3 → ℤ := ![(m : ℤ), -(m - 1), m - 1]
          set v4 : Fin 3 → ℤ := ![(m : ℤ) - 1, m, -m]
          have hk1 : 4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1 ≠ 0 := by
            have : 6 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith
            have : 1 < 4 * m ^ 3 - 6 * m ^ 2 + 4 * m := by
              zify [this]
              nlinarith
            omega
          have hk2 : 4 * m ^ 3 - 4 * m ^ 2 + 2 * m ≠ 0 := by
            have : 4 * 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 + m ≠ 0 := by
            have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith
            omega
  4. The support set of s is {v₁, v₂, v₃, v₄}.

    Unfolding s as a sum of four replicates, since all four multiplicities are non-zero, the support of each replicate multiset is the singleton {vᵢ}. The support of the sum of multisets is the union of their supports, yielding {v₁} ∪ {v₂} ∪ {v₃} ∪ {v₄} = {v₁, v₂, v₃, v₄}.

    lines 37–48

    uses Multiset.toFinset_add, Multiset.toFinset_replicate, if_neg

          have hS : s =
              Multiset.replicate (4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1) v1 +
              Multiset.replicate (4 * m ^ 3 - 4 * m ^ 2 + 2 * m) v2 +
              Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + m) v3 +
              Multiset.replicate (4 * m ^ 3 - 4 * m ^ 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 vectors v₁, v₂, v₃, v₄ are pairwise distinct, so the support set has cardinality 4.

    For each pair of vectors, assuming they are equal leads to a contradiction by evaluating at a coordinate where they differ. Using these distinctness relations, we see that v₃ ∉ {v₄}, v₂ ∉ {v₃, v₄}, and v₁ ∉ {v₂, v₃, v₄}, and build up the cardinality of {v₁, v₂, v₃, v₄} to 4 by repeated singleton insertions.

    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 multiset s has cardinality 16m³ - 16m² + 8m - 1.

    Applying the lemma `davenport_box_three_even_sequence_card` computes the sum of the four multiplicities to be exactly 16m³ - 16m² + 8m - 1.

    line 62

    uses davenport_box_three_even_sequence_card

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

    The Davenport constant is defined as the supremum of the lengths of valid sequences. Having exhibited s in the set of candidate lengths, `le_sSup` shows that this value is bounded above by the supremum.

    line 63

    uses le_sSup

      exact le_sSup hmem
davenport_box_three_even_sequence_minimal
For any even integer m ≥ 2, `davenport_box_three_even_sequence m` is a minimal zero-sum multiset.
Multiset.mem_add
An element belongs to the sum of two multisets if and only if it belongs to at least one of them.
Multiset.mem_replicate
An element belongs to n copies of a if and only if n ≠ 0 and the element equals a.
Nat.cast_le.mpr
An inequality between natural numbers carries over when they are cast to integers.
Multiset.toFinset_add
The support (set of distinct elements) of the sum of two multisets is the union of their supports.
Multiset.toFinset_replicate
The support of n copies of a is {a} if n ≠ 0, and ∅ if n = 0.
if_neg
If a condition is false, an if-then-else expression evaluates to its else branch.
congrFun
Equal functions evaluate to equal values on any argument.
Finset.card_insert_of_notMem
Inserting an element into a finite set not containing it increases its cardinality by 1.
Finset.card_singleton
A singleton finite set has cardinality 1.
davenport_box_three_even_sequence_card
For m ≥ 2, the total length (cardinality with multiplicity) of `davenport_box_three_even_sequence m` equals 16m³ - 16m² + 8m - 1.
le_sSup
Any element of a set is less than or equal to the supremum of the 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_even (m : ℕ) (hm : 2 ≤ m) (heven : Even m) :    ((16 * m ^ 3 - 16 * m ^ 2 + 8 * m - 1 : ℕ) : ℕ∞) ≤      davenport_constant_support 4 (int_box_three m) := by  let s := davenport_box_three_even_sequence m  have hmem : ((16 * m ^ 3 - 16 * m ^ 2 + 8 * m - 1 : ℕ) : ℕ∞) ∈      {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_even_sequence_minimal m hm heven, ?_, ?_⟩    · intro x hx      dsimp [davenport_box_three_even_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 - 1), m - 1]      set v4 : Fin 3 → ℤ := ![(m : ℤ) - 1, m, -m]      have hk1 : 4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1 ≠ 0 := by        have : 6 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith        have : 1 < 4 * m ^ 3 - 6 * m ^ 2 + 4 * m := by          zify [this]          nlinarith        omega      have hk2 : 4 * m ^ 3 - 4 * m ^ 2 + 2 * m ≠ 0 := by        have : 4 * 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 + m ≠ 0 := by        have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith        omega      have hS : s =          Multiset.replicate (4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1) v1 +          Multiset.replicate (4 * m ^ 3 - 4 * m ^ 2 + 2 * m) v2 +          Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + m) v3 +          Multiset.replicate (4 * m ^ 3 - 4 * m ^ 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_even_sequence_card m hm]  exact le_sSup hmem
See it in the graphDiscuss this resultChallenge it