Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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

2 Answers 2

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/.

share|improve this answer
    
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.