容斥筛法公式的进一步研究及其应用

The sieving formula, also known as the inclusion-exclusion principle, and its far reaching generalization---the theory of posets, plays an important role in number theory, combinatorics, algebraic topology and probability theory. However, the main drawback of this formula is the large error caused by its exponential number of terms. The traditional methods use truncation and then to get Bonferroni type inequalities. A typical example, Brun sieve, was used to prove many beautiful theorems in number theory...The previous joint work of the PI and Wan shows this formula has a great deal of cancellations in counting problems involving distinct coordinates. They discovered and proved a greatly improved formula which reduces the super-exponential number of terms to sub-exponential number of terms. This led to substantial improvements (first by the PI and Wan, and and then later by several other researchers) in several important applications in coding theory, graph theory and computational complexities...From the topological point of view, if the abstract simplicial complex has better structure, one expects better improvement. In particular, we expect essential improvements of this sieving formula in many areas, such as number theory (for example, the Waring type problems over finite rings), combinatorics (For example, Stanley's problem and Borwein conjecture), coding theory (deep holes and decoding problems of generalized Reed-Solomon codes), theoretical computer science (algorithms and complexity of the subset sum problems over finite fields), and so on. ..This project aims to study the sieving formula from the perspective of combinatorial algebraic topology. Based on our previous work, we expect to find new inequalities and use them to solve some existing hard problems. Furthermore, using deep tools in number theory and arithmetic geometry (such as the Weil-Deligne estimates), we propose to establish estimates of certain algebraically structured partial character sums and certain partial Chebatarev density type theorems. Combined with our new sieving formula, this would lead to major new results in several important applications in coding theory, cryptography, combinatorics, theoretical computer science and other fields.

筛法公式（也称容斥原理）及其推广偏序集理论，是一个广泛应用于数学各领域的基本方法。其应用的主要困难是指数项求和产生的巨大误差。传统上多采取适当截断得到不等式估计，解析数论中的 Brun 筛法即是经典范例。申请人与万大庆教授合作的关于相异坐标向量计数的工作显示了项数可以从超指数减为亚指数，并得到了一序列重要应用。..从拓扑角度看，若其对应的抽象单纯复形有好的结构，则可期待有好的改进。尤其可应用于数论（例如有限环上子集华林问题）、组合(如 Stanley 计数问题与 Borwein 猜想), 编码（广义 RS 码的深洞和译码）、理论计算机（有限域上子集和问题的计算复杂性）等领域。..本项目计划在已有工作基础上从代数拓扑的观点研究筛法公式，期望发现新的不等式，结合应用数论和算术几何方法（例如 Weil 估计）建立部分指数和估计及部分 Chebatarev 型密度定理，用以解决一些现有的困难问题。

筛法公式（也称容斥原理）及其进一步的理论是一个广泛应用于数学各领域的基本方法。筛法公式应用的主要缺点是过多项数产生的巨大误差。传统上多采取适当截断得到不等式估计，解析数论中的Brun筛法即是经典范例。项目主持人与万大庆教授合作的关于相异坐标向量计数的工作显示了此公式相数可以从超指数约减为亚指数，并导致了若干新的重要应用。 . 本项目是这一工作的持续和发展。理论方面：.1. 项目主持人与万大庆教授继续合作，计数了有限交换群中任意子集的子集和计数公式；.2. 项目主持人与余翔博士合作，将李-万公式从子集的情形自然推广到了多重集合的情形，所得的新公式同样简洁优美，统一了此前的几个组合公式，同时也具有潜在的应用价值。. 应用方面，我们在Reed-Solomon码的距离分布问题、Borwein 猜想、有限域上的背包问题等相关领域中取得进展。