Counting polynomial subset sums

Abstract

Let $D$ be a subset of a finite commutative ring $R$ with identity. Let $f(x)\in R[x]$ be a polynomial of positive degree $d$. For integer $0\le k\le |D|$, we study the number $N_f(D,k,b)$ of $k$-subsets $S\subseteq D$ such that \begin{align*} \sum_{x\in S} f(x)=b. \end{align*} In this paper, we establish several asymptotic formulas for $N_f(D,k,b)$, depending on the nature of the ring $R$ and $f$. For $R={\mathbb{Z}}_n$, let $p=p(n)$ be the smallest prime divisor of $n$, $|D|=n-c\ge C_{d}n{p}^{-\frac{1}{d}}+c$ and $f(x)=a_d{x}^d+\cdots +a_0\in \mathbb{Z}[x]$ with $(a_d,\dots ,a_1,n)=1$. Then $$\left|N_f(D,k,b)-\frac{1}{n}\left(\genfrac{}{}{0ex}{}{n-c}{k}\right)\right|\le \left(\genfrac{}{}{0ex}{}{\delta (n)(n-c)+(1-\delta (n))(C_{d}n{p}^{-\frac{1}{d}}+c)+k-1}{k}\right),$$ partially answering an open question raised by Stanley \cite{St}, where $\delta (n)={\sum }_{i\mid n,\mu (i)=-1}\frac{1}{i}$ and $C_d=e^{1.85d}$. Furthermore, if $n$ is a prime power, then $\delta (n)=1/p$ and one can take $C_d=4.41$. For $R={\mathbb{F}}_q$ of characteristic $p$, let $f(x)\in {\mathbb{F}}_q[x]$ be a polynomial of degree $d$ not divisible by $p$ and $D\subseteq {\mathbb{F}}_q$ with $|D|=q-c\ge (d-1)\sqrt{q}+c$. Then $$\left|N_f(D,k,b)-\frac{1}{q}\left(\genfrac{}{}{0ex}{}{q-c}{k}\right)\right|\le \left(\genfrac{}{}{0ex}{}{\frac{q-c}{p}+\frac{p-1}{p}((d-1)q^{\frac{1}{2}}+c)+k-1}{k}\right).$$ If $f(x)=ax+b$, then this problem is precisely the well-known subset sum problem over a finite abelian group. Let $G$ be a finite abelian group and let $D\subseteq G$ with $|D|=|G|-c\ge c$. Then $$\left|N_x(D,k,b)-\frac{1}{|G|}\left(\genfrac{}{}{0ex}{}{|G|-c}{k}\right)\right|\le \left(\genfrac{}{}{0ex}{}{c+(|G|-2c)\delta (e(G))+k-1}{k}\right),$$ where $e(G)$ is the exponent of $G$ and $\delta (n)={\sum }_{i\mid n,\mu (i)=-1}\frac{1}{i}$. In particular, we give a new short proof for the explicit counting formula for the case $D=G$.

arXiv comment15 pages. Any comment are warmly welcome

References in corpus (1)

• On the minimum distance of elliptic curve codes