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.

  • $\begingroup$ 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. $\endgroup$ – Gjergji Zaimi May 13 '17 at 7:34
  • $\begingroup$ 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)$. $\endgroup$ – T. Amdeberhan May 13 '17 at 20:47
  • $\begingroup$ @T.Amdeberhan I fixed the typo, and added a lemma to explain (1) and (2). $\endgroup$ – Gjergji Zaimi May 13 '17 at 23:14

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.