今回は〈 American Scientist 〉という科学雑誌に掲載されていた数学に関する英文記事を和訳してみました。以前塾講師をしていたときに、数学が得意な高校生に英語を教えていましたが、この記事を使って授業をしたところ、生徒が非常に喜んで話が盛り上がりました。記事の内容はとてもおもしろく、かつ素人にもわかりやすいので今回使ってみた次第です。概して外国人が書く理数系の理論書はわかりやすいですね。著者はマイケル・ヘイズという人です。ただ小生の拙訳ですので、意味不明なところがあるかもしれませんが、ご容赦ください。
※本文にカッコ書きで「訳注」というのが何箇所もありますが、これは小生が本文を読み進める上で参考になると思ったことを書き足したものです。
【三つ組でより安く】
一皮むけば、数を数える方法はすべて同じである。様々な基数における数字が違って見えるのはもっともだが、それらが表す値は全く同じである。10進法において、19と言う数字はこの次の式を速記したものである。
同様に2進法の10011という数字は次の式を意味していると理解される。
1×24+0×23+0×22+1×21+1×20
これは合計すると同じ値になる。3進法の201もそうなる。
2×32+0×31+1×30
r進法の数字に対する一般的な公式は次のようになる。
...d3r3+d2r2+d1r1+d0r0...
ここで r（radix）は基数であり、係数diはその桁の数字である。通常 r は正の整数で、diは 0 から r-1の範囲にある。しかしこれらの限定はどちらも必ずしも厳密に必要なものではない（負の、あるいは無理数の基数で完全に適切な数字を作ることができる。そして以下で負の桁をもつ数字に出会う）。
すべての基数が同じ数を表すという言うことは、しかしながら、すべての記数法がすべての目的において等しく適しているということではない。10という基数は指を使って物を数える私たちにとって適しているということは周知のごとくである。2という基数はコンピューター・テクノロジーを支配している。なぜなら2進法の装置はonやoff、全か無か、と言ったただ2つの確固たる状態をもつ簡単で信頼できるものだからである。コンピューターの回路構成はまた、2進法の計算と論理の間の偶然を利用している。同じ信号が数値（1か0か）と論理値（trueかfalseか）を表しうるのだ。
10進法が文化的に好まれることと、2進法の工学的な利点とは、10進法と2進法の本質的な特性とは何の関係もない。その一方で基数3はそれが有利になるように、純粋な数学的差異をもつのだ。あるもっともらしい尺度によれば、基数3はすべての整数の中でもっとも効率的なのである。基数3は数字を表記する上でもっとも経済的な方法を提供する。
数字表記の費用をどのようにして測るのか？ただ単に桁だけを数えれば、もっとも大きな基数が勝つだろう。例えば1,000,000という基数は0から10進法の999,999までの間のどんな数字も1桁で表す。困るのは一つの数字が百万個の異なる記号のどれにもなりうることである。私たちはそれをすべて識別する必要がある。その対極にあるのが、単一項、あるいは基数1の数字である。10進法の1,000,000の1進法における表記は、1種類の記号しか必要としないが、その記号は百万回繰り返される（1進法の表記は他の基数とは別のカテゴリーにある。それは実際には位取り記数法ではない。しかしこの文脈の中では便利な限定的なケースとして役に立つ）。
百万までの数字を表記するすべての可能な方法の中で、基数1,000,000も基数1も理想的とは思えない。事実、この2つの選択をするよりも悪い選択肢はありえない。桁の数字を最小にすれば、アルファベットの記号が爆発的に増加する。その逆も同様だ；一つの要素を押しつぶせば、他の要素が飛び出す。明らかに私たちは、一つの数字の幅（桁がどのぐらいあるのか）とその奥行き（どれだけ多くの記号が各々の桁を占めるのか）の継ぎ目の寸法を最適化する必要がある。明白な戦略はこれら2つの量の積を最小化することである。言い換えれば、桁数においてr（radix）が基数、w（width）が桁の幅だとすると、rwを一定に保ったまま、rw積を最小化したい。
興味深いことに、この問題は、rとwが整数変数ではなく、連続変数として扱われた場合、つまり、分数の基数と数字を認めた場合の方がより簡単に解ける。そして最適な基数はe、およそ2.718という数値の自然対数の底であることが判明する（図1参照）。3がeにもっとも近い整数なので、3がほとんどいつも最も経済的な整数の基数なのである（図2参照）。
0から10進法の999,999までのすべての数字を表すという作業をもう一度考えてみよう。基数10においては6桁の幅を明らかに必要とするので、rw=60となる。2進法だとよりよくなる。同じ範囲の数字を覆うのには2進法では20桁で十分である。したがってrw=40となる。しかし3進法だとまだ良くなる。3進法の表記では13桁の幅となり、rw=39となる。（もしeという基数が実用可能であるとすれば、その幅は14桁となり、rw=38.056を生み出す）
【3桁ごとに】
この基数3の特性は、初期のコンピューター・デザイナーたちの注目を浴びた。コンピューター部品の計算が、処理される数字の桁と基数の両方に比例するという仮定に立って、彼らはrwがハードウェアの費用をうまく予測し、したがって3進法がハードウェア・リソースを最も効率よく使用できるだろうと提示した。このアイデアの最も古く発表された論文は1950年の『 High-speed Computing Devices 』に現れている。この本は Engineering Research Associates（ERA）社のスタッフによって米海軍のために編纂されたコンピューター技術の調査書である。
ERA社の調査とほぼ同時期に、ハーバート・グロシュはMIT（マサチューセッツ工科大学）において『つむじ風コンピューター計画（Whirlwind computer project）』を3進法で設計することを提案した。『つむじ風』は軍事用のレーダーシステムのためのコントロールシステムに展開され、このレーダーは冷戦の30年間、北米上空を休むことなく監視し続けた。『つむじ風』はまた、磁気コアメモリを含むいくつかの目新しいコンピューター技術の性能試験場でもあった。しかし3進法はテストされた新機軸の中にはなかった。『つむじ風』とその後継者は2進法の装置であった。
たまたまではあるが、3進法で動くコンピューターの1号機は鉄のカーテンの向こう側で作られた。その装置はモスクワ州立大学のニコライ・ブルセンチョフと彼の同僚によって設計され、大学の近くを流れる川にちなんで『セタン（Setun）』と名付けられた。およそ50台の装置が1958年から1965年の間に製造された。セタンは18桁の3進法の数字で動き、その数字は装置に387,420,489通り（=318：訳注）の数値範囲（組合せ）を提供した。rw という観点から見れば、3進法のデザインは（2進法の）58に対して54で優れている。
（訳注：58=2×29、54=3×18）
不運なことに、セタンはコンピューターの計算量を減らすという基数3の可能性を実現しなかった。3桁の数字は各々二個一組の磁気コアに記憶され、磁気コアはその数字が安定した状態を保つため縦につながれた。二個一組の磁気コアは二つの2進数ビットを持ち、それは3桁の数字一つの情報量よりも多くなるため、3進法の利点が無駄になってしまった。
3進法の計算に加えて、3進法のハードウェアで作られたコンピューターは3進法の論理もまた利用できる。2つの数字を比較する作業を考えてみよう。2進法の論理をベースとした装置では、比較はしばしば2段階のプロセスになる。最初に「xはyよりも小さいか？」と問う。そしてその回答によって、そのあと「xはyと等しいか？」といったような2番目の質問をしなければならないかもしれない。3進法の論理はこのプロセスを簡易化するのである。一つの比較をするだけで「小さい」「等しい」「大きい」のどの結果も得ることができる。
3進法のコンピューターの流行は一時的であったが、すぐに消えていったわけではなかった。1960年代には、3進法のロジックゲート（訳注：論理演算を行う論理回路の単位）とメモリーセル（訳注：アドレスの値により指定できる記憶装置内の最小単位）を作り、これらのユニットを加算機のようなより大きな部品に組み立てる計画がいくつかあった。1973年、バッファローにあるニューヨーク州立大学のギデオン・フリーダーとその同僚たちが〈 TERNAC 〉と名付けられた完璧な3進法の装置を設計し、ソフトウェア・エミュレーターを作り上げた。それ以降も3進法でコンピューター処理をするという概念はときどき復活したが、〈 CompUSA 〉（訳注：米国のパソコン専門大型チェーン）で陳列された商品の中に3進法のデスクトップ・パソコンを見つけることはないだろう。
なぜ基数3は人気をはくすことができなかったのだろうか？信頼できる3状態（訳注：論理回路の出力が持つ状態で、高、低の電圧レベルに加えて高インピーダンス状態の3つの状態）の装置が存在しなかったか、あるいは開発をするのがあまりに難しかったのではないかということが容易に推測できる。一度2進法のテクノロジーが確立してしまうと、バイナリーチップを組み立てる方法に莫大な投資がなされたため、他の基数の小さな理論的な利点など圧倒されてしまったのだろう。かてて加えてそのような利点が存在するというのは単なる仮説にすぎない。rw積がハードウェアの複雑さにおける適切な尺度である、言い換えれば、基数が増えることにより増加するコストは、桁数が増えることにより増加するコストと同じであるという前提によってすべてのことが決まってくる。
たとえ3進法の回路がコンピューター・ハードウェアの中に居場所がなくても、基数3を支持する議論は他の文脈の中に適用できるだろう。ここで、
ひどい電話のメニュー・システムの一つを開発していると仮定してみよう。1を押すと迷惑をかけられる、2を押すと他人に見下されるといったようなものだ。もし選択肢がたくさんある場合、それらをまとめる最適な方法とは何だろうか？各々が2，3個のオプションしか提供しないたくさんの細かいメニューをもつ奥深いヒエラルキーを作るべきか？それとも2，3個の長いメニューにその構造を伸ばしたほうがいいだろうか？この状況において論理的なゴールは、悲惨な通話者が自分の目的地へ到達する前に聞かなければならないオプションの数を最小化することである。この問題は位取り表記法において整数をあらわすという問題と類似している。メニューあたりのアイテムの数は基数r（radix）に対応し、メニューの数は桁数w（width）に類似している。不愉快な電話に我慢すべき選択肢の平均数は、メニューあたり3つのアイテムがある場合、最小化される。
【3進法の塵を調べる】
数字の値はすべての基数において同じであるけれども、数字のいくつかの特性がある表記のもとで最もくっきりと現れてくる。たとえば、2進法の数字が偶数か奇数のどちらであるかは一目見ただけでわかる。最後の数字を見るだけである。3進法でも偶数と奇数は区別されるが、その違いの目印は2進法よりも微妙になる。3進法の数字は、その数字の中に1が偶数個含まれるときに偶数となる。（その理由は3の累乗を数えると簡単にわかる。3の累乗は常に奇数である）
20年以上前、ポール・エルデシュとロナルド・グラハムは2の累乗による3進法の表記について推測を発表した。彼らは22と28が、3進法では一つも2を使わずに表記できることに注目した（3進法の表記では22が11、28が100111である）。しかし他のすべての2の正の累乗は、3進法に書き換えると必ず2を一つは含んでしまう。言い換えれば、他の2の累乗に、3の累乗の単なる合計になるものは一つもないということだ。フランス高等科学研究所（ the institut des hautes etudes scientifiques ）の Ilan Vardi は26973568802まで調べ上げたが、反例を発見することができず、この推測は未解決なままである。
3進法はカントール集合、あるいはカントールの塵と呼ばれる特殊な数学上の対象を解明するのにも役立つ（訳注：カントール集合とはフラクタルの1種で、閉区間 [0, 1] に属する実数のうち、その3進展開のどの桁にも 1 が含まれないようなもの全体からなる集合である。カントールの塵はカントール集合の多次元版である）。この集合を組み立てるために、一本の線分をひき、その線分を3つに分割した後、真中のものを取り除く。そのあと残ったより短い2本の線分に戻り、また残った2本の線分をそれぞれ3分割して、真中の部分を取り除く。この作業を永遠に続けた後、何が残るのだろうか？この疑問を解決する一つの方法は、元の線分に0と0.222….の間の3進法の数字を使って、座標を付けることである。（3進法の循環小数0.222….は1.0.と等しい）このように座標を設定すると、最初に3分割して取り除いた真中の線分は、0.1と0.122….の間の座標で構成されている。言い換えれば、すべての座標の小数点以下第一位に1が含まれることになる。同様に2回目の作業によって、小数点以下第二位に1をもつ座標はすべて消える。このパターンを続けていくと、極限集合は3進法の表記においてはどこにも1がない点からなる。結局ほとんどすべての点が掃き出されるが、無数の点も残る。連続する線でつながる点は一つもないが、すぐ近くに任意のご近所さんがいる。このように無限に貫かれた対象を頭の中でイメージするのは難しいが、3進法で記述すると簡明になるのである。
【3重の王冠の中の宝石】
「おそらくすべての記数法の中で一番見事なのは、平衡3進法の記数法だろう」とドナルド・クヌースはその著書『The Art of Computer Programming』の中で述べている。普通の3進法と同じく、平衡3進法のそれぞれの数字は3の累乗の係数であるが、{0,1,2}という集合からできているかわりに、その数字は-1,0,1である。それらが平衡なのは、零を中心に左右対称に配置されているからだ。表記における便宜上、負の数はたいてい前にマイナスの印をつけるかわりに、括線あるいはオーヴァーバーを使って記される。「
」のように。
例をあげると、10進法の19は平衡3進法では
と記述され、この数字は以下のように解釈される。
言い換えると、27-9+0+1である。正の数と負の数の両方のすべての数字が、この体系の中で表記され、各々の数字には一つの表象しかない。平衡3進法を続けて数えると
となる。零をはさんで反対方向に向かうと、最初のいくつかの負の数は
となる。先頭の数字が常に負の数のため、負の値がわかりやすくなっていることに注目しよう。
平衡数システムのアイデアにはとてももつれた歴史がある。セタン・マシーンとフリーダーのエミュレーターは平衡3進法に基礎を置いていたし、つむじ風計画に対するグロシュの提案もそうである。1950年にはクロード・シャノンが左右対称な符号付きの数字のシステムの記事を発表した。その中には3進法と他の基数も含まれていた。しかし20世紀の学者や発明家がこの分野を最初に開拓したのではない。1840年にはオーギュスタン・ルイ・コーシーが様々な基数において符号付きの桁を持つ数について論じているし、レオン・ララネーは平衡3進法の特別な価値について論文を発表して、すぐにそのあとを追った。その20年前、ジョン・レスリーはその非凡な著書『 Philosophy of Arithmetic 』で符号がついているものとついていない数のあらゆる基数における計算方法を発表した。レスリーの理論はその1世紀も前に、ジョン・コルソンの『 Negativo-Affirmativo Arithmetik 』という短い論文の中で出現を予期されていた。さらに時代を遡ると、ヨハネス・ケプラーがローマ数字をモデルにした平衡3進法の体系を使った。符号付きの桁を使った算術は、すでにヒンドゥー教のヴェーダの中に暗示されているという示唆すらある。それは平衡数という概念をどれだけ古いものにしていることか！（訳注：ヴェーダはヒンドゥー教の聖典）
何が平衡3進法をこれほど素晴らしいものにしているのだろうか？それはすべてのものが簡単に見える表記法である。正の数と負の数が、一つのシステムの中に統一されているので、それぞれ別々の符号をもつことにわずらわされることはない。計算方法は2進法とほとんど同じぐらい簡単である。とりわけ掛け算の九九の表は簡明だ。足し算と引き算は本質的には同じ操作である。一つの数字を取り消して、そのあと足すだけだ。取り消し自体もまたたやすい。すべてのを1に変え、その逆もまた同様だ。四捨五入は単なる切り捨てである。最下位の数字を0に変換すれば、自動的に最も近い3の累乗になる。
平衡3進法の最も有名な利用法は、重さに関する数学パズルにおいてである。天秤ばかりを与えられ、1グラムと40グラムの間のある整数の重さがあるとわかっている一枚のコインの重さを測るよう求められる。コインの重さをはかるのに何個の重りが必要だろうか？そそっかしい人は1、2、4、8、16、32グラムの6個の重りが必要だと答えるかもしれない。仮にコインを片方の皿に置き、すべての重りを反対側の皿に置かないといけないとしたら、このような2の累乗の解法以上にいい解決法はない。しかしもし重りを両方の皿に置いていいのなら、1、3、9、27グラムのたった4つの重りで問題を解決する3進法のトリックがある。たとえば35グラムのコイン、符号付き3進法では
は、27グラムと9グラムの重りをコインと反対側の皿に置き、1グラムの重りをコインと同じ皿に置けば、はかりが釣り合う。40グラムまでの重さのすべてのコインをこの方法ではかることができる。
平衡3進法を奨励するウェブサイトを運営しているジェームズ・オールライトは、同じ原理に基づいた貨幣制度を提案している。もし小売店主と顧客の両方が、額面金額が各々3の累乗の紙幣またはコインを一つもっていれば、いかなる取引においても正確な釣銭の授受が可能になる。
【マーサ・スチュアートのファイル・キャビネット】
数週間前、古い新聞や雑誌の切り抜きや書類のファイルの中をかきまわしてあさっていると、私は驚くべき明白さと平凡さを発見した。私が見つけたものはファイルの内容とは関係がない。それは（ファイル・キャビネットの）引き出しの中の整理・配置についてのことであった。
一人の好みがうるさいオフィス・ワーカー、ファイリングで有名なマーサ・スチュアートのことを考えてみよう。彼女は一つのファイル・フォルダーも他のものの陰に潜ませるべきではないと主張している。フォルダーに張られた突き出しているタブは、隣接するフォルダーが常に別の位置にタブを張られるようにアレンジされなければならない。もし新しいファイルを作っているのならば、タブが重ならないように配置をずらすことは簡単だが、フォルダーが無作為に付け足されたり、削除されれば、乱雑で汚くなってしまう。
タブをつける場所が2箇所しかない〈ハーフ・カット〉フォルダーで一杯の引き出しは、最初は左・右・左・右と交互になるだろう。しかし引き出しの真ん中にフォルダーを一つ入れてしまえば、そのパターンは崩れてしまう。どのタイプのフォルダーを選ぼうが、それをどこに置こうが（連続した順番の最後に置く場合は除く）、そのようなあらゆるフォルダーの挿入は配列の競合を招く。フォルダーを取り除いてしまっても同じことが起こる。左を0、右を1というふうに2進法の数字に変換して考えると、初期のファイルは…0101010101….という交互に連続する数列となる。一つの挿入、あるいは削除が00かあるいは11を生み出してしまう。それは結晶転位に非常によく似た傷である（訳注：結晶転位とは結晶における格子欠陥の一種で，結晶の一部を一定方向にすべらせた場合に生ずる原子配列のゆがみ）。反対の符号を持つ2番目の傷を作るか、あるいは傷の位置と配列の最後の間にあるすべてのビットを反転させる（訳注：ビットの反転とは0を1に、1を0にすること）ことによって、原則として傷は修復しうるが、どんなに熱狂的にきれい好きな文書保存者でも、実際のファイルの引き出しにそんなことを実行したがる人はいないだろう。
私自身のファイルの中では、ハーフ・カットではなくサード・カットのフォルダーを利用している。タブは左・真ん中・右の3箇所に現れる。しかしながら毎回フォルダーを挿入した後に、ファイルを喜んで新しいフォルダーに移さなければ、隣接するフォルダーの間の競合を避けられないことを確信していることを、私は長い間考えた、というよりむしろ考えるという面倒な作業を省いて思い込んでいた。そしてエピファニーのファイル・キャビネットが数週間前に届いた（訳注：エピファニーは会社名だと思われる）。私はハーフ・カットとサード・カットのフォルダーを使うことは、全く違うことだと気付いた。
その理由は簡単である。引き出しにいっぱい詰まったサード・カットのフォルダーを、3進法の連続する数字だと解釈すればいいだけだ。その数字の列のどの位置にでも、隣接する数字とは違う新しい数字をいつも挿入することができる。基数3はこの特性を持つ最小の基数である。さらに配列の競合を避ける数字を首尾一貫して挿入することによって3進法の数字を作り上げるとすれば、挿入する数字の選択は常に強制されたものになる。2つかそれ以上の正当な可能性の中から気ままな数字を選択する必要はない。このように、ファイルの引き出しが一杯であるとき、マーサ・スチュアートの完璧な配列を維持することが可能なだけではない。それは実際極めて簡単なのである。
削除は残念ながら挿入よりもより面倒になる。2つの同じ数字が隣り合わないという保証をもって、2進法あるいは3進法の数字の並びから、恣意的に数字を取り除く方法はない。（したがって、もしファイル・フォルダーのダブの位置についてやきもきするほど神経質な人は、おそらく決して何も捨てないだろう）
サード・カットのファイル・フォルダーの間の配列の競合を避ける規則は、極めて明らかなので、私はどこのファイルメーカーの社員にも知られているものと思い込んでいる。ところがファイリングにおける6冊のテキストの中で――明らかにそれは驚くべきほど広範囲にわたる印刷物の小さなサンプルであるが――私は先に上記で述べたような原理について明確な記述を何一つ発見できなかった。
大変奇妙なことに、ファイル・キャビネットの引き出しの中でフォルダーを並べることに関する私の些細な考察によって、より広範な興味をそそるいくつかの数学的な法則につながるのだ。フォルダーの並べ方を探していると仮定してみよう。その中では、2つの同じタブが隣同士に置かれるのを回避するだけでなく、より長いパターンの数字の配列が繰り返されるのも避けようとする。この規則は00や11だけでなく、0101や021021も決して認めない。あらゆる長さの隣接した繰り返されるパターンがない数字の配列を、同じ素因数を一つも持たない数字との類似によって Square Free と言う（訳注：Square Free とは元々素因数分解したときに、同じ因数が出てこない数字のことだが、ここでは同じパターンの繰り返しが出てこない数字の配列のことを指している）。
2進法の場合、1桁の数字である0と1は明らかに Square Free であり、01と10も同様だ（しかし00あるいは11は違う）。そして3ビットの数字の列の中では、010と101がある。しかし他に6通りある組合せの中に、Square Free の数字はない。そしてもし4桁の Square Free の2進法の数字を作りだそうとすれば、行き詰るだろう。そのような配列の数字は存在しないからだ。
Square Free の3進法の数字の列についてはどうだろうか？1桁ごとに桁を増やして調べてみよう。そうすれば、おそらくあるところで道がふさがれていることに気付くだろう。たとえば、0102010という列の上でつまずくかもしれない。0102010は Square Free だが、次に3つの数字のどれを置いてもパターンの繰り返しが発生してしまう。他の多くの3進法の数字もまた、同じような行き詰りに突き当たってしまう。
しかしながら、ノルウェーの数学者 Axel Thueはほぼ1世紀前に無限に続く Square Free の3進法の列が存在することを証明し、その作り方を提示した。そのアルゴリズムの核心は1セットの数字を次のように置き換える規則である。0 → 12、1 → 102、2 → 0。列を構築するどの段階においても、適切な規則が各々の数字に適用され、その結果が次の段階への始点になる。図4はこのプロセスのいくつかの相互連関を示している。Thue はもし Square Free の列でスタートして、その規則を適用し続けるならば、その数字の列は無限に増大していき、決してパターンの繰り返しを含むことはないということを示した。
より最近になると、Square Free の3進法の数字がいくつあるのかという問題に注目が集められてきた。ラトガース大学のドロン・ザイルベルガーは、彼のコンピューターである Shalosh B.Ekhad と共同して書いた論文において、全部で3n個あり、n個の数字が並ぶ3進法の数字の配列の中には、少なくとも2n/17個の Square Free があるということを証明した。アムステルダム大学の Uwe Grimm はいくぶんこの下界を引き締めた。彼はまた上界も発見し、すべてのn桁の数字の並びを n=110まで数えあげた（訳注：順序集合の空でない部分集合 Aについて、A の任意の元 a に対してa≦bが成り立つような b を A の上界という。また、A の任意の元 a に対してb≦aが成り立つような b を A の下界という）。繰り返されるパターンをすべて回避する110個の3進法の数字を並べる方法は、50,499,301,907,904通りあることがわかっている。私は自分の Square Free のファイルの引き出しを組み上げる時、その膨大な数の中の一つを選ばなければならない。
