Rudin-Shapiro-like polynomials with low correlation

01/23/2018 - 12:15pm
01/23/2018 - 1:10pm
Daniel Katz (Cal State Northridge)

The Rudin-Shapiro polynomials are a sequence of polynomials with coefficients in {+1,-1} arising from an elegant recursive construction that gives them interesting analytic and combinatorial properties. They are known to be very flat on the complex unit circle: if f is a Rudin-Shapiro polynomial and we let z range over the unit circle, then the ratio of the maximum value of |f(z)| to the root mean square value is never larger than the square root of 2. When we identify a polynomial with the sequence of its coefficients, we find that a typical Rudin-Shapiro polynomial has very low autocorrelation: the inner products of the sequence of coefficients with nontrivial translates of itself have considerably smaller mean square magnitude than what one would obtain with a typical random sequence with entries from {+1,-1}. The fact that the inner product is only large when the sequences are perfectly aligned makes such sequences very useful for synchronization in communications networks. For multi-user networks, we want to avoid confusing one user's sequence with another's, so we demand pairs of sequences that also have low cross-correlation (inner product with each other) at all shifts. We investigate pairs of Rudin-Shapiro-Like polynomials, a generalization of Shapiro's original recursive construction, and derive a general formula for their mean square cross-correlation. Borwein and Mossinghoff had shown that there are Rudin-Shapiro-like polynomials with low autocorrelation, and now we have found pairs of polynomials such that both have low autocorrelation and the pair has low mutual cross-correlation. There are bounds on how small these quantities can be, and we have found infinite families that achieve the bounds. This is joint work with Sangman Lee, Eli Moore, and Stanislav A. Trunov.

Millikan 2099, Pomona College
Misc. Information: 

There will be a short organizational meeting in the same room right before the talk at 12:00 noon.