AFTD Auto-Formalizing Theoretical Domains

lexical_degree_seventeen_class_a_counterexample

theoremverifiederratum

The lexical sequences a = (3,1,1,3,3,2,2,1) and b = (3,1,1,2,1,3,2,2,1) both have degree 16, are adjacent in the source lexical order among lexical sequences of degree 16, and have meet f = (3,1,1,2). However, a does not begin with (3,1,1,3,3,1,1,3), the square of the even extension of f required by the class-A formula with n=17, m=8, d=2, r=1.

Statement

theorem lexical_degree_seventeen_class_a_counterexample :
    let a : List ℕ := [3, 1, 1, 3, 3, 2, 2, 1]
    let b : List ℕ := [3, 1, 1, 2, 1, 3, 2, 2, 1]
    alpha_is_lexical a ∧ alpha_is_lexical b ∧
    a.sum + 1 = 17 ∧ b.sum + 1 = 17 ∧ alpha_lexical_lt a b ∧
    (∀ c : List ℕ, alpha_is_lexical c → c.sum + 1 = 17 →
      ¬ (alpha_lexical_lt a c ∧ alpha_lexical_lt c b)) ∧
    alpha_lexical_meet a b = [3,1,1,2] ∧
    ¬ ∃ tail : List ℕ, a = [3,1,1,3,3,1,1,3] ++ tail
Corrects
Adjacency and Parity Relations of Words in Discrete Dynamical Systems, DOI 10.1006/jcta.2000.3112, Theorem 5.1, class A, equation (5.1). The example concerns the asserted repeated-prefix structural formula, not the parity theorem or the necklace conjecture.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12
  • alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
  • alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
  • alpha_binary_prefix_inverse_parityThe inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.
  • brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
  • alpha_lexical_meetThe common left factor, including the minimum value at the first unequal cell.
  • alpha_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
  • alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
  • alpha_binary_prefix_boundsThe encoding of a nonempty positive cell sequence has exactly sum(a) bits and starts with a one.
  • alpha_is_lexicalA nonempty positive sequence strictly larger than all its proper nonempty suffixes.
  • bitword_rotateCyclic rotation of an n-bit word x (a number below 2^n) by one position: the word is shifted up and its top bit moves to the bottom.
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
  • brgc_inverseThe inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.

Read back from the Lean

Let $a = [3, 1, 1, 3, 3, 2, 2, 1]$ and $b = [3, 1, 1, 2, 1, 3, 2, 2, 1]$ be lists of natural numbers. The theorem asserts that all of the following hold: 1. alpha_is_lexical a (i.e., $a$ is non-empty, all of its elements are positive, and every non-empty proper suffix of $a$ is strictly smaller than $a$ under alpha_lexical_lt). 2. alpha_is_lexical b (similarly for $b$). 3. The sum of the elements of $a$ plus 1 equals 17 (i.e., the sum of $a$ is 16). 4. The sum of the elements of $b$ plus 1 equals 17 (i.e., the sum of $b$ is 16). 5. alpha_lexical_lt a b holds (i.e., $a$ is strictly less than $b$ under the signed lexicographic order). 6. For every list of natural numbers $c$, if alpha_is_lexical c and the sum of elements of $c$ plus 1 equals 17, then it is not the case that both alpha_lexical_lt a c and alpha_lexical_lt c b hold (that is, $b$ is the immediate successor of $a$ among lexical lists with sum $+ 1 = 17$). 7. The lexical meet of $a$ and $b$ is $[3, 1, 1, 2]$ (alpha_lexical_meet a b = [3, 1, 1, 2]). 8. There does not exist a list tail : List ℕ such that $a = [3, 1, 1, 3, 3, 1, 1, 3] ++ \text{tail}$ (i.e., $[3, 1, 1, 3, 3, 1, 1, 3]$ is not a prefix of $a$).

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 theorem proves that $a = (3,1,1,3,3,2,2,1)$ and $b = (3,1,1,2,1,3,2,2,1)$ form a counterexample to the degree-16 class-A formula: they are both lexical of degree 16 with meet $(3,1,1,2)$, yet $a$ does not start with $(3,1,1,3,3,1,1,3)$ as the formula predicts. The main step is proving adjacency—that no lexical sequence $c$ of degree 16 lies strictly between $a$ and $b$ in the lexical order. This betweenness condition constrains the 16-bit Gray code rank of $c$'s prefix to the range $[59623, 59672]$, but an exhaustive certificate (`finite_cert`) verifies that every rank in this 50-element window violates cyclic rotation maximality, contradicting the prime-degree rotation-maximality criterion for lexical sequences at $n = 17$.

  1. The lexical order comparison `alpha_lexical_lt` and the lexical predicate `alpha_is_lexical` are decidable. automation

    Unfolding the definitions reduces both properties to bounded quantifiers over finite lists and signed cell values, which typeclass synthesis recognizes as decidable.

    lines 7–13

    instance (a b : List ℕ) : Decidable (alpha_lexical_lt a b) := by
      unfold alpha_lexical_lt
      infer_instance
    instance (a : List ℕ) : Decidable (alpha_is_lexical a) := by
      unfold alpha_is_lexical
      infer_instance
    
  2. The sequences `lo` and `hi` are lexical, `lo < hi` in the lexical order, and their meet is `[3, 1, 1, 2]`. automation

    Since the definitions are fully explicit and decidable, kernel computation directly verifies all four conjunctions.

    lines 14–17

    example : alpha_is_lexical lo ∧ alpha_is_lexical hi ∧
        alpha_lexical_lt lo hi ∧
        alpha_lexical_meet lo hi = [3,1,1,2] := by decide
    
  3. For each candidate Gray code rank $r \in [59623, 59672]$, the corresponding 17-bit word $x$ fails strict cyclic rotation maximality. automation

    The finite search over the 50 values of $k$ evaluates each candidate word and finds a non-trivial cyclic rotation whose 17-bit Gray code rank is at least that of the original word; `decide` verifies this exhaustively.

    lines 18–23

    private theorem finite_cert : ∀ k : Fin 50, ∃ j : Fin 17,
        0 < j.val ∧
        let r := 59623 + k.val
        let x := 2 * brgc_word r + (r + 1) % 2
        brgc_inverse 17 x ≤ brgc_inverse 17 ((bitword_rotate 17)^[j.val] x) := by decide
    
  4. All entries of `lo` and `hi` are positive, and their 16-bit Gray code prefix ranks are 59622 and 59673, respectively. automation

    These numerical values and element positivity checks are verified directly by computation on the explicit lists `lo` and `hi`.

    lines 24–29

    private theorem lorank : brgc_inverse 16 (alpha_binary_prefix lo) = 59622 := by decide
    private theorem hirank : brgc_inverse 16 (alpha_binary_prefix hi) = 59673 := by decide
    private theorem lopos : ∀ v ∈ lo, 0 < v := by decide
    private theorem hipos : ∀ v ∈ hi, 0 < v := by decide
    
  5. The counterexample statement is reformulated using the abbreviations `lo` and `hi`.

    The tactic `change` syntactically replaces the explicit lists $a = [3, 1, 1, 3, 3, 2, 2, 1]$ and $b = [3, 1, 1, 2, 1, 3, 2, 2, 1]$ with `lo` and `hi`.

    lines 30–44

    theorem lexical_degree_seventeen_class_a_counterexample :
        let a : List ℕ := [3, 1, 1, 3, 3, 2, 2, 1]
        let b : List ℕ := [3, 1, 1, 2, 1, 3, 2, 2, 1]
        alpha_is_lexical a ∧ alpha_is_lexical b ∧
        a.sum + 1 = 17 ∧ b.sum + 1 = 17 ∧ alpha_lexical_lt a b ∧
        (∀ c : List ℕ, alpha_is_lexical c → c.sum + 1 = 17 →
          ¬ (alpha_lexical_lt a c ∧ alpha_lexical_lt c b)) ∧
        alpha_lexical_meet a b = [3,1,1,2] ∧
        ¬ ∃ tail : List ℕ, a = [3,1,1,3,3,1,1,3] ++ tail := by
      change alpha_is_lexical lo ∧ alpha_is_lexical hi ∧
        lo.sum + 1 = 17 ∧ hi.sum + 1 = 17 ∧ alpha_lexical_lt lo hi ∧
        (∀ c : List ℕ, alpha_is_lexical c → c.sum + 1 = 17 →
          ¬ (alpha_lexical_lt lo c ∧ alpha_lexical_lt c hi)) ∧
        alpha_lexical_meet lo hi = [3,1,1,2] ∧
        ¬ ∃ tail : List ℕ, lo = [3,1,1,3,3,1,1,3] ++ tail
  6. The explicit properties of `lo` and `hi` are established, leaving betweenness and prefix non-containment as the remaining subgoals. automation

    Kernel computation via `decide` establishes that `lo` and `hi` are lexical, have sum 16 (so degree 17), satisfy `lo < hi`, and have meet `[3, 1, 1, 2]`. The tactic `refine` plugs these into the conjunction, leaving two subgoals: proving no lexical sequence lies strictly between them, and proving `lo` does not start with the specified prefix.

    lines 45–48

      have hl : alpha_is_lexical lo ∧ alpha_is_lexical hi ∧
          alpha_lexical_lt lo hi ∧
          alpha_lexical_meet lo hi = [3,1,1,2] := by decide
      refine ⟨hl.1, hl.2.1, by decide, by decide, hl.2.2.1, ?_, hl.2.2.2, ?_⟩
  7. Any lexical sequence $c$ with sum 16 strictly between `lo` and `hi` must have Gray code prefix rank $r$ strictly between 59622 and 59673. automation

    Assume for contradiction that $c$ is lexical with sum 16 and $\mathrm{lo} < c < \mathrm{hi}$. By `alpha_lexical_lt_iff_inverse_prefix`, the lexical order on sequences of equal sum is equivalent to the strict order of the Gray code ranks of their binary prefixes. Using the precomputed ranks 59622 for `lo` and 59673 for `hi`, the rank $r$ of $c$ must satisfy $59622 < r < 59673$.

    lines 49–55

    uses alpha_lexical_lt_iff_inverse_prefix, lopos, hipos, lorank, hirank

      · intro c hc hsum hcbet
        have hcs : c.sum = 16 := by omega
        have hlo : lo.sum = c.sum := by simp [lo, hcs]
        have hhi : c.sum = hi.sum := by simp [hi, hcs]
        have hrlo := (alpha_lexical_lt_iff_inverse_prefix lo c lopos hc.2.1 hlo).mp hcbet.1
        have hrhi := (alpha_lexical_lt_iff_inverse_prefix c hi hc.2.1 hipos hhi).mp hcbet.2
        simp only [show lo.sum = 16 by decide, show hi.sum = 16 by decide, hcs, lorank, hirank] at hrlo hrhi
  8. There is a non-trivial cyclic rotation $j \in \{1, \dots, 16\}$ under which the candidate 17-bit word for $c$ has Gray code rank at least that of the unrotated word. automation

    Since $59623 \le r < 59673$, the offset $k = r - 59623$ lies in $\{0, \dots, 49\}$. Instantiating the finite certificate `finite_cert` at $k$ yields a rotation index $j > 0$ such that the 17-bit Gray code rank of $x$ does not exceed that of the $j$-th rotation of $x$.

    lines 56–61

    uses finite_cert

        let r := brgc_inverse 16 (alpha_binary_prefix c)
        have hr : 59623 ≤ r ∧ r < 59673 := by dsimp [r]; omega
        let k : Fin 50 := ⟨r - 59623, by omega⟩
        obtain ⟨j, hj0, hj⟩ := finite_cert k
        have hjr : 59623 + k.val = r := by dsimp [k]; omega
        simp only [hjr] at hj
  9. The word $x$ from the certificate equals the odd completion $2 \cdot \mathrm{alpha\_binary\_prefix}(c) + (|c| + 1 \bmod 2)$. automation

    Since the prefix of $c$ is strictly bounded by $2^{16}$, Gray code inversion is two-sided via `brgc_word_inverse`, recovering the binary prefix. Furthermore, `alpha_binary_prefix_inverse_parity` shows that $r \bmod 2 = |c| \bmod 2$, so $(r + 1) \bmod 2 = (|c| + 1) \bmod 2$. Rewriting these identities into the certificate inequality matches the odd completion of $c$.

    lines 62–68

    uses alpha_binary_prefix_bounds, brgc_word_inverse, alpha_binary_prefix_inverse_parity

        have hb := (alpha_binary_prefix_bounds c hc.1 hc.2.1).2
        rw [hcs] at hb
        have hword : brgc_word r = alpha_binary_prefix c := brgc_word_inverse hb
        have hpar := alpha_binary_prefix_inverse_parity c hc.2.1
        rw [hcs] at hpar
        have hmod : (r + 1) % 2 = (c.length + 1) % 2 := by dsimp [r]; omega
        rw [hword, hmod] at hj
  10. The certificate inequality contradicts rotation maximality, proving no such intermediate lexical sequence $c$ exists. automation

    Because $n = 17$ is prime and at least 3, `alpha_lexical_odd_completion_iff_rotation_max_of_prime` establishes that $c$ is lexical if and only if its odd completion has strictly greater Gray code rank than all its non-trivial cyclic rotations. The rotation $j$ from the certificate yields a weak inequality in the opposite direction, producing a contradiction via `not_le_of_gt`.

    lines 69–73

    uses alpha_lexical_odd_completion_iff_rotation_max_of_prime, not_le_of_gt

        have hmax := (alpha_lexical_odd_completion_iff_rotation_max_of_prime 17
          (by norm_num) (by norm_num) c hc.1 hc.2.1 (by omega)).mp hc
        dsimp only at hmax
        have hstrict := hmax.2.2 j.val hj0 j.isLt
        exact (not_le_of_gt hstrict) hj
  11. The sequence `lo` does not start with `[3, 1, 1, 3, 3, 1, 1, 3]`. automation

    Supposing `lo` begins with `[3, 1, 1, 3, 3, 1, 1, 3]`, applying the 6th element projection `List.getD · 5 0` to both sides via `congrArg` gives $2 = 1$, since the 6th element of `lo` is 2 while the 6th element of the candidate prefix is 1. The tactic `simp` detects this contradiction and closes the goal.

    lines 74–77

    uses congrArg

      · intro h
        obtain ⟨tail, htail⟩ := h
        have := congrArg (List.getD · 5 0) htail
        simp [lo] at this
alpha_lexical_lt_iff_inverse_prefix
For sequences of positive integers with equal sums, one is strictly smaller in the lexical order if and only if the Gray code rank of its binary prefix is strictly smaller.
lopos
Every element of the list `lo` is strictly positive.
hipos
Every element of the list `hi` is strictly positive.
lorank
The 16-bit Gray code rank of the binary prefix of `lo` equals 59622.
hirank
The 16-bit Gray code rank of the binary prefix of `hi` equals 59673.
finite_cert
For every integer $r$ from 59623 to 59672, the 17-bit word $x = 2 \cdot \mathrm{brgc\_word}(r) + (r + 1 \bmod 2)$ has a non-trivial cyclic rotation with Gray code rank at least that of $x$.
alpha_binary_prefix_bounds
For a non-empty sequence of positive integers, its binary prefix integer is bounded between $2^{\sum a - 1}$ and $2^{\sum a} - 1$.
brgc_word_inverse
For any $x < 2^n$, the Gray code word of the $n$-bit Gray code rank of $x$ equals $x$.
alpha_binary_prefix_inverse_parity
For any positive sequence, the parity of the Gray code rank of its binary prefix equals the parity of the sequence length.
alpha_lexical_odd_completion_iff_rotation_max_of_prime
For a prime $n \ge 3$ and a positive sequence $a$ with $\sum a + 1 = n$, $a$ is lexical if and only if its 17-bit completion $x$ has strictly greater Gray code rank than all its non-trivial cyclic rotations.
not_le_of_gt
In a preorder, if $a < b$, then $b \le a$ is false.
congrArg
Functions preserve equality: if $a_1 = a_2$, then $f(a_1) = f(a_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

set_option maxRecDepth 100000set_option maxHeartbeats 0private def lo : List ℕ := [3, 1, 1, 3, 3, 2, 2, 1]private def hi : List ℕ := [3, 1, 1, 2, 1, 3, 2, 2, 1]instance (a b : List ℕ) : Decidable (alpha_lexical_lt a b) := by  unfold alpha_lexical_lt  infer_instanceinstance (a : List ℕ) : Decidable (alpha_is_lexical a) := by  unfold alpha_is_lexical  infer_instanceexample : alpha_is_lexical lo ∧ alpha_is_lexical hi ∧    alpha_lexical_lt lo hi ∧    alpha_lexical_meet lo hi = [3,1,1,2] := by decideprivate theorem finite_cert : ∀ k : Fin 50, ∃ j : Fin 17,    0 < j.val ∧    let r := 59623 + k.val    let x := 2 * brgc_word r + (r + 1) % 2    brgc_inverse 17 x ≤ brgc_inverse 17 ((bitword_rotate 17)^[j.val] x) := by decideprivate theorem lorank : brgc_inverse 16 (alpha_binary_prefix lo) = 59622 := by decideprivate theorem hirank : brgc_inverse 16 (alpha_binary_prefix hi) = 59673 := by decideprivate theorem lopos : ∀ v ∈ lo, 0 < v := by decideprivate theorem hipos : ∀ v ∈ hi, 0 < v := by decidetheorem lexical_degree_seventeen_class_a_counterexample :    let a : List ℕ := [3, 1, 1, 3, 3, 2, 2, 1]    let b : List ℕ := [3, 1, 1, 2, 1, 3, 2, 2, 1]    alpha_is_lexical a ∧ alpha_is_lexical b ∧    a.sum + 1 = 17 ∧ b.sum + 1 = 17 ∧ alpha_lexical_lt a b ∧    (∀ c : List ℕ, alpha_is_lexical c → c.sum + 1 = 17 →      ¬ (alpha_lexical_lt a c ∧ alpha_lexical_lt c b)) ∧    alpha_lexical_meet a b = [3,1,1,2] ∧    ¬ ∃ tail : List ℕ, a = [3,1,1,3,3,1,1,3] ++ tail := by  change alpha_is_lexical lo ∧ alpha_is_lexical hi ∧    lo.sum + 1 = 17 ∧ hi.sum + 1 = 17 ∧ alpha_lexical_lt lo hi ∧    (∀ c : List ℕ, alpha_is_lexical c → c.sum + 1 = 17 →      ¬ (alpha_lexical_lt lo c ∧ alpha_lexical_lt c hi)) ∧    alpha_lexical_meet lo hi = [3,1,1,2] ∧    ¬ ∃ tail : List ℕ, lo = [3,1,1,3,3,1,1,3] ++ tail  have hl : alpha_is_lexical lo ∧ alpha_is_lexical hi ∧      alpha_lexical_lt lo hi ∧      alpha_lexical_meet lo hi = [3,1,1,2] := by decide  refine ⟨hl.1, hl.2.1, by decide, by decide, hl.2.2.1, ?_, hl.2.2.2, ?_⟩  · intro c hc hsum hcbet    have hcs : c.sum = 16 := by omega    have hlo : lo.sum = c.sum := by simp [lo, hcs]    have hhi : c.sum = hi.sum := by simp [hi, hcs]    have hrlo := (alpha_lexical_lt_iff_inverse_prefix lo c lopos hc.2.1 hlo).mp hcbet.1    have hrhi := (alpha_lexical_lt_iff_inverse_prefix c hi hc.2.1 hipos hhi).mp hcbet.2    simp only [show lo.sum = 16 by decide, show hi.sum = 16 by decide, hcs, lorank, hirank] at hrlo hrhi    let r := brgc_inverse 16 (alpha_binary_prefix c)    have hr : 59623 ≤ r ∧ r < 59673 := by dsimp [r]; omega    let k : Fin 50 := ⟨r - 59623, by omega⟩    obtain ⟨j, hj0, hj⟩ := finite_cert k    have hjr : 59623 + k.val = r := by dsimp [k]; omega    simp only [hjr] at hj    have hb := (alpha_binary_prefix_bounds c hc.1 hc.2.1).2    rw [hcs] at hb    have hword : brgc_word r = alpha_binary_prefix c := brgc_word_inverse hb    have hpar := alpha_binary_prefix_inverse_parity c hc.2.1    rw [hcs] at hpar    have hmod : (r + 1) % 2 = (c.length + 1) % 2 := by dsimp [r]; omega    rw [hword, hmod] at hj    have hmax := (alpha_lexical_odd_completion_iff_rotation_max_of_prime 17      (by norm_num) (by norm_num) c hc.1 hc.2.1 (by omega)).mp hc    dsimp only at hmax    have hstrict := hmax.2.2 j.val hj0 j.isLt    exact (not_le_of_gt hstrict) hj  · intro h    obtain ⟨tail, htail⟩ := h    have := congrArg (List.getD · 5 0) htail    simp [lo] at this
See it in the graphDiscuss this resultChallenge it