完全差集合のつくり方

Cyclic Difference Sets - by Kris Coolsaetを眺めていると、「How to make perfect CDSs（完全差集合のつくり方）」と題されたところがあったので、気になって読んでみた。それまでのページをしっかりと読んでいないので、理屈がわからないところもあるが、おおよそ以下の内容である。

まず、ひとつの数列をつくる。初項 \( 0 \) からはじまり、第2項も \( 0 \) 、第3項は \( 1 \) 、第4項以降は前の3項を足した数でつくる数列である。具体的に書くと、次の数列である。
$$
0 \quad 0 \quad 1 \quad 1 \quad 2 \quad 4 \quad 7 \quad 13 \quad 24 \quad 44 \quad 81 \quad 149 \quad 274 \quad 504 \quad 927 \quad \cdots
$$
そして、この数列を \( mod \ p \) で書く。\( p \) は素数である。たとえば \( mod \ 3 \) で、上の数列は次のようになる（ \( mod \ 3 \) は、\( 3 \) で割った余りのこと）。この数列で、\( 0 \) が2連続で続いているところの間に注目する。以下の数列では、初項と第2項で \( 0 \) が2連続し、次は14項目と15項目で \( 0 \) が2連続している。なので、この数列の初項から13項目までに注目する。
$$
0 \quad 0 \quad 1 \quad 1 \quad 2 \quad 1 \quad 1 \quad 1 \quad 0 \quad 2 \quad 0 \quad 2 \quad 1 \quad 0 \quad 0 \quad \cdots
$$
この数列の \( 0 \) の部分に印（下図では \( \sharp \) ）をつけて、印のついたナンバを見る。下図では、印のついたナンバは \( 0, 1, 8, 10 \) である。
$$
\begin{array}{lcrrrrrrrrrrrrrl}
sequence &:& 0 & 0 & 1 & 1 & 2 & 1 & 1 & 1 & 0 & 2 & 0 & 2 & 1 & ( 0 \quad 0 \ \cdots ) \\
marks &:& \sharp & \sharp & & & & & & & \sharp & & \sharp & & & \\
numbering &:& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & (13)
\end{array}
$$
この集合 \( \{ 0, 1, 8, 10 \} \) が、\( mod \ 13 \) での完全差集合となるということだ。理屈はあるようだが、僕はまだ理解していない。

最初につくった数列については、「linear recurrences of degree three」（3次の線形再帰？）と呼ばれている。フィボナッチ数列というものがあるが、フィボナッチ数列は、最初の2項が \( 0, 1 \) で、第3項以降の項はその直前の2つの項の和となっている数列である。最初につくった数列は、このフィボナッチ数列と似ており、最初の3項が \( 0, 0, 1 \) で、以降はその直前の3つの項の和となっている数列である。Wikipedia「フィボナッチ数」の項を見ていると、「トリボナッチ数（数列）」という名称があった。この数列の一般項を \( T_n \) とすると、
$$
T_0 = T_1 = 0, \qquad T_2 = 1 \\
T_{n+3} = T_n + T_{n + 1} + T_{n + 2} \qquad ( n \geqq 0)
$$
と表わされる。

最初の例では、素数 \( 3 \) を法としたトリボナッチ数列から、\( 13 \) を法としたサイズ \( 4 \) の完全差集合をつくった。一般的には、素数 \( p \) を法としたトリボナッチ数列から、\( p^2 + p + 1 \) を法としたサイズ \( p+1 \) の完全差集合がつくれるということだ。

これまで、5つのビリヤード玉の問題を考えるにあたり、完全差集合に行き当たった。5つのビリヤード玉の問題に関係する完全差集合としては、\( 21 \) を法とする、サイズ \( 5 \) の完全差集合である。単純に考えると、サイズ \( 5 \) の完全差集合をつくるなら \( p \) を \( 4 \) とすることになるが、\( 4 \) は素数ではない。しかし、以前に確認したTweetの中に、「\( n-1 \) が素数か素数の冪ならば、\( mod \ n(n-1)+1 \) で完全差集合になる \( \{ a_1, a_2, …, a_n \} \) が存在することを、Singer が証明している」というものがあった。\( 4 \) は素数ではないが、素数の冪である（ \( 4 = 2^2 \) ）。また、\( p = 4 \) とすると、\( p^2 + p + 1 = 21 \) となる。同様の方法で、\( 21 \) を法とする、サイズ \( 5 \) の完全差集合はつくれるだろうか。

トリボナッチ数列を \( mod \ 4 \) で表すと以下のようになる。
$$
0 \quad 0 \quad 1 \quad 1 \quad 2 \quad 0 \quad 3 \quad 1 \quad 0 \quad 0 \quad 1 \quad 1 \quad 2 \quad 0 \quad 3 \quad \cdots
$$
第9、10項で0が連続する。やはりこの方法は \( p \) が素数であることが必要みたいだ。 そしてサイズ \( 5 \) の完全差集合をつくる方法は、また違うということだろう。