# How can i rewrite my specific $F_{n,2d}^a$ polynomial to be a sum of $(3n-4)$ squares?

So, i've been messing around with the following $$n$$-variate polynomials of degree $$2d$$: $$F_{n,2d}^a = \sum_{i=1}^n a_ix_i^{2d} + 2d\prod_{i=1}^n x_i^{a_i}$$ Where $$\sum_{i=1}^n a_i=2d$$ Now, i want to show that this $$F_{n,2d}^a$$ can be written at most as the sum of $$3n-4$$ squares.

I thought of doing it per induction, but there were two problems:

• $$F_{2,2d}^a$$ can be written as 2 sums of squares (which works) , but i couldn't prove it
• even if i could, it doesnt work because if you presume $$\sum_{i=1}^n a_i=2d$$, you cant say this about $$\sum_{i=1}^{n+1} a_i$$ anymore.

What can I do? (I would like to show the first one anyway, just to understand whats going on. so if you have any ideas on that, let me know)

thanks!!

• @RiverLi I've solved it :) Jun 14, 2020 at 15:32
• Congratuations! Jun 14, 2020 at 15:35
• From your solution, do you mean $F_{n,2d}^a = \sum_{i=1}^n a_ix_i^{2d} + 2d\prod_{i=1}^n x_i^{a_i}$ rather than $F_{n,2d}^a = \sum_{i=1}^n a_ix_i^{2d} + 2d\sum_{i=1}^n x_i^{a_i}$? Jun 14, 2020 at 15:43
• oh, you are entirely right! feels like a very stupid mistake. Jun 14, 2020 at 15:48
• It seems there are some typos. Do you mean $F_{n,2d}^a = \sum_{i=1}^n a_ix_i^{2d} - 2d\prod_{i=1}^n x_i^{a_i}$ (see your 1st equation in your solution). Also, check your 1st equation in your solution, $a_2x_2^{2d}$? Jun 14, 2020 at 15:52

(1) First, we prove $$F_{2,2d}^a$$ is the sum of two squares:

So $$F_{2,2d}^a=a_1x_1^{2d} +a_2x_2^{2d} -2dx_1^{a_1}x_2^{a_2}$$

We can take the homonization $$P(x) = a_1x^{2d} + a_2 -2dx^{a_1}$$, which is univariate. If we now show that $$P(x)\geq 0$$, then it follows from excercise 11.3(b) in the lecture notes that $$P$$ is a sum of at most two squares. And if we then rewrite this sum of square polynomial it to its homogeniousation, $$F_{2,2d}^a$$, we attain that this can also only be a sum of at most two squares as well.

Now, to prove $$P\geq0$$, there are 3 cases we can distinguish between:

• $$a_1=0$$, In this case we'd have: $$P(x) = 0 + 2d - 2dx^0 = 0$$, which is clearly a sum of zero squares.

• $$a_1=2d$$, In this case we'd have: $$P(x) = 2dx^{2d} - 2dx^{2d} = 0$$, which is clearly also a sum of zero squares.

• $$0, In that case we see that \begin{align*} \lim\limits_{x\to \infty} P(x) &= \lim\limits_{x\to \infty} a_1x^{2d} + a_2 -2dx^{a_1}\\ &= \lim\limits_{x\to \infty} a_1x^{2d} \\ &= \lim\limits_{x\to \infty} a_1(-x)^{2d} \\ &= \lim\limits_{x\to -\infty} a_1x^{2d} \\ &= \lim\limits_{x\to -\infty} a_1x^{2d} + a_2 -2dx^{a_1}\\ &= \lim\limits_{x\to -\infty} P(x) \end{align*} Then, $$\frac{\partial}{\partial x} P(x) = 2da_1x^{2d-1} - 2da_1x^{a_1-1} = 2da_1x^{a_1-1}(x^{2d-a_1} - 1)$$, so our extreme points are attained at 0 and 1 (and possibly -1, in the case that $$a_1$$ is even). Which are $$P(0)=a_2$$ and $$P(1) = a_1 + a_2 - 2d=0$$. And as we know $$a_2>0$$, we know that $$P(x)\geq 0$$.

$$\begin{pmatrix} 0 & \frac{a_1}{2} & & -d \\ \frac{a_1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{a_1}{2} \\ -d & 0 & \frac{a_1}{2} & 0 \\ \end{pmatrix}$$ and take the vector $$\begin{pmatrix} x_1^{a_1} \\ x_1^{a_2} \\ x_2^{a_1} \\ x_2^{a_2} \\ \end{pmatrix}$$ But this is not a PSD matrix because the vector (1,-1,0,0) makes things go off.

(2) Now we show that if $$a\in\mathbb{N}^n$$ with $$|a|= 2d$$ that $$a$$ can be decomposed as $$a=b+c$$, where $$b,c\in\mathbb{N}^n$$, $$|b|=|c|= d$$ and there is at most one index $$i \in[n]$$ such that $$b_i,c_i>̨0$$. There are two options: there exists an $$i$$ such that $$a_i\geq d$$ or $$\forall i$$ $$a_i

• In the case there exists an $$i$$ such that $$a_i\geq d$$ set $$\begin{equation*} b_j = \begin{cases} 0 \quad & j\neq i\\ d & j=i \end{cases} \qquad \text{ and } \qquad c_j = \begin{cases} a_j & j\neq i\\ a_i-d & j=i \end{cases} \end{equation*}$$ Then $$|b| = 0+\dots+0+d =d$$ and $$|c| = \smash{\sum_{j\neq i} a_j + a_i -d = \smash{\sum_{i=1}^n} a_i} -d = 2d-d=d$$. And it is also trivial that $$(b+c)_j = \begin{cases} 0 +a_j \quad & j\neq i\\ d + a_i-d& j=i \end{cases} = a_j \quad \Rightarrow b+c=a$$

• In the case $$\forall i$$ $$a_i, set $$m = \max\Bigg\{i\in[n] \mid \smash{\sum_{j=1} ^i} a_i \leq d\Bigg\}$$ Then set $$\begin{equation*} b_j = \begin{cases} a_i \quad & i\leq m\\ d-\smash{\sum_{j=1}^m} a_j & i=m+1 \\ 0 & i>m+1\end{cases} \qquad \text{ and } \qquad c_j = \begin{cases} 0 \quad & i\leq m\\ d-\smash{\sum_{j=m+2}^n} a_j & i=m+1 \\ a_i & i>m+1\end{cases} \end{equation*}$$

Then $$|b| =\smash{\sum_{j=1}^m} a_j +d-\smash{\sum_{j=1}^m} a_j =d$$ and $$|c| = \smash{\sum_{j=m+2}^n} a_j +d-\smash{\sum_{j=m+2}^n} a_j =d$$. And lastly, \begin{align*} (b+c)_i & = \begin{cases} a_i+0 \quad & i\leq m\\ d-\smash{\sum_{j=1}^m} a_j +d-\smash{\sum_{j=m+2}^n} a_j & i=m+1 \\ 0+a_i & i>m+1\end{cases}\\ &= \begin{cases} a_i \quad & i\leq m\\ 2d-\smash{\sum_{j\neq m+1}} a_j & i=m+1 \\ a_i & i>m+1\end{cases}\\ &= \begin{cases} a_i \quad & i\leq m\\ \smash{\sum_{j=1}^n} a_j-\smash{\sum_{j\neq m+1}} a_j & i=m+1 \\ a_i & i>m+1\end{cases}\\ &= \begin{cases} a_i \quad & i\leq m\\ a_{m+1} & i=m+1 \\ a_i & i>m+1\end{cases}\\ &= a_i \end{align*} $$\Rightarrow b+c=a$$ Thus, for both cases there is at most one index $$i \in[n]$$ such that $$b_i,c_i>̨0$$

(3) Now we show that with $$a, b, c$$ as in (2), show that $$F_{n,2d}^a(x) =\frac{1}{2}\Big(F_{n,2d}^{2b}(x)+F_{n,2d}^{2c}(x)\Big) + d(x^b-x^c)^2$$

\begin{align*} \frac{1}{2}\Big(F_{n,2d}^{2b}(x)&+F_{n,2d}^{2c}(x)\Big) + d(x^b-x^c)^2\\ &= \frac{1}{2}\Bigg(\smash{\sum_{i=1}^n} 2b_ix_i^{2d} - 2dx^{2b} + \smash{\sum_{i=1}^n} 2c_ix_i^{2d} - 2dx^{2c} \Bigg) + d(x^b-x^c)^2\\ &= \smash{\sum_{i=1}^n} (b_i+c_i)x_i^{2d} - d(x^{2b}+ x^{2c}) + d(x^b-x^c)^2\\ &\\ (*)&= \smash{\sum_{i=1}^n} a_ix_i^{2d} - d(\smash{\prod_{i=1}^n} x_i^{2b_i} + \smash{\prod_{i=1}^n} x_i^{2c_i} ) + d(\smash{\prod_{i=1}^n} x_i^{b_i} -\smash{\prod_{i=1}^n} x_i^{c_i})^2\\ \end{align*} Then we have \begin{align*} \Big(\smash{\prod_{i=1}^n} x_i^{b_i} -\smash{\prod_{i=1}^n} x_i^{c_i} \Big)^2& = \smash{\prod_{i=1}^n} x_i^{2b_i} + \smash{\prod_{i=1}^n} x_i^{2c_i} - 2\smash{\prod_{i=1}^n} x_i^{b_i}\smash{\prod_{i=1}^n} x_i^{c_i} \\ &\\ &= \smash{\prod_{i=1}^n} x_i^{2b_i} + \smash{\prod_{i=1}^n} x_i^{2c_i} - 2\smash{\prod_{i=1}^n} x_i^{b_i+c_i}\\ &\\ &= \smash{\prod_{i=1}^n} x_i^{2b_i} + \smash{\prod_{i=1}^n} x_i^{2c_i} - 2\smash{\prod_{i=1}^n} x_i^{a_i}\\ \end{align*} $$\iff$$ $$\smash{\prod_{i=1}^n} x_i^{2b_i} + \smash{\prod_{i=1}^n} x_i^{2c_i} = \Big(\smash{\prod_{i=1}^n} x_i^{b_i} -\smash{\prod_{i=1}^n} x_i^{c_i} \Big)^2 + 2\smash{\prod_{i=1}^n} x_i^{a_i}$$

So we can continue \begin{align*} \smash{\sum_{i=1}^n} a_ix_i^{2d} - &d(\smash{\prod_{i=1}^n} x_i^{2b_i} + \smash{\prod_{i=1}^n} x_i^{2c_i} ) + d(\smash{\prod_{i=1}^n} x_i^{b_i} -\smash{\prod_{i=1}^n} x_i^{c_i})^2\\ \\ &= \smash{\sum_{i=1}^n} a_ix_i^{2d} - d\Bigg(\Big(\smash{\prod_{i=1}^n} x_i^{b_i} -\smash{\prod_{i=1}^n} x_i^{c_i} \Big)^2 + 2\smash{\prod_{i=1}^n} x_i^{a_i} \Bigg) + d(\smash{\prod_{i=1}^n} x_i^{b_i} -\smash{\prod_{i=1}^n} x_i^{c_i})^2\\ \\ &= \smash{\sum_{i=1}^n} a_ix_i^{2d} - 2d \smash{\prod_{i=1}^n} x_i^{a_i} \\ \\ &= F_{n,2d}^a(x) \end{align*}

(4) And now we show that, for any $$a\in\mathbb{N}^n$$ with $$|a|=2d$$, the polynomial $$F_{n,2d}^a$$ can be written as the sum of at most $$3n - 4$$ squares.

We prove this by induction. We know it holds for $$n=2$$, as can be assumed from (1) (because $$F_{2,2d}^a$$ is sum of 2 squares, and $$3\times 2 -4 = 2$$.) Now, we assume it holds for all $$k\leq n$$, and we show it holds for $$n+1$$.

From (3) we know $$F_{n+1,2d}^a(x) =\frac{1}{2}\Big(F_{n+1,2d}^{2b}(x)+F_{n+1,2d}^{2c}(x)\Big) + d(x^b-x^c)^2$$ with the assumtions on $$b$$ and $$c$$ as in (2). Define $$I_b = \{i\in[n+1] \mid b_i\neq 0\}$$ and $$I_c = \{i\in[n+1] \mid c_i\neq 0\}$$ and set $$n_b=|I_b|$$ and $$n_c=|I_c|$$. Then, from (2) we know that $$n_b+n_c \leq n+2$$ as they have at most one component double. So there are two cases: $$n_b$$, $$n_c or $$n_b=n=1$$ and $$n_c=1$$ or the other way around.

We'll first show the case of $$n_b$$, $$n_c. Define the vectors $$b'=b_{I_b}\in \mathbb{N}^{n_b}$$ and $$c'=c_{I_c}\in \mathbb{N}^{n_c}$$ as the vectors $$b$$ and $$c$$ with the zero components deleted. Then the polynomials $$F_{n+1,2d}^{2b}$$ and $$F_{n+1,2d}^{2c}$$ are equivalent to the polynomials $$F_{n_b,2d}^{2b'}$$ and $$F_{n_c,2d}^{2c'}$$, because $$b_k=0 \quad \forall k\notin I_b$$. So for these $$k\notin I_b$$ we have $$b_kx_k =0$$ and $$x_k^{b_k}=1$$. Thus $$F_{n+1,2d}^{2b}=F_{n_b,2d}^{2b'}$$. Same thus holds for $$c'$$. Because $$n_b$$, $$n_c, we can apply the induction hypotheses. So, for these $$F_{n+1,2d}^{2b}$$ and $$F_{n+1,2d}^{2c}$$ we know from the induction hypothesis that these are the sums of at most $$3n_b-4$$ and $$3n_c-4$$ squares resp.

Then, as $$F_{n,2d}^a(x) =\frac{1}{2}\Big(F_{n,2d}^{2b}(x)+F_{n,2d}^{2c}(x)\Big) + d(x^b-x^c)^2$$, this is the sum of at most $$3n_b-4+3n_c-4 + 1$$ squares. Which is the same as $$3(n_b+n_c)-7 = 3(n+2)-7=3(n+1)-4$$. Thus $$F_{n+1,2d}^a(x)$$ is the sum of at most $$3(n+1)-4$$ squares.

Now, in the case where $$n_b=n=1$$ and $$n_c=1$$ or the other way around, assume wlog that $$n_b=n=1$$ and $$n_c=1$$. Then we can keep splitting $$2b$$ until we do have that it splits into two vectors $$b_1$$ and $$b_2$$ such that $$2b=b_1+b_2$$ and $$|b_1|=d$$ and $$|b_2|=d$$. And then we can just apply the induction hypothesis as above. For $$c$$ an possible other offsplittings of $$b$$ with $$n_c=1$$, we know $$c=de_i$$ (with $$e_i$$ being the $$i^{th}$$ canonical basis vector), because it only has one non zero component and $$|c|=d$$. But in this case $$F_{n+1,2d}^{2c} = 2dx_i^{2d} - 2dx_i^{2d} =0$$. So this is just the zero polynomial and has zero sums of squares. Therefore we know that in the end $$F_{n+1,2d}^{2b}$$ is at most $$3n_b-4$$ sums of squares.

• For (1), alternative solution: By AM-GM inequality $P(x) = a_1x^{2d} + a_2 -2dx^{a_1} = \underbrace{x^{2d} + x^{2d} + \cdots + x^{2d}}_{a_1} + \underbrace{1+1+\cdots + 1}_{a_2} - 2d x^{a_1} \ge (a_1+a_2) \sqrt[a_1+a_2]{(x^{2d})^{a_1}} - 2d x^{a_1} = 2d |x|^{a_1} - 2dx^{a_1} \ge 0$ Jun 15, 2020 at 0:19
• Also, $F_{n, 2d}^a \ge 2d \sqrt[2d]{(x_1^{2d})^{a_1} (x_2^{2d})^{a_2} \cdots (x_n^{2d})^{a_n}} - 2d \prod_{i=1}^n x_i^{a_i} = 2d \prod_{i=1}^n |x_i|^{a_i} - 2d \prod_{i=1}^n x_i^{a_i} \ge 0$ Jun 15, 2020 at 0:35