van der Waerden予想(パーマネント)(van der Waerden conjecture for permanents)とは、$n$ 次の二重確率行列 $A$ のパーマネントについて $\operatorname{per}A\ge n!/n^n$ が成り立ち、等号は全成分が $1/n$ の行列に限るという主張である。1926 年に問われ、1981 年に Falikman と Egorychev が解決したので、いまは定理である。正則な二部グラフの完全マッチングの個数の下界を与え、Gurvits による安定な多項式の容量を使う短い証明がある。
前提知識: 二部グラフ, Hallの結婚定理, 重み付きの相加相乗平均の不等式
二重確率行列(成分が $0$ 以上で、各行・各列の和が $1$ の正方行列)のパーマネントはどこまで小さくなるか。1926 年に van der Waerden は、$n$ 次の二重確率行列 $A$ について
$$
\operatorname{per}A\ge\frac{n!}{n^n}
$$
であり、等号は全成分が $1/n$ の行列に限るのではないかと問うた(Wae26)。これが van der Waerden 予想 である。行列の成分を整数倍すれば、正則な二部グラフの完全マッチングの個数の下界になる。
予想は半世紀以上解けず、1981 年に Falikman が不等式を(Fal81)、Egorychev が等号の条件まで含めて(Ego81)解決した(Gur08 §1)。どちらも混合判別式についての Alexandrov の不等式の、行列が対角の場合を用いている(Huh18 §2.1)。したがって「予想」は歴史的な名前で、いまは定理である。Egorychev–Falikman の定理 とも呼ぶ。
この記事では、2008 年に Gurvits が与えた、多項式についての帰納法による短い証明(Gur08)を Laurent–Schrijver の整理(LS10)に沿って述べる。発想は、パーマネントを多項式の係数として読み、変数を 1 つずつ消すごとに「容量」という量がどれだけ減るかを追うことである。減り方を決めるのは 1 変数の実根の多項式についての不等式だけで、道具は相加相乗平均と、複素解析の Hurwitz の定理で足りる。
| 主張 | 内容 | この記事で |
|---|---|---|
| thm-vdw-main | 下界 $n!/n^n$ と等号の条件 | 証明する |
| thm-vdw-cap | 安定な多項式の容量の不等式 | 証明する |
| cor-vdw-column | 列の非零成分の個数を入れた下界 | 証明する |
| cor-vdw-regular | 正則二部グラフの完全マッチングの下界 | 証明する |
$n\times n$ 行列 $A=(a_{ij})$ の パーマネント(permanent)を
$$
\operatorname{per}A:=\sum_{\sigma\in\mathfrak{S}_n}\prod_{i=1}^na_{i\sigma(i)}
$$
で定める。行列式から置換の符号を取り除いたものである。成分がすべて $0$ 以上の実数で、各行の和と各列の和がすべて $1$ である行列を 二重確率行列 という。全体を $\Omega_n$ と書く。全成分が $1/n$ の行列を $J_n$ と書く。
$\operatorname{per}J_n=n!/n^n$ である。$\operatorname{per}A$ は行や列の入れ替えで変わらない。$A$ が $0,1$ 行列なら $\operatorname{per}A$ は対応する二部グラフの完全マッチングの個数である。$\Omega_n$ の元は 二重確率行列 の記事で詳しく扱う。
$A\in\Omega_n$ なら $\operatorname{per}A\ge n!/n^n$ である。等号は $A=J_n$ のときに限る。
証明は節「主定理の証明」の prf-vdw-main で与える。それまでの節で、容量と安定な多項式の性質を準備する。
Stirlingの公式 により $n!/n^n\sim\sqrt{2\pi n}\,e^{-n}$ である。
| $n$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|
| $n!/n^n$ | $1$ | $1/2$ | $2/9$ | $3/32$ | $24/625$ | $5/324$ |
$\Omega_2$ の元は $A=\begin{pmatrix}a&1-a\\1-a&a\end{pmatrix}$($0\le a\le1$)で、$\operatorname{per}A=a^2+(1-a)^2=\frac12+2(a-\frac12)^2\ge\frac12$ である。等号は $a=1/2$ に限る。
$n=3$ で $A=\frac12\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}$ なら $\operatorname{per}A=\frac14>\frac29$ である。$0$ の成分があっても $A\ne J_3$ なら真に大きい。
$x=(x_1,\dots,x_n)$ の多項式で、係数がすべて $0$ 以上の実数のものを考える。
$p$ を $x_1,\dots,x_m$ の係数が $0$ 以上の多項式とする。$p$ の 容量 を
$$
\operatorname{cap}(p):=\inf_{x_1,\dots,x_m>0}\frac{p(x)}{x_1\cdots x_m}
$$
で定める($m=0$ なら $p$ は定数で $\operatorname{cap}(p)=p$ とする)。$p$ が H 安定 であるとは、すべての $j$ で $\operatorname{Re}z_j>0$ である $z\in\mathbb{C}^m$ について $p(z)\ne0$ であることをいう。また、変数を 1 つ消す操作を
$$
p'(x_1,\dots,x_{m-1}):=\frac{\partial p}{\partial x_m}\Big|_{x_m=0}
$$
で定める。$p'$ は $p$ の $x_m$ の 1 次の項の係数である。
$A\in\Omega_n$(一般に $0$ 以上の行列)に対して $p_A(x):=\prod_{i=1}^n\bigl(\sum_{j=1}^na_{ij}x_j\bigr)$ とおく。これは $n$ 次の斉次多項式で、$x_1\cdots x_n$ の係数が $\operatorname{per}A$ である。$q_n:=p_A$、$q_{i-1}:=q_i'$ と順に消すと、$q_0=\operatorname{per}A$ である。
$A\in\Omega_n$ なら $p_A$ は H 安定で、$\operatorname{cap}(p_A)=1$ である。
$\operatorname{Re}z_j>0$ なら $\operatorname{Re}\sum_ja_{ij}z_j=\sum_ja_{ij}\operatorname{Re}z_j>0$ である(各行に正の成分がある)ので、$p_A(z)\ne0$ である。$x_j>0$ なら 重み付きの相加相乗平均の不等式 より $\sum_ja_{ij}x_j\ge\prod_jx_j^{a_{ij}}$ である。$i$ について掛けると、各列の和が $1$ なので $p_A(x)\ge\prod_jx_j$ である。$x=(1,\dots,1)$ で等号なので容量は $1$ である。$\square$
次の関数が減り方を測る。$g(0)=g(1):=1$、$k\ge2$ で $g(k):=\bigl(\frac{k-1}k\bigr)^{k-1}$ とする。$g(2)=\frac12$、$g(3)=\frac49$、$g(4)=\frac{27}{64}$ で、$g(k)$ は $1/e$ に向かって減少する。実際、$m=k-1\ge1$ について、相加相乗平均を $m$ 個の $1+\frac1m$ と $1$ 個の $1$ に当てると $(1+\frac1m)^m< (1+\frac1{m+1})^{m+1}$ であり、$1/g(k)=(1+\frac1m)^m$ なので $g(k)>g(k+1)$ である。また、
$$
\prod_{i=1}^ng(i)=\prod_{i=2}^n\frac{(i-1)^{i-1}}{i^{i-1}}=\frac{(n-1)!}{n^{n-1}}=\frac{n!}{n^n}\qquad(1)
$$
である(分子の $j^j$ と分母の $j^{j-1}$ が約分されて $j$ が残る)。
$R$ を係数が $0$ 以上で $0$ でない 1 変数の実多項式とし、次数を $k$ とする。$R$ の根がすべて実数なら、
$$
R'(0)\ge g(k)\inf_{t>0}\frac{R(t)}t
$$
である。
$k\le1$ なら $R=a+bt$($a,b\ge0$)で、$\inf_{t>0}(a/t+b)=b=R'(0)$ である。$k\ge2$ とする。$R(0)=0$ なら $R(t)/t\to R'(0)$($t\to+0$)なので、$g(k)\le1$ から成り立つ。$R(0)>0$ なら、定数倍して $R(0)=1$ としてよい。係数が $0$ 以上なので根は負で、$R(t)=\prod_{l=1}^k(1+b_lt)$($b_l>0$)と書ける。$B:=\sum_lb_l=R'(0)>0$ とする。相加相乗平均により $R(t)\le(1+Bt/k)^k$ である。$t:=\frac{k}{(k-1)B}$ を代入すると $1+Bt/k=\frac k{k-1}$ なので
$$
\frac{R(t)}t\le\Bigl(\frac k{k-1}\Bigr)^k\frac{(k-1)B}k=\frac{B}{g(k)}
$$
である。$\square$
$p\ne0$ を $x_1,\dots,x_m$ の係数が $0$ 以上の斉次多項式で、H 安定なものとする。
1:根 $t_0$ が $0$ 以下の実数でないとする。$t_0=\rho e^{2i\theta}$($\rho>0$、$-\pi/2<\theta<\pi/2$)と書く。$p$ は斉次なので、$p(e^{-i\theta}x_1,\dots,e^{-i\theta}x_{m-1},e^{-i\theta}t_0)=0$ である。$e^{-i\theta}x_j$ の偏角は $-\theta$、$e^{-i\theta}t_0$ の偏角は $\theta$ で、実部はすべて正なので、H 安定性に反する。
2:$k:=\deg_{x_m}p$ とする。$k=0$ なら $p'=0$ である。$k\ge1$ とし、$p=\sum_{l=0}^kc_l(x')x_m^l$($x'=(x_1,\dots,x_{m-1})$)と書く。右半平面の直積 $D:=\{z\mid\operatorname{Re}z_j>0\}$ の上で、$\varepsilon\to+0$ のとき $\varepsilon^kp(x',x_m/\varepsilon)$ は $c_k(x')x_m^k$ に広義一様収束する。多変数の場合の Hurwitz の定理(零点をもたない正則関数の広義一様極限は、零点をもたないか恒等的に $0$ である。極限の零点と非零点を通る複素直線に制限して Hurwitzの定理(複素解析) を当てれば得られる)により、$c_k$ は $x'$ の右半平面の直積の上で零点をもたない。
$a$ を右半平面の直積の点とする。$R(t):=p(a,t)$ は次数 $k\ge1$ で、$\operatorname{Re}t>0$ に零点がない。$R$ の根を $r_l$ とすると、$\operatorname{Re}t>0$ で $\operatorname{Re}(t-r_l)>0$ なので $\operatorname{Re}\frac1{t-r_l}>0$ であり、$R'(t)/R(t)=\sum_l\frac1{t-r_l}\ne0$ である。よって $\partial_{x_m}p(a,t)\ne0$($\operatorname{Re}t>0$)である。$\varepsilon\to+0$ のとき $\partial_{x_m}p(x',\varepsilon)$ は $p'(x')$ に広義一様収束するので、Hurwitz の定理から $p'$ は $0$ であるか零点をもたない。$\square$
$p\ne0$ を $x_1,\dots,x_m$ の $m$ 次斉次多項式で、係数が $0$ 以上で H 安定なものとする。$k:=\deg_{x_m}p$ とすると
$$
\operatorname{cap}(p')\ge g(k)\operatorname{cap}(p)
$$
である。
$x_1,\dots,x_{m-1}>0$ を固定し、$x'$ と書く。$R(t):=p(x',t)$ は $0$ でなく、係数が $0$ 以上で次数は $k$ であり(係数が $0$ 以上なので $x'$ を代入して次数は落ちない)、lem-vdw-stable の 1 により根はすべて実数である。$R'(0)=p'(x')$ である。容量の定義から $R(t)/t\ge x_1\cdots x_{m-1}\operatorname{cap}(p)$ である。lem-vdw-uni から $p'(x')\ge g(k)\,x_1\cdots x_{m-1}\operatorname{cap}(p)$ である。$\square$
定理の不等式は Gur08 §2.2 の要点で、LS10 Theorem 1 に同じ形がある。lem-vdw-uni で最悪なのは、$R$ の根がすべて等しい場合である。
$A$ を行が $0$ でない $0$ 以上の $n$ 次行列とし、第 $i$ 列の正の成分の個数を $\lambda_i$ とする。このとき
$$
\operatorname{per}A\ge\operatorname{cap}(p_A)\prod_{i=1}^ng(\min(i,\lambda_i))
$$
である。とくに $A\in\Omega_n$ なら右辺の容量は $1$ である。
$p_A$ は(prop-vdw-capa と同じ理由で)H 安定である。lem-vdw-stable の 2 により各 $q_i$ は $0$ か H 安定で、$q_i$ は $x_1,\dots,x_i$ の $i$ 次斉次である。$q_i\ne0$ なら $\deg_{x_i}q_i\le\min(i,\lambda_i)$ である($p_A$ の $x_i$ の次数は $\lambda_i$ で、微分と代入で増えない)。thm-vdw-cap と $g$ の単調性から $\operatorname{cap}(q_{i-1})\ge g(\min(i,\lambda_i))\operatorname{cap}(q_i)$ である。$q_i=0$ なら両辺とも $0$ である。$\operatorname{cap}(q_0)=\operatorname{per}A$ なので、$i=n,\dots,1$ について掛ければよい。$\square$
不等式. $A\in\Omega_n$ とする。cor-vdw-column と $g$ の単調性($\min(i,\lambda_i)\le i$)、(1) により $\operatorname{per}A\ge\prod_ig(i)=n!/n^n$ である。
等号. $\operatorname{per}A=n!/n^n$ とする。$n=1$ は自明なので $n\ge2$ とする。列を入れ替えても $A\in\Omega_n$ と $\operatorname{per}A$ は変わらないので、最後の列の成分がすべて等しいことを示せばよい。$a_i:=a_{in}$ とおく。$q_{n-1}$ は $x_n$ の 1 次の係数なので、$y=(x_1,\dots,x_{n-1})$、$u_i:=\sum_{j< n}a_{ij}y_j$ として
$$
q_{n-1}(y)=\sum_{l=1}^na_l\prod_{i\ne l}u_i
$$
である。$\sum_la_l=1$ なので、重み $a_l$ の相加相乗平均により($0^0=1$ と読む)
$$
q_{n-1}(y)\ge\prod_l\Bigl(\prod_{i\ne l}u_i\Bigr)^{a_l}=\prod_iu_i^{1-a_i}
$$
である。$a_i< 1$ なら、重み $a_{ij}/(1-a_i)$($j< n$、和は $1$)の相加相乗平均で $u_i\ge(1-a_i)\prod_{j< n}y_j^{a_{ij}/(1-a_i)}$ なので、$u_i^{1-a_i}\ge(1-a_i)^{1-a_i}\prod_{j< n}y_j^{a_{ij}}$ である。これは $a_i=1$ でも両辺 $1$ で成り立つ。$i$ について掛け、各列の和が $1$ であることを使うと
$$
\operatorname{cap}(q_{n-1})\ge\prod_i(1-a_i)^{1-a_i}
$$
である。$h(s):=s\log s$($h(0)=0$)は $[0,1]$ で狭義凸で、$1-a_i$ の平均は $(n-1)/n$ である。よって右辺は $\bigl(\frac{n-1}n\bigr)^{n-1}=g(n)$ 以上で、等号は $a_i$ がすべて等しいときに限る。
一方、prf-vdw-column の連鎖を $i=n-1,\dots,1$ だけ掛けると、$\operatorname{per}A\ge\operatorname{cap}(q_{n-1})\prod_{i< n}g(i)$ である。$\operatorname{per}A=\prod_{i\le n}g(i)$ なので $\operatorname{cap}(q_{n-1})\le g(n)$ である。したがって上の評価はすべて等号で、$a_i$ はすべて等しく、$1/n$ である。どの列についても同じなので $A=J_n$ である。$\square$
cor-vdw-column は Gur08 Theorem 2.4、LS10 Corollary 1a の形で、等号の部分は LS10 Corollary 1d の議論による。二重確率行列 の記事の Sinkhorn の定理と合わせると、成分が正の行列 $A$ について $\operatorname{per}A/\operatorname{cap}(p_A)$ は $n!/n^n$ 以上 $1$ 以下にある。
各行・各列の和が $k\ge1$ である $0$ 以上の整数の $n$ 次行列を $A$ とする($k$-正則な二部多重グラフの隣接の表である)。このとき
$$
\operatorname{per}A\ge k^n\prod_{i=1}^ng(\min(i,k))\ge\Bigl(\frac{(k-1)^{k-1}}{k^{k-2}}\Bigr)^n
$$
である($k=1$ の右辺の底は $1$ と読む)。
$B:=A/k\in\Omega_n$ で、各列の正の成分は高々 $k$ 個である。cor-vdw-column と $g$ の単調性から第 1 の不等式を得る。$g(\min(i,k))\ge g(k)$ なので右辺は $(k\,g(k))^n$ 以上で、$k\,g(k)=(k-1)^{k-1}/k^{k-2}$ である。$\square$
第 2 の不等式の形は Schrijver の定理(Sch98)で、第 1 の形は Gur08 §2.1 の式 (18) による(第 2 の形の導出は LS10 Corollary 1c)。$k=3$ の第 1 の形は Voorhoeve の下界 $6(4/3)^{n-3}$($n\ge3$)である。van der Waerden の下界から直接出るのは $k^nn!/n^n$ で、$n$ が大きいと底は $k/e$ であるのに対し、上の底は $k\,g(k)>k/e$ である。
巡回行列(第 $i$ 行の $1$ の位置が $i,i+1,\dots$、番号は $n$ で割った余り)で比べる。第 1 の下界は小数第 2 位までに丸めた。
| $n$ | $k$ | $\operatorname{per}A$ | 第 1 の下界 | 第 2 の下界 |
|---|---|---|---|---|
| $8$ | $2$ | $2$ | $2$ | $1$ |
| $3$ | $3$ | $6$ | $6$ | $2.37$ |
| $4$ | $3$ | $9$ | $8$ | $3.16$ |
| $5$ | $3$ | $13$ | $10.67$ | $4.21$ |
| $7$ | $3$ | $31$ | $18.96$ | $7.49$ |
$k=2$ の $\operatorname{per}A=2$ と $n=k=3$ の $6$ は第 1 の下界に一致する。$n=7$、$k=3$ でも、Fano 平面の点と直線の接続行列なら $\operatorname{per}=24$ で、値は行列によって変わる。
上界については、行和がすべて $1$ 以上の $0,1$ 行列のパーマネントを行和で抑える Bregmanの定理 $\operatorname{per}A\le\prod_i(r_i!)^{1/r_i}$ がある。正則の場合は上界の底が $(k!)^{1/k}$ で、$k$ が大きいと上の底 $k\,g(k)$ とともに $k/e$ に近づく。
| 外す条件 | 反例 | 成り立たなくなるもの |
|---|---|---|
| 各列の和が $1$ | $\begin{pmatrix}1&0\\1&0\end{pmatrix}$:成分は $0$ 以上、行の和は $1$ だが、$\operatorname{per}=0$ | thm-vdw-main の不等式 |
| 成分が $0$ 以上 | $\begin{pmatrix}1&1&-1\\1&-1&1\\-1&1&1\end{pmatrix}$:各行・各列の和は $1$ だが、$\operatorname{per}=-2$ | thm-vdw-main の不等式 |
| H 安定 | $p=x_1^2+x_2^2$:斉次で係数は $0$ 以上、容量は $2$ だが、$z=(e^{i\pi/4},e^{-i\pi/4})$ で $p(z)=0$ | thm-vdw-cap の不等式 |
第 3 行では $p'=0$($x_2$ の 1 次の項がない)で、$k=2$ の不等式は $0\ge\frac12\cdot2$ となって成り立たない。
| 誤り | 正しくは |
|---|---|
| 頂点の置換行列で $\operatorname{per}$ が最小になる | 置換行列では $\operatorname{per}=1$ で最大である。最小は重心の $J_n$ でとる |
| 容量の不等式は係数が $0$ 以上の斉次多項式ならよい | H 安定が本質的で、上の反例で成り立たない |
| 下界は $n$ だけで決まり、$0$ の成分の配置は効かない | cor-vdw-column のとおり、列の正の成分が少ないほど下界は良くなる(ex-vdw-regular) |
元の証明との関係. Egorychev・Falikman の証明は Alexandrov の不等式と最適化の議論を組み合わせる(Gur08 §1.1)。行列のパーマネントについての Alexandrov の不等式は、$0$ 以上の列ベクトルについて
$$
\operatorname{per}(a_1,a_2,a_3,\dots,a_n)^2\ge\operatorname{per}(a_1,a_1,a_3,\dots,a_n)\operatorname{per}(a_2,a_2,a_3,\dots,a_n)
$$
である(Huh18 §2.1)。これは 混合体積 の記事にある Aleksandrov–Fenchel の不等式と同じ形で、Hodge–Riemann の関係式の特別な場合として位置づけられる。Gurvits の証明はこれらを使わず、帰納の中で「$q_i$ の H 安定性」という情報だけを保つ。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する