On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Abstract
We introduce a novel take on sum-of-squares that is able to reason with complex numbers and still make use of polynomial inequalities. This proof system might be of independent interest since it allows to represent multivalued domains both with Boolean and Fourier encoding. We show degree and size lower bounds in this system for a natural generalization of knapsack: the vanishing sums of roots of unity. These lower bounds naturally apply to polynomial calculus as-well.
Full text
comput. complex. (2023) 32:12 c The Author(s) 2023 https://doi.org/10.1007/s00037-023-00242-z computational complexity ON VANISHING SUMS OF ROOTS OF UNITY IN POLYNOMIAL CALCULUS AND SUM-OF-SQUARES Ilario Bonacina , Nicola Galesi , and Massimo Lauria Abstract. We introduce a novel take on sum-of-squares that is able to reason with complex numbers and still make use of polynomial inequalities. This proof system might be of independent interest since it allows to represent multivalued domains both with Boolean and Fourier encoding. We show degree and size lower bounds in this system for a natural generalization of knapsack: the vanishing sums of roots of unity. These lower bounds naturally apply to polynomial calculus as-well. Keywords. polynomial calculus, sum-of-squares, roots of unity, knapsack Subject classification. 03F20, 68T15. 1. Introduction Problems in combinatorics, constraint satisfaction, arithmetic circuit design, or algebra, can be formalized in a variety of languages. The popular propositional logic approach, based on the Conflict- Driven-Clause-Learning SAT solvers (Bayardo Jr & Schrag 1997; Marques-Silva & Sakallah 1999;Moskewicz et al. 2001), fails to exploit the algebraic structure of the problem and often resorts to inefficient brute-force. Maintaining the algebraic representation allows to use Hilbert’s Nullstellensatz, Gr¨obner basis computation, or semidefinite 0123456789().: V,-vol Birkh¨auser
12 Page 2 of 45 Bonacina, Galesi & Lauria cc programming (Cox et al. 2007;Lasserre 2001;Parrilo 2003). These tools have been successful in practice, for instance to solve κcoloring (De Loera et al. 2009,2011,2015) and to verify arithmetic multiplier circuits (Kaufmann & Biere 2020;Kaufmann et al. 2019,2020). CSP problems over domains of size κ,e.g. κ-coloring,can be naturally represented using either the Fourier encoding or the Boolean encoding. The Fourier encoding represents values via complex variables zsubjected to the constraint zκ= 1 and hence such that z∈{1,ζ,ζ2,...,ζκ−1}, where ζis a primitive κth root of unity. The Boolean encoding uses {0,1}-valued indicator variables x1,...,x κ, equipped with the additional constraint x1+···+xκ=1. A good encoding is essential to leverage the algebraic structure of a problem: even simple variations may give significant speedups both in theory and in practice (Kaufmann et al. 2022;de Rezende et al. 2021). In this paper, we show that algorithms leveraging Hilbert’s Nullstellensatz or Gr¨obner basis computations cannot prove efficiently the unsatisfiability of some natural sets of polynomials equations over the Fourier variables. We focus on polynomial calculus and sum-of-squares proof systems. Polynomial calculus is a well-studied proof system that captures Hilbert’s Nullstellensatz and Gr¨obner basis computations, and certifies the unsatisfiability of sets of polynomial equations (Buss et al. 2001). Sum-of-squares certifies the unsatisfiability of sets of polynomial equations and inequalities over R. A sum-of- squares SoSRrefutation of the set of constraints {p=0: p∈ P}∪{h≥0: h∈H}is an identity of the form −1= p∈P qp·p+ h∈H qh·h+ s∈S s2, where the s, qp,q hare polynomials over Rand moreover the qhsare sums of squared polynomials. Sum-of-squares p-simulates polynomial calculus over the reals on {0,1}-valued and {±1}-valued variables (Berkholz 2018;Sokolov 2020).
cc On vanishing sums of roots of unity Page 3 of 45 12 In this paper, we introduce a generalization of sum-of-squares with polynomials over C,SoSC(see Section 2 for the formal definition). Since Cis not an ordered field, this generalization of sum-of-squares to Ccan only be used to certify the unsatisfiability of sets of polynomial equations. For sets of polynomial equations over R, and in the presence of Boolean variables, SoSCcoincides with the usual notion of sum-of-squares over R, but the generalization is necessary to deal with Fourier variables or to reason about polynomials with complex coefficients. As in the real case SoSC p-simulates PCC,seeSection 2 for more details. Finding deductions in PC/SoS may be hard, and in general there are important proxy measures to estimate such hardness: the maximum degree of the polynomials involved in the deductions, and the size of the proof measured as number of monomials involved in the whole proof when polynomials are written explicitly as sums of monomials. The degree is a very rough measure of the proof search space, and the size is a lower bound on the time required to produce the proof. Studying size and degree complexity in algebraic systems over Fourier encodings is particularly relevant to understand how to leverage to proof complexity techniques such as the Smolensky’s method in circuit complexity. Smolensky (1987) proved exponential lower bounds to compute the MODpfunction by bounded-depth circuits using the unbounded gates in {∧,∨,MODq}, for pand q relatively prime, employing a reduction to low-degree polynomials over GF(q) approximating such circuits. In proof complexity, it is a long-standing problem to obtain lower bounds for proof systems over bounded-depth formulas with modular gates. Non-trivial degree lower bounds for Fourier encodings were first obtained for the Nullstellensatz proof system and PC by Grigoriev (1998)andBuss et al. (2001) for the Tseitin principle over p-valued variables and the MODpprinciples. For PC/SoSRover Boolean variables, we know degree and size lower bounds for the encodings of several computational problems, see for instance (Atserias & Ochremiak 2018;Grigoriev 2001; Potechin 2020;Schoenebeck 2008;Tulsiani 2009). Over Boolean variables a strong degree lower bound implies immediately a size
12 Page 4 of 45 Bonacina, Galesi & Lauria cc lower bounds thanks to degree-size trade-offs: if a set of polynomials over Boolean variables has no refutation of degree at most D, then it has no refutation containing less than 2Ω( (D−d)2 n)monomials (Atserias & Hakoniemi 2019;Impagliazzo et al. 1999). No such result exists for Fourier variables. Indeed, Tseitin contradictions over {0,1}-valued variables require an exponential number of monomials to be refuted in PC, while PC can refute them with a linear number of monomials if the encoding uses {±1}- valued variables (Buss et al. 2001). To the best of our knowledge, the first size lower bounds in PC/SoSRfor polynomials with {±1}-valued variables are proved by Sokolov (2020) for the pigeonhole principle and random 11- CNFs. Moreover, (Sokolov 2020) gives a technique to turn strong degree lower bounds to strong size lower bounds via the composition with some carefully constructed gadgets. We extend this latter approach to get size lower bound under the Fourier encoding of κ-valued variables, and we apply it to a generalization of the knapsack problem. The classical knapsack problem corresponds to the set of polynomials (1.1) n i=1 cixi−r, x 2 1−x1,...,x 2 n−xn, where r, c1,...,c n∈C. knapsack requires a linear degree to be refuted in PC (Impagliazzo et al. 1999, Theorem 5.1) regardless of the coefficients r, c1,...,c n∈R. Grigoriev (2001) showed that, when all the cisare1andr∈R, knapsack requires degree at least min{2min{r, n −r} +3,n} to be refuted in SoSR. Size lower bounds follow via the respective size-degree tradeoffs. 1.1. Sums of roots of unity. We consider the problem of when asumofnvariables with values in the κth roots of unity can be
cc On vanishing sums of roots of unity Page 5 of 45 12 equal to some value r∈C, that is the satisfiability of (1.2) SRUκ,r n:= i∈[n] zi−r, zκ 1−1,...,zκ n−1. Linear relations of the form n i=1 ciζi=0,whereciare complex numbers and ζiare roots of unity, arise naturally in several contexts (Conway & Jones 1976), and have been extensively studied in the literature, for instance (Dvornicich & Zannier 2002,2000). When κdivides n,SRUκ,0 nis satisfiable, because the κth roots of unity sum to zero. For κthat is a power of a prime number p this is indeed the only possibility (Proposition 2.2 in Section 2). Lam & Leung (2000) proved a complete characterization of when SRUκ,0 nis satisfiable. In particular, when κis not a power of a prime thereexistsan0(κ) s.t. for every n≥n0(κ) the set of polynomials SRUκ,0 nis satisfiable. 1.2. Our results. In this paper, we show the hardness to certify in PC and SoSCthe unsatisfiability of SRUκ,0 nwhen κis a prime and does not divide n. A preliminary version of this work appeared in the proceedings of MFCS’22 (Bonacina et al. 2022). Our main results regarding PC/SoSCinformally say that SoSC and PCCcannot capture divisibility arguments. A linear degree lower bound for SRU2,0 nfollows immediately, via a linear transformation, from the known degree lower bound for knapsack in SoS,sinceGrigoriev (2001) lower bound extends to SoSC. In this paper, we generalize this result proving degree and size lower bounds in SoSCfor SRUκ,r nfor κan odd prime. Theorem 1.3 (Degree lower bound for SRUκ,r n). Let n, d ∈N,κ be a prime, r∈C.Letrbe written as r1+ζr2,wherer1,r 2∈R and ζis some κth primitive root of unity. If κd ≤min{r1+r2+(κ−1)n+κ, n −r1−r2+κ}, then there are no SoSC-refutations of SRUκ,r nof degree at most d. In particular, SRUκ,0 nrequires refutations of degree Ωn κin SoSC. From the set of polynomials in SRU2,r n, we can easily infer the polynomials in SRUκ,0 n, via a linear transformation and a weakening. This is enough to prove degree lower bounds for SRUκ,0 nin
12 Page 6 of 45 Bonacina, Galesi & Lauria cc PCCsince Impagliazzo et al. (1999, Theorem 5.1) proved a linear degree lower bound for knapsack and therefore SRU2,r nfor any r (see Section 3). This is not the case for SoSC:SRU2,r nis refutable in small degree and size in SoSCif r∈C\R,seeExample 2.4.In other words, in SoSC, unlike the case of PC, it is not possible to reduce the hardness of SRUκ,0 n, for κ>2toknapsack. To prove the degree lower bound in SoSCfor SRUκ,r n(Theorem 1.3), first we construct a candidate pseudo-expectation based on the symmetries of SRUκ,r n. Then, we prove its correctness, following a generalization to SoSCof the approach by Blekherman et al. (2016)andBlekherman & Riener (2020) as presented in (Lee et al. 2016, Theorem B.11). We also prove a size lower bound for SRUκ,0 nin SoSC. The lift of degree lower bounds to size lower bounds on κ-valued Fourier variables generalizes the lifting approach due to Sokolov (2020)on real valued polynomials and {±1}-variables. Theorem 1.4 (Size lower bound for SRUκ,0 n). Let κbe a prime and n∈N,ifnκthen the set of polynomials SRUκ,0 nhas no refutation in SoSCwithin monomial size 2o(n). For κ=2,Theorem 1.4 follows easily from Sokolov’s (2020) techniques and Grigoriev’s (2001) degree lower bound for knapsack. For κ>2, Theorem 1.4 requires some non-trivial generalization of the lifting technique from (Sokolov 2020). This generalization is Theorem 4.10 in Section 4. Theorem 1.3 and Theorem 1.4 also hold for PCC,sinceSoSC simulates PCC. 1.3. Related works. Recently and independently of us, Impagliazzo et al. (2022) generalized Sokolov’s (2020) approach for proving size and degree lower bounds in PC to the case of PCC equipped with certain limited extension axioms and where variables are taking values in the κth roots of unity. They prove lower bounds in PCCwith limited extensions for unsatisfiable systems of random linear equations lifted by certain hardness functions.
cc On vanishing sums of roots of unity Page 7 of 45 12 Our results on the vanishing root principle SRUκ,r nare incomparable with the results from (Impagliazzo et al. 2022). First, SRUκ,r n is a generalization of the knapsack problem and, to our knowledge, not related or reducible in PCCto the case of random linear equations, even adding to PCCthe extra limited extension axioms used in (Impagliazzo et al. 2022). Furthermore, one of the main results in our work is the degree lower bound for SRUκ,0 nin SoSC, while the same degree lower bound for PCCfollows essentially as a corollary of known results. SoSCand PCCproofs deal with arbitrary polynomial systems rather than simply encodings of CNF formulas. In the literature, several algebraic proof systems extending PC were considered, among these the Ideal Proof System (IPS)from(Grochow & Pitassi 2018), the Cone Proof System (CPS)from(Alekseev et al. 2020), a version of PC working with bounded k-conjunctions (Galesi & Lauria 2010), and a version of PC working with depth-dalgebraic circuits (Grigoriev & Hirsch 2003;Impagliazzo et al. 2020). IPS and CPS are, at least on variables taking Boolean values, strictly stronger than PC and SoS (Grochow & Pitassi (2018)). Interestingly to this work, the complexity of proofs for IPS and CPS was studied by using a particular subset-sum principle, the Binary Value Principle (BVP) expressing the fact that natural numbers written in binary cannot be negative. Moving from a technique of Forbes et al. (2021), Alekseev et al. (2020) proved that the BVP is conditionally hard to refute in IPS modulo the Shub-Smale conjecture on the hardness of computing factorials. Alekseev et al. (2020) prove lower bounds on the magnitude of the coefficients and this is completely different from the techniques developed in this article. Despite being seemingly hard for a strong proof system like IPS, the binary value principle is easy to refute in SoSC, contrary to other subset-sum principles. Hence, to the best of our knowledge, no immediate relation can be drawn between our results and the previous results on BVP. 1.4. Structure of the paper. In the next section, we give the necessary preliminaries on roots of unity and the formal definition of SoSC. The proof of the main degree lower bound (Theorem 1.3) is in Section 3.InSection 4, we lift degree lower bounds to size
12 Page 8 of 45 Bonacina, Galesi & Lauria cc lower bounds for sets of polynomials over the roots of unity and we prove Theorem 1.4. The main technical ingredient of this proof is Theorem 4.8. Its proof is deferred to Section 5. 2. Preliminaries Given n, k ∈N,let[n]:={1,...,n},andifkdivides nwe write k|n.Fora∈Rand b∈N,leta 0:= 1 and a b:= a(a−1)...(a−b+1) b! for b≥1. Boldface symbols indicate vectors, and xdenotes a vector with nelements (x1,...,x n). We usually denote with xBoolean variables, with zκ-valued Fourier variables and with ygeneric variables or auxiliary variables. Given a set of polynomials P⊆C[y], Pdenotes the ideal generated by Pin C[y]. 2.1. Vanishing sums of roots of unity. For κ∈N,aκth root of unity is a root of the polynomial Xκ−1. All the roots of unity except 1 are also roots of the polynomial 1+X+···+Xκ−1, indeed Xκ−1=(X−1) ·(1 + X+···+Xκ−1). A κth root of unity ζis called primitive if ζt= 1 for all 1 ≤t<κ. If this is the case, the κth roots of unity are indeed 1,ζ,ζ2,...,ζκ−1. Some of the results of this paper hold for roots of unity in generic fields but, for sake of clarity, we only consider roots of unity in C. Notice that the complex conjugate of ζtis ζκ−t. For concreteness, we denote as ζ a specific primitive κth root of unity, for instance e2πi/κ,andasΩ κ the set {1,ζ,ζ2,...,ζκ−1}. We often denote as ωa generic element in Ωκ. The κth cyclotomic polynomial is the unique irreducible univariate polynomial in Z[X] that divides Xκ−1 and does not divides Xκ−1 for any κ∈[κ−1]. The κth cyclotomic polynomial is denoted as Φκ(X). If κis prime, then Φκ(X)=1+X+···+Xκ−1. Proposition 2.1. Let κbe a prime number. The set of polynomials SRUκ,0 nis satisfiable over Cif and only if κ|n.
cc On vanishing sums of roots of unity Page 9 of 45 12 Proof. Let ζbe a primitive κth root of unity. That is ζis a root of the κth cyclotomic polynomial Φκ(X). If κ|n,sayn=κ·a, then a solution is trivial to construct: 1+···+1 a +ζ+···+ζ a +···+ζκ−1+···+ζκ−1 a =aΦκ(ζ)=0. Suppose now the set of polynomials SRUκ,0 nis satisfiable over C.Lety1,...,y nbe a solution. For j=0,...,κ−1, let αj=|{∈[n]: y=ζj}|. From the definition, it follows immediately that κ−1 j=0 αj=nand that for some j>0, αj=0. That is, ζis a root of the polynomial p(X)=κ−1 j=0 αjXj, but then ζis also a root of p(X)−ακ−1Φκ(X)=κ−2 j=0 (αj−ακ−1)Xj. This polynomial has degree strictly less than κ−1 and hence it must be identically 0, i.e. α0=α1=···=ακ−1.Since κ−1 j=0 αj=n this implies κ|n. If κ=pmfor some prime pand integer m, then the κth cyclotomic polynomial is Φκ(X)=1+Xpm−1+X2pm−1+···+X(p−1)pm−1. Using this fact, it is immediate to generalize the proof of Proposition 2.1 to κpower of a prime. Proposition 2.2. Let κbeapowerofaprimenumberp.The set of polynomials SRUκ,0 nis satisfiable over Cif and only if p|n. 2.2. Proof systems. The proof systems of interest in this work are polynomial calculus and a variant of Sum-of-Squares designed to deal with complex numbers and complex roots of unity. 2.2.1. Polynomial calculus (PC)overC.Given a set of polynomials P⊂C[y]andq∈C[y], a refutation of Pin polynomial calculus over C, denoted as PCC, is a sequence of polynomials p1,...,p sin C[y] such that ps=1,andeachpiis either 1. a polynomial from the set P;
12 Page 16 of 45 Bonacina, Galesi & Lauria cc ◦˜ E(1) = 1, ◦˜ E(mp) = 0, for every p∈Pand mmonomial such that deg(p)+deg(m)≤d, ◦˜ E(s·s∗)∈R≥0, for every polynomial ss.t. deg(s·s∗)≤d. It is immediate to see that the existence of a degree-dpseudo- expectation for a set of polynomials Pimplies that Pcannot be refuted in degree-dSoSC. It turns out it is easier to construct a pseudo-expectation for a Boolean encoding of SRUκ,r n. This Boolean encoding is bool-SRUκ,r n. First, we show (Proposition 3.6) that the degree needed to refute SRUκ,r nin PC and SoSCis at least the degree needed to refute bool-SRUκ,r n. Secondly, we construct a pseudo-expectation for bool-SRUκ,r n and this implies a SoSClower bound both for bool-SRUκ,r nand SRUκ,r n. After imposing some natural symmetry assumption there is only one candidate pseudo-expectation ˜ Efor bool-SRUκ,r nsatisfying the first two properties of the definition of pseudo-expectation (Theorem 3.10). To show that the candidate pseudo-expectation satisfies also the third property is more involved but it follows some standard structure of the arguments used to construct pseudoexpectations in the context of SoSR. 3.2. A Boolean encoding of SRUκ,r n.We consider a Boolean encoding of the sums of roots of unity. This is the set bool-SRUκ,r n consisting of the following polynomials for every i∈[n]andj∈[κ] (3.5) i∈[n] j∈[κ] ζj−1xij−r, x2 ij −xij, j∈[κ] xij −1. The set of polynomials SRUκ,r nuses variables taking values in Ωκ, while the encoding in eq. (3.5) uses indicator variables to select the appropriate power of ζ.ToproveTheorem 1.3, it is enough to prove the degree lower bound for bool-SRUκ,r n.
cc On vanishing sums of roots of unity Page 17 of 45 12 Proposition 3.6. The degree needed to refute SRUκ,r nin PCC (resp. SoSC) is at least the degree needed to refute bool-SRUκ,r n in PCC(resp. SoSC). Proof. (sketch) Take a refutation of SRUκ,r nof degree D. Necessarily κ≤D. We want to argue that bool-SRUκ,r nhas a refutation of degree D, as well. To avoid ambiguity, we consider SRUκ,r ndefined on variables zand bool-SRUκ,r non variables x. We apply the linear substitution zi→ j∈[κ] ζj−1xij, to the degree Drefutation of SRUκ,r n. We get a refutation of degree Dof the resulting set of polynomials. It is sufficient to show we can infer these polynomials in low degree PCCfrom the axioms of bool-SRUκ,r n. Indeed, from bool-SRUκ,r n, we can easily infer xijxij= 0 for each i∈[n]andj=j∈[κ]; hence, we have j∈[κ] ζj−1xijκ=PC j∈[κ] ζ(j−1)kxκ ij =PC j∈[κ] xij =PC 1, where with p=PC qwe mean that p−qis derivable in PC.The whole derivation of bool-SRUκ,r nhas degree D. 3.3. Notation. Consider fixed r∈Cand r1,r 2∈Rsuch that r=r1+ζr2.Letejbe the vector of dimension κwith the jth entry 1 and all other entries 0. For j∈[κ], let x(j)=(x1j,...,x nj). That is, bool-SRUκ,r nis a set of polynomials in C[x(1),...,x(κ)]. Given a tuple of sets I=(I1,...,I κ), where Ij⊆[n], let |I|= (|I1|,...,|Iκ|)andletXI=j∈[κ]i∈Ijxij With ·, we always denote the 1-norm. So x(j)denotes the polynomial i∈[n]xij. Given a variable Xand t∈N,letX tbe the univariate polynomial X(X−1) ···(X−t+1) t!. Let Bbe the ideal x2 ij −xij,x ijxij:i∈[n],j,j ∈[κ],j=j. Given polynomials p, q ∈C[x(1),...,x(κ)], we use the notation p≡qto denote that p−q∈B.
12 Page 18 of 45 Bonacina, Galesi & Lauria cc Lemma 3.7. Given a vector of variables y=(y1,...,y m),wehave that y t≡ I⊆[n] |I|=t YI. Proof. To prove the equality proceed by induction on t.The base case t= 1 is immediate: y 1=y=i∈[n]yi.Fort>1, i∈[n] yi I⊆[n] |I|=t−1 YI≡t I⊆[n] |I|=t YI+(t−1) I⊆[n] |I|=t−1 YI. That is, using the inductive hypothesis, yy t−1≡t I⊆[n] |I|=t YI+(t−1)y t−1, and therefore I⊆[n] |I|=t YI≡y−t+1 ty t−1=y t. 3.4. The candidate pseudo-expectation. A potential satisfying assignment of bool-SRUκ,r nconsists of γ=(γ1,...,γ κ), the allocation of the nroots of unity in the directions ζ0,...,ζκ−1.The sum j∈[κ]ζj−1γjmust be equal to the target value r=r1+ζr2, so we spread uniformly n−r1−r2among the γjs, and then add r1and r2to γ1and γ2respectively. This intuition leads to the definitions (3.8) ⎧ ⎪ ⎨ ⎪ ⎩ γ1=n−r1−r2 κ+r1, γ2=n−r1−r2 κ+r2, γj=n−r1−r2 κfor j≥3. Observe that γ=n. For ease of notation let ˆγ=n−r1−r2 κ
cc On vanishing sums of roots of unity Page 19 of 45 12 and r3=···=rκ= 0. Therefore, we can write γj=ˆγ+rj for each j∈[κ]. Given t=(t1,...,t κ)∈[n]κ,andvariablesv=(v1,...,v κ), let Stbe the polynomial in the variables vgiven by St(v)=(n−t)! n! j∈[κ] tj!· j∈[κ]vj tj. Notice that for every j∈[κ], St+ej(v)=St(v)·vj−tj n−t. To define the candidate pseudo-expectation ˜ E,bylinearity,it is enough to define it on monomials. For a monomial of the form XIwe define it as ˜ E(XI)=S|I|(γ)ifthesetsinIare pair-wise disjoint, 0 otherwise. For a general monomial m, possibly not multilinear, we define ˜ E(m) as ˜ E(XI)whereXIis the unique multilinear monomial equivalent to mmodulo B, that is such that m≡XI. We show that, for the range of parameters of Theorem 1.3,˜ Eis a pseudo-expectation for bool-Knκ,r n. Lemma 3.9. If p≡qthen ˜ E(p)=˜ E(q). Proof. By definition p≡qmeans there exists a polynomial s∈Bsuch that p=q+s. By construction, ˜ Emaps to 0 every polynomial in B, in particular ˜ E(s) = 0. By the linearity of ˜ E, then ˜ E(p)=˜ E(q). The definition of ˜ Eis to enforce that ˜ E(pq) = 0 for every p∈ bool-SRUκ,r n. Theorem 3.10. For every I=(I1,...,I κ)with Ij⊆[n]and i∈[n], and every p∈bool-SRUκ,r n,˜ E(XIp)=0.
12 Page 20 of 45 Bonacina, Galesi & Lauria cc Proof. The fact that ˜ E(XI(x2 ij −xij)) = 0 is immediate by the definition of ˜ E. If the sets Ijare not pair-wise disjoint then, by definition, the pseudo-expectation is already 0, so it is enough to consider the case when the Ijs are pair-wise disjoint. Let t=(t1,...,t κ)where tj=|Ij|. To show that ˜ E(XI( j∈[κ] xij −1)) = 0 we have two cases. Case 1.Ifi∈j∈[κ]Ij,then ˜ E(XI( j∈[κ] xij −1)) = St(γ)−St(γ)=0. Case 2.Ifi/∈j∈[κ]Ij,then ˜ E(XI( j∈[κ] xij −1)) = j∈[κ] St+ej(γ)−St(γ) =St(γ)·⎛ ⎝ j∈[κ] γj−tj n−t−1⎞ ⎠ =St(γ)·γ−t n−t−1 =0, since γ=n. We now prove that (3.11) ˜ E(XI( j∈[κ] ζj−1x(j)−r1−ζr2)) = 0. Let Tbe the LHS of eq. (3.11). The following chain of equalities gives T=0. T=St(γ) j∈[κ] ζj−1tj+ i/∈j∈[κ]Ij ( j∈[κ] ζj−1St+ej(γ)) −(r1+ζr2)St(γ)
cc On vanishing sums of roots of unity Page 21 of 45 12 =St(γ) j∈[κ] ζj−1tj+(n−t) j∈[κ] ζj−1St+ej(γ)−(r1+ζr2)St(γ) =St(γ) j∈[κ] ζj−1tj+St(γ) j∈[κ] ζj−1(γj−tj)−(r1+ζr2)St(γ) =St(γ)·⎛ ⎝ j∈[κ] ζj−1tj+ j∈[κ] ζj−1(γj−tj)−(r1+ζr2)⎞ ⎠ =St(γ)·⎛ ⎝ j∈[κ] ζj−1γj−(r1+ζr2)⎞ ⎠ =St(γ)·⎛ ⎝ j∈[κ] ζj−1ˆγ+ j∈[κ] ζj−1rj−(r1+ζr2)⎞ ⎠ =0, since γj=ˆγ+rj,rj= 0 for j>2, and j∈[k]ζj−1=0. We now use Blekherman’s approach (Lee et al. 2016, Appendix B,C) to prove that, for a suitable range of parameters, ˜ E(p·p∗)∈ R≥0. First we introduce some notation on the symmetric group and how it acts on polynomials. Let Snbe the group of permutations over nelements. For a set J⊆[n] and a permutation σ∈Sn,let σJ ={σ(j): j∈J}. Consider variables y=(y1,...,y n). For a set J⊆[n], let YJ=j∈Jyj. Given a polynomial p∈C[y], that is p(y)=J⊆[n]pJYJ,withpJ∈C,let σp(y)= J pJYσJ. The symmetrization of pis the polynomial Sym(p)∈C[y]givenby Sym(p)(y)= 1 n! σ∈Sn σp(y). Lee et al. (2016, Theorem B.11), following Blekherman, prove a decomposition for Sym(p2)(y) analog as the one in the following theorem.
12 Page 22 of 45 Bonacina, Galesi & Lauria cc Theorem 3.12 (adaptation of Lee et al. 2016, Theorem B.11). Given Boolean variables y=(y1,...,y n)and p∈C[y]with degree at most d≤n/2, Sym(p·p∗)(y)≡ d j=0 pd−j(y)·p∗ d−j(y) j−1 i=0 (y−i)(n−y−i), where pd−jis a univariate polynomial with coefficients in C,p∗ d−j is the formal conjugate of pd−jand the degree of both polynomials is at most (d−j)/2. Remark. Theorem B.11 in (Lee et al. 2016) is proved for real polynomials and a crucial notion in its proof is the inner product ·,· on the space of degree-thomogenous multilinear polynomials: for p=mpmmand q=mqmm,p, qis defined as mpmqm. We can likewise define a Hermitian inner product ·,· on the space of degree-thomogenous multilinear polynomials with complex coefficients as p, q=mpmq∗ m. With this change, the proof of Theorem B.11 in (Lee et al. 2016) generalizes to complex polynomials and gives Theorem 3.12. We want to use Theorem 3.12 andtodosoweextendthe polynomial S|I|(v) in the following way: given p=IαIXIwith αI∈C,let S(p)(v)= I αIS|I|(v). The polynomial S(p) is useful since it is both connected to ˜ Eand to Sym(p). The connection with ˜ Eis trivial: ˜ E(p)=S(p)(γ). The connection with Sym(p) is the content of the following theorem. Theorem 3.13. Given p∈C[x(1),...,x(κ)], S(p)(r1+y,r 2+y,r 3+y,...,r κ+y)≡Sym(pρ)(y), where ρis the substitution given by ρ(xij)=yi+rj n where r3=···=rκ=0.
cc On vanishing sums of roots of unity Page 23 of 45 12 Proof. Lemma 3.7 implies that (3.14) j∈[κ]x(j) tj≡ I=(I1,...,Iκ),I j⊆[n] |Ij|=tj XI. For a vector of sets I=(I1,...,I κ) and a permutation σ∈Sn, let σI=(σI1,...,σI κ). Given a polynomial p=IpIXIin C[x(1),...,x(κ)]andapermutationσ∈Snlet σp = I pIXσI. Now, for any polynomial p∈C[x(1),...,x(κ)] (3.15) 1 n! σ∈Sn σp ≡S(p)(x(1),...,x(κ)). To see this equivalence, by linearity, it is enough to show that for every Iwith Ij⊆[n] 1 n! σ∈Sn XσI≡S(XI)(x(1),...,x(κ)). IfthesetsinIare not pair-wise disjoint, it is immediate to see that 1 n!σ∈SnXσI∈B, and therefore 1 n!σ∈SnXσI≡0. Suppose then I=(I1,...,I κ)andthesetsIjare pair-wise disjoint. Let tj=|Ij|,then 1 n! σ∈Sn XσI=(n−t)! j∈[κ]tj! n!·S=(S1,...,Sκ) pair-wise disj. |Sj|=tj XS ≡(n−t)! j∈[κ]tj! n!·S=(S1,...,Sκ) |Sj|=tj XS ≡(n−t)! n!j∈[κ]tj!·j∈[κ]x(j) tj =S(XI)(x(1),...,x(κ)),(3.16) where the equality in eq. (3.16) follows from eq. (3.14). To conclude, it is then enough to observe that the statement we want to prove follows from eq. (3.15) restricting both sides of the equality by ρ. To prove this, we use that σXIρ=σ(XIρ).
12 Page 24 of 45 Bonacina, Galesi & Lauria cc We now prove the degree lower bound for SRUκ,r nin SoSC,that is Theorem 1.3, restated here for convenience of the reader. Theorem 1.3 (Degree lower bound for SRUκ,r n). Let n, d ∈N,κ be a prime, r∈C.Letrbe written as r1+ζr2,wherer1,r 2∈R and ζis some κth primitive root of unity. If κd ≤min{r1+r2+(κ−1)n+κ, n −r1−r2+κ}, then there are no SoSC-refutations of SRUκ,r nof degree at most d. In particular, SRUκ,0 nrequires refutations of degree Ωn κin SoSC. Proof. We show that ˜ Eis a degree-dpseudo-expectation. Theorem 3.10 already showed that for every p∈bool-SRUκ,r n,˜ E(qp)= 0. Therefore, it is enough to show that, whenever the condition on dis satisfied, for every polynomial p∈C[x(1),...,x(κ)]ofdegree at most d,˜ E(p·p∗)∈R≥0where p∗is the formal conjugate of p, Let γbe defined as in eq. (3.8). Recall that ˆγ=n−r1−r2 κand S(p)(γ)=˜ E(p). We have that ˜ E(p·p∗)=S(p·p∗)(γ) =S(p·p∗)(r1+ˆγ,r2+ˆγ,...,r κ+ˆγ) [by def. of γ] =Sym(pρ·p∗ ρ)(ˆγe1)[byTheorem 3.13] =d j=0 pd−j(ˆγ)·p∗ d−j(ˆγ)j−1 i=0 (ˆγ−i)(n−ˆγ−i) where the last equality follows from Theorem 3.12 and ρis the substitution given by ρ(xij)=yi+rj n(recall that r3=··· = rκ=0). Now,pd−j(ˆγ)·p∗ d−j(ˆγ) is always real and non-negative since it is the module of the complex number pd−j(ˆγ), hence to enforce the non-negativity of ˜ E(p·p∗) it is enough to argue that j−1 i=0 (ˆγ−i)(n−ˆγ−i)≥0. This is true if ˆγ−d+1≥0and n−ˆγ−d+1≥0. That is if −(κ−1)n+κd −κ≤r1+r2≤n−κd +κ. 4. Size lower bounds In this section, we prove the size lower bound for SRUκ,0 nin SoSC (Theorem 1.4) from the the corresponding degree lower bound (Theorem 1.3).
cc On vanishing sums of roots of unity Page 25 of 45 12 4.1. High level structure of the argument. A way to prove Theorem 1.4 from Theorem 1.3 is the following. On a very high level, this is done composing the polynomials in SRUκ,r nwith some polynomials g, obtaining then some new set of polynomials SRUκ,r n◦g(see Definition 4.3). We are interested in composing polynomials with gwith good properties (see Definition 4.1). Then a lifting theorem shows that degree lower bounds on SRUκ,r n imply size lower bounds on SRUκ,r n◦g(Theorem 4.10). The overall structure of this size lower bound it follows the typical structure of size-degree trade-offs, see for instance (Atserias & Hakoniemi 2019; Clegg et al. 1996;Sokolov 2020) for other examples of size-degree trade-offs. The idea is to show, first, that there exists a relatively long sequence of restrictions such that the restricted polynomials have small degree refutations (Theorem 4.8) and, secondly, that each individual restriction can only make the degree decrease a little (Lemma 4.9). These two components will imply that the sequence of restrictions must be very long and this will imply the size-degree trade-off (Theorem 4.10). Finally, the size lower bound for SRUκ,r n(Theorem 1.4)isjust a corollary of the size-degree trade-off (Theorem 4.10). The rest of the section is just following this high level scheme. We first introduce the notion of compliant polynomials. 4.2. Composition with compliant polynomials. Compliant polynomials are a generalization of the compliant gadgets from (Sokolov 2020, Definition 2.1). The main difference with Sokolov’s gadgets is that compliant gadgets are polynomials with real coefficients and taking values in {0,1}or {±1}, while ours are complex polynomials taking values in the set Ωκof κth roots of unity. Definition 4.1 (compliant polynomial). A polynomial g∈C[y1, ...,y ]is compliant if it is symmetric and there exists a function h:Ω κ→Ω κsuch that (i) g◦h=id, i.e. for all b∈Ωκ,g(h(b)) = b; (ii) for each b∈Ωκ, the first κcoordinates of h(b)list all the elements of Ωκ;and
12 Page 32 of 45 Bonacina, Galesi & Lauria cc Given a polynomial p∈C[y1,...,yn], the symmetrization of p with respect to (σ;ˆı) is the polynomial SYMσ,ˆı(p)= κ−1 m=0 (σ;ˆı)m(p), where (σ;ˆı)mis application of (σ;ˆı)mtimes, and (σ;ˆı)0is the identity. Example 5.1. Say 1=2=3=4,κ=3,andσis the 3-cycle (123). Thetermt=y1,2y2 1,3y1,4y2,2is Yα1 1Yα2 2with α1=(0,1,2,1) and α2=(0,1,0,0). Then, the maps (σ;1) and (σ;2) map tinto: (σ;1)(t)=y1,3y2 1,1y1,4y2,2, (σ;2)(t)=y1 1,2y2 1,3y1,4y2,3, (σ;3)(t)=y1,2y2 1,3y1,4y2,2. Moreover, SYMσ,1(t)=(y1 1,2y2 1,3+y1 1,3y2 1,1+y1 1,1y2 1,2)y1,4y2,2, SYMσ,2(t)=y1,2y2 1,3y1,4(y2,1+y2,2+y2,3), SYMσ,3(t)=3y1,2y2 1,3y1,4y2,2.♦ The example above already suggests the following lemma. Lemma 5.2. Let p, q ∈C[y1,...,yn],ˆı∈[n]and σ∈Sˆı.Ifqis invariant under (σ;ˆı),thenSYMσ,ˆı(pq)=SYM σ,ˆı(p)q. Proof. The action of (σ;ˆı) is multiplicative, therefore SYMσ,ˆı(pq)= κ−1 m=0 (σ;ˆı)m(pq) = κ−1 m=0 (σ;ˆı)m(p)·(σ;ˆı)m(q) = κ−1 m=0 (σ;ˆı)m(p)·q[qis invariant under (σ;ˆı)] =SYM σ,ˆı(p)q.
cc On vanishing sums of roots of unity Page 33 of 45 12 In the Boolean framework, it is possible to kill high degree terms by setting variables to zero, but in the Fourier framework, we cannot do that. Instead, we apply assignment βσ,ˆıto variables yˆıso that, together with symmetrization SYMσ,ˆı(·), it acts as if it was a partial restriction mapping some terms to 0. Definition 5.3 (the partial assignment βσ,ˆı). For ˆı∈[n]and a κ-cycle σ=(j0j1... j κ−1),letβσ,ˆıbe the partial assignment on the variables yˆımapping yˆı,jmto ζm, for every m=0,...,κ−1and mapping the remaining variables yˆı,j to themselves. We denote the partial assignment βσ,ˆıapplied to a polynomial pas pβσ,ˆı. Since we mostly consider SYMσ,ˆı(t) after the restriction by βσ,ˆı we introduce the notation Sσ,ˆı(t)=SYM σ,ˆı(t)βσ,ˆı. Example 5.1 continued. Using the notation of Example 5.1, Sσ,1(t)=(ζζ4+ζ2+ζ2)y1,4y2,2=3ζ2y1,4y2,2, Sσ,2(t)=y1,2y2 1,3y1,4(ζ0+ζ1+ζ2)=0, Sσ,3(t)=3y1,2y2 1,3y1,4y2,2. Notice that, Sσ,1(t)=3tβσ,1and similarly Sσ,3(t)=3tβσ,3.This holds in general, as the next lemma shows. ♦ We show that Sσ,ˆı(t) acts as a sort of partial restriction that either maps the term tto 0 or to a restriction of t. Lemma 5.4. Let ˆı∈[n]and j0,...,j κ−1∈[ˆı]be distinct indices. Let σbe the κ-cycle (j0j1... j κ−1).Lett=i∈[n]Yαi ibe a term in Tn.Then Sσ,ˆı(t)=0if κκ−1 m=0 αˆı,jm κ·tβσ,ˆıotherwise. Proof. Since (σ;ˆı)0is the identity, we have (σ;ˆı)0(t)βσ,ˆı=tβσ,ˆı. For (σ;ˆı)1,wecanseethatnowβσ,ˆımaps the variable yˆıjmto ζm+1, that is (σ;ˆı)1(t)βσ,ˆı=ω·tβσ,ˆı,
12 Page 34 of 45 Bonacina, Galesi & Lauria cc where ω=ζκ−1 m=0 αˆıjm. Likewise, for every 0 ≤m<κ,wehave that (σ,ˆı)m(t)βσ,ˆı=ωm·tβσ,ˆı. That is Sσ,ˆı(t)=κ−1 m=0 ωmtβσ,ˆı=0ifw=1 κ·tβσ,ˆıotherwise, where the last equality follows since ωis a power of ζ, all powers of ζexcept 1 are roots of polynomial 1+X+X2+···+Xκ−1,and ω=1ifandonlyifκk−1 m=0 αˆı,jm. An immediate consequence of Lemma 5.4 is that if Sσ,ˆı(t)=0 then Sσ,ˆı(t∗) = 0, where t∗is the formal conjugate of t. Lemma 5.5. If Sσ,ˆı(t)=0then Sσ,ˆı(t∗)=0,wheret∗is the formal conjugate of t. Proof. By Lemma 5.4,Sσ,ˆı(t) = 0 implies that κk−1 m=0 αˆı,jm. The exponent of the variable yˆı,j in t∗is (καˆı,j/κ−αˆı,j), which is equal to −αˆı,j modulo κ. Therefore κk−1 m=0(καˆı,jm/κ−αˆı,jm). Hence, again by Lemma 5.4,Sσ,ˆı(t∗)=0. Another immediate consequence of Lemma 5.4 is that given a term t=i∈[n]Yαi isuch the entries of the vector αˆıare not all equal modulo κ, then there exist a κ-cycle σsuch that Sσ,ˆı(t)=0. Lemma 5.6. Let t=i∈[n]Yαi iaterminTn, and suppose the entries of the vector αˆıare not all equal modulo κ. Then there exist a κ-cycle σsuch that Sσ,ˆı(t)=0. Proof. By Lemma 5.4, it is enough to show that there are κ distinct indices j0,...,j κ−1∈[ˆı] such that καˆı,j0+···+αˆı,jκ−1. Consider two distinct indices j0,j 1such that αˆı,j0=αˆı,j1modulo κ. Now consider arbitrary distinct indices j2,...,j κ∈[ˆı]. We can find those indices since ˆı≥κ+ 1. It must be that either καˆı,j0+κ m=2 αˆı,jmor καˆı,j1+κ m=2 αˆı,jm. By linearity, define Sσ,ˆı(p) for every p∈C[y1,...,yn]. We show now this operator is well-behaved on polynomials of the form pp∗.
cc On vanishing sums of roots of unity Page 35 of 45 12 Lemma 5.7. For every polynomial p∈C[y1,...,yn],everyˆı∈[n] and every κ-cycle σ∈Sˆı, there are polynomials s0,...,s (κ−1) such that Sσ,ˆı(pp∗)= κ−1 j=0 sjs∗ j, and moreover the total number of monomials in κ−1 j=0 sjs∗ jbefore cancellations is at most the number of monomials in pp∗(again before cancellations). Proof. The permutation σis a κ-cycle, say (j0j1... j κ−1). We focus on the set Aof tuples of exponents for the variables yˆıj0,...,y ˆıjκ−1that occur in the polynomial p. For each such α∈A, we define its norm α=κ−1 m=0 αˆı,jm. Let t(α) be the monomial κ−1 m=0 yαˆıjm ˆıjm. By construction, the formal conjugate of t(α) can be written as t(κIα−α)whereIα is some vector of integers. We can partition Ain A0,A 1,...,A (κ−1) based on the residue of their norm modulo κ.NamelyAm={α∈A:α=m (mod κ)}. Then, we can write p= α∈A0 pαt(α)+ α∈A1 pαt(α)+···+ α∈A(κ−1) pαt(α). where each pαis a polynomial not containing variables among yˆıj0,...,y ˆıjκ−1. Observe that the polynomial Sσ,ˆı(t(α)t(α)∗) is non-zero if and only if κdivides α+κIα−α(by Lemma 5.4), which happens if and only if α=αmodulo κ. By linearity of SYMσ,ˆı(·) and this observation, we have that Sσ,ˆı(pp∗)= α,α∈A pαp∗ αSσ,ˆı(t(α)t(α)∗) = κ−1 j=0 α,α∈Aj pαp∗ αSσ,ˆı(t(α)t(α)∗) =κ κ−1 j=0 α,α∈Aj pαp∗ αt(α)βσ,ˆıt(α)∗βσ,ˆı
12 Page 36 of 45 Bonacina, Galesi & Lauria cc =κ κ−1 j=0 α∈Aj pαt(α)βσ,ˆı· α∈Aj pαt(α)βσ,ˆı∗ = κ−1 j=0 sjs∗ j, where each sjis √κ·α∈Ajpαt(α)βσ,ˆı. We conclude the proof discussing the size. Let cjbe the number of monomials in the polynomial α∈Ajpαt(α). The polynomial sjhas no more monomials than cj, being its restriction. Hence, the total count of monomials in κ−1 j=0 sjs∗ jbefore cancellations is at most κ−1 j=0 c2 jwhich is less than κ−1 j=0 cj2, the number of monomials in pp∗before cancellations. We now restate and prove Theorem 4.8. Theorem 4.8. Let Pbe finite a set of polynomials of degree d0 in C[x]containing the polynomials xκ j−1for each j∈[n].Letg be a tuple of compliant polynomials with gi∈C[yi1,...,y ii]and ω1,ω 2,...,ω m∈Ωκ.IfthereisaSoSCrefutation of P◦g∪{yκ ij − 1: i∈[n],j∈[i]}of size sthen there exists a sequence of variables xi1,...,x imwith m=κnln(s)/Dsuch that (i) =max ii; (ii) the choice of xitonly depends on ω1,...,ω t−1; (iii) there is a SoSCrefutation of Pxi1=ω1,...,xim=ωmof reduced degree at most D+d0. Proof. Let πbe a SoSCrefutation of P◦g∪{yκ ij −1i∈[n],j∈[i]} of size s.Proofπhas the form (5.8) −1= p∈P◦g qp·p+ i∈[n] j∈[i] qij(yκ ij −1) + q∈Q q·q∗,
cc On vanishing sums of roots of unity Page 37 of 45 12 where qp,q ij,qs are polynomials in C[y1,...,yn]. Without loss of generality we can consider a “multilinearized” version of (5.8) where all variables in polynomials qp,qs are raised to powers at most κ−1. This assumption increases proof size only polynomially. We say a term t=i∈[n]Yαi iis fat when there are at least D/κ distinct indices iso that the entries of the vector αiare not all equal. By Lemma 5.6, if a term is fat there are at least D/κ maps (σ;i) with distinct indices isuch that Sσ,i(t)=0. Let Fbe the set of fat terms in the qpsandinq·q∗before cancellations.2For each block of variables yiwe have at most (−1) ...(−κ+1)/κ ≤κ/κ possible κ-cycles in total, hence the maps (σ;i) are at most n·κ/κ.Byaveraging,wehaveapair (σ1,i 1) such that the number of fat terms t∈Fwhere Sσ1,i1(t)=0 are at least k κn·D κ·|F|=D κn|F|. Fix an arbitrary ω1∈Ωκ. By applying (σ1;i1)0,...,(σ1;i1)κ−1 to (5.8), summing and restricting by βi1,σ1we obtain the equality −κ= p∈P◦gSσ1,i1(qp·p)+ i∈[n] j∈[i] Sσ1,i1(qij(yκ ij −1)) + q∈QSσ1,i1(q·q∗).(5.9) Now, since gis symmetric, pis invariant under the action of (σ1;i1) and, by Lemma 5.2,then Sσ1,i1(qp·p)=Sσ1,i1(qp)·pβi1,σ1. For the same reason Sσ1,i1(qij(yκ ij −1)) = Sσ1,i1(qij)(yκ ij −1)βi1,σ1. Therefore, by Lemma 5.7, the expression in (5.9) is a SoSCrefutation π 1of (P◦g)βi1,σ1. Again, symmetry and the other compliance properties of glet us extend βi1,σ1to some βthat sets all remaining variables in yi1and ensures gi1(β(yi1,1),...,β(yi1,i1))=w1. 2This set of polynomials is the analog of the quadratic representation in (Sokolov 2020).
12 Page 38 of 45 Bonacina, Galesi & Lauria cc Restricting π 1by βwe obtain a SoSCrefutation of the set of polynomials (Pxi1=ω1)◦g.Letπ1be this refutation. By Lemma 5.4 and Lemma 5.7,π1hassizeatmostsand, by construction, contains at most (1 −D kn)|F|fat terms. By repeating this process mtimes, we get a partial assignment xi1=ω1,...,x im=ωmand a SoSCrefutation πof the set of polynomials (Pxi1=ω1,...,xim=ωm)◦g. Since by assumption m= κnln(s)/D, the resulting πdoes not have fat terms anymore, because 1−D κnm s≤exp −Dm κn+ln(s)<1. To conclude the argument, we need to transform πinto an SoSC refutation of Pxi1=ω1,...,xim=ωmof reduced degree at most D+d0. More concretely for any unassigned xi, we need to set variables yij to some univariate polynomial over xi, so that the corresponding gi(yi)evaluatestoxiitself. We need the indicator function χa(X) for a∈{0,...,κ−1}. More specifically, χa(X) is the univariate polynomial that evaluates to1whenX=ζaandto0whenX=ζbwith b=a.Thatis, χa(X) is defined as χa(X):= 1 0≤i<κ,i=a(ζa−ζi) 0≤i<κ,i=a (X−ζi) expanded as a sum of monomials. Finally, we substitute all the occurrences of the variable yij in πfor each i∈[n]andj∈[i] with (5.10) κ−1 a=0 hi(ζa)jχa(xi). We recall that hi:Ω κ→Ωi κis the function witnessing that giis compliant, and that hi(ζa)jis the jth coordinate of its value on ζa. Let π be the result applying the substitution (5.10) to π.We have that no monomial in π has degree bigger than D κ(κ−1) <D. We now modify π to get a proper refutation of Pxi1=ω1,...,xim=ωm.
cc On vanishing sums of roots of unity Page 39 of 45 12 The part of π that is a “sum-of-squares”, i.e., a sum of polynomials of the form ss∗, still remains a sum-of-squares after the substitution. The only missing part is to derive in degree at most D+d0 the axioms (Pxi1=ω1,...,xim=ωm)◦gto which substitution (5.10) was applied. We set up useful notation: given polynomials p, q ∈C[x], we write p≡qto denote the fact that p−qis in the ideal generated by xκ 1−1,...,x κ n−1. The following two equivalences (5.11) giκ−1 a=0 hi(ζa)1χa(xi), ..., κ−1 a=0 hi(ζa)iχa(xi)≡xi and (5.12) κ−1 a=0 hi(ζa)jχa(xi)κ ≡1 are enough to see that proof π can be modified into a proof of Pxi1=ω1,...,xim=ωmwith reduced degree not exceeding D+d0,and to conclude the proof. To prove (5.11) and (5.12) notice that χa(xi)2≡χa(xi) and, when a=b,thatχa(xi)χb(xi)≡0Tosee(5.12) we have the calculation κ−1 a=0 h(ζa)jχa(xi)κ = 0≤a1,...,ak<κ ∈[κ] h(ζa)jχa(xi) ≡ κ−1 a=0 h(ζa)κ j·χa(xi)= κ−1 a=0 χa(xi)=1. A similar calculations gives (5.11). giκ−1 a=0 hi(ζa)1χa(xi), ..., κ−1 a=0 hi(ζa)iχa(xi) ≡ κ−1 a=0 gi◦hi(ζa)·χa(xi) = κ−1 a=0 ζa·χa(xi)=xi
12 Page 40 of 45 Bonacina, Galesi & Lauria cc The last equality holds because κ−1 a=0 ζaχa(xi)andxiare two polynomials of degree <κand are equal on all the κth roots of unity. 6. Conclusions The study of algebraic proof systems under Fourier encoding is still at its infancy. There are many natural questions about its size efficiency. We understand reasonably well the strength relation between resolution and PC in the Boolean encoding. Sokolov (2020) stresses that we do not even know yet whether PC with {±1}simulates resolution or not. We mentioned already that the study of κ-coloring of graphs is a very natural application of PC with Fourier encoding. There are some degree lower bounds in literature Lauria & Nordstr¨om (2017), but size lower bounds are still unknown. Understanding size would allow to understand larger classes of algebraic algorithms for this problem. Acknowledgements The authors would like to thank Albert Atserias for fruitful discussions. The first author was supported by the Ministerio de Ciencia e Innovaci´on MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, and IJC2018-035334-I]. Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will
cc On vanishing sums of roots of unity Page 41 of 45 12 need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. References Yaroslav Alekseev,Dima Grigoriev,Edward A. Hirsch & Iddo Tzameret (2020). Semi-Algebraic Proofs, IPS Lower Bounds, and the τ-Conjecture: Can a Natural Number Be Negative? In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC’20), 54–67. Albert Atserias &Tuomas Hakoniemi (2019). Size-Degree Trade- Offs for Sums-of-Squares and Positivstellensatz Proofs. In Proceedings of the 34th Computational Complexity Conference (CCC’19),volume 137 of LIPIcs, 24:1–24:20. Albert Atserias &Joanna Ochremiak (2018). Proof Complexity Meets Algebra. ACM Trans. Comput. Logic 20(1). Roberto J Bayardo Jr &Robert Schrag (1997). Using CSP look-back techniques to solve real-world SAT instances. In Proceedings of the 14th National Conference on Artificial Intelligence and 9th Conference on Innovative Applications of Artificial Intelligence (AAAI’97/IAAI’97), 203–208. Christoph Berkholz (2018). The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS’18), volume 96, 11:1–11:14. Grigoriy Blekherman,Jo˜ ao Gouveia &James Pfeiffer (2016). Sums of squares on the hypercube. Mathematische Zeitschrift 1–14. Grigoriy Blekherman &Cordian Riener (2020). Symmetric Non- Negative Forms and Sums of Squares. Discrete and Computational Geometry 65(3), 764–799.