# Avoiding Squares and Overlaps Over the Natural Numbers

• Published in 2009
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.

## Other information

key
AvoidingSquaresandOverlapsOvertheNaturalNumbers
type
article
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 = {},
}