所有的代數不等式都可以配方證明么?

01-01

是否所有的代數不等式都可以寫成若干項平方的形式? 配方的結果是唯一的么?

任何正的實係數齊次多項式 $F$ 都可表示為 $F=sum_i R_i^2$ , 其中 $R_i$ 是實有理函數[1][2].

注意 $R_i$ 不一定是多項式. 可以被表示為有理式的平方和但不能被表示為多項式的平方和的一個例子是:

$egin{align} x^4y^2+x^2y^4+z^6-3x^2y^2z^2\ =frac{(x^2yz-yz^3)^2+(xy^2z-xz^3)^2+(x^2y^2-z^4)^2+frac{1}{4}(xy^3-x^3y)^2+frac{3}{4}(xy^3+x^3y-2xyz^2)^2}{x^2+y^2+z^2} end{align}$

(又因為 $frac{w^2}{x^2+y^2+z^2}=(frac{xw}{x^2+y^2+z^2})^2+(frac{yw}{x^2+y^2+z^2})^2+(frac{zw}{x^2+y^2+z^2})^2$ , 於是上式可以改寫為分式的平方和.)

配方並不是唯一的. 例如:

$2x^2+5y^2-6xy=(x-y)^2+(x-2y)^2=(sqrt{2}x-frac{3y}{sqrt{2}})^2+frac{y^2}{2}$

不過這個不等式太弱了, 那些更強的不等式也可以花式配方么? 答案是可以的, 例如(Vasile不等式):

$egin{align}(x^2+y^2+z^2)^2-3sum_{cyc} x^3y\ =frac{1}{2}sum_{cyc} (x^2-z^2-2xy+yz+zx)^2\ =frac{1}{6}sum_{cyc} (x^2+y^2-2z^2-3xy+3zx)^2\ =frac{1}{14}sum_{cyc} (x^2+2y^2-3z^2-4xy-yz+5zx)^2\ end{align}$

[1] Hardy, G. H.; Littlewood, J. E.; Pólya, G.; Polya, G.; P, G. Inequalities, Second edition; 2nd ed.; Cambridge University Press: Cambridge, 1952.

[2] Artin, E. über die Zerlegung definiter Funktionen in Quadrate. Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg1927, 5, 100–115.

@藥丸千歲已經回答得很具體了，我想扯遠點，講一講sos和理論計算機的關係。首先，實係數多項式若在實數上只取非負值叫做非負多項式，sum of square簡寫為sos。希爾伯特證明了除開二元二次和三元四次多項式以外，其他變元和次數組合都有非sos的多項式。然後希爾伯特問了17問題：是不是非負多項式都能表示成實有理函數的平方和？Emil Artin給出了肯定答案。

到這裡理論問題已經比較清楚了，但演算法問題還完全沒碰。列幾個結果：

多項式SOS判定是個半定規劃，不過變數個數隨次數指數增長
17問題可以用Charles Delzell的方法構造解決，但我推測會需要指數多個有理函數，因為：
四次多項式判斷是否非負是NP-hard

從這裡我們就從實代數幾何到了理論計算機的範疇：一般地，許多（事實上我認為可以是所有）組合優化問題可以化為半代數集（有限個代數不等式定義的集合）是否有整點的問題，然而這是個不可判定問題……

放鬆一下限制，現在只問半代數集是否非空。我們不禁想起代數集是否非空這個子問題，關於這個問題在代數閉域的情形我們有希爾伯特零點定理Nullstellensatz. 令人驚異的是，半代數集也有一個相似的定理，叫(Stengle"s)positivstellensatz。這個定理有很多版本，Stengle這個最一般。

定理(Positivstellensatz)[Stengle (1974)]

$K:={xinmathbb{R}^nmid g_i(x)geqslant0,i=1,ldots,m,h_i(x)=0,i=1,ldots,k}$
是空集當且僅當
存在多項式 $t_1, ldots, t_k$ 以及sos多項式 $s_0,s_1,ldots,s_m$ , $s_{12},s_{13},ldots,s_{m-1,m}$ , $s_{123},ldots,s_{m-2,m-1,m}$ , … , $s_{12ldots m}$ 使得 $-1 = sum_{i=1}^k t_i(x)h_i(x) + s_0(x)+sum_{{i}}s_i(x)g_i(x)+sum_{{i,j}}s_{ij}(x)g_i(x)g_j(x)+cdots+s_{12ldots m}g_1(x)g_2(x)cdots g_m(x)$

這個定理沒告訴你這堆t和s都是多少次的（有上界但是指數增長，沒啥用），所以就有一個所謂hierarchy：逐漸提高這些未知多項式的次數，去解半定規劃。一般在應用上很低的次數就夠了。

現在有了這個NB定理，半代數集是否非空的問題可以解答了。怎麼從實數解過渡到整數解呢？這就不得不需要一些組合優化里到處都是的舍入（rounding）技巧了，畢竟要是有通用技巧，半代數集整點判定也不會是undecidable了。

其實沒有能夠答完整，因為我已經黔驢技窮了……有興趣的同學請看博客[1]（本文主要參考文獻），以及幾位大牛的專著[2]。一直對這個topic很感興趣，但因為懶癌無葯醫，一直沒仔細看。如果有人有相關research經驗請務必點評一下！

Guest post by Amir Ali Ahmadi: Sum of Squares (SOS) Techniques: An Introduction, Part II/II
Semidefinite Optimization and Convex Algebraic Geometry

樓上幾位已經說得很清楚了。

如果需要實例，可以看看《命題人講座——代數不等式》，你會知道什麼是真正的暴力配方。

Artin定理，一個非常優雅的證明