ビリヤードの問題再考（10）巡回差集合、完全差集合

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えているなかで、「完全差集合」「巡回差集合」という言葉に出会いました。今回は、完全差集合、巡回差集合とはどのようなものなのかを確認したいと思います。

今回確認するのは、前回に紹介したtweet中にあった英語のサイトです。

Cyclic Difference Sets - by Kris Coolsaet

この中の Cyclic difference sets の内容を確認します。基本的には英文を引用し、意訳するところもあるかと思いますが、日本語に訳していきながら進めていきます。

では、早速。

A cyclic difference set (CDS) modulo n is a set of s positive numbers {a1=0,a2,a3,...,as} less than n, with the property that all differences ai-aj modulo n for i not equal to j, are different. The number n is called the modulus of the CDS and s is the size of the CDS. The set itself is usually written as

0 a1 a2 ... as (n)

where 0 < a1 < a2 < ... < as.

（意訳）
法 $n$ の巡回差集合（CDS: cyclic difference set）とは、$n$ より少ない正の整数の集合 $\{ a_1 = 0, a_2, a_3, \cdots, a_s \}$ で、すべての差 $a_i - a_j ( \bmod n, \ i \neq j )$ が異なるという特性をもっています。$n$ をCDSの法、$s$ をCDSのサイズといいます。この集合は通常次のように書きます。
$$0 \ a_1 \ a_2 \ \cdots \ a_s \ (n)$$
ここで、$0 \lt a_1 \lt a_2 \lt \cdots \lt a_s$ です。

英文内での集合の要素である a1 などについて、意訳では添字として表現しました。数学用語の訳語はそれっぽいものを採用。意訳での $a_i - a_j ( \bmod n, \ i \neq j )$ という表記は $a_i - a_j ( \bmod n ) \ ( i \neq j )$ と書いたほうがいいのかもしれません。意味としては、$\bmod n$ での引き算で、$a_i \neq a_j$ ということです（よね？）。size を単にサイズと訳しましたが、専門用語があるかもしれません。

OK, apart from some terminology, we have not really encountered anything new. Consider the 21-bead necklace from the previous page, written as a numerical sequence:

0 5 6 9 19 (21)

Here, the cyclic difference set is {0,5,6,9,19} ({a1,...,a5} in the definition), the modulus is 21 (n in the definition) and the size is 5 (s). By the difference of two numbers a and b 'modulo 21' we mean a-b if a is not less than b, or else a-b+21. Hence, the requirement that no two differences `modulo 21' are the same, means that all non-diagonal elements in the difference table must be different.
Therefore, mathematically speaking, cyclic difference sets are the same as weird necklaces, whichever terminology you prefer.

（意訳）
用語は別として、何も新しいことに出会ったわけではありません。前のページの21個の玉のネックレスを思い出してみましょう。前ページのネックレスは数列として次のように書けます。

0 5 6 9 19 (21)

ここで、巡回差集合は $\{ 0,5,6,9,19 \}$ （定義では $\{ a_1, \cdots, a_5 \}$ ）で、法は $21$ （定義での $n$ ）、サイズは $5$ （定義での $s$ ）です。$\bmod 21$ での2つの数 $a$ と $b$ の差というのは、$a \geqq b$ ならば $a - b$ を、$a \lt b$ ならば $a - b + 21$ を計算することを意味します。よって、$\bmod 21$ での差が同じものはないということは、差の演算表のなかで対角線上にない要素がすべて異なっていなければなりません。したがって、数学的にいえば、巡回差集合は奇妙なネックレスと同じであるともいえます。

ちょっとこなれた日本語にはなっておらず、何となく意味がつかめるかなという意訳です。difference table を差の演算表としていますが、引用元のサイトではリンクが張られており、前ページに飛ぶようになっています。そこに（まだ読んでいませんが）演算表らしきものがあったので、差の演算表としました。$\bmod 21$ での演算表だと思われます。

ビリヤードの問題では、ネックレスのようにリング状につながったビリヤード玉として問題が提示されていました。いま参照している引用元のサイトではネックレスで例を挙げながら巡回差集合を説明しているのだと思われます。diagonalの意味は辞書をひいて「対角線」とあったので、演算表の対角線上にない（non-diagonal）としています。

引用元の前ページも確認したほうがよさそうですね。しかし、いまは後回しとして先に進みます。

As you may have noticed while trying to string your own weird necklaces, it is fairly easy to construct cyclic difference sets with large modulus and small size. For example:

0 1 10 100 1000 10000 ... 100000000000 (1000000000000)

The trick lies in constructing large sets with small modulus. We may ask the question again: is there a weird necklace with 5 yellow beads and less than 16 black beads? Or in other words, is there a cyclic difference sets of size 5 with modulus less than 21?

（意訳）
ネックレスをつける間に気づいたかもしれませんが、法が大きくサイズが小さい巡回差集合をつくることはとても簡単です。たとえば、（略）
法が小さい、大きな集合をつくるときにはトリックがあります。もう一度質問しましょう：5個の黄色い玉と16個より少ない黒い玉で作られたネックレスはありますか？　別の言葉でいえば、法が21よりも少ない、サイズが5の巡回差集合はありますか？

trick の訳がすぐに思いつかず、そのままトリックとしています。前ページでは、黄色い玉と黒い玉を使った例を挙げているようですね。ビリヤード玉の問題を考えているので、何となくの意味はわかります。

次に進みます。

To answer this question, we must have a closer look at the difference table. For size 5, this table has the following form:

0 * * * * (n)
* 0 * * *
* * 0 * *
* * * 0 *
* * * * 0

where the various stars correspond to different positive numbers. Now, the picture above contains 20 stars (count them!) and each star must hold a number greater than 0 and less than the modulus. In other words the modulus must be at least one more than the number of stars, in this case 20+1=21. The total number of beads in a necklace with 5 yellow beads must therefore be at least 21.

（意訳）
この質問に答えるために、差の演算表をもう少し詳しくみてみましょう。サイズ5の演算表は以下になります。
$$\begin{array}{cccccc} 0 & * & * & * & * & (n) \\ * & 0 & * & * & * & \\ * & * & 0 & * & * & \\ * & * & * & 0 & * & \\ * & * & * & * & 0 & \end{array}$$
ここで $*$ は異なる正の整数に対応します。いま、上の図には20個の $*$ があり（数えたらわかる！）、そしてそれぞれの $*$ は、0より大きく法より小さい数でなければなりません。別の言葉でいうと、法は $*$ の数よりも少なくとも1は大きくなければなりません。このケースでは、$20+1 = 21$ です。したがって、5個の黄色い玉のネックレスでの玉の総数は少なくとも21でなければなりません。

表をきれいにしてみました（笑）

This reasoning can be repeated for any size s. Indeed, the number of stars is s times s-1 (there are s rows of s-1 stars) and hence the modulus n is at least s^2-s+1. (We write s^2 to denote s squared.) The following table lists the various values of this number for given sizes s:

s | 4 5 6 7 8 9 10 11 12 13
-------------------------------------------------
s^2-s+1 | 13 21 31 43 57 73 91 111 133 157

So you see that our 13-bead necklace is the shortest possible for size 4 as well.
A CDS of size s for which the modulus is exactly s^2-s+1 (and hence the smallest possible) is called a perfect difference set. It has the added property that every number between 0 and the modulus can be found in the corresponding difference table.

（意訳）
この理屈は $s$ がどんなサイズでもいえます。実際、$*$ の数は、$s ( s-1)$個（ $s-1$ 個の $*$ が $s$ 列 ある）で、よって法 $n$ は少なくとも $s^2 - s + 1$ です。次の表は、サイズ $s$ が与えられたときの $s^2 - s + 1$ の値です。
$$\begin{array}{c|rrrrrrrrrr} s & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline s^2-s+1 & 13 & 21 & 31 & 43 & 57 & 73 & 91 & 111 & 133 & 157 \end{array}$$
13玉のネックレスはサイズ4で最短であることがわかります。
法がちょうど $s^2-s+1$ であるサイズ $s$ の巡回差集合（つまり、サイズ $s$ で最小の法 $s^2-s+1$ である巡回差集合）を完全差集合と呼びます。完全差集合は、対応する差の演算表に、0と法の間のすべての数が現れるという特性があります。

完全差集合（perfect difference set）がでてきました。巡回差集合はすべての差が異なる数の集合、完全差集合はすべての差が異なり、かつ差が $0$ より大きく法 $n$ より小さいすべての数となる集合ということです。

たしかに、ビリヤードの問題と完全差集合は関係しそうです。では、どのように関係しているか。

引用文中に、サイズ5の巡回差集合の例として、$\{ 0,5,6,9,19 \}$ が挙げられていました。この集合は、サイズ $5$ で、法 $21$ ですので、完全差集合となります。数列としては以下です。

$0 \quad 5 \quad 6 \quad 9 \quad 19 \quad (21)$

一方、5個のビリヤード玉での問題での解答は以下でした。

$1 \quad 3 \quad 10 \quad 2 \quad 5$

注意深く眺めると、完全差集合の数列では、初項に5を足すと第2項に、第2項に1を足すと第3項に、第3項に3を足すと第4項に、第4項に10を足すと第5項に、第5項に2を足すと法である21になります。$\bmod 21$ では $21 \equiv 0$ ですので、第5項に2を足すと初項になるともいえます。足していった数に、ビリヤード玉での問題の解答の数が並んでいます。

次回は、完全差集合の特性とビリヤード玉の問題について確認することにしましょう。