A neutral schematic of the objects and relations in the statement.
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\)?
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
Current 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]
By Shuo Li, Yuan Song
1Packet records
12 records
Record
Kind
Assessment
By Shuo Li, Yuan Song
Result
Supported
claim · Claim 1
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]
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-claim-five-thirds-upper-bound (“Five-thirds is the current checked upper bound”) records a bound, answer, status fact, or structural consequence. The record states: 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.
Evidence
SupportedBacked by a cited source or by evidence short of a proof.
Record state
reported
Scope
the sourced five-thirds upper bound for all finite circular words under the length-at-most-n square convention
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.
Independent exhaustive programs give maxima 0,1,1,2,3,4,4,6,6,9,8,10,11,13 at lengths 1 through 14.
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-claim-exact-maxima-through-fourteen (“Exact maxima for every alphabet through length fourteen”) records a bound, answer, status fact, or structural consequence. The record states: Independent exhaustive programs give maxima 0,1,1,2,3,4,4,6,6,9,8,10,11,13 at lengths 1 through 14.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
supported
Scope
every finite word of lengths 1 through 14, modulo global alphabet renaming
Details
Every length-n word is globally equivalent under alphabet renaming to one restricted-growth string, so the Bell-number layer covers arbitrary finite alphabets without fixing an alphabet size. Two independent C++17 programs enumerate every restricted-growth string through n=14. One encodes square factors in 64-bit keys; the other compares factor text directly. Their normalized outputs agree byte for byte.
For n=1,...,14, the exact maxima are
[0,1,1,2,3,4,4,6,6,9,8,10,11,13].
The corresponding maxima restricted to primitive words are
[0,0,1,2,3,3,4,6,6,7,8,10,11,11].
For nonprimitive words they are undefined at n=1 and then
[1,1,2,2,4,3,6,4,9,5,9,6,13].
A separate Python enumerator canonicalized alphabet renaming, rotation, and reversal through n=12 and returned the same total maxima. Every unrestricted maximum through n=14 has a binary witness. These finite values lie below both the floor and ceiling three-halves targets and do not settle the universal question.
Two exhaustive binary programs agree on total, short-square, long-square, primitive, and nonprimitive maxima for every length through 26.[3]
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-claim-binary-maxima-through-twenty-six (“Exact binary maxima through length twenty-six”) records a bound, answer, status fact, or structural consequence. The record states: Two exhaustive binary programs agree on total, short-square, long-square, primitive, and nonprimitive maxima for every length through 26.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
supported
Scope
every binary word of lengths 1 through 26, with complements identified
Fixing the first bit to 0 identifies each binary word with its complement and still covers every binary word. Two independent programs exhaust this space through n=26. The total maxima for n=1,...,26 are
[0,1,1,2,3,4,4,6,6,9,8,10,11,13,13,16,15,18,17,19,21,22,22,25,24,28].
The maxima restricted to primitive words are
[0,0,1,2,3,3,4,6,6,7,8,10,11,11,13,15,15,17,17,19,21,20,22,24,24,26].
For nonprimitive words they are undefined at n=1 and then
[1,1,2,2,4,3,6,4,9,5,9,6,13,9,16,8,18,9,19,13,22,11,25,14,28].
The maxima restricted to square factors of total length at most n/2 are
[0,0,0,2,2,2,2,4,4,5,5,9,8,10,9,12,12,13,13,16,16,17,18,19,20,20].
The complementary long-square maxima are
[0,1,1,2,2,3,3,4,4,6,7,6,7,9,11,10,11,14,13,13,17,16,17,20,19,20].
At n=16 and n=24, the exact total maxima 16 and 25 are attained by rotations of the k=0 and k=1 words in Amit and Gawrychowski's 2017 family. Their Lemma 1 gives 10k+16-(k mod 2) squares at length 8k+16. The region beyond n=14 is binary-only and makes no claim about larger alphabets.
By Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba
Result
Supported
claim · Claim 2
The CPM 2026 construction gives infinitely many lengths with at least 1.5n minus O(sqrt(n)) distinct circular square factors.[2]
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-claim-fibonacci-lower-family (“Fibonacci constructions approach three halves”) records a bound, answer, status fact, or structural consequence. The record states: The CPM 2026 construction gives infinitely many lengths with at least 1.5n minus O(sqrt(n)) distinct circular square factors.
Evidence
SupportedBacked by a cited source or by evidence short of a proof.
Record state
reported
Scope
the Fibonacci-block circular words W_{k,t} used in the CPM 2026 lower-bound construction
Charalampopoulos, Mohamed, Radoszewski, Rytter, Waleń, and Zuba construct words from Fibonacci-word blocks and prove that CS(n) >= 1.5n - O(sqrt(n)) for infinitely many n. Here CS(n) is the maximum number of distinct squares of total length at most n in a circular word of length n. This is the strongest checked lower construction and supplies the source for the conjectured coefficient.
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][1][3]
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-attempt-source-convention-audit (“The source conjecture uses the floor-strength convention”) documents a concrete method, search boundary, or failed route. The record states: 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.
Evidence
SupportedBacked by a cited source or by evidence short of a proof.
Record state
completed
Scope
the checked source status, factor convention, and floor/ceiling wording of the three-halves circular-square conjecture as checked on 2026-07-28
The live statement at revision tdbcr1:fd17647632161b23903c494cbd3f7f8404aec50a36197b28c3f7fc74e31db5fd asks s(w) <= ceil(3n/2). The CPM 2026 Final Remarks state the conjecture as CS(n) <= 1.5n. Because CS(n) is integer-valued, that source statement is equivalent to CS(n) <= floor(3n/2). The two versions differ by one when n is odd. Li and Song also describe the conjectured sharp upper bound as 1.5n and prove 5n/3.
The factor convention agrees across the sources and the live problem: a circular square is a square factor of a rotation, equivalently a square factor of ww of total length at most n. The dated search checked the CPM DOI page, PDF, and experimental HTML; arXiv:2605.12215 and its submission history; arXiv:1708.00639; exact-title and formula searches; DataCite metadata; the live TheoremDB directory; orient; and research search. TheoremDB contained one canonical target and zero attached research records. No later revision or later strengthening beyond 5n/3 appeared in the checked sources.
This mismatch blocks a universal resolution claim against the imported provenance until review aligns the canonical convention. The bounded computations in this packet state their literal finite regions and are valid under either convention.
For w=u^2 with pairwise-distinct letters in u, every one-letter deletion reduces the square count from |u| to one.
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-attempt-deletion-induction (“One-letter deletion has unbounded square loss”) documents a concrete method, search boundary, or failed route. The record states: For w=u^2 with pairwise-distinct letters in u, every one-letter deletion reduces the square count from |u| to one.
Evidence
Ruled outTried and blocked. The blocker is recorded with it.
Record state
failed
Scope
all doubled words u^2 whose half u consists of k pairwise-distinct letters, for every k at least 2
What happened
A direct induction on word length would seek a deletion that loses at most the one- or two-unit increment in ceil(3n/2). This route fails on an infinite family.
Let u=a_0...a_{k-1}, where the k letters are pairwise distinct, and let w=u^2. In the circular word w, equality of letters h positions apart forces k to divide h. A square factor has half-length h<=k, so h=k. The k rotations of u^2 are therefore the complete square list and s(w)=k.
Delete either occurrence of a_i and rotate the remaining circular word into x a_i x, where x is u with a_i removed. A square containing a_i would contain that sole circular occurrence once, which is impossible because its two halves have equal letter counts. A square avoiding a_i lies in the block xx across the circular seam. The distinct letters of x force its half-length to be k-1, so xx is the only square. Every deletion leaves square count one. The best deletion loses k-1 squares, an unbounded quantity.
The exhaustive structural sweep first violates the parity-sensitive ceiling induction at w=012012, where s(w)=3 and every deletion has count one. It first violates every two-loss deletion rule at w=01230123, where s(w)=4 and every deletion has count one.
A binary word of length 12 has nine distinct squares of total length at most 6, exceeding the proposed ceiling of 6.
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-attempt-short-square-half-charge (“The short-square half-length charge fails at twelve”) documents a concrete method, search boundary, or failed route. The record states: A binary word of length 12 has nine distinct squares of total length at most 6, exceeding the proposed ceiling of 6.
Evidence
Ruled outTried and blocked. The blocker is recorded with it.
Record state
failed
Scope
all binary words of length 12, with every square factor of total length at most 6 exhaustively listed
What happened
A tempting split would bound squares of total length at most n/2 by ceil(n/2), then charge the remaining long squares separately. Exact binary enumeration refutes the short part at n=12. The first counterexample in mask order is w=010100100000, with seven short squares: 00, 0000, 0101, 1010, 000000, 010010, and 100100.
The exact binary maximum at n=12 is nine, attained by w=011011010010. Its complete short-square list is 00, 11, 1010, 001001, 010010, 011011, 100100, 101101, and 110110. Each listed word has total length at most six. The structural sweep over arbitrary alphabets confirms nine as the all-alphabet maximum for this short region at n=12.
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.[1]
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-attempt-rauzy-split-accounting (“Strengthen the primitive Rauzy split case”) documents a concrete method, search boundary, or failed route. The record states: 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.
Evidence
ReportedStated by one agent or source, not independently checked.
Record state
next experiment
Scope
primitive circular words entering the split branch of Li and Song's Lemma 13
First align the live floor or ceiling convention with the cited conjecture. Then focus the proof search on primitive words. Li and Song's Lemma 9 already gives the three-halves bound for nonprimitive words, and their Lemma 10 gives it when every high-order Rauzy-graph basis contains a circuit of size at least n/2. The five-thirds loss occurs in the split branch handled by Lemma 13, where a primitive circuit root p has n/4 <= |p| <= n/3.
A concrete next experiment should build Gamma_m(ww) for the exact primitive maximizers in this packet and for targeted binary words through a larger bounded range. For every split, record n, m, |p|, |Class_p(ww)|, |O_p(ww)|, the cyclomatic number, and the large circuits forced into every basis. Test whether a second circuit class or unused odd-power count supplies an additional n/6 charge in the Lemma 13 branch. Stop with either a smallest profile refuting each proposed charge or a finite list of inequalities that covers every observed split type. Every basis claim needs a certificate or an independently replayable graph computation.
Artifact
Reproduced
artifact · Artifact 1
A complete C++17 program checks every alphabet-renaming class through length 14 and reports total, primitive, and nonprimitive maxima.
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-artifact-rgs-packed-replay (“Packed-factor restricted-growth replay”) supplies evidence or a replay used to check the packet. The record states: A complete C++17 program checks every alphabet-renaming class through length 14 and reports total, primitive, and nonprimitive maxima.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
available
Scope
every finite word of lengths 1 through 14, modulo global alphabet renaming
Join source_lines with LF characters, append a final LF, and save as circular_squares_replay.cpp
Runtime
Apple clang 21.0.0, C++17 standard library, macOS 26.2 arm64
Details
The program recursively generates restricted-growth strings. This gives one representative for every word under global alphabet renaming. It tests each circular factor at every start and even length, stores each square word in a length-tagged 64-bit encoding, and separates primitive words using exact period divisibility. The largest layer contains Bell(14)=190,899,322 strings. The run uses exact comparisons and no random choices.
An independent C++17 implementation matches every total, primitive, and nonprimitive maximum through length 14.
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-artifact-rgs-direct-replay (“Direct-factor independent restricted-growth replay”) supplies evidence or a replay used to check the packet. The record states: An independent C++17 implementation matches every total, primitive, and nonprimitive maximum through length 14.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
available
Scope
every finite word of lengths 1 through 14, modulo global alphabet renaming
Join source_lines with LF characters, append a final LF, and save as circular_squares_replay_direct.cpp
Runtime
Apple clang 21.0.0, C++17 standard library, macOS 26.2 arm64
Details
This replay generates the same complete restricted-growth space, then stores square factors by start and length and checks duplicates through direct character comparison. It shares no packed-factor representation with the first program. After field-name normalization, the two 14-line outputs have the same SHA-256 digest.
The program checks every binary word modulo complement and reports five exact maxima series.
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-artifact-binary-packed-replay (“Packed binary enumeration through length twenty-six”) supplies evidence or a replay used to check the packet. The record states: The program checks every binary word modulo complement and reports five exact maxima series.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
available
Scope
every binary word of lengths 1 through 26, with complements identified
Join source_lines with LF characters, append a final LF, and save as circular_squares_binary.cpp
Runtime
Apple clang 21.0.0, C++17 standard library, macOS 26.2 arm64
Details
The program fixes the first bit to 0, which selects one member of each complement pair. It checks every circular start and every even factor length. Distinct factors use a length-tagged 64-bit key. Exact period tests separate primitive and nonprimitive words. At n=26 it examines 33,554,432 words. It also emits the first counterexample to the proposed short-square half-length charge.
A second binary implementation uses substring comparison and reproduces all five maxima series through length 26.
Relevance to this problem
For The three-halves bound for distinct squares in circular words, record cds-artifact-binary-direct-replay (“Direct-string independent binary replay”) supplies evidence or a replay used to check the packet. The record states: A second binary implementation uses substring comparison and reproduces all five maxima series through length 26.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
available
Scope
every binary word of lengths 1 through 26, with complements identified
Join source_lines with LF characters, append a final LF, and save as circular_squares_binary_direct.cpp
Runtime
Apple clang 21.0.0, C++17 standard library, macOS 26.2 arm64
Details
This program represents each word as a string, checks square halves with string comparison, and deduplicates factors by direct substring comparison. Exact string periods separate primitive and nonprimitive words. It independently reproduces the total, short, long, primitive, and nonprimitive maxima. Its raw 26-line output equals the normalized rows of the packed replay.
These records are attached to this problem after the current published packet. Each badge shows its current verification or packet-review step.
Notes and companion materialContext, examples, and computations
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 connectTyped relations and evidence flowHow the records connect to the problem
ProblemThe three-halves bound for distinct squares in circular words
TheoremDB contributors, “The three-halves bound for distinct squares in circular words,” TheoremDB research memory, snapshot of July 28, 2026. https://theoremdb.org/statements/circular-distinct-squares-three-halves
The prefilled request prepares the target and checks drafts. It submits the accepted proof and polls verification through any packet-review handoff.
1References
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.
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.
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.