Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory
Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory
复制标题
大域中多项式的偏差与结构，以及在有效代数几何和编码理论中的应用
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Shachar Lovett
中科院分区：
文献类型：
--
作者：
Abhishek Bhowmick;Shachar Lovett
令$f$ 为有限域$mathbb{F}$ 上$n$ 个变量的$d$ 次多项式。如果 mathbb{F}^n$ 中均匀输入 $x 的 $f(x)$ 分布接近于 $mathbb{F}$ 上的均匀分布，则该多项式被称为无偏，否则称为有偏。如果多项式可以表示为几个较低阶多项式的组合，则称该多项式具有低秩。格林和涛 [贡献。 Discrete Math 2009] 以及 Kaufman 和 Lovett [FOCS 2008] 表明，偏差意味着固定素数域上固定次数多项式的低秩。这是高阶傅立叶分析中许多工具的核心。在这项工作中，我们将此结果扩展到所有素数域（大小可能随 $n$ 增长）。我们还提供了对大特征情况下的非素数域的概括。然而，为了简化演示，我们在主场设置中陈述了所有应用。
作为直接应用，我们获得了有效代数几何中一系列问题的改进界限，包括 Hilbert nullstellensatz、根式隶属度和低次簇中的有理点计数。
使用上述对大域的推广作为起点，我们还能够确定生长域上固定度 Reed-Muller 码的列表解码半径。 Bhowmick 和 Lovett [STOC 2015] 解决了固定大小字段的情况，解决了 Gopalan-Klivans-Zuckerman [STOC 2008] 的猜想。在这里，我们表明列表解码半径等于所有固定度数的代码的最小距离，即使字段大小可能随着 $n$ 增长也是如此。
Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x in mathbb{F}^n$ is close to the uniform distribution over $mathbb{F}$, and is called biased otherwise. The polynomial is said to have low rank if it can be expressed as a composition of a few lower degree polynomials. Green and Tao [Contrib. Discrete Math 2009] and Kaufman and Lovett [FOCS 2008] showed that bias implies low rank for fixed degree polynomials over fixed prime fields. This lies at the heart of many tools in higher order Fourier analysis. In this work, we extend this result to all prime fields (of size possibly growing with $n$). We also provide a generalization to nonprime fields in the large characteristic case. However, we state all our applications in the prime field setting for the sake of simplicity of presentation.
As an immediate application, we obtain improved bounds for a suite of problems in effective algebraic geometry, including Hilbert nullstellensatz, radical membership and counting rational points in low degree varieties.
Using the above generalization to large fields as a starting point, we are also able to settle the list decoding radius of fixed degree Reed-Muller codes over growing fields. The case of fixed size fields was solved by Bhowmick and Lovett [STOC 2015], which resolved a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008]. Here, we show that the list decoding radius is equal the minimum distance of the code for all fixed degrees, even when the field size is possibly growing with $n$.