# P2818: The three-halves bound for distinct squares in circular words

- ID: `P2818`
- Reference: `circular-distinct-squares-three-halves`
- Page: https://theoremdb.org/statements/P2818
- Record maturity: Reviewed problem with recorded work

## Problem

For a word \(w\) of length \(n\), let \(s(w)\) be the number of distinct words of the form \(uu\), with \(u\ne\epsilon\), that occur as factors of \(ww\) of length at most \(n\). Is \(s(w)\le\lceil3n/2\rceil\) for every finite word \(w\)?

### Problem setup

- **Definition.** A factor is a contiguous block, and occurrences that spell the same word are counted once.
- **Remark.** Passing to \(ww\) and restricting factor length to at most \(n\) records exactly the factors of the circular word represented by \(w\).
- **Definition.** A square is a nonempty word repeated twice consecutively.

### What counts as a solution

- Prove \(s(w)\le\lceil3|w|/2\rceil\) for every finite word \(w\), or give a word \(w\) and a complete list of more than \(\lceil3|w|/2\rceil\) distinct square factors of \(ww\) having length at most \(|w|\).

## Status

Current checked results give infinitely many lower constructions with \(3n/2-O(\sqrt n)\) distinct circular squares and the universal upper bound \(s(w)\le5n/3\); whether \(s(w)\le\lceil3n/2\rceil\) for every finite word remains open. [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (Five-thirds is the current checked upper bound).** Current checked results give infinitely many lower constructions with \(3n/2-O(\sqrt n)\) distinct circular squares and the universal upper bound \(s(w)\le5n/3\); whether \(s(w)\le\lceil3n/2\rceil\) for every finite word remains open.

Let s(w) count the distinct square words occurring among the rotations of a word w of length n, equivalently the distinct square factors of ww whose total length is at most n. Li and Song's Main Theorem gives s(w) <= 5n/3 for every finite word w. Since s(w) is integral, this also gives s(w) <= floor(5n/3). The result leaves the three-halves target open.

### Background and intake notes

The gap between the current five-thirds upper bound and Fibonacci-word lower constructions is narrow enough for structural lemmas to accumulate. Lists of runs, double-square configurations, and extremal circular words can all be checked and reused.

- Original intake status: UNKNOWN as of 2026-07-27. A 2026 paper proves \(s(w)\le5n/3\), improving the earlier \(\lceil1.8n\rceil\) bound, and reports \(3n/2\) as the conjectured sharp constant.
- 2026-07-27 status search checked the CPM 2026 paper, its cited ordinary-word square bound, and the May 2026 improvement to \(5n/3\). None proves the stated three-halves upper bound.
- The strongest checked upper bound is \(5n/3\); the strongest checked lower construction has \(3n/2-O(\sqrt n)\) distinct squares for infinitely many lengths.
- Any proof must control equality of square words across different rotations, rather than merely count square occurrences or starting positions.

- Recorded example: The word \(w=aaaa\) has the distinct circular square factors \(aa\) and \(aaaa\), so \(s(w)=2\).

### Other known results

- **Computation 1** (reproduced): Independent exhaustive programs give maxima 0,1,1,2,3,4,4,6,6,9,8,10,11,13 at lengths 1 through 14.
- **Computation 2** (reproduced): Two exhaustive binary programs agree on total, short-square, long-square, primitive, and nonprimitive maxima for every length through 26. [3](#reference-3)
- **Claim 2** (supported): The CPM 2026 construction gives infinitely many lengths with at least 1.5n minus O(sqrt(n)) distinct circular square factors. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): The primary source states CS(n) <= 1.5n, which is floor(3n/2) for integer CS(n); the live canonical target asks the weaker ceiling bound at odd n. [1](#reference-1) [2](#reference-2) [3](#reference-3)
- **Route 2** (ruled out): For w=u^2 with pairwise-distinct letters in u, every one-letter deletion reduces the square count from |u| to one.
- **Route 3** (ruled out): A binary word of length 12 has nine distinct squares of total length at most 6, exceeding the proposed ceiling of 6.

### Open directions

- **Route 4** (reported): Instrument Li and Song's Lemma 13 case and search for the missing independent-cycle or odd-power-class charge needed to improve 5n/3 to 3n/2. [2](#reference-2)

### Runnable artifacts

- **Artifact 1** (reproduced): A complete C++17 program checks every alphabet-renaming class through length 14 and reports total, primitive, and nonprimitive maxima.
- **Artifact 2** (reproduced): An independent C++17 implementation matches every total, primitive, and nonprimitive maximum through length 14.
- **Artifact 3** (reproduced): The program checks every binary word modulo complement and reports five exact maxima series.
- **Artifact 4** (reproduced): A second binary implementation uses substring comparison and reproduces all five maxima series through length 26.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `circular-distinct-squares-three-halves`, 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>Charalampopoulos, Panagiotis, Mohamed, Manal, Radoszewski, Jakub, Rytter, Wojciech, Waleń, Tomasz, and Zuba, Wiktor, “Improved Bounds on the Maximum Number of Distinct Squares in Circular Words”. LIPIcs, Volume 369, CPM 2026 (2026). DOI 10.4230/LIPIcs.CPM.2026.6. The conjectured sharp constant is stated in the 2026 circular-squares literature; this CC0 record is an original restatement prepared on 2026-07-27. https://doi.org/10.4230/LIPIcs.CPM.2026.6
   - Also cited at Panagiotis Charalampopoulos et al., Improved Bounds on the Maximum Number of Distinct Squares in Circular Words, LIPIcs CPM 2026, DOI 10.4230/LIPIcs.CPM.2026.6, Theorem 12 and its proof on pages 6:6, with the conjecture in Final Remarks on page 6:12
   - Also cited at Abstract, Theorem 12, Theorem 27, and Final Remarks
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Gives the 3n/2 minus lower-order-term construction and states the three-halves conjecture.
   - Source used to assess the problem's recorded status.
   - For The three-halves bound for distinct squares in circular words: The primary source states CS(n) <= 1.5n, which is floor(3n/2) for integer CS(n); the live canonical target asks the weaker ceiling bound at odd n.
2. <a id="reference-2"></a>Shuo Li and Yuan Song, “A Tighter Upper Bound for the Number of Distinct Squares in Circular Words”. arXiv:2605.12215 (2026). Shuo Li and Yuan Song, A Tighter Upper Bound for the Number of Distinct Squares in Circular Words, arXiv:2605.12215v1, Main Theorem on pages 1-2, proof on pages 6-10, and Conclusion on page 10 https://arxiv.org/abs/2605.12215
   - Also cited at v1 submission history, Main Theorem, proof, and Conclusion
   - Also cited at Li and Song, arXiv:2605.12215v1, Lemmas 9, 10, 12, and 13 and the proof of the Main Theorem on pages 6-10
   - preprint; reference source; arXiv source revision v1; checked 2026-07-28
   - Source use: citation_only
   - Proves the current 5n/3 upper bound for distinct square factors in circular words.
   - For The three-halves bound for distinct squares in circular words: Proves the current 5n/3 upper bound for the exact circular-word quantity.
3. <a id="reference-3"></a>definition in Section 2, Lemma 1 and Figure 1, Conclusion https://arxiv.org/abs/1708.00639
   - Also cited at Section 3, Lemma 1 and Figure 1
   - preprint; reference source; arXiv:1708.00639, version checked 2026-08-01; checked 2026-07-28
   - Source use: citation_only
   - Gives the earlier circular-word square bound used as the comparison point for the 2026 improvements.