Various problems in engineering and natural science demand binary sequences that do not resemble translates of themselves, that is, the sequences must have small aperiodic autocorrelation at every nonzero shift. If f is a sequence, then the demerit factor of f is the sum of the squared magnitudes of the autocorrelations at all nonzero shifts for the sequence obtained by normalizing f to unit Euclidean norm. The demerit factor is the reciprocal of Golay’s merit factor, and low demerit factor indicates low self-similarity of a sequence under translation. We endow the$2^{\ell } $binary sequences of length$\ell $with uniform probability measure and consider the distribution of their demerit factors. Earlier works used combinatorial techniques to find exact formulas for the mean, variance, skewness, and kurtosis of the distribution as a function of$\ell $. These revealed that for$\ell \geq 4$, the pth central moment of this distribution is strictly positive for every$p \geq 2$. This article shows that for every p, the pth central moment is$\ell ^{-2 p}$times a quasi-polynomial function of$\ell $with rational coefficients. It also shows that, in the limit as$\ell $tends to infinity, the pth standardized moment is the same as that of the standard normal distribution.

Aperiodic autocorrelation is an important indicator of performance of sequences used in communications, remote sensing, and scientific instrumentation. Knowing a sequence’s autocorrelation function, which reports the autocorrelation at every possible translation, is equivalent to knowing the magnitude of the sequence’s Fourier transform. The phase problem is the difficulty in resolving this lack of phase information. We say that two sequences are equicorrelational to mean that they have the same aperiodic autocorrelation function. Sequences used in technological applications often have restrictions on their terms: they are not arbitrary complex numbers, but come from a more restricted alphabet. For example, binary sequences involve terms equal to only +1 and −1. We investigate the necessary and sufficient conditions for two sequences to be equicorrelational, where we take their alphabet into consideration. There are trivial forms of equicorrelationality arising from modifications that predictably preserve the autocorrelation, for example, negating a binary sequence or reversing the order of its terms. By a search of binary sequences up to length 44, we find that nontrivial equicorrelationality among binary sequences does occur, but is rare. An integer n is said to be equivocal when there are binary sequences of length n that are nontrivially equicorrelational; otherwise n is unequivocal. For$n \leq 44$, we found that the unequivocal lengths are 1–8, 10, 11, 13, 14, 19, 22, 23, 26, 29, 37, and 38. We pose open questions about the finitude of unequivocal numbers and the probability of nontrivial equicorrelationality occurring among binary sequences.

Sequences with low aperiodic autocorrelation and crosscorrelation are used in communications and remote sensing. Golay and Shapiro independently devised a recursive construction that produces families of complementary pairs of binary sequences. In the simplest case, the construction produces the Rudin–Shapiro sequences, and in general it produces what we call Golay–Rudin–Shapiro sequences. Calculations by Littlewood show that the Rudin–Shapiro sequences have low mean square autocorrelation. A sequence’s peak sidelobe level is its largest magnitude of autocorrelation over all nonzero shifts. Høholdt, Jensen, and Justesen showed that there is some undetermined positive constant$A$such that the peak sidelobe level of a Rudin–Shapiro sequence of length$2^{n}$is bounded above by$A(1.842626\ldots)^{n}$, where$1.842626\ldots $is the positive real root of$X^{4}-3 X-6$. We show that the peak sidelobe level is bounded above by$5(1.658967\ldots)^{n-4}$, where$1.658967\ldots $is the real root of$X^{3}+X^{2}-2 X-4$. Any exponential bound with lower base will fail to be true for almost all$n$, and any bound with the same base but a lower constant prefactor will fail to be true for at least one$n$. We provide a similar bound on the peak crosscorrelation (largest magnitude of crosscorrelation over all shifts) between the sequences in each Rudin–Shapiro pair. The methods that we use generalize to all families of complementary pairs produced by the Golay–Rudin–Shapiro recursion, for which we obtain bounds on the peak sidelobe level and peak crosscorrelation with the same exponential growth rate as we obtain for the original Rudin–Shapiro sequences.

Pursley and Sarwate established a lower bound on a combined measure of autocorrelation and crosscorrelation for a pair$(f,g)$of binary sequences (i.e., sequences with terms in {−1, 1}). If$f$is a nonzero sequence, then its autocorrelation demerit factor,$\text {ADF}(f)$, is the sum of the squared magnitudes of the aperiodic autocorrelation values over all nonzero shifts for the sequence obtained by normalizing$f$to have unit Euclidean norm. If$(f,g)$is a pair of nonzero sequences, then their crosscorrelation demerit factor,$\text {CDF}(f,g)$, is the sum of the squared magnitudes of the aperiodic crosscorrelation values over all shifts for the sequences obtained by normalizing both$f$and$g$to have unit Euclidean norm. Pursley and Sarwate showed that for binary sequences, the sum of$\text {CDF}(f,g)$and the geometric mean of$\text {ADF}(f)$and$\text {ADF}{(g)}$must be at least 1. For randomly selected pairs of long binary sequences, this quantity is typically around 2. In this paper, we show that Pursley and Sarwate’s bound is met for binary sequences precisely when$(f,g)$is a Golay complementary pair. We also prove a generalization of this result for sequences whose terms are arbitrary complex numbers. We investigate constructions that produce infinite families of Golay complementary pairs, and compute the asymptotic values of autocorrelation and crosscorrelation demerit factors for such families.

A new method is used to resolve a long-standing conjecture of Niho concerning the crosscorrelation spectrum of a pair of maximum length linear recursive sequences of length 22m-1 with relative decimation d=2m+2-3, where m is even. The result indicates that there are at most five distinct crosscorrelation values. Equivalently, the result indicates that there are at most five distinct values in the Walsh spectrum of the power permutation f(x)=xdover a finite field of order 22mand at most five distinct nonzero weights in the cyclic code of length 22m-1 with two primitive nonzeros α and αd. The method used to obtain this result proves constraints on the number of roots that certain seventh degree polynomials can have on the unit circle of a finite field. The method also works when m is odd, in which case the associated crosscorrelation and Walsh spectra have at most six distinct values.

Borwein and Mossinghoff investigated the Rudin-Shapiro-like sequences, which are infinite families of binary sequences, usually represented as polynomials. Each family of Rudin-Shapiro-like sequences is obtained from a starting sequence (which we call the seed) by a recursive construction that doubles the length of the sequence at each step, and many sequences produced in this manner have exceptionally low aperiodic autocorrelation. Borwein and Mossinghoff showed that the asymptotic autocorrelation merit factor for any such family is at most 3, and found the seeds of length 40 or less that produce the maximum asymptotic merit factor of 3. The definition of Rudin-Shapiro-like sequences was generalized by Katz, Lee, and Trunov to include sequences with arbitrary complex coefficients, among which are families of low autocorrelation polyphase sequences. Katz, Lee, and Trunov proved that the maximum asymptotic merit factor is also 3 for this larger class. Here we show that a family of such Rudin-Shapiro-like sequences achieves asymptotic merit factor 3 if and only if the seed is either of length 1 or is the interleaving of a pair of Golay complementary sequences. For small seed lengths where this is not possible, the optimal seeds are interleavings of pairs that are as close as possible to being complementary pairs, and the idea of an almost-complementary pair makes sense of remarkable patterns in previously unexplained data on optimal seeds for binary Rudin-Shapiro-like sequences.

Pairs of binary sequences formed using linear combinations of multiplicative characters of finite fields are exhibited that, when compared with a random sequence pairs, simultaneously achieve significantly lower mean square autocorrelation values (for each sequence in the pair) and significantly lower mean square crosscorrelation values. If we define crosscorrelation merit factor analogously to the usual merit factor for autocorrelation, and if we define demerit factor as the reciprocal of merit factor, then randomly selected binary sequence pairs are known to have an average crosscorrelation demerit factor of 1. Our constructions provide sequence pairs with a crosscorrelation demerit factor significantly less than 1, and at the same time, the autocorrelation demerit factors of the individual sequences can also be made significantly less than 1 (which also indicates better than average performance). The sequence pairs studied here provide combinations of autocorrelation and crosscorrelation performance that are not achievable using sequences formed from single characters, such as maximal linear recursive sequences (m-sequences) and Legendre sequences. In this paper, exact asymptotic formulae are proved for the autocorrelation and crosscorrelation merit factors of sequence pairs formed using linear combinations of multiplicative characters. Data is presented that shows that the asymptotic behavior is closely approximated by sequences of modest length.

It is shown that the pairs of maximal linear recursive sequences (m-sequences) typically have mean square aperiodic crosscorrelation on par with that of random sequences, but that if one takes a pair of m-sequences where one is the reverse of the other, and shifts them appropriately, one can get significantly lower mean square aperiodic crosscorrelation. Sequence pairs with even lower mean square aperiodic crosscorrelation are constructed by taking a Legendre sequence, cyclically shifting it, and then cutting it (approximately) in half and using the halves as the sequences of the pair. In some of these constructions, the mean square aperiodic crosscorrelation can be lowered further if one truncates or periodically extends (appends) the sequences. Exact asymptotic formulas for mean squared aperiodic crosscorrelation are proved for sequences derived from additive characters (including m-sequences and modified versions thereof) and multiplicative characters (including Legendre sequences and their relatives). Data are presented that show that the sequences of modest length have performance that closely approximates the asymptotic formulas.

This corrects a proposition and its proof in the paper “Sharp$p$-Divisibility of Weights in Abelian Codes over${\BBZ}/p^d{\BBZ}$” by Daniel J. Katz (2008). This proposition was used to prove further results in the paper. The rest of the paper (including the main results and all other claims, and their proofs) stands as written, for it is not at all sensitive to the change.

A theorem of McEliece on thep-divisibility of Hamming weights in cyclic codes over Fpis generalized to Abelian codes over Zopf/pdZopf. This work improves upon results of Helleseth-Kumar-Moreno-Shanbhag, Calderbank-Li-Poonen, Wilson, and Katz. These previous attempts are not sharp in general, i.e., do not report the full extent of thep-divisibility except in special cases, nor do they give accounts of the precise circumstances under which they do provide best possible results. This paper provides sharp results onp-divisibilities of Hamming weights and counts of any particular symbol for an arbitrary Abelian code over Zopf/pdZopf. It also presents sharp results on2-divisibilities of Lee and Euclidean weights for Abelian codes over Zopf/4Zopf.

A generalization of McEliece's theorem on the p-adic valuation of Hamming weights of words in cyclic codes is proved in this paper by means of counting polynomial techniques introduced by Wilson along with a technique known as trace-averaging introduced here. The original theorem of McEliece concerned cyclic codes over prime fields. Delsarte and McEliece later extended this to Abelian codes over finite fields. Calderbank, Li, and Poonen extended McEliece's original theorem to cover cyclic codes over the rings Zopf2d, Wilson strengthened their results and extended them to cyclic codes over Zopfpd, and Katz strengthened Wilson's results and extended them to Abelian codes over Zopfpd. It is natural to ask whether there is a single analogue of McEliece's theorem which correctly captures the behavior of codes over all finite fields and all rings of integers modulo prime powers. In this paper, this question is answered affirmatively: a single theorem for Abelian codes over Galois rings is presented. This theorem contains all previously mentioned results and more

Counting polynomial techniques introduced by Wilson are used to provide analogs of a theorem of McEliece. McEliece's original theorem relates the greatest power of p dividing the Hamming weights of words in cyclic codes over GF (p) to the length of the smallest unity-product sequence of nonzeroes of the code. Calderbank, Li, and Poonen presented analogs for cyclic codes over Zopf(2d) using various weight functions (Hamming, Lee, and Euclidean weight as well as count of occurrences of a particular symbol). Some of these results were strengthened by Wilson, who also considered the alphabet Zopf(pd) for p an arbitrary prime. These previous results, new strengthened versions, and generalizations are proved here in a unified and comprehensive fashion for the larger class of Abelian codes over Zopf(pd) with p any prime. For Abelian codes over Zopf4, combinatorial methods for use with counting polynomials are developed. These show that the analogs of McEliece's theorem obtained by Wilson (for Hamming weight, Lee weight, and symbol counts) and the analog obtained here for Euclidean weight are sharp in the sense that they give the maximum power of 2 that divides the weights of all the codewords whose Fourier transforms have a specified support