正規数のソースを表示

[[数学]]における{{読み仮名|'''正規数'''|せいきすう|{{lang-en-short|normal number}}}}とは、[[実数]]のうち、その[[小数]]部の[[数字]]が一様に分布し、数字の列が現れる頻度に[[偏り]]がないものをいう（より詳細な定義については [[#定義]] を参照）。

[[位取り記数法|{{mvar|r}} 進法]]での表示についてこの性質を持つ数を '''{{mvar|r}} 進正規数'''という。単に正規数と述べた場合は、{{math|2}} 以上の任意の[[整数]] {{mvar|r}} に対して {{mvar|r}} 進正規数であることを意味する。

一般論として[[ほとんど (数学)|ほとんど全ての]]実数が正規数であることが知られているが、その[[証明 (数学)|証明]]は{{仮リンク|label=構成的|構成的証明|en|constructive proof}}でないため、正規数であることが判明している具体的な数は非常に限られている。例えば、[[2の平方根]]、[[円周率]]、[[ネイピア数]]はそれぞれ正規数だと予想されているが、その通りか否かは未だ知られていない。

== 定義 ==
本記事では[[数学]]のみならず[[計算機科学]]の用語および記号も用いる。

* &Sigma;　　　''r'' 個の文字からなる[[文字列]]全体からなる[[集合]]（[[アルファベット (計算機科学)|アルファベット]]）
* &Sigma;<sup>&infin;</sup>　　　&Sigma; の[[元 (数学)|元]]のうち、その[[文字列]]が[[無限列]]であるような元全体からなる[[部分集合]]。
* &Sigma;<sup>*</sup>　　　&Sigma; の[[元 (数学)|元]]のうち、その[[文字列]]が[[有限列]]であるような元全体からなる[[部分集合]]。
* ''n''　　　正の[[整数]]
* ''S''　　　&Sigma;<sup>&infin;</sup> の元
* ''w''　　　&Sigma;<sup>*</sup> の元
* ''N''<sub>''S''</sub> ( ''w'', ''n'' )　　　''S'' の最初の ''n'' 個の列に ''w'' が現れる回数（例えば、''S'' = 01010101... のとき、 ''N''<sub>''S''</sub> ( 010, 8 ) = 3 である）


''S'' が'''正規'''であるとは、任意の''w'' に対して、

:<math>\lim_{n \to +\infty} \frac{N_S(w,n)}{n} = \frac{1}{r^{|w|}}</math>

が成り立つことを言う（ここに、|''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<ref>Cassels, J. W. S. "On a problem of Steinhaus about normal numbers."  Colloq. Math., 7, 95-101, 1959.</ref>)。任意の ''r'' 進正規数が ''s'' 進正規数でもあるためには log ''r'' /log ''s'' が[[有理数]]であることが必要十分である (Schmidt, 1960<ref>Schmidt, W. "On normal numbers."  Pacific J. Math., 10, 661-672, 1960.</ref>)。

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

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

== 性質および例 ==
{{Unsolved|数学上|円周率、ネイピア数などは正規数なのか？}}
正規数の概念は、1909年に[[エミール・ボレル|ボレル]]によって導入された<ref>Borel, E. "Les probabilités dénombrables et leurs applications arithmétiques." Rend. Circ. Mat. Palermo, 27, 247-271, 1909.</ref>。彼は「ほとんど全ての」実数は正規数であることを証明した。彼が証明したことを正確に述べると、2 以上の任意の整数 ''r'' に対して ''r'' 進正規でない数の集合はルベーグ零集合（[[ルベーグ測度]]が 0 である集合）である。[[可算集合|可算]]個のルベーグ零集合の[[合併 (集合論)|和集合]]はやはりルベーグ零集合であるから、正規でない数の集合もルベーグ零集合である。この事実から正規数が存在することが従うが、その例は1917年に[[ヴァツワフ・シェルピニスキ|シェルピンスキー]]によって初めて与えられた<ref>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.</ref>。

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

[[チャンパーノウン定数]]
: 0.1234567891011121314151617...
は、十進小数表示において[[自然数]]が順に連なっている実数である。これは基数 10 に関して正規であるが (Champernowne, 1933<ref>Champernowne, D. G. "The Construction of Decimals Normal in the Scale of Ten." J. London Math. Soc., 8, 254-260, 1933.</ref>)、他の基数に関しては正規か否かわかっていない。

[[コープランド-エルデシュ定数]]
: 0.235711131719232931374143...,
は、十進小数表示において[[素数]]が順に連なっている実数であり、これもまた基数 10 に関して正規である (Copeland and Erdős, 1946<ref>Copeland, A. H. and Erdős, P. "Note on normal numbers." Bull. Amer. Math. Soc., 52, 857-860, 1946.</ref>)。

正規数の例として人工的に作られたものではない数たちの正規性を示すことは一般には難しい。例えば、2の平方根、円周率、ネイピア数、[[2の自然対数|log 2]] といった数学的に重要な定数が正規数であるか否かは未だに知られていない。いくつかの傍証によってこれらは正規数であると強く信じられているが、十進小数表示においてそれぞれの数字が無限回現れるか否かさえ知られていない。2001年の論文で、Bailey と Crandall は「[[無理数]]かつ[[代数的数]]である数は正規数である」と予想した<ref>Bailey, D. H. and Crandall, R. E. "On the random character of fundamental constant expansions." Experiment. Math., 10, 175-190, 2001.</ref>。しかし解決への道のりは遠く、反例も知られていないし、正規である代数的数の例も知られていない。

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

* 正規列に対して、有限個の文字を加えたり取り除いたり変更したりといった操作をしても、正規列のままである。この事実は文字列の正規性の定義より明らかである。故に正規数の定義において、小数点より前の部分を含めるか否かは本質的ではない。
* 任意の正の数は二つの正規数の積である。これはより一般的な次の事実より導かれる。正の実数全体の集合を '''R'''<sup>+</sup> とする。その[[部分集合]] ''X'' について、[[差集合]] '''R'''<sup>+</sup> - ''X'' のルベーグ測度が 0 ならば、任意の正の数は二つの ''X'' の元の積に表せる。
* ''x'' が ''r'' 進正規数かつ ''q'' が有理数であるとき、''q'' ''x'' は ''r'' 進正規数である (Wall, 1949<ref>Wall, D. D. "Normal Numbers." Ph.D. thesis, University of California, Berkeley, California, USA, 1949.</ref>)。
* 整数の増大[[数列|列]] (''a''<sub>''n''</sub>) が条件「任意の実数 &alpha; < 1 と十分大きな自然数 ''N'' に対して ''N'' 以下の ''a''<sub>''n''</sub> の個数が ''N''<sup>&alpha;</sup> 以上となる」を満たすとき、''a''<sub>''n''</sub> の ''r'' 進表示を順に小数点以下に並べてできる実数は ''r'' 進正規数となる (Copeland and Erdős, 1946)。このことから、チャンパノウン定数やコープランド-エルデシュ定数が十進正規数であることが従う（素数の列が条件を満たすことは[[素数定理]]より直ちにわかる）。
* 文字列が正規であることは、次のように定義をやや修正した条件を満たすことと同値である。「自然数 ''k'' に対して、文字列を ''k'' 個ずつのブロックに区切る（無限列 ''S'' に対して、最初のブロックは ''S'' [1 ... ''k'']、次のブロックは ''S'' [''k'' + 1 ... 2 ''k''] のように）。これらのブロックたちにおいて、長さが ''k'' の文字列たちが漸近的に同じ頻度で現れる、という性質を任意の ''k'' に対して満たす。」この同値性は、本質的には [[ジェイコブ・ジヴ|Ziv]], [[エイブラハム・レンペル|Lempel]] (1978) の仕事であるが<ref>Ziv, J. and Lempel, A. "Compression of individual sequences via variable-rate coding."  IEEE Trans. Inform. Theory, 24, 530-536, 1978.</ref>、明示的に述べたのは Bourke, Hitchcock, Vinodchandran (2005) である<ref>Bourke, C., Hitchcock, J. M., and Vinodchandran, N. V. "Entropy rates and finite-state dimension."  Theoret. Comput. Sci., 349, 392-406, 2005.</ref>。
* このことより直ちに次の事実が従う。''r'' 進正規数であることと、任意の自然数 ''k'' に対して基数 ''r''<sup>''k''</sup> に関する単正規数であることは同値である。
* したがって、正規数であることと、全ての基数に関して単正規であることは同値である。
* ''x'' が ''r'' 進正規であることは、数列 (''r''<sup>''n''</sup> ''x'')<sub>''n''</sub> の小数部分が[[ヘルマン・ワイル|ワイル]]の意味で一様分布することと同値であり、{{仮リンク|ワイルの判定法|en|Weyl's criterion}}により任意の自然数 ''m'' に対して次の式を満たすことと同値である <ref>Kuipers, L. and Niederreiter, H. "Uniform distribution of sequences." Pure and Applied Mathematics, Wiley-Interscience, New York-London-Sydney, 1974.</ref>。
::<math>\lim_{n \to \infty} \frac{1}{n} \sum_{k=0}^{n-1} e^{2 \pi i m r^k x}=0</math>

== 有限オートマトンとの関係 ==
Agafonov (1968) は[[有限オートマトン]]と正規列との関係を指摘した<ref>Agafonov, V. N. "Normal sequences and finite automata." Soviet Math. Dokl., 9, 324-325, 1968.</ref>。正規列からある[[正則言語]]によって得る部分列はまた正規列である。言い換えると、正規列を有限オートマトンに入力し、受理状態のときのみ入力した文字をそのまま出力することにすれば、そうして出力される部分列はまた正規である。

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

'''有限状態ギャンブラー'''（''finite-state gambler'' または ''finite-state martingale''、以下 '''FSG'''）とは、有限アルファベット &Sigma; 上の有限オートマトンの[[有限オートマトン#概念と用語|状態]]に応じて文字たち（&Sigma; の各元）に金を賭けるギャンブラーのモデルのことである。例えばバイナリアルファベット &Sigma; = { 0, 1 } 上の FSG は、現在の状態 ''q'' に対して定められた割合 ''q''<sub>0</sub> (0 &le; ''q''<sub>0</sub> &le; 1), ''q''<sub>1</sub> (= 1 - ''q''<sub>0</sub>) に従い、ギャンブラーは持ち金の ''q''<sub>0</sub> 倍を 0 に賭け、残りを 1 に賭ける。それから文字が入力され、その文字に賭けられた金の2倍（一般には |&Sigma;| 倍）が次の賭けの元手となる。入力された文字に従い、有限オートマトンの状態が移り、ギャンブラーの賭け方が変わる。ある FSG ''d'' が無限列 ''S'' に対して'''成功する'''とは、有限の元手から始めていつかは任意の目標額に到達すること、すなわち
:<math>\limsup_{n \to \infty} d(S \upharpoonright n) = \infty</math>
が成り立つことをいう。ここに、<math>d(S \upharpoonright n)</math> はギャンブラー ''d'' が ''S'' の最初の ''n'' 個の文字を読み込んだときに持っている金額を表し、limsup は[[上極限]]を意味する。

Schnorr, Stimm (1972) は、正規列に対して「成功する」FSG は存在しないことを示し<ref>Schnorr, C. P. and Stimm, H. "Endliche Automaten und Zufallsfolgen." Acta Informatica, 1, 345-359, 1972.</ref>、Bourke, Hitchcock, Vinodchandran (2005) はその逆を示した<ref>Bourke, C., Hitchcock, J. M. and Vinodchandran, N. V. "Entropy rates and finite-state dimension." Theoret. Comput. Sci. 349, 392-406, 2005.</ref>。すなわち、
:''文字列が正規であることと、その列に対して「成功する」FSG が存在しないことは同値である''
ことが知られている。

'''有限状態圧縮機''' (''finite-state compressor'') とは、有限オートマトンの状態に応じて文字列（空列もあり得る）を出力する機械のモデルである。有限状態可逆圧縮機（''information lossless finite-state compressor''、以下 '''ILFSC'''）とは、出力データおよび最終状態から入力データを一意に復元できる有限状態圧縮機のことである。言い換えると、アルファベット &Sigma; 上の有限状態圧縮機 ''C'' の状態集合が ''Q'' であるとき、''C'' が ILFSC であるとは、''C'' に入力したデータを出力データと最終状態のペアに移す[[写像]] ''f'' : &Sigma;<sup>*</sup> → &Sigma;<sup>*</sup> &times; ''Q'' が[[全単射]]であることを言う。[[ハフマン符号]]や[[シャノン符号化|シャノン符号]]といった[[データ圧縮|圧縮]]の技術は ILFSC を用いて[[実装]]することができる。ある ILFSC ''C'' が無限列 ''S'' を'''圧縮する'''とは、
:<math>\liminf_{n\to\infty} \frac{C(S \upharpoonright n)}{n} < 1</math>
が成り立つことをいう。ここに、<math>C(S \upharpoonright n)</math> は''C'' が ''S'' の最初の ''n'' 個の文字を読み込んだときに出力した文字の個数を表し、liminf は[[下極限]]を意味する。

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

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

== 関連項目 ==
* [[無理数]]
* [[乱数列]]
* [[アルゴリズム的ランダムな無限列]]
* [[コルモゴロフ複雑性]]
* [[チャイティンの定数]]
* [[可逆圧縮]]

== 参考文献 ==
{{脚注ヘルプ}}
{{reflist}}

== 外部リンク ==
* {{MathWorld|urlname=NormalNumber|title=Normal Number}}

{{DEFAULTSORT:せいきすう}}
[[Category:実数]]
[[Category:数論]]
[[Category:乱数]]
[[Category:数学に関する記事]]