Feit–Higmanの定理

同義語:Feit-Higmanの定理Feit–Higman theorem

概要

Feit–Higmanの定理(Feit–Higman theorem)とは、各直線に $s+1$ 個の点、各点に $t+1$ 本の直線がある有限の一般化 $n$ 角形(点と直線の接続グラフが直径 $n$、内周 $2n$ の連結な二部グラフであるもの)で $s\ge2$、$t\ge2$ のものは、$n\in\{2,3,4,6,8\}$ の場合に限るという定理である。$n\ge3$ のとき、$n$ が偶数なら点の共線グラフ、奇数なら接続グラフが距離正則グラフになり、その固有値と重複度は余弦を含む明示的な式で与えられる。重複度が有理数であることと、$\cos(2\pi/m)$ が有理数になる $m$ が限られることから $n$ が絞られる。

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

前提知識: 二部グラフ, 距離正則グラフ, 射影平面, 代数的整数

Feit–Higmanの定理(Feit–Higman theorem)とは、各直線が $s+1$ 個の点を、各点が $t+1$ 本の直線をもつ有限の一般化 $n$ 角形で $s\ge2$、$t\ge2$ のものは、$n\in\{2,3,4,6,8\}$ の場合にしか存在しない、という定理である。
一般化 $n$ 角形は、点と直線の接続関係で、その接続グラフ(点と直線を頂点とし、接続する点と直線を辺で結んだ二部グラフ)が直径 $n$、内周(最短の閉路の長さ)$2n$ をもつものである。$n=3$ は射影平面にあたる。通常の $n$ 角形($n$ 個の頂点と $n$ 本の辺)はどの $n$ についても一般化 $n$ 角形で、$s=t=1$ である。W. Feit と G. Higman が 1964 年に示した(FH64)。BH11 Theorem 12.7.2(p. 178)も、証明が固有値の重複度の有理性の条件による旨を述べている。
この記事では、$n$ が偶数なら点の共線グラフ、奇数なら接続グラフが共通の形の距離正則グラフになることを示し、その固有値の重複度が有理数であることから $n$ を絞る。

結果内容扱い
prop-fh-arrays共線グラフ・接続グラフが型 $(s,t,d)$ の距離正則グラフになる証明
thm-fh-spectrum型 $(s,t,d)$ の固有値と重複度証明
thm-fh-main$s,t\ge2$ なら $n\in\{2,3,4,6,8\}$証明

定義

接続構造 とは、点の集合 $\mathcal P$ と直線の集合 $\mathcal L$(互いに交わらない空でない集合)と、関係「点 $p$ が直線 $\ell$ の上にある」の組である。接続グラフ $\Gamma$ は $\mathcal P\cup\mathcal L$ を頂点とし、$p$ が $\ell$ の上にあるとき $p$ と $\ell$ を辺で結んだ二部グラフである。$\Gamma$ の 2 頂点の距離を $d(x,y)$ と書く(距離(グラフ))。

一般化 $n$ 角形

$n\ge2$ とする。有限の接続構造が 一般化 $n$ 角形 であるとは、接続グラフ $\Gamma$ が連結で、直径が $n$、内周が $2n$ であることをいう。さらに整数 $s,t\ge1$ があって、各直線の上にちょうど $s+1$ 個の点があり、各点を通る直線がちょうど $t+1$ 本あるとき、位数 $(s,t)$ をもつという。

$n=2$ では、内周 $4$・直径 $2$ の連結な二部グラフは完全二部グラフなので、すべての点がすべての直線の上にある。$n=3$ では、相異なる 2 点を通る直線がちょうど 1 本あり、2 直線はちょうど 1 点で交わる。

短い道の一意性

$\Gamma$ を一般化 $n$ 角形の接続グラフとし、頂点 $x,y$ について $j:=d(x,y)$ とする。

  1. $j< n$ なら、$y$ の隣接頂点のうち $x$ からの距離が $j-1$ のものはちょうど 1 個で、残りの隣接頂点の距離は $j+1$ である($j=0$ なら、すべての隣接頂点の距離が $1$ である)。
  2. $j=n$ なら、$y$ の隣接頂点の $x$ からの距離はすべて $n-1$ である。

$z$ が $y$ に隣接するなら $|d(x,z)-j|\le1$ であり、$\Gamma$ は二部グラフなので $d(x,z)$ と $j$ の偶奇は異なる。よって $d(x,z)\in\{j-1,j+1\}$ である。
1:$j\ge1$ とする。$x$ から $y$ への長さ $j$ の道の、$y$ の直前の頂点は距離 $j-1$ にある。距離 $j-1$ の隣接頂点 $z\ne z'$ が 2 つあれば、$x$ から $z$ を経て $y$ に至る長さ $j$ の道と、$z'$ を経て $y$ に至る長さ $j$ の道は、最後の辺が異なる 2 つの道である。同じ端点をもつ相異なる 2 つの道を合わせると長さ $2j$ 以下の閉路が含まれ、$2j< 2n$ は内周に反する。
2:直径が $n$ なので $d(x,z)\le n$ であり、$d(x,z)=n-1$ である。$\square$

向かい合う頂点の次数

一般化 $n$ 角形の接続グラフ $\Gamma$ で $d(x,y)=n$ なら、$x$ と $y$ の次数は等しい。とくに $n$ が奇数で位数 $(s,t)$ をもつなら $s=t$ である。

$z$ を $y$ の隣接頂点とすると、lem-fh-paths の 2 により $d(x,z)=n-1< n$ なので、$x$ から $z$ への長さ $n-1$ の道はただ 1 つで、その $x$ の次の頂点を $f(z)$ とおく。$f$ は $y$ の隣接頂点の集合から $x$ の隣接頂点の集合への写像である。
$f$ が単射であることを示す。$z\ne z'$ で $f(z)=f(z')=w$ とする。$d(w,y)\ge d(x,y)-1=n-1$ であり、$w$ から $z$ を経て $y$ に至る道と、$z'$ を経て $y$ に至る道はどちらも長さ $(n-2)+1=n-1$ なので、$d(w,y)=n-1< n$ である。lem-fh-paths の 1 により $y$ の隣接頂点で $w$ からの距離が $n-2$ のものはただ 1 つなので $z=z'$ となり、矛盾する。よって $y$ の次数は $x$ の次数以下で、$x,y$ を入れ替えて等号を得る。
$n$ が奇数なら、直径 $n$ を実現する $x,y$ は距離が奇数なので一方が点、他方が直線であり、次数はそれぞれ $t+1$ と $s+1$ である。よって $s=t$ である。$\square$

距離正則グラフへの翻訳

距離正則グラフの記号は 距離正則グラフ の定義「距離正則グラフ」による。直径 $d$ の距離正則グラフで $x,y$ の距離が $i$ のとき、$y$ の隣接頂点のうち $x$ からの距離が $i-1$、$i$、$i+1$ のものの個数が $c_i$、$a_i$、$b_i$ である。

型 $(s,t,d)$ の交差配列

整数 $s,t\ge1$、$d\ge2$ について、交差配列
$$ b_0=s(t+1),\quad b_i=st\ (1\le i\le d-1);\qquad c_i=1\ (1\le i\le d-1),\quad c_d=t+1 $$
を 型 $(s,t,d)$ とよぶ。次数は $k=s(t+1)$ で、$a_i=k-b_i-c_i$ から $a_i=s-1$($1\le i\le d-1$)、$a_d=(s-1)(t+1)$ である。

距離正則グラフ の命題「距離 $i$ の頂点の個数」により、型 $(s,t,d)$ の距離正則グラフでは、距離 $i$ にある頂点の個数は
$$ k_i=s(t+1)(st)^{i-1}\quad(1\le i\le d-1),\qquad k_d=s^dt^{d-1} $$
である($k_{i+1}=b_ik_i/c_{i+1}$)。
点 $p,q$ は、ある直線の上にともにあるとき 共線 という。点の集合を頂点とし、相異なる共線な 2 点を辺で結んだグラフを 共線グラフ $\Delta$ という。

共線グラフと接続グラフの交差配列

位数 $(s,t)$ の一般化 $n$ 角形($n\ge3$)を考える。

  1. $n=2d$ が偶数なら、共線グラフ $\Delta$ は型 $(s,t,d)$ の距離正則グラフである。
  2. $n$ が奇数なら $s=t$ で、接続グラフ $\Gamma$ は型 $(1,s,n)$ の距離正則グラフである。

2:lem-fh-opposite により $s=t$ なので、$\Gamma$ のどの頂点の次数も $s+1$ である。$d(x,y)=i$ とすると、lem-fh-paths により、$1\le i< n$ なら $c_i=1$、$a_i=0$、$b_i=s$ で、$i=n$ なら $c_n=s+1$、$a_n=0$ である。これは型 $(1,s,n)$ の交差配列である。
1:$\Gamma$ の道は点と直線を交互にたどるので、点 $p,q$ について $\Delta$ での距離は $d(p,q)/2$ である。
点 $q$ の隣接頂点を数える。$q$ を通る $t+1$ 本の直線のそれぞれに $q$ 以外の点が $s$ 個ある。相異なる 2 直線が $q$ 以外の点を共有すると $\Gamma$ に長さ $4$ の閉路ができ、内周 $2n\ge6$ に反するので、これらの $s(t+1)$ 個の点は相異なる。よって $\Delta$ は次数 $k=s(t+1)$ の正則グラフである。
$\Delta$ での距離が $i$($1\le i\le d$)の点 $p,q$ をとる。$d(p,q)=2i$ である。
$2i< n$($i\le d-1$)の場合:lem-fh-paths の 1 により、$q$ を通る直線のうち $p$ から距離 $2i-1$ のものがただ 1 本 $\ell$ あり、残りの $t$ 本は距離 $2i+1< n$ にある。$\ell$ の上の $q$ 以外の点は、$\ell$ から見てただ 1 つが $p$ から距離 $2i-2$ で、残り $s-1$ 個は距離 $2i$ である。距離 $2i+1$ の直線 $m$ の上の点は、$q$ だけが距離 $2i$ で、残り $s$ 個は距離 $2i+2$ である。よって $c_i=1$、$a_i=s-1$、$b_i=st$ である。
$2i=n$($i=d$)の場合:lem-fh-paths の 2 により、$q$ を通る $t+1$ 本の直線はどれも $p$ から距離 $n-1$ にあり、それぞれの上で $p$ から距離 $n-2$ の点はただ 1 つ($q$ ではない)、残り $s-1$ 個は距離 $n$ である。よって $c_d=t+1$、$a_d=(s-1)(t+1)$ である。
$\Gamma$ の直径は $n$ なので $\Delta$ の直径は $d$ 以下であり、$b_i=st\ge1$($i\le d-1$)から距離 $d$ の点の対もある。以上で $\Delta$ は直径 $d$ で、交差数が点の対によらない。$\square$

型 $(1,s,n)$ の距離正則グラフは、型の定義の $d$ を $n$ にしたもので、奇数の $n$ の場合も偶数の場合と同じ計算に入る。

固有値と重複度

型 $(s,t,d)$ の距離正則グラフのスペクトル

型 $(s,t,d)$ の距離正則グラフの頂点数を $v$、隣接行列を $A$ とし、$q:=\sqrt{st}$ とおく。$A$ の相異なる固有値は
$$ k=s(t+1),\qquad -t-1,\qquad \theta_j=s-1+y_j,\quad y_j:=2q\cos\frac{\pi j}{d}\quad(1\le j\le d-1) $$
の $d+1$ 個であり、$\theta_j$ の重複度は
$$ m(\theta_j)=\frac{(t+1)v}{2d}\cdot g(y_j),\qquad g(y):=\frac{4st-y^2}{(s+t+y)(1+st-y)} $$
である。

標準列を三角関数で解く

段 1:固有値の条件. 距離正則グラフ の定理「距離正則グラフの固有値」により、$A$ の相異なる固有値は交差数の三重対角行列 $L$ の $d+1$ 個の相異なる固有値である。$\theta$ が $L$ の固有値であることは、$L$ の第 $0$ 行から第 $d-1$ 行で決まる標準列 $u_0=1,u_1,\dots,u_d$ が第 $d$ 行を満たすことと同値である(同記事の定理「Biggs の公式」の前の段落)。型 $(s,t,d)$ では
$$ ku_1=\theta,\qquad u_{i-1}+(s-1)u_i+st\,u_{i+1}=\theta u_i\ (1\le i\le d-1),\qquad (t+1)u_{d-1}+(s-1)(t+1)u_d=\theta u_d $$
である。中央の式を $i=d$ でも成り立たせるように $u_{d+1}$ を定めると、$u_{d-1}+(s-1)u_d=\theta u_d-st\,u_{d+1}$ なので、最後の式は $(t+1)(\theta u_d-st\,u_{d+1})=\theta u_d$、すなわち
$$ \theta u_d=s(t+1)\,u_{d+1}\qquad(1) $$
と同値である。
段 2:$k$ と $-t-1$. $\theta=k$ では $u_i=1$(すべての $i$)が漸化式を満たし、(1) も成り立つ。$\theta=-t-1$ では $u_i=(-1/s)^i$ が $ku_1=-(t+1)$ と $u_{i-1}+(s-1)u_i+st\,u_{i+1}=(-1/s)^{i-1}\bigl(1-\tfrac{s-1}s+\tfrac ts\bigr)=-(t+1)u_i$ を満たし、(1) の両辺は $-(t+1)u_d$ である。
段 3:$\theta_j$. $a:=\sqrt s$、$b:=\sqrt t$($q=ab$)とし、$0< \varphi< \pi$、$\zeta:=e^{i\varphi}$、$\theta:=s-1+q(\zeta+\zeta^{-1})=s-1+2q\cos\varphi$ とおく。$w_i:=q^iu_i$ とおくと、漸化式に $q^i$ を掛けて
$$ w_{i-1}+w_{i+1}=(\zeta+\zeta^{-1})\,w_i\qquad(1\le i\le d) $$
を得る。$\zeta\ne\zeta^{-1}$ なので、$w_i=\alpha\zeta^i+\beta\zeta^{-i}$($0\le i\le d+1$)と書け、$\alpha+\beta=w_0=1$、$\alpha\zeta+\beta\zeta^{-1}=w_1=qu_1=b\theta/(a(1+t))$ である。展開して確かめられる恒等式
$$ b\theta-a(1+t)\zeta^{-1}=(a+b\zeta)(q-\zeta^{-1})\qquad(2) $$
と、その $\zeta$ と $\zeta^{-1}$ を入れ替えた式により、
$$ \alpha=\frac{(a+b\zeta)(q-\zeta^{-1})}{a(1+t)(\zeta-\zeta^{-1})},\qquad \beta=\frac{(a+b\zeta^{-1})(q-\zeta)}{a(1+t)(\zeta^{-1}-\zeta)}=\overline{\alpha} $$
である。(1) に $q^{d+1}$ を掛けて $a$ で割ると $b\theta\,w_d=a(1+t)\,w_{d+1}$ となり、(2) を使うと
$$ a(1+t)w_{d+1}-b\theta w_d=-\alpha\zeta^d(a+b\zeta^{-1})(q-\zeta)-\beta\zeta^{-d}(a+b\zeta)(q-\zeta^{-1})=-\frac{P\,(\zeta^d-\zeta^{-d})}{a(1+t)(\zeta-\zeta^{-1})} $$
である。ここで $y:=2q\cos\varphi$ として $P:=|a+b\zeta|^2|q-\zeta|^2=(s+t+y)(1+st-y)$ であり、$s+t+y>s+t-2q=(a-b)^2\ge0$、$1+st-y>(q-1)^2\ge0$ なので $P>0$ である。よって $\theta$ が固有値であることは $\zeta^{2d}=1$、すなわち $\varphi=\pi j/d$($1\le j\le d-1$)と同値で、$\theta_j$ は固有値である。
段 4:固有値はこれで全部. $\cos$ は $(0,\pi)$ で狭義単調減少なので $\theta_1,\dots,\theta_{d-1}$ は相異なる。$\theta_j+t+1=s+t+y_j>0$、$k-\theta_j=1+st-y_j>0$ なので、$k$、$-t-1$、$\theta_j$ は $d+1$ 個の相異なる固有値であり、$L$ の固有値はこれで全部である。
段 5:重複度. 距離正則グラフ の定理「Biggs の公式」により $m(\theta)=v/\sum_{i=0}^dk_iu_i^2$ である。$k_i$ の式から $k_iu_i^2=k_iw_i^2/(st)^i$ は、$1\le i\le d-1$ で $\frac{t+1}t w_i^2$、$i=d$ で $\frac1t w_d^2$ である。$\zeta^d=\zeta^{-d}=\pm1$ なので $w_d=\pm(\alpha+\beta)=\pm1$ で、$w_d^2=w_0^2=1$ だから
$$ \sum_{i=0}^dk_iu_i^2=\frac{t+1}t\sum_{i=0}^{d-1}w_i^2 $$
である。$\beta=\overline\alpha$ なので $w_i^2=2|\alpha|^2+2\operatorname{Re}(\alpha^2\zeta^{2i})$ であり、$\zeta^2\ne1$、$(\zeta^2)^d=1$ から $\sum_{i=0}^{d-1}\zeta^{2i}=0$ なので、$\sum_{i=0}^{d-1}w_i^2=2d|\alpha|^2$ である。$|\zeta-\zeta^{-1}|^2=4\sin^2\varphi$ から $|\alpha|^2=P/(4s(1+t)^2\sin^2\varphi)$ であり、$4st\sin^2\varphi=4st-y^2$ を使うと
$$ \sum_{i=0}^dk_iu_i^2=\frac{2d\,P}{(t+1)(4st-y^2)},\qquad m(\theta_j)=\frac{(t+1)v}{2d}\cdot\frac{4st-y_j^2}{(s+t+y_j)(1+st-y_j)} $$
を得る。$\square$

恒等式 (2) は、$\theta=a^2-1+ab(\zeta+\zeta^{-1})$ を代入すると両辺とも $a^2b-b+ab^2\zeta-a\zeta^{-1}$ になる。

主定理

有理数になる余弦

正の整数 $m$ について $\cos(2\pi/m)$ が有理数なら、$m\in\{1,2,3,4,6\}$ である。

多項式を $P_0=2$、$P_1=x$、$P_{k+1}=xP_k-P_{k-1}$ で定めると、$P_k$ は整数係数で、$k\ge1$ なら最高次の係数が $1$ の $k$ 次式であり、$P_k(\zeta+\zeta^{-1})=\zeta^k+\zeta^{-k}$ である($k$ についての帰納法。$(\zeta+\zeta^{-1})(\zeta^k+\zeta^{-k})=(\zeta^{k+1}+\zeta^{-k-1})+(\zeta^{k-1}+\zeta^{1-k})$ による)。$\zeta=e^{2\pi i/m}$ とすると $x_0:=2\cos(2\pi/m)$ は $P_m(x)-2$ の根である。$x_0=r/u$(既約分数、$u\ge1$)が有理数なら、$P_m(r/u)=2$ に $u^m$ を掛けると $r^m$ が $u$ で割り切れるので $u=1$ で、$x_0$ は整数である。$|x_0|\le2$ なので $2\cos(2\pi/m)\in\{-2,-1,0,1,2\}$ であり、$0<2\pi/m\le2\pi$ でこれを満たすのは $m=2,3,4,6,1$ である。$\square$

共役な固有値の重複度

$A$ を整数成分の実対称行列、$F$ をその固有多項式 $\chi_A$ の $\mathbb Q$ 上の最小分解体とする。$F$ の自己同型 $\sigma$ と $A$ の固有値 $\theta$ について、$\sigma(\theta)$ も $A$ の固有値で、重複度は等しい。また $\theta$ が有理数でなければ、$\sigma(\theta)\ne\theta$ となる $\sigma$ がある。

$A$ は対角化可能なので、固有値 $\theta$ の重複度は $\chi_A$ の根としての重複度に等しく、$\chi_A(x)=\prod_\theta(x-\theta)^{m(\theta)}$ である。$\chi_A$ は有理数係数なので、係数に $\sigma$ を施しても変わらず、$\chi_A(x)=\prod_\theta(x-\sigma(\theta))^{m(\theta)}$ である。$\sigma$ は単射なので、根 $\sigma(\theta)$ の重複度は $m(\theta)$ である。後半は、$F/\mathbb Q$ は Galois 拡大で、Galois群 の全体で固定される元は $\mathbb Q$ の元に限ることによる。$\square$

Feit–Higman の定理

位数 $(s,t)$ の有限の一般化 $n$ 角形で $s\ge2$、$t\ge2$ なら、$n\in\{2,3,4,6,8\}$ である。

重複度の有理性

$n\ge3$ とする。
$n$ が奇数の場合. prop-fh-arrays の 2 により $s=t$ で、接続グラフ $\Gamma$ は型 $(1,s,n)$ の距離正則グラフである。thm-fh-spectrum を $(s,t,d)=(1,s,n)$ で使うと、$Y:=y_1^2=4s\cos^2(\pi/n)$ について
$$ m(\theta_1)=\frac{(s+1)v}{2n}\cdot\frac{4s-Y}{(1+s)^2-Y} $$
である($v$ は $\Gamma$ の頂点数)。$m(\theta_1)$ と $\frac{(s+1)v}{2n}$ は正の有理数なので、$r:=\frac{4s-Y}{(1+s)^2-Y}$ は有理数である。$r=1$ なら $(1+s)^2=4s$ となり $s=1$ に反するので、$Y=\frac{r(1+s)^2-4s}{r-1}$ は有理数である。$Y=2s\bigl(1+\cos(2\pi/n)\bigr)$ なので $\cos(2\pi/n)$ は有理数で、lem-fh-cos により $n$ は $1,2,3,4,6$ のどれかである。$n$ は $3$ 以上の奇数なので $n=3$ である。
$n=2d$ が偶数の場合. prop-fh-arrays の 1 により共線グラフ $\Delta$ は型 $(s,t,d)$ で、thm-fh-spectrum により $m(\theta_j)=C\,g(y_j)$、$C:=\frac{(t+1)v}{n}>0$ である($v$ は点の個数)。
段 1:$g(y)=g(y')$ の言い換え。$E:=(s+t)(1+st)$、$B:=(s-1)(t-1)$、$A:=E-4st=s(t-1)^2+t(s-1)^2$ とし、$g(y)=N(y)/D(y)$、$N(y):=4st-y^2$、$D(y):=(s+t+y)(1+st-y)$ と書く。$D(y)=E+By-y^2=A+By+N(y)$ なので、$N(y)N(y')$ の項が打ち消し合って
$$ N(y)D(y')-N(y')D(y)=A\bigl(N(y)-N(y')\bigr)+B\bigl(y'N(y)-yN(y')\bigr)=(y'-y)\bigl[A(y+y')+B(4st+yy')\bigr] $$
である。$|y|,|y'|<2q$ では $D>0$ なので、$y\ne y'$ について $g(y)=g(y')$ は $A(y+y')+B(4st+yy')=0$ と同値である。$s,t\ge2$ なので $A>0$、$B>0$ である。
段 2:すべての $y_j$ は有理数である。$y_j$ が無理数とすると $\theta_j=s-1+y_j$ も無理数で、lem-fh-galois により $\sigma(\theta_j)\ne\theta_j$ となる $\sigma$ がある。$\sigma$ は有理数 $k$、$-t-1$ を固定する単射なので、$\sigma(\theta_j)$ はある $\theta_{j'}$($j'\ne j$)で、重複度が等しいから $g(y_{j'})=g(y_j)$、$\sigma(y_j)=y_{j'}$ である。段 1 と $|y_jy_{j'}|<4st$ から
$$ A(y_j+y_{j'})=-B(4st+y_jy_{j'})<0,\qquad y_j+y_{j'}<0 $$
である。一方 $y_{d-j}=-y_j$ も無理数で、$\sigma(-y_j)=-y_{j'}$ なので、同じ議論を $-y_j$ と $\sigma$ に当てると $(-y_j)+(-y_{j'})<0$ となり、矛盾する。
段 3:段 2 から $y_1^2=4st\cos^2(\pi/d)=2st\bigl(1+\cos(2\pi/d)\bigr)$ は有理数で、$\cos(2\pi/d)$ は有理数である。lem-fh-cos と $d\ge2$ から $d\in\{2,3,4,6\}$ である。$d=6$ なら $y_1=2q\cos(\pi/6)=\sqrt3\,q$ と $y_2=2q\cos(\pi/3)=q$ がともに有理数で $q>0$ なので、$\sqrt3$ が有理数となり矛盾する。よって $d\in\{2,3,4\}$、$n\in\{4,6,8\}$ である。$\square$

奇数の場合は重複度が $y^2$ の 1 次分数式なので、Galois の議論なしに $y_1^2$ の有理性が出る。

例

Fano 平面($n=3$)

Fano平面 は 7 点・7 直線で、各直線に 3 点、各点に 3 直線があり、位数 $(2,2)$ の一般化 $3$ 角形である。接続グラフ $\Gamma$ は 14 頂点の $3$ 正則グラフで、prop-fh-arrays の 2 により型 $(1,2,3)$ である。thm-fh-spectrum により固有値は $k=3$、$-3$、$y_1=2\sqrt2\cos(\pi/3)=\sqrt2$、$y_2=-\sqrt2$ で、
$$ m(\pm\sqrt2)=\frac{3\cdot14}{6}\cdot\frac{8-2}{9-2}=6 $$
である。共役な $\pm\sqrt2$ の重複度は等しい(lem-fh-galois)。

6 点の対による一般化 4 角形($n=4$)

6 点集合 $\{1,\dots,6\}$ の 2 元部分集合(15 個)を点、6 点を 3 つの 2 元部分集合に分ける分け方(15 個)を直線とし、2 元部分集合がその分け方の 1 つの組であるとき接続するとする。各直線に 3 点、各点に 3 直線がある($\{1,2\}$ を含む分け方は残りの 4 点の分け方 3 通り)。点が共線であることは、2 元部分集合が交わらないことである。これは位数 $(2,2)$ の一般化 $4$ 角形である。

確かめを開く

長さ $4$ の閉路はない。交わらない 2 つの対を含む分け方は、残りの対が決まるので 1 つだけだからである。長さ $6$ の閉路もない。どの 2 つも交わらない 3 つの対は 1 つの分け方をなし、1 本の直線の上にあるからである。点 $p$ と $p$ を通らない直線 $L$ について、$L$ の 3 つの対のうち $p$ と交わらないものはちょうど 1 つである($p$ の 2 元は $L$ の別々の対に入る)。これから点と直線の距離は $3$ 以下、直線どうしの距離は $4$ 以下である。交わる 2 つの対は、両方と交わらない対を経て距離 $4$ にある。最後に、$\{1,2\},\{3,4\},\{1,5\},\{3,6\}$ を順に結ぶ直線 $\{12,34,56\}$、$\{34,15,26\}$、$\{15,36,24\}$、$\{36,12,45\}$ は相異なり、長さ $8$ の閉路を与える。


共線グラフは型 $(2,2,2)$ で、thm-fh-spectrum から固有値は $6$、$\theta_1=1+4\cos(\pi/2)=1$、$-3$ であり、$m(1)=\frac{3\cdot15}{4}\cdot\frac{16}{4\cdot5}=9$、$m(-3)=15-1-9=5$ である。

位数 $(2,2)$ の一般化 5 角形の重複度

位数 $(2,2)$ の一般化 $5$ 角形があれば、接続グラフは型 $(1,2,5)$ の距離正則グラフで、距離正則グラフ の命題「距離 $i$ の頂点の個数」から頂点数は $1+3+6+12+24+16=62$ である。$Y=y_1^2=8\cos^2(\pi/5)=3+\sqrt5$ について
$$ m(\theta_1)=\frac{3\cdot62}{10}\cdot\frac{8-Y}{9-Y}=\frac{93}5\cdot\frac{5-\sqrt5}{6-\sqrt5}=15-\frac{3\sqrt5}5 $$
となり、整数でない。よってそのような一般化 $5$ 角形は存在しない。

反例

thm-fh-main は位数 $(s,t)$ について $s\ge2$、$t\ge2$ を、一般化 $n$ 角形の定義として「接続グラフの内周が $2n$」を仮定している。各行で 1 つだけを外す。

外す仮定例成り立たなくなる結論
$s\ge2$、$t\ge2$($s=t=1$ を許す)通常の 5 角形(5 点・5 辺)$n\in\{2,3,4,6,8\}$($n=5$ になる)
内周が $2n$(直径 $n$ だけを課す)5 点集合の 2 元部分集合を点、3 元部分集合を直線、包含を接続とする構造$n\in\{2,3,4,6,8\}$(直径 $5$、位数 $(2,2)$)
反例の確かめ

1 行目:接続グラフは 10 頂点の閉路 $C_{10}$(閉路グラフ)で、連結な二部グラフ、直径 $5$、内周 $10$ であり、各直線に 2 点、各点に 2 直線がある。よって位数 $(1,1)$ の一般化 $5$ 角形である。
2 行目:各 3 元部分集合は 2 元部分集合を 3 つ含み、各 2 元部分集合は 3 つの 3 元部分集合に含まれるので、位数 $(2,2)$ の条件を満たす。$\{1,2\},\{1,2,3\},\{1,3\},\{1,3,4\},\{1,4\},\{1,2,4\}$ は長さ $6$ の閉路なので、内周は $10$ でない。接続グラフは連結で直径 $5$ である。

直径の確かめを開く

接続グラフで $\{1,2\}$ から距離 $1,2,3,4,5$ にある頂点は、それぞれ $\{1,2\}$ を含む 3 元部分集合、$\{1,2\}$ とちょうど 1 元を共有する 2 元部分集合、$1,2$ の一方だけを含む 3 元部分集合、$\{1,2\}$ と交わらない 2 元部分集合、$\{3,4,5\}$ である。$\{1,\dots,5\}$ の置換は 2 元部分集合の全体に推移的に作用し、補集合をとる写像は 2 元部分集合と 3 元部分集合を入れ替えて接続を保つ($P\subset L$ と $L^c\subset P^c$ は同値)ので、どの頂点からの距離も $5$ 以下で、直径は $5$ である。

補足

関連する結果. BH11 Theorem 12.7.3(p. 178)は、Higman と Haemers–Roos による結果として、$s,t\ge2$ の一般化 $n$ 角形では $n=4,8$ なら $s\le t^2$、$t\le s^2$、$n=6$ なら $s\le t^3$、$t\le s^3$ が成り立つことを挙げている。同じ節(p. 178)は、直径 $3$ 以上の Mooreグラフ が閉路に限ることも、重複度の有理性から導かれる結果として並べている。

関連項目

参考文献

[1]
Walter Feit, Graham Higman, The nonexistence of certain generalized polygons, Journal of Algebra 1 (1964), no. 2, pp. 114–131, 1964
[2]
Andries E. Brouwer, Willem H. Haemers, Spectra of Graphs, Springer, 2012, 頁は著者公開版(2011-02-01)の頁。§12.7(p. 178):一般化 $m$ 角形と位数 $(s,t)$ の定義、共線グラフが直径 $\lfloor m/2\rfloor$ の距離正則グラフになること、Theorem 12.7.1(Moore グラフ)、Theorem 12.7.2(Feit–Higman の定理)、Theorem 12.7.3(Higman、Haemers–Roos の不等式)

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