正規数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

数学における正規数（せいきすう、（英: normal number）とは、実数のうち、その小数部の数字が一様に分布し、数字の列が現れる頻度に偏りがないものをいう（より詳細な定義については #定義 を参照）。

r 進法での表示についてこの性質を持つ数を r 進正規数という。単に正規数と述べた場合は、2 以上の任意の整数 r に対して r 進正規数であることを意味する。

一般論としてほとんど全ての実数が正規数であることが知られているが、その証明は構成的（英語版）でないため、正規数であることが判明している具体的な数は非常に限られている。例えば、2の平方根、円周率、ネイピア数はそれぞれ正規数だと予想されているが、その通りか否かは未だ知られていない。

定義[編集]

本記事では数学のみならず計算機科学の用語および記号も用いる。Σ を r 個の文字の集合（アルファベット）とする。Σ∞ で Σ の元からなる無限列全体の集合を、Σ* で有限列全体の集合を表すものとする。これらの集合の元は文字列 (string) とみなす。自然数（本記事では 1 以上の整数を意味する）n、Σ∞ の元 S、Σ* の元 w に対し、NS ( w, n ) で「S の最初の n 個の列に w が現れる回数」を表すものとする。例えば、S = 01010101... に対して NS ( 010, 8 ) = 3 である。

Σ∞ の元 S が正規であるとは、任意の Σ* の元 w に対し、

が成り立つことを言う（ここに、|w| は w の長さを意味する）。言い換えると、長さが同じ文字列たちが漸近的に同じ頻度で現れる場合にその無限列を正規と呼ぶのである。例えば、二進列（0, 1 の列）が正規であるとは、0 と 1 が 1/2 ずつの頻度で現れ、00, 01, 10, 11 が 1/4 ずつの頻度で現れ、000, 001, 010, 011, 100, 101, 110, 111 が 1/8 ずつの頻度で現れ...（以下同様に続く）ということを意味する。さらに直感的に言い換えるならば、S のある位置に w が現れる「確率」が、乱数列のそれと一致するということである。（乱数列であるためには正規列であることが望まれるが、正規列であれば必ず乱数列とみなせるかというと必ずしもそうではない。）

以降は r を 2 以上の整数とし、x を実数とする。x を r 進法で無限小数表示したときの小数点以降の文字列（この場合は数字の列）が正規であるとき、x は r 進正規数、もしくは基数 r に関して正規数であるという。x が任意の r に対して r 進正規数であるとき、x を単に正規数と呼ぶ。

当然、無限列は正規か正規でないかのいずれかである。一方、実数については、ある r に対しては r 進正規であるのに、別の s に対しては s 進正規ではない、ということがあり得る (Cassels, 1959[1])。任意の r 進正規数が s 進正規数でもあるためには log r /log s が有理数であることが必要十分である (Schmidt, 1960[2])。

定義より明らかなように、正規数の無限小数表示の中には任意の文字列が現れる。デジタルデータを二進数だとみなせば、二進正規数にはあらゆるデータが含まれると考えることができる。しかし、逆は成り立たず、任意の文字列が現れるからといって正規とは限らない。

正規より弱い概念として、単正規 (simply normal) がある。それは |w| = 1 の場合のみ上記の性質を満たすことを意味する。すなわち r 進単正規数とは、r 進小数表示において各数字が 1/r の割合で現れる実数のことである。

性質および例[編集]

数学上の未解決問題
円周率、ネイピア数などは正規数なのか？

正規数の概念は、1909年にボレルによって導入された[3]。彼は「ほとんど全ての」実数は正規数であることを証明した。彼が証明したことを正確に述べると、2 以上の任意の整数 r に対して r 進正規でない数の集合はルベーグ零集合（ルベーグ測度が 0 である集合）である。可算個のルベーグ零集合の和集合はやはりルベーグ零集合であるから、正規でない数の集合もルベーグ零集合である。この事実から正規数が存在することが従うが、その例は1917年にシェルピンスキーによって初めて与えられた[4]。

有理数はいかなる基数に関しても循環小数なので、定義より明らかに正規ではない。非正規数の集合はルベーグ零集合であるのである意味「小さい」が、非可算無限集合であるのでその意味では十分「大きい」とも言える。実際、例えば十進小数表示において 5 を含まない実数は明らかに非正規であり、そのような数は非可算無限個存在する。

チャンパーノウン定数

0.1234567891011121314151617...

は、十進小数表示において自然数が順に連なっている実数である。これは基数 10 に関して正規であるが (Champernowne, 1933[5])、他の基数に関しては正規か否かわかっていない。

コープランド-エルデシュ定数

0.235711131719232931374143...,

は、十進小数表示において素数が順に連なっている実数であり、これもまた基数 10 に関して正規である (Copeland and Erdős, 1946[6])。

正規数の例として人工的に作られたものではない数たちの正規性を示すことは一般には難しい。例えば、2の平方根、円周率、ネイピア数、log 2 といった数学的に重要な定数が正規数であるか否かは未だに知られていない。いくつかの傍証によってこれらは正規数であると強く信じられているが、十進小数表示においてそれぞれの数字が無限回現れるか否かさえ知られていない。2001年の論文で、Bailey と Crandall は「無理数かつ代数的数である数は正規数である」と予想した[7]。しかし解決への道のりは遠く、反例も知られていないし、正規である代数的数の例も知られていない。

以下、その他の正規数の性質を列挙する。

  • 正規列に対して、有限個の文字を加えたり取り除いたり変更したりといった操作をしても、正規列のままである。この事実は文字列の正規性の定義より明らかである。故に正規数の定義において、小数点より前の部分を含めるか否かは本質的ではない。
  • 任意の正の数は二つの正規数の積である。これはより一般的な次の事実より導かれる。正の実数全体の集合を R+ とする。その部分集合 X について、差集合 R+ - X のルベーグ測度が 0 ならば、任意の正の数は二つの X の元の積に表せる。
  • x が r 進正規数かつ q が有理数であるとき、q x は r 進正規数である (Wall, 1949[8])。
  • 整数の増大列 (an) が条件「任意の実数 α < 1 と十分大きな自然数 N に対して N 以下の an の個数が Nα 以上となる」を満たすとき、an の r 進表示を順に小数点以下に並べてできる実数は r 進正規数となる (Copeland and Erdős, 1946)。このことから、チャンパノウン定数やコープランド-エルデシュ定数が十進正規数であることが従う（素数の列が条件を満たすことは素数定理より直ちにわかる）。
  • 文字列が正規であることは、次のように定義をやや修正した条件を満たすことと同値である。「自然数 k に対して、文字列を k 個ずつのブロックに区切る（無限列 S に対して、最初のブロックは S [1 ... k]、次のブロックは S [k + 1 ... 2 k] のように）。これらのブロックたちにおいて、長さが k の文字列たちが漸近的に同じ頻度で現れる、という性質を任意の k に対して満たす。」この同値性は、本質的には Ziv, Lempel (1978) の仕事であるが[9]、明示的に述べたのは Bourke, Hitchcock, Vinodchandran (2005) である[10]。
  • このことより直ちに次の事実が従う。r 進正規数であることと、任意の自然数 k に対して基数 rk に関する単正規数であることは同値である。
  • したがって、正規数であることと、全ての基数に関して単正規であることは同値である。
  • x が r 進正規であることは、数列 (rn x)n の小数部分がワイルの意味で一様分布することと同値であり、ワイルの判定法（英語版）により任意の自然数 m に対して次の式を満たすことと同値である [11]。

有限オートマトンとの関係[編集]

Agafonov (1968) は有限オートマトンと正規列との関係を指摘した[12]。正規列からある正則言語によって得る部分列はまた正規列である。言い換えると、正規列を有限オートマトンに入力し、受理状態のときのみ入力した文字をそのまま出力することにすれば、そうして出力される部分列はまた正規である。

以下の二つの事実が示すように、正規列と有限オートマトンとの間にはより深い関係がある。

有限状態ギャンブラー（finite-state gambler または finite-state martingale、以下 FSG）とは、有限アルファベット Σ 上の有限オートマトンの状態に応じて文字たち（Σ の各元）に金を賭けるギャンブラーのモデルのことである。例えばバイナリアルファベット Σ = { 0, 1 } 上の FSG は、現在の状態 q に対して定められた割合 q0 (0 ≤ q0 ≤ 1), q1 (= 1 - q0) に従い、ギャンブラーは持ち金の q0 倍を 0 に賭け、残りを 1 に賭ける。それから文字が入力され、その文字に賭けられた金の2倍（一般には |Σ| 倍）が次の賭けの元手となる。入力された文字に従い、有限オートマトンの状態が移り、ギャンブラーの賭け方が変わる。ある FSG d が無限列 S に対して成功するとは、有限の元手から始めていつかは任意の目標額に到達すること、すなわち

が成り立つことをいう。ここに、 はギャンブラー d が S の最初の n 個の文字を読み込んだときに持っている金額を表し、limsup は上極限を意味する。

Schnorr, Stimm (1972) は、正規列に対して「成功する」FSG は存在しないことを示し[13]、Bourke, Hitchcock, Vinodchandran (2005) はその逆を示した[14]。すなわち、

文字列が正規であることと、その列に対して「成功する」FSG が存在しないことは同値である

ことが知られている。

有限状態圧縮機 (finite-state compressor) とは、有限オートマトンの状態に応じて文字列（空列もあり得る）を出力する機械のモデルである。有限状態可逆圧縮機（information lossless finite-state compressor、以下 ILFSC）とは、出力データおよび最終状態から入力データを一意に復元できる有限状態圧縮機のことである。言い換えると、アルファベット Σ 上の有限状態圧縮機 C の状態集合が Q であるとき、C が ILFSC であるとは、C に入力したデータを出力データと最終状態のペアに移す写像 f : Σ* → Σ* × Q が全単射であることを言う。ハフマン符号やシャノン符号といった圧縮の技術は ILFSC を用いて実装することができる。ある ILFSC C が無限列 S を圧縮するとは、

が成り立つことをいう。ここに、 はC が S の最初の n 個の文字を読み込んだときに出力した文字の個数を表し、liminf は下極限を意味する。

Ziv, Lempel (1978) は

文字列が正規であることと、その列を「圧縮する」ILFSC が存在しないことは同値である

ことを示した。実際には彼らは次の事実を示している。「ある文字列の ILFSC による最適な圧縮率は、その列のエントロピー率（entropy rate、エントロピーのビット数に対する比）に等しい。」エントロピー率は、ある意味で正規であることにどれだけ近いかを表す数値であり、正規である場合は丁度 1 になる（入力した文字をそのまま出力する ILFSC では、圧縮率が 1 であることも注意しておく）。LZ 圧縮アルゴリズムは漸近的に任意の ILFSC 以上の圧縮率を誇るため、任意の非正規列を圧縮することができる。

この二つの正規列の特徴付けを標語的にまとめると、正規であることは有限オートマトンで制御できない程「ランダム」である、と言える。同様に、チューリングマシンに対して「ランダム」であるという概念を考えることができる。理論的にチューリングマシンは有限オートマトンよりも高性能であるため、この概念は正規であるという概念よりも強い。

関連項目[編集]

参考文献[編集]

[脚注の使い方]
  1. ^ Cassels, J. W. S. "On a problem of Steinhaus about normal numbers." Colloq. Math., 7, 95-101, 1959.
  2. ^ Schmidt, W. "On normal numbers." Pacific J. Math., 10, 661-672, 1960.
  3. ^ Borel, E. "Les probabilités dénombrables et leurs applications arithmétiques." Rend. Circ. Mat. Palermo, 27, 247-271, 1909.
  4. ^ Sierpinski, W. "Démonstration élémentaire d'un théorème de M. Borel sur les nombres absolutment normaux et détermination effective d'un tel nombre." Bull. Soc. Math. France, 45, 125-144, 1917.
  5. ^ Champernowne, D. G. "The Construction of Decimals Normal in the Scale of Ten." J. London Math. Soc., 8, 254-260, 1933.
  6. ^ Copeland, A. H. and Erdős, P. "Note on normal numbers." Bull. Amer. Math. Soc., 52, 857-860, 1946.
  7. ^ Bailey, D. H. and Crandall, R. E. "On the random character of fundamental constant expansions." Experiment. Math., 10, 175-190, 2001.
  8. ^ Wall, D. D. "Normal Numbers." Ph.D. thesis, University of California, Berkeley, California, USA, 1949.
  9. ^ Ziv, J. and Lempel, A. "Compression of individual sequences via variable-rate coding." IEEE Trans. Inform. Theory, 24, 530-536, 1978.
  10. ^ Bourke, C., Hitchcock, J. M., and Vinodchandran, N. V. "Entropy rates and finite-state dimension." Theoret. Comput. Sci., 349, 392-406, 2005.
  11. ^ Kuipers, L. and Niederreiter, H. "Uniform distribution of sequences." Pure and Applied Mathematics, Wiley-Interscience, New York-London-Sydney, 1974.
  12. ^ Agafonov, V. N. "Normal sequences and finite automata." Soviet Math. Dokl., 9, 324-325, 1968.
  13. ^ Schnorr, C. P. and Stimm, H. "Endliche Automaten und Zufallsfolgen." Acta Informatica, 1, 345-359, 1972.
  14. ^ Bourke, C., Hitchcock, J. M. and Vinodchandran, N. V. "Entropy rates and finite-state dimension." Theoret. Comput. Sci. 349, 392-406, 2005.

外部リンク[編集]

  • Weisstein, Eric W. "Normal Number". mathworld.wolfram.com (英語).
「https://ja.wikipedia.org/w/index.php?title=正規数&oldid=94927065」から取得