op_491_threshold_gt_of_ne
Assuming the stabilization threshold set is nonempty, if $A_q(n, \\{2,4\\}) \\ne 1 + \\binom{n}{2}$ for some length $n$, then $n$ is strictly less than the eventual length threshold $N_*(q)$.
Statement
theorem op_491_threshold_gt_of_ne (q n : ℕ)
(h_nonempty : ∃ N, ∀ m ≥ N, two_four_code_max_card q m = 1 + Nat.choose m 2)
(hne : two_four_code_max_card q n ≠ 1 + Nat.choose n 2) :
n < two_four_eventual_threshold q- Source
- arXiv:2610.30613 Section 6
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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$…
- two_four_eventual_thresholdFor an integer $q$, the eventual length threshold $N_*(q)$ is the infimum of all integers $N$ such that…
- Used by 2
- op_491_threshold_ge_two_q_plus_one_of_neAssuming the stabilization threshold set is nonempty, if $A_q(2q, \\{2,4\\}) \\ne 1 + \\binom{2q}{2}$, then the eventual length threshold…
- op_491_threshold_ge_two_q_of_neAssuming the stabilization threshold set is nonempty, if $A_q(2q - 1, \\{2,4\\}) \\ne 1 + \\binom{2q - 1}{2}$, then the eventual length…
Read back from the Lean
For all natural numbers q and n:
Assuming there exists a natural number N such that for every m ≥ N, the maximum cardinality of a two-four code of length m over an alphabet of size q (that is, the supremum of cardinalities of finsets of words in Fin m → Fin q where every pair of distinct words has Hamming distance 2 or 4) is equal to 1 + Nat.choose m 2;
and assuming that for the given n, the maximum cardinality of a two-four code of length n over an alphabet of size q is not equal to 1 + Nat.choose n 2;
then n is strictly less than the eventual threshold for q, defined as the infimum (sInf) of the set of all natural numbers N such that for all m ≥ N, the maximum cardinality of a two-four code of length m over an alphabet of size q equals 1 + Nat.choose m 2.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by contradiction: suppose $n \ge N_*(q)$, where $N_*(q)$ is the eventual length threshold. Since the set of stabilization thresholds is assumed to be nonempty, its infimum $N_*(q)$ belongs to the set by the well-ordering principle of $\mathbb{N}$. Therefore, the maximum code size $A_q(m, \{2,4\})$ equals $1 + \binom{m}{2}$ for all $m \ge N_*(q)$—in particular for $m = n$, which directly contradicts the hypothesis that $A_q(n, \{2,4\}) \ne 1 + \binom{n}{2}$.
Assume for contradiction that $N_*(q) \le n$.
We assume the negation of the target inequality $n < N_*(q)$, which simplifies to $N_*(q) \le n$ (`hle`), reducing the goal to deriving a contradiction.
by_contra! hle
The threshold $N_*(q)$ itself satisfies the stabilization condition: for all $m \ge N_*(q)$, $A_q(m, \{2,4\}) = 1 + \binom{m}{2}$.
The eventual threshold $N_*(q)$ is defined as the infimum of the set of natural numbers $N$ for which the equality holds for all $m \ge N$. Since this set is assumed to be nonempty (`h_nonempty`), the infimum of the set belongs to the set itself by `Nat.sInf_mem`.
uses
Nat.sInf_memhave h_mem : two_four_eventual_threshold q ∈ { N : ℕ | ∀ m ≥ N, two_four_code_max_card q m = 1 + Nat.choose m 2 } := Nat.sInf_mem h_nonemptyA contradiction is reached, completing the proof.
Specializing the membership condition to $m = n$ (which is valid since $n \ge N_*(q)$ by the contradiction hypothesis `hle`) yields $A_q(n, \{2,4\}) = 1 + \binom{n}{2}$, directly contradicting the assumption `hne` that they are unequal.
exact hne (h_mem n hle)
Nat.sInf_mem- A nonempty set of natural numbers contains its infimum (minimum).
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.
/-- If A_q(n, {2,4}) ≠ 1 + choose n 2 and the threshold set is nonempty, then n < N_*(q). -/theorem op_491_threshold_gt_of_ne (q n : ℕ) (h_nonempty : ∃ N, ∀ m ≥ N, two_four_code_max_card q m = 1 + Nat.choose m 2) (hne : two_four_code_max_card q n ≠ 1 + Nat.choose n 2) : n < two_four_eventual_threshold q := by by_contra! hle have h_mem : two_four_eventual_threshold q ∈ { N : ℕ | ∀ m ≥ N, two_four_code_max_card q m = 1 + Nat.choose m 2 } := Nat.sInf_mem h_nonempty exact hne (h_mem n hle)