Ten Squares Force an Overlap

Jeffrey Shallit

arxiv: 2605.28570 · v1 · pith:Z3FRS6G2new · submitted 2026-05-27 · 🧮 math.CO · cs.DM· cs.FL

Ten Squares Force an Overlap

Jeffrey Shallit This is my paper

Pith reviewed 2026-06-29 11:29 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.FL

keywords binary squaresoverlapconcatenationoverlap-freecombinatorics on wordsavoidabilityThue wordssquare factors

0 comments

The pith

Concatenating ten or more binary squares always produces an overlap, and the bound is tight.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that over two letters, any concatenation of ten or more squares must contain an overlap, a repetition of the form axaxa. Shorter concatenations can avoid overlaps, making ten the smallest number that forces the pattern. The same does not hold over three letters, where overlap-free square concatenations can be arbitrarily long. A reader would care because the result pins down exactly when square factors become unavoidable in binary words, separating finite from infinite avoidability. The argument rests on checking all short cases to establish both the forcing threshold and its sharpness.

Core claim

We prove that every concatenation of 10 or more binary squares contains an overlap. The bound 10 is best possible. In contrast, over a ternary alphabet, there are infinitely long overlap-free words that consist of a concatenation of squares.

What carries the argument

The threshold number 10, which forces an overlap in any binary square concatenation and is shown to be minimal by explicit examples of length 9.

Load-bearing premise

Exhaustive enumeration has found all overlap-free concatenations of nine or fewer binary squares and confirmed none exist for ten or more.

What would settle it

An explicit concatenation of ten binary squares whose resulting word contains no overlap pattern axaxa.

read the original abstract

We prove that every concatenation of $10$ or more binary squares contains an overlap. The bound $10$ is best possible. In contrast, over a ternary alphabet, there are infinitely long overlap-free words that consist of a concatenation of squares.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Shallit pins down a sharp threshold: ten binary squares force an overlap, nine do not, with a clean contrast to the ternary case.

read the letter

Shallit shows that any concatenation of ten or more squares over a binary alphabet must contain an overlap, and that nine is achievable without one. The paper also records that the ternary case allows arbitrarily long overlap-free square concatenations.

The new content is the exact cutoff at ten for the binary alphabet. The argument establishes both the forcing direction and the matching example that shows the bound cannot be lowered. This kind of precise threshold is the sort of fact that gets used when people classify morphisms or build long overlap-free words.

The paper keeps the claim self-contained and states the ternary contrast explicitly, which helps locate the result. The combinatorial nature of the claim means the main work is in the case analysis or enumeration that rules out overlap-free sequences of length ten while exhibiting one of length nine.

The soft spot is the completeness of whatever enumeration or case split is used for the optimality part. If the check for nine-square sequences is computer-assisted, a referee will want the generation method and the overlap test spelled out so it can be rerun. No formal verification is mentioned, so that remains a point a careful reader would verify by hand or by code.

The paper is aimed at people who work on repetition thresholds and square-free constructions in combinatorics on words. Anyone tracking sharp bounds in this subfield will want the result on file.

It should go to peer review. The central statement is narrow and checkable, and the ternary comparison adds context without overclaiming.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that every concatenation of 10 or more binary squares contains an overlap, with the bound 10 being optimal because there exists at least one overlap-free concatenation of exactly 9 binary squares. It further shows that, over a ternary alphabet, there exist arbitrarily long (in fact infinite) overlap-free words that are concatenations of squares.

Significance. If the central claims hold, the result supplies a sharp, falsifiable threshold in combinatorics on words for when overlaps are forced under square concatenation over a binary alphabet. This complements classical constructions such as the Thue-Morse word and overlap-free morphisms. The ternary construction demonstrates that the forced-overlap phenomenon is alphabet-dependent. The reliance on exhaustive enumeration for both the forcing statement and the optimality bound makes the result concrete and checkable once the enumeration is fully documented.

major comments (2)

[Section establishing the binary optimality bound] The optimality claim (existence of an overlap-free 9-square concatenation and non-existence for 10 or more) rests on exhaustive enumeration of binary square sequences; the manuscript must specify the precise generation procedure for all candidate square concatenations up to length 9, the overlap-detection algorithm, and any pruning rules, so that completeness can be independently verified.
[Section proving that 10 squares force an overlap] The proof that every concatenation of 10 binary squares contains an overlap likewise depends on exhaustive case analysis or computer search; without an explicit description of the search space, the overlap checker, and confirmation that all possible orderings and lengths were considered, the completeness of the argument cannot be assessed.

minor comments (2)

The abstract is concise; the introduction would benefit from a short comparison with known results on overlap-free binary words (e.g., the maximal length of overlap-free binary words that are not necessarily square concatenations).
If any part of the enumeration is implemented in code, the source code or pseudocode should be included or linked to ensure reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater transparency in the computational components of the proof. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Section establishing the binary optimality bound] The optimality claim (existence of an overlap-free 9-square concatenation and non-existence for 10 or more) rests on exhaustive enumeration of binary square sequences; the manuscript must specify the precise generation procedure for all candidate square concatenations up to length 9, the overlap-detection algorithm, and any pruning rules, so that completeness can be independently verified.

Authors: We agree that the current version lacks sufficient detail on the enumeration used to establish optimality. In the revised manuscript we will add an explicit subsection describing: (i) the recursive generation procedure that enumerates all finite sequences of binary squares of total length at most that of the longest 9-square example, (ii) the linear-time overlap-detection routine based on the standard definition of an overlap, and (iii) the pruning rules (length bounds and early termination when an overlap is found) that render the search feasible. These additions will allow independent verification that an overlap-free 9-square concatenation exists while none exists for 10 squares. revision: yes
Referee: [Section proving that 10 squares force an overlap] The proof that every concatenation of 10 binary squares contains an overlap likewise depends on exhaustive case analysis or computer search; without an explicit description of the search space, the overlap checker, and confirmation that all possible orderings and lengths were considered, the completeness of the argument cannot be assessed.

Authors: We concur that the computer-assisted portion of the forcing argument requires fuller documentation. The revision will include a precise specification of the search space (all sequences of exactly 10 binary squares whose total length is bounded by a computable constant derived from the square-length distribution), the same overlap checker referenced above, and a short argument showing that every possible ordering and length combination falls within the enumerated range. This will make the completeness of the case analysis verifiable without changing the logical structure of the proof. revision: yes

Circularity Check

0 steps flagged

No circularity; standard exhaustive enumeration proof

full rationale

The paper establishes a combinatorial statement (every 10+ binary square concatenation contains an overlap, with 10 tight) via exhaustive case analysis of finite concatenations. This is a direct, non-self-referential proof technique with no fitted parameters, no predictions derived from the result itself, and no load-bearing self-citations or ansatzes. The enumeration checks an external property (overlap-freeness) on generated words and does not reduce to the claim by construction. Self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions of squares and overlaps in combinatorics on words together with exhaustive verification that nine squares can avoid overlaps while ten cannot. No free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)

standard math Standard definitions of square (xx) and overlap (axaxa) in finite words over a finite alphabet.
Invoked implicitly when stating the theorem; these are background notions from the field.

pith-pipeline@v0.9.1-grok · 5541 in / 1140 out tokens · 24812 ms · 2026-06-29T11:29:04.740732+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

10 extracted references

[1]

Allouche and J

J.-P. Allouche and J. Shallit.Automatic Sequences: Theory, Applications, Generaliza- tions. Cambridge University Press, Cambridge, 2003

2003
[2]

D. A. Bean, A. Ehrenfeucht, and G. McNulty. Avoidable patterns in strings of symbols. Pacific J. Math.85(1979), 261–294

1979
[3]

Berstel.Axel Thue’s Papers on Repetitions in Words: a Translation

J. Berstel.Axel Thue’s Papers on Repetitions in Words: a Translation. Number 20 in Publications du Laboratoire de Combinatoire et d’Informatique Math´ ematique. Univer- sit´ e du Qu´ ebec ` a Montr´ eal, February 1995

1995
[4]

Currie and N

J. Currie and N. Rampersad. Infinite words containing squares at every position.RAIRO Inform. Th´ eor. App.44(2010), 113–124

2010
[5]

Karhum¨ aki and J

J. Karhum¨ aki and J. Shallit. Polynomial versus exponential growth in repetition-free binary words.J. Combin. Theory. Ser. A105(2) (2004), 335–347. 7

2004
[6]

A.-J. Kfoury. Square-free and overlap-free words. In G. Mirkowska and H. Rasiowa, editors,Mathematical Problems in Computation Theory, Vol. 21 ofBanach Center Pub- lications, pp. 285–297. PWN – Polish Scientific Publishers, Warsaw, 1988

1988
[7]

Restivo and S

A. Restivo and S. Salemi. Overlap free words on two symbols. In M. Nivat and D. Perrin, editors,Automata on Infinite Words, Vol. 192 ofLecture Notes in Computer Science, pp. 198–206. Springer-Verlag, 1985

1985
[8]

Restivo and S

A. Restivo and S. Salemi. Some decision results on nonrepetitive words. In A. Apostolico and Z. Galil, editors,Combinatorial Algorithms on Words, pp. 289–295. Springer-Verlag, 1985

1985
[9]

R. O. Shelton and R. P. Soni. Chains and fixing blocks in irreducible binary sequences. Discrete Math.54(1985), 93–99

1985
[10]

A. Thue. ¨Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.Norske vid. Selsk. Skr. Mat. Nat. Kl.1(1912), 1–67. Reprinted inSelected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 413–478. 8

1912

[1] [1]

Allouche and J

J.-P. Allouche and J. Shallit.Automatic Sequences: Theory, Applications, Generaliza- tions. Cambridge University Press, Cambridge, 2003

2003

[2] [2]

D. A. Bean, A. Ehrenfeucht, and G. McNulty. Avoidable patterns in strings of symbols. Pacific J. Math.85(1979), 261–294

1979

[3] [3]

Berstel.Axel Thue’s Papers on Repetitions in Words: a Translation

J. Berstel.Axel Thue’s Papers on Repetitions in Words: a Translation. Number 20 in Publications du Laboratoire de Combinatoire et d’Informatique Math´ ematique. Univer- sit´ e du Qu´ ebec ` a Montr´ eal, February 1995

1995

[4] [4]

Currie and N

J. Currie and N. Rampersad. Infinite words containing squares at every position.RAIRO Inform. Th´ eor. App.44(2010), 113–124

2010

[5] [5]

Karhum¨ aki and J

J. Karhum¨ aki and J. Shallit. Polynomial versus exponential growth in repetition-free binary words.J. Combin. Theory. Ser. A105(2) (2004), 335–347. 7

2004

[6] [6]

A.-J. Kfoury. Square-free and overlap-free words. In G. Mirkowska and H. Rasiowa, editors,Mathematical Problems in Computation Theory, Vol. 21 ofBanach Center Pub- lications, pp. 285–297. PWN – Polish Scientific Publishers, Warsaw, 1988

1988

[7] [7]

Restivo and S

A. Restivo and S. Salemi. Overlap free words on two symbols. In M. Nivat and D. Perrin, editors,Automata on Infinite Words, Vol. 192 ofLecture Notes in Computer Science, pp. 198–206. Springer-Verlag, 1985

1985

[8] [8]

Restivo and S

A. Restivo and S. Salemi. Some decision results on nonrepetitive words. In A. Apostolico and Z. Galil, editors,Combinatorial Algorithms on Words, pp. 289–295. Springer-Verlag, 1985

1985

[9] [9]

R. O. Shelton and R. P. Soni. Chains and fixing blocks in irreducible binary sequences. Discrete Math.54(1985), 93–99

1985

[10] [10]

A. Thue. ¨Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.Norske vid. Selsk. Skr. Mat. Nat. Kl.1(1912), 1–67. Reprinted inSelected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 413–478. 8

1912