Séminaire Delange-Pisot-Poitou.
Théorie des nombres

PAUL E RDÖS
Problèmes extrémaux et combinatoires en théorie des nombres
Séminaire Delange-Pisot-Poitou. Théorie des nombres, tome 17, no 2 (1975-1976),
exp. no G7, p. G 1-G 5.
<http://www.numdam.org/item?id=SDPP_1975-1976__17_2_A13_0>© Séminaire Delange-Pisot-Poitou. Théorie des nombres(Secrétariat mathématique, Paris), 1975-1976, tous droits réservés.
L’accès aux archives de la collection « Séminaire Delange-Pisot-Poitou. Théorie des nombres »implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php).
Toute utilisation commerciale ou impression systématique est constitutive d’une infraction
pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright.

Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/

G7-01

Séminaire DELANGE-PISOT-POITOU(Groupe d’études de Théorie des nombres)
17e année,

1er décembre 1976

1975/76, n° G7, 5 p.

PROBLÈMES EXTRÉMAUX ET COMBINATOIRESEN THÉORIE DES NOMBRESpar Paul ERDÖS(rédigé par Jean-Louis NICOLAS)
1 . - Il est connu que la densité asymptotique des entiers ayant deux divi-vérifiant

d1 et d2seursd1 ~ d,~2d1existe(cf. [4], et le livre de[10], p. 262, théorème 14). Soit

HALBERSTAM et ROTH

L’énoncé précédent revient à diret1

P. ERDOS aconjecturé que

ont deux diviseurs

c=1,c’est-à -dire que presque tous les entierstels qued~,On peut conjecturer aussi que, pouret.

k2d1 .

d2fixé, presque tous les entiers véri-B-(n) > k . Soit

fient

On conjecture que, pour presque tout

2 . -- Pour chaque entier

Ainsi, sinn ,n,appelons

llmn ,tlend({»)
d ~n ~-0 .

plus petit entier vérifiant

tn = n - 1 ; si n = x(x + 1 ) , 1: == x .

est premier,,,*P. ERDOS et R. R. HALL ont montré quece(non encore publié)qui était une conjecture d’ERDOS.

3 . - Rappelons la définition suivante, liée au théorème de Van der Waerden(cf. [5] ou j~13] pour un historique plus détaillé).
Définition. - On désigne parfinie

vérifiant1

progression arithmétique dek

le nombre maximum de termes d’une suiterk(n)a2 ...

aln , etnecontenant pas unetermes.

E. SZEMEREDI a marqué une étape importante dqns cette étude en démontrant que,pour tout

kfixé( cf ~ ~ 13 ] ~CONJECTURE

vérifiant(primée- 15 000 francs). - Soit une suite

03A31 aAlors, pour toutsuite en progression arithmétique.
=+ CI:) .

d’entiers positifséléments de cettekk, on peut trouver

Cette coniecture permettrait de démontrer au’,11 existe des progressions arith-métiques arbitrairement longues formées uniquement de nombres premiers.
Dans l’autre sens,onpeut définir :"sup" étant pris sur l’ensemble des suites
sion arithmétique de k termes.

(a.)

leA 1’aide du résultat de BERIEKAMP
1. $ n ~n ~9k

dek2k ttermes,

ondeux classes

enne

contenant pas de progres-[2] qui montre qu’on peut partager les entiers
necontenant

aucuneprogression arithmétiquepeut montrer que

Très récemment, J. GERVER a observé, dans un article à paraître dans les Proc.
Amer. math. Soc., que, pourne

contenait aucune

ceassure, pourppremier,l’ensemble

progression arithmétique dek

assez

termes,, et que l’on ap

grande Ak (1. - a ~ k log k .

4. - Suites primitives : soit 2 . a.
a~a, S n . Trouver la plus
grande valeur de k tel que chaque ai ne divise pas le produit des autres. La
réponse est...

k =n(n) = nombre de nombres premiers ~ n .

H.~.

En

aj ,effet, si
avec un exposant maximum :Ceci

unnombre

implique qu’il ne peut y avoir plus deOn appelle suite
tout

il existei ~ j, ajaj.

premierque de nombres

a. 1

premiers % n .

primitive (cf. [1:0~, p. 244~ une suite a, 1 telle que, pourLe plus grand nombre possible de termes d’une suite

2n

est

n, réalisé

avec

n+1,...

,2n .

( n + 1 ) termes a . 2n , en écrivant a.
pair, il y aurait (n + 1) valeurs possibles àe b. et lesavait

a.

i J

tive inférieurs àondivisantp.

plus deOn montre que pour toute suite

primitive, la=en

2 1 . tbieffet,b.

sontlog ai)

imn .

est

convergente (cf. ~?,] ~ et [ 1a~ p th. 2, p. 245).
Soit maintenantle maximum étant pris pour toutes les suites

primitives. On a

Mais probablement~ il n’existe pas de solution

On consultera

transposer le problème une suite de nombres réels

On peuta./ta.
r jsujet l’article de synthèse [8].

cesursimple qui réalise le maximum.

a..

La condition

traduit par

seA-t-on, pour une telle suite,

HAIGHT [London]
eta~a’,
Lecas~.~ ,démontré que si lesen1

indépendants,

alors 1.

deux

sont rationellernent

a ,vraiment difficile semble être le(n + 1)

5. - Soit

Il yacasoù lesa.

sont rationnels.

1

nombres entiers vérifiant :qui sont relativement premiers. En effet, il y en a deux qui sontconsécutifs. Cette réponse fut donnée par POSA à l’âge de 12 ans.
CONJECTURE. - Soit 1 $:suite d’entiers telle qu’on
nombresrne peut pas trouver
ai qui soient deux à deux relativement premiers .
On obtient la plus grande valeur de k en considérant tous les nombres qui ont
au moins un facteur premier $ p _ 9 où 2, 3 , ... , p - sont les (r - 1. )
...

a2n

une

premiers nombres premiers.

de6. - Soit

Sparties deS

unensemble fini àtelle que

Ai ~ Ajthéorème de Sperner dit que le nombrennetéléments. Soit
soit jamais vérifié pouru’1.

D.

A. ~ A.
1213

lorsque’i~, , i~¿
1etJL-famillei ~ j . Le.

d’éléments d’une telle famille vérifie

Soit maintenant une famille de parties deA.

une

S :

~~ 1, ~!~l~t~~l~t, vérifiant

sont distincts.

démontré que l’on ava it

I~_P. ERDOS
1~/~ pouvait être remplacé

conjecturé que le coefficient

apar0(1 ) , et KLEITMAN l’a récemment démontré.

+(cf. [11] et [1 ]) le résultat

7. - BAUMGARTNER et HINDMAN ont démontré
suivant : si l’on partage l’ensemble ?
unesuite infinie

lessommes

Mais

infinie

sait pas(a)kenil existe

classes,

a~ , ... , a n appartenant à l’une des classes telle que toutes
e . -on nedes entiers

0ousoient dans la même classe.

1

telle quea.

et+ a.

en .deux

Nsi, lorsqu’on divise(1a.a.

iil y aclasses,j)

une

suite

soient tous dans lamême classe.

Autrequestion : On divise les entiers en deux classes. Est-il vrai que, pourtoutt , il y a des entiers
t ?

plus grand que

ettous dans la même classe

a~ ,a~ ,GRAHAM a démontré que l’onpeut partager les entiers ~ 251endeux classes defaçon qu’aucun classe ne contienne les 4 nornbres : a1 t a2 , a. + a2 ’
Si l’on partage les entiers ~ 252 , l’une des classes contient toujours 4 nom~
bres
Malheureusement, il ne peut pas exclure la possia1 ~ a~ , a1. + a2 q.

bilité queai

8. - Soit1--.

nombres :an . Montrer que, pour ~ > 0 etl’ensemble des nombres de la forme
assez grand,a. + a et a.a. ,i j .$ n , a un cardinal n2-l(cette conjecture est primée 1 000 francs).

n1na~a1...

E.SZEMEREDI et P. ERDOS savent montrer que
quenf( n)pour une fonction

vérifiantfcardinal est

celim f(n)=toujours plus grand+ co .

A l’aide des métho-exposée dans le livre de FREIMAN [9J, on peut montrer que
ne peut pas être remplacé pardes de théorie additive

n2 ElePeut-être a-t-on le même résultat plus fort :s Soit un graphe de sommet

a2 ,(a. , a.)... , a . Si

nombresa. + a.

eta. a..

sontreliés par une arête,Si le grapheakon

a1 ’considère les deuxarêtes, on trouve plus quek2

nombres distincts.
9. - Problème de Sidon

infinietelle que les

a1 , ... , anOn peut construire

une

lim

sommesai + ajsoient toutes

telle suite par récurrence vérifiant

fait les calcul jusqu’àque(cf. [10], chap. II, et [6] p. 227) : Soit une suite

akdistinctes.

cka25 000).

Peut-on, pour $ 100 , en construire une telle

â2

an est une suite infinie d’entiers tels
ai + aj est inférieur à C, alors la suitea~~-0?

Est-il vrai que, si

a1

que lE nombre de solutions de...

n=

G7-05peut être partitionnée en+sommes

a~~r~

f(C)

morceaux{ai(r)},

1.

r

f(C) , telle que lessoient toutes distinctes ?

BIBLIOGRAPHIE[1]

BAUMGARTNER(J. E.). - A short proof of Hindman’s theorem, J. of combinatio-rial Theory, Series A, t. 17, 1974, p. 384-386.
[2] BERLEKAMP (E. R.). - A construction for partitions which avoid long arithmetic progressions, Proc. Nat. Acad. Sc. U. S. A., t. 32, 1946, p.331-332.
[3] COMTET (L.). - Analyse combinatoire. - Paris, Presses Universitaires deFrance, 1970 (Collection SUP. "Le Mathématicien", 4 et 5).
[4] ERDÖS (P.). - On the density of some sequences of integers, Bull. Amer.
math. Soc., t. 54, 1948, p. 685-692.
[5] ERDÖS (P.). - Résultats et problèmes en theorie des nombres, Séminaire
Delange-Pisot-Poitou : Théorie des nombres, 14e année, 1972/73, n° 24, 7 p.
[6] ERDÖS (P. ). - Some unsolved problems, Magyar Tudomanyos Akad., Publ. Math.
Inst. Hung. Acad. Sc., t. 6, 1961, p. 221-254.

[7][8]ERDÖS (P.). - Note on sequences of integers no one of which is divisible byany other, J. London math. Soc. , t. 10, 1935, p. 126-128.
ERDÖS (P. ), SARKÖZI (A. ) and SZEMEREDI (E.). - On divisibility propertiesof sequences of integers, "Number theory". Edited by P. Turan [1968,Debrecen.], p. 37-49. - Amsterdam, North-Holland publishing Company, 1970
(Colloquia Mathematica Societatis Janos Bolyai, 2).

(G. A.). - Foundations of a structural theory of set addition. Providence, American mathematical Society, 1973 (Translations of mathematical Monographs, 37).
[10] HALBERSTAM (H.) and ROTH (K. F.). - Sequences, vol I. - Oxford, at the Cla-

[9]

FREJMANrendon Press, 1966.

[11]

HINDMAN (N.). - Finite sums from sequences within cells of a partition ofN , J. combinatorial Theory, Series A, t. 17, 1974, p. 1-11.

[12]

KLEITMAN (D.). - On a combinatorial
t. 17, 1966, p. 139-141.

[13]

SZEMEREDI (E.). - On sets of integers containing no k elements in arithmetic progression, "Proceedings of the international congress of mathematicians" [1974, Vancouver], p. 503-505 ; et Acta Arithmetica, Warszawa ,t. 27, 1975, p. 199-245.

problem of Erdös, Proc. Amer. math. Soc.,(Texte reçu le 16 juillet 1976)
Paul ERDOS
Akademia Matematikai Intezete,Realtanoda u. 13-15
H - 1053 BUDAPEST(Hongrie)