大子集S<$Fn: 多种规避设置与有界度的仿射簇有小交集

1多种规避设置ZeevDvirJanosKollar<$ShacharLovett摘要我们给出了一个大子集S<$Fn的显式构造，其中F是一个有限域，它与任何固定维数和有界度的仿射簇有小的交集。我们的构造推广了Dvir和Lovett（STOC2012）的最近结果，他们考虑了一次（即仿射子空间）的簇。1介绍在这项工作中，我们考虑的子集Fn，其中F是一个有限域。我们将有兴趣在construction-structing大子集的Fn有小的交集与任何k维仿射品种的fbounded'Com plexity'。 我们对复杂性的评估将取决于价值的确定性。我们称这样的集合为变种回避集。我们可以用概率方法证明，一个大的随机集与任何k维有界度簇（概率界见第7节）的交集都很小（这里的小是指与域的大小无关）。 我们给出了这样一个集的明确的结构，并提供了与可变的SS 通过对该集合进行快速更新，使得该集合是一种高效的算法，其在给定索引的情况下以一对一的方式输出集合中的元素。我们的工作建立在作者[DL12]的一个子集的早期工作的基础上，在该工作中，给出了各种一次仿射子空间的构造在[DL 12]中所做工作的原始动机是对Guruswami-Rudra码[GR 08，Gur 11]的列表解码算法的改进。我们不知道任何应用程序的品种规避集，但希望这些将确实证明在未来的有用。我们的出发点是[DL12]的主要定理的一个新的、更直接的证明新的证明技术使我们能够将结果推广到更高程度的品种。新的证明使用了一个关于Laurent级数解的引理（引理3.1），该引理在早期处理具有伪随机性质的图的显式构造的作品中被隐式地使用[KRS 96]。在我们的建设的主要成分是一个定理（定理2.1），给出了一个明确的一组k多项式f1，。. .，fk∈F[x1，. . .，xn]这样，他们定义的各种（在普林斯顿大学计算机科学系和数学系，新泽西州普林斯顿电邮地址：zeev. dvir@gmail. com。 Rearchpa†Mat hementm enfMathemat i m a ti m enM a t i m a t i m a t i m atimenNJ. 嗯，我知道了。我是一个很好的朋友。edu。美国新泽西州宾夕法尼亚州Advancdd Email：slovett@math. 我也是。edu。 Research由NSF资助DMS-0835373支持。arXiv：1203.4532v1 [cs.CC] 2012年3月21k1kJJF的代数闭包与任意k维至多d次簇有零维交。这些k个多项式的次数取决于次数参数d和变量的数量n。 有限域的结果表明，这些多项式在有限域F上有一个大的（并且容易描述的）公共解集。组织：在第2节中，我们工作的代数封闭的F和展示如何构建多项式f1，。. .，f，k。第3节包含证明的主要引理有关洛朗级数的解决方案以及另一个有用的引理投影的品种。第2节的两个主要定理，定理2.1和定理2.2，在第4节和第5节中得到证明。在第6节中，我们回到原来的问题，并讨论零集的f1，。. .，fk在有限域F上的空间. 在第7节中，我们将显式构造与随机构造进行比较。最后，在第8节中，我们讨论了我们的工作和格里菲斯和哈里斯猜想之间的一些联系2代数闭包设F是一个域，F是它的代数闭包.给定k个多项式f1，. . .，fk∈F[x1，. . .，xn]，我们将它们定义为V（f，. . . ，f）：={x ∈ Fn |f（x）=. . . = f（x）= 0}。我们将使用以下定义：一个k×n矩阵（其中k≤n）是k-正则的，如果它的所有k×k子式都是正则的（即有非零行列式）。例如，如果F是具有至少n个 不同非零元素γ1，. . .，γn则Vandermonde矩阵Ai，j= γi是k-正则的.下面的定理是我们构造的核心，并在第4节中得到证明。定理2.1. 设1 ≤ k ≤ n，d ≥ 1是整数，F是域. 设A是系数在F中的k × n矩阵，F是k-正则矩阵.设d1> d2>. . . > dn> d是两两互素的整数。 设多项式f1，. . . ，fk∈ F [x1，. . . ，xn]定义如下：fi（x1，. . . ，xn）：=卢恩j=1Ai，j·xdjn设U = V（f1，. . .，fk）<$F 表示由这些多项式定义的簇。然后，对于每个仿射簇V <$Fn的维数为k，次数最多为d，簇V <$U的维数为零。特别是|VU |≤ d· Yki=1迪岛选择d1，. . . ，dn是前n个大于d的素数，我们得到，对于绝对常数c>0，d1≤c（d+n）log（d+n），因此|（c（d + n）log（d + n））k ≤（d + n）O（k）.|≤ d·(c (d + n)log(d + n)) k≤ (d + n) O(k).（一）31m m +1 2m n−m +1nJ当次数d与变量数n相当时，这个界是相当有效的。在某些情况下，它是有用的，以获得更好的界限时，dn。这是通过以下结构实现的固定m > k，使得m整除n。设U∈Fm是由定理2.1构造的m维簇。我们证明了（n/m）-笛卡尔积Un/m在它与任意k维d次簇V<$Fn的交 上有界，并且这个界只依赖于m而不依赖于n.回想一下，如果U<$Fm是一个簇，那么它的（n/m）-笛卡尔积Un/m<$Fn是由下式给出的簇：un/m={x∈Fn：（x，. . .，x）∈U，（x ，. . . ，x）∈ U，. . . ，（x，. . . ，x）∈ U}。我们在第5节中证明下一个定理。定理2.2. 设k，d≥ 1是整数，F是域. 设m> k是整数，使得m除n 设A是系数在F中的k -正则k × m矩阵. 设d1> d2>. . . > dm> d是两两互素的整数。 设多项式f1，. . . ，fk∈ F [x1，. . . ，xm]定义如下：fi（x1，. . . ，xm）：= 布勒姆j=1Ai，j·xdjM设U= V（f1，. . .，fk）<$F 是由这些多项式定义的簇。对于每个仿射维数为k且次数至多为d的变种V<$Fn，Yk|01-0|≤dk+1·(i=1di）k.在特定情况下，如果x=0，则setm=0k/0k，并且letd=1，. . . .，dm，如果k在d之后，则Un/m具有至少（1-n）n的维数，并且|≤（d + m）O（k2）.|≤ (d + m) O(k2).（二）我们不知道如果绑定上|VUn/m|可以改进定理2.2所实现的，以匹配|VU|在定理2.2中建立。我们目前的分析只意味着一个较弱的界限。我们注意到，当d= 1时，在[DL12]中显示，|VUn/m| ≤mk。我们猜想，对于一般d，定理2.2中的界可以改进为：|VUn/m|时间复杂度为O（k）。3两个引理3.1关于Laurent级数解的变量T中的洛朗级数是以下形式的形式表达：h（T）= Σ∞j=−r4bj·T j510n也就是说，T中的形式幂级数具有有限个负幂。在变量T中的形式洛朗级数和来自F的系数的集合将被表示为F{{T}}。如果f（x1，. . . ，xn）是系数为F和h1，. . . ，hn∈F{{T}}，我们称f在h1，. . . ，hn如果f（h1（T），. . . ，hn（T））是F{{T}}的零元素。请 注意，在所评估的多项式中，T的系数是系数在该多项式中的系数集合的函数，并且该输出是定义良好的Laurent级数。 我们说h（T）有极点，如果T的至少一个负幂出现在其中，且系数不为零。下面的引理指出，每个至少一维的仿射簇都有一个罗朗级数的解，使得至少一个坐标有一个极点。它最初在[KRS 96]（备注1）中使用，但没有明确说明。证明将使用代数曲线理论的我们将使用的所有结果都可以在[Sha94]的前两章中找到引理3.1. 设V <$Fn是k ≥ 1维仿射簇，I（V）<$F [x，. . . ，x]是在V上为零的多项式的理想。 则存在h1（T），. . . ，hn（T）∈ F{{T}}，使得对于所有f∈I（V），fvan是关于h1，. . . ，hn. 在一次事故中，他的一个儿子被发现了。证据 我们遵循[KRS96，注释1]中给出的论证。 设CV是一条不可约曲线包含在V中，设I（C）为其理想，使得I（V）<$I（C）。考虑将Fn嵌入到通过添加新的坐标x（使得Fn与集合x= 1相同）来对射影空间PFn进行改进0 0恩设C是C在PF中的投射闭包。 由于曲线和超平面总是相交在预执行阶段，我们有一个包含点P0，x0= 0（即，无穷远的点我们希望在P0处使用幂级数解，但这是有问题的，因为P0可能是单一的。为了弥补这一点，我们利用了这样一个事实，即总是存在一条非奇异的不可约射影曲线C′和一个满射态射φ：C′→ C。 设Q0∈ C′是一个（非奇异）点，使得φ（Q0）=P0.设OQ0是Q 0的局部环，MQ0 <$OQ0是其极大理想.由于φ是一个态射，它的坐标可以局部地写成n +1个函数φ0，. . . ，φn∈ OQ0. 由于Q0是非奇异的，所以存在一个内射环同态τ将OQ0映射到T中的形式幂级数环F[[T]]，使得MQ0映射到包含所有可被T整除的幂级数的极大理想I0<$F[[T]]（即，具有零常数项的那些）。 对于每个0 ≤ i ≤n +1，定义对应于φ i的幂级数gi（T）= τ（φi）。然而，当P 0为零时，φ 0 ∈ M Q 0且s0 g 0（T）为零常数项.此外，由于P0至少有一个非零坐标，因此有一些gi（T）具有非零常数项。考虑形式Laurent级数hi（T）=gi（T）/g0（T），其中i∈[n]. 从一个关于在这个星期内发生的事件的分析来看，这个问题是一个很大的问题。 我们现在知道这是怎么回事了，这是一个很好的平衡。Letf∈I（C）anddletf<$∈ F[x0，. . . ，xn]是其均匀化定义为f<$（x0，. . . ，x1）= xdeg（f）·f（x1/x0，. . . ，xn/x0）。Sincefffan 是 指 在 Cw 上 具 有 idetiyfff（ φ0 ， ...， φn ） =0 。 这 说 明 f′ （ g0（T），. . . ，gn（T））= 0作为形式幂级数恒等式。 除以g0（T）deg（f），我们得到f（h1（T），. . . ，hn（T））= 0。这就完成了证明。6注3.2. 即使V定义在F上，引理给出的洛朗级数解的系数一般不会在F中，而只在代数闭包F中。注3.3. 罗朗级数中有一个极点的事实使这个引理如此有用（我们将在定理2.1的证明中看到）。这个极点允许我们只处理级数的首项，而不必分析高阶项（就像我们必须处理幂级数解一样）。我们将使用的基本事实是，如果h（T）有一个r阶极点，则h（T）d对每个d ≥ 1都有一个rd阶极点。3.2关于簇引理3.4. 设V ∈ Fn是维数为 d2> . . . > dn> d是两两互素的整数，并假定d1，. . . ，dn是互素的，|F|-1。 设U <$F n为定理2.1定义的簇，U ′= U <$Fn. 然后|为|F|n-k，|n−k,并且对于每个维数为k且次数至多为d的仿射簇V <$Fn，Yk|沃乌|≤ d·i=1迪岛第六章. 二、 Letk，d≥1beintegrs，n>0，且LeFbeaf ield。 令m>k/n∈N，使得m整除n。设d1>d2> . . . > dm> d是成对互质整数，并且假设d，. . . ，d是互质的，|F|-1。 设Un/m<$Fn是定义的簇1m由定理2.2，设U ′= Un/m <$Fn. 然后|为|F|n（1− k/m）≥|F|（1− n）n，|(1−ǫ) n,并且对于每个维数为k且次数至多为d的仿射簇V <$Fn，Yk|01-0|≤dk+1·(i=1di）k.7与随机构造的在这一节中，我们比较了我们得到的显式结果，结果比随机结构。在许多情况下，随机构造获得最优或接近最优的参数，并且这些可以与可以显式获得的最佳结果进行比较为13K由于技术原因，我们在本节中的讨论将仅限于定义在F.这与我们的显式构造相反，它也适用于在F的扩张上定义的varietes。定义不在F上的簇的主要技术困难是限制它们的数量（这个数量是有限的，因为我们只对Fn中的点感兴趣）。我们回想一下在推论6.2中得到的参数。令k表示维数，d表示度，n表示变量的个数，令n>0表示一个小参数。通过选择一个有限域Fapropriat，我们实现了一个子空间S istFnofiz的一种快速实现|S|≥|F|（1−n）n使得对于任意d次维数k的仿射簇V<$Fn，|≤（d + k /n）O（k2）.|≤(d+ k/ǫ)O(k2).在本节中，我们比较了如果SFn是随机选择的，|S|为|F|（1−1）; 我们通常会在这些变量的大小足够小的情况下，将其转换为随机数。我们注意到，我们对随机构造的简单分析在k≠n时中断，而我们的显式构造仍然得到与域大小无关的界n设Vn，d，k表示F中定义的d次k维簇族超过F.我是7号。1 .一、 Letn，d，k≥1，k>0是一个参数，且k≤n/4. LetF是一个文件，如果d≤|F|K.LetSFnbearanddomss sebsetofsize|S|为|F|（1−1）; 对所有的变种V∈Vn，d，k，S，的选择具有高概率.D|≤O|≤ Oǫ.ΣΣk+d+2·你知道吗？K首先，我们需要在一个簇V∈Vn，d，k中Fn中的点的数目的一个界。权利要求7.2. 设V∈ Vn，d，k. 然后|VFn| ≤d·|F|K.证据我们证明了索赔的诱导变量的数量，度和维数。它可以有效地为可计算的变量提供分类，如果V=0 V，则将V的分解分解为不可约簇，则deg（V）= deg（Vi）且dim（Vi）≤dim（V）。因此，我们假设V是不可简化的设Hc：=（x1=c），其中c∈F是超平面族.如果对于某个c，V∈Hc，则通过对变量数的归纳得出该断言。否则设Vc：=V<$Hc。则Vc的维数为k−1，次数≤d。因此Σ|≤|V c Fn|≤|F|· d|F|k − 1 = d|F|K .|k.c∈F我们接下来需要一个关于Vn，d，k中的变种数的界。回想一下，这个集合只包含定义在有限域F上的簇。权利要求7.3.|Vn，d，k|F|n · O（d（k + d + 2））.|n·O(d(k+d+2)).111K+IK证据 我们首先讨论不可约簇。设V是一个维数为k，次数为d的不可约簇. 假设w.l.o.g，x1，. . . ，x，k在V上代数无关。 我们首先证明存在多项式{fi（x1，. . . ，xk，xk+ i）：1 ≤ i ≤ n-k}，其中F中的系数为d次，使得V是U ={x ∈ Fn：f（x）=. . . = fn−k（x）= 0}。为了看到这个，注意，通过引理3.4，我们可以将fi取为通过投影到变量定义的多项式x1，. . . ，xk，xk+1。 Sinceeasumdx1，. . . ，xk是一个全局性的抽象概念，它包含了V，fi依赖于xk+ i。 让我们分解fi（x1，. . .，xk，xk+ i）=DiQj=1 fi，j（x1，. . . ，xk）·xj，其中1 ≤ di≤ d且fi，d不恒为零。 设g（x1，. . . ，xk）=nfi，d（x1，. . . ，xk），以及nii=1i设G={x∈F：g（x）= 0}是由g定义的超曲面。我们可以通过构造具有维度k。 此外，我们有V\G有维数k，因为V是不可约的，并且是不包含在G中。因此，存在一个维为k的U的Zebriki开子集，它包含V的Zebriki开子集。由于V是不可约的，这只能发生在V是U的不可约分量时。因此，我们得到存在F上k+1个变量的（n-k）个d次多项式，使得它们定义的簇有一个等于V的不可约分量。因此，V的不同可能性的数量由下式限定：. - 是的k+d+2（n−k）k+d+2k+d+2n|F|（千美元））的方式K≤nk|F|（K ）≤|F|n·O（K））。为了得到一般的，不一定是不可约的簇的界，我们需要对V的所有可能的分解求和到d1+的不可约分量。. . +dr=d。因此ΣYrk+d+2k+d+2|≤|≤d1 +. +dr=di=1|n · O（（i|n·O((i）的情况）≤|F|n·O（K））。我们现在证明引理7.1。引理7.1的证明 设c> 0是一个参数，以后再修正。 设S ∈ Fn是S_iz的随机子集|S|为|F|（1−1）; 我们将如何看待你对S的选择的高度重视，|SV|对所有V ∈ Vn，d，k，有≤ c。 为了证明这一点，首先考虑一个固定簇V ∈ Vn，d，k。 根据权利要求7.2，我们知道，|VFn|≤d|F|k，因此.|Σ|ΣPR[|S V |≥ c] ≤S|− n · c ≤（d|F|k − n）c ≤|F|−（n/ 2）n · c，|−(ǫ/2)n·c,C我们选择的参数。 不同的V∈Vn，d，k的数目由权利要求7.3限定为最|F|NS. k+d+2π）。So，forc≥O（s/s）weregbytheunionbounddthithattwitthehigh时间复杂度O（k）概率，|S V|对所有V ∈ Vn，d，k，有≤ c。118与Griffiths和Harris猜想的联系在这里我们考虑定理2.1如何与各种已知的关于完全交的子簇的结果和定理相吻合.121k1k一个d次超曲面是一个d次多项式的零集;它们形成一个向量空间Vn，d。 一个主张对一个非常一般的超曲面成立，如果它在多项式在外部时成立V n，d的Zagliki闭子簇的可数并集。 根据[GH 85]的一个猜想，如果Xd<$Pn是一个非常一般的具有足够高次数的射影超曲面，则对于每个子簇Z<$X，X的次数除以Z的次数。该猜想没有指定“s u ffi nly hig h degree”，但所有已知的猜想都有一个m p le d ≤ 2 n − 3。这种共同的联系是不为人知的。 当n=3时，它是经典的Nof-Le f s c h e t z定理. 在更高的维度只有弱得多的整除结果已知使用的方法[Kol92]和只有其中一些已明确制定。例如，如果Xd<$P4是一个非常一般的超曲面，且对于素数p≥5，d =p3，则p整除每个子簇Z<$Xd的次数。进一步注意，众所周知，对于猜想成立，肯定需要Vn，d关于完整的治疗，参见[第03卷，第III章]和[第89卷]，以了解更多相关结果。现在让我们假设上述猜想，并看看如果我们用相同次数的一般完全交来代替定理2.1的结构，它将意味着什么。将该猜想应用于几种超曲面，得到了：如果d1，. . . ，d，k是两两互质的，Xd，...，d：= Xd ·· · Pn是一个非常一般的充分高次数的完全交，那么d1···dk整除每个子簇的次数Z<$Xd1，.dk。现在设Y∈Pn是度mini{di}的任何子簇。<考虑交叉点的顺序YY Xd1 Y Xd1，d2···Y Xd1，.，dk。如果维度在每一步都下降，那么Y=Xd1，.，k是零维的。 否则，存在索引i，使得Yi：=Y<$Xd1 ， . ， di的维数为k−i，但Xdi+1 包含Y i的一个不可约分量。我们知道deg Yi=degY·d1· · ·di，并且Y ij <$Y i的每个不可约分支的次数都能被d1· · ·di整除。如果Yij<$Xdi+1，则它的次数也可被di+1整除。THUSdegY·d1···di=d egYi≥d egYij≥d1···di·di+1，矛盾边界degY mini{di}是最优的，如Xdi与k+1维线性空间的交集所示最后让我们注意到，[GH85]和相关的作品考虑投射品种，而设置考虑定理2.1是仿射的。事实上，我们构造的射影闭包是非常退化的：它们与超平面在无穷远处的相交是一个线性空间（具有高重数）。引用[DL12] Zeev Dvir和Shachar Lovett。 次空间躲避装置。 STOC 2012（即将出现），2012年。13[GH85] Phillip Griffiths and Joe Harris.关于Noether-Lefschetz定理和关于双循环中的余度定理的几点注记 MATH。 Ann. ，271（1）：31- 51，1985.[GR08] V. Guruswami和A.楼陀罗实现列表译码能力的显式码：最佳冗余纠错. 信息理论，IEEE Transactions on，54（1）：135- 150，2008。[Gur11] V. Guruswami.折叠里德-所罗门码的线性代数列表译码。Computa-tionalC onplexity，AnnualIEEEC onferenceon，0：77- 85，2011。[Hei83] Joos Heintz. 代数闭域中的可定义性与量词快速消去。我是说。 来吧。 SCI. ，24：239[Kol92]我不在乎。 我想让你看看。 在C1asif icatioofregularvarieties（Trento，1990）中，M a t h中的LectureNotesv o l u m e 151 5。，第136- 139页。 Springer，Berlin，1992.[KRS96]Ja'nosKolla'r ， LajosRo'nyai ， anddTiborSzabo'.NORM-GRAHS 和 BIPARTTCombinatorica，16（3）：399- 406，1996.[Sha94] I. R. Shafarevich 基本代数几何。Springer-Verlag New York，Inc.美国纽约州纽约市，1994年。克莱尔·瓦辛。格里菲斯和哈里斯的一个猜想。在《代数曲线与投影》（Tren to，1988）中，LectunntesinMath. 参见第270- 275页。施普林格，柏林，1989年。[Voi03]克莱尔·瓦辛。 霍奇理论与复代数几何。剑桥高等数学研究第77卷。剑桥大学出版社，剑桥，2003年。由Leila Schneps从法语翻译而来