2015/07/22 by Li, Jiyou, Wan, Daqing · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1507.06329
Let D be a subset of a finite commutative ring R with identity. Let f(x)∈ R[x] be a polynomial of positive degree d. For integer 0≤ k ≤ |D|, we study the number Nf(D,k,b) of k-subsets S⊆ D such that ∑x∈ S f(x)=b. In this paper, we establish several asymptotic formulas for Nf(D,k, b), depending on the nature of the ring R and f. For R=ℤn, let p=p(n) be the smallest prime divisor of n, |D|=n-c ≥ Cdn p-\frac 1d +c and f(x)=adxd +⋯ +a0∈ ℤ[x] with (ad, …, a1, n)=1. Then | Nf(D, k, b)-(1)/(n)n-c \choose k|≤ δ(n)(n-c)+(1-δ(n))(Cdnp-\frac 1d+c)+k-1\choose k, partially answering an open question raised by Stanley \citeSt, where δ(n)=∑i| n, μ(i)=-1\frac 1 i and Cd=e1.85d. Furthermore, if n is a prime power, then δ(n) =1/p and one can take Cd=4.41. For R=\mathbbFq of characteristic p, let f(x)∈ \mathbbFq[x] be a polynomial of degree d not divisible by p and D⊆ \mathbbFq with |D|=q-c≥ (d-1)√(q)+c. Then | Nf(D, k, b)-(1)/(q)q-c \choose k|≤ (q-c)/(p)+\frac p-1p((d-1)q\frac 12+c)+k-1 \choose k. 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⊆ G with |D|=|G|-c≥ c. Then | Nx(D, k, b)-(1)/(|G|)|G|-c \choose k|≤ c + (|G|-2c)δ(e(G))+k-1 \choose k, where e(G) is the exponent of G and δ(n)=∑i| n, μ(i)=-1\frac 1 i. In particular, we give a new short proof for the explicit counting formula for the case D=G.