## Pairwise nonrecurrent sequences

Consider the following intriguing definition:

A pairwise-nonrecurrent sequence is a sequence of symbols (taken here to be the non-negative integers) in which any pair of identical symbols, separated a certain number of digits apart, appears in the sequence, with that separation, at most once.

Our lab discovered, explored, and extended this class of sequences, focusing in particular, in each case, on the leading pairwise-nonrecurrent sequence available - that is, lexographically (i.e., in dictionary order), on the first pairwise-nonrecurrent sequence available for that value of m (the number of distinct symbols used) and n (the length of the sequence).

The first 150 terms of the (unique) infinite leading pairwise-nonrecurrent sequence, composed of m=15 distinct symbols, are:

0,0,1,0,1,1,2,0,2,1,3,2,0,3,3,1,4,2,2,3,0,3,4,1,4,4,5,5,6,4,0,2,1,3,5,2,5,6,6,4,5,6,7,3, 0,7,7,1,8,6,2,4,5,7,8,5,6,8,3,7,9,8,8,1,9,0,2,4,7,9,9,3,5,6,10,10,11,8,6,8,0,9,10,1,7,4, 7,2,9,3,11,10,11,10,5,11,0,10,6,5,12,9,11,8,4,3,12,12,13,1,11,12,6,2,7,4,13,9,10,11,12, 10,0,11,8,13,13,14,12,5,12,3,13,7,14,4,8,13,1,9,14,2,6,7,14,14,12,0,3,2, ...

Note that the pairs {0,0}, {1,1}, {2,2}, {3,3}, etc., appear at most once in this sequence; denoting * as any symbol, the pairs {0,*,0}, {0,*,*,0}, {0,*,*,*,0}, {1,*,1}, {1,*,*,1}, etc., appear at most once as well. Note that the first 10,000 terms of this sequence are available here.

Six examples of leading pairwise-nonrecurrent finite sequences, with m={2,3,4,5,6,7} symbols and of length n={7,14,24,35,49,62}, respectively, are:

0,0,1,1,0,1,0;
0,0,1,1,2,2,1,0,2,0,2,1,0,1;
0,0,1,2,1,2,3,3,0,2,2,0,1,0,3,1,1,0,3,2,3,1,2,3;
0,0,1,1,2,2,3,4,1,4,3,2,3,4,4,2,0,3,0,1,3,1,0,4,2,0,4,2,1,2,0,1,3,3,4;
0,0,1,1,2,3,4,5,2,1,0,5,5,1,4,3,4,3,5,4,4,3,3,2,0,1,5,0,1,2,3,4,0,1,2,5,2,2,5,0,4,3,1,0,3,0,2,4,5;
0,0,1,0,2,3,2,0,4,3,5,5,0,1,2,4,1,6,4,6,0,5,1,1,6,3,5,3,2,5,4,2,6,6,3,0,6,3,4,4,2,1,3,5,4,1,2,2,3,0,5,2,5,1,6,4,5,4,1,0,6,3.

Seven examples of leading pairwise-nonrecurrent periodic sequences (that is, sequences which are pairwise-nonrecurrent even when considered as connected in a ring), with m={2,3,4,5,6,7,8} symbols and of length n={4,9,16,25,36,49,62}, respectively, are:

0,0,1,1;
0,0,1,0,1,2,2,1,2;
0,0,1,0,1,1,2,0,2,3,1,3,2,2,3,3;
0,0,1,0,1,1,2,0,2,1,3,2,2,4,4,0,3,4,3,3,2,1,4,3,4;
0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3;
0,0,1,0,1,2,3,4,3,1,5,4,2,2,3,2,4,6,3,1,1,3,4,1,6,6,5,0,5,4,4,0,4,5,5,6,0,5,6,2,6,3,0,2,6,1,3,5,2;
0,0,1,0,1,1,2,2,0,3,2,4,3,5,0,2,6,6,0,4,5,6,4,6,3,7,4,2,1,7,0,4,4,3,3,6,5,1,3,0,3,7,5,2,5,2,7,5,4,1,4,3,6,1,7,6,5,5,2,1,7,7.

Note that pairwise-nonrecurrent periodic sequences solve the matrix coloring problem, discussed further in Cooper, Fenner, & Purewal (2008) and Fenner, Gasarch, Glover, & Purewal (2009). In particular, circulant Hankel matrices and circulant Toeplitz matrices with top rows given by the seven pairwise-nonrecurrent periodic sequences listed above give immediately: a 2-colored 4×4 matrix, a 3-colored 9×9 matrix, a 4-colored 16×16 matrix, a 5-colored 25×25 matrix, a 6-colored 36×36 matrix, a 7-colored 49×49 matrix, and an 8-colored 62×62 matrix. (Note that any submatrix of these matrices are also m-colored matrices.)

For example, the following 36×36 circulant Toeplitz matrix is 6-colored:

0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3
3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5
5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4
4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1
1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3
3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3
3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2
2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5
5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4
4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0
0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4
4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5
5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3
3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2
2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0
0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1
1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5
5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4
4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5
5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5
5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4,4
4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3,4
4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2,3
3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2,2
2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3,2
2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1,3
3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2,1
1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0,2
2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2,0
0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1,2
2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1,1
1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0,1
1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1,0
0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0,1
1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0,0
0,1,0,1,1,2,0,2,1,3,2,2,3,4,4,5,5,4,5,1,0,2,3,5,4,0,4,5,2,3,3,1,4,5,3,0

Further, as the seven sequences listed above are in fact the longest pairwise-nonrecurrent periodic sequences available at each corresponding value of m, which we have proved via exhaustion, it follows that 2-colored 5×5, 3-colored 10×10, 4-colored 17×17, 5-colored 26×26, 6-colored 37×37, 7-colored 50×50, and 8-colored 63×63matrices with circulant Hankel or circulant Toeplitz structure do not exist.

For further discussion, please see our paper on the subject, a preprint of which is available here.