Sharpness: the Erdős–Ginzburg–Ziv constant is best possible
Provedegz_constant_sharpadditive-combinatoricsnumber-theoryzero-sum-theory
The constant in the Erdős–Ginzburg–Ziv theorem cannot be improved: among integers, it is not always possible to find with sum divisible by .
Concretely, take zeros and ones. Any chosen elements have sum equal to the number of chosen ones, with . Divisibility by forces , i.e. all chosen elements are zeros — but only zeros are available.
Together with erdos_ginzburg_ziv, this shows the Erdős–Ginzburg–Ziv constant of (the least such that any elements contain summing to zero) is exactly .
Formalization Note The witnessing sequence is the explicit function fun i => if (i : ℕ) < n - 1 then 1 else 0 on Fin (2 * n - 2); the cardinality accounting translates the zeros block down by n - 1 and injects it into range (n - 1).
Preamble
import Mathlib
Formal statement
theorem egz_constant_sharp (n : ℕ) (hn : 1 < n) :
∃ a : Fin (2 * n - 2) → ℤ, ∀ t : Finset (Fin (2 * n - 2)), t.card = n →
¬ ((n : ℤ) ∣ ∑ i ∈ t, a i) := by sorrySource
Sharpness example from P. Erdos, A. Ginzburg, A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel 10F (1961), 41-43