two_four_code_max_card_ge
For every $q \ge 2$ and every $n$, $1 + \binom{n}{2} \le A_q(n,\{2,4\})$, i.e. the extremal code of the previous lemma is counted by the supremum defining $A_q(n,\{2,4\})$. This is equation (1) of arXiv:2610.30613 and holds with no threshold on $n$.
Statement
theorem two_four_code_max_card_ge (q n : ℕ) (hq : 2 ≤ q) :
1 + n.choose 2 ≤ two_four_code_max_card q n- Source
- step towards op_491_threshold_le
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- two_four_code_card_achievableFor every alphabet size $q \ge 2$ and every length $n$, there is a $\{2,4\}$-code $C \subseteq (\mathrm{Fin}\, n \to \mathrm{Fin}\, q)$ of…
- two_four_code_max_cardFor integers $q$ and $n$, $A_q(n, \{2,4\})$ is the supremum of cardinalities of finite subsets of $\mathrm{Fin}\, n \to \mathrm{Fin}\, q$…
- is_two_four_codeA set of codewords $C \subseteq (\mathrm{Fin}\, n \to \mathrm{Fin}\, q)$ is a $\{2, 4\}$-code if any two distinct codewords $x, y \in C$…
The proof, explained
The maximum code size A_q(n,{2,4}) is defined as the supremum of cardinalities of all {2,4}-codes of length n over an alphabet of size q. The lower bound 1 + (n choose 2) ≤ A_q(n,{2,4}) follows by showing that the set of achievable code sizes is bounded above by the total number of words q^n, and that 1 + (n choose 2) is attained by an explicit code constructed in `two_four_code_card_achievable`.
It suffices to show that the set of sizes of {2,4}-codes is bounded above and contains 1 + (n choose 2).
By definition, the maximum code size is the supremum of the cardinalities of all {2,4}-codes of length n over an alphabet of size q. By `le_csSup`, any member of a set bounded above is at most the supremum of that set.
uses
le_csSupunfold two_four_code_max_card apply le_csSup
The set of {2,4}-code sizes is bounded above by the total number of words, q^n.
Any code s is a subset of the finite type of all words of length n over an alphabet of size q (Fin n → Fin q). By `Finset.card_le_univ`, the cardinality of s cannot exceed the total size of this ambient space.
uses
Finset.card_le_univ· refine ⟨Fintype.card (Fin n → Fin q), ?_⟩ rintro k ⟨s, rfl, -⟩ exact Finset.card_le_univ s
The value 1 + (n choose 2) belongs to the set of achievable {2,4}-code sizes.
The previously established lemma `two_four_code_card_achievable` guarantees the existence of a {2,4}-code C with cardinality exactly 1 + (n choose 2), which witnesses that this value is in the set.
uses
two_four_code_card_achievable· obtain ⟨C, hcard, hcode⟩ := two_four_code_card_achievable q n hq exact ⟨C, hcard, hcode⟩
le_csSup- In a conditionally complete lattice, if a set is bounded above, then any element of the set is less than or equal to its supremum.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the entire type.
two_four_code_card_achievable- For any length n and alphabet size q ≥ 2, there exists a {2, 4}-code of cardinality 1 + (n choose 2).
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.
/-- Lower bound A_q(n,{2,4}) ≥ 1 + C(n,2), for every length n and every q ≥ 2. -/theorem two_four_code_max_card_ge (q n : ℕ) (hq : 2 ≤ q) : 1 + n.choose 2 ≤ two_four_code_max_card q n := by unfold two_four_code_max_card apply le_csSup · refine ⟨Fintype.card (Fin n → Fin q), ?_⟩ rintro k ⟨s, rfl, -⟩ exact Finset.card_le_univ s · obtain ⟨C, hcard, hcode⟩ := two_four_code_card_achievable q n hq exact ⟨C, hcard, hcode⟩