Combinatorial design theory and digital communications

组合设计理论和数字通信

• 批准号: RGPIN-2022-03110
• 负责人: Jedwab, Jonathan
• 金额: $ 3.5万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758527
• 关键词: Combinatorial; design; theory; digital; communications

Modern society would be unrecognisable without digital communications technologies such as satellite communication, cell phones, portable music players, flash drives, GPS (global positioning system) navigation, and movies on demand. A key reason these technologies have become ubiquitous and highly dependable is the critical support provided by mathematical structures and algorithms that remain invisible to the user. The mathematics underlying these technologies arises from a combination of physical requirements, for example the desire to: send information from one device to another using energy efficiently; pass information securely between two parties even though outsiders can monitor the exchange; or recover transmitted information correctly despite corruption of the original signal. These combinations of physical requirements correspond to mathematical problems of arranging objects subject to multiple constraints; such problems are solved by combinatorial designs. The long-term vision of this research program is to combine combinatorial, algebraic, analytical, and computational techniques to revolutionise the study of classical and emerging problems involving combinatorial designs, by identifying the simplest possible structure explaining them. The short-term objectives of this research program are to solve three notoriously challenging problems of combinatorial design theory: 1. The existence pattern for Hadamard matrices 2. The existence of transversals and near-transversals in Latin squares 3. The existence pattern for difference sets in groups of order 4d. Seeking a complete solution to these problems is highly ambitious: each has perplexed researchers for sixty years or more. These problems are important practically, as well as theoretically. Problem 3 arises in signal design, where one wishes to determine when two signals are synchronised or when two images are optically aligned. Problems 1 and 2 arise, for example, in experimental design, where one wishes to test the statistical association between two quantities such as the frequency of cell phone use and the development of cancer, after accounting for other possible influences including lifestyle and genetic predisposition. The originality of this research program lies in the careful choice of which techniques to develop and which to discard as being unlikely to lead to a resolution. The anticipated outcomes are new insights into the mathematical structures underlying these problems, and greatly simplified ways of viewing them. Solving any of these problems would be a tremendous theoretical advance of great importance to mathematicians and computer scientists, and would stimulate interest in resolving other longstanding open problems using similar methods. Additionally, the wider Canadian and international scientific communities would take significant interest in the resulting deeper understanding of the possibilities and limitations of future digital communications technologies.

如果没有数字通信技术，如卫星通信、手机、便携式音乐播放器、闪存驱动器、GPS（全球定位系统）导航和点播电影，现代社会将变得面目全非。这些技术变得无处不在和高度可靠的一个关键原因是由用户不可见的数学结构和算法提供的关键支持。这些技术背后的数学基础来自于物理需求的组合，例如：有效地利用能源将信息从一个设备发送到另一个设备；在双方之间安全地传递信息，即使外部人员可以监视交换；或者在原始信号损坏的情况下正确恢复传输的信息。这些物理要求的组合对应于安排受多种约束的对象的数学问题；这类问题可以用组合设计来解决。本研究计划的长期愿景是结合组合、代数、分析和计算技术，通过确定最简单的可能结构来解释组合设计，从而彻底改变涉及组合设计的经典和新兴问题的研究。本研究计划的短期目标是解决组合设计理论中三个众所周知的具有挑战性的问题：1。Hadamard矩阵的存在模式2。拉丁方格中截线和近截线的存在性4d阶群中差分集的存在模式。寻求这些问题的完整解决方案是非常雄心勃勃的：每一个问题都困扰了研究人员60多年。这些问题在实践上和理论上都很重要。问题3出现在信号设计中，人们希望确定两个信号何时同步或两个图像何时光学对齐。例如，在实验设计中出现了问题1和问题2，在考虑了生活方式和遗传易感性等其他可能的影响后，人们希望测试两个数量（如手机使用频率和癌症发展）之间的统计关联。这项研究计划的独创性在于仔细选择发展哪些技术，放弃哪些技术，因为它们不太可能导致解决问题。预期的结果是对这些问题背后的数学结构的新见解，以及对它们的观察方式的极大简化。对数学家和计算机科学家来说，解决这些问题中的任何一个都将是一个巨大的理论进步，具有重要意义，并将激发人们用类似的方法解决其他长期存在的开放性问题的兴趣。此外，更广泛的加拿大和国际科学界将对由此产生的对未来数字通信技术的可能性和局限性的更深入了解产生极大的兴趣。