op_491_threshold_le_two_q_minus_one_of_stabilizes
If $A_q(n, \\{2,4\\}) = 1 + \\binom{n}{2}$ holds at $n = 2q - 1$, at $n = 2q$, and for all $n \\ge 2q + 1$, then the eventual length threshold satisfies $N_*(q) \\le 2q - 1$.
Statement
theorem op_491_threshold_le_two_q_minus_one_of_stabilizes (q : ℕ) (h_base : two_four_code_max_card q (2 * q - 1) = 1 + Nat.choose (2 * q - 1) 2) (h_next : two_four_code_max_card q (2 * q) = 1 + Nat.choose (2 * q) 2) (h_large : ∀ n ≥ 2 * q + 1, two_four_code_max_card q n = 1 + Nat.choose n 2) : two_four_eventual_threshold q ≤ 2 * q - 1- Source
- arXiv:2610.30613 Remark 6.1
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- op_491_eventual_threshold_le_of_stabilizesIf a natural number $N$ has the property that $A_q(n, \\{2,4\\}) = 1 + \\binom{n}{2}$ for all integers $n \\ge N$, then the eventual…
- 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…
Read back from the Lean
For any natural number q, if: 1. (h_base) the maximum cardinality of a subset of (Fin (2 * q - 1) → Fin q) whose distinct elements have Hamming distance 2 or 4 is 1 + Nat.choose (2 * q - 1) 2, 2. (h_next) the maximum cardinality of a subset of (Fin (2 * q) → Fin q) whose distinct elements have Hamming distance 2 or 4 is 1 + Nat.choose (2 * q) 2, and 3. (h_large) for all natural numbers n ≥ 2 * q + 1, the maximum cardinality of a subset of (Fin n → Fin q) whose distinct elements have Hamming distance 2 or 4 is 1 + Nat.choose n 2, then two_four_eventual_threshold q ≤ 2 * q - 1 (that is, the infimum of all N : ℕ such that the maximum cardinality equals 1 + Nat.choose n 2 for all n ≥ N is at most 2 * q - 1).
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
To show that the eventual threshold satisfies $N_*(q) \le 2q - 1$, it suffices by definition to prove that the code size formula $A_q(n, \{2, 4\}) = 1 + \binom{n}{2}$ holds for all $n \ge 2q - 1$. Any such integer $n$ must be either $2q - 1$, $2q$, or at least $2q + 1$. The proof splits into these three cases, each of which is settled immediately by one of the theorem's three hypotheses.
It suffices to show that the code size formula $A_q(n, \{2, 4\}) = 1 + \binom{n}{2}$ holds for all $n \ge 2q - 1$.
Applying the lemma `op_491_eventual_threshold_le_of_stabilizes` reduces the goal $N_*(q) \le 2q - 1$ to verifying that stabilization holds for all $n \ge 2q - 1$. We then introduce an arbitrary integer $n$ and the assumption that $n \ge 2q - 1$.
uses
op_491_eventual_threshold_le_of_stabilizesapply op_491_eventual_threshold_le_of_stabilizes intro n hn
The formula holds when $n < 2q$, in which case $n = 2q - 1$.
Using `lt_or_ge`, we perform a case split on whether $n < 2q$ or $n \ge 2q$. In the first branch where $n < 2q$, combining this with $n \ge 2q - 1$ via linear arithmetic yields $n = 2q - 1$. Rewriting $n$ to $2q - 1$, the goal matches the base hypothesis `h_base`.
uses
lt_or_gercases lt_or_ge n (2 * q) with h | h · have hEq : n = 2 * q - 1 := by omega rw [hEq] exact h_base
The formula holds when $n \ge 2q$, split into the cases $n = 2q$ and $n \ge 2q + 1$.
In the second branch where $n \ge 2q$, `eq_or_lt_of_le` further splits into $n = 2q$ and $n > 2q$. If $n = 2q$, the claim holds by the hypothesis for the next value (`h_next`). If $n > 2q$, linear arithmetic gives $n \ge 2q + 1$, so the claim holds by the asymptotic stabilization hypothesis (`h_large`).
uses
eq_or_lt_of_le· rcases eq_or_lt_of_le h with hEq | hlt · rw [← hEq] exact h_next · exact h_large n (by omega)
op_491_eventual_threshold_le_of_stabilizes- If the maximum code size $A_q(n, \{2, 4\})$ stabilizes to $1 + \binom{n}{2}$ for all $n \ge N$, then the eventual stabilization threshold satisfies $N_*(q) \le N$.
lt_or_ge- In any linear order, either $a < b$ or $a \ge b$.
eq_or_lt_of_le- In any partial order, if $a \le b$, then either $a = b$ or $a < b$.
- The linear arithmetic tactic `omega` automatically establishes that $n = 2q - 1$ follows from $n \ge 2q - 1 \land n < 2q$, and that $n \ge 2q + 1$ follows from $n > 2q$.
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 stabilization holds at 2q-1, 2q, and all n ≥ 2q+1, then N_*(q) ≤ 2q - 1. -/theorem op_491_threshold_le_two_q_minus_one_of_stabilizes (q : ℕ) (h_base : two_four_code_max_card q (2 * q - 1) = 1 + Nat.choose (2 * q - 1) 2) (h_next : two_four_code_max_card q (2 * q) = 1 + Nat.choose (2 * q) 2) (h_large : ∀ n ≥ 2 * q + 1, two_four_code_max_card q n = 1 + Nat.choose n 2) : two_four_eventual_threshold q ≤ 2 * q - 1 := by apply op_491_eventual_threshold_le_of_stabilizes intro n hn rcases lt_or_ge n (2 * q) with h | h · have hEq : n = 2 * q - 1 := by omega rw [hEq] exact h_base · rcases eq_or_lt_of_le h with hEq | hlt · rw [← hEq] exact h_next · exact h_large n (by omega)