A bÀtons rompus... (gilles.hunault@univ-angers.fr) A bÀtons rompus, Fichier mis È jour le 13 Jul 1994 On trouvera ici quelques sujets de rÅflexion... 1. "baton.html#slc">SystÉmes L et fonctions de croissance 2. "baton.html#arithm">ArithmÅtique : nombres parfaits et suite de Syracuse 3. "baton.html#matfc">Matrices de croissance 4. "baton.html#thens">ThÅorie des ensembles, construction de R et axiomes 5. "baton.html#morphfc">Morphismes de croissance SUJET 1 : SystÉmes L et fonctions de croissance DÅfinitions Un systÉme L est dÅfini par la donnÅe d'un symbole de dÅpart et d'une liste de rÉgles de rÅÅcritures. Le langage associÅ È un tel systÉme est la suite des rÅÅcritures ("itÅrÅes") du symbole de dÅpart. On appelle fonction de croissance du langage la suite des longueurs des itÅrÅes. Un exemple cÅlÅbre : A partir du symbole a et des rÉgles a -> a b et b -> a, on on obtient comme itÅrÅes a b puis a b a puis a b a a b puis a b a a b a b a, ce qui donne comme fonction de croissance la suite (1) 2 3 5 8... des nombres de Fibonacci. Questions a) Peut-on trouver un systÉme L qui admette comme fonction de croissance - la suite 1,2,3,4... des entiers positifs - la suite 1,4,9,16... des carrÅs d'entiers - la suite des nombres premiers - la suite des nombres parfaits - la suite des nombres de "tutmaple.html#mersenne">Mersenne ou de leur 37gÅnÅrateur - un polynome en N donnÅ b) Quelles sont les propriÅtÅs des fonctions de croissance ? - une fonction de croissance est une fonction dÅfinie sur N*, l'ensemble des entiers positifs ; È n on associe la longueur de la n-iÉme itÅrÅe. Peut-on considÅrer cette fonction comme une suite traditionnelle ? - È quelle(s) condition(s) une suite dÅfinie sur N peut-elle Átre considÅrÅe comme une fonction de croissance ? - dÅmontrer qu'une fonction de croissance f : n |--> f(n) vÅrifie une relation de rÅcurrence linÅaire : f(n) = a[1].f(n-1) + a[2].f(n-2) + ... SUJET 2 : ArithmÅtique : nombres parfaits et suite de Syracuse DÅfinitions Un nombre premier est un nombre qui n'admet que 2 diviseurs : 1 et lui-mÁme. Un nombre de Mersenne est de la forme 2^p - 1 avec p premier et 2^p - 1 premier. Un nombre parfait est un nombre somme de ses diviseurs. La successeur de Syracuse pour n vaut n/2 si n est pair et (3*n+1)/2 si n est impair. Questions a) Etudier la rÅpartition dans Q, dans R des nombres premiers b) Trouver tous les nombres premiers entre 2^17 et 2^18 - 1È^5, trouver les 10 premiers nombres de Mersenne et les 30 premiers nombres parfaits (si vous rÅpondez È cette question, le gouvernement amÅricain vous paie un milion de dollars) c) Le MIT s'intÅressait beaucoup È la suite des successeurs de Syracuse pour un enter n quelconque. Pourquoi ? (ce problÉme s'appelle aussi le problÉme de Collatz, le problÉme des 3*x+1...) d) Quels rapports ont ces sujets avec la thÅorie des codes correcteurs ? e) Quels rapports ont ces sujets avec le dernier thÅorÉme de Fermat ? SUJET 3 : Matrices de croissance DÅfinitions Une matrice de croissance est une matrice carrÅe (n,n) dont les coefficients sont entiers, positifs ou nuls. On appelle suite de croissance associÅe È la matrice de croissance M la suite dÅfinie par u(k) = G . M^k . D oË G = (1,0,0....0) et D = (1,1,1...1) sont des vecteurs de Rn. Un exemple La matrice 1 1 a pour suite de croissance 1,2,3,4,5 etc. 0 1 Questions a) Peut-on trouver une matrice M qui admette comme suite de croissance - la suite 1,2,3,5,8... des nombres de Fibonacci - la suite 1,4,9,16... des carrÅs d'entiers - la suite des nombres premiers - la suite des nombres parfaits - la suite des nombres de "tutmaple.html#mersenne">Mersenne ou de leur 37gÅnÅrateur - un polynome en N donnÅ b) Quelles sont les propriÅtÅs des suites de croissance ? - È quelle(s) condition(s) une suite dÅfinie sur N peut-elle Átre considÅrÅe comme une suite de croissance ? - soit u(n) une suite de croissance n ; quelles sont toutes les matrices qui admettent u(n) comme suite de croissance ? - montrer que la suite de croissance u(n) d'une matrice M suit une relation de rÅcurrence linÅaire : u(n) = a[1].u(n-1) + a[2].u(n-2) + ... oË les a[i] sont les coefficients du polynÂme caractÅristique de M ; en particulier, montrer que pour l'exemple citÅ, les coefficients correspondent È la trace et au dÅterminant de la matrice. - quel est le rapport entre une suite de croissance et une Åquation aux diffÅrences finies È coefficients entiers ? SUJET 4 : ThÅorie des ensembles, construction de R et axiomes a) Commenter la construction de N par l'axiomatique de PÅano b) Discuter la progression suivante x + 1 = 0 fait passer de N È Z 2*x + 1 = 0 fait passer de Z È Q x*x - 2 = 0 fait passer de Q a R x*x + 1 = 0 fait passer de R a C c) Les ensembles N Z Q R C H mettent en jeu des structures, des relations Comparer ces structures. On n'oubliera pas la notion de relation d'ordre. Justifier le trou entre C et H (quaternions). d) L'axiome de choix et l'axiome de ZF sont-ils Åquivalents ? En a-t-on vraiment besoin pour "la" thÅorie des ensembles ? e) Peut-on envisager une construction de R diffÅrente des constructions classiques (Deeekind, Cantor, Conway) ? Commenter le thÅorÉme de Conway "tout nombre est un jeu et rÅciproquement". f) En quoi les thÅorÉmes d'incomplÅtude de Goedel influencent-ils les questions prÅcÅdentes ? SUJET 5 : Morphismes de croissance DÅfinitions Soient x et y deux indÅterminÅes. On appelle morphisme f de base (a,b,c,d) la fonction f dÅfinie par f(x) = x^a . y^b, f(y) = x^c . y^d f(x^p . y ^q) = f(x)^p . f(y)^q L'ordre de croissance de x^k . y^m est par dÅfinition k+m. On appelle suite de croissance pour un morphisme f, la suite des ordres de croissance de x, f(x), f(f(x)), f(f(f(x)))... Questions a) Si on ne suppose pas que x et y commutent, comparer ce genre de suite avec la liste des coefficients d'une sÅrie rationelle rÅguliÉre en x et en y b) Quelles sont les propriÅtÅs des suite de croissance liÅes aux morphismes ? c) GÅnÅralisez È un morphisme de base (a[i],i=1...) pour p variables x[k],k=1... d) Quel est le lien entre les sÅries rationnelles et les suites linÅairement rÅcurrentes ?