块对称多项式的相关性优于对称多项式，解决开放问题和研究突破

≥ ∈·−≥块对称多项式与奇偶校验的相关性优于对称多项式弗雷德里克·格林（FredericGreen）DanielKreymer<$Emanuele Viola< $2016年11月23日摘要我们证明了n元d次块对称多项式模任意奇数p与奇偶校验指数相关性优于d次对称多项式，如果n cd2log d和d [0。995pt1，pt）对于某个t1和某个c> 0，只依赖于p。 对于这些无限多的度，我们的结果解决了一个开放的问题，提出了一些研究人员，包括Alon和Beigel在2001年[AB01]。已知的唯一既往病例为d= 2和p= 3 [Gre04]。这一结果是通过我们称之为对称相关谱分析的理论的发展而得到的，该理论起源于蔡、格林和蒂埃罗夫的著作[CGT96，Gre99]。特别地，我们的结果来自于对对称多项式的相关性的详细分析，当d=pt− 1时，该相关性被确定为指数小的相对误差。电子邮件：fgreen@clarku.edu†支持通过NSF授予CCF-0845003、CCF-1319206和REU增补。电子邮件地址：@ccs.neu.edu1{}|√−§Σζp| |≤√≥1介绍在复杂性下限的几十个简单到状态的长期挑战中，有一个挑战可以说是突出的。这是展示与（a.k.a.）具有小相关性的显式函数的挑战。平均而言，对于n个变量模p的低次多项式是非常困难的。正如[Vio 09，Vio 13]中所讨论的，它之所以突出有几个原因：(i) 在相关界限方面取得进展是在其他一些长期存在的问题上取得进展的先决条件。例如，一个鲜为人知的事实是，它是一个先决条件的最坏情况下的沟通下界的额头上的数字模型与多对数的球员。它也是电路复杂性取得基本进展的先决条件，例如，确定NP不具有准多项式大小的深度3多数电路。关于这些联系的更多信息，我们请读者参阅《说明书》[Vio13]。(ii) 已知所谓的(iii) 可以说，对这一挑战的了解比其他挑战更多。例如，考虑Mod q函数，其在输入（x1，x2，. . .，xn）0，1 n，如果qixi。 对于不同的素数p和q，它与n元模p的d次多项式的相关性有两个不同的界。首先，O（d/ n）[Raz 87，Smo 87，Smo 93];其次，exp（n/cd））[BNS 92，Bou 05，GRS 05]。读者可以在[Vio09]中找到这两个证明，其中也包含了Nisan出于上述几点，特别是由（iii），在这项工作中，我们认为与模q函数的相关性。为了具体起见，让我们定义“相关性”。在前面的工作之后，我们使用复和;为了完整起见，我们在附录A中回顾了这个和与其他相关性概念之间的密切关系，例如函数不一致的输入部分。定义1.1.n个变量x1，. . . ，xnmod- ulop和相同变量中的Mod q1γ=2nx∈<${0，1}nni=1Q（1）函数的表达式：其中，u= e2πi/u是本原复u的单位根。当我们说相关性最大化/更大/等等时， 我们参考它的标准|γ|.很自然地，人们会猜想，|γ|对于每一个固定互质，p和q，甚至对于度d=n<$（1）。唉，据我们所知|γ|≥ 1/n甚至对于d = log2n。事实上，关于上述第iii）点，[Raz 87，Smo 87]的技术不足以证明γ1/n，而[BNS 92，Bou05]的结果在d log 2 n时不产生有趣的边界.因此，研究哪些多项式具有（接近）最大相关性似乎是很自然的。 在这个方向上，一些研究人员提出了一个具体的问题，包括Alon和Beigel [AB01]十多年前：2§≥−≥||≥≤- ≥ −···≥± ± ±···±对称多项式有最大相关性吗？回想一下，如果一个多项式在变量的置换下是不变的，那么它就是上述问题的正解将产生戏剧性的后果，因为对于对称多项式，已知非常强的边界[CGT96]。但直到目前的工作，它只知道答案是否定的多项式的次数d= 2模p= 3与国防部q= 2功能（a.k.a. parity）[Gre04]。相比之下，在其他情况下，经验结果（在6中重现）表明，对于更高的次数d>2，对称实际上可以最大化相关性。1.1我们的结果我们证明，事实上，对称多项式模p的奇偶校验的相关性是指数比最大的无限多度d，和任何奇数p。 我们通过显示块对称多项式来实现这一点，这些多项式的变量被划分为块，并且在每个块内是对称的，但不是整体的，比相同程度的对称多项式实现指数更好的相关性定理1.2（块对称拍对称）。对于每一个奇数p 3，每一个n，和每一个满足pt> d 0的d。对于某个t1，设γb是n元模p的d次块对称多项式与奇偶函数之间的最大相关，|γs|对于对称多项式，最大值为。然后，其中c> 0仅取决于p。|γb||γs|1 .一、01[n/（cd2lgd）]、PD从它的证明中可以明显看出，该定理还表明，对于范围（1 <$（1））中的次数d，pt> d 0。995PT1，d次的块对称多项式比更大次（1 +0（1））d的对称多项式实现更高的相关性。另一方面，一致的是，次数为pd的对称比任何次数为d的多项式获得更高的相关性。我们注意到，上述定理适用于“小”度，如d = 8（对于p = 3），并适用于后者的度数可以大到n0。49、对于足够大的N。这种大度数的状态对于应用来说是最有趣的先前已知的唯一情况是d= 2和p= 3 [Gre04]，对应于t= 1。事实上，[Gre 04]表明{-1，1}上的最优多项式具有块对称形式x1x2x3x4 xn−1xn（如果n是偶数; n是奇数的情况有一个额外的1次项）。然而，这些多项式到更高次数的自然推广（例如，x1x2x3+ +xn−2xn−1xn）对任何d3都不我们发现有点令人惊讶的是，一个不同类型的块对称多项式击败对称，正如我们上面的定理所给出的。事实上，我们用更多的设置来补充上面的结果，只要块足够大，对称我们注意到，上述结果中的块确实足够大。首先，我们证明了当d是p的幂时也是如此，从而表明定理1.2中的不等式pt> d必须是严格的。≥3−联系我们≤D我 我i≤D定理1.3（对称拍数对d=pt是大块对称的）。固定任何奇素数p和次数d = pt。 有一个常数c，使得对于n ≥ c，任何具有n> block-size ≥ c的块对称多项式与奇偶性的相关性比对称性差。第二，我们考虑多项式模p= 2与Mod 3功能在这篇论文之前，没有任何证据表明不同的模数会产生不同的最优多项式。事实上，我们可以证明，对称击败块对称，同样有足够大的块。定理1.4（在计算Mod 3时，对称模2击败大块对称）。 对于任何固定次数d，具有足够大的块的块对称模2多项式与Mod 3函数的相关性比对称的差。事实上，在定理1.4的p= 2的设置中，我们提供了后来的计算证据，证明对称可能是最佳的。到目前为止所讨论的所有结果都涉及块对称多项式和对称多项式之间的关系。我们还介绍了一个新的家庭的多项式，我们称之为开关对称。 这些是形式为x1f（x2，. . . ，xn）+FJ（x2，. . . 其中f，FJ是n1个变量的对称多项式。我们得到各种设置的程度d和模p，使开关对称拍对称无穷多n。具体而言：定理1.5（开关对称拍对称）。 设（d，p） （4，3），（10，3），（6，5）。 对于所有足够大的，甚至n，存在一个d次开关对称多项式mod p在n个变量，与奇偶校验比d次对称多项式更好地相关。1.2技术：对称相关我们的主要结果是通过发展一种我们称之为对称相关谱分析的理论得到的，这种理论起源于蔡，格林和蒂埃罗夫的作品[CGT96，Gre99]。在描述它之前，我们提到一个有用的方法来命名对称多项式，与变量的数量n无关。众所周知，n元dd在n个变量。 (Ann个变量的d次初等对称多项式是以下项的和：所有次数恰好为d的多线性单项式）。 因此，我们常常发现，在该线性组合中具有d+1个系数选择的对称多项式。在这种情况下，当我们谈论n增长时的固定对称多项式时，我们实际上是指多项式的无限族。也就是说，对于任何给定的n值，实际的n元对称多项式是通过取n元初等对称多项式的固定线性组合自然获得的。上述理论允许我们将相关性γ改写为以下格式：γ=1<$αnβ，（2）其中D≤pd是p大于d的最小幂，αi是实数独立的从多项式和递减（即，α1> α2>。. . > αD> 0）; βi是依赖于对称多项式的复数，但仅依赖于n模O（D）。41Σ| || |−Σp11因此，对于任何对称多项式，存在值β1J，使得相关性由和式（2）中的首项αnβJ/D渐近控制中的所有结果1 1本文仅通过分析这个首项β1而得到。因为它的重要性，我们将β1称为β。在这个非正式讨论的其余部分，我们忽略低阶项（对应于i>1），我们认为对称多项式的相关性为αnβ/D。（三）注意与谱图理论的类比。正如后者在特征向量基础上重写转移矩阵并且通常通过界定最大（非平凡）特征值来进行，对称相关的谱分析以等式（2）的形式重写相关并且通过界定前导βi来进行。为了研究对称和块对称之间的关系，我们首先进行以下关键观察。 考虑将变量划分为n/b个块X1，X2，. . .，Xn/b个变量。在b个变量中选择一个对称多项式t，并构建块对称多项式tJ：=t（Xi）。i≤n/b注意，tJ的相关性在块之间相乘。因此，如果对称多项式t的相关性具有特定的β，则块对称多项式tJ的相关性变为：. αbβ/D n/b = αn（β/D）n/b。（四）比较等式（3）和（4），我们看到：块对称拍对称如果|β|/D > 1。为了得到块对称拍对称的主要定理1.2，我们证明（对于定理中的参数）一个多项式，|β|/D>1。事实上，我们应该接近2 3/π = 1。102. . . 证明这是最好的方法一路上，这些在以下情况下，边界确定相关性，直到相对误差1 +n，其中n= 2−n（n）d= pt1为T。我们证明存在一个多项式达到β /D >1有多个步骤。首先，我们在引理2.1中提供了一个细化的谱公式，该公式产生了方程（2）中β的以下关键D−1β=2（−1）k<$r（ k） cos（π（n−2k）/2D），（5）k=0其中r（k）是汉明权重k的输入上的多项式的值。我们的上述β表达式（5）优于[CGT96，Gre99]中的先前表达式的优点在于，我们5的表达式仅取决于第一D汉明权重处的对称多项式的值。正如我们在引理3.4中所展示的，这赋予了我们完全的自由，6| |−| || |§§§||| |.0if（−1）kcos（π（n − 2k）/2 D）≥ 0，§在d=pt−1=D− 1的情况下，选择r（k换句话说，对于每一组值r（k），0≤k≤D− 1，存在一个对称d次多项式来实现这些值。(The对于l>1，次数d=pt−l的情况被简化为l=1的情况）。一分钟的思考现在表明，为了最大限度地提高|β|我们应该选择r（k）以尽可能与（−1）k cos（π（n− 2 k）/2 D）的符号一致。具体而言：r（k）：=（p-1）/2 如果（−1）k cos（π（n− 2 k）/2 D）<0.事实上，我们证明了这个选择对于p= 3是最好的（定理7.1）。在这一点上，本文中的一个有点技术性的结果（定理3.1）表明，对于上述对r的选择和（5）可以重写为更简单的表达式，不涉及取消，因此更容易绑定。实际上，我们在引理3.3中将这个更简单的表达式绑定到β /D >1。 这结束了我们的主要定理1.2的证明的概述。我们的补充结果，定理1.3和1.4，通过类似的两步方法证明。也就是说，我们得到合适的谱公式，然后我们约束β，这次是从上面建立β /D1。(Here忽略对应于（2）中i>1的低阶项产生了块足够大的要求对于我们的开关对称多项式的结果，我们证明了最大的相关性，对于一个固定的偶数度d，减少也就是说，当n也是奇数时，它对n1和n个变量然后我们证明这与(5)对于d的选择值，使用计算机搜索。计算机搜索的作用本文的所有主要结果，包括定理1.2，1.3和1.4，都是在不使用任何计算机的情况下解析地得到的（a.k.a. 蛮力）搜索。然而，这项工作建立在作者的计算机搜索基础在这一段中，我们希望详细说明这一点，以提供一些观点。首先，作者使用计算机搜索验证了对称多项式模p对于n，d，p，q的各种小值具有与Modq函数的最大相关性，除了q= 2和d= 2的情况，参见。6.这促使作者进一步研究对称的情况。然后，作者使用计算机搜索来计算表达式（2）中β的几个最大值，参见。六、令他们惊讶的是，作者观察到在某些情况下β/D>1，并意识到这特别意味着块对称拍数是对称的;这篇论文就是从这里开始的。计算机搜索经常用于密码学和组合学，参见例如[BK 10，Rad09]。尽管有一些例外，见例如。Amano我们希望扭转这一趋势。我们相信，在基本的复杂性下限上，特别是在相关性界限上，显然缺乏进展Organization. 在图2中，我们得到了我们的谱公式，它细化了[CGT96，Gre99]，特别是提供了β的表达式。在[3]中得到了β的各种界，建立了我们的主要定理1.2.为了可读性，本节中的一些证明被推迟7§§Σp|| ≤r（k）≠t（x）（modp），当k=ni=1 Xi. 我们说t是通过 r对称的。到7. 4包含了我们关于对称拍块对称的补充结果，证明了定理1.3和1.4。最佳相关的逐步行为和开关对称多项式在§5中讨论，特别是证明定理1.5。为了完整起见，我们在第6节中报告了计算机搜索的结果，这也引发了本文的发展。第 8节讨论了一些悬而未决的问题。2一个谱公式在本节中，我们陈述并证明了我们的谱公式。首先，我们来定义一些符号。当t是对称多项式l时，它可表示为函数r：Z→Zp，其中用d来表示t的次数，结果是函数r是周期的，其周期取决于d，我们用D来表示;也就是说，对于任何k，r（k+D）=r（k）。当p是素数时，我们有D=pt，其中t是使得d pt的最小整数。引理2.1（相关性的谱表达式）。 设t是模p的d次多项式，它是通过r对称的. 设D是p大于d的最小幂。 那么t和奇偶校验在n个变量上的相关性是γ=1μ mαnβ，（6）其中对于每个l：Dll1≤l Dl奇数αl= cos（πl/2D），（7）D−1βl= 2（−1）k<$r（k）cos（πl（n − 2 k）/2 D）。（八）k=0为了简单起见，我们在本文中使用符号β来表示β1因为对于l=1和βl2D，可以清楚地得到max lαl1nDn|≤ D α 1 2 2 D = Dα 1。| ≤ Dα1 2 2 D = Dα1.（九）引理2.1的证明使用[Gre99]中的以下引理。为了完整性，我们注意到后者是通过首先重写相关性来证明的（参见。定义1.1）作为γ=1μm.nj2njq pj=0通过重新表达j k（mod qD）。 通过二项式定理，用单位根表示，n8Jn得到了γ的另一种有用形式。9−（1+2个DΣpΣ4DΣ4Dl =1，3，5... D−24D4D4D4D4DΣΣ引理2.2（[Gre99]中的引理2.6）。 设t是模p的多项式，通过r，且r具有周期D。然后哪里1 1γ=2nqDqD−1l n（ l）QDl=零qD−1σ（l）=Σζkζr (k)ζkl.（十一）q p qDk=0此外，若l+D/φ 0 mod q，则σ（l）= 0。引理2.1的证明 我们使用引理2.2中γ的表达式，设q = 2，对应于宇称。因为D是奇数，从引理2.2我们知道，在γ的和中，我们可以忽略l的偶数值。我们也可以忽略l=D的值，因为（1+n-D）= 0。将每一项与0 1。102.(2) 对于p=D= 3，我们有|β٨|对于n奇数，= 3，并且|β٨|= 2个(3) 最后，对于任何p ≥ 3和D ≥ 5，我们有|β٨|/D> 1。04的时候。这个引理的证明在§7中。3如果n是偶数下面的引理表明，d次对称多项式可以被设计为在汉明权重为0，. . .，d.这也是从Bhatnagar、Gopalan和Lipton [BGL 06，推论2.7]的一个更一般的结果得出的。这种情况的下面的证明是更基本的，因为它避免了卢卡斯引理3.4. 对任意整数d ≥ 0和n ≥ d，以及任意整数a0，a1，. . . ，ad，存在n元d次对称多项式fd，且系数为整数，使得对于任意汉明权的输入x∈{0，1}n|X|≤d，fd（x）=a|X|.P roof. 通过归纳总结。Letf0：=a0.Giv enfd−1，定义fd（x）：=fd−1（x）+（ad−注意fd是对称的，并且有d次。关于汉明重量的输入x∈ {0， 1}n< d，ea ch单项式xi1···xid将是e0，因此fd（x）=fd−1（x）=a|X|. Fin all y，ony输入x的汉明重量d恰好有一个单项式xi1· · ·xid将为1，因此fd（x）= fd−1（x）+ad− fd−1（wd）= ad。β=（−1）罪.（十二）12ppΣ.Σ.p≥−≥||≥11≥.≥ppp11.pp2个Dββ 下一个引理总结了β逼近的对称多项式的存在性引理3.5. 对每一个n，奇数p和D是p的幂，且对每一个l ≥ 0，存在n个变量的对称p多项式deg reed=D−1−l，其中|β|≥|β٨|−2|（p−1）/2−1|l≥|-4升| − 4 l.注意，l=0的情况是特别有趣的;在这种情况下，我们实际上得到β=β。应该可以稍微优化常数4。证据 设r：ZD→ Zp是定理3.1所保证的函数，从而定义了βp。从引理3.4得到一个D − 1 − l次对称多项式f，它在输入x上的汉明重量|X| d 0的d。对于某个t1，设γb是n元模p的d次块对称多项式与奇偶函数之间的最大相关，|γs|对于对称多项式，最大值为。然后，其中c> 0仅取决于p。|γb||γs|1 .一、01[n/（cd2lgd）]、PD证据首先回想一下引理2.1，d次对称多项式的相关性在绝对值上≤Dαn≤pdαn，参见。等式（9）。证明的其余部分构造了一个d次块对称多项式，相关系数为αn（1+n）[n ≠/d2lgd≠，由≥k：rJ（ k）/=r（ k）.a/=bK13此定理m如下. 该结构首先表现出一个对称多项式，其相关系数为αb（1 +1），对于任意大的b，然后通过将N个变量划分为大小为B的块来增强相关性。14- − −≥−| || |.Σ≥α|β|/D−D（α/α），3111≥≥|− ≥ ≥|−≥≥[2014 -05- 23]1≤≥2l =3，5，.，D−2LL111结束证明。将上面的引理3.5与引理3.3中的最后一个界结合起来，我们得到存在b个变量的对称多项式，假设β/D> 1。02只要次数d满足d=D1 l为1。044 l/D > 1。02. 这是由d 0的情况。小行星995 D 1. 这是所需的多项式。（在p = 3和d = 2的情况下，这也是在[Gre04]中，我们需要取b为奇数，这对于证明是足够的。这个证明的其余部分表明，当b足够大时，β /D不超过1。01.具体地，从等式（6）回忆，该多项式与b个变量上的奇偶校验的相关性为：≥αb。|/ D − 1 max|β |（α / α）b|(α/α)bΣB b1使用该|βl|对于任何多项式和l，α l ≤ 2 D，从公式（8）中可以看出，对于l = 3，5，. . .，D-2在l = 3时有其最大值，这从等式（7）中再次显而易见。现在，使用三角公式cos 3θ = 4 cos3θ− 3 cosθ和小角近似cos2θ≤ 1−θ2/ 3，我们将α3/α1限制为：α3/α1= 4 cos 2（π/2 D）− 3 ≤ 1 − π2/D2。因此，回想一下Dpd，对于任何 bcd2lg d，对于一个足够大的仅取决于p的常数c，我们有β/DD（α3/α1）b1。01，因此相关性为1。01αb.为了获得所需的块对称多项式，将n个变量分成n/（cd2lgd）个块，每个块都有cd2lgd个变量在每个块中应用刚刚用相关性1构造的对称多项式。01αb.相关性在块之间相乘，如从等式（1）显而易见的。因此，我们得到相关性≥。1 .一、01αb[n/（c d2lgd）=1. 01[n/（cd2lgd）n，4当对称性优于大块对称性时在本节中，我们提出了两种设置，其中对称多项式击败了大块的块对称。4.1度d=D/p我们发现，对于奇素数p，如果次数是D/p，对称多项式击败块对称。以下是证明所需的主要技术引理引理4.1. 设p是奇素数，r（k）表示次数为d=pt−1，t> 1的对称多项式。设D=pt表示r（k）的周期。然后|β| 0。15Σp.ΣpΣpΣp（−1）pD/P。 根据卢卡斯KD/p l（modp）forΣΣ证据记得β= 2D−1k=0（−1）kr（k）cos2 k −nπ。2个D当d = D/p，wlog时，我们可以写r（k）= c。k+ rJ（k），对于某个常数ci = 0，D/p其中r j的多项式次数至多为D/p− 1，而he。nce=RJ（k）的周期lD/p≤k<（l + 1）D/p。因此，通过上述r（k）的形式，我们发现r（k）= RJ（k）+cl，其中0 ≤l≤p−1且lD/p≤k<（l + 1）D/p。因此，我们认为，β= 2p−1l=零（l+1）D/p−1中国共产党k= lD/p（−1）k<$rJ（k）cos2 k −nπ。2个D通过改变内和中的变量k<$→k+lD/p，并利用（-1）lD/p=（-1）l（sinceD/p是奇数）和drJ（k+lD/p）=rJ（k）的事实，我们发现（l+1）D/p−1k= lD/p（−1）k<$rJ（k）cos2k−nπ2个D=（−1）lD/p−1k=0（−1）k<$rJ（k）cos2k−n2个D π+ lπ/pπ。我们可以把这个等式代入上面的β的表达式 这允许我们交换l上的和和k上的和，β= 2D/p−1k rJ（ k） p哪里k=0p−1sk=<$（−1）l<$clcos（θ+lπ/p），l=零θ = 2 k−nπ。2个D我们现在计算sk。 第一，重写p−1s=1<$（−1）l<$cl（eiθ+liπ/p+e−iθ−liπ/p）k2pl=零p−1p−1=1eiθ（−1）lc ll+1e−iθ（−1）lc l−l。Σζ...Σ162个pp2个pp2个ppppNow（−1）l=pl，所以2l=零p2p2l=零p2个p（−1）lcll =c l（p+1）l=c ll（p+1）/2=（c+（p+1）/2）l.17Σζ好吧（十四）−−−| |||/∈{−}Σ| || |≤·| |11| || ||∈ |∈≥1≡ −{−}p4D类似地，观察到t（−1）l<$l<$ −l=<$（c+（p−1）/2）l。Toevaluees因此，我们面临着两个总和，p2 ppp−1Kp−1（c+（ p+1）/2）lpl=零和（c+（ p1）/2）l pl=零对于任何c（p1）/2，（p+ 1）/2，（14）中的两个和都是0，这产生β= 0，特别是所需的β D(This包括c= 0，这意味着当r的周期为D/p1时β如果c =（p1）/2，第一个和是p，第二个是0。 如果c=（p+ 1）/2，则第一个和为0，第二个是p。因此，不失一般性地假设c=（p1）/2。那么既然peiθ=pei2k−nπ=p<$2k−n，由此得出，2个D2 2 24Dβ=pD/p−1（−1）k<$rJ（k）<$2k−n。（十五）k=0和中的每一项都是单位范数的，所以βp D/p = D。我们现在证明这个不等式是严格的，即， β p。p2p2D2D D为了证明存在β > 0的多项式的根据引理3.4，我们可以随意设置RJ（k）的值。显然，可以设置它们，|β|> 0，因为给定任何导致|β| = 0我们可以改变一个值来获得|β|> 0。定理1.3（对称拍数对d=pt是大块对称的）。固定任何奇素数p和次数d = pt。 有一个常数c，使得对于n ≥ c，任何具有n> block-size ≥ c的块对称多项式与奇偶性的相关性比对称性差。证据 设D = pt +1。 根据引理4.1，在任何大小为b的块中，c、最大相关性是αb（β/D）（1 +<$），对于某些β /D（0， 1）和某些实数<$，随着c的增加，绝对值接近0。如果有m个块，则块对称多项式的相关性≤ αn（|β|/D）m（1+m. 这是<（|β|/D）αn（1 + n），其中m> 1且c足够大。4.2其他模数下一个定理表明，γ表达式中的主要项（见等式2）。(10))只有配对（就像他们在方程的推导中所做的那样）。(6))当q = 2c时，0，. . .，q1 等了cD模q 特别是，q= 2是唯一的素数，他们配对。然后我们注意到，在q= 3和p= 2的情况下，当项不18配对时，19≥<$−cos（πl/（qD））<$σ，≥/||（+−2qD<$−cos（πl/（qD））<$σ。||||−∈{−}−∈{−}/−.−D前导项的系数β较小，即，|一日一次|< qD.这意味着具有足够大的块的块对称多项式与Mod3函数的相关性指数地比对称差。定理4.2（当事物不成对时）。设t是一个d2模p = 2的多项式，它是通过r对称的. 设D是p大于d的最小幂。 则t与Modq函数（q= 3）之间的相关性为：qD−11γ=QD其中σ的定义如引理2.2所示。nln（l）2qDl=零此外，re恰好是l的一个值lJ，使得σ（l）=0并且cos（πl/（qD））n最大化。此外，该值满足0<最大值|σ（lJ）|一<日一次注意，限制d2是必要的，因为对于d= 1，对称多项式和块对称多项式之间没有有用的区别证据从引理2.2开始，使用与前面类似的操作，我们发现，qD−11 1γ=2nqDL2qDl=零L2qD）n−lnσ（l）qD−1n ln（ l）qD2qDl=零现在回想一下同样的引理，σ（ l ）= 0 l Dmodulo q。后者是值l= c + sq，其中c1，. . .，q 1满足c D模q，且s 0，1，. . .，D1.通过检查，对于s= 0或s=D 1，相应的值cos（π 1/（qD））被最大化。我们现在讨论这些cos（πl/（qD））的值是不同的（事实上，都是不同的）。实际上，当πc=ππcqD qD+π（D − 1）引力2 c = q。因此，渐近地，当q是奇数时，恰好有一个σ（l）系数起作用。在p = 2，q= 3的情况下，重要的是由l= 1（对于D = 2，8，32，. . . ）或l = qD − 1（对于D = 4，16，64，. . . ）. 在这个证明中，我们只使用l的这些值是奇数。把所有的奇数都修好。 我们继续进行绑定|σ（l）|从上到下不1=