# P2820: Eventual existence of four-letter circular abelian-square-free words

- ID: `P2820`
- Reference: `circular-abelian-square-free-four-eventual`
- Page: https://theoremdb.org/statements/P2820
- Record maturity: Reviewed problem with recorded work

## Problem

Does there exist an integer \(N\) such that for every \(n\ge N\) there is a word \(w\in\{0,1,2,3\}^n\) for which no factor \(uv\) of \(ww\) with \(0<|uv|\le n\) and \(|u|=|v|\) has \(u\) and \(v\) with the same number of each letter?

### Problem setup

- **Definition.** Two words are abelian equivalent when their four letter-count vectors, also called Parikh vectors, are equal.
- **Definition.** An abelian square is a concatenation \(uv\) of two nonempty equal-length abelian-equivalent words.
- **Remark.** The restriction to factors of \(ww\) of length at most \(n\) tests every factor of the circular word represented by \(w\).

### What counts as a solution

- Give a proof and an explicit threshold \(N\) covering every \(n\ge N\), or prove that infinitely many lengths admit no such circular word.
- For a constructive proof, each generated word or family must come with a complete Parikh-vector avoidance argument, finite-state certificate, or independently checkable verifier.

## Status

Four-letter circular abelian-square-free words exist at arbitrarily large lengths, and the checked source reports no counterexample below length 150; no threshold \(N\) covering every \(n\ge N\) is known, so eventual existence remains open. [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (The source reports no cyclic counterexample below length 150).** Four-letter circular abelian-square-free words exist at arbitrarily large lengths, and the checked source reports no counterexample below length 150; no threshold \(N\) covering every \(n\ge N\) is known, so eventual existence remains open.

The candidate asks for circular avoidance. For a word of length n, it forbids adjacent abelian-equivalent h-blocks only when 2h <= n. Peltomäki and Whiteland define the stronger cyclic condition by forbidding every such pair with h < n in the periodic word w^omega.

Their Theorem 1.2 proves A_infinity(4)=2. Its witnesses are phi^r(01), where phi is Keränen's 85-uniform abelian-square-free morphism, so arbitrarily long four-letter words satisfy the stronger cyclic condition. These lengths form a sparse sequence and give no cofinite length interval.

Section 6 reports that their computer experiments found no counterexample to A(4)=2 among lengths below 150. Any cyclic witness located in that experiment is also a circular witness. The article provides no witness table, code, or certificate for the bounded search, so this record preserves the authors' wording and evidence level. The exact mathematical theorem remains the arbitrarily-long result.

### Background and intake notes

The problem turns a known infinite avoidance phenomenon into a length-complete circular construction. Morphisms, splice lemmas, and certified automata can cover whole congruence classes and remain useful before the final finite set of gaps closes.

- Original intake status: UNKNOWN as of 2026-07-27. The checked primary source establishes neighboring cyclic-avoidance results and leaves eventual existence at every sufficiently large four-letter length as a conjecture.
- 2026-07-27 status search checked the journal and arXiv versions of Avoiding abelian powers cyclically and later citations found by its title; no proof or counterexample to eventual four-letter circular abelian-square-free existence was found.
- Linear infinite abelian-square-free words over four letters are known. Closing a word into a circle introduces factors across the seam, which is the stated obstruction.
- A useful artifact can be a certified length set, a prolongation rule that covers residue classes, or a finite obstruction showing that a proposed morphic closure fails.

- Recorded example: The word \(012\) is circular abelian-square-free under the stated length-at-most-three convention, since it has no even-length factor longer than two and no repeated adjacent letter.

### Other known results

- **Claim 2** (reproduced): A deterministic restricted-growth search found one four-letter circular abelian-square-free word at each length 1 through 36, and a separate direct verifier checked every cyclic start and half-length.
- **Claim 3** (reproduced): Complete enumeration modulo alphabet permutations gives 1,1,1,3,5,14,21,16,12,20,66,177,208,210,405,160 circular abelian-square-free representatives at lengths 1 through 16.

### Prior approaches

- **Route 1** (inconclusive): The exact cycle-coloring conjecture, both avoidance conventions, arXiv revisions, the journal article, and the indexed citing literature were checked; no proof or counterexample to eventual circular existence was located. [2](#reference-2) [1](#reference-1) [3](#reference-3) [4](#reference-4) [5](#reference-5) [6](#reference-6)
- **Route 2** (reproduced): A deterministic search fixed alphabet-name symmetry, pruned every newly completed linear abelian square, and tested seam-crossing factors at complete length; it reached one witness at every n through 36.
- **Route 3** (ruled out): Complete enumeration finds zero valid one-letter insertion edges from any of the 16 length-eight orbits to a length-nine circular word; selected witnesses at 14 later lengths are also insertion dead ends.
- **Route 4** (reproduced): Scanning every factor of the 7,225-letter word phi^2(0) found circular witnesses at 24 lengths in 36 through 100 and exhausted all windows without a witness at the other 41 lengths. [1](#reference-1)
- **Route 5** (timed out): A direct Z3 encoding returned unknown at its 60-second limit for n=36,40,50,60, even though independent witnesses exist at all four lengths.

### Open directions

- **Route 6** (reported): The next useful route is to classify prefix and suffix Parikh-difference profiles of morphic blocks, then certify length intervals closed under a finite set of splices.

### Runnable artifacts

- **Artifact 1** (reproduced): A self-contained standard-library Python program checks all stored witnesses, repeats the complete enumeration through 16, builds the full small insertion graph, and exhausts one-letter moves around each selected word through length 36.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `circular-abelian-square-free-four-eventual`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Peltomäki and Whiteland, Avoiding abelian powers cyclically, Advances in Applied Mathematics 121 (2020), Theorem 1.2, proof in Section 3, and Section 6; arXiv:2006.06307v2 https://arxiv.org/abs/2006.06307
   - Also cited at Peltomäki and Whiteland, Introduction, Theorem 1.2, and Section 6; open-copy locator: journal version of Avoiding abelian powers cyclically
   - Also cited at Peltomäki and Whiteland, Section 3, displayed definition of Keränen's morphism phi; original window scans executed 2026-07-28
   - preprint; reference source; arXiv source revision v2; checked 2026-07-28
   - Source use: citation_only
   - Provides the Keränen-morphism construction used for the packet's certified finite window scan.
   - For Eventual existence of four-letter circular abelian-square-free words: Scanning every factor of the 7,225-letter word phi^2(0) found circular witnesses at 24 lengths in 36 through 100 and exhausted all windows without a witness at the other 41 lengths.
2. <a id="reference-2"></a>Tim E. Wilson and David R. Wood, “Anagram-Free Graph Colouring”. The Electronic Journal of Combinatorics 25(2) (2018), P2.20. DOI 10.37236/6267. Wilson and Wood, Anagram-Free Graph Colouring, Electronic Journal of Combinatorics 25(2) (2018), page 17; later-state audit completed 2026-07-28 https://doi.org/10.37236/6267
   - Also cited at Wilson and Wood 2018, page 17
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Connects circular abelian-square avoidance with anagram-free coloring and records the neighboring existence question.
3. <a id="reference-3"></a>Fici and Puzynina, cyclic abelian avoidance survey passage https://arxiv.org/abs/2207.09937v2
   - preprint; reference source; arXiv:2207.09937v2; checked 2026-07-28
   - Source use: citation_only
   - Surveys abelian and additive powers and records the structural results used to place the four-letter additive-cube target.
4. <a id="reference-4"></a>Svetlana Puzynina and Markus A. Whiteland, Abelian Closures of Infinite Binary Words, arXiv:2008.08125v2 (2021). Introduction, p. 1, citation [23] under abelian repetitions and avoidance; bibliography entry on p. 32 https://arxiv.org/abs/2008.08125
   - preprint; discovery source; arXiv:2008.08125v2; checked 2026-07-28
   - Source use: citation_only
   - Cites cyclic abelian-power avoidance as background without settling the eventual cycle question.
5. <a id="reference-5"></a>Xiao-Tao Lü, Jin Chen, Zhi-Xiong Wen, and Wen Wu, On the 2-binomial complexity of the generalized Thue-Morse words, arXiv:2112.05347v1 (2021). Introduction, p. 1, citation [18] under abelian repetitions and avoidance; bibliography entry on p. 17 https://arxiv.org/abs/2112.05347
   - preprint; discovery source; arXiv:2112.05347v1; checked 2026-07-28
   - Source use: citation_only
   - Cites the cyclic-avoidance article as background and gives no result on eventual circular avoidance.
6. <a id="reference-6"></a>Anuran Maity and K. V. Krishna, Mutually Abelian-Bordered Binary Words, arXiv:2509.20773v1 (2025). Introduction, p. 1, citation [21] in the general abelian-combinatorics bibliography; bibliography entry on p. 31 https://arxiv.org/abs/2509.20773
   - preprint; discovery source; arXiv:2509.20773v1; checked 2026-07-28
   - Source use: citation_only
   - Lists the cyclic-avoidance article in later abelian-combinatorics work without treating the cycle conjecture.