New sets for old: Shifts

巡回差集合、完全差集合について確認するために参照したサイトCyclic Difference Sets - by Kris Coolsaetが、難しそうではあるが面白そうなので、少しずつ読み進めることにした。しかし、英語で書かれている上に、数学の専門用語が散見されるので、斜め読みではなく、一応は理解しようとして読んでいきたい（理解できるできないは別として）。

そこで、大まかな訳をつけつつ、いま自分がわかるところわからないところを確認しながら読んでいく。このブログに書いていくことはCyclic Difference Sets - by Kris Coolsaetの内容の大まかな訳と、現在の自分の理解である。

第3章（章番号は勝手につけた）にあたる Cyclic difference sets は以前に確認したので、今回は続きの New sets for old: Shifts を見ていきたい。第1章、2章については流し読みで何となく理解できたのでこのブログには書かない。

New sets for old: Shifts

Write down any CDS. (In our example we use the previously encountered set {0,3,5,12} modulo 13.) On the line underneath it, write the same set but increase each number by 1. Instead of 13 just write 0. Do the same again with that new line and continue until you end up with the same line as you started with.
どのような巡回差集合でもいいので書いてほしい。（ここでは以前に挙げた \( 13 \) を法とする集合 \( \{ 0, 3, 5, 12 \} \) を例にする。）その巡回差集合の下に、集合の要素それぞれを1増やしたものを書いてほしい。\( 13 \) のときは \( 0 \) を書く。同様にして、最初と同じ数字になるまで続けてほしい。

This is what you should get:
すると次のようになる：
$$
\begin{array}{rrrrrl}
& 0 & 3 & 5 & 12 & \\
& 1 & 4 & 6 & 0 & \\
& 2 & 5 & 7 & 1 & \\
& 3 & 6 & 8 & 2 & \\
& 4 & 7 & 9 & 3 & \\
& 5 & 8 & 10 & 4 & \\
& 6 & 9 & 11 & 5 & \\
& 7 & 10 & 12 & 6 & \\
& 8 & 11 & 0 & 7 & \\
& 9 & 12 & 1 & 8 & \\
& 10 & 0 & 2 & 9 & \\
& 11 & 1 & 3 & 10 & \\
& 12 & 2 & 4 & 11 & \\
( & 0 & 3 & 5 & 12 & )
\end{array}
$$
If we leave out the (repeated) last line we find 13 different sets. They are called shifts of the original CDS. In general, for every CDS of size s and modulus n we may construct n different shifts.
最後の行は最初と同じものであるのでそれを除くと、\( 13 \) 個の異なる集合ができる。それらは最初の巡回差集合のシフト（shifts）と呼ばれる。一般に、\( n \) を法とするサイズ \( s \) の巡回差集合において、\( n \) 個の異なるシフトをつくることができる。

shiftをそのまま「シフト」と書いたが、専門用語がありそうな気がする。転移とか、平行移動とか、そのような感じのものである。集合 \( \{ 0, 3, 5, 12 \} \) の要素の数字を1ずつズラしていって、計13個の集合ができる。

Shifts have remarkable properties
シフトの主な性質

You may use the example above to check the following properties which hold for shifts of any CDS:
巡回差集合のシフトがもっている次の性質を上の例を使って確認してほしい：

• Every number from 0 up to n-1 occurs in exactly s shifts.
• Each of the s shifts that contain the number 0 is again a CDS.
• In fact, these shifts all occur as lines in the difference table of the CDS (in reverse order).
• Two different shifts may have either 0 or 1 element in common. (In the example above you will not find a disjoint pair, but this is a consequence of the fact that the CDS is perfect.)
• Any pair of different numbers (in the range 0..n-1) occurs in at most one shift. (Again, when the CDS is perfect, you will not find a pair that does not occur in any shift.)

We shall not prove these properties here.

• ちょうど \( s \) 個のシフトで、\( 0 \) から \( n-1 \) までのすべての数が現れる。
• \( 0 \) を要素にもつ \( s \) 個のシフトはそれぞれ巡回差集合になる。
• 事実、これらのシフトはすべて巡回差集合の差の演算表の行として現れる（順序は逆になる）。
• 2つの異なるシフトは \( 0 \) か \( 1 \) を共通にもつ。（上の例では a disjoint pair は見つからないだろうが、これは巡回差集合が完全であるという事実の結果である）
• 多くとも１つのシフトで、（ \( 0 \) から \( n-1 \) の範囲で）異なる数のペアが現れる。（巡回差集合が完全であるときはいかなるシフトでもこのようなペアは見つからない。）

ここではこれらの性質についての証明はしない。

訳が悪いのだと思うが、これらの性質がまだよくわかっていない（わかっていないから訳がよくわからないともいえる）。1つめの性質は、1ずつ増やしていくことを \( n \) 回繰り返すのだから当たり前のようなことをいっているような気がして、かえって意味を取り違えているのではないかと疑ってしまう。2つめは、巡回差集合の定義として、\( 0 \) を含むというのがあるのだろう。それぞれの要素を1ずつ増やしていっても要素間の差は変わらないのでシフトはすべて巡回差集合になると思っていたが、\( 0 \) を含まなければならないということなら話はわかる。3つめの性質は、集合 \( \{ 0, 3, 5, 12 \} \) での差の演算表を確認すると、たしかに \( \{ 10, 0, 2, 9 \} \) 、\( \{ 8, 11, 0, 7 \} \) 、\( \{ 1, 4, 6, 0 \} \) を見つけることができる。in reverse order というのは、これらの集合が出てくる順番が逆という意味であろう。
$$
\begin{array}{r|rrrrl}
& 0 & 3 & 5 & 12 & (13) \\
\hline
0 & 0 & 3 & 5 & 12 & \\
3 & 10 & 0 & 2 & 9 & \\
5 & 8 & 11 & 0 & 7 & \\
12 & 1 & 4 & 6 & 0 &
\end{array}
$$
4つめと5つめがよくわかっていない。また、a disjoint pair の意味がつかめていない。4つめと5つめの性質は、\( \{ 0, 3, 5, 12 \} \) は完全差集合であるので、確認できない（のだろう）。完全でない巡回差集合での例を確認する必要がありそうだが、完全でない巡回差集合の例をまだ見つけていないので、確認はひとまず保留とする。

Apart from providing us new CDSs for old ones, the notion of `shifts' is also useful in providing a geometrical interpretation of cyclic difference sets as will be explained in the following pages.
古い巡回差集合に対する新しい巡回差集合から離れて、「シフト」は、これから説明する巡回差集合の幾何学的解釈に有用である。

Cyclic Difference Sets - by Kris Coolsaet

前に巡回差集合、完全差集合について確認するために参照したサイトを確認していると、そこそこ文量があり、一気に読めそうになかった。

目次がなく、読みたいページにすぐにたどり着くことができないので、目次代わりのリンク集を作っておく。内容はまだ読んでいないのでわからない（前回参照したところは3.のCyclic difference setsである）。

実際には章番号はついていないが、ここでは便宜上つけている。各リンクの後にあるのは小見出し的な箇所。


Cyclic Difference Sets - by Kris Coolsaet
　　Preface

1. Weird coloured necklaces
What is happening?
Do these necklaces have any use?
2. Necklaces and numbers
Difference tables
3. Cyclic difference sets
Sorry, could you repeat that?
Short necklaces
4. New sets for old: Shifts
Shifts have remarkable properties
5. Is this geometry?
What has all this to do with CDSs?
How about an example?
6. Is this any help?
No, nothing in mathematics is as simple as it looks.
7. Affine and semi-affine planes
Finite affine planes
Some examples
Semi-affine planes
8. And now for something completely different
Modular arithmetic
9. Modular arithmetic and semi-affine planes
An example might make this more clear
10. Fibonacci turns up everywhere
Hm ... three, eight, ... sounds familiar!
Great! And now we do the same with q=5,7,11... Right?
11. Fibonacci's nephews
Other nephews of Fibonacci
Which nephew for which prime?
12. How to make perfect CDSs
Meet the rest of the family!
13. Projective planes
Defining axioms
Coordinates
14. Other CDSs
A semi-affine CDS of order 4.
A semi-affine CDS of order 9.
A semi-affine CDS of order 8.
A perfect CDS of size 5 (order q=4).
A perfect CDS of size 9 (order q=8=p^3 with p=2).
15. New sets for old: multipliers
Multipliers
Using `runs' to construct CDSs
16. Golomb rulers
Golomb rulers and CDSs

ビリヤードの問題再考（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を足すと初項になるともいえます。足していった数に、ビリヤード玉での問題の解答の数が並んでいます。

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

ビリヤードの問題再考（９）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えていて、少し煮詰まってきたので Web 上で \( n \) が大きいときの解の一覧がないかとか、解を見出すためのアルゴリズムにはどのようなものがあるのかを確認していたら、興味深いtweetのまとめを見つけました。

Togetter：『笑わない数学者』のパズルと目盛の節約，ゴロム分度器と完全差集合予想について

tweet内のリンク先で非公開となってしまっているところがあるのが少し残念ですが、話題として盛りだくさんな内容です。

簡単に興味あるところをピックアップして書くと、まずは考えているビリヤード玉の問題について、次のことが書かれていました。解もいくつか書かれていましたが、解の個数については明記されてはいませんでした。検証はまだしていません。

• \( n = 8 \) のときの解（解の個数についての明記なし）
  $$
  ( 1, 3, 8, 2, 16, 7, 15, 5 ）
  $$
• \( n = 10 \) のときの解（解の個数についての明記なし）
  $$
  ( 1, 2, 9, 8, 14, 4, 43, 7, 6, 10, 5, 24 )
  $$
• \( n = 14 \) までのうち，解が存在しないのは \( n = 7, 11, 13 \) 。この先の素数でも解は存在しない様子。
• \( n = 15, 16, 21, 22 \) でも解なしの模様。
• \( n = 30 \) のときの解（解の個数についての明記なし）
  $$
  ( 1, 35, 17, 21, 20, 56, 7, 19, 98, 5, 29, 3, 11, 2, 62, \\ 6, 60, 25, 15, 9, 18, 4, 8, 47, 10, 23, 28, 44, 99, 89 )
  $$

「隣接ではなく、球のすべての組み合わせの合計でやるなら、番号 \( 1, 2, 4, …, 2^{n-1} \) の \( n \) 個の球で \( 1 \) から \( 2^{n-1} \) までの全部の整数が作ることができる。2進法。」「輪にする（＝ \( mod \) で考える）だけで大きな \( n \) でも完全性が成り立つようになる」というのもおもしろいです。

また、目盛節約定規、ゴロム定規について。ゴロム定規というのを初めて知りましたが、Wikipediaにも載っていて、いま考えているビリヤード玉の問題ではリング状に並んだ状態で考えていますが、ゴロム定規はリング状ではなく直線上として並んでいるようなものですね。まだ詳しくは読んでいません。そして、モジュラーゴロム定規（ゴロム分度器）。詳しく書かれているわけではありませんが、ビリヤード玉の問題と同じような気がします。すでに定理となっているのか予想のままなのかはわかりませんが、「\( n-1 \) が素数か素数の羃のとき、かつそのときに限って、目盛数 \( n \) の完全ゴロム分度器が存在するであろう」という有名な予想があるようです。おそらくはこの予想のことを指していると思いますが、\( n \lt 1600 \) ではこの予想が成り立っていることが Evans & Mann によって確かめられているみたいです。

興味をひいたのは、完全差集合という言葉です。\( n-1 \) が素数か素数の羃ならば、\( mod \ n(n-1)+1 \) で完全差集合になる \( \{ a_1, a_2, …, a_n \} \) が存在することを、Singer が証明しているらしく、tweet主がビリヤードの問題と「完全差集合」と本質的に同じであることをつぶやいています。\( n(n-1)+1 \) はビリヤードの問題にも出てきました。

Wikipediaには「完全差集合」の項はありませんでした。「差集合」の項がありましたが、完全差集合での差集合とは違うものかと思われます。

tweetのリンク先には英語で書かれているサイトも含まれているので、ななめ読みしかしていませんが、完全差集合は英語で perfect different sets でしょう。もうひとつ、cyclic difference sets というのもリンク先にありました。日本語ではどうやら「巡回差集合」と訳されているようです。

完全差集合、巡回差集合について確認してみます。