Théorème de Folkman

Soit (N₁, N₂, … , N_k) 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 à N_i[1].

Le 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

${\displaystyle x_{T}=\sum _{i\in T}x_{\{i\}},}$

où T parcourt les parties non vides de l'ensemble {1, 2, … , m}[1].

On 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] ?

Richard Rado et Jon Sanders avaient démontré des variantes du théorème de Folkman [1]^,[2]^,[3].

• Portail des mathématiques