Erdős–Ginzburg–Ziv theorem
Provederdos_ginzburg_zivThe Erdős–Ginzburg–Ziv theorem (conjectured 1935, proved 1961): among any integers, some have a sum divisible by .
The number is best possible: among integers ( zeros and ones), any chosen have sum between and , which is divisible by only when it is — forcing all chosen elements to be zeros, of which there are only .
The theorem founded zero-sum theory: it is the statement that the Erdős–Ginzburg–Ziv constant of the cyclic group equals , the first nontrivial instance of a family of problems (Gao's constant, Kemnitz-type results) that remain active research. The standard proof treats prime by the Chevalley–Warning theorem and then inducts along the prime factorization of .
Formalization Note The sequence is a function Fin (2 * n - 1) → ℤ, the chosen subsequence is a Finset of indices of cardinality n, and divisibility is stated as (n : ℤ) ∣ ∑ i ∈ t, a i. The proof is a direct appeal to Mathlib's Int.erdos_ginzburg_ziv, which carries out the Chevalley–Warning and prime-factorization argument.
import Mathlib
theorem erdos_ginzburg_ziv (n : ℕ) (a : Fin (2 * n - 1) → ℤ) :
∃ t : Finset (Fin (2 * n - 1)), t.card = n ∧ (n : ℤ) ∣ ∑ i ∈ t, a i := by sorry