RUI: Extremal Combinatorics of Patterns, Correlation, and Structure

RUI：模式、相关性和结构的极值组合

• 批准号: 1500856
• 负责人: Daniel Katz
• 金额: $ 15万
• 依托单位: The University Corporation, Northridge
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-15 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1500856&HistoricalAwards=false
• 关键词: RUI; Extremal; Combinatorics; Patterns; Correlation

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.

组合学考虑有限结构，其中许多结构在科学技术中出现的问题中起着至关重要的作用。这些结构中最突出的是有限二进制序列（0和1的字符串），用于通信网络、密码系统、遥感、声学设计和科学仪器的有效操作。由多项式、集合和图产生的其他有限结构也在各种各样的技术和科学努力中得到广泛的应用。为了实现一个工程目标或理解一个自然过程，人们必须经常找到与某个特征相关的极端（最小或最大）的结构。例如，为了避免多用户通信网络中的相互干扰，我们可能会寻找一组彼此尽可能不相似的二进制序列：这是低相关性的问题。这类极端问题的解决方案往往涉及具有大量结构的数学对象。本研究项目旨在探讨极值组合中的一些问题以及这些极值问题所涉及的数学结构。该项目的组织原则是研究涉及高度结构化离散对象的纯数学中的重要问题，其中许多问题在科学和技术中具有很大的兴趣。例如，最小化二值序列的非周期自相关问题在遥感和通信等工程应用中至关重要。后来，物理学家注意到，在统计物理学中，极小值描述了某些系统的基态。然而，这个问题也与利特尔伍德在1966年提出的谐波分析问题有关，目前仍在积极研究中，首席研究员最近的贡献正在进一步发展。诸如此类的问题与数学的其他分支有着丰富的联系，因为它们的最优或最知名的离散结构通常来自数论、代数或几何等领域。例如，已知的最小渐近非周期自相关序列，是由解析数论中的Fekete多项式推导出来的。本项目研究的Weil和起源于数论和算术代数几何：它们提供了一种计算有限域上曲线上点的方法。在技术上，它们决定了密码学中使用的函数的非线性，纠错码的权重分布，以及有限域上线性递归序列的互相关性质。在平面上的有限点集合中绑定模式实例的最大数量的新技术利用了从顺序关系到拓扑参数的各种技术。所有这些思想的相互作用，无论是纯粹的还是应用的，都导致了数学、工程和科学的相互丰富。

项目成果

Sequences with Low Correlation

• DOI: 10.1007/978-3-030-05153-2_8
• 发表时间: 2018-06
• 期刊: ArXiv
• 作者: D. Katz

Peak Sidelobe Level and Peak Crosscorrelation of Golay–Rudin–Shapiro Sequences

Golay-Rudin-Shapiro 序列的峰值旁瓣电平和峰值互相关

• DOI: 10.1109/tit.2021.3135564
• 发表时间: 2021
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Katz, Daniel J.;Van der Linden, Courtney M.
• 通讯作者: Van der Linden, Courtney M.

An improved uncertainty principle for functions with symmetry

对称函数的改进不确定性原理

• DOI: 10.1016/j.jalgebra.2021.07.017
• 发表时间: 2021
• 期刊: Journal of Algebra
• 影响因子: 0.9
• 作者: Garcia, Stephan Ramon;Karaali, Gizem;Katz, Daniel J.
• 通讯作者: Katz, Daniel J.

The Resolution of Niho’s Last Conjecture Concerning Sequences, Codes, and Boolean Functions

• DOI: 10.1109/tit.2021.3098342
• 发表时间: 2020-06
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: T. Helleseth;D. Katz;Chunlei Li

Sequence Pairs with Lowest Combined Autocorrelation and Crosscorrelation

具有最低组合自相关和互相关的序列对

• DOI: 10.1109/tit.2022.3187923
• 发表时间: 2022
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Katz, Daniel J.;Moore, Eli
• 通讯作者: Moore, Eli