On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem

Introduction

The study of total $\mathsf{NP}\!$ search problems ($\mathsf{TFNP}$) was initiated by Megiddo and Papadimitriou [MP91] and Papadimitriou [Pap94] to characterize the complexity of search problems that have a solution for every input and where a given solution can be efficiently checked for validity. Meggido and Papadimitriou [MP91] showed that the notion of $\mathsf{NP}$-hardness is inadequate to capture the complexity of total $\mathsf{NP}$ search problems. By now, this theory has flowered into a sprawling jungle of widely-studied syntactic complexity classes (such as $\mathsf{PLS}$ [JPY88], $\mathsf{PPA}/\mathsf{PPAD}/\mathsf{PPP}$ [Pap94], $\mathsf{CLS}$ [DP11]) that serve to classify the complexities of many relevant search problems.

The goal of identifying naturalFollowing the terminology of many $\mathsf{TFNP}$ papers, including [Gri01, FG18, FG19, SZZ18], a natural problem is one that does not have explicitly a circuit or a Turing machine as part of the input. complete problems for these complexity classes lies in the foundation of this sub-field of complexity theory and not only gives a complete picture of the computational complexity of the corresponding search problems, but also provides a better understanding of the complexity classes. Such natural complete problems have also been an essential middle-step for proving the completeness of other important search problems, the same way that the $\mathsf{NP}$-completeness of Sat is an essential middle step in showing the $\mathsf{NP}$-completeness of many other natural problems. Some known natural complete problems for $\mathsf{TFNP}$ subclasses are: the $\mathsf{PPAD}$-completeness of NashEquilibrium [DGP09], the $\mathsf{PPA}$-completeness of ConsensusHalving, NecklaceSplitting and HamSandwich problems [FG18, FG19] and the $\mathsf{PPP}$-completeness of natural problems related to lattice-based cryptography [SZZ18]. Finally, the theory of total search problems has found connections beyond its original scope to areas like communication complexity and circuit lower bounds [GKRS19], cryptography [BPR15, KNY19, CHK+19] and the Sum-of-Squares hierarchy [KM18].

Our main result is to identify the first natural complete problem for the classes $\mathsf{PPA}_{q}$, a variant of the class $\mathsf{PPA}$. We also illustrate the relevance of these classes through connections with important search problems from combinatorics and cryptography.

Class $\mathsf{PPA}_{q}$. The class $\mathsf{PPA}_{q}$ was defined, in passing, by Papadimitriou [Pap94, p. 520]. It is a modulo-$q$ analog of the well-studied polynomial parity argument class $\mathsf{PPA}$ (which corresponds to $q=2$). The class embodies the following combinatorial principle:

If a bipartite graph has a node of degree not a multiple of $q$, then there is another such node.

In more detail, $\mathsf{PPA}_{q}$ consists of all total $\mathsf{NP}$ search problems reducibleHere, we consider a many-one reduction, which is a polynomial time algorithm with one oracle query to the said problem. In contrast, a Turing reduction allows polynomially many oracle queries. See Section 1.5 for a comparison. to the problem $\textsc{Bipartite}_{q}$ defined as follows. An instance of this problem is a balanced bipartite graph $G=(V\cup U,E)$, where $V\cup U=\{0,1\}^{n}$ together with a designated vertex $v^{\star}\in V\cup U$. The graph $G$ is implicitly given via a circuit $C$ that computes the neighborhood of every node in $G$. Let $\deg(v)$ be the degree of the node $v$ in $G$. A valid solution is a node $v\in\{0,1\}^{n}$ such that, either

In Section 2 we provide some other total search problems ($\textsc{Lonely}_{q}$, $\textsc{Leaf}_{q}$) that are reducible to and from $\textsc{Bipartite}_{q}$. Any one of these problems could be used to define $\mathsf{PPA}_{q}$. In fact, $\textsc{Lonely}_{q}$ and $\textsc{Leaf}_{q}$ are natural variants of the standard problems Lonely and Leaf which are used to define the class $\mathsf{PPA}$.

Our contributions. We illustrate the importance of the complexity classes $\mathsf{PPA}_{q}$ by showing that many important search problems whose computational complexity is not well understood belong to $\mathsf{PPA}_{q}$ (see §1.6 for details). These problems span a wide range of scientific areas, from algebraic topology to cryptography. For some of these problems we conjecture that $\mathsf{PPA}_{q}$-completeness is the right notion to characterize their computational complexity. The study of $\mathsf{PPA}_{q}$ is also motivated from the connections to other important and well-studied classes like $\mathsf{PPAD}$.

In this paper, we provide a systematic study of the complexity classes $\mathsf{PPA}_{q}$. Our main result is the identification of the first natural complete problem for $\mathsf{PPA}_{q}$ together with some structural results. Below we give a more precise overview of our results.

We characterize $\mathsf{PPA}_{q}$ in terms of $\mathsf{PPA}_{p}$ for prime $p$.

Our main result is that an explicitFollowing the terminology in [BIQ+17], by explicit we mean that the system of polynomials, which is the input of the computational problems we define, are given as a sum of monic monomials. version of the Chevalley-Warning theorem is complete

for $\mathsf{PPA}_{p}$ for prime $p$. This problem is natural in that it does not involve circuits as part of the input and is the first known natural complete problem for $\mathsf{PPA}_{p}$ when $p\geq 3$.

As a consequence of the $\mathsf{PPA}_{p}$-completeness of our natural problem, we show that restricting

the input circuits in the definition of $\mathsf{PPA}_{p}$ to just constant depth arithmetic formulas doesn’t change the power of the class.

We show a connection between $\mathsf{PPA}_{q}$ and the Short Integer Solution (SIS) problem from

the theory of lattices. This connection implies that SIS with constant modulus $q$ belongs to $\mathsf{PPA}_{q}\cap\mathsf{PPP}$, but also provides a polynomial time algorithm for solving SIS when the modulus $q$ is constant and has only $2$ and $3$ as prime factors.

We sketch how existing results already paint a near-complete picture of the relative power

of $\mathsf{PPA}_{p}$ relative to other $\mathsf{TFNP}$ subclasses (via inclusions and oracle separations). We also show that $\mathsf{PPA}_{q}$ is closed under Turing reductions.

In Section 1.6, we include a list of open problems that illustrate the broader relevance of $\mathsf{PPA}_{q}$. We note that a concurrent and independent work by Hollender [Hol19] also establishes the structural properties of $\mathsf{PPA}_{q}$ corresponding to §1.1 and §1.5.

$\mathsf{PPA}_{q}=\textsf{\&}_{p|q}\,\mathsf{PPA}_{p}$.

A special case of Theorem 1 is that $\mathsf{PPA}_{p^{k}}=\mathsf{PPA}_{p}$ for every prime power $p^{k}$. Showing the inclusion $\mathsf{PPA}_{p^{k}}\subseteq\mathsf{PPA}_{p}$ is the crux of our proof. This part of the theorem can be viewed as a total search problem analog of the counting class result of Beigel and Gill [BG92] stating that $\mathsf{Mod}_{p^{k}}{\text{P}}=\mathsf{Mod}_{p}{\text{P}}$; “an unexpected result”, they wrote at the time. Throughout this paper, we use $q$ to denote any integer $\geq 2$ and $p$ to denote a prime integer.

2 A Natural Complete Problem via Chevalley-Warning Theorem

There have been several works focusing on completeness results for the class $\mathsf{PPA}$ (i.e. $\mathsf{PPA}_{2}$). Initial works showed the $\mathsf{PPA}$-completeness of (non-natural) total search problems corresponding to topological fixed point theorems [Gri01, ABB15, DEF+16]. Closer to our paper, Belovs et al. [BIQ+17] show the $\mathsf{PPA}$-completeness of computational analogs of Combinatorial Nullstellensatz and the Chevalley–Warning Theorem, but which explicitly involve a circuit as part of the input. More recently, breakthrough results showed $\mathsf{PPA}$-completeness of problems without a circuit or a Turing Machine in the input such as Consensus-Halving, Necklace-Splitting and Ham-Sandwich [FG18, FG19] resolving an open problem since the definition of $\mathsf{PPA}$ in [Pap94].

Our main contribution is to provide a natural complete problem for $\mathsf{PPA}_{p}$, for every prime $p$; thereby also yielding a new complete problem for $\mathsf{PPA}$. Our complete problem is an extension of the problem $\textsc{Chevalley}_{p}$, defined by Papadimitriou [Pap94], which is a search problem associated to the celebrated Chevalley-Warning Theorem. We first present an abstract way to understand the proof of the Chevalley-Warning Theorem that motivates the definition of our natural complete problem for $\mathsf{PPA}_{p}$.

In 1935, Claude Chevalley [Che35] resolved a hypothesis stated by Emil Artin, that all finite fields are quasi-algebraically closed. Later, Ewald Warning [War36] proved a slight generalization of Chevalley’s theorem. This generalized statement is usually referred to as the Chevalley-Warning Theorem (CWT, for short). Despite its initial algebraic motivation, CWT has found profound applications in combinatorics and number theory as we discuss in §1.4 (and Section 6).

In the above definition, it is important to consider the symbolic expansion of $\mathsf{CW}_{\bm{f}}$ and ignore any cancellation of coefficients that might occur. Observe that, although the expansion of $\mathsf{CW}_{\bm{f}}$ is exponentially large in the description size of $\bm{f}$, each monic monomial of $\mathsf{CW}_{\bm{f}}$ can be succinctly described as a combination of monic monomials of the polynomials $f_{1},\ldots,f_{m}$. We formally discuss this in Section 4.

Using the definition of max-degree monic monomials, we state the main technical lemma underlying the proof of CWT (with proof in Section 4).

2.2 Proofs of Cancellation

Thus, any condition on $\bm{f}$ that implies the (Extended CW Condition) can replace (CW Condition) in the Chevalley-Warning Theorem. Note that the (Extended CW Condition) is equivalent to all the max-degree monic monomials in $\mathsf{CW}_{\bm{f}}$ cancelling out. Thus, we call any such condition on $\bm{f}$ that implies (Extended CW Condition) to be a “proof of cancellation” for the system $\bm{f}$.

We can now reinterpret the result of Belovs et al. [BIQ+17] in this framework of “proof of cancellation” conditions. In particular, [BIQ+17] considers the case $p=2$ and defines the problem PPA-Circuit-Chevalley, in which a “proof of cancellation” is given in a specific form of circuits. These circuits describe the system $(f_{1},\ldots,f_{m})$ in the PPA-Circuit-Chevalley problem. It is then shown that PPA-Circuit-Chevalley is $\mathsf{PPA}_{2}$-complete.

2.3 Computational Problems Based on Chevalley-Warning Theorem

Every “proof of cancellation” that is syntactically refutable can be used to define a total search problem that lies in $\mathsf{PPA}_{p}$. By syntactically refutable we mean that whenever the “proof of cancellation” is false, there exists a small witness that certifies so. In this section, we define three computational problems with their corresponding “proof of cancellation”: (1) the $\textsc{Chevalley}_{p}$ problem defined by [Pap94], (2) the $\textsc{GeneralChevalley}_{p}$ problem that is a generalization of $\textsc{Chevalley}_{p}$, and (3) the problem $\textsc{ChevalleyWithSymmetry}_{p}$ that we show to be $\mathsf{PPA}_{p}$-complete. All these problems are defined for every prime modulus $p$ and are natural in the sense that they do not explicitly involve a circuit or a Turing Machine in their input. In particular, the polynomial systems in the input are explicit in that they are given as a sum of monic monomials.

This is the direct computational analog of the Chevalley-Warning Theorem and was defined by Papadimitriou [Pap94] as the following total search problem:

[Refuting witness] (CW Condition) is not satisfied.

$\bm{x}\in\mathcal{V}_{\bm{f}}\smallsetminus\left\{\bm{x}^{\star}\right\}$.

We will particularly consider a special case where all the $f_{i}$’s have zero constant term (zecote, for short). In this case, $\bm{x}^{\star}=\mathbf{0}\in\mathcal{V}_{\bm{f}}$, so there is no need to explicitly include $\bm{x}^{*}$ in the input.

As mentioned already, we can define a search problem corresponding to any syntactically refutable condition that implies the (Extended CW Condition). One such condition is to directly assert that

In particular, note that (CW Condition) implies this condition. Moreover, this condition is syntactically refutable by a max-degree monic monomial, which is efficiently representable as a combination of at most $m(p-1)$ monomials of the $f_{i}$’s. Thus, we can define the following total search problem generalizing $\textsc{Chevalley}_{p}$.

$\underline{\textsc{GeneralChevalley}}_{p}$

[Refuting Witness] A max-degree monic monomial of $\mathsf{CW}_{\bm{f}}$.

$\bm{x}\in\mathcal{V}_{\bm{f}}\smallsetminus\left\{\bm{x}^{\star}\right\}$.

Hence, we further generalize $\textsc{GeneralChevalley}_{p}$ into a problem that incorporates this additional “proof of cancellation” in the form of a permutation $\sigma\in S_{n}$.

We now define the following natural total search problem.

$\underline{\textsc{ChevalleyWithSymmetry}}_{p}$

[Refuting Witness – 1] A max-degree monic monomial of $\mathsf{CW}_{\bm{g}}$.

[Refuting Witness – 2] $\bm{x}\in\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}}$ such that $\sigma(\bm{x})\notin(\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}})\smallsetminus\left\{\bm{x}\right\}$.

$\bm{x}\in\mathcal{V}_{\bm{f}}\smallsetminus\left\{\bm{x}^{\star}\right\}$.

The above problem is natural, because the input consists of a system of polynomial in an explicit form, i.e. as a sum of monic monomials, together with a permutation in $S_{n}$ given say in one-line notation. Also, observe that when $\bm{h}$ is empty, the above problem coincides with $\textsc{GeneralChevalley}_{p}$ (since $\overline{\mathcal{V}_{\bm{h}}}=\emptyset$ when $\bm{h}$ is empty). Our main result is the following (proved in Section 4).

For any prime $p$, $\textsc{ChevalleyWithSymmetry}_{p}$ is $\mathsf{PPA}_{p}$-complete.

3 Complete Problems via Small Depth Arithmetic Formulas

We hope that this theorem will be helpful in the context of proving $\mathsf{PPA}_{{p}}$-hardness of other problems. There it would be enough to consider only constant depth arithmetic formulas (and hence $\mathsf{NC}^{1}$ Boolean formulas) in the definitions of $\mathsf{PPA}_{{p}}$ as opposed to unbounded depth circuits. Such a simplification has been a key-step for proving hardness results for other $\mathsf{TFNP}$ subclasses, e.g. in the $\mathsf{PPAD}$-hardness proofs of approximate-Nash (cf. [Rub16]).

4 Applications of Chevalley-Warning

Apart from its initial algebraic motivation, the Chevalley-Warning theorem has been used to derive several non-trivial combinatorial results. Alon et al. [AFK84] show that adding an extra edge to any $4$-regular graph forces it to contain a 3-regular subgraph. More generally, they prove that certain types of “almost” regular graphs contain regular subgraphs. Another application of CWT is in proving zero-sum theorems similar to the Erdös-Ginzburg-Ziv Theorem. A famous such application is the proof of Kemnitz’s conjecture by Reiher [Rei07].

For a certain range of parameters $n,m$, it holds that

For all primes $p$ : $\textsc{BIS}_{p}$ and $\textsc{SIS}_{p}$ are Karp-reducible to $\textsc{Chevalley}_{p}$, hence are in $\mathsf{PPA}_{p}$.

For all $q$ : $\textsc{BIS}_{q}$ and $\textsc{SIS}_{q}$ are Turing-reducible to any $\mathsf{PPA}_{q}$–complete problem.

For all $k$ : $\textsc{BIS}_{2^{k}}$ is solvable in polynomial time.

Even though the $\textsc{SIS}_{q}$ problem is well-studied in lattice theory, not many results are known in the regime where $q$ is a constant and the number of variables depends linearly on the number of equations. Part (1) of the above theorem establishes a reduction from $\textsc{SIS}_{p}$ to $\textsc{Chevalley}_{p}$ for prime $p$. Part (2) follows by a bootstrapping method that allows us to combine algorithms for $\textsc{SIS}_{q_{1}}$ and $\textsc{SIS}_{q_{2}}$ to give an algorithm for $\textsc{SIS}_{q_{1}q_{2}}$ (for a certain regime for parameters $n$ and $m$). Finally Parts (3) and (4) results follow by using this bootstrapping method along with the observation that Gaussian elimination provides valid solutions for $\textsc{BIS}_{2}$ (hence also $\textsc{SIS}_{2}$) and for $\textsc{SIS}_{3}$.

5 Structural properties

Buss and Johnson [BJ12, Joh11] had defined a class $\mathsf{PMOD}_{q}$ which turns out to be slightly weaker than $\mathsf{PPA}_{q}$ (refer to Section 7). Despite this slight difference between the definitions of $\mathsf{PPA}_{q}$ and $\mathsf{PMOD}_{q}$, we can still deduce statements about $\mathsf{PPA}_{q}$ from the work of [Joh11]. In particular, it follows that $\mathsf{PPAD}\subseteq\mathsf{PPA}_{q}$ (refer to Section 7.1).

More broadly, a near-complete picture of the power of $\mathsf{PPA}_{q}$ relative to other subclasses of $\mathsf{TFNP}$ is summarized in Figure 1. These relationships (inclusions and oracle separations) mostly follow from prior work in proof complexity [BR98, BGIP01, Joh11, GKRS19] (refer to Section 7.2).

Recall that $\mathsf{TFNP}$ subclasses are defined as the set of all total search problems that are many-one reducible (aka Karp–reducible) to the corresponding complete problems. One can ask whether more power is gained by allowing Turing reductions, that is, polynomially many oracle queries to the corresponding complete problem. Buss and Johnson [BJ12] showed that $\mathsf{PLS}$, $\mathsf{PPAD}$, $\mathsf{PPADS}$, $\mathsf{PPA}$ are closed under Turing reductions (with a notable exception of $\mathsf{PPP}$, which remains open). We show this for $\mathsf{PPA}_{p}$ when $p$ is a prime.

$\mathsf{FP}^{\mathsf{PPA}_{p}}=\mathsf{PPA}_{p}$ for every prime $p$.

By contrast, it follows from [BJ12, §6] that $\mathsf{PPA}_{q}$ is not closed under black-box Turing reductions for non-prime powers $q$. See Section 7.3 for details.

6 Open questions

It has been shown that Factoring reduces to $\mathsf{PPP}$-complete problems as well as to $\mathsf{PPA}$-complete problems [BO06, Jer16], albeit under randomized reductions (which can be derandomized assuming the Generalized Reimann Hypothesis). It has been asked whether in fact Factoring could be reduced to $\mathsf{PPAD}$-complete problems [Jer16]. As a step towards this problem, we propose the following question.

Is Factoring in $\mathsf{PPA}_{p}$ for all primes $p$ (perhaps under randomized reductions)?

This is clearly an easier problem since $\mathsf{PPAD}\subseteq\mathsf{PPA}_{p}$. Interestingly, note that there exists an oracle $\mathcal{O}$ relative to which $\bigcap_{p}\mathsf{PPA}_{p}^{\mathcal{O}}\nsubseteq\mathsf{PPAD}^{\mathcal{O}}$. Thus, the above problem, even if established for all prime $p$, is still weaker than showing that Factoring reduces to $\mathsf{PPAD}$-complete problems.

The $q\textsc{-Necklace-Splitting}$ problem is defined as follows: There is an open necklacean “open necklace” means that the beads form a string, not a cycle with $q\cdot a_{i}$ beads of color $i$, for $i\in[n]$. The goal is to cut the necklace in $(q-1)\cdot n$ places and partition the resulting substrings into $k$ collections, each containing precisely $a_{i}$ beads of color $i$ for each $i\in[n]$.

The fact that such a partition exists was first shown in the case of $q=2$ by Goldberg and West [GW85] and by Alon and West [AW86]. Later, Alon [Alo87] proved it for all $q\geq 2$. As mentioned before, Filos-Ratsikas and Goldberg [FG19] showed that the $2\textsc{-Necklace-Splitting}$ problem is $\mathsf{PPA}$-complete. Moreover, they put forth the following question (which we strengthen further).

Is $q\textsc{-Necklace-Splitting}$ in $\mathsf{PPA}_{q}$? More strongly, is it $\mathsf{PPA}_{q}$-complete?

While we do not know how to prove/disprove this yet, we point out that it was also shown in [FG19] that $2^{k}\textsc{-Necklace-Splitting}$ is in fact in $\mathsf{PPA}_{2}$. This is actually well aligned with this conjecture since we showed that $\mathsf{PPA}_{2^{k}}=\mathsf{PPA}_{2}$ (Theorem 1).

Alon’s proof of the $q$-Necklace-Splitting theorem [Alo87] was topological and used a certain generalization of the Borsuk-Ulam theorem due to Bárány, Shlosman and Szücs [BSS81]. Since the computational Borsuk-Ulam problem is $\mathsf{PPA}$-complete, we could ask a similar question about this generalization.

Is $\textsc{B\'{a}r\'{a}ny-Shlosman-Sz\"{u}cs}_{p}$ problem in $\mathsf{PPA}_{p}$ (perhaps even $\mathsf{PPA}_{p}$-complete)?

We conclude with some interesting directions for further exploring the connections of Chevalley with other computational problems.

Does $\textsc{SIS}_{q}$ admit worst-to-average case reductions to other lattice problems in our range of parameters? Or is it average-case hard assuming standard cryptographic assumptions, e.g. the “learning with errors” assumption?

If resolved positively, the above would serve as evidence of the average-case hardness for the class $\mathsf{PPA}_{p}$, similar to the evidence that we have for $\mathsf{PPA}$ by reduction from Factoring.

For all primes $p$, is $\textsc{Chevalley}_{p}$ reducible to $\textsc{BIS}_{p}$?

For all $q$, is there a non-trivial regime of parameters $n$, $m$ where $\textsc{BIS}_{q}$ is solvable in polynomial time?

A search problem $\mathcal{R}_{1}$ is Karp-reducible (or many-one reducible) to a search problem $\mathcal{R}_{2}$, or $\mathcal{R}_{1}\preceq\mathcal{R}_{2}$ for short, if there exist polynomial-time computable functions $f$ and $g$ such that given any instance $x$ of $\mathcal{R}_{1}$, $f(x)$ is an instance of $\mathcal{R}_{2}$ such that for any $y\in\mathcal{R}_{2}(f(x))$, it holds that $g(x,f(x),y)\in\mathcal{R}_{1}(x)$.

On the other hand, we say that $\mathcal{R}_{1}$ is Turing-reducible to $\mathcal{R}_{2}$, or $\mathcal{R}_{1}\preceq_{T}\mathcal{R}_{2}$ for short, if there exists a polynomial-time oracle Turing machine that on input $x$ to $\mathcal{R}_{1}$, makes oracle queries to $\mathcal{R}_{2}$, and outputs a $y\in\mathcal{R}_{1}(x)$. In this paper, we primarly deal with Karp-reductions, except in Section 7.3, where we compare the two different notions of reductions in the context of $\mathsf{PPA}_{q}$.

We describe several total search problems (parameterized by $q$) that we show to be inter-reducible. $\mathsf{PPA}_{q}$ is then defined as the set of all search problems reducible to either one of the search problems defined below.

A bipartite graph with a non-multiple-of-$q$ degree node has another such node.

Bipartite graph $G=(V\cup U,E)$. Designated vertex $v^{*}\in V$

$\triangleright$ $C:\left\{0,1\right\}^{n}\to(\left\{0,1\right\}^{n})^{k}$, with $(\left\{0,1\right\}^{n})^{k}$ interpreted as a $k$-subset of $\left\{0,1\right\}^{n}$ $\triangleright$ $v^{*}\in\left\{0\right\}\times\left\{0,1\right\}^{n-1}$ (usually $0^{n}$)

$V\coloneqq\left\{0\right\}\times\left\{0,1\right\}^{n-1}$, $U\coloneqq\left\{1\right\}\times\left\{0,1\right\}^{n-1}$, $E\coloneqq\left\{(v,u):v\in V\cap C(u)\text{ and }u\in U\cap C(v)\right\}$

A $q$-dimensional matching on a non-multiple-of-$q$ many vertices has an isolated node.

$q$-dimensional matching $G=(V,E)$. Designated vertices $V^{*}\subseteq V$ with $|V^{*}|\leq q-1$

$\triangleright$ $C:[q]^{n}\to[q]^{n}$ $\triangleright$ $V^{*}\subseteq[q]^{n}$ with $|V^{*}|\leq q-1$

$V\coloneqq[q]^{n}$. For distinct $v_{1},\ldots,v_{q}$, edge $e\coloneqq\left\{v_{1},\ldots,v_{q}\right\}\in E$ if $C(v_{i})=v_{i+1}$, $C(v_{q})=v_{1}$

$v\in V^{*}$ if $\deg(v)=1$ and $v\notin V^{*}$ if $\deg(v)=0$

A $q$-uniform hypergraph with a non-multiple-of-$q$ degree node has another such node.

$q$-uniform hypergraph $G=(V,E)$. Designated vertex $v^{*}\in V$

$\triangleright$ $C:\left\{0,1\right\}^{n}\to(\left\{0,1\right\}^{nq})^{q}$, with $(\left\{0,1\right\}^{nq})^{q}$ interpreted as $q$ many $q$-subsets of $\left\{0,1\right\}^{n}$ $\triangleright$ $v^{*}\in\left\{0,1\right\}^{n}$ (usually $0^{n}$)

$V\coloneqq\left\{0,1\right\}^{n}$. For distinct $v_{1},\ldots,v_{q}$, edge $e\coloneqq\left\{v_{1},\ldots,v_{q}\right\}\in E$ if $e\in C(v)$ for all $v\in e$

We remark that $\textsc{Lonely}_{q}$ and $\textsc{Leaf}_{q}$ are modulo-$q$ analogs of the $\mathsf{PPA}$-complete problems Lonely and Leaf [Pap94, BCE+98]. We prove the following theorem in Appendix A.

The problems $\textsc{Bipartite}_{q}$, $\textsc{Lonely}_{q}$ and $\textsc{Leaf}_{q}$ are inter-reducible.

We will use the following simple conventions repeatedly, in order to simplify the descriptions of reductions between different search problems.

We will often use “algorithms”, instead of “circuits” to encode our hypergraphs. It is standard to simulate polynomial-time algorithms by polynomial sized circuits.

The above simplification gives us that all our problems have an instance-extension property (cf. [BM04]) – this will be helpful in proving Theorem 4.

To simplify our reductions even further, we’ll often describe the edges/hyperdges directly instead of specifying how to compute the neighbors of a given vertex. This is only for simplicity and it will be easy to see how to compute the neighbors of any vertex locally.

Characterization via Primes

In this section we prove Theorem 1, namely $\mathsf{PPA}_{q}=\textsf{\&}_{p|q}\,\mathsf{PPA}_{p}$. The theorem follows by combining the following two ingredients.

$\mathsf{PPA}_{p^{k}}=\mathsf{PPA}_{p}$ for any prime power $p^{k}$.

2 Prime power case

We will describe an algorithm that on vertex $\overline{v}\in\overline{V}$ outputs a hyperedge of $p$ vertices that contains $\overline{v}$ (if any). To this end, first fix an algorithm that for any set $e\coloneqq\left\{u_{1},\ldots,u_{p^{k}}\right\}\subseteq V$ and for any $1\leq i\leq p^{t}$, computes some “canonical” partition of the set $\binom{e}{i}$ into subsets of size $p$, and moreover assigns a canonical cyclic order within each such subset. This is indeed possible because of Eq. 3.2, since $t<k$.

Given a vertex $\overline{v}\coloneqq\left\{v_{1},\ldots,v_{p^{t}}\right\}\in\overline{V}$,

It is easy to see that $\overline{v}$ is isolated in $\overline{G}$ iff all $v\in\overline{v}$ are isolated in $G$. Moreover, any isolated vertex in $\overline{V}\smallsetminus\overline{V}^{*}$ contains at least one isolated vertex in $V\smallsetminus V^{*}$; and a non-isolated vertex in $\overline{V}^{*}$ contains at least one non-isolated vertex in $V^{*}$ (in fact $p^{t}$ many).

The edges of $\overline{G}$ can indeed be computed efficiently with just black-box access to $C$. In order to complete the reduction, we only need that $\overline{V}$ is efficiently indexable. This is indeed standard; see [KS98, §2.3] for a reference. See Figure 3 for an illustration of the proof.

Note that the size of the underlying graph blows up polynomially in our reduction. We do not know whether a reduction exists that avoids such a blow-up, although we suspect that the techniques of [BR98] can be used to show that some blow-up is necessary for black-box reductions.

A Natural Complete Problem

We start with some notation that will be useful for the presentation of our results.

We repeat the formal statement of Chevalley-Warning Theorem together with its proof.

A monic monomial of $\mathsf{CW}_{\bm{f}}$ is a product $t_{S}(\bm{x})=\prod_{i=1}^{m}t_{s_{i}}(\bm{x})$ for $S=(s_{1},\ldots,s_{m})\in U$.

We define $\mathcal{M}_{\bm{f}}$ to be the set of max-degree monic monomials of $\mathsf{CW}_{\bm{f}}$, i.e. $\mathcal{M}_{\bm{f}}\coloneqq\left\{S\in U\mid t_{S}\text{ is a max-degree monic monomial of }\mathsf{CW}_{\bm{f}}\right\}$.

In words, the monomials $t(S)$ are precisely the ones that arise when symbolically expanding $\mathsf{CW}_{\bm{f}}({\bm{x}})$. We illustrate this with an example: Let $p=3$ and $f_{1}(x_{1},x_{2})=x_{1}+x_{2}$ and $f_{2}(x_{1},x_{2})=x_{1}^{2}$. Then modulo $\left\{x_{1}^{3}-x_{1},x_{2}^{3}-x_{2}\right\}$, we have

Thus there are $18$ $(=6\times 3)$ monic monomials in the system $(f_{1},f_{2})$. The monomial corresponding to $S=((1,5),(2,2))$ is a maximal monomial since the $5$-th term in $\mathsf{CW}_{f_{1}}$ is $x_{2}^{2}$ and $2$-nd term in $\mathsf{CW}_{f_{2}}$ is $x_{1}^{2}$. Using the above definitions, we now state the main technical lemma of the proof of CWT.

The proof of Chevalley-Warning Theorem follows easily from 4.2.

We have that $\deg(\mathsf{CW}_{\bm{f}})\leq(p-1)\sum_{i=1}^{m}\deg(f_{i})$. Thus, if $\bm{f}$ satisfies (CW Condition), then $\deg(\mathsf{CW}_{\bm{f}})<(p-1)n$ and hence $\left|\mathcal{M}_{\bm{f}}\right|=0$. CWT now follows from 4.2. ∎

2 The Chevalley-Warning Theorem with Symmetry

In this section, we formalize the intuition that we built in Sections 1.2.2 and 1.2.3 to prove the more general statements to lead to the same conclusion as the Chevalley-Warning Theorem.

First, we prove a theorem that argues about the cardinality of $\mathcal{V}_{\bm{f}}$ directly using some symmetry of the system of polynomials $\bm{f}$. Then, combining this symmetry-based argument with the (General CW Condition) we get the generalization of the Chevalley-Warning Theorem. Our natural $\mathsf{PPA}_{p}$-complete problem is based on this generalization.

Our first theorem highlights the use of symmetry in arguing about the size of $\left|\mathcal{V}_{\bm{f}}\right|$.

Since $\sigma$ acts freely on $\overline{\mathcal{V}}_{\bm{f}}$, we can partition $\overline{\mathcal{V}}_{\bm{f}}$ into orbits of any $\bm{x}\in\overline{\mathcal{V}}_{\bm{f}}$ under actions of $\langle\sigma\rangle$, namely sets of the type $\left\{\sigma^{i}(\bm{x})\right\}_{i\in[p]}$ for $\bm{x}\in\overline{\mathcal{V}}_{\bm{f}}$. Since $\langle\sigma\rangle$ acts freely on $\overline{\mathcal{V}}_{\bm{f}}$, each such orbit has size $p$. Thus, we can conclude that $\left|\overline{\mathcal{V}}_{\bm{f}}\right|\equiv 0\pmod{p}$ from which the theorem follows. ∎

We now state and prove an extension of CWT that captures both the argument from 4.2 and the symmetry argument from Theorem 6.

3 Computational Problems Related to Chevalley-Warning Theorem

We now follow the intuition developed in the previous section and in Section 1.2 to formally define the computational problems $\textsc{Chevalley}_{p}$, $\textsc{GeneralChevalley}_{p}$, and $\textsc{ChevalleyWithSymmetry}_{p}$.

General Chevalley-Warning Theorem via (General CW Condition).

A max-degree monic monomial $t_{S}(\bm{x})$ of $\mathsf{CW}_{\bm{f}}$, or

black($\textsc{ChevalleyWithSymmetry}_{p}$)

Chevalley-Warning Theorem with Symmetry (Theorem 7).

(a) A max-degree monic monomial $t_{S}(\bm{x})$ of $\mathsf{CW}_{\bm{g}}$, or

(b) $\bm{x}\in\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}}$ such that $\sigma(\bm{x})\not\in(\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}})\smallsetminus\left\{\bm{x}\right\}$, or

Some observations about the above computational problems follow:

In the problems $\textsc{GeneralChevalley}_{p}$ and $\textsc{ChevalleyWithSymmetry}_{p}$, we assume that, if the output is a max-degree monic monomial, this is given via the multiset of indices $S$ that describes the monomial as formalized in 4.1.

We have $\textsc{Chevalley}_{p}\preceq\textsc{GeneralChevalley}_{p}\preceq\textsc{ChevalleyWithSymmetry}_{p}$. Thus, inclusion of $\textsc{ChevalleyWithSymmetry}_{p}$ in $\mathsf{PPA}_{p}$ implies that the problems $\textsc{Chevalley}_{p}$ and $\textsc{GeneralChevalley}_{p}$ are in $\mathsf{PPA}_{p}$. Also, in Section 6 we prove that $\textsc{SIS}_{p}\preceq\textsc{Chevalley}_{p}$, where $\textsc{SIS}_{p}$ is a cryptographically relevant problem. This shows that the $\textsc{GeneralChevalley}_{p}$ and the $\textsc{ChevalleyWithSymmetry}_{p}$ problems are at least as hard as the $\textsc{SIS}_{p}$ problem.

We fist prove that ChevalleyWithSymmetry is in $\mathsf{PPA}_{{p}}$ and then prove its $\mathsf{PPA}_{{p}}$-hardness.

Even though Papadimitriou [Pap94] provided a rough proof sketch of $\textsc{Chevalley}_{p}\in\mathsf{PPA}_{{p}}$, a formal proof was not given. We show that $\textsc{ChevalleyWithSymmetry}_{p}$ is in $\mathsf{PPA}_{{p}}$ (and so are $\textsc{GeneralChevalley}_{p}$ and $\textsc{Chevalley}_{p}$). In order to do so we extend the definition of $\textsc{Bipartite}_{q}$ to instances where the vertices might have exponential degree and edges appear with multiplicity. The key here is to define a $\textsc{Bipartite}_{q}$ instance with unbounded (even exponential) degree, but with additional information that allows us to verify solutions efficiently.

Similar to $\textsc{Bipartite}_{q}$, but degrees are allowed to be exponentially large, edges are allowed with multiplicities at most $q-1$.

Let $V\coloneqq\left\{0\right\}\times\left\{0,1\right\}^{n-1}$ and $U\coloneqq\left\{1\right\}\times\left\{0,1\right\}^{n-1}$: $\triangleright$ $\mathcal{C}:V\times U\to[q]$, edge counting circuit $\triangleright$ $\phi_{V}:V\times U\times[q]\to(U\times[q])^{q}$, grouping pivoted at $V$ $\triangleright$ $\phi_{U}:V\times U\times[q]\to(V\times[q])^{q}$, grouping pivoted at $U$ $\triangleright$ $e^{*}=(v^{*},u^{*},k^{*})$, designated edge

$V\coloneqq\left\{0\right\}\times\left\{0,1\right\}^{n-1}$, $U\coloneqq\left\{1\right\}\times\left\{0,1\right\}^{n-1}$, $E\coloneqq\left\{(v,u,k):1\leq k\leq C(v,u),\ (v,u)\in V\times U\right\}$ (here $k$ distinguishes multiplicities) Edge $(v,u,k)$ is grouped with $\left\{(v,u^{\prime},k^{\prime}):(u^{\prime},k^{\prime})\in\phi_{V}(v,u,k)\right\}$ (pivoting at $v$), provided $|\phi_{V}(v,u,k)|=q$, all $(v,u^{\prime},k^{\prime})\in E$ and $\phi_{V}(v,u^{\prime},k^{\prime})=\phi_{V}(v,u,k)$. Edge $(v,u,k)$ is grouped with $\left\{(v^{\prime},u,k^{\prime}):(v^{\prime},k^{\prime})\in\phi_{U}(v,u,k)\right\}$ (pivoting at $u$), provided $|\phi_{U}(v,u,k)|=q$, all $(v,u^{\prime},k^{\prime})\in E$ and $\phi_{U}(v^{\prime},u,k^{\prime})=\phi_{V}(v,u,k)$.

$e^{*}$ if $e^{*}$ is grouped, pivoting at $v^{*}$, or if $e^{*}$ is not grouped pivoting at $u^{*}$, OR $e\neq e^{*}$ if $e$ is not grouped pivoting at one of its ends.

In words, $\textsc{SuccinctBipartite}_{p}$ encodes a bipartite graph with arbitrary degree. Instead of listing the neighbors of a vertex using a circuit, we have a circuit that outputs the multiplicity of edges between any two given vertices. We are therefore unable to efficiently count the number of edges incident on any vertex. The grouping function $\phi_{V}$ aims to group edges incident on any vertex $v\in V$ into groups of size $q$. Similarly, $\phi_{U}$ aims to group edges incident on any vertex $u\in U$. The underlying principle is that if we have an edge $e^{*}$ that is not grouped pivoting at $v^{*}$ (one of its endpoints), then either $e^{*}$ is not pivoted at $u^{*}$ (its other endpoint) or there exists another edge that is also not grouped pivoting at one of its ends. Note that in contrast to the problems previously defined, $v^{*}$ might still be an endpoint of a valid solution.

For all primes $p$, $\textsc{ChevalleyWithSymmetry}_{p}\in\mathsf{PPA}_{{p}}$.

We reduce $\textsc{ChevalleyWithSymmetry}_{p}$ to $\textsc{SuccinctBipartite}_{p}$, which we show to be $\mathsf{PPA}_{p}$–complete in Section A.1. Given an instance of $\textsc{ChevalleyWithSymmetry}_{p}$, namely a zecote polynomial system $\bm{f}=(\bm{g},\bm{h})$ and a permutation $\sigma$, we construct a bipartite graph $G=(U\cup V,E)$ encoded as an instance of $\textsc{SuccinctBipartite}_{p}$ as follows.

We first describe the edges between $U$ and $V_{1}$, namely include an edge between an assignment $\bm{x}$ and a monomial $t$ with multiplicity $t(\bm{x})$. With these edges in place, the degree of vertices are as follows:

$\bm{x}=0^{n}$ has a single edge corresponding to the constant monomial $1$, since $\bm{f}$ is zecote. We let this be the designated edge $e^{*}$ in the final $\textsc{SuccinctBipartite}_{p}$ instance.

$\bm{x}\in\mathcal{V}_{\bm{g}}\cap\mathcal{V}_{\bm{h}}$ such that $\bm{x}\neq\bm{0}$, or

$t\in V_{1}$ such that $t(\bm{x})$ is a max-degree monomial or

$\bm{x}\in\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}}$ such that $\sigma(\bm{x})=\bm{x}$ or

$v\in V_{2}$ such that $\exists\,\bm{x}\in v$ satisfying $\bm{x}\in\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}}$ and $\sigma(\bm{x})\notin\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}}$.

These correspond precisely to the solutions of $\textsc{ChevalleyWithSymmetry}_{p}$. To summarize, the edge counting circuit $C$ on input $(\bm{x},t)\in U\times V_{1}$ outputs $t(\bm{x})$ and on input $(\bm{x},v)\in U\times V_{2}$ outputs $p-1$ if $\bm{x}\in\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}}$, $\sigma(\bm{x})\neq\bm{x}$ and $v=\Sigma_{\bm{x}}$ and 0 otherwise.

The grouping functions $\phi_{U}$ and $\phi_{V}$ are defined as follows (analogous to the so-called “chessplayer algorithm” in [Pap94]):

Grouping $\phi_{U}$ (corresponding to endpoint in $U$):

For $\bm{x}\in\overline{\mathcal{V}_{\bm{g}}}$: there exists some $i$ such that $\mathsf{CW}_{g_{i}}(\bm{x})=0$. Consider an edge $(\bm{x},(a_{1},a_{2},\dots,a_{m_{g}}),k)$. We can explicitly list out the multiset containing the monomials $t_{j}=(a_{1},a_{2},\dots,a_{i}\leftarrow j,\dots,a_{m_{g}})$ with multiplicity $t_{j}(\bm{x})$, for each $1\leq j\leq L_{i}$. Since $\mathsf{CW}_{g_{i}}(\bm{x})=0$, this multiset has size multiple of $p$. Hence, we can canonically divide its elements into groups of size $p$, counting multiplicities and $\phi_{U}$ returns the subset containing $(t,k)$.

For $\bm{x}\in\mathcal{V}_{\bm{g}}\cap\overline{\mathcal{V}_{\bm{h}}}$ such that $\sigma(\bm{x})\neq\bm{x}$: Note that $g_{i}^{p-1}(\bm{x})=0$ for all $i\in[m_{g}]$. Let $v_{1}\in V_{1}$ be the vertex corresponding to the constant monomial $1$. $\phi_{U}$ groups the edge $(\bm{x},v_{1},1)$ (of multiplicity $1$) with the $p-1$ edges $(\bm{x},\Sigma_{\bm{x}},k)$ for $k\in[p-1]$. For any other $t\in~V_{1}\setminus\left\{v_{1}\right\}$ and an edge $(\bm{x},t,k)$, we have that $t=(a_{1},\dots,a_{m_{g}})$ has $a_{i}\neq 0$ for some $i$. We define the multiset containing $t_{j}=(a_{1},\dots,a_{i}\leftarrow j,\dots a_{m_{g}})$ with multiplicity $t_{j}(\bm{x})$ for each $1\leq j<L_{i}$. Since $g_{i}^{p-1}(\bm{x})=0$, this multiset has size which is a multiple of $p$, which we can canonically partition into groups of size $p$. Thus, $\phi_{U}$ on input $(\bm{x},t,k)$ returns the group containing $(t,k)$.

Grouping $\phi_{V}$ (corresponding to endpoint in $V$):

We show that $\textsc{Lonely}_{p}\preceq\textsc{ChevalleyWithSymmetry}_{p}$. In the $\textsc{ChevalleyWithSymmetry}_{p}$ instance that we create, we will ensure that there are no solutions of type 0 (as in 4.8) and thus, the only valid solutions will be of type 1. In order to do so, we introduce the notions of labeling and proper labeling and prove a generalization of CWT that we call Labeled CWT (Theorem 8).

As we will see, the Labeled CWT, is just a re-formulation of the original CWT rather than a generalization. To understand the Labeled CWT we start with some examples that do not seem to satisfy the Chevalley-Warning condition, but where a solution exists.

Ignore Some Terms. The Labeled CWT formalizes the phenomenon observed in Example 1 and shows that under certain conditions we can ignore some terms when defining the degree of each polynomial. For instance, in Example 1, we can ignore the term $x_{1}^{2}$ when computing the degree of $f$ and treat $f$ as a degree $1$ polynomial of $2$ variables, in which case the condition of CWT is satisfied.

We describe which terms can be ignored by defining a labeling of the terms of each polynomial in the system. The labels take values in $\{-1,0,+1\}$ and our final goal is to ignore the terms with label $+1$. Of course, it should not be possible to define any labeling that we want; for example we cannot ignore all the terms of a polynomial. Next, we describe the rules of a proper labeling that will allow us to prove the Labeled CWT. We start with a definition of a labeling.

Example 1 (continued). According to the lexicographic ordering, $f(x_{1},x_{2})=-x_{1}^{2}+x_{2}$ and we have the monomials $t_{11}=-x_{1}^{2}$ and $t_{12}=x_{2}$. Hence, one possible labeling, which as we will see later corresponds to the vanilla Chevalley-Warning Theorem, is $\lambda(1,1)=\lambda(1,2)=0$. According to this labeling, $\deg^{\lambda}(f)=2$. Another possible labeling, that, as we will see, allows us to apply the Labeled CWT ​, is $\lambda(1,1)=+1$ and $\lambda(1,2)=-1$. In this case, the labeled degree is $\deg^{\lambda}(f)=1$.

As we highlighted before, our goal is to prove the Chevalley-Warning Theorem, but with the weaker condition that $\sum_{i=1}^{m}\deg^{\lambda}(f_{i})<n$ instead of $\sum_{i=1}^{m}\deg(f_{i})<n$. Of course, we first have to restrict the space of all possible labelings by defining proper labelings. In order to make the condition of proper labelings easier to interpret we start by defining the notion of a labeling graph.

Example 2. Let $p=2$ and $f_{1}(x_{1},x_{2},x_{3},x_{4})=x_{1}x_{2}-x_{3}$, $f_{2}(x_{1},x_{2},x_{3},x_{4})=x_{1}x_{3}-x_{4}$. In this system, if we use the lexicographic monomial ordering we have the monomials $t_{11}=x_{1}x_{2}$, $t_{12}=-x_{3}$, $t_{21}=x_{1}x_{3}$, $t_{22}=-x_{4}$. The following figure shows the graph $G_{\lambda}$ for the labeling $\lambda(1,1)=+1$, $\lambda(1,2)=-1$, $\lambda(2,1)=+1$ and $\lambda(2,2)=-1$.