グラフと素数：Erdős-Evansの定理 - フィボナッチ・フリーク

$0$ から $n-1$ までの整数から相異なる数 $a_1,\cdots,a_r$ を取り、「 $a_i-a_j$ が $n$ と互いに素なら $a_i,a_j$ を結ぶ」という規則で $a_i$ たちを頂点とするグラフを作ってみましょう。例えば $n=8$ として $0,1,2,5,7$ を選ぶと下のようなグラフが得られます（小さい数字は $|a_i-a_j|$ ）。

f:id:fibonacci_freak:20170728000103p:plain

グラフ $G$ をこのような方法で作ることができるとき、 $G$ は $\mathrm{mod}~n$ で表現可能であると言います。

ではどんなグラフが $\mathrm{mod}~n$ で表現可能なのでしょうか。

例えば $n$ を大きな素数として $0,1,\cdots,r-1$ を選べば完全グラフ $K_r$ を作ることができます。また $n=r!$ として $0,1,\cdots,r-1$ を選べば鎖状のグラフが得られます。

サイクルを作るのは少し難しいです。Twitterでこれを出題したところ、＠rudjereverisさんからとてもエレガントな解法を寄せて頂いたのでここで紹介します（私の想定解は間違っていることに後で気づきました…）。

大きな整数 $M$ をとって $n=3\times5\times7\times\cdots\times(2M+1)$ とします。すると考えている範囲で「 $n$ と互いに素 $\Leftrightarrow2$ 冪」としてよいことになります。このとき $0,1,3,7,\cdots,2^i-1, \cdots,2^r-1,2^r$ をとると、これは長さ $r+2$ のサイクルになっています。

さて、本題に入りましょう。実は次の驚くべき事実が成り立ちます！

定理(Erdős-Evans,1989). 任意のグラフはある $n$ に対し $\mathrm{mod}~n$ で表現可能である。

証明のために補題を準備します。

補題. 任意の正整数 $n$ について、 $n$ 個の素数からなる集合 $S$ で次の条件を満たすものが存在する:
【条件】共通部分を持たない任意の部分集合 $A,B\subset S$ について

$\displaystyle{\prod_{p\in A}p-\prod_{q\in B}q}$

は $\prod_{p\in S}p$ と互いに素。

証明. $n$ を固定し、条件を満たす $k$ 個の素数からなる集合で、全ての要素が $3^n$ 以上のもの $S_k$ を帰納的に構成していく。 $k=1$ の時は $3^n$ 以上の素数を任意に取れば良い。 $k\gt1$ の時、新たに加える素数 $p_k$ が満たすべき条件は

$\displaystyle{p_i\nmid p_k\prod_{p\in A}p-\prod_{q\in B}q}$

が任意の $1\leq i\lt k, A,B\subset S_{k-1}(A\cap B=\emptyset)$ に対し成り立つことである。 $p_i\in A$ なら必ず成り立つからそうでない場合のみ考えると、これは

$\displaystyle {p_k\not\equiv\frac{\prod_{q\in B}q}{\prod_{p\in A}p}~\mathrm{mod}~p_i}$

と同値である。右辺の組み合わせは高々 $3^{k-1}(\lt 3^n\leq p_i)$ 通りしかないので、これらをすべて満たす $\mathrm{mod}~p_i$ の剰余類が存在する。中国剰余定理によって $i$ をすべて合わせて考えれば、 $p_k$ はある等差数列中にあればよいことになる。よって算術級数定理より条件をみたす十分大きい $p_k$ を取ることができる。 $~~~\square$

それでは定理を示しましょう。

定理の証明. 表現したいグラフ $G$ に1つの頂点を加え、その補グラフ（辺で結ばれているかどうかを全て反転したグラフ）を $H$ とする。 $H$ の辺の数を $m$ とし、補題の条件を満たす $m$ 個の素数からなる集合 $S$ をとり、各辺に1つずつ素数を割り当てる。 $n=\prod_{p\in S}p$ とし、 $G$ の各頂点に対し「 $H$ で自分に繋がっている辺に割り当てられた素数の積」を選べばよい。 $~~~\square$

如何でしたでしょうか。この証明は美しいですが、算術級数定理を使っているところが少し残念かもしれません。もっと初等的に示せた方がいましたら、ぜひ教えてください。