A bâtons rompus... (gilles.hunault@univ-angers.fr)
A bâtons rompus...
Fichier mis à jour le 03 May 1997
- Systèmes L et fonctions de croissance
- Arithmétique : nombres parfaits et suite de Syracuse
- Matrices de croissance
- Théorie des ensembles, construction de R et axiomes
- Morphismes 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
<![CDATA[
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) + ...
]]>
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
<![CDATA[
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 ?
]]>
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
<![CDATA[
La matrice 1 1 a pour suite de croissance 1,2,3,4,5 etc.
0 1
]]>
Questions
<![CDATA[
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 ?
]]>
Questions
<![CDATA[
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 ?
]]>
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
<![CDATA[
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
<![CDATA[
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 ?
]]>