Perfect sequences and arrays of unbounded lengths and sizes over the basic quaternions

The aim of this Thesis is to provide new understanding of the existence of perfect sequences and arrays over the alphabets of quaternions and complex numbers, and multi-dimensional arrays with recursive autocorrelation. Perfect sequences over the quaternion algebra H were first introduced by O. Kuznetsov in 2009. The quaternion algebra is a non-commutative ring, and for this reason, the concepts of right and left autocorrelation and right and left perfection were introduced. Kuznetsov showed that the concepts of right and left perfection are equivalent. One year later, O. Kuznetsov and T. Hall showed a construction of a perfect sequence of length 5,354,228,880 over a quaternion alphabet with 24 elements, namely the double-trahedron group H24. The authors made the following conjecture: there are perfect sequences of unbounded lengths over the double tetrahedron group H_24. We worked on this conjecture and found a family of perfect sequences of unbounded lengths over H8 = {±1, ±i, ±j, ±k}, which is an alphabet more likely to be implemented in Electronic Communication, being smaller than H24 and easier to handle. In our proof of Kuznetsov and Hall’s conjecture, we show that Lee sequences, which are defined over the alphabet {0,1,−1,i,−i} and exist for unbounded lengths, can always be converted, with perfection preserved, into sequences over the basic quaternions {1, −1, i, −i, j}. More generally, we show that every sequence over the complex numbers, that is palindromic about one or two zero-centres, can be converted into a sequence over the quaternions H, preserving its off-peak autocorrelation values. Then, we use the existence of Lee sequences of unbounded lengths to show the existence of perfect sequences over the basic quaternions {1, −1, i, −i, j} of unbounded lengths. We call these sequences over the basic quaternions, by the name, modified Lee sequences. We then use Lee sequences and modified Lee sequences to show the existence of perfect sequences of odd unbounded lengths over the following alphabets:G={±1±i,i}, U_4^∗={±1,±i,1+i} and T={±1±i,1±j}. Once the question of the existence of perfect sequences of unbounded lengths over the basic quaternions is answered, the next question posed in this work concerns arrays: can the array inflation algorithm by Arasu and de Launey be extended to perfect arrays over the basic quaternions? In order to answer this second question, we show that Arasu and de Launey’s algorithm can be modified to inflate perfect arrays over the basic quaternions, preserving perfection and giving approximately equal numbers of the eight basic quaternions 1, −1, i, −i, j, −j, k and −k. We also show that all modified Lee Sequences of length m = p + 1 ≡ 2(mod 4), where p is a prime number, can be folded into a perfect two-dimensional array(with only one occurrence of the element j) of size 2 × (m/2) , with GCD(2, m/2 ) = 1. Each of these arrays can then be inflated into a perfect array of size 2p × (m/2) p, with approximately equal numbers of the eight basic quaternions 1, −1, i, −i, j, −j, k and −k. And so, we have a family of perfect arrays of unbounded sizes over the basic quaternions.