ILLINOIS JOURNAL OF MATHEMATICS
Volume 39, Number 4, Winter 1995

ON THE PARITY OF PARTITION FUNCTIONS
J.L. NICOLAS AND A. S,RK/ZY
Section 1

For n 1, 2,..., p(n) denotes the number of unrestricted partitions of n,and q(n) the number of partitions of n into distinct parts, and we write
0. If N,b arep(0)=q(0)= 1, p( -1) q( -1) p( 2) q( 2)positive integers, a is an integer, then let Ea, b(N) denote the number of
non-negative integers n such that n < N and p(n) a mod b.
Starting out from a question of Ramanujan, in 1920 MacMahon [3] gave analgorithm for determining the parity of p(n). Since then, many papers havebeen written on the parity of p(n). In particular, in 1959 Kolberg proved thatp(n) assumes both even and odd values infinitely often (for n > 0). His proof
was based on Euler’s identity+ E

0k>l1/2k(3k 1), tk 7 k(3k + 1) and the summation extends over all
terms with a non-negative argument. It follows from this identity that

where s kp(n) +_,(p(ns) +p(nt))

Omod2.

(1)k>lOther proofs have been given for Kolberg’s theorem by Newman [5] andFabrykowski and Subbarao [1]. Parkin and Shanks [7] have computed theparity of p(n)up to n 2039999. Their calculation suggest that E0,z(N)EI, z(N) N/2. Mirsky [4] has proved the only quantitative result on thefrequency of the odd values and even values of p(n). In fact, starting out

Received June 25, 1993.
1991 Mathematics Subject Classification. Primary 11P83.
1Research partially supported by the Hungarian Foundation for Scientific Research, Grant
No. 1901, by CNRS, GDR Math6matiques Informatique, and by MEN, EA 619.
(C) 1995 by the Board of Trusteesof the University of Illinois
Manufactured in the United States of America

586

ON THE PARITY OF PARTITION FUNCTIONS

587

form (1), he proved that for N > No we havemin(Eo, e(N),E,e(N)) >log log N
2 log 2(2)Note that he claims the following result: for each b there exist at least two
distinct values of a (with 0 < a < b) such that, whenever N is sufficiently
large,log log N

Ea’b(N) > blog2(3)However, his proof seems to give only the following slightly weaker result:for each b and N > No(b) there exist at least two distinct values al a(N),a 2 a2(N) depending on N (with 0 < aa < a 2 < b) such that
log log N
b log 2min(E,,,b(N),Ea,b(N)) >This implies that there exist at least two distinct values of a (with0 < a < b) such that (3) holds for infinitely many N, and it gives also (2).
In this paper, first we will improve on (2) by showing that there is aconstant c > 0 such thatmin(Eo, z( N), El,z( N) ) >> (log N) c.
Moreover, we will point out that the parity of the values of q(n) can be
determined easily. Motivated by this fact, we will show that the parities ofp(n) and q(n) are different for infinitely many n. Finally, we will discuss
several related unsolved problems.
We are pleased to thank P. Bateman who introduced us in the subject, andM. Del6glise for kindly computing the parity of p(f(n)) displayed at the endof this paper.
Section 2

We write10ifp(n) p(nifp(n) =-p(nand_,NG(N)=n=lg(n).

1) mod21) mod2

J.L. NICOLAS AND A. S/RKZY588

We will prove:
THEOREM 1. Let r be an integer > 2. For M > 2r 2, we have

G(M) > 3 log(2r (log M) Cr(4)2)

wherec3log 212r)/log 2

COROLLARY 1. For any c < log(3/2)/log2.

0.585..., we havemin(Eo, e(N),E,(N)) >_ -G(N) >> (log N)(5)

The proof of (4) will be based on Euler’s identity (1)Proof of the theorem.

(although a lower bound of type (4) could be derived from (27) below aswell). First we will prove that for every positive integer M we have
3r- 1a(2riM 2) > 2------- G(M).

(6)

Replacing n by n- 1 in (1) and subtracting the congruence obtained inthis way from (1), we getg(n) +,(g(nsk) + g(ntk)) =- Omod2

(7)

k>l

where the summation extends over all terms with a non-negative argument(note that g(0) p(0) p(- 1) p(0) 1).
Let U denote the set of the integers u with 1 < u < M, g(u) 1 so thatUI G(M). Let us consider the congruence (7)with tj + u in place of n for
all u Uandj=M+ 1, M+2,...,rM:g(t + u) + E (g(tj + u s) + g(t + u -t,)) =- 0 mod2

(8)

k>_lwhereu

U,j=M+ 1,...,rM.

We have
tj + U

1/2j(3j + 1) + u g(j + 1)(3j + 2)
tj+ < tj -Jr- U Sj+-2j- 1 +u < -2M- I+M= -M- 1<0(9)589

ON THE PARITY OF PARTITION FUNCTIONS

andt+u s>t+u tu > O.

Thus the greatest s, resp. t, appearing in the sum in (8) is sy, resp. t., sothat (8)can be rewritten in the form_, (g(tjJg(t+s,) + g(tj + u -t,))+u

0 mod2.

k=l

The term g(tj + u -tj)= g(u)= 1 (since u U) appears on the left
hand side. Thus there is another term equal to 1 on the left hand side, inother words, there is a v v(j, u) such thatg(v)1,(10)and v can be represented in one of the forms

v=#+u-s (withl <k<j)

(11)
(12)

v=tj+u-tk (withl <k<j- 1).

(13)

otj -k- U,

andThe smallest of the numbers on the right hand sides of (11), (12) and (13) isand the largest is t. + u so thatt. + us.

v > tj + u

si =j + u > j > M

(14)

and

v<tj+U<trM+M=-r_ 2M2 + 1/2rM + M < m 2 ( 7r3 2 + $rl + 1)< 2r2M 2(15)
Let V denote the set of the distinct integers u that can be obtained asv

v(j,u)(16)

for some u, j satisfying (9), and let h(v) denote the number of the solutionsof (16) in j and u. The number of pairs (j, u) satisfying (9) is Ul(r 1)MJ.L. NICOLAS AND A. S/RKOZY

590(r1)MG(M) so that clearly,1)MG(M)
IvI > (r-maxoh(v)(17)

To obtain an upper bound for h(v), we will first show that the numbers
tj + u (with j, u satisfying (9)) are distinct. In fact, assume thattj + u =tj, + u’
whenceutj,- tju’.

(18)

3j + 2 > M.

(19)

If j’ > j, thentj.,- tj > t.+ltj

Moreover, we havelu(20)u’l <M.

j’, u u’.
Thus for fixed v, (11) has at most one solution in j and u. Moreover, if (12)holds for some v, j, u and k, then we have 1 < k < j < rM so that k can bechosen in at most rM ways. If v and k in (12) are fixed, then, by theargument above, v + s tj + u has at most one solution in j and u, so thatfor fixed v the total number of solutions of (12) is at most rM. A similarargument gives that (13) has at most rM- 1 solutions. Summarizing, we
obtain that(18), (19) and (20) imply jh(v) N 1 + rM + (rM- 1) =2rM.
Thus it follows form (17) that

Ivl > (r- 1)MG(M)
2rM

r-2r

1G(M)

(21)

By (10), (14), (15) and (21) we have(G(2r2M 2) G(M)) + G(M)G(2r2M 2)> IV[ +G(M) >3r- 1
2r G(M)(22)

which completes the proof of (6).
Let us write M (2r2) 2k-1 for k 1,2,... so that M 2r 2 and M+
2r 2 M{2 for k 1, 2,Clearly we have g(2) g(3)= 1 so that,
8G(M1) > G(8)n=lg(n) > g(2) + g(3)2 > (3r- 1)/2r.

591

ON THE PARITY OF PARTITION FUNCTIONS

Thus it follows form (6) by straightforward induction that

G(M) >(3r- 1)

for k

2r

(23)

1,2,

To complete the proof of the theorem, assume that M > 8 and define k by

2rZM,

M, < M < M,+
Then we have

loglog(2r2) 2k+1- < log log(2r2) 2k+1(k + 1)1og2 + loglog(2r2).

loglog M < loglog Mk+

Thus it follows from (23) that

G(M)>_G(M)>(3r-12r) >(3r-1(log log M-log 2-log log(2r2))/log 2--Cr2(logM)Cr3 log(2 r 2 )2r(which completes the proof of Theorem 1.

Proof of the corollary. Clearly, g(n)= 1 if and only if one of p(n) andp(n- 1) is odd and the other one is even, and this is so if and only if

Ei,2(n) Ei,2(n2)1 for both

0 and 1. Thus for both

0 and 1 wehaveN
n=l[(N+ 1)/2]

[N/2]

g(n)

g(Zm) +.,

m=lg(Zm- 1)
m=l[N/2](Ei,2(Zm)

Ei,2(Zm2))

m=l[(N+ 1)/2](Ei,2(2m1)

Ei,2(2m3))

m=l(Ei,z(2[N/2]) Ei,2(0))+(Ei,z(2[(N + 1)/2] 1) Ei,2(-1))< 2Ei,z(N).

(24)

J.L. NICOLAS AND A. SRKZY592(5) follows from (4) (with r chosen large enough to ensure Cr > c) and (24),and this completes the proof of the corollary.
Section 3

Let q(n) denote the number of partitions of n into unequal parts, and let
E(n), resp. U(n), be the number of partitions of n into an even, resp. odd,.

number of unequal parts. It follows from an identity of Euler (see Theorem358 in [2]) that E(n)= U(n) except when n is a pentagonal number, i.e.,n s 1/2k(3k- 1) or n tk 1/2k(3k + 1); in these latter cases we haveE(n) U(n) (- 1) Sinceq(n)E(n) + U(n)E(n)U(n) mod2,

thus q(n) is odd if and only if n is a pentagonal number. In view of this fact,
one might like to see that the parities of p(n) and q(n) are independent. We
will prove the following result in this direction:

THEOREM 2. Bothp(n)q(n) mod2, n < Nandp(n)q(n) + 1 mod2, n < Nhave more than (log N) solutions for N large enough, where c is a fixed positiveconstant.

Proof We start out from the well-known recursion formula (cf. [6], p. 44).
n-1

np(n)

(25)

p(i)tr(n -i)i=0

where r(n) denotes the sum of the positive divisors of the positive integer n.
+pr
If p is a prime and r is a positive integer, then o(p r) 1 + p + p2 +is odd if and only if either p 2 or p 4:2 and r is even. By the multiplicativity of r(n), it follows that r(n) is odd if and only if n is of the form eithern k 2 or n 2k 2. Thus we obtain from (25) that[x/h--]

np(n)[,,/h--/2]

p(nk=lk 2) +p(nk=l2k 2) mod 2.

(26)

593

ON THE PARITY OF PARTITION FUNCTIONS

Next, we shall prove a similar formula for q(n), namely,[yen-1nq(n)[/h--/21] q(nk 2) 4-q(nk=l2k 2) mod2.

(27)

k=lDifferentiating the function

_.

F(x)

I-I(aq(n)x(28)

i=1

n=O

we getE nq( H)Xn-----O/xi_F(x) ] i 7 i"

n-1

i=1

Multiplying by x, we have.,nq(n)x =- F( x)
n=O

i=1/x

1- x(29)

mod 2.

NOW,

Eixki:

i=1 k=lX
m=l_,o’(m)x m,

m=land (28) and (29)yield

_.

n-1

nq(n) =-q(i)tr(n -i) mod2.

(30)

i=0

Finally (27) follows from (30) in the same way as (26) from (25). Now, write
F(n) p(n) q(n). From (26) and (30), we getnF(n) =-F(nk 2) 4-kZ<n] F(n2k 2) mod2.

2kZ<nLet h(n)= 0 for n _< 1 andh(n)h(n)

0 if F(n)1 if F(n)F(nF(n2) mod22) mod2(31)J.L. NICOLAS AND A. S/RKZY

594

forn >2, andE h(n).

H(N)

<n <N

We shall prove

H(N) >> (log N) c,(32)and then the proof of Theorem 2 can be completed similarly to the proof ofthe corollary of Theorem 1. Indeed, let us define

T/(N) =card{1 <n <N,n--Nmod2, F(n) --imod2)
and T/(N) 0 for N < 0. Then we have h(n) 1 if and only if one of F(n)and F(n- 2) is odd, and the other even, and this is so if and only if
0 and
1. Thus for both
0 and 1,
T/(n) T/(n 4) 1 for both
we haveNH(N)Eh(n) < E (T/(n)l<n<Nn=lT/(n-4))

T/(N) + T/(N- 1) + T/(N- 2) + T/(N- 3)< 2(T/(N) + T/(N 1))
2card{n < N; F(n) =-i mod2}
which, assuming (32), completes the proof of Theorem 2.
Since the proof of (32) is similar to the proof of Theorem 1, we shall leavesome details to the reader. Replacing n by n 2 in (31), and then subtracting we obtain/,1,h(/7)

E h(/’1,k 2) q-

k2<nE h(F/,2k 2) mod 2.

(33)

2k2<n

Let M be a positive integer and let
U= {u,l<u NM, h(u)J-- j, rM <j <sM,

12rv1),< {jg-} < 1where {x} denotes the fractional part of x, and r and s are two integers to be595

ON THE PARITY OF PARTITION FUNCTIONSfixed, but such that 2 _< r < s. Substituting nj J, we obtaineuh(2j 2+u) +2u + j2 in (33)where u

U,E h(2j 2+u-k 2) + Eh(2j +u-2k 2) =0 mod2
2k=lk=l(34)where eu u mod2. Here the term h(2j 2 + u- 2j 2)
thus there is another term equal to 1 so that there is ato(35)to(j, u)tosuch that h(to)h(u)= 1 appears,

1, to =/= u, and to can be represented in the form

2 {with 1 < k < [jlQI)
2k (with 1 < k < j 1).

2j 2 + u,2j 2 + u
2j2+u2or(36)It follows form (36) thatM < to < (2s 2 + I)M 2.
If V denotes the number of distinct integers to that can be obtained inform (35) for some j J, u U, and for a fixed to V, l(to) denotes thenumber of solutions of (35) in j, u, then a simple computation shows that if r,s and e > 0 are fixed, then for M > Mo(r, s, e) we haveH((2s2 + 1)m)- H(M) >_ IVI>

IJIH(M)1(v)max(1 1/(2rye) e)(s
(1 + v)sr)

H(M). (37)The proof can be completed in the same way as the proof of Theorem 1.
Observe that choosing r large and, say, s r 2, the constant factor on theright of (37) is close to 1/(1 + -), which yields c in Theorem 2 as close to1/2 as we wish.
Section 4

The problems discussed so far can be generalized by studying the parity ofgeneralized additive representation functions. Indeed, for A c N let r(A, n)J.L. NICOLAS AND A. S/RK)ZY596

and p(A, n) denote the number of solutions ofa +a’ =n,a A,a’ A,a <a’,andail + ai2 ++ain, ail,aiA, ail << airespectively.
Answering a question of the authors, V. Flynn (in a letter written to one ofthe authors) and I.Z. Ruzsa (oral communication) showed that there areinfinitely many (but only countably many) infinite sets A c N such thatr(A, n) is either odd or it is even from a certain point on, and the same istrue with p(A, n) in place of r(A, n). One might like to study density andother properties of the sets A with these properties; we will return to these
problems in a subsequent paper.
In both recursion formulas (1) and (26), sums of the form Ep(f(k))
appear where f(k) is a quadratic polynomial. This suggests that, perhaps,
there is a quadratic polynomial f(k) such that p(f(k)) is more often odd,
than even, or vice versa. Thus we have computed the parity of p(f(k)) up tok < 16,000,000 for each of the polynomials f(k) k 2 + a, a 0, 1, 2,..., 9and, in view of Theorem 2, f(k)= 1/2k(3k + 1)+ a, a 0, 1,2,..., 9 (cf.
Table 1).
Table

For -9 < a < 9, this table shows the number of n’s satisfying 0 < n < 16,000,000 which are ofthe form n k + a, or n k(3k 1)/2 + a or n k(3k + 1)/2 + a and such that p(n) is
odd or even.

p(n)ak(3k- 1) +ak +an-9-8-7-6-5-4-3-2
02
3
4
5
6
7
8
92k(3k + 1) +a2

even

odd

even

odd

even

odd

2044
2012
2053
2049
1984
2000
1986
2023
2027
2006
2003
2002
1943
2014
1977
1992
1991
1935
2039

1954
1986
19451949
2014
1999
2013
1976
1973
1994
1997
1998
2057
1986
2023
2008
2009
2065
1961

1681
1579
1614
1646
1630
1585
1604
1624
1627
1592
1547
1583
1663
1628
1700
1598
1633
1635
1614

1583
1685
1650
1618
1635
1680
1661
1641
1639
1675
1720
1684
1604
1639
1567
1669
1634
1632
1653

1658
1602
1644
1612
1615
1578
1636
1640
1614
1661
1574
1677
1593
1623
1615
1680
1590
1606
1621

1605
1661
1620
1652
1649
1686
1628
1625
1651
1605
1692
1589
1673
1643
1651
1586
1676
1660
1645

ON THE PARITY OF PARTITION FUNCTIONS

597

It turned out that in each of these cases, the odd values and the evenvalues occur with about the same frequency. This fact, together with several
results [1], [7] of the type that p(f(k)) assumes both odd and even values
infinitely often for certain special linear polynomials f(k), suggests thefollowing conjecture: If f(k) is a polynomial whose coefficients are integers,then p(f(k)) assumes both odd and even values infinitely often, and, indeed,
we havelimN+

I{n’n <N,p(f(n)) 0mod2}lN-1

Table 1 was calculated by Marc Del6glise on an HP 730. In a first step hecalculated p(n) mod 2 up to n 16- 106 by Euler’s identity (1), and next heextracted the values of p(f(k)) from the memory.
REFERENCES
1. J. FABRYKOWSKI and M.V. SUBBARAO, "Some new identities involving the partition functionp(n)" in Number theory, Proceedings of the First Conference of the Canadian
Number Theory Association (Banff, Alberta, April 17-27, 1988), ed. R.A. Mollin,
Walter de Gruyter, New York, 1990, pp. 125-138.
2. G.H. HARDY and E.M. WRIGHT, An introduction to the theory of numbers, 4th ed., Oxford,
Clarendon Press, 1960.
3. O. KOLBERG, Note on the parity of the partition function, Math. Scand. 7 (1959), 377-378.
4. P.A. MACMAHON, Note on the parity of the number which enumerates the partitions of a number,
Proc. Cambridge Philos. Soc. 20 (1920-21), 281-283.
5. L. MIRSKY, The distribution of values of the partition function in residue classes, J. Math.
Anal. Appl. 93 (1983), 593-598.
6. M. NEWMAN, Periodicity modulo m and divisibility properties of the partition function, Trans.
Amer. Math. Soc. 97 (1960), 225-236.
7. H.H. OSTMAYN, Additive zahlentheorie, vol. 1, Springer-Verlag, New York, 1956.
8. T.R. PARIAN and D.SHAYKS, On the distribution ofparity in the partition function, Math. Comp.
21 (1967), 466-480.
9. M.V. SUBBARAO, Some remarks on the partition function, Amer. Math. Monthly 73 (1966),851-854.

UN1VERSITfE CLAUDE BERNARD (LYON I)
VILLEURBANNE, FRANCE
MATHEMATICAL INSTITUTE OF THE HUNGARIAN ACADEMY OF SCIENCESBUDAPEST, HUNGARY