スリー・ギャップ定理と黄金比
円の上に点をいくつも一定の向きに打ってゆくとする。点は直前に打った点と必ず一定の間隔で離れている。すると、円は点によっていくつもの円弧に分割される。ここではそれを円分割と呼ぶことにする。
円分割において現れる円弧の長さにはどのような法則があるだろうか。そして、最も偏りの少ない点の配置になるのは点を打つ間隔がどんな長さのときだろうか。前者に関してはユークリッドの互除法が、後者に関しては黄金比が、密接に関係してくる。
定義１（点間隔）
点を打ってゆく間隔を点間隔と呼ぶ。点間隔の長さは円周上の距離で測る。点間隔は円周の長さを超えず、ゼロではない。 □
定義２（始点・終点）
最初の点を始点、最後の点を終点という。点は打った順に番号が付けられている。始点の番号はゼロである。 □
定義３（正の向き・負の向き）
時計回りか反時計回りのどちらかを正の向きとし、その逆回りを負の向きとする。正の向きに点を打ってゆく。 □
定義４（端点）
円弧の両端の点を端点という。 □
定義５（分割）
円弧が自身の端点以外の点によって二つに分けられることを円弧の分割という。 □
定義６（ギャップ）
一度も分割されていない円弧をギャップという。 □
定義７（正余白・負余白）
始点を端点に持つ二つのギャップのうち、正の向き側のものを正余白、負の向き側のものを負余白と呼ぶ。 □
定義８（合余白）
終点を端点に持つ二つのギャップからなる円弧を合余白と呼ぶ。合余白はギャップではない。 □
定義９（親・子）
始点を端点に持たない任意の円弧に対して、二つの端点の番号が共に１だけ少ない円弧が二つあることになるが、正の向きに点間隔だけ回転移動して重なる方の円弧を、もとの円弧の親、あるいは親円弧という。親の逆を子という。 □
定理１
終点以外の点は、ギャップの親を分割しえない。
［証明］
もし終点以外の点が親円弧を分割しているなら、その次の点が存在し、回転移動の関係により子円弧を分割しているはずである。ゆえに、子円弧がギャップである限り、親円弧は終点以外の点によって分割されない。 □
定理１の系
ギャップの親は、ギャップもしくは合余白である。 □
定義１０（先祖・子孫）
親円弧の親円弧といくつもたどったものを先祖という。逆の関係のものを子孫という。 □
定理２（スリー・ギャップ定理）
いくつの点を打とうとも、同時に存在するギャップの長さは高々三つしかない。正余白の長さ、負余白の長さ、合余白の長さ、この三つである。
［証明］
任意のギャップをａとする。
ギャップａの先祖を、それがギャップであり続ける限りにおいて、たどれなくなるまでたどる。定理１の系により、合余白にたどり着くか、あるいは、二つの端点どちらかの番号がゼロになって、それ以上たどれなくなる。
前者の場合、子孫のギャップａは合余白と長さが等しい。なぜなら親円弧の定義より、ここでのたどり方において円弧の長さは変わらないからである。
後者の場合、正余白または負余白にたどり着いたのである。子孫のギャップａはそれらのどちらかと長さが等しいということである。
ところで、ギャップａは任意であった。したがって、定理の主張が成り立つ。 □
定理３
終点は、合余白を正余白の長さと負余白の長さに分割し、かつ、正の向きに見てこの順で内分する。
［証明］
合余白においては、終点を二つの端点が挟んでいる。そこで、正の向きにたどって、最初にある方をＡ点、最後にある方をＢ点と名付ける。ここで当然、Ａ点とＢ点の番号は終点のそれより若い。
よって、Ａ点と終点の番号から数が１ずつ引かれるなら、Ａ点が先にゼロになる。ゆえに、Ａ点と終点を二つの端点とするギャップは、その先祖をたどったとき、正余白に行き着かねばならない。番号のより大きい端点が残りの端点に対して常に正の向き側にあるからである。
同様の論法によって、終点とＢ点を二つの端点とするギャップは負余白を先祖としなければならない。
ただし、合余白に行き着かなければの話だが、実際にそれはありえない。部分と全体の関係なので明らかに長さが異なるからである。 □
定理４
円分割における点は、一つ増えるたびにギャップを一つ分割するか、他の点に重なるかのどちらかだが、このとき次のことが言える。初めの分割を除いて、分割の片方の長さは常に既存の長さである。
［証明］
分割はすべて終点が引き起こし、また、定理３より、分割は正余白と負余白の長さである。そして、正余白と負余白の少なくとも一方は新たに誕生したものではない。なぜなら、終点は一つしかないので、正余白と負余白を同時に分割することはできないからである。
これは、最初の分割の場合、全体を正余白と負余白に分割することになるので、例外となる。 □
定理５
ギャップに長さの違いがあるとき、最も長いギャップがまず分割される。
［証明］
三つの長さがあるときは、合余白と等しい長さのギャップが存在している。定理２の証明から分かるように、その先祖は合余白で、合余白は現在の終点によって分割されている。ゆえに、次に分割されるのは合余白の子供のギャップであり、それは合余白と長さが等しい。
二つの長さのみがあるときは、次の点の位置に関して三つの場合に分けられる。既にある点の上に重なるか、短いギャップを分割するか、長いギャップを分割するか、である。
第一の、新たな点が既存の点に重なる場合は、以下のようにして起こりえないことが示される。
点間隔がαで円周が１のとき、番号ｉよりも後の番号ｊの点が番号ｉの点に重なったとする。ｊαの小数部はｉαの小数部に等しい。ゆえに、ｊα－ｉαはｊαの整数部からｉαの整数部を差し引いたものに等しい。つまり、αはｊ－ｉ分の１の整数倍となる。したがって、すべての点は、始点からｊ－ｉ分の１ごとに刻んだｊ－ｉ個の目盛り上に必ず位置することになる。
さて、まだ一度も点が重なったことがないのであれば、終点の番号をＮとして、円はＮ＋１個のギャップに区分されている。ここで、次の番号Ｎ＋１の点が番号ｋの点に重なったとしよう。αはＮ＋１－ｋ分の１の整数倍になる。すなわち、すべてのギャップを構成する、言うなれば目盛り間隔は、ｋが最小でゼロであるから最大でもＮ＋１個しかない。ところが、ここで考えているのはギャップの長さが二種類の場合である。点が重なったのだから長さの種類は変化しない。そして、すでにＮ＋１個のギャップがある。どんなに少なく見積もっても、Ｎ＋２個の目盛り間隔が必要になる。これは不可能である。
よって、二つの長さのみ存在するときに、点が重なるということは起きない。
第二の、短いギャップが分割される場合は、以下のようにして矛盾する。大きい長さａと小さい長さｂがあって、ｂがさらに長さｃとｄに分割されたとしよう。定理３より、ｃとｄは正余白の長さと負余白の長さである。もし長さｂが残っているのなら、正余白、負余白、合余白の長さのどれでもない長さａがあることになって、定理２に反する。したがって、ａが合余白の長さとなるしかない。しかし、ａはｃ＋ｄよりも大きいから、定理３に反する。
ゆえに、第三の、長いギャップが分割される場合に必然的になる。 □
定理６
円分割の生みだす長さの系列は、正余白と負余白の長さの変化に着目すれば、長さに適用されたユークリッドの互除法のそれと全く同じであり、円分割で同時に存在可能な三つの長さは、互除法の連続する二段階におけるそれぞれの長さの集合の、その和集合になっている。ただしここでいう互除法は、ユークリッドが述べたオリジナルの形の、引き算を繰り返す形式のものである。
［証明］
ここでは、長さａ，ｂ，ｃ等の集合を考える。また、長さａのギャップｎ個の集合をここだけの表記法でｎａと表す。
まず、ａがｂより大きいとして、円分割がａとｂの集合をａ－ｂとｂの集合に変換することを示す。長さの集合がａとｂのみからなる、つまり、長さがａとｂのみ存在している円分割の状況とは、長さａのギャップがｍ個、長さｂのギャップがｎ個あるとして、集合ｍａと集合ｎｂの和集合で表される。以下のように変換されてゆく。 ｍａとｎｂの和集合、 （ｍ－１）ａと１（ａ－ｂ）と（ｎ＋１）ｂの和集合、 （ｍ－２）ａと２（ａ－ｂ）と（ｎ＋２）ｂの和集合、 （ｍ－３）ａと３（ａ－ｂ）と（ｎ＋３）ｂの和集合、 以下同様で、そして、 １ａと（ｍ－１）（ａ－ｂ）と（ｎ＋ｍ－１）ｂの和集合、 ｍ（ａ－ｂ）と（ｎ＋ｍ）ｂの和集合。 定理５により、最も大きい長さａのギャップがある限り、そのうちの一つが分割の対象に選ばれる。定理４により、分割の片方の長さはｂかａ－ｂだが、どちらを選ぼうとも結果は同じである。それゆえこのようになる。ここで、三つの長さａ，ａ－ｂ，ｂが現れているが、これらのなす集合は、ａとｂの集合と、ａ－ｂとｂの集合との、和集合になっている。
次に、ａをｂで割った商がｑで余りｒがゼロでないとして、円分割がａとｂの集合をｒとｂの集合に変換することを示す。以下のように変換されてゆく。 ａとｂの集合、 ａ－ｂとｂの集合、 ａ－２ｂとｂの集合、 ａ－３ｂとｂの集合、 以下同様で、そして、 ａ－ｑｂとｂの集合。 この最後のものはｒとｂの集合にほかならない。
ｒはｂより小さいから、定理５により、ｒとｂの集合の場合においてはｂが割られる長さである。割られる長さと割る長さの組として考えると、ａとｂの組をｂとｒの組に変換していることになる。
余りrがゼロになるときは、０とｂの集合までは到り着かずに、直前の段階で長さｂのみの集合が得られる。
そして、円分割において長さが一つしかなくなった場合、円は等分されたということである。これがｎ等分なら、円周を１としたときの点間隔は、分母がｎの有理数で表されることになる。よって、打つ点はすべて既存の点に重なるようになり、もはや新しい長さは生まれない。つまり、長さの観点からは停止と見なせる。
ゆえに、円分割はまさにユークリッドの互除法である。 □
定義１１（悪分割）
円分割の分割においては一つのギャップが二つのギャップに分割される。二分されてできるギャップの一方が他方の二倍よりも大きくなる分割を、悪分割という。 □
補題１
長さに適用されたユークリッドの互除法においては、初めの二つの長さの比が異なれば、導き出される商の系列も異なる。
［証明］
商の系列が一致すれば初めの二つの長さの比も等しいということを示せばよい。それを商の系列の長さに関する数学的帰納法で示す。
長さが１のとき、初めの二つの長さをａ，ｂ並びにｃ，ｄとして、ａ＝ｂｑ，ｃ＝ｄｑと表すことができる。ゆえに、ａ：ｂ＝ｃ：ｄ．
長さがｎのとき主張が成り立つと仮定する。長さがｎ＋１の場合の第一段階は、ａ＝ｂｑ＋ｒ，ｃ＝ｄｑ＋ｓと表すことができる。そして、それぞれの続きにあたるｂとｒに対する互除法とｄとｓに対する互除法とで商の系列が一致している。するとこれらは長さｎの場合だから、仮定により、ｂ：ｒ＝ｄ：ｓ．ゆえに、ｂｑ：ｒ＝ｄｑ：ｓ．ゆえに、（ｂｑ＋ｒ）：ｂｑ＝（ｄｑ＋ｓ）：ｄｑ．ゆえに、（ｂｑ＋ｒ）：ｂ＝（ｄｑ＋ｓ）：ｄ．ゆえに、ａ：ｂ＝ｃ：ｄ．よって、長さがｎ＋１のときも主張は成り立つ。 □
定理７
円分割において点が決して重ならず、かつ、悪分割が起こりえないのは、φ＝（１＋√５）／２，円周を１として、点間隔がφ－１あるいは２－φの場合のみである。
［証明］
定理６より、円分割における長さの系列を、引き算を繰り返す形式の互除法におけるそれと見なすことができる。すると明らかに、悪分割は、減算方式の互除法に特有な「引けるだけ引く」ことが一度の引き算で終わらない場合を、ただし余りがないときのみは二度の引き算でも終わらない場合を、意味している。しかし後者の場合、互除法は停止することになる。すると、定理６の証明で述べたように、打つ点がすべて重なりだす。ゆえに、この場合は除外してよい。したがって定理の条件の下で、悪分割のない円分割を、減算方式でなく除算方式の互除法で考えるなら、互除法のすべての商が１になる場合を意味していることになる。
円周を１として、点間隔αの円分割における最初の分割は、αと１－αへの二分割である。よって、円分割に対応するのは、αと１－αから始まる互除法である。
さて、先ほども触れたようにこの互除法は止まってはならない。
ゆえに、互除法で無限に商１のみが続く場合を考えればよい。ところで、黄金比をなす二つの長さに互除法を適用するとその商の系列で無限に１のみが続くことは、簡単に示すことができる。反対に、そのようになる二つの長さは黄金比をなすもの以外にないことが、補題１より分かる。したがって、黄金比の定義「小なる部分と大なる部分の比が大なる部分と全体の比に等しい」より、αが１－αより大きい場合、（１－α）：α＝α：１とおける。αが１－αより小さい場合は、α：（１－α）＝（１－α）：１．これらを個別に解いて定理の二数を得る。 □
応用
最後の定理７の応用として、φ－１または２－φをハッシュ表のためのハッシュ関数の定数として使う方法があり、フィボナッチ・ハッシュ(Fibonacci hashing)として知られている。ハッシュ表とはコンピュータ・プログラムにおけるデータ構造の一つで、理想的な状況においては、要素数に依存しない定数時間での高速な検索を可能にする。ハッシュ表は通例、配列として実装される。ハッシュ表を使うには、キーから配列の番号を計算するハッシュ関数が必要になる。ハッシュ関数の値をハッシュ値といい、異なるキーに対して同じハッシュ値になることを衝突という。ハッシュ関数は衝突が起きにくいほど望ましい。
フィボナッチ・ハッシュは以下のようなものである。前提として、二進数を基礎にしたコンピュータを使うとし、そのワード長はｗであるとする。さらに、ここでは最も簡単な場合として、キーｋは負でない整数値で、かつ、そのコンピュータが直接扱える範囲の値であるとする。
まず、黄金数（１＋√５）／２をφとして、定数ａを ａ＝（（φ－１）×２ｗ）の整数部 あるいは ａ＝（（２－φ）×２ｗ）の整数部 と定義する。ただし、ａが奇数になるようにする。φ－１と２－φは二進数表示の小数点以下の各桁で０と１が逆になっているので、これらの式のどちらかから必ず奇数のａが得られる。
そして、ハッシュ関数ｈを ｈ（ｋ）＝（（ａｋ／２ｗ）の小数部×２ｄ）の整数部 と定義する。始点から正の向きにある点まで測った円周上の距離をその点の位置というとして、「（ａｋ／２ｗ）の小数部」が、円周１の円の円分割における番号ｋの点の位置に相当する。それを２ｄ倍して小数を切り捨てて、０から２ｄ－１までの整数に変換する。ここで、２ｄはハッシュ表のサイズであり、その限りにおいてｄは任意である。つまり、ハッシュ表のサイズは２の累乗でしか変えられない。その見返りとして、関数ｈの計算に出てくる割り算はシフト演算で代用できることになる。
すなわち、実際は ｈ（ｋ）＝ａ×ｋをｗ－ｄビットだけ右にシフト と計算する。オーバーフローを上手く利用していることに注意（言ってみれば、こちらの式は数学的ではない）。
実は、定数ａが奇数でありさえすれば、ここで考えている場合において可能な２ｗ個のキーすべてをハッシュするとして、その衝突の総数はｄに応じて常に同じであり、かつ、可能な限り少ない――ｄ＝ｗのとき２ｗ個のキーが決して衝突せずに２ｄ個の位置に再配置されることは、奇数ａと２ｗ－ａの最大公約数が１であることと定理６および定理５から分かり、かつ、ゼロから二つずつに区切った位置は、ｄが１減ると一つずつの位置にまとめられ、すなわち、それぞれの二つの位置に入っていたキーは衝突することになる――。
しかし、たとえばａ＝１とすると、連続するキーのハッシュ値は連続するか、さもなければ衝突することになる。フィボナッチ・ハッシュの特徴は、連続したキーのハッシュ値がよく分散することであり、このことは定理７から明らかである。これによって、キーが等差数列をなしているとき、分散性――ここでいう分散性は、最も近接している箇所でどれだけ離れているか、の意味であり、つまり、分散性が高ければｄを小さくしても衝突が起きにくい――が極端に悪くならないことが保証される。具体的には、公差ｐ，初項ｑの等差数列をなすｎ個のキーは、ゼロから連続して並ぶｐ（ｎ－１）＋ｑ＋１個のキーがハッシュされて分散する程度の分散性を最低限、保証される。これは、後者の数列は前者の数列を内に含むのだから、自明の理である。
要するに、ゼロから連続する２ｗ個のキーすべてをハッシュすると、ａが（φ－１）×２ｗか（２－φ）×２ｗであることと、それ以外の奇数であることとで衝突数に違いは表れないのだが、その中からキーを部分的に選んで、なおかつそれらが等差数列をなすようにすると、違いが出てくる。もちろん、前者の方が平均的に性能がよいことが期待できる。そして、人間の作り出したシステムでは、キーが部分的に等差数列をなして分布していることが非常に多いのである。