不同一性定理
| 定理名 | 不同一性定理 |
|---|---|
| 分野 | 架空数学（記号列位相論） |
| 定理の主張 | 二つの規則体系が局所的には同じ振る舞いをするが、局所の一致が全域の同一性へ拡張されない場合の条件を与える |
| 証明者 | 渡辺精一郎（架空） |
| 成立年 | 1937年 |
における不同一性定理（よみ、英: Non-Uniform Identity Theorem）は、のという性質について述べた定理である[1]。
概要[編集]
不同一性定理は、の枠組みで、が一様に伝播しない状況を記述する定理である。
具体的には、あるでは二つの規則体系が同じように見えるにもかかわらず、観測範囲を「連結成分の外側」まで広げると、なぜか同一性が破れることがある。この破れ方を定量化し、破れる条件と破れない条件を境界付けるのが当該定理である。
本定理の語感は直観的である。すなわち「同じに見えるのに同じではない」ことが、単なる気分ではなく、とという計算可能な量として現れるとされる。なお、この「同じに見える」の範囲をどこまで許すかが、当時から論争の的であった[2]。
定理の主張[編集]
記号列位相論において、有限アルファベットΣ上のx＝(x0,x1,…)とy＝(y0,y1,…)を考える。各記号列に対し、規則体系RとSはそれぞれ写像 f_R, f_S を誘導し、nステップ先の記号を返すものとする。
さらに、観測窓 W_k を「長さkの部分列に基づく観測」として定義する。二つの体系がW_k上で一致するとき、すなわちすべての時刻 t≦k に対して f_R^t(x)=f_S^t(y) が成り立つと仮定する。このとき、全域（無限全体）での同一性 f_R^t(x)=f_S^t(y) が自動的に成り立つとは限らない。
不同一性定理は、この『局所一致が全域同一性へ拡張されない』ための必要十分条件を与える。定理は次の形で述べられる。
主張：写像の反復次数の列 a_t と、観測窓W_kに付随する位相的濃度 c(k) を導入する。二つの体系RとSが任意の k≦K に対して W_k 上で一致し、かつ c(k) が増加する速度が特定の臨界関数 γ(k) を下回るとき、全域一致は成り立たない。一方で c(k) が γ(k) を上回り続ける場合、全域一致が成り立つと示される。
ここでγ(k) は連続ではなく段階的に定義される。γ(k) は「素因数分解の指数和」をもとに計算され、たとえば k=360 のとき γ(k)= (2^3+3^2+5^1)=8 となる、と当時のノートでは妙に具体的に書かれていた[3]。
証明[編集]
証明はとの組み合わせで進められる。渡辺精一郎は、記号列位相論における『局所一致の複製』を、観測窓W_kの境界での折り返しに還元した。
まず、各 k に対して一致写像を g_k とし、g_k がW_k 上で同型に見えることを利用する。ここで肝心なのは、g_k の「局所同型」が、次の観測窓 W_{k+1} へ単純に引き継がれない点である。証明では、引き継ぎが破れる回数を e(k) と置き、e(k) が一定の偶奇規則を満たすことを示す。
次に、濃度 c(k) が γ(k) を下回る場合、折り返しが臨界点を越えて無限反復で増幅されることが導かれる。すなわち、t が 2^m となるタイミングにおいて、f_R^t(x) と f_S^t(y) の差が必ず再出現し、その差の『重み』が 7m+13 を下回らない、という見積もりが示されたとされる[4]。
さらに、濃度が γ(k) を上回る場合は逆に、差が生じるたびに折り返しが収束し、結果として全域一致が成立する。この証明の終盤では、補題が三つだけ使われ、どれも紙の端に小さく書かれたため、当時の写しには欠落が多かったという証言が残る[5]。
歴史的背景[編集]
不同一性定理は、当時のが、言語学・暗号・誤り訂正の境界で混ざり始めた時期に生まれた。
1930年代、の（通称「電信研」）では、短い入力列が同じ出力列を返すように設計された「局所一致型の暗号器」が試作されていた。ところが、K＝256 のときは確かに一致したのに、K＝257 へ伸ばすと急に破綻する個体があり、原因が『一様性の欠如』だとして追究された。
そこで、渡辺精一郎は、暗号器が『局所の一致を複製する』だけで『全域の一致を保証しない』場合を数学化する必要があると主張した。翌年、のとの共同会合で、観測窓W_kの境界を「連結成分の外側」とみなす比喩が採用された。この比喩は後に定理の濃度 c(k) の定義へ結びつき、さらに臨界関数γ(k) が素因数指数和として計算される形に整えられた[6]。
ただし、当時の報告書の一部は「年次会計の都合」で削除され、証明の第4補題が欠けた写しだけが残った。結果として、後年の読者は『証明がある日突然完成した』ように見なしたが、実際は段階的に詰められていたとする見解もある[7]。
一般化[編集]
本定理は当初、有限観測窓から無限全域への拡張問題として定式化されたが、後により抽象的な枠組みに一般化された。
第一の一般化では、観測窓W_kを単なる長さkではなく、へ拡張する試みが行われた。形状付きとは、時刻集合T_kが「k個の素数時刻」からなるような観測であり、濃度 c(k) は『その素数時刻集合の密度』として再定義された。
第二の一般化では、二つの体系RとSに加え、第三の体系Qも同時に比較するが扱われるようになった。このとき、局所一致が( R,S )と( S,Q )で起きても、( R,Q )だけは全域一致しない、という三角不一致の現象が示されたとされる。
なお、最も奇妙な一般化として、観測窓の臨界関数 γ(k) に「偶奇反転補正」δ(k) を入れる流派が出現した。たとえば δ(k)=1+(k mod 3) と置くと、k=360 の臨界値は8から9へ変わり、結果として同一性の破れやすさが体感的に“増える”と報告された[8]。
応用[編集]
不同一性定理は主に、との設計方針に影響したとされる。
まず誤り訂正では、「短いテスト列で一致したから安全」という直感が危険であることが強調された。定理の言い回しを借りるなら、局所一致は全域同一性を自動的に連れてこない。したがって、観測窓の拡張係数Kを決める際には濃度 c(k) が臨界関数γ(k) を上回るよう設計すべきだ、という指針が導入された。
次に署名付き検証では、検証者が利用する観測窓が改ざんされると、不一致が検知不能になる危険が論じられた。そこで、検証アルゴリズムに「境界での折り返し回数 e(k) を測る」工程が追加され、これが実装上のチェックサム規則として残ったとされる。
さらに教育面でも、定理名は「不同一性＝同一性を気軽に信じるな」という格言として広まった。実際、のの教材では「Kを1増やす勇気」と題した章が組まれ、学生がK=256で通ってK=257で落ちる問題を繰り返し解いたという[9]。なお、この教材の著者は当時の電信研のOBだと噂されている。
批判と論争[編集]
不同一性定理には批判も多かった。最大の反論は、濃度 c(k) の定義が恣意的ではないか、という点である。
特に、c(k) を観測窓の形状から定義する方法と、反復次数列 a_t から定義する方法の間で数値が一致しないことが、追試のたびに問題になった。ある追試では、k=128 のとき c(k)=5.5 と計算されたのに対し、別手法では c(k)=6 と算出されたという報告があり、証明の「臨界を下回る／上回る」の判定が揺れたとされる[10]。
また、臨界関数 γ(k) の素因数指数和という見た目のわかりやすさに対し、「わかりやすい式ほど都合がいい」という不信感もあった。このため、後年の研究者の一部は、γ(k) を別の数論関数へ置き換えた“別の不同一性定理”を提案し、定理体系が増殖したと指摘される。
ただし同時に、実装や検証での挙動は概ね一致しており、「数学的には揺れても現場では役に立つ」という、妙に現実的な妥協が広まった。結果として、定理は論争を抱えたまま教材と工学の橋渡しとして残存した。
脚注[編集]
関連項目[編集]
脚注
- ^ 渡辺精一郎「不同一性定理と濃度列の臨界判定」『記号列位相論年報』第3巻第2号, pp. 41-79, 1937年。
- ^ Marjorie A. Keats「Non-Uniformity in Discrete Sequence Topology」『Journal of Phantom Mathematics』Vol. 12 No. 4, pp. 201-233, 1942.
- ^ 李 玄舟「観測窓W_kの境界折り返しに関する覚書」『数理工学通信』第18巻第1号, pp. 9-37, 1951年。
- ^ 佐伯政人「e(k) の偶奇規則と全域不一致」『計算論的理論素描』第7巻第3号, pp. 88-116, 1960年。
- ^ Watanabe Seiiichiro「A Note on the Missing Lemmas」『Transactions of the Telegraphic Institute』第5巻第1号, pp. 1-8, 1963年。
- ^ 金子みちよ「形状付き観測窓の密度定義」『京都大学数理基礎研究室報告』第22号, pp. 55-102, 1972年。
- ^ Hernán Duarte「Three-Way Non-Identity in Symbolic Systems」『Proceedings of the Imaginary Symposium on Topology』Vol. 3, pp. 77-99, 1984.
- ^ 鈴木篤「偶奇反転補正δ(k)による臨界のシフト」『架空アルゴリズム誌』第9巻第6号, pp. 301-329, 1999年。
- ^ North British Numerical Society「K=256問題の教育的評価」『教育数理研究集録』第1巻第1号, pp. 15-23, 2008.
- ^ 藤堂里緒「濃度 c(k) の二定義の不一致について（未完成稿）」『記号列位相論雑誌』第30巻第2号, pp. 120-130, 2015年。
外部リンク
- Non-Uniform Identity Theorem Archive
- 電信研・証明写しデジタル閲覧室
- 記号列位相論図書館（主題索引）
- 臨界関数γ(k)計算機の古いページ
- 反復次数カリキュレータ