Entropy methods in Additive Combinatorics and Analytic Number Theory

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

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.