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


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}$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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