平方根次数界的无界违反
Unbounded Violations of the Square-Root Degree Bound
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究布尔函数线性Fourier系数之和与多项式次数的关系。作者声称否定Gopalan–Servedio平方根猜想，且可差任意常数倍：对每个实数C>0，存在非恒定布尔函数f:{-1,1}^n→{-1,1}，使Σ_i f̂({i})>C√(deg(f))。摘要给出构造性否定声称，未涉及独立复核。
- 对任意C>0构造非恒定布尔函数使线性Fourier系数和超过C√(deg f)。
- 作者声称否定Gopalan–Servedio平方根猜想，且差任意常数倍。
- 结论针对有限符号立方体上的布尔函数。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We disprove the Gopalan–Servedio square-root conjecture, even up to an arbitrary constant factor. For every real C > 0, there is a nonconstant Boolean function $`f:\{-1,1\}^n\to\{-1,1\}`$ on a finite sign cube such that $`\displaystyle \sum_{i=1}^n \widehat f(\{i\})\gt C\sqrt{\deg(f)}.`$ Here $`\widehat f(\{i\})`$ is the linear Fourier coefficient associated with the ith input, and $`\deg(f)`$ is the degree of the real multilinear polynomial representing f.
用户标记：未标记
固定编号：283e75d68f09a686
原文来源