Generalizing and Implementing

Michael Hirschhorn’s AMAZING Algorithm for Proving Ramanujan-Type Congruences^{1}

Edinah GNANG and Doron ZEILBERGER

Preamble

Let p(n) be the number of integer partitions of n. Euler famously proved that

∑_{n=0}^{∞} p(n)q^{n} = ∏_{i=1}^{∞} \frac{1}{1 − q^{i}} .

Srinivasa Ramanujan famously discovered (by glancing at a table of p(n) for 1 ≤ n ≤ 200, computed by the analytic machine, Major Percy Alexander MacMahon’s head) the three congruences

p(5m + 4) ≡ 0 (mod 5) ,
p(7m + 5) ≡ 0 (mod 7) ,
p(11m + 6) ≡ 0 (mod 11) .

The first two are really easy, and the proofs that G.H. Hardy chose to present in his classic book “Ramanujan” ([Ha], pp. 87-88), slightly streamlined, go as follows.

First recall the (purely elementary and shaloshable) identities of Euler and Jacobi :

E(q) = ∏_{i=1}^{∞}(1 − q^{i}) = ∑_{n=−∞}^{∞}(−1)^{n}q^{(3n^{2}+n)/2} , and

E(q)^{3} = ∑_{n=0}^{∞}(−1)^{n}(2n + 1)q^{(n^{2}+n)/2} .

Also recall the obvious fact (but extremely useful [e.g. the AKS algorithm!] ), that follows from the binomial theorem and Fermat’s little theorem, that for every prime ℓ, and any polynomial, or formal power series, f(q), f(q)^{ℓ} ≡ f(q^{ℓ}) (mod ℓ) . In particular E(q)^{ℓ} ≡ E(q^{ℓ}) (mod ℓ) . p(5n+4) is divisible by 5 Since {(n^{2} + n)/2 mod 5 ; 0 ≤ n ≤ 4 , 2n + 1 ≢ 0 (mod 5)} = {0, 1}, we have:

1 First written: June 27, 2013. This version: June 28, 2013. Exclusively published in the Personal Journal of Shalosh

B. Ekhad and Doron Zeilberger as well as in arxiv.org . Accompanied by Maple packages HIRSCHHORN and BOYLAN downloadable from the front of this article http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/mh.html, where there are several sample input and output files containing computer-generated theorems (and proofs!).

The work of DZ was supported in part by the National Science Foundation of the United States of America.

E(q)^{3} ≡ J_{0} + J_{1} (mod 5) ,

where J_{i} consists of those terms in which the power of q is congruent to i modulo 5. Now

∑_{n=0}^{∞} p(n)q^{n} = E(q)^{−1} = \frac{(E(q)^{3})^{3}}{E(q)^{10}} = \frac{(E(q)^{3})^{3}}{(E(q)^{5})^{2}} ≡ \frac{(J_{0} + J_{1})^{3}}{E(q^{5})^{2}} (mod 5) .

Since (J_{0} + J_{1})^{3} = J_{0}^{3} + 3J_{0}^{2}J_{1} + 3J_{0}J_{1}^{2} + J_{1}^{3}, whose terms consist of powers of q that are 0, 1, 2, 3 modulo 5, respectively, none of the powers of q that are congruent to 4 modulo 5 show up, and hence the coefficient of q^{5n+4} is always 0 modulo 5. p(7n+5) is divisible by 7 Since {(n^{2} + n)/2 mod 7 ; 0 ≤ n ≤ 6 , 2n + 1 ≢ 0 (mod 7)} = {0, 1, 3}, we have:

E(q)^{3} ≡ J_{0} + J_{1} + J_{3} (mod 7) ,

where J_{i} consists of those terms in which the power of q is congruent to i modulo 7. Now

∑_{n=0}^{∞} p(n)q^{n} = E(q)^{−1} = \frac{(E(q)^{3})^{2}}{E(q)^{7}} ≡ \frac{(J_{0} + J_{1} + J_{3})^{2}}{E(q^{7})} (mod 7) ,

Since (J_{0} + J_{1} + J_{3})^{2} = J_{0}^{2} + J_{1}^{2} + J_{3}^{2} + 2J_{0}J_{1} + 2J_{0}J_{3} + 2J_{1}J_{3}, whose terms consist of powers of q that are 0, 2, 6, 1, 3, 4 modulo 7, respectively, none of the powers of q that are congruent to 5 modulo 7 show up, and hence the coefficient of q^{7n+5} is always 0 modulo 7. At the bottom of page 88 of Hardy’s above-mentioned classic “Ramanujan”[Ha], he states “There does not seem to be an equally simple proof that p(11n + 6) is divisible by 11”. Over the years there were many proofs, but none as simple and elementary and, most importantly, beautiful!, as the one recently found by Michael Hirschhorn [Hi]. Michael Hirschhorn’s proof that p(11n+6) is divisible by 11 The proof in [Hi] goes like this. It starts the same way. Since {(n^{2} + n)/2 mod 11 ; 0 ≤ n ≤ 10 , 2n + 1 ≢ 0 (mod 11)} = {0, 1, 3, 6, 10}, we have:

E(q)^{3} ≡ J_{0} + J_{1} + J_{3} + J_{6} + J_{10} (mod 11) ,

where J_{i} consists of those terms in which the power of q is congruent to i modulo 11. Now

∑_{n=0}^{∞} p(n)q^{n} = E(q)^{−1} = \frac{(E(q)^{3})^{7}}{E(q)^{22}} ≡ \frac{(J_{0} + J_{1} + J_{3} + J_{6} + J_{10})^{7}}{E(q^{11})^{2}} (mod 11) .

Alas, now the part consisting of the powers that are congruent to 6 modulo 11 in the polynomial (J_{0} + J_{1} + J_{3} + J_{6} + J_{10})^{7} (mod 11) is not identically zero modulo 11, but a certain polynomial of degree 7 in {J_{0}, J_{1}, J_{3}, J_{6}, J_{10}}, (over GF (11)) let’s call it P OL. It is readily seen that, introducing an auxiliary variable t, that P OL(J_{0}, J_{1}, J_{3}, J_{6}, J_{10}) = Coeff_{t^{6}} (J_{0} + J_{1}t + J_{3}t^{3} + J_{6}t^{6} + J_{10}t^{10})^{7} (mod 11) (mod t^{11}−1) , that is not identically zero. But, Since {(3n^{2} + n)/2 mod 11 ; 0 ≤ n ≤ 10 } = {0, 1, 2, 4, 5, 7}, we have,

E(q) = E_{0} + E_{1} + E_{2} + E_{4} + E_{5} + E_{7} ,

where E_{i} consists of those terms in which the power of q is congruent to i modulo 11, and

(E(q)^{3})^{4} = E(q)^{12} = E(q)^{11}E(q) ≡ E(q^{11})E(q) (mod 11) ,

so

(J_{0} + J_{1} + J_{3} + J_{6} + J_{10})^{4} ≡ E(q^{11})(E_{0} + E_{1} + E_{2} + E_{4} + E_{5} + E_{7}) (mod 11) .

By expanding the left side and extracting the complementary powers (mod 11) ( {3, 6, 8, 9, 10}), we get five polynomials of degree 4, let’s call them Q_{3}, Q_{6}, Q_{8}, Q_{9}, Q_{10} that we know are 0 modulo 11 (once the J_{i}’s are replaced by the formal power series they stand for). For m ∈ {3, 6, 8, 9, 10}, we have Q_{m}(J_{0}, J_{1}, J_{3}, J_{6}, J_{10}) = Coeff_{t^{m}} (J_{0} + J_{1}t + J_{3}t^{3} + J_{6}t^{6} + J_{10}t^{10})^{4} (mod 11) (mod t^{11} −1) . Then we ask our beloved computer to find five polynomials of degree 3, (in the variables {J_{0}, J_{1}, J_{3}, J_{6}, J_{10}}), let’s call them R_{3}, R_{6}, R_{8}, R_{9}, R_{10}, such that

P OL ≡ R_{3}Q_{3} + R_{6}Q_{6} + R_{8}Q_{8} + R_{9}Q_{9} + R_{10}Q_{10} (mod 11) .

Since it succeeded (a priori there was no guarantee!), we are done!! Quod Erat Demonstratum.

See the output file http://www.math.rutgers.edu/~zeilberg/tokhniot/oHIRSCHHORN1v, that

contains the above three proofs, (and four other ones!), that was generated, by running the Maple package HIRSCHHORN (that accompanies this article), in three seconds! More Ramanujan Type Congruences Let’s consider, more generally,

∑_{n=0}^{∞} p_{−a}(n)q^{n} = ∏_{i=1}^{∞} \frac{1}{(1 − q^{i})^{a}} .

(Note that p_{−1}(n) = p(n) and p_{24}(n) = τ(n − 1), where τ(n) is Ramanujan’s τ-function).

There are many known Ramanujan-type congruences for p_{−a}(n). Matthew Boylan [B] (Theorem 1.3, where our p_{−a}(n) is denoted by p_{a}(n), and the entry r = 27, l = 31 is erroneous) has found all of them for a odd and ≤ 47.

The first few are (here we restricted our search to primes ≥ 2a + 1).

p_{−1}(5n + 4) ≡ 0 (mod 5) , p_{−1}(7n + 5) ≡ 0 (mod 7) , p_{−1}(11n + 6) ≡ 0 (mod 11) ,

(Ramanujan’s)

p_{−2}(5n + 2) ≡ 0 (mod 5) , p_{−2}(5n + 3) ≡ 0 (mod 5) , p_{−2}(5n + 4) ≡ 0 (mod 5) ,

p_{−3}(11n + 7) ≡ 0 (mod 11) , p_{−3}(17n + 15) ≡ 0 (mod 17) ,
p_{−5}(11n + 8) ≡ 0 (mod 11) , p_{−5}(23n + 5) ≡ 0 (mod 23) ,
p_{−7}(19n + 9) ≡ 0 (mod 19) ,
p_{−9}(19n + 17) ≡ 0 (mod 19) , p_{−9}(23n + 9) ≡ 0 (mod 23) ,
p_{−21}(47n + 42) ≡ 0 (mod 47) .

Thanks to the impressive algorithm of Silviu Radu[R1], every such congruence (and even more general ones, see [R1]), is effectively (and fairly efficiently!) decidable. Let’s hope that Radu would post a public implementation of his method. Since no such an implementation seems to exist, we Emailed Radu, who kindly[R2] showed us how to deduce these (except for the last two, that we are sure can be done just as easily) from his powerful algorithm, by specifying the N_{0} for which checking them for 0 ≤ n ≤ N_{0} would imply them for all 0 ≤ n < ∞.

As impressive as Radu’s algorithm is, it is not elementary. It uses the ‘fancy’, and intimidating, theory of modular functions, that being analytic, is not quite legitimate according to our finitistic and discrete philosophy of mathematics. Hence it is still interesting (at least to us!) to find elementary, Hirschhorn-style proofs. Also, by the principle of serendipity our extension and implementation of Hirschhorn’s method may lead to new things that even modular functions can not do.

Extending Hirschhorn’s Method

Suppose that, for some prime ℓ and some integer r (0 ≤ r < ℓ), we want to prove a congruence of the type

p_{−a}(ℓn + r) ≡ 0 (mod ℓ) .

We first find the smallest integer α such that b := (αℓ − a)/3 is an integer, noting that

E(q)^{−a} = \frac{(E(q)^{3})^{b}}{E(q)^{αℓ}} ≡ \frac{(E(q)^{3})^{b}}{E(q^{ℓ})^{α}} (mod ℓ) .

We now define the subset of {0, 1, …, ℓ − 1}:

Jset(ℓ) := {(n^{2} + n)/2 mod ℓ ; 0 ≤ n ≤ ℓ − 1 , 2n + 1 ≢ 0 (mod ℓ)} ,

and write

E(q)^{3} ≡ ∑_{i∈Jset(ℓ)} J_{i} (mod ℓ) ,

where J_{i} consists of those terms in which the power of q is congruent to i modulo ℓ. Next we define P OL to be the polynomial, in the set of variables {J_{i}; i ∈ Jset(ℓ)},

P OL({J_{i}; i ∈ Jset(ℓ)}) = Coeff_{t^{r}} [ ( ∑_{i∈Jset(ℓ)} J_{i}t^{i})^{b}] (mod ℓ) (mod t^{ℓ} − 1) .

Now, if we are lucky, the polynomial P OL({J_{i}}) would be identically zero (modulo ℓ). In that case we have a Ramanujan-style proof, since the powers of q that are congruent to r modulo ℓ in ((E(q)^{3})^{b}, and hence in E(q)^{−a}, do not show up!

Otherwise, we need to resort to Hirschhorn’s enhancement.

Analogously to Jset(p), let’s define

Eset(ℓ) := {(3n^{2} + n)/2 mod ℓ ; 0 ≤ n ≤ ℓ − 1} ,

the set of residue classes modulo ℓ that show up as powers in the sparse Euler Pentagonal Theorem expression for E(q).

Now let c be the reciprocal of 3 modulo ℓ, and let d = (3c − 1)/ℓ. Then

(E(q)^{3})^{c} = E(q)E(q)^{3c−1} = E(q)E(q)^{dℓ} ≡ E(q)(E(q^{ℓ}))^{d} (mod ℓ).

Now define a set of polynomials, for each 0 ≤ m < ℓ that is not in Eset(ℓ) (i.e. for the members of the complement of Eset(ℓ)):

Q_{m} := Coeff_{t^{m}} [ ( ∑_{i∈Jset(ℓ)} J_{i}t^{i} )^{c}] (mod ℓ) (mod t^{ℓ} − 1) , m ∉ Eset(ℓ) .

We know that all the Q_{m}({J_{i}}) [m ∉ Eset(ℓ)] are 0 modulo ℓ (once the J′_{i}s are replaced by the formal power series, in q, that they stand for).

Finally, we decide whether the polynomial P OL (that lives in the polynomial ring over the Galois Field GF (ℓ) in the J_{i}’s), or one of its powers, belongs to the ideal generated by the polynomials Q_{m}. This can be done (for small ℓ) either directly, using undetermined coefficients, and for larger ℓ, using the Buchberger algorithm (alias Gröbner bases).

The Big Disappointment We naively hoped that Hirschhorn’s method, as explicated and generalized above, would work for all of these other congruences. To our dismay, it failed to prove the congruence p_{−3}(17n + 15) ≡ 0 (mod 17). It turns our that for the specialization

J_{0} = 1 , J_{1} = 1 , J_{3} = 2 , J_{4} = 10 , J_{6} = 9 , J_{10} = 11 , J_{11} = 15 , J_{15} = 12 ,

all the Q_{m} are zero (modulo 17) but P OL ≡ 6 (mod 17) ≠ 0. So, of course, P OL is not in the ideal generated by the Q_{m} in GF (17)[J_{0}, J_{1}, J_{3}, J_{4}, J_{6}, J_{10}, J_{11}, J_{15}]. But there is Hope The Euler and Jacobi identities are but the first two in an infinite sequence of identities, the Macdonald identities[M] made famous in Freeman Dyson’s[D] historic 1972 Gibbs Lecture. In fact, the next-in-line in Macdonald’s identities, earlier found by Winquist[W], was already used to give “a Ramanujan-style proof” of p(11m + 6) ≡ 0 (mod 11). We strongly believe that every Ramanujan-type congruence that can be proved using Radu’s[R1] beautiful algorithm (that relies on the theory of modular functions), has either a “Ramanujan-style”, or “Hirschhorn-style” proof, by using one of the Macdonald identities, that in spite of their “fancy” pedigree (Lie theory) are purely elementary. The Maple package HIRSCHHORN Everything (and more) is implemented in the Maple package HIRSCHHORN available from

http://www.math.rutgers.edu/~zeilberg/tokhniot/HIRSCHHORN .

The webpage

http://www.math.rutgers.edu/~zeilberg/mamarmim/mamarimhtml/mh.html

contains several computer-generated articles outputted by that package. Gröbner via special cases For ℓ > 11, both P OL and the {Q_{m}} get too big for Maple. But by doing sufficiently many specializations (mod ℓ) for a subset of the variables J′_{i}s one can get a fully rigorous proof of ideal

membership. See procedures TerseMikeProof, TerseMikeProofG, TerseMikeProofGviaSC, that

use, respectively, undetermined coefficients, Groöbner bases, and Groöbner bases via special cases. As we already pointed out above, we are not always guaranteed success.

Future Directions We believe that our extension of Hirschhorn’s method could be generalized to more general q-series, including those that are not modular functions. FIRST Encore: The Maple package BOYLAN The Maple package BOYLAN available from

http://www.math.rutgers.edu/~zeilberg/tokhniot/BOYLAN

reproduces and extends Theorem 1.3 of [Bo], albeit empirically. See

http://www.math.rutgers.edu/~zeilberg/tokhniot/oBOYLAN1

for a reproduction of the original (in less than two seconds), and

http://www.math.rutgers.edu/~zeilberg/tokhniot/oBOYLAN2

for many more congruences (going as far as a = 399). SECOND Encore: Infinitely Many Congruences (All having Ramanujan-style proofs!) Now that, thanks to Radu[R1], any specific congruence of the form p_{−a}(ℓn + r) ≡ 0 (mod ℓ), is purely routine (or, more politely, algorithmically provable, or shaloshable), the next stage would be to come up with “infinitely many congruences”. There is, of course, a cheap way to get “infinitely many” such congruences, namely when a = ℓ − 3, since

\frac{1}{E(q)^{ℓ−3}} ≡ \frac{E(q)^{3}}{E(q^{ℓ})} (mod ℓ),

and since the set Jset(ℓ) is about one half of all residue classes, we get many r’s (all the members of the complement of Jset(ℓ)). But, a little less trivially, we can generalize the Ramanujan proof of p(7n + 5) ≡ 0 (mod 7), to the following proposition (we hesitate to call it a theorem, for two reasons. First it is a bit shallow, and second we only have a sketch of a proof [that we are sure can be easily completed, but we have better things to do]). [Added June 28, 2013: Michael Hirschhorn instantly completed our skecth by proving the lemma, see:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/MikeHirschhornsProofOfLemma.pdf,

so the proposition below, for what it is worth, is completely proved.] Proposition: Let ℓ be a prime that is either 7 or 11 modulo 12 and let r := (ℓ − 6)/24 (mod ℓ), then

p_{−(ℓ−6)}(nℓ + r) ≡ 0 (mod ℓ) .

Sketch of a Ramanujan style proof. It is easy to see that r := (ℓ − 6)/24 (mod ℓ) ∉ Jset(ℓ) + Jset(ℓ) (mod ℓ), thanks to the following (presumably elementary) lemma, that we verified empirically for ℓ ≤ 2000.

Elementary Lemma: Let ℓ be a prime that leaves remainder 7 or 11 when divided by 12. Then for any 0 ≤ n_{1}, n_{2} < ℓ such that

\frac{n_{1}(n_{1} + 1)}{2} + \frac{n_{2}(n_{2} + 1)}{2} ≡ r (mod ℓ) ,

we must have either n_{1} = (ℓ − 1)/2 or n_{2} = (ℓ − 1)/2.

Using the lemma it follows that

\frac{1}{E(q)^{ℓ−6}} = \frac{(E(q)^{3})^{2}}{E(q^{ℓ})} ≡ \frac{(∑_{i∈Jset(ℓ)} J_{i})^{2}}{E(q^{ℓ})} (mod ℓ)

and the powers of q that are r modulo ℓ do not show up.

It would be interesting to come up with an infinite family provable by Hirschhorn-style proofs!

Acknowledgment: We are grateful to George Andrews, Bruce Berndt, Lev Borisov, Shaun Cooper, Frank Garvan, and Michael Hirschhorn, for very useful advice, and to Silviu Radu for permission to post [R2].

References

[B] Matthew Boylan, Exceptional congruences for powers of the partition functions, Acta Arith. 111 (2004), 187-203.

[D] Freeman J. Dyson, Missed opportunities, Bulletin of the American Mathematical Society 78 (1972), 635652.

[Ha] G.H. Hardy, “Ramanujan”, Cambridge University Press, 1940.

[Hi] Michael D. Hirschhorn, A short and simple proof of Ramanujan’s mod 11 partition congruence, preprint available from

http://web.maths.unsw.edu.au/~mikeh/webpapers/paper184.pdf

[M] I.G. Macdonald, I. G., Affine root systems and Dedekind’s -function, Inventiones Mathematicae 15 (1972), 91143

[R1] Silviu Radu, An algorithmic approach to Ramanujan’s congruences, Ramanujan J. 20 (2009), 215-251 .

[R2] Silviu Radu, Email message to Doron Zeilberger,

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/SilviuRaduMessageJune2013.pdf

[W] Lasse Winquist, An elementary proof of p(11m + 6) ≡ 0 (mod 11), J. Combinatorial Theory 6, 5659.

Edinah K. Gnang, Computer Science Department, Rutgers University (New Brunswick), Piscat-

away, NJ 08854, USA. gnang at cs dot rutgers dot edu

Doron Zeilberger, Mathematics Department, Rutgers University (New Brunswick), Piscataway, NJ

08854, USA. zeilberg at math dot rutgers dot edu