Square-free word¶
A square-free word is a finite or infinite symbol sequence containing no adjacent repetition XX of any nonempty contiguous factor X.
Core Idea¶
A square-free word is a finite or infinite sequence over an alphabet that contains no adjacent repetition of a nonempty block. Formally, no contiguous factor may have the form XX for any nonempty word X. The prohibited square can be as short as a doubled letter or as long as two consecutive copies of a complex substring. Square-freeness is therefore a local avoidance condition imposed at every position and every block length, not a requirement that symbols never recur anywhere in the sequence. Alphabet size controls what constructions are possible.
Scope of Application¶
-
Combinatorics on words. Alphabet size, length, and avoidance constraints determine possible sequences.
-
Morphic constructions. Substitution rules generate arbitrarily long or infinite ternary examples when preservation is proved.
-
Enumeration. Counts and growth rates of admissible words are studied by length and equivalence convention.
-
Recognition algorithms. Every position and block length is tested for exact adjacent duplication.
-
Incremental generation. A prefix is extended only when no newly completed suffix forms a square.
Clarity¶
Square-free word forbids every contiguous factor of the form \(XX\) for nonempty \(X\). Symbols may recur elsewhere; the prohibition concerns immediate repetition of a whole block at any length. Alphabet size, finite or infinite length, and morphism used for construction are therefore central. The term distinguishes squares from palindromes and from runs of a single letter alone.
Manages Complexity¶
Square-free words compress an infinite family of forbidden repetitions into one factor condition: no contiguous nonempty block may occur twice in succession. The combinatorialist tracks alphabet size, word length, substitution rule, and local factors rather than cataloging each repeated motif type. Finite binary and unbounded ternary branches reveal the alphabet threshold. Morphisms generate long or infinite examples from compact rules, and automata or backtracking test candidates.
Abstract Reasoning¶
Factor move. Scan a word for a nonempty contiguous block repeated immediately twice and reject it if any square occurs. Construction move. Extend a prefix symbol by symbol while maintaining square-freeness, using backtracking or morphisms to avoid forbidden suffixes. Alphabet move. Infer feasibility from alphabet size and length, noting the sharp distinction between binary and larger alphabets. Proof move. Establish infinite square-free words by a morphism whose images preserve avoidance under stated conditions. Boundary move.
Knowledge Transfer¶
Within the home domain. Square-free words transfer across combinatorics on words, symbolic dynamics, morphisms, formal languages, and repetition-avoidance constructions when no nonempty contiguous factor occurs twice consecutively. Alphabet size, factor, square, morphism, extension, and infinite construction retain exact roles. Beyond the home domain (C — formal pattern). The definition applies literally to any finite or infinite symbol word. Biological sequences can be tested by the same criterion, but the result alone carries no biological mechanism. Square-free does not forbid separated repetition or repeated symbols, and numerical square-freeness is a different concept.
Relationships to Other Abstractions¶
Current abstraction Square-free word Domain-specific
Parents (1) — more general patterns this builds on
-
Square-free word presupposes Pattern Prime
Square-free word structurally presupposes Pattern rather than being a subtype of it.
Hierarchy path (1) — routes to 1 parentless root
- Square-free word → Pattern → Abstraction
Neighborhood in Abstraction Space¶
Square-free word sits in a moderately populated region (42nd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Formal Sequences & Language Structure (16 abstractions)
Nearest neighbors
- Locally catenative sequence — 0.92
- Unavoidable Pattern — 0.91
- Phonotactics — 0.87
- Hamming Scheme — 0.86
- Morphology — 0.85
Computed from structural-signature embeddings · 2026-10-08