11
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ What is your solution for $n$ prime? $\endgroup$ Jan 23, 2011 at 3:19
  • $\begingroup$ 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. $\endgroup$
    – user9072
    Jan 23, 2011 at 20:38
  • $\begingroup$ 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. $\endgroup$ Jan 24, 2011 at 1:27
  • $\begingroup$ @EricNaslund - It is similar to Richard Stanley's solution below, but less clever. I had a polynomial based on roots of 1 whose coefficients give info about the desired numbers and which was obtainable a different way. $\endgroup$ Sep 30, 2016 at 18:57

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Jan 23, 2011 at 16:32
  • $\begingroup$ Sorry, should have explained the notation. $y\cdot x$ is the standard bilinear form on $\mathbb{Z}_N$, defined as $xy/N$. $\endgroup$ Jan 23, 2011 at 17:07
  • $\begingroup$ 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? $\endgroup$ Jan 24, 2011 at 1:46
  • $\begingroup$ 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! $\endgroup$ Jan 24, 2011 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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