Period-doubling prefix palindromic length is not 2-regular
Let be the fixed point beginning with 0 of the substitution , (the period-doubling word). Let be the least number of nonempty palindromes whose concatenation is the length- prefix of , with , and put . Frid, Laborde and Peltomäki conjectured that is not 2-automatic, and so is not 2-regular. Is that true?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Computation
- Field
- Combinatorics on words; automatic sequences and palindromic factorization
- Posed by
- Anna E. Frid, Enzo Laborde and Jarkko Peltomäki, On prefix palindromic length of automatic words (2020 preprint; TCS 2021), Conjecture 17 in arXiv v2 / published Conjecture 2.
- Year posed
- 2020
- Years open
- 6y
- Solved
- 2026-10-04
- Model
- OpenAI assistant (dot; underlying model unspecified)
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Unreviewed
- Publication
- Announced
- Significance
- 6 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
The exact period-doubling conjecture is proved: d(n)=P(n+1)−P(n) is not 2-automatic and P is not 2-regular. The proof uses a marker C(n) recording a singleton 1 in some globally optimal factorization. A Gray-code independent-set bound gives nonnegative palindrome-edge slack. Uniform constructions and an all-path diagonal obstruction distinguish infinitely many binary prefixes for C. The sole computer-assisted lemma is an all-length local inclusion proved by complete reachable-state closure, independently implemented twice; finite value tests are not its proof. This does not provide a full closed formula for P or settle the separate Fibonacci conjecture. Classical palindrome structure, automatic-sequence closure and state distinguishability, and the source regularity/difference equivalence are credited. Worldwide priority remains unassessed.
What the AI did
dot (OpenAI) developed the marked-optimum lift, Gray-code lower bound, uniform separating-family constructions, and final all-path obstruction. The model wrote the universal local-inclusion checker and mathematical proof. A separate AI review checked the complete argument and independently implemented a second all-length transition-system proof with different state representations. No external human expert endorsement is claimed.
Verification
Re-checked by this site on 6 October 2026. Both of the submission's checkers passed: the local tiling automaton (2,460 states, 3,092 transitions, 173 eligible ends) and the second checker (1,593 states, 101 eligible ends), with hashes matching the README. A separate computation written here (eertree dynamic programming, not the submission's code) found P(n) for every n up to 2^20 and confirmed the proof's exact lift lemma for every m below 2^19, its N(a,b) formula in all cases in range, and that the windowed 2-kernel keeps growing. These are finite checks. The all-length statement rests on the hand proof (backward lifting and the diagonal obstruction), which was not checked here. The package's review is by the same AI agent and is not independent. No Lean formalisation.
Sources
Submitted by ZestyDingo473 on