稀疏仿射不变线性码的局部可测性：一项新的研究

1稀疏仿射不变线性码是局部可测的Eli Ben-SassonNoga Ron-Zewi<$MadhuSudanNogaRon-Zewi 2012年4月27日摘要我们表明，稀疏的仿射不变的线性性质在任意有限域是局部可测试的查询的一个常数。给定一个有限域Fq和一个扩张域Fqn，一个性质是将Fqn映射到Fq的一组函数。该属性被称为是仿射不变的，如果它是不变的仿射变换下的Fqn，它被称为是稀疏的，如果它的大小是多项式的域大小。我们的工作完成了Grigorescu等人[RANDOM 2009]以及Kaufman和Lovett [FOCS 2011]的一系列工作后者在q是素数的情况下给出了这样扩展到非素数的情况下，原来是不平凡的，我们的证明涉及到添加剂组合学的一些弯路，以及一个新的微积分的仿射不变的线性特性的建设性能测试。以色列海法理工学院计算机科学系和马萨诸塞州剑桥新英格兰微软研究院。李国章我不知道。梭IL. 该等储备乃根据欧洲共同体第七个框架计划（FP 7/2007-2013）（资助协议编号240258）而获得。†海法理工学院计算机科学系。 nogaz@cs.technion.ac.il. 研究进行时，作者是马萨诸塞州剑桥市新英格兰微软研究院的实习生，并得到了以色列科技部的支持。Reeearcnew-Eng land，Cambridge，MA. 我是一个胡@ mit。埃杜乌1内容1 介绍21.1问题及主要结果...........................................................................................................21.2动机...............................................................................................................................21.3与以往工作的....................................................................................................................31.4技术贡献............................................................................................................................41.5本文件............................................................................................ 其余部分的组织. 52第五章2.1建立k-单轨道特征性质对于k-局部可测性的52.2仿射不变线性性质............................................................................................................62.3仿射不变线性性质............................................................................................................73主要定理7的证明3.1伪测试满足本地可测试性............................................................................................... 83.2主要技术定理证明概述3.5...............................................................................................93.3覆盖（q，n）-移位代表集......................................................................................... 93.4分离一对具有不相交p-移位..................................................................................... 103.5在同一p移位...............................................................................................................113.6用于编写伪测试..............................................................................................................113.7完成定理3.5....................................................................................................................4分离同一p移位中的度数对-引理3.9125分离具有不相交p-移位的一对集合-引理3.85.1引理5.1............................................................................................................................. 176构造伪测试的演算-引理3.10的证明7基本和一般单轨道特征的等价性222|D|1介绍本文研究了线性仿射不变性质的性质测试，并证明了该类中的所有稀疏性质都是可测试的。在解释这项研究的背景和动机之前，我们在下面更精确地描述这些概念1.1问题和主要结果给定有限集合D和R（对于定义域和值域），映射D到R的函数的性质简单地由子集F<${D→R}给出（F是满足该性质的函数的子集）。属性测试研究了有效算法的可能性，这些算法对f：D → R的预言进行了很少的查询，并接受f∈F，同时以恒定的概率拒绝远离F的f。Distan ndistan gdi st a ngdistan g disoδ（f，g）=1·|{x|f（x）=g（x）|δ（f，F）=min g∈F{δ（f，g）}.一个性质F被称为k-局部可测试的，如果存在一个测试者对函数f：D→R进行至多k次查询，以概率1接受f∈F，同时以至少δ（f，F）的概率拒绝所有f。一个大的，非常重要的，一类性质，即代数的，是抽象的最好线性和仿射不变的特性。 在这样的设置的范围内的性质是一个（小）有限域Fq（其中Fq表示的领域的大小q）和域是一个（大）有限extensionFqn。 一个伪F_n{F_q_n→F_q}是一个F_q-向量空间，即. e. ，<$f，g∈F和dα∈Fq，则有αf+g∈ F.性质F称为仿射不变的，如果它在对该定义的仿射变换下是不变的，即。e. ，<$α，β∈Fqn 当hα/=0时，当f∈ F时，fα，β（x）= f（α·x+ β）也在F中.最后，我们说F是稀疏的，如果它只包含多项式许多功能在其域大小。 更确切地说，我们说F <${Fqn → Fq}是t-（大小-）稀疏的，如果|F|≤ qnt。我们的主要定理表明，所有的稀疏属性是可测试的一个常数数量的查询。定理1.1（主）. 对于每个q和t，存在k = kq，t使得对于每个n，每个t-稀疏的、线性的、仿射不变的性质F <${Fqn→ Fq}是k-局部可测的。我们的工作扩展了Grigorescu等人的先前工作。[GKS 09]和Kaufman和Lovett [KL 11]。后者，特别是证明了上述定理时，q是素数，留下开放的情况下，所有扩展的素领域。我们描述的关系，以前的工作，并解释我们的技术贡献后，讨论了研究仿射不变的线性性质的动机1.2动机属性测试：理解线性、仿射不变属性的一般动机是，它们形成了一些最有用的属性测试的最自然的抽象，这些属性测试在构建局部可测试代码和概率可检查证明中发挥了作用。某些措施可以使您在具有“线性”和“低数据量”两种策略的存储结构中充分利用数据。 一种高效的虚拟化方法是一种简单的简单方法，它是一种简单的简单方法，它是一种简单的方法，它是一种简单的方法。考虑到代数性质所起的主要作用，理解它们的可测试性似乎与理解图的可测试性一样重要。局部可测试码：如果仿射不变性的研究在属性测试的上下文中是自然的，那么对线性的限制在纠错码的上下文中也是自然的大多数研究得很好的纠错码都是线性的，而局部可测的纠错码通常是由线性3Q局部可测性质我们注意到，一个性质是线性的，仿射不变的和局部可测试的这一事实意味着它是一个纠错码。通过本-萨森等人的工作 [BHR 05]众所周知，所有的可用代码都是由一组本地约束定义的，即“LD PC代码”。然而，它也是已知的，从工作的Ben-Sassonetal。[BGK+05]为了使LDPC代码具有可局部化的冗余，必须具有局部约束的冗余集合。局部约束之间的冗余是一种相对罕见的现象，施加某种对称性（如仿射不变性）是获得这种冗余的一种方法。事实上，仿射不变性提供的对称性是唯一的设置（与一些额外的功能）的冗余是已知的，导致可测试的代码。因此，仿射不变的线性性质导致了一些最自然和最广泛的局部可测试码。尽管我们对仿射不变线性性质的结构有了比较好的理解，但我们还没有一个使这种性质局部可测的特征为了更好的生活。[AFNS06，BCL+06]. 如果您的数据不符合要求，properyFFn→Fq是一个“b a s e- p r o p e r t ies”的组合，propertiesarofokin d s-“low-degree“p r o p e r t ie s（所有已知的新数据集-多个数据集）degree）andd“s par s e“o ne s.（对于在BEN-S中使用CONJECTURESSEECTION5的这些可能不可靠的数据，进行了详细的描述。 [BGM+11a]。但是，有限线性局部可测试码的有限确定性和确定性意味着我们不能排除某些其他性质的存在，尽管“低分组”或“非分组”，但这些性质是局部可测试的。在此工作之前，我们还没有看到任何关于“数据备份”的信息，因为这些数据备份的信息是不可见的，也是不可见的。 这些工作基本上实现了预处理的“简单化”，以实现高效的预处理--在虚拟化环境中实现了可重用的预处理，并通过显示所有可能存在的“备份”的信息组合来说明这一点。 现在仍然存在一个有限的结果，即其余类的仿射不变线性性质是不可测试的。1.3与以往工作的测试稀疏代码的任务由Kaufman和Litsyn [KL 05]发起，然后由Kaufman和Sudan [KS 07b]进一步推进，最近由Kopparty和Saraf [KS 10]进行。所有上述结果表明，如果一个代码是稀疏的，距离很高，那么它是可测试的。（[KL05]，[KS07b]只处理二进制代码。[KS10]的结果似乎扩展到素数字母码，甚至q元字母码的情况，尽管结果没有这样说明测试稀疏仿射不变线性性质的任务由[GKS 09]发起。他们表明，在某些特殊情况下，二进制稀疏仿射不变的线性性质是可测试的。[KL 11]极大地扩展了这个结果-他们证明了素域F p上的每个稀疏仿射不变线性性质都是可测试的。上述结果证明的主要内容是证明稀疏仿射不变线性性质满足稀疏仿射不变线性性质的充分条件（高距离）. 当所有这些都是在过程中获得“好处”时，这可以被视为一种奖励，但对于可测试性来说不是必需的。由于一个根本原因，在非素有限域上的测试变得更加复杂。F q上的码（其中q=ps，p是素数且s > 1）具有适当的距离，但在所有的预编码工作中，在该序列中肯定无处接近“e x单元t”。我发现，我们的算法主要依赖于这样一个事实，即来自所讨论的稀疏属性的每个非零函数都是大致平衡的（取范围内的每个值的次数大致相同）。这种说法在我们的环境中根本不正确。其原因不仅在于Fq包含Fp作为子域，而且还在于Fq包含素子域Fp上的许多向量空间。 事实上，对于F q的每个这样的子空间V，可以创建包含仅从V取值的函数的稀疏性质，并且对V中的每个值取值的次数大致相同。这一障碍4我我证明是足够的脱轨以前的证明技术（这仍然是有用的，但不够）。为了克服这一障碍，我们重新审视仿射不变的线性属性的结构，并引入一个简单的微积分来构建此类属性的测试我们的最终测试也使用了一些来自和积定理证明的代数机器来构建必要的测试。1.4技术贡献先前关于测试仿射不变线性性质的工作已经表明，它足以对具有相同的“最佳”函数的数据进行识别。具体而言，如果Trace：Fqn →Fq表示由Trace（x）=x+xq+··+xqn−1给出的标准迹映射，则它（大致）足以构造出对于T r a c e（x e）∈ B的具有d ∈ G的任意块的连续函数的“t e sts”。为了实现这一目标k由元组α1，. . .，αk∈Fqn 结合Fq-线性形式（λ1，. . .，λk）∈Fk.“te s t“是一个克i=1 λiTrace（αd）= 0，如果克i=1QλiTrace（αe）/= 0。 集合G和B取决于被测试的属性F。 以前的分析，特别是[KL11]，选择了一个一个恒定大小的随机测试，接受所有好的函数，并能够声称这样的测试将以（压倒性的）高概率拒绝所有坏的函数。这一说法依赖于这样一个事实，即所有非零函数（好/坏）对该范围内的每个值的取数频率大致相等。这一事实在我们的例子中不再成立，并转化为一个代数挑战。对于某些d∈G和de∈Bitisnolonge，如果某个数据集和某个数据集T r a c e（xd）将以很高的概率返回Trace（x e）。对我们来说，一个特别具有挑战性的情况是当e = pid时，其中p是文件dwe与h的关系。为此，我们使用加法组合学中的一些方法，设计了一个测试，该测试接受Trace（x d）而拒绝Trace（x p i d）。这是这项工作的核心技术贡献，我们将在接下来对此进行深入探讨如果我们幸运地在Fqn中有一个元素α，使得λ，αd包含在Fq中，但不包含在Fpi中 本文讨论了λ · f（1）= f（α）时的临界点。“接受f（x）= Trace（xd）而拒绝f（x）= Trace（xpid）。一般来说，我们不能保证.有这样一个幸运的α。 因此，我们考虑集合A=αdΣ| α ∈ Fqn 和它的双态和设A={a1 +. . . +a|ai∈A}。如果我们可以证明，对于某个常数λ（可能取决于F和q的稀疏性），λ A包含一个元素λ∈Fq\Fpi，这似乎也是合理的，因为集合A在乘法下是完全封闭的，因此和积估计[BGK 06]表明，|A.A.| ≫ |一|.因此，可以想象，较大的集合λ A可能包含一个很好的λ，如果是这样，我们将有一个arity约束，大致将Trace（xd）与Trace（xpid）分开。确定在加法下（对于给定的d），λ A是封闭的最小λ是W a r i n g对于有限域d s的普遍性研究得很好。 对于Cochrane和dCipra，bsbone的值为n≤d1/log|一|[CC 11]（更多信息见[Cip 10]）。对于一般的d，参数可能需要随着n的增长而增长，但是在我们的例子中d是有限的（由于F的稀疏性），所以上面的界限给出常数。为了给出一个简单而完备的证明，我们提供了一个比Waringg的证明更简单的方法，既能满足我们的目的，又更容易分析。基于[BIW 06]中和积定理的简化分析，我们考虑形式为A=（A−A）/（A−A）的集合A（即，包含两个元素之比的集合，每个元素都可以表示为A的两个元素之差）。我们表明，与一个自包含的基本证明，对于足够大的集合A，A是封闭的下，5Σ加法，因此包含一个λ∈Fq\Fpi。通过一些额外的工作，我们然后能够从T r ac e（x p i d）模拟O（k）s e p a t i n g T r ac e（x d）的“lucky“cas e b o v e t a c o n s t r a i n t at不幸的是，虽然手工测试设法解决了单个对d，e的玩具挑战，但它无法构建一个同时接受所有好函数Trace（xd），d ∈ G，同时拒绝所有坏函数的单个测试。特 别是，关于仿射不变性质测试的文献将测试简化为区分基本函数，这似乎关键地依赖于这样一个事实，即测试同时接受d ∈ G的所有函数Trace（xd）。 只接受其中一个基本函数的测试在它们的设置中似乎是无用的。事实上，我们称我们的测试区分Trace（xd）从Trace（xe）“p s e ud o - t e s t s“由于这是r a o n。为了使我们更好地进行测试，我们构建了一种用于组合伪测试的演算，该演算允许我们构建更大的伪测试，该更大的伪测试组合更小的伪测试以扩大被接受的好函数的集合或者扩大被接受的坏函数的集合。除此之外，我们还利用Kaufman和Lovett的证明方法，找到了区分其它good和bad funti on的伪检验。我们在使用我们的实用程序时，会使用一个“psedotestt”，它接受所有好的功能，拒绝所有坏的功能。在这个阶段，我们现在可以应用以前的工作，以获得一个测试的家庭F。1.5文件其余部分的组织在第3节中，我们在第2节中回顾了以前工作中所需的工具后证明了我们的主要定理。InSection4对于将x d与x e分离的最具挑战性的情况，我们使用了一种特殊的复杂的拓扑结 构 来 实 现 “p s e d- t e s t“ ， 其 中 e = p i d （ 参 见 前 一 小 节 中 的 讨 论 ） 。 选 择5generaasamaneref[KL11]和constrat a p s e d e t et 在第6节中，我们将继续使用我们的数据库，以便进行“p s e ud o t e s t s”的合并。 第7节，不需要为我们的制造业提供任何帮助，这是不必要的。 它可以有效地简化仿射不变性质测试研究中的约束条件。2预赛我们首先回顾的概念k-单轨道特征化，度集和边界集的仿射不变的线性家庭和他们的角色，在测试这些属性。本节中介绍的所有信息已经出现在以前的作品中[KS08，GKS08，GKS09，BS11，BGM+11a]。我们将在[BGM+11a，Sections2，3]中列出这一点。2.1建立k-单轨道特征性质是k-局部可测性的充分条件我们的稀疏仿射不变线性性质的测试器来自一个结构定理，该定理表明，稀疏仿射不变线性性质具有“s in gle-or b bit ch ar act eriza t i o n“。为了说明这一点，我们不需要几个定义。定义2.1（k-（基本）-约束，k-表征）。 一个k-约束C=（α，. 布 雷尔λii=1）overFqn由向量α =（α1，. . . ，αk）∈ Fk和r个向量λi=（λi，1，. . . λi，k）∈ Fk，对于qnqK1≤i≤r。我们说约束C接受函数f：Fqn→Fqn，如果j=1λi，jf（αj）= 0，所有1≤i≤r。否则我们说C排斥F。我们说一个约束是基本的，如果r=1。设F∈{Fqn→Fq}是线性性质.F的k-特征是k-约束C1，. . .，Cm使得f∈F当且仅当Cj接受f，对任意j∈{1，. . .，m}。6众所周知[BHR 05]，每一个k-局部可测线性性质必须有一个k-特征。在仿射不变的线性性质的情况下，一些特殊的特征是已知的，导致k-可测性。我们接下来描述这些特殊的特征。定义2.2（k-单轨道特性（k-s-o-c））。令C=..α，λi布雷尔河i=1是k约束在Fqn上 C在仿射变换集合下的轨道是以下k-约束{TC}T=，的。（T（α1），. . . ，T（αk）），.布雷尔河λii=1、| T : Fqn →Fqn 是仿射变换我们说C是F的k-单轨刻划（k-s-o-c），如果C的轨道构成F的k-刻划.我们说F有一个基本k-s-o-c，如果上面的约束C是一个基本约束。（在这项工作中证明的简化之一是基本的单轨道特征等价于一般的单轨道特征，参见。第7节）Kaufman和Sudan [KS 08]的一个定理（也见[KS 07 a]）说k-s-o-c蕴含局部可测性。定理2.3（k-s-o-c蕴含局部可测性，[KS 07 a]定理2.9.）. 设F ∈{Fqn→Fq}是仿射不变的线性性质。如果F具有k-单轨道特征，则F也是poly（k）-局部可测的。2.2仿射不变线性性质设F ∈ {Fqn→Fq}是函数的线性仿射不变性质请注意，{Fqn→Fq}可以唯一地写成一个从Fqn[x]至多为qn−因此，对于函数f：Fqn→Fq，我们定义其支集，记为supp（f），为指数在一个非公开的社交媒体平台上。 I. e. ，supp（f）={d∈{0，. . . ，qn−1}|cd/=0}wheref（x）= dcdxd。F的度集是F中函数支集的并集：Deg（F）=<$f∈Fsupp（f）.相反，对于一组度D {0，. . . ，qn− 1}令Fam q（D）={f |f：Fqn→ Fq，supp（f）<$D}.仿射不变线性性质是用它们的度集来表征的（这通常在nexa中说明），并且这些度集具有特殊的结构--ya re“closed“und e r“p - s had ows“and d“（q，n）- s hifts“a sex p l a i n e d n ex t。定义整数d的p-阴影为整数的集合，其基-p表示为但不是所有人都知道，这是一个很好的机会。更准确地说，在数据库中定义i≥0dipi我们定义阴影p（d）=Σi≥0伊比伊|ei∈ {0，1，. . . ，di} i ≥ 0。从文献[KS08]可知，当d∈Deg（F）满足仿射不变线性性质时，F则q·dmodqn− 1也属于Deg（F）。 这激发了整数d的（q，n）移位的以下定义：.移位q，n（d）={. 0}Did=07c∈{1，. . . ，qn− 1} |c <$qi·d mod qn− 1，对于某个0 ≤ i ≤ n1 ≤ d ≤ qn− 18将0与qn−1区别对待的原因是这两个指数导出的函数有些不同，即00 = 1，但0qn−1 =0。一组整数D的p-阴影是阴影p（D）=Sd∈DShadowp（d）.我们说D是p-阴影如果D= Shadowp（D），则闭合D的（q，n）-移位也有类似的定义，我们说D是（q，n）-移位闭的，如果D= Shiftq，n（D）。下面的公式是[BGM+11a，Lemmma2. 11]。证明了在{Fqn→Fq}中的一个非线性映射是由它的度集刻画的，并且这个度集是p-阴影和（q，n）-移位闭的.引理2.4（度集对仿射不变线性性质的刻画）。 令F{Fqn→ Fq}是仿射不变的线性性质。 则Deg（F）是（q，n）-移位闭的，p-阴影闭的，并且F = Famq（Deg（F））。相反，假设D是（q，n）-移位闭和p-阴影闭的度集。 则Fam q（D）是仿射不变的线性性质，并且D = Deg（Fam q（D））。注2.5（引理2.4中p和q的作用）。我们指出域Fq的特征p和它的大小q在上述引理中起着不同的作用。 一个整数的阴影是相对于以p为底的表示，而一个整数的移位是通过取它的q2.3仿射不变线性性质仿射不变线性性质的度集是p-阴影闭的这一事实，促使了[BGM+11a]中的Bord定理的失败. 在构造我们的稀疏仿射不变线性性质测试器时，这将是一个不可分割的过程。定义2.6（边界）。仿射不变线性性质F ∈ {Fqn→Fq}的边界，其中q是一个p-阴影p，是Deg（F）的一个p-阴影中的每个元素的集合，e不在D e g（F）中，但e的p -阴影中的Border（F）={e∈{0，. . .，qn− 1}|e/∈ Deg（F）但（Shadow p（e）\ {e}）<$Deg（F）}.在下文中，如果Fqn上的约束C接受函数f（x）=xd，则我们说它接受次数d，否则我们说C拒绝次数d。 对于一组度D {0，1，. . . ，qn− 1}，我们说约束C接受D，如果它接受D中的所有次数。在定理1.1的证明中，我们将通过边界的概念使用以下k-单轨道特征化的等价定义引理2.7（经由边界的k-单轨道可表征性质的等价定义，[BGM+11b]，Lemma3. 二、）的。LetFbeanaf ine-invariantlinearppery，并且LetCbak-constraint。则C形成F的k-单轨道特征当且仅当C接受Deg（F）中的所有度并且拒绝Border（F）中的所有度。3主要定理在本节中，我们证明我们的主要定理（定理1.1），并解释主要的新成分和它们的必要性。与以往关于仿射不变线性性质的k-局部可测性的工作一样，我们的主要定理也是通过证明k-s-o-c性质的存在性而得到的定理3.1（稀疏仿射不变线性性质具有k-单轨道特征）。对于每一个素数p的幂q和每一个整数t，存在一个整数k = k（t，q），使得以下成立。 若F ∈ {Fqn→ Fq}是t-稀疏线性仿射不变性质，则F有k-单轨刻画。主要定理1.1的证明 由定理3.1和定理2.3直接得出。9RK3.1伪测试满足局部可测性我们的简单的比特流实现方式是通过以下两种方式来实现的，即我们在下面定义的两种类型的“p s e ud o t e s t“。Defi。n=3.2（Pseudo-test）。对于连接集合D，B{0，. . . ，qn−1}，和ndak-constraintC=（α， λii=1），我们说C是一个k-伪测试，如果C接受D中的所有度，并拒绝所有的B级。我们说C是一个基本的伪测试，如果它是一个基本的约束。（当这种传统的知识结构将导致大量的数据丢失，数据挖掘基本上是一种“重复性测试“。）因此，上面的伪测试不需要满足任何语义属性。虽然测试本身在单个内存空间{xd}中 非 常 有 效 |d∈D}tclearlyacceptsavastnber of other functions（因为它是一个单一的确定性测试，因此接受一个维数为qn−r的子空间）。因此，它远非健全。我们的意图是使用伪测试的轨道作为测试，但是这个轨道现在还不完整！它可能不以概率1接受xd，即使d∈D。因此，伪测试似乎与手头的任务完全无关。然而，正如我们在下面的推论中所指出的，在某些情况下，它们确实可以很好地作为测试。此外，有些令人惊讶的是，有可能采取两个伪测试，其中每个都是不完整的，或不健全的，并将它们组合起来得到完整和健全的东西。实际上，伪测试的价值在于它们可以很好地组合在一起 一些基本步骤已在Propositions6中进行了说明。2和6。4和3中的“bro a d“组合。10年来，它是一个非常简单的伪测试（“ice“），它是一个“pieece me al”，来自于（非同步的）简单的伪测试。伪测试和单轨道特征化之间的关系由以下推论给出，该推论是引理2.7和伪测试的定义的直接结果推论3.3（k-单轨道的等价定义）通过伪测试的属性）。设F是仿射不变线性性质，C是k-约束。 则C构成F的k-单轨刻画当且仅当F是分离Deg（F）和Border（F）的伪测试。当应用上面的推论时，我们可以使用下面的简单引理：Fqn上的约束接受度d当且仅当它接受其（q，n）-移位中的所有度。引理3.4. 设d是{0，1，. . . ，qn− 1}，设C是Fqn上的k-约束. 那么C接受d当且仅当它接受Shift q，n（d）中的所有度数。证据设d′∈Shift q，n（d）使得d′<$d·q <$mod qn− 1。那么对于所有1≤i≤r，我们有. 克 λ阿克什图尔克αd=q d·qd′j=1i，j，jj=1λi，jαj =j=1λi，jαj，其中第一个等式是由于qn的幂是Fqn上的线性运算，而第二个等式是由于λ∈F，因此λq<$=λ.因此，我们有，λ αd=0当且仅当i，jqd′i、ji、jj=1i，j，jj=1λi，jαj =0。给定伪测试的概念，我们可以陈述其证明占据本文其余部分的主要技术定理下面我们说D′是一个（q，n）-移位闭集D的（q，n）-移位代表集，如果移位q，n（D′）=D。1000定理3.5（主要技术-稀疏仿射不变线性性质具有k-伪检验）。对于每一个素数p的幂q和每一个整数t，存在一个整数k = k（t，q），使得以下成立。 设F ∈ {Fqn→ Fq}是t-稀疏仿射不变线性性质，D′，B′分别是Deg（F），Border（F）的（q，n）-代表集. 然后存在一个k-伪检验，它将D′与B′分开。定理3.1的证明 由定理3.5、推论3.3和引理3.4直接得出。3.2主要技术定理3.5分别固定Deg（F）和Border（F）的（q，n）-移位代表集D′，B′我们构造了一个伪测试，它通过三个步骤将D′从B′中分离出来，如下所示。1. D′×B′由常数个乘积集覆盖D′× B′= D′× B′×。. . D ′× B′（一）0 0ℓ ℓ其中常数k仅取决于t和q，并且关键地，与n无关。2. 对于每个i = 1，. . . ，n构造一个k′-伪测试，将D′与B′分开，其中k′不我我依赖于n（它也依赖于q和t）。3. 将k′-p微分方程组的一个完全解称为“组合解”，以确定一个k-p微分方程组，该方程组将D ′与B ′分开，其中k = k（k ′，t，n）。这通过一个大小仅取决于q和t而与n无关的伪检验将D ′与B ′分开，从而证明了定理3.5。我们现在详细介绍每一个步骤。第二步将分为两个子步骤，因为我们需要考虑两种非常不同的配对集合，每种都需要自己的一套工具。3.3覆盖（q，n）-移位代表集首先我们用集对定义D′×B′的覆盖，然后在引理3.7中限定覆盖中的集对的数目。（检验表明，我们的覆盖实际上是D′×B′的一个划分，但我们的其余证明只需要覆盖的较弱假设。定义3.6（封面）。给定D′，B′分别是Deg（F）和Border（F）的（q，n）-移位代表集，其中q=p，p为素数，将B′划分为B0 = B′\Shift p，sn（D′）;B1 = B′\Shiftp，sn（D′）.（二）集合D′=D′和B′=B0. 对D′× B1中的对任意排序为{（d1，b1），. . . ，（d<$，b<$）}，其中=|D′|·|B1|并且对于所有i=1，. . . ，J.我我注意，虽然Border（F）的元素不属于Deg（F）（参见定义2.6），它们可能属于Shiftp，sn（Deg（F）），因此集合B1确实可以是非空的。检查表明，定义3.6中的上述对集合覆盖了D′×B′。以下是由债券组成的债券基金的组成部分|D′|·|B1|. 这个定理的证明部分很快就会被使用，由于它的证明依赖于第一部分，我们发现在这里包括它是很方便的。到根据数据段的数据集总和，确定数据段的预处理数据（d）代表D。形式上，如果d=i≥0dipi则wtp（d）=i≥0di.1100引理3.7（t-稀疏性质具有稀疏代表集）. 假设F<${Fqn →Fq}是t-稀疏仿射不变线性性质。则以下成立：1. 存在Deg（F），Border（F）的（q，n）-移位代表集D′，B′，使得|D′|≤ 2 t +1，且假定q =ps，其中p是素数，则B1= Border（F）<$Shift p，sn（D′）的大小至多为s（2 t +1）。2. Deg（F）中的所有整数的p-权重至多为2 t，Border（F）中的所有整数的p-权重至多为2t+1。Proof. 我们的价格是2欧元。15from[BGM+11a].这是因为如果Fist-paenit有一个大小至多为2t + 1的（q，n）-移位代表集D′. 边界可能具有更大的尺寸，但是如果我们将注意力仅限于位于Shift p，sn（D′）中的元素，则它们可以由尺寸至多为s的集合B1表示|D′|因为对于每个非零d∈D′，d，dp，. . . ，dps−1覆盖d的（p，sn）-移位。为了证明第二部分，我们称Deg（F）包含p-权至多为2t的整数.根据定义，这将立即意味着（cf.定义2.6），边界（F）的每个元素的p-权重至多为2t + 1。 要看到Deg（F）不能包含p-权重大于2 t的整数，请注意引理2.4暗示如果p-权重r的整数属于Deg（F），则对于每个r′= 0，1，.，在Deg（F）中存在p -权重r ′的整数。. . ，r − 1. 由于整数d的（q，n）移位仅包含与d具有相同p权重的整数，这意味着|D′|> r. 的假设|<2 t + 1因此表明，Deg（F）中没有任何整数具有如所要求的大于2 t的p -权重| ≤ 2 t + 1 thereforeshows that no integer in Deg(F) has p-weight greater than 2 t as claimed这就完成了我们的证明3.4分离具有不相交p-移位现在我们转向从定义3.6中给出的覆盖中分离单个集合对的任务。我们首先展示一个伪测试，它将一对集合D，B分开，使得B不包含D中的任何p移位一度。该伪检验将用于分离集合D′从B'和此外，用于分离所有对（di，bi），使得次数bi不属于次数di的p移位。我们的证明方法使用考夫曼和洛维特的工作[KL 11]。用我们的伪检验语言，证明了对素域Fp上的每个t-稀疏仿射不变线性性质F <${Fpn→Fp}，存在一个k（t）-伪检验来区分D′和B′，其中D′，B′分别是Deg（F），Border（F）的（p，n根据推论3.3和引理3.4。这容易地暗示F也是k（t）-单轨道可表征的。我们观察到[KL 11]的证明方法实际上给出了以下更一般的伪测试。引理3.8（不同（p，n）-移位的分离）。 对于每个t，w和素数p，存在k = k（t，w），使得对于足够大的n，以下成立：设D，B ∈ {0，. . . ，pn-1}，使得|D|≤ t，B在D中不包含任何（p，n）-移位，且对任意的d ∈ D<$B，wtp（d）≤ w. 则存在将D与B分开的单个（基本）k-伪测试C。我们在第5节中证明了这个引理。要看到[KL 11]的结果是它的一个特殊情况，请注意，如果F ∈ {Fpn→Fp}是素域Fp上的t-稀疏仿射不变线性性质，则引理3.7意味着Deg（F）有一个大小至多为2 t + 1的（p，n）-移位代表集D′.此外，同一引理的第二部分还暗示：如果B′是Border（F）的（p，n）-移位表示集，则对任意d∈D′∈B′，wtp（d）≤2t + 1.最后，注意F是Fp上的仿射不变线性性质这一事实意味着它是（p，n）-移位闭的，因此B′在D′中不包含任何（p，n）-移位。12003.5在同一p位移中分离一对度引理3.8只给出了一个伪测试，它分离属于不同（p，n）-移位的度对如上所述，这足以证明素域Fp上仿射不变线性性质的单轨道特征化，因为这些性质的度集是（p，n）-移位闭的。然而，在大小为q=p的非素域的情况下，仿射不变线性性质不一定是（p，sn）-移位闭合的，因此我们需要能够分离属于相同（p，sn）-移位的度对。下面的引理涵盖了这种情况。引理3.9（在相同的（p，sn）-移位中两个度的分离）。设q= p，p为素数，d ∈{0，. . . ，qn− 1}，b ∈ Shift p，sn（d）\Shift q，n（d）是p-权的一对次数，至多w. 则存在单个（基本）k-伪测试C，其分离{d}和{b}，k = 4·84w+1。如前所述，这是我们必须显式设计伪测试的情况。我们证明这个引理，使用来自和积定理的证明的机器，在第4节。3.6一种构造伪测试到目前为止，我们已经找到了定义3.6中给出的D′× B′的覆盖