van der Waerden予想(パーマネント)

同義語:van der Waerden予想Egorychev–Falikmanの定理van der Waerden conjecture

概要

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 による安定な多項式の容量を使う短い証明がある。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 二部グラフ, 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$ の元は 二重確率行列 の記事で詳しく扱う。

van der Waerden 予想(Egorychev–Falikman の定理)

$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$
2 次の場合

$\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$ 以上の実数のものを考える。

容量と H 安定

$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$ が残る)。

1 変数の不等式

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

H 安定性は保たれ、根は実数になる

$p\ne0$ を $x_1,\dots,x_m$ の係数が $0$ 以上の斉次多項式で、H 安定なものとする。

  1. $x_1,\dots,x_{m-1}>0$ なら、$t$ の多項式 $p(x_1,\dots,x_{m-1},t)$ の根はすべて $0$ 以下の実数である。
  2. $p'$ は $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$

容量の不等式(Gurvits)

$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 安定性」という情報だけを保つ。

関連項目

参考文献

[1]
Monique Laurent, Alexander Schrijver, On Leonid Gurvits's proof for permanents, The American Mathematical Monthly, 2010, pp. 903–911、Theorem 1、Corollary 1a–1d
[2]
Leonid Gurvits, Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all, The Electronic Journal of Combinatorics, 2008, #R66、§1、§2、Theorem 2.4
[3]
B. L. van der Waerden, Aufgabe 45, Jahresbericht der Deutschen Mathematiker-Vereinigung, 1926, p. 117
[4]
G. P. Egorychev, The solution of van der Waerden's problem for permanents, Advances in Mathematics, 1981, pp. 299–305
[5]
D. I. Falikman, Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix, Mathematical Notes of the Academy of Sciences of the USSR, 1981, pp. 475–479
[6]
June Huh, Combinatorial applications of the Hodge–Riemann relations, Proceedings of the International Congress of Mathematicians (Rio de Janeiro 2018), 2018, §2.1
[7]
Alexander Schrijver, Counting 1-factors in regular bipartite graphs, Journal of Combinatorial Theory, Series B, 1998, pp. 122–135

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する