# Is “OEIS A001935 Number of partitions with no even part repeated” efficiently computable $\mod 4$?

Is A001935 Number of partitions with no even part repeated efficiently computable $\mod 4$?

I am interested because of this relation with sum of divisors of $8n+1$.

$\sigma(8n+1) \equiv A001935(n) \pmod 4$

Gjergji Zaimi's proof of the above

Do S. Ahlgren & K. Ono congruences for the partition function shed some light?

The generating function is $\prod_{k \geq 1}\frac{1-x^{4k}}{1-x^k}$

Let $a(n)=A001935(n) \mod 4$.

Up to $10^7$ these hold: $$a(9n+4)=0$$ $$a(9n+7)=0$$

Update

Related sequence is A001936 Expansion of q^(-1/4) (eta(q^4) / eta(q))^2 in powers of q

Gjiergji proved:

$$\sigma(4n+1) \equiv A001936(n) \pmod 4$$

A001936 mod 4 is zero for n = 9m+5 or 9m+8 up to $10^7$.

Let $a(n)=A001936(n) \mod 4$. Up to $10^7$:

$$a(n)=a(9n+2)$$

EDITED version by David Speyer:

The question is:

Given an integer $m$ which is $1 \mod 8$, is there an algorithm which computes $\sigma(m) \mod 4$ in time polynomial in $\log m$?

Reason we might think no: If there were such an algorithm, there would be an efficient algorithm for the following question: Given an integer $m$ which is $1 \mod 8$, and a promise that $m$ is either of the form $pq$ or $p^2 q$ with $p$ and $q$ prime, determine which once holds. The method is simply to note that $\sigma(pq) \equiv 0 \mod 4$ and $\sigma(p q^2) \equiv 2 \mod 4$.

I have a heuristic that there are only two easy problems in prime factorization: Determining whether a number is prime (by AKS) and determining whether a number is a perfect power. So I expect that this problem is not easy and, thus, $\sigma(m) \mod 4$ is hard to compute. But I (David) am not an expert on factorization, so this argument should not be taken very seriously.

Reasons we might think yes: As explained in a
previous answer of Gjergji Zaimi, $\sigma(8n+1)$ is given by an infinite product similar to that for the partition function and $\sigma(8n+1) \mod 4$ can be described as the number of partitions of a certain sort.

Recent work of Folsom, Kent and Ono provides a very general method for writing $\ell$-adically convergent power series for the coefficients of modular forms resembling the partition generating function. (The original version of this question links to earlier work of Ahlgren and Ono but I might as well link to the most powerful result.)

If those results apply in this case, with $\ell=2$, we could presumably look at the lowest two bits of the sum. If this sum converges at all rapidly, this should be an efficient algorithm. Note that the complexity of finding this $2$-adic expansion is irrelevant because that is a one time cost; the only question is, once the expression is found, how fast does it converge and how hard are the individual terms to compute?

As I (David) haven't read Ono's work, this argument also shouldn't be taken very seriously. But the conflict of these two arguments against each other makes it seem like an interesting question.

-
@joro: You have already received one vote to close. I think that your question should be rephrased a little bit. For example, it is unclear why there is a line that just says "proof in this question": is it a just a reference for the curious reader? Is it necessary in order to understand the formulation of the question? Also, what kind of answer do you expect to the question "Do Ahlgren & Ono [...] shed some light?" Please reword the question, add some motivation, make complete sentences, etc. –  André Henriques Mar 22 '11 at 19:15
I think this is an interesting question, and took the liberty of making an edited version that explains why. –  David Speyer Mar 23 '11 at 14:12
@David: Why don't make this an answer? –  joro Mar 23 '11 at 14:24
Because I am not an expert on factorization, so my intuitions about what should be hard aren't worth much, and I haven't read Ono's work, so my guesses about what sort of formulas should follow from it aren't worth much. I'm hoping that experts of one or the other sort will start posting answers soon. –  David Speyer Mar 23 '11 at 14:27
the reason why $9n+4$ and $9n+7$ give zero is because both $72n+33$ and $72n+57$ are divisible by $3$ but not $9$. In general, if $n$ is not a sum of two squares then $\sigma(n)$ is divisible by $4$. –  Gjergji Zaimi Mar 23 '11 at 15:47