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

Schur (numeri di)

Matematica combinatoria 

Un insieme di numeri si dice “libero da somme” se non contiene tre elementi, non necessariamente distinti, x, y e z tali che x + y = z.

Il teorema dimostrato nel 1916 da Issai Schur (Mogilev, allora impero Russo, oggi Bielorissia, 10/1/1875 – Tel Aviv, 10/1/1941) afferma che se si suddividono i numeri naturali in un numero finito di sottoinsiemi, questi non possono essere tutti liberi da somme.

Quello che non si può fare con infiniti numeri, si può fare accontentandosi di un numero finito: se si suddividono gli interi da 1 a k in numero finito di sottoinsiemi, è possibile fare in modo che siano tutti liberi da somme. Si pone quindi il problema di quale sia il massimo numero S(n) tale che gli interi da 1 a S(n) possano essere suddivisi tra n insiemi liberi da somme. Tali numeri si chiamano “numeri di Schur”, perché lo stesso Schur dimostrò che esistono per ogni intero positivo n.

Per esempio, S(3) = 13, perché gli interi da 1 a 13 possono essere suddivisi in 3 insiemi liberi da somme: { 1, 4, 10, 13 }, { 2, 3, 11, 12 } { 5, 6, 7, 8, 9 }, mentre non è possibile una suddivisione del genere degli interi da 1 a 14.

 

Di solito si preferisce parlare di “colorare gli interi” con r colori diversi, invece di suddividerli in r sottoinsiemi, forse per l’immediatezza dell’immagine suggerita, ma il problema rimane inalterato.

 

Non si conosce una formula semplice per calcolare i numeri di Schur e quelli noti sono pochi, ottenuti provando una miriade di combinazioni, oggi con l’aiuto di potenti elaboratori.

 

I migliori limiti noti sono:

  • Limite inferiore per i numeri di Schur (Schur 1916);

  • S(n) ≥ S(n – 1) + 1 (Schur 1916);

  • Limite inferiore per i numeri di Schur, per n > 5 e una costante c (H.L. Abbott e Leo Moser 1966);

  • S(n) ≤ n!e (Schur 1916);

  • S(n) ≤ Rk(3) – 2 (Schur 1916), dove Rk(n) è un numero di Ramsey per k colori;

  • Limite superiore per i numeri di Schur;

  • Limite superiore per i numeri di Schur, per n pari e maggiore di 5 (Honghui Wan, 1990).

 

La tabella seguente riporta i pochi numeri di Schur noti.

n

S(n)

1

1

2

4

3

13

4

44 (L.D. Baumert 1965)

5

[160 .. 305] (G.Exoo, 1994 e M.I. Sanz, 2010)

6

[536 .. 1922] (Harold Fredricksen e Melvin M. Sweet 2000 e Honghui Wan, 1990)

7

≥ 1680 (Harold Fredricksen e Melvin M.Sweet 2000)

 

Se si modifica la definizione, stabilendo che ogni sottoinsieme non debba contenere la somma di elementi distinti dello stesso, abbiamo i numeri di Schur deboli S’(n); La tabella seguente riporta i pochi noti.

n

S’(n)

1

2

2

8

3

23

4

66 (P.F. Blanchard, F. Harary e R. Reis, 2004)

5

≥ 196 (S. Eliahou, J.M. Marín, M.P. Revuelta e M.I. Sanz, 2012)

6

≥ 575 (S. Eliahou, J.M. Marín, M.P. Revuelta e M.I. Sanz, 2012)

 

Il teorema di Folkman, noto anche come “teorema delle somme finite”, afferma che se si colorano i naturali maggiori di zero con r colori, per ogni valore intero n esiste un insieme S di n numeri naturali non nulli tale che tutte le somme di sottoinsiemi non vuoti di S siano dello stesso colore.

Il teorema fu dimostrato indipendentemente da varie persone, ma nel 1980 Ronald L. Graham, Bruce L. Rothschild e Joel H. Spencer gli diedero il nome di “teorema di Folkman” in onore di Jon Hal Folkman (Ogden, Utah, USA, 8/12/1938 – 23/1/1969).

 

Il teorema di Hindman estende il teorema di Folkman a sottoinsiemi infiniti; esso afferma, infatti, che si colorano i naturali maggiori di zero con r colori, esiste un insieme infinito S di numeri naturali non nulli tale che tutte le somme di sottoinsiemi finiti e non vuoti di S siano dello stesso colore (Neil Hindman, 1974). Per esempio, se attribuiamo il colore rosso ai numeri primi e il blu ai numeri composti, possiamo prendere per S l’insieme dei numeri pari maggiori di 4, perché tutte le somme di sottoinsiemi finiti e non vuoti di S sono pari e maggiori di 4, quindi blu.

 

Il concetto chiave espresso dai teoremi di Schur, Folkman e Hindman è che ogni struttura complessa abbastanza grande, per quanto disordinata possa apparire, contiene una struttura ordinata di qualsiasi dimensione voluta; all’incirca lo stesso concetto espresso dai teoremi di Ramsey (v. numeri di Ramsey) e van der Waerden (v. numeri di van der Waerden).

 

Una possible generalizzazione del problema è determinare il massimo numero S(n, k), tale che gli interi da 1 a S(n, k) possano essere suddivisi in n sottoinsiemi, in modo che le somme con fino a k addendi, non necessariamente distinti, di elementi di un sottoinsieme non appartengano al sottoinsieme stesso. Anche in questo caso esiste la variante debole, nella quale si cerca il numero S’(n, k) con la definizione analoga, ma considerando solo somme di elementi distinti,

 

E’ facile dimostrare che nkS’(n, k) ≤ S(n, k).

 

Una variante del problema è determinare il massimo numero Sm(n, k), tale che gli interi da 1 a Sm(n, k) possano essere suddivisi in n sottoinsiemi, in modo che le somme modulo m con fino a k addendi, non necessariamente distinti, di elementi di un sottoinsieme non appartengano al sottoinsieme stesso. Anche in questo caso esiste la variante debole, che considera solo somme di elementi distinti.

Si dimostra facilmente che Sm(n, k) ≤ S(n, k), Sm(n, k) ≤ m – 1 e S1(n, k) = 0.

 

Nel 2013 Jonathan Chappelon dimostrò che:

  • S2(n, k) = 0, per k dispari;

  • S2(n, k) = 1, per k pari;

  • S3(n, k) = 0, per k ≡ 1 mod 3;

  • S3(n, k) = 1, per n = 1 e k ≡ 0 o 2 mod 3;

  • S3(n, k) = 2, per n > 1 e k ≡ 0 o 2 mod 3;

  • Sm(2, 2) = 4, per m = 1 e m = 3;

  • Sm(2, 2) = 5, per m = 2 e m = 4;

  • Sm(2, 2) = 6, per m = 5, m = 6 e m = 8;

  • Sm(2, 2) = 7, per m = 7, m = 9, m = 10 e m = 11;

  • Sm(2, 2) = 8, per m > 11;

  • S1(n, k) = nk;

  • S2(n, k) = k + 1, per n = 1 e k ≡ 0 o 1 mod 4;

  • S2(n, k) = k, per n = 1 e k ≡ 2 o 3 mod 4;

  • S2(n, k) = 2(n – 1)k + 1, per n > 1 e k pari;

  • S2(n, k) = n(k + 1), per n > 1 e k ≡ 1 mod 4;

  • S2(n, k) = n(k + 1), per n > 1, n pari e k ≡ 3 mod 4;

  • S2(n, k) = n(k + 1) – 1, per n > 1, n dispari e k ≡ 3 mod 4;

  • S3(n, k) = 3n, per k = 1;

  • S3(n, k) = k, per n = 1 e k > 1;

  • S3(n, k) = 2k + 2, per n = 2, k > 1 e k ≡ 0, 1 o 5 mod 9;

  • S3(n, k) = 2k + 1, per n = 2 e k = 3;

  • S3(n, k) = 2k + 1, per n = 2, k > 4 e k ≡ 2, 3, 4, 6, 7 o 8 mod 9;

  • S3(n, k) = 2k, per n = 2 e k = 2 o k = 4;

  • S3(n, k) = 3(n – 2)k + 2, per n > 2 e k ≡ 0 o 2 mod 3;

  • S3(n, k) = n(k + 1), per n > 2, ma diverso da 4, k > 1 e k ≡ 1 mod 3;

  • S3(n, k) = n(k + 1), per n = 4, k > 1 e k ≡ 1 o 7 mod 9;

  • S3(n, k) = n(k + 1), per n = 4 e k = 4 mod 9.

 

Più in generale un sistema lineare omogeneo (cioè con termini noti uguali a zero) di equazioni si dice “r-regolare” su un insieme di interi A, se per ogni colorazione degli elementi di A con r colori esiste una soluzione costituita da un sottoinsieme di A monocromatico e si dice “regolare” se è r-regolare per qualsiasi valore intero positivo di r.

Un sistema è regolare sui numeri naturali maggiori di zero se e solo se è regolare sugli interi diversi da zero.

Un sistema è regolare sugli interi diversi da zero se e solo se è regolare sui numeri razionali diversi da zero.

Una soluzione costituita da numeri dello stesso colore si dice “monocromatica”.

Se un sistema è regolare sui naturali maggiori di zero:

  • per ogni numero di colori r esiste un intero n tale che per ogni colorazione degli interi da 0 a n con r colori esiste una soluzione monocromatica con numeri naturali non superiori a n;

  • per ogni numero di colori r esiste un insieme R finito di interi diversi da zero (ma anche negativi), tale che per ogni colorazione degli elementi di R con r colori esiste una soluzione monocromatica costituita da elementi di R;

  • per ogni numero di colori r esiste un insieme R finito di numeri razionali diversi da zero (ma anche negativi), tale che per ogni colorazione degli elementi di R con r colori esiste una soluzione monocromatica costituita da elementi di R.

 

Nel 1933 Richard Rado dimostrò nella sua tesi del 1933 che un sistema è regolare se e solo se le colonne della corrispondente matrice dei coefficienti possono essere partizionate in insiemi C1, C2, … Cn tali che la somma delle colonne di C1 è una colonna nulla e tutte le colonne di ogni insieme Ck possono essere espresse come combinazione lineare delle colonne degli insiemi precedenti.

 

E’ facile vedere che dati due sistemi regolari, esistono due soluzioni monocromatiche, una del primo, una del secondo, dello stesso colore, quindi dato un qualsiasi numero finito di sistemi regolari, esistono soluzioni monocromatiche di tutti, tutte dello stesso colore.

Contattami

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