AFTD Auto-Formalizing Theoretical Domains

finset_card_ge_one_add_clog_of_midpoint_balanced

theoremverifiedformalization

For a prime p, every nonempty balanced subset B of Z/pZ has |B| ≥ 1 + ⌈log₂ p⌉.

Statement

theorem finset_card_ge_one_add_clog_of_midpoint_balanced {p : ℕ} [Fact p.Prime]
    (B : Finset (ZMod p)) (hB : finset_is_midpoint_balanced B) : 1 + Nat.clog 2 p ≤ B.card
Formalizes
arXiv:2610.09349 (A near-quadratic lower bound for sets with no unique sums), Lemma B.1 (second statement), proved there by a determinant argument on the midpoint-certificate matrix (rows 2e_i − e_{u_i} − e_{v_i}) with the unit-incidence minor lemma (Lemma 2.2).
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1
  • nus_min_card_ge_one_add_clogFor an odd prime p, m(p) ≥ 1 + ⌈log₂ p⌉: every subset of Z/pZ with no unique sums has at least 1 + ⌈log₂ p⌉ elements.

The proof, explained

A midpoint-balanced subset B of Z/pZ induces linear midpoint relations among k + 1 ≤ |B| elements. A non-zero k × k minor of this relation matrix yields an integer determinant D ≠ 0 that satisfies |D| ≤ 2^k and is divisible by p. Because D is non-zero, this forces p ≤ |D| ≤ 2^k, which is equivalent to ⌈log₂ p⌉ ≤ k, and therefore 1 + ⌈log₂ p⌉ ≤ k + 1 ≤ |B|.

  1. There exist k ≥ 1 with k + 1 ≤ |B| and a k × k submatrix M of the midpoint certificate matrix whose determinant D is non-zero.

    Applying finset_midpoint_balanced_exists_nonzero_minor to the midpoint-balanced set B produces k + 1 distinct points in B satisfying the midpoint relations, together with indices i₀ and j₀ deleting which yields a k × k minor M with non-zero determinant D = det M.

    lines 3–9

    uses finset_midpoint_balanced_exists_nonzero_minor

      obtain ⟨k, hk0, hk, u, v, b, hinj, hmid, i₀, j₀, hdet_ne⟩ :=
        finset_midpoint_balanced_exists_nonzero_minor B hB
      let M := (Matrix.of fun (i j : Fin (k + 1)) =>
        (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix
        i₀.succAbove j₀.succAbove
      let D := M.det
      have hD_ne : D ≠ 0 := hdet_ne
  2. |D| ≤ 2^k and p divides D in ℤ.

    By midpoint_certificate_matrix_minor_abs_le, the absolute value of the determinant of any such minor is bounded by 2^k. Furthermore, since the points satisfy the midpoint equations modulo p, the prime p divides D by midpoint_certificate_matrix_minor_dvd_p.

    lines 10–11

    uses midpoint_certificate_matrix_minor_abs_le, midpoint_certificate_matrix_minor_dvd_p

      have hle : |D| ≤ (2 ^ k : ℤ) := midpoint_certificate_matrix_minor_abs_le u v i₀ j₀
      have hdvd : (p : ℤ) ∣ D := midpoint_certificate_matrix_minor_dvd_p hk0 u v b hinj hmid i₀ j₀
  3. p ≤ |D| as natural numbers.

    Since D ≠ 0, its absolute value |D| is positive by Int.natAbs_pos.mpr. Because p divides D in ℤ, p divides the natural absolute value |D| by Int.ofNat_dvd_left.mp. A positive natural number divisible by p is at least p by Nat.le_of_dvd.

    lines 12–14

    uses Int.natAbs_pos.mpr, Int.ofNat_dvd_left.mp, Nat.le_of_dvd

      have hpos : 0 < D.natAbs := Int.natAbs_pos.mpr hD_ne
      have hdvd' : p ∣ D.natAbs := Int.ofNat_dvd_left.mp hdvd
      have hp_le_D : p ≤ D.natAbs := Nat.le_of_dvd hpos hdvd'
  4. |D| ≤ 2^k holds as an inequality of natural numbers.

    Casting |D| to ℤ via Int.natCast_natAbs recovers |D| ≤ 2^k, which is then cast back to an inequality between natural numbers using Nat.cast_le.mp.

    lines 15–20

    uses Int.natCast_natAbs, Nat.cast_le.mp

      have hD_le_pow : D.natAbs ≤ 2 ^ k := by
        have : (D.natAbs : ℤ) ≤ ((2 ^ k : ℕ) : ℤ) := by
          rw [Int.natCast_natAbs]
          push_cast
          exact hle
        exact Nat.cast_le.mp this
  5. ⌈log₂ p⌉ ≤ k.

    Chaining the inequalities gives p ≤ |D| ≤ 2^k, so p ≤ 2^k. Since 1 < 2 by Nat.one_lt_two, the inequality p ≤ 2^k is equivalent to ⌈log₂ p⌉ ≤ k via Nat.clog_le_iff_le_pow.

    lines 21–22

    uses Nat.clog_le_iff_le_pow, Nat.one_lt_two

      have hp_le_pow : p ≤ 2 ^ k := hp_le_D.trans hD_le_pow
      have hclog : Nat.clog 2 p ≤ k := (Nat.clog_le_iff_le_pow Nat.one_lt_two).mpr hp_le_pow
  6. 1 + ⌈log₂ p⌉ ≤ |B|. automation

    Linear integer arithmetic (omega) finishes the proof by combining ⌈log₂ p⌉ ≤ k with k + 1 ≤ |B|.

    line 23

      omega
finset_midpoint_balanced_exists_nonzero_minor
For any midpoint-balanced subset B of Z/pZ with p prime, there exists k ≥ 1 with k + 1 ≤ |B|, index maps u and v, an injection b : Fin(k + 1) → Z/pZ satisfying 2 b(i) = b(u(i)) + b(v(i)), and indices i₀, j₀ such that the (k × k) minor obtained by deleting row i₀ and column j₀ has non-zero determinant.
midpoint_certificate_matrix_minor_abs_le
The determinant of any (k × k) minor of a midpoint certificate matrix has absolute value at most 2^k.
midpoint_certificate_matrix_minor_dvd_p
If k > 0 and there is an injective midpoint solution in Z/pZ, the prime p divides the integer determinant of any minor of the midpoint certificate matrix.
Int.natAbs_pos.mpr
An integer is non-zero if and only if its absolute value as a natural number is strictly positive.
Int.ofNat_dvd_left.mp
If an integer cast of a natural number m divides an integer n, then m divides the natural absolute value of n.
Nat.le_of_dvd
If a positive natural number n is divisible by m, then m ≤ n.
Int.natCast_natAbs
The cast of the natural absolute value of an integer n into ℤ equals |n|.
Nat.cast_le.mp
For natural numbers m and n, if (m : ℤ) ≤ (n : ℤ), then m ≤ n.
Nat.clog_le_iff_le_pow
For base b > 1, the ceiling logarithm satisfies ⌈log_b x⌉ ≤ y if and only if x ≤ b^y.
Nat.one_lt_two
The inequality 1 < 2 holds for natural numbers.

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 finset_card_ge_one_add_clog_of_midpoint_balanced {p : ℕ} [Fact p.Prime]    (B : Finset (ZMod p)) (hB : finset_is_midpoint_balanced B) : 1 + Nat.clog 2 p ≤ B.card := by  obtain ⟨k, hk0, hk, u, v, b, hinj, hmid, i₀, j₀, hdet_ne⟩ :=    finset_midpoint_balanced_exists_nonzero_minor B hB  let M := (Matrix.of fun (i j : Fin (k + 1)) =>    (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix    i₀.succAbove j₀.succAbove  let D := M.det  have hD_ne : D ≠ 0 := hdet_ne  have hle : |D| ≤ (2 ^ k : ℤ) := midpoint_certificate_matrix_minor_abs_le u v i₀ j₀  have hdvd : (p : ℤ) ∣ D := midpoint_certificate_matrix_minor_dvd_p hk0 u v b hinj hmid i₀ j₀  have hpos : 0 < D.natAbs := Int.natAbs_pos.mpr hD_ne  have hdvd' : p ∣ D.natAbs := Int.ofNat_dvd_left.mp hdvd  have hp_le_D : p ≤ D.natAbs := Nat.le_of_dvd hpos hdvd'  have hD_le_pow : D.natAbs ≤ 2 ^ k := by    have : (D.natAbs : ℤ) ≤ ((2 ^ k : ℕ) : ℤ) := by      rw [Int.natCast_natAbs]      push_cast      exact hle    exact Nat.cast_le.mp this  have hp_le_pow : p ≤ 2 ^ k := hp_le_D.trans hD_le_pow  have hclog : Nat.clog 2 p ≤ k := (Nat.clog_le_iff_le_pow Nat.one_lt_two).mpr hp_le_pow  omega
See it in the graphDiscuss this resultChallenge it