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

Van der Waerden (numeri di)

Matematica combinatoria  Vari 

Indice

  1. 1. Pagina principale
  2. 2. Numeri di Van der Waerden per piĆ¹ sottoinsiemi

Il teorema dimostrato da Bartel Leendert van der Waerden (Amsterdam, 2/2/1903 – Zurigo, 12/1/1996) nel 1927 riguarda la presenza di progressioni aritmetiche contenute in insiemi di interi. Dati due interi r e k, può essere espresso in varie forme equivalenti:

  • data una successione infinita e crescente di interi tali che la differenza tra termini successivi sia minore di r, la successione contiene una progressione aritmetica di lunghezza k;

  • esiste un intero g(k, r), tale che una successione crescente di g(k, r) interi con differenza tra termini successivi non superiore a r contiene una progressione aritmetica di lunghezza k;

  • se l’unione di r insiemi contiene tutti gli interi positivi, almeno uno degli insiemi contiene una progressione aritmetica di lunghezza k (congettura di Baudet);

  • esiste un intero W(r, k), tale che se l’unione di r insiemi contiene tutti gli interi da 1 a W(r, k), almeno un insieme contiene una progressione aritmetica di lunghezza k;

Nel caso dell’ultima formulazione il teorema dice che se suddividiamo gli interi da 1 a W(r, k) in r insiemi (non necessariamente disgiunti), almeno un insieme contiene una progressione aritmetica di lunghezza k.

 

I numeri W(r, k) sono noti come “numeri di van der Waerden”. Sebbene Saharon Shelah abbia mostrato che sono computabili tramite una funzione primitiva ricorsiva, non si conosce una formula generale per calcolarli e i loro valori sono noti in pochissimi casi.

 

Alcuni risultati generali noti:

  • W(r, 1) = 1;

  • W(r, 2) = r + 1;

  • W(r, 3) ≤ erc1, con c1 costante da determinare;

  • W(r, 4) ≤ eeerc2, con c2 costante da determinare;

  • W(2, p + 1) > p2p, se p è primo (E. Berlekamp, 1968);

  • Limite inferiore per W(2, n) (R.L. Graham, B.L. Rothschild e J.H. Spencer, 1980);

  • Limite inferiore per W(2, n) (William Gasarch e Bernhard Haeupler, 2011);

  • Limite inferiore per W(2, n) (William Gasarch e Bernhard Haeupler, 2011);

  • Limite inferiore per W(r, n) (William Gasarch e Bernhard Haeupler, 2011);

  • W(r, k) ≤ 22r22k + 9 (Timothy Gowers, 2003);

  • per ogni ε > 0 vale Limite inferiore per W(r, n), per k abbastanza grande (Zoltán Szabó, 1990).

 

Il miglior limite superiore generale oggi noto, dovuto a Timothy Gowers è una spaventosa sopravvalutazione del valore corretto.

 

La tabella seguente mostra i risultati noti.

r \ k

1

2

3

4

5

6

7

8

9

2

1

3

9

35

178

1132

> 3703

> 11495

> 41265

3

1

4

27

293

> 2173

> 11191

> 48811

> 238400

 

4

1

5

76

> 1048

> 17705

> 91331

> 420217

 

 

5

1

6

> 170

> 2254

> 98740

> 540025

 

 

 

6

1

7

> 223

> 9778

> 98748

> 816981

 

 

 

 

I risultati mostrati sono stati ottenuti esaminando un numero colossale di combinazioni; anche se un gran numero di scorciatoie e semplificazioni peremette di esaminare realmente solo una minima parte del totale, il lavoro necessario è enorme: per determinare W(2, 6) nel 2000, Michal Kouril e Jerome L. Paul utilizzarono fino a 200 calcolatori e alcune macchine con componenti progettati appositamente per 235 giorni e dichiararono che il calcolo di W(2, 7) con gli stessi strumenti e metodi è improponibile.

 

Negli ultimi anni i progressi nel calcolo dei valori sono dovuti sia all’impiego di macchine più veloci, sia al miglioramento degli algoritmi, ma i progressi verso una formula generale o limiti inferiori e superiori migliori sono scarsi.

 

Una variante appena più forte del teorema Van der Waerden afferma che per ogni valore intero di r, k e s, esiste un intero W(r, k, s), tale che se suddividiamo gli interi da 1 a W(r, k, s) in r insiemi (non necessariamente disgiunti), almeno un insieme contiene una progressione aritmetica di lunghezza k con differenza d tra elementi successivi e contiene anche il numero ds.

 

Il teorema di van der Waerden è una conseguenza del teorema di E. Szmerédi, dimostrato nel 1975, che afferma che qualsiasi sequenza di interi con densità superiore di Banach positiva contiene progressioni aritmetiche di lunghezza arbitraria. L'affermazione era stata proposta come congettura da Paul Erdös e P. Turán nel 1936.

Un corollario è che per ogni intero k e ogni numero reale δ, esiste un intero n, tale che ogni sottoinsieme degli interi da 1 a n contenente almeno δn interi contenge una progressione aritmetica di k termini. In questa versione fu dimostrato per k = 3 da Roth nel 1953 e per k = 4 da Szmerédi nel 1969, poi lo stesso Szmerédi trovò la dimostrazione generale.

 

Il concetto chiave espresso dal teorema di van der Waerden è 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 Schur (v. numeri di Schur) e Ramsey (v. numeri di Ramsey).

Contattami

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