AFTD Auto-Formalizing Theoretical Domains

two_four_code_max_card_ge

theoremverified

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

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

    lines 4–5

    uses le_csSup

      unfold two_four_code_max_card
      apply le_csSup
  2. 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.

    lines 6–8

    uses Finset.card_le_univ

      · refine ⟨Fintype.card (Fin n → Fin q), ?_⟩
        rintro k ⟨s, rfl, -⟩
        exact Finset.card_le_univ s
  3. 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.

    lines 9–10

    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

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