On Rademacher’s Infinite Partial Fraction Conjecture

Andrew V. Sills and Doron Zeilberger

October 1, 2011

“It is a capital mistake to theorise before one has data. Insensibly one begins to twist facts to suit theories, instead of theories to suit facts.”—Sherlock Holmes to Dr. Watson in A Scandal in Bohemia by A. Conan Doyle, 1891.

Important Note: This article is accompanied by the Maple package HANS, downloadable from

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

The “front” of this article,

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

contains lots of supporting input and output files.

1 Introduction

Let p_{N}(n) denote the number of partitions of the integer n into at most N parts. The generating function of p_{N}(n),

F_{N}(x) := ∑_{n≥0} p_{N}(n)x^{n} = ∏_{j=1}^{N} \frac{1}{1 − x^{j}} ,

may be decomposed into partial fractions:

∏_{j=1}^{N} \frac{1}{1 − x^{j}} = ∑_{k=1}^{N}_{∑_{0≤h<k} ; gcd(h,k)=1} ∑_{l=1}^{⌊N/k⌋} \frac{C_{h,k,l}(N)}{(x − e^{2πih/k})^{l}} .  (1.1)

We shall refer to the C_{h,k,l}(N) defined by (1.1) as the Rademacher coefficients.

Near the end of his posthumously published masterpiece Topics in Analytic Number Theory [4, p. 302], Hans Rademacher made the following conjecture:

Rademacher’s Conjecture. For all integers h, k, l such that 0 ≤ h < k, gcd(h, k) = 1 and l ≥ 1, lim_{N→∞} C_{h,k,l}(N) exists and equals

R_{h,k,l} := −2π (\frac{π}{12})^{3/2} \frac{e^{πi(s(h,k)+2hl/k)}}{k^{5/2}} Δ_{α}^{l−1}L_{3/2} (−\frac{π^{2}}{6k^{2}} (α + 1)) ,  (1.2)

evaluated at α = \frac{1}{24}, where s(h, k) = ∑_{μ=1}^{k−1} (\frac{μ}{k} − ⌊\frac{μ}{k}⌋ − \frac{1}{2}) (\frac{hμ}{k} − ⌊\frac{hμ}{k}⌋ − \frac{1}{2}) is the Dedekind sum, Δ_{α} is the forward difference operator, so that

Δ_{α}^{j}f(α) = ∑_{h=0}^{j}(−1)^{h}\binom{j}{h}f(α + j − h),

and

L_{3/2}(−y^{2}) = −\frac{1}{2\sqrt{π}y^{2}} (2 cos(2y) − \frac{sin(2y)}{y}) .

In particular, if the Rademacher conjecture would have been true then it would have followed that

lim_{N→∞} C_{0,1,1}(N) = R_{0,1,1}(= −\frac{6}{25} (1 + \frac{2\sqrt{3}}{5π}) = −0.292927573960 …),

lim_{N→∞} C_{0,1,2}(N) = R_{0,1,2}(= \frac{144}{1225} + \frac{5616}{42875π} = 0.1897670688440 …),

lim_{N→∞} C_{1,2,1}(N) = R_{1,2,1}(= −\frac{2\sqrt{6}}{25} (cos \frac{5π}{12} − \frac{12}{5π} sin \frac{5π}{12} ) = 0.093882853484 …).

(Let us make the minor remark, for the sake of mathematical accuracy, that the floating-point approximation for the value of R_{0,1,1} stated by Rademacher [4, p. 302] was erroneous, as were the exact values of R_{0,1,2} and R_{1,2,1} [for the latter he gave exactly one half of the correct value]. These erroneous values were quoted, without correction, by Andrews [1, p. 388].)

Rademacher supplied (with one error) a table of values for C_{0,1,1}(N), C_{0,1,2}(N), and C_{1,2,1}(N) for N = 1, 2, 3, 4, 5, and in fact these values are not too far off from conjectured “N = ∞” case.

Rademacher began work on the book in which this conjecture appeared [4] no later than 1944 and was still working on it at the inception of his final illness. Thus as the final version was edited and published by Rademacher’s students Emil Grosswald, Joseph Lehner, and Morris Newman, after Rademacher’s death in 1969, we will never know whether Rademacher came to doubt the truth of the conjecture after he had written it down. However, George Andrews reports that Rademacher discussed the conjecture in a course he taught at the University of Pennsylvania in the 1961–1962 academic year.

In [3], Augustine Munagi considered an different type of partial fraction decomposition called q-partial fractions, and proved a special case of the analog of the Rademacher conjecture, relative to the q-partial fraction decomposition.

We should also note that the first to cast doubts on the Rademacher conjecture were Jane Friedman and Leon Ehrenpreis. Ehrenpreis [2, p. 317] stated, “If one attempts to carry out the usual type of partial fraction decomposition of the partition function term-by-term, it is difficult to compute the coefficients. My student, Jane Friedman, spent a great deal of time trying to apply computer algorithm methods to compare the coefficients with those of Rademacher… Unfortunately, the computer study proved inconclusive.”

In this article, we present overwhelming evidence against this conjecture, taken literally, but we will present ample evidence for a modified conjecture. Additionally, we will present a fast algorithm for generating the Rademacher coefficients, and formulas for a selection of particular Rademacher coefficients.

2 Empirical evidence against the Rademacher conjecture

2.1 The actual behavior of the sequence C_{0,1,1}(N)

The values of C_{0,1,1}(N), for 1 ≤ N ≤ 400 are provided, in both exact rational and floating point approximation form, at

http://www.math.rutgers.edu/ zeilberg/tokhniot/oHANS1

Figures 1 and 2 are graphical summaries of C_{0,1,1}(N).

Figure 1: Graph of C_{0,1,1}(N) for N from 1 to 100, together with the line y = −0.2929276

Figure 2: Graph of C_{0,1,1}(N) for N from 1 to 200.

Notice that C_{0,1,1}(25) differs from Rademacher’s conjectured value of C_{0,1,1}(∞) by less than 0.000032, but then things go down hill (for the conjecture) from there, and get particularly bad after about n = 150. Numerical evidence points to the sequence C_{0,1,1}(N) oscillating and attaining arbitrarily large positive and negative values. The same thing is true for other sequences C_{h,k,l}(N); see the output at the webpage of this article

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

By examining the graphs in Figures 1 and 2 and the associated numerical data, it seems reasonable to state the following alternative conjecture:

Conjecture 1. C_{0,1,1}(N) is an oscillating function of N of “period” about 32, whose absolute value increases without bound as N increases.

By “period” 32 we mean that the peaks and valleys, eventually, recur at a period of 32. We also noticed, numerically, that the elevations and depths of successive peaks and valleys roughly grows exponentially with a factor around 8.

2.2 How to compute the sequence C_{0,1,1}(N) fast

If you use the definition of C_{0,1,1}(N), or Andrews’s formula [1, p. 388, Theorem 1], you can’t go very far, even with Maple. Rademacher calculated C_{0,1,1}(N) for N = 1, 2, 3, 4, 5, presumably by hand, and made an error in the N = 5 case. Andrews [1, p. 388], who had access to a computer algebra system in 2003, corrected Rademacher’s error at N = 5 and extended the list to N = 6, 7, 8.

We need to be more clever. A fast recurrence can be derived as follows. Since

∏_{j=1}^{N} \frac{1}{1 − x^{j}} = ∑_{l=1}^{N} \frac{C_{0,1,l}(N)}{(x − 1)^{l}} + …,

we can multiply both sides by (x − 1)^{N} and get

(x − 1)^{N} ∏_{j=1}^{N} \frac{1}{1 − x^{j}} = ∑_{r=0}^{N−1} D_{r}(N)(x − 1)^{r} + ….

Once we know D_{r}(N), we can find C_{0,1,l}(N), since they equal D_{N−l}(N). It remains to find a fast recurrence for D_{r}(N).

By definition, we have:

\frac{1 − x^{N}}{x − 1} (∑_{r=0}^{∞} D_{r}(N)(x − 1)^{r}) = ∑_{r=0}^{∞} D_{r}(N − 1)(x − 1)^{r} .

Letting z = x − 1, this is:

\frac{1 − (z + 1)^{N}}{z} (∑_{r=0}^{∞} D_{r}(N)z^{r}) = ∑_{r=0}^{∞} D_{r}(N − 1)z^{r} .

By the binomial theorem,

− ( ∑_{a=0}^{N−1} \binom{N}{a + 1}z^{a}) (∑_{r=0}^{∞} D_{r}(N)z^{r}) = ∑_{r=0}^{∞} D_{r}(N − 1)z^{r} .

Equating coefficients of z^{r} we get:

ND_{r}(N) + ∑_{a=1}^{r} \binom{N}{a + 1}D_{r−a}(N) = −D_{r}(N − 1) .

And finally:

D_{r}(N) = −\frac{D_{r}(N − 1)}{N} − ∑_{a=1}^{r} \frac{1}{N} \binom{N}{a + 1}D_{r−a}(N) .

This is implemented in procedure C01 of HANS.

The same argument leads to efficient recurrences for C_{h,k,l}(N), except that now we have to distingish between the case when N is divisible by k and when it is not, yielding two different recurences. This is implemented in procedure ChklN(h,k,l,N) of HANS.

2.3 C_{1,2,1}(N)

The values of C_{1,2,1}(N) for 1 ≤ N ≤ 700, in both exact rational form and approximate floating point form are provided at

   http://www.math.rutgers.edu/ zeilberg/tokhniot/oHANS3

Graphical summaries are provided in Figures 3 and 4.

Figure 3: Graph of C_{1,2,1}(N) for N from 1 to 150, together with the line y = 0.09388285

Figure 4: Graph of C_{1,2,1}(N) for N from 1 to 300, together with the line y = 0.09388285

3 “Top down” formulas for the Rademacher Coefficients

3.1 C_{0,1,l}(N)

As Rademacher already pointed out, it seems hopeless to get a closed-form formula for C_{h,k,l}(N) for l = 1, 2, …, but if you work your way up from the “top” one can conjecutre, and then rigorously prove explicit formuals for C_{h,k,N−r}(N), that alas, get increasingly more complicated as r gets larger.

Conjecture 2.

C_{0,1,N−r}(N) = \frac{(−1)^{N+r}}{4^{r}N!r!} P_{0,1,N−r}(N),

where P_{0,1,N−r}(N) is a convex, alternating, monic polynomial of degree 2r whose only real roots are 0 and 1.

Theorem 3. Explicit formulas for the P_{0,1,N−r}(N) of Conjecture 2 may be given for any specific r, in particular, we have

P_{0,1,N}(N) = 1  (3.1)
P_{0,1,N−1}(N) = N^{2} − N  (3.2)
P_{0,1,N−2}(N) = N^{4} − \frac{22N^{3}}{9} + \frac{13N^{2}}{3} − \frac{26N}{9}  (3.3)
P_{0,1,N−3}(N) = N^{6} − \frac{13N^{5}}{3} + \frac{43N^{4}}{3} − 25N^{3} + \frac{98N^{2}}{3} − \frac{56N}{3}  (3.4)

P_{0,1,N−4}(N) = N^{8} − \frac{20N^{7}}{3} + \frac{862N^{6}}{27} − \frac{21104N^{5}}{225} + \frac{29039N^{4}}{135} − \frac{14548N^{3}}{45} + \frac{9892N^{2}}{27} − \frac{42896N}{225}

P_{0,1,N−5}(N) = N^{10} − \frac{85N^{9}}{9} + \frac{1610N^{8}}{27} − \frac{33862N^{7}}{135} + \frac{36869N^{6}}{45} − \frac{269371N^{5}}{135} + \frac{34712N^{4}}{9}

− \frac{716548N^{3}}{135} + \frac{742928N^{2}}{135} − \frac{120448N}{45}

P_{0,1,N−6}(N) = N^{12} − \frac{38N^{11}}{3} + \frac{905N^{10}}{9} − \frac{675574N^{9}}{1215} + \frac{321073N^{8}}{135} − \frac{158916134N^{7}}{19845}

+ \frac{4121695N^{6}}{189} − \frac{134142298N^{5}}{2835} + \frac{11129492N^{4}}{135} − \frac{908622824N^{3}}{8505}

+ \frac{2805920N^{2}}{27} − \frac{317019904N}{6615}

Remark 4. Readers desiring formulas for C_{0,1,N−r}(N) for r > 6 are directed to the ChkFormula procedure in the HANS Maple package. Remark 5. From the above (and additional data not reproduced here but available at the website), we may deduce that

P_{0,1,N−r}(N) = N^{2r} − \frac{2r^{2} + 7r}{9} N^{2r−1} + \frac{2r^{4} + 6r^{3} + \frac{287}{2}r^{2} − \frac{303}{2}r}{9^{2}} N^{2r−2} + lower order terms.

Proof of Theorem 2. Define G_{N} := (x − 1)^{N}F_{N}(x). Then G_{N} has a Taylor series expansion about x = 1, whose first N coefficients are the Rademacher coefficients:

G_{N} = ∑_{j=0}^{N−1} C_{0,1,N−j}(N)(x − 1)^{j} + O((x − 1)^{N}).

Clearly,

(1 − x^{N})G_{N} = (x − 1)G_{N−1}.  (3.5)

Expanding (1 − x^{N}) on the left hand side of (3.5) as a Taylor polynomial about x = 1, we have

(− ∑_{j=1}^{N} \binom{N}{j}(x − 1)^{j}) ( ∑_{j=0}^{N−1} C_{h,k,N−j}(N)(x − 1)^{j} + higher degree terms )

= ∑_{j=1}^{N−1} C_{0,1,N−j}(N − 1)(x − 1)^{j} + higher degree terms (3.6)

Comparing the coefficients of (x − 1)^{1} on both sides of (3.6), we find

−NC_{0,1,N}(N) = C_{0,1,N−1}(N − 1).

Solving the recurrence with the initial condition C_{0,1,1}(1) = −1, yields

C_{0,1,N}(N) = \frac{(−1)^{N}}{N!} ,  (3.7)

which is (3.1).

Comparing the coefficients of (x − 1)^{2} on both sides of (3.6), we find, taking into account (3.7),

−NC_{0,1,N−1}(N) − \binom{N}{2}\frac{(−1)^{N}}{N!} = C_{0,1,N−2}(N − 1)  (3.8)

with initial condition C_{0,1,1}(2) = −\frac{1}{4} yields

C_{0,1,N−1}(N) = \frac{(−1)^{N+1}}{4(N − 2)!},  (3.9)

which is (3.2).

Comparing the coefficients of (x − 1)^{3} on both sides of (3.6), we find, taking into account (3.7) and (3.9),

−NC_{0,1,N−2}(N) − \binom{N}{2}\frac{(−1)^{N+1}}{4(N − 2)!} − \binom{N}{3}\frac{(−1)^{N}}{N!} = C_{0,1,N−3}(N − 1)  (3.10)

with initial condition C_{0,1,1}(3) = −\frac{17}{72} yields

C_{0,1,N−2}(N) = \frac{(−1)^{N}(9N^{2} − 13N + 26)}{288(N − 2)!},  (3.11)

which is (3.3). Results for larger r follow analogously.

3.2 C_{1,2,l}(N)

Let us now define Ḡ_{N}, analogous to G_{N}. Let

Ḡ_{N} := (x + 1)^{⌊N/2⌋}F_{N}(x).

Then Ḡ_{N} has a Taylor series expansion about x = −1, whose first ⌊\frac{N}{2} ⌋ coefficients are the Rademacher coefficients:

Ḡ_{N} = ∑_{r=0}^{⌊N/2⌋−1} C_{1,2,⌊N/2⌋−r}(N)(x + 1)^{r} + O((x + 1)^{⌊N/2⌋}).

We now abandon the use of the floor function. Notice that

(1 − x^{2n−1})(1 − x^{2n})Ḡ_{2n} = (x + 1)Ḡ_{2n−2}.  (3.12)

Thus, by expanding the two left most factors on the left side as a Taylor series about x = −1,

\{ ∑_{r=1}^{4n−1}(−1)^{r+1} [\binom{4n − 1}{r} + \binom{2n}{r} − \binom{2n − 1}{r}] (x + 1)^{r}\}

× (∑_{r=0}^{n−1} C_{1,2,n−r}(2n)(x + 1)^{r} + higher degree terms )

= ∑_{r=1}^{n−1} C_{1,2,n−r}(2n − 2)(x + 1)^{r} + higher degree terms (3.13)

By comparing coefficients of (x + 1)^{r} in both sides of (3.13) and solving the recurrences, we obtain formulas for C_{1,2,n−r}(2n) analogous to those for C_{0,1,N−r}(N).

Comparing coefficients of (x + 1) on both sides of (3.13), we find

4nC_{1,2,n}(2n) = C_{1,2,n−1}(2n − 2),

which, together with initial condition C_{1,2,1}(2) = \frac{1}{4}, yields

C_{1,2,n}(2n) = \frac{1}{2^{2n}n!}.  (3.14)

Comparing coefficients of (x + 1)^{2} on both sides of (3.13), and taking into account (3.14), we find

4nC_{1,2,n−1}(2n) − \frac{2n − 1}{4^{n−1}(n − 1)!} = C_{1,2,n−2}(2n − 2),

which, together with initial condition C_{1,2,1}(4) = \frac{1}{8}, yields

C_{1,2,n−1}(2n) = \frac{n}{2^{2n}(n − 1)!}.  (3.15)

Comparing coefficients of (x + 1)^{3} on both sides of (3.13), and taking into account (3.14) and (3.15), we find

4nC_{1,2,n−2}(2n) − \frac{4n^{2}(2n − 1)}{4^{n}(n − 1)!} + \frac{n(2n − 1)(16n − 13)}{3 · 4^{n}n!} = C_{1,2,n−3}(2n − 2),

which, together with initial condition C_{1,2,1}(6) = \frac{461}{4608}, yields

C_{1,2,n−2}(2n) = \frac{18n^{3} − 8n^{2} + 15n + 2}{3^{2} · 2^{2n+2}(n − 1)!}.  (3.16)

This process can be continued indefinitely with higher powers of (x + 1), e.g.

C_{1,2,n−3}(2n) = \frac{(n^{2} + 1)(6n^{3} − 8n^{2} + 9n + 2)}{3^{2} · 2^{2n+2}(n − 1)!},  (3.17)

C_{1,2,n−4}(2n) = \frac{2700n^{7} − 7200n^{6} + 15100n^{5} − 17448n^{4} + 21205n^{3} − 8880n^{2} + 13350n + 3423}{25 · 3^{4} · 2^{2n+5}(n − 1)!}. (3.18)

Of course, the observation

(1 − x^{2n})(1 − x^{2n+1})Ḡ_{2n+1} = (x + 1)Ḡ_{2n−1}

leads to analogous formulas for the C_{1,2,n−r}(2n + 1), e.g.,

C_{1,2,n}(2n + 1) = \frac{1}{2^{2n+1} n!},  (3.19)

C_{1,2,n−1}(2n + 1) = \frac{2n^{2} + 2n + 1}{2^{2n+2} n!},  (3.20)
C_{1,2,n−2}(2n + 1) = \frac{18n^{5} + 46n^{4} + 61n^{3} + 53n^{2} + 29n + 9}{9 · 2^{2n+3} (n + 1)!},  (3.21)

C_{1,2,n−3}(2n + 1) = \frac{(2n^{2} + 2n + 3)(6n^{4} + 4n^{3} + 3n^{2} + 2n + 3)}{9 · 2^{2n+4}n!}.  (3.22)

Clearly, the same idea can be used to find formulas for C_{h,k,n−j}(kn + r) for any h, k, j, r. This has been implemented in the procedure ChkFormula in the HANS Maple package. For those desiring automatically generated papers, containing both formulas of this type and their proofs, please use the HansTopDownAutoPaper procedure in the HANS Maple package.

4 Close Encounters of the Rademacher Kind

While it appears that lim_{N→∞} C_{h,k,l}(N) does not exist for any (h, k, l), we can nonetheless define B_{h,k,l}(N) to be the N which comes closest to Rademacher’s conjectured value of C_{h,k,l}(∞). This is implemented in the CloseEncounters procedure in HANS.

l B_{0,1,l}(N) absolute difference absolute ratio
1  25  0.0003177  0.99989
2  47  0.0001434  0.99924
3  71  0.0000828  0.99991
4  149  0.0000009  1.00001
5  109

Notice that the first few values of B_{0,1,l}(N) are close to 24l. This motivates us to consider comparing C_{0,1,l}(24l) to R_{0,1,l}, Rademacher’s conjectured value of C_{0,1,l}(∞).

\begin{matrix}l & |C_{0,1,l}(24l) − R_{0,1,l}| & |C_{0,1,l}(24l)/R_{0,1,l}| \\ 1 & 0.0053741095 & 1.018346206 \\ 2 & 0.0015044594 & 1.007927400 \\ 3 & 0.00033240887 & 0.996241370 \\ 4 & 0.00004427030 & 1.001376635 \\ 5 & 0.000011288321 & 0.9988220859 \\ 6 & 0.000001686611 & 1.0006971253 \\ 7 & 0.0000001275687 & 0.9997575030 \\ 8 & 0.0000000110523 & 1.0000986383 \\ 9 & 0.00000000239242 & 0.9999562770 \\ 10 & 0.000000005333208 & 1.0000141594 \\ 11 & 0.0000000187490584 & 0.9999947242 \\ 12 & 0.0000000393434274 & 1.0000017401 \end{matrix}

Thus we have some evidence that even though the N for which C_{0,1,l}(N) is closest to R_{0,1,l} is not N = 24l, C_{0,1,l}(24l) seems to provide a good approximation to R_{0,1,l}.

References

[1] G. E. Andrews, Partitions: at the interface of q-series and modular forms, Ramanujan J. 7 (2003) 385–400.

[2] L. Ehrenpreis, Function theory for Rogers-Ramanujan-like partition identities, in A Tribute to Emil Grosswald: Number Theory and Related Analysis, ed. M. I. Knopp and M. Sheingorn, Contemporary Math 143 (1993) 259–320.

[3] A. O. Munagi, The Rademacher conjecture and q-partial fractions, Ramanujan J. 15 (2008) 339–347.

[4] H. Rademacher, Topics in Analytic Number Theory, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen Band 169, Springer, 1973.