When are subset sums equidistributed modulo \(m\)?

Stan Wagon ; Herbert S. Wilf

The electronic journal of combinatorics, Tome 1 (1994)

Résumé

For a triple $(n,t,m)$ of positive integers, we attach to each $t$-subset $S=\{a_1,\ldots ,a_t\}\subseteq \{1,\ldots ,n\}$ the sum $f(S)=a_1+\cdots +a_t$ (modulo $m$). We ask: for which triples $(n,t,m)$ are the ${n\choose t}$ values of $f(S)$ uniformly distributed in the residue classes mod $m$? The obvious necessary condition, that $m$ divides ${n\choose t}$, is not sufficient, but a $q$-analogue of that condition is both necessary and sufficient, namely: $${{q^m-1}\over {q-1}}\quad \text{divides the Gaussian polynomial}\quad \binom{n}{t}_q.$$ We show that this condition is equivalent to: for each divisor $d>1$ of $m$, we have $t\ {\rm mod}\, d>n\ {\rm mod}\, 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.

Détail

DOI : 10.37236/1183

Classification : 11B83, 11B50
Mots-clés : subset sums, uniform distribution in residue classes mod m, Gaussian polynomial