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	31

21/11/2015

Lemme de Higman

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques, le lemme de Higman est un résultat de la théorie des ordres qui affirme que, pour un ensemble $X$ muni d'un bel ordre, l'ensemble $X^*$ des mots finis sur $X$ muni de l'ordre sous-mot est également un bel ordre. C'est un cas particulier du théorème de Kruskal sur les arbres, qui se généralise à son tour en le théorème de Robertson-Seymour sur les graphes.

Ce lemme est dû à Graham Higman qui l'a publié en 1952¹.

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

↑ (Higman 1952)

Bibliographie[modifier | modifier le code]

Graham Higman, « Ordering by divisibility in abstract algebras », Proceedings of the London Mathematical Society, vol. 2, n^o 7,‎ 1952, p. 326-336 (DOI 10.1112/plms/s3-2.1.326)

Lien externe[modifier | modifier le code]

Notes sur les beaux ordres de Bastien Legloannec.

Portail des mathématiques

Catégories :

| [+]

Théorème de Kruskal

Pour l’article homonyme, voir Théorème de Kruskal-Katona.

En mathématiques, le théorème des arbres de Kruskal est un résultat de théorie des graphes conjecturé en 1937 par Andrew Vázsonyi (en) et démontré indépendamment en 1960 par Joseph Kruskal et S. Tarkowski¹, affirmant que l'ensemble des arbres étiquetés par un ensemble muni d'un bel ordre est lui-même muni d'un bel ordre. Ce théorème est un cas particulier du théorème de Robertson-Seymour, dont il a constitué une des motivations.

En utilisant ce théorème, Harvey Friedman a pu définir des entiers « incompréhensiblement grands »², qu'il a utilisé pour obtenir des résultats nouveaux d'indécidabilité.

Sommaire

[masquer]

Définitions préliminaires[modifier | modifier le code]

Articles détaillés : arbre (théorie des graphes), arbre (mathématiques) et bel ordre.

En théorie des graphes, un arbre est un graphe non orienté, acyclique et connexe ; on obtient un arbre enraciné en fixant l'un des sommets, qu'on appelle la racine de l'arbre. Enthéorie des ensembles, on définit une autre notion d'arbre, à partir d'une relation symétrique ; on démontre³ que, dans le cas fini, ces deux notions coïncident, et que tout arbre enraciné correspond à un ordre partiel unique défini sur l'ensemble des sommets, tel que tout sommet admette un unique prédécesseur⁴, sauf la racine, qui n'en a aucun (les arêtes du graphe étant exactement celles reliant chaque sommet à son prédécesseur) ; c'est cette représentation qui va servir à définir les applications qui font l'objet du théorème de Kruskal.

On dit qu'un arbre est étiqueté par un ensemble d'étiquettes X si on a défini une application x de l'ensemble des sommets de l'arbre vers X, autrement dit si on attache au sommet s l'étiquette x(s).

On dit qu'une application f entre ensembles partiellement ordonnés finis respecte les minorants si a= inf (b, c) entraîne f(a)= inf (f(b), f (c)), où inf(x, y) =z désigne la borne inférieure de x et y, c'est-à-dire le plus grand élément qui soit ≤ à x et à y ; on voit aisément que cela implique que f est strictement croissante, autrement dit que a<b entraînef(a)<f(b) et que f est une injection. Pour des arbres étiquetés par un ensemble X lui-même muni d'un ordre partiel noté ≤, on définit une notion de morphisme : une application fest un morphisme si elle respecte les minorants, et si elle respecte l'ordre des étiquettes, autrement dit si, pour tout sommet s du premier arbre, on a $scriptstyle x(s)le x(f(s))$ . La relation « il existe un morphisme de A vers B » est une relation d'ordre partiel sur l'ensemble des arbres étiquetés, considérés à isomorphisme près⁵ (si l'on ne considère pas les arbres isomorphes comme identiques, la relation n'est plus antisymétrique, et on obtient seulement un préordre⁶) ; pour des arbres non étiquetés, on démontre que s'il existe un morphisme entre A et B, A est un mineur topologique de B.

Un ordre partiel (ou même un préordre) est appelé un bel ordre s'il ne contient aucune suite infinie strictement décroissante, ni aucune antichaîne infinie (définition qui généralise aux ordres partiels la notion de bon ordre définie pour les ensembles totalement ordonnés) ; c'est équivalent à dire que dans toute suite infinie d'éléments de l'ensemble $x_1,x_2,dots,x_n,dots$ , il existe deux éléments $x_i$ et $x_j$ tels que $i<j$ et $x_ile x_j$ .

Énoncé[modifier | modifier le code]

Ces définitions permettent de formuler rigoureusement⁷ le

Théorème de Kruskal — Soit S un ensemble d'arbres étiquetés par un ensemble X d'étiquettes muni d'un bel ordre. La relation de préordre sur S : « $scriptstyle Ale B$ si et seulement si il existe un morphisme de A vers B », est alors également un bel ordre.

L'existence d'une suite infinie strictement décroissante étant évidemment impossible (puisque, si A ≤ B et si A n'est pas isomorphe à B, A contient moins d'arêtes que B, ou des étiquettes plus petites), ce théorème revient donc à affirmer qu'il n'y a pas d'antichaînes infinies, c'est-à-dire d'ensemble infini d'arbres deux à deux incomparables par la relation ≤ (il convient cependant de remarquer qu'il existe des antichaînes finies aussi grandes que l'on veut).

Cas particuliers et généralisation[modifier | modifier le code]

Le lemme de Higman est un cas particulier de ce théorème, dont il existe de nombreuses généralisations, pour des arbres munis d'un plongement dans le plan, des arbres infinis, etc. Une généralisation bien plus puissante, concernant les graphes quelconques, est donnée par le théorème de Robertson-Seymour.

Les résultats d'indécidabilité de Friedman[modifier | modifier le code]

Harvey Friedman a remarqué⁸ que certains cas particuliers du théorème de Kruskal peuvent être énoncés dans l'arithmétique du premier ordre (la logique du premier ordrecorrespondant aux axiomes de Peano), mais que cette théorie est trop faible pour les démontrer, alors qu'ils se démontrent aisément en utilisant l'arithmétique du second ordre (en). Un exemple analogue est donné par le théorème de Goodstein, mais pour démontrer les énoncés de Friedman, une portion significativement plus grande de l'arithmétique du second ordre doit être utilisée⁹.

Soit P(n) l'affirmation

Il existe un m tel que si T₁,...,T_m est une suite finie d'arbres (non étiquetés), avec T_k ayant (pout tout k) k+n sommets, alors il existe un couple (i,j) tel que i < j et T_i ≤ T_j.

Cette affirmation est un cas particulier du théorème de Kruskal, où la taille du premier arbre est fixée, et où la taille des arbres croît au plus petit rythme possible ; on dit souvent qu'il s'agit d'une forme finie du théorème de Kruskal.

Pour chaque n, les axiomes de Peano permettent de démontrer P(n), mais ces axiomes ne permettent pas de démontrer que « P(n) est vrai quel que soit n »¹⁰. De plus, la plus courte démonstration de P(n) a une longueur grandissant extrêmement vite en fonction de n, beaucoup plus vite que les fonctions récursives primitives ou que la fonction d'Ackermann par exemple.

Friedman a également utilisé la forme finie suivante du théorème de Kruskal pour les arbres étiquetés (avec des étiquettes non ordonnées), forme paramétrée, cette fois, par le nombre d'étiquettes :

Pour tout n, il existe un m tel que si T₁,...,T_m est une suite finie d'arbres dont les sommets sont étiquetés parn symboles, chaque T_i ayant au plus i sommets, alors il existe un couple (i,j) tel que i < j et T_i ≤ T_j.

Dans ce cas, la relation ≤ signifie qu'il existe une application préservant les minorants, et envoyant chaque sommet sur un sommet ayant la même étiquette ; en théorie des graphes, ces applications sont souvent appelées des plongements.

Ce dernier théorème affirme l'existence d'une fonction à croissance rapide, que Friedman a nommée TREE, telle que TREE(n) est la longueur de la plus longue suite d'arbres àn étiquettes T₁, ..., T_m dans laquelle chaque T_i a au plus i sommets, et telle qu'aucun arbre n'est plongeable dans un arbre ultérieur.

Les premières valeurs de TREE sont TREE(1) = 1, TREE(2) = 3, mais soudain TREE(3) explose à une valeur si gigantesque que la plupart des autres « grandes » constantes combinatoires, comme le nombre de Graham, sont ridiculement petites en comparaison. Ainsi, Friedman a défini (pour un autre problème plus simple) une famille de constantesn(k), et a montré que n(4) était beaucoup plus petit que TREE(3)². Or n(4) est minoré par A(A(...A(1)...)), où le nombre de A est A(187196), A() étant une variante de la fonction d'Ackermann définie par : A(x) = 2↑↑...↑x avec un nombre de flèches de Knuth ↑ égal à x-1. À titre de comparaison, le nombre de Graham est de l'ordre de A⁶⁴(4) ; pour mieux voir à quel point ce nombre est petit par rapport à A^A(187196)(1), se reporter à l'article Hiérarchie de croissance rapide. Plus précisément, dans les notations de cette hiérarchie, on peut montrer que la vitesse de croissance de la fonction TREE est supérieure à celle de f_Γ₀, où Γ₀ est l'ordinal de Feferman-Schütte, ce qui montre au passage à quel point cette fonction croît plus vite que la fonction de Goodstein, qui ne croît que comme f_ε₀.

Tous ces résultats ont pour conséquence que les théorèmes précédents (tels que le fait que TREE soit une application, c'est-à-dire soit définie pour tout n) ne peuvent être démontrés que dans des théories assez fortes¹¹ ; plus précisément, la force d'une théorie est mesurée par un ordinal (celui de l'arithmétique de Peano, par exemple, étant ε₀), et des théorèmes ayant pour conséquence l'existence de fonctions croissant trop vite (plus rapidement que f_ε₀ dans le cas des axiomes de Peano) ne peuvent être démontrés dans ces théories. Comme leur négation ne peut évidemment pas y être démontrée non plus (en supposant que la théorie où l'on a démontré ces théorèmes est cohérente), il en résulte que, par exemple dans l'arithmétique du premier ordre, ces théorèmes sont indécidables, ce qui a d'importantes conséquences métamathématiques, ces formes d'indécidabilité étant ressenties comme beaucoup plus naturelles que celles correspondant au théorème de Gödel¹¹.

L'ordinal qui mesure la force du théorème de Kruskal est le petit ordinal de Veblen (en) (lequel est beaucoup plus grand que Γ₀)¹² ; il en résulte que l'on peut, par des constructions analogues à celles de Friedman, obtenir grâce à ce théorème des fonctions croissant plus vite que toute f_α de la hiérarchie de croissance rapide, où α est un ordinal plus petit que l'ordinal de Veblen.

Notes[modifier | modifier le code]

↑ Kruskal 1960 ; une preuve courte en fut obtenue par Crispin Nash-Williams trois ans plus tard (Nash-Williams 1963)
↑ ^{a et b} Friedman décrit ces entiers comme « incompréhensiblement grands » ; n(p) reste cependant plus petit que TREE(3), même pour des valeurs énormes de p, telles que le nombre de Graham ; on trouvera une analyse plus serrée de ces encadrements dans ces notes de conférence [archive] (en), et des calculs plus précis des premières valeurs de n(k) dans cet autre article de Friedman [archive] (en) ; enfin, une estimation déjà moins imparfaite de TREE(3) figure sur cette page [archive] de MathOverflow.
↑ C. Berge, Graphes et hypergraphes, chapitre 3
↑ On dit que a est un prédécesseur de b (pour la relation d'ordre partiel <) si a<b et s'il n'existe aucun c tel que a<c<b.
↑ Elle est en effet réflexive (en utilisant le morphisme identité), et transitive (en composant les morphismes) ; de plus, s'il existe des morphismes de A vers B et de B vers A, A et B sont isomorphes.
↑ Voir par exemple N. Bourbaki, Éléments de mathématique : Théorie des ensembles [détail des éditions], ch. III, § 1, n° 2, p. 3, pour les définitions et les premières propriétés des ordres partiels. p. 3 pour les définitions et les premières propriétés des ordres partiels et des préordres
↑ On trouvera une présentation plus formalisée encore dans l'exposé de Jean Gallier [archive] (en anglais), dont cette section est largement inspirée ; toutefois, il réécrit la présentation initiale des théorèmes dans le langage des tree domains, ce qui peut demander un certain effort au lecteur non spécialiste...
↑ Friedman 2002
↑ En terme d'ordinaux, le théorème de Goodstein demande une récurrence jusqu'à l'ordinal $varepsilon_0$ , alors que la fonctionTREE demande au moins l'ordinal de Feferman-Schütte, comme exposé plus loin.
↑ Voir l'article ω-cohérence (en) pour plus de détails sur d'autres situations de ce type.
↑ ^{a et b} Voir, par exemple, les analyses de Gallier 1991.
↑ On trouvera une description constructive de cet ordinal, sous forme d'un bon ordre explicite entre arbres finis, dans cet article de H. R. Jervell [archive] (en) (des dessins beaucoup plus nombreux d'arbres, avec les ordinaux correspondants, figurent dans ce document écrit par David Madore [archive] (en) [PDF]), et une démonstration du résultat lui-même dans cet article de Rathjen et Weiermann [archive]

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é « Kruskal's tree theorem » (voir la liste des auteurs).
Un exposé rigoureux de Bastien Legloannec, en français (contenant également une démonstration du théorème de Kruskal dans le cas des arbres non étiquetés, une présentation du théorème de Robertson-Seymour, et beaucoup d'exemples et de contre-exemples)

(en) Harvey Friedman, Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998), Urbana, IL, ASL, coll. « Lect. Notes Log. » (n^o 15),‎ 2002, p. 60-91

(en) Jean H. Gallier, « What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory », Ann. Pure Appl. Logic, vol. 53, n^o 3,‎ 1991,p. 199-260 lien Math Reviews (texte intégral sous forme de trois documents PDF : partie 1 partie 2 partie 3).

(en) J. B. Kruskal, « Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture », Trans. Amer. Math. Soc., vol. 95, n^o 2,‎ mai 1960, p. 210-225 (DOI 10.2307/1993287)

(en) C. St.J. A. Nash-Williams, « On well-quasi-ordering finite trees », Math. Proc. Cambridge Phil. Soc., vol. 59, n^o 04,‎ 1963, p. 833-835 (DOI 10.1017/S0305004100003844)

(en) Stephen Simpson, « Nonprovability of certain combinatorial properties of finite trees », dans Harvey Friedman's Research on the Foundations of Mathematics, North-Holland, coll. « Studies in Logic and the Foundations of Mathematics »,‎ 1985, p. 87-117

Voir aussi[modifier | modifier le code]

The Cameron–Erd˝os Conjecture Ben Green1 Abstract

Voir le pdf : http://arxiv.org/pdf/math/0304058.pdf

arXiv:math/0304058v1 [math.NT] 4 Apr 2003 The Cameron–Erd˝os Conjecture Ben Green1 Abstract A subset A of the integers is said to be sum-free if there do not exist elements x,y,z ∈ A with x+y = z. It is shown that the number of sum-free subsets of {1,... ,N} is O(2N/2 ), confirming a well-known conjecture of Cameron and Erd˝os. 1. Introduction. If A is any subset of an abelian group then we say that A is sum-free if (A + A) ∩ A = ∅, that is if there do not exist x, y, z ∈ A for which x + y = z. The study of such sets goes back at least 30 years, and over 10 years ago Cameron and Erd˝os [4, 5] raised the question of enumerating the sum-free subsets of [N] = {1, . . . , N}. They noted that any set of odd integers is sum-free, as is any subset of {⌈N/2⌉, . . . , N}, but that it is hard to think of many sum-free sets which are not essentially of this form. Thus they advanced the following conjecture. Conjecture 1 (Cameron–Erd˝os) The number of sum-free subsets of [N] is O(2N/2 ). There has been some progress on this conjecture. Writing SF(N) for the collection of sum-free subsets of [N], Alon [1], Calkin [2] and Erd˝os and Granville (unpublished) showed independently that |SF(N)| = 2N/2+o(N) . (1) Results in a rather different direction were obtained by Freiman [7] and by Deshouillers, Freiman, S´os and Temkin [6]. In [7], for example, it was shown that the number of sum-free subsets of [N] with cardinality at least 5N/12 + 2 is at most O(2N/2 ). Let us also mention that Calkin and Taylor [3] showed that the number of subsets of [N] containing no solutions to x + y + z = w is O(22N/3 ), an estimate which is basically sharp. It is natural to ask for estimates for SF(Γ), the number of sum-free subsets of some finite abelian group Γ. When Γ = Z/pZ (p prime) this question is perhaps even more natural than the question of Cameron and Erd˝os. It was first considered explicitly by Lev and Schoen [12], who showed that |SF(Z/pZ)| ≤ 2 0.498p . Their result was improved by Ruzsa and the author [9], who obtained the estimate |SF(Z/pZ)| ≤ 2 p/3+o(p) . This is tight except for the o(p) term. For more general abelian groups Γ, work started by Lev, Luczak and Schoen [11] in the case |Γ| even was continued by Ruzsa and the author 1Supported by a Fellowship of Trinity College, Cambridge and a grant from the EPSRC, United Kingdom. Mathematics Subject Classification: 11B75. 1 [10], who obtained reasonably precise estimates for all abelian groups. The objective of the present paper is to prove the conjecture of Cameron and Erd˝os. Theorem 2 The number of sum-free subsets of [N] is asymptotically c(N)2N/2 , where c(N) takes two different constant values according as N is odd or even. It is extremely likely that our methods extend to give, for example, much tighter bounds on |SF(Z/pZ)| but we do not pursue such matters here. 2. A strategy for counting sum-free sets. The purpose of this section is to outline the broad strategy that we will use to count sum-free subsets of [N]. Our method falls conveniently into two parts, which are dealt with in detail in the two sections immediately following this one. We have tried to make these sections as independent as possible. Our strategy, then, is as follows. Part I. We find some family F of subsets of [N] with the following properties. Firstly, each A ∈ F is almost sum-free, meaning that the number of additive triples (triples with x+y = z) in A is o(N2 ). Secondly, F does not contain too many sets; in fact, |F| = 2o(N) . Finally, every sum-free subset of [N] is contained in some member of F. Part II. Given A ∈ SF(N), we consider some set A′ ∈ F with A ⊆ A′ . As F is so small, the number of A for which |A′ | ≤ 1 2 − 1 120 N is o(2N/2 ). If, however, |A′ | ≥ 1 2 − 1 120 N then it is possible to say something about the structure of A ′ , and hence about the structure of almost all A ∈ SF(N). What we will actually show is that almost all A ∈ SF(N) consist either entirely of odd numbers, or else are contained in the interval {⌈(N+1)/3⌉, . . . , N}. The author was delighted to discover that, in their original paper [4], Cameron and Erd˝os gave an elegant argument leading to an estimate for the number of sum-free subsets of {⌈(N + 1)/3⌉, . . . , N}. This argument, together with our work in the present paper, constitutes an affirmative solution to Conjecture 1. 3. Construction of F. Granularizations. In this section we complete Part I of the program outlined in §2 by constructing the family F. This was basically achieved in the paper of Ruzsa and the author [9]. Since it is not quite a trivial matter to isolate results from that paper in the form that we need them, we repeat some of the material from [9] here. We begin with a small amount of notation concerning Fourier transforms. We will be working on the group G = Z/pZ, where p is a prime. If f : G → C is a function and if r ∈ G then we define the Fourier transform ˆf by ˆf(r) = X x∈G f(x)e(rx/p) 2 where, as usual, e(θ) = e 2πiθ. If f, g are two functions then we define their convolution f ∗ g by (f ∗ g)(x) = X y∈G f(y)g(x − y). Observe that (f ∗ g)ˆ(r) = ˆf(r)ˆg(r). Finally, we remark that if A ⊆ G then we will identify A with its characteristic function: that is, we write A(x) = 1 if x ∈ A and A(x) = 0 otherwise. Observe that if A, B ⊆ G are two sets then (A ∗ B)(x) is the number of representations of x as a + b with a ∈ A, b ∈ B. Let p ∈ [2N, 4N] be a prime, let M be a positive integer, and let d ∈ (Z/pZ) ∗ . Let A ⊆ [N] be a set, and regard A as a subset of Z/pZ in the obvious manner. Suppose that |A| = αp. Consider a partition of Z/pZ into arithmetic progressions Ii , i ∈ Z/MZ, of common difference d defined by Ii = ( λd : ip M ≤ λ < (i + 1)p M ) , (2) where i denotes the least positive residue of i. Each of these progressions has length either L or L − 1, where L = ⌈p/M⌉. Let ǫ1 > 0 be a real number, and let T = {i ∈ Z/MZ | |A ∩ Ii | ≥ ǫ1|Ii |}. Finally, define the granularization A′ of A (with respect to the length d and the parameter ǫ1) by A ′ = [ i∈T Ii . It is easy to see that we have |A ′ A| ≤ ǫ1p. (3) One of the key results of [9] is that, provided d has a certain property (for which we will use the term “good length”) the set A′ retains some of the additive features of A. In fact, we will be able to show that A′ is almost sum-free. Let us now say what we mean by the statement “d is a good length”. Let ǫ2, ǫ3 > 0 be two further real numbers and set δ = 1 16 ǫ 2 1 ǫ2ǫ 1/2 3 α −1/2 . Let R, |R| = k, be the set of all r 6= 0 for which |Aˆ(r)| ≥ δp. We say that d is a good length for A (with respect to the parameters ǫ1, ǫ2, ǫ3) if kdr/pk ≤ 1 4L δp |Aˆ(r)| !1/2 (4) for all r ∈ R. The following proposition was (essentially) the main result of [9]. It clarifies the rˆole of ǫ2 and ǫ3, which have not so far featured. 3 Proposition 3 Suppose that d is a good length for A. Then the granularization A′ has the property that A + A contains all x for which A′ ∗ A′ (x) ≥ ǫ2p, with at most ǫ3p exceptions. Proof. We claim that if d is a good length then the function g(x) = 1 2L − 1 X L−1 j=−(L−1) e(jdx/p) (5) satisfies |Aˆ(x)||1 − g(x) 2 | ≤ δp (6) for all x. This automatically holds for x = 0, as g(x) = 1, and also whenever |Aˆ(x)| ≤ δp, since g(x) ∈ [−1, 1]. For any x ∈ Z/pZ we may estimate 1 − g(x) as follows. Writing ktk for the distance of t from the nearest integer we have the inequality 1 − cos 2πt ≤ 2π 2ktk 2 . It follows that 1 − g(x) = 2 2L − 1 X L−1 j=1 1 − cos 2πjdx p ≤ 4π 2 2L − 1 X L−1 j=1 jdx p 2 ≤ 4π 2 2L − 1 dx p 2 X L−1 j=1 j 2 ≤ 2π 2L 2 3 dx p 2 . (7) Hence |Aˆ(x)||1 − g(x) 2 | ≤ 2|Aˆ(x)||1 − g(x)| ≤ 14L 2 kdx/pk 2 |Aˆ(x)| It is now easy to see that d being a good length is exactly the property required to make (6) hold. Now to establish the proposition we define a function a1 by a1(n) = 1 |P| (A ∗ P)(n) = 1 |P| |A ∩ (P + n)|, where P = {−(L − 1)d, . . . , 0, d, 2d, . . . ,(L − 1)d}. Observe that ˆa1(x) = Aˆ(x)g(x). Thus we 4 have, by two applications of Parseval’s identity, that X n |(A ∗ A)(n) − (a1 ∗ a1)(n)| 2 = p −1X x Aˆ(x) 2 − aˆ1(x) 2 2 = p −1X x |Aˆ(x)| 4 1 − g(x) 2 2 ≤ p −1 sup x |Aˆ(x)||1 − g(x) 2 | 2 X x |Aˆ(x)| 2 = αp sup x |Aˆ(x)||1 − g(x) 2 | 2 . (8) (6) therefore implies that X n |(A ∗ A)(n) − (a1 ∗ a1)(n)| 2 ≤ αδ2 p 3 . (9) Now if n ∈ A′ then there is a progression of common difference d and length L containing n which contains at least ǫ1L/2 points of A. This progression is contained in [n − (L − 1)d, . . . , n + (L − 1)d]. Hence a1(n) is certainly at least ǫ1/4, and so a1(n) ≥ ǫ1A(n)/4 for all values of n. It follows immediately that (a1 ∗ a1)(n) ≥ ǫ 2 1 (A′ ∗ A′ )(n)/16 for all n, and hence that if A′ ∗ A′ (n) ≥ ǫ2p then a1 ∗ a1(n) ≥ ǫ 2 1 ǫ2p/16. We are to show that there are not many points n for which this is true whilst A ∗ A(n) = 0. Letting B denote the set of these “bad” points, observe that n ∈ B implies that |(A ∗ A)(n) − (a1 ∗ a1)(n)| 2 ≥ ǫ 4 1 ǫ 2 2p 2 256 . Substituting into (9) gives the bound |B| ≤ 256αδ2 ǫ 4 1 ǫ 2 2 p ≤ ǫ3p (this explains our choice of δ). We defer for a while the issue of whether there are any good lengths. Our next result says that the conclusion of Proposition 3 is enough to guarantee that if A is sum-free then A′ is almost sum-free. Proposition 4 Suppose that A is sum-free. Let ǫ > 0, set ǫ1 = ǫ, ǫ2 = ǫ 2 /144, ǫ3 = ǫ 2 /80 and let A′ be the granularization of A with respect to some good length d. Then A′ contains at most ǫp2 triples (x, y, z) with x + y = z. 5 Proof. The choice of p (that is, p ≥ 2N) guarantees that A is sum-free when considered as a subset of Z/pZ. Suppose without loss of generality that d = 1, and suppose for a contradiction that the proposition is false. Recall the notation we set up at the start of the section, particularly the definitions of the intervals Ii and the set T ⊆ Z/mZ. We begin by claiming that there are at least ǫM2/4 triples (i, j, k) ∈ T 3 for which i + j = k or k + 1. Indeed note that if x+y = z and if x ∈ Ii , y ∈ Ij and z ∈ Ik then i+j = k or k +1. However for a fixed triple (i, j, k) with this property there are at most 4p 2/M2 triples (x, y, z), so our claim follows from a simple double count. For definiteness suppose that there are at least ǫM2/8 triples (i, j, k) ∈ T 3 with i + j = k (the argument when there are many triples with i + j = k + 1 is very similar). Let K be the set of all k ∈ T for which T ∗ T(k) ≥ ǫM/16 so that, by an easy averaging argument, we have |K| ≥ ǫM/16. Suppose that i + j = k with i, j, k ∈ T, and suppose that z lies in the middle (1 − ǫ/2) of Ik. Then the number of representations of z as x + y with x ∈ Ii , y ∈ Ij is at least ǫp/8M. Therefore if k ∈ K we have A′ ∗A′ (z) ≥ ǫ 2p/144. Note, however, that since k ∈ T the middle (1 − ǫ/2) of Ik contains at least ǫp/4M points of A. We have now shown that there are at least ǫ 2 p/64 elements x ∈ A for which A ′ ∗ A ′ (x) ≥ ǫ 2p/144. By the property of A′ described in Proposition 3 we see that A + A contains an element of A, contrary to our assumption that A is sum-free. We now look at the issue of finding a good length. Proposition 5 Let A ⊆ Z/pZ have cardinality αp. A good length for A with parameters ǫ1, ǫ2, ǫ3 exists if p > (4L) 256α 2 ǫ −4 1 ǫ −2 2 ǫ −1 3 . (10) Proof. It follows by a standard application of the pigeonhole principle that a d satisfying (4) exists if p > (4L) k Y r∈R |Aˆ(r)| δp !1/2 . (11) We claim that this inequality is a consequence of the hypothesis on p, L, ǫ1, ǫ2 and ǫ3 in the statement of the proposition. Indeed, observe that Parseval’s identity implies that X r∈R |Aˆ(r)| 2 ≤ αp2 , (12) from which the arithmetic-geometric mean inequality gives Y r∈R |Aˆ(r)| ≤ αp2 k k/2 . It follows that the right side of (11) is at most (4Lα1/4 δ −1/2 k −1/4 ) k , (13) 6 which is an increasing function of k in the range k < 256L4 e α δ 2 . However another consequence of (12) is the inequality k < α/δ2 , and hence (13) is itself bounded above by (4L) α/δ2 . Recalling our choice of δ confirms the claim, and hence there is a d for which (4) holds. To get the conclusion of Proposition 4 we required ǫ1 = ǫ, ǫ2 = ǫ 2 /144 and ǫ3 = ǫ 2 /80. It is an easy but slightly tedious task to check that if we put ǫ = (log N) −1/11 and M = N exp(−(log N) 1/12) then, at least for N sufficiently large, A has at least one good length. For the remainder of the section we assume that the parameters ǫ and M take these values. We are now in a position to define our family of sets F. Take F to consist of all sets which can be formed in the following manner. For all d ∈ (Z/pZ) ∗ consider the decomposition (2) of Z/pZ into progressions Ii (i ∈ Z/mZ) with common difference d. Let G be the collection of sets which are unions of progressions Ii , for some d. Now throw away from G all those sets which have more than ǫp2 additive triples, giving a new collection H. Finally, let F consist of all subsets of [N] which can be obtained by adding at most ǫp elements to some H ∩ [N], H ∈ H. This may seem complicated. It turns out, however, that we can rather easily establish the following rather clean proposition concerning F which contains all the information we need for subsequent sections. Proposition 6 The family F has the following properties: (i) Every member of F has at most o(N2 ) additive triples; (ii) If A is sum-free then A is contained in some member of F; (iii) |F| ≤ 2 o(N) . Proof. (i) By definition every set in H has at most ǫp2 additive triples, and thus the same is true of sets of the form H ∩ [N], H ∈ H. By adding ǫp elements to such an H, we cannot create more than 3ǫp2 new additive triples. The result follows from the fact that p ≤ 4N. (ii) Set ǫ1 = ǫ, ǫ2 = ǫ 2/144 and ǫ3 = ǫ 2/80. Choose a good length d for A with respect to ǫ1, ǫ2, ǫ3, and consider the granularization A′ with respect to d and ǫ1. By Proposition 4 this lies in H, and the result follows from (3). (iii) There are p −1 choices for d, and then 2M ways to pick elements of G. Thus |H| ≤ p2 M, and so |F| is at most p2 M times the number of subsets of [N] of size at most ǫN. This is clearly 2o(N) . 4. The structure of almost sum-free sets. In this section we study large almost sumfree sets. The results may be regarded as “almost” versions of the results of Freiman [7]. Freiman’s methods do not seem to generalise easily to almost sum-free sets, so we have been forced to devise our own arguments. We will need one further piece of notation. If K is a positive real number and if A ⊆ G is a subset of an abelian group, we will write D(A, K) for the set of all x ∈ G which have at least K representations as a − a ′ with a, a′ ∈ A. We call 7 this the set of K-popular differences of A. In this section the objects Ii , M and ǫ are not the same as in the previous section. Proposition 7 Let ǫ = o(N) and suppose that A ⊆ [N] has at most ǫN2 additive triples, and that |A| = ( 1 2 − η)N where η ≤ 1/50 (η is allowed to be negative). Then one of the following alternatives occurs: (i) With the possible exception of at most 32ǫ 1/8N elements, A is contained in some interval of length ( 1 2 + 3η + 60ǫ 1/8 )N; (ii) At most 54ǫ 1/8N elements of A are even. Throughout what follows we shall assume that |A| = ( 1 2 − η)N, η ≤ 1/50 and that A has at most ǫN2 additive triples. Lemma 8 We have 1 2 |D(A, ǫ1/2N)| + |A| ≤ N(1 + 2ǫ 1/2 ). (14) Proof. We have D(A, ǫ1/2N) ∩ Z>0 ∩ A ≤ ǫ 1/2N, or else A would contain more than ǫN2 additive triples. The result follows quickly from this and the observation that d is K-popular if and only if −d is. Lemma 9 For all but at most 8ǫ 1/4N values of a, at least |A| − 16ǫ 1/4N of the differences a − a ′ with a ′ ∈ A lie in D(A, 32ǫ 1/2N). Proof. Consider the graph on vertex set A in which a is joined to a ′ if a − a ′ is not in D(A, 32ǫ 1/2N). It has at most 64ǫ 1/2N2 edges. The number of vertices with degree more than 16ǫ 1/4N is thus at most 8ǫ 1/4N. The next lemma, which is an application of basic graph theory, is [11], §4, Proposition 1. We specialise the result to the case we need. Lemma 10 (Lev, Luczak, Schoen) Let S be a subset of an abelian group Γ, |Γ| ≤ N. Suppose that |D(S, 8ǫ 1/2N)| ≤ 2|S| − 16ǫ 1/4N. Then there is a set X ⊆ S, |S X| ≤ 4ǫ 1/4N, with X − X ⊆ D(S, 8ǫ 1/2N). Now partition [N] into intervals Ii such that the smallest element of Ii is ⌊2iǫ1/8N⌋. Let j be minimal so that Ij contains at least 9ǫ 1/4N points of A. Then, by Lemma 9, there is some m ∈ Ii such that at least |A| − 16ǫ 1/4N of the differences a − m, a ∈ A, lie in D(A, 32ǫ 1/2N). Let k be maximal so that Ik contains at least 9ǫ 1/4N points of A. Again, there is M ∈ Ik so that at least |A| − 16ǫ 1/4N of the differences a − m, a ∈ A, lie in D(A, 32ǫ 1/2N). Clearly for at least |A| − 32ǫ 1/4N values of a both a − m and a − M are popular. Furthermore |A ∩ [1, m]| ≤ 9ǫ 1/4N ǫ 1/8 ≤ 9ǫ 1/8N, and a similar inequality holds for |A ∩[M, N]|. Thus there is a set B ⊆ A, with the following properties: 8 (i) B is contained in {m + 1, . . . , M}; (ii) |B| ≥ |A| − 50ǫ 1/8N; (iii) For all b ∈ B the differences b − m and b − M are both in D(A, 32ǫ 1/2N). Observe that the first and second of these points imply that M − m > N/4. Now let t = M − m. Following Lev and Smeliansky [13], consider the projection map π : Z → Z/tZ. We note some simple facts about this map in a lemma. Lemma 11 (i) |π(A)| ≥ |A| − 50ǫ 1/8N; (ii) Let δ > 0. If d ∈ D(A, 4δN) then π(d) ∈ D(π(A), δN); (iii) If d ∈ D(π(A), 8δN) then some element of π −1 (d) lies in D(A, δN). Proof. (i) Clearly |π(A)| ≥ |π(B)| = |B|. (ii) If d = a−a ′ then π(d) = π(a)−π(a ′ ). For different representations of d as a−a ′ , certain of these representations of π(d) may be the same. However, since t > N/4, no element of Z/tZ has more than 4 preimages under π which lie in A. The result follows. (iii) If π(d) = π(ai) − π(a ′ i ) then ai − a ′ i = d + λit for some λi ∈ Z. As t > N/4 and −N < ai − a ′ i < N there are at most 8 possible values for λi . Thus for at least one value of i there are δN solutions to ai − a ′ i = d + λit. It is immediate from part (iii) of this lemma that |D(A, δN)| ≥ |D(π(A), 8δN)|. However we can do better than this, since for several d at least two of the elements π −1 (d) are popular differences. Indeed, for any b ∈ B we have b−m, b−M ∈ D(A, 32ǫ 1/2N), but b−m ≡ b−M (mod t). Certainly π(b − m) ∈ D(π(A), 8ǫ 1/2N) by Lemma 11(ii). Thus, by Lemma 11(iii), we have |D(A, ǫ1/2N)| ≥ |D(π(A), 8ǫ 1/2N)| + |B| ≥ |D(π(A), 8ǫ 1/2N)| + |A| − 50ǫ 1/8N. (15) Combining this with (14) gives |D(π(A), 8ǫ 1/2N)| ≤ 2N(1 + 30ǫ 1/8 ) − 3|A|. (16) Now we must have |D(π(A), 8ǫ 1/2N)| ≤ 2|π(A)| − 16ǫ 1/4N, since otherwise (16) and Lemma 11(i) would give |A| ≤ ( 2 5 + 100ǫ 1/8 )N, which is contrary to our assumption about |A|. Thus Lemma 10 applies, and we may pass to a subset X ⊆ π(A) with |X| ≥ |A| − 54ǫ 1/8N (17) and X − X ⊆ D(π(A), 8ǫ 1/2N). (18) We distinguish three further cases. 9 Case 1. |X| ≥ t/2. Then X − X is all of Z/tZ, and so (16) and (18) yield t ≤ 1 2 + 3η + 60ǫ 1/8 N. (19) But we know that, with at most 18ǫ 1/8N exceptions, the elements of A lie in the interval {m + 1, . . . , M} which has length t. This is alternative (i) of Proposition 7. Case 2. |X − X| ≥ 2|X| − t/3. Then (16),(17) and (18) give |A| ≤ ( 7 15 + 40ǫ 1/8 )N, contrary to assumption. Case 3. |X − X| < 2|X| − t/3. Then, by Kneser’s theorem on the addition of sets in abelian groups (see [14], Theorem 4.2), X−X is a union of cosets of some subgroup H ≤ Z/tZ of index 2. Thus t is even and π −1 (X) consists of integers of just one parity. That is, either at least |A|−54ǫ 1/8N elements of A are odd, or else at least that many are even. The latter possibility is, however, easily excluded; any subset of {2, 4, 6, . . . , 2⌊N/2⌋} of cardinality at least 12N/25 contains at least N2/100 additive triples. This concludes the proof of Proposition 7. An immediate corollary of Propositions 6 and 7 is the following result of Alon [1], Calkin [2] and Erd˝os and Granville (unpublished). Proposition 12 (Alon,Calkin,Erd˝os–Granville) |SF(N)| = 2N/2+o(N) . Proof. It follows from Proposition 7 that if F ⊆ [N] has o(N2 ) triples then |F| ≤ ( 1 2+o(1))N. The result now follows from Proposition 6. A much more important corollary for us will be the following description of almost all sum-free subsets of [N]. Corollary 13 With o(2N/2 ) exceptions, all sum-free subsets of [N] consist entirely of odd numbers, or else are contained in {⌈(N + 1)/3⌉, . . . , N}. Proof. Let A ∈ SF(N), and let F ∈ F contain A. The number of A for which |F| ≤ 1 2 − 1 120 N is certainly o(2N/2 ), so suppose that |F| ≥ 1 2 − 1 120 N. Proposition 7 then applies. Suppose first of all that alternative (ii) of that proposition holds, so that A contains o(N) even numbers. Suppose that A contains at least one even number, t say. If t < N/2 then we may select ⌊N/8⌋ disjoint pairs (x, x + t) of odd numbers, and A cannot contain both of the elements of any of them since it is sum-free. The number of choices for A is thus no more than 2N/4+o(N) 3 N/8 = o(2N/2 ). If t ≥ N/2 then a very similar argument applies with pairs (x, t − x). Thus all but o(2N/2 ) of the sum-free sets with o(N) even numbers consist entirely of odd numbers. Now suppose that alternative (i) of Proposition 7 holds. If A ∩ 1 − 1 120 N, N ≤ 32ǫ 1/8N (20) 10 then, using the fact that A ∩ [1, 1 − 1 120 N] is sum-free together with Theorem 12, we see that there are just o(2N/2 ) possibilities for A. Suppose, then, that (20) fails to hold. Since Proposition 7, (i), holds we infer that A is contained in the interval [ 1 2 − 1 30 − 256ǫ 1/8 N, N] with the exception of at most 32ǫ 1/8N elements. Suppose that A contains some element t ∈ {1, . . . , ⌊(N + 1)/3⌋}. Then we may select ⌊N/12⌋ − 4 totally disjoint pairs (x, x + t) with x ≥ N/2, and A can contain at most one element from each of them. This means that the number of choices for A is no more than 3N/122 ( 1 3 + 1 30 +o(1))N which, it can be checked, is o(2N/2 ). As we remarked in the introduction, Cameron and Erd˝os [4] addressed the issue of counting sum-free subsets of {⌈(N + 1)/3⌉, . . . , N}. They discovered that the number of such sets is asymptotically c(N)2N/2 , where c(N) takes two different constant values depending on whether N is odd or even. Combining their result with the work of this paper, then, leads to Theorem 2. Concluding remarks. The paper [4] of Cameron and Erd˝os can be hard to locate and so we have written up their argument and posted it on the web [8]. The author would like to thank Imre Ruzsa for the many conversations which led to the papers [9, 10] and which, naturally, have had a significant bearing on the present work. References [1] Alon, N., Independent sets in regular graphs and sum-free subsets of abelian groups, Israel Jour. Math. 73 (1991) 247 – 256. [2] Calkin, N.J.,On the number of sum-free sets, Bull. London Math. Soc. 22 (1990), no. 2, 141–144. . [3] Calkin, N. J., Taylor, A. C. Counting sets of integers, no k of which sum to another, J. Number Theory 57 (1996), no. 2, 323–327. [4] Cameron, P.J; Erd˝os, P. On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), 61–79, de Gruyter, Berlin, 1990. [5] Cameron, P.J and Erd˝os, P. Notes on sum-free and related sets, Recent trends in combinatorics (M´atrah´aza, 1995), 95–107, CUP, Cambridge, 2001. [6] Deshouillers, J-M; Freiman, G. A; S´os, V; Temkin, M; On the structure of sum-free sets. II, Structure theory of set addition. Ast´erisque 258, (1999), xii, 149–161. [7] Freiman, G. A. On the structure and the number of sum-free sets, Journ´ees Arithm´etiques, 1991 (Geneva). Ast´erisque 209, (1992), 13, 195–201. 11 [8] Green, B.J. Notes on an argument of Cameron and Erd˝os, available at: http://www.dpmms.cam.ac.uk/˜bjg23/papers/ce.pdf. [9] Green, B.J. and Ruzsa, I.Z. Counting sumsets and sum-free sets in Z/pZ, preprint. [10] Green, B.J. and Ruzsa, I.Z. Counting sum-free sets in abelian groups, preprint. [11] Lev, V.F., Luczak, T. and Schoen, T. Sum-free sets in abelian groups, Israel Jour. Math. 125(2001) 347 – 367. [12] Lev, V.F. and Schoen, T. Cameron-Erd˝os modulo a prime, Finite Fields Appl. 8 (2002), no. 1, 108–119. [13] Lev, V. F. and Smeliansky, P. Y. On addition of two distinct sets of integers, Acta Arith. 70 (1995), no. 1, 85–91. [14] Nathanson, M.B. Additive number theory: inverse problems and the geometry of sumsets, Graduate Texts in Mathematics 165, Springer-Verlag, New York 1996. Ben Green Trinity College, Cambridge, England. email: bjg23@hermes.cam.ac.uk 12

The Book of Numbers Par John H. Conway,Richard Guy

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

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

Décembre 2024

Notes récentes

Archives

Catégories

Derniers weblogs mis à jour

Liens Sites Amis

21/11/2015

Lemme de Higman

Lemme de Higman

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

Bibliographie[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Théorème de Kruskal

Théorème de Kruskal

Sommaire

Définitions préliminaires[modifier | modifier le code]

Énoncé[modifier | modifier le code]

Cas particuliers et généralisation[modifier | modifier le code]

Les résultats d'indécidabilité de Friedman[modifier | modifier le code]

Notes[modifier | modifier le code]

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

Voir aussi[modifier | modifier le code]

The Cameron–Erd˝os Conjecture Ben Green1 Abstract

The Book of Numbers Par John H. Conway,Richard Guy

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]