Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T12:58:34Z http://mathoverflow.net/feeds/question/52892 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52892/sums-of-subsets-of-mathbbz-n-mathbbz Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$ benblumsmith 2011-01-23T01:01:06Z 2011-01-23T08:18:26Z <p>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?</p> <p>Here is the problem:</p> <p>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}$?</p> <p>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.</p> http://mathoverflow.net/questions/52892/sums-of-subsets-of-mathbbz-n-mathbbz/52929#52929 Answer by Thomas Bloom for Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$ Thomas Bloom 2011-01-23T08:18:26Z 2011-01-23T08:18:26Z <p>Fix $V=A\cup B$ (and assume $N$ is odd). Then this problem is the Littlewood-Offord problem, which studies the distribution of <code>$X_V:=\epsilon_1v_1+\cdots+\epsilon_nv_n$</code> for an n-tuple $V=(v_1,...,v_n)$ and where $\epsilon_i\in\lbrace -1,1\rbrace$. We have</p> <p><code>$\mathbb{P}(X_V=x)=\mathbb{E}_{y\in Z}\cos(2\pi y\cdot x)\prod_{j=1}^n\cos(2\pi y\cdot v_j).$</code></p> <p>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,</p> <p><code>$\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).$</code></p> <p>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</p> <blockquote> <p>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.</p> </blockquote> <p>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 <a href="http://scholarcommons.sc.edu/math_facpub/31/" rel="nofollow">http://scholarcommons.sc.edu/math_facpub/31/</a>.</p>