Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$

I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related problem?

Here is the problem:

Let $A$ and $B$ be disjoint $k$-subsets of $\mathbb{Z}/n\mathbb{Z}$. Consider $S(A,B)=\sum_{x\in A}x - \sum_{y\in B}y$. As $(A,B)$ ranges over all possible ordered pairs of disjoint $k$-subsets of $\mathbb{Z}/n\mathbb{Z}$, how are the sums $S(A,B)$ distributed over the elements of $\mathbb{Z}/n\mathbb{Z}$? More precisely, for how many of the $\binom{n}{k}\binom{n-k}{k}$ choices of $(A,B)$ is $S(A,B)$ equal to each of the elements of $\mathbb{Z}/n\mathbb{Z}$?

Again I am just looking for references. I actually have a solution in the case that n is prime, but I assume the result is known for more general n. I would be interested in any leads.

-
What is your solution for $n$ prime? – Eric Naslund Jan 23 '11 at 3:19
Reading this I got somewhat confused: is the question about the values of the function $f: \mathbb{Z}/n \mathbb{Z} \to \mathbb{N}_0$ where $f(x)$ is defined as the number of ways one can write $x$ in a specified particular form, or am I getting this wrong? If this is so, then in the prime case, it seems to me it should be constant on the non-zero elements, multiplying 'everything' by an appropriate non-zero element (preserving cardinality and disjointness of the sets). Likewise, for elements of the same order in general. Sorry, that this comment does not contribute to the actual question. – quid Jan 23 '11 at 20:38
Agreed, the size of $\{S(A,B)=x\}$ is constant on $x$ of the same order, for just the reason you say. The question is really about distribution across the order classes. My solution for prime $n$ is based on there being just 2 order classes. – benblumsmith Jan 24 '11 at 1:27
Thank you for this clarification/confirmation. – quid Jan 24 '11 at 10:15

For convenience I will first consider how many sums $S(A,B)$ are equal to 0. I might have made some computational errors, but I think that the method is correct. Regard $n$ as fixed. Let $f_k$ be the number of pairs $(A,B)$ of $k$-element subsets (not necessarily disjoint) of $\mathbb{Z}/n\mathbb{Z}$ such that $\sum_{x\in A}x-\sum_{y\in B}y=0$. Let $g_k$ be the same, except that $A$ and $B$ must be disjoint. It is easy to see that $$f_k = g_k+{n-2(k-1)\choose 1}g_{k-1}+{n-2(k-2)\choose 2}g_{k-2}+\cdots.$$ These equations for $0\leq k\leq n$ can be inverted to express the $g$'s in terms of the $f$'s, so it suffices to find $f_k$.

Let $[x^iy^j]P(x,y)$ denote the coefficient of $x^iy^j$ in the polynomial $P(x,y)$. By standard properties of roots of unity, we have \begin{eqnarray*} f_k & = & [x^ky^k] \frac 1n \sum_{\zeta^n=1} \prod_{j=0}^{n-1} (1+x\zeta^j) (1+y\zeta^{-j})\\ & = & \frac 1n\sum_{d|n}\phi(d)(1-(-x)^{n/d})^d (1-(-y)^{n/d})^d. \end{eqnarray*} It is routine to extract the coefficient of $x^ky^k$,

Completely analogous reasoning works for sums equal to any $m\in \mathbb{Z}/n\mathbb{Z}$, though the computation becomes messier. A related computation appears in http://math.mit.edu/~rstan/pubs/pubfiles/8g.pdf. See also Enumerative Combinatorics, vol. 1, Exercise 1.105.

-

Fix $V=A\cup B$ (and assume $n$ is odd). Then this problem is the Littlewood-Offord problem, which studies the distribution of $$X_V:=\epsilon_1v_1+\cdots+\epsilon_nv_n$$ for an n-tuple $V=(v_1,...,v_n)$ and where $\epsilon_i\in\lbrace -1,1\rbrace$. We have

$$\mathbb{P}(X_V=x)=\mathbb{E}_{y\in \mathbb{Z}_n}\cos(2\pi y\cdot x)\prod_{j=1}^n\cos(2\pi y\cdot v_j).$$

Chapter 7 of Tao and Vu has lots of useful bounds for this problem (the one above is Lemma 7.11). Summing over all $V$ would give you an exact answer,

$$\lbrace S(A,B)=x\rbrace=2^{2k}\mathbb{E}_{y\in \mathbb{Z}_n}\cos(2\pi y\cdot x)\sum_{\lvert V\rvert=2k}\prod_{v\in V}\cos(2\pi y\cdot v).$$

For a more practical bound, the paper "On the distribution of sums of residues" by Griggs might be useful. For instance, Corollary 3 of that paper gives

Let $P\subset\mathbb{Z}_n$ with $\lvert P\rvert=p$, and $V$ as above. Then the number of $X_V$ inside $P$ is at most the sum of the $p$ middle binomial coefficients in $n$, and this bound is best possible.

Again, summing over possible $V$ in clever ways gives you good upper and lower bounds for your problem from this. You can find this paper at http://scholarcommons.sc.edu/math_facpub/31/.

-
Thank you, both these references look very promising. Regarding your application of Tao and Vu's lemma to my problem, apologies if I'm missing something obvious but I'm confused: since $x$, $y$, and $v$ are all (residues of) integers, isn't $\cos(2\pi y \cdot x)=\cos(2\pi y \cdot v)=1$ always? So that you are claiming that $|\{S(A,B)=x\}|=2^{2k}\sum_{|V|=2k}1=2^{2k}\binom{n}{2k}$? This is the total number of ways that a subset $V$ can be picked and then signs assigned to its elements. $|\{S(A,B)\}|$ should be much smaller and depend on $x$. Please clarify? – benblumsmith Jan 23 '11 at 16:32
Sorry, should have explained the notation. $y\cdot x$ is the standard bilinear form on $\mathbb{Z}_N$, defined as $xy/N$. – Thomas Bloom Jan 23 '11 at 17:07
Thank you, very helpful. Having now consulted Tao and Vu, it seems to me that this expression still wouldn't quite be the answer to my question because I need $A$ and $B$ to be the same size, i.e. the same number of $\epsilon_i$ equal to 1 as to -1, whereas this expression would be counting all possible choices of the $\epsilon_i$. Does this seem correct to you? – benblumsmith Jan 24 '11 at 1:46
Yes, of course, sorry. I would still expect the contribution from your case to dominate, but I don't see how to make this work; certainly the upper bounds would still apply. Hopefully you'll find a reference from Tao and Vu which would be more helpful! – Thomas Bloom Jan 24 '11 at 6:32