论文标题
在有限函数中搜索规律性
Searching for Regularity in Bounded Functions
论文作者
论文摘要
给定$ \ mathbb {f} _2^n $上的功能$ f $，我们研究以下问题。什么是最大的Aggine子空间$ \ MATHCAL {U} $，因此，当限制到$ \ Mathcal {u} $时，所有的非平淡傅立叶系数的$ f $都很小？ 对于自然等级的有限级傅里叶度$ d $函数$ f：\ mathbb {f} _2^n \ to [-1,1] $，我们表明存在一个尺寸的仿射子空间，至少$ \tildeΩ（n^{1/d/d！}！ 2^{ - k} $。为了补充这个结果，我们显示了$ d $函数的存在，其系数大于$ 2^{ - d \ log n} $，当限制到大于$ω（dn^{1/（d-1）}）$的任何副本子空间时。此外，我们给出了具有类似但较弱属性的功能的明确示例。 在此过程中，我们提供了限制在$ \ mathbb {f} _2^n $子空间的傅立叶系数的多个特征，这些函数的傅立叶系数可能在其他情况下很有用。最后，我们重点介绍了结果与奇偶校验杀死数量和仿射分散器的连接。
Given a function $f$ on $\mathbb{F}_2^n$, we study the following problem. What is the largest affine subspace $\mathcal{U}$ such that when restricted to $\mathcal{U}$, all the non-trivial Fourier coefficients of $f$ are very small? For the natural class of bounded Fourier degree $d$ functions $f:\mathbb{F}_2^n \to [-1,1]$, we show that there exists an affine subspace of dimension at least $ \tildeΩ(n^{1/d!}k^{-2})$, wherein all of $f$'s nontrivial Fourier coefficients become smaller than $ 2^{-k}$. To complement this result, we show the existence of degree $d$ functions with coefficients larger than $2^{-d\log n}$ when restricted to any affine subspace of dimension larger than $Ω(dn^{1/(d-1)})$. In addition, we give explicit examples of functions with analogous but weaker properties. Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of $\mathbb{F}_2^n$ that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers.
