AFTD Auto-Formalizing Theoretical Domains

op_491_threshold_le_two_q_minus_one_of_stabilizes

theoremverified

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.

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

    lines 3–4

    uses op_491_eventual_threshold_le_of_stabilizes

      apply op_491_eventual_threshold_le_of_stabilizes
      intro n hn
  2. 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`.

    lines 5–8

    uses lt_or_ge

      rcases lt_or_ge n (2 * q) with h | h
      · have hEq : n = 2 * q - 1 := by omega
        rw [hEq]
        exact h_base
  3. 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`).

    lines 9–12

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

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

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