Davenport's theorem: the Davenport constant of is at most
Proveddavenport_zero_sumDavenport's theorem. Every sequence of elements of the cyclic group has a nonempty subsequence whose sum is zero: the Davenport constant of is at most .
The bound is sharp — the Davenport constant of equals exactly, since the sequence of ones has no nonempty zero-sum subsequence (a nonempty partial sum equals for some , which is zero only at multiples of ).
Together with the Erdős–Ginzburg–Ziv theorem (constant for the version requiring subsequences of length exactly ), this is the foundation of zero-sum theory in finite abelian groups. The proof is the classical partial-sums pigeonhole: the initial sums , , cannot all be distinct in a group of elements, and from with the interval is a nonempty zero-sum subsequence.
Formalization Note The sequence is a function ℕ → ZMod n restricted to the first n indices via t ⊆ Finset.range n; the subsequence is a Finset ℕ.
import Mathlib
theorem davenport_zero_sum (n : ℕ) (hn : 0 < n) (a : ℕ → ZMod n) :
∃ t : Finset ℕ, t.Nonempty ∧ t ⊆ Finset.range n ∧ ∑ k ∈ t, a k = 0 := by sorry