Numero normal

Em matemática , um número normal na base 10 é um número real tal que na sequência de seus decimais, qualquer sequência finita de decimais consecutivos (ou sequência ) aparece com a mesma frequência limite que qualquer uma das sequências do mesmo comprimento. Por exemplo, a sequência 1789 aparece ali com uma frequência de corte de 1 / 10.000. Émile Borel os nomeou assim durante sua demonstração de que quase todos os reais possuem essa propriedade.

Definições

Vamos denotar o conjunto de dígitos na base e ser um número real . Se for uma sequência finita de elementos de , notemos o número de aparições da sequência entre os primeiros dígitos após a vírgula do próprio desenvolvimento de em base . O número é dito: NO={0,...,b-1}{\ displaystyle A = \ {0, \ dots, b-1 \}}b{\ displaystyle b}x{\ displaystyle x}s{\ displaystyle s}NO{\ displaystyle A}NÃO(s,não){\ displaystyle N (s, n)}s{\ displaystyle s}não{\ displaystyle n}x{\ displaystyle x}b{\ displaystyle b}x{\ displaystyle x}

• simplesmente normal (ou às vezes uniformemente distribuído ) na base seb{\ displaystyle b} ∀no∈NOlimnão→∞NÃO((no),não)não=1b{\ displaystyle \ forall a \ in A \ quad \ lim _ {n \ to \ infty} {\ frac {N ((a), n)} {n}} = {\ frac {1} {b}}} ;
• normal na baseb{\ displaystyle b} se for simplesmente normal na base para qualquer número inteiro , que é equivalente a:bk{\ displaystyle b ^ {k}}k>0{\ displaystyle k> 0} ∀k⩾1∀s∈NOk{\ displaystyle \ forall k \ geqslant 1 \ quad \ forall s \ in A ^ {k}}limnão→∞NÃO(s,não)não=1bk{\ displaystyle \ quad \ lim _ {n \ to \ infty} {\ frac {N (s, n)} {n}} = {\ frac {1} {b ^ {k}}}} ;
• normal (ou às vezes absolutamente normal ) se for normal em qualquer base, o que equivale a: simplesmente normal em qualquer base.

Teorema do número normal

O conceito de número normal foi introduzido por Émile Borel em 1909. Usando o lema de Borel-Cantelli , ele prova o "teorema dos números normais": quase todos os números reais são absolutamente normais, no sentido de que o conjunto dos números não absolutamente normais é de medida zero (para a medida de Lebesgue ).

Teorema  -  Em , quase qualquer número (no sentido da medida de Lebesgue) é absolutamente normal. R{\ displaystyle \ mathbb {R}}

Demonstração

Usando que qualquer união contável de conjuntos desprezíveis é desprezível, facilmente nos resumimos a provar que em uma base fixa b , quase todos os elementos de é simplesmente normal. Ω=[0,1[{\ displaystyle \ Omega = \ left [0,1 \ right [}

Vamos denotar então . Qualquer elemento ω de tem um desenvolvimento adequado exclusivo na base b  : existe uma escrita única de ω na forma: NO={0,...,b-1}{\ displaystyle A = \ {0, \ dots, b-1 \}}Ω{\ displaystyle \ Omega}

ω=∑não=1∞εnão(ω)bnão{\ displaystyle \ omega = \ sum _ {n = 1} ^ {\ infty} {\ frac {\ varepsilon _ {n} (\ omega)} {b ^ {n}}}}

de forma que, para todo n , e de forma que a sequência não termine com uma sequência infinita de dígitos b - 1. εnão(ω)∈NO,{\ displaystyle \ varepsilon _ {n} (\ omega) \ in A,}(εnão(ω))não≥1{\ displaystyle \ left (\ varepsilon _ {n} (\ omega) \ right) _ {n \ geq 1}}

Damos a nós mesmos uma figura a ∈ A e estamos interessados ​​na frequência de aparecimento desta figura na seqüência das n primeiras figuras do desenvolvimento de ω na base b .

Colocamo-nos no espaço probabilized onde denota a tribo Borelian de e onde é a medida de Lebesgue restrito a . Então, sob , a família é uma família de variáveis ​​aleatórias uniformes sobre A e independentes , ou seja, para qualquer subconjunto finito B de ℕ(Ω,NO,P),{\ displaystyle \ left (\ Omega, {\ mathcal {A}}, \ mathbb {P} \ right),}NO{\ displaystyle {\ mathcal {A}}}Ω{\ displaystyle \ Omega}P{\ displaystyle \ mathbb {P}}NO{\ displaystyle {\ mathcal {A}}}P{\ displaystyle \ mathbb {P}}(εnão)não≥1{\ displaystyle \ left (\ varepsilon _ {n} \ right) _ {n \ geq 1}}

P(∀eu∈Bεeu=meu)=b-#B.{\ displaystyle \ mathbb {P} \ left (\ forall i \ in B \ quad \ varepsilon _ {i} = m_ {i} \ right) = b ^ {- \ # B}.}

Variáveis ​​aleatórias

Xj=1εj=no{\ displaystyle X_ {j} = 1 _ {\ varepsilon _ {j} = a}}

são variáveis ​​de Bernoulli independentes com parâmetro 1 / b e, em virtude da lei forte dos grandes números , a frequência de ocorrência de a na sequência dos primeiros n dígitos da expansão de ω  :

Fno(não,ω)=X1(ω)+...+Xnão(ω)não{\ displaystyle F_ {a} (n, \ omega) = {\ frac {X_ {1} (\ omega) + ... + X_ {n} (\ omega)} {n}}}

verificado:

Fno(não)⟶p.s.E[X1]=1b.{\ displaystyle F_ {a} (n) {\ underset {ps} {\ longrightarrow}} E [X_ {1}] = {\ frac {1} {b}}.}

Concluímos usando que uma união de conjuntos b desprezíveis - cada um correspondendo a um dígito a - é insignificante.

Propriedades e exemplos

• Um número racional (portanto de desenvolvimento periódico em qualquer base) é simplesmente normal na base se e somente se a duração de seu período nesta base for um múltiplo de e cada dígito de 0 a aparece vezes neste período. Portanto, nunca é normal na base . Por exemplo, o racional , cuja expansão decimal é escrita , é simplesmente normal na base dez, mas não na base cem.b{\ displaystyle b}p{\ displaystyle p}b{\ displaystyle b}b-1{\ displaystyle b-1}p/b{\ displaystyle p / b}b{\ displaystyle b}1371742101111111111{\ displaystyle {\ frac {137174210} {1111111111}}}0,12345678901234567890 ...{\ displaystyle 0.12345678901234567890 ...}

• Um número é normal na base se e somente se a sequência for equidistribuída módulo 1 , que, de acordo com o critério de Weyl , é equivalente a:x{\ displaystyle x}b{\ displaystyle b}(bkx)k{\ displaystyle \ left (b ^ {k} x \ right) _ {k}}

lim1não∑k=0não-1e2πeumbkx=0{\ displaystyle \ lim {\ frac {1} {n}} \ sum _ {k = 0} ^ {n-1} \ mathrm {e} ^ {2 \ pi \ mathrm {i} mb ^ {k} x } = 0}para todos .m≥1{\ displaystyle m \ geq 1}

• O produto de um número normal na base por um racional diferente de zero é normal na base .b{\ displaystyle b}b{\ displaystyle b}

• O conjunto de números que são simplesmente normais na base é enxuto . A fortiori , o conjunto de números normais na base é magro (enquanto o superconjunto de números do universo na base é comapar ).b{\ displaystyle b}b{\ displaystyle b}b{\ displaystyle b}

• O número de Champernowne , cuja expansão decimal é formada pela concatenação de todos os números naturais, é normal na base dez, assim como o número de Copeland-Erdős , obtido pela concatenação dos números primos , mas não é mostrado que 'eles estão em outros bases.0,1234567891011121314151617⋯{\ displaystyle 0 {,} 123 \, 456 \, 789 \, 10 \, 11 \, 12 \, 13 \, 14 \, 15 \, 16 \, 17 \ cdots} 0,2357111317192329313741⋯{\ displaystyle 0 {,} 2357 \, 11 \, 13 \, 17 \, 19 \, 23 \, 29 \, 31 \, 37 \, 41 \ cdots}

• Um número pode de fato ser normal em uma base, mas não em outra; por exemplo

α=∑m=1∞13m23m{\ displaystyle \ alpha = \ sum _ {m = 1} ^ {\ infty} {\ frac {1} {3 ^ {m} 2 ^ {3 ^ {m}}}}}

é normal na base 2, mas não na base 6. Mais geralmente, para duas bases e em , os números normais são os mesmos se e somente se os inteiros e são "equivalentes" no sentido de "  poder racional um do outro", enquanto se duas partes complementares e de são fechadas para essa relação de equivalência , então o conjunto de números que são normais em qualquer base de e anormais em qualquer base de tem o poder do continuum . b{\ displaystyle b}vs{\ displaystyle c}{2,3,4,...}{\ displaystyle \ {2,3,4, ... \}}b{\ displaystyle b}vs{\ displaystyle c} R{\ displaystyle R}S{\ displaystyle S}{2,3,4,...}{\ displaystyle \ {2,3,4, ... \}}R{\ displaystyle R}S{\ displaystyle S}

Em particular (caso ) o conjunto de números normais tem o poder do contínuo (que já foi deduzido do teorema de Borel), bem como (caso ) o conjunto de números reais que não são normais em qualquer base (que já é deduzido de o fato de ele estar em coma). S=∅{\ displaystyle S = \ varnothing}R=∅{\ displaystyle R = \ varnothing}

• O teorema do número normal estabelece a existência de números normais, mas explicitamente não constrói nenhum. No entanto, Henri Lebesgue e Wacław Sierpiński pegaram independentemente a prova de Borel e a expressaram de uma "forma construtiva  " que torna possível definir explicitamente um número normal, mas talvez não computável . Existem muitos números normais não computáveis ​​(por exemplo, todos os números reais com expansão numérica aleatória , como a constante de Chaitin Ω), mas também existem números normais computáveis.

• É extremamente difícil demonstrar a normalidade de números ainda simples. Por exemplo, não está claro se √ 2 , π , ln (2) ou e é normal (mas experimentos numéricos são conjecturas que sim ). Nem mesmo sabemos como demonstrar que uma dada figura aparece um número infinito de vezes na expansão decimal dessas constantes. Émile Borel conjecturou em 1950 que qualquer irracional algébrico é normal; não conhecemos um contra-exemplo, mas nem mesmo conhecemos um número algébrico que seja normal em uma base.

Números normais e autômatos finitos

Existem ligações entre números normais e autômatos finitos . Assim, temos

Teorema  -  Um número real é normal em uma determinada base inteira se e somente se sua expansão nesta base for incompressível por um autômato de compressão sem perdas.

Nesse contexto, um autômato de compressão sem perdas é um autômato determinístico com saídas injetivas (portanto, um transdutor funcional ).

Um corolário do teorema é um teorema devido a VN Agafonov e datado de 1968 sobre a preservação da normalidade das subsequências selecionadas por um autômato finito:

Teorema de Agafonov  -  Let Be o alfabeto binário. Uma seqüência infinita em é normal em se e somente se qualquer subseqüência selecionada por um autômato finito é normal em . NO{\ displaystyle A}NO{\ displaystyle A}NO{\ displaystyle A}

Este teorema, cuja prova original está em russo, foi provado novamente por Mary G. O'Connor, e então generalizado para alfabetos arbitrários por Broglio e Liardet.

Notas e referências

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado "  Número normal  " ( ver a lista de autores ) .

1. Jean-Paul Delahaye , “  Ser normal? Não tão fácil !  " Pour la science , n o  422,dezembro 2012, p.  126-131 ( ler online ).
2. J.-P. Marco e L. Lazzarini, Mathematics L1 , Pearson ,2012( leia online ) , p.  634(apresentado apenas para base dez ).
3. É. Borel, “  As probabilidades contáveis ​​e suas aplicações aritméticas  ”, Rend. Circ. Mastro. Palermo , vol.  27,1909, p.  247-271( p.  260 ).
4. Borel 1909 (retomado em Hardy e Wright , § 9.12 ) exigiu mais do que bx , b 2 x , b 3 x ,  etc. são simplesmente normais na base b k (podemos, é claro, parar o “etc.” em b k –1 x ), mas essa condição era redundante, conforme demonstrado por SS Pillai , “  Em números normais  ” , Proc. Indian Acad. Sci. A , vol.  12,1940, p.  179-184 ( ler online ), para responder à objeção de um revisor à sua prova simples do teorema de Champernowne . Esta prova contradiz o comentário de Hardy e Wright sobre este teorema: “  a prova [...] é mais problemática do que se poderia esperar.  » (Última frase do cap. 9).
5. Um k é o conjunto de sequências de comprimento k de elementos Uma .
6. É essa definição, agora clássica, que é escolhida por Niven 1956 , p.  95 e assumido por Hervé Queffélec e Claude Zuily, Analysis for aggregation , Dunod ,2013, 4 th  ed. ( leia online ) , p.  550. Niven 1956 , p.  104-110, de fato, mostra que está inserido na implicação demonstrada por Pillai entre sua definição light e aquela de Borel (cf. nota anterior).
7. Borel 1909 .
8. Mesmo ( cf. Niven 1956 , p.  103-104 ou Hardy e Wright Hardy e Wright , início de § 9.13) com a definição redundante de Borel, segundo a qual um x real é normal se para qualquer base b e todo j ≥ 0 e k ≥ 1, o número b j x é simplesmente normal na base b k .
9. Niven 1956 , p.  110, th. 8,15.
10. (em) SD Wall , Números normais , UC Berkeley , col.  "Tese de doutorado",1949.
11. O resultado de Tibor Šalát  (en) (1966) , mais preciso, é afirmado na p.  233 por Martine Queffélec, “Old and new results on normality” , em Dee Denteneer, Frank den Hollander e Evgeny Verbitskiy, Dynamics & Stochastics: Festschrift in Honor of MS Keane , IMS ,2006( leia online ) , p.  225-236.
12. Kuipers e Niederreiter 2012 , p.  8 e 75; Niven 1956 , p.  112-115; mais geralmente, se f é um polinômio que envia qualquer inteiro> 0 sobre um inteiro> 0, então o real formado (na base dez, por exemplo) pela concatenação dos inteiros f (1), f (2), ... é normal nesta base: (en) H. Davenport e P. Erdős , “  Nota sobre decimais normais  ” , canadense J. Math. , vol.  4,1952, p.  58-63 ( ler online ).
13. (em) Arthur H. Copeland e Paul Erdős , "  normal we note numbers  " , Bull. Amargo. Matemática. Soc. , vol.  52,1946, p.  857-860 ( ler online ) ; este artigo mostra que esse resultado é verdadeiro para qualquer sequência de números inteiros suficientemente densa.
14. (em) David H. Bailey e Michał Misiurewicz  (de) , "  Teorema de um ponto forte forte  " , Proc. Amargo. Matemática. Soc. , vol.  134,2006, p.  2495-2501.
15. (em) DH Bailey, "  Um resultado de não normalidade  " ,12 de setembro de 2007.
16. (em) Wolfgang Schmidt , "  is normal numbers  " , Pacific J. Math. , vol.  10,1960, p.  661-672 ( ler online ).
17. (De) Wolfgang M. Schmidt, “  Über die Normalität von Zahlen zu verschiedenen Basen  ” , Acta Arithmetica , vol.  7, n o  3,1962, p.  299-309 ( ler online ).
18. W. Sierpiński, "Prova elementar do teorema de M. Borel sobre números absolutamente normais e determinação efetiva de tal número", Bull. Soc. Matemática. França , vol. 45, 1917, p.  125-132 [ ler online ]  ;
    H. Lebesgue, “Em certas demonstrações de existência”, mesmo vol. (mas escrito em 1909), p.  132-144 [ ler online ] .
19. (in) Verónica Becher e Santiago Figueira, "Um exemplo de um número absolutamente normal computável", Teoreto. Comput. Sci. , vol. 270, 2002, p.  947-958 .
20. (em) David H. Bailey e Richard Crandall , "  On the Random Character of Fundamental Constant expansions  " , Exp. Matemática. , vol.  10,2001, p.  175-190 ( ler online ).
21. (em) Davar Khoshnevisan, "  Números normais são normais  " , CMI Annual Report ,2006, p.  15, 27-31 ( ler online ).
22. Verónica Becher e Pablo Ariel Heiber , “  números normais e autômatos finitos  ”, Ciência da Computação Teórica , vol.  477,2013, p.  109–116 ( DOI  10.1016 / j.tcs.2013.01.019 )
23. V .N. Agafonov, “  Sequências normais e autômatos finitos  ”, Soviet Mathematics Doklady , vol.  9,1968, p.  324-325 ( zbMATH  0242.94040 )- (tradução de Dokl. Akad. Nauk SSSR , vol.  179, p.  255-256 ).
24. (ru) VN Agafonov, "  Sequências normais e autômatos finitos  " , Problemy Kibernetiky , n o  20,1968, p.  123-129 ( revisões de matemática 0286576 ) .
25. Mary G. O'Connor, "  Uma abordagem imprevisível para a aleatoriedade de estados finitos  ", J. Comput. System Sci. , vol.  37, n o  3,1988, p.  324-336 ( avaliações de matemática  0975448 ).
26. Annie Broglio e Pierre Liardet, “  Predictions with automata  ”, Contemporary Mathematics , vol.  135,1992, p.  111-124 ( revisões de matemática 1185084 ) .

Bibliografia

• (en) L. Kuipers e H. Niederreiter , Distribuição Uniforme de Sequências , Dover ,2012( 1 st  ed. 1974) ( lido on-line ) , capítulo 1, § 8: "números normais", p.  69-77
• (pt) Ivan Niven , Irrational Numbers , MAA , col.  "A Mathematical Caro Monographs" ( N O  11),1956( leia online ) , Capítulo 8: “Números normais”, p.  94-116
• (en) GH Hardy e EM Wright , An Introduction to a Teoria de números ( 1 st  ed. 1938) [ Edições Comerciais ], § 9.12 e 9.13