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.

Combinatorics认为有限结构，其中许多结构在科学和技术中出现的问题中起着至关重要的作用。 在这些结构中，著名的是在通信网络，加密系统，遥感，声学设计以及科学仪器的有效操作中使用的有限二进制序列（零和一个字符串）。 由多项式，集合和图形产生的其他有限结构也可以在各种技术和科学努力中使用。 为了实现工程目标或理解自然过程，人们通常必须找到相对于某个特征的极端结构（最小或最大）。 例如，我们可能会寻求一个二进制序列的家庭，它们尽可能少地相似，以避免在多用户通信网络中相互干扰：这是相关性低的问题。 这种极端问题的解决方案通常涉及大量结构的数学对象。该研究项目旨在调查极端组合学和这些极端问题所涉及的数学结构中的一些问题。该项目的组织原理是研究涉及高度结构化离散对象的纯数学问题中的重要问题，其中许多对科学和科学技术具有极大的兴趣。 例如，在遥感和通信等工程应用中，将二进制序列的多态自相关最小化的问题至关重要。 后来，物理学家指出，最小值描述了统计物理学中某些系统的基态。 然而，这个问题也与利特伍德（Littlewood）在1966年提出的谐波分析中的问题有关，并仍在积极研究，主要研究人员的最新贡献正在进一步发展。 诸如此类的问题与数学的其他分支具有丰富的联系，因为它们的最佳或最著名的离散结构通常来自数字理论，代数或几何形状等领域。 例如，具有最低已知渐近性大道自相关的序列源自分析数理论中的fekete多项式。 该项目中研究的WEIL总和源于数字理论和算术代数几何：它们提供了一种在有限场上曲线上计数点的方法。 在技​​术中，他们确定了密码学中使用的函数的非线性，误差校正代码的重量分布以及有限场上线性递归序列的互相关属性。 在飞机中，在有限的一组点中绑定模式最大实例数的新技术利用了从订单关系到拓扑参数的各种技术。 所有这些思想的相互作用，纯粹和应用，都导致数学，工程和科学的相互充实。

项目成果

Sequences with Low Correlation

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

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.

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.

Rudin-Shapiro-Like Sequences With Maximum Asymptotic Merit Factor

具有最大渐进优值因子的类 Rudin-Shapiro 序列

• DOI: 10.1109/tit.2020.3011853
• 发表时间: 2020
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Katz, Daniel J.;Lee, Sangman;Trunov, Stanislav A.
• 通讯作者: Trunov, Stanislav A.

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