Exact Thue–Morse matching heights in an avoiding population

Section 5 of the separate 10 September 2026 manuscript A classification of biologically unavoidable sequences asks for useful explicit bounds on matching-prefix lengths for its fixed Thue–Morse target. More precisely, let $t(n)$ be the parity of the number of ones in the binary expansion of $n$ . For $w ≥ 2$ , the graph has $w-1 -> w$ labelled $t(w)$ and $w-2 -> w$ labelled $1-t(w)$ , with no edge $0 -> 1$ . A matching path starting at $v$ has label $t(k)$ on its $k$ -th edge, starting with $k=0$ . How large can the number of matching edges be, as a function of $v$ ? The preceding source argument gives finiteness at every start but leaves useful explicit bounds open. This is a quantitative follow-up to the already catalogued classification, not a new claim to solve the original classification problem.

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Combinatorics on words; infinite labelled graphs
Posed by: Separate avg-netizen manuscript, A classification of biologically unavoidable sequences (10 Sep 2026), Section 5; AI role in Section 7. Alexander posed the earlier classification question.
Year posed: 2026
Years open: 0y
Solved: 2026-09-25
Model: OpenAI Codex (GPT-6 family)
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Significance: 5 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

The proof gives an explicit closed formula for the attained maximum $L(v)$ at every natural starting vertex, including $L(0)=1$ , and a certified ten-coordinate integer recurrence that evaluates the same actual-path maximum from binary digits. For $v ≥ 1$ , $3L(v)\le 8v-1$ . Equality holds exactly at $v=3\cdot 2^n-1$ for natural n, where $L(v)=8\cdot 2^n-3$ . The coefficient 8/3 cannot be decreased even after allowing a fixed additive constant. The source note gives the complete piecewise formula. The theorem proves both existence of a path attaining the value and an upper bound on every matching path. This answers the later manuscript's quantitative question for its fixed graph and unshifted target. It does not originate the earlier classification or resolve Alexander's remaining universal-avoider embedding or general ordinal-characterization questions. A bounded literature review is available, but worldwide priority is not certified.

What the AI did

A human collaborator directed the research questions and requested explanations, literature checks and formal verification. Codex agents developed the central mathematical arguments, exploration tools, Lean proofs and exposition. Other agents in the same project reviewed source attribution and informal-to-formal correspondence. These are internal project checks, not independent human expert endorsement. The AI-discovered classification describes model-led proof discovery; it does not assert that a human independently verified the mathematics.

Verification

Checked here on 27 September 2026. GitHub Actions run 36116271138 is green at the pinned commit 19544a4d, under a workflow named Verify, which is what the submission claims. The audited endpoints named in the submission - FullHeight.height_isMaximum, height_formula, height_closed_form, DigitRecurrence.actual_digit_recurrence and evaluate_isMaximum - concern actual matching paths and attained maxima rather than a relaxation, and the permitted logical axioms are propext, Classical.choice and Quot.sound. Lean-checked rather than Lean-verified: the statements are anchored only by the project's own agent review, which the submitter correctly says is not independent, and the site did not rebuild the development. The underlying graph and target are those of the catalog's classification entry, and the question answered is the one raised in Section 5 of the manuscript behind it.

Sources

Submitted by ZestyDingo473 on 25 Sep 2026

Exact Thue–Morse matching heights in an avoiding population

What was actually shown

What the AI did

Verification

Sources

Discussion1