Consider the finite sums
$$F\_n(q)=\sum\_{k=1}^nq^{\binom{k}2}$$
with exponents the *triangular numbers* $\binom{k}2$. When $n$ is odd, it appears that $F\_n(q)$ does not factorize over $\mathbb{Z}[q]$. On the other hand, when $n=2m$ is even



> 
> **QUESTION.** is it true that $F\_{2m}(q)$ is divisible by the product
>  $$\prod\_{j\geq0}(1+q^{m/2^j})$$
>  where the product extends so long as $m/2^j$ is an integer.
> 
> 
> 


**Examples.** Here is a sample:
\begin{align}
(1+q^2)(1+q)\,\vert&\, F\_4(q); \qquad (1+q^3)\,\,\vert\,F\_6(q); \\
(1+q^4)(1+q^2)(1+q)\,\,\vert&\,F\_8(q); \qquad (1+q^6)(1+q^3)\,\,\vert\,F\_{12}(q).
\end{align}



Divisibility of certain polynomials
**Yes.**


Let $n = a\*2^b$ with $a$ odd. Then your question is whether $\prod\_{j = 1}^{b} \left((1 + q^{\frac{n}{2^j}})\right) \, | \, F\_n(q)$. Multiplying both by $q^a - 1$, the question becomes whether $F\_n(q)(q^a - 1)$ is divisible by $q^{n} - 1$. 


Consider the multiset $\{{i(i - 1)} (\text{mod} \; 2n)\}\_{i = 1}^{2n}$. I claim that this multiset is invariant under translation by $2a$, that is, the number of times the residue class $x (\text{mod} \; 2n)$ appears is the same as the number of times $x + 2a$ appears. 


The Chinese remainder theorem on rings allows us to analyze the multiset using the remainders modulo $a$ and $2^{b + 1}$ separately; the distribution of outcomes will be the product of the distributions on each. We first tackle $a$. As $2a \equiv 0 (\text{mod} \; a)$, the distribution of remainders modulo $a$ will be invariant under translation by $2a$. 


On the other hand, consider the map $i \mapsto i (i - 1): \mathbb{Z}/2^{b + 1} \rightarrow \mathbb{Z}/2^{b + 1}$. Clearly, all outcomes must be even. I claim that each even outcome appears exactly twice. Assume $i(i - 1) = j (j - 1) (\text{mod} \; 2^{b + 1})$. Then $(i - j)(i + j - 1) = 0 (\text{mod} \; 2^{b + 1})$. The two factors are of opposite parity, so one of them is odd, while the other must be divisible by $2^{b + 1}$. Therefore, each outcome appears at most twice. But by pigeonhole principle, we therefore have that each even outcome appears exactly twice - and so the distribution of remainders modulo $2^{b + 1}$ is invariant under translation by any even amount, including $2a$. 


Putting these together, we have that the multiset of outcomes $\{i(i - 1) (\text{mod} \; 2n)\}\_{i = 1}^{2n}$ is invariant under translation by $2a$. We have that $i (i - 1) \equiv (1 - i)(1 - i - 1)$, so by restricting to $1 \leq i \leq n$, we cut the multiset exactly in half - so $\{i(i - 1) (\text{mod} \; 2n)\}\_{i = 1}^{n}$ is also invariant under translation by $2a$. Then, by dividing the polynomial by $2$ (and also dividing the modulus by $2$), we get that the multiset of outcomes $\{{i \choose 2} = \frac{i(i - 1)}{2} (\text{mod} \; n)\}\_{i = 1}^{n}$ is invariant under translation by $a$. 


This implies that $\sum\_{i=1}^n q^{i \choose 2} \equiv \sum\_{i=1}^n q^{{i \choose 2} + a} (\text{mod} \; q^n - 1)$, as if $x \equiv y (\text{mod} \; n)$, then $q^x \equiv q^y (\text{mod} \; q^n - 1)$. We can rewrite this as $q^n - 1 | \sum\_i q^{{i \choose 2} + a} - q^{i \choose 2} = (q^a - 1) F\_n(q)$, so we are done.


