Combinatorics and number theory · existing Mathlib declaration

Erdős–Ginzburg–Ziv Theorem

Assign a residue modulo n to every index in a finite set. If there are at least 2n−1 indices, then some n distinct indices carry values whose sum is zero modulo n. Different indices may carry the same residue.

zero-sum subsequences
cyclic groups
indexed finite families
Chevalley–Warning
prime-composite induction

The theorem at a glance

Erdős–Ginzburg–Ziv Theorem at a glance

A source-bound editorial overview of the exact Mathlib formulation. The image is explanatory; the statement map, formal type, and pinned source remain authoritative.

An ivory theorem poster states the at-least 2n−1 indexed-residue hypothesis, exactly-n selection, zero-sum conclusion, repeated-value boundary, n equals four example, and prime/composite proof route. — At least 2n−1 indexed residues modulo n guarantee exactly n distinct indices whose values sum to zero.

Formal orientation

Statement map

This deterministic map orients the reader from the mathematical summary to the pinned declaration and exact checked form. The HTML statement below is authoritative.

Original pixels inspected. The Scientific diagram is structurally distinct from the illustrated assets. It shows exactly eight abstract index nodes and eight residue-rail positions with one total downward map per node, a four-node hatched subset t inside s, the lower-bound inequality, exact cardinality and zero-sum labels, a repeated-value bracket, and the n=0 empty-selection inset. The cobalt multi-stroke path is read as one grouped conduit from the selected subset to the sum junction, not as a one-stroke-per-index count; the four-node enclosure and |t|=n label carry selection cardinality. No proof-route decoration, fixed-n claim, watermark, or workflow semantics appears. — From 2n−1 indexed residues, the theorem selects exactly n indices whose values sum to zero; repeated values at different indices are allowed.

Complementary intuition

A mathematical landmark

The Erdős–Ginzburg–Ziv theorem is a foundational zero-sum selection principle. Mathlib’s route also exposes a striking proof architecture: Chevalley–Warning supplies the prime case, while induction over prime and composite factors assembles disjoint zero-sum blocks for general n.

The low-text schematic gives the theorem a visual identity; it does not replace the source-bound poster or exact statement.

Authoritative formal type

Exact Mathlib statement

theorem ZMod.erdos_ginzburg_ziv {ι : Type*} {n : ℕ} {s : Finset ι} (a : ι → ZMod n) (hs : 2 * n - 1 ≤ #s) : ∃ t ⊆ s, #t = n ∧ ∑ i ∈ t, a i = 0

Selected evidence declaration text

theorem ZMod.erdos_ginzburg_ziv {ι : Type*} {n : ℕ} {s : Finset ι} (a : ι → ZMod n) (hs : 2 * n - 1 ≤ #s) : ∃ t ⊆ s, #t = n ∧ ∑ i ∈ t, a i = 0

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

These states distinguish upstream identity, local reproduction, review, and Atlas acceptance. This page is part of the public, read-only Mathlib landmark collection.

Claim boundary

No new theorem is claimed

This page indexes Mathlib’s finite indexed-family theorem in ZMod n. The hypothesis is 2*n−1 ≤ |s|, and the conclusion selects a subset t of exactly n distinct indices whose indexed values sum to zero. Values at different indices may repeat. The statement includes n=0 through the empty selection; it does not require exactly 2n−1 input indices, assert uniqueness, count witnesses, or provide an extraction algorithm.

Proof Atlas did not originate the Erdős–Ginzburg–Ziv theorem or Mathlib’s declaration.
The selected declaration is an indexed-family statement; it does not require the residue values themselves to be distinct.
The hypothesis is a lower bound on the number of indices, not an exact-length requirement.
The declaration does not assert uniqueness, count valid selections, or supply an extraction algorithm.
The generated explanation and visuals are not proof evidence.

Provenance

Origin and evidence stay separate

Existing declaration: ZMod.erdos_ginzburg_ziv in mathlib
Relationship: The checked artifact is the upstream declaration itself
Preferred checked artifact: artifact.library.mathlib.erdos-ginzburg-ziv-theorem.v001
Source handling: Verified upstream reference; no mirrored source package