lexical_degree_seventeen_class_a_counterexample
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$.
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.
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
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.
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
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.
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
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`.
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
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`.
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
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.
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, ?_⟩
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$.
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
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$.
uses
finite_certlet 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
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$.
uses
alpha_binary_prefix_bounds,brgc_word_inverse,alpha_binary_prefix_inverse_parityhave 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
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`.
uses
alpha_lexical_odd_completion_iff_rotation_max_of_prime,not_le_of_gthave 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
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.
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)$.
- The certificate `finite_cert` checks all 50 possible intermediate Gray code ranks entirely via kernel evaluation using `decide`, verifying that none satisfies cyclic rotation maximality.
- The degree of the lexical sequences is $\sum a = 16$, which corresponds to length $n = \sum a + 1 = 17$ for the cyclic rotation test on bitwords.
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.
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