Schur多项式的半环复杂性的界是O(log(λ1))

关于Schur多项式谢尔盖·福明，迪玛·格里戈里耶夫，DORIANNOGNENG和E'rIcScHOST2018年10月8日，抽象。半环复杂性是算术电路复杂性的一种，它只允许两种运算：加法和乘法。证明了Schur多项式s λ（x1，. . .，x，k）的有界性是O（log（λ1））的.关键词 半环复杂性，Schur函数，Young tableaux。主题分类。 2010年数学科目分类小学68Q25，中学05E05。1. 导言和主要结果设f（x1，. . . ，xk）是具有非负整数系数的多项式。因此，f可以仅使用加法和乘法计算，而无需减法或除法。更准确地说，可以构建一个算术电路，其中◦ 每个门执行加法或乘法运算◦ 输入是x1，. . .，x k，可能还有一些正整数标量;◦ 唯一的输出是f（x1，. . . ，x k）。f的半环复杂度（或{+，×}-复杂度）是（即，在）这种算术中的最小数目的门电路.这个概念如图1.1所示。更多详细信息，请参见Fomin等人（2016，第2节）及其参考文献。arXiv：1608.05043v2 [cs.CC] 2018年5月2Fomin，Grigoriev，Nogneng Schost/×关于我们✻×♥✻❅■❅公司简介✻❅■❅×♥❅公司简介✻❅■/✒/✒✻❅■❅//下载♥联系我们❅❅公司简介//×♥联系我们x1x2图1.1：计算多项式的最小+，f（x 1，x 2）= h 5（x 1，x 2）= x5+ x4 x 2+ x3 x2+ x2 x3+ x 1 x4+ x5。这1 1 1 2 1 2 2 2电路利用公式H5（x1，x2）=（x1+x2）（x2（x2+x2）+x4）。1 1 2 2本文研究对称多项式的半环复杂性的判定问题。更具体地说，我们把注意力集中在舒尔函数，一类重要的对称多项式，在数学的几个分支中发挥着突出的作用;见，例如，Macdonald（2015，Chapter I）andStanley（1999，Chapter 7）.设λ=（λ1≥λ2≥···≥0）为整数分拆。的Shurfunction（or Shurpolynomial））sλ（x1，. . . ，xk）是一个symmet。三次多项式|λ|=iλ i在变量x1，. . .，xk其可以以许多不同的方式来定义。一个令人瞩目的fea-舒尔多项式的一个令人兴奋的研究对象，在代数复杂性理论是经典公式定义他们分为两类。一方面，有行列式表达式（例如，Jacobi-Trudi公式或双交替公式），其提供了在无限制设置中计算Schur函数的有效方法，即，当所有的算术运算都被允许时。另一方面，Schur函数是半标准Young tableaux的生成函数。这种描述将它们表示为具有明显正系数的多项式;因此它们可以使用加法和乘法来计算×Schur多项式的半环复杂性3′1J2JJ14仅限折叠。然而，我们注意到，基于这些单项展开的朴素方法产生的算法（半环）复杂度非常高，实际上离最优值很远。我们的主要结果如下。 (We使用符号λ′=（λ′≥λ2 对于与λ共轭的分区，≥· · ·）。THEOREM 1.1. 给出了Schur多项式s λ（x1，. . . ，xk）的时间复杂度为O（log（λ1）k52kd），其中d =max λ′（k −λ′）.由于k≤k（否则s（x，. . .得双曲余切值.）= 0）且d≤k2，我们得到：推论1.2。Schur多项式的半环复杂性1s λ（x1，. . . ，xk）的上界为kk（4 +o（1））O（log（λ1））. 如果如果变量的个数k是固定的，那么复杂度为O（log（ λ1））。REMARK 1.3.在数值计算中，设计有效的加法和乘法算法的问题自然会 出 现 ， 因 为 这 些 算 法 具 有 有价 值 的稳 定 性 。 出 于 这 些 考 虑 ，Demmel& Koev（200 6）使用动态规划方法设计了一种用于约束S chur多项式的{+，×}-lgorithms。在的符号中在1.1或5.3中，Pr o p oson l oc。 c它。一个简单的例子是，sλ（ x1，.. . ，x k）的时间复杂度为O（e5. 2|λ| Oakland）。当k是固定的，并且形状λ增长时，这个界限要大得多比推论1.2中的要多 另一方面，在λ固定而变量数k增长的情况下，Demmel-Koev算法的复杂性是关于k的线性的，而定理1.1中的界是关于k的指数的。如果能找到这些结果的共同概括，那将是很有趣的。我们分两个阶段证明定理1.1在第一阶段（见第3节），我们处理一个特殊情况，其中划分λ只有一个（非零）部分。更明确地说，我们得到以下结果。回想一下，完全齐次对称多项式Σhn（ x1，.. . ，xk）=1≤i1≤···≤in≤kxi1···xinλK4Fomin，Grigoriev，Nogneng Schost是变量x1，. . .，xk. 参见图1.1中的示例。THEOREM 1.4. 证明了完备齐次对称多项式HN（x1，. . . （k=1），时间复杂度为O（ n）。我们在第6节中给出的定理1.1的证明依赖于三个主要成分：◦ 定理1.4;用完全齐次多项式表示可壳偏序集的多链生成函数的公式，见第4节;◦ 作为多链生成函数的舒尔多项式的表示，或者更确切地说，其迭代和，见第5。2. 相关问题确定Schur多项式的半环复杂性的一般问题是公开的。特别是，以下棘手的问题仍然无法解决。问题2.1（Fomin等人，2016，问题3.2）。是s λ（x1，. . . ，x k）由k中的多项式限定，并且|λ|？REMARK 2.2. Schnorr（1976）提出了一种获得半环复杂性下界的一般方法。Schnorr的界限仅取决于多项式的支持，即，对正系数有贡献的单项式的集合。施诺尔氏Shamir &Snir（1977）进一步完善了这一论证; Jerrum &Snir（1982）给出了强有力的应用。 如Fomin et al. （2016，备注3.3），Schnorr型下界在Schur函数的情况下是无用的，因为计算Schur 函 数 很 困 难 ，不 是 因 为 它 的 支 持 ， 而 是 因 为 它 的 系数（Kostka数）的复杂性。计算单个Kostka数的问题是P-完全的（Narayanan2006），而Schur函数的支持是很容易确定的。◦Schur多项式的半环复杂性5关于我们{− ×}REMARK 2.3. Fomin等人 （2016）研究了半环复杂性的概念以及其他类似的计算模型，涉及算术运算的限制集。总之，本文给出了在上述文献中所得到的结果. 前引书，与Jerrum Snir（1982）和Valiant（1980）证明，在某些情况下，对允许的算术运算的二元集+，进行相邻的减法和/或除法可以显著降低计算复杂性。(By相反，从+，中去除除法只需要多项式代价，如Strassen（1973）所示。我们建议读者参考Fomin et al. （2016）讨论这些问题。REMARK 2.4. 在非限制模型中，可以计算Schur多项式s λ（x1，. . . ，xk）在k和log（λ1）的时间多项式中，通过双交替公式（Stanley1999，Section 7.15），并使用重复平方来计算相关行列式中出现的变量的幂。Fomin等人研究的一个重要的复杂性模型。 （2016）是无减法复杂度，它允许加法、乘法和除法运算。事实证明，舒尔函数的无减法复杂度确实是多项式：T HEOREM 2.5（Koev2007，第6节，Chan等人2008，第4节，Fomin等人2008，第10节，Fomin等人2008，第11节，Fomin等人2008，F 2016，定理3.1）。 Schur多项式s λ（x1，. . . ，xk）的时间复杂度为O（n3），其中n = k +λ1.在loc.前引书在本质上利用除法，所以它们不会使我们更接近问题2.1的解决方案。由于无减复杂度由上而下受半环复杂度的限制，定理1.1意味着一个特殊的Schur多项式sλ（x1，. . . ，xk）可以比定理2.5的上界小得多（对于小k）。问题2.6. 找到同时加强定理1.1和定理2.5的舒尔多项式的无减法复杂度的自然上界。6Fomin，Grigoriev，Nogneng Schost我⌊ ⌋−REMARK 2.7. Grigoriev &Koshevoy（2016）给出了单项式对称函数的{+，×}-复杂度的指数下界。3. 完全齐次多项式在本节中，我们证明定理1.4。我们固定k，使用符号Σhm= hm（ x1，.. . ，xk）=1≤i1≤···≤im≤khm= hm（x2，. . . ，x2），xi1···xim，1kem= em（ x1，.. . ，xk）=1≤i1··· ≤<$n <$$>且 b≥<$m−k<$$>≥<$n−2k+1<$=2 2 2 2n2k+ 1。因此，我们可以使用公式3.2来计算这些hm;这需要对于m的k个值中的每一个，O（k）运算。QSchur多项式的半环复杂性72≺n2∈3.3. babyBABY可以计算出e1，。. .时间复杂度为O（k2）。P屋顶。通 过 迭代Pascal型递推式得到了所需的算法em （ x1 ， .. . ， xj ） = xj em−1 （ x1 ， .. . ， xj-1 ） + em（ x1，.. . ，xj-1）。 Q我们注意到，在无限制模型中，计算e1，. . . ，ek的阶为k log（k），参见Strassen（1972/73）。P屋顶（定理1.4）。设T（n）表示c_m_ti nghn−k+1，. . . ，hn.Lemma3.1和Lemma3.3表明T（n）≤ T（k）+O（k）. （ 将变量x1平方，. . ，x，k，其中需要确定是否插入hub，takesline，a，t，k，i 我们可以包括T（n）= O（k2log（n）），如所期望的.Q4. 偏序集上极大链的线性序D定义 4.1（偏序集，链，正确排序）. 设P是一个有限分次偏序集，它具有唯一的极小元素0和唯一的极大元素1. P的一个线性或非线性子集称为链。 我们用MaxChains（P）表示P中所有极大（通过包含）链的集合。 在上述假设下，MaxChains（P）中的所有链具有相同的基数m。让我们在MaxChains（P）上固定一个线性排序，并写为Q′Q以表示Q′（严格地）以这个顺序在Q之前。用于QMaxChains（P），我们表示（4.2）Qd=ef{c∈Q|Q−{c}<$Q′forsomeQ′<$Q}.因此，Q是由一个极大链Q中的那些元素组成的，这些元素可以被另一个元素替换，使得所得到的极大链在Q之前。我们称MaxChains（P）的线性序为真序，如果对于任何Q个MaxChains（P），Q之前的链都不包含Q≠：(4.3)Q′Q=Q′/Q。∈8Fomin，Grigoriev，Nogneng Schost≺∈≺REMARK 4.4. 在代数/几何组合学中，定义4.1中引入的概念传统上是用单纯复形及其壳的语言描述的;参见，例如， Wachs（2007）关于这个问题的介绍 在本文中，我们尽量避免使用这个术语，以保持论述的独立性. 下面的简短评论是为对更广泛的组合背景感兴趣的读者准备的，在后续文章中将不依赖这些评论。P的序复形是基集P上的单纯复形，其单纯形是P中的链。序复形的极大单形是极大链。Ma x C h a in s （P）的一个线性序被称为（序复形的）壳，如果对于任何Q个MaxChains（P），由单形Q ′与Q ′ Q形成的序复形的子复形（或者更精确地说，这个子复形的几何实现）在Q的余维1面的并集处与极大单形Q相交（的几何实现）。众所周知--也不难看出--任何炮击在定义4.1的意义上，顺序是适当的。更具体地说，通过（4.2）定义的子链QQ可以被看作与上述的交集的补（在Q内部）一致。余维1面对。换句话说，Q是唯一最小的脸，S不包含在子复形中的Q′Q Q′。我们使用极大链的适当排序的概念将依赖于以下关键引理。4.5. 设P是MaxChains（P）上具有适当线性序的偏序集，如定义4.1所示。对于链C和最大链Q，以下是等价的：(i) Q是包含C的最小极大链（关于MaxChains（P）上的线性序）;(ii) QCQ（回想一下，Q是由公式4.2定义的）。PROF.这是一个很好的例子。 Letc∈Q。Ifc∈/C，则C包含在某个极大链Q′Q中（见（4.2）），矛盾（一）。Schur多项式的半环复杂性9||Q在相反的方向上，假设QCQ。设存在一个包含C的极大链Q′<$Q。然后Q′<$Q′，与公式4.3相矛盾。Q定义4.6（多链，支持）。一个“弱增”序列M={p1≤··· ≤pm}P称为大小为m的多链;我们写M = m。 出现在M中的P的元素（具有非零重数）形成M的支撑，记为supp（M）。多链的支持是一个链。让我们将形式变量zc与每个元素c∈P相关联。对于P中的M个元素Qt，我们不能通过ZM来计算，响应单项：zM=c∈M zc.4.7. blog 设P是一个偏序集，它的极大链具有一个适当的线性序，见定义4.1。（或者：假设给出了P的序复形的一个壳。） 然后，P中大小为m的多链的生成函数由下式给出：Σ（4.8）多链M|M|=mΣzM=Q∈MaxChains（P）∗zhm−|Q|（（zc）c∈Q），其中Q由式（4.2）定义。P屋顶。根据引理4.5，P中的链的集合分裂成形式为[Q，Q]的（偏序集理论）区间的不交并通过对多重链M的支集进行分类，并将这一观察应用于C= supp（M），我们得到了恒等式：Σ多链M|M|=mΣzM=Q∈MaxChains（P）ΣQsupp（M）Q|M|=mzM，这意味着（4.8）。Q在第5节中，我们将把舒尔多项式与上述构造的一种特殊情况联系起来，这种特殊情况涉及下面定义4.9中描述的一类（可壳）偏序集Ph，k 这些偏序集10Fomin，Grigoriev，Nogneng Schost≤C1HH由于它们在表示论和经典舒伯特微积分中的作用，在代数组合学中得到了广泛的研究。特别是，Ph，k描述了格拉斯曼流形Gr（h，k）中Schubert细胞的附着。D定义4.9（偏序集Ph，k）. 设h和k为正整数，其中h为k.我们用Ph，k表示偏序集，其元素是高度为h的列向量（或简单列）c，其条目位于集合{1，. . . ，k}，并严格地向下增加：1000万美元（4.10）c =。Ch∈Zh， 1 ≤c1 <··· 0和λ n> k意味着s λ（x1，. . . ，xk）= 0。我们使用符号n=|λ|=λ1+···+λ表示分区λ的大小。定义5.1（表格，Schur函数）。形状为λ = λ的半标准杨氏表T|不|是一个整数数组T=（t i，j|1≤i≤λ i，1≤j≤ λ i）满足ti，j···>λ′ 这些数据项列在数据项中，其中appearaspartsofλ′。在这篇文章中，λ′，. . . ，λ′都是不同的-1s在λ的杨氏图中输入柱的高度我们表示为λ=（λ1≥···≥λ），则将其转换为λ′=（λ′，. . . ，λλ′）。对于图1，通过对每个高度的列进行检查，并删除其余的列，可以从λ中删除我们现在可以通过垂直切割将杨氏图λ分解为s个大小为h×（ λh− λh+1）的矩形，其中h在λ16Fomin，Grigoriev，Nogneng SchostJ××563λλ′的部分的集合（等价地，该集合是λ的集合的集合）。为了简化符号以便将来的论证，我们表示hj=λ′ andmj=λh−λh+1−1，sothatλgetsdi sectedi noJ J大小为hj×（ mj+1）的矩形，其中j=1，.. . ，s.实施例5.4. 设λ=（6，6，4，1，1），λ= 5.然后λ′=（ 5，3，3，2，2），λ′=（5，3，2），λ=（3，3，2，1，1），s=3.形状λ可以通过垂直切割分成三个大小分别为5×1、3× 3和2×2的矩形。在本例中，我们有h1= 5，h2 = 3，h3 = 2，m1 = 0，m2 = 2，m3 = 1。定义5.5（表格修剪）。设T是λ形的半标准表。T的剪枝是半标准表T通过对每个高度的最高列进行筛选（并移除该高度的所有列，这是它的一部分）。 我们不可能在一起，。 . . ，作为T恤的一个专栏，左而右环行（这些列的高度为h1，. . . ，hs）。我们不会通过重新移动hj −h j +1 bottom m e n t r i es 来 删 除 h j+1bt a i n e dhighhj+1bt a i n e d ec o lum nned hj。我们进一步用T1表示。. . ，T是半标准的矩形h1m1，. . . 通过定义5.3中描述的垂直切割来分解T，然后从每个结果表格中移除最右边的列，从而获得。(Ifmj=0，则Tj为空）。因此，通过将矩形表格T j与修剪的列交错来获得T：|的1|T2|一个2|···|Ts|as]。实施例5.6. 继续例5.4，设T=Σ Σ1 1 2 2 2 42 2 3 3 3 5四五六。5Σ Σ1 2 4˜2 3 5Σ1ΣΣ Σ Σ Σ2 1 2 22则T=4 656，T1= π，a1=4 ，T2=562 3 ，a2=5 63 ，T3=[]，6a 3=[4]。♦♦关于Schur多项式7≤≤˜.考虑给定形状λ的半标准表集T，其中s≤k，且具有给定的形式T∈[a1|···|as]。一旦T和λ固定，每个表Tj，对于1js，可以独立于其他选择，只要它满足以下限制：◦ Tj是一个hj×mj的矩形半标准表，元素≤k，因此它可以看作是偏序集Phj，k中一个大小为mj的重链;◦ Tj中的每一列a（即，这条多链的每个元素）是有限的，这条方程是a<$j−1≤a≤aj，其中p是Phj，k中的偏序。(We设置a<$0= 0=Σ Σ1.按照惯例，ℓ对于j=1是冗余的）。这给出了一组考虑的表格和在偏序集Phj，k中的多链集合的笛卡尔积：半标准T型台形状为λ的矩阵，元素≤k，其中hprni gT=[a1|···|as]←→ Ysj=1多链多线程尺寸mj在Phj中，k[a<$j−1，aj]如果yi ngmulti chai ns在Phj，k[a<$j−1，aj]中有一个矩形的ux，则通过母函数，我们得到如下结果.5.7. 用上面的符号，我们有(5.8)S（x，. . .得双曲余切值.Ys）=xTΣ xTj，哪里λ1kTj=1Tj◦ T=[a1|···|运行一个具有≤ k个条目的、可访问的数据集;◦每个Tj在矩形形状的半标准表格上运行hj× mj是对Phj，k[a<$j−1，aj]中的一个m u lt i c h a in的一个代数。Σ根据引理4.7和引理4.19，xTjap-公式（4.8）中的pearing可以用公式（4.8）计算：18Fomin，Grigoriev，Nogneng Schost∈≤Q∗联系我们∈LEMMA5.9. 设a，b，P，h，k为两列，使得a，b. 然后（5.10）Σ Σ∗xT=xhn（xc1，.. . ，xcN），m −|Q|T Q哪里◦ T在半标准的矩形H× M表格上运行其列在Ph，k[a，b]中形成多重链;◦ Q=[c1|···|c[N]在Ph，k[a，b]中的最大似然性上的运行;◦ Q由公式4.2给出。为了读者注4.17。对于每一对连续列cj和cj+1，我们有cj+1=cj+eij，i j1，. . .，h，其中ei表示其第i个分量等于1，其他都等于0。链/表Q由列cj的子集构成，其中ij−1>ij，而且cj−1+eijPh，k（因此用cj−1+eij代替cj将Q转换为字典上较小的极大链）。第五章. 十一岁 Leth=2，k=5，a=100，b=101，cf. Exam p le4.1 3.则（5.10）变为s（m，m）（x1，. . 、.、x5）=hm（x1x2，x1x3，x2x3，x2x4，x3x4，x3x5，x4x5）+x2x5hm−1（x1x2，x1x3，x2x3，x2x4，x2x5，x3x5，x4x5）+x1x4hm−1（x1x2，x1x3，x1x4，x2x4，x3x4，x3x5，x4x5）+x1x4 ·x2x5hm−2（x1x2，x1x3，x1x4，x2x4，x2x5，x3x5，x4x5）+ x1x5h m−1（x1x2，x1x3，x1x4，x1x5，x2x5，x3x5，x4x5）。 ♦6.主要定理