\documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.44}{21(4)}{2014} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{tabularx} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newcommand{\vecc}[1]{\mathbf{#1}} \newcommand{\modu}[1]{(\textnormal{mod }#1)} \newcommand{\computationalproblem}[1]{\noindent\center\textsc{#1}\vspace{3mm}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \title{\bf Combinatorial Nullstellensatz modulo\\ prime powers and the Parity Argument} \author{L\'aszl\'o Varga\thanks{Supported by Hungarian Scientific Research Fund - OTKA, K109240.}\\ \small Institute of Mathematics\\[-0.8ex] \small E\"otv\"os Lor\'and University\\[-0.8ex] \small Budapest, Hungary\\ \small\tt LVarga@cs.elte.hu\\ } \date{\dateline{Feb 19, 2014}{Nov 18, 2014}{Nov 27, 2014}\\ \small Mathematics Subject Classifications: 11B75} \begin{document} \maketitle \begin{abstract} We present new generalizations of Olson's theorem and of a consequence of Alon's Combinatorial Nullstellensatz. These enable us to extend some of their combinatorial applications with conditions modulo primes to conditions modulo prime powers. We analyze computational search problems corresponding to these kinds of combinatorial questions and we prove that the problem of finding degree-constrained subgraphs modulo $2^d$ such as $2^d$-divisible subgraphs and the search problem corresponding to the Combinatorial Nullstellensatz over $\mathbb{F}_2$ belong to the complexity class Polynomial Parity Argument (PPA). \bigskip\noindent \textbf{Keywords:} Combinatorial Nullstellensatz; Olson's theorem; PPA \end{abstract} \section{Introduction} In this paper, we are interested in combinatorial and computational problems in connection with Alon's Combinatorial Nullstellensatz \cite{alon} which is a landmark theorem in algebraic combinatorics. \begin{theorem}[Combinatorial Nullstellensatz, Alon, \cite{alon}] Let $\mathbb{F}$ be an arbitrary field, and let $f\in \mathbb{F}[x_1,\dots x_m]$ be an $m$-variable polynomial. Suppose that the degree of $f$ is $\sum_{j=1}^m t_j$, where each $t_j$ is a nonnegative integer, and that the coefficient of $\prod_{j=1}^m x_j^{t_j}$ is nonzero. Then, if $S_1,S_2,\dots,S_m$ are subsets of $\mathbb{F}$ with $|S_j| > t_j$ for all $j=1,\dots,m$, then there exists $\vecc{s}=(s_1,s_2,\dots, s_m) \in S_1 \times S_2 \times \dots \times S_m$ such that $f(\vecc{s})\neq 0$. \end{theorem} The following corollary is often used implicitly in applications, see \cite{alon}. \begin{corollary} \label{combnullprimes} Let $p$ be an arbitrary prime. Let us be given some $m$-variable polynomials $f_1,f_2,\ldots,f_n$ over $\mathbb{F}_p$ with no constant terms and $Q_1,Q_2,\ldots,Q_n\subseteq \mathbb{F}_p$ such that $0 \in Q_i$ for all $i$. If \[ m>\sum_{i=1}^n \deg(f_i)\cdot |\mathbb{F}_{p} \backslash Q_i|, \] then there exists a vector $\vecc{0}\neq \vecc{x}\in \{0,1\}^m$ such that $f_i(\vecc{x})\in Q_i$ for all $i$. \end{corollary} \begin{proof} Let $f(\vecc{x})=\prod_{i=1}^n \prod_{q \not \in Q_i} (q-f_i(\vecc{x})) - c \cdot \prod_{j=1}^m (1-x_j)$ over $\mathbb{F}_p$, where $c=\prod_{i=1}^n \prod_{q \not \in Q_i} q$. It is easy to check that $\deg(f)=m>\sum_{i=1}^n \deg(f_i)\cdot |\mathbb{F}_{p} \backslash Q_i|$ and for a vector $\vecc{x}\in \{0,1\}^m$, $f(\vecc{x})\neq 0$ if and only if $\vecc{0}\neq \vecc{x}$ and $f_i(\vecc{x})\in Q_i$ for all $i$. Then, with setting $S_i=\{0,1\}$ for all $i$, the Combinatorial Nullstellensatz implies the statement. \end{proof} \bigskip The goal of this paper is to give similar theorems for problems modulo arbitrary prime powers: we prove that if the number $m$ of variables is sufficiently large, the corollary also holds modulo arbitrary prime powers. We develop a general method for the Combinatorial Nullstellensatz-type proofs, where the polynomials are modulo prime powers instead of primes. As an application, we extend the following theorem of Olson \cite{ols} and its generalization by Alon, Friedland and Kalai \cite{reg}. Let us be given a prime $p$, nonnegative integers $d_1\geq d_2 \geq \dots \geq d_n$ and sets $Q_1,Q_2,\dots,Q_n$ such that each of them contains zero and $Q_i \subseteq\mathbb{Z}_{p^{d_i}}$ for every $i=1,\dots ,n$. Let us denote $(d_1,d_2,\dots, d_n)$ by $\mathbf{d}$ and $(Q_1,Q_2,\dots, Q_n)$ by $\mathbf{Q}$. Alon et al. \cite{reg} ask to determine the minimum value $F(\mathbf{d},\mathbf{Q})$ such that for every $m>F(\mathbf{d},\mathbf{Q})$ and for arbitrary integers $a_{ij}$ $\left(i=1,\dots ,n,j=1,\dots ,m\right)$ there exists a nonempty subset $J \subseteq \{1,2,\dots,m \}$ that fulfills the following condition: \[ \sum_{j\in J} a_{ij} \equiv q_i \qquad \modu{p^{d_i}} \quad \textnormal{ for some } q_i \in Q_i \textnormal{ for every }i=1,\dots ,n. \label{eq:cong} \tag{$\clubsuit$} \] Using this terminology, we can easily formulate Olson's theorem and its extension by Alon et al. as follows: \begin{theorem}[Olson, \cite{ols}] \label{olson} $F(\mathbf{d},\mathbf{Q}) = \sum_{i=1}^n \left(p^{d_i} - 1\right)$, if $\{0\}=Q_i$ for all $i$. \end{theorem} \begin{theorem}[Alon, Friedland, Kalai, \cite{reg}] \label{alonolson} $F(\mathbf{d},\mathbf{Q}) \leq \sum_{i=1}^n \left(p^{d_i} - card_p(Q_i)\right)$ where $card_p(Q)$ denotes the number of distinct elements in $Q$ modulo $p$. \end{theorem} Whereas Theorem \ref{alonolson} does not seem to be a strong estimation because of $card_p(Q)\leq p$, no better estimation has been known thus far. It is worth noting that for $d_1=d_2=\dots=d_n=1$, Theorem \ref{olson} and Theorem \ref{alonolson} immediately follow from Corollary \ref{combnullprimes}: for $f_i(\vecc{x})=\sum_{j=1}^{m} a_{ij}x_j$, there exists a vector $\vecc{0}\neq \vecc{s}\in \{0,1\}^m$ such that $f_i(\vecc{s})\in Q_i$ for all $i$. Consequently, $J=\{j : s_j = 1 \}$ fulfills the condition (\ref{eq:cong}). Motivated by these questions, in this paper, we give analogous theorems modulo arbitrary prime powers instead of primes, extending Corollary \ref{combnullprimes}, and give improved bounds on $F(\mathbf{d},\mathbf{Q})$. It is also worth noting that Brink \cite{brink} gave another extension of Corollary \ref{combnullprimes} and Olson's theorem in a slightly different way. His theorem also deals with arbitrary prime powers, however, the variables are restricted to sets where the elements are pairwise incongruent modulo $p$. In contrast, our results allow one variable, the right hand side of the polynomial, to be restricted to arbitrary set, and the other variables remain to be restricted to the set $\{0,1\}$. \subsection{Complexity aspects} As an application of Olson's theorem, Alon, Friedland and Kalai \cite{reg} discussed the following extremal graph theoretic question. Given a prime power $p^d$ and an integer $n$, the problem is to determine the smallest value of $m$ such that for every graph on $n$ vertices and $m$ edges, there exists a nonempty $p^d$-divisible subgraph, that is, a nonempty subset of edges such that the number of edges incident to every vertex is divisible by $p^d$. Conversely, determine the maximum number of edges a graph can have without containing a nonempty $p^d$-divisible subgraph. The exact answer was given in \cite{reg}, see Theorem \ref{qdiv}. A natural question is to determine the computational complexity of finding such a subgraph if the graph has sufficiently large number of edges. For the case $p^d=2$, the problem is equivalent to finding a cycle in a graph. In this case, there exists a polynomial time algorithm, but the problem is open in all other cases. Due to various applications of the Combinatorial Nullstellensatz, it is also a natural question to determine the computational complexity of the corresponding search problem. An open question by West \cite{west} is about the complexity of the Combinatorial Nullstellensatz over $\mathbb{F}_2=\{0,1\}$. He conjectures that the corresponding search problem belongs to the complexity class Polynomial Parity Argument (PPA) defined by Papadimitriou \cite{papa}. This complexity class contains such computational search problems that the existence of a solution can be proved by so-called parity argument: \textit{Every finite graph has an even number of odd-degree nodes.} In this paper, we verify his conjecture. \section{Main results} \label{sec:mainresults} Now we present the first main result of this paper: the extension of Corollary \ref{combnullprimes} for arbitrary prime powers. This theorem also implies Theorem \ref{olson} and Theorem \ref{alonolson}. \begin{definition} \label{covering} Let $h(x)$ be an integer-valued polynomial in $\mathbb{Q}[x]$ such that $h(0)$ is not divisible by $p$. We say that $B \subseteq \mathbb{Z}_{p^{d}}$ is covered by a set of such integer-valued polynomials $\mathcal{H}$ if for every $b\in B$, we have $p\mid h(b)$ for at least one $h\in\mathcal{H}$. The price of the set $B$ is defined as \[ price(B)=\min \{ \sum_{h\in\mathcal{H}} \deg(h) : B \textnormal{ is covered by }\mathcal{H} \textnormal{, such that for all } h\in\mathcal{H}, p \nmid h(0)\}. \] \end{definition} \begin{theorem} \label{maintheorem} Suppose that there are given some $m$-variable polynomials $f_1,f_2,\ldots,f_n$ over $\mathbb{Z}$ without constant terms and some sets $Q_1,Q_2,\ldots,Q_n$ such that $Q_i \subseteq \mathbb{Z}_{p^{d_i}}$ and $0\in Q_i$ for all $i$. If \[ m > \sum_{i=1}^n \deg(f_i)\cdot price(\mathbb{Z}_{p^{d_i}} \backslash Q_i) \] then exists a $\vecc{0}\neq \vecc{x}\in \{0,1\}^m$ such that \[ f_i(\vecc{x}) \equiv q_i \qquad \modu{p^{d_i}} \quad \textnormal{ for some }q_i \in Q_i \textnormal{ for all }i. \] \end{theorem} We will prove this theorem in Section \ref{sec:proof}. It is easy to check that Theorem \ref{maintheorem} implies Corollary \ref{combnullprimes}: let $d=1$, so $0\in Q \subseteq \mathbb{F}_p$. Then, $\{h(x)=x-q : q \not\in Q \}$ covers $\mathbb{F}_{p} \backslash Q$ with price $|\mathbb{F}_{p} \backslash Q|$. Theorem \ref{olson} and Theorem \ref{alonolson} will follow from Theorem \ref{maintheorem} via the following general estimation for $F(\mathbf{d},\mathbf{Q})$ which we will prove in Section \ref{sec:olson}. \begin{theorem} \label{genolsontheorem} $F(\mathbf{d},\mathbf{Q})\leq \sum_{i=1}^{n} price( \mathbb{Z}_{p^{d_i}} \backslash Q_i)$. \end{theorem} In Section \ref{sec:kappa}, we will give a general and constructive bound for $price(B)$, which gives a strictly stronger estimation for $F(\mathbf{d},\mathbf{Q})$ than that one in Theorem \ref{alonolson}. We also show a wide class where this estimation is tight. In the rest of the paper, we analyze the related computational questions. In Section \ref{sec:subgraphs}, we will prove that the $2^d$-divisible subgraph problem belongs to the complexity class Polynomial Parity Argument (PPA). We reduce the $2^d$-divisible subgraph problem to the search problem of the Combinatorial Nullstellensatz over $\mathbb{F}_2$ and in Section \ref{sec:combnull}, we verify West's conjecture: the search problem of the Combinatorial Nullstellensatz over $\mathbb{F}_2$ is also in PPA, if the polynomial is given in a general form such as in most of the applications. In Section \ref{sec:louigi}, we focus on degree-constrained subgraphs modulo prime powers, and we will prove an analogous theorem for Shirazi-Verstra\" ete theorem \cite{louigi}. \section{The proof of Theorem \ref{maintheorem}} \label{sec:proof} The proof of Theorem \ref{maintheorem} presented here is similar to the proof of Theorem \ref{alonolson} in \cite{reg}. Alon et al. used a similar polynomial to the one in Equation (\ref{eq:maintheorem}), however, they used only the special construction of Equation (\ref{eq:alonconstr}) instead of arbitrary polynomials. Now we extend it to arbitrary integer-valued polynomials $h$ and we can use more than one polynomial at the same time. We apply the following corollary of Gregory-Newton formula for integer-valued polynomials, see e.g. \cite{integervalued}. \begin{theorem} Let $h(x)$ be an integer-valued polynomial in $\mathbb{Q}[x]$, namely, for every integer $T$, $h(T)$ is an integer. Then, $h(x)$ can be written as $\sum_{r=0}^d \alpha_r \binom{x}{r}$ where $\alpha_r \in \mathbb{Z}$. \end{theorem} In the following abstract definitions, one can think of the polynomial $f$ as the 'true meaning' of the problem such as $f_i$ in Corollary \ref{combnullprimes}, and one can think of the polynomial $h$ as the covering polynomial in Definition \ref{covering}. The key idea is in the following observation. Although $h(x)$ may have non-integral coefficients, we can construct a polynomial $\Psi^h(f)$ over $\mathbb{Z}$ that satisfies the equality $\Psi^h(f)(\vecc{s}) = h(f(\vecc{s}))$, if $\vecc{s}=(s_1,s_2,\dots,s_m) \in \{0,1\}^m$. Since $\Psi^h(f)$ have integral coefficients, it can be considered over $\mathbb{F}_p$, so some information over $\mathbb{Z}$ -- and hence, modulo $p^d$ -- can be encoded over $\mathbb{F}_p$. \begin{definition} Let $f=\sum_{i=1}^{k} p_i$ be a polynomial over $\mathbb{Z}$, where each $p_i$ is a monomial with coefficient 1. Let $\Psi_r(f)\in \mathbb{Z}[x_1,\dots,x_m]$ be the following polynomial: \[ \Psi_r(f) = \sum_{1\leq i_1 \sum_{i=1}^{n} price( \mathbb{Z}_{p^{d_i}} \backslash Q_i)$. Applying Theorem \ref{maintheorem}, there exists a vector $\vecc{0}\neq \vecc{s}\in \{0,1\}^m$ such that \[ f_i(\vecc{s}) \equiv q_i \qquad \modu{p^{d_i}} \quad \textnormal{ for some }q_i \in Q_i \textnormal{ for every }i=1,\dots ,n. \] Let $J= \{j : s_j=1 \}$. Then, \[ \sum_{j\in J} a_{ij} = f_i(\vecc{x}) \equiv q_i \qquad \modu{p^{d_i}} \quad \textnormal{ for some }q_i \in Q_i \textnormal{ for every }i=1,\dots ,n. \] Hence, $F(\mathbf{d},\mathbf{Q})\leq \sum_{i=1}^{n} price( \mathbb{Z}_{p^{d_i}} \backslash Q_i)$. \end{proof} We are ready to show that Theorem \ref{genolsontheorem} implies Theorem \ref{alonolson} and its special case, Theorem \ref{olson}. Let $d$ be arbitrary, and $0\in Q' \subseteq \mathbb{Z}_{p^d}$ be a set of distinct integers modulo $p$. Then, let \[ h(T):=\frac{1}{p^\delta}\prod_{q\not \in Q'}( T-q)\textnormal{, where }\delta = \sum_{r=0}^{d-1} (p^r-1). \label{eq:alonconstr} \tag{2} \] For every integer $T$, in the product $\prod_{q\not \in Q'}( T-q)$, at least $p^{d-r}-1$ numbers are divisible by $p^r$ for every $1\leq r \leq d$. Hence $h(T)$ is an integer-valued polynomial. Further, $h(T)$ is not divisible by $p$ if and only if no factor is divisible by $p^{d}$. So $h(T)$ is divisible by $p$ if and only if $T\equiv q\quad \modu{p^d}$ for some $q\not \in Q'$. Hence, $h(0)$ is not divisible by $p$ and $h(T)$ covers $\mathbb{Z}_{p^d} \backslash Q'$ with price $deg(h)=p^d-|Q'|$. This implies that if $0\in Q$ is an arbitrary subset of $\mathbb{Z}_{p^d}$, $price(\mathbb{Z}_{p^d} \backslash Q) \leq p^d - card_p(Q) $, so Theorem \ref{alonolson} follows from Theorem \ref{genolsontheorem}. \label{sec:kappa} Furthermore, Theorem \ref{genolsontheorem} enables to obtain strictly stronger bounds than the one in Theorem \ref{alonolson} via the following general constructive estimation on $price(B)$. \begin{definition} \label{kappa} For set $B$ of integers modulo $p$, let $\kappa(B)=|B|$. For any $d>1$ and for set $B$ of integers modulo $p^d$, let us define $k$ as the cardinality of the set $\{b\in B : b\textnormal{ is divisible by }p^{d-1}\}$ and $\hat{B}$ as the set of such residues modulo $p^{d-1}$ that appear in $B$ more than $k$ times. Then, let $\kappa(B)=k\cdot p^{d-1}+\kappa(\hat{B})$. \end{definition} The following definition for $\kappa$ is equivalent to the above one. It gives a way to compute the value of $\kappa(B)$. Let $B$ be a set of integers modulo $p^d$. Now, we define integers $k_{d-1},\dots,k_{0}$ and sets $B_{d},\dots,B_{1}$ such that $B_r$ is a set of integers modulo $p^r$. Let $B_{d}=B$ and \[ k_{d-1}=|\{b\in B : b\textnormal{ is divisible by }p^{d-1}\}|. \] Then, for $r=d-1,\ldots,2, 1$, if $B_{r+1}$ is given, let $B_{r}$ be the set of such residues modulo $p^r$ that appear in $B_{r+1}$ more than $k_{r}$ times and let $k_{r-1} = |\{b\in B_{r} : b\textnormal{ is divisible by }p^{r-1}\}|$. Then, $\kappa(B)=\sum_{r=0}^{d-1} k_r\cdot p^r$. \begin{example} Let $p^d=5^3=125$ and \[ B=\{1,2,5,6,12,20,40,42,50,51,52,56,69,70,87,95,100,101,102,112\}. \] Then, $k_2=2$, because two integers in $B$ are divisible by 25 (50 and 100). Then, $B_{2}=\{1,2,12,20\}$. For instance, $20 \in B_2$, because $20\equiv 70 \equiv 95 $ are in $B_3$, but $6 \not\in B_2$, because only $6\equiv 56$ are in $B_3$. So on, $k_1=1$, $B_{1}=\{2\}$, and $k_0=1$. Hence, $\kappa(B)=2\cdot 25 + 1\cdot 5 + 1 \cdot 1 = 56$. \end{example} \begin{theorem} \label{kappabound} With the above definition, $price(B) \leq \kappa(B)$ holds. \end{theorem} \begin{proof} As the first step, we construct a polynomial that covers a complete $p^r$-residue system modulo $p^{r+1}$ with price $p^r$. Let $q_1,q_2,\dots,q_{p^r}$ be a complete $p^r$-residue system and let \[ h(T):=\frac{1}{p^\delta}\prod_{i=1}^{p^r}( T-q_i)\textnormal{, where }\delta = \sum_{j=0}^{r-1} p^{j}. \] For every integer $T$, the integers $T-q_1,T-q_2,\dots,T-q_{p^r}$ also form a complete residue system modulo $p^r$, so in the product $\prod_{i=1}^{p^r}( T-q_i)$, $p^{r-j}$ factors are divisible by $p^j$ for every $1\leq j \leq r$. Hence, the product is divisible by $p^\delta$ and $h(T)$ is an integer-valued polynomial. Further, $h(T)$ is divisible by $p$ if and only if the factor which is divisible by $p^r$ is also divisible by $p^{r+1}$. This means $T \equiv q_i \quad \modu{p^{r+1}}$ for some $i$, that is, $h(T)$ covers $q_1,q_2,\dots,q_{p^r}$ modulo $p^{r+1}$, precisely, it covers the set \[ \{q \in \mathbb{Z}_{p^d} : q \equiv q_i \quad \modu{p^{r+1}}\textnormal{ for some }i \} \] with price $p^r$. Then, by Definition \ref{kappa}, the statement immediately follows: one can cover the integers that are divisible by $p^{d-1}$ with $k$ such conditions. These conditions also covers other residues $k$ times, so such residues are not covered by the conditions that appear more than $k$ times. These remaining residues are in $\hat{B}$ modulo $p^{d-1}$ and they can be covered with $\kappa(\hat{B})$. \end{proof} \subsection{A special case when Theorem \ref{genolsontheorem} is tight} Here we show a special case when the theorem is tight. This statement shows a wide class where Theorem \ref{genolsontheorem} and hence Theorem \ref{maintheorem} give tight estimation. In general, tightness is not yet known. This result also shows cases when Theorem \ref{alonolson} gives strictly weaker estimation than the one in Theorem \ref{genolsontheorem}. \begin{definition} \label{rzeroset} Let $R$ be a subset of $\{ 0,1,\dots,d-1\}$. Let us define the set $\Omega \subseteq \mathbb{Z}_{p^{d}}$ by the following property: $c \in \Omega$ if and only if $c^{(r)}=0$ for every $r\in R$ in the $c^{(d-1)}\dots c^{(1)}c^{(0)}$ form of $c$ in base $p$. We call $\Omega$ the $R$-zero set modulo $p^d$. Let $\sigma(R)= (p-1)\sum_{r \in R} p^r$. \end{definition} \begin{theorem} \label{rzerolson} Let $R_i$ be an arbitrary subset of $\{ 0,1,\dots,d_i-1\}$ and denote the $R_i$-zero set modulo $p^{d_i}$ by $\Omega_i$. Then, $F(\mathbf{d},\mathbf{\Omega}) = \sum_{i=1}^{n} \sigma(R_i)$. \end{theorem} \begin{proof} We show that $\sigma(R)=\kappa(\mathbb{Z}_{p^{d}} \backslash \Omega)$ and hence $F(\mathbf{d},\mathbf{\Omega}) \leq \sum_{i=1}^{n} \sigma(R_i)$ by Theorem \ref{genolsontheorem} and Theorem \ref{kappabound}. The proof is by induction on $d$. Let $B = \mathbb{Z}_{p^{d}} \backslash \Omega$. Further, let $d'=d-1$ and let $\Omega'$ be the $R'=R\backslash \{d-1\}$-zero set modulo $p^{d'}$ and $B' = \mathbb{Z}_{p^{d'}} \backslash \Omega'$. By induction, $\sigma(R')=\kappa(B')$. If $d-1 \not\in R$, then $k=|\{b\in B : b\textnormal{ is divisible by }p^{d-1}\}|=0$, and $\hat{B}=B'$. Then $\kappa(B)=0 + \kappa(B')=\sigma(R')=\sigma(R)$. If $d-1 \in R$, then $k=|\{b\in B : b\textnormal{ is divisible by }p^{d-1}\}|=p-1$ and $\hat{B}=B'$. Then $\kappa(B)=(p-1)\cdot p^{d-1} + \kappa(B')=(p-1)\cdot p^{d-1}+ \sigma(R')=\sigma(R)$. Moreover, these bounds are tight: $F(\mathbf{d},\mathbf{\Omega}) = \sum_{i=1}^{n} \sigma(R_i)$, because if $m=\sum_{i=1}^{n} \sigma(R_i)$, then there exists integers $a_{ij}$ such that the proper nontrivial subset does not exist. Let $a_{ij}$ be $-1$ if $\sum_{l=1}^{i-1} \sigma(R_l) < j \leq \sum_{l=1}^{i} \sigma(R_l)$, and zero otherwise. However, in the range $-p^{d_i},\dots,0$, the largest integer of the $R_i$-zero sets modulo $p^{d_i}$ is \[ \sum_{r \not \in R_i} (p-1)\cdot p^r = p^{d_i} - 1 - \sum_{r \in R_i} (p-1)\cdot p^r = p^{d_i} - 1 - \sigma(R_i) \equiv -\sigma(R_i) - 1 \quad \modu{p^{d_i}} \] and $-\sigma(R_i) \leq \sum_{j\in J} a_{ij} \leq 0$, hence, no nonempty subset exists that fulfills the condition (\ref{eq:cong}). \end{proof} \section{Complexity aspects of \\ the Combinatorial Nullstellensatz} \label{sec:combnull} Due to various applications of the Combinatorial Nullstellensatz, it is a natural and important question to determine the computational complexity of the corresponding search problem. Now, we study the complexity of the Combinatorial Nullstellensatz over $\mathbb{F}_2$. It is worth noting that if $t_i=0$ for some indices, then we could choose $|S_i|=1$, so in an appropriate vector $(s_1,s_2,\dots, s_m)$, we have to choose the only element of $S_i$ to $s_i$ and therefore, we could replace $x_i$ by the only element of $S_i$ in $f$. Hence, we may assume that $S_i=\mathbb{F}_2$ for every index $i$ and the problem is finding a vector $(s_1,s_2,\dots, s_m) \in \mathbb{F}_2^m$ such that $f(s_1,s_2,\dots s_m)\neq 0$. The complexity of finding such a vector whose existence is guaranteed by the Combinatorial Nullstellensatz depends on the input form of the given polynomial. It is easy to check that the problem belongs to P if the polynomial is given explicitly as the sum of monomials. First, we can replace the term $x_{i_1}^{t_{i_1}}x_{i_2}^{t_{i_2}}\dots x_{i_k}^{t_{i_k}}$ by $x_{i_1}x_{i_2}\dots x_{i_k}$, because these are equal due to the fact $0^t=0, 1^t=1$ in $\mathbb{F}_2$. Substitute 0 and 1 to $x_1$: let $g(x_2,\dots,x_{n})=f(0,x_2,\dots,x_{n})$ and $h(x_2,\dots,x_{n})=f(1,x_2,\dots,x_{n})$. If in $f$ the coefficient of $x_2x_3\dots x_m$ is nonzero, then in $g$ the coefficient of $x_2x_3\dots x_m$ will be also nonzero. If it is zero, in $h$ the coefficient of $x_2x_3\dots x_m$ will be nonzero. Then, substitute 0 and 1 to $x_2$ and in one of them the coefficient of $x_3x_4\dots x_m$ will be nonzero, and so on. Finally, we obtain a constant nonzero polynomial, and this means that for this substitution $\vecc{s} \in \mathbb{F}_2^m$, $f(\vecc{s}) \neq 0$ holds. It is worth noting that a similar polynomial time algorithm can be obtained over arbitrary finite field, if the polynomial is given explicitly. However, if the polynomial is given as the sum of products of polynomials (such as in most of the applications), the problem is not known to be solvable in polynomial time. Furthermore, the existence of an efficient general algorithm for this case would imply that there cannot be any one-way permutations \cite{alon2}. An open question in \cite{west} is about the complexity of the Combinatorial Nullstellensatz conjecturing that the problem over $\mathbb{F}_2$ belongs to the class Polynomial Parity Argument (PPA) defined by Papadimitriou \cite{papa}. In this section, we verify this conjecture: we prove that the Combinatorial Nullstellensatz over $\mathbb{F}_2$ is in PPA if the polynomial is given as the sum of products of polynomials. Consequently, the applications given in Sections \ref{sec:subgraphs} and \ref{sec:louigi} also belong to PPA. Roughly speaking, the class PPA is a subclass of the semantic class TFNP, the set of all total search problems. A search problem is called {\em total} if the corresponding decision problem is trivial, that is, for every feasible input, there exists a solution. A total problem is usually equipped with a mathematical proof showing that it belongs to TFNP, so the problems can be classified based on their proof styles. The complexity class PPA is the class of all search problems whose totality is proved using the parity argument: \textit{Every finite graph has an even number of odd-degree nodes.} It is worth noting that the class TFNP coincides with the set of search variants of NP $\cap$ coNP problems \cite{total}, so the class PPA is between the the set of search variants of P and NP. The class PPA can be defined with a canonical complete problem, the \textsc{End Of The Line}. Hence, a computational search problem is in PPA if and only if it is reducible to the problem \textsc{End Of The Line}. In this problem, we are given a graph $G=(V,E)$ on exponentially many nodes. It can be assumed that each node has an unique code from $\Sigma^n$, that is $V\subseteq \Sigma^n$. The edges of the graph are described by a polynomial time algorithm in $n$. This polynomial time pairing function is the following. For an undirected graph $G=(V,E)$, the function $\phi : V\times V \rightarrow V\cup\{*\}$ is called a {\em pairing function}, if it satisfies the following conditions: if $vw$ is not an edge of $G$, let $\phi(v,w)=*$. Otherwise, it outputs a node $w'=\phi(v,w)$ such that $w'$ is also connected to $v$ and $\phi(v,\phi(v,w))=w$ holds. Furthermore, for every $v$, at most one such node $w$ exists with property $\phi(v,w)=w$. It means that $\phi$ pairs up the neighbours of an input node $v$: for an even-degree node $v$, it pairs its neighbours completely, and for an odd-degree node $v$, $\phi$ pairs all but one neighbours. The task is to find an odd-degree node $v$ and a node $w$ such that $\phi(v,w)=w$. This node $w$ verifies that $v$ is an odd-degree node. The problem \textsc{End Of The Line} can be defined as follows. \begin{center} \fbox{ \parbox{0.85\linewidth}{ \computationalproblem{End of the Line.} \begin{tabularx}{\linewidth}{lX} \textit{Input:}& an undirected finite graph $G=(V,E)$ in the above way. The edges of the graph is described by a polynomial time pairing function. Furthermore, a node $\varepsilon$ is given which has odd number of edges and a node $\delta$ which shows it: $\phi(\varepsilon,\delta)=\delta$. \\ \textit{Find:}& another node $v$ which has odd number of edges and a node $w$ which give the certificate $\phi(v,w)=w$. \end{tabularx} }} \end{center} \medskip In order to prove problems belonging to PPA, we give reductions to the problem \textsc{End Of The Line}. It is worth noting that this problem is computationally equivalent to the problem in which the nodes have at most two neighbours, a node of degree one is given and the task is to find another node which has exactly one incident edge. (Instead of the polynomial time pairing function, a polynomial time algorithm is given which outputs the neighbours of an input node.) It is easy to see that this is an easier problem, however, Papadimitriou showed that they are computationally equivalent. In \cite{papa}, Papadimtriou shows that the following computational problem \textsc{Ch\'evalley MOD 2} belongs to the class PPA. The required vector exists due to Ch\'evalley's following theorem. \begin{theorem}[Ch\'evalley] Let $\mathbb{F}$ be a finite field with characteristic $p$. Let $p_1,p_2,\dots, p_n$ be polynomials in $m$ variables over $\mathbb{F}$. Suppose that $\sum_{i=1}^{n} \deg(p_i) < m$. Then, the number of common solutions of the polynomial equation system $p_i(x_1,\dots,x_m)=0$ $(i=1\dots n)$ is divisible by $p$. In particular, if there is a solution, there exists another. \end{theorem} \begin{center} \fbox{ \parbox{0.85\linewidth}{ \computationalproblem{Ch\'evalley MOD 2.} \begin{tabularx}{\linewidth}{lX} \textit{Input:}& polynomials $p_1,p_2, \dots , p_n$ in $\mathbb{F}_2[x_1,\dots x_m]$ such that \[ \sum_{i=1}^n \deg(p_i) < m. \] Also, we are given a root $(c_1,c_2,\dots,c_m) \in \mathbb{F}_2^m$ of the equation system $p_i(\vecc{x})=0$ ($i=1,\dots,n$).\\ \textit{Find:}& another root of the equation system $p_i(\vecc{x})=0$ ($i=1,\dots,n$). \end{tabularx} }} \end{center} \medskip Using Theorem \ref{combulltheo} and that Ch\'evalley's theorem can be proved via a reduction to the Combinatorial Nullstellensatz, see \cite{alon}, one can give an alternative proof for the PPA membership of \textsc{Ch\'evalley MOD 2}. Originally, this reduction motivates West's question \cite{west} about the complexity of the Combinatorial Nullstellensatz. Now, let us define the following computational problem. Note that the required vector exists due to the Combinatorial Nullstellensatz. \begin{center} \fbox{ \parbox{0.85\linewidth}{ \computationalproblem{Combinatorial Nullstellensatz over $\mathbb{F}_2$.} \begin{tabularx}{\linewidth}{lX} \textit{Input:}& a polynomial $f$ in $m$ variables in a general form \[ f= \sum_{i=1}^{k} \left( \prod_{j=1}^{m_i} p_{ij} \right), \] where $p_{ij}$ is an explicitly given polynomial in $\mathbb{F}_2[x_1,\dots x_m]$, $k,m_i$ and the number of monomials of $p_{ij}$ is polynomially bounded in $m$. Suppose that $\sum_{j=1}^{m_i} \deg(p_{ij}) \leq m$ for all $i$ and there is a polynomial time pairing function which can pair up all but one terms $x_1x_2\dots x_m$ to prove that the degree of $f$ is $m$ and the coefficient of $x_1x_2\dots x_m$ is nonzero. \\ \textit{Find:}& a vector $(s_1,s_2,\dots, s_m) \in \mathbb{F}_2^m$ such that $f(s_1,s_2,\dots,s_m) \neq 0$. \end{tabularx} }} \end{center} \medskip \begin{theorem} \label{combulltheo} The \textsc{Combinatorial Nullstellensatz over $\mathbb{F}_2$} is polynomially reducible to \textsc{End of the Line}. Consequently, The \textsc{Combinatorial Nullstellensatz over $\mathbb{F}_2$} is in PPA. \end{theorem} The proof of Theorem \ref{combulltheo} is similar to the proof for PPA membership of \textsc{Ch\'evalley MOD 2}. Our construction is based on that proof, nevertheless, we need a new key idea about the upper-level pairing function which pairs up blocks whose value at 1 for the substitution $\vecc{x}$. We construct a graph, the nodes correspond to the vectors and the terms. The nodes with odd degree correspond to the vectors $\vecc{x}$ such that $f(\vecc{x})\neq 0$ and an extra node $w$. As we mentioned, we have to present a pairing function. It can be done easily at the terms, but it is more complicated at the vectors. The main idea here is the following. We call the polynomials $\prod_{j=1}^{m_i} p_{ij}$ as the blocks of the input polynomial $f$. Each term is the product of monomials from the given polynomials of a block, so each term in the $i$th block can be represented by an $(m_i+1)$-tuple of integers: $(i,a_{i,1},\dots, a_{i,m_i})$. The first coordinate shows the block the term belongs to, and the other coordinates show the monomials the term is product of: it is the product of $a_{i,j}$th monomials of $p_{ij}$. (Note that the same term might have more than one occurrence and these occurrences are represented by different tuples.) In the next proof, we will pair up these tuples. \begin{remark} In a standard PPA-type problem definition it is required that the assumptions of the problem should be in NP. If the input is feasible, we have to return a solution, but if the input is infeasible, we have to return a polynomial certificate of infeasibility. It is easy to check that the assumptions in the definition of the \textsc{Combinatorial Nullstellensatz over $\mathbb{F}_2$} are in NP. In the case of an infeasible input, we can give the following certificate: the index $i$ such that $\sum_{j=1}^{m_i} \deg(p_{ij}) > n$ or two occurrences of the term $x_1x_2\dots x_m$ for which the polynomial time pairing function fails. \end{remark} \begin{proof}[Proof of Theorem \ref{combulltheo}] We shall construct a graph $\Gamma$ whose odd-degree nodes precisely correspond to appropriate vectors $\vecc{s}$ such that $f(\vecc{s}) \neq 0$ and furthermore, we add an extra node $w$: the standard leaf. The graph is bipartite. The nodes on one side are all the vectors in $\mathbb{F}_2^m$ and the extra node $w$. The nodes of the other side are the terms of the polynomial $f= \sum_{i=1}^{k} \left( \prod_{j=1}^{m_i} p_{ij} \right)$. Each term is represented in the above way as an $(m_i+1)$-tuple of integers. There is an edge between vector $\vecc{x}$ and term $t$ if and only if $t(\vecc{x})=1$, and there is an edge between the extra node $w$ and the term $t$ if and only if $t(\vecc{x})=x_1x_2\dots x_m$. It is easy to see that for a vector $\vecc{x}$, $f(\vecc{x})\neq 0$ holds if and only if its degree is odd. The extra node $w$ also has an odd degree because the coefficient of $x_1x_2\dots x_m$ is nonzero due to the assumptions. All nodes in the other side have even degree. In $\Gamma$, the degree of each term $t(\vecc{x})=x_1x_2\dots x_m$ is precisely 2, because it is connected only to the vector $(1,1,\dots,1)$ and to the extra $w$ node. Let $t$ be any other term, and let $x_l$ be a variable not appearing in $t$. Then, if $t$ is connected to $(s_1,s_2,\dots,0,\dots,s_m)$, it is also connected to $(s_1,s_2,\dots,1,\dots,s_m)$, so the degree of these nodes are even. Therefore, odd-degree nodes are precisely the vectors $\vecc{s}$ such that $f(\vecc{s}) \neq 0$ and the extra node $w$. However, the nodes of this graph have exponentially large degrees, and therefore we must exhibit a pairing function between the edges incident to a node. For a node corresponding to the term $t(\vecc{x}) \neq x_1x_2\dots x_m$, we pair up the vector $\vecc{x}$ for which $t(\vecc{x})=1$ to $(x_1,x_2,\dots,1-x_l,\dots x_m)$ where $x_l$ is such a variable which does not appear in $t$. (We choose the smallest such index $l$.) The degree of nodes corresponding to terms $x_1x_2\dots x_m$ in this side is only 2, its edges can be simply paired up. For such node corresponding to a vector $\vecc{x}$ that $f(\vecc{x}) = 0$ holds, we should pair up the terms such that $t(\vecc{x})=1$. Suppose that term $t$ is represented by $(i,a_{i1},\dots, a_{ij}, \dots, a_{i,m_i})$. Denote its block by $g=\prod_{j=1}^{m_i} p_{ij}$. If $g(\vecc{x})=0$, then there is an index $j$ such that $p_{ij}(\vecc{x})=0$. Pick the smallest such $j$. There is an even number of monomials of $p_{ij}$ such that $p_{ij}(\vecc{x})=1$. We pair these monomials by a pairing function $\phi_i$. Then the mate of term $(i,a_{i1},\dots, a_{ij}, \dots, a_{i,m_i})$ is $(i,a_{i1},\dots, \phi_i(a_{ij}),\dots, a_{i,m_i})$. It is a more complicated case when $g(\vecc{x})=1$. Since $f(\vecc{x})=0$, there is an even number of indices $l$, such that $\left( \prod_{j=1}^{m_l} p_{lj} \right)$ is 1 at $\vecc{x}$. We pair these blocks by a pairing function $\phi$. So, for $i$ and every $j=1,\dots ,m_i$, $p_{ij}$ is 1 at $\vecc{x}$, and we can pair all but one monomials of $p_{ij}$ with $p_{ij}(\vecc{x})=1$ by a pairing function $\phi_{ij}$. One of them does not have a mate, denote its index by $\omega_{ij}$. If $a_{ij}=\omega_{ij}$ for all indices $j$, then we define its mate to be $(\phi(i),\omega_{\phi(i),1},\dots, \omega_{\phi(i),m_{\phi(i)}})$. Otherwise there is an index $j$ such that $a_{ij} \neq \omega_{ij}$. Pick the smallest such $j$. Then the mate of $(i,a_{i1},\dots, a_{i,m_i})$ is defined as $(i,a_{i1},\dots,\phi_{ij}(a_{ij}),\dots, a_{i,m_i})$. Observe that this gives a bijection and a correct pairing function. For such node corresponding to a vector $\vecc{x}$ that $f(\vecc{x}) = 1$ holds, we should pair up all but one terms such that $t(\vecc{x})=1$. If $t$ is a term of such block $g=\prod_{j=1}^{m_i} p_{ij}$ that $g(\vecc{x})=0$ holds, it can be paired up similarly to the previous case. If $g(\vecc{x})=1$, we pair these blocks by a pairing function. One of them does not have a mate, denote its index by $\Omega$. If $g$ is not the block with index $\Omega$, the pairing can be similar to the previous case. If $g$ is the block with index $\Omega$, we can pair up the terms similarly to the previous case, only the term $t$ represented by $(\Omega,\omega_{\Omega 1},\dots, \omega_{\Omega,m_\Omega})$ does not have a mate. So we paired up all but one neighbours of the node corresponding to the vector $\vecc{x}$. Finally, we pair up the terms which are connected to the extra node $w$. These are the terms $x_1x_2\dots x_m$. Due to the assumptions, there is a polynomial time pairing function which can pair up all but one terms $x_1x_2\dots x_m$, so it can pair up the nodes which are connected to the extra node $w$. We presented a polynomial algorithm that computes the mate of an edge out of a node, so the proof is complete. \end{proof} \section{Complexity of finding divisible subgraphs} \label{sec:subgraphs} Alon, Friedland and Kalai proved the following corollary of the original Olson's Theorem \ref{olson} and using it in the case $p=2$, they derived the result on $p^d$-divisible subgraphs (Theorem \ref{qdiv}) mentioned in the Introduction. We present their proofs since they also show the reductions between the corresponding computational problems. \begin{corollary}[\cite{reg}] \label{corolson} Let $n,m$ be positive integers and let $p$ be a prime. Let $d_1\geq d_2 \geq \dots \geq d_n\geq 1 $ positive integers and for $i=1,\dots ,n,j=1,\dots ,m$ let $a_{ij}$ be an integer such that $\sum_{i=1}^{n} a_{ij}$ is divisible by $p$ for every $j$ index. If $m > p^{d_n-1}-1 + \sum_{i=1}^{n-1} (p^{d_i} -1)$, then there is a subset $\emptyset \neq J \subseteq \{1,2,\dots,m \}$ such that $\sum_{j\in J} a_{ij}$ is divisible by $p^{d_i}$ for every $i=1,\dots ,n$. \end{corollary} \begin{proof}[Proof in \cite{reg}] For $\ j=1,\dots ,m$, let $b_{ij}=a_{ij}$, if $i=1,\dots ,n-1$ and let $b_{nj}=\frac{1}{p}\left( \sum_{i=1}^{n} a_{ij} \right)$. According to Olson's Theorem \ref{olson}, there is an $\emptyset \neq J \subseteq \{1,2,\dots,m\}$ such that $\sum_{j\in J} b_{ij}$ is divisible by $p^{d_i}$ for every $i=1,\dots ,n-1$ and $\sum_{j\in J} b_{nj}$ is divisible by $p^{d_{n-1}}$ because $m > p^{d_n-1}-1 + \sum_{i=1}^{n-1} (p^{d_i} -1)$. However, $\sum_{j\in J} b_{nj} = \sum_{j\in J} \frac{1}{p}\left( \sum_{i=1}^{n} a_{ij} \right)$ is divisible by $p^{d_{n-1}}$ , so $\sum_{j\in J} \left( \sum_{i=1}^{n} a_{ij} \right)$ is divisible by $p^{d_{n}}$. Because of $d_1\geq d_2 \geq \dots \geq d_n\geq 1$, $\sum_{j\in J} b_{ij} = \sum_{j\in J} a_{ij}$ is divisible by $p^{d_n}$ for every $i=1,\dots ,n-1$, hence $\sum_{j\in J} a_{nj}$ should be divisible by $p^{d_n}$ and we are done. \end{proof} \begin{theorem}[Alon, Friedland, Kalai, \cite{reg}] \label{qdiv} For the maximum number of edges of a graph $G$ on $n$ vertices that contains no nontrivial $p^d$-divisible subgraph, \[ f(n,p^d) = \begin{cases} (p^d-1) \cdot n & \textnormal{ if }p\textnormal{ is an odd prime.}\\ (2^d-1) \cdot n - 2^{d-1} & \textnormal{ if }p=2 \end{cases} \] \end{theorem} \begin{proof}[Proof in \cite{reg}] Here, we only prove the direction $\leq$ of the equality. In \cite{reg}, Alon et al. showed by examples that these bounds are tight. Denote the number of edges of $G$ by $m$. Let $a_{ij}=1$ if and only if the $j^{th}$ edge is incident to the $i^{th}$ vertex, as usual. (That is, $((a_{ij}))$ is the incidence matrix of $G$.) For an odd prime $p$, suppose $m>(p^d-1) \cdot n$. According to Olson's Theorem \ref{olson} with $d_1=d_2=\dots = d_n=d$, there is a nonempty subset $J$ of edges such that $\sum_{j\in J} a_{ij}$ is divisible by $p^d$ for every $i$, so there is nontrivial $p^d$-divisible subgraph. For $p=2$, suppose $m>(2^d-1) \cdot n - 2^{d-1}= (n-1)\cdot (2^d-1) + (2^{d-1}-1) $. According to Corollary \ref{corolson} with $d_1=d_2=\dots = d_n=d$, there is a nonempty subset $J$ of edges such that $\sum_{j\in J} a_{ij}$ is divisible by $p^d$ for every $i$, so there is nontrivial $p^d$-divisible subgraph. The conditions of corollary hold, because $\sum_{i=1}^{n} a_{ij}=2$ for every index $j$. \end{proof} Let us now define the computational problems corresponding to the above theorems. The existence of the solutions is guaranteed by Theorem \ref{qdiv}, Theorem \ref{olson} and Corollary \ref{corolson}, respectively. \begin{center} \fbox{ \parbox{0.85\linewidth}{ \computationalproblem{$2^d$-divisible subgraph.} \begin{tabularx}{\linewidth}{lX} \textit{Input:}& a positive integer $d$ and a graph $G=(V,E)$, where $|V|=n$, $|E|=m$ and $m> n\cdot (2^d - 1 ) - 2^{d-1}$ holds. \\ \textit{Find:}& a $2^d$-divisible subgraph, that is, an $\emptyset \neq F \subseteq E$ such that for every $v \in V$, the number of incident edges of $F$ is divisible by $2^d$. \end{tabularx} }} \end{center} \medskip \begin{center} \fbox{ \parbox{0.85\linewidth}{ \computationalproblem{Olson MOD $2^d$.} \begin{tabularx}{\linewidth}{lX} \textit{Input:}& a positive integer $d$, the integers $n$ and $m$ such that $m> n\cdot (2^d - 1 )$ and given integers $a_{ij}$ ($i=1,\dots ,n , j=1,\dots,m$). \\ \textit{Find:}& a $\emptyset \neq J \subseteq \{1,2,\dots,m\}$ such that $\sum_{j\in J} a_{ij}$ is divisible by $2^d$ for every $i$. \end{tabularx} }} \end{center} \medskip \begin{center} \fbox{ \parbox{0.85\linewidth}{ \computationalproblem{Even-Sum Olson MOD $2^d$.} \begin{tabularx}{\linewidth}{lX} \textit{Input:}& a positive integer $d$, the integers $n$ and $m$ such that $m> n\cdot (2^d - 1 ) - 2^{d-1}$ and given integers $a_{ij}$ ($i=1,\dots ,n , j=1,\dots ,m$) such that $2\mid \sum_{i=1}^n a_{ij}$. \\ \textit{Find:}& a $\emptyset \neq J \subseteq \{1,2,\dots,m\}$ such that $\sum_{j\in J} a_{ij}$ is divisible by $2^d$ for every $i$. \end{tabularx} }} \end{center} \medskip As we have seen in the previous sections, Olson's theorem can be proved via the Combinatorial Nullstellensatz. It implies the following propositions. \begin{theorem} \label{olsred} \textsc{Olson MOD $2^d$} and \textsc{Even-Sum Olson MOD $2^d$} are polynomially reducible to the \textsc{Combinatorial Nullstellensatz over $\mathbb{F}_2$}. Consequently, they are in PPA. \end{theorem} \begin{proof} In the proof of Theorem \ref{genolsontheorem} and Theorem \ref{maintheorem}, we construct a polynomial $f$ in $m$ variables over $\mathbb{F}_2$ such that $\deg(f)=m$ and the coefficient of $\prod_{j=1}^m x_j$ is nonzero. Such vectors $\vecc{s}$ that satisfy $f(\vecc{s})\neq 0$ precisely correspond to the subsets $\emptyset \neq J \subseteq \{1,2,\dots,m\}$ such that $\sum_{j\in J} a_{ij}$ is divisible by $2^d$ for every $i$. We only have to check that this reduction is a polynomial reduction. In the proofs the size of the constructed polynomial is $O(2^d \cdot d \cdot n + m)$, which can be bounded $O(nm\log(m))$ due to condition $m> n\cdot (2^d - 1 )$, so the reduction is polynomial. For reduction to the \textsc{Combinatorial Nullstellensatz over $\mathbb{F}_2$}, we have to present a pairing function which can pair up terms $x_1x_2\dots x_m$. Here it is obvious, because there is only one term $x_1x_2\dots x_m$. Similarly, one can check that \textsc{Even-Sum Olson MOD $2^d$} is also polynomially reducible to the \textsc{Combinatorial Nullstellensatz over $\mathbb{F}_2$}. \end{proof} The reduction in the proof of Theorem \ref{qdiv} immediately implies the following. \begin{theorem} \label{graphred} \textsc{$2^d$-divisible subgraph} is polynomially reducible to \textsc{Even-Sum Olson MOD $2^d$}. Consequently, \textsc{$2^d$-divisible subgraph} is in PPA. \end{theorem} \section{Degree-constrained subgraphs: Louigi's problem} \label{sec:louigi} In Louigi's problem, given are a graph $G=(V,E)$ and forbidden sets $F(v)\subseteq \mathbb{N}$ for every $v\in V$. By an $F$-avoiding subgraph we mean a subgraph $\emptyset \neq E' \subseteq E$ such that for every $v \in V$ the number of incident edges of $E'$ is not in $F(v)$. Shirazi and Verstra\"ete \cite{louigi} proved the following theorem. We give a new proof using our techniques. \begin{theorem}[Shirazi, Verstra\" ete \cite{louigi}] \label{louigi} If $0 \not \in F(v)$ for all $v\in V$ and $\sum_{v\in V} |F(v)| < |E|$, then there exists a nontrivial $F$-avoiding subgraph. \end{theorem} \begin{proof} Let $p$ be a prime greater than the maximum degree in $G$. For the node $v_i\in V $, let $Q_i=\mathbb{Z}_{p} \backslash F(v_i)$ and $a_{ij}=1$ if the node $v_i$ is incident to the edge $e_j \in E$, and 0 otherwise. Due to the conditions, $\sum_{v_i \in V} price(\mathbb{Z}_{p}\backslash Q_i) = \sum_{v_i \in V} | \mathbb{Z}_{p} \backslash Q_i| = \sum_{v\in V} |F(v)| < |E|$, so according to Theorem \ref{genolsontheorem}, there exists a subset $J$, which corresponds to a nontrivial $F$-avoiding subgraph. \end{proof} Note that, in \cite{louigi}, the authors also proved their theorem via the Combinatorial Nullstellensatz, but in a different way via polynomials over $\mathbb{R}$. One may ask a version of Louigi's problem modulo prime powers: given are a prime power $p^d$, a graph $G=(V,E)$ and forbidden sets modulo $p^d$: $F(v)\subseteq \mathbb{Z}_{p^d}$ for every $v\in V$. By an $F$-avoiding subgraph modulo $p^d$ we mean a subgraph $\emptyset \neq E' \subseteq E$ such that for every $v \in V$ the number of incident edges of $E'$ is not congruent to any number in $F(v)$ modulo $p^d$. We can show the following. \begin{theorem} \label{louigimodulo} If $0 \not \in F(v)$ for all $v\in V$ and $\sum_{v\in V} price(F(v)) < |E|$, then there exists a nontrivial $F$-avoiding subgraph modulo $p^d$. \end{theorem} \begin{proof} Similarly to the proof above, for the node $v_i\in V $, let $Q_i=\mathbb{Z}_{p^d} \backslash F(v_i)$ and $a_{ij}=1$ if the node $v_i$ is incident to the edge $e_j \in E$, and 0 otherwise. Due to the conditions, $\sum_{v_i \in V} price(\mathbb{Z}_{p}\backslash Q_i) = \sum_{v\in V} price(F(v)) < |E|$, so according to Theorem \ref{genolsontheorem}, there exists a subset $J$, which corresponds to a nontrivial $F$-avoiding subgraph modulo $p^d$. \end{proof} Frank et al. \cite{frank} gave a polynomial time combinatorial algorithm for finding an $F$-avoiding subgraph as in Theorem \ref{louigi}. For $F$-avoiding subgraph modulo $2^d$, one can show that the search problem belongs to PPA. Let us define the corresponding computational problem. The existence of a solution is guaranteed by Theorem \ref{louigimodulo}. \begin{center} \fbox{ \parbox{0.85\linewidth}{ \computationalproblem{Degree-constrained subgraph modulo $2^d$.} \begin{tabularx}{\linewidth}{lX} \textit{Input:}& a positive integer $d$, a graph $G=(V,E)$, subsets $F(v)\subseteq \mathbb{Z}_{p^d}$ such that $\sum_{v\in V} price(F(v)) < |E|$. \\ \textit{Find:}& a nontrivial $F$-avoiding subgraph modulo $2^d$. \end{tabularx} }} \end{center} \medskip Similarly to the proofs of Theorems \ref{olsred}, \ref{graphred}, the proofs of Theorems \ref{louigimodulo}, \ref{genolsontheorem}, \ref{maintheorem} imply the following. \begin{theorem} \label{louigired} \textsc{Degree-constrained subgraph modulo $2^d$} is polynomially reducible to \textsc{Combinatorial Nullstellensatz over $\mathbb{F}_2$}. Consequently, the problem \textsc{Degree-constrained subgraph modulo $2^d$} is in PPA. \end{theorem} \section*{Acknowledgments} I am grateful to L\'aszl\'o V\'egh for his extremely helpful remarks and valuable suggestions. Also, I would like to thank the anonymous referee for providing constructive comments. \begin{thebibliography}{99} \bibitem{alon} N. Alon: \textit{Combinatorial Nullstellensatz}. Combinatorics, Probability and Computing, 8, 1999, pp. 7-29. \bibitem{ols} J. E. Olson: \textit{A combinatorial problem on finite Abelian groups, I}. Journal of Number Theory, Vol. 1, Issue 1, January 1969, pp. 8-10. \bibitem{reg} N. Alon, S. Friedland, G. Kalai: \textit{Regular subgraphs of almost regular graphs}. Journal of Combinatorial Theory, Series B Vol. 37, Issue 1, August 1984, pp. 79-91. \bibitem{papa} C. H. Papadimitriou: \textit{On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence}. Journal of Computer and System Sciences Vol. 48, Issue 3, June 1994, pp. 498-532. \bibitem{west} D. B. West: \textit{Research Experiences for Graduate Students in Combinatorics (Open Problem Collection)} \url{http://www.math.uiuc.edu/~west/regs/combnull.html} \bibitem{integervalued} P-J. Cahen, J-L. Chabert: \textit{Integer-valued Polynomials}. Mathematical Surveys and Monographs 48, Providence, RI: American Mathematical Society 1997. \bibitem{louigi} H. Shirazi, J. Verstra\"ete: \textit{A note on polynomials and f-factors of graphs}. Electronic J. of Combinatorics, 15, 2008, N22. \bibitem{frank} A. Frank, L. C. Lau, J. Szab\'o: \textit{A note on degree-constrained subgraphs}. Discrete Mathematics, 2008, 308.12, pp. 2647-2648. \bibitem{brink} D. Brink: \textit{Chevalley's theorem with restricted variables}. Combinatorica 2011, 31.1, pp. 127-130. \bibitem{alon2} N. Alon: \textit{Discrete Mathematics: methods and challenges}. Proc. of the International Congress of Mathematicians, Beijing 2002, China, Higher Education Press 2003, pp. 119-135. \bibitem{total} C. H. Papadimitriou, N. Meggido: \textit{On total functions, existence theorems and computational complexity}. Theoretical Computer Science, Vol. 81, Issue 2, 30 April 1991, pp. 317-324. \end{thebibliography} \end{document}