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

We study the search problem class ${\mathrm{P}\mathrm{P}\mathrm{A}}_q$ defined as a modulo-$q$ analog of the well-known $\mathit{\text{polynomial}}\mathit{\text{parity}}\mathit{\text{argument}}$ class $\mathrm{P}\mathrm{P}\mathrm{A}$ introduced by Papadimitriou '94. Our first result shows that this class can be characterized in terms of ${\mathrm{P}\mathrm{P}\mathrm{A}}_p$ for prime $p$. Our main result is to establish that an $\mathit{\text{explicit}}$ version of a search problem associated to the Chevalley–Warning theorem is complete for ${\mathrm{P}\mathrm{P}\mathrm{A}}_p$ for prime $p$. This problem is $\mathit{\text{natural}}$ in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for ${\mathrm{P}\mathrm{P}\mathrm{A}}_p$ when $p\ge 3$. Finally we discuss connections between Chevalley-Warning theorem and the well-studied $\mathit{\text{short}}\mathit{\text{integer}}\mathit{\text{solution}}$ problem and survey the structural properties of ${\mathrm{P}\mathrm{P}\mathrm{A}}_q$.