APPLICATIONS OF THE HARDY-RAMANUJAN PARTITION THEORY

TO LINEAR DIOPHANTINE PROBLEMS

by
Michael Anshel and Dorian Goldfeld1

§1. Introduction and summary of results

In 1918 G.H. Hardy and S. Ramanujan [H-R] gave an asymptotic formula for
the now classic partition function p(n) which equals the number of unrestricted
partitions of n. The value of p(n) is precisely the number of solutions in nonnegative
integers to the linear diophantine equation

1 · y1 + 2 · y2 + ··· + n · yn = n.

Hardy and Ramanujan proved that

1 √ 2n
(1) p(n) ∼ √ eπ 3
4n 3

and actually obtained a more precise asymptotic formula where the error tends
to 0 as n → ∞. It was quite suprising at the time to find by analytic methods
an asymptotic formula for an integer valued function (which grows exponentially)
which was correct up to a term which rapidly approached zero! The method they
developed to prove this result was subsequently refined by Hardy and Littlewood
and is now generally referred to as the Hardy-Littlewood method. The key to
proving (1) is the fact that the generating function

∞
Y
φ(τ ) = (1 − e2πimτ )−1
m=1
(2) ∞
X
= p(m) e2πimτ
m=0

satisfies the modular relation [H-R]

r
cτ + d πi aτ +b aτ + b
(3) φ(τ ) =  e 12 (τ − cτ +d ) φ( )
i cτ + d

for all matrices ac db ∈ P SL(2, Z), where  is a certain 24th root of unity.

We shall now give higher dimensional versions of the Hardy-Ramanujan partition

theory and apply it to the following linear diophantine problem.

1 Supported in part by NSF grant DMS-87-02169

1
2

Given positive integers k, t, nonnegative integers wi,j for 1 ≤ i ≤ k, 1 ≤ j ≤ t

and nonnegative integers n1 , ..., nk consider the linear diophantine problem

n1 = w1,1 y1 + w1,2 y2 + · · · + w1,t yt

n2 = w2,1 y1 + w2,2 y2 + · · · + w2,t yt
·
(4)
·
·
nk = wk,1 y1 + wk,2 y2 + · · · + wk,t yt

which can be written succinctly as

(5) N = WY

where N = (n1 , ..., nk ), and W denotes the matrix W = (wi,j ). Here N, W are fixed
and given, and  
y1
 .. 
Y = . 
yt
consists of nonnegative integral variables.
It was pointed out by Euler in 1748 [Eu], (see also [Sch]) that the number of
nonnegative integral solutions to (4) is precisely equal to the coefficient of xn1 1 ···xnk k
in the expansion of
w w
−1 w w
−1
R(x1 , ..., xk ) = 1 − (x1 1,1 · · · xk k,1 ) · · · 1 − (x1 1,t · · · xk k,t ) .

In the case of one equation (i.e. k = 1 n1 = n, etc.) let N (n) denote the number
of solutions of
w1 y1 + · · · + wt yt = n.
Then (see [Sch])
N (n) 1
lim = .
n→∞ nk−1 (k − 1)! w1 · · · wt
One of the principal difficulties of working with R(x1 , ..., xk ) is that it doesn’t
have the nice properties of a modular function. Our approach is to follow Hardy
and Ramanujan and develop instead a generalized partition theory for the linear
diophantine problem (4). This will enable us to get sharp estimates for the solutions
of (4). It seems likely that this method is capable of further refinements and
improvements and should ultimately lead to asymptotic results. This would require,
however, a higher dimensional version of the Hardy-Littlewood method.
Let
X Y t 
S(N, W ) = p(yj )
N =W Y j=1

where the sum ranges over nonnegative integral solutions in Y to the linear dio-
phantine equation (4). We now construct a generating function in several variables
for S(N, W ).
 3

For arbitrary variables xi , i = 1, 2, . . . , k, let

k
Y
(6) Xj = (xi )wi,j .
i=1

Define
∞
t Y
Y
F (x1 , ..., xk ) = (1 − (Xj )r )−1 .
j=1 r=1

It follows that
∞
t Y
Y
1 + Xj r + Xj 2r + Xj 3r + · · ·


F (x1 , ..., xk ) =
j=1 r=1

Y ∞
t X 
m
= p(m) Xj
j=1 m=0

Y ∞
t X k
Y 
= p(m) (xi )mwi,j
j=1 m=0 i=1
∞ ∞ ∞ k P 
X X X Y t
mj wi,j
= ··· p(m1 )p(m2 ) · · · p(mt ) (xi ) j=1 .
m1 =0 m2 =0 mt =0 i=1

Hence, we obtain
∞
X ∞
X
(7) F (x1 , ..., xk ) = ··· S(N, W ) x1 n1 · · · xk nk .
n1 =0 nk =0

Now, let
∞
X
f (τ ) = a(n)e2πinτ
n=1

be an arbitrary holomorphic modular form for SL(2, Z) with nonnegative Fourier

coefficients a(n). Assume that
 
−s aτ + b
f (τ ) = (cτ + d) f
cτ + d

ab


for all matrices cd ∈ SL(2, Z), so that f (τ ) has weight s.
Let us define
X
S` (N, W ) = p(y1 ) · · · p(y` ) a(y`+1 ) · · · a(yt ).
N =W Y

Since we have the Hecke estimate (see [Gu])

s
a(n)  n 2
4

and √
1 π 2n
p(n) ∼ √ e 3
4n 3
we see that S` (N, W ) counts the solutions to N = W Y and selectively weights
(stresses) y1 , . . . , y` .
By an argument similar to the proof of (7), we see that S` (N, W ) is precisely
the coefficient of e2πin1 τ1 · · · e2πink τk in
`
Y k
X  Yt k
X 
φ τi wi,j · f τi wi,j .
j=1 i=1 j=`+1 i=1

We can now state our final results.

Theorem (1) Let δ1 , δ2 , ...,

 δk be arbitrary nonnegative real numbers. Let q ≥ 1,
i
P k
and define C = φ q+(1/q) , and Λj = i=1 δi wi,j . Then we have

t √ p  12  
1 π
−Λj +(Λj )−1
Y
t 2π[n1 δ1 +···+nk δk ]
S(N, W ) ≤ C e q + 1/q Λj e
4 12 .
j=1
1
Λj < q+(1/q)

Theorem
 (2) Let δ1 , δ2 , ..., δkbe arbitrary real numbers. Let q, q 0 ≥ 1,
 nonnegativeP
i i k
Cφ = φ q+(1/q) , Cf = f q0 +(1/q 0) , and Λj = i=1 δi wi,j , where f is an
arbitrary holomorphic modular form of weight s for SL(2, Z).
Then we have the estimate

S` (N, W ) ≤ e2π[n1 δ1 +···+nk δk ] Uφ Vf

where
` √ p  21  
1 π
−Λj +(Λj )−1
Y
`
Uφ = C φ q + 1/q Λj e
4 12 ,
j=1
1
Λj < q+(1/q)
and
`
Y hp p  i−s
t−`
Vφ = Cf q 0 + 1/q 0 Λj .
j =`+1
1
Λj < q0 +(1/q 0)

Let B` (N, W ) denote the bound for S` (N, W ) given in theorem (2). Since very
precise asymptotics exist for p(n), it is possible to remove the weights without
considerable loss of accuracy. In this manner we obtain:
 5

Theorem (3) If N = W Y admits a solution Y , then for arbitrary nonnegative real

numbers δ1 , · · · , δk we have
`  k ` Xk −1 
X √ 1 X  X
yj ≤ ni δi + δi wi,j .
j=1
2 i=1 j=1 i=1

Assume there exists a solution Y of N = W Y so that p(y1 ) · · · p(y` ) a(y`+1 ) · · · a(yt )

is minimal subject to a(y`+1 ) · · · a(yt ) ≥ 1, where the a(n) are nonnegative Fourier
coefficients of an arbitrary modular form f of weight s as in theorem (2).
Let X
N = 1.
N =W Y

Then we have
`
X √  1
yj + log(N ) ≤ log (B` (N, W )) + κ`
j=1
A

where A = 2(1−log( 34 )− log√ 7 ) = .68915..., and κ = 1. If all the yj , (j = 1, · · · , `)

7 q
are sufficiently large, then we may take κ = 0 and A arbitrarily close to π 23 .

To optimize the bounds in the previous theorems it is necessary to choose δ1 , ...δk

so that
` X
X k −1
n1 δ 1 + · · · + nk δ k ≈ δi wi,j .
j=1 i=1

If all the δi , (i = 1, ..., k) are equal to some fixed δ then we may take
 1
k
X −1 X k
` X −1 2
δ= ni · wi,j  .
i=1 j=1 i=1

In this manner we obtain the estimate

` k
X  12 X
` X
k −1  21
X √
yj ≤ ni · wi,j .
j=1 i=1 j=1 i=1

Pt
We now obtain from theorem (3) a bound for the length j=1 yj of the solution
Y for the linear diophantine equation N = W Y. We have
t t
X   
X √ √
yj ≤ yj · max yj .
1≤j≤t
j=1 j=1

Putting ` = 1 in theorem (3) we see that

 k 
√ 1 X 
−1
yj ≤ ni δi + (Λj ) .
2 i=1
6

Hence
t
X
yj ≤ B(N, W )
j=1

with
 k t  Xk 
1 X  X
−1

−1
B(N, W ) = ni δ i + (Λj ) · max ni δi + (Λj ) .
4 i=1 j=1
1≤j≤t
i=1

With the choice of δ given above, it follows that

k
X ` X
 X k −1  12 k
X − 21
(8) B(N, W ) = ni · wi,j · max wi,j .
1≤j≤t
i=1 j=1 i=1 i=1

Note that bounds of the above type may be useful in determining small solutions
to the diophantine problem (4).
 7
√
§2. Elementary proof that e −A
A A
e m
≤ p (m)

In this section, we give an elementary proof that for all integers m = 0, 1, 2, 3, ...
√
(9) p(m) ≥ e−A eA m

for A = 2(1 − log ( 43 ) − log

√ 7 ) = .68915... Since p(0) = 1 > e−A , we consider only
7
the case m ≥ 1.
Let us define pr (m) as the number of partitions of m into at most r parts. A
generating function for pr (m) is given by
∞
X h i−1
pr (m)xm = (1 − x)(1 − x2 ) · · · (1 − xr ) .
m=0

Then pr (m) satisfies the recurrence relation

(10) pr (m) = pr−1 (m) + pr−1 (m − r) + pr−1 (m − 2r) + · · ·

Following Hardy and Ramanujan [H-R], we use (10) to prove, by induction, that

rmr−1
(11) pr (m) ≥ .
(r!)2

Clearly (11) is true for r = 1. Assuming it is true for r ≥ 1, we have

r  r−1 r−1 r−1

pr+1 (m) ≥ m + (m − r + 1) + (m − 2r − 2) + · · ·
(r!)2
mr
≥
[(r + 1)(r!)] 2
(r + 1)mr
= 2 .
((r + 1)!)
√
This proves (11). But p(m) ≥ pr (m) for any r. Choosing r = [ m ], where [x]
denotes the smallest integer ≥ x, we obtain
√ √
[ m ]m m
(12) p(m) ≥ √
2 .
m [ m ]!

By Stirling’s asymptotic formula, (see Gradshteyn and Ryzhik [G-R]), we have

that
√  [√m ]+ 12  √  
√ 2π √ θ 
[ m ]! = [ m ]+1 · e−[ m ] · 1 +
e 12([m] + 1)

where |θ| ≤ 1 uniformly for

√ m = 1, 2, 3,√...
√
Now, for m ≥ B, and [ m ] + 1 ≤ m + 2 ≤ 1 + √2 m, it follows that for
B
m≥B>3
2  √ 2[√m ]+1
√
 √


2 2π 37 1
 2
[ m ]! ≤ 2 · m( m)+ 2 · e−2[ m ] · 1 + √ .
e 36 B
8

Combining this result with (12) yields

−1 √
e2 36
2

2 1

2 1−log (1+ √2 ) m
p(m) ≥ · 1+ √ · √ ·e B .
2π 37 B m
Since
1 7√
− log
√ m
≤ C 7
m
for all m ≥ 1, we have, upon choosing B = 36 that
√
p(m) ≥ C1 eC2 m
(m ≥ 36)
36 2 2
3 4
− log
√ 7 ). On the other hand, one easily



with C1 = 8π 37 e and C2 = 2 1 − log 3 7
checks that
√
(13) p(m) ≥ e−C2 eC2 m

for 1 ≤ m ≤ 36, and since e−C2 < C1 we obtain the inequality (13) for all integers
m ≥ 0.

§3. Proofs of theorems

The proofs of theorems (1),(2), and (3) are based on the following lemmas.

Lemma (1) Let τ = θ + iδ be in the upper half plane. Then the function
∞
X
φ(τ ) = p(n)e2πinτ
n=0

satisfies the estimate

p  12
 √
1 π −1
i 1




 (δ) 4
q + 1/q φ q+(1/q) e 12 [−δ+δ ]
, if 0 < δ < q+(1/q) ;
|φ(τ )| ≤

i 1


φ
q+(1/q) if δ ≥ q+(1/q) ,

where q ≥ 1 is arbitrary.

1
Proof: If δ ≥ q+(1/q) , then clearly
∞
X −2πn
|φ(τ )| ≤ p(n)e q+(1/q) .
n=0

1
On the other hand, if 0 < δ < q+(1/q) , and θ ∈ R, we can always choose integers
c, d with 1 ≤ c ≤ qδ so that
p

p
0 ≤ |cθ + d| ≤ δ/q.
 9

Since  
aτ + b δ
Im =
cτ + d (cθ + d)2 + (cδ)2
it follows that  
1 aτ + b
≤ Im ≤ δ −1 .
q + (1/q) cτ + d
With this choice of c, d we then obtain from (3) that

p  21
√  
1 i π −1
|φ(τ )| ≤ (δ) 4
q + 1/q φ e 12 [−δ+δ ]
.
q + (1/q)

Lemma (2) Let τ = θ + iδ be in the upper half plane. Let

∞
X
f (τ ) = a(n)e2πinτ
n=0

be a holomorphic modular form of weight s for SL(2, Z). Then we have

p −s  i 
 δ − 2s √q + 1/q
 
1
f q+(1/q) if 0 < δ < q+(1/q)
|f (τ )| ≤  
i 1
f q+(1/q) if <δ

q+(1/q)

where q > 1 is arbitrary.

Proof: The proof is the same as the proof of lemma (1) except that instead of
(3) we use the modular relation
 
aτ + b
f (τ ) = (cτ + d)−s f .
cτ + d

Proof of Theorems (1), (2):

Let τr = θr + iδr be in the upper half plane for 1 ≤ r ≤ k. We easily see from
(7) that
Z 1 Z 1 Pk
F e2πiτ1 , ..., e2πiτk e−2πi r=1 nr θr dθ1 · · · dθk


(14) S(N, W ) = D ···
0 0

where
D = e2π[n1 δ1 +···+nk δk ] .
But
t
Y k
X 
2πiτ1 2πiτk


F e , ..., e = φ τi wi,j .
j=1 i=1
10

It immediately follows from Lemma (1) that

(15)
t √ p  12
1 π −1
Λj 4 e 12 [−Λj +(Λj ) ]
Y
2πiτ1 2πiτk t


|F e , ..., e | ≤ C q + 1/q
j=1
1
Λj < q+(1/q)

where
k
X
Λj = δi wi,j
i=1

and  
i
C=φ .
q + (1/q)
The proof of Theorem (1) is completed after the bound (15) is substituted into
equation (14).
The proof of theorem (2) is exactly the same, except we use the generating
function
` t
2πiτ1 2πiτk

Y Y
F` e ,··· ,e = φ(Λj ) · f (Λj )
j=1 j=`+1

and the bounds given in lemmas (1) and (2).

Proof of Theorem (3):

If the linear diophantine problem N = W Y has a solution Y, then it follows from
the Cauchy-Schwartz inequality that
` `
√ √
X X q
yj = yj · Λj /Λj
j=1 j=1
`
 X  X`  12
−1
≤ yj Λ j · (Λj )
j=1 j=1
k `
1 X 1X −1
≤ ni δ i + (Λj ) .
2 i=1
2 j=1

since
`
X t
X k
X
yj Λj ≤ yj Λj = ni δ i .
j=1 j=1 i=1

If we have a solution y1 = m1 , . . . , yt = mt with

p(m1 ) · · · p(m` ) a(m`+1 ) · · · a(mt )

minimized subject to
a(m`+1 ) · · · a(mt ) ≥ 1,
then
N · p(m1 ) · · · p(m` ) ≤ S` (N, W ).
 11

It now follows from theorem (2) that

`
X
log (p(mj )) + log N ≤ log (B` (N, W )) .
j=1

The completion of the proof follows easily from the lower bound (9)
√
log (p(mj )) ≥ A mj − A,

and the asymptotic formula (3).

§4. Applications to equations in HNN groups

We apply the Hardy-Ramanujan partition theory developed above to the in-

vestigation of equations in HNN groups and relate the existence of solutions (and
associated bounds) in special cases to a linear diophantine problem of Frobenius.
The groups we have in mind are a subclass of the HNN groups investigated in
[An] in connection with Hilbert’s tenth problem and in [An-M] in connection with
fragments of Peano arithmetic.
By the class of linear vector groups (LVA) we understand the HNN groups G =
G(q1 , ..., qt ) given by the generators and relations

(16) < a1 , ..., at , b; a−1 q1 −1 qt

1 ba1 = b , . . . , at bat = b >

where the exponents q1 , ..., qt are distinct rational integers and each qi ≥ 2. Let
p1 , ..., pk denote the distinct prime divisors of the exponents qi so that each qi
factors as

(17) qi = p1 wi,1 · · · pk wi,k , (i = 1, ..., t)

with nonnegative integer exponents wi,1 , ..., wi,k . In addition, call a positive integer
n admissible for G if its positive prime divisors are among p1 , ..., pk .
A positive conjugate power equation for G = G(q1 , ..., qt ) is given by

(18) bn = x−1 bx

where n is a positive integer termed the parameter and x is a positive word (i.e.
one containing no negative exponents in the generating symbols a1 , ..., at , b).
It is a consequence of [An] or [An-M] that (18) has a solution provided n is
admissible for G and (4) takes the form N = (n1 , . . . , nk ), n = pn1 1 · · · pnk k , where W
consists of the wi,j given in (17) and each yj in Y = (y1 , · · · , yt ) denotes the number
of occurrences of ai in the word x. Also, if x is a solution to (18), then insertion or
deletion of a b symbol anywhere in the word x results in another solution to (18).
A solution x to (18) is called standard provided it is monotone nondecreasing
in the generating symbols a1 , . . . , at and in the syllable sequence corresponding to
each ai . Thus x contains no subword of the form ai uaj where i > j, nor a sub-
word containing succesive ai -syllables ari , asi , r > s ≥ 1, (e.g. a31 ba21 ). In addition,
12

we call two standard solutions equivalent provided their ai -syllable sequences are
the same (e.g. ba21 b2 a21 a52 ba62 and a21 b2 a21 ba52 b3 a62 b each give rise to the syllable se-
quence a21 , a21 , a52 , a62 ). We call the equivalence classes of standard solutions (18) the
standard solution types of that equation.
The number of standard solution types of G to (18) is precisely given by S(N, W ).
To see this note that each standard solution type is determined by its ai -syllable
sequence. These syllable sequences are in turn in one-to-one correspondence with
the partitions defined by the linear diophantine system (4) associated with the
parameter n and the presentation (16) of G.
From theorem (1), equation (8), and the remarks above, we obtain.

Corollary (1) Let G = G(q1 , . . . , qt ) be a linear vector group. Then it is decidable

whether or not a positive power equation (18) has a solution x in G. If one such so-
lution exists, then there exists a solution x involving only the generators a1 , . . . , at .
The word length of x denoted |x| satisfies the bound

|x| ≤ B(N, W ),

with B(N, W ) given by (8) and the number of standard solution types is precisely
S(N, W ). Moreover, N, W, B(N, W ), and S(N, W ) together with its bound given
in theorem (1) are effectively computable from the parameter n of (18) and the
exponents of G given in (16).

Let w1 , w2 , ..., wt be positive relatively prime integers satisfying wi ≥ 2. The

classical linear diophantine problem of Frobenius [Sch] is to find the largest positive
integer g(w1 , w2 , ..., wt ) which is not a linear combination of nonnegative integral
multiples of the wi , i = 1, 2, ...t. The Frobenius problem occurs cryptomorphically
in solving (18) for a certain class of linear vector groups.
By a linear vector group G = G(q1 , ..., qt ) of the Frobenius problem, we mean
one such that qi = pwi , p a fixed positive prime and wi , i = 1, .., t are distinct
positive relatively prime integers 1 < w1 < · · · < wt .

Corollary (2) If G = G(pw1 , ..., pwt ) is a linear vector group of the Frobenius
problem and n ≥ g(w1 , ..., wt )+1, then the positive power equation admits a solution
x and |x| ≤ B(N, W ) with B(N, W ) given by (8).

BIBLIOGRAPHY

[An] M.Anshel, Vector groups and the equality problem for vector addition systems,
Math. Comp. 32, (1978), 614-616.

[An-M] M. Anshel and K. McAloon, Reducibilities among decision problems for

HNN groups, vector addition systems and subsystems of Peano arithmetic, Proc.
Amer. Math. Soc. vol. 89, Number 3 (1983), 425-429.
 13

[Eu] L.Euler, Introductio in Analysin Infinistorum, vol.1, M.-M Bousquet, Lau-

sanne 1748 [German translation by H. Maser: Einleitung in die Analysis des Un-
endlichen Erster Teil. Springer, Berlin, (1885) [reprinted; 1983] ].

[G-R] I.S. Gradsteyn and I.M. Ryzhik, Tables of Integrals Series and Products,
Academic Press (1965), 937.

[Gu] R.C. Gunning, Lectures on modular forms, Annals of Math. Studies Number
48, Princeton Univ. Press, (1962).

[H-R] G.H. Hardy and S. Ramanujan, Asymptotic formulae in combinatorial anal-

ysis, Proc. London Math. Soc. (2) 17, (1918), 75-115.

[Sch] A. Schrijver, Theory of Linear and Integer Programming, John Wiley and
Sons (1986), 375-376.

Michael Anshel
Department of Computer Sciences
The City College of the City University of New York
New York, New York 10031

Dorian Goldfeld
Department of Mathematics
Columbia University
New York, New York 10027