When are subset sums equidistributed modulo \(m\)?
Summary: For a triple \((n,t,m)\) of positive integers, we attach to each \(t\)-subset \(S= \{a_ 1,\dots, a_ t\} \subseteq \{1,\dots, n\}\) the sum \(f(S)= a_ 1+ \cdots+ a_ t\) (modulo \(m\)). We ask: for which triple \((n,t,m)\) are the \(\left( \begin{smallmatrix} n\\ t\end{smallmatrix} \right)\) values of \(f(S)\) uniformly distributed in the residue classes \(\text{mod } m\)? The obvious necessary condition, that \(m\) divides \(\left( \begin{smallmatrix} n\\ t\end{smallmatrix} \right)\), is not sufficient, but a \(q\)-analogue of that condition is both necessary and sufficient, namely: \[ {\textstyle {{q^ m-1} \over {q-1}}} \quad \text{divides the Gaussian polynomial} \quad \left( \begin{smallmatrix} n\\ t\end{smallmatrix} \right)_ q. \] We show that this condition is equivalent to: for each divisor \(d>1\) of \(m\), we have \(t\bmod d>n\bmod d\). Two proofs are given, one by generating functions and another via a bijection. We study the analogous question on the full power set of \([n]\): given \((n,m)\); when are the \(2^ n\) subset sums modulo \(m\) equidistributed into the residue classes? Finally, we obtain some asymptotic information about the distribution when it is not uniform, and discuss some open questions.
uniform distribution in residue classes mod m
scientific article; zbMATH DE number 741544