AFTD Auto-Formalizing Theoretical Domains

Research Blogs

A Counterexample to the Class-A Repeated-Prefix Adjacency Formula for Lexical Sequences at Prime Degree Seventeen

low tier2026-11-13reviewed by Claude Code中文版

Abstract

DOI 10.1006/jcta.2000.3112 (Theorem 5.1, class A) describes the structure of adjacent pairs of lexical sequences: if $a < b$ are adjacent among the lexical sequences with $1 + \sum a = 1 + \sum b = n$, their meet $f$ has $1 + \sum f = m$, and $n = md + r$ with $0 < r < m$, then the smaller sequence is $a = (f_e)^d \delta$, where $f_e$ is the even-length extension of $f$. We show that this formula is false. The sequences $a = [3, 1, 1, 3, 3, 2, 2, 1]$ and $b = [3, 1, 1, 2, 1, 3, 2, 2, 1]$ are lexical of degree 16 ($n = 17$), satisfy $a < b$, are adjacent among lexical sequences of degree 16, and have meet $f = [3, 1, 1, 2]$, so $m = 8$, $d = 2$, $r = 1$. But $a$ does not begin with $(f_e)^2 = [3, 1, 1, 3, 3, 1, 1, 3]$: it differs at the sixth entry. Adjacency is the substantial part: lexical order on sequences of equal sum is inverse Gray-code rank order, so an intermediate lexical sequence would have one of 50 ranks, and at the prime length 17 each of these is excluded by a rotation-maximality criterion. The whole statement is checked in Lean 4.

1. Introduction

Lexical sequences are finite sequences of positive integers that are strictly larger than each of their proper right factors in the alternating lexicographic order, in which the signs of the entries alternate $+, -, +, \dots$ before the sequences are compared. The degree of a sequence is the sum of its entries, and $L_n$ denotes the set of lexical sequences of degree $n - 1$. These sequences describe the periodic orbits of unimodal maps of an interval, and their order and adjacency within $L_n$ were studied in DOI 10.1006/jcta.2000.3112, "Adjacency and Parity Relations of Words in Discrete Dynamical Systems".

Theorem 5.1 of that paper classifies the adjacent pairs of $L_n$. For two sequences $a < b$ adjacent in $L_n$, let $f$ be their meet: the longest common left factor, extended by the smaller of the two entries at the first place where they differ. Then $f$ is lexical; write $f \in L_m$ and $n = md + r$ with $0 \le r < m$. For $r > 0$ (class A) the theorem asserts the factorizations $$a = (f_e)^d \delta, \qquad b = f_o (f_e)^{d-1} \delta,$$ where $f_e$ and $f_o$ are the extensions of $f$ to even and odd length: for $f$ of even length, $f_e$ adds 1 to the last entry and $f_o$ appends an entry 1; for $f$ of odd length the roles are exchanged. In particular $a$ begins with $(f_e)^d$.

In this post we show that this formula fails. The two sequences $$a = [3, 1, 1, 3, 3, 2, 2, 1] \quad \text{and} \quad b = [3, 1, 1, 2, 1, 3, 2, 2, 1]$$ both have entry sum 16, so both lie in $L_{17}$; they are lexical (alpha_is_lexical), satisfy $a < b$ in the alternating order (alpha_lexical_lt), have meet $f = [3, 1, 1, 2]$ (alpha_lexical_meet), and are adjacent: no lexical $c$ of sum 16 lies strictly between them.

Here $1 + \sum f = 8$, so $m = 8$ and $17 = 8 \cdot 2 + 1$, that is $d = 2$ and $r = 1 > 0$. Since $f$ has even length, $f_e = [3, 1, 1, 3]$ and $(f_e)^2 = [3, 1, 1, 3, 3, 1, 1, 3]$. The entry of $a$ at index 5 is 2, while that of $(f_e)^2$ is 1, so $a$ does not begin with $(f_e)^2$. (The companion formula for $b$ fails too: $f_o f_e = [3, 1, 1, 2, 1, 3, 1, 1, 3]$ differs from $b$ at index 6.)

The checks on $a$, $b$ and $f$ are finite computations; adjacency is a statement about all sequences of sum 16, and its proof is the substance of the result. Lexical order on sequences of equal sum coincides with the order of the inverse binary reflected Gray-code ranks of their binary encodings (alpha_lexical_lt_iff_inverse_prefix), so a lexical sequence strictly between $a$ and $b$ would have one of 50 ranks. At the odd prime length 17, a positive sequence is lexical exactly when its one-bit completion is the strict rank maximum among its cyclic rotations (alpha_lexical_odd_completion_iff_rotation_max_of_prime), and each of the 50 ranks fails this test. The statement is lexical_degree_seventeen_class_a_counterexample, proved in Lean 4.

2. Preliminaries

We work with sequences of natural numbers represented as lists of natural numbers. Throughout, the degree of a sequence $a$ refers to its entry sum $\sum a$, and period parameters satisfy $n = \sum a + 1$.

Definition 1 (alpha_lexical_lt). The source alternating lexicographic order on integer sequences is the relation alpha_lexical_lt. For lists $a$ and $b$, alpha_lexical_lt a b holds if there exists an index $i < \max(a.\text{length}, b.\text{length})$ such that for all $j < i$, the signed cells satisfy $\text{alpha\_signed\_cell } a\ j = \text{alpha\_signed\_cell } b\ j$, and at index $i$, $\text{alpha\_signed\_cell } a\ i < \text{alpha\_signed\_cell } b\ i$. *Remark*. The signed cell convention incorporates alternating signs reflecting orientation-reversing dynamics. The inequality at the distinguishing position $i$ is strict.

Definition 2 (alpha_is_lexical). A sequence $a$ is lexical, written alpha_is_lexical a, if it is non-empty ($a \neq []$), every entry $v \in a$ satisfies $0 < v$, and for every integer $k$ with $0 < k < a.\text{length}$, the proper suffix $a.\text{drop } k$ satisfies alpha_lexical_lt (a.drop k) a. *Remark*. A lexical sequence is strictly greater than each of its non-empty proper suffixes in the alternating order. In Lean, the definition explicitly requires non-emptiness and strict positivity of all elements, excluding the empty list.

Definition 3 (alpha_lexical_meet). The lexical meet of two lists $a$ and $b$, denoted alpha_lexical_meet a b, is defined recursively by: $$\text{alpha\_lexical\_meet}(a :: as, b :: bs) = \begin{cases} a :: \text{alpha\_lexical\_meet } as\ bs & \text{if } a = b, \\ [\min(a, b)] & \text{if } a \neq b, \end{cases}$$ and $\text{alpha\_lexical\_meet}(a, b) = []$ whenever either argument is empty. *Remark*. Unlike the standard longest common prefix of two lists, the lexical meet appends the minimum of the two unequal values at the index where the sequences diverge. For instance, for $a = [3, 1, 1, 3, \dots]$ and $b = [3, 1, 1, 2, \dots]$, the meet is $[3, 1, 1, \min(3, 2)] = [3, 1, 1, 2]$.

Definition 4 (alpha_binary_prefix). The binary prefix encoding alpha_binary_prefix maps a sequence of positive integers to a natural number representing a bitword: $$\text{alpha\_binary\_prefix}([]) = 0,$$ $$\text{alpha\_binary\_prefix}(a :: as) = 2^{a - 1 + as.\text{sum}} + \text{alpha\_binary\_prefix}(as).$$ *Remark*. This encoding maps each cell $v \ge 1$ to a binary block of $v$ bits consisting of a 1 followed by $v - 1$ zeros. The concatenation of these blocks yields an integer whose binary representation has length exactly $a.\text{sum}$ and whose most significant bit is 1.

Definition 5 (brgc_word). The binary reflected Gray code (BRGC) word of rank $t \in \mathbb{N}$, denoted brgc_word t, is the bitword defined by: $$\text{brgc\_word}(t) = t \oplus \lfloor t / 2 \rfloor,$$ where $\oplus$ denotes bitwise exclusive-or. *Remark*. The function brgc_word evaluates the standard Gray code mapping $g(t) = t \oplus (t \gg 1)$.

Definition 6 (brgc_inverse). The inverse prefix-parity transform brgc_inverse on $n$-bit words is defined by recursion on $n$: $$\text{brgc\_inverse}(0, x) = 0,$$ $$\text{brgc\_inverse}(n + 1, x) = x \oplus \text{brgc\_inverse}(n, \lfloor x / 2 \rfloor).$$ *Remark*. The function brgc_inverse computes the rank $t$ such that $\text{brgc\_word}(t) = x$ for any word $x < 2^n$. The parameter $n$ specifies the fixed bit-width of the representation.

Definition 7 (bitword_rotate). The cyclic rotation of an $n$-bit word $x < 2^n$ by one bit position is defined by: $$\text{bitword\_rotate}(n, x) = (2 \cdot x) \bmod 2^n + \lfloor x / 2^{n - 1} \rfloor.$$ *Remark*. This shifts $x$ left by one bit within the $n$-bit window and moves the most significant bit (at position $n - 1$) to the least significant bit (position 0). Iterated rotation by $r$ steps is denoted $(\text{bitword\_rotate } n)^r(x)$.

3. Main result

The main result is the disproof of the repeated-prefix formula of Theorem 5.1, class A, in DOI 10.1006/jcta.2000.3112, via an explicit counterexample at degree 16.

Theorem (lexical_degree_seventeen_class_a_counterexample). Define the two integer sequences: $$a = [3, 1, 1, 3, 3, 2, 2, 1] \quad \text{and} \quad b = [3, 1, 1, 2, 1, 3, 2, 2, 1].$$ Then the following statements hold:

  1. Both sequences are lexical: alpha_is_lexical a and alpha_is_lexical b.
  2. Both sequences have degree 16, corresponding to period 17: $a.\text{sum} + 1 = 17$ and $b.\text{sum} + 1 = 17$.
  3. $a$ is strictly smaller than $b$ in the lexical order: alpha_lexical_lt a b.
  4. $a$ and $b$ are adjacent among lexical sequences of degree 16: for every sequence $c$, if alpha_is_lexical c and $c.\text{sum} + 1 = 17$, then it is not the case that both alpha_lexical_lt a c and alpha_lexical_lt c b hold.
  5. The lexical meet of $a$ and $b$ is $f = [3, 1, 1, 2]$: alpha_lexical_meet a b = [3, 1, 1, 2].
  6. $a$ does not begin with $[3, 1, 1, 3, 3, 1, 1, 3]$: there is no list $\text{tail}$ such that $a = [3, 1, 1, 3, 3, 1, 1, 3] \mathbin{+\!+} \text{tail}$.

In Lean, the theorem lexical_degree_seventeen_class_a_counterexample assigns $a$ and $b$ locally as concrete lists of natural numbers, asserting the conjunction of their lexicality via alpha_is_lexical, their degree evaluations $a.\text{sum} + 1 = 17$ and $b.\text{sum} + 1 = 17$, strict ordering via alpha_lexical_lt, the universal quantification over all candidate lists $c$ of degree 16 ruling out intermediate lexical sequences, the meet equality alpha_lexical_meet a b = [3, 1, 1, 2], and the negation of the existential statement that $a$ factorizes with prefix $[3, 1, 1, 3, 3, 1, 1, 3]$.

In DOI 10.1006/jcta.2000.3112, Theorem 5.1 categorized adjacent lexical pairs $(a, b)$ of equal degree into structural classes. For class A, parameterized by integers $n$, $m$, $d$, and $r$, Theorem 5.1 asserts, when $r > 0$, that the smaller sequence is $a = (f_e)^d \delta$; in particular $a$ begins with $(f_e)^d$. For the sequences $a$ and $b$ in the theorem, the parameters are: $$n = 17, \quad m = 8, \quad d = 2, \quad r = 1.$$ The meet $f = [3, 1, 1, 2]$ has length 4 and entry sum $\sum f = 7$. Since $f$ has even length, its even-length extension $f_e$ adds 1 to the last entry, yielding $f_e = [3, 1, 1, 3]$. Since $d = 2$, the $d$-fold repetition of this extension is: $$(f_e)^2 = [3, 1, 1, 3, 3, 1, 1, 3].$$ Theorem 5.1 therefore requires $a$ to begin with $(f_e)^2$. However, item 6 of our theorem shows that $a$ does not begin with $(f_e)^2$: $a$ has length 8, and its entries are $a = [3, 1, 1, 3, 3, 2, 2, 1]$. Comparing entries at index 5 (0-indexed), we find $a[5] = 2$, whereas $(f_e)^2[5] = 1$. Consequently, the class-A formula of Theorem 5.1 fails for this pair.

Theorem lexical_degree_seventeen_class_a_counterexample (Lean 4, verified)
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

4. Proof

The proof decomposes into three main parts: verifying the direct properties of $a$ and $b$ by computation, proving the negative prefix condition by entry inspection, and establishing the adjacency of $a$ and $b$ among lexical sequences of degree 16. The adjacency proof is the core mathematical challenge; it converts alternating lexical order to binary reflected Gray code order and uses rotation maximality at prime length $n = 17$ to rule out all 50 intermediate ranks.

We begin by stating the supporting lemmas from the Lean formalization.

Lemma 1 (alpha_lexical_lt_iff_inverse_prefix). Let $a$ and $b$ be sequences of positive integers ($0 < v$ for all $v \in a$ and $v \in b$) having equal sum $a.\text{sum} = b.\text{sum}$. Then: $$\text{alpha\_lexical\_lt } a\ b \iff \text{brgc\_inverse}(a.\text{sum}, \text{alpha\_binary\_prefix } a) < \text{brgc\_inverse}(b.\text{sum}, \text{alpha\_binary\_prefix } b).$$ Lean proves this theorem by showing that the inverse prefix-parity transform linearizes the alternating sign structure of the lexicographic order on equal-sum binary prefix encodings.

Lemma 2 (alpha_binary_prefix_bounds). Let $a$ be a non-empty sequence of positive integers. Then: $$2^{a.\text{sum} - 1} \le \text{alpha\_binary\_prefix } a < 2^{a.\text{sum}}.$$ In particular, the binary prefix encoding alpha_binary_prefix of $a$ is strictly bounded by $2^{a.\text{sum}}$, ensuring that it fits into an $(a.\text{sum})$-bit register with a leading bit of 1.

Lemma 3 (brgc_word_inverse). For any $n, x \in \mathbb{N}$ satisfying $x < 2^n$: $$\text{brgc\_word}(\text{brgc\_inverse } n\ x) = x.$$ This lemma establishes that brgc_word is the left inverse of brgc_inverse on words of width $n$.

Lemma 4 (alpha_binary_prefix_inverse_parity). For any sequence $a$ of positive integers: $$\text{brgc\_inverse}(a.\text{sum}, \text{alpha\_binary\_prefix } a) \bmod 2 = a.\text{length} \bmod 2.$$ Lean verifies this by induction on $a$, showing that each cell in the list contributes a single 1-bit to the binary prefix, so the rank parity under the inverse Gray code equals the cell count modulo 2.

Lemma 5 (alpha_lexical_odd_completion_iff_rotation_max_of_prime). Let $n \ge 3$ be a prime number, and let $a$ be a non-empty sequence of positive integers with $a.\text{sum} + 1 = n$. Then $a$ is lexical (alpha_is_lexical a) if and only if the completion word: $$x = 2 \cdot \text{alpha\_binary\_prefix } a + (a.\text{length} + 1) \bmod 2$$ satisfies $0 < x < 2^n - 1$ and is the strict maximum in its necklace orbit under the inverse Gray code order: for all rotation counts $r \in \mathbb{N}$ with $0 < r < n$, $$\text{brgc\_inverse } n\ ((\text{bitword\_rotate } n)^r(x)) < \text{brgc\_inverse } n\ x.$$ This bridge theorem connects lexicality of positive sequences of prime degree to the rotation-maximality of their $(n)$-bit odd-parity completions under the binary reflected Gray code order.

We now present the complete proof of the main theorem, following the steps of lexical_degree_seventeen_class_a_counterexample.

Step 1: Direct evaluations for $a$ and $b$. We define $lo = a = [3, 1, 1, 3, 3, 2, 2, 1]$ and $hi = b = [3, 1, 1, 2, 1, 3, 2, 2, 1]$. Computing the sums: $$a.\text{sum} = 3 + 1 + 1 + 3 + 3 + 2 + 2 + 1 = 16,$$ $$b.\text{sum} = 3 + 1 + 1 + 2 + 1 + 3 + 2 + 2 + 1 = 16.$$ Thus $a.\text{sum} + 1 = 17$ and $b.\text{sum} + 1 = 17$, both of which hold by reflexivity. The sequences are non-empty and all entries are positive ($3, 1, 2 > 0$). To compute alpha_lexical_meet a b, we compare elements recursively: - Position 0: $a[0] = 3 = b[0]$, so the meet begins with 3. - Position 1: $a[1] = 1 = b[1]$, so the meet continues with 1. - Position 2: $a[2] = 1 = b[2]$, so the meet continues with 1. - Position 3: $a[3] = 3$ and $b[3] = 2$. Since $3 \neq 2$, the recursive definition terminates with $[\min(3, 2)] = [2]$. Hence alpha_lexical_meet a b = [3, 1, 1, 2]. The predicates alpha_is_lexical a, alpha_is_lexical b, and alpha_lexical_lt a b are decidable propositions on concrete finite lists; Lean evaluates them directly by computational reduction.

Step 2: Disproof of the repeated prefix. Suppose there exists a list $\text{tail}$ such that: $$a = [3, 1, 1, 3, 3, 1, 1, 3] \mathbin{+\!+} \text{tail}.$$ Applying the projection extracting the element at 0-based index 5 to both sides yields: $$a[5] = ([3, 1, 1, 3, 3, 1, 1, 3] \mathbin{+\!+} \text{tail})[5].$$ On the left-hand side, since $a = [3, 1, 1, 3, 3, 2, 2, 1]$, the element at index 5 is $a[5] = 2$. On the right-hand side, the prefix $[3, 1, 1, 3, 3, 1, 1, 3]$ has length 8, and its entry at index 5 is 1. This implies $2 = 1$, an immediate contradiction. Thus no such $\text{tail}$ exists.

Step 3: Adjacency of $a$ and $b$. It remains to prove that no sequence $c$ can satisfy: $$\text{alpha\_is\_lexical } c \land c.\text{sum} + 1 = 17 \land \text{alpha\_lexical\_lt } a\ c \land \text{alpha\_lexical\_lt } c\ b.$$ Assume for contradiction that such a sequence $c$ exists. From $c.\text{sum} + 1 = 17$, we have $c.\text{sum} = 16$. Since $a.\text{sum} = 16$ and $b.\text{sum} = 16$, we have $a.\text{sum} = c.\text{sum}$ and $c.\text{sum} = b.\text{sum}$. All entries of $a$, $b$, and $c$ are strictly positive (by lexicality). We apply Lemma 1 (alpha_lexical_lt_iff_inverse_prefix) to both inequalities: - From alpha_lexical_lt a c, we obtain: $$\text{brgc\_inverse } 16\ (\text{alpha\_binary\_prefix } a) < \text{brgc\_inverse } 16\ (\text{alpha\_binary\_prefix } c).$$ - From alpha_lexical_lt c b, we obtain: $$\text{brgc\_inverse } 16\ (\text{alpha\_binary\_prefix } c) < \text{brgc\_inverse } 16\ (\text{alpha\_binary\_prefix } b).$$

We evaluate the ranks of $a$ and $b$ explicitly: The binary prefix of $a$ has bit length 16. Evaluating its inverse Gray rank gives: $$\text{lorank} = \text{brgc\_inverse } 16\ (\text{alpha\_binary\_prefix } a) = 59622.$$ Similarly, for $b$, the inverse Gray rank is: $$\text{hirank} = \text{brgc\_inverse } 16\ (\text{alpha\_binary\_prefix } b) = 59673.$$ Let $r = \text{brgc\_inverse } 16\ (\text{alpha\_binary\_prefix } c)$. The inequalities state that: $$59622 < r < 59673,$$ which is equivalent over integers to: $$59623 \le r < 59673.$$ The number of candidate integers in this range is $59673 - 59623 = 50$. We define the index $k = r - 59623$, so $k \in \{0, 1, \dots, 49\}$.

We now reconstruct the completion word $x$ of $c$. By Lemma 2 (alpha_binary_prefix_bounds), $\text{alpha\_binary\_prefix } c < 2^{c.\text{sum}} = 2^{16}$. By Lemma 3 (brgc_word_inverse), decoding the rank $r$ recovers the prefix encoding: $$\text{brgc\_word } r = \text{alpha\_binary\_prefix } c.$$ Furthermore, by Lemma 4 (alpha_binary_prefix_inverse_parity), we have: $$r \bmod 2 = c.\text{length} \bmod 2,$$ which implies: $$(r + 1) \bmod 2 = (c.\text{length} + 1) \bmod 2.$$ Therefore, the 17-bit odd completion word of $c$ defined in Lemma 5 is: $$x = 2 \cdot (\text{brgc\_word } r) + (r + 1) \bmod 2.$$ Since $n = 17$ is prime and $17 \ge 3$, Lemma 5 (alpha_lexical_odd_completion_iff_rotation_max_of_prime) applies to $c$. Because $c$ is lexical, Lemma 5 implies that for every non-zero rotation count $j \in \{1, 2, \dots, 16\}$, the rotated word $(\text{bitword\_rotate } 17)^j(x)$ satisfies: $$\text{brgc\_inverse } 17\ ((\text{bitword\_rotate } 17)^j(x)) < \text{brgc\_inverse } 17\ x.$$

However, the finite certificate inspects each of the 50 candidate offsets $k \in \{0, 1, \dots, 49\}$. For each $k$, with $r = 59623 + k$, the certificate produces an explicit rotation witness $j \in \{1, \dots, 16\}$ such that: $$\text{brgc\_inverse } 17\ ((\text{bitword\_rotate } 17)^j(x)) \ge \text{brgc\_inverse } 17\ x.$$ Specifically, for each candidate $r \in [59623, 59672]$, the word $x$ is formed and its cyclic rotations by $1 \le j \le 16$ positions are computed; at least one rotation yields an inverse Gray rank greater than or equal to that of $x$, so $x$ is not a maximum in its necklace orbit. This inequality directly contradicts the strict inequality required by Lemma 5. Hence, no such sequence $c$ can be lexical, proving that $a$ and $b$ are strictly adjacent.

This completes the proof of lexical_degree_seventeen_class_a_counterexample.

5. Discussion

The theorem lexical_degree_seventeen_class_a_counterexample shows that the class-A structure formula of Theorem 5.1 of DOI 10.1006/jcta.2000.3112 is false: an adjacent pair in $L_n$ with $r > 0$ need not have the smaller sequence equal to $(f_e)^d \delta$. In the example the repetition of $f_e = [3, 1, 1, 3]$ breaks off at the sixth entry, where $a$ has a 2 instead of a 1, and $a$ is still adjacent to $b$ in $L_{17}$. Since $17$ is prime, every meet of two distinct sequences of $L_{17}$ falls in class A, so the failure is not tied to a boundary case of the classification.

The counterexample concerns only this factorization. It does not show that other parts of Theorem 5.1, or other results of the paper, are wrong. Arguments that cite the factorization from Theorem 5.1 need another justification for that step.

The method is the main reusable part. Adjacency in $L_n$ is a universal statement over an unbounded family of sequences. Lexical order on sequences of equal sum is inverse Gray-rank order (alpha_lexical_lt_iff_inverse_prefix), which turns the sequences between $a$ and $b$ into an interval of ranks, here the 50 integers strictly between 59622 and 59673; at prime length, lexicality is rotation maximality of the completed word (alpha_lexical_odd_completion_iff_rotation_max_of_prime), which each rank can be tested against by a finite computation.

Questions that remain open:

  • What is the correct structure of class-A adjacent pairs? A replacement for the factorization $a = (f_e)^d \delta$, valid for all $n, m, d, r$ with $r > 0$, is not known.
  • Does the formula fail in infinitely many degrees, and which pairs violate it? This post gives one pair in degree 16.

Why it is research-level

  • Gives an explicit prime-degree counterexample to the repeated-prefix class-A formula in the 2000 lexical-sequence adjacency classification; the necklace conjecture itself remains open

Lean declarations

  • lexical_degree_seventeen_class_a_counterexampleThe 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…
  • alpha_is_lexicalA nonempty positive sequence strictly larger than all its proper nonempty suffixes.
  • alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
  • alpha_lexical_meetThe common left factor, including the minimum value at the first unequal cell.
  • alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
  • 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_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
  • 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.
  • 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.
  • alpha_binary_prefix_boundsThe encoding of a nonempty positive cell sequence has exactly sum(a) bits and starts with a one.
  • brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
  • 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.

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.