J OURNAL DE T HÉORIE DES N OMBRES DE B ORDEAUX

P. E RDÖS
J.-L. N ICOLAS
A. S ÁRKOZYSommes de sous-ensembles
Journal de Théorie des Nombres de Bordeaux, tome 3, no 1 (1991), p. 5572.
<http://www.numdam.org/item?id=JTNB_1991__3_1_55_0>© Université Bordeaux 1, 1991, tous droits réservés.
L’accès aux archives de la revue « Journal de Théorie des Nombresde Bordeaux » (http://jtnb.cedram.org/) 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/

55-7

Sommes de sous-ensembles.

par P.

ERDÖS, J.-L. NICOLAS, A. SÁRKOZY(1)Résumé 2014 On dit qu’un ensemble A est admissible si les sommes deséléments de deux sous ensembles de A de cardinaux différents sont différentes. Nous démontrons que si A C {1, 2, ..., N} est admissible, alors
Card A ~ (1 +améliorant ainsi les résultats de Erdöset Straus, et nous formulons quelques conjectures d’après des calculs numériques. Enfin nous construisons un ensemble infini admissible A vérifiant
A (x) = Card{a ~ A ; a x} &#x3E;&#x3E; x5-2~6.

o(1))(143/27)1/2~N,Abstract 2014 A set ,A is said to be admissible if the sums of the elements of two subsets of A of different cardinalities are different. Weshall prove that if A ~ {1, 2, ..., N} is an admissible set, then Card A ~improving preceding results of Erdôs and Straus.
From numerical calculations, some conjectures are given. Finally, we construct an infinite admissible set A such that A(x) = Card {a ~ A; a(1+o(1))(143/127)1/2~Nx} &#x3E; &#x3E; x5-2~6.

1. Introduction

Tout au long de cet article nous utiliserons les notations suivantes :écrirons N == {1,2,3,...} et N~ = {1,2,....M}. Nous dirons qu’unensemble ,~4 C N est admissible, si les sommes des éléments de deux sousensembles de .A de cardinaux différents sont différentes. Cette définition anous désignerons
été introduite par E.G. Straus ([2]). Si .A C N
etdesentiers
lecardinaldel’ensemble,~4qui peuventpar 1,41park)être représentés comme la somme d’exactement k éléments distincts de ,~1,et nous écrirons P(,~4, k) =Dire que ,~l est admissible équivaut à
dire quenous

En d’autres termes, ,~l est admissible si la somme des éléments d’une partiede ,~l détermine le cardinal de cette partie.
"Manuscrit reçu le 30 octobre 1990.

,(1) Recherche partiellement financée par la Fondation Nationale Hongroise pourScientifique, contrat n° 1811 et par le C.N.R.S. SDI 5614 et PRC
Mathématiques- Informati que .

la Recherche

56

P. Erdôs ([1]) a posé et étudié le problème suivant : Quel est le cardinalmaximum F(N) d’une partie admissible .A deSes résultats ont étéaméliorés par E.G. Straus ([2]), qui a démontré :De plus, Erdos a conjecturé que le cardinal maximum F(N) est atteint
lorsque ,A est formé d’entiers consécutifs incluant N, c’est-à-dire

En rapport avec cette conjecture, Straus a démontré :(ii) L’ensemble ,Ak=

2m-1 si m2=

N{7V 2013&#x26;+1, N - k + 2, ..., 7V} est admissible pourm + m et pour k=

2m si m2+mN(m+1)~.

Ceci implique :Nous nous proposons dans cet article d’étendre et de préciser les résultatsde Erdôs et Straus. D’abord, nous améliorons la borne supérieure de (i).
Ensuite, au paragraphe 4, à l’aide des tables numériques construites parJ.-P. Massias et M. Deléglise, que nous avons plaisir à remercier ici, nous
ferons des conjectures sur ce problème. Finalement, nous étudierons lesensembles infinis admissibles, dans le cinquième paragraphe.
2. THÉORÈME 1. On a :Il serait possible d’améliorer ce résultat par une application plus élaboréede nos idées. Cependant, il semble impossible d’obtenir de cette façon lalimite conjecturée : lim sup F(N~N-~ ~2 = 2 et en fait, une nouvelle idéesemble nécessaire pour donner une borne supérieure plus petite que 2.2.

Pour démontrer le théorème 1, nous avons besoin de deux lemmes.
LEMME 1. Soit ,A un ensemble fini,lAI. Alors ona :Démonstratz«on. C’est le théorème 2 de Straus [2], qui se démontre facilement par récurrence sur lAI.

Nous utiliserons le théorème 4 de Straus sous la forme suivante :57

LEMME 2. Soit N E N. On a :Démonstration. Nous suivons la preuve de Straus. Soit ,A C ~,v un ensemble admissible. Il est clair que les éléments dek) sont inférieurs àDonc, pour x &#x3E; 1, nous avons par le lemme 1 :d’où il vient, en posant x = [3IAI/4] (la notation [u] désigne la partie entièrede u)

Supposons maintenant que l’on ait :contrairement à (4). Cela impliqueraitce

qui contredit (5), et achève la preuve du lemme 2.

58

3. Démonstration du Théorème 1.

...

Nous distinguerons 3 cas. Soit ,A =ay) un ensemble admissible. On pose :C NN,(aia2PREMIER CAS. On suppose que

Comme dans la démonstration du lemme 2, nous partons de la relation
avecélément detoujours x=[3y/4]. Le plus grandk) est évidemment le plus grand élément de P(A, ~),et par (6), il vaut

Nous avons donc :Par le lemme 1, ceci entraîne :59

et en utilisant x = [3y/4],

Nous avons donc, lorsque y -~ oo,

DEUXIÈME CAS.
On suppose que

Posons z =+ 1. Le plus petit élément de 1deélémentpetitP(A, z~ et vaut :~2 y~enutilisant (9). Par ailleurs, le plus grand élément de 1et donc

60

Puisque ,~l est admissible, ceci entraîne,Maintenant, par le lemme 1, nous obtenons la minoration :On déduit de (10) et (11) que :d’où il vient lorsque N --~ oo,

TROISIÈME CAS. Nous supposons maintenantetPosons u = (y/32~. Nous allons d’abord minorer P(,,4, k) lorsque

61

Considérons toutes les sommes de la forme

avec

ai,

ax2...

et ai j E

pour jde sommes de cette forme est
ces sommes ne=l, 2, ..., ~ - u. Le nombreu) et par (14) et (15) chacune dedépasse pas

De plus, pournous avonset les sommes dans (17) sont ainsi plus grandes que les sommes dans (16).
Par ailleurs, les sommes dans (16) et dans (17) appartiennent àk).
Ainsi, P(A, k) est supérieur ou égal au nombre total des sommes dans (16)et dans (17) :D’où il vient par (13) et le lemme 1 :Le plus grand élément dex=P(,4, I~~ est~3y/4~~, et comme ,~l est admissible,(où, comme précédemment,

62

Par le lemme 1 et (18) nous avons :d’où l’on déduit

La démonstration du théorème 1 résulte alors de (7), (12) et (19).
4.

Quelques conjectures

Il est commode de définir :On a donc

Nous dirons ensuite qu’un ensemble admissible ,A est N-optimal si ,A C N N,
et lAI = F(N). Nous noterons p(N) le nombre d’ensembles admissibles

63.N optimaux, et par a(N) le nombre d’ensembles admissibles non vides

Nous dirons aussi qu’un ensemble ,~4 est impair si tous les éléments de,~4 sont impairs. Dans le cas contraire, c’est-à-dire si ,A contient un nombre
pair, nous dirons que .~4 est non impair. Nous définissons

où ,~l parcourt l’ensemble E,y des ensembles admissibles N-optimaux etnon impairs. Si Ejy = 0, alors h(N~ _ +oo.

J .-P. Massias et M. Deléglise ont donné la liste des ensembles N-optimauxpour N50, et l’on trouvera un extrait de leurs résultats dans la table enannexe. Ces calculs sur ordinateur montrent un comportement très régulier
qui nous conduit aux conjectures suivantes :CONJECTURE 1. On a pour tout N &#x3E; 1]

et l’ensemble (ii) de Straus est N-optimal.

Conjecture 2. Lorsque N est de la forme m2 ou m(m + 1), on a
1, autrement dit l’ensemble (ii) de Straus est le seul ensemble
admissible N-optimal. De façon plus générale, soit t &#x3E; 0. Il existe deux
fonctionson aitet q(t) telles que, pour m &#x3E;p(N)=Conjecture 3. Les ensembles admissibles N-optimaux impairs sont :~1{7V, N - 2, ..., N - 2g(N) + 2} lorsque N m,2 - 2 et m impair,lorsque N m2 - 1 et m pair et lorsque N m(m + 1~ - 1 et
A2 {N, N - 2, ..., N - 2g(N) -f- 4, N - 2g(N)} lorsque N m2 - 1avec m pair et lorsque Nm(m + 1) - 1.
===

=

=

=

=

Il est facile de voir que les ensembles ci-dessus ont g(N) éléments etsont admissibles, et donc sous réserve de la conjecture 1 sont N- optimaux.

64

De façon plus générale on peut caractériser les progressions arithmétiques
admissibles
1

par la condition :Ce résultat se démontre comme (ii) en observant que, comme (N, r) = 1, ilsuffit de comparer la somme des j plus grands termes de A avec la sommedes (j + r) plus petits termes de A, et ceci pour 1 j k - r.
Un calcul un peu technique montre que pour r &#x3E; 3, A(g( N), r, N) n’est
pas admissible, et pour r = 2 et N impair, A(g(N), 2, N) est admissible
seulement dans les cas décrits à la conjecture 3.

Conjecture 4. Pour N &#x3E; 16, la fonction N - h(N) est constante surles intervalles (m2, m(m + 1) - 1) et (m(m + 1), (m ~- 1)2 - 1). On a de plush(m2)=rn2 - 2m + 2 et h(m(m + 1))=

m2 - m + 1.

Comportement de a(N). Il est clair que toute partie d’un ensemble
admissible est admissible. Il résulte donc de (ii) que

Par ailleurs, il résulte du lemme 2, en posantque

pour un certain c.

Il nous semble difficile de préciser davantage le comportement de a(N).
L’étude de la table numérique laisse penser quemais nous conjecturons cependant que l’on a log

65

5. Suites infinies.

Nous allons maintenant étudier les ensembles infinis admissibles. Si ,~i CN, et x &#x3E; 0, on poseet nous conjecturons que si ,~1 est admissible, alors(La limite ci-dessus est finie par (1).) Malheureusement nous n’avons pas
été capables de le démontrer.
Par ailleurs, Erdos [1] a démontré qu’il existe c &#x3E; 0 (la valeur de c n’estpas précisée) et un ensemble infini admissible A tel quePeut-être est-il possible d’obtenir

Nous prouvons seulement le résultat plus faible :THÉORÈME 2. Il existe un ensemble infini admissibIe,4 C N vérifiant pourDémonstration. Soit xn = 0, et pour N = 1, 2, ..., posons ;avec !{ = 40.
Par récurrence nous allons définir les ensembles de nombres entiers positifs A 1 , .,42 , ... vérifiant

Lorsque N=

1, on pose Tl

=1 et

66

Pour N &#x3E; 2, supposant construits...,~4/~-i, on poseetMaintenant nous allons démontrer l’inclusion (21) pour tout N. On remarque d’abord que, pour1, on a :De plus, d’après la définition de AN, on a :En tenant compte de (22) et (23), il suffit de démontrer

pour démontrer (21).

Or (24) se vérifie numériquement lorsque N _ 1.
définitions de...,~4/v-i et TN entraînent, par (22)Nous avons ainsi

Pour N &#x3E;

1, les67d’où l’on déduit (24) en vérifiant numériquement que

On pose ,,4 =AN. Nous allons montrer que cet ensemble est admissible et qu’il vérifie (20).
D’abord nous allons montrer que pour tout N, l’ensemble ,A,Y est admissible. Il suffit pour cela de montrer que pour 1 ~ ~,~1,v ~ - 1,on aOn pose

Nous avons alors

Le minimum du trinôme f (k~ est atteint en k =et donc

68

Par (25) et (28), (29) devient :cequi prouve (27), et donc que pour tout l~ &#x3E; 1, AN est admissible.

Nous devons montrer maintenant que l’ensemble .A =a2...~ est aussi admissible. Raisonnons par l’absurde, et supposons
que ,A a deux sous-ensembles de mêmes sommes, avec un nombre différentd’éléments, c’est-à-dire qu’il existe des entiers i i 2 ... i71.,jli j2...

j,, tels que

Nous pouvons supposerj,,, et que a~,...,a~~û[~,...,a~, (avec
est minimal. On définitu =fi v) est une solution telle que j,,
N par aj,, 6 A N (on a évidemment N &#x3E; 2) et soit u’ et v’ les plus grands=nombres tels que
N-11(et l’on a, ou bien

1si l’on akpour v’

on poseu’ = 0. Alors1v, et (30) entraîne69De plus, nous avons

Par (31) et (32), il vient

Mais jt1 a été choisi

et tous les termes ci-dessus appartiennent àminimum ; cela implique

On a ensuite par (30), (33) et (34)et les nombres de termes dans les deux sommes ci-dessus sont différents :mais ceci
u v’. De plus tous ces termes appartiennent àest admissible. Cette
est impossible puisque nous avons démontré que
contradiction termine la preuve que ,~4 est admissible.

Il reste à démontrer (20). Pour x &#x3E;
D’après la définition de .A, nous avons

ondéfinit N par x,v_i

et cela achève la démonstration du théorème 2.

x

70

Table numérique

71

REFERENCES[1] P. ERDÖS, Számelméleti megjegyzések, III, Mat. Lapok 13 (1962), 28-38.
[2] E.G. STRAUS, On a problem in combinatorial number theory, J. Math. Sci. I (1966),
77-80.

P. Erdôs, A. Sarkozy

Magyar Tudomanyos Akadémia

72

Matematikai Kutat6 Intézete
Realtanoda utca 13-15PF 127
H-1364 BUDAPEST V - HONGRIE.
etJ.-L. NICOLASDépartement de Mathématiques, bât. 101
Université Claude Bernard, Lyon 1
F-69622 VILLEURBANNE Cedex - FRANCE.