New bounds on antipowers in words (Q2203608)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New bounds on antipowers in words |
scientific article |
Statements
New bounds on antipowers in words (English)
0 references
7 October 2020
0 references
In combinatorics on words, a \(k\)-power is a word that is the concatenation of \(k\) copies of another nonempty word. Recently, the notion of \emph{antipower} has been introduced. An \(r\)-antipower is the concatenation of \(r\) pairwise distinct words of the same length. For any fixed \(k\) and \(r\), every sufficiently long word cannot avoid simultaneously \(k\)-powers and \(r\)-antipowers. The authors improve upper and lower bounds for the quantity \(N(k,r)\), defined as the shortest length for which every binary word of that length contains a \(k\)-power or an \(r\)-antipower. They also give bounds for larger alphabet sizes. Moreover, the authors show that \(4\)-antipowers can be avoided over alphabets of any size, while a \(3\)-antipower-free infinite word is necessarily over an alphabet of size at most two. They also show that every (finite or infinite) word containing four or more distinct letters must contain a \(3\)-antipower.
0 references
combinatorial problems
0 references
power
0 references
antipower
0 references
avoidance
0 references
growth
0 references