# Avoiding Squares and Overlaps Over the Natural Numbers

- Published in 2009
- Added on

In the collection

We consider avoiding squares and overlaps over the natural numbers, using a greedy algorithm that chooses the least possible integer at each step; the word generated is lexicographically least among all such infinite words. In the case of avoiding squares, the word is 01020103..., the familiar ruler function, and is generated by iterating a uniform morphism. The case of overlaps is more challenging. We give an explicitly-defined morphism phi : N* -> N* that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all h,k in N with h <= k, the word phi^{k-h}(h) is the lexicographically least overlap-free word starting with the letter h and ending with the letter k, and give some of its symmetry properties.

## Links

## Other information

- key
- AvoidingSquaresandOverlapsOvertheNaturalNumbers
- type
- article
- date_added
- 2016-10-03
- date_published
- 2009-07-24

### BibTeX entry

@article{AvoidingSquaresandOverlapsOvertheNaturalNumbers, key = {AvoidingSquaresandOverlapsOvertheNaturalNumbers}, type = {article}, title = {Avoiding Squares and Overlaps Over the Natural Numbers}, author = {Mathieu Guay-Paquet and Jeffrey Shallit}, abstract = {We consider avoiding squares and overlaps over the natural numbers, using a greedy algorithm that chooses the least possible integer at each step; the word generated is lexicographically least among all such infinite words. In the case of avoiding squares, the word is 01020103..., the familiar ruler function, and is generated by iterating a uniform morphism. The case of overlaps is more challenging. We give an explicitly-defined morphism phi : N* -> N* that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all h,k in N with h <= k, the word phi^{\{}k-h{\}}(h) is the lexicographically least overlap-free word starting with the letter h and ending with the letter k, and give some of its symmetry properties.}, comment = {}, date_added = {2016-10-03}, date_published = {2009-07-24}, urls = {http://arxiv.org/abs/0901.1397v1,http://arxiv.org/pdf/0901.1397v1}, collections = {Integerology}, url = {http://arxiv.org/abs/0901.1397v1 http://arxiv.org/pdf/0901.1397v1}, urldate = {2016-10-03}, archivePrefix = {arXiv}, eprint = {0901.1397}, primaryClass = {math.CO}, year = 2009 }