Théorème de Folkman
Le théorème de Folkman est un théorème en théorie combinatoire des nombres et théorie de Ramsey selon lequel, pour toute partition finie de l'ensemble des entiers strictement positifs, il existe un ensemble arbitrairement grand d'entiers dont toutes les sommes partielles appartiennent à la même partie de la partition[1]. Découvert et démontré indépendamment par plusieurs mathématiciens[2],[3], il a été baptisé « théorème de Folkman » (en mémoire de Jon Folkman (en)) par Graham, Rothschild et Spencer[1].
Énoncé
modifierSoit (N1, N2, … , Nk) une partition finie de l'ensemble {1, 2, 3, … }. Pour tout entier m > 0, il existe un ensemble S de m entiers et un indice i tels que pour toute partie non vide T de S, la somme des éléments de T appartienne à Ni[1].
Liens avec les théorèmes de Schur et de Rado
modifierLe théorème de Schur est le cas m = 2 du théorème de Folkman.
Le théorème de Rado porte lui aussi sur les partitions finies de l'ensemble {1, 2, 3, … } : il caractérise les matrices A à coefficients entiers pour lesquelles, quelle que soit la partition choisie, le système d'équations linéaires Ax = 0 a toujours une solution x dont toutes les coordonnées sont dans une même partie de la partition. Le théorème de Folkman en est le cas particulier correspondant aux systèmes
où T parcourt les parties non vides de l'ensemble {1, 2, … , m}[1].
Version multiplicative
modifierOn peut remplacer l'addition par la multiplication dans le théorème de Folkman : pour toute partition finie de {1, 2, 3, … }, il existe un ensemble arbitrairement grand S d'entiers tel que tous les produits de parties non vides de S soient dans une même partie de la partition. Il suffit en effet de choisir un S constitué uniquement de puissances de 2 pour se ramener à la version additive du théorème de Folkman. Cependant, on ne sait pas si les deux versions (additive et multiplicative) peuvent toujours être réalisées par un même S. On ne le sait même pas pour m = 2 : existe-t-il, quelle que soit la partition choisie, un ensemble de la forme {x, y, x + y, xy} inclus dans une même partie de cette partition[1] ?
Résultats antérieurs
modifierRichard Rado et Jon Sanders avaient démontré des variantes du théorème de Folkman [1],[2],[3].
Notes et références
modifier- (en) Ronald L. Graham, Bruce L. Rothschild et Joel H. Spencer, Ramsey Theory, Wiley-Interscience, , chap. 3.4 (« Finite sums and finite unions (Folkman's theorem) »), p. 65-69
- (en) R. Rado, « Some partition theorems », dans Combinatorial theory and its applications, III: Proc. Colloq., Balatonfüred, 1969, North-Holland, , p. 929-936
- (en) Jon Henry Sanders, A generalization of Schur's theorem, Yale University, coll. « Ph.D. thesis »,