标题： 多项式不等式的不可判定性在子集密度和加性能量中的应用 显示英文标题

标题： Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies

摘要： 许多极值图论的结果可以表述为图同态密度的某些多项式不等式。为了解答 Lovász、Szegedy 和 Razborov 提出的基本问题，Hatami 和 Norine 证明了确定任意此类图同态密度多项式不等式的有效性是不可判定的。我们观察到，许多加性组合学的结果也可以表述为子集密度及其变体的多项式不等式。基于 Hatami 和 Norine 引入的技术，结合代数和图构造以及傅里叶分析，我们同样证明了两个不可判定性定理，从而表明在加性组合学中建立此类多项式不等式在完全一般的情况下本质上是困难的。 显示英文摘要

摘要： Many results in extremal graph theory can be formulated as certain polynomial inequalities in graph homomorphism densities. Answering fundamental questions raised by Lov{\'a}sz, Szegedy and Razborov, Hatami and Norine proved that determining the validity of an arbitrary such polynomial inequality in graph homomorphism densities is undecidable. We observe that many results in additive combinatorics can also be formulated as polynomial inequalities in subset's density and its variants. Based on techniques introduced in Hatami and Norine, together with algebraic and graph construction and Fourier analysis, we prove similarly two theorems of undecidability, thus showing that establishing such polynomial inequalities in additive combinatorics are inherently difficult in their full generality.