finset_card_ge_one_add_clog_of_midpoint_balanced
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
- finset_is_midpoint_balancedA finite set B is balanced: it is nonempty and every b ∈ B satisfies 2b = u + v for two distinct elements u, v of B other than b.
- midpoint_certificate_matrix_minor_abs_leThe absolute value of every k x k minor of a (k+1) x (k+1) midpoint-certificate matrix is bounded by 2^k, proved by multilinear expansion…
- midpoint_certificate_matrix_minor_dvd_pFor an injective certificate vector b in (ZMod p)^{k+1} satisfying the midpoint equations with k > 0, the shifted vector b - b(j₀)…
- finset_midpoint_balanced_exists_nonzero_minorEvery nonempty midpoint-balanced subset B of ZMod p contains an inclusion-minimal balanced subconfiguration of size k+1 ≤ |B| with k > 0…
- 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|.
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.
uses
finset_midpoint_balanced_exists_nonzero_minorobtain ⟨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
|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.
uses
midpoint_certificate_matrix_minor_abs_le,midpoint_certificate_matrix_minor_dvd_phave 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₀
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.
uses
Int.natAbs_pos.mpr,Int.ofNat_dvd_left.mp,Nat.le_of_dvdhave 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'
|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.
uses
Int.natCast_natAbs,Nat.cast_le.mphave 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
⌈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.
uses
Nat.clog_le_iff_le_pow,Nat.one_lt_twohave 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
1 + ⌈log₂ p⌉ ≤ |B|. automation
Linear integer arithmetic (omega) finishes the proof by combining ⌈log₂ p⌉ ≤ k with k + 1 ≤ |B|.
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.
- Lines 15–20 carry out a routine coercion between the integer inequality |D| ≤ 2^k and its natural-number version, which would typically be treated as implicit on paper.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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