Decomposing $\sum_{i = 0}^{2n} x^i$ as a simple sum of squares

Question

As we have $\sum_{i = 0}^{2n} x^i = (x^{2n + 1} - 1) / (x - 1)$, the polynomial is positive. So we know that there is a decomposition as a sum of squares. Is there a closed simple form for such a decomposition? For small value of $n$ we have $$ x^2 + x + 1 = 1/4 ((2x+1)^2+ 3)$$ $$ x^4 + x^3 + x^2 + x + 1 = 1/16((4 x^2 + 2 x + 1)^2 + (2 x + 3)^2 + 6)$$ $$ x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 = 1/144 ((12x^3+6x^2+4x+3)^2+ 3(2x^2+2x+5)^2 + 5(2x+3)^2 +15)$$

Answer 1

Note that $$\begin{split} \sum_{k=0}^{2n}x^k &= \frac{x^{2n+1}-1}{x-1} \\ &= (2n+1)\int_0^1 (1-t + tx)^{2n}\mathrm{d}t \\ &= \frac{2n +1}{2^{2n+1}} \int_{-1}^1(x+1 + (x-1)t)^{2n}\mathrm{d}t \\ &= \sum_{k=0}^{2n}\frac{_{2n}C_k(2n +1)}{2^{2n+1}} \int_{-1}^1(x+1)^{2n-k}(x-1)^{k}t^k\mathrm{d}t \\ &= \sum_{k=0}^{n}\frac{_{2n}C_{2k}(2n+1)}{2^{2n}(2k+1)} (x+1)^{2n-2k}(x-1)^{2k}\text{;} \end{split}$$ whence $$\boxed{\sum_{k=0}^{2n}x^k =\sum_{k=0}^{n}\frac{_{2n}C_{2k}(2n+1)}{2^{2n}(2k+1)} ((x+1)^{n-k}(x-1)^{k})^2}\text{.}$$ Consequently, if $\frac{_{2n}C_{2k}(2n+1)}{2^{2n}(2k+1)}$ is a sum of squares (all nonnegative rationals are), then $\sum_{k=0}^{2n}x^k$ is a sum of squares with rational coefficients.

Answer 2

Let $\,\omega\,$ be a primitive $\,(2n+1)^{th}\,$ root of unity, so $\,\omega^{2n+1}=1\,$ and $\,\omega^{2n+1-k} = \dfrac{1}{\omega^k}=\overline{\omega^k}\,$. Then:

$$ P(x)=\sum_{k=0}^{2n} x^k = \prod_{k=1}^{2n}(x-\omega^k) = \prod_{k=1}^n\big((x-\omega^k)(x-\overline{\omega^k})\big) = \underbrace{\prod_{k=1}^n(x-\omega^k)}_{Q(x)} \;\underbrace{\prod_{k=1}^n(x-\overline{\omega^k})}_{\overline{\,Q\,}(x)} $$

$Q\,$ is a polynomial with complex coefficients which can be written as $\,Q(x)=U(x) + i V(x)\,$ where $\,U,V\,$ are polynomials with real coefficients. It follows that:

$$ P(x) = Q(x) \, \overline{Q}(x)=\big(U(x)+i V(x)\big)\big(U(x)-i V(x)\big)=U^2(x) + V^2(x) $$

---

[ EDIT ] $\;$ The above proves that $\,P(x)\,$ can always be written as the sum of just $\,2\,$ squares, and gives an explicit form for the two polynomials. However, $\,U(x)\,$ and $\,V(x)\,$ will generally not have rational coefficients, and can be laborious to calculate. A couple of examples below.

• $n=1:\;$ then $\,\omega = e^{i\,2\pi/3}=\frac{-1 + i\sqrt{3}}{2}\,$ and $\,Q(x) = \underbrace{\frac{2x+1}{2}}_{\, U(x)} + i \cdot \underbrace{\frac{-\sqrt{3}}{2}}_{\,V(x)}\,$, so:

$$ P(x)=U^2(x)+V^2(x) \quad\iff\quad x^2+x+1 =\frac{1}{4}\big((2x+1)^2 + 3\big) $$

• $n=2:\;$ then $\,\omega = e^{i\,2\pi/5}=\frac{1}{4} (\sqrt{5} - 1) + i \sqrt{\frac{1}{8}\left(5 + \sqrt{5}\right)}\;$ and:

$$ Q(x)=\frac{1}{4} (4 x^2 + 2 x - \sqrt{5} - 1) - \frac{1}{4} i \sqrt{\frac{5 + \sqrt{5}}{2}} \left(\left(\sqrt{5} + 1\right) x + \sqrt{5} - 1\right) $$

    so:

$$ x^4+x^3+x^2+x+1 = \frac{1}{16}(4 x^2 + 2 x - \sqrt{5} - 1)^2 + \frac{5 + \sqrt{5}}{32} \left((\sqrt{5} + 1)x + \sqrt{5} - 1\right)^2 $$

Answer 3

$$ P(x) = \prod_{d \mid 2n+1, d \neq 1} \Phi_d (x)\\ $$

So focus on getting a good decomposition for $\Phi_d (x)$.

$\Phi_d (x)$ is a product of $\phi(d)$ terms. $d$ is not even because it divides $2n+1$ and it is greater than $1$ by assumption. For the factor corresponding to $k$ there is also the factor corresponding to $d-k$ and those two are conjugate and distinct so $\Phi_d (x) = Q(x) \overline{Q}(x)$ for some $Q$ as before but with the caveat that now we are taking only other primitive roots of unity rather than all powers of $\omega$. But that doesn't really help because the decomposition is still using polynomials with irrational and hard to compute coefficients.

Another property $\Phi_n (x) = \Phi_q (x^{n/q})$ where $q$ is the radical of $n$ by only keeping the same prime factors but only with multiplicity $1$.

So we focus on providing good sum of squares decomposition for $\Phi_q (x)$ where $q$ is a square free number dividing $2n+1$ and greater than $1$.

If $q=3$, then

$$ \Phi_3 (x) = x^2 + x + 1\\ = (x+\frac{1}{2})^2 + (\frac{1}{2})^2 + (\frac{1}{2})^2 + (\frac{1}{2})^2\\ $$

Otherwise Gauss' formula applies

$$ \Phi_q (x) = (\frac{1}{2} A_n (x))^2 - (-1)^{(q-1)/2} q (\frac{1}{2} x B_n(x))^2\\ $$

When $q \equiv 3 (4)$ this gives a decomposition into a sum of $q+1$ squares of polynomials. All the coefficients involved are half-integers in this case.