2024-12-03

ソファ問題が解決！？

Yonsei UniversityのJineon Baekという人がプレプリントサーバ arXiv にソファ問題を解決したとするプレプリント"Optimality of Gerver’s Sofa"を投稿している。

119ページの大論文だ。

ソファ問題（英語では the moving sofa problem）と呼ばれる1966年来の未解決問題がある。

問題の設定はこうだ： $H_L:=(-\infty,1]\times [0,1]$ および $V_L:=[0,1]\times (-\infty,1]$ を用いて廊下 $L$ を $L:=H_L\cup V_L$ と定める。 $S\subset \mathbb{R}^2$ が移動ソファであるとは、 $S$ が「 $H_L$ の非空な連結閉部分集合であって、 $L$ 内における連続な剛体移動によって $V_L$ の部分集合に移せるような集合」の平行移動になっていることをいう。移動ソファの面積が取り得る最大値が存在することは示されている。その最大値を求めよ。

初出の論文は

Leo Moser. “Problem 66-11, Moving Furniture Through a Hallway”. In: SIAM Review 8.3 (1966), pp. 381–381.

問題となっている最大値を実現する移動ソファのことを最大面積移動ソファと呼ぶことにする。

Gerverという人が1992年に最大面積移動ソファの候補 $G$ を論文

Joseph L. Gerver. “On Moving a Sofa around a Corner”. In: Geometriae Dedicata 42.3 (June 1992), pp. 267–283.

で与えている。 $|G|=2.2195\cdots$ である（ $|S|$ で $S$ の面積を表す）。

Jineon BaekはGerverの仕事とRomikという人の2018年の論文

Dan Romik. “Differential Equations and Exact Solutions in the Moving Sofa Problem”. In: Experimental Mathematics 27.3 (July 3, 2018), pp. 316–330.

の内容をベースにして、「 $G$ は確かに最大面積移動ソファである」ことを証明したと今回宣言している。

プレプリントなので査読にはこれから時間がかかるのだろうと予想するが、とりあえず一見して怪しいかどうかをチェックすることはできる。

Jineon Baekという人物の経歴やこれまでの論文の確認および、プレプリント原稿をさらっと眺めた際に感じる品質からは「怪しくない」と期待できる。arXivのSubjectsもGeneral Mathematicsではない。
謝辞に出てくる人物達も期待を高める。

もちろんそれで正しいかは全くわからないが、この論文の規模であるから短時間で判定するのは無理だ。ただ、現時点で怪しくはないので中身が気になってくるし、証明の方針がどんなものかだけでも知りたい。

理解に誤りが含まれるだろうことはご了承いただいて、この記事には論文から読み取れる証明方針を簡単にまとめようと思う。時間ができたらどんどん追記するかもしれないし、しないかもしれない。

証明の前半では、最大面積移動ソファに「それを課しても一般性を失わない」ような条件を見出していく。つまり、移動ソファに関する条件Pについて、条件Pを満たすような最大面積移動ソファが必ず存在すると言えるのであれば、条件Pを課しても一般性を失わない。また、それらの条件は全てGerverの $G$ も共有する条件である。

まず、移動ソファ $S$ に対して、回転角 $\omega$ を付与させることができる。これは、 $L$ 内における $H_L$ から $V_L$ への移動を1つ考えた際の原点中心時計回りに回転する角度である。例えば、 $[0,1]^2$ は回転角 $0$ で移動させることができる移動ソファである。最大面積移動ソファを考察する場合には、 $\omega\in(0,\pi/2]$ と仮定してよいことが知られている。以下、仮定。

$u_t=(\cos t, \sin t)$ , $v_t=(-\sin t, \cos t)$ とベクトルの名前をつけておく。非空なコンパクト集合 $S\subset \mathbb{R}^2$ に対して、サポート関数 $h_S\colon \mathbb{R}/2\pi \mathbb{Z} \to \mathbb{R}$ を $h_S(t):=\mathrm{sup}\{s\cdot u_t \mid s \in S\}$ で定める。

回転角 $\omega$ を持つ移動ソファ $S$ が標準配置であるとは、 $h_S(\omega)=1$ が成り立つこととする。標準配置であることを仮定しても一般性を失わないので、以下仮定。

1つの重要な視点はソファを廊下の中で動かすのではなく、「ソファは固定して廊下を回転させる」というものである。 $R_t\colon\mathbb{R}^2\to\mathbb{R}^2$ を原点中心で反時計回りに $t\in\mathbb{R}$ だけ回転させる写像とする。すると、 $S$ が移動ソファであれば、各 $t\in[0,\omega]$ に対して、 $R_t(L)$ の平行移動 $L_t$ （回転した廊下）が存在して、 $S\subset L_t$ が成り立つことになる。このとき、 $S$ が $L_t$ の外壁にうまく接するような特別な $L_t$ を一意的に選べることがわかる。それを $L_S(t)$ と書く。

すると、 $H:=\mathbb{R}\times [0,1]$ , $V:=[0,1]\times\mathbb{R}$ , $V_{\omega}:=R_{\omega}(V)$ として、 $S$ は

$\displaystyle \mathcal{I}(S):=H\cap V_{\omega}\cap\bigcap_{t\in[0,\omega]}L_S(t)$

に含まれることがわかる。

ここで面白いのは、この「廊下が回転していった軌跡の共通部分」である $\mathcal{I}(S)$ をソファと思うことができることだ。もっと強く、「回転角 $\omega\in(0,\pi/2]$ を持つ標準配置の移動ソファ $S$ に対する $\mathcal{I}(S)$ は、それもまた回転角 $\omega$ を持つ標準配置の移動ソファである」ことが示される。この $\mathcal{I}(S)$ として実現される移動ソファのことを単調なソファと呼ぶ。 $S=\mathcal{I}(S)$ が成り立つことは、単調なソファであるための必要十分条件である。

1つ目の重要な結果は、最大面積移動ソファに単調なソファであることを課して良いということである。

$S$ が単調なソファであることを仮定すると、

$\displaystyle S=H\cap V_{\omega}\cap\bigcap_{t\in[0,\omega]}L_S(t)$

という表示を持つことになる。 $\Theta_{\omega,n}:=\{\frac{k}{n}\omega \mid 1\leq k < n\}$ とし、

$\displaystyle S_{\Theta_{\omega,n}}:=H\cap V_{\omega}\cap\bigcap_{t\in\Theta_{\omega,n}}L_S(t)$

と定めれば、 $S_{\Theta_{\omega,n}}$ は $S$ を離散近似した多角形型のソファとなる。

さて、多角形 $P$ について、距離が1であるような任意の平行な2直線 $l^+$ , $l^-$ に対して（全て同一平面内で考える）、「 $l^+$ 内にある $P$ の辺の長さの総和 = $l^-$ 内にある $P$ の辺の長さの総和」が成り立つとき、 $P$ はバランスが取れているという。

2つ目の重要な結果は、最大面積移動ソファに「 $S$ がバランスが取れている $S_{\Theta_{\omega,n}}$ の（適切な意味における）極限になっている」ということを課して良いということである。この条件を満たす $S$ をバランスが取れている最大面積移動ソファといい、以下仮定する。

3つ目の重要な結果は、最大面積移動ソファに「回転角 $\pi/2$ を持つ」と仮定して良いということである。以下、仮定する。

回転角 $\pi/2$ の単調なソファ $S$ は

$\displaystyle S=H\cap \bigcap_{t\in[0,\pi/2]}L_S(t)$

という表示を持つことになる。回転した廊下 $L_S(t)$ の内側のコーナー（ $L$ に対する $(0,0)$ に対応する点）を $\mathbf{x}(t)$ と表す。すると、 $\mathbf{x}\colon[0,\pi/2]\to\mathbb{R}^2$ は曲線を描くことになるが、4つ目の重要な結果は、バランスが取れている最大面積移動ソファに対して、 $\mathbf{x}$ は連続微分可能であり、

$\mathbf{x}'(t)\cdot u_t <0,\quad \mathbf{x}'(t)\cdot v_t>0$

が成り立つということだ。この示された性質（を精密化したもの）を単射性条件と呼ぶ。最大面積移動ソファに対しては単射性条件を仮定して良い。

単射性条件を満たすソファ $S$ に対して、 $S$ を太らせた領域 $R$ を構成する（ $R$ は移動ソファとは限らない）。この $R$ の面積を $\mathcal{Q}(S)$ と定めると、 $|S|\leq \mathcal{Q}(S)$ が成り立つ。

この $\mathcal{Q}$ の性質を詳らかにするために、 $R$ の構成を基にして、 $S$ から凸体のトリプル $(K,B,D)$ を更に構成する。

凸体のトリプルであって適当な条件を満たすもの全体からなる空間 $\mathcal{L}$ を定める。このとき、直前の構成は「これまでに最大面積移動ソファに課して良いことが判明した条件を全て満たす移動ソファ全体のなす集合 $\mathcal{S}$ 」から $\mathcal{L}$ への埋め込みを与えるようになっている。

そして、写像 $\mathcal{Q}\colon\mathcal{L}\to\mathbb{R}$ が定義される。これは、埋め込み $\mathcal{S}\hookrightarrow \mathcal{L}$ と合成するとさっきの $\mathcal{Q}$ と一致する。この新しく定義された $\mathcal{Q}$ が凸領域上の2次汎関数と呼ばれる良い条件を満たす写像になっているということが1つの重要な結果である。

さて、Gerverの $G$ を $\mathcal{L}$ に埋め込んだトリプルを $(K_G, B_G, D_G)$ と書こう。示すべきことは、 $\mathcal{Q}$ が $(K_G, B_G, D_G)$ で最大値をとることだ。なぜなら、 $G$ についての $R$ は $G$ に一致するため、 $S\in \mathcal{S}$ とそれに対応するトリプル $(K,B,D)$ に対して、

$\displaystyle |S|\leq |R|=\mathcal{Q}(K,B,D)\leq \mathcal{Q}(K_G, B_G, D_G)=|G|$

となって、最大面積移動ソファは $\mathcal{S}$ の元であると仮定してよかったのであるから、ソファ問題の解決となる。

この最大性をどうやって示すかであるが、 $\mathcal{Q}$ の $(K_G, B_G, D_G)$ から $(K,B,D)$ へ向かう方向微分

$\displaystyle D\mathcal{Q}(K_G,B_G,D_G;K,B,D)$

を定義することができ、 $\mathcal{Q}$ が凸領域上の2次汎関数であるということを使って、任意の $(K,B,D)\in\mathcal{L}$ に対して、

$\displaystyle D\mathcal{Q}(K_G,B_G,D_G;K,B,D)\leq 0$

を満たすことを示せば十分ということを示せる。よって、後は方向微分を計算する枠組みを構築し、それに基づいて計算して実際に非正になることを示せば終わりだ。

この計算の枠組みを作るために利用されるのが、Romikの結果である。Gerverの $G$ に対しては $L_G(t)$ の4つの外壁における接点 $\mathbf{A}(t)$ , $\mathbf{B}(t)$ , $\mathbf{C}(t)$ , $\mathbf{D}(t)$ が定まり、その結果5つの曲線 $\mathbf{A}, \mathbf{B}, \mathbf{C}, \mathbf{D}, \mathbf{x}$ が得られる。これら5つの曲線が満たす10個の常微分方程式をRomikが求めており、それを取り込むことが方向微分計算の1つの鍵となる。

みたいな感じかなと思った。

INTEGERS

数、特に整数に関する記事。

ソファ問題が解決！？