# What does the computer suggest about the parity of p(n), for n in a fixed arithmetic progression?

Let p(n) be the number of partitions of n. A famous theorem of Euler allows one to compute the parity of p(n) quickly for quite large n. In:

On the distribution of parity in the partition function, Math. Comp. 21 (1967) 466-480

Parkin and Shanks, on the basis of such computations, conjecture that for each rho> 1/2, the number of n that are smaller than x and have p(n) even is (x/2)+ O(x^rho).

Nothing remotely like this has been proved. But I wonder:

Does the computer suggest that the analogous result holds when we restrict n to lie in a fixed arithmetic progression? Or does it suggest that there are there arithmetic progressions in which the n with p(n) even predominate? (And are there MO viewers interested in making such calculations, if they haven't yet been done?)

-

The answer to your very last question is yes. As for the rest:

Computing the parity up to N is, in theory, quasi linear by using Pentagonal Number Theorem: compute the inverse of the pentagonal number power series mod $x^N$. This is of course faster than the quadratic-complexity "en masse" method of using simply the recurrence relation. I am not sure how inverse_mod is actually computed in sage, but it ran fine for the following code:

def get_parity(n):
x = GF(2)['x'].0
f = 1
for k in xrange(1,sqrt(2*n/3)+10):
f += x^((k*(3*k-1))/2) + x^((-k*(-3*k-1))/2)
return f.inverse_mod(x^n).coeffs()

def get_best(l):
n = len(l)
highest, lowest = [0,0,0], [0,0,1]
for a in [1..sqrt(n)]:
for b in [0..a-1]:
score = (l[b::a].count(1) + 0.0)*a/(n-b)
if score > highest[2]:
highest = [a, b, score]
elif score < lowest[2]:
lowest = [a, b, score]
return highest, lowest

l = get_parity(2^22)
best = get_best(l[:2^21])
for x in best:
print x[2], (l[x[1]::x[0]].count(1)+0.0)*x[0]/(len(l)-x[1])


What this does is calculate for every a.p. $an+b$ the density of odd values, and finds the two a.p.'s with most and least odd values.

get_parity took more than 20 minutes (not sure exactly since I was watching TV), and get_best took almost an hour (again, I think). I'm running a macbook pro with 4gb ram.

The results were:

(1442, 766) 0.557846694263366 0.531611381990907
(1389, 357) 0.440522320970815 0.468967411597574


This is to say that the most special a.p.'s up to $2^{21}$ become a bit less special when going up to $2^{22}$, and quite close to equidistribution. Hence, I would say that yes, the computer does suggest that the analogous result holds when we restrict n to lie in a fixed arithmetic progression.

Edit 1: If we change the "score" of an a.p. to: $$\frac{\\\#\{odd\\ in\\ a.p.\} - \\\#\{even\\ in\\ a.p.\}}{\sqrt{length}}$$ Then up to $2^{21}$ the largest values are:

(712, 254) 4.84633129231862
(1389, 357) -4.60795692951670

-
Dror: Thanks for the calculations. They seem consistent with the hypothesis that for each a.p. and for each eps. your "score" is O(length^eps.). But they're consistent with lots of other plausible hypotheses as well, and what's convincing is subjective. (Parker and Shanks conjecture that the number whose n'th binary digit is the parity of p(n) is normal. Maybe, but they really have no evidence except for progressions with small modulus). Calkin et. al. make calculations up to 10^9; I'll try to contact them. And I'll e-mail you if something more turns up. –  paul Monsky Sep 1 '10 at 12:00

Hi Paul, You might look out for this:

Kaavya N. Jayram

"Crank 0 Partitions and the Parity of the Partition Function" has been accepted to the International Journal of Number Theory.

The formal properties of integer partitions have been investigated for over 200 years by some of the brightest minds in mathematics such as Euler, Hardy, and Ramanujan, with surprising applications to modern physics and computer science. The partition function p(n) denotes the number of ways in whic an integer n can be written as an (unordered) sum of other integers. Motivated by Ramanujan's investigations into the modular properties of p(n), this project aims to make progress on the parity problem of p(n) by means of deriving generating functions for cranks and ranks.

Berkovich and Garvan (2002) showed that there is always a bijection between the crank k and crank -k partitions of n for every k>0. Consequently, the parity problem for p(n) reduces to studying crank 0 partitions. I obtained the following results: (1) I derived a generating function for crank 0 partitions of n, which is similar to a generating function p(n). I also obtained a general form for the crank k generating function. (2) I described an involution on crank 0 partitions of n, whose fixed points are called invariant partition then derived a generating function for crank 0 invariant partitions. (3) Finally, I derived a generating function for rank 0 self-conjugate partitions.

The proof techniques are based on identifying and manipulating the key combinatorial objects underlying cranks and ranks, and avoid the analytic techniques inherent in previous methods.

-
Hi. Will, I'm not looking for a proof of anything, as the best minds of our generation haven't gotten anywhere with understanding the parity of p(n). But I really wonder what to expect. I remember Keith Conrad talking about the parity of p(n) years ago--I wonder if he made any calculations for n in arithmetic progressions. Paul –  paul Monsky Aug 26 '10 at 21:23
Paul, I must have been talking about something else. I've never computed parities of p(n). –  KConrad Aug 27 '10 at 4:59
Keith, I had thought that the first time I met you was at a talk you gave on congruence properties of p(n). It must have been someone else--the false memory is strong, but I suppose that's the nature of false memories. –  paul Monsky Aug 27 '10 at 6:39

There have been several papers on the parity of the partition function in arithmetic progressions. I don't know whether any of them cite computational evidence one way or the other, but it might be worth having a look (or just writing to Ken Ono). Cutting and pasting from Math Reviews,

MR1844553 (2002f:11139) Boylan, Matthew(1-WI); Ono, Ken(1-WI) Parity of the partition function in arithmetic progressions. II. (English summary) Bull. London Math. Soc. 33 (2001), no. 5, 558--564.

MR1945975 (2003j:11128) Subbarao, M. V.(3-AB) Partitions---some parity problems and results. Proceedings of the Second International Conference of the Society for Special Functions and their Applications (SSFA) (Lucknow, 2001), 59--65, Soc. Spec. Funct. Appl., Chennai, 200?.

MR1816213 (2002i:11102) Ahlgren, Scott(1-PAS) Distribution of parity of the partition function in arithmetic progressions. (English summary) Indag. Math. (N.S.) 10 (1999), no. 2, 173--181.

MR1384904 (97e:11131) Ono, Ken(1-IASP) Parity of the partition function in arithmetic progressions. J. Reine Angew. Math. 472 (1996), 1--15.

EDIT: I have found a paper which seems to present numerical results on $p(n)$ for $n$ outside of certain arithmetic progressions. Neil Calkin et al., Computing the integer partition function, Math Comp 76 (2007) 1619-1638, freely available on the web at http://www.ams.org/journals/mcom/2007-76-259/S0025-5718-07-01966-7/S0025-5718-07-01966-7.pdf

-
Gerry, I've looked at the papers that reference Parkin and Shanks, among them the ones you mention. I find no attempts to guess what's happening from computational evidence--the authors are all intent on proofs, and what can be proven, though it requires great ingenuity, is of necessity incredibly weak. With computers far more powerful now, I hope someone has made or will make calculations like those of Parkin and Shanks for n in the congruence classes mod 3, mod 5, etc. –  paul Monsky Aug 27 '10 at 2:08
Though the Calkin reference isn't exactly what I'm looking for, it's very interesting. Thanks. –  paul Monsky Aug 27 '10 at 7:01
I know that Scott Ahlgren computed the parity out to $10^7$, but I don't know how much analysis he performed or if he still has the data. In any case, it isn't that much data anymore. Also, Euler's formula seems like a big help, but it really isn't that big a help, as it is very memory intensive. Parkin & Shanks have an identity, iirc, that allowed them to compute out to 8N while only storing data out to N. –  Kevin O'Bryant Aug 27 '10 at 8:57