AFTD Auto-Formalizing Theoretical Domains

op_491_threshold_gt_of_ne

theoremverified

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

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

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

    line 6

      by_contra! hle
  2. 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`.

    lines 7–8

    uses Nat.sInf_mem

      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
  3. A 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.

    line 9

      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

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