Bruck–Ryserの定理

同義語:Bruck-Ryserの定理Bruck–Ryser theorem

概要

Bruck–Ryserの定理(Bruck–Ryser theorem)とは、$n\equiv1,2\pmod4$ のとき、位数 $n$ の有限射影平面が存在するならば、$4$ で割って $3$ 余る素数はどれも $n$ を偶数乗で割り切る、すなわち $n$ は 2 つの整数の平方の和であるという定理である。これにより位数 $6,14,21,22$ などの射影平面は存在しない。接続行列の式 $NN^{\mathsf T}=nI+J$ を有理数の 2 次形式の等式とみて、四平方の恒等式で変数を取り替え 1 つずつ消すと $nX^2=1+W^2$ が残ることから証明され、対称デザインについての Bruck–Ryser–Chowla の定理に一般化される。

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

前提知識: 射影平面, 組合せデザイン, Lagrangeの四平方定理

有限射影平面には位数 $n$ があり、各直線に $n+1$ 個の点が乗り、点も直線も $n^2+n+1$ 個ある。$q$ が素数冪なら有限体 $\mathbb F_q$ の上の射影平面 $\mathbb P^2(\mathbb F_q)$ は位数 $q$ をもつので、位数 $2,3,4,5,7,8,9,\dots$ の射影平面は存在する。では、素数冪でない $n$ についてはどうか。Bruck–Ryser の定理(Bruck–Ryser theorem)は、この問いに対する次の否定的な答えである。

$n\equiv1,2\pmod4$ とする。位数 $n$ の射影平面が存在するならば、$4$ で割って $3$ 余る素数は $n$ をそれぞれ偶数乗で割り切る。言い換えると、$n$ は 2 つの整数の平方の和である。
たとえば $6=2\cdot3$、$14=2\cdot7$、$21=3\cdot7$、$22=2\cdot11$ はどれも $4$ で割って $1$ か $2$ 余り、$3,7,11$ を奇数乗で含むので、これらの位数の射影平面は存在しない。定理は R. H. Bruck と H. J. Ryser が 1949 年に証明した。
証明の考え方は、点と直線の接続行列 $N$ がみたす行列の式 $NN^{\mathsf T}=nI+J$($J$ はすべての成分が $1$ の行列)を 2 次形式の等式とみて、有理数の範囲で変数を 1 つずつ消すことにある。最後に残るのは $nX^2=1+W^2$ という等式で、$n$ が 2 つの有理数の平方の和であることを意味する。有理数の平方の和についての整数論で結論が出る。同じ議論は、射影平面を含む対称デザインに一般化される(Bruck–Ryser–Chowla の定理)。

名前と分担

射影平面 の記事は、有限射影平面の位数を定め、点と直線の個数を数えている。組合せデザイン の記事は、対称デザインの点の個数 $v$ が偶数の場合の条件($k-\lambda$ が平方数)を証明し、$v$ が奇数の場合の条件を主張だけ述べている。この記事は $v$ が奇数の場合を、射影平面について完全に証明し、対称デザインへの一般化も証明する。

有限射影平面と接続行列

位数 $n\ge2$ の射影平面の点を $P_1,\dots,P_v$、直線を $\ell_1,\dots,\ell_v$($v:=n^2+n+1$)と番号付け、$P_i$ が $\ell_j$ の上にあるとき $1$、そうでないとき $0$ を $(i,j)$ 成分とする $v\times v$ 行列 $N$ を 接続行列 という(射影平面 の定理「有限射影平面の位数」により点と直線の個数は等しい)。

接続行列の式

位数 $n$ の射影平面の接続行列 $N$ について $NN^{\mathsf T}=nI+J$ である。

$(NN^{\mathsf T})_{ik}=\sum_jN_{ij}N_{kj}$ は、$P_i$ と $P_k$ の両方を通る直線の本数である。$i=k$ なら $P_i$ を通る直線の本数で $n+1$ であり、$i\ne k$ なら射影平面の公理により $1$ である。よって対角成分は $n+1$、ほかの成分は $1$ で、$NN^{\mathsf T}=nI+J$ である。$\square$

$\mathbb P^2(\mathbb F_2)$(Fano平面)と $\mathbb P^2(\mathbb F_3)$ の接続行列について、この式を計算機で確かめた。

2 つの補題

四平方の行列

整数 $a_1,a_2,a_3,a_4$ について
$$ M:=\begin{pmatrix}a_1&a_2&a_3&a_4\\-a_2&a_1&-a_4&a_3\\-a_3&a_4&a_1&-a_2\\-a_4&-a_3&a_2&a_1\end{pmatrix} $$
とおき $m:=a_1^2+a_2^2+a_3^2+a_4^2$ とすると、$MM^{\mathsf T}=mI$ である。とくに $m>0$ なら $M$ は正則で、$M^{-1}=\frac1mM^{\mathsf T}$ である。

証明を開く

各行の成分の平方和は $m$ である。異なる 2 行の内積は、成分ごとの積を順に足して、第 1・2 行で $-a_1a_2+a_2a_1-a_3a_4+a_4a_3=0$、第 1・3 行で $-a_1a_3+a_2a_4+a_3a_1-a_4a_2=0$、第 1・4 行で $-a_1a_4-a_2a_3+a_3a_2+a_4a_1=0$、第 2・3 行で $a_2a_3+a_1a_4-a_4a_1-a_3a_2=0$、第 2・4 行で $a_2a_4-a_1a_3-a_4a_2+a_3a_1=0$、第 3・4 行で $a_3a_4-a_4a_3+a_1a_2-a_2a_1=0$ である。どの計算も $a_i$ の符号によらない。$\square$

4 で割って 3 余る素数と 2 つの平方の和

$p$ を $p\equiv3\pmod4$ の素数とする。

  1. 整数 $a,b$ について $p\mid a^2+b^2$ なら $p\mid a$ かつ $p\mid b$ である。
  2. $a^2+b^2\ne0$ なら、$a^2+b^2$ を割り切る $p$ の最大の冪の指数は偶数である。

1:$p\nmid b$ とすると、$b$ は法 $p$ で逆元 $b'$ をもち、$t:=ab'$ は $t^2\equiv-1\pmod p$ をみたす。$p$ は奇数なので $-1\not\equiv1$ であり、$t^4\equiv1$ だから $t$ の法 $p$ での位数は $4$ である。乗法群 $(\mathbb Z/p\mathbb Z)^\times$ の位数は $p-1$ なので $4\mid p-1$ となり、$p\equiv3\pmod4$ に反する。よって $p\mid b$ で、$p\mid a^2$ から $p\mid a$ である。
2:$|a|+|b|$ についての帰納法による。$p\nmid a^2+b^2$ なら指数は $0$ である。$p\mid a^2+b^2$ なら 1 により $a=pa'$、$b=pb'$ と書け、$a^2+b^2=p^2(a'^2+b'^2)$ で $0<|a'|+|b'|<|a|+|b|$ だから、帰納法の仮定により指数は偶数である。$\square$

主定理

Bruck–Ryser の定理

$n\ge2$ を $n\equiv1$ または $n\equiv2\pmod4$ の整数とし、位数 $n$ の射影平面が存在するとする。このとき、$p\equiv3\pmod4$ のすべての素数 $p$ について、$n$ を割り切る $p$ の最大の冪の指数は偶数である。同じことだが、$n$ は 2 つの整数の平方の和である。

変数を 1 つずつ消す

$v:=n^2+n+1$ とし、$N$ を接続行列とする。$n\equiv1$ なら $v\equiv1+1+1=3$、$n\equiv2$ なら $v\equiv4+2+1\equiv3\pmod4$ である。
2 次形式の等式. 有理数の行ベクトル $x=(x_1,\dots,x_v)$ に対し $y:=xN$、すなわち $y_j:=\sum_ix_iN_{ij}$($\ell_j$ の上の点の $x_i$ の和)とおく。lem-br-incidence により
$$ \sum_{j=1}^vy_j^2=xNN^{\mathsf T}x^{\mathsf T}=n\sum_{i=1}^vx_i^2+w^2,\qquad w:=\sum_{i=1}^vx_i $$
である。新しい変数 $x_{v+1}$ を加え、両辺に $nx_{v+1}^2$ を足すと、$m:=v+1$ について、すべての $x\in\mathbb Q^m$ で次の等式(E1)が成り立つ。
$$ \sum_{j=1}^vy_j^2+nx_{v+1}^2=n\sum_{i=1}^mx_i^2+w^2 $$
四平方で変数を取り替える. Lagrangeの四平方定理 により $n=a_1^2+a_2^2+a_3^2+a_4^2$ となる整数がある。lem-br-four の行列 $M$ を使い、$m\equiv0\pmod4$ なので $x$ を 4 個ずつの組 $x^{(1)},\dots,x^{(m/4)}$ に分けて、$z^{(b)}:=x^{(b)}M$ とおく。$x^{(b)}=\frac1nz^{(b)}M^{\mathsf T}$ なので、$x\mapsto z$ は $\mathbb Q^m$ の全単射であり、
$$ \sum_{i=1}^mz_i^2=\sum_bx^{(b)}MM^{\mathsf T}x^{(b)\mathsf T}=n\sum_{i=1}^mx_i^2 $$
である。$x$ の各成分は $z$ の有理数係数の一次式なので、$y_j$、$x_{v+1}$、$w$ も $z$ の一次式であり、(E1)はすべての $z\in\mathbb Q^m$ で成り立つ次の等式(E2)になる。
$$ \sum_{j=1}^vy_j^2+nx_{v+1}^2=\sum_{i=1}^mz_i^2+w^2 $$
変数を消す. $j=1,2,\dots,v$ の順に、$z_j$ を $z_{j+1},\dots,z_m$ の有理数係数の一次式で置き換えて、置き換えた後に $y_j=\pm z_j$ となるようにする。$z_1,\dots,z_{j-1}$ をすでに置き換えたとすると、$y_j$ は $z_j,\dots,z_m$ の一次式なので $y_j=cz_j+R$($c\in\mathbb Q$、$R$ は $z_{j+1},\dots,z_m$ の一次式)と書ける。

  • $c\ne1$ なら $z_j:=R/(1-c)$ とおく。このとき $y_j=cR/(1-c)+R=R/(1-c)=z_j$ である。
  • $c=1$ なら $z_j:=-R/2$ とおく。このとき $y_j=-R/2+R=R/2=-z_j$ である。
    $v$ 回の置き換えの後、$z_1,\dots,z_v$ はすべて $z_m$ の有理数倍になり、したがって $x_{v+1}$ と $w$ も $z_m$ の有理数倍になる。$z_m:=1$ とおくと、すべての変数が有理数の値をとり、(E2)はこの値でも成り立つ。$j\le v$ では $y_j^2=z_j^2$ なので両辺から消え、$X:=x_{v+1}$、$W:=w$ の値について
    $$ nX^2=1+W^2 $$
    が残る。右辺は $1$ 以上なので $X\ne0$ である。

整数論で仕上げる. $X,W$ を共通の分母 $t>0$ で $X=s/t$、$W=u/t$($s,u$ は整数、$s\ne0$)と書き、$nX^2=1+W^2$ に $t^2$ を掛けると $ns^2=t^2+u^2$ である。$p\equiv3\pmod4$ の素数について、右辺は $0$ でないので lem-br-two-squares の 2 により右辺の $p$ の指数は偶数で、左辺の $s^2$ の $p$ の指数も偶数だから、$n$ の $p$ の指数は偶数である。後半の言い換えは、Fermatの二平方定理 の記事の定理「二つの平方数の和で書ける整数の判定」による。$\square$

証明の所在と由来

定理は BR49 の Theorem 1(p. 88)で、そこでは「$n\equiv1,2\pmod4$ で、$n$ の平方因子を除いた部分が $4k+3$ の形の素因数を含めば、位数 $n$ の射影平面は存在しない」という形で述べられている。平方因子を除いた部分が $p$ で割り切れることと、$p$ の指数が奇数であることは同じである。同論文の証明は、有理数体上の 2 次形式の同値についての Minkowski–Hasse の理論(Hasse–Minkowskiの定理)を使う。上の証明は、CR50 の Theorem 4・5(pp. 96–98)の証明の方法(四平方の恒等式と、変数を 1 つずつ消す議論)を射影平面の場合に書いたもので、CR50 は自分たちの定理が射影平面については新しい情報を与えないこと、証明が Minkowski–Hasse の理論によらないことを述べている(p. 96)。

証明は有理数の範囲でしか議論していない。したがって、成分が有理数の $v\times v$ 行列 $N$ で $NN^{\mathsf T}=nI+J$ となるものがあるだけで、同じ結論が出る。$n=2$ の Fano平面 と $n=5$ の $\mathbb P^2(\mathbb F_5)$ について、上の置き換えの手順を分数の計算で実行し、$nX^2=1+W^2$ を満たす有理数が実際に得られることを確かめた($n=2$ では $X=1$、$W=-1$)。

例:位数 $30$ までの判定

素数冪 $q$ の位数の射影平面 $\mathbb P^2(\mathbb F_q)$ と、thm-br-main で除かれる位数を並べる。

$n$$n \bmod 4$判定$n$$n \bmod 4$判定
2–5素数冪(存在する)182$9+9$、除かれない
62除かれる($3^1$)193素数冪
7, 8, 9素数冪200除かれない
102$1+9$、除かれない211除かれる($3^1,7^1$)
113素数冪222除かれる($11^1$)
120除かれない233素数冪
131素数冪240除かれない
142除かれる($7^1$)25, 27, 29素数冪
153除かれない262$1+25$、除かれない
16, 17素数冪280除かれない
302除かれる($3^1$)

「除かれない」は定理の仮定が成り立たないか、結論が成り立つことを意味し、射影平面の存在を意味しない。素数冪の位数で定理と矛盾するものはない(たとえば $n=9\equiv1$ は $0+9$、$n=13$ は $4+9$)。$n=3,7,11,19,23,27$ は $4$ で割って $3$ 余り、定理の仮定を満たさないので、2 つの平方の和でなくても矛盾しない。位数 $6$ の射影平面が存在しないことは BR49 の時点ですでに知られており(同論文 p. 88 が引用している)、定理はそれを含む。表の判定は計算機でも確かめた。

直交ラテン方陣の完全な組

$n$ が thm-br-main で除かれる位数なら、位数 $n$ の互いに直交する $n-1$ 個のラテン方陣は存在しない。たとえば $n=6,14,21,22,30$ でそうである。

そのような $n-1$ 個のラテン方陣があれば、ラテン方陣 の記事の定理「射影平面の構成」により位数 $n$ の射影平面が存在し、thm-br-main に反する。$\square$

この系は BR49 p. 88 にも述べられている。

対称デザインへの一般化

射影平面は、点の個数 $v=n^2+n+1$、ブロック(直線)の大きさ $k=n+1$、$\lambda=1$ の対称 2-$(v,k,\lambda)$ デザインである(組合せデザイン の定義「対称デザイン」)。対称デザインの接続行列は $NN^{\mathsf T}=(k-\lambda)I+\lambda J$ をみたす(同記事の節「接続行列と対称デザイン」。対称デザインでは各点を含むブロックの個数が $k$ に等しい)。

Bruck–Ryser–Chowla の定理

対称 2-$(v,k,\lambda)$ デザインが存在し、$v$ が奇数ならば、
$$ z^2=(k-\lambda)x^2+(-1)^{(v-1)/2}\lambda y^2 $$
は $(x,y,z)\ne(0,0,0)$ の整数解をもつ。

証明を開く

$n':=k-\lambda$ とおく。prf-br-main と同じく $y:=xN$、$w:=\sum_ix_i$ とすると $\sum_jy_j^2=n'\sum_ix_i^2+\lambda w^2$ である。$n'$ を 4 つの平方の和に書き、lem-br-four の行列で 4 変数ずつ取り替える。

$v\equiv3\pmod4$ のとき:変数 $x_{v+1}$ を加えて両辺に $n'x_{v+1}^2$ を足し、$x_1,\dots,x_{v+1}$ を取り替えると $\sum_{j\le v}y_j^2+n'x_{v+1}^2=\sum_{i\le v+1}z_i^2+\lambda w^2$ となる。prf-br-main と同じ手順で $z_1,\dots,z_v$ を消し、$z_{v+1}=1$ とおくと、有理数 $X,W$ で $n'X^2=1+\lambda W^2$、すなわち $1^2=n'X^2-\lambda W^2$ を得る。分母を払えば $z\ne0$ の整数解になる。$(v-1)/2$ は奇数なので符号は $-$ である。

$v\equiv1\pmod4$ のとき:$x_1,\dots,x_{v-1}$ を取り替え、$z_v:=x_v$ とおくと $\sum_{j\le v}y_j^2=\sum_{i\le v-1}z_i^2+n'z_v^2+\lambda w^2$ となる。$z_1,\dots,z_{v-1}$ を同じ手順で消して $y_1^2,\dots,y_{v-1}^2$ を打ち消し、$z_v=1$ とおくと、有理数 $Y,W$ で $Y^2=n'\cdot1^2+\lambda W^2$ を得る。分母を払えば $x\ne0$ の整数解になる。$(v-1)/2$ は偶数なので符号は $+$ である。$\square$

射影平面($\lambda=1$、$k-\lambda=n$)で $v\equiv3\pmod4$ なら、方程式は $nx^2=y^2+z^2$ となり、prf-br-main の最後の段落と同じ議論で thm-br-main が出る。$v\equiv1\pmod4$($n\equiv0,3\pmod4$)なら方程式は $z^2=nx^2+y^2$ で、$(x,y,z)=(0,1,1)$ という解がいつもあるので、射影平面については何も除かない。CR50 の Theorem 4・5(pp. 96–98)は、この方程式の可解性を Legendre 記号で判定できる一部の場合について、同じ方法で非存在を示したものである。

存在しない対称デザイン $(29,8,2)$

$(v,k,\lambda)=(29,8,2)$ は $\lambda(v-1)=56=k(k-1)$ をみたし、$v$ は奇数である。$v\equiv1\pmod4$ なので方程式は $z^2=6x^2+2y^2$ である。自明でない整数解があるとして、$\gcd(x,y,z)=1$ のものをとる。法 $3$ で $z^2\equiv2y^2$ であり、平方は法 $3$ で $0$ か $1$ なので $3\mid y$、$3\mid z$ である。すると $9\mid z^2-2y^2=6x^2$ から $3\mid x$ となり、最大公約数が $1$ であることに反する。よって thm-br-brc により対称 2-$(29,8,2)$ デザインは存在しない。

反例の表

外す条件例成り立たなくなること
$n\equiv1,2\pmod4$$\mathbb P^2(\mathbb F_3)$($n=3$)$n$ が 2 つの平方の和
$N$ の成分が有理数(証明が使う範囲)$NN^{\mathsf T}=6I+J$ をみたす $43\times43$ の実行列「$NN^{\mathsf T}=nI+J$ をみたす行列があれば $n$ は 2 つの平方の和」
反例の確認

1 行目:$\mathbb P^2(\mathbb F_3)$ は位数 $3$ の射影平面である(射影平面 の記事)。$3$ は $4$ で割って $3$ 余るので 2 つの平方の和でない(Fermatの二平方定理 の記事の命題「4で割って3余る整数」)。この場合 $v=13\equiv1\pmod4$ で、証明で $x_{v+1}$ を加えて 4 の倍数個の変数にそろえる段が成り立たない。
2 行目:$6I+J$ は対称で、固有値は $6$($J$ の核の上)と $6+43=49$(すべての成分が $1$ のベクトルの上)で、どれも正である。よって正定値で、実対称行列の平方根 $N:=(6I+J)^{1/2}$ をとれば $NN^{\mathsf T}=6I+J$ である。$6$ は 2 つの平方の和でない。証明は $x$ と $z$ を有理数の範囲で選ぶ(実数の範囲ではどんな正の数も $1$ 個の平方なので、変数を消した最後の等式から情報が出ない)ことに $N$ の有理性を使っている。

関連項目

参考文献

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