davenport_constant_support_le_davenport_constant
Restricting the support size can only lower the maximal length: D^{(k)}(X) ≤ D(X).
Statement
theorem davenport_constant_support_le_davenport_constant {G : Type*} [AddCommMonoid G] [DecidableEq G] (k : ℕ) (X : Set G) : davenport_constant_support k X ≤ davenport_constant X
- Source
- Sanity lemma for davenport_constant_support.
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- davenport_constant_supportD^{(k)}(X): the maximal length (a supremum in ℕ∞) of a minimal zero-sum sequence over X whose support has exactly k elements.
- davenport_constantThe Davenport constant D(X) of a subset X of an abelian group: the supremum (in ℕ ∪ {∞}) of the lengths of minimal zero-sum sequences with…
- multiset_is_minimal_zero_sumA minimal zero-sum sequence: a nonempty finite sequence (multiset) with sum zero, no nonempty proper subsequence of which has sum zero.
The proof, explained
Both $D^{(k)}(X)$ and $D(X)$ are defined as suprema of the lengths of minimal zero-sum multisets with elements in $X$. Any multiset satisfying the support-size constraint trivially satisfies the unrestricted conditions, so the set of lengths defining $D^{(k)}(X)$ is a subset of that defining $D(X)$. The inequality then follows directly from the monotonicity of the supremum.
It suffices to show that the set of lengths of valid multisets with support size $k$ is a subset of the set of lengths of all valid multisets.
Unfolding the definitions of `davenport_constant_support` and `davenport_constant`, both are defined as the supremum of the lengths of minimal zero-sum multisets over $X$ (with and without the support-size restriction, respectively). By the monotonicity of the supremum (`sSup_le_sSup`), showing that the first set is contained in the second implies the inequality.
uses
sSup_le_sSupunfold davenport_constant_support davenport_constant apply sSup_le_sSup
Every length realized by a minimal zero-sum multiset of support size $k$ is also realized in the unrestricted setting.
Given a length $n$ witnessed by a minimal zero-sum multiset $s$ with elements in $X$, support size $k$, and length $n$, the exact same multiset $s$ witnesses that $n$ belongs to the unrestricted set, simply discarding the requirement that its support has size $k$.
rintro n ⟨s, hX, hmin, -, hcard⟩ exact ⟨s, hX, hmin, hcard⟩
sSup_le_sSup- If a set $s$ is contained in a set $t$, then the supremum of $s$ is less than or equal to the supremum of $t$.
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 davenport_constant_support_le_davenport_constant {G : Type*} [AddCommMonoid G] [DecidableEq G] (k : ℕ) (X : Set G) : davenport_constant_support k X ≤ davenport_constant X := by unfold davenport_constant_support davenport_constant apply sSup_le_sSup rintro n ⟨s, hX, hmin, -, hcard⟩ exact ⟨s, hX, hmin, hcard⟩