RUI: Extremal Combinatorics of Patterns, Correlation, and Structure

Combinatorics considers finite structures, many of which play a crucial role in problems that arise in science and technology. Preeminent among these structures are finite binary sequences (strings of zeroes and ones) that are used in the communications networks, cryptographic systems, remote sensing, acoustic design, and efficient operation of scientific instrumentation. Other finite structures arising from polynomials, sets, and graphs also find use in a wide variety of technological and scientific endeavors. To achieve an engineering goal or understand a natural process, one must often find the structures that are extremal (minimal or maximal) with respect to a certain feature. For example, we might seek a family of binary sequences that resemble each other as little as possible in order avoid mutual interference in a multi-user communications network: this is the problem of low correlation. The solutions to such extremal problems often involve mathematical objects with a large amount of structure. This research project aims to investigate some problems in extremal combinatorics and the mathematical structures involved in these extremal problems.

The organizing principle of this project is to investigate important problems in pure mathematics involving highly structured discrete objects, many of which are of great interest in science and technology. For example, the problem of minimizing aperiodic autocorrelation of binary sequences is of vital importance in engineering applications like remote sensing and communication. Later, physicists noted that the minima describe the ground states of certain systems in statistical physics. Yet the problem is also related to questions in harmonic analysis raised by Littlewood in 1966 and still actively researched, with recent contributions from the principal investigator that are being further developed. Problems such as this are rich in connections to other branches of mathematics, because the optimal or best known discrete structures for them often come from fields like number theory, algebra, or geometry. For example, the sequences with lowest known asymptotic aperiodic autocorrelation derive from the Fekete polynomials in analytic number theory. The Weil sums studied in this project originate in number theory and arithmetic algebraic geometry: they provide a method for counting points on curves over finite fields. In technology, they determine the nonlinearity of functions used in cryptography, the weight distribution of error-correcting codes, and the cross-correlation properties of linear recursive sequences over finite fields. New techniques to bound the maximum number of instances of a pattern in a finite set of points in the plane utilize diverse techniques that range from order relations to topological arguments. The interplay of all these ideas, pure and applied, leads to a mutual enrichment of mathematics, engineering, and science.