When are subset sums equidistributed modulo \(m\)?
type: Item
instance of: scholarly article
title: When are subset sums equidistributed modulo \(m\)?
zbMATH Open document ID: 0816.11012
author: Stan Wagon
author: Herbert S. Wilf
published in: The Electronic Journal of Combinatorics
publication date: 1995-04-06T00:00:00Z
full work available at URL: https://eudml.org/doc/118611
full work available at URL: R3
review text: 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.
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 11B50
zbMATH DE Number: 741544
zbMATH Keywords: subset sums
zbMATH Keywords: uniform distribution in residue classes mod m
zbMATH Keywords: Gaussian polynomial
MaRDI profile type: Publication
Recommended article: Comments on: ``When are subset sums equidistributed modulo \(m\)?''
Recommended article: On subset sums of \(\mathbb{Z}_n^{\times}\) which are equally distributed modulo \(n\)
Recommended article: When subset-sums do not cover all the residues modulo \(p\).
Recommended article: WHEN ARE TWO DEDEKIND SUMS EQUAL?
Recommended article: On the sum \(\sum_{k\equiv r\pmod m}{n\choose k}\) and related congruences.
Recommended article: Subset sums modulo a prime
Recommended article: Sum Zero (\mod n), Size n Subsets of Integers
Recommended article: Distribution of a Subset of Non-residues Modulo p
Recommended article: Dedekind sums and uniform distribution (mod 1)
description: scientific article; zbMATH DE number 741544