Don't take life too seriously: it's just a temporary situation

Erdös degli insiemi a somme distinte (costante di)

Matematica combinatoria  Teoria dei numeri 

Un insieme di interi positivi si dice “a somme distinte” se tutte le somme degli elementi dei suoi sottoinsiemi sono diverse o, in modo equivalente, se le somme di elementi, senza ripetizioni, sono tutte diverse.

 

Le potenze di due costituiscono un semplice insieme a somme distinte, che in un certo senso funge da pietra di paragone per gli altri, perché l’elemento massimo di una sequenza di insiemi a somme distinte non può crescere molto più lentamente delle potenze di due all’aumentare del numero di elementi.

 

Erdös considerando sequenze crescenti di interi a somme distinte si chiese quale potesse essere il minimo rapporto Formula per la definizione di α(n) per qualsiasi sequenza di n interi avente come massimo an, ovvero quanto potesse essere reso piccolo il massimo elemento dell’insieme, e arrivò nel 1931 a supporre che esista un limite inferiore non nullo ai possibili valori di αn: tale limite si chiama “costante di Erdös degli insiemi a somme distinte”.

 

Gli insiemi a somme distinte con minimo elemento massimo per un numero di elementi da 1 a 9 sono mostrati nella tabella seguente.

n

Insiemi

an

αn

1

{ 1 }

1

 1 / 2

2

{ 1, 2 }

2

 1 / 2

3

{ 2, 3, 4 }, { 1, 2, 4 }

4

 1 / 2

4

{ 3, 5, 6, 7 },

7

 7 / 16

5

{ 3, 6, 11, 12, 13 }, { 6, 9, 11, 12, 13 }

13

 13 / 32

6

{ 11, 17, 20, 22, 23, 24 }

24

 3 / 8

7

{ 20, 31, 37, 40, 42, 43, 44 }

44

 11 / 32

8

{ 20, 40, 71, 77, 80, 82, 83, 84 }, { 39, 59, 70, 77, 78, 79, 81, 84 }, { 40, 60, 71, 77, 80, 82, 83, 84 }

84

 21 / 64

9

{ 77, 117, 137, 148, 154, 157, 159, 160, 161 }

161

 161 / 512

 

Erdös e L. Moser dimostrarono nel 1955 che Limite inferiore per α(n) per n > 1, poi N.D. Elkies dimostrò (1986) che Limite inferiore per α(n), per n abbastanza grande, quindi A.M Gleason e N.D. Elkies, alzarono il limite a Limite inferiore per α(n), ma nessuno ha ancora scoperto se α = inf αn sia maggiore di zero, ossia se aumentando il numero di elementi nell’insieme si possa ridurre a piacere αn.

 

Altri hanno cercato un limite superiore al valore di α: M.D. Atkinson, A. Negro e N. Santoro studiarono una sequenza particolarmente utile, definita come: u0 = 0, u1 = 1 e Formula per u(k + 1).

La sequenza risultante è quindi: 0, 1, 2, 4, 7, 13, 24, 46, 88, 172, 337, 667, 1321, 2629, 5234, 10444, 20842, 41638, 83188, 166288, 332404, 664636, 1328935, 2657533, 5314399, 10628131, ...; fissato un valore di n si prende ora la sequenza ak = ununk e si ottiene un insieme a somme distinte di n elementi. Per esempio, per n = 10 abbiamo 165, 249, 291, 313, 324, 330, 333, 335, 336, 337 e Valore di a(10) / 2^10, mentre in generale an = unLimite del rapporto u(n) / 2^n (W.F. Lunnon 1988). Il limite è anche chiamato “costante di Atkinson, Negro e Santoro”.

 

J.H. Conway e R.C. Guy suggerirono di ridefinire la sequenza come Formula per u(k + 1), ottenendo in tal modo la sequenza 0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284, 4484, 8807, 17305, 34301, 68008, 134852, 267420, 530356, 1051905, 2095003, 4172701, 8311101, 16554194…, che riduce il limite di u(n) / 2^n a circa 0.2351252848 (W.F. Lunnon 1988). Solo nel 1996, tuttavia, T. Bohman riuscì a dimostrare che la sequenza così generata è effettivamente a somme distinte.

 

Un’altra via per trovare un limite superiore per α è trovare una sequenza finita con un rapporto abbastanza basso. Ogni sequenza a somme distinte a1, a2, a3, ... an può, infatti, essere estesa un elemento per volta semplicemente aggiungendo 1 in testa e raddoppiando gli altri termini: anche la sequenza 1, 2a1, 2a2, 2a3, ... 2an, infatti, è a somme distinte ed ha il valore di αn + 1 uguale al doppio del valore di αn della sequenza di partenza. Se si riesce a cambiare qualche termine in modo da ridurre l’ultimo, si migliora il rapporto.

 

W.F. Lunnon trovò nel 1988 una sequenza di 67 numeri con rapporto minimo 0.22096 e T. Bohman nel 1997 ridusse ulteriormente il rapporto a 0.22002.

 

Erdös e S. Benkoski dimostrarono nel 1974 che data una sequenza infinita a somme distinte an, Limite superiore per la somma dei reciproci dei termini.

Bibliografia

  • Honsberger, Ross;  Mathematical Gems III, The Mathematical Association of America,, 1985.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.