# “strange” diophantine and parity of the partition function

Let $\{x_i\}:=\{x_1=5, x_2=13, x_3=29, x_4=37, x_5=45, \dots \}$ be the sequence of those positive integers of the form $$p^{4\alpha+1}n^2$$ in increasing order where $p\equiv 5\pmod 8$ is prime and $\gcd(n,2p)=1$. Next, define the sequence $\{y_i\}$ by letting $y_i:=\frac{x_i-5}{8}$. The first few terms of the $q$-series $\sum_{i=1}^{\infty}q^{y_i}$ are $$\sum_{i=1}^{\infty}q^{y_i}=1+q+q^3+q^4+q^5+q^6+q^7+q^{12}+q^{13}+q^{14}+q^{18}+q^{19}+\cdots.$$ If $p(N)$ denotes the number of ordinary integer partitions of $N$, then $$\sum_{N=0}^{\infty}p(N)q^N\equiv 1+q+q^3+q^4+q^5+q^6+q^7+q^{12}+q^{13}+q^{14}+q^{16}+q^{17} +q^{18}+\cdots\mod 2.$$ By comparing these two $q$-series one finds for $N\leq 15$ that $p(N)$ is odd precisely for those $N$ that are elements in the sequence $\{y_i\}$.

If one searches for long strings of consecutive even values of the partition function in arithmetic progressions, one immediately finds in the progression $10\pmod{16}$ that $$p(10)\equiv p(26)\equiv p(42)\equiv p(58)\equiv p(74)\equiv 0\pmod 2,$$ but $p(90)\equiv 1\pmod 2$. It is curious to note that $10, 26, 42, 58, 74\not \in \{y_i\}$ but $90=y_{45}$.

This motivates me to inquire:

Question. If $N< 16^k$, is the following true? $$p(N)\equiv \# \left \{ (z_0,z_1,\dots z_{k-1})\ | \ z_j\in \{y_i\}\ \text {and}\ \sum_{j=0}^{k-1}16^jz^j=N \right \} \mod 2.$$

Your conjecture is true! Here is one way to get it using some mod 4 generatingfunctionology. The answer got a bit long, so I divided it into two parts, as an attempt to improve readability.

Part1: Let's denote by $Y(q)$ your generating function $\sum_{i\geq 1}q^{y_i}$. We will prove that $$Y(q)\equiv \prod_{k\geq 1}(1+q^{2k-1})(1+q^{16k})\pmod{2}.$$

Proof: One very classical theorem that dates back to Legendre states that the number of ways of writing $n\in \mathbb N$ as a sum of four triangular numbers is equal to $\sigma(2n+1)$, the sum of divisors of $2n+1$. Since the generating function of triangular numbers admits an infinite product expression from Jacobi's triple product formula, we can rewrite this theorem in the language of generating functions: $$\sum_{n\geq 0}\sigma(2n+1)q^n=\prod_{k\geq 1}\frac{(1-q^{2k})^8}{(1-q^k)^4}.$$ I made use of this in an older answer, where we also pointed out the following simple corollary: $$\sum_{n\geq 0}\sigma(4n+1)q^n\equiv\prod_{k\geq 1}\left(\frac{1-q^{4k}}{1-q^k}\right)^2=\prod_{k\geq 1}(1+q^{2k-1})^2(1+q^{2k})^4\pmod{4}.$$ Let us denote $$A(q)=\sum_{n\geq 0}\sigma((2n+1)^2)q^{\binom{n+1}{2}}.$$ The next lemma will allow us to split $\sum_{n\geq 0}\sigma(2n+1)q^n \pmod{4}$ into its even and odd parts. More precisely it will show $$\sum_{n\geq 0}\sigma(2n+1)q^n\equiv A(q^2)+2qY(q^2) \pmod{4}$$

Lemma: The value of $\sigma(4n+1)$ is $1,3\pmod{4}$ iff 4n+1 is a perfect square, and it is $2\pmod{4}$ iff $n=2y_i+1$ for some $i$.

Proof of lemma: An odd number $m$ has a factorization $\prod p_i^{\alpha_i}q_j^{\beta_j}$ where $p_i$'s are primes $1\pmod 4$ and $q_j$'s are primes $3\pmod{4}$. The function $\sigma$ is multiplicative, so we just need to check the prime powers individually. $$\sigma(p_i^{\alpha_i})=\frac{p_i^{\alpha_i+1}-1}{p_i-1}\equiv \alpha_i+1\pmod{4}$$ $$\sigma(q_j^{\beta_j})=\frac{q^{\beta_j+1}-1}{q_j-1}\equiv\left\{ \begin{array}{ll} 1\pmod{4} & \beta_j\text{ is even} \\ 0\pmod{4} & \beta_j\text{ is odd} \\ \end{array} \right.$$ Using the fact that $\sigma(m)=\prod \sigma(p_i^{\alpha_i})\sigma(q_j^{\beta_j})$ we see that $\sigma(m)$ is odd iff each $\alpha_i$ and $\beta_j$ are even, iff $m$ is a perfect square. We also see that $\sigma(m)=2\pmod{4}$ iff all $\beta_j$ are even, and exactly one $\alpha_i$ is $1\pmod{4}$, which is equivalent to saying that $m$ is one of the elements of your $x_i$ sequence. Now, $4n+1=x_i \implies n=2y_i+1$, so this concludes the proof of the lemma.

Some algebraic manipulations give us $$\prod_{k\geq 1}(1+q^{2k-1})^2(1+q^{2k})^4=\prod_{k\geq 1}(1+q^{4k-2})(1+q^{2k})^4\prod_{k\geq 1}(1+2\frac{q^{2k-1}}{1+q^{4k-2}})$$ $$\equiv \prod_{k\geq 1}(1+q^{4k-2})(1+q^{2k})^4\left(1+2\sum_{k\geq 1} \frac{q^{2k-1}}{1+q^{4k-2}}\right)\pmod{4}.$$ Therefore we have an expression for $Y(q)\pmod{2}$ $$Y(q)\equiv \prod_{k\geq 1}(1+q^{2k-1})(1+q^{k})^4\left(\sum_{k\geq 1} \frac{q^{k-1}}{1+q^{2k-1}}\right)\pmod{2}$$ $$\equiv \prod_{k\geq 1}(1+q^{2k-1})(1+q^{k})^4\left(\sum_{k\geq 1} \frac{q^{k-1}}{1-q^{2k-1}}\right)\pmod{2}.$$ Next we notice that the coefficient of $q^n$ in $\sum_{k\geq 1} \frac{q^{k-1}}{1-q^{2k-1}}$ counts the number of integers $r\geq 0,k\geq 1$ such that $n=k-1+r(2k-1)$, which can be rewritten as $2n+1=(2k-1)(2r+1)$. The number of solutions to this equation is precisely the number of divisors of $2n+1$, and since the divisors of an odd number are odd, the number of divisors of $2n+1$ has the same parity as the sum of divisors of $2n+1$. Therefore $\sum_{k\geq 1} \frac{q^{k-1}}{1-q^{2k-1}}$ is also equal to $\sum_{n\geq 0}\sigma(2n+1)q^n\pmod{2}$. Plugging this in our equation gives $$Y(q)\equiv \prod_{k\geq 1}(1+q^{2k-1})(1+q^{k})^4\frac{(1-q^{2k})^8}{(1-q^k)^4}\equiv \prod_{k\geq 1}(1+q^{2k-1})(1+q^{16k})\pmod{2}$$ and this finishes our proof. $\blacksquare$

Part2: Your conjecture would follow easily from the equality $$\prod_{k\geq 1}\frac{1}{1-q^k}\equiv \prod_{i\geq 0}Y(q^{16^i})\pmod{2}.$$ Indeed the coefficient of $q^n$ on the left represents the parity of $p(n)$, the number of partitions of $n$, whereas the right hand side represents the number of ways of writing $n=z_0+16z_1+16^2z_2+\cdots$ where each $z_j$ is equal to some $y_i$.

In order to prove this we will use the mod 2 identity $$\prod_{k\geq 1}(1+q^{2k-1})=\prod_{k\geq 1}\frac{1+q^k}{1+q^{2k}}=\prod_{k\geq 1}\frac{1+q^k}{(1+q^k)^2}=\prod_{k\geq 1}\frac{1}{1+q^k}\pmod{2}$$ which implies that $$\prod_{k\geq 1}(1+q^{16k})=\prod_{k\geq 1}\frac{1}{1+q^{16(2k-1)}}\pmod{2}.$$ We can use this in our expression for $Y(q)$ to get $$Y(q)=\prod_{k\geq 1}\frac{1+q^{2k-1}}{1+q^{16(2k-1)}}$$ which shows that the product $Y(q)Y(q^{16})Y(q^{16^2})\cdots$ telescopes to $\prod_{k\geq 1} (1+q^{2k-1})$ which is equal to the partition function $\pmod{2}$ thanks to the same identity above.

• Cute question, by the way. I would have never guessed that $Y(q)$ has such a simple infinite product expansion mod 2, had I not been looking for it. – Gjergji Zaimi May 13 '17 at 7:34
• This is very cool. A few questions. Can you prove: (1) $\sigma(4n+1)$ is odd iff $4n+1$ is a perfect square, (2) the numbers $2y_i+1$ are exactly the numbers $n$ for which $\sigma(4n+1)\equiv 2\pmod{4}$? Also edit this: $2n+1=(2k-1)(2r+1)$. – T. Amdeberhan May 13 '17 at 20:47
• @T.Amdeberhan I fixed the typo, and added a lemma to explain (1) and (2). – Gjergji Zaimi May 13 '17 at 23:14