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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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