A bâtons rompus...

Fichier mis à jour le / Last update: 11 Feb 2000

  1. Systèmes L et fonctions de croissance

  2. Arithmétique : nombres parfaits et suite de Syracuse

  3. Matrices de croissance

  4. Théorie des ensembles, construction de R et axiomes

  5. 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 Mersenne - 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

Questions

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 ?