Double Sequences with Complexity mn+1
Julien Cassaigne · Universitätsbibliothek Gießen · 1999
For usual infinite words, a classical result of Morse and Hedlund states that if the complexity function satisfies $p(n)\geq n$ for some value of $n$, then the word is eventually periodic. To generalize this result to two dimensions (in a way which is still to be precised) is an open problem. We will focus here on the limit case. In one dimension, the non-periodic sequences with lowest possible complexity are Sturmian sequences, for which $p(n) = n + 1$ for all $n$; their structure has been extensively studied. In two dimensions, it seems that this role could be played by double sequences with a rectangle complexity equal to $p(m, n) = mn +1$. We give an exhaustive description of these sequences, showing that they can be of three different types; in two of these types, one-dimensional Sturmian sequences are used to code the boundary between two parts of the plane.