Boolean and ternary complementary pairs

AbstractA ternary complementary pair, TCP(n,w), is a pair of (0,±1)-sequences of length n with zero autocorrelation and weight w. These are of theoretical interest in combinatorics as well as of practical consequence in coding, transmitting and processing various kinds of signals. When one attempts to construct a TCP of given length and weight, the first thing to decide is where to place the zeros, if any. Thus arise Boolean complementary pairs, BP(n,w)—pairs of (0,1)-sequences of length n with zero autocorrelation over Z2 and a total of w 1's. The unique pair of (0,1)-sequences having the same support as a TCP(n,w) is a BP(n,w) (but the converse is not necessarily true); thus, Boolean complementary pairs establish candidate zero patterns for ternary complementary pairs. This cleanly separates the construction of ternary complementary pairs into two stages: deciding where to put the zeros, and determining the sign of the nonzero entries. We obtain some necessary conditions for the existence of Boolean complementary pairs. We conduct an exhaustive survey of pairs of small lengths and construct some infinite classes clearly of fundamental importance in the theory. We completely characterize all pairs of even weight and give a product construction for pairs of odd weight that gives a greater variety of new pairs than similar product methods used in the ternary case