初等对称多项式的算术复杂性：多线性公式与齐次公式对比

本篇文章探讨了初等对称多项式的算术复杂性与多线性齐次公式的关系，以及它们与一般齐次公式和乘积深度的联系。作者Pavel Hrubes和Amir Yehudayof的研究焦点集中在初等对称多项式Sk上，这些多项式在数学和计算理论中有重要应用。 他们首先回顾了一个基本的算术复杂性结构结果，指出一个k次齐次多项式如果有非齐次公式的大小为s，其齐次公式的大小上限不超过sO（logk）。然而，对于初等对称多项式Sk，以往的研究表明其非齐次公式大小为O(n^2)，而齐次公式要求的最小大小是n<k(logk)。这与之前上界相一致，但论文进一步揭示了Sk在齐次多线性公式中的特殊性质。 论文的核心贡献在于证明了计算Sk的多线性齐次公式需要的大小至少为2^(k^(1/d))n，其中d是乘积深度。这揭示了一种超多项式分离现象，即多线性公式和一般的齐次公式之间存在明显的复杂性差距。尽管这并不完全符合一般齐次公式大小的上界，但它表明了在多线性模型中，初等对称多项式的复杂性与常规估计有所不同。 值得注意的是，对于固定k值，Sk的齐次公式大小被证明为kO(logk)n，这与单调公式（大小为n^(1+o(1)))的情况形成对比，即使对于单调公式，当k保持不变时，这个猜想也不再成立。这表明在多线性背景下，对称多项式的复杂性特性有着独特的表现。 这篇论文不仅深化了我们对初等对称多项式算术复杂性的理解，还展示了在特定计算模型——多线性公式中，它们的复杂性界限与一般情况存在显著差异。这对于进一步探索算术复杂性理论和对称多项式的计算能力具有重要意义，同时也提出了有待解决的挑战，如齐次公式复杂度的超多项式下限问题。