Distinct squares in circular words

DOI10.1007/978-3-319-67428-5_3MaRDI QIDQ5150916zbMATH OpenOpenAlexFDO

Authors Mika Amit, Paweł Gawrychowski

Publication date 16 February 2021

Published in String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.00639

zbMATH Keywords

circular wordssquares conjecture

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: A circular word, or a necklace, is an equivalence class under conjugation of a word. A fundamental question concerning regularities in standard words is bounding the number of distinct squares in a word of length $n$. The famous conjecture attributed to Fraenkel and Simpson is that there are at most $n$ such distinct squares, yet the best known upper bound is $1.84n$ by Deza et al. [Discr. Appl. Math. 180, 52-69 (2015)]. We consider a natural generalization of this question to circular words: how many distinct squares can there be in all cyclic rotations of a word of length $n$? We prove an upper bound of $3.14n$. This is complemented with an infinite family of words implying a lower bound of $1.25n$.

Recommendations

• A note on the number of squares in a word
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• How many squares can a string contain?
• A stronger square conjecture on binary words
• scientific article; zbMATH DE number 1943964

Cites work

• A New Periodicity Lemma
• A note on the number of squares in a word
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• Circular Sturmian words and Hopcroft's algorithm
• Counting distinct squares in partial words
• Equations on palindromes and circular words
• How many double squares can a string contain?
• How many squares can a string contain?
• scientific article; zbMATH DE number 1948509 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 7361969 (Why is no real title available?)
• Intersecting periodic words
• Linear-Time Sequence Comparison Using Minimal Absent Words & Applications
• More results on overlapping squares
• On ternary square-free circular words
• Palindromes in circular words
• Square-density increasing mappings
• Squares, cubes, and time-space efficient string searching
• The maximum number of squares in a tree
• The three squares lemma revisited
• There are ternary circular square-free words of length \(n\) for \(n \geq\) 18
• Three overlapping squares: the general case characterized \& applications
• Uniqueness Theorems for Periodic Functions

Cited in

(12)

• Lower bounds for the number of repetitions in 2D strings
• Square network on a word
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• On the number of \(k\)-powers in a finite word
• A stronger square conjecture on binary words
• Balance Properties and Distribution of Squares in Circular Words
• BALANCE PROPERTIES AND DISTRIBUTION OF SQUARES IN CIRCULAR WORDS
• Palindromes in circular words
• scientific article; zbMATH DE number 1948509 (Why is no real title available?)
• scientific article; zbMATH DE number 7361969 (Why is no real title available?)
• Density of distinct squares in non-primitive words
• Characterization of dense patterns having distinct squares

This page was built for publication: Distinct squares in circular words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5150916)