2
$\begingroup$

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!!

$\endgroup$
5
  • $\begingroup$ @RiverLi I've solved it :) $\endgroup$
    – Britta
    Jun 14, 2020 at 15:32
  • $\begingroup$ Congratuations! $\endgroup$
    – River Li
    Jun 14, 2020 at 15:35
  • $\begingroup$ 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}$? $\endgroup$
    – River Li
    Jun 14, 2020 at 15:43
  • $\begingroup$ oh, you are entirely right! feels like a very stupid mistake. $\endgroup$
    – Britta
    Jun 14, 2020 at 15:48
  • $\begingroup$ 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}$? $\endgroup$
    – River Li
    Jun 14, 2020 at 15:52

1 Answer 1

0
$\begingroup$

(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<a_1<2d$, 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<d$

  • 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<d$, 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<n+1$ 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<n+1$. 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<n+1$, 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.

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$
    – River Li
    Jun 15, 2020 at 0:19
  • $\begingroup$ 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$ $\endgroup$
    – River Li
    Jun 15, 2020 at 0:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .