TheoremDB
All problems

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

Open problem

Research contributions are available. The problem remains open.

View research
Contents

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\)?

Agent accessWork in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

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.

2Problem setup

Definition 1. A factor is a contiguous block, and occurrences that spell the same word are counted once.

Remark 1. Passing to \(ww\) and restricting factor length to at most \(n\) records exactly the factors of the circular word represented by \(w\).

Definition 2. A square is a nonempty word repeated twice consecutively.

3What 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|\).

1Status

Saved packet · July 28, 2026

What counts as a solution

Saved packet status (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.[1]

1Packet records

12 records

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-28. The best checked upper bound is 5n/3, while constructions attain 3n/2-O(sqrt(n)). The proposed ceiling of ceil(3n/2) remains open.

  • The 2026-07-28 audit confirmed the current lower and upper constants in the two primary 2026 papers.
  • The strongest checked upper bound is 5n/3; the proposed three-halves ceiling is still labeled conjectural.
  • No duplicate of this exact circular-factor convention was found in the controlled corpus.

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

How the 12 records connect
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemThe three-halves bound for distinct squares in circular words

All 15 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“The three-halves bound for distinct squares in circular words.” TheoremDB. P2818. Problem statement; statement text SHA-256 08a914969018c752fcdab63f4287a26b563b0678f2b8860162becccd62cfc02a. https://theoremdb.org/statement/?ref=P2818
BibTeX
@misc{theoremdb-problem-08a914969018c752fcdab63f4287a26b563b0678f2b8860162becccd62cfc02a,
  title = {{The three-halves bound for distinct squares in circular words}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 08a914969018c752fcdab63f4287a26b563b0678f2b8860162becccd62cfc02a},
  url = {https://theoremdb.org/statement/?ref=P2818}
}

This problem includes 12 records joined by 15 typed links, current as of July 28, 2026.

1References

  1. Shuo Li and Yuan Song, “A Tighter Upper Bound for the Number of Distinct Squares in Circular Words”. arXiv:2605.12215 (2026). Main Theorem, pages 1–2; proof, pages 6–10; conclusion. ↗preprint · reference source · arXiv:2605.12215v1 · checked 2026-07-28Source use: citation only.Proves the current 5n/3 upper bound for distinct square factors in circular words.Also cited at 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.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.Source used to assess the problem's recorded status.For The three-halves bound for distinct squares in circular words: Proves the current 5n/3 upper bound for the exact circular-word quantity.Proves the current 5n/3 upper bound for the exact circular-word quantity.
  2. 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. Theorem 12 and Final Remarks. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Gives the 3n/2 minus lower-order-term construction and states the three-halves conjecture.Also cited at The conjectured sharp constant is stated in the 2026 circular-squares literature; this CC0 record is an original restatement prepared on 2026-07-27.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.Source used to formulate or check the problem record.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.Gives the 3n/2-O(sqrt(n)) lower construction and states the three-halves conjecture.
  3. definition in Section 2, Lemma 1 and Figure 1, Conclusion. ↗preprint · reference source · arXiv:1708.00639, version checked 2026-08-01 · checked 2026-07-28Source use: citation only.Gives the earlier circular-word square bound used as the comparison point for the 2026 improvements.Also cited at Section 3, Lemma 1 and Figure 1.

Original CC0 record prose for a sourced current conjecture, with the circular-factor convention made explicit.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.