完全差集合のつくり方

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$ の完全差集合をつくる方法は、また違うということだろう。