フィボナッチ・フリーク

数学の小ネタ集。

グラフと素数:Erdős-Evansの定理

0からn-1までの整数から相異なる数a_1,\cdots,a_rを取り、「a_i-a_jnと互いに素なら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

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