\magnification 1200
\nopagenumbers
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 1 (1994), \#R3\hfill\folio}\fi}
\voffset=2\baselineskip
\input epsf
\def\fw{f\kern-2pt w}
\def\gauss#1#2#3{{{#1}\choose {#2}}_{\kern -3pt #3}}
\font\smcp =cmtcsc10
\font\bigf =cmbx12 at 14pt
\font\bff =cmbx12
\def\vrl{\vrule width 5pt height 5pt}
\def\sech#1{\vskip 16pt
\noindent{\bff #1}
\vskip 12pt}
\font\smf=cmr7
\def\eqdef{\, =\kern -12pt\raise 6pt\hbox{{\smf def}}\, }
{\topskip .5 in
\centerline{\bigf When are subset sums equidistributed modulo m?}
\vskip .8in
\centerline{ Stan Wagon\footnote{$^1$}{\smf Until July, 1994: P. O. Box 1782, Silverthorne, CO 80498 (71043.3326@compuserve.com)}}
\centerline{Macalester College, St. Paul, MN 55105 (wagon@macalstr.edu)}
\vskip 6pt
\centerline{and}
\vskip 6pt
\centerline{Herbert S. Wilf\footnote{$^2$}{\smf Supported by the Office of Naval Research}}
\centerline{University of Pennsylvania, Philadelphia, PA 19104 (wilf@central.cis.upenn.edu)}
\vskip 10pt
\centerline{January 30, 1994}
\vskip .7in
\hrule
\vskip .1 in
\noindent{\bf Abstract.} 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 {\rm divides\ the\ Gaussian\ polynomial}\quad \gauss{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.
\vskip .1in
\hrule
}
\vfill\eject
\sech{1. Introduction}
While working on a problem related to lotteries, Larry Carter, of IBM, and the first author were led to the question
of the title. Positive integers $n$, $t$, and $m$ are given. By a
$t$-{\it ticket} we mean a subset of $\{1,2,\ldots ,n\}$ of size $t$.
The {\it value} of a $t$-ticket is the modulo-$m$ sum of its entries.
Our question is: for which triples $(n,t,m)$ are the values of the
$t$-tickets equally distributed among the $m$ residue classes? Let us
call a triple {\it uniform} if equidistribution holds.
There is an obvious necessary condition, namely that ${n\choose t}$ be divisible by $m$, but this is not sufficient, as the example
$(n,t,m)=(5,2,2)$ shows. A special case of this
question was considered by Snevily [4].
In this paper we will describe some of the experimentation that went
into formulation of a conjecture about the necessary and sufficient
condition. We then will prove that the conjecture is true, using the
method of generating functions. Then we will give a bijective proof of
the fact that $(n,t,m)$ is uniform when the conditions of the theorem
hold.
The following recurrence was used in our computations. For nonnegative integers $(n,t,m)$,
and for residue classes $i$ modulo $m$, let $f(i,n,t,m)$ be the number
of $t$-tickets from $\{1,2,\ldots ,n\}$ whose value is congruent to
$i$ mod $m$. Then we have
$$f(i,n,t,m)=f(i,n-1,t,m)+f(i-n,n-1,t-1,m).\eqno(1)$$ The proof is
immediate, by considering separately those $t$-tickets that contain
$n$ and those that do not.
From this formula and suitable initial values it is easy to generate images of the uniform triples (we used {\it Mathematica}), by fixing $m$ and varying $t$ and $n$. Figure 1 shows twelve cases (moduli), where each plotted point indicates a uniform triple. The data suggest some definite patterns, but the statement that covers all cases does not immediately leap out.
Larry Carter made the observation from these data that the cases in which uniformity holds can be summarized by a succinct arithmetical condition (condition 3 in the theorem below).
\vskip 15pt
\noindent{\bf Theorem}. {\sl The following properties of a triple $(n,t,m)$ of positive integers are equivalent:
{\parindent 40pt\parskip 5pt
\item{1.} $(n,t,m)$ is uniform;
\item{2.} $(q^m-1)/(q-1)$ divides the Gaussian polynomial $\gauss{n}{t}{q}$;
\item{3.} For all $d>1$ that divide $m$, we have $t$ mod $d>n$ mod $d$ (here $a$ mod $b$ denotes the least nonnegative residue).
}}
\vfill\eject
{\hoffset .5in
\voffset -.5in
\nopagenumbers
$$\hbox{
\epsfysize=6in
\epsffile{figure1.eps}}$$
\vskip 35pt
{\hsize 4.4in
\line{F{\smcp igure} 1. Dots indicate that $t$-subset sums from $[n]$ are equidistributed\hfil}
\line {modulo $m$. By fixing $m$ and varying $t$ and $n$, various patterns are revealed.\hfil}
\line {For example there is an $m$-periodicity in both the $t$- and the $n$-directions;\hfil}
\line {thus for the moduli 10, 12, 14 and 16, we show only a fundamental region.\hfil}}
\vfill\eject}
\hphantom{aa}
\vskip-1in
$$\hbox{\epsfysize=2.5in
\epsffile{figure2.eps}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaa}$$
\vskip 50pt
{\hsize 4in
\noindent F{\smcp igure} 2. The uniform pairs $(n,t)$ for modulus $m=15$ arise from those for $m=3$ and $m=5$. The left chart shows the uniform pairs for 3 (gray triangles) and 5 (black triangles). A pair $(n,t)$ is uniform modulo 15 iff it is uniform modulo 3 and 5 and $t$ mod 15 $>n$ mod 15, as in chart on right.}
\sech{2. A proof by generating functions}
To prove the theorem, we start with the following lemma.
\proclaim Lemma 1. Let $h(q)$ denote the $t^{\rm th}$ elementary symmetric function of the $n$ quantities $q,q^2,\ldots ,q^n$. Then the subset sums are equidistributed modulo $m$ if and only if $h(q)$ is divisible by $(q^m-1)/(q-1)$.
\noindent{\bf Proof.} First, for each $i=0,1,2,\ldots $, let $a_i$ be the number of these sums that are {\it equal} to $i$. Then clearly
the $t^{\rm th}$ elementary symmetric function of the $n$ quantities $q,q^2,\ldots ,q^n$ is
$$\sum_{1\le i_11$ and $k$ divides $m$ then we must require that $\beta <\delta$, i.e., that $n\bmod{k}1$ that divides $m$. \vrl
We remark that the proof shows that whether or not the conditions of the theorem hold, we always have
$$r(q)\eqdef \sum_{i=0}^{m-1}f(i,n,t,m)q^i=q^{t(t+1)/2}\gauss{n}{t}{q}{\rm \ modulo\ }(q^m-1).\eqno(3)$$ This makes it easy to compute the numbers of subset sums in each residue class mod $m$ whether or not the tickets are equidistributed, by looking at the remainder of the division of $q^{t(t+1)/2}$ times the Gaussian polynomial by $(q^m-1)$. For example the triple $(n,t,m)=(17,10,16)$ is not uniform. After dividing $q^{55}\gauss{17}{10}{q}$ by $q^{16}-1$ we find a remainder of $$\eqalign{&1212 + 1219\,q + 1212\,{q^2} + 1219\,{q^3} + 1212\,{q^4} + 1219\,{q^5} +
1212\,{q^6} + 1219\,{q^7}\cr & + 1212\,{q^8} + 1219\,{q^9} + 1212\,{q^{10}} +
1219\,{q^{11}} + 1212\,{q^{12}} + 1219\,{q^{13}} + 1212\,{q^{14}} +
1219\,{q^{15}},\cr}$$
in which the coefficient of each $q^i$ is $f(i,17,10,16)$.
We note, following [2], that the factorization of $1-q^i$ into cyclotomic polynomials means that $\gauss{n}{t}{q}$ is the product of precisely those cyclotomic polynomials $F_d(q)$ for which the number of multiples of $d$ in $[n-t+1,n]$ is greater than the number in $[1,t]$. But this excess is $\lfloor{n/d}\rfloor-\lfloor{(n-t)/d}\rfloor-\lfloor{t/d}\rfloor$, which is 0 unless $\bar{t}>\bar{n}$\footnote{$^\dagger$}{We use the abbreviation $\bar{t}$ (mod $d$) for the least nonnegative residue of $t$ mod $d$.}, when it is 1. We can restate this as a relationship between the cyclotomic factors of the Gaussian polynomial and uniform triples, which at the same time gives a nice way of computing the Gaussian polynomials, as follows.
\proclaim Proposition. The Gaussian polynomial $\gauss{n}{t}{q}$ is the product of exactly those cyclotomic polynomials $F_j(q)$ for which the triple $(n,t,j)$ is uniform.
We can express the distribution function $r(q)$, of (3) explicitly in terms of the values of the Gaussian polynomials at the roots of unity. Indeed (3) implies that
$$q^{t(t+1)/2}\gauss{n}{t}{q}=(q^m-1)Q(q)+r(q)$$
for some quotient polynomial $Q(q)$. If $\omega^m=1$, let $q=\omega$ in the above, to find that $r(\omega )=\omega^{t(t+1)/2}\gauss{n}{t}{\omega}$ at every $m$th root of unity $\omega$. Hence by Lagrange interpolation,
$$r(q)={1\over m}\sum_{\omega^m=1}{{q^m-1}\over {q-\omega}}\omega^{1+t(t+1)/2}\gauss{n}{t}{\omega}.\eqno(4)$$
Note that the single term $\omega =1$ has the value ${n\choose t}$ and that, by (3), this actually accounts for all of $r(q)$ precisely when the conditions of our theorem hold, for then and only then is it true that all $f(i,n,t,m)={n \choose t}/m$.
By matching coefficients of powers of $q$ on both sides of (4) we obtain the following formula for the occupancies of each residue class:
$$f(j,n,t,m)={1\over m}\sum_{\omega^m=1}\omega^{t(t+1)/2-j}\gauss{n}{t}{\omega}.$$
Hence the frequency vector is essentially the Fourier transform of the vector of values of the Gaussian polynomials at the roots of unity. This last formula is a nice way to compute the occupancy numbers, and in fact the images in Figure 3 below were found in a few seconds by this method.
\vskip -.2in
%\epsfxsize=5in
%$$\hbox{\hphantom{cccccc}\epsffile{figure3.eps}}$$
\epsfxsize=1.75in\epsfysize=1.4in
$$\hbox{\epsffile{fig3a.eps}\epsfysize=1.4in
\epsfxsize=1.75in\epsffile{fig3b.eps}\epsfysize=1.4in
\epsfxsize=1.75in\epsffile{fig3c.eps}}$$
\noindent F{\smcp igure} 3. The first two panels show two frequency vectors for 9-tuples from [26]. The modulus in the first is 31, with a
down-and-up pattern characteristic of primes. In the second panel the
modulus is 30, and the vector's behavior is more complex. The
frequencies in the third panel are from the triple $(36, 13, 48)$.
\vfill\eject
\sech{3. A bijective proof}
In this section we attack the problem using elementary combinatorial arguments. We present a bijective proof of the positive direction of the theorem ((3) $\Rightarrow$ (1)). The method also yields the negative, nonuniform, direction of the theorem ((1) $\Rightarrow$ (3)) if $m$ is a prime power. As a bonus we get some formulas for the residue frequencies as well as an elementary proof of the $m$-periodicity that is so striking in Figure 1. We begin with the general proof of the positive direction, in which we recursively construct a bijection.
\vskip 15pt
\noindent{\bf Proof of the positive direction.} Fix $n$ and $t$ and suppose $m$ satisfies the hypothesis of the theorem: $\bar{t}>\bar{n}$ (mod $d$), for each $d>1$ that divides $m$. The proof will be by induction on $m$. To this end, note that the hypothesis is satisfied for triples $(n,t,d)$ if $d$ divides $m$; more important, it is satisfied for any triple $(n',t',d)$ where $n'\equiv n$ and $t'\equiv t$ (mod $d$).
Now let $km$ be the largest multiple of $m$ with $km\le n$; call numbers in $[km]$ {\it small}. Let $w$ be the number of small entries in a ticket $T$, and let $d={\rm gcd}(w,m)$. We will call $d$ the {\it type} of $T$. Our hypothesis tells us that $d < m$. For suppose otherwise. Then $m$ divides $w$, which implies that $t - w =\bar{t}$ (mod $m$), since $t - w$, being the number of nonsmall entries in $T$, is at most $n - km$, which is less than $m$ by definition of
$k$. But also $t - w\le\bar{n}$ (mod $m$) because $t - w\le n - km$. Therefore $\bar{t}\le \bar{n}$ (mod $m$), contradicting the hypothesis.
We claim that within the family of tickets of type $d$ there is equidistribution among values modulo $d$. This claim suffices, for if $c_i$ is the frequency of the residue class $i$ within type $d$, then the claim implies, for each $j\le d-1$:
$$c_0+c_d+c_{2d}+\cdots +c_{({m\over d}-1)d}=c_j+c_{j+d}+\cdots +c_{j+d({m\over d}-1)}.\eqno(5)$$
We can now construct a bijection showing that $c_j=c_{j+id}$ as follows. If $T$ is a ticket of value $j$ and type $d$, let $w$ be the number of small entries in $T$; write $w$ as $Ld$ where gcd$(L,m)=1$. Then add $iL^{-1}$ (the inverse is modulo $m$) to each of the small entries of $T$ (reducing modulo $km$ and using $km$ for 0). This adds $wiL^{-1}=LdiL^{-1}=di$ to the mod-$m$ value, as desired. These bijections, together with (5), imply that each $c_0m/d$ equals $c_jm/d$, and so $c_0=c_j$. This is true within each type $d$, proving uniformity.
It remains to prove the claim. We will show here a remarkable fact. If $S$ is some fixed set of small elements, consider the collection of all tickets whose set of small elements is exactly $S$. We claim that {\it within this collection, the modulo $d$ frequencies are all equal.} Indeed, for tickets $T$ in such a family the mod-$d$ frequencies are a translation of the mod-$d$ frequencies of $T\cap [km+1,n]$. But these intersections are all possible $(t-w)$-subsets from $[km+1,n]$. Since $d$ divides $m$, as far as mod-$d$ values are concerned such a subset may be viewed as a $(t-w)$-subset of $[\bar{n}\ $mod $m]$. But $d2n$. Then take $\mu=1$. We have $2j \mu/m < 2 j
\mu/2n=j/n\le 1$. Hence $2j \mu/m$ cannot be an odd integer, a
contradiction. So $m$ must be a power of 2 that is $\le 2n$.
Conversely, suppose $m\le 2n$ and $m$ is a power of 2. Choose $\mu$, $1\le\mu\le m-1$. Then we can choose $j$ to be the largest power of 2 that is $\le n$, say $j=2^b$. With that choice we have $2j \mu/m = j \mu/(m/2)$.
But the denominator is a power of 2 that is $\le n$. Hence $j/(m/2)$ is an integer. \vrl
For the positive direction of this theorem, we can give a bijective proof: Use induction on $n$. First suppose $n$ is not a power of 2, say $2^i < n < 2^{i+1}$. Any subset of $[n]$ is either a subset of
$[n - 1]$ or is obtained from such a subset by adjoining $n$. By the induction
hypothesis, the subset-sums from $[n - 1]$ are equidistributed modulo $2^{i+1}$, and hence so are the subset-sums from $[n]$.
Now suppose we are dealing with subsets of $[2^i]$. The induction
hypothesis tells us that the subset-sums from $[2^i - 1]$ are
equidistributed modulo $2^i$. If $f_j$ denotes the number of subsets
whose mod-$2^{i+1}$ sum is $j$, then this means that
$$f_0+f_{2^i}=f_1+f_{1+2^i}=f_2+f_{2+2^i}=\cdots =f_{2^i-1}+f_{2^{i+1}-1}.$$
Now consider the function that takes a subset of $[2^i]$ and deletes $2^i$ if $2^i$ is in the subset, and adjoins $2^i$ otherwise. This is a bijection and its effect
on the mod-$2^{i+1}$ value of the sum of a set is to add $\pm 2^i$, which is the same as adding $2^i$. This bijection therefore shows that each $f_j = f_{j+2^i}$, which
combines with the equations above to yield equidistribution. \vrl
\sech{5. Asymptotics of the distribution for the power set}
We work out an exact and an asymptotic expression for the standard deviation, $\sigma (n,m)$, of the occupancies of the residue classes modulo $m$ in the power set case. It shows that the ratio of standard deviation to mean goes to zero exponentially, for fixed $m$, as $n\to\infty$, at least in the case where $n$ goes to $\infty$ through multiples of $m$. The rate at which the ratio approaches zero depends on the smallest odd prime factor of $m$, which refines the fact, discussed in the previous section, that for equidistribution $m$ must be a power of 2.
\vskip 10pt
\noindent{\bf Theorem}. {\sl Fix an integer $m>0$.}
{\parindent 30pt
\sl
\item{(a)} If $m$ is a power of 2, then $\sigma (n,m)=0$ if $n$ is a multiple of $m$.
\item{(b)} If $m$ is not a power of 2, and the odd part of $m$, say $m''$, is prime, then when $n$ is a multiple of $m$ we have
$${{\sigma (n,m)}\over {{\rm mean}(n,m)}}={{\sqrt{m''-1}}\over {2^{n(1-1/m'')}}}.$$
\item{(c)} If $m$ is not a power of 2, and the odd part of $m$, say $m''$, is composite, then asymptotically, as $n\to\infty$ through multiples of $m$, we have
$${{\sigma (n,m)}\over {{\rm mean}(n,m)}}\sim 2^{-n(1-1/p_2)},$$
where $p_2$ is the smallest odd prime factor of $m$.
}
\vskip 10pt
For $n,m$ fixed, let $c(n,m,j)$ be the number of subsets of $[n]$ whose sum is $j$ modulo $m$. Then we know that
$$f_{n,m}(q)\eqdef \sum_{j=0}^{m-1}c(n,m,j)q^j=\prod_{j=1}^n(1+q^j)\quad ({\rm modulo\ }q^m-1),$$
which means that
$$g_n(q)\eqdef \prod_{j=1}^n(1+q^j)=p(q)(q^m-1)+f_{n,m}(q),$$
for some polynomial $p$.
Now it is well known and easy to check that if $f(q)$ is any real polynomial of degree $m-1$, then the sum of the squares of the coefficients of $f$ is equal to
$${1\over m}\sum_{\omega^m=1}|f(\omega )|^2.$$
Hence
$$\sum_{j=0}^{m-1}c(n,m,j)^2={1\over m}\sum_{\omega^m=1}|g_{n}(\omega )|^2.$$
Now we will suppose that $n$ is a multiple of $m$, say $n=km$. Then, if $\omega =e^{2\pi ir/m}$ is a fixed $m$th root of unity, the sequence $\{\omega^j\}_{j\ge 0}$ is periodic in $j$ of period $m$. Hence
$$|g_{n}(\omega )|=\prod_{j=1}^n|(1+\omega^j)|
=\bigl(\prod_{j=1}^m|(1+\omega^j)|\bigr)^k
=\bigl(\prod_{j=1}^m|2\cos{{{\pi rj}\over m}}|\bigr)^k.$$
Suppose $(r,m)=1$. Then in the last product above, $rj$ runs through a complete system of residues modulo $m$, so in that case
$$\prod_{j=1}^m|2\cos{{{\pi rj}\over m}}|=\prod_{j=1}^m|2\cos{{{\pi j}\over m}}|=\cases{2&if $m$ is odd;\cr 0&if $m$ is even.\cr}$$
If, on the other hand, $(r,m)=d\ge 1$, then put $m'=m/d, r'=r/d$, and find
$$|g_{n}(\omega )|=\prod_{j=0}^{m-1}|\bigl(2\cos{{{\pi jr'}\over {m'}}}\bigr)|
=\bigg|\prod_{j=0}^{m'-1}(2\cos{{{\pi j}\over {m'}}})\bigg|^d
=\cases{2^d&if $m'$ is odd;\cr 0 &if $m'$ is even.\cr}$$
Now for the variance of the occupancy numbers, when $n=km$, we have
$$\eqalign{\sigma^2(km,m)&={1\over {m^2}}\sum_{r=1}^{m-1}|g_{n}(\omega_r)|^2
={1\over {m^2}}\sum_{r=1}^{m-1}|g_{m}(\omega_r)|^{2k}\cr
&={1\over {m^2}}\sum_{\scriptstyle {{r=1}\atop {m/(m,r) {\rm \ odd}}}}^{m-1} 2^{2k\, gcd(m,r)}
={1\over {m^2}}\sum_{r''=1}^{m''-1}2^{k2^{a+1}gcd(m'',r'')},\cr}\eqno(7)$$
where $m=2^am''$, $m''$ odd.
Now, as $r''$ runs through its range, in the last displayed sum, the largest possible value that the gcd can take is $m''/p_2$, where $p_2$ is the smallest prime factor of $m''$, unless $m''$ is itself prime. In the former case, $m''$ is the odd part of $m$, so $p_2=p_2(m)$ is the smallest {\it odd} prime factor of $m$. In the case where $m''$ is prime, the last member of (7) above is exactly $(m''-1)2^{2n/m''}/m^2$.
Suppose the odd part of $m$ is not prime. Then asymptotically, as $k\to\infty$, $n=km$, we have
$$\sigma^2(km,m)\sim {1\over {m^2}}2^{k2^{a+1}m''/p_2}={{2^{2mk/p_2}}\over {m^2}}= {{2^{2n/p_2}}\over {m^2}}.$$
Since the mean occupancy of a residue class is $2^n/m$, we have
$${{\sigma (km,m)}\over {{\rm mean}(km,m)}}\sim 2^{-n(1-1/p_2)},$$
as claimed.
If the odd part of $m$ is prime then we have an exact evaluation, as stated in the theorem above. \vrl
\sech{6. Questions}
{\parindent 0pt
1. Can the negative direction of the theorem, i.e. that (3) $\Rightarrow$ (1), be given an elementary proof?
2. We have shown that for the full power set, the standard deviation
of the distribution is an asymptotically vanishing fraction of the
mean, on certain subsequences of $n\to\infty$. Is the same true in the case of $t$-subsets of $[n]$?
3. THE PRIME MODULUS CONJECTURE. Let $f(n, t, m)$ denote the entire
sequence of frequencies $\{f(i, n, t, m)\}_{i=0}^{m-1}.$ For an odd
prime modulus $p$, computations suggest that $f(n, t, m)$ is a
unimodal sequence, provided we shift to start at the minimum
frequency. This means that the frequencies would then go from a
minimum to a maximum and then back to the minimum, with no direction
changes except at the maximum. We will henceforth use the term
$d$-{\it wave} for a sequence of $d$ integers that is unimodal after a shift. Note that if $p > t(n - t)$, then the mod-$p$ reduction
disappears from the problem and this conjecture is a consequence of
the classical unimodality result about the Gaussian polynomials (see
[7]).
4. Given $(n, t, m)$ and a divisor $d$ of $m$ with $d > 1$. Say that
$d$ is {\it good} if $\bar{t} > \bar{n}$ (mod $d$); otherwise $d$ is
{\it bad}. This question and the following one are attempts to explain
and quantify the observed link between the shape of the frequency
vector $f(n, t, m)$ and the shapes of $f(n, t, d)$ for bad divisors
$d$ of $m$. First note that if there are no bad divisors, then the
main theorem applies and $f(n, t, m)$ is constant.
Consider the case
where $m$ has a single bad divisor, $d$. Computations lead to the
following two conjectures:
{\parindent 40pt
\item{(a)} If $d = m$, then $f(n, t, m)$ is an $m$-wave, as conjectured for prime moduli in Question 3.
\item{(b)} $f(n, t, m) = (d/m) f(n,t,d)*$, where $*$ denotes a periodic extension that turns the $d$-vector into an $m$-vector.
}
At present the simple formula in (b) remains a conjecture. Statements
(a) and (b) together imply that the wave behavior for primes
holds whenever there is only one bad divisor of $m$ (see the third panel of Figure 3 for an example of this situation with $(n, t, m ) = (36, 13, 48)$ and the only bad divisor being 48).
5. We now formulate a general conjecture that attempts to explain
the overall shape of the frequency sequence $f(n, t, m)$ by positing a
Fourier-like decomposition of $f(n, t, m$) into components (waves)
corresponding to the bad divisors of $m$.
\proclaim The General Conjecture. For every triple $(n, t, d)$, there is a $d-$wave, $\hat{f}(n, t, d)$, such that, for every triple $(n, t, m)$ ($m>1$) we have
$$ f(n, t, m) = \sum_{d\in \beta (m)}C_d\hat{f}(n, t, d)*,$$
where the $C_d$'s are rational, and ``*'' indicates that the $d$-wave is to be extended periodically to an $m$-sequence, and $\beta (m)$ is the set of bad divisors of $m$.
The idea behind this formulation is that $\hat{f}(n, t, m)$ captures the
essence of the mod-$m$ nonuniformities in $f(n, t, m)$ caused by $m$,
as opposed to those caused by bad divisors of $m$. Note first that, if this conjecture is true and $p$ is prime, then $f(n, t, p)
= C_p \hat{f}(n, t, p)$. Thus $f(n, t, p)$ has the shame shape as
$\hat{f}(n, t, p)$ and $f(n, t, p)$ is a $p$-wave, which settles the Prime
Moduli Conjecture (Question 3). Moreover, if $m$ has a single bad
divisor then $f(n, t, m$) is a periodic extension of a $d$-wave, as
conjectured in Question 4.
As an illustration of the case of two bad divisors, consider $(n, t, m) =
(26, 9, 15)$; the bad divisors are 3 and 15, and we can take
$$\hat{f}(26, 9, 3) = f(26, 9, 3) = \{1041554, 1041498, 1041498\},$$
$$\hat{f}(26, 9, 5) = f(26, 9, 5) = \{624910, 624910, 624910, 624910, 624910\}.$$
In order to find $\hat{f}(26, 9, 15)$, we used trial and error to discover
that 11/56 works as the constant $C_3$. In other words, $f(26, 9, 15) - (11/56) \hat{f}(26, 9, 3)$ turns out to be a 15-wave, so we take it as the definition of $\hat{f}(26, 9, 15)$; moreover, 11/56 appears to be the unique constant that works in this case. To summarize, $$f(26, 9, 15) = \hat{f}(26, 9, 15) + {{11}\over {56}} \hat{f}(26, 9, 3)$$
is a decomposition of the frequency vector into a 15-wave and a
3-wave. We have not been able to identify
any pattern in the coefficients that arise in such decompositions.
\vskip 40pt
\centerline{\bff References}
\vskip 12pt
\parindent 20pt
\item{1.} L. Comtet, {\it Advanced Combinatorics}, Dordrecht: D. Reidel, 1974.
\item{2.} D. E. Knuth and H. S. Wilf, The power of a prime that divides a binomial coefficient, {\it J. f\"ur die reine u. angew. Math.} {\bf 396} (1989), 212-219.
\item{3.} G. P\'olya and G. L. Alexanderson, Gaussian binomial coefficients, {\it Elem. der Math.} {\bf 26} (1971), 102-109.
\item{4.} H. Snevily, Subsets whose sums are congruent, Problem E3472, {\it Amer. Math. Monthly} {\bf 100} (1993), 503.
\item{5.} D. Zeilberger, Kathy O'Hara's constructive proof of the unimodality of the Gaussian coefficients, {\it Amer. Math. Monthly} {\bf 96} (1989), 590-602.
}
\bye