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.
古い巡回差集合に対する新しい巡回差集合から離れて、「シフト」は、これから説明する巡回差集合の幾何学的解釈に有用である。