Entropy methods in Additive Combinatorics and Analytic Number Theory

该项目属于EPSRC逻辑学与组合学和EPSRC数论研究领域。加性组合学和解析数论中许多问题的解决都需要将结构与随机性、规则行为与均匀行为分离开来。实际上，考虑在特定空间（区间、大密度集合、图）中估计（加权）特定模式（如素数、素数元组或等差数列）计数的一般问题。在伪随机情况下，当模式和空间大致独立时，联合计数可以估计为两个单独计数的乘积。另一种极端情况是，当空间相对于模式是高度结构化的时候，通常要么因为不同的原因很容易分析，要么很少分析。因此，策略是将一般情况分解为一个有结构的部分和一个随机的部分，或者分解为不能全部同时结构化的多个部分，然后分别处理这些部分。基于香农熵概念的信息论为形式化这些论点提供了一种方便的语言。香农最初将熵作为一种工具引入编码理论，给出了数据压缩的限制；从那时起，他的想法在密码学、统计推断和生物信息学等领域得到了应用。然而，最近，信息论的价值在纯数学中也得到了认可。例如，szemeracimdi定理是加性组合学的基础结果之一，它指出，上密度为正的整数的每个子集都包含任意长的等差数列；它有令人印象深刻的各种各样的证明，所有这些证明都依赖于前面提到的将给定集合分解为结构化和随机部分的方法。在图论方法中，用来完成这种分解的工具是szemersamedi的正则引理，它有一个基于Tao的熵增量论证的信息论类比；这个公式稍微简单一些，也更一般一些。同样，陶对著名的Erdös差异问题的解决方案采用了一种创新的熵递减论证。粗略地说，由于香农熵的变化可表示为（条件）互信息，它测量近似（条件）独立性，熵增和熵减算法可以找到两个随机变量表现出弱独立性的尺度（或最佳程度）。在陶的工作中，这导致了艾略特猜想的对数平均版本，这足以回答Erdös的问题。这个项目的主要目标是将熵方法的应用扩展到各种组合和算术问题。一个目标是利用Tao的正则引理的推广，获得szemersamedi定理的完全信息论证明。这个公式也可以简化用于证明Green-Tao定理（说明质数包含任意长的等比数列）的迁移原理机制，该定理目前使用szemersamedi定理作为黑盒。由于信息论的量可以作为高尔斯范数的替代品，因此将szemersamedi定理的傅立叶解析方法翻译成这种语言也是可取的。如果这样的方法对等差数列是成功的，人们希望将它扩展到合适的多项式数列的情况，首先通过采用Sarah Peluse的降次论证。另一个潜在的方向，源于Erdös差异问题的解决方案，涉及熵方法在纯算术问题上的应用，如Chowla猜想的变化，或与覆盖系统相关的问题。

This project falls within the EPSRC Logic and Combinatorics, and EPSRC Number Theory research areas.The solutions to many problems in additive combinatorics and analytic number theory require a separation between structure and randomness, between regular and uniform behaviors. Indeed, consider a general problem of estimating (weighted) counts of a certain pattern (such as primes, prime tuples or arithmetic progressions) in a certain space (an interval, a set with large density, a graph). In the pseudorandom case, when the pattern and the space are roughly independent, the joint count can be estimated as the product of two individual counts. The other extreme case, when the space is highly structured with respect to the pattern, is often either easy to analyze for different reasons, or rare. The strategy, therefore, is to decompose the general case into a structured and a random part, or into multiple parts which cannot all be structured simultaneously, and then to deal with these parts individually.Information theory, based on the notion of Shannon entropy, provides a convenient language for formalizing such arguments. Shannon originally introduced entropy as a tool in coding theory, giving limits for data compression; since then, his ideas found applications across cryptography, statistical inference and bioinformatics, among others. More recently, though, the value of information theory has also been recognized in pure mathematics.For instance, Szemerédi's theorem, one of the cornerstone results of additive combinatorics, states that every subset of the integers with positive upper density contains arbitrarily long arithmetic progressions; it has an impressive variety of proofs, all of which rely on the aforementioned decomposition of the given set into structured and random parts. In the graph-theoretic approach, the tool used to accomplish this decomposition is Szemerédi's regularity lemma, which has an information-theoretic analogue based on an entropy increment argument due to Tao; this formulation is both slightly simpler and more general.Similarly, Tao's solution to the famous Erdös discrepancy problem employed an innovative entropy decrement argument. Roughly speaking, since variations in Shannon entropy are expressible as (conditional) mutual information, which measures approximate (conditional) independence, entropy increment and decrement algorithms can find a scale at which (or the optimal extent to which) two random variables exhibit weak independence properties. In Tao's work, this led to a logarithmically averaged version of Elliott's conjecture, which was enough to answer Erdös's question.The main goal of this project is to extend the applications of entropy methods to various combinatorial and arithmetic problems.One objective is to obtain a fully information-theoretic proof of Szemerédi's theorem, using generalizations of Tao's regularity lemma. This formulation may also simplify the transference principle machinery used to prove the Green-Tao theorem (stating that the primes contain arbitrarily long arithmetic progressions), which currently uses Szemerédi's theorem as a black-box.Since information-theoretic quantities can function as substitutes for Gowers norms, it would also be desirable to translate the Fourier-analytic approach to Szemerédi's theorem into this language. If such an approach is successful for arithmetic progressions, one would hope to extend it to the case of suitable polynomial progressions, at first by adapting Sarah Peluse's degree-lowering argument.Another potential direction, stemming from the solution to the Erdös discrepancy problem, concerns applications of entropy methods to purely arithmetic questions such as variations of Chowla's conjecture, or related to covering systems.