Folgen mit gutem Korrelationsverhalten, Differenzmengen und flache Polynome
Zusammenfassung der Projektergebnisse
A classical problem in sequence design is to identify binary (±1-valued) sequences (or more generally sequences with complex entries of unit magnitude) whose aperiodic autocorrelations are collectively small. This problem is originally motivated by its practical importance in communications engineering and condensed matter physics, but interesting questions in combinatorics, analysis, and number theory have emerged, some of which remain open since decades. There are also intimate connections to classical extremal polynomial questions, and as such the problem has been extensively studied by eminent o mathematicians, such as Littlewood and Erd˝s. In this context one asks for so-called Littlewood polynomials (having coefficients 1 or −1) that provide a good approximation to a function that is constant on the complex unit circle. A Barker sequence has the ideal property that all nontrivial aperiodic autocorrelations are in the set {−1, 0, 1}; if existent, these would also be the solutions to many extremal polynomial problems. Barker sequences are known for several lengths at most 13, but an old conjecture asserts that there are no more. This conjecture was proven in 1961 by Turyn and Storer for Barker sequences of odd length using a laborious induction argument, but the conjecture remains open for even lengths. One result of the project is a new short and elegant proof for Turyn and Storer’s result on the nonexistence of Barker sequences of odd length greater than 13. The main part of the project aims however at obtaining existence results. The merit factor of a sequence, or equivalently the L4 norm on the unit circle of the corresponding polynomial, are normalised measures for the collective smallness of the aperiodic autocorrelations. It was already observed in the early 1980s that binary sequences derived from difference sets are natural candidates for sequences with good merit factor. However, until recently, the analysis of such sequences could only be done for two somewhat canonical difference sets, namely Paley and Singer difference sets. In this project the asymptotic merit factor of binary sequences derived from other difference sets were studied. This in particular solves problems on difference sets dating back to 1991, explains more recent numerical observations by other authors, and proves several conjectures. The principal methods were then extended in order to deal with Lp norms of Littlewood polynomials whose coefficients are derived from difference sets, leading to the first results that give the limiting behaviour of Lp norms for specific sequences of nontrivial Littlewood polynomials and infinitely many p. These polynomials include the Fekete polynomials, which correspond to Paley difference sets. Instead of single sequences with small aperiodic autocorrelations, applications often require pairs of sequences with small aperiodic autocorrelations and crosscorrelations. In this project, pairs of sequences were constructed that are asymptotically optimal in some sense with respect to their combined aperiodic autocorrelations and crosscorrelations. The most significant result of the project concerns a famous conjecture from 1983 by Patterson and Wiedemann on the largest nonlinearity of Boolean functions, or equivalently, on the covering radius of the [2^n , n + 1] Reed-Muller code. This problem can be translated to a problem that asks for the smallest supremum norm on the hypercube {−1, 1}^n of multivariate Littlewood polynomials. This conjecture was proved within the project using a mixture of number-theoretic and probabilistic arguments.
Projektbezogene Publikationen (Auswahl)
- Sequence pairs with asymptotically optimal aperiodic correlation
Ch. Günther, K.-U. Schmidt
- Barker sequences of odd length, Des. Codes Cryptogr. 80 (2016), 409-414
K.-U. Schmidt, Jürgen Willms
(Siehe online unter https://doi.org/10.1007/s10623-015-0104-4) - Lq norms of Fekete and related polynomials, Canad. J. Math. 69 (2017), 807-825
Ch. Günther, K.-U. Schmidt
(Siehe online unter https://doi.org/10.4153/CJM-2016-023-4) - Merit factors of polynomials derived from difference sets, J. Combin. Theory Ser. A 145 (2017), 340-363
Ch. Günther, K.-U. Schmidt
(Siehe online unter https://doi.org/10.1016/j.jcta.2016.08.006) - Flat polynomials, low autocorrelation sequences, and difference sets, Universität Paderborn, Dissertation, 2018
Ch. Günther
- Asymptotically optimal Boolean functions, J. Combin. Theory Ser. A 164 (2019), 50-59
K.-U. Schmidt
(Siehe online unter https://doi.org/10.1016/j.jcta.2018.12.005)
