D	L	M	M	J	V	S
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

21/11/2015

A Ramsey Problem on Hypercubes

Consider the vertex set of the unit n-dimensional cube embedded in n-dimensional Euclidean space. Join each pair of vertices by a straight line segment, creating a complete graph. Color the edges of this complete graph in two colors. Graham and Rothschild proved that if n is sufficently large, there is a monochromatic complete graph of order 4 in some plane. They posed the problem of determining how large n must be. Their lower bound was 6 and their upper bound came to be known as Graham's number. Below we give links to colorings that improve the lower bound to 11. In the coloring matrices, we use colors 0 and 1.

The following link points to a coloring matrix for n=10 wherein 1/3 of the edges are bicolored. When an edge is bicolored, it can belong to cliques of either color. The matrix is here. Here, we use colors 1 and 2. An entry of 3 indicates a bicolored edge. This topic is discussed in a paper that appeared in the Journal of Discrete and Computational Geometry.

Geoff Exoo

Source :

http://isu.indstate.edu/ge/GEOMETRY/cubes.html

Peter Cameron (mathématicien)

Pour les articles homonymes, voir Cameron.

Peter Cameron

Données clés
Naissance	23 janvier 1947 (68 ans) Toowoomba, Queensland(Australie)
Domicile	Oxford
Nationalité	Australien
Champs	Mathématiques
Institutions	Université d'Oxford Queen Mary, University of London (en)
Diplôme	Université du Queensland Université d'Oxford
Distinctions	Prix Whitehead (1979) Médaille Euler (2003)

Peter Jephson Cameron (né le 23 janvier 1947) est un mathématicien australien qui a travaillé en théorie des groupes, encombinatoire, sur la théorie des codes, et la théorie des modèles. Il est actuellement professeur de mathématiques àQueen Mary, University of London (en).

Cameron a reçu un B.Sc. à l'université du Queensland et un D.Phil. en 1971 à l'université d'Oxford, sous la direction dePeter Neumann (de).

Sommaire

[masquer]

Œuvre[modifier | modifier le code]

Cameron s'est spécialisé en algèbre et en combinatoire ; il a écrit des livres sur la combinatoire, l'algèbre, les groupes de permutations, et la logique, et a produit plus de 250 articles¹. Il a un nombre d'Erdős de 1². Son nom est attaché à laconjecture de Cameron–Erdős (en).

Bibliographie[modifier | modifier le code]

Permutation Groups, CUP, 1999
Combinatorics: topics, techniques, algorithms, CUP, 1994
Sets, logics and combinatorics, Springer 1999
Oligomorphic permutation groups, CUP, 1990 (ISBN 0521388368)
Introduction to Algebra, Oxford University Press 1989, 2. éd. 2008
avec Jacobus van Lint (de) : Graph theory, coding theory and block designs, CUP, 1975
avec Jacobus van Lint : Graphs, codes and designs, CUP, 1980
Parallelisms of complete designs, CUP, 1976

Distinctions[modifier | modifier le code]

1979 : Prix Whitehead
2003 : Médaille Euler

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Peter Cameron » (voir la liste des auteurs).

Liens externes[modifier | modifier le code]

Notices d’autorité : Fichier d’autorité international virtuel • International Standard Name Identifier • Bibliothèque nationale de France •Système universitaire de documentation • Bibliothèque du Congrès • Gemeinsame Normdatei • WorldCat
(en) Peter Cameron's home page
(en) Peter Cameron's 60th birthday conference
(en) Theorems by Peter Cameron at Theorem of the Day
(en) Peter Cameron's blog
(en) Peter J. Cameron sur le site du Mathematics Genealogy Project

Source : wikipedia

Conjecture de Cameron-Erdős

En combinatoire, la conjecture de Cameron-Erdős est l'énoncé selon lequel le nombre d'ensembles sans somme contenus dans l'ensemble ${1, \dots , N}$ est $O(2 N /2)$ .

Comme la somme de deux entiers impairs est un entier pair, un ensemble d'entiers impairs est toujours sans somme. Il y a $⎡ N /2⎤$ entiers impairs inférieurs ou égaux à $N$ , et il y a donc $2 N /2$ sous-ensembles de nombres impairs dans ${1, \dots , N}$ . La conjecture de Cameron-Erdős affirme que ceci compte le nombre d'ensembles sans somme, à une constante multiplicative près.

La conjecture a été formulée par Peter J. Cameron et Paul Erdős en 1988¹. Elle a été démontrée par Ben Green² et indépendamment par Alexander Sapozhenko³. Sapozhenko⁴ donne une borne plus précise : le nombre de sous-ensembles sans somme est $\sim c 02 N /2$ si $N$ est pair, et $\sim c 12 N /2$ si $N$ est impair, où $c 0$ et $c 1$ sont des constantes.

Voir aussi[modifier | modifier le code]

Conjecture d'Erdős

Références[modifier | modifier le code]

↑ Peter J. Cameron et Paul Erdős, « On the number of sets of integers with various properties », dans R. A. Mullin (éditeur), Number Theory : Proceedings of the First Conference of the Canadian Number Theory Association (Banff, 1988), Berlin, de Gruyter,‎ 1990, p. 61-79
↑ Ben Green, « The Cameron–Erdős conjecture [archive] », Bulletin of the London Mathematical Society, vol. 36,‎ 2004, p. 769-778 (DOI 10.1112/S0024609304003650, arXiv math.NT/0304058)
↑ Alexander A. Sapozhenko, « The Cameron-Erdős conjecture », Doklady Akademii Nauk, vol. 393, n^o 6,‎ 2003, p. 749–752.
↑ Alexander A. Sapozhenko, « The Cameron–Erdős conjecture », Discrete Mathematics, vol. 308, n^o 19,‎ 2008, p. 4361-4369 (DOI 10.1016/j.disc.2007.08.103)

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cameron–Erdős conjecture » (voir la liste des auteurs).

Portail des mathématiques

Source : wikipedia

Conjecture d'Erdős

Le mathématicien Paul Erdős et ses nombreux collaborateurs ont émis de nombreuses et parfois fameuses conjectures mathématiques sur un large spectre de sujets.

Voici quelques-unes de ces conjectures :

La conjecture de Cameron-Erdős sur des ensembles d'entiers ne contenant pas de somme, démontrée par Ben J. Green.
La conjecture d'Erdős-Burr sur les nombres de Ramsey de graphes.
La conjecture d'Erdős-Faber-Lovász (en) sur la coloration d'unions de cliques.
La conjecture d'Erdős-Graham sur la représentation de l'unité par des fractions égytiennes monochromatiques.
La conjecture d'Erdős-Gyárfás (en) sur les cycles dont la longueur est une puissance de 2 dans des graphes de degré minimum 3.
La conjecture d'Erdős-Hajnal (en) selon laquelle, dans une famille de graphes définie par un sous-graphe induit exclu, chaque graphe possède soit une grande clique, soit un grand sous-ensemble indépendant. (Dans : Ramsey-type theorems, Discrete Applied Mathematics 25 (1989) 37-52)
La conjecture d'Erdős-Heilbronn, en théorie combinatoire des nombres, minorant le nombre de sommes de deux éléments distincts d'un ensemble de résidus modulo un nombre premier, démontrée en 1994 par José António Dias da Silva et Yahya Ould Hamidoune (1947-2011).
La conjecture d'Erdős-Lovász sur les delta-systèmes faibles-forts, ([1], p. 406), démontrée par Michel Deza (en).
La conjecture d'Erdős-Mollin-Walsh sur les triplets consécutifs de nombres puissants.
La conjecture d'Erdős-Menger conjecture sur les chemins disjoints dans des graphes infinis. (résolue par Ron Aharoni (en) et Eli Berger)
La conjecture d'Erdős-Selfridge selon laquelle tout système couvrant contient au moins un module pair.
La conjecture d'Erdős-Stewart sur l'équation diophantienne $n!+1=p_k^ap_{k+1}^b$ , démontrée par Florian Luca, (lien Math Reviews).
La conjecture d'Erdős-Straus sur l'équation diophantienne $4/n=1/x+1/y+1/z$ . 4/n = 1/x + 1/y + 1/z.
La conjecture d'Erdős sur les progressions arithmétiques sur les suites dont la somme des inverses diverge.
La conjecture d'Erdős-Woods sur les nombres déterminés par l'ensemble des diviseurs premiers des k nombres suivants.
La conjecture d'Erdős-Szekeres sur le nombre de points requis pour qu'un ensemble de points contienne un grand polygone convexe.
La conjecture d'Erdős-Turán démontrée par Szemerédi
La conjecture d'Erdős-Turán sur les bases additives d'entiers naturels.
Une conjecture sur la suite de Sylvester.
Une conjecture sur les colorations équitables prouvée en 1970 par András Hajnal et Endre Szemerédi, connue maintenant sous le nom théorème de Hajnal-Szemerédi.
Une conjecture, formulée avec Norman Oler, sur remplissage d'un triangle par des cercles (en) avec un nombre de cercles inférieur, d'une unité, à un nombre triangulaire.
Le problème des distances distinctes d'Erdős.

Sommaire

[masquer]

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős conjecture » (voir la liste des auteurs).

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

[PDF] (en) Fan Chung, Open problems of Paul Erdős in graph theory
Liste de sujets nommés d'après Paul Erdős (en)

Portail des mathématiques

Source : wikipedia

Conjecture d'Erdős-Graham

En théorie combinatoire des nombres, la conjecture d'Erdős-Graham, aujourd'hui résolue, assure que dans toute partition finie de l'ensemble des entiers supérieurs ou égaux à 2, un sous-ensemble de l'une des parties peut servir à représenter 1 par une fraction égyptienne, c'est-à-dire que pour tout r > 0 et toute coloration des entiers 2, 3, 4, … par rcouleurs, il existe un ensemble fini monochrome S tel que

sum_{nin S}frac1n=1.

Plus précisément, Paul Erdős et Ronald Graham avaient conjecturé, parmi les nombreux problèmes sur les fractions égyptiennes, l'existence d'une constante b (nécessairement supérieure ou égale à $e$ ) telle que pour tout r assez grand, le plus grand élément de S puisse être majoré par b^r.

Ernest S. Croot III (en) a démontré leur conjecture en 2000 dans sa thèse de Ph.D.¹ puis, en post-doc à l'UC Berkeley, a publié sa preuve dans une revue². La valeur qu'il donne pour b est $e$ ^{167 000}. Son résultat est un corollaire d'un théorème où il établit l'existence de représentations de 1 par des fractions égyptiennes pour des ensembles C de nombres lisses dans des intervalles de la forme [X, X^1+δ], si C contient assez de nombres pour que la somme de leurs inverses soit au moins égale à 6. La conjecture d'Erdős-Graham s'en déduit en montrant qu'on peut trouver un intervalle de cette forme dans lequel la somme des inverses de tous les nombres lisses vaut au moins 6r ; par conséquent, si les entiers sont colorés par r couleurs, il doit exister une partie C monochrome satisfaisant les conditions de la conjecture.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős–Graham problem » (voir la liste des auteurs).

↑ (en) Ernest S., III Croot, Unit Fractions : Ph.D. thesis, Athens, Univ. Georgia,‎ 2000
↑ (en) Ernest S., III Croot, « On a coloring conjecture about unit fractions », Ann. Math., vol. 157, n^o 2,‎ 2003, p. 545-556, arXiv:math.NT/0311421 [archive]

Parcours de Graham

Le parcours de Graham est un algorithme déterminant l'enveloppe convexe d'un ensemble de points. Son principal intérêt est sa complexité algorithmique en O(n log n). Cet algorithme doit son nom à Ronald Graham, qui a publié l'algorithme original en 1972¹.

Sommaire

[masquer]

Algorithme[modifier | modifier le code]

Illustration : Comme on peut le voir, passer deA à B ou de B à C se fait dans le sens opposé aux aiguilles d'une montre, mais ce n'est pas le cas pour passer de C à D. L'algorithme détecte cette situation et rejette les segments précédemment choisis jusqu'à ce que le tournant pris soit dans le sens opposé aux aiguilles d'une montre (B à D dans ce cas).

La première étape de cet algorithme consiste à rechercher le point de plus petite ordonnée. S'il y a égalité entre un ou plusieurs points, l'algorithme choisit parmi eux le point de plus petite abscisse. Nommons P ce point. La complexité en temps de cette étape est en O(n), n étant le nombre de points de l'ensemble.

L'ensemble des points (P compris) est ensuite trié en fonction de l'angle que chacun d'entre eux fait avec l'axe des abscisses relativement à P. N'importe quel algorithme de tri convient pour cela, par exemple le tri par tas (qui a une complexité de O(n log n)). Pour cela, il n'est pas nécessaire de calculer l'angle réel ; on peut se limiter à la comparaison des tangentes, ou bien même utiliser le produit en croix des coordonnées pour connaître les positions relatives des points. À l'issue de cette étape, on dispose d'un tableau T contenant les points ainsi triés.

L'algorithme considère ensuite successivement les séquences de trois points contigus dans le tableau T, vus comme deux couples successifs. Pour chacune de ces paires de couples, il décide si passer du premier couple au second constitue un « tournant à gauche » ou un « tournant à droite ». Si c'est un « tournant à droite », cela signifie que l'avant dernier point considéré (le deuxième des trois) ne fait pas partie de l'enveloppe convexe, et qu'il doit être rejeté de T. Cette analyse se répète ensuite, tant que l'ensemble des trois derniers points est un « tournant à droite ». Dès que l'on rencontre un « tournant à gauche », l'algorithme passe au point suivant de T. (Si l'on rencontre trois points alignés, à quelque étape que ce soit, on peut choisir de conserver ou de rejeter le point considéré, au choix, suivant la définition que l'on choisit pour l'enveloppe convexe : en effet certaines applications requièrent que tous les points sur l'enveloppe soient compris dans l'enveloppe.)

Ici encore, déterminer si trois points constituent un « tournant à gauche » ou un « tournant à droite » ne requiert pas de calculer l'angle réel entre les deux segments, et peut être réalisé par simple arithmétique. Pour trois points (x₁, y₁), (x₂, y₂) et (x₃, y₃), il suffit de calculer le sens du produit vectoriel des deux vecteurs définis par les points (x₁, y₁), (x₂, y₂) et (x₁, y₁), (x₃, y₃), donné par le signe de l'expression (x₂-x₁)(y₃-y₁)-(y₂-y₁)(x₃-x₁). Si le résultat est nul, les points sont alignés. S'il est positif, les trois points constituent un « tournant à gauche », dans le cas contraire c'est un « tournant à droite ».

Ce processus retournera finalement au point auquel il a commencé, auquel cas l'algorithme sera terminé, et T contiendra alors les points formant l'enveloppe convexe, dans l'ordre inverse des aiguilles d'une montre.

Complexité algorithmique[modifier | modifier le code]

Le tri des points peut se faire avec une complexité en temps en O(n log n). La complexité de la boucle principale peut sembler être O(n²), parce que l'algorithme revient en arrière à chaque point pour évaluer si l'un des points précédents est un « tournant à droite ». Mais elle est en fait en O(n), parce que chaque point n'est considéré qu'une seule fois. Ainsi, chaque point analysé ou bien termine la sous-boucle, ou bien est retiré de T et n'est donc plus jamais considéré. La complexité globale de l'algorithme est donc en O(n log n), puisque la complexité du tri domine la complexité du calcul effectif de l'enveloppe convexe.

Pseudo-code[modifier | modifier le code]

Soit Points l'ensemble de points à examiner, sous la forme d'un tableau indexé à partir de un, et Pile une pile qui contiendra le résultat final.

Trouver le pivot P;
Trier les points par angle (les points d'angle égal seront triés par rapport à leur abscisse);

# Points[1] est le pivot, Points[longueur] aussi (fin du circuit)
Pile.empiler(Points[1]);
Pile.empiler(Points[2]);
POUR i = 3 A Points.longueur
        TANT QUE (Pile.hauteur >= 2) ET (Produit_vectoriel(Pile.second, Pile.haut, Points[i]) ≤ 0)
                Pile.dépiler;
        FIN TANT QUE
        Pile.empiler(Points[i]);
FIN POUR

FONCTION Produit_vectoriel(p1, p2, p3)
        RENVOYER(p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
FIN FONCTION

Explication du pseudo code:

Pile.haut : renvoie le sommet tout en haut de la pile S

Pile.second : renvoie le sommet juste avant Pile.haut

Produit_vectoriel(p1,p2,p3)≤0 : p3 est à droite du segment [p1,p2]

Note: pour gérer les cas dégénérés où l'enveloppe convexe a moins de trois points, un seul point devrait être entré dans la pile au départ, et si jamais la pile a moins de deux points (elle en aura au moins toujours un), alors le haut de la pile devrait être également sorti si le nouveau point est le point considéré. En d'autres termes, la condition du « tant que » devrait être comme suit.

Pile.hauteur >= 2 ? Produit_vectoriel(Pile.second, Pile.haut, Points[i])≤ 0 : Pile.haut == Points[i]

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graham scan » (voir la liste des auteurs).

↑ (en) R. L. Graham, An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set' [archive], Information Processing Letters 1, 1972, p. 132-133.

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill,‎ 2001, 2^e éd. [détail de l’édition](ISBN 0-262-03293-7, 978-0-262-03293-3 et 978-0-262-53196-2). Pages 949–955 de la section 33.3: Finding the convex hull.
(en) Implémentations du parcours de Graham en C++ et en Pascal Objet.
[PDF] Présentation d'algorithmes pour calculer l'envelopper convexe d'un nuage de points

Source : wikipedia

Nombre de Graham

Le nombre de Graham, du nom du mathématicien Ronald Graham, est un entier naturel connu pour avoir été longtemps le plus grand entier apparaissant dans une démonstration mathématique¹. Il est beaucoup trop grand pour être écrit grâce à la notation scientifique et nécessite une notation permettant d'écrire de très grands nombres. Toutefois, il est possible d'obtenir ses derniers chiffres sans trop de difficulté (les dix derniers sont …2464195387).

Sommaire

[masquer]

Le problème de Graham[modifier | modifier le code]

Le nombre de Graham entretient un lien avec une branche des mathématiques connue sous le nom de théorie de Ramsey :

Soit un hypercube de dimension n dont on relie tous les couples de sommets pour obtenir un graphe complet à 2ⁿ sommets. Si l'on colore chacune des 2^n–1(2ⁿ– 1) arêtes du graphe en bleu ou en rouge, quelle est la plus petite valeur de n telle que pour chaque façon de colorer le graphe, il existe un sous-graphe complet monochrome sur quatre sommets coplanaires ?

On ne connait pas encore la réponse à cette question, mais on sait depuis 2003² que ce plus petit n doit être supérieur ou égal à 11 et depuis 2008³ qu'il vaut même au moins 13.

Quant aux majorants de ce plus petit n, le meilleur connu en 1971 était⁴

$left . begin{matrix} underbrace{2 uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow 3} \ underbrace{2 uparrow dots dots dots uparrow 3} \ {vdots } \ underbrace{qquad qquad qquad } \ {2 uparrow dots dots uparrow 3} end{matrix} right } text{7 niveaux}$

(il a été affiné depuis⁵).

Ce nombre est énorme, mais encore moins que le « nombre de Graham » G ci-dessous. Le nombre G doit sa célébrité et son nom à ce qu'il a été présenté en 1977 par Martin Gardner, dans le Scientific American, comme un majorant dû à Graham⁶, au lieu⁷ du majorant bien plus précis ci-dessus, trouvé par Graham et Rothschild (en).

Définition[modifier | modifier le code]

Le nombre de Graham est le 64^e terme de la suite :

4, 3uparrowuparrowuparrowuparrow3, 3uparrowcdotsuparrow3, 3uparrowcdotsuparrow3, ldots

où chaque terme est le nombre de flèches du terme suivant, en utilisant la notation des flèches de Knuth.

De façon équivalente, soit f(n) = hyper(3, n + 2, 3) = 3 → 3 → n ; alors le nombre de Graham est la valeur de la 64^e itérée de la fonction f au point 4.

left. begin{matrix} G &=&3underbrace{uparrow uparrow cdotscdotscdotscdotscdots uparrow}3 \ & &3underbrace{uparrow uparrow cdotscdotscdotscdots uparrow}3 \ & &underbrace{qquad;; vdots qquad;;} \ & &3underbrace{uparrow uparrow cdotscdotcdot uparrow}3 \ & &3uparrow uparrow uparrow uparrow3 end{matrix} right } text{64 niveaux}

Le nombre de Graham G lui-même ne s'exprime pas commodément avec la notation des flèches chaînées de Conway, mais on a l'encadrement

3rightarrow 3rightarrow 64rightarrow 2 < G < 3rightarrow 3rightarrow 65rightarrow 2.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graham's number » (voir la liste des auteurs).

↑ Vers la fin des années 1980, des entiers bien plus grands que le nombre de Graham sont apparus dans plusieurs démonstrations mathématiques sérieuses, par exemple en relation avec les formes finies du théorème de Kruskal découvertes par Harvey Friedman.
↑ (en) Geoffrey Exoo, « A Euclidean Ramsey Problem », Discrete Comput. Geom., vol. 29, n^o 2,‎ 2003, p. 223-227 (DOI 10.1007/s00454-002-0780-5).
↑ (en) Jerome Barkley, « Improved lower bound on an Euclidean Ramsey problem »,‎ 2008 (arXiv 0811.1055).
↑ (en) R. L. Graham et B. L. Rothschild, « Ramsey's theorem for n-parameter sets », Trans. Amer. Math. Soc., vol. 159,‎ 1971, p. 257-292 (lire en ligne [archive]) (p. 290).
↑ (en) Mikhail Lavrov, Mitchell Lee et John Mackey, « Graham's number is less than 2 ↑↑↑ 6 »,‎ 2013 (arXiv 1304.6910). Commentaires [archive] de David Roberts : « The title of this paper is misleading […] it is the exact solution to this problem that they are calling 'Graham's number' […] In fact the bound given in the title, 2↑↑↑6, is a simplification, and not the smallest bound arrived at in the paper, which is 2↑↑2↑↑2↑↑9 […] In terms of the function F of Graham and Rothschild, the LLM bound is between F(4) and F(5) ».
↑ (en) M. Gardner, « Mathematical Games », Scientific American, vol. 237,‎ 1977, p. 18-28 (DOI 10.1038/scientificamerican1177-18). Cette inexactitude est reprise dans (en) Eric W. Weisstein, « Graham's Number [archive] », MathWorld.
↑ Pour plus de détails, voir (en) John Baez, « A while back I told you about Graham's number... » [archive],‎ janvier 2013.

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

(en) John H. Conway et Richard Guy, The Book of Numbers, Springer-Verlag, 1996, p. 61-62 [lire en ligne]

Lien externe[modifier | modifier le code]

(en) Geoffrey Exoo, « A Ramsey Problem on Hypercubes »

Portail des mathématiques

Catégories :

| [+]

Source : wikipedia

Ronald Graham

Ronald Lewis Graham, né le 31 octobre 1935 à Taft en Californie, est un mathématicien que l’American Mathematical Society a reconnu comme « l'un des principaux architectes du développement rapide des mathématiques discrètes ces dernières années à l'échelle mondiale »¹. Il a effectué d'importants travaux sur la théorie de l'ordonnancement, la géométrie algorithmique, la théorie de Ramsey et les suites quasi-aléatoires.

Il occupe le poste d'expert scientifique en chef à l'Institut des technologies de l'information et de la communication deCalifornie, également connu sous le nom de Cal-(IT)² (pour California Institute for Telecommunication and Information Technology), tout en étant professeur titulaire de la chaire Irwin et Joan Jacobs du département d'informatique et d'ingénieriede l'université de Californie à San Diego (UCSD).

Sommaire

[masquer]

Carrière[modifier | modifier le code]

Né à Taft en Californie, il a obtenu son doctorat en mathématiques à l'université de Californie à Berkeley en 1962, sous la direction de Derrick Lehmer².

En 1977, dans un article traitant d'un problème de la théorie de Ramsey, il donnait un grand nombre comme borne supérieure de la solution. Ce nombre, devenu célèbre depuis en tant que nombre le plus grand jamais utilisé dans une démonstration mathématique sérieuse (et inscrit comme tel dans le livre Guinness des records), est désormais connu comme le nombre de Graham.

Graham a popularisé le concept du nombre d'Erdős, qui doit son nom au très prolifique mathématicien hongrois Paul Erdős(1913-1996). Le nombre d'Erdős d'Erdős lui-même est 0 et celui d'un mathématicien M est le plus petit nombre d'Erdős de tous les mathématiciens avec qui M a cosigné un article mathématique, plus un. Le nombre d'Erdős de Graham vaut 1, car celui-ci a corédigé un article avec Erdős, qui était également un de ses bons amis. Erdős logeait souvent chez lui, le laissant s'occuper de ses publications mathématiques, et même de son argent.

Entre 1993 et 1994, Graham fut président de l’American Mathematical Society (AMS). En 1999, il est devenu membre émérite de l’Association for Computing Machinery. En 2003, il a reçu le prix Leroy P. Steele de l'AMS pour l'ensemble de sa carrière. Ce prix lui a été remis le 16 janvier, lors des Joint Mathematics Meetings (rencontres conjointes de mathématiques) tenues àBaltimore, au Maryland. Graham, un mathématicien prolifique — et plus généralement un homme toujours actif —, a reçu bien d'autres prix au fil des années : il fut l'un des lauréats du prestigieux prix Pólya, l'année même où le prix était décerné pour la première fois ; il fut également parmi les premiers à obtenir la médaille Euler. La Mathematical Association of Americalui a également décerné le prix Lester R. Ford, « … institué en 1964 pour récompenser les auteurs d'articles d'excellence publiés dans The American Mathematical Monthly… »³, ainsi que le prix Carl Allendoerfer, institué en 1976 pour les mêmes raisons, mais pour une autre revue, le Mathematics Magazine⁴.

Vie personnelle[modifier | modifier le code]

Ronald Graham, sa femme Fan Chung et Paul Erdős, Japon 1986

Ronald Graham est marié à Fan Chung, professeur titulaire de la chaire Akamai de « mathématiques de l'Internet » à l'université de Californie à San Diego. Il a quatre enfants — trois filles, Che, Laura, Christy, et un fils, Marc — né d'un précédent mariage.

Il fut présenté dans Ripley's Believe It or Not non seulement comme « l'un des plus célèbres mathématiciens du monde », mais aussi comme « un trampoliniste et un jongleur très doué », ancien président de l’International Jugglers' Association (une association internationale de jongleurs).

Publications[modifier | modifier le code]

En 2003, Ronald Graham avait publié environ 300 articles et cinq livres, dont Concrete Mathematics (mathématiques concrètes) avecDonald Knuth.

Notes et références[modifier | modifier le code]

↑ (en) Les prix Leroy P. Steele de l'AMS pour 2003 [archive] (PDF format)
↑ (en) Ronald Graham [archive] sur le site du Mathematics Genealogy Project
↑ (en) Le prix Lester R. Ford de la MAA [archive]
↑ (en) Le prix Carl B. Allendoerfer de la MAA [archive]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ronald Graham » (voir la liste des auteurs).

Voir aussi[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Profil de R. Graham à la faculté de recherche de l'UCSD.

Notices d’autorité : Fichier d’autorité international virtuel • International Standard Name Identifier • Bibliothèque nationale de France •Système universitaire de documentation • Bibliothèque du Congrès • Gemeinsame Normdatei • Bibliothèque nationale de la Diète • WorldCat

Des nombres grands, TRÈS grands - Micmaths

05/08/2015

Vidéo Matrices et applications linéaires - partie 4 : changement de bases

Vidéo Matrices et applications linéaires - partie 2 : applications linéaires en dimension finie

Vidéo Matrices et applications linéaires - partie 1 : rang d'une famille de vecteurs

Espaces vectoriels - partie 1 : espace vectoriel (début)

11/07/2015

Les espaces de Hilbert

Voir le pdf :

http://www.math.polytechnique.fr/~golse/MAT311-10/cours31...

Les espaces de Hilbert MOTIVATIONS Les espaces de Hilbert sont les espaces vectoriels de dimension infinie les plus simples. Ils interviennent entre autres - dans l’´etude des ´equations diff´erentielles et aux d´eriv´ees partielles - en m´ecanique classique (fr´equences propres) - en physique (´equation de Schr¨odinger, m´ecanique quantique). On se placera ici dans le cas d’espaces vectoriels complexes, le cas r´eel ´etant analogue. Principe heursitique : Les propri´et´es alg´ebriques des e.v. de dimension finie s’´etendent aux Espaces de Hilbert pourvu de se limiter aux applications lin´eaires continues et aux sous-espaces ferm´es. On dit qu’une application f entre les C espaces vectoriels H et H 0 est anti-lin´eaire si elle v´erifie ∀x, y ∈ H, ∀λ, µ ∈ C f (λx + µy) = λ¯f (x) + ¯µf (y) D´efinition Un produit hermitien sur un C- espace vectoriel H est une application (u, v) −→< u, v > 1. sesquilin´eaire : u −→< u, v > est anti-lin´eaire, v −→< u, v > lin´eaire 2. hermitienne < u, v >= < v, u > (en particulier < u, u > est r´eel) 3. positive < u, u >> 0 si u 6= 0 On appelle (H,h•, •i) espace pr´ehilbertien. On d´efinit une norme sur H par kxk = √ < x, x > et donc une distance par d(x, y) = kx − yk. D´efinition : Espace de Hilbert On appelle espace de Hilbert un espace pr´ehilbertien dont la norme associ´ee en fait un espace complet. Rappel : Complet ⇔ toute suite de Cauchy est convergente Une source presque in´epuisable d’espaces de Hilbert est donn´ee par Proposition Un sous-espace ferm´e d’un espace de Hibert est un espace de Hilbert (pour la restriction du produit hermitien). EXEMPLES 1. L’espace C n muni de la forme hermitienne hx, yi = Xn j=1 x¯jyj 2. ` 2 (N) espace des suites complexes (xn)n≥0 telles que P∞ n=0 |xn| 2 < +∞ munies de h(xn)n≥0,(yn)n≥0i = X +∞ n=0 x nyn D´emonstration 5. L’espace de Sobolev discret H 1 (N) = {(xn)n≥0 | P n≥1 n 2 |xn| 2 + |x0| 2} muni de h(xn)n≥0,(yn)n≥0iH1 = X +∞ n=1 n 2 x nyn + x 0y0 En effet, l’application (xn)n≥0 −→ (un)n≥0 o`u un = nxn pour n ≥ 1 et u0 = x0 fournit un isomorphisme (= bijection lin´eaire pr´eservant le produit hermitien) entre H 1 (N) et ` 2 (N). Ils sont donc tous deux complets. 3. L 2 (R, C), espace des fonctions L 2 sur R pour < f , g >= Z R ¯f (x)g(x)dx Cf. cours d’int´egration. 4. L 2 (S 1 , C) espace des fonctions L 2 sur le cercle, ou encore des fonctions 2π-p´eriodiques sur R, munies de < f , g >= Z 2π 0 ¯f (x)g(x)dx En effet, les fonctions 2π-p´eriodiques sont d´efinies par la relation f (t + 2π) − f (t) = 0 p.p. ce qui d´efinit un ferm´e de L 2 (R, C). 5. L’espace L0 des fonctions L 2 ([0, 1]) de moyenne nulle muni de < f , g >= Z 1 0 ¯f (x)g(x)dx est un espace de Hilbert. En effet, c’est un ferm´e de L 2 ([0, 1], C) car F(f ) = R 1 0 f (t)dt est continue sur L 2 ([0, 1]) d’apr`es Cauchy-Schwarz : |F(f ) − F(g)| ≤ R 1 0 |f (t) − g(t)| 2dt1/2 . Donc F −1 (0) est ferm´e. G´eom´etrie dans un Hilbert • L’in´egalit´e de Cauchy-Schwarz s’´ecrit |hx, yi| ≤ kxk · kyk • L’´egalit´e de la m´ediane kx − ak 2 + kx − bk 2 = 2kx − a + b 2 k 2 + 2k a − b 2 k 2 • Formule de polarisation (i.e. la norme d´efinit le produit hermitien) <hx, yi="(kx" +="" yk="" 2="" −="" kx="" )="" 4="" (1)="hx," iyk="" (2)="" orthogonalit´e="" si="" f="" est="" un="" sous-espace="" quelconque="" de="" h,="" pose="" ⊥="{x" ∈="" h="" |="" ∀y="" f,hx,="" c’est="" ferm´e.="" la="" continuit´e="" y="" −→="" hx,="" d´eduit="" facilement="" que="" (f="" ⊥)="F" :="" x="" ⇒="" f,="" donc="" il="" r´esultera="" des="" th´eor`emes="" qui="" suivent="" contre-exemples="" existe="" sous-espaces="" ne="" sont="" pas="" ferm´es="" les="" suites="" ayant="" nombre="" fini="" termes="" non="" nuls="" dans="" `="" (n)="" p+∞="" j="1" 1="" ej="" son="" adh´erence.="" le="" c="" 0="" (r)="" l="" (il="" dense,="" cf.="" cours="" d’int´egration)="" etc....="" applications="" continues="" mˆeme="" certains="" ferm´es,="" certaines="" lin´eaires="" continues.="" th´eor`eme="" une="" application="" lin´eaire="" entre="" deux="" espaces="" hilbert,="" e,="" continue="" et="" seulement="" constante="" telle="" pour="" tout="" e="" a="" ku(x)kf="" ≤="" ckxke="" plus="" petit="" tel="" l’in´egalit´e="" ci-dessus="" soit="" v´erifi´ee="" appel´ee="" norme="" u="" not´ee="" kuk.="" attention,="" (continues)="" injectives="" surjectives="" ou="" d’une="" espace="" hilbert="" lui-mˆeme.="" par="" exemple="" lui-mˆeme="" donn´ee="" (x1,="" x2,="" ...,="" xn,="" ...)="" (x2,="" x3,="" xn+1,="" (0,="" x1,="" xn−1,="" respectivement="" surjective="" injective="" surjective.="" noter="" seconde="" pr´eserve="" norme.="" pr´eservant="" norme,="" bijectives.="" d´efinition="" isom´etrie="" elle="" bijective,="" dit="" bijective="" isomorphisme="" isom´etrique.="" (on="" parfois="" simplement="" isomorphisme).="" quatre="" sur="" id´ee="" base="" classiques="" d’alg`ebre="" s’´etendent="" aux="" se="" limite="" vectoriels="" projection="" ferm´e="" pf="" (x)="" (x="" (x))="" (x)k="d(x," f)="infy∈F" yk.="" ∀x="" ⊥.="" illustration="" du="" projection.="" d´emonstration="" d´ecomposition="" ferm´e,="" alors="" ⊕="" repr´esentation="" riesz="" forme="" hilbert.="" unique="" vecteur="" au="" ,="" u(x)="<" au,=""> D´emonstration : On peut supposer u 6= 0. On choisit bu un vecteur unitaire orthogonal `a F = ker(u) (bu existe car H = F ⊕ F ⊥ et F 6= H). On a alors u(x − u(x) bu u(bu) ) = 0, donc H = ker(u) ⊕ Cbu. On v´erifie alors que u(x) = hu(bu)bu, xi pour x ∈ ker(u) puis pour x ∈ Cbu. C’est donc vrai pout tout x, et la proposition est v´erifi´ee avec au = u(bu)bu. Applications : Si F est un sous-espace vectoriel de H, (F ⊥) ⊥ = F Si H est un espace de Hilbert, H ∗ = {Appl.lin.ctn u : H → C} est isomorphe `a H. Le produit hermitien est donn´e par hhu, vii = hau, bv i. On a aussi (H ∗ ) ∗ ' H. Crit`ere de fermeture F ⊂ H est ferm´e si et seulement si il existe u : H −→ K continue telle que F = ker(u). L’existence de u continue entraˆıne ´evidemment la fermeture de F. Inversement, si F est ferm´e, l’application de projections sur F ⊥ fournit le u recherch´e. Crit`ere de densit´e F ⊂ H est un sous espace dense, si et seulement si F ⊥ = {0} Exemple fondamental : Pour n ∈ Z, les en(t) = e int de L 2 (S 1 , C) engendrent l’espace des polynˆomes trigonom´etriques. Cet espace sera dense ssi R 1 0 f (t)e intdt = 0 pour tout n ∈ Z entraˆıne f = 0 p.p. Le th´eor`eme de F´ejer (cf. appendice du poly) affirme la densit´e (pour la norme C 0 ) des polynˆomes trigonom´etriques dans C 0 (S 1 , C). Donc si R 1 0 f (t)e intdt = 0 pour tout n, R 1 0 f (t)g(t)dt = 0 pour tout g dans C 0 et donc par densit´e de C 0 (S 1 , C) dans L 2 (S 1 , C) (pour la norme L 2 , cette fois), cela sera encore vrai pour tout g dans L 2 , et finalement f = 0. Plus g´en´eralement les e iλnt forment un ensemble dense dans L 2 ([0, 1], C) si et seulement si R 1 0 f (t)e iλntdt = 0 pour tout n entraˆıne f = 0 p.p. La th´eorie des fonctions holomorphes (cf. amphis 8,9) fournira un crit`ere efficace pour r´epondre `a cette question (th´eor`eme de M¨untz-Szasz). Le th´eor`eme de Hahn-Banach est une cons´equence des pr´ec´edents et s’utilise dans un cadre plus g´en´eral. Th´eor`eme de Hahn-Banach Soit F un sous espace d’un espace de Hilbert. Si x0 ∈/ F alors il existe une forme lin´eaire continue u telle que u(F) = 0 et u(x0) = 1 D´emonstration. Soit W = F ⊥ = (F) ⊥. On a PW (x0) 6= 0 car x0 ∈/ F. Soit a = PW (x0) |PW (x0)| 2 Alors < a, x0 >= 1 et < a, x >= 0 pour x ∈ F. Repr´esentation de Riesz pour les formes hermitiennes Definition (Th´eor`eme) On dit qu’une forme sesquilin´eaire B(u, v) est continue sur H si il existe une constante C telle que ∀u, v ∈ H |B(u, v)| ≤ Ckukkvk Remarque : Si B est hermitienne, il suffit de v´erifier que B(u, u) ≤ Ckuk 2 . Cela r´esulte ais´ement de la formule de polarisation. On a alors : Th´eor`eme de repr´esentation de Riesz (cas hermitien) Soit B une forme sesquilin´eaire continue. Il existe alors une application lin´eaire unique L : H −→ H, continue, telle que B(u, v) = hLu, vi D´emonstration . Cons´equence : Existence de l’adjoint Si u : H −→ K est continue, il existe u ∗ : K −→ H continue telle que ∀x ∈ H, ∀y ∈ K, hu(x), yi = hx, u ∗ (y)i II. Bases Hilbertiennes D´efinition des bases Hilbertienne La famille (en)n≥1 est une base Hilbertienne ssi 1. ∀i, j,hei , eji = δ j i 2. L n Cen est dense dans E Attention, en dimension infinie une base Hilbertienne n’est pas une base au sens alg´ebrique..... ( un espace complet n’a pas de base alg´ebrique d´enombrable). Proposition Si (en)n≥1 est une base Hibertienne de H, tout x ∈ H s’´ecrit de mani`ere unique x = P n xnen avec xn ∈ C. De plus kxk 2 = P n kxnk 2 (formule de Parseval). Si (en)n≥1 est une base Hilbertienne, on a la d´ecomposition en s´erie convergente (mais pas absolument convergente) x = X n < x, en > en et kxk 2 = X n kxnk 2 = X n |hx, eni|2 (Formule de Parseval) Existence des bases Hilbertiennes On dit qu’un espace est s´eparable s’il poss`ede un sous ensemble d´enombrable dense. Th´eor`eme d’existence d’une base Hilbertienne. Tout espace de Hilbert s´eparable poss`ede une base Hilbertienne. D´emonstration : Proc´ed´e de Gram-Schmidt Soit (xn)n≥1 une suite dense dans H, et Fn le s.e.v. engendr´e par x1, ..., xn. Quitte `a renum´eroter, on peut supposer dim(Fn) = n et donc Fj de codimension un dans Fj+1. Soit en un g´en´erateur de F ⊥ n−1 ∩ Fn. Alors (en) est une base Hilbertienne. Les espaces ` 2 (N), L 2 (R, C), L 2 (S 1 , C), H k , bref tous les espaces que l’on rencontre habituellement .... sont s´eparables. Le r´esultat pr´ec´edent nous dit que les espace de Hilbert s´eparables se ressemblent tous, c’est-`a-dire qu’ils sont tous isomorphes. Proposition Un espace de Hilbert s´eparable est isomorphe `a ` 2 (N) D´emonstration En effet un tel isomorphisme est fourni par les coordonn´ees dans une base Hilbertienne (en)n≥1, i.e. l’application de ` 2 (N) dans H donn´ee par (xn)n≥1 −→ X +∞ n=1 xnen La formule de Parseval dit que c’est une isom´etrie. D´esormais tous les espaces de Hilbert seront suppos´es s´eparables Corollaire 1 Si H est de dimension infinie, sa boule unit´e B = {x ∈ H | kxk ≤ 1} n’est pas compacte. En effet la suite (en)n≥1 n’a pas de sous-suite convergente (car ken. − emk = 2). Corollaire 2 Si H est de dimension infinie, il n’existe pas de mesure non triviale sur H, invariante par translation En effet, B(0, 1) contient une infinit´e de boules de rayon 1/4, les B(ej/2, 1/4), donc µ(B(0, 1/4)) = 0, et comme H est r´eunion d´enombrable de boules de rayon 1/4, µ(H) ≡ 0. Mais alors pour tout sous ensemble A de H, µ(A) ≤ µ(H) = 0, donc µ est identiquement nulle. Remarque : Il existe malgr´e tout des mesures int´eressantes en dimension infinie : la mesure de Wiener permet de mesurer certaines parties de C 0 ([0, 1], R). Elle est li´ee au mouvement Brownien. Exemple Fondamental : S´erie de Fourier L 2 Ici n ∈ Z, H = L 2 (S 1 , C), < f , g >= R S1 f (t)g(t)dt. On prend en(t) = √ 1 2π exp(−int) et on a bien < en, em >= δ n m. Dans ce cas, xn =< x, en >= √ 1 2π R S1 f (t) exp(−int)dt sont les coefficients de Fourier. La densit´e de l’espace engendr´e par les ep, entraˆıne D´ecomposition en s´erie de Fourier L 2 Pour f dans L 2 (S 1 ), la s´erie de Fourier de f converge en moyenne quadratique : limq→∞ R 2π 0 |f (t) − Pq n=−q cn(f )e −int| 2dt −→ 0 On a l’´egalit´e de Parseval : 1 2π R 2π 0 |f (t)| 2dt = P n∈Z |cn(f )| 2 Inversement si an est une suite telle que P n a 2 n < +∞, la s´erie de Fourier P n ane int converge (en norme L 2 !) dans L 2 (S 1 ). Une bonne th´eorie des s´eries de Fourier • Comme en th´eorie de l’int´egration (et d’ailleurs, grˆace `a cette th´eorie) on a une th´eorie de s´eries de Fourier parfaite : toute fonction L 2 est somme de sa s´erie de Fourier, toute s´erie de Fourier convergent quadratiquement a pour somme une fonction L 2 (`a condition d’utiliser la bonne norme pour la convergence). • Ce n’est pas le cas pour la norme C 0 : on ne sait pas d´ecrire simplement les fonctions qui sont limites uniformes de leur s´erie de Fourier (certaines fonctions continues ne le sont pas-voir plus loin). • Cela n’empˆeche pas que toute fonction continue soit limite uniforme de polynˆomes trigonom´etriques (mais pas n´ecessairement sa s´erie de Fourier), d’apr`es le th´eor`eme de F´ejer. • On peut montrer facilement que si f est de classe C 1 , la s´erie de Fourier converge uniform´ement vers f . Divers types de Convergence des S´eries de Fourier La question de la convergence ponctuelle (ou uniforme) de la s´erie de Fourier de f vers f date de Dirichlet (1829). Attention, l’´enonc´e pr´ec´edent n’affirme a priori aucune convergence ponctuelle, mais par Cauchy pr´ecis´e dans L 2 , une suite qui converge L 2 a une sous-suite convergeant p.p. (donc on peut trouver une suite de sommes partielles convergeant p.p. ). Un r´esultat c´el`ebre et difficile de Carleson (1966) affirme que pour une fonction L 2 , la suite elle-mˆeme PN −N cn(f )e int converge p.p. vers f (t). D’apr`es Kahane et Katznelson (1965), ´etant donn´e un ensemble quelconque de mesure nulle sur S 1 , il existe une fonction continue dont la s´erie de Fourier ne converge pas sur E. D’apr`es Kolmogorov, si f est suppos´ee int´egrable (et non de carr´e int´egrable) la s´erie de Fourier peut diverger partout.... Bases orthogonales de polynomes Soit < f , g >= R R f (t)g(t)e − t 2 2 dt. Les polynˆomes forment un sous-espace dense de L 2 (R, e − t 2 2 dt). On peut construire une base orthogonale de polynˆomes en appliquant l’orthogonalisation de Gram-Schmidt `a la famille (t n )n≥1. Ce sont les polynˆomes d’Hermite. A une constante de ` normalisation pr`es, on a Hn(x) = (−1)n e x 2/2 d n dx n (e −x 2/2 ) De mˆeme pour le produit hermitien < f , g >= R +∞ 0 f (t)g(t)e −tdt on obtient comme base orthogonale les polynˆomes de Laguerre Ln(x) = e x n! d n dx n (e −x x n ) D´ecomposition en polynˆomes de Laguerre D´ecomposition en polynˆomes de Laguerre de cos(5x) exp(x) D´ecomposition en Ondelettes de Haar. On note ϕ = 1[0,1/2[ − 1[1/2,1[ et ϕn,k (x) = 2nϕ(2n x − k) o`u 1A d´esigne la fonction caract´eristique de l’intervalle A et n, k ∈ N. La fonction constante 1 et les ϕn,k pour 0 ≤ k < 2n , forment un syst`eme orthonormal de l’espace de Hilbert L 2 ([0, 1]). Les ondelettes de Haar ϕ5,3(bleu), ϕ3,2(rouge) D´ecomposition en ondelettes de Haar de cos avec 25 coefficients. 09 D´ecomposition en ondelettes de Haar de cos(5x) exp(x) D´ecomposition en Fourier et en ondelettes de Haar de x 2 avec 16 coefficients. Convergence faible On dit que la suite (xn)n≥1 converge faiblement vers x∞ si pour tout vecteur v ∈ H, hxn, vi converge vers hx∞, vi. La convergence faible peut se voir comme une convergence coordonn´ee par coordonn´ee . Mais elle ne d´epend pas du choix de la base Hilbertienne. Proposition : compacit´e faible de la boule unit´e Si H est de dimension infinie, toute suite born´ee poss`ede une sous suite convergeant faiblement . D´emonstration Il suffit d’extraire une suite diagonale des coordonn´ees dans une base Hilbertienne (ek )k≥1. Il est alors clair que pour chaque k, la suite n −→ hxn, ek i converge vers hx, ek i et par lin´earit´e il en est de mˆeme pour hx, vi si v est somme finie des ek . Par densit´e des sommes finies, on v´erifie sans peine qu’il en est de mˆeme pour hxn, vi quel que soit v dans E. Remarque La notion de convergence faible n’est la convergence pour aucune m´etrique. Elle d´efinit une topologie, et satisfait les propri´et´es de la convergence des suites. En particulier si une suite converge faiblement, la limite est unique. Pour la prochaine fois : revoir la compacit´e et la transform´ee de Fourier. Mercredi 16 Juin `a 15H45. Le cours sera donn´e par Etienne Ghys, ´ Membre de l’Acad´emie des Sciences Sp´ecialiste de G´eom´etrie et Dynamique Coauteur du film “Dimensions” Mercredi 16 Juin `a 15H45. Etienne Ghys, ´ “Sur la coupe des vˆetements, d’apr`es Tchebychev”. On se donne une surface S et on veut l’habiller par un tissu. Le tissu c’est un domaine du plan D (le patron de la couturi`ere), les fils sont les droites horizontales et verticales, et l’habillage c’est F : D −→ S tel que F est une isom´etrie sur les fils horizontaux et verticaux (chaˆıne et trame) mais on ne demande pas que l’orthogonalit´e des fils soit pr´eserv´ee. Quelles sont les surfaces habillables ? Combien de morceaux faut-il pour habiller une sph`ere par exemple ? Compl´etude de ` 2 (N). Si (xk )k≥1 est une suite de Cauchy de ` 2 (N), on pose xk = (xn,k )n≥1 et chacune des suites (xn,k )k≥1 est de Cauchy (car |xn,k − xn,l | 2 ≤ kxk − xlk 2 ) et donc converge vers un nombre complexe zn. On pr´etend maintenant que z = (zn)n≥1 est la limite des (xk )k≥1. En effet pour tout n, on a que Xn j=1 |xj,k − zj | 2 = lim q→∞ Xn j=1 |xj,k − xj,q| 2 ≤ lim q→∞ kxk − xqk 2 Comme le terme de droite est ind´ependant de n, on a kxk − zk 2 ≤ limq→∞ kxk − xqk 2 qui tend vers 0 avec k (car la suite (xk )k≥1 est de Cauchy) et donc (xk )k≥1 tend vers z. Retour D´emonstration du th´eor`eme de la projection. Soit une suite yn ∈ F telle que limn kx − ynk = d(x, F). La suite yn est de Cauchy en utilisant la formule de la m´ediane kyn − ymk 2 = 2(kyn − xk 2 + kym − xk 2 ) − 4(kx − yn + ym 2 k 2 ) ≤ 4(d(x, F) + ε) 2 − 4d(x, F) 2 Si le minimum est atteint en y = PF (x), on a kx − (y + tz)k 2 ≥ kx − yk 2 pour tout z ∈ F et donc 2thx − y, zi + t 2 kzk 2 ≤ 0 pour tout t, ce qui n’est possible que si hx − y, zi = 0 quel que soit z ∈ F c’est-`a-dire x − PF (x) ∈ F ⊥. Retour D´emonstration du th´eor`eme de Riesz (cas sesquilin´eaire) : D’apr`es l’ hypoth`ese de continuit´e, pour chaque u fix´e la forme lin´eaire v −→ B(u, v) est continue. Par le th´eor`eme de Riesz, il existe Lu unique tel que B(u, v) = hLu, vi. Il nous faut montrer que L est lin´eaire et continue. La lin´earit´e r´esulte imm´ediatement de l’unicit´e et de la sesquilin´earit´e de B. Pour la continuit´e, nous avons par hypoth`ese kLuk 2 = hLu, Lui = B(u, Lu) ≤ CkukkLuk On en d´eduit kLuk ≤ Ckuk et donc la continuit´e de L. Retour

Algèbre multilinéaire

Pour les articles homonymes, voir Algèbre (homonymie).

En mathématiques, l’algèbre multilinéaire étend les méthodes de l’algèbre linéaire. Tout comme l’algèbre linéaire est bâtie sur le concept de vecteur et développe la théorie des espaces vectoriels, l’algèbre multilinéaire est bâtie sur le concept de tenseur et développe la théorie des espaces tensoriels. Dans les applications, de nombreux types de tenseurs surviennent. La théorie se veut exhaustive et comprend l'étude d'un certain nombre d'espaces et l'exposé de leurs relations.

Sommaire

[masquer]

Historique de la notion d’algèbre multilinéaire[modifier | modifier le code]

L'algèbre multilinéaire a des racines variées plongeant dans ce qui a été appelé au XIX^e siècle l’analyse tensorielle ou le « calcul tensoriel des champs tensoriels ». Elle s’est développée à partir de l’utilisation des tenseurs en géométrie différentielle, en relativité générale, et dans de nombreuses branches des mathématiques appliquées. Vers le milieu du XX^e siècle, l’étude des tenseurs est reformulée plus abstraitement. Le traité d’algèbre multilinéaire du groupe Bourbaki (le chapitre 3 du livre d'Algèbre, intitulé plus précisément Algèbres tensorielles, algèbres extérieures, algèbres symétriques) est particulièrement influent — en fait le terme algèbre multilinéaire a probablement été inventé là.

Une des raisons de cette nouvelle formulation est une nouvelle aire d’application, l’algèbre homologique. Le développement de la topologie algébrique durant les années 1940 donne une incitation additionnelle au développement d’un traitement purement algébrique du produit tensoriel. Le calcul des groupes homologiques du produit de deux espaces topologiques utilise le produit tensoriel ; mais c'est seulement dans les cas les plus simples, tel que celui d’un tore, que les groupes homologiques peuvent être calculés directement de cette façon (voir le théorème de Künneth). Les phénomènes topologiques, assez subtils, sont à la source d’une nouvelle réflexion sur les concepts fondamentaux du calcul tensoriel.

Le matériel à organiser est dense, incluant des idées remontant à Hermann Günther Grassmann, et des idées venant de la théorie des formes différentielles qui avaient mené à la cohomologie de De Rham, ainsi qu’à des notions plus élémentaires telles que le produit extérieur qui généralise le produit vectoriel.

La description qui résulte du travail de Bourbaki, axiomatique, rejette entièrement l'approche vectorielle (utilisée par exemple dans la construction des quaternions), c’est-à-dire, dans le cas général, la relation entre les espaces tensoriels et les groupes de Lie. Bourbaki suit, au contraire, une approche nouvelle basée sur la théorie des catégories1, dans laquelle le groupe de Lie ne fournit qu'une description secondaire. Puisque cela mène à un traitement beaucoup plus rigoureux, il n’y aura probablement, en mathématiques, plus de retour en arrière.

Cette approche revient essentiellement à définir les espaces tensoriels comme les constructions requises dans le but de réduire les problèmes multilinéaires à des problèmes linéaires. Cette attaque purement algébrique ne transfère aucune intuition géométrique.

Le bénéfice de cette formalisation est qu’en réexprimant des problèmes en termes d’algèbre multilinéaire, il y a une « meilleure solution » claire et bien définie : les contraintes que la solution exerce sont exactement celles dont on a besoin en pratique. En général il n’y a pas besoin d’invoquer une quelconque construction ad hoc, idée géométrique ou autre pour coordonner des systèmes. Dans le vocabulaire de la théorie des catégories, tout est entièrement naturel.

Conclusion sur l’approche abstraite[modifier | modifier le code]

En principe l’approche abstraite peut recouvrir tout ce qui est fait via l’approche traditionnelle. En pratique cela peut ne pas sembler si simple. D’autre part la notion detransformation naturelle est compatible avec le principe de la covariance générale de la relativité générale. Ce dernier fait affaire aux champs tensoriels (les tenseurs variant de point en point sur une variété), mais la covariance affirme que le langage des tenseurs est essentiel à la formulation propre de la relativité générale.

Quelques décennies plus tard le point de vue plus abstrait venant de la théorie des catégories fut lié à l’approche qui avait été développée dans les années 1930 par Hermann Weyl (dans son livre célébré et difficile Les groupes classiques). En un sens, cela compléta la théorie, regroupant les points de vue anciens et nouveaux.

Contenu de l’algèbre multilinéaire[modifier | modifier le code]

Le contenu de l’algèbre multilinéaire a changé bien moins que la présentation, à travers les ans. Voici d’autres pages qui y sont centralement pertinentes :

Du point de vue des applications[modifier | modifier le code]

Consultez ces articles pour certains moyens dans lesquels les concepts de l’algèbre multilinéaire sont appliqués, dans diverses guises :

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Algèbre multilinéaire, sur Wikiversity

Notes et références[modifier | modifier le code]

↑ En fait, Bourbaki base son approche sur la notion de propriété universelle, ce qui est moins général que la théorie des catégories, mais semble suffisant dans ce cas

Source : https://fr.wikipedia.org/wiki/Alg%C3%A8bre_multilin%C3%A9aire

Espace de Hilbert

Cette page contient des caractères spéciaux ou non latins. Si certains caractères de cet article s’affichent mal (carrés vides, points d’interrogation…), consultez la page d’aide Unicode.

Le concept mathématique d'espace de Hilbert, nommé d'après David Hilbert, généralise la notion d'espace euclidien. Il étend les méthodes de l'algèbre linéaire et de l'analysedes espaces euclidiens classiques (plan, de dimension deux, et espace à trois dimensions) à des espaces de dimension quelconque, finie ou infinie. Un espace de Hilbert est unespace vectoriel muni d'un produit scalaire qui permet de mesurer des longueurs et des angles. De plus, un espace de Hilbert est complet, ce qui permet d'y appliquer les techniques de l'analyse mathématique.

Des espaces de Hilbert apparaissent fréquemment en mathématiques et en physique, essentiellement en tant qu'espaces fonctionnels de dimension infinie. Les premiers espaces de Hilbert ont été étudiés sous cet aspect pendant la première décennie du xx^e siècle par David Hilbert, Erhard Schmidt et Frigyes Riesz. Ils sont des outils indispensables dans les théories des équations aux dérivées partielles, mécanique quantique, analyse de Fourier (ce qui inclut des applications au traitement du signal et letransfert de chaleur) et la théorie ergodique qui forme le fondement mathématique de la thermodynamique. John von Neumann forgea l'expression espace de Hilbert pour désigner le concept abstrait qui sous-tend nombre de ces applications. Le succès des méthodes apportées par les espaces de Hilbert menèrent à une époque très prolifique pour l'analyse fonctionnelle. En plus des espaces euclidiens classiques, les exemples les plus courants d'espaces de Hilbert sont les espaces de fonctions de carré intégrable, lesespaces de Sobolev qui sont constitués de fonctions généralisées, et les espaces de Hardy de fonctions holomorphes.

L'intuition géométrique intervient dans de nombreux aspects de la théorie des espaces de Hilbert. Ces espaces possèdent des théorèmes analogues au théorème de Pythagoreet à la règle du parallélogramme. En mathématiques appliquées, les projections orthogonales sur un sous-espace (ce qui correspond à aplatir l'espace de quelques dimensions) jouent un rôle important dans des problèmes d'optimisation entre autres aspects de la théorie. Un élément d'un espace de Hilbert peut être défini de manière unique par ses coordonnées relativement à une base de Hilbert, de façon analogue aux coordonnées cartésiennes dans une base orthonormale du plan. Quand cet ensemble d'axes estdénombrable, l'espace de Hilbert peut être vu comme un ensemble de suites de carré sommable. Les opérateurs linéaires sur un espace de Hilbert sont semblables à des objets concrets : dans les « bons » cas, ce sont simplement des transformations qui étirent l'espace suivant différents coefficients dans des directions deux à deux perpendiculaires, en un sens qui est précisé par l'étude de leur spectre.

Sommaire

[masquer]

Définition et exemples[modifier | modifier le code]

Exemple introductif : l'espace euclidien de dimension 3[modifier | modifier le code]

Un des exemples les plus courants d'espace de Hilbert est l'espace euclidien de dimension 3, noté ℝ³, muni du produit scalaire usuel. Le produit scalaire associe, à deux vecteurs $mathbf{x}$ et $mathbf{y}$ un nombre réel noté $mathbf{x} cdot mathbf{y}$ . Si $mathbf{x}$ et $mathbf{y}$ ont pour coordonnées cartésiennes respectives $(x_1,x_2,x_3)$ et $(y_1,y_2,y_3)$ , alors leur produit scalaire est :

mathbf{x} cdot mathbf{y} = x_1y_1+x_2y_2+x_3y_3.

Le produit scalaire satisfait aux propriétés suivantes :

il est symétrique : pour tous vecteurs $mathbf{x}$ et $mathbf{y}$ , $mathbf{x} cdot mathbf{y} = mathbf{y} cdot mathbf{x}$
il est linéaire par rapport au premier argument : pour tous nombres réels $a$ et $b$ et tous vecteurs $x_1, x_2, y$ , on a l'égalité $(a x_1 + b x_2)cdot y = a x_1 cdot y + b x_2 cdot y$
il est défini positif : pour tout vecteur $mathbf{x}$ , le produit $mathbf{x}cdot mathbf{x}$ est positif, et nul si et seulement si $mathbf{x}$ est égal au vecteur nul.

Le produit scalaire est intimement relié avec la géométrie euclidienne par la formule suivante, qui relie le produit scalaire de deux vecteurs $mathbf{x}$ et $mathbf{y}$ avec leurs longueurs (notées respectivement $|mathbf{x}|$ et $|mathbf{y}|$ ) et l'angle $theta$ qu'ils forment :

mathbf{x}cdotmathbf{y} = |mathbf{x}|,|mathbf{y}|,costheta.

Toute opération sur les vecteurs qui vérifie les trois propriétés ci-dessus est également appelée produit scalaire. Un espace vectoriel muni d'un produit scalaire est dit espace préhilbertien réel.

Un espace de Hilbert est un espace préhilbertien qui possède de plus une propriété d'analyse mathématique : il est complet, argument reposant sur les limites de suites de vecteurs dans cet espace.

Définition[modifier | modifier le code]

Un espace de Hilbert est un espace préhilbertien complet, c'est-à-dire un espace de Banach dont la norme ║·║ découle d'un produit scalaire ou hermitien 〈·, ·〉 par la formule

| x| = sqrt{langle x,x rangle}.

C'est la généralisation en dimension quelconque d'un espace euclidien ou hermitien.

Théorème de Fréchet-von Neumann-Jordan[modifier | modifier le code]

Article détaillé : Théorème de Fréchet-von Neumann-Jordan.

Un espace de Banach (respectivement espace vectoriel normé) est un espace de Hilbert (respectivement espace préhilbertien) si et seulement si sa norme vérifie l'égalité

| x + y|^2 + | x - y|^2 = 2 ( | x|^2 + | y|^2)

qui signifie que la somme des carrés des quatre côtés d'un parallélogramme est égale à la somme des carrés de ses diagonales (règle du parallélogramme).

Ce théorème est dû à Maurice René Fréchet, John von Neumann et Pascual Jordan.

Identité de polarisation :

Dans le cas réel le produit scalaire est défini par $langle x,y rangle = frac{1}{4}bigl(| x + y|^2 -| x - y|^2bigr).$
Dans le cas complexe le produit hermitien est défini par $langle x,y rangle = langle x,y rangle_1+{rm i}langle x,{rm i}y rangle_1$ ,où $langle x,yrangle_1=frac14bigl(|x+y|^2-|x-y|^2bigr)$ et $i$ est l'unité imaginaire (le nombre complexe identifié au couple de réels (0, 1)).

Exemples[modifier | modifier le code]

L'espace euclidien ℝⁿ muni du produit scalaire usuel.
L'espace hermitien ℂⁿ muni du produit hermitien usuel.
L'espace $L 2 ([a, b])$ des fonctions de [a, b] à valeurs dans ℂ et de carré sommable avec la convention que deux fonctions égales presque partout sont égales (voir l'articleespace $L p$ ), muni de $langle f,g rangle = int_a^bf(x)overline{g(x)}~mathrm dx.$
L'espace de suites ℓ², constitué des suites $(u_n)_{n inN}$ de nombres complexes telles que $sum_{n=0}^infty|u_n|^2<+infty,$ le produit hermitien de deux suites $u$ et $v$ étant par définition la somme de la série $sum_{n=0}^infty u_noverline{v}_n.$

Classification[modifier | modifier le code]

Article détaillé : Base hilbertienne.

Dans un espace de Hilbert de dimension infinie, le concept habituel de base est remplacé par celui de base hilbertienne qui permet, non plus de décrire un vecteur par ses coordonnées, mais de l'approcher par une suite infinie de vecteurs ayant chacun des coordonnées finies. On est donc au confluent de l'algèbre linéaire et de la topologie.

Deux espaces de Hilbert admettant des bases hilbertiennes équipotentes sont isométriquement isomorphes, autrement dit : tout espace de Hilbert de base hilbertienne X est isomorphe à ℓ²(X). Par exemple : tout espace de Hilbert séparable (et de dimension infinie) est isomorphe à ℓ²(ℕ) = ℓ².
Réciproquement, deux bases hilbertiennes d'un même espace de Hilbert ont même cardinalité. Ce nombre cardinal, appelé la dimension hilbertienne de l'espace, le caractérise donc à isomorphisme près et joue ainsi le même rôle que la dimension dans la catégorie des espaces vectoriels sur un corps fixé.
Un espace de Hilbert est de dimension finie si et seulement si sa dimension hilbertienne est finie, et dans ce cas, ces deux entiers sont égaux.

Applications[modifier | modifier le code]

C'est dans le cadre des espaces de Hilbert qu'est développée la théorie de la formulation variationnelle, utilisée dans de nombreux domaines de la physique.
En mécanique quantique, l'état d'un système est représenté par un vecteur dans un espace de Hilbert.

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hilbert Space » (voir la liste des auteurs).
Pierre Colmez, Éléments d'analyse et d'algèbre (et de théorie des nombres), Éditions de l'École Polytechnique,‎ 2009 (ISBN 978-2-7302-1563-3, lire en ligne), chap. II.2 (« Espaces de Hilbert »), p. 159-164

Annexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Cours d'analyse — Jacques Harthong

Source : https://fr.wikipedia.org/wiki/Espace_de_Hilbert

12/06/2015

Rapport sur l'Impact Socio-Economique des Mathématiques en France

Etude sur l'Impact Socio-Economique des Mathématiques en France

Téléchargement des fichiers

Les articles et interviews consacrés à cette étude sont inventoriés ici.

Source :

http://www.agence-maths-entreprises.fr/a/

11/06/2015

Calculateur de dérivées

http://www.formaltools.com/derivativecalculator.php

16/03/2015

Faire des objets géométriques en papier

"Un ordinateur, une imprimante, du carton, des feuilles de papier, des ciseaux et de la colle. C'est tout ce qu'il faut pour passer du virtuel au monde réel, en réalisant les maquettes en 3D tactile Visual Kit"

http://www.visualkit.com/index.php?ulg=fr

14/02/2015

Calculs de triplets pythagoriciens

"Ce module propose de calculer des triplets pythagoriciens par plusieurs méthodes.

Les algorithmes de ce module ont été programmés par Joan, élève de 3ème au collège Longchamp à Marseille.
Si vous programmez d'autres algorithmes (dans un langage de programmation quelconque) et que vous souhaitez les faire figurer dans ce module, n'hésitez pas à les envoyer à l'adresse de l'auteur)."

Accéder au site :

http://wims.unice.fr/wims/fr_H4~number~triplPythag.fr.html

Mathématique

Cours, définitions, Vidéos, théorèmes, exercices, corrigés, livres sur les mathématiques, Livres Rares, Livres anciens de mathématiques

Recherchez sur le site (cours, livres, Agregation, etc.)

Liens utiles

Rechercher

CODE PROMO

Liens mathématiques divers

Livres en pdf

Cours

Documents Mathématiques

Avril 2024

Notes récentes

Archives

Catégories

Derniers weblogs mis à jour

Commentaires récents

Liens Sites Amis

21/11/2015

A Ramsey Problem on Hypercubes

A Ramsey Problem on Hypercubes

Peter Cameron (mathématicien)

Peter Cameron (mathématicien)

Sommaire

Œuvre[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Distinctions[modifier | modifier le code]

Notes et références[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Conjecture de Cameron-Erdős

Conjecture de Cameron-Erdős

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

Conjecture d'Erdős

Conjecture d'Erdős

Sommaire

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Conjecture d'Erdős-Graham

Conjecture d'Erdős-Graham

Notes et références[modifier | modifier le code]

Article connexe[modifier | modifier le code]