# Solved and unsolved problems about abelian squares

@article{Simpson2018SolvedAU, title={Solved and unsolved problems about abelian squares}, author={Jamie Simpson}, journal={arXiv: Combinatorics}, year={2018} }

We present and discuss a number of known results and open problems abelian squares in words on small alphabets.

#### One Citation

Hardness of Detecting Abelian and Additive Square Factors in Strings

- Computer Science
- ESA
- 2021

3SUM-hardness (no strongly subquadratic-time algorithm, assuming the 3SUM conjecture) of several problems related to finding Abelian square and additive square factors in a string is proved and conditional optimality of state-of-the-art algorithms for finding such factors is concluded. Expand

#### References

SHOWING 1-10 OF 20 REFERENCES

Binary Words with Few Squares

- Mathematics, Computer Science
- Bull. EATCS
- 2006

A short proof is given for the result of Fraenkel and Simpson stating that there exists an infinite binary word which has only three different squares u^2. Expand

Circular Words Avoiding Patterns

- Mathematics, Computer Science
- Developments in Language Theory
- 2002

It is proved that there are circular binary cube-free words of every length and several open problems regarding circular words avoiding more general patterns are presented. Expand

Words with the Maximum Number of Abelian Squares

- Mathematics, Computer Science
- WORDS
- 2015

This paper studies infinite words such that the number of abelian square factors of length $n$ grows quadratically with $n$. Expand

On some generalizations of abelian power avoidability

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2015

We prove that 2-abelian-cubes are avoidable over a binary alphabet and that 3-abelian-squares are avoidable over a ternary alphabet, answering positively to two questions of Karhumaki et al. We also… Expand

Strongly Non-Repetitive Sequences and Progression-Free Sets

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 1979

Abstract By a simple method we show the existence of (1) a sequence on two symbols in which no four blocks occur consecutively that are permutations of each other, and (2) a sequence on three symbols… Expand

Palindromes in circular words

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2014

This paper shows, with a very complicated proof, that the number of distinct non-empty palindromes with length at most n in a circular word of length n is less than 5n/3. Expand

Maximum number of distinct and nonequivalent nonstandard squares in a word

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2016

The combinatorics of nonstandard squares in a word depends on how the equivalence of halves of the square is defined, and several results on the maximum number of distinct squares for nonstandard factor equivalence relations are presented. Expand

Avoiding large squares in infinite binary words

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2005

An open question of Prodinger and Urbanek from 1979 is answered by demonstrating the existence of two infinite binary words, each avoiding arbitrarilyLarge squares, such that their perfect shuffle has arbitrarily large squares. Expand

Non-repetitive sequences

- Mathematics
- 1970

This note is concerned with infinite sequences whose terms are chosen from a finite set of symbols. A segment of such a sequence is a set of one or more consecutive terms, and a repetition is a pair… Expand

How Many Square Occurrences Must a Binary Sequence Contain?

- Mathematics, Computer Science
- Electron. J. Comb.
- 2003

It is shown that this quantity is a constant fraction of the word length, and it is proved that this constant is 0.55080. Expand