1

③EX 相加相乗の理、その先へ

9
0
$$$$

③EX 相加相乗平均の発見可能性を探る ― 証明形式・アルゴリズム・限界

はじめに

ごきげんよう、みなさま。
ネスビットの不等式
$$\begin{gathered}\frac a{b+c}+\frac b{c+a}+\frac c{a+b}\geq\frac32,\\a,b,c>0.\end{gathered}$$
には、相加相乗平均を使った証明があります。分母を別の文字で置き、逆数同士を組にすれば、確かに証明できます。
ただ、証明を読んで納得した後にも、一つ疑問が残ります。どうして、その変形を思いつけるのでしょうか。
そこで、相加相乗平均を適用する項を、式にある情報から作れないかと考えてみました。分母を取り出す、指数を比較する、係数を配分する。こうした操作で候補を作れるなら、「うまく気付く」部分を少しずつ計算に置き換えられそうです。
もっとも、ネスビットの不等式で説明できたとしても、ほかの不等式にも使えるとは限りません。考えていくうちに、今度は「そもそも相加相乗平均は、どこまで使えるのか」が気になってきました。使う項を構成できるだけでなく、ある形式では証明できないことまで判定できるでしょうか。置換や補助項を許したら、その答えは変わるのでしょうか。
① AM-GM FLASH では式の外見と初動を、 ② 相加相乗平均の入試問題集 では問題への応用を扱いました。③「相加相乗を嗜むために ― 作法と理」は、候補を作り、選び、失敗したら考え直す具体的な手順を扱う記事です。本記事では、その背景を数学的に調べます。③を読んでいなくても追えるよう、必要な定義から始めます。
途中から線形代数や凸性も使いますが、まずは具体的な式から見ていきましょう。定理の主張は表示し、長い証明は折りたたみにしています。記号 $x=1$ は、複数の変数がある場合には全ての成分が1である点を表します。相加相乗平均は、以下AM-GMとも書きます。
先に位置づけも述べておきます。指数の凸結合、凸順序、SAGE、SONCなどは既存の数学です。本記事では、それらとの関係を確認しながら、等号点を固定した証明の判定や具体的な多項式の分類を導きます。ここで証明した命題を、数学界で初めて得られた定理だと主張するものではありません。
なお、本記事は公開後も内容を見直し、必要に応じて加筆・修正を行う予定です。

目次

R01 ネスビットから、分数形の構造へ

最初に、導入で触れた証明を実際に作ってみます。分母を別の文字に置くだけでなく、分子もその分母で表すと、使う項が計算から決まります。

分母から三つの逆数対を作る

$a,b,c>0$ とし、
$$F=\frac a{b+c}+\frac b{c+a}+\frac c{a+b}-\frac32$$
とおきます。$X=b+c,Y=c+a,Z=a+b$ とおきます。例えば $a=rX+sY+tZ$ の係数を比較すると $s+t=1,r+t=0,r+s=0$ なので、$2a=Y+Z-X$ です。他の分子も同じように表すと
$$\begin{gathered} F=\frac12\{(X+Y+Z)E-9\},\\ E=\frac1X+\frac1Y+\frac1Z,\\ F=\frac12\left\{\begin{gathered}\frac{(X-Y)^2}{XY}+\frac{(Y-Z)^2}{YZ}\\+\frac{(Z-X)^2}{ZX}\end{gathered}\right\}. \end{gathered}$$
第1の等式は $2a=Y+Z-X$ を各項へ代入すれば得られます。第2の等式は、和と逆数和を展開し、$\dfrac XY+\dfrac YX-2=\dfrac{(X-Y)^2}{XY}$ を使います。
元の変数で通分すると
$$F=\frac{N}{2(a+b)(b+c)(c+a)},$$
$$\begin{gathered} N=(a+b)(a-b)^2\\+(b+c)(b-c)^2\\ +(c+a)(c-a)^2=2U-V,\\ U=a^3+b^3+c^3,\\ V=a^2b+ab^2+b^2c\\+bc^2+c^2a+ca^2. \end{gathered}$$
正の3項 $a^3,a^3,b^3$ にAM-GMを使うと $2a^3+b^3\geq3a^2b$。文字を入れ替えた6式を足すと $6U\geq3V$、すなわち $2U-V\geq0$ です。従って分母を残した逆数対の証明と、通分後の単項式を組み合わせる証明の両方が可能です。後者を次節で「直接型」と定義します。いずれも等号は $a=b=c$。
$p=a+b+c$、$q=ab+bc+ca$、$r=abc$ とすれば $N=2p^3-7pq+9r$ です。ただし、この表示は文字を減らす一方、正の項の組を見えにくくすることもあります。式を短くする操作が、そのまま証明発見を容易にするとは限りません。

一次分母の共通構造

以下は本記事で検証する一般恒等式です。$n\geq2$、$a_i>0$、$B>0$、$A+B\geq0$ とし、
$$\begin{gathered}S=\sum_{i=1}^{n}a_i,\\D_i=BS+Aa_i,\quad K=A+nB.\end{gathered}$$
とおきます。この条件では $K>0$ かつ $D_i>0$ です。実際、$A<0$ の場合も $D_i=(A+B)a_i+B(S-a_i)>0$。
$$\boxed{\begin{gathered} \sum_{i=1}^{n}\frac{a_i}{D_i}-\frac nK\\ =-\frac{AB}{K}\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{(a_i-a_j)^2}{D_iD_j}. \end{gathered}}$$

証明


$A\ne0$ とします。$\displaystyle \sum_{i=1}^{n}D_i=KS$ と、$a_i=\dfrac{D_i-BS}{A}$ から
$$\begin{gathered}\sum_{i=1}^{n}\frac{a_i}{D_i}-\frac nK\\ =-\frac B{AK}\left\{KS\sum_{i=1}^{n}\frac1{D_i}-n^2\right\}.\end{gathered}$$
また任意の正の $D_i$ に対し、括弧内は
$$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{(D_i-D_j)^2}{D_iD_j}.$$
$D_i-D_j=A(a_i-a_j)$ を代入すれば得られます。$A=0$ では左右とも0です。


従って $A<0$ では $\dfrac nK$ が最小値、$A>0$ では最大値であり、$A\ne0$ の等号条件は全ての $a_i$ の一致です。$A=0$ では恒等的に $\dfrac1B$ です。非零の $A$ の等号点は、正の任意の同じ値を全ての $a_i$ に入れれば実現します。
他方の端も区別できます。$A+B>0$ なら、$A>0$ のとき下限、$-B< A<0$ のとき上限は $\dfrac1{A+B}$。正の範囲ではその端を取りません。$\dfrac{a_1}{S}\to1$ とすれば近づきます。$A=-B$ の場合は上に有界ではありません。
実際、$D_i-(A+B)S=A(a_i-S)$ で、$0< a_i< S$ です。この符号に従って $\dfrac{a_i}{D_i}$ と $\dfrac{a_i}{(A+B)S}$ を比較すれば、反対側の評価は厳密な不等号で得られます。$A=-B$ では $a_1/S\to1$ により第1項が無限大になります。定数の評価と、端が実際に取れるかの確認を混同しないことが必要です。

平方分子の恒等式

$q_i>0$、$p_i$ は実数とし、$\displaystyle P=\sum_{i=1}^{n}p_i$、$\displaystyle Q=\sum_{i=1}^{n}q_i$ とおきます。
$$\boxed{\begin{gathered} \sum_{i=1}^{n}\frac{p_i^2}{q_i}-\frac{P^2}{Q}\\ =\sum_{i=1}^{n}\frac{(p_i-\frac{Pq_i}{Q})^2}{q_i}\geq0. \end{gathered}}$$
展開して $\displaystyle\sum_{i=1}^{n}q_i=Q,\quad\sum_{i=1}^{n}p_i=P$ を使えば恒等式が確かめられます。等号は全ての $\dfrac{p_i}{q_i}=\dfrac PQ$。これはコーシー・シュワルツの不等式の分数形で、Engelの形、ティトゥの補題とも呼ばれる標準形です。ここで新しい不等式として導入するものではありません。
$p_i>0$ なら、各組 $i< j$ に2項のAM-GMを用いて
$$\frac{p_i^2q_j}{q_i}+\frac{p_j^2q_i}{q_j}-2p_ip_j\geq0$$
を足しても証明できます。$p_i$ が負の場合までこの正の2項の説明をそのまま使う必要はなく、平方の恒等式またはコーシー・シュワルツの不等式を使います。
平方分子を見たときには、$p_i,q_i$ の和を計算すれば、この下界を候補にできます。例えば $a,b,c>0$ のとき、
$$\begin{gathered} \frac{a^2}{b+c}+\frac{b^2}{c+a}\\+\frac{c^2}{a+b}\geq\frac{a+b+c}{2},\\ \frac{(a+b)^2}{a+2b}+\frac{(b+c)^2}{b+2c}\\+\frac{(c+a)^2}{c+2a}\geq\frac43(a+b+c) \end{gathered}$$
を同じ規則で復元できます。いずれも正の範囲の等号は $a=b=c$ です。

R02 何をAM-GMの証明と呼ぶか

同じネスビットの不等式に二通りの証明がありました。ここで「AM-GMで証明できる」の意味を決めておかないと、見つからなかったときに何が分かるのかも曖昧になります。
全変数を正とし、変数の個数 $n$ は正の整数とします。$x=(x_1,\ldots,x_n)$、実数の指数ベクトル $\alpha=(\alpha_1,\ldots,\alpha_n)$ に対し
$$x^\alpha=\prod_{h=1}^{n}x_h^{\alpha_h}$$
と書きます。負の指数も許すときは、正の範囲での一般化された単項式です。有限個のこのような単項式の実係数一次結合を対象にします。重複する指数は係数を足してまとめ、係数0の項は除きます。実際に残った指数の集合を、その式の支持と呼びます。
重み付きAM-GMは、正の $A_i$ と $w_i>0$、$\sum_{i=1}^{m}w_i=1$ に対し
$$\sum_{i=1}^{m}w_iA_i\geq\prod_{i=1}^{m}A_i^{w_i}$$
と述べ、等号は全ての $A_i$ が等しいときに成立します。以下の基本形は $A_i=x^{\alpha_i}$ への適用です。
使う基本形。 正の定数 $K$、重み $w_i>0$、$\displaystyle \sum_{i=1}^{m}w_i=1$、指数 $\alpha_i$ に対する
$$\begin{gathered}K\left\{\sum_{i=1}^{m}w_ix^{\alpha_i}-x^\beta\right\},\\ \beta=\sum_{i=1}^{m}w_i\alpha_i.\end{gathered}$$
という非負な式を本記事では一つのAM-GM差と呼びます。直接型AM-GM証明は、この差を有限個足して目的式と恒等的に一致させる証明です。零の式は空和でも表せるものとします。重み0の項は除きます。各AM-GM差は $x=(1,\ldots,1)$ で0になります。従って直接型の和で表せる式も $P(1)=0$ です。この等号点の指定が、後の判定を一次条件へ変える鍵になります。
一般の係数を持つ単項式へAM-GMを用いた差であっても、その有限非負和が $x=1$ で0なら、各差もそこで0です。従って、それぞれの適用する量の係数は等号条件によってそろい、上の形式になります。正の等号点 $x=r$ を指定する場合は $x_h=r_hz_h$ として $z=1$ に移します。
このクラスでは、正の係数を持つ単項式をAM-GM差に掛ける操作も許されています。指数を同じだけ平行移動すれば、同じ形式になるためです。また、補助単項式を有限個導入し、足した際に相殺することも許します。この許可によって判定範囲が増えるかはR05で証明します。
一方、$X=a^2+bc$ のような新しい正の量への置換や、既に得た非負式同士の乗算は、上の定義には含めません。例えば $(x-1)^4\geq0$ は二乗の非負性として簡単ですが、直接型ではありません。証明操作を増やすと、証明できる式の集合も変わります。
本記事で扱う証明形式の関係は、次のようになります。

  • 直接型:定数の非負係数で、単項式のAM-GM差を有限加算する。
  • 置換を許す型:正値を確認した多項式・分母などを一つの量として使う。
  • 非負式の再利用を許す型:証明済みの非負式の乗算や、平方の恒等式を使う。
  • 一般的な非負性の証明:平方和、定義域の条件、実代数幾何学なども使う。
    これは全てが一本の厳密な包含列になるという主張ではありません。特に多項式平方和と単項式AM-GM和は、互いを含みません。各結果には、対象となる形式を明記します。
    補足――実数の指数でも係数を比較できる理由
    相異なる有限個の指数 $\alpha_i$ に対する関数 $x^{\alpha_i}$ は、正の領域上で一次独立です。実際、$x_h=e^{y_h}$ と置き、全ての $(\alpha_i-\alpha_j)\cdot h$ が0でない方向 $h$ を選べます。避けるべき超平面は有限個だからです。$y=th$ 上で恒等式を制限すると、相異なる実数 $b_i=\alpha_i\cdot h$ を持つ指数関数 $e^{b_it}$ の一次結合になります。
    $t=0$ で0回から項数−1回まで微分すると、Vandermonde行列の連立方程式になります。その行列式は相異なる $b_i$ の差の積なので0でなく、係数は全て0です。従って、以下の恒等式で同じ指数の係数を比較する操作は、実数指数でも正当です。

R03 指数から最良係数を求める

まずは、右辺の単項式が一つだけの場合を考えます。指数を合わせる重みを求めた後、係数まで最良にできるでしょうか。
重み付きAM-GMの積の指数は、元の指数の加重平均になります。従って目標の指数が、使用する指数の凸結合にならなければ、その1回の適用からは目標を作れません。「凸結合」は、非負の重みの和を1にした平均のことです。与えられた点の全ての凸結合の集合を、その点の凸包と呼びます。
この関係は、正の変数の単項式を掛けることによる指数の平行移動や、係数1の単項式による変数置換の線形写像で保たれます。正の定数も含む置換なら、その定数は別に係数へ吸収します。ただし、元の変数へ戻せない置換では、証明形式の存在・不存在まで逆向きに保存されるとは限りません。

負の単項式が一つの場合の正確な定理

$m\geq1$、$c_i>0$、$\alpha_i,\beta\in\mathbb R^n$ とし、
$$G(x)=\sum_{i=1}^{m}c_ix^{\alpha_i}$$
とおきます。また、$W$ を、$w_i\geq0$ と次の条件を満たす重みの集合とします。
$$\begin{gathered}\sum_{i=1}^{m}w_i=1,\\\sum_{i=1}^{m}w_i\alpha_i=\beta.\end{gathered}$$
$w_i=0$ の因子は省き、
$$\Theta(w)=\prod_{i=1}^{l}\left(\frac{c_i}{w_i}\right)^{w_i}$$
を定義します。ここだけは、正の重みを持つ $l$ 個の項を $i=1,\ldots,l$ と並べ直して積に入れています。従って0で割ることも $0^0$ を用いることもありません。
命題。 $\beta$ が $\alpha_i$ の凸包に入るとき、
$$\inf_{x_1,\ldots,x_n>0}\frac{G(x)}{x^\beta} =\max_{w\in W}\Theta(w).$$
従って $G(x)\geq d x^\beta$ が全ての正の $x$ で成り立つ必要十分条件は、$d\leq\max\Theta(w)$ です。$\beta$ が凸包の外なら、この下限は0であり、正の $d$ は取れません。
上の下限が正の有限点で達成される必要十分条件は、$\beta$ が全ての $\alpha_i$ の凸包の相対内部にあることです。相対内部とは、その凸包が含まれる最小のアフィン空間の中での内部です。相対境界にある場合、最良係数は下限として得られますが、有限の正の点では達成されません。

証明――重み付きAM-GMと対数座標


任意の $w\in W$ について、正の重みの項にAM-GMを使うと $G(x)\geq\Theta(w)x^\beta$。重み0の項は左辺に非負の余りとして残ります。


$x_h=e^{y_h}$ として $\displaystyle h(y)=\sum_{i=1}^{m} c_i e^{(\alpha_i-\beta)\cdot y}$ とおきます。ここで $\displaystyle \alpha\cdot y=\sum_{h=1}^{n}\alpha_h y_h$ です。まず $\beta$ が凸包の相対内部にある場合を考えます。指数差が張る線形空間を $L$ とします。$L$ の単位方向のどれについても、ある指数差との内積が正になります。コンパクト性から、その最大内積には単位方向によらない正の下界があり、$h$ は $L$ 上で無限遠に向かうと無限大になります。従って $L$ 上で最小点 $y_0$ を持ちます。$L$ が0次元の場合も定数なので成立します。


最小値を $k_0$ とし、$w_i=\dfrac{c_i e^{(\alpha_i-\beta)\cdot y_0}}{k_0}$ とおきます。和は1で、微分が0であることから指数の加重平均は $\beta$。従って $w\in W$ です。また
$$\begin{gathered}\log\Theta(w)\\=\sum_{i=1}^{m}w_i\{\log k_0-(\alpha_i-\beta)\cdot y_0\}\\=\log k_0.\end{gathered}$$
よってAM-GMの下界が最小値と一致します。


$\beta$ が境界にある場合は、$\beta$ を含む最小の面にある指数に制限します。その面の相対内部では先ほどの議論を使えます。また、$\beta$ の凸結合に面の外の点を正の重みで入れることはできません。面を支える線形関数の値を平均すれば、その値が厳密にずれてしまうためです。従って $W$ の全要素はこの面上に支持を持ちます。指数差 $\alpha_i-\beta$ に対し、面上で内積0、面の外で正となるベクトルを選びます。有限個の点の凸包の各面は、支える超平面との交わりで表せるためです。その反対方向へ $y$ を動かすと、面の外の指数項だけが0へ近づくので、全体の下限は面上の問題の最小値に一致します。全ての係数が正であるため、面外の項があると有限点で等号にはなりません。


凸包の外では、分離超平面により全ての $(\alpha_i-\beta)\cdot h>0$ となる $h$ が取れ、$y=-th$、$t\to\infty$ で $h(y)\to0$。最後に、$W$ はコンパクトで、$w\log w\to0$ とすれば $\log\Theta$ は連続なので最大値を持ちます。以上で全ての場合が示されます。


この定理は、AM-GMと幾何計画・相対エントロピーの双対性に対応する既知の枠組みです。ここでは、境界での不達成まで含め、探索に必要な形で述べ直しました。全ての重みを一つに決めただけでは、一般には最良係数とは限りません。指数がアフィン独立で、目標がその凸包にあるなら、重みは一意なのでその計算だけで決まります。アフィン独立とは、ある点を基準にした他の点への差ベクトルが一次独立であることです。
例えば $a^6+b^2+1\geq k a^2b$ では、指数から重みが $\dfrac13,\dfrac12,\dfrac16$ に決まり、
$$k_{\max}=2^{\frac23}\sqrt3.$$
等号は $a^6=2,b^2=3$、すなわち $a=2^{\frac16},b=\sqrt3$。一方 $1+x\geq1$ の最良係数1は、指数0が凸包 $[0,1]$ の端なので、$x>0$ では等号を取りません。
重みを持たない項・重複指数・等号条件
$\beta$ が相対内部にある場合、最小点で得た重みは全て正です。その点でのAM-GMの等号条件は
$$\frac{c_ix^{\alpha_i}}{w_i} =\frac{c_jx^{\alpha_j}}{w_j}\quad(1\leq i,j\leq m).$$
境界の場合、面の外の項は正の余りとなるので、有限点で等号は成立しません。全指数が同じ点なら凸包の相対内部はその一点であり、最良係数は $\sum_{i=1}^{m}c_i$、全ての正の点で達成されます。重複指数があっても定理は成り立ちますが、先に係数をまとめれば小さい問題になります。
係数0の項を許したいときは、まずその項を除き、残った指数の凸包で判定します。係数0の指数まで凸包の材料に加えるのは誤りです。

重みを少ない項に限れば、係数の最適化も済むわけではありません。例えば
$$1+x+x^2\geq kx\qquad(x>0)$$
では、指数1を作る重みの端の候補は $(0,1,0)$ と $(\frac12,0,\frac12)$ で、与える係数は1と2です。しかし重み $(\frac13,\frac13,\frac13)$ は係数3を与え、$x=1$ で達成します。有限候補への分解と最良係数の最大化は、目的が異なります。この点はR06でも使います。

R04 係数の割当てによる必要十分条件

右辺の項が複数なら、各項へ何を使うかを別々に決めるだけでは足りません。同じ正の項を二度使わないように、全ての係数を一緒に割り当てます。
同じ指数を全てまとめ、零係数を除いた非零の式を
$$\begin{gathered}P(x)=\sum_{i=1}^{m}c_ix^{\alpha_i}-\sum_{j=1}^{k}d_jx^{\beta_j},\\c_i,d_j>0.\end{gathered}$$
とします。$P(1)=0$、すなわち $\displaystyle\sum_{i=1}^{m}c_i=\sum_{j=1}^{k}d_j$ を仮定します。この場合は $m,k\geq1$ です。$P=0$ は別に空和で処理します。
定理。 R02の直接型AM-GM証明が存在する必要十分条件は、次の有限個の一次条件を満たす $t_{ij}\geq0$ が存在することです。
$$\boxed{\begin{gathered} \sum_{j=1}^{k}t_{ij}=c_i\quad(1\leq i\leq m),\\ \sum_{i=1}^{m}t_{ij}=d_j\quad(1\leq j\leq k),\\ \sum_{i=1}^{m}t_{ij}\alpha_i=d_j\beta_j\quad(1\leq j\leq k). \end{gathered}}$$
この定理は、有限支持の凸順序・マルチンゲール輸送をAM-GM証明へ適用したものです。証明では有限次元の分離だけを使います。補助単項式の相殺まで許した必要性は次節で示します。

十分性――割当てから証明を作る


固定した $j$ について、正の $t_{ij}$ だけを残します。重み $\dfrac{t_{ij}}{d_j}$ の和は1で、指数の平均は $\beta_j$。従って
$$\sum_{i=1}^{m}t_{ij}x^{\alpha_i}\geq d_jx^{\beta_j}.$$
全ての $j$ について足し、行和の条件を使うと $P(x)\geq0$。各負の単項式へどの正の項を何量使うかが、そのまま証明になります。


$t_{ij}$ は係数の配分量です。必要な変数の個数は $mk$、一次等式の本数は高々 $m+k(n+1)$ です。「線形実行可能性」とは、一次等式と非負条件を同時に満たす数があるかという問題です。実数の指数・係数でも上の数学的同値は成り立ちます。有理数データなら、有理解または有理数の不可能性証明書を有限の厳密計算で求められます。非空の有理多面体は有理点を持ち、不存在側も $b^{\mathsf T}y=-1$ と正規化した有理線形系に直せるためです。任意の実数を有限の入力として比較できる、という計算可能性の主張ではありません。
例えば $2U-V$ なら、負の $a^2b$ に $a^3$ を $\dfrac23$、$b^3$ を $\dfrac13$ 割り当てます。6列を合わせて各立方をちょうど2ずつ使います。係数を無制限に重複使用しないことが、この行和の条件に当たります。
$x=r$ を等号点とする場合は、各係数を $r^{\alpha_i}$、$r^{\beta_j}$ 倍して同じ判定へ移せます。有理係数・整数指数・正の有理数点なら、この正規化も有理数で行えます。指定点で等号でない式に、この定理の必要性を適用することはできません。
得た割当てから、等号条件も読み取れます。$t_{ij}>0$ の全ての組について
$$x^{\alpha_i}=x^{\beta_j}$$
が同時に成り立つことが必要十分です。実際、各列のAM-GM差は非負なので、和が0なら各列が0となります。対数座標では $(\alpha_i-\beta_j)\cdot y=0$ という一次条件になります。支持が一点だけの恒等的な差も、この記述に含まれます。

R05 凸関数による不存在証明

割当てが見つかれば証明は作れます。では見つからないとき、計算の失敗なのか、本当にその形式の証明がないのかをどう確かめればよいでしょうか。指数に凸関数を当てると、有限個の補助単項式まで一度に扱えます。
凸関数 $\varphi$ とは、$0\leq t\leq1$ に対して
$$\begin{gathered}\varphi(t\alpha+(1-t)\beta)\\ \leq t\varphi(\alpha)+(1-t)\varphi(\beta) \end{gathered}$$
を満たす関数です。有限個の重みに対する同じ関係は、項数の帰納法で得られ、イェンセンの不等式と呼ばれます。ここでは指数をこの関数の引数にします。指数に対する凸関数 $\varphi$ を一つ選びます。直接型の1個の差に対し、凸性から
$$\sum_{i=1}^{m}w_i\varphi(\alpha_i)\geq\varphi(\beta).$$
従って、直接型で表せる $P$ は必ず
$$\boxed{\sum_{i=1}^{m}c_i\varphi(\alpha_i)-\sum_{j=1}^{k}d_j\varphi(\beta_j)\geq0}$$
を満たします。指数が同じ補助単項式は、ここでも係数が相殺されます。従って、補助項を何個入れても、この必要条件を破る式は表せません。

凸順序と線形条件が同値になる理由

全ての凸関数について上の条件が成り立つことを、ここでは「正の指数の係数分布が、負の指数の係数分布より凸順序で大きい」と呼びます。総質量で割れば確率分布になります。割当て $t_{ij}$ は、負の指数 $\beta_j$ を平均として正の指数へ分けるマルチンゲール輸送です。なお、ここでアフィン関数 $\varphi(\alpha)=h\cdot\alpha$ とその負を使えば、両側の指数の一次モーメントが等しいことも必要になります。

必要性を閉じる証明――Farkasの補題から凸関数を作る


$A$ を実行列、$b$ を実ベクトルとします。Farkasの補題[9]は、有限の線形系 $Az=b,z\geq0$ の実行可能性と、$A^{\mathsf T}y\geq0,b^{\mathsf T}y<0$ を満たす分離ベクトル $y$ の存在が、ちょうど一方だけ成り立つと述べます。これは、有限生成凸錐から点 $b$ を分離する超平面の定理です。


R04の行和・列和・指数の式に対応する成分を、それぞれ $r_i,s_j,z_j$ と書くと
$$r_i+s_j+z_j\cdot\alpha_i\geq0$$
であり、
$$\begin{gathered}\sum_{i=1}^{m}c_ir_i\\+\sum_{j=1}^{k}d_j(s_j+z_j\cdot\beta_j)<0.\end{gathered}$$
ここで $\varphi(a)=\max_{1\leq j\leq k}(-s_j-z_j\cdot a)$ とおきます。アフィン関数の最大なので凸です。$r_i\geq\varphi(\alpha_i)$、$s_j+z_j\cdot\beta_j\geq-\varphi(\beta_j)$ であるため、上の負の数は凸関数の差
$$\begin{gathered}\sum_{i=1}^{m}c_i\varphi(\alpha_i)\\-\sum_{j=1}^{k}d_j\varphi(\beta_j)\end{gathered}$$
以上です。従ってこの差も負になります。


つまり線形条件が不可能なら、必ず凸関数による反証が得られます。逆に直接型の和からは全ての凸関数について非負です。よって直接型の証明は線形条件を満たし、R04の必要性も示されました。逆方向はR04の十分性とイェンセンの不等式から従うので、割当ての存在・全凸関数の不等式・直接型証明の存在は同値です。


この議論により、元の式に現れる指数の集合(支持)以外の指数を持つ補助単項式を有限個入れて相殺しても、直接型の証明可能性は増えません。存在するなら元の正負の支持だけで割当てを作れます。任意の補助式への置換や、非負式の乗算まで同じ結論になるわけではありません。

シュールの不等式は、指定形式では表せない

$a,b,c>0$ とし、
$$\begin{aligned}V={}&a^2b+ab^2+b^2c\\&+bc^2+c^2a+ca^2\end{aligned}$$
とおきます。
$$H=a^3+b^3+c^3+3abc-V$$
に対し、$\varphi(\alpha)=-\min(\alpha_1,\alpha_2,\alpha_3)$ を取ります。これは三つの線形関数 $-\alpha_h$ の最大なので凸です。純立方と $V$ の指数では0、$abc$ の指数では $-1$。従って係数付きの差は $-3<0$。直接型の有限和では表せません。
不等式自体は正しく、対称性から $a\geq b\geq c>0$ とすると
$$\begin{gathered}H=(a-b)^2(a+b-c)\\+c(a-c)(b-c)\geq0.\end{gathered}$$
文字の大小による因子の符号を使う証明です。直接型では利用しなかった情報を使っています。

R06 候補は有限個に絞れるか

存在条件は有限の一次問題になりました。今度は、読者が使うAM-GMの組そのものを、何個調べれば十分なのかを考えます。
正の係数を持つ項の指数を $\alpha_1,\ldots,\alpha_m\in\mathbb R^n$、目標の指数を $\beta$ とする。$W(\beta)$ を、次の条件を満たす重み $w\in\mathbb R^m$ の集合と定義する。
$$\begin{gathered} w_i\geq0,\qquad\sum_{i=1}^{m}w_i=1,\\ \sum_{i=1}^{m}w_i\alpha_i=\beta. \end{gathered}$$
重み $w$ の支持は、$w_i>0$ となる添字の集合とする。$B$ を、$i$ 列目が $(1,\alpha_i)$ である $(n+1)\times m$ 行列とし、階数(一次独立な列の最大本数)を $r$ と書く。
命題A。 空集合でない $W(\beta)$ の任意の要素は、$B$ の列が一次独立となる支持を持つ重みの凸結合である。従って、各支持の大きさは高々 $r\leq n+1$ とできる。同じ次数の指数なら $r\leq n$。アフィン独立、すなわち列 $(1,\alpha_i)$ が一次独立となる各支持では重みが一意に定まり、有限個の連立一次方程式から全候補を生成できる。

証明――支持を減らす操作
$w$ の正の支持を $I$ とする。ここで重みの支持とは、$w_i>0$ である添字の集合である。$B$ の $I$ に属する列が一次独立なら終了する。従属なら、$I$ の外で0、$Bh=0$ を満たす零でない $h$ がある。第1行より $\displaystyle \sum_{i=1}^{m}h_i=0$ だから、$h$ は正負両方の成分を持つ。
$w+th$ が非負である $t$ の区間の両端を $t_-<0< t_+$ とする。$I$ 上の $w_i$ は正なので、この両端は有限であり、両端では少なくとも一つの正の成分が0になる。$B(w+t_\pm h)=Bw$ だから両方とも $W(\beta)$ に属し、
$$\begin{aligned} w={}&\frac{t_+}{t_+-t_-}(w+t_-h)\\ &+\frac{-t_-}{t_+-t_-}(w+t_+h). \end{aligned}$$
各端点の支持は元より小さい。同じ操作を繰り返すと、支持の大きさは正の整数として減少するため、有限回で一次独立な支持の重みの凸結合になる。
独立な支持 $I$ では $B_Iw_I=(1,\beta)$ の解は高々一つであり、$|I|\leq r$。全指数の成分和が同じ $d$ なら、$B$ の指数座標の行の和は第1行の $d$ 倍となるので、$r\leq n$。重みが0になる添字は除いて重複候補をまとめる。添字の部分集合は有限なので、全候補も有限である。$W(\beta)$ が空なら候補は0個であり、その目標は作れない。有理数データなら、候補の重みも全て有理数である。

R04の有限単項式和
$$\begin{gathered} P=\sum_{i=1}^{m}c_ix^{\alpha_i}-\sum_{j=1}^{k}d_jx^{\beta_j},\\ P(1)=0 \end{gathered}$$
に戻る。各 $\beta_j$ に対し、上の有限候補を $w^{j1},\ldots,w^{jN_j}$ とする。候補がない場合は $N_j=0$、空の和は0とする。担当量 $z_{je}\geq0$ を用いた条件は
$$\begin{gathered} \sum_{e=1}^{N_j}z_{je}=d_j,\\ \sum_{j=1}^{k}\sum_{e=1}^{N_j}z_{je}w_i^{je}=c_i. \end{gathered}$$

(6.1)


系。 (6.1)はR04の割当て条件と同値である。従って、生成した候補の共同配分により、R02の直接型の存在・不存在を判定できる。R05により、有限個の補助単項式を導入して相殺する場合も、この設定の証明可能性は拡大しない。
証明と、候補を一つずつ確定してはいけない理由
(6.1)の解から $\displaystyle t_{ij}=\sum_{e=1}^{N_j}z_{je}w_i^{je}$ と定めると、R04の総量・指数条件を満たす。各候補にAM-GMを用いて足す構成も、そのまま得られる。
逆にR04の割当てがあれば、$w_i=\frac{t_{ij}}{d_j}$ は $W(\beta_j)$ の元である。命題Aにより $\displaystyle w=\sum_{e=1}^{N_j}q_{je}w^{je}$、$q_{je}\geq0$、$\displaystyle \sum_{e=1}^{N_j}q_{je}=1$ と分解できる。$z_{je}=d_jq_{je}$ とすれば(6.1)を満たす。
例えば
$$5x^6+6x^3+7\geq6x^5+6x^2+6x$$
では、各目標に二つずつの二点支持が生成される。指数2を先に $(6,0)$ で担当量6とすると、$2x^6+4$ を消費し、残る $x^6$ の係数は3。しかし指数5を作るには指数6の重みが少なくとも $\frac{2}{3}$ 必要なので、$6x^5$ のためだけに係数4以上が要る。
共同配分なら
$$\begin{aligned} 4x^6+2x^3&\geq6x^5,\\ 4x^3+2&\geq6x^2,\\ x^6+5&\geq6x \end{aligned}$$
を同時に選べる。局所的に有効な候補を確定する操作は、残りの目標の実現可能性を保存しない。

命題Aは凸多面体の頂点分解をこの重み集合で具体化したものです。上の系で完全に列挙できるのは、指定点で等号となる直接型の組です。R03の一般の最良係数を、少数項の候補の係数だけ比べて求めることはできません。
この系は、$P(1)=0$ により各非負差も同じ点で0になる設定を使っています。既知の別の正の等号点は正規化できますが、等号点の発見や一般の係数最適化まで解決するものではありません。一般のSAGEとの関係はR14で見ていきます。

R07 一変数の係数判定

一般の一次条件を、一変数ではもっと簡単に読めます。等号点の因子 $(x-1)^2$ を除いた多項式の係数が、そのまま答えになります。
$P(x)$ を実係数・非負整数指数の通常の多項式とし、$P(1)=P'(1)=0$ とします。
$$P(x)=(x-1)^2Q(x)$$
と書けます。
定理。 $P$ がR02の直接型AM-GM差の有限和で表せることと、$Q$ の係数が全て非負であることは同値です。最終的な $P$ は非負整数の指数を持つ通常の多項式とします。途中の補助指数には実数を許しても、この結論は変わりません。

証明


$P=0$ なら $Q=0$ として両条件とも成立する。$P\ne0$ なら仮定より次数 $d\geq2$ であり、$\displaystyle P(x)=\sum_{i=0}^{d}p_ix^i$、$\displaystyle Q(x)=\sum_{k=0}^{d-2}q_kx^k$ と書きます。形式的な割り算、または係数比較により
$$q_k=\sum_{i=0}^{k}(k+1-i)p_i.$$
凸関数 $\varphi_k(t)=\max\{k+1-t,0\}$ を指数へ適用すると、R05の必要条件の左辺はまさに $q_k$。従って直接型なら全ての $q_k\geq0$ です。


逆に全て $q_k\geq0$ なら
$$P(x)=\sum_{k=0}^{d-2}q_k\{x^{k+2}+x^k-2x^{k+1}\}.$$
各括弧は2項のAM-GMの差であり、直接型の証明になります。$P=0$ の場合は空和として扱います。


例えば次のように判定できます。

  • $(x-1)^4$:$Q=x^2-2x+1$ なので直接型では不可能。
  • $(x-1)^2(x-2)^2$:$Q=x^2-4x+4$ なので不可能。
  • $(x-1)^2(x^2+x+1)$:$Q$ の全係数が非負なので可能。
    最初の式は、$x^2+1\geq2x$ から得た非負式 $(x-1)^2$ を自分自身に掛ければ証明できます。これは、非負性の証明と直接型の証明が異なる明確な例です。なお $Q$ が全て非負係数でなくても、$Q(x)>0$ となることはあります。通常の多項式の非負性判定と、この係数判定を混同してはいけません。

R08 対称3次式の分類

証明形式の違いは、どれくらい小さな式でも現れるのでしょうか。まずは三変数の対称3次式を、係数を動かしながら全部調べてみます。
$$\begin{gathered} U=a^3+b^3+c^3,\\ V=a^2b+ab^2+b^2c\\ +bc^2+c^2a+ca^2 \end{gathered}$$
とし、
$$F=AU+BV-(3A+6B)abc$$
を考えます。これは $a=b=c$ で0になる対称3次同次式の一般形です。$A,B$ は実数です。
定理。 全ての $a,b,c>0$ に対し $F\geq0$ である必要十分条件は
$$A\geq0,\qquad A+B\geq0.$$
一方、直接型AM-GMの有限和で表せる必要十分条件は
$$A\geq0,\qquad A+2B\geq0.$$

非負性の必要性・十分性


$H=U-V+3abc$、$T=V-6abc$ とおくと $F=AH+(A+B)T$。$H\geq0$ はR05のシュールの証明、$T\geq0$ は、$V$ の6項の積が $(abc)^6$ なので6項AM-GMから成立します。従って二条件は十分です。


必要性は境界への極限で示せます。$(a,b,c)=(1,e,e)$、$e\to0+0$ で $F\to A$。また $(1,1,e)$ で $F\to2(A+B)$。全ての正の組で非負なら、これらも非負です。境界を定義域に含める必要はありません。極限が負なら近くの正の組でも負になるためです。


直接型の必要性・十分性


恒等式
$$\begin{gathered} F=L_c(a-b)^2+L_a(b-c)^2\\+L_b(c-a)^2 \end{gathered}$$
が成り立ちます。ここで $L_c=\dfrac A2(a+b)+\left(\dfrac A2+B\right)c$、$L_a,L_b$ は文字を巡回させた式です。二条件のもとで展開した各項は、正の定数と単項式を掛けた2項AM-GM差なので直接型です。


逆に、凸関数 $\max\{\alpha_1-2,\alpha_2-2,\alpha_3-2,0\}$ による差は $3A$。また $-\min(\alpha_1,\alpha_2,\alpha_3)$ による差は $3A+6B$。R05よりどちらも非負でなければなりません。


非零の式が非負になる上の範囲では、$F=AH+(A+B)T$ の係数の少なくとも一方が正です。$H$ も $T$ も正の範囲での等号は $a=b=c$ なので、$F$ の等号も $a=b=c$ に限ります。$A=B=0$ では恒等的に0です。例えばシュールの式 $A=1,B=-1$ は非負の範囲に入りますが、直接型の範囲には入りません。

R09 対称4次式の分類

四次でも、直接型に限れば三つの一次条件で分類できます。ここでは一般の非負性まで全て分類するのではなく、二つの範囲が異なることを一つのパラメータ族でも確かめます。
この節でも $a,b,c>0$ とします。ここからは記号を改め、
$$\begin{gathered} U=a^4+b^4+c^4,\\ V=a^3b+ab^3+b^3c\\+bc^3+c^3a+ca^3,\\ W=a^2b^2+b^2c^2+c^2a^2,\\ T=abc(a+b+c) \end{gathered}$$
とします。$a=b=c$ で0となる一般形は
$$\begin{gathered}F=AU+BV+CW\\-(A+2B+C)T.\end{gathered}$$
定理。 $F$ が直接型で表せる必要十分条件は
$$\begin{gathered}A\geq0,\quad A+B\geq0,\\A+2B+C\geq0.\end{gathered}$$

十分性――三つの基本差


$R_1=U-V+W$、$R_2=V-2W$、$R_3=W-T$ とおけば
$$\begin{gathered}F=AR_1+(A+B)R_2\\+(A+2B+C)R_3.\end{gathered}$$
また
$$\begin{gathered} R_1=\frac12\{(a^2+b^2)(a-b)^2\\ +(b^2+c^2)(b-c)^2\\+(c^2+a^2)(c-a)^2\},\\ R_2=ab(a-b)^2+bc(b-c)^2\\+ca(c-a)^2,\\ R_3=\frac12\{(ab-bc)^2+(bc-ca)^2\\+(ca-ab)^2\}. \end{gathered}$$
それぞれを展開すれば、正の単項式を掛けた2項AM-GM差の非負和です。


必要性――三つの凸関数


指数 $\alpha\in\mathbb R^3$ に対する次の凸関数を使います。


1. $\max\{\alpha_1-3,\alpha_2-3,\alpha_3-3,0\}$ による係数付きの差は $3A$。


2. $\max\{\alpha_1,\alpha_2,\alpha_3\}$ による差は $6(A+B)$。


3. $-\min\{\alpha_1,\alpha_2,\alpha_3\}$ による差は $3(A+2B+C)$。


例えば2では、指数の型 $(4,0,0),(3,1,0),(2,2,0),(2,1,1)$ での値が順に $4,3,2,2$。各項数が $3,6,3,3$ であることを入れると $6(A+B)$ になります。R05より三つとも非負である必要があります。


三条件を満たす非零の式では、少なくとも一つの $R_i$ の正の係数があり、正の変数での等号は $a=b=c$。三係数が全て0の場合、$A=B=C=0$ です。なお、この定理は対称4次式全体の非負性の完全分類ではなく、直接型の完全分類です。

パラメータで二つの範囲を比較する

$$G_t=U+tW-\frac{1+t}{2}V$$
では $A=1,\ B=-\dfrac{1+t}{2},\ C=t$。従って直接型で表せる必要十分条件は $t\leq1$ です。
一方、恒等式
$$\begin{gathered} G_t=\frac{3-t}{2}R_2+\frac12D,\\ D=(a-b)^4+(b-c)^4+(c-a)^4 \end{gathered}$$
より $t\leq3$ なら非負です。必要性は $a=1+h,b=c=1$ として
$$G_t=h^2\{(3-t)(1+h)+h^2\}$$
を見ると、$t>3$ で小さい正の $h$ に対して負になることから従います。正の範囲の等号はいずれの $t\leq3$ でも $a=b=c$ です。
従って $1< t\leq3$ には、非負だが直接型では証明できない区間が実際にあります。$t=3$ では等号点で2次の変化が消え、4次の差が残ります。等号点近くの情報も、証明形式の違いを示しています。
5次以上でも同じ割当て判定は使えます。例えば $(a+b+c)R_1$ は、各AM-GM差に正の単項式 $a,b,c$ を掛けて足せば直接型になります。ただし、これは一般の対称5次式の非負性の分類を得たという意味ではありません。

R10 置換と、比を一周させる証明

ここまでの不存在は、単項式をそのまま組み合わせる形式についての結論でした。式に現れる正の量を新しい文字に置いたら、何が変わるでしょうか。
$$\begin{gathered}X=a^2+bc,\quad Y=b^2+ca,\\Z=c^2+ab.\end{gathered}$$
とおきます。ここでも $a,b,c>0$ とし、
$$F=\frac XY+\frac YZ+\frac ZX-3$$
を考えます。正の3項の積が1なので $F\geq0$。これは標準的な3項AM-GMを、式に繰り返し登場する正の量へ適用したものです。
ところが、$P=XYZF$、すなわち $X^2Z+Y^2X+Z^2Y-3XYZ$ の展開後の単項式だけへ直接型AM-GMを使う証明は存在しません。
次の凸関数で、計算機を使わずに確認できます。
$$\begin{gathered}\varphi(\alpha)=\max_{1\leq i\leq3}(\alpha_i-\alpha_{i+1}),\\\alpha_4=\alpha_1.\end{gathered}$$
展開係数を、巡回置換 $a\to b\to c\to a$ ごとの3項にまとめると、型と係数は次のとおりです。ここで型は、その単項式の指数です。

  • 正の項:$(5,1,0)$ 型が係数1で3項、$(4,0,2)$ 型が係数2で3項、$(3,2,1)$ 型が係数5で3項。
  • 負の項:$(4,1,1)$ 型と $(3,3,0)$ 型がそれぞれ係数 $-3$ で3項ずつ、$(2,2,2)$ が係数 $-6$。
    $\varphi$ の値は順に $4,4,1,3,3,0$ なので、係数付きの差は
    $$\begin{gathered}12+24+15-27-27\\=-3<0.\end{gathered}$$
    R05によって直接型では不可能です。これは「候補の正の量を元の変数だけに限らない」ことに意味がある具体例です。展開前には短い証明があり、展開後の単項式だけでは、補助単項式の相殺を許しても直接型には戻せません。
    等号は $X=Y=Z$ です。最大の変数を $a$、最小を $b$ と呼び直して等号の条件を調べると、$a+b-c>0$ であり、
    $$X-Y=(a-b)(a+b-c)=0$$
    から $a=b$。従って $a=b=c$ であり、逆も成立します。この呼び直しは対称な方程式 $X=Y=Z$ を調べるためのもので、向きを持つ元の式を並べ替える操作ではありません。

比を一周させる候補を、有限に作る

共通の定義域上で正の関数 $D_1,\ldots,D_m$ と、有限の向き付き辺集合 $E$ を固定する。$m\geq1$、$C$ は実数とする。辺 $e=(i,j)$ は $\frac{D_i}{D_j}$ を表す。自己辺は定数1なのであらかじめまとめる。係数 $b_e>0$ に対し
$$F=\sum_{e=(i,j)\in E}b_e\frac{D_i}{D_j}-C$$
という固定した係数表示を考える。
単純閉路 $c=(i_1,\ldots,i_r)$ とは、頂点が途中で重複せず、$i_1\to i_2\to\cdots\to i_r\to i_1$ の全辺が $E$ にある列である。回転は同一視し、逆向きは、辺が実在する場合に別候補とする。
$$G_c=\sum_{h=1}^{r}\frac{D_{i_h}}{D_{i_{h+1}}}-r\geq0.$$
ただし $i_{r+1}=i_1$ とする。
生成する積は1であり、各 $G_c$ は $r$ 項AM-GMの差である。
全単純閉路を $c_1,\ldots,c_N$ と番号付けし、その長さを $l_h$ とする。辺 $e$ が $c_h$ に含まれるとき $a_{eh}=1$、そうでなければ0とする。
また辺を $e_1,\ldots,e_s$ と番号付けし、$e_l=(p_l,q_l)$ と書く。
命題B。 固定した係数表示を、閉路AM-GMの非負和と、残った正の比・非負定数へ、係数を保って分解できることは、閉路の担当量 $z_h\geq0$ と余り $r_e\geq0,k\geq0$ が存在して
$$\begin{gathered} b_e=\sum_{h=1}^{N}a_{eh}z_h+r_e,\\ -C=-\sum_{h=1}^{N}l_hz_h+k \end{gathered}$$

(10.1)


となることと同値である。第1式は全ての $e\in E$ に課す。全ての係数は固定した比の表示に対して比較する。
証明・完全性の範囲
(10.1)を辺ごと・定数ごとに足せば
$$\begin{aligned} F={}&\sum_{h=1}^{N}z_hG_{c_h}\\ &+\sum_{l=1}^{s}r_{e_l}\frac{D_{p_l}}{D_{q_l}}+k \end{aligned}$$
を得るので十分。逆に、係数を保つこの形式の分解があれば、各辺の使用量と定数を比較して(10.1)になるので必要である。
途中で頂点を重複する閉じた歩道を許しても、新しい候補は不要である。重複した頂点で二つの閉じた歩道へ分け、繰り返すと単純閉路へ分解できる。元の比の和と長さも、その分解の和になる。
したがって全単純閉路を生成すれば、この係数通りの閉路分解形式について候補を尽くせる。ただし $D_i$ に代数的な関係がある場合、同じ関数を別の係数表示へ直せることがある。本命題はそのような全表示を尽くすものではなく、任意のAM-GM差の和の不存在を与えるものでもない。
例えば $D_1=a,D_2=b,D_3=a+b$ なら $\dfrac{D_3}{D_1}-\dfrac{D_2}{D_1}=1$ という関係がある。独立な三変数として比の係数を固定する場合には使わない関係である。一つの係数表示で分解できなくても、その関係を使って表示を変えれば証明できる可能性が残る。

式を読む段階では、各分母を取り出し、同じ分母の分子をまとめ、分子をその分母群の一次結合で表す。係数比較により生成された非負の比だけを辺とする。この前処理は、分子の次数不一致・負係数・選んだ基準の不足により失敗し得る。分母群が従属して表示が一意でない場合、一つの表示を選ぶだけでは、他の表示を使う証明は尽くせない。
従って、(10.1)の完全性と、元の不等式から良い係数表示を必ず見つける完全性は異なる。閉路がなく $C>0$ ならこの形式では不可能である。ただし、それは他の係数表示や別のAM-GM証明の不存在ではない。
閉路が0個の場合も、和を0とする約束で(10.1)を使えます。例えば $C>0$ なら定数の条件が不可能です。$C\leq0$ なら、比の正の和と非負定数だけで証明できます。零係数の辺は最初に除き、同じ辺の係数はまとめます。
全ての量が独立である必要はなく、分解が得られれば実際の正の関数にも適用できます。ただし、必要性が成り立つのは固定した係数を保つ分解に対してです。恒等関係を使うあらゆる証明へ、その必要性を広げてはいけません。

R11 等号点の微分情報

等号条件は、候補を捨てるためだけでなく、係数を逆算する材料にもなります。ここでは等号点の近くを微分して、逆数対の組を絞ります。
開集合内の点 $z_0$ の近傍で正の、2回連続微分可能な関数 $g_i$ に対し、
$$\begin{gathered}F(z)=\sum_{i=1}^{m-1}\sum_{j=i+1}^{m}w_{ij}E_{ij}(z),\\w_{ij}\geq0,\\E_{ij}(z)=\frac{g_i(z)}{g_j(z)}+\frac{g_j(z)}{g_i(z)}-2.\end{gathered}$$
というモデルを考えます。$w_{ij}$ は定数であり、$m\geq2$ とします。
$F(z_0)=0$ なら、$w_{ij}>0$ の各組で $g_i(z_0)=g_j(z_0)$ が必要です。そこで
$$v_i=\nabla\log g_i(z_0)$$
とおきます。$\nabla$ は各座標での偏微分を並べた列、$H$ は $F$ の2階偏微分を並べたヘッセ行列です。すると必要条件は
$$\boxed{\begin{gathered}H=2\sum_{i=1}^{m-1}\sum_{j=i+1}^{m}w_{ij}q_{ij}q_{ij}^{\mathsf T},\\q_{ij}=v_i-v_j.\end{gathered}}.$$

導出と注意


$h=\log g_i-\log g_j$ とすれば、逆数対の差は $e^h+e^{-h}-2$。$h(z_0)=0$ では1階微分が0、2階微分は $2\nabla h\nabla h^{\mathsf T}$ です。従って重み付きで足すと得られます。


等号点で $g_i\ne g_j$ の組に正の係数を与えることはできません。全ての候補量が互いに等しい必要はなく、正の係数でつながる組にだけ等しさが必要です。


制約面上で比較する場合は、独立な座標で両辺を微分する必要があります。正規化前の全空間の行列と、正規化後の接方向の行列をそのまま比較してはいけません。


候補量へ同じ正の関数を掛けても比は変わらず、$v_i-v_j$ も変わりません。一方、各候補を別々の正の定数倍にすると、対数微分は変わらなくても等号点での値は変わります。従って、2次情報だけでなく候補量同士の値の一致も確認する必要があります。


ネスビットでは $g_1=b+c,g_2=c+a,g_3=a+b$、$z_0=(1,1,1)$ とすると
$$\begin{gathered} v_1=(0,\tfrac12,\tfrac12)^{\mathsf T},\\ v_2=(\tfrac12,0,\tfrac12)^{\mathsf T} \end{gathered}$$
で、$v_3$ も同様です。元の差の $a,b$ に関する混合2階微分は $-\dfrac14$。この成分に寄与するのは $(1,2)$ の組だけで、その値は $-\dfrac12w_{12}$ なので、$w_{12}=\dfrac12$ となります。他の二成分からも同じ重みが決まり、R01の恒等式で全体の一致を確認できます。
しかし、$g_1=x,g_2=1$ に対し
$$F(x)=\frac{(x-1)^2}{x}+(x-1)^4$$
を考えると、$x=1$ での2階微分だけからは重み1が得られます。元の式との差は $(x-1)^4$ で、恒等的には一致しません。2次の一致は候補の選別であり、証明書ではありません。 候補を得た後には、必ず元の式との恒等的な一致を確かめます。
モデルから $\nabla F(z_0)=0$ も必要です。係数を非負の $C^2$ 級関数 $w_{ij}(z)$ へ広げても、全ての候補で $E_{ij}(z_0)=0$ なら、積の微分から同じ式が $w_{ij}(z_0)$ を使って成り立ちます。
ただし $w_{ij}(z_0)=0$ だけでは、$E_{ij}(z_0)=0$ は従いません。例えば $g_1=2,g_2=1$、$w=(x-1)^2$ なら $F=\frac{(x-1)^2}{2}$。$v_1-v_2=0$ なのに $F''(1)=1$ であり、係数の2階微分から新しい項が出ます。また、$g_1=x,g_2=1$、$w=(x-1)^2$ なら $F=\frac{(x-1)^4}{x}$ で、2次情報が0でも非零の式を表せます。関数係数を許したモデルには、定数係数の判定をそのまま適用できません。
補足――2次の変化が全方向で消えると、直接型は不可能


R02の直接型の一つの差を対数座標 $x_h=e^{y_h}$ で微分すると、指定等号点 $y=0$ でのヘッセ行列は
$$K\sum_{i=1}^{m}w_i(\alpha_i-\beta)(\alpha_i-\beta)^{\mathsf T}$$
です。これは各方向で非負の二次式を与える行列です。直接型の有限和のヘッセ行列が0なら、そのトレース、すなわち対角成分の和も0。従って全ての原子で $\alpha_i=\beta$ が必要になり、各差は恒等的に0です。


よって、非零の式が指定等号点 $y=0$ で全方向の2次の変化を持たない場合、直接型の有限和にはできません。$(x-1)^4$ やR09の $G_3$ がこの例です。これは全空間の対数座標での主張であり、制約面の一方向だけで2次項が消える場合に同じ結論は出せません。

R12 平方和との違い

平方の和を探せば、AM-GMの使い方も全部見つかるでしょうか。ここでも答えは証明形式に依存します。
モツキン多項式
$$M(x,y)=x^4y^2+x^2y^4+1-3x^2y^2$$
は、実数 $x,y$ に対して非負です。非負の3項 $x^4y^2,x^2y^4,1$ にAM-GMを用いれば、積の3乗根は $x^2y^2$ になります。等号は $|x|=|y|=1$。正の範囲では $(1,1)$ です。
しかし実係数多項式の平方和には表せません。

平方和で表せないことの証明


正の整数 $l$ と実多項式 $h_i$ によって $\displaystyle M=\displaystyle\sum_{i=1}^{l}h_i^2$ と表せるなら、各 $h_i$ の指数の凸包は $M$ の指数の凸包を $\dfrac12$ 倍したものに含まれます。もし外側に指数があれば、それを分離する方向の最高次部分を見たとき、その最大重みの成分の平方和は零多項式になれないため相殺できず、$M$ に存在しない外側の項が生じるためです。


これをニュートン多面体の半分への包含と呼びます。ニュートン多面体は、その多項式に実際に現れる指数の凸包です。この $\dfrac12$ 倍の三角形は頂点 $(0,0),(2,1),(1,2)$ を持ち、含まれる整数点は $(0,0),(1,1),(2,1),(1,2)$ の四つだけです。従って各 $h_i$ は $A_i+B_i xy+C_i x^2y+D_i xy^2$ の形に限られます。すると $\displaystyle\sum_{i=1}^{l}h_i^2$ の $x^2y^2$ の係数は $\displaystyle\sum_{i=1}^{l}B_i^2\geq0$。$M$ の係数 $-3$ と一致しません。


逆に $(x-1)^4$ は多項式の平方なのに直接型ではありません。従って、多項式平方和の探索と直接型AM-GM探索は、それぞれ別の証明を見つけます。
Artinによるヒルベルト第17問題の解決は、全実空間で非負な実多項式が有理関数の平方和になることを保証します。これは「自然な単項式AM-GMの組が見つかる」という保証ではありません。分母が0になる点では、有理式としての恒等性と点ごとの評価も区別します。
また、正の領域だけでの非負性を、そのまま元の変数の有理関数平方和で表せるとはいえません。例えば $x$ は $x>0$ では正ですが、全実数上では負にもなるので、有理関数平方和の恒等式にはなりません。通常の多項式なら、$x_h=t_h^2$ と置いて全実空間へ持ち上げる方法が考えられます。正の領域での非負性は連続性により境界にも延びるので、置換後は全実空間で非負です。ただし、得られる有理関数平方和は $t$ の式であり、そのまま元の $x$ の有理関数平方和になるとは限りません。領域を表す因子を伴う証明も別の枠組みです。

R13 候補生成を一つの探索へ

これまでに、単項式の組と比の一周について、有限の候補を調べる根拠が得られました。では、元の式から候補の材料をどう取り出し、失敗したら何へ進むのでしょうか。③の手順と対応する形でまとめます。

平方分子では、相手を逆算できる

正の $p_i,q_i,h$ と
$$U=\sum_{i=1}^{n}p_i,\qquad V=\sum_{i=1}^{n}q_i$$
に対し、2項AM-GMを
$$\frac{p_i^2}{q_i}+h^2q_i\geq2hp_i$$
と使うと、和は
$$\sum_{i=1}^{n}\frac{p_i^2}{q_i}\geq2hU-h^2V.$$
右辺を平方完成すると
$$2hU-h^2V=\frac{U^2}{V} -V\left(h-\frac UV\right)^2.$$
従って、この一パラメータ族の中で最大の下界を与えるのは $h=\dfrac UV$。元の項に組み合わせる相手 $h^2q_i$ が、計算で決まります。
右辺の目標を $R$ とすれば、R01の恒等式は
$$\begin{aligned} &\sum_{i=1}^{n}\frac{p_i^2}{q_i}-R\\ &=\sum_{i=1}^{n}\frac{(p_i-hq_i)^2}{q_i}\\ &\quad+\left(\frac{U^2}{V}-R\right) \end{aligned}$$
と書けます。最後の差が、次に示すべき目標です。これが負になる点があれば、平方の余りを捨てたこの下界だけからは進めません。元の不等式が偽になったわけではありません。
例えば $a,b,c>0,abc=1$ の下で
$$\begin{gathered} \frac1{a^3(b+c)}+\frac1{b^3(c+a)}\\ +\frac1{c^3(a+b)}\geq\frac32 \end{gathered}$$
を考えます。これは IMO 1995第2問 です。元の分子1を平方として使うと、下界は $\dfrac9V$、
$$V=a^3(b+c)+b^3(c+a)+c^3(a+b)$$
となります。必要な $V\leq6$ は、条件を満たす $a=2,b=1,c=\dfrac12$ で $V=\dfrac{119}{8}$ となるため成立しません。
一方、$x=\dfrac1a,y=\dfrac1b,z=\dfrac1c$ と置けば $xyz=1$ で、
$$\frac1{a^3(b+c)} =\frac{x^3yz}{y+z}=\frac{x^2}{y+z}.$$
今度は $U=x+y+z,V=2U,h=\dfrac12$ となり、残る目標は $x+y+z\geq3$。積1の条件から3項AM-GMで得られます。両段階の等号は $x=y=z=1$ で同時に成立します。

有限に調べる材料を決める

以下の規則名は③と共通です。いずれも、式にない補助量を無制限に作る操作ではありません。

  • F:二項因子の積。 分子に現れる正の二項式、または有理係数で一度因数分解して得られる正の二項因子を使う。各因子の二項積を掛け、元の分母・目標との指数を比較する。
  • G:分母から作る比。 同じ分母の分子をまとめ、分子を取り出した分母の定数係数の一次結合で表す。単項式の分母なら展開・約分も行う。実際に出た非負の比だけで、R10の閉路候補を作る。
  • S:平方分子。 表示された $\dfrac{p_i^2}{q_i}$ から $U,V,h=\dfrac UV$ を計算し、上の恒等式を使う。$p_i>0$ を確認できる場合のAM-GMの規則であり、任意の符号の平方根を勝手に正と扱わない。
  • M:単項式。 正の共通分母を払い、同じ指数をまとめる。R06で重みを列挙し、R04の共同配分を解く。既知の正の等号点があれば先に1へ移す。
  • C1:和一定の条件。 正の係数の一次式 $H=K>0$ の下で逆数和を扱うなら、目的式を $\dfrac HK$ 倍する。条件上で値は変わらず、展開により定数と比が現れる。
  • C2:積1の条件。 全変数の積が1なら、全変数を同時に逆数へ置く。新しい単項式の指数から共通の最小値を引き、積1の因子を除く。
  • P:積条件で残った和。 正の単項式和の係数の総和を $C>0$ とし、係数を $C$ で割った重みを作る。指数の平均の全成分が等しければ、積は変数全体の積のべきになる。積1の条件では下界 $C$ を得る。
    C1は条件上で元の式と等しく、C2も正の領域の積1の集合をそれ自身へ移す可逆な置換です。ただし、置換前後で等号点も移ります。分母を払うときは、その符号と元の零点を先に確認しなければなりません。約分で消えた分母の零点を、元の定義域へ勝手に加えることはできません。

選択と撤退の根拠

最初は元の形を保つF、表示された分母を使うG、平方分子S、必要に応じたP、展開後のMという順で短く試します。Gは短い閉路から、Mは少ない項の組から、許す大きさを段階的に広げます。各段階では全候補の係数を一緒に決め、一つだけ最大限使って確定しません。
数学的に候補を捨てられる理由は、正値性を満たさない、指数の非負の重みがない、全候補でも係数条件が不可能、残った目標が偽、などです。一方、短い組から試す順序は計算を抑えるための選択であり、最短の証明を保証する定理ではありません。
特に、下界が得られても等号が両立しないなら、最適値は確定しません。例えば
$$\frac{(x^2+3y^2)(3x^2+y^2)}{x^2y^2} \qquad(x,y>0)$$
にFを使うと12以上ですが、二つの等号は同時に成立しません。展開すれば
$$10+3\left(\frac{x^2}{y^2}+\frac{y^2}{x^2}\right)\geq16$$
となり、$x=y$ で達成します。失敗した評価を続けるのではなく、その不足を確認して表示を変えます。

どこが完全で、どこが探索なのか

R04・R06のMは、支持と等号点を固定し、全候補を調べて厳密に一次条件を解く範囲で完全です。R10のGも、固定した比の係数表示を閉路AM-GMと正の余りへ分ける形式について完全です。
一方、元の式から良い分母の基準を必ず選ぶ方法、全ての正の置換を作る方法、最短の証明を選ぶ方法は、ここでは完成していません。F・S・C1・C2も、明記した形に限る候補生成です。
有限の実装では、候補数と探索の深さにも上限を設けます。例えばSで残った目標の再探索は二段階まで、C1・C2は元の目標から各一度とし、変換を繰り返し合成しません。具体的な計算上限と入力形式は別添資料に示します。候補を途中で打ち切った場合、数学的な不存在とは判定しません。

R14 先行研究とのつながり

ここまで考えたところで、似たことが既に研究されていないか調べてみました。すると、AM-GMを非負性の証明に使う理論が、幾つかの方向から見つかりました。用語は少し違っていても、指数の平均や係数の配分という同じ構造が現れます。

AGE・SAGE――一つの負の項から始める

Chandrasekaran・Shahの論文[1]では、指数関数の和の非負性をAM-GMで保証します。$x_h=e^{y_h}$ と置けば $x^\alpha=e^{\alpha\cdot y}$ なので、本記事の単項式と対応します。
AGEは、負の係数が高々一つで、全実空間で非負な指数関数和です。固定した有限の指数集合を使い、そのような式の有限和で表せるものがSAGEです。R03は、一つの負の項を持つ場合に、同じ双対性を最良係数の形で表したものです。
相対エントロピーを
$$D(p,q)=\sum_{i=1}^{m}p_i\log\frac{p_i}{q_i}$$
と定義します。ここでは $p_i\geq0,q_i>0$ とし、$p_i=0$ の項は連続的な値0とします。$\log$ は自然対数、$e$ はその底です。$p,q$ が確率分布でないとき、この $D$ 自体が常に非負とは限りません。
$c_i,d>0$ に対する
$$G(y)=\sum_{i=1}^{m}c_i e^{\alpha_i\cdot y} -d e^{\beta\cdot y}$$
が全ての $y\in\mathbb R^n$ で非負となる必要十分条件は、ある $t_i\geq0$ が存在して
$$\begin{gathered} \sum_{i=1}^{m}t_i(\alpha_i-\beta)=0,\\ D(t,ec)\leq-d \end{gathered}$$
となることです。$ec$ は各成分を $e$ 倍したベクトルです。論文[1]のLemma 2と式(3)に対応します。

R03の最良係数とのつながり
$t_i=s w_i$、$s>0$、$\sum_{i=1}^{m}w_i=1$ と置くと、指数条件は $w\in W$ となり、
$$D(sw,ec)=s\left\{\log\frac{s}{\Theta(w)}-1\right\}.$$
右辺を $s>0$ で最小にするのは $s=\Theta(w)$ で、値は $-\Theta(w)$。従って、ある $w$ に対して $d\leq\Theta(w)$ となることと同値であり、R03へつながります。重み0の項は除いて計算します。$d>0$ なので、証明書の $t$ は零ベクトルではありません。

一般のSAGEで、係数と重みを同時に決める条件を、無条件にR04の一次条件へ置き換えることはできません。本記事では、和が指定点で0なので、各非負なAGEもそこで0になります。その値と勾配が0という条件から、各AGEの係数総和と指数の平均がそろい、R02の形になります。この特別な場合をR04・R05で特徴づけています。

SONC――重みが一意に決まる配置

Iliman・de Wolffの論文[2]では、指数が単体の頂点と、その相対内部の一点からなる回路多項式を扱います。頂点がアフィン独立なので、内部点を作る正の重み $w_i$ は一意です。この場合、R03の
$$\Theta=\prod_{i=1}^{m}\left(\frac{c_i}{w_i}\right)^{w_i}$$
は回路数と呼ばれ、正の領域で内部項が $-d x^\beta$($d>0$)なら、非負性は $d\leq\Theta$ と同値です。
全実空間の多項式として扱うときには、頂点指数が非負の偶数整数であることを仮定します。内部項の係数を $b$ とすれば、内部指数も全成分が偶数なら $b\geq-\Theta$、それ以外なら $|b|\leq\Theta$ が必要十分です。[2]のTheorem 3.8で確認できます。正の領域では現れなかった符号の違いが、ここで効きます。
非負な回路多項式の有限和がSONCです。単項式の二乗のような非負な単項式も、通常この証明のクラスに含めて扱います。一般の非負多項式が全てSONCとなるわけではありません。

凸順序――平均を保って指数を移す

R04の係数を総量で割ると、有限個の指数に置かれた二つの確率分布になります。「全ての凸関数で平均値を比較する」のが凸順序です。
各 $\beta_j$ から、重み $\dfrac{t_{ij}}{d_j}$ で $\alpha_i$ へ移すと、移動先の条件付き平均は $\beta_j$ のままです。この平均を保つ結合をマルチンゲール結合と呼びます。R05の必要十分条件は、有限支持のStrassen型の定理に当たります。
Beiglböck・Juilletの Shadow couplings [3]は、実数直線上の凸順序から具体的な結合を作る関連研究です。多次元の本記事の結論を、その一次元の構成定理から直接引用するのではなく、R05の有限次元の分離で証明しました。Strassenの原論文[8]の全文は今回直接確認できていないため、その一般形を本記事の証明の前提にはしていません。

対称化と、一般の非負性判定

ミューアヘッドの不等式[4]では、指数の順列を全て含む対称和を比較します。指数の平均を作り、対応するAM-GMを全順列について足す、という見方ができます。R08・R09は、そのような指数の構造を具体的な三次・四次式で分類したものです。ただし巡回式には、元にない順列の項を追加できません。R10の例でも、実際の係数と向きを保つ必要があります。
また、Reznickの解説[5]には、平方和、モツキン多項式、ヒルベルト第17問題との関係がまとめられています。R12は、その違いを具体例で確かめた節です。
ポリアの定理[6]は、閉じた標準単体
$$\begin{gathered} \Delta=\{x_i\geq0\ (1\leq i\leq n),\\ \sum_{i=1}^{n}x_i=1\} \end{gathered}$$
上で厳密に正な同次多項式 $f$ に対し、十分大きい非負の整数 $N$ で
$$(x_1+\cdots+x_n)^N f$$
の全ての該当次数の係数が正になることを保証します。内部に零点を持つ非負多項式へ、この結論をそのまま使うことはできません。正係数の非零多項式は、全変数が正の点では0にならないからです。境界の零点を許す場合にも追加条件が必要で、本記事ではその一般化は扱いません。
実閉体の量化記号消去[7]は、有理係数多項式の符号条件を含む論理式を原理的に判定します。例えば「全ての正の $x$ で $P(x)\geq0$」も対象です。一方、その答えから短いAM-GM証明が得られるとは限らず、任意の実指数の式まで多項式の理論として扱えるわけでもありません。
既存理論と結びついたことで、今回の問いの位置も見えてきました。全く新しい非負性理論を作るというより、既知の構造を使い、入試の式から候補を作るためにどこまで小さな判定へ落とせるかを調べている、と捉えるのが近いと思います。

R15 計算実験で確かめたこと

定理を実装したときに、実際に証明の組が得られるかも確かめました。ここでの計算実験は、数学的な命題の証明とは別に、候補生成が働く範囲と限界を調べるためのものです。

方法と判定の扱い

Python、SymPy、SciPyを使い、有理係数の多項式・有理式と正の変数を入力しました。Mでは整数指数と既知の正の有理数の等号点を扱い、条件の利用は明記した和一定・積1の形に限っています。平方根を含む一般の式や、一般の最良定数を自動生成する機能は対象外です。
浮動小数点の線形計画は候補を探すために使い、最後は有理数の割当て、またはFarkasの証明書を検算しました。候補量の正値性、分子の係数比較、閉路の積、残った目標との恒等式も照合しています。厳密に確認できない場合は未判定です。
元の式にあった分母も、約分前に調べます。例えば $\dfrac{x-1}{x-1}$ を正の全域で扱うことはできません。$x=1$ で定義されないからです。約分済みの式しか与えられないときは、消えた分母の零点を自動復元できないため、元の定義域を別に確かめる必要があります。

開発例と、規則を固定した後の検証例

最初の開発用16例は、単項式型9例・逆数対型4例・平方分子型3例です。単項式型では、直接型の存在5例・不存在4例について厳密な証明書を確認しました。
その後の検証は、規則とコードを固定してから、当該規則の調整に使っていない式を与える方法で行いました。結果は、実行順に次のとおりです。

  • 第1群・24例。 証明14例、通分後の分子の直接型不存在5例、未解決または入力範囲外5例。
  • 第2群・8例。 証明7例、分子の直接型不存在1例。
  • 第3群・9例。 証明6例、直接型不存在は確認したが元の非負性は未解決1例、偽の不等式に対して未解決1例、定義域の確認で入力範囲外1例。
  • 第4群・5例。 全5例で証明を得た。
    各群の結果から探索規則を変えた場合、次の群に使う前に再び固定しています。以前の例の再実行は新しい検証例へ数え直していません。詳細な式・出典・候補・割当て・探索上限は、別添の研究検証報告と再実行資料に収録しています。
    これらは、既知の構造を踏まえて構成・選定した集合です。無作為な入試問題の標本でも、作問者が解法を知らない盲検でもありません。従って群を合算した「一般の不等式を解ける割合」は出しません。「調整に使っていない」は、数学的に未知の問題を意味する言葉ではありません。

結果から何が分かるか

元の正の量を残す意味。 R10の非線形の三つの量を使う例は、二項の逆数対だけでは見つからず、三項の一周を候補にすると証明できます。その通分後の分子には直接型が存在しないので、単に展開項の探索を増やすだけでは代わりになりません。
発見できても最短とは限らない。 $x^6+y^6+1\geq3x^2y^2$ は3項AM-GM一回で済みますが、一般手順では平方分子の規則を先に使い、残った目標へ別の単項式配分を行う経路が得られました。候補を生成できることと、短い答案を選ぶことには、別の工夫が要ります。
不存在と未解決は同じ結果ではない。
$$x^4+5x^2+2-3x^3-5x$$
には直接型が存在しません。一変数の係数判定でも
$$P=(x-1)^2(x^2-x+2)$$
の商に負係数があると分かります。しかし $x^2-x+2=(x-\frac12)^2+\frac74>0$ なので、元の不等式は正しい。単項式型の不存在を返しただけで、問題全体の非負性を解決したことにはなりません。
逆に、条件なしの $\dfrac1x+\dfrac1y\geq1$ は $x=y=3$ で偽ですが、探索器は反例を見つけず未解決となりました。これは実行後の別の確認であり、反例探索の成功としては数えていません。
以上は、候補の構成と厳密な検算を実装できたこと、そして範囲を広げる必要のある箇所を示す結果です。読者に実行してもらう被験者実験は行っていないため、人間の発見率・学習効果・必要時間についての結論はまだありません。

R16 分かったこと、残った問い

出発点は、ネスビットの不等式を見て「どうしてその組を選べるのだろう」と思ったことでした。分母から比を作る道と、通分して単項式を配分する道を調べるうちに、証明の形そのものを区別する必要が見えてきました。
等号点を固定した直接型については、係数の割当てが必要十分条件となります。存在するなら、その割当てからAM-GMの組を構成できます。存在しないなら、凸関数による反証を得られます。有限個の補助単項式を導入して相殺しても、この形式の範囲は広がりません。一変数や対称三次・四次の具体的な分類にも、この構造が現れました。
ただし、同じ式でも正の量への置換を許すと、直接型の範囲を越えて証明できることがあります。平方和とも一致しません。「どこまでAM-GMを使えるか」という問いには、まず何を許すのかを答える必要があります。
まだ分からないことも残っています。未知の置換を全て生成する方法、未知の等号点の発見、一般の制約式の自動利用、最も短く自然な証明の選択は、ここでは解決していません。支持を固定した有限次元の判定と、良い支持そのものを発見する問題は、必要となる情報が異なります。
特に「有限な探索」と呼ぶときには、候補の式が本当に有限個に定まっているかを確認しなければなりません。R04の係数は連続変数ですが、有限個の未知数を持つ一次問題です。一方、あらゆる補助式を列挙するには、次数や長さだけでなく、係数の記述方法とその長さにも制限が要ります。任意の実数係数を自由に許したまま、候補数を有限とはいえません。
先行研究を調べると、今回の指数の平均や係数の問題は、凸順序・SAGE・SONCなどへつながっていました。既存の理論を踏まえ、本記事で具体的に分類し直した部分と、まだ探索の規則にとどまる部分を区別することで、③の手順にも根拠と限界を与えられます。
AM-GMが見えない式に出会ったとき、毎回一つの妙案を言い当てる必要はありません。式から作れる候補を調べ、見つからなければ、その形式での限界なのか、まだ試していない表示があるのかを確かめる。その判断を数学としてどこまで説明できるか、というところまでが、本記事で辿った道です。
ここまでお読みくださり、ありがとうございました。皆さんの日常に良き数学の彩のあらんことを。それでは、ごきげんよう。

参考文献

  1. V. Chandrasekaran, P. Shah, Relative Entropy Relaxations for Signomial Optimization, SIAM Journal on Optimization 26 (2016), 1147–1173. DOI:10.1137/140988978 / 著者原稿 。一負項の非負性証明書とSAGEの定義。
  2. S. Iliman, T. de Wolff, Amoebas, nonnegative polynomials and sums of squares supported on circuits, Research in the Mathematical Sciences 3, Article 9 (2016). DOI:10.1186/s40687-016-0052-2 / 著者原稿 。回路数、Theorem 3.8、SONC。
  3. M. Beiglböck, N. Juillet, Shadow couplings, Transactions of the American Mathematical Society 374 (2021), 4973–5002. DOI:10.1090/tran/8380 / 著者原稿 。実数直線上の凸順序とマルチンゲール結合。
  4. R. F. Muirhead, Some Methods applicable to Identities and Inequalities of Symmetric Algebraic Functions of n Letters, Proceedings of the Edinburgh Mathematical Society 21, 144–162. DOI:10.1017/S001309150003460X 。原文§1の対称和の不等式。巻の書誌表示は1902年、原文の講演日は1903年3月13日となっている。
  5. B. Reznick, Some concrete aspects of Hilbert's 17th Problem, Contemporary Mathematics 253 (2000), 251–272. DOI:10.1090/conm/253/03936 / 著者掲載版 。モツキン多項式と平方和、有理関数平方和の解説。
  6. V. Powers, B. Reznick, A new bound for Pólya's Theorem with applications to polynomials positive on polyhedra, Journal of Pure and Applied Algebra 164 (2001), 221–229. DOI:10.1016/S0022-4049(00)00155-9 / 著者原稿 。閉じた単体上の厳密な正値性に対する係数正値化。
  7. S. Basu, Algorithms in Real Algebraic Geometry: A Survey, arXiv:1409.1534 (2014). 著者原稿 。特にTheorem 2.1の量化記号消去と、その計算上の位置づけ。
  8. V. Strassen, The Existence of Probability Measures with Given Marginals, The Annals of Mathematical Statistics 36 (1965), 423–439. DOI:10.1214/aoms/1177700153 。原論文の全文は今回未確認。凸順序とマルチンゲール結合の対応は[3]で確認し、本記事の有限支持の結果はR05で証明した。
  9. S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press (2004), §5.8.3. 著者公開版 。Farkasの補題と強い二者択一。
投稿日:19時間前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

bloom
bloom
211
27980
殆ど受験数学の講義関連の記事です 偶に研究系も

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中