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 44 matrix, a 3-colored 99 matrix, a 4-colored 1616 matrix, a 5-colored 2525 matrix, a 6-colored 3636 matrix, a 7-colored 4949 matrix, and an 8-colored 6262 matrix. (Note that any submatrix of these matrices are also m-colored matrices.)

For example, the following 3636 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 55, 3-colored 1010, 4-colored 1717, 5-colored 2626, 6-colored 3737, 7-colored 5050, and 8-colored 6363matrices 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.