AFTD Auto-Formalizing Theoretical Domains

davenport_constant_support_le_davenport_constant

theoremverified

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.

  1. 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.

    lines 3–4

    uses sSup_le_sSup

      unfold davenport_constant_support davenport_constant
      apply sSup_le_sSup
  2. 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$.

    lines 5–6

      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

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⟩
See it in the graphDiscuss this resultChallenge it