% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P34}{20(1)}{2013} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \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} \newtheorem{Lem}{Lemma} \newtheorem{Def}{Definition} \newtheorem{Them}{Theorem} \newtheorem{Cor}{Corollary} \newtheorem{Prop}{Proposition} \newcommand{\fq}{\mathbb{F}_q} \newcommand{\rmv}[1]{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Partitions and compositions over finite fields} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Muratovi\'{c}-Ribi\'{c}\\ \small Department of Mathematics\\[-0.8ex] \small University of Sarajevo\\[-0.8ex] \small Zmaja od Bosne 33-35, 71000 Sarajevo, Bosnia and Herzegovina\\ \small\tt amela@pmf.unsa.ba\\ \and Qiang Wang \thanks{Supported by NSERC of Canada.}\\ \small School of Mathematics and Statistics\\[-0.8ex] \small Carleton University\\[-0.8ex] \small Ottawa, K1S 5B6, Canada\\ \small\tt wang@math.carleton.ca } \date{\dateline{Aug 31, 2012}{Feb 3, 2013}{Feb 12, 2013}\\ \small Mathematics Subject Classifications: 11B30, 05A15, 11T06} \begin{document} \maketitle \begin{abstract} In this paper we find an exact formula for the number of partitions of an element $z$ into $m$ parts over a finite field, i.e. we find the number of nonzero solutions of the equation $x_1+x_2+\cdots +x_m=z$ over a finite field when the order of terms does not matter. This is equivalent to counting the number of $m$-multi-subsets whose sum is $z$. When the order of the terms in a solution does matter, such a solution is called a composition of $z$. The number of compositions is useful in the study of zeta functions of toric hypersurfaces over finite fields. We also give an application in the study of polynomials of prescribed ranges over finite fields. \end{abstract} %\maketitle \section{Introduction} Let $n$ and $m$ be positive integers. A \emph{composition} of $n$ is an ordered list of positive integers whose sum is $n$. A \emph{$m$-composition} of $n$ is an ordered list of $m$ positive integers ($m$ parts) whose sum is $n$. It is well known that there is a bijection between all $m$-compositions of $n$ and $(m-1)$-subsets of $[n-1] = \{1, 2, \ldots, n-1\}$ and thus there are $\binom{n-1}{m-1}$ $m$-compositions of $n$ and $2^{n-1}$ compositions of $n$. Similarly, a \emph{weak composition} of $n$ is an ordered list of non-negative integers whose sum is $n$ and a \emph{weak $m$-composition} of $n$ is an ordered list of $m$ non-negative parts whose sum is $n$. Using substitution of variables, we can easily obtain that the number of weak $m$-compositions of $n$ (i.e., the number of non-negative integer solutions to $x_1+ x_2 + \cdots + x_m = n$) is equal to the number of $m$-compositions of $n + m$ (i.e., the number of positive integer solutions to $x_1+ x_2 + \cdots + x_m = n+m$), which is $\binom{n+m-1}{m-1} = \binom{n+m -1}{n}$. The combinatorial interpretation of $\binom{n+m-1}{m-1} = \binom{n+m -1}{n}$ is the number of ways in selecting $n$-multisets from a set $M$ with $m$ elements, which is sometimes called $n$-combinations of $M$ with repetitions. Disregarding the order of the summands, we have the concepts of partitions of $n$ into $m$ parts, partitions of $n$ into at most $m$ parts, and so on. For more details we refer the reader to \cite{Stanley}. Let $\fq$ be a finite fields of $q=p^r$ elements. The subset problem over a subset $D \subseteq \fq$ is to determine for a given $z \in \fq$, if there is a nonempty subset $\{x_1, x_2, \ldots, x_m\} \subseteq D$ such that $x_1 + x_2 + \cdots +x_m = z$. This subset sum problem is known to be $NP$-complete. In the study of the subset sum problem over finite fields, Li and Wan \cite{LiWan} estimated the number, $N(m, z, D) = \# \{ \{x_1, x_2, \ldots, x_m\} \subseteq D \mid x_1 + x_2 + \cdots x_m = z \}$, of $m$-subsets of $D \subseteq \fq$ whose sum is $z \in \fq$. In particular, exact formulas are obtained in cases that $D= \fq$ or $\fq^*$ or $\fq \setminus \{0, 1\}$. Similarly, we are interested in the number $S(m, z, D) = \# \{ (x_1, x_2, \ldots, x_m) \in D \times D \times \cdots \times D \mid x_1 + x_2 + \cdots + x_m = z \}$, that is, the number of ordered $m$-tuples whose sum is $z$ and each coordinate belongs to $D \subseteq \fq$, as well as the number $M(m, z, D)$ which counts the number of $m$-multisets of $D \subseteq \fq$ whose sum is $z \in \fq$. In particular, when $D = \fq$ or $\fq^*$, this motivated us to introduce the following. \begin{Def} A \emph{partition} of $z\in \fq $ into $m$ parts is a multiset of $m$ nonzero elements in $\fq^*$ whose sum is $z$. The $m$ nonzero elements are the parts of the partition. We denote by $M(m, z, \fq^*)$ or $\tilde{P}_m(z)$ the number of partitions of $z$ into $m$ parts over $\fq$. Similarly, we denote by $M(m, z, \fq)$ or $\hat{P}_m(z)$ the number of partitions of $z$ into at most $m$ parts over $\fq$ and by $\tilde{P}(z)$ the total number of partitions of $z$ over finite field $\fq$. \end{Def} We remark that $N(m, z, \fq^*)$ is the number of partitions of an element $z$ over finite field $\fq$ such that all summands are distinct, and $M(m, z, \fq^*)$ is the number of partitions of an element $z$ into $m$ parts over finite field $\fq$, dropping the restriction that all summands are distinct. We also remark that in the study of polynomials of prescribed ranges over finite fields \cite{MuWa} there has arisen a need as well for counting the number $M(m, 0, \fq)$ of partitions of $0$ with at most $m$ parts over finite field $\fq$, which in turn leads us to answer a recent conjecture by G\'{a}cs et al on polynomials of prescribed ranges over finite fields \cite{gacsetal}. In this article we first obtain an exact formula for the number of partitions of an element $z \in \fq$ into $m$ parts over $\fq$. \begin{Them}\label{partitions} Let $m$ be a non-negative integer, $\fq$ be a finite field of $q=p^r$ elements with prime $p$, and $z\in \fq$. The number of partitions of $z$ into $m$ parts over $\fq$ is given by $$\tilde{P}_m(z)=\frac{1}{q}\binom{q+m-2}{m}+D_m(z),$$ where \begin{eqnarray*} D_m(z) &= \left\{ \begin{array}{ll} 0, & \mbox{if} ~m\not\equiv 0 ~(\bmod~p) ~\mbox{and}~ m\not\equiv 1 ~(\bmod~p); \\ \frac{q-1}{q}\binom{q/p - 1+j}{j}, & \mbox{if}~ m =jp, j \geq 0, ~\mbox{and} ~z=0 ;\\ -\frac{q-1}{q}\binom{q/p - 1+j}{j}, & \mbox{if}~ m = jp+ 1, j \geq 0, ~\mbox{and} ~z=0 ;\\ -\frac{1}{q}\binom{q/p-1+j}{j}, & \mbox{if}~ m =jp, j \geq 0, ~\mbox{and} ~z \in \fq^*;\\ \frac{1}{q}\binom{q/p-1+j}{j}, & \mbox{if}~ m = jp+ 1, j \geq 0, ~\mbox{and} ~z \in \fq^*. \end{array} \right. \end{eqnarray*} \end{Them} Similarly, we have the following definition of compositions over finite fields. \begin{Def} A \emph{composition} of $z\in \fq $ with $m$ parts is a solution $(x_1, x_2, \ldots, x_m)$ to the equation \begin{equation} \label{eqCompo} z=x_1+x_2+\cdots +x_m, \end{equation} with each $x_i \in \fq^*$. Similarly, a \emph{weak composition} of $z\in \fq $ with $m$ parts is a solution $(x_1, x_2, \ldots, x_m)$ to Equation~(\ref{eqCompo}) with each $x_i \in \fq$. We denote the number of compositions of $z$ having $m$ parts by $S(m, z, \fq^*)$ or $S_m(z)$. The number of weak compositions of $z$ with $m$ parts is denoted by $S(m, z, \fq)$. The total number of compositions of $z$ over $\fq$ is denoted by $S(z)$. \end{Def} A formula for the number of compositions over $\mathbb{F}_p$ can be found on page 295 in \cite{BEW}. A general formula for $S_m(z)$ over $\mathbb{F}_q$ for arbitrary $q$ and nonzero $z$ can be obtained using a remark on the normalized Jacobi sum of the trivial character given in \cite{Conrad} (see Remark 1 on page 144). In fact, the numbers $S_m(1)$ are the simplest example of the number of rational points on an affine toric variety over a finite field (namely a toric hyperplane); see for example \cite{Wan:06}, \cite{Wan:08}, and \cite{Wong:08}. In order to compare with the formula for partitions, we only present a recurrence formula for compositions as follows. \begin{Prop}\label{compositions} Let $m>2$, $\fq$ be a finite field of $q=p^r$ elements with prime $p$, and $z\in \fq$. The number of compositions of $z$ with $m$ parts over $\fq$ is given by $$S_m(z)=(q-1)^{m-2}(q-2)+S_{m-2}(z).$$ It follows that $$S_m(0)=\frac{(q-1)^m+(-1)^m(q-1)}{q}$$ and $$S_m(z)=\frac{(q-1)^m-(-1)^m}{q}, ~~~\mbox{if}~~ z\neq 0.$$ \end{Prop} Using the fact that additive group $(\fq,+)$ is isomorphic to the additive group $(\mathbb{F}_p^r,+)$, we obtain that the numbers of partitions and compositions of elements over $\mathbb{F}_p^r$ are the same as the numbers of partitions and compositions of corresponding elements over $\fq$. Finally, we demonstrate an application of Theorem~\ref{partitions} in the study of polynomials of prescribed range. First let us recall that the {\it range} of the polynomial $f(x) \in \fq[x]$ is a multiset $M$ of size $q$ such that $M = \{ f(x) : x \in \fq \}$ as a multiset (that is, not only values, but also multiplicities need to be the same). Here and also in the following sections we abuse the set notation for multisets as well. In \cite{gacsetal}, there is a nice connection between polynomials with prescribed ranges and hyperplanes in vector spaces over finite fields. We refer the reader to this paper for more details. In this paper, we obtain the following result as an application of Theorem~\ref{partitions}. \begin{Them} \label{main} Let $\fq$ be a finite field of $q =p^r$ elements. For every $\ell$ with $\frac{q}{2}\leq \ell < q-3$ there exists a multiset $M$ with $\sum_{b\in M} b =0$ and the highest multiplicity $\ell$ achieved at $0\in M$ such that every polynomial over the finite field $\fq$ with the prescribed range $M$ has degree greater than $\ell $. \end{Them} We note that Theorem~\ref{main} generalizes Theorem 1 in \cite{MuWa} which disproves Conjecture 5.1 in \cite{gacsetal}. In the following sections, we give the proofs of Theorems~\ref{partitions}-\ref{main} respectively. \section{Proof of Theorem~\ref{partitions}} In this section we prove Theorem~\ref{partitions}. First of all we prove a few technical lemmas. \begin{Lem}\label{lemma 1} Let $a\in \mathbb{F}_q^*$ and $m$ be a positive integer. Then $\tilde{P}_m(a)=\tilde{P}_m(1)$. \end{Lem} \begin{proof} Let $x_1+x_2+\cdots +x_m=1$. The following mapping between two multisets defined by $$\{x_1,x_2,\ldots ,x_m\}\mapsto \{ax_1,ax_2,\ldots,ax_m\}$$ for some $a\in \fq^*$ is one-to-one and onto, which results in $ax_1+ax_2+\ldots +ax_m=a$. Thus $\tilde{P}_m(a)=\tilde{P}_m(1)$. \end{proof} It is obvious to see that $\tilde{P}_1(z)=1$ if $z\in \fq^*$ and $\tilde{P}_1(0)=0$. However, we can show that $\tilde{P}_m(0)=\tilde{P}_m(z)$ if $m\not\equiv 0~(\bmod ~p)$ and $m\not\equiv 1 ~(\bmod~ p)$ as follows. \begin{Lem} \label{equality} Let $m$ be any positive integer satisfying $m\not\equiv 0~(\bmod ~p)$ and $m\not\equiv 1 ~(\bmod~ p)$. Then $\tilde{P}_m(0)=\tilde{P}_m(1)$. \end{Lem} \begin{proof} Let $x_1+x_2+\cdots +x_m=0$ be a partition of $0$ into $m$ parts. Then $(x_1+1)+(x_2+1)+\cdots +(x_m+1)=m$ is a partition of $m\in \fq^*$ with at most $m$ parts (if $x_j=p-1$ then $x_j+1=0$), but since $x_j\neq 0$ there is no $x_j+1=1$. Moreover, there is a bijective correspondence of multisets $\{x_1,\ldots,x_m\}\mapsto \{x_1+1,\ldots,x_m+1\}$. Therefore, in order to find the number $\tilde{P}_m(0)$ of partitions of $0$ into $m$ parts over $\fq$, we need to find the number of partitions of $m$ with at most $m$ parts but no element is equal to $1$. This means these partitions of $m$ can have parts equal to the zero. Let $x_1+x_2+\cdots +x_m=m$. We assume that the parts equal to 1 (if any) appear in the beginning of the list: $x_1,x_2,\ldots,x_m$. If $x_1=1$ then $x_1+ x_2 + \cdots +x_m=m$ implies $x_2+\cdots +x_m=m-1$. Conversely, each partition of $m$ into $m-1$ parts can generate a partition of $m$ into $m$ parts with the first part equal to $1$. So the number of partitions of $m$ into $m$ parts with at least one part equal to 1 is equal to the number of partitions of $m-1$ into $m-1$ parts. Let $U_0$ be the family of partitions of $m$ into $m$ parts without zero elements and no part is equal to $1$. Therefore $|U_0|=\tilde{P}_m(m)-\tilde{P}_{m-1}(m-1)$. \par Let $U_1$ be the family of partitions of $m$ with $m$ parts with exactly one element equal to $0$ and no element equal to $1$. Let $x_1+x_2+\cdots +x_m=m$ be a partition in $U_1$ and $x_1=0$ and $x_j \neq 0, 1$ for $j=2, \ldots, m$. Obviously, it is equivalent to a partition $x_2+\cdots +x_m=m$ of $m$ into $m-1$ parts with all parts not equal to $1$. Similarly as in the case for $U_0$ we have $|U_1|=\tilde{P}_{m-1}(m)-\tilde{P}_{m-2}(m-1)$. More generally, let $U_i$ be the family of partitions with $m$ parts with $i$ parts equal to the zero, say $x_1=x_2=\ldots =x_i=0$, and $x_{j} \neq 0, 1$ for $j=i+1, \ldots, m$. Then we have a partition of $m$ into $m-i$ parts, $x_{i+1}+\cdots +x_m=m$, such that no part is equal to $1$. Similarly, we have $|U_i|=\tilde{P}_{m-i}(m)-\tilde{P}_{m-i-1}(m-1)$. In particular, for $i=m-1$ there is only one solution of the equation $x_m=m$ and thus $|U_{m-1}|= \tilde{P}_1(m)=1$. We note that these families of $U_i$'s are pairwise disjoint and their union is the family of partitions of $m$ into $m$ parts with no part equal to $1$. Therefore we have $\tilde{P}_m(0)=|U_0|+|U_1|+\cdots +|U_{m-1}|= (\tilde{P}_m(m)-\tilde{P}_{m-1}(m-1))+(\tilde{P}_{m-1}(m)-\tilde{P}_{m-2}(m-1))+\cdots +(\tilde{P}_2(m)-\tilde{P}_1(m-1))+\tilde{P}_1(m)$. If $m\not\equiv 0~(\bmod ~p)$ and $m\not\equiv 1 ~(\bmod~ p)$, then $m-1$ and $m$ are both nonzero elements in $\fq$. By Lemma~\ref{lemma 1}, we can cancel $\tilde{P}_{i}(m-1)=\tilde{P}_{i}(m)$ for $i=1, \ldots, m-1$. Hence $\tilde{P}_m(0) = \tilde{P}_m(m) = \tilde{P}_m(1)$. \end{proof} Using the above two lemmas, we obtain the exact counts of $\tilde{P}_m(z)$ when $m\not\equiv 0~(\bmod ~p)$ and $m\not\equiv 1 ~(\bmod~ p)$. \begin{Lem}\label{equality1} If $z\in \fq $ and $m$ is any positive integer satisfying $m\not\equiv 0~(\bmod ~p)$ and $m\not\equiv 1 ~(\bmod~ p)$ then we have $$\tilde{P}_m(z) = \frac{1}{q}\binom{q+m-2}{m}.$$ \end{Lem} \begin{proof} We note that there are $\binom{(q-1)+m-1}{m}$ multisets of $m$ nonzero elements from $\fq $ in total and the sum of elements in each multiset can be any element in $\fq$. Using Lemmas~\ref{lemma 1} and \ref{equality} we have $$\sum_{s\in \fq}\tilde{P}_m(s)=q\tilde{P}_m(1)=\binom{(q-1)+m-1}{m}$$ and therefore $$\tilde{P}_m(z)=\tilde{P}_m(1)=\frac{1}{q}\binom{q+m-2}{m}$$ for every $z\in \fq $. \end{proof} In order to consider other cases, we use an interesting result by Li and Wan \cite{LiWan}, which gives the number $N(k,b,\fq^*)$ of sets with (all distinct) $k$ nonzero elements that sums to $b\in \fq$. Namely, \begin{equation}\label{N} N(k,b,\fq^*)=\frac{1}{q}\binom{q-1}{k}+(-1)^{k+\lfloor k/p\rfloor}\frac{\nu (b)}{q}\binom{q/p-1}{\lfloor k/p \rfloor}, \end{equation} where $\nu(b)=-1$ if $b\neq 0$ and $\nu(b)=q-1$ if $b=0$ (see Theorem 1.2 in \cite{LiWan}). First we can prove \begin{Lem}\label{inclusion-exclusion} Let $N(k,b,\fq^*)$ be the number of sets with $k$ nonzero elements that sums to $b\in \fq$ and $m > 1$ be a positive integer. Then \begin{eqnarray*} \tilde{P}_m(0) &=& \left((q-1)N(1,1, \fq^*)\tilde{P}_{m-1}(1)+N(1,0,\fq^*)\tilde{P}_{m-1}(0) \right) \\ &&-\left((q-1)N(2,1,\fq^*)\tilde{P}_{m-2}(1)+N(2,0,\fq^*)\tilde{P}_{m-2}(0)\right)\\ &&+\ldots \\ &&+(-1)^{m-1} \left((q-1)N(m-2, 1,\fq^*)\tilde{P}_2(1)+N(m-2, 0, \fq^*)\tilde{P}_{2}(0)\right) \\ &&+(-1)^m (q-1)N(m-1,1,\fq^*) +(-1)^{m+1}N(m,0,\fq^*). \end{eqnarray*} \end{Lem} \begin{proof} Denote by $\mathcal{U}$ the family of all multisets of $m$ nonzero elements that sums to zero, i.e. $\tilde{P}_m(0)=|\mathcal{U}|$. Let $\mathcal{B}_a$ be the family of all multisets of $m$ nonzero elements such that $a$ is a member of each multiset and the sum of elements of each multiset is equal to $0$. Namely, $B_a\in \mathcal{B}_a$ implies $\sum_{s\in B_a}s=0$ and $a\in B_a$. Obviously, $\mathcal{U}=\bigcup_{a\in \fq^*}\mathcal{B}_a$. \par Now we will use the principle of inclusion-exclusion to find the cardinality of $\mathcal{U}$. For distinct $a_1, \ldots, a_k \in \fq^*$ and $k > m$, it is easy to see that $$\mathcal{B}_{a_1}\cap\mathcal{B}_{a_2}\cap\ldots \cap\mathcal{B}_{a_k}=\emptyset, $$ because each multiset $B_{a_1}$ contains only $m$ nonzero elements. Moreover, if $k=m$ then the number of multisets in the union of intersections is $N(m,0,\fq^*)$. If $B\in \mathcal{B}_{a_1}\cap\mathcal{B}_{a_2}\cap\ldots \cap\mathcal{B}_{a_k}$ and $k \leq m -1$ then $$B=\{a_1,a_2,\ldots,a_k, x_{k+1},\ldots,x_m\}.$$ Because $x_{k+1}+\cdots + x_m=-(a_1+\cdots +a_k)$, the number of elements in the intersection $\mathcal{B}_{a_1}\cap\mathcal{B}_{a_2}\cap\ldots \cap\mathcal{B}_{a_k}$ is the same as the number of partitions of $-(a_1+\cdots +a_k)$ into $m-k$ parts, i.e. $$|\mathcal{B}_{a_1}\cap\mathcal{B}_{a_2}\cap\ldots \cap\mathcal{B}_{a_k}|=\tilde{P}_{m-k}(-a_1-\cdots -a_k).$$ We note that none of $a_i$'s ($i=1, \ldots, k$) is equal to zero and $N(k, b,\fq^*) = N(k, 1, \fq^*)$ for any $b\in \fq^*$. In particular, if $k < m-1$, then the sum $a_1 + \cdots + a_{m-1}$ can be any element in $\fq$ and thus there are $(q-1)N(k,1,\fq^*)\tilde{P}_{m-k}(1)+N(k,0,\fq^*)\tilde{P}_{m-k}(0)$ such multisets $B\in \mathcal{B}_{a_1}\cap\mathcal{B}_{a_2}\cap\ldots \cap\mathcal{B}_{a_k}$ for all choices of nonzero distinct $a_1, \ldots, a_k$. If $k=m-1$ then the sum $a_1 + \cdots + a_{m-1}$ can not be equal to the zero, there are in total $(q-1)N(m-1,1,\fq^*)$ such multisets contained in the intersection of $m-1$ families of $\mathcal{B}_{a_i}$'s. Finally we combine the above cases and use the principle of inclusion-exclusion to complete the proof. \end{proof} In the sequel we also need the following identity which is a special instance of Chu-Vandermonde identity. \begin{Lem} \label{Mc Claren} For all positive integers $s$, we have $$\sum_{j=1}^s(-1)^{j+1}\binom{q-1}{j}\binom{q-2+s-j}{s-j}=\binom{q-2+s}{s}$$ \end{Lem} \begin{proof} The result follows from Chu-Vandermonde theorem $_2 F_1(-s;-(q - 1);-(q - 2 + s); 1) = 0$. % For the sake of completeness, Here we also include a direct proof. Multiplying $(1+x)^{q-1}=\sum_{k=0}^{q-1}\binom{q-1}{j}x^j$ and series $$\frac{1}{(1+x)^{q-1}}=\sum_{k=0}^\infty \binom{q-2+k}{k}(-1)^k x^k,$$ We obtain $$1=(1+x)^{q-1}\cdot\frac{1}{(1+x)^{q-1}}=\Bigl(\sum_{k=0}^{q-1}\binom{q-1}{j}x^j\Bigr)\Bigl(\sum_{k=0}^\infty \binom{q-2+k}{k}(-1)^k x^k\Bigr)=$$ $$\sum_{s=0}^\infty \Bigl(\sum_{j=0}^s(-1)^{s-j}\binom{q-1}{j}\binom{q-2+s-j}{s-j}\Bigr)x^s.$$ Therefore for $s\geq 1$ we have $\sum_{j=0}^s(-1)^{s-j}\binom{q-1}{j}\binom{q-2+s-j}{s-j}=0$. This implies $$\sum_{j=1}^s(-1)^{s-j+1}\binom{q-1}{j}\binom{q-2+s-j}{s-j}=(-1)^s\binom{q-2+s}{s}.$$ Finally multiplying both sides of the last equality by $(-1)^s$ we complete the proof. \end{proof} \par Next we prove Theorem~\ref{partitions}. In order to do so, we let \begin{equation} \label{relation} \tilde{P}_m(z)=\frac{1}{q}\binom{q-2+m}{m}+D_m(z). \end{equation} Without loss of generality, we can assume $q>2$. Obviously, by Lemma~\ref{equality1}, we have $D_m(z)=0$ for any $z\in \fq$ if $m\not\equiv 0~(\bmod ~p)$ and $m\not\equiv 1~(\bmod ~p)$. Further $D_m(z)=D_m(1)$ by Lemma~\ref{lemma 1} for all $z\neq 0$. Because $\tilde{P}_m(0)+(q-1)\tilde{P}_m(1)=\binom{q-2+m}{m}$, we have \begin{equation}\label{Dequality} D_m(0)+(q-1)D_m(1)=0, ~\text{i.e.,}\quad D_m(1)=-\frac{1}{q-1}D_m(0).\end{equation} Next we use the convention that $\tilde{P}_0(0)=1$ and $\tilde{P}_0(1)=0$ so that $D_0(0)=\frac{q-1}{q}$ and $D_0(1)=-\frac{1}{q}$. Similarly, $\tilde{P}_1(0)=0$ and $\tilde{P}_1(1)=1$ and thus $D_1(0)=-\frac{q-1}{q}$ and $D_1(1)=\frac{1}{q}$. For the rest of this section, we only need to compute $D_m(0)$ when $m= jp$ or $m=jp+1$ for some positive integer $j$ because of Equation~(\ref{Dequality}). To do this, we apply Lemmas~\ref{inclusion-exclusion} and \ref{Mc Claren}, along with Equations~(\ref{N}) (\ref{relation}), and the following equation \begin{equation}\label{Nsum} (q-1)N(m,1,\fq^*)+N(m,0,\fq^*)=\binom{q-1}{m}.\end{equation} Let us consider $m=up$ first. In this case, by Lemma~\ref{inclusion-exclusion} and Equation~(\ref{relation}), we have: \begin{eqnarray*} \tilde{P}_m(0)&=&\sum_{s=1}^{m-2}(-1)^{s+1}\left[\frac{1}{q}\binom{q-2+m-s}{m-s}\left((q-1)N(s,1,\fq^*) +N(s, 0,\fq^*)\right) \right.\\ && \left. +(q-1)N(s, 1,\fq^*)D_{m-s}(1)+N(s, 0, \fq^*)D_{m-s}(0) \right]\\ &&+(-1)^m (q-1)N(m-1,1,\fq^*)+(-1)^{m+1}N(m,0,\fq^*). \end{eqnarray*} Using Equations~(\ref{Nsum}) and (\ref{N}), we obtain \begin{eqnarray*} \tilde{P}_m(0)&=& \frac{1}{q}\sum_{s=1}^{m-2}(-1)^{s+1}\binom{q-1}{s}\binom{q-2+m-s}{m-s} \\ &&+\sum_{s=1}^{m-2}(-1)^{s+1}\frac{1}{q}\binom{q-1}{s} \left((q-1)D_{m-s}(1)+D_{m-s}(0)\right)\\ &&+ \sum_{s=1}^{m-2}(-1)^{s+1} (q-1)(-1)^{s+\lfloor s/p\rfloor }\frac{1}{q}\binom{q/p-1}{\lfloor s/p\rfloor} \left(-D_{m-s}(1)+D_{m-s}(0) \right) \\ &&+(-1)^m(q-1)\frac{1}{q}\binom{q-1}{m-1}+(-1)^{m+1}\frac{1}{q}\binom{q-1}{m}\\ &&+(-1)^m(q-1)(-1)^{m-1+\lfloor (m-1)/p\rfloor}\frac{-1}{q}\binom{q/p-1}{\lfloor (m-1)/p\rfloor}\\ &&+(-1)^{m+1}(-1)^{m+\lfloor m/p\rfloor}\frac{q-1}{q} \binom{q/p-1}{\lfloor m/p\rfloor} \end{eqnarray*} After rearranging terms, we use Lemma~\ref{Mc Claren}, Lemma~\ref{equality1}, Equations~(\ref{relation}) and (\ref{Dequality}) to simplify the above as follows: \begin{eqnarray*} &=& \frac{1}{q}\sum_{s=1}^{m}(-1)^{s+1}\binom{q-1}{s}\binom{q-2+m-s}{m-s}\\ &&+ \sum_{\begin{array}{c} 1\leq s\leq m-2\\ s\equiv 0,1 (\bmod{p}) \end{array}} (-1)^{s+1} (-1)^{s+\lfloor s/p\rfloor }\binom{q/p-1}{\lfloor s/p\rfloor}D_{m-s}(0)\\ &&+(-1)^{u-1}\frac{q-1}{q}\bigl[\binom{q/p-1}{u-1}+\binom{q/p-1}{u}\bigr]\\ &=&\frac{1}{q}\binom{q-2+up}{up} + \sum_{\begin{array}{c} 1\leq s\leq up \\ s\equiv 0,1(\bmod{p}) \end{array} }(-1)^{1+\lfloor s/p \rfloor }\binom{q/p-1}{\lfloor s/p\rfloor}D_{up-s}(0),\\ \end{eqnarray*} where we use Lemma~\ref{Mc Claren} and $-D_0(0)=D_1(0)=-\frac{q-1}{q}$ to obtain the last equality. Now let us rewrite this as \begin{eqnarray} \label{eq1} \tilde{P}_{up}(0)&=&\frac{1}{q}\binom{q-2+up}{up} +\sum_{t=0}^{u-1}(-1)^{1+(u-t)}\binom{q/p-1}{u-t}D_{tp}(0) \nonumber \\ &&+\sum_{t=0}^{u-1}(-1)^{(u-t)}\binom{q/p-1}{u-t-1}D_{tp+1}(0). \end{eqnarray} Similarly, for $m=up+1$, we have \begin{align*} \tilde{P}_{up+1}(0) &=\frac{1}{q}\binom{q-2+(up+1)}{up+1}+ \sum_{ \begin{array}{c} 1\leq s\leq up-1 \\ s\equiv 0,1(\bmod{p}) \end{array} }(-1)^{1+\lfloor s/p \rfloor }\binom{q/p-1}{\lfloor s/p\rfloor}D_{up+1-s}(0) \\ &= \frac{1}{q}\binom{q-2+up+1}{up+1}+\sum_{t=1}^{u-1}(-1)^{1+u-t}\binom{q/p-1}{u-t} \left( D_{tp}(0) + D_{tp+1}(0) \right) -D_{up}(0). \end{align*} Next we show $D_{up+1}(0)=-D_{up}(0)$ for all $u \geq 0$ by mathematical induction. The base case $u=0$ holds because $D_1(0) = D_0(0) = -\frac{q-1}{q}$. Assume now $-D_{sp}(0)=D_{sp+1}(0)$ for all $0\leq s< u$ and plug into the above formula we obtain $$\tilde{P}_{up+1}(0)=\frac{1}{q}\binom{q-2+up+1}{up+1}-D_{up}(0)$$ Because $\tilde{P}_{up+1}(0)=\frac{1}{q}\binom{q-2+up+1}{up+1}+ D_{up+1}(0)$, we conclude that $D_{up+1}(0)=-D_{up}(0)$. Hence it is true for all $u \geq 0$. Using this relation we simplify Equation~(\ref{eq1}) to \begin{eqnarray} \tilde{P}_{up}(0) &=& \frac{1}{q}\binom{q-2+up}{up}+\sum_{t=0}^{u-1}(-1)^{u-t+1} \left(\binom{q/p-1}{u-t}+\binom{q/p-1}{u-t-1}\right)D_{tp}(0) \nonumber \\ &=& \frac{1}{q}\binom{q-2+up}{up}+\sum_{t=0}^{u-1}(-1)^{u-t+1}\binom{q/p}{u-t}D_{tp}(0) \end{eqnarray} and by using $\tilde{P}_{up}(0)=\frac{1}{q}\binom{q-2+up}{up}+D_{up}(0)$ we obtain \begin{equation}\label{recursionD}D_{up}(0)=\sum_{t=0}^{u-1}(-1)^{u-t+1}\binom{q/p}{u-t}D_{tp}(0).\end{equation} Let $f(x)=\sum_{j=0}^\infty D_{jp}(0)x^j$ be the generating function of the sequence $\{D_{up}(0) : u =0,1, 2, \ldots\}$. Then \begin{eqnarray*} (1-x)^{q/p}f(x)&=&\left(\sum_{l=0}^{q/p}\binom{q/p}{l}(-1)^lx^l \right) \left(\sum_{j=0}^\infty D_{jp}(0)x^j \right)\\ &=&D_0(0)+\sum_{u=1}^\infty \left( \left(\sum_{t=0}^{u-1}\binom{q/p}{u-t}(-1)^{u-t}D_{tp}(0) \right)+D_{up}(0) \right)x^u \\ &=& D_0(0)+\sum_{u=1}^\infty (-D_{up}(0)+D_{up}(0))x^u=D_0(0)=\frac{q-1}{q}. \end{eqnarray*} Now $(1-x)^{q/p}f(x)=\frac{q-1}{q}$ implies $$f(x)=\frac{q-1}{q}\frac{1}{(1-x)^{q/p}}=\frac{q-1}{q}\sum_{t=0}^\infty \binom{q/p-1+t}{t}x^t.$$ Hence $D_{jp}(0)=\frac{q-1}{q}\binom{q/p-1+j}{j}$ for $j=0,1,2\ldots$. Moreover, we use Equation~(\ref{Dequality}) and $D_{jp+1}(0) = -D_{jp}(0)$ to conclude $$D_{jp}(0)=\frac{q-1}{q}\binom{q/p-1+j}{j};\qquad D_{jp}(1)=-\frac{1}{q}\binom{q/p-1+j}{j};$$ $$D_{jp+1}(0)=-\frac{q-1}{q}\binom{q/p-1+j}{j};\qquad D_{jp+1}(1)=\frac{1}{q}\binom{q/p-1+j}{j}.$$ Finally, together with Lemma~\ref{equality1} we complete the proof of Theorem~\ref{partitions}. Finally we note that it is straightforward to derive the following corollary. \begin{Cor} Let $m$ be a non-negative integer, $\fq$ be a finite field of $q=p^r$ elements with prime $p$, and $z\in \fq$. The number of partitions of $z$ into at most $m$ parts over $\fq$ is given by $$\hat{P}_m(z)=\sum_{k=0}^m\tilde{P}_k(z)=\frac{1}{q}\binom{q-1+m}{m}+\tilde{D}_m(z),$$ where \begin{eqnarray*} \tilde{D}_m(z) &= \left\{ \begin{array}{ll} D_m(z), & \mbox{if} ~ m \equiv 0 ~(\bmod~ p);\\ 0, & otherwise. \end{array} \right. \end{eqnarray*} \end{Cor} \section{Proof of Theorem~\ref{main}} Let $\ell = q-m$. The assumption $\frac{q}{2} \leq \ell < q-3$ implies that $4 \leq m \leq \frac{q}{2}$. As in \cite{MuWa}, we denote by $\mathcal{T}$ the family of all subsets of $\fq $ of cardinality $m$, i.e., $$\mathcal{T}=\{T \mid T\subseteq \fq, |T|=m\}.$$ Denote by $\mathcal{M}$ the family of all multisets $M$ of order $q$ containing $0$ with the highest multiplicity $\ell = q- m$ and the sum of elements in $M$ is equal to $0$, i.e., $$ \mathcal{M}=\{M \mid 0\in M, \text{ multiplicity}(0)=q-m, \sum_{b\in M}b=0\}. $$ We note that the polynomial with the least degree $q-m$ such that it sends $q-m$ values to $0$ can be represented by \begin{equation} \label{poly} f_{(\lambda,T)}(x)=\lambda \prod_{s\in \fq\setminus T}(x-s), \end{equation} which uniquely determines a mapping \begin{equation}\label{mapping} \mathcal{F}:\fq^* \times \mathcal{T}\rightarrow \mathcal{M}, \end{equation} defined by $$(\lambda,T)\mapsto \text{range}(f_{\lambda, T}(x)).$$ In Lemma 2 \cite{gacsetal} we found an upper bound for the number $|\text{range}(\mathcal{F})|$ of the images of the polynomial with the least degree $q-m$ such that it sends $q-m$ values to $0$, when $m < p$. Using this upper bound, we proved that, for every $m$ with $3 < m \leq \min\{p-1, q/2\}$, there exists a multiset $M$ with $\sum_{b\in M} b =0$ and the highest multiplicity $q-m$ achieved at $0\in M$ such that every polynomial over $\fq$ with the prescribed range $M$ has degree greater than $q-m$ (Theorem ~1, \cite{MuWa}). This result disproved Conjecture 5.1 in \cite{gacsetal}. In this section, we drop the restriction of $m 1}\phi(i)\binom{\frac{q-1}{i}}{\frac{m-1}{i}}+\frac{\delta (q-1)}{q}\binom{q/p}{m/p},$$ where $\delta=1$ if $p\mid m$ and zero otherwise. \end{Lem} \begin{proof} As in Lemma 2 of \cite{gacsetal} we consider the group $\mathcal{G}$ of all non-constant linear polynomials in $\fq[x]$ acting on the set $\fq^*\times \mathcal{T}$ with action $\Phi :(cx+b,(\lambda,T))\mapsto (c^{m-1}\lambda,cT+b)$. All the elements of the same orbit in $\fq^*\times \mathcal{T}$ are all mapped to the same range $M\in \mathcal{M}$. Thus we need to find the number $N$ of orbits under this group action. Using the Burnside's Lemma, we need to find the number of fixed points $|(\fq^*\times \mathcal{T})_g|$ in $\fq^*\times \mathcal{T}$ under the action of $g(x) = cx+b$. As in Lemma 2 \cite{gacsetal}, for $g(x)=x$ there are $(q-1)\binom{q}{m}$ elements fixed by $g(x)$. Moreover, if $g(x)=cx+b$, $c\neq 1$ then elements are fixed by $g(x)$ only if $i = ord(c) \mid d = \gcd (q-1, m-1)$ and in this case we have $|(\fq^*\times \mathcal{T})_g|=(q-1)\binom{\frac{q-1}{i}}{\frac{m-1}{i}}$. Under the assumption $m 0,i\mid d}\phi(i)\binom{\frac{q-1}{i}}{\frac{m-1}{i}}+ \delta (q-1)^2\binom{q/p}{m/p}\Bigr)\\ &=&\frac{1}{q}\binom{q}{m}+\sum_{i>0,i\mid d}\phi(i)\binom{\frac{q-1}{i}}{\frac{m-1}{i}}+\frac{\delta (q-1)}{q}\binom{q/p}{m/p}. \end{eqnarray*} \end{proof} In order to prove Theorem~\ref{main} it is clear that we only need to show \begin{equation}\label{Gacseq} \frac{(q-1)(q-2)\ldots (q-m+1)}{m!}+\sum_{i\mid d,~ i >1} \phi(i)\binom{\frac{q-1}{i}}{\frac{m-1}{i}}+\frac{\delta (q-1)}{q}\binom{q/p}{m/p} <\tilde{P}_m(0).\end{equation} By Theorem~\ref{partitions}, it is enough to show \begin{equation}\label{Gacseq1} \frac{(q-1)\ldots (q-m+1)}{m!}+\sum_{i\mid d,~ i >1} \phi(i)\binom{\frac{q-1}{i}}{\frac{m-1}{i}}+\frac{q-1}{q}\binom{\frac{q}{p} - 1+j}{j}< \frac{1}{q}\binom{q+m-2}{m}. \end{equation} for $m = jp + 1$ and \begin{equation}\label{Gacseq0} \frac{(q-1)(q-2)\ldots (q-m+1)}{m!}+\sum_{ i\mid d,~ i >1 }\phi(i)\binom{\frac{q-1}{i}}{\frac{m-1}{i}} < \frac{1}{q}\binom{q+m-2}{m}, \end{equation} for all other cases, because $\frac{q-1}{q}\binom{q/p}{m/p} = \frac{q-1}{q}\binom{q/p}{j} \leq \frac{q-1}{q}\binom{q/p - 1+j}{j}$ when $m=jp$ and $j\geq1$. For the cases $m=4$ and $m=5$, because $q\geq 2m$, we can check directly that Inequality~(\ref{Gacseq0}) holds and thus Inequality~(\ref{Gacseq}) holds. \par We now show Inequalities~(\ref{Gacseq1}) and ~(\ref{Gacseq0}) hold for $m>5$ by using a combinatorial argument. Let $G=$ be a cyclic group of order $q-1$ with generator $a$. Let $\mathcal{M^\prime}$ be the set of all multisets with $m$ elements chosen from $G$. Then $|\mathcal{M^\prime}|=\binom{q-2+m}{m}$. To estimate the left hand side of Inequalities~(\ref{Gacseq1}) and ~(\ref{Gacseq0}) we count now the number of multisets in some subsets of $\mathcal{M^\prime}$ defined as follows. These subsets of multisets of $m$ elements are defined from subsets of $k$-subsets of $G$ when $k \leq m$. First of all, let $\mathcal{M}_0$ be the set of all subsets of $G$ with $m$ elements. So $\mathcal{M}_0 \subseteq \mathcal{M^\prime}$ and $|\mathcal{M}_0 |= \binom{q-1}{m}$. Let $\mathcal{A}$ be the set of all subsets of $G$ with $m-1$ elements. For each $A=\{a^{u_1},a^{u_2}, $ $\ldots,a^{u_{m-1}}\} \in \mathcal{A}$ where $0\leq u_1i \geq 2$ and $i\mid d$, we let $S_i=$ be a cyclic subgroup of $G$ with $\frac{q-1}{i}$ elements. From each set $\mathcal{C}_i$ of all subsets of $S_i$ with $\frac{m-1}{i}$ elements, we can define two disjoint subclasses of $\mathcal{M}$ containing multisets with $m$ elements in $G$ corresponding to $\mathcal{C}_i$. First, let $B=\{a^{u_1i},a^{u_2i},\ldots, a^{u_{\frac{m-1}{i}}i}\}$ be a subset of $S_i$ where $0\leq u_11 \end{array} }$}\mathcal{M}_i\Bigg) \bigcup \mathcal{M}_m \Bigg | \\ &=&\binom{q}{m}+q\sum_{{i\mid d, ~i >1} }\phi(i)\binom{\frac{q-1}{i}}{\frac{m-1}{i}}+ \delta^\prime (q-1)\binom{q/p+(m-1)/p-1}{(m-1)/p}. \end{eqnarray*} We note that the multiset $\{1,1,1,a,a^2,\ldots,a^{m-3}\}$ is not included in the $\mathcal{M}_{LHS}$ and thus $|\mathcal{M}_{LHS}|<|\mathcal{M^\prime}|$. Dividing both sides by $q$, we have \begin{equation} \label{upperbound} \frac{1}{q} \binom{q}{m}+\sum_{{i\mid d,~ i >1} }\phi(i)\binom{\frac{q-1}{i}}{\frac{m-1}{i}}+\frac{\delta^\prime (q-1)}{q}\binom{q/p+(m-1)/p-1}{(m-1)/p} <\frac{1}{q} \binom{q+m-2}{m}. \end{equation} Hence both Inequalities~(\ref{Gacseq1}) and (\ref{Gacseq0}) are satisfied. This completes the proof of Theorem~\ref{main}. \subsection*{Acknowledgements} We would like to thank the anonymous referees for helpful suggestions, in particular, for pointing out the reference \cite{Conrad}, and also thank Keith Conrad for useful suggestions and for bringing the papers \cite{Wan:06,Wan:08,Wong:08} to our attention. \begin{thebibliography}{10} \bibitem{BEW} B. C. Berndt, R. J. Evans, K. S. Williams, Gauss and Jacobi sums. %Canadian Mathematical Society Series of Monographs and Advanced %Texts. A Wiley-Interscience Publication. John Wiley \& Sons, Canadian Math. Soc. Series of Monographs and Advanced Texts. John Wiley \& Sons, New York, 1998. \bibitem{Conrad} K. Conrad, Jacobi sums and Stickelberger's congruence, {\it Enseign. Math.} \textbf{41} (1995), 141-153. \bibitem{gacsetal} A. G\'{a}cs, T. H\'{e}ger, Z. L. Nagy, D. P\'{a}lv\"{o}lgyi, Permutations, hyperplanes and polynomials over finite fields, {\it Finite Field Appl.} \textbf{16} (2010), 301-314. \bibitem{LiWan} J. Li and D. Wan, On the subset sum problem over finite fields, {\it Finite Field Appl.}, \textbf{14} (2008), 911-929. \bibitem{MuWa} A. Muratovi\'{c}-Ribi\'{c} and Q. Wang, On a conjecture of polynomials with prescribed range, {\it Finite Field Appl.}, \textbf{18} (2012), no. 4, 728–737. \bibitem{Wan:06} D. Wan, Mirror symmetry for zeta functions, In Mirror Symmetry V, AMS/IP Studies in Advanced Mathematics, Vol.38, 2006, 159-184. \bibitem{Wan:08} D. Wan, Lectures on zeta functions over finite fields (Gottingen Lecture Notes). in Higher Dimensional Geometry over Finite Fields, eds: D. Kaledin and Y. Tschinkel, IOS Press, 2008, 244-268. \bibitem{Wong:08} C. F. Wong, Zeta functions of projective toric hypersurfaces over finite fields. Thesis (Ph.D.)–University of California, Irvine. 2008, %available at http://arxiv.org/pdf/0811.0887 \bibitem{Stanley} R. P. Stanley, Enumerative Combinatorics, Vol I, Cambridge University Press, 1997. \end{thebibliography} \end{document}