Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Up to $10^6$:

$\sigma(8n+1) \mod 4 = OEIS A001935(n) \mod 4$

A001935 Number of partitions with no even part repeated

Is this true in general?

It would mean relation between restricted partitions of $n$ and divisors of $8n+1$.

Another one up to $10^6$ is:

$\sigma(4n+1) \mod 4 = A001936(n) \mod 4$

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

$\sigma(n)$ is sum of divisors of $n$.

sigma(8n+1) mod 4 starts: 1, 1, 2, 3, 0, 2, 1, 0, 0, 2, 1, 2, 2, 0, 2, 1, 0, 2, 0, 2, 0, 3, 0, 0, 2, 0, 0, 0, 3, 2

sigma(4n+1) mod 4 starts: 1, 2, 1, 2, 2, 0, 3, 2, 0, 2, 2, 2, 1, 2, 0, 2, 0, 0, 2, 0, 1, 0, 2, 0, 2, 2


Up to 10^7

A001935 mod 4 is zero for n = 9m+4 or 9m+7

A001936 mod 4 is zero for n = 9m+5 or 9m+8

Question about computability

share|improve this question

1 Answer 1

up vote 17 down vote accepted

Let's call A001936(n) by $a(n)$. Here is a sketch of why $$a(n)\equiv \sigma(4n+1)\pmod{4}$$ Firs note that the generating function of $a(n)$ is $$A(x)=\sum_{n\geq 0}a(k)x^n=\prod_{k\geq 1}\left(\frac{1-x^{4k}}{1-x^k}\right)^2$$ for $\sigma(2n+1)$ the generating function is $$B(x)=\sum_{k\geq 0}\sigma(2k+1)x^k=\prod_{k\geq 0}(1-x^k)^4(1+x^k)^8$$ So $$B(x)\equiv \prod_{k\geq 1}(1+x^{2k})^2(1+x^{4k})^2\equiv \prod_{k\geq 1}(\frac{1-x^{8k}}{1-x^{2k}})^2\equiv A(x^2)\pmod{4}$$ Now the proof is complete once we know that $$B(x)\equiv \sum_{k\geq 0} \sigma(4n+1)x^{2n}\pmod{4}$$ this is an other way of saying $\sigma(4n-1)$ is divisible by $4$, which can be shown by pairing up the divisors $d+\frac{4n-1}{d}\equiv 0\pmod{4}$.

The proof for the other congruence is similar, but slightly longer, I might update this post later to include it.

Let's prove that $\sigma(8n+1)\equiv q(n)\pmod{4}$, where $q(n)$ is the number of partitions with no even part repeated. The generating function is $$Q(x)=\sum_{n\geq 0}q(n)x^n=\prod_{k\geq 1}\frac{1-x^{4k}}{1-x^k}$$ Since we know from above that $$\sum_{n\geq 0}\sigma(4n+1)x^{2n}\equiv \prod_{k\geq 1}(1+x^{2k})^2(1+x^{4k})^2 \pmod{4}$$ we conclude that $$L(x)=\sum_{n\geq 0}\sigma(4n+1)x^n\equiv Q(x)^2 \pmod{4}$$ so that $$\sum_{n\geq 0} \sigma(8n+1)x^{2n}\equiv \frac{L(x)+L(-x)}{2}\pmod{4}$$ So to finish off the proof we need the following $$\frac{Q(x)^2+Q(-x)^2}{2}\equiv Q(x^2)\pmod{4}$$ which I will leave as an exercise Actually let me write the proof, just to make sure I didn't mess up calculations. This reduces to proving $$\frac{\prod_{k\geq 1}(1+x^{2k})^4(1+x^{2k-1})^2+\prod_{k\geq 1}(1+x^{2k})^4(1-x^{2k-1})^2}{2}$$ $$\equiv \prod_{k\geq 1}(1+x^{4k-2})(1+x^{4k})^2 \pmod{4}$$ and since $$(1+x^{2k})^4\equiv (1+x^{4k})^2 \pmod{4}$$ this reduces to $$\frac{\prod_{k\geq 1}(1+x^{2k-1})^2+\prod_{k\geq 1}(1-x^{2k-1})^2}{2}\equiv \prod_{k\geq 1} (1+x^{4k-2})\pmod{4}$$ but we can write $$\prod_{k\geq 1}(1-x^{2k-1})^2\equiv \left(\prod_{k\ geq 1}(1+x^{2k-1})^2\right) \left(1-4\sum_{k\geq 1}\frac{x^{2k-1}}{(1+x^{2k-1})^2}\right)\pmod{8}$$ therefore now we have to show $$\prod_{k\geq 1}(1+x^{2k-1})^2\left(1-2\sum_{k\geq 1}\frac{x^{2k-1}}{(1+x^{2k-1})^2}\right)\equiv \prod_{k\geq 1}(1+x^{4k-2})\pmod{4}$$ Now everything is clear since $$\prod_{k\geq 1}(1+x^{2k-1})^2\equiv \prod_{k\geq 1}(1+x^{4k-2})\left(1+2\sum_{k\geq 1}\frac{x^{2k-1}}{(1+x^{2k-1})^2}\right)\pmod{4}$$

share|improve this answer
How do you prove that those are the generating functions for $a(n)$ and $\sigma(2n+1)$? –  zeb Mar 22 '11 at 14:40
Thank you Gjergji. Would it be possible the recently discovered congruences for partitions to be extended for the sequences in the question? –  joro Mar 22 '11 at 14:42
@zeb, that would be a nice exercise too :P. @joro, I don't know, perhaps it deserves a separate question? –  Gjergji Zaimi Mar 22 '11 at 15:08
Done. Let me know if the new questions needs changes: mathoverflow.net/questions/59192/… –  joro Mar 22 '11 at 15:36
@Gjergji There is some new empirical data - zeros and a(n)=a(9n+2). –  joro Mar 23 '11 at 14:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.