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 ?