Generalizing and Implementing

Michael Hirschhorn’s AMAZING Algorithm for Proving Ramanujan-Type Congruences

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, that for every prime p, and any polynomial, or formal power series, f(q), f(q)^{p} ≡ f(q^{p}) (mod p) . In particular E(q)^{p} ≡ E(q^{p}) (mod p) .

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:

E(q)^{3} = J_{0} + J_{1} ,

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) ,

and only powers congruent to 0, 1, 2, 3 modulo 5 show up, and hence the coefficient of q^{5n+4} is always 0 modulo 5. p(7n+4) 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} ,

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) ,

and none of the powers congruent to 5 modulo 7 show up, and hence the coefficient of q^{7n+5} is always 0 modulo 5. 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 for p(11n+6) The proof in [Hi] goes like this. It starts the same way:

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. But we also 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)^{12} (mod 11) ≡ 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 P_{3}, P_{6}, P_{8}, P_{9}, P_{10}. 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 Q_{3}, Q_{6}, Q_{8}, Q_{9}, Q_{10}, such that

P ≡ Q_{3}P_{3} + Q_{6}P_{6} + Q_{8}P_{8} + Q_{9}P_{9} + Q_{10}P_{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 HIRSCHHORN, in three seconds! Generalization 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). Now let’s do an exchaustive computer search for congruences of the form

p_{−a}(P n + r) ≡ 0 (mod P) ,

for primes P ≤ 101, and 1 ≤ a ≤ 50. [[1, 4, 5], [1, 5, 7], [1, 6, 11], [2, 2, 5], [2, 3, 5], [2, 4, 5], [3, 7, 11], [3, 15, 17], [5, 8, 11], [5, 5, 23], [7, 9, 19], [9, 17, 19], [9, 9, 23], [21, 42, 47]] By pure guessing, our beloved servant, Shalosh B. Ekhad, discovered the following 14 successful triples (rediscovering, for a = 1, the original three Ramanujan congruences).

[a, r, P] ∈ {[[1, 4, 5], [1, 5, 7], [1, 6, 11],

[2, 2, 5], [2, 3, 5], [2, 4, 5]

[3, 7, 11], [3, 15, 17],

[5, 8, 11], [5, 5, 23],

[7, 9, 19],

[9, 17, 19], [9, 9, 23],
[21, 42, 47]} .

Silviu Radu [R2] kindly 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.

But it is still nice to have a purely elementary proof, in the style of Hirschhorn. This is implemented in the Maple package

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

For primes up to 11 it works in a few seconds, alas, a naive implementation of Hirschhorn’s method, using “undetermined coefficients” runs ouf of memory.

Luckily we have Gröbner Bases and the Buchberger algorithm. The question boils down to proving that P belongs to the radical of the ideal generated by the P_{i}-s. Even here things run out of time and memory (in Maple), but since we are working over GF (p), by getting sufficiently many specializations, it is possible to prove ideal memberships for many special cases. Then we can either do all possible p^{r} specializations of freezing (any) r of the variables {J[i]}, or a semi-rigorous proof if we do a small random selection.

Since Radu[R1] has his powerful algorithm, we didn’t bother to finish this up, but we know that it is possible to always try to do it. Of course, it is possible, but unlikely, that some congruences are not provable by Hirschhorn’s elementary approach. So let us conclude with a

Meta Conjecture: Any Ramanujan-type congruence for so-called modular forms, that Radu[R1] famously proved is always doable with his powerful algorithm, that uses the deep theory of modular forms and functions, can also be done by only using Hirschhorn’s elementary approach as extended in this article, together with the purely elementary Buchberger algorithm over finite fields.

Readers are welcome to see the front of this article for sample input and output.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/hirschhorn.html .

Acknowledgement: We are grateful to Lev Borisov for insightful advice, and to Silviu Radu for permission to post [R2] and for useful discussion.

References

[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/paper188.pdf

[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

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