17-я проблема Гильберта

[Rak so dna]

Хочу предложить элементарное, конструктивное решение 17-й проблемы Гильберта для многочленов одной переменной, а также обсудить возможность расширить его на две и более переменных.

Формулировка: Любой неотрицательный многочлен можно представить в виде суммы квадратов рациональных функций.

Обозначения и определения:

"скобка чётной степени" ─ запись вида $(\cdots)^{2n}$, $n \in \mathbb{N}$ ;
"скобка нечётной степени" ─ запись вида $(\cdots)^{2n+1}$, $n \in \mathbb{N}$ ;
форма $SOS$ ─ сумма рациональных функций, в записи которых все знаки "$-$" и все переменные содержатся внутри скобок чётной степени ;
форма $SOS^+$ ─ сумма рациональных функций, в записи которых все знаки "$-$" содержатся внутри скобок чётной степени ;
форма $SOS^+[x_1,x_2\cdots x_n]$ ─ сумма рациональных функций, в записи которых переменные $x_1,x_2\cdots x_n$ и все знаки "$-$" содержатся внутри скобок чётной степени ;

*Во всех обозначениях ниже, вместо $x$ и $y$ можно рассматривать $x_1,x_2\cdots x_n$ и $y_1,y_2\cdots y_n$ соответственно.

$^+P_1(x,y)$ ─ неотрицательная рациональная функция $P_1$, при $x,y\geq0$ ;

$^{+S}P_1(x,y)$ ─ рациональная функция $P_1$, записанная в форме $SOS^+$ ;

$^{\ +}_{[x]}P_1(x,y)$ ─ неотрицательная рациональная функция $P_1$, при $x \in \mathbb{R}$, $y\geq0$ ;

$^{+S}_{[x]}P_1(x,y)$ ─ рациональная функция $P_1$, записанная в форме $SOS^+[x]$ ;

$^{S}P_1(x,y)$ ─ рациональная функция $P_1$, записанная в форме $SOS$ ;

*Если по контексту ясно (а так будет в подавляющем большинстве случаев), от каких переменных зависит рациональная функция, скобки после её названия будут опускаться, т.е. вместо $P_1(x)$ просто $P_1$.

$A\mathrel{|}\joinrel=B$ ─ отношение общего представления (читается: " любую форму $A$ можно представить формой $B$ ") ;

$^{\ X}_{[Y]}\mathcal{F}\{x,y,z,...\}$ ─ выражение вида $x\cdot^{\ X}_{[Y]}P_1+y\cdot^{\ X}_{[Y]}P_2+z\cdot^{\ X}_{[Y]}P_3+...$ ;

*Здесь $\mathcal{F}$ следует понимать как форму, поэтому индексы отсутствуют. Например, выражение $^{+S}\mathcal{F}\{x,y\}\cdot ^{+S}\mathcal{F}\{x,y\}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{xy,1\}$ следует понимать так:
$\left(x\cdot^{+S}A_1+y\cdot^{+S}A_2\right)\left(x\cdot^{+S}B_1+y\cdot^{+S}B_2\right)\mathrel{|}\joinrel=xy\cdot^{+S}C_1+^{+S}C_2$ и читается:
" произведение двух любых форм $^{+S}\mathcal{F}\{x,y\} $ представляется формой $^{+S}\mathcal{F}\{xy,1\}$ "

Некоторые простые свойства:

1. $_{[x_1,x_2\cdots x_n]}^{\qquad\quad+S}P(x_1,x_2\cdots x_n)=^SP(x_1,x_2\cdots x_n)$

2. $_{[\{x_i\}]}^{\quad+S}P(x_1,x_2\cdots x_n)\mathrel{|}\joinrel=^{+S}P(x_1,x_2\cdots x_n)$

3. $^{+S}\mathcal{F}\{1,1\}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{1\}+^{+S}\mathcal{F}\{1\}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{1\}$ т.е. всегда существует форма $^{+S}P_3$ такая, что $^{+S}P_1+^{+S}P_2\mathrel{|}\joinrel=^{+S}P_3$

4. $^{+S}\mathcal{F}\{1\}\cdot^{+S}\mathcal{F}\{1\}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{1\}$ т.е. всегда существует форма $^{+S}P_3$ такая, что $^{+S}P_1\cdot^{+S}P_2\mathrel{|}\joinrel=^{+S}P_3$

5. $\frac{^{+S}\mathcal{F}\{1\}}{^{+S}\mathcal{F}\{1\}}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{1\}$

6. пусть форма $^{+S}\mathcal{F}\{1\}$ представляет некоторую рациональную функцию переменных $x,\cdots$, тогда:
$^{+S}\mathcal{F}\{1\}=^{+S}_{[x]}\mathcal{F}\{x,1\}$

7. пусть форма $^{+S}\mathcal{F}\{1\}$ представляет некоторую рациональную функцию переменных $x,y,\cdots$, тогда:
$^{+S}\mathcal{F}\{1\}=^{\ +S}_{[x,y]}\mathcal{F}\{xy,x,y,1\}$

8. пусть форма $^{+S}\mathcal{F}\{1\}$ представляет некоторую рациональную функцию переменных $x,y,z,\cdots$, тогда:
$^{+S}\mathcal{F}\{1\}=^{\quad+S}_{[x,y,z]}\mathcal{F}\{xyz,xy,yx,xz,x,y,z,1\}$

Пример использования форм:
Дан многочлен $P(x,y,z)$ такой, что многочлены

$$ \begin{cases} P(x,x+y,x+y+z)\\ P(x+y+z,y+z,z)\\ P(x,x+y+z,x+z)\\ P(x+y+z,y,y+z)\\ P(x+y,y,x+y+z)\\ P(x+z,x+y+z,z) \end{cases} $$

не имеют отрицательных коэффициентов. Доказать, что $P=^{+S}P$

Имеем:

$$ \begin{cases} P(x,x+y,x+y+z)=^{+S}\mathcal{F}\{1\}=^{\ +S}_{[y,z]}\mathcal{F}\{yz,y,z,1\}\\ P(x+y+z,y+z,z)=^{+S}\mathcal{F}\{1\}=^{\ +S}_{[x,y]}\mathcal{F}\{xy,x,y,1\}\\ P(x,x+y+z,x+z)=^{+S}\mathcal{F}\{1\}=^{\ +S}_{[y,z]}\mathcal{F}\{yz,y,z,1\}\\ P(x+y+z,y,y+z)=^{+S}\mathcal{F}\{1\}=^{\ +S}_{[x,z]}\mathcal{F}\{xz,x,z,1\}\\ P(x+y,y,x+y+z)=^{+S}\mathcal{F}\{1\}=^{\ +S}_{[x,z]}\mathcal{F}\{xz,x,z,1\}\\ P(x+z,x+y+z,z)=^{+S}\mathcal{F}\{1\}=^{\ +S}_{[x,y]}\mathcal{F}\{xy,x,y,1\} \end{cases} $$

откуда

$$ \begin{cases} P=^{\ +S}_{[y,z]}\mathcal{F}\{(y-x)(z-y),(y-x),(z-y),1\}=^{\ +S}_{[y,z]}\mathcal{F}\{(x-y)(y-z),1\}-^{\ +S}_{[y,z]}\mathcal{F}\{(x-y),(y-z)\}\\ P=^{\ +S}_{[x,y]}\mathcal{F}\{(x-y)(y-z),(x-y),(y-z),1\}=^{\ +S}_{[x,y]}\mathcal{F}\{(x-y)(y-z),1\}+^{\ +S}_{[x,y]}\mathcal{F}\{(x-y),(y-z)\}\\ P=^{\ +S}_{[y,z]}\mathcal{F}\{(y-z)(z-x),(y-z),(z-x),1\}=^{\ +S}_{[y,z]}\mathcal{F}\{(y-z)(z-x),1\}+^{\ +S}_{[y,z]}\mathcal{F}\{(y-z),(z-x)\}\\ P=^{\ +S}_{[x,z]}\mathcal{F}\{(x-z)(z-y),(x-z),(z-y),1\}=^{\ +S}_{[x,z]}\mathcal{F}\{(y-z)(z-x),1\}-^{\ +S}_{[x,z]}\mathcal{F}\{(y-z),(z-x)\}\\ P=^{\ +S}_{[x,z]}\mathcal{F}\{(x-y)(z-x),(x-y),(z-x),1\}=^{\ +S}_{[x,z]}\mathcal{F}\{(x-y)(z-x),1\}+^{\ +S}_{[x,z]}\mathcal{F}\{(x-y),(z-x)\}\\ P=^{\ +S}_{[x,y]}\mathcal{F}\{(x-z)(y-x),(x-z),(y-x),1\}=^{\ +S}_{[x,y]}\mathcal{F}\{(x-y)(z-x),1\}-^{\ +S}_{[x,y]}\mathcal{F}\{(x-y),(z-x)\} \end{cases} $$

далее, учитывая что:

1. $^{\ +S}_{[x,y]}\mathcal{F}\{\cdots\}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{\cdots\}$

2. $^{+S}\mathcal{F}\{xy,1\}\cdot^{+S}\mathcal{F}\{xy,1\}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{xy,1\}$

3. $^{+S}\mathcal{F}\{xy,1\}+^{+S}\mathcal{F}\{xy,1\}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{xy,1\}$

4. $^{+S}\mathcal{F}\{x,y\}\cdot^{+S}\mathcal{F}\{x,y\}\mathrel{|}\joinrel=^{+S}\mathcal{F}\{xy,1\}$

из первых двух равенств системы (перенеся 1-е слагаемое влево и перемножив) имеем:

$$P^2-P\cdot ^{+S}\mathcal{F}\{(x-y)(y-z),1\}+^{+S}\mathcal{F}\{(x-y)(y-z),1\}=-^{+S}\mathcal{F}\{(x-y)(y-z),1\}$$

отсюда:
$P=^{+S}\mathcal{F}\{(x-y)(y-z),1\}=^{+S}\mathcal{F}\{(x-y)(y-z)\}+^{+S}\mathcal{F}\{1\}$ или

$P-^{+S}\mathcal{F}\{1\}=^{+S}\mathcal{F}\{(x-y)(y-z)\}$ аналогично, из (3,4) и (5,6) равенств системы получаем
$P-^{+S}\mathcal{F}\{1\}=^{+S}\mathcal{F}\{(y-z)(z-x)\}$
$P-^{+S}\mathcal{F}\{1\}=^{+S}\mathcal{F}\{(z-x)(x-y)\}$

перемножив эти три равенства, получим:
$P^3-P^2\cdot^{+S}\mathcal{F}\{1\}+P\cdot^{+S}\mathcal{F}\{1\}-^{+S}\mathcal{F}\{1\}=^{+S}\mathcal{F}\{1\}$, откуда, окончательно:

$P=\frac{P^2\cdot^{+S}\mathcal{F}\{1\}+^{+S}\mathcal{F}\{1\}+^{+S}\mathcal{F}\{1\}}{P^2+^{+S}\mathcal{F}\{1\}}=^{+S}\mathcal{F}\{1\}=^{+S}P$

Ч.Т.Д.

Такое доказательство, очевидно, конструктивно. Так, для многочлена $P=x^2+y^2+z^2-xy-yz-zx$ построение дает:

$P=\frac{2P^2\left((x-y)^2+(y-z)^2+(z-x)^2\right)+(x-y)^2(y-z)^2(z-x)^2+\left((x-y)^2+(y-z)^2\right)\left((y-z)^2+(z-x)^2\right)\left((z-x)^2+(x-y)^2\right)}{P^2+3\left((x-y)^2(y-z)^2+(y-z)^2(z-x)^2+(z-x)^2(x-y)^2\right)+(x-y)^4+(y-z)^4+(z-x)^4}$

Далее приступим к решению 17-й проблемы Гильберта для одной переменной.

-- 19.08.2022, 11:16 --

Схема решения:
1. Показываем, что для построения формы $SOS$ достаточно уметь строить форму $SOS^+$ для многочленов, неотрицательных на $x\geq0$.
2. Показываем, что для построения формы $SOS^+$ достаточно уметь строить форму $^{+S}\mathcal{F}\{1-x,1\}$ для многочленов, неотрицательных на единичном отрезке $0\leq x\leq1$.
3. Разбиваем единичный отрезок на несколько отрезков таким образом, что построение формы $^S\mathcal{F}\{(b-x)(x-a),1\}$ на каждом из них тривиально ($a,b$ ─ концы выбранного отрезка).
4. "Склеиваем" получившиеся в 3. формы в форму $^{+S}\mathcal{F}\{1-x,1\}$, что завершает решение проблемы.

1. Итак, пусть мы умеем строить форму $SOS^+$ для любых многочленов, неотрицательных на $x\geq0$. Тогда, для многочлена $P(x)\geq0$ на $x \in \mathbb{R}$ имеем:

$\begin{cases} P(x)=^{+S}\mathcal{F}\{1\}=^S\mathcal{F}\{x,1\}=x\cdot^S\mathcal{F}\{1\}+^S\mathcal{F}\{1\}\\ P(-x)=^{+S}\mathcal{F}\{1\}=^S\mathcal{F}\{x,1\}=x\cdot^S\mathcal{F}\{1\}+^S\mathcal{F}\{1\} \end{cases}\Rightarrow$$\begin{cases} P-^S\mathcal{F}\{1\}=x\cdot^S\mathcal{F}\{1\}\\ P-^S\mathcal{F}\{1\}=-x\cdot^S\mathcal{F}\{1\} \end{cases}\Rightarrow$

$P^2-P\cdot^S\mathcal{F}\{1\}+^S\mathcal{F}\{1\}=-^S\mathcal{F}\{1\}\Rightarrow$

$P=\frac{P^2+^S\mathcal{F}\{1\}+^S\mathcal{F}\{1\}}{^S\mathcal{F}\{1\}}=^SP$

2. Пусть мы умеем строить форму $SOS^+$ для любых многочленов, неотрицательных на единичном отрезке $0\leq x\leq1$. Тогда, для многочлена $P(x)\geq0$ при $x\geq0$ имеем:

$\begin{cases} P(x)=^{+S}\mathcal{F}\{1-x,1\}=(1-x)\cdot^{+S}\mathcal{F}\{1\}+^{+S}\mathcal{F}\{1\}\\ x^{deg(P)}P\left(\frac1x\right)=^{+S}\mathcal{F}\{1-x,1\}=(1-x)\cdot^{+S}\mathcal{F}\{1\}+^{+S}\mathcal{F}\{1\} \end{cases}\Rightarrow$

$\Rightarrow\begin{cases} P=(1-x)\cdot^{+S}\mathcal{F}\{1\}+^{+S}\mathcal{F}\{1\}\\ P=-(1-x)\cdot^{+S}\mathcal{F}\{1\}+^{+S}\mathcal{F}\{1\} \end{cases}$

откуда, аналогично 1. получаем $P=^{+S}P$

3. Разбиение единичного отрезка для многочлена $P(x)\geq0$ на $0\leq x\leq1$.

Теорема 3.1
Пусть $0\leq a<b$, а многочлен $P(x)$ такой, что $P(a)\geq0$, $P(b)\geq0$, $P^{(k)}(a)P^{(k)}(b)\geq0$ для $k\in \mathbb{N}$. Тогда многочлен $(x+1)^{deg(P)}P\left(a+\frac{b-a}{1+x}\right)$ не имеет отрицательных коэффициентов.

Доказательство:
Покажем, что достаточно рассмотреть случай $a=0$, $b=1$.
Рассмотрим многочлен $P_0(x)=P\left(x(b-a)+a\right)$. Имеем:

$P_0(0)=P(a)\geq0$, $P_0(1)=P(b)\geq0$,

$P_0^{(k)}(0)P_0^{(k)}(1)=(b-a)^{2k}P^{(k)}(a)P^{(k)}(b)\geq0$ и т.о. многочлен $P_0(x)$ удовлетворяет условиям теоремы при $a=0$, $b=1$.

Но $(x+1)^{deg(P)}P\left(a+\frac{b-a}{1+x}\right)=(x+1)^{deg(P)}P_0\left(\frac{1}{1+x}\right)$.

Поэтому достаточно доказать, что $(x+1)^{deg(P)}P_0\left(\frac{1}{1+x}\right)$ не имеет отрицательных коэффициентов. Вот доказательство TOTAL, которое существенно короче моего.

Отметим на единичном отрезке концы этого отрезка $[0;1]$, действительные корни многочлена $P$ и всех его производных, которые попадают в этот отрезок (совпадающие точки рассматриваются как одна). Получим таким образом последовательность $0=a_0<a_1<...<a_n=1$. Очевидно, что в этой последовательности для любых соседних точек выполняются условия Теоремы 3.1, а значит $(x+1)^{deg(P)}P\left(a_k+\frac{a_{k+1}-a_k}{1+x}\right)=^{+S}\mathcal{F}\{1\}=^S\mathcal{F}\{x,1\}\Rightarrow$

$\Rightarrow P=^S\mathcal{F}\{(a_{k+1}-x)(x-a_k),1\}$

4. Склейка

Из 3. имеем систему по всем $0\leq k\leq n-1$

$P=^S\mathcal{F}\{(a_{k+1}-x)(x-a_k),1\}=(a_{k+1}-x)(x-a_k)\cdot ^S\mathcal{F}\{1\}+^S\mathcal{F}\{1\}\Rightarrow$

$\Rightarrow P-^S\mathcal{F}\{1\}=(a_{k+1}-x)(x-a_k)\cdot ^S\mathcal{F}\{1\}$

Перемножив все эти равенства получим:

$P^n+\sum\limits_{i=1}^n{^S\mathcal{F}\{1\}(-1)^iP^{n-i}}=(-1)^{n-1}x(1-x)\cdot^S\mathcal{F}\{1\}$

Если $n=2m$ то:
$P^{2m}+\sum\limits_{i=1}^{2m}{^S\mathcal{F}\{1\}(-1)^iP^{2m-i}}+x(1-x)\cdot^S\mathcal{F}\{1\}=0\Rightarrow$

$\Rightarrow P^{2m}+\sum\limits_{i=1}^m{^S\mathcal{F}\{1\}P^{2(m-i)}}+x(1-x)\cdot^S\mathcal{F}\{1\}=\sum\limits_{i=1}^m{^S\mathcal{F}\{1\}P^{2(m-i)+1}} \Rightarrow$

$P=\frac{P^{2m}+\sum\limits_{i=1}^m{^S\mathcal{F}\{1\}P^{2(m-i)}}+x(1-x)\cdot^S\mathcal{F}\{1\}}{\sum\limits_{i=1}^m{^S\mathcal{F}\{1\}P^{2(m-i)}}}=^S\mathcal{F}\{x(1-x),1\}=^{+S}\mathcal{F}\{1-x,1\}$

Если $n=2m+1$ то:
$P^{2m+1}+\sum\limits_{i=1}^{2m+1}{^S\mathcal{F}\{1\}(-1)^iP^{2m+1-i}}=x(1-x)\cdot^S\mathcal{F}\{1\}\Rightarrow$

$\Rightarrow P^{2m+1}+\sum\limits_{i=1}^m{^S\mathcal{F}\{1\}P^{2(m-i)+1}}=x(1-x)\cdot^S\mathcal{F}\{1\}+\sum\limits_{i=0}^m{^S\mathcal{F}\{1\}P^{2(m-i)}}\Rightarrow$

$\Rightarrow P=\frac{x(1-x)\cdot^S\mathcal{F}\{1\}+\sum\limits_{i=0}^m{^S\mathcal{F}\{1\}P^{2(m-i)}}}{P^{2m}+\sum\limits_{i=1}^m{^S\mathcal{F}\{1\}P^{2(m-i)}}}=^S\mathcal{F}\{x(1-x),1\}=^{+S}\mathcal{F}\{1-x,1\}$

что завершает построение формы $SOS^+$ на единичном отрезке, а значит и формы $SOS$ в целом. Отметим, что коэффициенты построенной таким образом формы выражаются рационально через коэффициенты заданного многочлена, его действительные корни и действительные корни его производных.

[Rak so dna]

Две и более переменных.

1. Сведение задачи получения формы $SOS$ к нахождению формы $SOS^+$.

Пусть $^+Q(x,y)\mathrel{|}\joinrel=^{+S}\mathcal{F}\{1\}$ ( любая неотрицательная на $x,y\geq0$ рациональная функция $Q(x,y)$ представима в форме $^{+S}\mathcal{F}\{1\}$ ). Тогда, если $P(x,y)$ ─ неотрицательный многочлен на $x,y \in \mathbb{R}$, то:

$\begin{cases} P(x,y)=^{+S}\mathcal{F}\{1\}=^{\quad S}_{[x,y]}\mathcal{F}\{xy,x,y,1\}=^S\mathcal{F}\{xy,x,y,1\}\\ P(x,-y)=^{+S}\mathcal{F}\{1\}=^{\quad S}_{[x,y]}\mathcal{F}\{xy,x,y,1\}=^S\mathcal{F}\{xy,x,y,1\}\\ P(-x,y)=^{+S}\mathcal{F}\{1\}=^{\quad S}_{[x,y]}\mathcal{F}\{xy,x,y,1\}=^S\mathcal{F}\{xy,x,y,1\}\\ P(-x,-y)=^{+S}\mathcal{F}\{1\}=^{\quad S}_{[x,y]}\mathcal{F}\{xy,x,y,1\}=^S\mathcal{F}\{xy,x,y,1\} \end{cases} \Rightarrow $

$ \Rightarrow \begin{cases} P=^S\mathcal{F}\{xy,x,y,1\}=y\cdot ^S\mathcal{F}\{x, 1\}+^S\mathcal{F}\{x, 1\}\\ P=^S\mathcal{F}\{-xy,x,-y,1\}=-y\cdot ^S\mathcal{F}\{x, 1\}+^S\mathcal{F}\{x, 1\}\\ P=^S\mathcal{F}\{-xy,-x,y,1\}=y\cdot ^S\mathcal{F}\{-x, 1\}+^S\mathcal{F}\{-x, 1\}\\ P=^S\mathcal{F}\{xy,-x,-y,1\}=-y\cdot ^S\mathcal{F}\{-x, 1\}+^S\mathcal{F}\{-x, 1\} \end{cases}$

Из первых двух равенств имеем:

$\left( P-^S\mathcal{F}\{x, 1\} \right)\left( P-^S\mathcal{F}\{x, 1\} \right)=-^S\mathcal{F}\{x, 1\} $, откуда

$P=^S\mathcal{F}\{x, 1\}$, аналогично, из вторых двух равенств:
$P=^S\mathcal{F}\{-x, 1\}$ и т.о. все свелось к п.1 решения проблемы для одной переменной.

Точно так же, в случае $n$ переменных можно свести задачу к $n-1$ переменной. Покажем это на примере четырех переменных:

Дан неотрицательный многочлен $P(x,y,z,t)$. Сведем задачу построения формы $SOS$ к задаче для трех переменных:
Аналогично решению для двух переменных, имеем систему из $2^4$ равенств:

$\begin{cases} P=^S\mathcal{F}\{xyzt,xyz,xyt,xzt,yzt,xy,xz,xt,yz,yt,zt,x,y,z,t,1\}\\ P=^S\mathcal{F}\{-xyzt,xyz,-xyt,-xzt,-yzt,xy,xz,-xt,yz,-yt,-zt,x,y,z,-t,1\}\\ \cdots\\ P=^S\mathcal{F}\{-xyzt,-xyz,xyt,xzt,yzt,xy,xz,-xt,yz,-yt,-zt,-x,-y,-z,t,1\}\\ P=^S\mathcal{F}\{xyzt,-xyz,-xyt,-xzt,-yzt,xy,xz,xt,yz,yt,zt,-x,-y,-z,-t,1\} \end{cases}$

в этой системе равенства разбиты по парам так, что если первое равенство пары содержит $(x,y,z,t)$, то второе равенство пары содержит $(x,y,z,-t)$ (очевидно, что такое разбиение всегда возможно, поскольку система содержит все возможные наборы $(\pm x,\pm y,\pm z,\pm t,)$ ). Теперь "исключаем" переменную $t$ из каждой пары равенств точно так же, как и в случае двух переменных. Так, для первой пары имеем:

$\begin{cases} P=t\cdot^S\mathcal{F}\{xyz,xy,xz,yz,x,y,z,1\}+^S\mathcal{F}\{xyz,xy,xz,yz,x,y,z,1\}\\ P=-t\cdot^S\mathcal{F}\{xyz,xy,xz,yz,x,y,z,1\}+^S\mathcal{F}\{xyz,xy,xz,yz,x,y,z,1\} \end{cases} \Rightarrow $

$\Rightarrow\left(P-^S\mathcal{F}\{xyz,xy,xz,yz,x,y,z,1\} \right)\left(P-^S\mathcal{F}\{xyz,xy,xz,yz,x,y,z,1\} \right)=-^S\mathcal{F}\{xyz,xy,xz,yz,x,y,z,1\}\Rightarrow$

$\Rightarrow P=^S\mathcal{F}\{xyz,xy,xz,yz,x,y,z,1\}$. Из остальных пар получим аналогичные представления при всех возможных наборах $(\pm x,\pm y,\pm z)$, что и будет условием задачи для трех переменных.

[Rak so dna]

2. Сведение задачи получения формы $SOS^+$ к нахождению формы в единичном гиперкубе.

Как и в п.1 разберем случай для двух переменных, после чего станут ясны и случаи большей размерности.
Итак, пусть мы умеем строить форму $^{+S}\mathcal{F}\{(1-x)(1-y), (1-x), (1-y), 1\}$ для любых многочленов, неотрицательных в квадрате $0\leq x,y\leq 1$. Тогда если $P(x,y)$ ─ многочлен, неотрицательный на $x,y\geq0$, то:

$\begin{cases} P(x,y)=^{+S}\mathcal{F}\{(1-x)(1-y), (1-x), (1-y), 1\}\\ P\left(x,\frac1y\right)=^{+S}\mathcal{F}\{(1-x)(1-y), (1-x), (1-y), 1\}\\ P\left(\frac1x,y\right)=^{+S}\mathcal{F}\{(1-x)(1-y), (1-x), (1-y), 1\}\\ P\left(\frac1x,\frac1y\right)=^{+S}\mathcal{F}\{(1-x)(1-y), (1-x), (1-y), 1\} \end{cases} \Rightarrow$

$\Rightarrow\begin{cases} P=^{+S}\mathcal{F}\{(1-x)(1-y), (1-x), (1-y), 1\}=(1-y)\cdot^{+S}\mathcal{F}\{(1-x), 1\}+^{+S}\mathcal{F}\{(1-x), 1\}\\ P=^{+S}\mathcal{F}\{-(1-x)(1-y), (1-x), -(1-y), 1\}=-(1-y)\cdot^{+S}\mathcal{F}\{(1-x), 1\}+^{+S}\mathcal{F}\{(1-x), 1\}\\ P=^{+S}\mathcal{F}\{-(1-x)(1-y), -(1-x), (1-y), 1\}=(1-y)\cdot^{+S}\mathcal{F}\{-(1-x), 1\}+^{+S}\mathcal{F}\{-(1-x), 1\}\\ P=^{+S}\mathcal{F}\{(1-x)(1-y), -(1-x), -(1-y), 1\}=-(1-y)\cdot^{+S}\mathcal{F}\{-(1-x), 1\}+^{+S}\mathcal{F}\{-(1-x), 1\} \end{cases}$

откуда, таким же образом как и в п.1 получаем сведение к п.2 задачи для одной переменной:

$\begin{cases} P=^{+S}\mathcal{F}\{(1-x), 1\}\\ P=^{+S}\mathcal{F}\{-(1-x), 1\} \end{cases}$

Случай для $n$ переменных полностью аналогичен п.1, с той лишь поправкой, что вместо наборов $(\pm x, \pm y, \pm z, ...)$ рассматриваются наборы $(\pm (1-x), \pm (1-y), \pm (1-z), ...)$.

(очепятка)

*В первом посте темы вместо:

Rak so dna в сообщении #1563118 писал(а):

2. Пусть мы умеем строить форму $SOS^+$ для любых многочленов, неотрицательных на единичном отрезке $0\leq x\leq1$.

нужно, конечно же:
"2. Пусть мы умеем строить форму $^{+S}\mathcal{F}\{(1-x), 1\}$ для любых многочленов, неотрицательных на единичном отрезке $0\leq x\leq1$."

Т.о. показано, что форму $SOS$ (а значит и сумму квадратов рациональных функций) для любых неотрицательных многочленов можно построить, рассматривая лишь единичные области многочленов (отрезок, квадрат, куб или гиперкуб).

[Rak so dna]

3. Теперь покажем, как построить форму $^{+S}\mathcal{F}\{(1-x)(1-y),1-x,1-y,1\}$ для неотрицательных на $0\leq x,y \leq 1$ многочленов на примере многочлена Моцкина $M(x,y)=x^2y^2\left(x^2+y^2-3\right)+1$
Итак, будем строить форму $SOS$ для многочлена $M(x,y)$. Как показано в п.1. достаточно построить формы $SOS^+$ для многочленов $M(x,y),M(-x,y),M(x,-y),M(-x,-y)$. Поскольку $M(x,y)=M(-x,y)=M(x,-y)=M(-x,-y)$ то достаточно построить форму $SOS^+$ лишь для $M(x,y)$. Для этого, как показано в п.2. достаточно построить формы $^{+S}\mathcal{F}\{(1-x)(1-y),1-x,1-y,1\}$ для многочленов $M(x,y),x^4M\left(\frac1x,y \right),y^4M\left(x,\frac1y \right),x^4y^4M\left(\frac1x,\frac1y \right)$:

3.1. Для многочлена $M(x,y)$ требуемая форма строится обратными подстановками непосредственно из рациональной функции $M\left(\frac{1}{1+x},\frac{1}{1+y}\right)$, поскольку она не имеет отрицательных коэффициентов:

$M\left(\frac{1}{1+x},\frac{1}{1+y}\right)=\frac{(x+1)^4y^4+4(x+1)^4y^3+(6x^4+24x^3+33x^2+18x+4)y^2+(4x^4+16x^3+18x^2+4x)y+x^2(x+2)^2}{(1+x)^4(1+y)^4} \Rightarrow$

$M(x,y)=$
$(1-x)(1-y)\left(y^3(16(1-x)^2x+4x^3)\right)+$
$+(1-x)\left((24(1-x)^2x+18x^3)y^2(1-y)^2+4(1-x)^2xy^4\right)+$
$+(1-y)\left(4y(1-y)^2+(4(1-x)^4+18(1-x)^2x^2)y^3\right)+$
$+\left((1-y)^4+(6(1-x)^4+33(1-x)^2x^2+4x^4)y^2(1-y)^2+((1-x)^4+4(1-x)^2x^2)y^4\right)$

3.2. Для многочлена $x^4y^4M\left(\frac1x,\frac1y \right)$ требуемая форма строится обратными подстановками непосредственно из многочлена $M(1+x,1+y)$, поскольку он не имеет отрицательных коэффициентов:

$M(x+1,y+1)=(x^2+2x+1)y^4+(4x^2+8x+4)y^3+(x^4+4x^3+9x^2+10x+4)y^2+(2x^4+8x^3+10x^2+4x)y+x^4+4x^3+4x^2 \Rightarrow$

$x^4y^4M\left(\frac1x,\frac1y \right)=$
$(1-x)(1-y)\left(xy(8(1-y)^2x^2+8(1-x)^2y^2+4x^2y^2)\right) +$
$+ (1-x)\left(x(2x^2(1-y)^4+y^2(4(1-x)^2+10x^2)(1-y)^2+4y^4(1-x)^2)\right) +$
$+ (1-y)\left(y((4(1-x)^2+4x^2)x^2(1-y)^2+2(1-x)^4y^2+10x^2y^2(1-x)^2)\right) +$
$+ \left(x^2((1-x)^2+x^2)(1-y)^4+y^2((1-x)^4+9x^2(1-x)^2+4x^4)(1-y)^2+y^4(1-x)^4+4x^2y^4(1-x)^2\right) $

3.3. Ввиду симметрии $M(x,y)=M(y,x)$, для многочленов $x^4M\left(\frac1x,y \right),y^4M\left(x,\frac1y \right)$ достаточно построить требуемую форму только для одного из них, пускай это будет $f(x,y)=y^4M\left(x,\frac1y \right)$. В отличие от 3.1 и 3.2 попытка получить многочлен с неотрицательными коэффициентами подстановкой $M\left(\frac{1}{1+x},1+y\right)$ не удастся. Поступим следующим образом: разрежем квадрат $(0\leq x,y \leq 1)$ на две области прямой $y=a=4/5$. Область $(0\leq x \leq 1; a\leq y \leq 1)$ разрежем на две области прямой $x=a=4/5$. Получим три области (Рис.1):
I - $(0\leq x \leq a; a\leq y \leq 1)$,
II - $(0\leq x \leq 1; 0\leq y \leq a)$,
III - $(a\leq x \leq 1; a\leq y \leq 1)$.
Дальнейшая идея в следующем: построить для каждой из областей некоторую свою форму $^{+S}\mathcal{F}$ и склеить все в требуемую форму.

3.3.1 Для I -й области имеем:

$f\left(\frac{a}{1+x}, a+\frac{1-a}{1+y}\right)=^{+S}\mathcal{F}\{1\} \Rightarrow$

$f=^{+S}\mathcal{F}\{(a-x)(1-y)(y-a),a-x,(1-y)(y-a),1\}$

3.3.2 Для II -й области имеем:

$f\left(\frac{1}{1+x}, \frac{a}{1+y}\right)=$

$=\frac{625(x+1)^2y^4+2500(x+1)^2y^3+50(51x^2+102x+59)y^2+100(x^2+2x+9)y+(256x^4+1024x^3+814x^2+3(7x-3)^2+54)}{625(1+x)^4(1+y)^4}=$

$=^{+S}\mathcal{F}\{1\} \Rightarrow$

$\Rightarrow f=^{+S}\mathcal{F}\{(1-x)(a-y),1-x,a-y,1\}$



3.3.3 Для III-й области будет продемонстрирована идея, дающая гарантированное построение формы. (в предыдущих случаях 3.3.1, 3.3.2 текущая идея не применялась, поскольку мне хотелось показать её для области, где непосредственные подстановки не сработают - а это, как и следовало ожидать от многочленов - окрестности корней как самого многочлена, так и его производных)
Итак, непосредственная подстановка для III-й области: $f\left(a+\frac{1-a}{1+x}, a+\frac{1-a}{1+y}\right)$ не срабатывает. Пусть $f_{\gamma}(x,y)=(y+\gamma)f(x,y)$. Для всех $k \in \mathbb{N}$ рассмотрим кривые $y_{k,\gamma}(x)$, заданные уравнениями $\left(f_{\gamma}\right)^{(k)}_y=0$ при $\gamma=0$ (Рис.1 синий цвет) и $\gamma=1$ (Рис.1 зеленый цвет). В III-область попали лишь кривые, заданные уравнениями с $k=1$. Проведем рациональную кривую $y=S(x)$ так, чтобы для $a\leq x \leq 1$ выполнялось $y_{1,0}(x) \leq S(x) \leq y_{1,1}(x)$. В данном случае достаточно $S(x)=1+\frac{1}{2}(x-1)-\frac{37}{32}(x-1)^2-\frac{315}{384}(x-1)^3$ (разложили $y_{1,0}(x),y_{1,1}(x)$ в ряд Тейлора в точке $x=1$ до 3-й производной и взяли среднее). Теперь, по Теореме 3.1 многочлен $(1+y)^5 f_1\left(x, a+\frac{S(x)-a}{1+y}\right)$ не имеет на $a\leq x \leq 1$ отрицательных коэффициентов. Это означает, что каждый его коэффициент может быть представлен формой $^{+S}\mathcal{F}\{(1-x)(x-a),1\}$, поэтому он сам (а следовательно и $f$) представляется формой $^{+S}\mathcal{F}\{(1-x)(x-a)(S(x)-y)(y-a),(1-x)(x-a),(S(x)-y)(y-a),1\}$. Точно так же, по Теореме 3.1, многочлен $(1+y)^5 f_0\left(x, S(x)+\frac{1-S(x)}{1+y}\right)$ не имеет на $a\leq x \leq 1$ отрицательных коэффициентов, поэтому он сам (а следовательно и $f$) представляется формой $^{+S}\mathcal{F}\{(1-x)(x-a)(1-y)(y-S(x)),(1-x)(x-a),(1-y)(y-S(x)),1\}$. Итак:

$\begin{cases} f=^{+S}\mathcal{F}\{(1-x)(x-a)(S(x)-y)(y-a),(1-x)(x-a),(S(x)-y)(y-a),1\}\\ f=^{+S}\mathcal{F}\{(1-x)(x-a)(1-y)(y-S(x)),(1-x)(x-a),(1-y)(y-S(x)),1\} \end{cases} \Rightarrow $

$\begin{cases} f=(S(x)-y)(y-a)\cdot ^{+S}\mathcal{F}\{(1-x)(x-a),1\}+^{+S}\mathcal{F}\{(1-x)(x-a),1\}\\ f=(1-y)(y-S(x))\cdot ^{+S}\mathcal{F}\{(1-x)(x-a),1\}+^{+S}\mathcal{F}\{(1-x)(x-a),1\} \end{cases} \Rightarrow $

$f=(1-y)(y-a)\cdot ^{+S}\mathcal{F}\{(1-x)(x-a),1\}+^{+S}\mathcal{F}\{(1-x)(x-a),1\}=$

$=^{+S}\mathcal{F}\{(1-x)(x-a)(1-y)(y-a),(1-x)(x-a),(1-y)(y-a),1\}$.

Т.о. для III-й области произведена склейка по рациональной кривой $y=S(x)$.

3.4 осталось склеить формы I- и III-области по прямой $x=a$ а затем получившуюся форму с формой II-области по прямой $y=a$.


В п.3.3.3 реализована следующая идея:
Рассматриваем многочлен двух переменных $f(x,y)$ как многочлен одной переменной $y$ с коэффициентами - многочленами от $x$. Тогда, если мы отметим на плоскости все линии $f^{(k)}_y=0$, то к любой области плоскости, не содержащей внутри себя этих линий или их частей (однако, и это важно, граница такой области может являться частью линий $f^{(k)}_y=0$), можно применить Теорему 3.1. Т.е. если кусок плоскости, ограниченный линиями $x=x_0, x=x_1, y=a(x), y=b(x)$, где $x_1>x_0$, а $b(x)\geq a(x)$ - рациональные функции, не содержит внутри своей границы частей линий $f^{(k)}_y=0$, то многочлен $P(y)=(1+y)^{deg(f_y)}f\left(x,a(x)+\frac{b(x)-a(x)}{1+y}\right)$ не имеет отрицательных коэффициентов на $x_0\leq x\leq x_1$.
Т.о. если удастся разрезать единичную область рациональными линиями на области, не содержащие линий нулей производных, то удастся и построить нужную форму для этой единичной области. Проблема в том, что в общем случае функции $y(x)$ заданные уравнениями $f^{(k)}_y=0$ не являются рациональными. Поэтому (как в примере), поступаем следующим образом:
- домножаем многочлен $f(x,y)$ на некоторый многочлен $^+g_{\gamma}(x,y)$, где $\gamma$ - неотрицательный параметр: $P_{\gamma}=^+g_{\gamma}(x,y)f(x,y)$
- путем "шевеления" параметра, добиваемся "шевеления" линий нулей производных $\left(P_{\gamma}\right)^{(k)}_y=0$ (на Рис.1 это синяя и зеленая линии, при значении параметра $0$ и $1$ соответственно)
- проводим между этими линиями некоторую рациональную линию (на Рис.1 это $y=S(x)$), которая разрежет нашу область на две (обозначим их по параметрам линий, в них содержащихся $\gamma_0,\gamma_1$).
- для области $\gamma_0$ применяем Теорему 3.1 к многочлену $P_{\gamma_1}$
- для области $\gamma_1$ применяем Теорему 3.1 к многочлену $P_{\gamma_0}$
- склеиваем получившиеся формы по рациональной линии.

(Оффтоп)

Думаю, стоит описать эту схему, примененную более чем к одной линии нулей производных, проходящих через корень многочлена, подробно в следующих сообщениях.

Данную процедуру (с некоторыми уточнениями, о которых позже) можно применять для любой достаточно малой окрестности любой точки единичного квадрата в том случае, если линии нулей производных не являются корнями многочлена, т.к. в этом случае "пошевелить" их путем "шевеления" параметра не получится. Однако для многочлена двух переменных это не проблема, т.к. если $P(x,y)\geq 0$ то $P=R^2\cdot Q$, где $Q$ - неотрицательный многочлен, обнуляемый лишь конечным числом точек. Ну а в окрестности каждой такой точки процедура применима для такого многочлена $Q$, а значит он представим формой $SOS$.

[Rak so dna]

Реализуем идею п.3.3.3 для нескольких линий, проходящих через корень.
Итак, пусть $P(x,y)$ - неотрицательный многочлен, с корнем $(x_1;y_1)$. Домножим его на некий неотрицательный многочлен, коэффициенты которого зависят от параметра $\gamma$, такой, что у полученного многочлена $f_{\gamma}(x,y)$ все корни всех производных $\left(f_{\gamma}\right)^{(k)}_y$, не являющиеся корнями многочлена $P$, зависят от $\gamma$. Иными словами, "шевеление" параметра $\gamma$ приведет к "шевелению" линий корней производных, заданных уравнениями $\left(f_{\gamma}\right)^{(k)}_y=0$. Пускай теперь через точку $(x_1;y_1)$ пройдут две линии, заданные уравнениями $\left(f_{\gamma}\right)'_y=0,\left(f_{\gamma}\right)''_y=0$. Пошевелим их параметрами $\gamma_1\ne \gamma_2$ и попарно "разрежем" линиями $y=S_i(x)$ ($S_i$ - рациональные функции) в достаточно малой окрестности точки $(x_1;y_1)$ (Рис.2).

Теперь, выбрав произвольное направление обхода (например, против часовой), начнем склейку:
1 - область между линиями $x=x_1,y=y_2,y=S_3(x)$
2 - область между линиями $x=x_0,y=S_3(x),y=S_4(x)$
3 - область между линиями $x=x_0,y=y_1,y=S_4(x)$
По Теореме 3.1 для 1, 2, 3 областей соответственно имеем:

$f_{\gamma_1}\left(x, S_3(x)+\frac{y_2-S_3(x)}{1+y}\right)=^{+S}\mathcal{F}\{(x_1-x)(x-x_0),1\}$

$f_{\gamma_1}\left(x, S_4(x)+\frac{S_3(x)-S_4(x)}{1+y}\right)=^{+S}\mathcal{F}\{(x_1-x)(x-x_0),1\}$

$f_{\gamma_2}\left(x, y_1+\frac{S_4(x)-y_1}{1+y}\right)=^{+S}\mathcal{F}\{(x_1-x)(x-x_0),1\}$

что, методами описанными выше, склеивается в форму:

$P=^{+S}\mathcal{F}\{(x_1-x)(x-x_0)(y_2-y)(y-y_1),(x_1-x)(x-x_0),(y_2-y)(y-y_1),1\}$

Таким же образом можно обойти точку $(x_1;y_1)$ полностью, причем совершенно ясно, что склейку можно провести для любого числа линий.

Теперь укажем достаточное условие для возможности "разрезания". Иными словами:
Пусть алгебраические линии $f(x,y)=0,g(x,y)=0$ пересекаются в точке $(x_1;y_1)$. Функции $y_f(x),y_g(x)$ задаются этими уравнениями в окрестности этой точки, для определенности будем считать $y_f(x)\leq y_g(x)$, при $x\leq x_1$, тогда при каких условиях существует рациональная функция $S(x)$, такая, что в окрестности точки $x_1$ выполняется $y_f(x)\leq S(x) \leq y_g(x)$, при $x\leq x_1$, причем равенство достигается только при $x=x_1$ ?
Требования аналитичности в точке $x_1$ функций $y_f(x),y_g(x)$ должно быть достаточно, т.к. в этом случае каждую из них можно заменить соответствующим рядом Тейлора в точке $x_1$. Тогда ряд, равный среднему арифметическому этих рядов, пройдет между линиями $f(x,y)=0,g(x,y)=0$ (в окрестности точки $(x_1;y_1)$), и можно взять в качестве $S(x)$ достаточно большое количество первых его членов.

Т.о., с некоторыми натяжками на строгость, удалось показать следующее:

Пусть $P(x,y)$ - неотрицательный многочлен, обнуляемый лишь конечным числом точек, такой, что если функция $y_k(x)$, заданная уравнением $P^{(k)}_y=0, k \in \mathbb{N}$, проходит через какую-то из этих точек, то она в ней аналитична. Тогда $P$ можно представить в виде суммы квадратов рациональных функций с действительными коэффициентами.

[Pphantom]

Rak so dna, дождитесь, пожалуйста, чей-нибудь реакции, не надо превращать тему в собственный блог.