Off the Job Training: 2019/12

2019/12/25

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

2019/12/24

第2章第3節の節末問題

エミール・アルティン『ガロア理論入門』第2章第3節の節末問題です。ここには問題のみ。

問題3-1
$ K \subset E $ のとき、$ E $ の要素 $ \alpha $ が $ \alpha^2 + k \alpha + l = 0 \ ( k,l \in K ) $ を満たすための必要十分条件は、$ ( K ( \alpha ) / K ) = 1 $ または　$ ( K ( \alpha ) / K ) = 2 $ であることを示せ。

問題3-2
次の体は有理数体 $ Q $ 上何次の体か。

(1)　$ Q( \alpha ) $ ただし $ \alpha ^3 = 1, \ \alpha \neq 1 $
(2)　$ Q( \alpha ) $ ただし $ \alpha ^3 = 2 $
(3)　$ Q( \alpha ) $ ただし $ \alpha ^4 + \alpha ^2 + 1 = 0 $

問題3-3
$ \alpha $ が $ f(x) = x^3 - x - 2 = 0 $ の根のとき、$ ( Q( \alpha ) / Q ) = 3 $ を示し、さらに次の値を $ \alpha $ の2次以下の多項式で表わせ。

(1)　$ \alpha ^5 $
(2)　$ \frac { 1 } { \alpha +1 } $

問題3-4
$ E $ が $ K $ の拡大体で $ \alpha $ が $ K $ 上代数的であるとする。$ ( K ( \alpha ) / K ) = 2 , \ E \cap K ( \alpha ) = K $ とすると $ E ( \alpha ) $ は $ E $ 上次数 $ 2 $ であることを示せ。

問題3-5
体 $ K $ の相異なる $ n $ 個の要素 $ a_1, a_2, \cdots, a_n $ と $ n $ 個の要素 $ b_1, b_2, \cdots, b_n $ （こちらは等しい要素があってもよい）を与えたとき、$ f ( a_i ) = b_i \ ( i = 1, 2, \cdots, n ) $ となる $ n-1 $ 次の $ K $ 内の多項式

$ f(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1} $
が存在することを証明せよ。

問題3-6
$ \sigma $ が $ K $ から $ K' $ への同型写像で、$ K , \ K' $ がともに有理数体 $ Q $ の拡大体のとき有理数 $ a $ に対して $ \sigma ( a ) = a $ であることを示せ。

問題3-7
実数体 $ R $ の自己同型写像を $ \sigma $ とするとき、次を順に証明せよ。
(1)　$ \alpha \gt 0 $ ならば $ \sigma ( a ) \gt 0 $ 、$ \alpha \gt \beta $ ならば $ \sigma ( a ) \gt \sigma ( \beta ) $
(2)　$ \sigma $ は恒等写像である

2019/12/22

【定理7】【定理8】の証明

エミール・アルティン『ガロア理論入門』第2章第3節続き。

定理7（クロネッカーの定理）と定理8の証明です。

定理7.（クロネッカー）
$ f(x) $ を体 $ K $ における定数でない多項式とするとき、$ K $ の拡大体 $ E $ で、$ f(x) $ がその中に根をもつものが存在する。

非常に簡潔に証明が書かれており、証明は「 $ f(x) $ の1つの既約因子をとり、これを用いて上でつくった拡大体 $ E_1 $ をつくればよい」のみ。

定理8.
$ \sigma $ を体 $ K $ から体 $ K' $ の上への同型写像とする。$ f(x) $ を $ K $ 内の既約多項式とし、その像を $ f'(x) $ とする。$ f( \alpha ) = 0 $ を満たす $ \alpha $ による拡大体を $ E = K( \alpha ) $ とし、$ f'( \alpha ' ) = 0 $ を満たす $ \alpha ' $ による拡大体を $ E' = K'( \alpha ' ) $ とする。すると $ \sigma $ は $ \alpha $ の像が $ \alpha ' $ であるような $ E $ から $ E' $ の上への同型写像に延長される。

証明　$ E $ の任意の要素 $ \theta $ は $ \theta = g( \alpha ) $ の形をしている。ここに $ g(x) $ は $ K $ 内の多項式で、その次数は $ f(x) $ よりも低いものである。$ \theta $ に $ g'( \alpha ' ) $ を像として対応づけよう。この写像は明らかに与えられた写像 $ \theta $ の延長であり、$ E $ を $ E' $ の上へ一対一に写像する。このとき2要素の和は像の和に写像されることは明らかである。また $ g( \alpha ) h ( \alpha ) = r ( \alpha ) $ とすると $ r( \alpha ) $ は $ g( \alpha ) h ( \alpha ) $ の $ f(x) $ を法とした剰余であり、したがって $ g(x) h(x) = q(x)f(x) + r(x) $ のような多項式 $ q(x) $ が存在する。ここで多項式の像を考えると $ g'(x) h'(x) = q'(x)f'(x) + r'(x) $ であり、$ x = \alpha ' $ に対して $ g'( \alpha ') h'( \alpha ') = r'( \alpha ') $ となる。よって2要素の積は像の積に写像される。

（証明終り）

そして、この定理8により、「1つの既約方程式の根によって生成された拡大体の構造は、その根の選び方に関係しない」という特性が示されたことになります。

完全差集合のつくり方

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

同型写像

エミール・アルティン『ガロア理論入門』第2章第3節続き。

体 $ K $ 内の既約多項式 \ ( f(x) \) の根 $ \alpha $ を使って集合 $ E_0 $ をつくり、その集合 $ E_0 $ が体であることを示そうとしています。そこで、集合 $ E_0 $ を模写した、記号 $ xi $ を用いて集合 $ E_1 $ をつくりました。$ E_1 $ が体であることを示すことで、$ E_0 $ が体であることを示そうということです。前回は $ E_1 $ が体であることを示しました。

そして、$ E_1 $ から $ E_0 $ への写像を考えると、同型写像であり、$ E_0 $ が体であることがわかります。

以下は、1つの体 $ K $ から他の体 $ K' $ の中への写像 $ \sigma $ の性質について述べている箇所です。

　一般に1つの体 $ K $ から他の体 $ K' $ の中への写像 $ \sigma $ で次の性質をもつものを考える。すなわち $ K $ の任意の要素 $ \alpha $ に対して、 $ \alpha $ に対応する $ K' $ の要素を $ \sigma( \alpha ) $ で示すとき、$ K $ の任意の要素 $ \alpha , \beta $ に対して次の性質をもつ写像である。

1.　$ \sigma( \alpha + \beta ) = \sigma( \alpha ) + \sigma( \beta ) $
2.　$ \sigma( \alpha \beta ) = \sigma( \alpha ) \sigma( \beta ) $

ここで　$ \sigma( \alpha ) = 0 $ のような要素 $ \alpha \neq 0 $ が存在すれば、性質2によって任意の $ \beta $ に対して、
$$
\begin{eqnarray}
\sigma( \beta ) &=& \sigma( \alpha \alpha ^{-1} \beta ) = \sigma( \alpha ) \sigma( \alpha ^{-1} \beta ) \\
&=& 0 \sigma( \alpha ^{-1} \beta ) = 0
\end{eqnarray}
$$
となり、$ K $ 全体が0に写像されてしまう。しかしこの写像は意味のないものであるから、ここでは次のことを仮定する。

3　$ \alpha \neq 0 $ ならば $ \sigma ( \alpha ) \neq 0 $

この3つの性質から、さらに
$$
\sigma( \alpha - \beta ) = \sigma( \alpha ) - \sigma( \beta ) \\
\sigma( \frac { \alpha } { \beta } ) = \frac { \sigma( \alpha ) } { \sigma( \beta ) } \\
\alpha = \beta ならば \sigma( \alpha ) = \sigma( \beta )
$$
が得られ、$ \sigma $ は $ K $ から $ K' $ の中への一対一の写像であることがわかります。このような写像を $ K $ から $ K' $ の中への同型写像といいます。このとき、 $ K $ の像は $ K' $ の部分体です。

さらに、写像 $ \sigma $ が体 $ K $ を体 $ K' $ 全体へ写像するときは、 $ K $ から $ K' $ の上への同型写像といいます。このときは逆に $ K' $ から $ K $ の上へもどる逆写像 $ \sigma ^{-1} $ を考えることができ、これも $ K' $ から $ K $ の上への同型写像となります。そして、$ K $ から $ K' $ の上への同型写像が存在するとき、$ K $ と $ K' $ は同型であるともいいます。

この定義は $ K' $ が $ K $ に一致していてもさしつかえなく、$ \sigma $ が $ K $ からそれ自身への上への同型写像のとき、$ \sigma $ は $ K $ の自己同型写像といいます。この場合には $ \sigma ^{-1} $ も $ K $ の自己同型写像です。また、$ K $ の恒等写像は $ K $ の1つの自己同型写像です。

2019/12/21

Cyclic Difference Sets - by Kris Coolsaet

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

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

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

Cyclic Difference Sets - by Kris Coolsaet
　　Preface

Weird coloured necklaces

Necklaces and numbers
Cyclic difference sets

New sets for old: Shifts
Is this geometry?

Is this any help?
Affine and semi-affine planes

And now for something completely different
Modular arithmetic and semi-affine planes
Fibonacci turns up everywhere

Fibonacci's nephews

How to make perfect CDSs
Projective planes

Other CDSs

New sets for old: multipliers

Golomb rulers

2019/12/20

ビリヤードの問題再考（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 というのもリンク先にありました。日本語ではどうやら「巡回差集合」と訳されているようです。

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

2019/12/19

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

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？

5つのビリヤード玉 $ a_1, a_2, a_3, a_4, a_5 $ が、右回りでこの順につながっているとして、$ a_1 = 1 $ としたとき、21通りの取り出し方にどこまで大小関係がつけられるのかを考えています。前回は以下まで確認しました。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 & \lt & D_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] & \lt & D_5 \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & [ C_3 D_3 ] \\
A_4 & \lt & [ B_4 C_4 ] & \lt & [ C_3 D_3 ] \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] & \lt & D_4 \\
[ A_5 B_5 ] & \lt & C_5 & \lt & D_4
\end{eqnarray}
$$
上の不等式について、一応きれいにそろえるように書きましたが、もう少しわかりやすくならないでしょうか。

$ A_1 $ とか $ A_2 $ というような記号は、表記を短くするだけのために使っているのですが、もともとは、$ a_1, a_2, a_3, a_4, a_5 $ の組み合わせでつくったものです。いま $ a_1 = 1 $ として考えているので、$ a_1 = 1 $ を代入したそれぞれの記号は以下です。
$$
\begin{eqnarray}
A_1 &=& 1 \\
A_2 &=& a_2 \\
A_3 &=& a_3 \\
A_4 &=& a_4 \\
A_5 &=& a_5 \\\\

B_1 &=& 1 + a_2 \\
B_2 &=& a_2 + a_3 \\
B_3 &=& a_3 + a_4 \\
B_4 &=& a_4 + a_5 \\
B_5 &=& a_5 + 1 \\\\

C_1 &=& 1 + a_2 + a_3 \\
C_2 &=& a_2 + a_3 + a_4 \\
C_3 &=& a_3 + a_4 + a_5 \\
C_4 &=& a_4 + a_5 + 1 \\
C_5 &=& a_5 + 1 + a_2 \\\\

D_1 &=& 1 + a_2 + a_3 + a_4\\
D_2 &=& 20 \\
D_3 &=& a_3 + a_4 + a_5 + 1 \\
D_4 &=& a_4 + a_5 + 1 + a_2 \\
D_5 &=& a_5 + 1 + a_2 + a_3 \\\\

E &=& 21
\end{eqnarray}
$$
今度は、$ a_1, a_2, a_3, a_4, a_5 $ の大小関係が、どのように各要素に影響しているのかを見てみます。たとえば、$ a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5 $ だったならば、$ B_1 , B_2 , B_3 , B_4 , B_5 $ の大小関係はどうなるのか、ということです。

$ a_1 = 1 $ としているので、残りの $ a_2, a_3, a_4, a_5 $ の大小関係を仮定してすすめていこうと思いますが、4個の順列すべてを確認するのはさすがに骨が折れます（ $ 4! = 24 $ 通りあります）。なのでここでは、$ a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5 $ のときと、5つのビリヤード玉での解（ $ 1, 5, 2, 10, 3 $ ）のとき、つまり $ a_1 \lt a_3 \lt a_5 \lt a_2 \lt a_4 $ のときにとどめたいと思います。

まずは、$ a_1 \lt a_2 \lt a_3 \lt a_4 \lt a_5 $ のとき。

$ B_1 $ と $ B_2 $ では、$ a_2 $ が共通しているので、$ 1 $ と $ a_3 $ の大小関係が $ B_1 $ と $ B_2 $ の大小関係となり、$ B_1 \lt B_2 $ です。このように続けると、$ B_2 \lt B_3 $、$ B_3 \lt B_4 $、$ B_5 \lt B_4 $ がわかります。ひとまずまとめた不等式を書くと、$ B_1 \lt B_2 \lt B_3 \lt B_4, \ B_5 \lt B_4 $ です。さて、$ B_5 $ がどこに入るかですが、$ B_1 \lt B_5 $ はわかりますがパッと見ではわかりません。ひとまず現在の状況でまとめておきます。
$$
\begin{array}{ccccc}
B_1 & \lt & B_2 \lt B_3 & \lt & B_4 \\
B_1 & \lt & B_5 & \lt & B_4
\end{array}
$$
同様に $ C_1 $ から $ C_5 $ を見ると、
$$
\begin{array}{ccccc}
C_1 & \lt & C_2 & \lt & C_3 \\
C_1 & \lt & C_5 \lt C_4 & \lt & C_3
\end{array}
$$
$ D_1 $ から $ D_5 $ では、
$$
\begin{eqnarray}
D_1 \lt D_5 \lt D_4 \lt D_3 \lt D_2
\end{eqnarray}
$$
です。

$ D $ 系列（と勝手に呼びますが）は、$ A $ 系列のいわば逆の関係です。$ a_1, a_2, a_3, a_4, a_5 $ で$ A $ 系列、つまり1個の要素を取るということは、4個の要素を残すことになります。逆も然りです。いま$ A $ 系列の大小関係を決定させているので、$ D $ 系列の大小関係も決定しています。一方、$ B $ 系列と$ C $ 系列は（これも逆の関係です）、大小関係が決定しておりません（決定できるのに、僕が決定させられていないだけかもしれませんが……）。

では、$ a_1 \lt a_3 \lt a_5 \lt a_2 \lt a_4 $ のときはどうでしょうか。

まずは $ B $ 系列をみてみます。
$$
\begin{eqnarray}
B_5 \lt B_1 \lt B_2 \lt B_3 \lt B_4
\end{eqnarray}
$$
続いて $ C $ 系列。
$$
\begin{eqnarray}
C_1 \lt C_5 \lt C_4 \lt C_3 \lt C_2
\end{eqnarray}
$$
$ D $ 系列。
$$
\begin{eqnarray}
D_5 \lt D_3 \lt D_1 \lt D_4 \lt D_2
\end{eqnarray}
$$
となりました。

$ a_1 \lt a_3 \lt a_5 \lt a_2 \lt a_4 $ のときというのは解答のときなので、決定しても不思議ではないのですが、このメカニズムというか、本質というか、それが僕にはまだわかっていないようです。

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

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？

5つのビリヤード玉 $ a_1, a_2, a_3, a_4, a_5 $ が、右回りでこの順につながっているとして、$ a_1 = 1 $ としたとき、21通りの取り出し方にどこまで大小関係がつけられるのかを考えています。

使っている記号の意味については前回を確認してください。

$ B_1 $ を見ると、$ B_1 = 1 + A2 $ ですので、$ A_2 \lt B_1 $ となり、さらに $ A_2 $ と $ B_1 $ の差が1ですので、間に何も入らないという意味で $ [ A_2 B_1 ] $ と書こうというのが前回までのところです。ひとつひとつ確認しながら順に大小関係を確認していこうと思います。$ B_1 $ について、当然 $ 1 \lt B_1 $ がいえますが、$ 1 \lt B_1 $ や $ B_1 \lt 13 $ などはここでは省いていきます。

さて、$ B_2 $ を見ると、$ B_2 = A2 + A3 $ ですので、明らかに $ A_2 \lt B_2 $ 、$ A_3 \lt B_2 $ です。ところで $ [ A_2 B_1 ] $ ですので、 $ A_2 \lt B_2 $ から、$ [ A_2 B_1 ] \lt B_2 $ がいえます。

$ B_3 $ を見ると $ A_3 \lt B_3 $ 、$ A_4 \lt B_3 $ です。

また $ B_4 $ からは $ A_4 \lt B_4 $ 、$ A_5 \lt B_4 $ がいえます。$ B_5 $ を見ると、$ B_1 $ のときと同様に、$ [ A_5 B_5 ] $ がいえます。
$ A_5 \lt B_4 $ と $ [A_5 B_5] $ より、$ [A_5 B_5] \lt B_4 $ です。これまでをまとめると以下です。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & B_2 \\
A_3 & \lt & B_2 \\
A_3 & \lt & B_3 \\
A_4 & \lt & B_3 \\
A_4 & \lt & B_4 \\
[A_5 B_5] & \lt & B_4
\end{eqnarray}
$$
続いて $ C_1 $ から $ C_5 $ を見ます。

$ C_1 $ より、$ B_1 \lt C_1 $ と $ [ B_2 C_1 ] $ がいえます。つまり、$ B_1 \lt [ B_2 C_1 ] $ です。上のまとめた不等式に追加していきます。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] \\
A_3 & \lt & B_3 \\
A_4 & \lt & B_3 \\
A_4 & \lt & B_4 \\
[ A_5 B_5 ] & \lt & B_4
\end{eqnarray}
$$
$ C_2 $ は、$ B_2 \lt C_2 $ と $ B_3 \lt C_2 $ です。同様にまとめた不等式をまとめていきます。見やすくなるように表示を工夫してはいきたいですが、ごちゃごちゃするかもしれません。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & C_2 \\
A_3 & \lt & B_3 & \lt & C_2 \\
A_4 & \lt & B_3 \\
A_4 & \lt & B_4 \\
[ A_5 B_5 ] & \lt & B_4
\end{eqnarray}
$$
このようにして、ひとつずつ確認をしていきます。以下、読むには退屈になりますので飛ばしていただいても大丈夫です。

$ C_3 $ は、$ B_3 \lt C_3 $ と $ B_4 \lt C_3 $ です。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & C_2 \\
A_3 & \lt & B_3 & \lt & C_2 \\
A_4 & \lt & B_3 & \lt & C_3 \\
A_4 & \lt & B_4 & \lt & C_3 \\
[ A_5 B_5 ] & \lt & B_4
\end{eqnarray}
$$
$ C_4 $ は、$ [ B_4 C_4 ] $ と $ B_5 \lt C_4 $ です。$ B_5 \lt [ B_4 C_4 ] $ がいえ、$ [A_5 B_5] \lt B_4 $ と合わせることができます。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & C_2 \\
A_3 & \lt & B_3 & \lt & C_2 \\
A_4 & \lt & B_3 & \lt & C_3 \\
A_4 & \lt & [ B_4 C_4 ] & \lt & C_3 \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ]
\end{eqnarray}
$$
$ C_5 $ は、$ B_5 \lt C_5 $ と $ B_1 \lt C_5 $ です。だんだん書きづらくなってきました。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & C_2 \\
A_3 & \lt & B_3 & \lt & C_2 \\
A_4 & \lt & B_3 & \lt & C_3 \\
A_4 & \lt & [ B_4 C_4 ] & \lt & C_3 \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] \\
[ A_5 B_5 ] & \lt & C_5
\end{eqnarray}
$$

$ D_1 $ から $ D_5 $ をみます。

$ D_1 $ は、$ C_1 \lt D_1 $ と $ [ C_2 D_1 ] $ 。つまり $ C_1 \lt [ C_2 D_1 ] $ 。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & C_3 \\
A_4 & \lt & [ B_4 C_4 ] & \lt & C_3 \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] \\
[ A_5 B_5 ] & \lt & C_5
\end{eqnarray}
$$
$ D_2 $ は、$ D_2 = 20 $ ですので飛ばします。

$ D_3 $ は、$ [ C_3 D_3 ] $ と $ C_4 \lt D_3 $ 。つまり $ C_4 \lt [ C_3 D_3 ] $
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & [ C_3 D_3 ] \\
A_4 & \lt & [ B_4 C_4 ] & \lt & [ C_3 D_3 ] \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] \\
[ A_5 B_5 ] & \lt & C_5
\end{eqnarray}
$$
$ D_4 $ は、$ C_4 \lt D_4 $ と $ C_5 \lt D_4 $ 。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & [ C_3 D_3 ] \\
A_4 & \lt & [ B_4 C_4 ] & \lt & [ C_3 D_3 ] \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] & \lt & D_4 \\
[ A_5 B_5 ] & \lt & C_5 & \lt & D_4
\end{eqnarray}
$$
$ D_5 $ は、$ C_5 \lt D_5 $ と $ C_1 \lt D_5 $ 。
$$
\begin{eqnarray}
[ A_2 B_1 ] & \lt & C_5 & \lt & D_5 \\
[ A_2 B_1 ] & \lt & [ B_2 C_1 ] & \lt & D_5 \\
A_3 & \lt & [ B_2 C_1 ] & \lt & [ C_2 D_1 ] \\
A_3 & \lt & B_3 & \lt & [ C_2 D_1 ] \\
A_4 & \lt & B_3 & \lt & [ C_3 D_3 ] \\
A_4 & \lt & [ B_4 C_4 ] & \lt & [ C_3 D_3 ] \\
[ A_5 B_5 ] & \lt & [ B_4 C_4 ] & \lt & D_4 \\
[ A_5 B_5 ] & \lt & C_5 & \lt & D_4
\end{eqnarray}
$$
$ E $ は $ E = 21 $ なので省略。

ひと通りみましたが、どっか抜けてそうな気がします……。

また、チェックもしたいし、他にも考慮したいところがありますし、こんなことをやって意味があるのかも見直したいので、また次回……。

2019/12/18

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

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

原点に戻って、5つのビリヤード玉で問題をあらためて考えます。

五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？

問題文の条件でビリヤード玉を取り出す方法が何通りあるかと数えると、21通りあります。5つのビリヤード玉を $ a_1, a_2, a_3, a_4, a_5 $ として、この順につながっているとすると、取り出し方は次の21通りです。

1個だけ取り出す　5通り
$$
a_1, \quad a_2, \quad a_3, \quad a_4, \quad a_5
$$
2個取り出す　5通り
$$
a_1 + a_2 , \quad a_2 + a_3 , \quad a_3 + a_4 , \\
a_4 + a_5 , \quad a_5 + a_1
$$
3個取り出す　5通り
$$
a_1 + a_2 + a_3 , \quad a_2 + a_3 + a_4 , \quad a_3 + a_4 + a_5 , \\
a_4 + a_5 + a_1 , \quad a_5 + a_1 + a_2
$$
4個取り出す　5通り
$$
a_1 + a_2 + a_3 + a_4 , \quad a_2 + a_3 + a_4 + a_5 , \\
a_3 + a_4 + a_5 + a_1 , \quad a_4 + a_5 + a_1 + a_2 , \\
a_5 + a_1 + a_2 + a_3
$$
5個全部取り出す　1通り
$$
a_1 + a_2 + a_3 + a_4 + a_5
$$

この21通りが、1から21までのすべての数（自然数）に対応することになります。この21通りのそれぞれの計算結果はすべて異なる数で、1から21のどれかということになります。そこから、1（と2）が $ a_1, a_2, a_3, a_4, a_5 $ のうちのどこかに入ること、そして5個すべてを取り出した $ a_1 + a_2 + a_3 + a_4 + a_5 $ が21となることが容易にわかります。

そこで、$ a_1 = 1 $ としたとき、この21通りにどこまで大小関係がつけられるのかを考えてみたいと思います。

見やすさのため次のように記号をおきます。
$$
\begin{eqnarray}
A_1 &=& a_1 = 1 \\
A_2 &=& a_2 \\
A_3 &=& a_3 \\
A_4 &=& a_4 \\
A_5 &=& a_5 \\\\

B_1 &=& a_1 + a_2 = 1 + a_2 \\
B_2 &=& a_2 + a_3 \\
B_3 &=& a_3 + a_4 \\
B_4 &=& a_4 + a_5 \\
B_5 &=& a_5 + a_1 = a_5 + 1 \\\\

C_1 &=& a_1 + a_2 + a_3 = 1 + a_2 + a_3 \\
C_2 &=& a_2 + a_3 + a_4 \\
C_3 &=& a_3 + a_4 + a_5 \\
C_4 &=& a_4 + a_5 + a_1 = a_4 + a_5 + 1 \\
C_5 &=& a_5 + a_1 + a_2 = a_5 + 1 + a_2 \\\\

D_1 &=& a_1 + a_2 + a_3 + a_4 = 1 + a_2 + a_3 + a_4\\
D_2 &=& a_2 + a_3 + a_4 + a_5 = 20 \\
D_3 &=& a_3 + a_4 + a_5 + a_1 = a_3 + a_4 + a_5 + 1 \\
D_4 &=& a_4 + a_5 + a_1 + a_2 = a_4 + a_5 + 1 + a_2 \\
D_5 &=& a_5 + a_1 + a_2 + a_3 = a_5 + 1 + a_2 + a_3 \\\\

E &=& a_1 + a_2 + a_3 + a_4 + a_5 = 21
\end{eqnarray}
$$
$ A_1 $ など、記号をおく必要がないところもありますが、一貫性のために一応記号をおいています。また、$ A_1 = 1 $ のようにすでにわかっている数字を書き込んでいます。この21個を小さいものから順に並べると1から21の数字となります。現在は $ a_1 = 1 $ とおいているだけですので一列に並べることはできませんが、この状態でどこまで大小関係をつけられるか、どこまで並べられるのかを考えてみます。$ A_1 ( = 1) \lt \cdots \lt D_2 ( = 20 ) \lt E ( = 21 ) $ ですので、2から20の間を考えましょう。

まずは、$ A_2 $ から $ A_5 $ について。この4つは $ A_1 $ よりも大きいことはわかりますが、現状、$ A_2 $ から $ A_5 $ のあいだで大小関係をつけることはできません。ただし、すべて異なる自然数であるということと、$ E = 21 $ より、$ A_2 $ から $ A_5 $ のなかの自然数は最大でも11であることはわかります。4つの異なる自然数の組で最小の組み合わせは $ { 1, 2, 3, 4 } $ で、この合計は10です。合計が21である5つの自然数のうちの4つを一番小さくしたとすると、残る1つは11となり、11より大きくなると他の4つの組み合わせは存在しなくなるためです。ここで使うかどうかはわかりませんが、一応書いておきます。
$$
2 \leqq A_2 \leqq 11 \quad
2 \leqq A_3 \leqq 11 \\
2 \leqq A_4 \leqq 11 \quad
2 \leqq A_5 \leqq 11
$$
続いて $ B_1 $ をみてみましょう。$ B_1 = 1 + a_2 $ ですので、$ A_2 \lt B_1 $ が成り立ちます。ここで $ A_2 $ と $ B_1 $ の差は1ですので、 $ A_2 $ と $ B_1 $ の間には他の要素は入りません。そこで、このように間に何も入らないときは、$ [ A_2 B_1 ] $ と書いていきます。右側のほうが左側よりも1だけ大きいという意味です。3つ以上の要素を並べるときもあるかもしれませんが、その際も同様に考えます。

$ B_5 $ についても、$ [ A_2 B_1 ] $ と同様に、$ [ A_5 B_5 ] $ といえます。すぐにわかる差が1の組み合わせを挙げておきましょう。
$$
[ A_2 B_1 ] , \quad
[ A_5 B_5 ] , \\
[ B_2 C_1 ] , \quad
[ B_4 C_4 ] , \\
[ C_2 D_1 ] , \quad
[ C_3 D_3 ]
$$
と、このように大小関係を少しずつ確認してみることにします。

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

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

現時点では次のようなことを考えています。

$ n $ 個の自然数が、真珠のネックレスのように、リングでつながっている。この $ n $ 個の自然数のうち、幾つ取っても良いが、隣どうし連続したものしか取れない。一つでも、二つでも、$ n $ 個全部でも良い。しかし、離れているものは取れない。この条件で取った自然数を足し合わせて、1から $ n(n-1)+1 $ までのすべての自然数ができるようにしたい。$ n $ がどのようなときに成り立つだろうか。あるいはどのようなときに成り立たないだろうか。

具体例があったほうが考えやすいので、$ n $ が少ないときの状況についてまとめておきます。

$ n $ が少ないときの状況（ $ n = 7 $ まで）は以下です。成り立つときを解あり、成り立たないときを解なしと表現しています。解ありの場合は解の数と実際の解も明記しております。ただし、自分自身で実際に確認したのは $ n = 5 $ までで、 $ n = 6, 7 $ のときは以前にネットで確認したものを載せています（解ありの $ n = 6 $ の解が条件を満たすことは確認済み）。

$ n=1 $ のとき、$ n(n-1)+1 = 1 $。解は1つ
$$
( 1 )
$$
$ n=2 $ のとき、$ n(n-1)+1 = 3 $。解は1つ
$$
( 1, 2 )
$$
$ n=3 $ のとき、$ n(n-1)+1 = 7 $。解は1つ
$$
( 1, 2, 4 )
$$
$ n=4 $ のとき、$ n(n-1)+1 = 13 $。解は2つ
$$
( 1, 2, 6, 4 ), \ ( 1, 3, 2, 7 )
$$
$ n=5 $ のとき、$ n(n-1)+1 = 21 $。解は1つ
$$
( 1, 3, 10, 2, 5 )
$$
$ n=6 $ のとき、$ n(n-1)+1 = 31 $。解は5つ（以下の解が条件を満たしていることは確認済み。他に解があるかどうかは未確認）
$$
( 1, 2, 5, 4, 6, 13 ), \ ( 1, 2, 7, 4, 12, 5 ), \ ( 1, 3, 2, 7, 8, 10 ), \\
( 1, 3, 6, 2, 5, 14 ), \ ( 1, 7, 3, 2, 4, 14 )
$$
$ n=7 $ のとき、$ n(n-1)+1 = 43 $。解なし（未確認）

解があったりなかったり、またあったとしても1つだけではなく複数あったりするので、解の公式のようなものは存在しないと思われます。解き方としてはアルゴリズム的な解き方となると思います。以前にネットで見たものも、アルゴリズムをつくって、その結果を載せていたものだったと思います。

逆元の存在の証明

エミール・アルティン『ガロア理論入門』第2章第3節続き。

$ K \subset E $ で、体 $ K $ 上の代数的な $ E $ の要素 $ \alpha $ の最小多項式 $ f(x) $ の性質を確認し、要素 $ \theta $ のつくる $ E $ の部分集合 $ E_0 $ が体であり、$ K ( \alpha ) $ であることを示そうとしています。そのために、まずは $ E_0 $ を模写した $ E_1 $ が体であることを示そうとしています。$ E_1 $ は体の公理のほとんどを満たしていて、最後の確認です。

　ここで、 $ E_1 $ が体であることを示すために $ E_1 $ の2つの要素 $ g( \xi ) \neq 0 $ と $ h( \xi ) $ が与えられたとき
$$
g( \xi ) X( \xi ) = h( \xi )
$$
となるような $ E_1 $ の要素
$$
X( \xi ) = x_0 + x_1 \xi + \cdots + x_{n-1} \xi ^{n-1}
$$
が存在することを示さねばならない。そのためには $ X( \xi ) $ の係数 $ x_i $ を未知数と考え、左辺にある積を計算し、次に等式 $ f( \xi ) = 0 $ を用いて $ \xi $ について $ n-1 $ よりも高い次数の項をなくすようにする。その結果は次の形となる。
$$
L_0 + L_1 \xi + \cdots + L_{n-1} \xi ^{n-1}
$$
ここで $ L_i $ は $ K $ の要素を係数とする $ x_1, x_2, \cdots, x_{n-1} $ の線形和である。

左辺にある積を計算するというのは、以下を計算するということです。
$$
\begin{eqnarray}
& & g( \xi ) X( \xi ) \\
&=& ( c_0 + c_1 \xi + \cdots + c_{n-1} \xi ^{n-1} ) ( x_0 + x_1 \xi + \cdots + x_{n-1} \xi ^{n-1} )
\end{eqnarray}
$$
さすがにすべて計算することはしませんが、計算して整理すると、定数項は $ c_0 x_0 $ 、$ \xi $ の項の係数は $ c_0 x_1 + c_1 x_0 $、…となります。そして $ f( \xi ) = 0 $ を使って $ \xi $ について $ n-1 $ よりも高い次数の項をなくすようにすると、係数が $ x_1, x_2, \cdots, x_{n-1} $ の線形和となるような $ \xi $ の式となります。つまり、
$$
\begin{eqnarray}
& & g( \xi ) X( \xi ) \\
&=& ( c_0 + c_1 \xi + \cdots + c_{n-1} \xi ^{n-1} ) ( x_0 + x_1 \xi + \cdots + x_{n-1} \xi ^{n-1} ) \\
&=& L_0 + L_1 \xi + \cdots + L_{n-1} \xi ^{n-1}
\end{eqnarray}
$$
としたわけです。

この結果が $ h ( \xi ) $ に一致しなければならないので、$ h ( \xi ) $ の係数を $ b_i $ とすると、次のような $ n $ 個の未知数についての $ n $ 個の方程式を得る。
$$
L_0 = b_0, \quad L_1 = b_1, \quad \cdots, \quad L_{n-1} = b_{n-1}
$$

$ g( \xi ) X( \xi ) = h( \xi ) $ より、
$$
L_0 + L_1 \xi + \cdots + L_{n-1} \xi ^{n-1} = b_0 + b_1 \xi + \cdots + b_{n-1} \xi ^{n-1}
$$
として、係数を比較して得た方程式が、
$$
L_0 = b_0, \quad L_1 = b_1, \quad \cdots, \quad L_{n-1} = b_{n-1}
$$
です。

この連立方程式が解をもつためには、対応する同次連立方程式
$$
L_0 = 0, \quad L_1 = 0, \quad \cdots, \quad L_{n-1} = 0
$$
が自明解しかもたないことを示せばよい。ところがあとの連立方程式は、$ g( \xi ) X( \xi ) = 0 $ をみたす要素 $ X( \xi ) $ を問題にしたときに得られる方程式である。これは古い意味の乗法にもどって $ g( \xi ) X( \xi ) $ を考えたとき、 $ g( \xi ) X( \xi ) $ の剰余が $ 0 $ 、すなわち $ g( \xi ) X( \xi ) $ が $ f( \xi) $ で割りきれる場合である。ところが42ページの補題により、これは $ X( \xi) = 0 $ の場合のみ起こりうることである。すなわち上の同次方程式は自明解しかもち得ない。

第1章で定理5として、同次連立方程式が解をもつ必要十分条件が挙げられています。

定理5
$ m = n $ の場合の連立方程式 $ (1) $ が、任意に与えた右辺に対して解をもつための必要十分条件は、これに同伴な同次連立方程式が自明解のみをもつことである。そしてこの場合、解はただ一組である。

$ m = n $ の場合の連立方程式 $ (1) $ とは、以下の方程式で $ m = n $ の場合です。

$$
\begin{eqnarray}
a_{11} x_1 &+& a_{12} x_2 &+& \cdots &+& a_{1n} x_n &=& b_1 \\
a_{21} x_1 &+& a_{22} x_2 &+& \cdots &+& a_{2n} x_n &=& b_2 \\
\vdots && && && \vdots && \vdots \\
a_{m1} x_1 &+& a_{m2} x_2 &+& \cdots &+& a_{mn} x_n &=& b_m
\end{eqnarray}
\tag{1}
$$

そして連立方程式 $ (1) $ に同伴な同次連立方程式は次の同次連立方程式 $ (2) $ となります。

$$
\begin{eqnarray}
a_{11} x_1 &+& a_{12} x_2 &+& \cdots &+& a_{1n} x_n &=& 0 \\
a_{21} x_1 &+& a_{22} x_2 &+& \cdots &+& a_{2n} x_n &=& 0 \\
\vdots && && && \vdots && \vdots \\
a_{m1} x_1 &+& a_{m2} x_2 &+& \cdots &+& a_{mn} x_n &=& 0
\end{eqnarray}
\tag{2}
$$

また、42ページの補題は以下です。

補題
$ f(x) $ を $ K $ 内の次数 $ n $ の既約多項式とするとき、0と異なる2つの $ K $ 内の多項式でそれらの次数が $ n $ より小、しかもそれらの積は $ f(x) $ で割りきれるようなものは存在し得ない。

この補題から、$ g( \xi ) X( \xi ) = 0 $ となるのは $ X( \xi) = 0 $ の場合のみ起こりうることであり（ $ g( \xi ) $ と $ X( \xi ) $ の次数は $ n-1 $ で、$ f ( \xi ) $ より小。また $ g( \xi ) \neq 0 $ ）、同次連立方程式
$$
L_0 = 0, \quad L_1 = 0, \quad \cdots, \quad L_{n-1} = 0
$$
は自明解しかもたない。したがって、定理5より
$$
L_0 = b_0, \quad L_1 = b_1, \quad \cdots, \quad L_{n-1} = b_{n-1}
$$
は解をもつ。未知数 $ x_i $ が解をもつということは、 $ x_i $ は $ X( \xi ) $ の係数ですので、$ g( \xi ) X( \xi ) = h( \xi ) $ となるような $ E_1 $ の要素 $ X( \xi ) = x_0 + x_1 \xi + \cdots + x_{n-1} \xi ^{n-1} $ が存在する、となります。

こうして、$ E_1 $ が体であることが示されました。

2019/12/17

逆元の存在の確認

エミール・アルティン『ガロア理論入門』第2章第3節の続きです。

$ K \subset E $ で、体 $ K $ 上の代数的な $ E $ の要素 $ \alpha $ の最小多項式 $ f(x) $ の性質を確認し、要素 $ \theta $ のつくる $ E $ の部分集合 $ E_0 $ が体であり、$ K ( \alpha ) $ であることを示そうとしています。そのために、まずは $ E_0 $ を模写した $ E_1 $ が体であることを示そうとしています。 $ E_1 $ は、体の公理のほとんどが満たされていて、残るは、乗法に関して、0以外のすべての要素について逆元が存在することを示すことです。

　ここで、 $ E_1 $ が体であることを示すために $ E_1 $ の2つの要素 $ g( \xi ) \neq 0 $ と $ h( \xi ) $ が与えられたとき
$$
g( \xi ) X( \xi ) = h( \xi )
$$
となるような $ E_1 $ の要素
$$
X( \xi ) = x_0 + x_1 \xi + \cdots + x_{n-1} \xi ^{n-1}
$$
が存在することを示さねばならない。

逆元とは、次のような要素です。

逆元の定義（逆元の公理）
$ a $ を集合 $ G $ の要素とし、$ e $ を単位元とする。$ a $ に対して、以下の式を満たす $b \in G $ を、演算★に関する $ a $ の逆元と呼ぶ。
$$
a★b = b★a = e
$$

$ g( \xi ) X( \xi ) = h( \xi ) $ となるような $ X( \xi ) $ が存在することを示すことが、なぜ、乗法に関して0以外のすべての要素について逆元が存在することを示すことになるのか。

きちんとした証明になっているかどうかは少し怪しいですが、現時点での僕なりの理解を書いておきます。

もし $ X( \xi ) $ が存在するとすれば、$ X( \xi ) = g^{-1}( \xi ) h( \xi ) $ となるはずです。
$$
g( \xi ) X( \xi ) =g( \xi ) g^{-1}( \xi ) h( \xi ) = h( \xi )
$$
つまり、$ g( \xi ) $ の逆元である $ g^{-1}( \xi ) $ が存在すれば、$ X( \xi ) $ も存在することになります。もし $ g^{-1}( \xi ) $ が存在しなければ、$ X( \xi ) $ も存在しません（この部分の証明が必要な気がします）。なので、$ g( \xi ) X( \xi ) = h( \xi ) $ となるような $ X( \xi ) $ が存在することを示すことは、$ g^{-1}( \xi ) $ が存在することを示すことと同値であるといえます（いえると思っています）。

たとえ話ですが、次のようなことを考えてみましょう。方程式 $ 2x = 3 $ を満たす整数 $ x $ は存在しません。有理数であれば $ x = \frac{3}{2} $ と答えることができます。 $ \frac{3}{2} $ が存在すれば、$ \frac{1}{2} $ も存在するといえます（こちらのたとえ話でもちょっと曖昧です）。

整数全体の集合は体ではありません。有理数全体の集合は体です。整数の場合、除法について閉じてはいませんが、有理数の場合は除法でも閉じています。体は四則演算ができる数の集合といってもいいものです。 $ g( \xi ) X( \xi ) = h( \xi ) $ となるような $ E_1 $ の要素 $ X( \xi ) = x_0 + x_1 \xi + \cdots + x_{n-1} \xi ^{n-1} $ が存在することを示すことは、$ E_1 $ 内で除法ができることを示すことでもあります。

逆元の存在についてちょっと曖昧にしたままですが、次に進みます。

2次方程式の判別式

2次方程式 $ ax^2 +bx + c = 0 ( a \neq 0 ) $ の解の公式、
$$
x = \frac{ -b \pm \sqrt{ b^2 - 4ac }}{ 2a }
$$
の根号（ルート）の中身である $ b^2 - 4ac $ は、2次方程式の判別式と呼ばれる。判別式のことを英語で discriminant というので、判別式は $ D $ で表記されることが多い。
$$
D = b^2 - 4ac
$$
判別式が何を判別しているのかというと、解がどのようなものなのかを判別している。

ここでは、2次方程式 $ ax^2 +bx + c = 0 $ の係数 $ a, b, c $ は有理数としよう。またこの2次方程式の解を $ \alpha , \beta $ とする。

2次方程式の判別式 $ D $ は、最初に述べたように、2次方程式の解の公式にある根号（ルート）の中身である。 $ D = 0 $ であれば、$ \sqrt{D} = 0 $ となり、解は
$$
x = \frac{ -b \pm 0 }{ 2a } = - \frac{ b }{ 2a }
$$
となる。2次方程式は基本的に2つの解をもつが、このときの解は1つである。解が1つというのは $ \alpha = \beta $ のときであると考えて、重解をもつという。$ D = 0 $ であれば、重解をもつ。ここでは係数は有理数であるので、解 $ - \frac{ b }{ 2a } $ も有理数である。

$ D \gt 0 $ のときは、2つの実数解をもつ。係数 $ a, b, c $ が有理数であっても根号が残るので、解は実数となる。ただし、$ D $ が平方数であれば根号がはずれ、解が有理数となる。

$ D \lt 0 $ のときは、2つの虚数解をもつ。根号の中身がマイナスとなるので、実数範囲では解なしとなる。

四則演算ができる数の集合を体という。また係数が属する体を係数体と呼ぶ。

係数体が有理数体であるとき、$ D = 0 $ であれば解も係数体である有理数体に属する。また $ D $ が平方数であるときも解は有理数体に属する。$ D $ が平方数でなく、$ D \gt 0 $ のときは、有理数範囲では解なしとなる。解は、係数体である有理数体ではなく、実数体に属する。$ D \lt 0 $ のときは実数体にもなく、解は複素数体に属する。

判別式は差積で定義されている。2次方程式の解の差積は $ \alpha - \beta $（あるいは $ \beta - \alpha $）である。差積は $ \Delta $ で書かれることが多い。この差積 $ \Delta $ を2乗して、解と係数の関係を使って係数で表すと、
$$
\begin{eqnarray}
\Delta ^2 = ( \alpha - \beta )^2 &=& \alpha ^2 - 2 \alpha \beta + \beta ^2 \\
&=& ( \alpha ^2 + 2 \alpha \beta + \beta ^2 ) - 4 \alpha \beta \\
&=& ( \alpha + \beta ) ^2 - 4 \alpha \beta \\
&=& \left( - \frac{b}{a} \right ) ^2 - 4 \left( \frac{c}{a} \right ) \\
&=& \frac{b^2}{a^2} - \frac{4c}{a} \\
&=& \frac{ b^2 - 4ac }{a^2}
\end{eqnarray}
$$
と、分子に判別式 $ b^2 - 4ac $ が現れる。

2次方程式 $ ax^2 +bx + c = 0 $ の両辺を $ a $ で割って、 $ x^2 + \frac{b}{a}x + \frac{c}{a} = 0 $ とし、$ p = \frac{b}{a}, q = \frac{c}{a} $とすると、$ x^2 + px + q = 0 $ と書ける。解は $ \alpha , \beta $ で変わらない。

この2次方程式 $ x^2 + px + q = 0 $ での解の公式は、
$$
x = \frac{ -p \pm \sqrt{ p^2 - 4q }}{ 2 }
$$
となり、判別式は $ D = p^2 - 4q $ となる。また、差積 $ \Delta ^2 $ は、
$$
\begin{eqnarray}
\Delta ^2 = ( \alpha - \beta )^2 &=& ( \alpha + \beta ) ^2 - 4 \alpha \beta \\
&=& ( - p ) ^2 - 4q \\
&=& p^2 - 4q
\end{eqnarray}
$$
となり、判別式に一致する。

重解をもつときは $ \alpha = \beta $ のときであり、言い換えると、 $ \alpha - \beta = 0 $ のときである。判別式 $ D = \Delta ^2 $ であればよくわかる。また $ \alpha, \beta $ が有理数であれば、$ \Delta = \alpha - \beta $ も有理数となり、$ D = \Delta ^2 $ は有理数の平方数となることもよくわかる。

2019/12/15

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

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

前回、このビリヤードの問題を一般化して考えるとどのような問題になるのかについて考えてみました。現時点では次のようなことを考えています。

$ n $ 個の自然数が、真珠のネックレスのように、リングでつながっている。この $ n $ 個の自然数のうち、幾つ取っても良いが、隣どうし連続したものしか取れない。一つでも、二つでも、$ n $ 個全部でも良い。しかし、離れているものは取れない。この条件で取った自然数を足し合わせて、1から $ n(n-1)+1 $ までのすべての自然数ができるようにしたい。$ n $ がどのようなときに成り立つだろうか。あるいはどのようなときに成り立たないだろうか。

考え方も一般化していきたいので、さらに記号を導入していきます。ひょっとすると使わないような記号や定義があるかもしれませんが、考えられるだけ考えておきます。

まずは、$ n $ 個の自然数がリングでつながっている状態を図ではなく、数式のように表していくことを考えました。5個のビリヤード玉の問題を解いたときにはＡ－Ｂ－Ｃ－Ｄ－Ｅというような表記の仕方をしましたが、今後は一般化をみこして、ここでは $ \langle a_5 \rangle $ と表記していきます。$ \langle a_5 \rangle $ は、5個の自然数 $ a_1, a_2, a_3, a_4, a_5 $ がこの順序でリング状につながっていることを表します。$ \langle a_n \rangle $ ならば、$ n $ 個の自然数が、右回りで $ a_1, a_2, \cdots, a_n $ とつながっていて、最後の $ a_n $ が $ a_1 $ につながっています。当然のこと（？）ながら、$ a_1, a_2, \cdots, a_n $ は自然数です。

なので、$ \langle a_n \rangle $ を循環する数列とみることもできます。$ \langle a_5 \rangle $ ならば、 $ a_1, a_2, a_3, a_4, a_5, a_1, a_2, \cdots $ と続いていく数列です。ここでは循環数列と呼んでいきます。循環数列という言葉はあるようですが、一般の循環数列の定義をしっかりとは知らないので、一般的な循環数列の定義とは異なるかもしれません。

循環小数で循環する間隔（？）のことを長さと表現します。$ 0.121212\cdots $ ならば $ 12 $ が循環しているので循環の長さは $ 2 $ となります。$ 0.333333\cdots $ ならば長さは $ 1 $ 、$ 0.456745674567\cdots $ ならば、長さは $ 4 $ です。

ここでの循環数列 $ \langle a_n \rangle $ も、循環小数での言葉にならい、長さ $ n $ の循環数列と呼びます。$ \langle a_5 \rangle $ は、長さ $ 5 $ の循環数列です。また、数列にならい、 $ a_1, a_2, \cdots, a_n $ を初項（第1項）、第2項、…、第 $ n $ 項と呼びます（「第」をつけず単に $ n $ と呼ぶ場合もあり）。第 $ n+1 $ 項ということも言いますが、（長さ $ n $ の場合、）値としては第1項と同じ値です。

また、ここで考えていく循環数列の特徴として、「この $ n $ 個の自然数のうち、幾つ取っても良いが、隣どうし連続したものしか取れない。一つでも、二つでも、$ n $ 個全部でも良い。しかし、離れているものは取れない。この条件で取った自然数を足し合わせて、1から $ n(n-1)+1 $ までのすべての自然数ができるようにしたい」ということがあります。そこで、この特徴を表せるような表記も考えておきます。簡略化となるかどうかはわかりませんが、一応簡略化のための表記です。（逆にわかりにくくなってしまいこの表記ボツにするかもしれません。）

この条件での取り出し方のひとつに、$ a_1, a_2, \cdots, a_n $ の初項 $ a_1 $ と第2項 $ a_2 $ を取り出すということがあります。そして、$ a_1 + a_2 $ を計算することになります。この $ a_1 + a_2 $ を、$ a(2) _1 $ と表したいと思います。$ a(2) _1 = a_1 + a_2 $ です。括弧()の中の2は2つの項を足したという意味で、添字は足し算の最初の項という意味です。$ a(3) _1 $ ならば、$ a(3) _1 = a_1 + a_2 + a_3 $、$ a(4) _2 $ ならば $ a(4)_2 = a_2 + a_3 + a_4 + a_5 $ という意味です。循環の長さより大きな項が出てきたときは、同じ値の項に変換します（ここはうまく表現できていませんが、やっていくうちにわかるかと思います）。

もうひとつ、表記の仕方の（ここでの）ルールとして、次のようなことを挙げておきます。

以前、5個のビリヤード玉での解答として①－⑤－②－⑩－③（－①）を挙げましたが、これは①－③－⑩－②－⑤（－①）と同じものと見なします。この2つは、右回りか左回りの違い、別の表現では裏返したら同じです。また、⑤－②－⑩－③－①（－⑤）も同じものです。同じものを表すのに、いくつもの表記があるとわかりにくいので、①を初項として表記することを基本として、②がなるべく前にあるものを代表として表記とします。もしかすると計算過程などでこのルールとズレることがあるかもしれませんので、そこまで厳密ではありません。

まぁ、うだうだと書いておりますが、あまり考えが進んでいないことはわかったかと思います。

体の公理の確認

エミール・アルティン『ガロア理論入門』第2章第3節の続きです。

$ K \subset E $ で、体 $ K $ 上の代数的な $ E $ の要素 $ \alpha $ の最小多項式 $ f(x) $ の性質を確認し、いまは次のような要素 $ \theta $ のつくる $ E $ の部分集合 $ E_0 $ が体であり、$ K ( \alpha ) $ であることを示そうとしています。そのために、まずは $ E_0 $ を模写した $ E_1 $ が体であることを示そうとしています。 $ E_1 $ に体の乗法として新しい乗法を定義し、$ E_1 $ が体の定義に当てはまるかどうかの確認をしているところです。

　ここでわれわれは古い意味の乗法を完全にやめることにして、新しい乗法だけを扱うことにする。また、記号をかえて新しい乗法を点（または並べておくだけ）を用いて表わすことにする。
このような意味で演算
$$
c_0 + c_1 \xi + \cdots + c_{n-1} \xi ^{n-1}
$$
の結果を考えてみると、次数が $ n $ より小さいので、演算の結果ははじめからこの形に表わされている $ E_1 $ の要素に一致する。また
$$
\xi ^n = -a_{n-1} \xi ^{n-1} - a_{n-2} \xi ^{n-2} - \cdots - a_0
$$
であるから、移項して $ E_1 $ 内で $ f( \xi ) = 0 $ のなりたつことがわかる。
以上のようにして、集合 $ E_1 $ をつくり、次にその中で加法と乗法をつくり、この演算について、体の公理がほとんど満たされていることがわかった。さらに $ E_1 $ は $ K $ を部分体に含み、方程式 $ f( \xi ) = 0 $ を満たす要素を含んでいる。

新しい乗法を定義した上で、体の公理（定義）に当てはまるかどうかを確認し、そのほとんどの確認ができました。残るは、乗法に関して、0以外のすべての要素について逆元が存在することを示すことです。次のことはそのことを表わしていると思われます。

　ここで、 $ E_1 $ が体であることを示すために $ E_1 $ の2つの要素 $ g( \xi ) \neq 0 $ と $ h( \xi ) $ が与えられたとき
$$
g( \xi ) X( \xi ) = h( \xi )
$$
となるような $ E_1 $ の要素
$$
X( \xi ) = x_0 + x_1 \xi + \cdots + x_{n-1} \xi ^{n-1}
$$
が存在することを示さねばならない。

逆元とは、次のような要素です。

$ g( \xi ) X( \xi ) = h( \xi ) $ となるような $ X( \xi ) $ が存在することを示すことが、なぜ、乗法に関して0以外のすべての要素について逆元が存在することを示すことになるのか。次はそこを考えてみます。

2019/12/14

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

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？

この問題を一般的な問題におきかえることができるとしたらどのようになるのかについて考えてみます。

問題では5個のビリヤード玉で、取った玉のナンバを足し合わせて1から21までのすべての数ができるようにしたいとしていますが、これは、玉のとり方が$ 21 $ 通りあるからであるとします。$ n $ 個の場合だと、玉の取り方は $ n(n-1)+1 $ 通りとなります。ここから確認していきましょう。

まずは5個の場合を考えます。リング状につながったビリヤード玉に記号をつけておきます。右回りに「Ａ－Ｂ－Ｃ－Ｄ－Ｅ」とつながっているとします。リング状ですので最後のＥはＡにつながっています。

まずは、1個を取る場合。これはＡを取るか、Ｂを取るか、Ｃを取るか、Ｄを取るか、Ｅを取るかの5通り。2個の場合は、Ａ－Ｂ、Ｂ－Ｃ、Ｃ－Ｄ、Ｄ－Ｅ、Ｅ－Ａの5通り。3個の場合は、Ａ－Ｂ－Ｃ、Ｂ－Ｃ－Ｄ、Ｃ－Ｄ－Ｅ、Ｄ－Ｅ－Ａ、Ｅ－Ａ－Ｂの5通り。4個の場合は、Ａ－Ｂ－Ｃ－Ｄ、Ｂ－Ｃ－Ｄ－Ｅ、Ｃ－Ｄ－Ｅ－Ａ、Ｄ－Ｅ－Ａ－Ｂ、Ｅ－Ａ－Ｂ－Ｃの5通り。5個の場合は、Ａ－Ｂ－Ｃ－Ｄ－Ｅの1通りとなります。$ 5+5+5+5+1 = 21 $ で、$ 21 $ 通りとなります。

$ n $ 個の場合だと、1個を取る取り方が $ n $ 通り、2個も $ n $ 通り、3個も $ n $ 通り、……、 $ n-1 $ 個も $ n $ 通り、 $ n $ 個すべてを取るのが1通りとなり、合計 $ n(n-1) + 1 $ 通りとなります。

なので問題を一般化するとすれば、$ n $ 個のビリヤード玉で、1から$ n(n-1) + 1 $ までのすべての数ができるように、ということになります。玉を取る条件は変わりません。

5個のビリヤード玉のときは、1から21までのすべての自然数をつくることができましたが、他の個数のときには解答があるかどうかわかりません。また、一意に定まるかどうかもわかりません。実際、確認したところでは、1個のときは解あり（1つ）、2個のときも解あり（1つ）、3個の場合も解あり（1つ）、4個の場合は解ありですが2つの解、5つのときは解あり（1つ）。また、詳細未確認ですが、6個のときは複数解あり、7個のときは解なしとなるようです。（以前に書いたブログより。以前のブログに参照したサイトのリンクをつけていましたが、リンク切れとなっていました。6個のときと7個のときは検証が必要です。）

そこでこれから考えていく問題文を以下のようにしたいと思います。厳密さを要求するならばもう少ししっかりと書いたほうがいいのかもしれませんが、いまはこのくらいで。

$ n $ 個の自然数が、真珠のネックレスのように、リングでつながっている。この $ n $ 個の自然数のうち、幾つ取っても良いが、隣どうし連続したものしか取れない。一つでも、二つでも、$ n $ 個全部でも良い。しかし、離れているものは取れない。この条件で取った自然数を足し合わせて、1から $ n(n-1)+1 $ までのすべての自然数ができるようにしたい。$ n $ がどのようなときに成り立つだろうか。あるいはどのようなときに成り立たないだろうか。

2019/12/13

多項式の剰余演算

エミール・アルティン『ガロア理論入門』第2章第3節の続き。

$ K \subset E $ で、体 $ K $ 上の代数的な $ E $ の要素 $ \alpha $ の最小多項式 $ f(x) $ の性質を確認し、いまは次のような要素 $ \theta $ のつくる $ E $ の部分集合 $ E_0 $ が体であり、$ K ( \alpha ) $ であることを示そうとしています。そのために、まずは $ E_0 $ を模写した $ E_1 $ が体であることを示そうとしています。 $ E_1 $ に体の乗法として新しい乗法を定義し、新しい乗法と通常の乗法との対応、そして $ E_1 $ が体の定義に当てはまるかどうかの確認をしているところです。

新しい乗法を $ g( \xi ) \times h( \xi ) $ と表わします。そして $ g( \xi ) \times h( \xi ) $ とは、通常の積 $ g( \xi ) h( \xi ) $ の $ f(x) $ を法とした剰余 $ r( \xi ) $ のことです。

前回は、$ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) $ は通常の積 $ g_1 ( \xi ) g_2 ( \xi ) \cdots g_m( \xi ) $ の剰余に等しいことを示しました。今回はこの続きです。

さて、この事実からわれわれの新しい積が結合法則および交換法則をみたすことがわかる。また通常の積 $ g_1( \xi ) g_2 ( \xi ) \cdots g_m ( \xi ) $ の次数が $ n $ に達しないときは、新しい意味での積 $ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) $ はこの通常の積 $ g_1( \xi ) g_2 ( \xi ) \cdots g_m ( \xi ) $ に一致することもわかる。この新しい乗法が分配法則を満たすことも簡単に示すことができる。

証明は記載されていませんし、ここでの証明もしませんが、新しい乗法が結合法則、交換法則を満たすこと、通常の積 $ g_1( \xi ) g_2 ( \xi ) \cdots g_m ( \xi ) $ の次数が $ n $ に達しないときは、新しい意味での積 $ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) $ はこの通常の積 $ g_1( \xi ) g_2 ( \xi ) \cdots g_m ( \xi ) $ に一致すること、分配法則を満たすことを確認しています。

集合 $ E_1 $ は体 $ K $ を含み、 $ E_1 $ における新しい乗法を $ K $ 内に限れば、 $ K $ 内のもともとの乗法に一致している。また $ \xi $ は $ E_1 $ に含まれている多項式の1つである。これ自身を $ i $ 回かけた結果は、$ i \lt n $ である限り $ \xi ^i $ である。ところが $ i = n $ のときは多項式 $ \xi ^n $ の剰余を計算しなければならない。この剰余は次のようになる。
$$
\xi ^n - f( \xi ) = -a_{n-1} \xi ^{n-1} - a_{n-2} \xi ^{n-2} - \cdots - a_0
$$

通常の積 $ g_1( \xi ) g_2 ( \xi ) \cdots g_m ( \xi ) $ の次数が $ n $ に達しないときは、新しい意味での積 $ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) $ はこの通常の積 $ g_1( \xi ) g_2 ( \xi ) \cdots g_m ( \xi ) $ に一致しますが、通常の積 $ g_1( \xi ) g_2 ( \xi ) \cdots g_m ( \xi ) $ の次数が $ n $ に達したときには違いが生じます。

整数の割り算の余りは、割る数よりも小さくなければいけません。たとえば13÷5＝2余り3ですが、13÷5＝1余り8とはしません。多項式の割り算の余り（剰余）も条件があり、多項式の場合は、法である割る多項式（表現を知らないが、整数の割り算で割る数にあたる多項式）の次数よりも低次であることが条件となります。

ここで考えている新しい乗法での法は f(x) で、次数はn です。ですので次数がnの多項式は余りとはなりません。

13÷5＝1余り8のように余りが割る数を超えているとき、余り8から5を引いて余り3とします（その分、商も変わります）。多項式の余りも、割る数（割る多項式）の次数を超えてしまった場合、余りからその次数の項が消えるように引き算します。それが $ \xi ^n - f( \xi ) $ という式の意味するところです。

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

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？

最終的には $ n $ 個のビリヤード玉で解が存在するかどうか、存在するとすればその求め方、存在しないとすればその証明などを明らかにしたいと思いますが、そこまで行き着けない可能性もあります。

まずは、5個のビリヤード玉での解法を確認します。解法といっても、僕が以前に解いたやり方（場合分けによる総当り的なやり方）ですので、もう少しスマートな解法があるかもしれません。あらためて解くことで、そういった解法に出会えるかもしれませんし、当たり前と思ってさらっと流していた条件などに気づけるかもしれませんので、もう一度あらためて解いてみたいと思います。なので少し細かく書いているので冗長な部分があるかと思います。

条件とか、ここでの表記の仕方についての確認しながら解いていきます。

5個のビリヤード玉を、Ａ・Ｂ・Ｃ・Ｄ・Ｅとして、この順で右回りにリングでつながっているとします。Ａ－Ｂ－Ｃ－Ｄ－Ｅ（－Ａ）とつながっていて、最後のＥとＡがつながってリング状になっている状態です。書かれているナンバは自然数とします。5つの玉のうち、幾つ取っても良いが隣どうし連続したものしか取れません。この条件で取った玉のナンバを足し合わせて、1から21までのすべての自然数ができるようにします。

問題の条件での玉の取り方が何通りあるかを数えると、$ 21 $ 通りあります。まずは、1個を取る場合。これはＡを取るか、Ｂを取るか、Ｃを取るか、Ｄを取るか、Ｅを取るかの5通り。2個の場合は、Ａ－Ｂ、Ｂ－Ｃ、Ｃ－Ｄ、Ｄ－Ｅ、Ｅ－Ａの5通り。3個の場合は、Ａ－Ｂ－Ｃ、Ｂ－Ｃ－Ｄ、Ｃ－Ｄ－Ｅ、Ｄ－Ｅ－Ａ、Ｅ－Ａ－Ｂの5通り。4個の場合は、Ａ－Ｂ－Ｃ－Ｄ、Ｂ－Ｃ－Ｄ－Ｅ、Ｃ－Ｄ－Ｅ－Ａ、Ｄ－Ｅ－Ａ－Ｂ、Ｅ－Ａ－Ｂ－Ｃの5通り。5個の場合は、Ａ－Ｂ－Ｃ－Ｄ－Ｅの1通りとなります。$ 5+5+5+5+1 = 21 $ で、$ 21 $ 通りとなります。この $ 21 $ 通りで1から21までのすべての自然数をつくるので、Ａ・Ｂ・Ｃ・Ｄ・Ｅはすべて異なる自然数で、玉の取り方1つに対し、1から21までの自然数のどれかが対応することになります。

したがって、①は必ず入っていることになります。ここでは1と書かれているビリヤード玉を①と書きます。1をつくるのには①が必要です。①の場所をＡに固定して考えます。これをＡ=①と書きます。Ａ－Ｂ－Ｃ－Ｄ－Ｅ（－Ａ）とつながっているので、①－Ｂ－Ｃ－Ｄ－Ｅ（－①）となります。

そして②も必ず入っていることになります。2をつくるためには $ 1+1 $ でもつくれますが、ビリヤード玉に書かれている自然数はすべて異なる自然数となりますので、①+①という組み合わせはありません。②も必ず存在することになりますが、場所はわかりません。

また、$ Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 $ となります。Ａ・Ｂ・Ｃ・Ｄ・Ｅを場所と言ったり、文字式の中に使ったりしてしまいますが、ご容赦ください。このあたり、一般化して考えるときにはもう少し表記の仕方を考えなければならないかもです。

Ａ=①として、その隣に②があるかどうかで場合分けをして考えます。もし①の隣に②があれば、$ ①+②=3$ となり、③の玉は不要になります。逆に①の隣に②がなければ③の玉が必要になります。もし3を自然数の和で表すとすれば、$ 1+2 $ しか存在しないためです。（Mathjaxを使って書いており、フォントが異なってしまっているところがあります。フォントの違いは無視してください。区別しなければならないときはその旨記載します。）

Ａ=①の隣ということは、ＢかＥとなりますが、ＢでもＥでも裏返して考えると同じになるので、ここではＢ=②かどうかで考えます。

(i) ①の隣に②がある場合（Ｂ=②の場合）
つまり、①－②－Ｃ－Ｄ－Ｅ（－①）の場合です。

残りのＣ・Ｄ・Ｅについて考えると、①、②は使われていて、3は①+②で不要ですので、4以上の自然数となります。また、$ Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 $ ですので、$ Ｃ+Ｄ+Ｅ=18 $ です。このような相異なる自然数の組となるものは、{ ④, ⑤, ⑨ } { ④, ⑥, ⑧ } { ⑤, ⑥, ⑦ } の3組です。{}でくくった組み合わせは順番関係なしの組み合わせとします。このうち { ⑤, ⑥, ⑦ } では4をつくることができませんので、残るは { ④, ⑤, ⑨ } { ④, ⑥, ⑧ } です。

④が存在しなければならないことになるので、④が①－②－Ｃ－Ｄ－Ｅ（－①）のどこに入るかを場合分けして考えます。

(i-a) Ｃ=④の場合
つまり、①－②－④－Ｄ－Ｅ（－①）の場合です。

この状態では5をつくることができませんので⑤が必要となり、Ｃ・Ｄ・Ｅの組み合わせは、{ ④, ⑤, ⑨ } となります。しかし、①－②－④－⑤－⑨（－①）としても、①－②－④－⑨－⑤（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｃ=④ではありません。

(i-b) Ｄ=④の場合
つまり、①－②－Ｃ－④－Ｅ（－①）の場合です。

この場合も⑤が必要となり、Ｃ・Ｄ・Ｅの組み合わせは、{ ④, ⑤, ⑨ } となります。しかし、①－②－⑤－④－⑨（－①）としても、①－②－⑨－④－⑤（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｄ=④でもありません。

(i-c) Ｅ=④の場合
つまり、①－②－Ｃ－Ｄ－④（－①）の場合です。

この場合は、④+①で5をつくれます。したがって、Ｃ・Ｄ・Ｅの組み合わせは { ④, ⑥, ⑧ } となります。しかし、①－②－⑥－⑧－④（－①）としても、①－②－⑧－⑥－④（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｅ=④でもありません。

したがって、(i)①の隣に②がある場合は解なしです。

(ii) ①の隣に②がない場合
つまり、①－Ｂ－②－Ｄ－Ｅ（－①）か、①－Ｂ－Ｃ－②－Ｅ（－①）の場合ですが、この2つは裏返すと同じものですので、①－Ｂ－②－Ｄ－Ｅ（－①）として考えます。

①と②が離れているので、③が必要になります。そこで、③の場所で場合分けして考えます。

(ii-a) Ｂ=③の場合
つまり、①－③－②－Ｄ－Ｅ（－①）の場合です。

この場合は、①、②、③、①+③、③+②、①+③+②と、6までの自然数がつくれます。7をつくるには、Ｄ=⑤とするか、ＤかＥに⑦が存在するかのどちらかです。

(ii-a1) Ｄ=⑤の場合
この場合は、$ Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 $ から、①－③－②－⑤－⑩（－①）となります。しかし、8をつくることができません。

(ii-a2) ＤかＥに⑦が存在する場合
この場合、残るひとつは⑧になります。したがって、①－③－②－⑦－⑧（－①）か、①－③－②－⑧－⑦（－①）です。しかし、どちらも1から21までのすべての自然数をつくることができません（前者は10がつくれない。後者は⑧と⑦+①で8がダブる）。

したがって、(ii-a) Ｂ=③の場合、解なしです。

(ii-b) Ｄ=③の場合
つまり、①－Ｂ－②－③－Ｅ（－①）の場合です。

この場合、④が必要となります。したがって残る1つは⑪となり、①－④－②－③－⑪（－①）か、①－⑪－②－③－④（－①）となります。しかし、どちらも1から21までのすべての自然数をつくることができません（どちらも5がダブる）。

したがって、(ii-b) Ｄ=③の場合も、解なしです。

(ii-c) Ｅ=③の場合
つまり、①－Ｂ－②－Ｄ－③（－①）の場合です。

この場合、③+①で4がつくれます。このままでは5がつくれないので⑤が必要です。⑤が決まれば、残りは⑩となります。したがって、①－⑤－②－⑩－③（－①）か、①－⑩－②－⑤－③（－①）です。後者は6がつくれません。前者の場合は、1から21までのすべての自然数をつくることができます。

念のため、確認してみましょう。

①

②

③

③+①

⑤

①+⑤

⑤+②

①+⑤+②

③+⑤+①

⑩

③+①+⑤+②

②+⑩

⑩+③

⑩+③+①

②+⑩+③

②+⑩+③+①

⑤+②+⑩

①+⑤+②+⑩

⑩+③+①+⑤

⑤+②+⑩+③

①+⑤+②+⑩+③

1から21までのすべての自然数をつくれることが確認できました。

したがって、5つのビリヤード玉の問題の答えは、①－⑤－②－⑩－③（－①）となります。

さて、これを一般化して考えるにはどうすればよいでしょうか。

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

森博嗣さんの『笑わない数学者』の中で、数学者天王寺博士が出す問題の一つに、以下の問題があります。

五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？

小説内では解答も解法も載っておらず、読んだ当時に力づくで解きました。しかし、小説内ではさらに以下のようなやり取りがあります。

天王寺博士の宿題について少し議論した。問題は玉の数が五個だったが、四個の場合も問題が成立する。では、六個はどうか、$ n $ 個ではどうか、という話だった。

$ n $ 個の場合に問題が成立するかどうかについては、以前考えてみたものの煮詰まって途中で投げ出しておりました。

以前は力づくで解いたのですが、もう少しスマートな方法はないか、また、$ n $ 個の場合に問題が成立するかどうかについてなど、あらためて考えてみたいと思います。

（以前途中で投げ出した記事はこちら）

５つのビリヤード玉の問題(1)(2)(3)(4)(5)(6)、試行錯誤編(1)(2)

これから考えていくことの方向性としては、次のようなことを考えます。まずは5つのビリヤード玉での問題をどのように解いたのかの整理。次に5つではなく4つとか6つとか他の場合での解き方や解答の確認。そこから一般的な問いや条件、解き方などを見出していき、最終的には、$ n $ 個の場合に問題が成立するかどうか、言い換えると、$ n $ がどのようなときに解答が存在するのか、存在するならばその解き方を、存在しないならばなぜなのかを明らかにできればいいと考えています。

書きながら考えているので、まだ結論はでておりませんので、（以前のように）途中で放棄するかも。

まずは5つのビリヤード玉で、問題をどのように解いたのかの整理していきたいと思います。

2019/12/12

証明に取り組む

エミール・アルティン『ガロア理論入門』第2章第3節で、証明を読者にまかされたところがある。

ここで $ E_1 $ の2つの要素 $ g( \xi ) $ と $ h( \xi ) $ に対して通常の積のほかに新しい乗法を定義し、それを $ g( \xi ) \times h( \xi ) $ と表わす。すなわち $ g( \xi ) \times h( \xi ) $ とは通常の積 $ g( \xi ) h( \xi ) $ の $ f(x) $ を法とした剰余 $ r( \xi ) $ のことと定義する。するとまず、$ g_1 ( \xi ) $, $ g_2 ( \xi ) $ , $ \cdots $, $ g_m( \xi ) $ の積 $ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) $ は通常の積 $ g_1 ( \xi ) g_2 ( \xi ) \cdots g_m( \xi ) $ の剰余に等しいことがわかる。この性質は $ m = 2 $ のときは定義から明らかであり、任意の $ m $ に対しては次の性質と数学的帰納法とを用いて示される。その性質とは
“ $ g_1( \xi ) $ と $ g_2( \xi ) $ の剰余をそれぞれ $ r_1( \xi ) $ と $ r_2( \xi ) $ とすると $ g_1( \xi ) g_2( \xi ) $ と $ r_1( \xi ) r_2( \xi ) $ とは同じ剰余をもつ”
ということである。この証明の詳細は読者にまかせよう。

この証明に取り組んでみよう。

もう少しスマートな証明方法、書き方があるかもしれないし、不足部分もあるかもしれない。

（以下、証明）

まず「$ g_1( \xi ) $ と $ g_2( \xi ) $ の剰余をそれぞれ $ r_1( \xi ) $ と $ r_2( \xi ) $ とすると $ g_1( \xi ) g_2( \xi ) $ と $ r_1( \xi ) r_2( \xi ) $ とは同じ剰余をもつ」ということについて確認しておこう。

$ g_1( \xi ) $ と $ g_2( \xi ) $ の剰余をそれぞれ $ r_1( \xi ) $ と $ r_2( \xi ) $ とする。このときの商をそれぞれ $ q_1( \xi ) $ と $ q_2( \xi ) $ とすると、除法のアルゴリズムにより $ g_1( \xi ) $ と $ g_2( \xi ) $ は次のように書ける。
$$
g_1( \xi ) = q_1( \xi ) f( \xi ) + r_1( \xi ) , \qquad g_2( \xi ) = q_2( \xi ) f( \xi ) + r_2( \xi )
$$
$ g_1( \xi ) g_2( \xi ) $ を計算する。
$$
\begin{eqnarray}
g_1( \xi ) g_2( \xi ) &=& \{ q_1( \xi ) f( \xi ) + r_1( \xi ) \} \{ q_2( \xi ) f( \xi ) + r_2( \xi ) \} \\
&=& q_1( \xi ) f( \xi ) q_2( \xi ) f( \xi ) + q_1( \xi ) f( \xi ) r_2( \xi ) + q_2( \xi ) f( \xi ) r_1( \xi ) + r_1( \xi ) r_2( \xi ) \\
&=& f( \xi ) \{ q_1( \xi ) q_2( \xi ) f( \xi ) + q_1( \xi ) r_2( \xi ) + q_2( \xi ) r_1( \xi ) \} + r_1( \xi ) r_2( \xi ) \\
\end{eqnarray}
$$
右辺の $ f( \xi ) \{ q_1( \xi ) q_2( \xi ) f( \xi ) + q_1( \xi ) r_2( \xi ) + q_2( \xi ) r_1( \xi ) \} $ は $ f( \xi ) $ で割りきれる。$ r_1( \xi ) r_2( \xi ) $ を $ f( \xi ) $ で割ったときの剰余が $ g_1( \xi ) g_2( \xi ) $ の剰余となることがわかる。

続いて「$ g_1 ( \xi ) $, $ g_2 ( \xi ) $ , $ \cdots $, $ g_m( \xi ) $ の積 $ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) $ は通常の積 $ g_1 ( \xi ) g_2 ( \xi ) \cdots g_m( \xi ) $ の剰余に等しいこと」を数学的帰納法で証明する。

通常の積 $ g_1 ( \xi ) g_2 ( \xi ) \cdots g_m( \xi ) $ を $ f ( \xi ) $ で割った商を $ Q_m ( \xi ) $ 、剰余を $ R_m( \xi ) $ とすると、除法のアルゴリズムにより次のように書ける。$ g_1( \xi ) $ と $ g_2( \xi ) $ の剰余をそれぞれ $ r_1( \xi ) $ と $ r_2( \xi ) $ とすると $ g_1( \xi ) g_2( \xi ) $ と $ r_1( \xi ) r_2( \xi ) $ とは同じ剰余をもつことが示されているのでこのように書いても差し支えない。$ r_1( \xi ) r_2( \xi ) $ の剰余が $ R_2 ( \xi ) $ 、$ r_1( \xi ) r_2( \xi ) \cdots r_m ( \xi ) $ の剰余が $ R_m ( \xi ) $ であると考えてもいい。
$$
g_1 ( \xi ) g_2 ( \xi ) \cdots g_m( \xi ) = Q_m ( \xi ) f ( \xi ) + R_m( \xi )
$$
$ R_m( \xi ) $ の次数は、$ f ( \xi ) $ の次数より小さい。
いま証明したいことは、 $ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) = R_m( \xi ) $ である。

定義より、$ m = 2 $ のとき成り立つことは明らかである。

$ m = k $ のとき、$ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_k( \xi ) = R_k( \xi ) $ が成り立っていると仮定する。

$ m = k+1 $ のとき、$ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_k( \xi ) \times g_{k+1}( \xi ) $ は、帰納法の仮定より次のように書ける。
$$
g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_k( \xi ) \times g_{k+1}( \xi ) = R_k( \xi ) \times g_{k+1}( \xi )
$$
定義より、$ R_k( \xi ) \times g_{k+1}( \xi ) $ は、$ R_k( \xi ) g_{k+1}( \xi ) $ の剰余である。

除法のアルゴリズムより、
$$
g_1 ( \xi ) g_2 ( \xi ) \cdots g_k( \xi ) = Q_k ( \xi ) f ( \xi ) + R_k( \xi ) \\
g_1 ( \xi ) g_2 ( \xi ) \cdots g_k( \xi ) g_{k+1}( \xi ) = Q_{k+1} ( \xi ) f ( \xi ) + R_{k+1}( \xi )
$$
であるので、
$$
\{ Q_k ( \xi ) f ( \xi ) + R_k( \xi ) \} g_{k+1}( \xi ) = Q_{k+1} ( \xi ) f ( \xi ) + R_{k+1}( \xi ) \\
$$
がいえる。これを式変形すると、
$$
\begin{eqnarray}
\{ Q_n ( \xi ) f ( \xi ) + R_n( \xi ) \} g_{k+1}( \xi ) &=& Q_{k+1} ( \xi ) f ( \xi ) + R_{k+1}( \xi ) \\
Q_n ( \xi ) f ( \xi ) g_{k+1}( \xi ) + R_k( \xi ) g_{k+1}( \xi ) &=& Q_{k+1} ( \xi ) f ( \xi ) + R_{k+1}( \xi ) \\
R_k( \xi ) g_{k+1}( \xi ) &=& f ( \xi ) \{ Q_{k+1} ( \xi ) - Q_k ( \xi ) g_{k+1}( \xi ) \} + R_{k+1}( \xi )
\end{eqnarray}
$$
となり、$ R_k( \xi ) g_{k+1}( \xi ) $ の剰余は $ R_{k+1} ( \xi ) $ であることがわかる。つまり $ R_k( \xi ) \times g_{k+1}( \xi ) = R_{k+1} ( \xi ) $ であり、$ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_k( \xi ) \times g_{k+1}( \xi ) = R_{k+1} ( \xi ) $ が成り立つ。

以上より、数学的帰納法により、$ g_1 ( \xi ) $, $ g_2 ( \xi ) $ , $ \cdots $, $ g_m( \xi ) $ の積 $ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) $ は通常の積 $ g_1 ( \xi ) g_2 ( \xi ) \cdots g_m( \xi ) $ の剰余に等しいことがいえる。

2019/12/11

新しい乗法

エミール・アルティン『ガロア理論入門』第2章第3節の続きです。

$ K \subset E $ で、体 $ K $ 上の代数的な $ E $ の要素 $ \alpha $ の最小多項式 $ f(x) $ の性質を確認し、いまは次のような要素 $ \theta $ のつくる $ E $ の部分集合 $ E_0 $ が体であり、$ K ( \alpha ) $ であることを示そうとしています。
$$
\theta = g( \alpha ) = c_0 + c_1 \alpha + \cdots + c_{n-1} \alpha ^{n-1}
$$
アルティンは、$ E_0 $ が体であることを示すために、集合 $ E_0 $ の模写をはじめます。

　$ E_0 $ が体であることを示すために、拡大体 $ E $ と要素 $ \alpha $ を用いないで集合 $ E_0 $ を模写してみる。いま $ K $ 内の既約多項式
$$
f(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_0
$$
が与えられたとしよう。
$ \xi $ を1つの記号とする。次数が $ n $ より小さく $ \xi $ の多項式
$$
g( \xi ) = c_0 + c_1 \xi + \cdots + c_{n-1} \xi ^{n-1}
$$
全体の集合を $ E_1 $ とする。この集合は加群をなす。ここで $ E_1 $ の2つの要素 $ g( \xi ) $ と $ h( \xi ) $ に対して通常の積のほかに新しい乗法を定義し、それを $ g( \xi ) \times h( \xi ) $ と表わす。すなわち $ g( \xi ) \times h( \xi ) $ とは通常の積 $ g( \xi ) h( \xi ) $ の $ f(x) $ を法とした剰余 $ r( \xi ) $ のことと定義する。するとまず、$ g_1 ( \xi ) $, $ g_2 ( \xi ) $ , $ \cdots $, $ g_m( \xi ) $ の積 $ g_1 ( \xi ) \times g_2 ( \xi ) \times \cdots \times g_m( \xi ) $ は通常の積 $ g_1 ( \xi ) g_2 ( \xi ) \cdots g_m( \xi ) $ の剰余に等しいことがわかる。この性質は $ m = 2 $ のときは定義から明らかであり、任意の $ m $ に対しては次の性質と数学的帰納法とを用いて示される。その性質とは
“ $ g_1( \xi ) $ と $ g_2( \xi ) $ の剰余をそれぞれ $ r_1( \xi ) $ と $ r_2( \xi ) $ とすると $ g_1( \xi ) g_2( \xi ) $ と $ r_1( \xi ) r_2( \xi ) $ とは同じ剰余をもつ”
ということである。この証明の詳細は読者にまかせよう。

議論の方向性を簡単に例えると、 $ E_0 $ が体であることを示すために、$ E_0 $ の模型をつくったようなものです。その模型の名前が $ E_1 $ で、$ E_1 $ が体であることを示し、$ E_0 $ と $ E_1 $ は同じ型であることを示すことで、$ E_0 $ が体であることを示そうとしています。

体であるかどうかの確認は、体の定義に当てはまるかどうかです。体の定義は別に載せています（「体の定義」参照）のでここでは詳しくは書きませんが、体には加法と乗法が定義されています。 $ E_1 $ は加群（加法が定義された可換群）をなすため、加法についてはOK。乗法についてですが、通常の乗法（簡単にいえば掛け算）では閉じていませんので、新しい乗法を定義します。その新しい乗法を $ g( \xi ) \times h( \xi ) $ と表わし、$ g( \xi ) \times h( \xi ) $とは通常の積 $ g( \xi ) h( \xi ) $ の $ f(x) $ を法とした剰余 $ r( \xi ) $ のことと定義します。

このような言葉が適切ではないかもしれませんが、多項式での $ \bmod $ ですね。

さて、証明が読者にまかされています。取り組んでみましょう。

2019/12/10

拡大体の大きさ

エミール・アルティン『ガロア理論入門』第2章第3節の続き。

おそらく体論のなかでは基礎の部分となりますが、僕にとってはもう少し理解したいところの大きなひとつとなるところです。

これまで $ K $ 上代数的な要素 $ \alpha $ を根にもつ $ K $ 内の最小多項式 $ f(x) $ の性質を見てきました。先取りになってしまいますが、これから、この $ \alpha $ を $ K $ 添加した体 $ K ( \alpha ) $ の性質を探っていくことになります。

次に $ E $ の中で、次のような要素 $ \theta $ のつくる部分集合 $ E_0 $ をとりあげる。
$$
\theta = g( \alpha ) = c_0 + c_1 \alpha + \cdots + c_{n-1} \alpha ^{n-1}
$$
ここに $ g(x) $ は $ K $ 内の多項式で $ n $ よりも低次とする（ $ n $ は $ f(x) $ の次数である）。この集合 $ E_0 $ は加法、乗法で閉じている。乗法で閉じていることは $ g(x) $ と $ h(x) $ を次数が $ n $ より小さい2つの多項式としたとき
$$
g(x)h(x) = q(x)f(x) + r(x)
$$
とおけば、$ g( \alpha ) h( \alpha ) = r( \alpha ) $ となることからわかる。最後にまた $ c_0, c_1, \cdots, c_{n-1} $ は $ \theta $ から一意的に定まることがわかる。なぜなら、もし同一の $ \theta $ に対して2通りの表わし方があれば、差をとることによって $ \alpha $ の満たす $ n $ より低次数の方程式が存在することになってしまうからである。

最初は $ \theta $ や、その $ \theta $ がつくる部分集合 $ E_0 $ が何を意味しているのかわからず、しばらく悶々としていたのですが、具体例を入れることで少し理解することができました。

有理数体上の代数的な要素である $ \sqrt{2} $ を例にします。$ \sqrt{2} $ の有理数体での最小多項式は $ x^2 - 2 $ です。引用部分に当てはめると、$ \alpha = \sqrt{2}, \ f(x) = x^2 - 2 $ です。このとき、$ \theta = g( \sqrt{2} ) = c_0 + c_1 \sqrt{2} $ です。$ g(x) $ は $ K $ 内の多項式（ここでは、$ g(x) = c_0 + c_1 x $ ）ですので、$ c_0 , c_1 $ は有理数。馴染みのある記号（いや、馴染みはないけれど）におきかえると、$ \theta = p + q \sqrt{2} $ 、つまりこの例では、部分集合 $ E_0 $ は、
$$
E_0 = \{ p + q \sqrt{2} \mid p, q \in \mathbb{ Q } \}
$$
となります。

以前に、$ K \subset E $ のとき、$ E $ は $ K $ 上のベクトル空間とみることができることを学びました。『ガロア理論入門』とは別の本ですが、$ \mathbb{ Q } $ に $ \sqrt{2} $ を添加した体 $ \mathbb{ Q } ( \sqrt{2} ) $ も $ \mathbb{ Q } $ 上のベクトル空間と見なせることも知ってはいます。ここ例での $ \theta $ は、$ \mathbb{ Q } ( \sqrt{2} ) $ の任意の要素を表わし、 $ E_0 $ は、$ \mathbb{ Q } ( \sqrt{2} ) $ を表わしています。$ \theta = g( \alpha ) = c_0 + c_1 \alpha + \cdots + c_{n-1} \alpha ^{n-1} $ は、体 $ K $ に $ \alpha $ を添加したときの任意の要素を一般的に表わしていると考えられます。

さきに進みましょう。

さてここで、集合 $ E_0 $ の内部構造は、$ \alpha $ の特性によって定まるものではなく、既約多項式 $ f(x) $ によって定まるものであることを注意しよう。すなわち、この多項式を知れば、集合 $ E_0 $ における和と乗法を定めることができるわけである。この $ E_0 $ は実は体であることがこのあと証明され $ K( \alpha ) $ と書かれる。もし $ E_0 $ が体 $ K ( \alpha ) $ であることが示されたならば、$ K ( \alpha ) $ は線形独立な $ 1, \alpha, \alpha ^2 , \cdots, \alpha ^{n-1} $ で生成されることになるので
$$
( K ( \alpha ) / K ) = n
$$
であることが判明する。

「集合 $ E_0 $ の内部構造は、$ \alpha $ の特性によって定まるものではなく、既約多項式 $ f(x) $ によって定まる」ということも最初のうちはよくわかりませんでした。 $ \theta $ の値は $ \alpha $ の値によって決まるのではないか、と。しかしよくよく読んでいると、値ではなく「内部構造」という言葉が使われていますし、また $ \alpha = \sqrt{2} $ として具体例を挙げて確認したときに、$ f(x) $ が2次の多項式であったため、$ \theta $ が2項（ $ c_0 $ と $ c_1 \sqrt{2} $ ）の和の項となっていることに気がつきました。つまり、最小多項式が3次の多項式だったら $ \theta = c_0 + c_1 \alpha + c_2 \alpha ^2 $ となり、このような意味で、集合 $ E_0 $ の内部構造は最小多項式 $ f(x) $ によって定まるといえます。

これからこの集合 $ E_0 $ が体であることを示していきます。そして$ E_0 $ が体であれば、$ ( K ( \alpha ) / K ) = n $ となります。いわば、$ \alpha $ を添加した体はどれだけ大きく拡大するのかを示すことができるのです。

最小多項式の性質

エミール・アルティン『ガロア理論入門』第2章第3節の続き。

最小多項式について、3つの性質を挙げています。本では3つの性質についての一般的な証明がなされていますが、ここでは具体例を使ってその証明を見ていきたいと思います。

$ \alpha $ が $ K $ 上代数的のとき、$ \alpha $ を根にもつ $ K $ 内の $ 0 $ でない多項式の中で最低次数のものを選び、次にそれに適当な $ K $ の要素をかけて、その最高次の係数を $ 1 $ にしたものをつくり、これを $ f(x) $ で表わす。するとこの多項式 $ f(x) $ について、次の3つの性質がなりたつ。

$ g(x) $ を $ g( \alpha ) = 0 $ のような $ K $ 内の多項式とすると $ g(x) $ は $ f(x) $ で割りきれる。

$ f(x) $ は $ K $ 上既約である。

$ f(x) $ は上のつくり方のもとで一意的に定まる。

例として、 $ \sqrt{2} $ の有理数体上の最小多項式 $ x^2 -2 $ を見てみます。上にならい、$ f(x) = x^2 -2 $ とします。$ x^2 -2 $ は $ \sqrt{2} $ を根にもち、$ \sqrt{2} $ は有理数体上代数的です。 $ \sqrt{2} $ を根にもつ、有理数係数の中で最低次数の多項式で、最高次の係数が1ですので、$ x^2 -2 $ は $ \sqrt{2} $ の有理数体上の最小多項式となります。

$ g(x) $ を $ g( \sqrt{2} ) = 0 $ である有理数係数の多項式とします。$ g(x) $ は、$ f(x) $ よりも低次数の $ r(x) $ を用いて、$ g(x) = f(x) q(x) + r(x) $ と表すことができます。$ g(x) $ を $ f(x) $ で割った商を $ q(x) $ 、余りを $ r(x) $ として表わした等式です。

この等式の $ x $ に、$ \sqrt{2} $ を代入すると、$ g( \sqrt{2} ) = f( \sqrt{2} ) q( \sqrt{2} ) + r( \sqrt{2} ) $ となります。いま、$ f( \sqrt{2} ) = 0 $、$ g( \sqrt{2} ) = 0 $ ですので、$ r( \sqrt{2} ) = 0 $ となります。

$ r( \sqrt{2} ) = 0 $ ということは、$ r(x) $ は \sqrt{2} を根にもちます。しかし、$ r(x) $ は有理数係数の多項式で、その次数が$ f(x) $ よりも低次の多項式となりますので、零多項式でなければなりません。つまり、$ g(x) = f(x) q(x) + 0 = f(x) q(x) $ となり、$ g(x) $ は $ f(x) $ で割りきれることになり性質1がなりたちます。

また $ g(x) = f(x) q(x) $ ですので、$ f(x) $ は一意に定まります。$ g(x) $ を $ q(x) $ で割った商がいろいろな多項式になったら困ります。

さらに、もし $ f(x) = x^2 -2 $ が有理数体上で因数分解できたとすると、その因子の多項式のひとつは $ f(x) $ よりも低次で、$ x = \sqrt{2} $ で$ 0 $ になるものとなり、最小多項式のとり方に反します。したがって $ f(x) = x^2 -2 $ は有理数体上で既約です。

最小多項式の例として $ x^2 -2 $ で示しましたが、$ \alpha $ の $ K $ 上の最小多項式として上と同じやり方で、3つの性質を証明することが可能です。

最小多項式の性質
$ \alpha $ が $ K $ 上代数的のとき、$ \alpha $ を根にもつ $ K $ 内の $ 0 $ でない多項式の中で最低次数のものを選び、次にそれに適当な $ K $ の要素をかけて、その最高次の係数を $ 1 $ にしたものをつくり、これを $ f(x) $ で表わす。するとこの多項式 $ f(x) $ について、次の3つの性質がなりたつ。

$ g(x) $ を $ g( \alpha ) = 0 $ のような $ K $ 内の多項式とすると $ g(x) $ は $ f(x) $ で割りきれる。
$ f(x) $ は $ K $ 上既約である。
$ f(x) $ は上のつくり方のもとで一意的に定まる。

チルンハウス変換

結城浩『数学ガール／ガロア理論』のなかで、3次方程式の解の公式を求めていくところがある。その最初に一般的な3次方程式を簡単なかたちに変換する方法として、チルンハウス変換というものが載っていた。

1変数の3次方程式は一般的に次のように書ける。

$$
a y^3 + b y^2 + c y + d = 0 \qquad ( a \neq 0 )
$$

これに、$ y = x - \frac { b }{ 3a } $ を代入して整理すると、

$$
\begin{eqnarray}
a \left( x - \frac { b }{ 3a } \right) ^3 + b \left( x - \frac { b }{ 3a } \right) ^2 + c \left( x - \frac { b }{ 3a } \right) + d &=& 0 \\
x^3 - \frac { b^2 - 3ac } { 3a^2 } x + \frac { 2b^2 -9abc + 27a^2d } { 27a^3 } &=& 0
\end{eqnarray}
$$

$ p = - \frac { b^2 - 3ac } { 3a^2 }, \ q = \frac { 2b^2 -9abc + 27a^2d } { 27a^3 } $ とおくと、

$$
x^3 + p x + q = 0
$$

と表せる。こちらの3次方程式は変数の2次の項がない。

$ y = x - \frac { b }{ 3a } $ と $ p = - \frac { b^2 - 3ac } { 3a^2 }, \ q = \frac { 2b^2 -9abc + 27a^2d } { 27a^3 } $ から、$ x^3 + p x + q = 0 $ を $ a y^3 + b y^2 + c y + d = 0 $ に戻すことができるので、3次方程式を考える場合には、$ x^3 + p x + q = 0 $ を一般形として考えることが多い。

この変換を『数学ガール／ガロア理論』ではチルンハウス変換と呼んでいたが、別の本やWeb記事などでは「フェラーリの方法」とか「立法完成」とも呼ばれていた。

さて、このチルンハウス変換は3次方程式だけではなく、他の次数の方程式でも使えるのだろうか。

たとえば2次方程式で考えてみる。

3次方程式で $ y = x - \frac { b }{ 3a } $ としたならば、2次方程式では $ y = x - \frac { b }{ 2a } $ がよさそうである。2次方程式の一般形を

$$
a y^2 + b y + c = 0 \qquad ( a \neq 0 )
$$

として、$ y = x - \frac { b }{ 2a } $ を代入して整理する。

$$
\begin{eqnarray}
a \left( x - \frac { b }{ 2a } \right) ^2 + b \left( x - \frac { b }{ 2a } \right) + c &=& 0 \\
a \left( x^2 - \frac { b }{ a } x + \frac { b^2 }{ 4a^2 } \right) + b x - \frac { b^2 }{ 2a } x + c &=& 0 \\
a x^2 + \frac { -b^2 + 4ac }{ 4a } &=& 0 \\
x^2 + \frac { -b^2 + 4ac }{ 4a^2 } &=& 0
\end{eqnarray}
$$

1次の項が消えた。そして、馴染みのあるかたちが出てきた。ちょっと逸れるが、このまま $ x $ について解いてみる。

$$
\begin{eqnarray}
x^2 + \frac { -b^2 + 4ac }{ 4a^2 } &=& 0 \\
x^2 &=& \frac { b^2 - 4ac }{ 4a^2 } \\
x &=& \pm \sqrt{ \frac { b^2 - 4ac }{ 4a^2 } } \\
x &=& \frac { \pm \sqrt{ b^2 - 4ac }} { 2a } \\
\end{eqnarray}
$$

$ y = x - \frac { b }{ 2a } $ から

$$
\begin{eqnarray}
y &=& \frac { \pm \sqrt{ b^2 - 4ac }} { 2a } - \frac { b }{ 2a } \\
y &=& \frac { - b \pm \sqrt{ b^2 - 4ac }} { 2a } \\
\end{eqnarray}
$$

と、2次方程式 $ a y^2 + b y + c = 0 $ の解の公式が出てきた。

2次方程式の解の公式を導出する際、普通はチルンハウス変換のような変数変換は行なわない。「平方完成」という操作をする。（「2次方程式の解の導出」参照）。

とすると、3次方程式でもチルンハウス変換ではなく、2次方程式の平方完成に相当するような「立法完成」をやってみてはどうだろうか（計算は面倒くさそうだが）。

とりあえずやってみる。3次方程式を $ a x^3 + b x^2 + c x + d = 0 \ ( a \neq 0 ) $ として、両辺を $ a $ で割った $ x^3 + \frac {b}{a} x^2 + \frac {c}{a} x + \frac {d}{a} = 0 $ から計算してみる。

$$
\begin{eqnarray}
(左辺) &=& x^3 + \frac {b}{a} x^2 + \frac {c}{a} x + \frac {d}{a} \\\\
&=& \left( x + \frac{ b }{ 3a } \right) ^3 - \frac {b}{a} x^2 - \frac { b^2 }{ 3a^2 } x - \frac{ b^3 }{ 27a^3 } + \frac {b}{a} x^2 + \frac {c}{a} x + \frac {d}{a} \\\\
&=& \left( x + \frac{ b }{ 3a } \right) ^3 - \frac { b^2 }{ 3a^2 } x + \frac {c}{a} x - \frac{ b^3 }{ 27a^3 } + \frac {d}{a} \\\\
&=& \left( x + \frac{ b }{ 3a } \right) ^3 - \frac { b^2 -3ac }{ 3a^2 } x - \frac{ b^3 - 27a^2 d}{ 27a^3 }
\end{eqnarray}
$$

2次の項は消え、$ x^3 + p x + q = 0 $ という形式にはなる。が、解の公式の導出がやりやすくなるというようなことはなかった。

話を戻し、チルンハウス変換はどうやら最高次の次の項を消すような変換のことを指すようだ。4次のときにも $ y = x - \frac{b}{4a} $ で変換すると3次の項が消える。確認は面倒なのでしない。Wikipediaで四次方程式の項を見ると、フェラーリの方法の一部として同様の変数変換が行なわれていた。フェラーリは4次方程式の解の公式を導いた人の名前である。チルンハウスも人名。

僕のなかで曖昧だった用語を次のように整理する。
チルンハウス変換：ここでみたような最高次の次の項を消すような変数変換（あるいは式変形）
平方完成：2次の場合のチルンハウス変換、主に式変形
立法完成：3次の場合のチルンハウス変換、主に式変形
フェラーリの方法：フェラーリの4次方程式の解の公式の導出方法

代数的要素

エミール・アルティン『ガロア理論入門』第2章第3節「代数的要素」に入ります。

僕にとって、もう少ししっかりと押さえておきたいところです。

まずは「代数的」とはどのようなことか、の説明から入ります。

$ K $ を体とし、$ E $ を $ K $ の拡大体とする。$ \alpha $ を $ E $ の要素とするとき、$ K $ 内に係数をもつ多項式で $ \alpha $ を根にもつものが存在するかどうかを問題にする。もしそのような $ 0 $ でない多項式が存在するならば、$ \alpha $ は $ K $ 上で代数的であるという。

有理数体でみてみましょう。たとえば $ sqrt{2} $ は、有理数係数の多項式 $ x^2-2 $ の根となりますので、有理数体上で代数的です。$ sqrt{2} $ は無理数ですので、有理数体の要素ではありませんが、その拡大体（たとえば実数体）の要素です。有理数体上で代数的な要素を代数的数といいます。上記引用では有理数体に限らず一般的な体となりますので、代数的数の説明ではありませんが、代数的数が理解できれば、代数的であるということの理解はそう難しくないと思います。

ちなみに代数的数でない数を超越数といいます。言い換えると、有理数係数の多項式の根とならない数です。たとえば円周率の $ \pi $ は超越数です。

アルティンの『ガロア理論入門』は、代数的の説明のあと、その代数的要素をもつ多項式についての説明に移ります。

$ \alpha $ が $ K $ 上代数的のとき、$ \alpha $ を根にもつ $ K $ 内の $ 0 $ でない多項式の中で最低次数のものを選び、次にそれに適当な $ K $ の要素をかけて、その最高次の係数を $ 1 $ にしたものをつくり、これを $ f(x) $ で表わす。するとこの多項式 $ f(x) $ について、次の3つの性質がなりたつ。

$ g(x) $ を $ g( \alpha ) = 0 $ のような $ K $ 内の多項式とすると $ g(x) $ は $ f(x) $ で割りきれる。

$ f(x) $ は $ K $ 上既約である。

$ f(x) $ は上のつくり方のもとで一意的に定まる。

アルティンの本には載っていませんが、このような $ f(x) $ を最小多項式といいます。

たとえば先ほどの $ \sqrt{2} $ の有理数体上の最小多項式は $ x^2-2 $ です。 $ x^2-2 $ は、有理数係数の $ 0 $ でない多項式で、 $ \sqrt{2} $ を根にもつ多項式の中で最低次数であり、その最高次の係数は1となりますので条件にあてはまります。

$ \sqrt{2} $ を根にもつ多項式はたくさんあります。$ x^2-2 $ はもちろん、他にたとえば $ 2(x^2 -2) $ や $ ( x - 1) ( x^2 -2 ) $ なども $ \sqrt{2} $ を根にもつ多項式です。$ \sqrt{2} $ を根にもつ多項式の中で、最低次数（この例では2次）で、最高次の係数が1である多項式が最小多項式です。

1次の多項式で $ \sqrt{2} $ を根にもつ多項式に、$ x - \sqrt{2} $ がありますが、これは有理数係数の多項式ではありません。

この最小多項式の性質を3つ挙げています。そしてその証明もありますので、次回取り上げたいと思います。

代数的
$ K $ を体、$ E $ を $ K $ の拡大体とする。$ \alpha $ を $ E $ の要素とする。
$ K $ 内に係数をもつ多項式で、 $ \alpha $ を根にもつ $ 0 $ でない多項式が存在するとき、$ \alpha $ は $ K $ 上で代数的であるという。

最小多項式
$ \alpha $ が $ K $ 上代数的のとき、$ \alpha $ を根にもつ $ K $ 内の $ 0 $ でない多項式の中で、最低次数の多項式で、その最高次の係数が $ 1 $ である多項式を $ \alpha $ の $ K $ 上の最小多項式という。

2019/12/08

第2章第2節の節末問題（問題2-7、2-8解答）

エミール・アルティン『ガロア理論入門』第2章第2節の節末問題、問題2-7です。

問題2-7　$ p $ は素数、$ a_0, a_1, \cdots, a_n $ は整数で、

(1) $ \ p \nmid a_n \quad $
(2) $ \ p \mid a_i ( i = 0, 1, 2, \cdots, n-1 ) \quad $
(3) $ \ p^2 \nmid a_0 $
のとき $ f(x) = a_0 + a_1 x + \cdots + a_n x^n $ は有理数体 $ Q $ 上既約であることを示せ。

早速、本の解答をみてみましょう（早速かい！！）

解答
$ f(x) $ が $ Q $ 上可約ならば、整数を係数とする、次数が $ n-1 $ 以下の $ g(x), h(x) $ の積に分解される。

$ g(x) = b_0 + b_1 x + \cdots + b_{n-1} x^{n-1} $,
$ h(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1} $
とする。ここで係数の中には0のものがあってもよい。$ f(x) = g(x) h(x) $ の係数をくらべて $ a_0 = b_0 c_0 $ かつ $ p \mid a_0 , \ \ p^2 \nmid a_0 $ だから、たとえば $ p \mid b_0 , \ \ p \nmid c_0 $となる。これと $ a_1 = c_0 b_1 + c_1 b_0 $ かつ $ p \mid a_1 $ から $ p \mid c_0 b_1 $、したがって $ p \mid b_1 $ となる。

次に $ a_2 = c_0 b_2 + c_1 b_1 + c_2 b_0 $ と $ p \mid a_2 $ から $ p \mid b_2 $ となり、これをつづけて $ p \mid b_i \ (i= 0, 1, \cdots, n-1 ) $ となり、$ g(x) $ の係数はすべて $ p $ で割りきれてしまい、したがって $ p \mid a_n $ となって仮定に反する。

記号が多いですが、しっかりと読めば証明の内容は理解することができます（証明の方法を思いつくことはまだ難しいですが……）。ここでも背理法が使われていますね。

$ f(x) $ が $ Q $ 上可約であると仮定して、可約であれば、整数を係数とする、次数が $ n-1 $ 以下の $ g(x), h(x) $ の積に分解されることから論を進めています。 $ g(x), h(x) $ を式で表わし、$ f(x) = g(x) h(x) $ の係数をくらべ、矛盾を導いています。

証明自体は理解できましたが、「$ p $ は素数、$ a_0, a_1, \cdots, a_n $ は整数で、$ \ p \nmid a_n \quad $, $ \ p \mid a_i ( i = 0, 1, 2, \cdots, n-1 ) \quad $, $ \ p^2 \nmid a_0 $のとき $ f(x) = a_0 + a_1 x + \cdots + a_n x^n $ は有理数体 $ Q $ 上既約である」とは具体的にどういうことでしょうか。それを確認するために、問題2-8をみてみましょう。

問題2-8　前問を用いて、次の多項式は有理数体上既約であることを示せ。

(1) $ x^3 -3 $
(2) $ x^4 -8x^2 +2 $
(3) $ x^4 + x^3 + x^2 + x + 1 $

問題2-8は、問題2-7の内容を用いて、多項式が有理数体上既約であることを示す問題です。(1) から見ていきましょう。

$ x^3 -3 $ は、問題2-7での記号に当てはめると、$ a_0 = -3 , a_1 = 0 , a_2 = 0 , a_3 = 1 $ です。$ a_3 $ つまり1の約数ではなく、他の係数（ $ a_0 = -3 , a_1 = 0 , a_2 = 0 $ ) の約数で、かつ、$ p^2 $ が $ a_0 $ の約数ではないような素数 $ p $ として、$ p = 3 $ があります。$ \ 3 \nmid 1 $ で、$ 3 \mid -3(= a_0 ), 3 \mid 0 ( = a_1, a_2 ) $ そして $ \ 3^2 \nmid -3 $ なので、$ x^3 -3 $は有理数体上で既約であるといえます。

有理数体上で既約であるかどうかの判定に、問題2-7で示したことが使えるということですね。

続いて(2) を見ると、最高次の方から係数を列挙すると、1, 0, -8, 0, 2 となります。最高次の係数である1以外の数（ 0, -8, 2 ) に共通の約数で素数のものとして、2があります。最高次の係数である1を割りきることはできませんし、定数項の2の約数に $ 2^2 $ はありません。(2)では、$ p= 2 $ が条件にあてはまり、
$ x^4 -8x^2 +2 $ は有理数体上で既約であるといえます。

では、(3) $ x^4 + x^3 + x^2 + x + 1 $ はどうでしょうか。

係数はすべて1ですので、条件にあう素数は見つかりません。だから可約、というわけではないことに注意ですね。この多項式は円分多項式と呼ばれているもののひとつで、有理数体上で既約であることは有名です（円分多項式については『ガロア理論入門』でも後ででてくるので、詳しくはそちらで）。

(3) が既約であることについては、『ガロア理論入門』の解答では以下のようにしていました。

$ f(x) = x^4 + x^3 + x^2 + x + 1 = \frac { x^5 - 1 }{ x -1 } $ に対して $ g(y) = f(y+1) $ とおくと

$ g(y) = \frac { ( y + 1 )^5 - 1 }{ ( y+1 ) -1 } = y^4 + 5 y^3 + 10 y^2 + 10 y + 5 $
であるから、前問により $ g(y) $ は既約、ところがもし $ f(x) = h(x) k(x) $ ならば $ g(y) = h(y+1)k(y+1) $ となって $ g(y) $ が可約となってしまうので、$ f(x) $ も既約である。

$ g(y) = y^4 + 5 y^3 + 10 y^2 + 10 y + 5 $ については、$ p = 5 $ のときに問題2-7の条件にあてはまり、$ g(y) $ は既約となります。もし $ f(x) $ が可約であれば、$ g(y) $ が可約になってしまい矛盾する、だから $ f(x) $ は既約であるという背理法です。

なぜこのような一手間をかけなければならないのかは、おそらく円分多項式だからということなのでしょうが、僕は詳しくはわかっておりません。今後、円分多項式が出てきたときに再考してみたいと思います。

この記事には関係ないですが、ブロクのCSSに囲み枠を追加してみました。以下のように書くと、なんとなく様になった気がします。

有理数体上の既約多項式
$ p $ は素数、$ a_0, a_1, \cdots, a_n $ は整数で、

$ p \nmid a_n $
$ p \mid a_i \quad ( i = 0, 1, 2, \cdots, n-1 ) $　
$ p^2 \nmid a_0 $

のとき、 $ f(x) = a_0 + a_1 x + \cdots + a_n x^n $ は有理数体上既約である。

CSSの追加について、以下の記事を参考にしました。

サルワカ「【CSS】おしゃれなボックスデザイン（囲み枠）のサンプル30」

第2章第2節の節末問題（問題2-5解答）

エミール・アルティン『ガロア理論入門』第2章第2節の節末問題、問題2-5と問題2-6です。

問題2-5　次の各多項式は有理数体 $ Q $ 上既約であることを示せ。

(1) $ f(x) = x^5 -x -1 $
(2) $ x^4 +8 $

問題2-6　$ f(x) = x^5 - ax -1 $ が有理数体上可約となるように整数 $ a $ を定めよ。

問題2-5について、『ガロア理論入門』の解答は、(1) が有理数体 $ Q $ 上既約であることの証明を掲載し、「(2)も同様である」としていましたので、このブログでは(2)が有理数体 $ Q $ 上既約であることを示したいと思います。問題2-6の解答は、このブログでは省略します。

有理数体 $ Q $ 上既約であるというのは、言葉を変えると、有理数体 $ Q $ 上で因数分解できないということです。有理数体 $ Q $ 上可約であるとは、有理数体 $ Q $ 上で因数分解できるということです。

できないことを証明するには、背理法がよく使われます。解答も背理法を使って証明しています。

以下に記載している証明は、本に載っている証明の式や数を変えただけではなく、自分なりのやり方で自分の言葉におきなおして書いているので、冗長なところや言葉足らずなところがあるかもしれません。

問題
$ x^4 +8 $ は有理数体 $ Q $ 上既約であることを示せ。

解答
背理法を使う。$ f(x) = x^4 +8 $ として、$ f(x) $ は有理数体上可約であると仮定する。

$ f(x) $ が可約であるとすると、問題2-4から、整数を係数にもつ多項式に分解できる。
（問題2-4はこちらを参考）
$ f(x) $ は4次の多項式であるので、分解できるとすると、$ f(x) $ が1次因数をもつ（1次の多項式と3次の多項式に分解）か、2次因数をもつ（2つの2次の多項式）かの分解となる。

(i) $ f(x) $ が1次因数をもつ場合

$ f(x) = ( x - a ) ( x^3 + \cdots + b ) $ とする（ $ a, b $ はともに整数）。展開して係数を比較すると、$ -ab = 8 $ が得られる。これを満たす整数 $ a $ は、$ a = \pm 1, \pm 2, \pm 4, \pm 8 $ である。一方、$ a $ は、$ f(x) $ の根であるので $ f(a) = 0 $ となるはずだが、$ a = \pm 1, \pm 2, \pm 4, \pm 8 $ はどれも $ f(a) = 0 $ を満たさない（有理数範囲では $ x $ がどのような値でも $ x^4 +8 \gt 0 $ である）ので矛盾する。

(ii) $ f(x) $ が2次因数をもつ場合

$ f(x) = ( x^2 + ax + b ) ( x^2 + cx + d ) $ とする（ $ a,b, c, d $ はともに整数）。
$$
\begin{eqnarray}
f(x) &=& ( x^2 + ax + b ) ( x^2 + cx + d ) \\
&=& x^4 + ( a + c ) x^3 + ( b + d + ac ) x^2 + ( ad + bc ) x + bd
\end{eqnarray}
$$
より、係数を比較して、
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
a + c = 0 & \cdots \cdots ① \\
b + d + ac = 0 & \cdots \cdots ② \\
ad + bc = 0 & \cdots \cdots ③\\
bd = 8 & \cdots \cdots ④\\
\end{array}
\right.
\end{eqnarray}
$$
①より、$ c = -a $
③に代入して、
$$
\begin{eqnarray}
ad + b(-a) &=& 0 \\
a(d-b) &=& 0
\end{eqnarray}
$$
よって、$ a = 0 $ または $ b = d $。

$ a = 0 $ のとき、$ c = 0 $。②に代入して、$ b + d = 0 $ つまり $ b = -d $。④に代入して、$ b^2 = -8 $ を得るが、2乗して-8となる整数は存在しない。

$ b = d $ のときも、④に代入すると $ b^2 = 8 $ を得るが、2乗して8となる整数は存在しない。

ゆえに、(i) $ f(x) $ が1次因数をもつ場合も、(ii) $ f(x) $ が2次因数をもつ場合も矛盾が生じるので、$ x^4 +8 $ は有理数体 $ Q $ 上既約である。

第2章第2節の節末問題（問題2-4解答）

エミール・アルティン『ガロア理論入門』第2章第2節の節末問題。問題2-4。

問題2-4　$ f(x) \in Z[x] $ が、有理数を係数にもつ2つの多項式 $ g(x), h(x) $ の積に分解されるならば、実は $ Z[x] $ に属する2つの多項式の積に分解されることを示せ。またとくに $ f(x) $ の最高次の係数が1ならば、分解する多項式の最高次の係数も1としてよいことを示せ。

この問題のみピックアップすると、$ Z[x] $ って何？となりますが、$ Z[x] $ は、問題2-3に出てきたもので、整数を係数とする $ x $ の多項式の全体の集合です。

何度も言いたくなってしまいますが、当たり前のように感じていることほど、証明するとなると難しいですね……。解答を見ます。

解答
$ g(x), h(x) $ それぞれについて、その係数の分母の最小公倍数をくくり出し、次に係数の分子の最大公約数をくくり出して、

$ g(x) = \frac { a } { b } g_0(x) , \qquad h(x) = \frac { c }{ d } h_0(x) $
とする。ここに $ a, b, c, d \in Z $ で、$ g_0(x) , h_0(x) $ はともに $ Z[x] $ に属し、係数の最大公約数は1である。すると $ f(x) = g(x) h(x) $ から

$ bd f(x) = ac g_0(x) h_0(x) $
であり、問題2-3により $ p \mid g_0(x) h_0(x) $ となる素数 $ p $ は存在しないので、右辺の係数の最大公約数はちょうど $ ac $ である。左辺からはそれが $ bd $ の倍数であることを示すので $ bde = ac \ ( e \in Z ) $ すなわち $ f(x) = e g_0(x) h_0(x) $ となり $ e g_0(x) \in Z[x] , \ h_0(x) \in Z[x] $

次に $ f(x) $ の最高次の係数が1で $ f(x) = ( ax^n + \cdots )( bx^m + \cdots ) $ とすると、整数 $ a, b $ は $ ab = 1 $ をみたす。$ a = b = -1 $ のときは、全体の符号をかえればよいので $ a = b = 1 $ としてよい。

最初のところがよくわかりません。問題2-3で証明したことをつかうために、$ g(x), h(x) $ それぞれについて、その係数の分母の最小公倍数をくくり出し、次に係数の分子の最大公約数をくくり出して、$ g(x) = \frac { a } { b } g_0(x) , \ h(x) = \frac { c }{ d } h_0(x) $ としたということはわかりますが、「分母の最小公倍数をくくり出し、次に係数の分子の最大公約数をくくり出す」というのがどういったことを意味するのか。

何か具体例を作って確認してみます。

適当な有理数係数の多項式でみてみましょう。たとえば、$ \frac{1}{2}x^2 + \frac{4}{3}x + \frac{5}{6} $ を考えます。係数の分母の最小公倍数、ここでは2, 3, 6の最小公倍数は6。係数の分子の最大公約数、ここでは1, 4, 5の最大公約数は1。くくり出してみると、
$$
\frac{1}{2}x^2 + \frac{4}{3}x + \frac{5}{6} = \frac{1}{6} ( 3x^2 + 8x + 5 ) \\
$$
$ 3x^2 + 8x + 5 $ の部分が、解答文での $ g_0(x) $ や $ h_0(x) $ に相当します。$ 3x^2 + 8x + 5 $ は整数係数ですので、$ Z[x] $ の要素です。そして $ 3x^2 + 8x + 5 $ の係数の最大公約数は1です。

方程式を見やすくするために似たような操作をしますね。たとえば $ \frac{1}{2}x^2 + \frac{4}{3}x + \frac{5}{6} = 0 $ という方程式で、
$$
\begin{eqnarray}
\frac{1}{2}x^2 + \frac{4}{3}x + \frac{5}{6} &=& 0 \qquad & \\
3x^2 + 8x + 5 &=& 0 \qquad & 両辺に6を掛けた \\
\end{eqnarray}
$$
というようなことをしたりします（実際には最高次の係数を1にすることが多いですが）。$ \frac{1}{2}x^2 + \frac{4}{3}x + \frac{5}{6} $ は方程式ではなく多項式ですので、勝手に6倍したら違う式となってしまいます。多項式では、6倍したあと $ \frac{1}{6} $ 倍を掛けて元に戻したという感じですかね。この $ \frac{1}{6} $ 倍のところの操作を、一般化して述べたものが「係数の分母の最小公倍数をくくり出し、次に係数の分子の最大公約数をくくり出す」ということのようです。

証明の内容の方に戻ると、 $ f(x) = g(x) h(x) $ ですので、$ g(x), h(x) $ のところに $ g(x) = \frac { a } { b } g_0(x) , h(x) = \frac { c }{ d } h_0(x) $ を代入して、
$$
\begin{eqnarray}
f(x) &=& g(x) h(x) \\
f(x) &=& \left( \frac { a } { b } g_0(x) \right) \left( \frac { c }{ d } h_0(x) \right) \\
f(x) &=& \frac { ac } { bd } g_0(x) h_0(x) \\
bdf(x) &=& ac g_0(x) h_0(x) \\
\end{eqnarray}
$$
です。

いま $ g_0(x) $ の係数の最大公約数は1、$ h_0(x) $ の係数の最大公約数も同じく1ですので、$ g_0(x) h_0(x) $ の係数の最大公約数も1。したがって、右辺 $ ac g_0(x) h_0(x) $ の係数の最大公約数は $ ac $ です。左辺からはそれが $ bd $ の倍数であることを示すので、$ bde = ac $ とおいています（ $ e \in Z $ ）。$ bd $ の $ e $ 倍が $ ac $ ということです。

ちなみに問題2-3で証明したことは、

$ p $ を素数とし $ g(x), h(x) \in Z[x] $ とするとき $ p \mid g(x)h(x) $ ならば $ p \mid g(x) $ または $ p \mid h(x) $

です。

$ bde = ac $ を、$ bdf(x) = ac g_0(x) h_0(x) $ に代入して整理すると、$ f(x) = e g_0(x) h_0(x) $ となり、$ f(x) \in Z[x] $ が、有理数を係数にもつ2つの多項式 $ g(x), h(x) $ の積に分解されるならば、$ Z[x] $ に属する2つの多項式の積に分解されることが示されました。

登録: 投稿 (Atom)

ページ

2019/12/25

2019/12/24

2019/12/22

2019/12/21

2019/12/20

2019/12/19

2019/12/18

2019/12/17

2019/12/15

2019/12/14

2019/12/13

2019/12/12

2019/12/11

2019/12/10

2019/12/08

ブログ アーカイブ

ブログアーカイブ