Normalt antal

I matematik er et normalt tal i base 10 et reelt tal, således at i en række af dets decimaler vises en endelig sekvens af på hinanden følgende decimaler (eller sekvenser ) med den samme begrænsende frekvens som en hvilken som helst af sekvenserne med samme længde. For eksempel vises sekvensen 1789 der med en afskæringsfrekvens på 1 / 10.000. Émile Borel navngav dem således under sin demonstration af, at næsten alle reelle har denne egenskab.

Definitioner

Lad os betegne sæt cifre i basis , og lad os være et reelt tal . Hvis er en endelig rækkefølge af elementer af , lad os bemærke antallet af forekomst af sekvensen blandt de første cifre efter decimaltegnet for den korrekte udvikling af i basen . Nummeret siges: ${\ displaystyle A = \ {0, \ dots, b-1 \}}$ $b$ $x$ $s$ $PÅ$ ${\ displaystyle N (s, n)}$ $s$ $ikke$ $x$ $b$ $x$

simpelthen normal (eller undertiden jævnt fordelt ) i basen, hvis $b$ ${\ displaystyle \ forall a \ i A \ quad \ lim _ {n \ to \ infty} {\ frac {N ((a), n)} {n}} = {\ frac {1} {b}}}$ ;
normal i base, $b$ hvis den simpelthen er normal i base for hele , hvilket svarer til: $b ^ k$ $k> 0$ ${\ displaystyle \ forall k \ geqslant 1 \ quad \ forall s \ i A ^ {k}}$ ${\ displaystyle \ quad \ lim _ {n \ to \ infty} {\ frac {N (s, n)} {n}} = {\ frac {1} {b ^ {k}}}}$ ;
normal (eller undertiden helt normal ), hvis det er normalt i en hvilken som helst base, hvilket svarer til: simpelthen normalt i enhver base.

Normalt antal sætning

Begrebet normalt tal blev introduceret af Émile Borel i 1909. Ved hjælp af Borel-Cantellis lemma beviser han "det normale talteorem": næsten alle reelle tal er helt normale, i den forstand at sættet med ikke-absolut normale tal er af nulmål (for Lebesgue-foranstaltningen ).

Sætning - I næsten ethvert tal (i betydningen Lebesgues mål) er det helt normalt. $\ mathbb {R}$

Demonstration

Ved at bruge, at enhver tællelig sammenslutning af ubetydelige sæt er ubetydelig, koger vi let ned til bevis for, at på et fast grundlag b er næsten ethvert element simpelthen normalt. ${\ displaystyle \ Omega = \ venstre [0,1 \ højre [}$

Lad os betegne dengang . Ethvert element ω af har en unik korrekt udvikling i base b : der findes en unik skrivning af ω i form: ${\ displaystyle A = \ {0, \ dots, b-1 \}}$ $\ Omega$

{\ displaystyle \ omega = \ sum _ {n = 1} ^ {\ infty} {\ frac {\ varepsilon _ {n} (\ omega)} {b ^ {n}}}}

sådan, at for alle n , og sådan, at sekvensen ikke ender med en uendelig række af cifre b - 1. ${\ displaystyle \ varepsilon _ {n} (\ omega) \ i A,}$ ${\ displaystyle \ left (\ varepsilon _ {n} (\ omega) \ right) _ {n \ geq 1}}$

Vi giver os en figur a ∈ A, og vi er interesserede i hyppigheden af udseende af denne figur i rækkefølgen af de n første figurer af udviklingen af ω i base b .

Vi placerer os på probabilized rum hvor betegner den Borelian stamme af , og hvor er det Lebesgue foranstaltning begrænset til . Derefter er familien under en familie af ensartede tilfældige variabler over A og uafhængig , det vil sige for enhver begrænset delmængde B af ℕ ${\ displaystyle \ left (\ Omega, {\ mathcal {A}}, \ mathbb {P} \ right),}$ ${\ mathcal A}$ $\ Omega$ ${\ mathbb P}$ ${\ mathcal A}$ ${\ mathbb P}$ ${\ displaystyle \ left (\ varepsilon _ {n} \ right) _ {n \ geq 1}}$

{\ mathbb P} \ left (\ forall i \ i B \ quad \ varepsilon _ {i} = m_ {i} \ right) = b ^ {{- \ # B}}.

Tilfældige variabler

{\ displaystyle X_ {j} = 1 _ {\ varepsilon _ {j} = a}}

er uafhængige Bernoulli-variabler med parameter 1 / b og i kraft af den stærke lov af store tal hyppigheden af forekomst af a i rækkefølgen af de første n cifre i udvidelsen af ω :

{\ displaystyle F_ {a} (n, \ omega) = {\ frac {X_ {1} (\ omega) + ... + X_ {n} (\ omega)} {n}}}

kontrolleret:

{\ displaystyle F_ {a} (n) {\ underset {ps} {\ longrightarrow}} E [X_ {1}] = {\ frac {1} {b}}.}

Vi konkluderer med at bruge, at en forening af b ubetydelige sæt - hver svarende til et ciffer a - er ubetydelig.

Egenskaber og eksempler

Et rationelt tal (derfor af periodisk udvikling i en hvilken som helst base) er simpelthen normal i base, hvis og kun hvis længden af dets periode i denne base er et multiplum af og hvert ciffer fra 0 til vises tidspunkter i denne periode. Det er derfor aldrig normalt ved basen . For eksempel er den rationelle , hvis decimaludvidelse er skrevet , simpelthen normal i base ti, men ikke i base hundred. $b$ $s$ $b$ ${\ displaystyle b-1}$ ${\ displaystyle p / b}$ $b$ ${\ displaystyle {\ frac {137174210} {1111111111}}}$ ${\ displaystyle 0.12345678901234567890 ...}$

Et tal er normalt i basen, hvis og kun hvis sekvensen er lige fordelt modulo 1 , som ifølge Weyls kriterium svarer til: $x$ $b$ ${\ displaystyle \ left (b ^ {k} x \ right) _ {k}}$

{\ displaystyle \ lim {\ frac {1} {n}} \ sum _ {k = 0} ^ {n-1} \ mathrm {e} ^ {2 \ pi \ mathrm {i} mb ^ {k} x } = 0}

for alle .

{\ displaystyle m \ geq 1}

Produktet af et normalt tal i base med en ikke-nul rationel er normal i base . $b$ $b$

Sættet med tal, der simpelthen er normalt i basen, er magert . A fortiori er sættet med normale tal i basen magert (mens overmængden af universtal i basen er comapar ). $b$ $b$ $b$

Det Champernowne nummer , hvis decimal ekspansion er dannet ved sammenkædning af alle naturlige tal, er normalt i basen ti, som er den Copeland-erdős-tal , opnået ved at sammenkæde de primtal , men det er ikke vist, at 'de er i andre baser. ${\ displaystyle 0 {,} 123 \, 456 \, 789 \, 10 \, 11 \, 12 \, 13 \, 14 \, 15 \, 16 \, 17 \ cdots}$ ${\ displaystyle 0 {,} 2357 \, 11 \, 13 \, 17 \, 19 \, 23 \, 29 \, 31 \, 37 \, 41 \ cdots}$

Et tal kan faktisk være normalt i en base, men ikke i en anden; for eksempel

{\ displaystyle \ alpha = \ sum _ {m = 1} ^ {\ infty} {\ frac {1} {3 ^ {m} 2 ^ {3 ^ {m}}}}}

er normalt i base 2, men ikke i base 6. Mere generelt er de normale tal for to baser og i de samme, hvis og kun hvis heltalene og er "ækvivalente" i betydningen "hinandens rationelle magt ", mens hvis to komplementære dele og af er lukkede for dette ækvivalensrelation , så sæt numre, som er normale i noget grundlag af og unormal i noget grundlag af har magt kontinuum . $b$ $vs.$ ${\ displaystyle \ {2,3,4, ... \}}$ $b$ $vs.$ $R$ $S$ ${\ displaystyle \ {2,3,4, ... \}}$ $R$ $S$

Især (tilfælde ) har sættet med normale tal styrken af kontinuumet (som allerede var udledt fra Borels sætning) såvel som (tilfældet ) sættet af reelle tal, som ikke er normale på noget grundlag (som allerede er trukket fra det faktum, at han er koma). ${\ displaystyle S = \ varnothing}$ ${\ displaystyle R = \ varnothing}$

Normaltalsætningen fastslår eksistensen af normale tal, men konstruerer eksplicit ikke nogen. Imidlertid tog Henri Lebesgue og Wacław Sierpiński uafhængigt Borels bevis og udtrykte det i en " konstruktiv form ", der gør det muligt eksplicit at definere et normalt tal, men måske ikke beregnet . Der er mange ikke-beregnelige normale tal (for eksempel alle reelle tal med tilfældig numerisk udvidelse , som Chaitin-konstanten Ω), men der er også beregelige normale tal.

Det er ekstremt vanskeligt at demonstrere normaliteten af alligevel enkle tal. For eksempel er det uklart, om √ 2 , $π$ , $ln (2)$ eller $e$ er normal (men numeriske eksperimenter er formodninger, de er). Vi ved ikke engang, hvordan vi skal demonstrere, at en given figur vises et uendeligt antal gange i decimaludvidelsen af disse konstanter. Émile Borel formodede i 1950, at algebraisk irrationel er normal; vi kender ikke et modeksempel, men vi kender ikke engang et algebraisk tal, der er normalt i en base.

Normale tal og endelige automater

Der er forbindelser mellem normale tal og endelige automater . Således har vi

Sætning - Et reelt tal er normalt i et bestemt heltal base, hvis og kun hvis dets udvidelse i denne base er ukomprimerbar af en tabsfri kompressionsautomat.

I denne sammenhæng er en tabsfri kompressionsautomat en deterministisk automat med injektionsudgange (derfor en funktionel transducer ).

En følge af sætningen er en sætning på grund af VN Agafonov og stammer fra 1968 om bevarelse af normaliteten af sekvenser valgt af en endelig automat:

Agafonovs sætning - Lad være det binære alfabet. En uendelig rækkefølge til er normal, hvis og kun hvis en efterfølgende valg, der er valgt af en endelig automat, i sig selv er normal . $PÅ$ $PÅ$ $PÅ$

Denne sætning, hvis originale bevis er på russisk, blev bevist af Mary G. O'Connor, derefter generaliseret til vilkårlige alfabeter af Broglio og Liardet.

Noter og referencer

(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på engelsk med titlen " Normal number " ( se listen over forfattere ) .

Jean-Paul Delahaye , “ At være normal? Ikke så let! ", Pour la science , nr . 422,December 2012, s. 126-131 ( læs online ).
J.-P. Marco og L. Lazzarini, Matematik L1 , Pearson ,2012( læs online ) , s. 634(præsenteres kun for base ti ).
É. Borel, " De tællbare sandsynligheder og deres aritmetiske anvendelser ", Rend. Cirk. Mast. Palermo , vol. 27,1909, s. 247-271( s. 260 ).
Borel 1909 (opløst i Hardy og Wright , § 9.12 ) krævede mere end bx , b 2 x , b 3 x , etc. er simpelthen normale i base b k (vi kan tydeligvis stoppe "osv." ved b k -1 x ), men denne tilstand var overflødig, som demonstreret af SS Pillai , " On normale tal " , Proc. Indian Acad. Sci. A , bind. 12,1940, s. 179-184 ( læs online ), for at svare på en anmelders indsigelse mod hans enkle bevis for Champernownes sætning . Dette bevis modsagde Hardy og Wrights kommentar til denne sætning: ” beviset [...] er mere besværligt end man kunne forvente. ” (Sidste sætning i kapitel 9).
En k er det sæt af sekvenser med længden k af elementer A .
Det er denne definition, nu klassisk, der er valgt af Niven 1956 , s. 95 og overtaget af Hervé Queffélec og Claude Zuily, analyse for aggregering , Dunod ,2013, 4 th ed. ( læs online ) , s. 550. Niven 1956 , s. 104-110 viser faktisk, at det er indsat i den implikation, som Pillai demonstrerede mellem hans lysdefinition og Borels (jf. Forrige note).
Borel 1909 .
Samme ( jf. Niven 1956 , s. 103-104 eller Hardy og Wright Hardy og Wright , begyndelsen af § 9.13) med Borels overflødige definition, hvorefter en reel x er normal, hvis det er tilfældet b og alle j ≥ 0 og k ≥ 1, tallet b j x er simpelthen normalt i base b k .
Niven 1956 , s. 110, th. 8.15.
(in) SD Wall , Normal Numbers , UC Berkeley , coll. "Ph.D.-afhandling",1949.
Resultatet af Tibor Šalát (en) (1966) , mere præcist, er angivet på s. 233 af Martine Queffélec, "Gamle og nye resultater om normalitet" , i Dee Denteneer, Frank den Hollander og Evgeny Verbitskiy, Dynamics & Stochastics: Festschrift til ære for MS Keane , IMS ,2006( læs online ) , s. 225-236.
Kuipers og Niederreiter 2012 , s. 8 og 75; Niven 1956 , s. 112-115; mere generelt, hvis f er et polynom, der sender et hvilket som helst heltal> 0 over et heltal> 0, så er den reelle dannede (f.eks. i base ti) ved sammenkædning af heltal f (1), f (2), ... er normal i denne base: (en) H. Davenport og P. Erdős , " Note om normale decimaler " , canadiske J. Math. , Vol. 4,1952, s. 58-63 ( læs online ).
(i) Arthur H. Copeland og Paul Erdős , " normale vi nodenumre " , Bull. Bitter. Matematik. Soc. , Vol. 52,1946, s. 857-860 ( læs online ) ; denne artikel viser, at dette resultat gælder for enhver tilstrækkelig tæt sekvens af heltal.
(i) David H. Bailey og Michał Misiurewicz (de) , " En stærk hot spot teorem " , Proc. Bitter. Matematik. Soc. , Vol. 134,2006, s. 2495-2501.
(in) DH Bailey, " Et ikke-normalitetsresultat " ,12. september 2007.
(i) Wolfgang Schmidt , " er normale tal " , Pacific J. Math. , Vol. 10,1960, s. 661-672 ( læs online ).
(De) Wolfgang M. Schmidt, “ Über die Normalität von Zahlen zu verschiedenen Basen ” , Acta Arithmetica , vol. 7, n o 3,1962, s. 299-309 ( læs online ).
W. Sierpiński, “Elementært bevis for M. Borels sætning om absolut normale tal og effektiv bestemmelse af et sådant tal”, Bull. Soc. Matematik. Frankrig , vol. 45, 1917, s. 125-132 [ læs online ] ;
H. Lebesgue, "Om visse demonstrationer af eksistens", samme bind. (men skrevet i 1909), s. 132-144 [ læs online ] .
(i) Verónica Becher og Santiago Figueira, "Et eksempel på et beregnet absolut normalt tal", Teoretisk. Comput. Sci. , Vol. 270, 2002, s. 947-958 .
(i) David H. Bailey og Richard Crandall , " On Random Character om grundlæggende Constant udvidelser " , Exp. Matematik. , Vol. 10,2001, s. 175-190 ( læs online ).
(i) Davar Khoshnevisan, " Normale tal er normale " , CMI årsrapport ,2006, s. 15, 27-31 ( læs online ).
Verónica Becher og Pablo Ariel Heiber , “ Normal numbers and finite automata ”, Theoretical Computer Science , vol. 477,2013, s. 109–116 ( DOI 10.1016 / j.tcs.2013.01.019 )
V.N. Agafonov, “ Normale sekvenser og endelig automat ”, Sovjetisk matematik Doklady , bind. 9,1968, s. 324-325 ( zbMATH 0242.94040 )- (oversættelse af Dokl. Akad. Nauk SSSR , bind 179, s. 255-256 ).
(ru) VN Agafonov, " Normale sekvenser og endelig automata " , Problemy Kibernetiky , nr . 20,1968, s. 123-129 ( Matematikanmeldelser 0286576 ).
Mary G. O'Connor, “ En uforudsigelig tilgang til endelig tilstands tilfældighed ”, J. Comput. System Sci. , Vol. 37, nr . 3,1988, s. 324-336 ( matematikanmeldelser 0975448 ).
Annie Broglio og Pierre Liardet, ” Forudsigelser med automater ”, Moderne matematik , vol. 135,1992, s. 111-124 ( Matematikanmeldelser 1185084 ).

Bibliografi

(en) L. Kuipers og H. Niederreiter , ensartet fordeling af sekvenser , Dover ,2012( 1 st ed. 1974) ( læses online ) , kapitel 1, § 8: "Normal tal", s. 69-77
(en) Ivan Niven , Irrational Numbers , MAA , koll. "De matematiske monografier fra Carus" ( nr . 11),1956( læs online ) , kapitel 8: “Normale tal”, s. 94-116
(en) GH Hardy og EM Wright , En introduktion til teorien om Numbers ( 1 st ed. 1938) [ Detail Editions ], § 9.12 og 9.13