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年仍在积极研究，最近的贡献，主要研究人员正在进一步发展。 这类问题与数学的其他分支有着丰富的联系，因为它们的最佳或最知名的离散结构通常来自数论、代数或几何等领域。 例如，具有最低已知渐进非周期自相关的序列源自解析数论中的费克特多项式。 在这个项目中研究的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