Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Erdős e progressioni aritmetiche

Analisi, geometria, algebra, topologia...

Moderatori: Foto UtenteIanero, Foto UtentePietroBaima

5
voti

[1] Erdős e progressioni aritmetiche

Messaggioda Foto UtenteIanero » 14 lug 2015, 10:20

Apro una nuova discussione per fare una cosa un po' più formale.
Ho provato a ragionarci su per il gusto di farlo e volevo condividere con voi il risultato che ho ottenuto, mi farebbe piacere una discussione sul problema da parte di qualche curioso interessato.

Dunque, il problema è il seguente:

Dato un insieme A di interi positivi, se \sum_{n \in A} \frac{1}{n} = \infty allora A contiene progressioni aritmetiche di ogni lunghezza?

Innanzittutto occorre osservare che se l'insieme A fosse finito, la somma di tutti i suoi reciproci non potrebbe in nessun caso divergere, per cui A deve essere numerabile.

Prima di continuare, dimostro un risultato parziale che sarà cruciale successivamente.

D'ora in avanti chiamerò spazio tra due numeri nell'insieme A la seguente grandezza:

s_{n}=a_{n+1}-a_{n}



Lemma: Dato un insieme numerabile di interi positivi A la serie associata \sum_{n \in A} \frac{1}{n} diverge se e solo se gli elementi di A sono distribuiti in modo tale che la media degli spazi tra essi sia finita.

Dimostrazione
Definisco la successione a_n come l'unica successione strettamente crescente che si può trovare in A.
Una media degli spazi infinita è equivalente ad avere una successione a_n con crescita maggiore di quella lineare, ovvero un comportamento asintotico del tipo a_n\sim n^ \beta \; , \; \beta>1 (\beta intero positivo).
Infatti si avrebbe che:

s_{n}=a_{n+1}-a_{n}=\left( n+1 \right)^{\beta }-n^{\beta }

\overline{s_n}^N = \frac{\sum_{n=1}^{N}\left [ (n+1)^\beta - n^\beta \right ]}{N}

\overline{s_n}^\infty = \lim_{N\rightarrow \infty} \frac{\sum_{n=1}^{N}\left [ (n+1)^\beta - n^\beta \right ]}{N}

Per il Lemma di Toeplitz l'espressione dello spazio medio diventa:

\overline{s_n}^\infty = \lim_{n\rightarrow \infty} \left [ (n+1)^\beta - n^\beta \right ]

\overline{s_n}^\infty = \lim_{n\rightarrow \infty} \sum_{k=1}^{\infty}n^{\beta -k}\binom{\beta}{k}

Dove si vede che per \beta>1 si ha che \overline{s_n}^\infty \rightarrow \infty.
Allo stesso modo dall'ultima espressione trovata per \overline{s_n}^\infty si nota che nel caso \beta=1 si ha \overline{s_n}^\infty = 1.
Si potrebbe analizzare anche il caso \beta<1 che porterebbe a \overline{s_n}^\infty = 0, ma poiché A contiene solo interi positivi questo caso non può presentarsi.
Il lemma è infine dimostrato associando ad ogni a_n la sua corrispondente serie \sum_{a_n \in A} \frac{1}{a_n}\sim \sum \frac{1}{n^\beta} e utilizzando le proprietà di convergenza delle serie armoniche generalizzate.


Edit: Dimostrazione corretta nel messaggio [8]

A questo punto il problema diventa:

Dato un insieme A di interi positivi distribuiti in modo da avere media degli spazi finita, allora A contiene progressioni aritmetiche di ogni lunghezza?

Dimostrando però che:

Dato un insieme A di interi positivi distribuiti in modo da avere media degli spazi finita, allora A contiene almeno una progressione aritmetica di lunghezza infinita.

si dimostra automaticamente anche quello precedente.

Per il lemma precedente sappiamo che ora l'unico caso possibile che assicura la divergenza della serie \sum_{a_n \in A} \frac{1}{a_n} (avendo scelto solo interi positivi) è quello di crescita lineare.

Quello più banale è il seguente:



a_n=s \cdot n

\overline{s_n}^\infty = s

Per questi tipi di insiemi si trova subito una progressione aritmetica infinita di ragione s.

Tutti gli altri casi meno banali (per l'osservazione sul lemma precedente) si possono condensare nell'espressione:

a_{n+1} = a_n+s_n

con s_n interi positivi tali che \overline{s_n}^\infty < \infty.



Procediamo a questo punto con un'analisi algoritmica.



Presi i primi due numeri a_1 e a_2 si esplora l'insieme cercando l'eventuale esistenza di una progressione aritmetica di lunghezza infinita e ragione s_1=a_2-a_1.

Casi:
1) tale progressione aritmetica esiste -> Stop.
2) la progressione aritmetica cercata non esiste in A...

...



Si considera anche a_3 e si verifica l'eventuale esistenza di una progressione aritmetica infinita di ragione a_3-a_2 oppure di ragione s_2=a_3-a_1.

Casi:
1) almeno una delle due esiste -> Stop.
2) nessuna delle due esiste in A...

...



Si considera anche a_4 e si verifica l'eventuale esistenza di una progressione aritmetica infinita di ragione a_4-a_3 oppure a_4-a_2 oppure s_3=a_4-a_1.

Casi:
1) almeno una esiste -> Stop.
2) nessuna esiste in A...

...

...

...



Si considera anche a_k e si verifica l'eventuale esistenza di progressioni aritmetiche infinite di ragione a_k-a_{k-1} oppure a_k-a_{k-2} oppure ... s_{k-1}=a_k-a_1.

Procedendo in questo modo il caso peggiore che si presenta e che viene analizzato è la verifica della presenza della successione:

a_n=s_k \cdot n

Se i tentativi portano a risultati sempre negativi si arriva a:

a_n=\lim_{k\rightarrow \infty}s_k \cdot n=s_\infty \cdot n

poiché s_k è una successione strettamente crescente (con incremento minimo pari ad 1) vale che:

\lim_{k\rightarrow \infty}s_k =\infty

ovvero si arriverebbe al limite ad avere una successione intervallata da spazi di infinita lunghezza.
Ciò rappresenta un assurdo che viola l'ipotesi di partenza (la media spaziale non sarebbe più finita), il che implica allora che in A deve essere presente almeno una progressione aritmetica infinita di una qualche ragione s_i.
Questo quindi permette di affermare anche che in A è possibile trovare progressioni aritmetiche di qualsiasi lunghezza.

Spero di non aver annoiato nessuno :mrgreen:
Mi farebbe piacere discuterne con qualcuno di questo forum, buona giornata a tutti :-)
Servo, dai a costui una moneta, perché ha bisogno di trarre guadagno da ciò che impara.
Euclide.
Avatar utente
Foto UtenteIanero
7.754 5 8 13
Master EY
Master EY
 
Messaggi: 4110
Iscritto il: 21 mar 2012, 15:47

2
voti

[2] Re: Erdős e progressioni aritmetiche

Messaggioda Foto Utentefairyvilje » 14 lug 2015, 10:42

Dopo i miei genitori ritengono me una persona strana...
:mrgreen:

Oggi pomeriggio ho un esame, ma dopo proverò a leggere tutto :mrgreen:
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
12,9k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2683
Iscritto il: 24 gen 2012, 19:23

0
voti

[3] Re: Erdős e progressioni aritmetiche

Messaggioda Foto UtenteIanero » 14 lug 2015, 10:44

Dopo i miei genitori ritengono me una persona strana :mrgreen:

Esiste sempre di peggio :mrgreen:

Oggi pomeriggio ho un esame, ma dopo proverò a leggere tutto

In bocca al lupo e grazie!
Servo, dai a costui una moneta, perché ha bisogno di trarre guadagno da ciò che impara.
Euclide.
Avatar utente
Foto UtenteIanero
7.754 5 8 13
Master EY
Master EY
 
Messaggi: 4110
Iscritto il: 21 mar 2012, 15:47

1
voti

[4] Re: Erdős e progressioni aritmetiche

Messaggioda Foto Utentefairyvilje » 14 lug 2015, 20:46

Ho letto, ma mi manca un pezzo, il lemma di Toeplitz di cui non ho mai sentito parlare.
Per il resto i singoli passaggi mi sembrano corretti, e a prima vista non noto fallacie logiche nella dimostrazione. Ma potrei semplicemente essere molto stanco :mrgreen: .
Proverò a rivederla un po' più da riposato, con maggiore attenzione. Per allora è meglio che la controlli anche qualcun altro perché non mi fido troppo della mia capacità di trovare errori :mrgreen:
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
12,9k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2683
Iscritto il: 24 gen 2012, 19:23

2
voti

[5] Re: Erdős e progressioni aritmetiche

Messaggioda Foto UtenteIanero » 14 lug 2015, 22:56

Siccome ho notato che su internet non c'è lo posto io.

Lemma di Toeplitz:
Data la successione a_n con n \geq 1 e tale che \lim_{n\rightarrow \infty}a_n=a, allora:

\lim_{n\rightarrow \infty} \frac{\sum_{k=1}^{n}a_k}{n}=a

Dimostrazione

Per \epsilon>0 esiste un n_0(\epsilon ) per cui per n \geq n_0( \epsilon ) succede che

|a_n-a|< \frac{\epsilon }{2}

Perciò per n sufficientemente grande si può scrivere:

|\frac{\sum_{k=1}^{n}a_k}{n}-a|=|\frac{\sum_{k=1}^{n}\left (a_k-a  \right )}{n}|\leq \frac{\sum_{k=1}^{n} |a_k-a  |}{n}=
=\frac{\sum_{k=1}^{n_0(\epsilon )} |a_k-a  | + \sum_{k=n_0(\epsilon )+1}^{n} |a_k-a  |}{n}\leq \frac{\epsilon}{2}\frac{\left (n-n_0(\epsilon )  \right )}{n}+\frac{\epsilon}{2}< \epsilon
Servo, dai a costui una moneta, perché ha bisogno di trarre guadagno da ciò che impara.
Euclide.
Avatar utente
Foto UtenteIanero
7.754 5 8 13
Master EY
Master EY
 
Messaggi: 4110
Iscritto il: 21 mar 2012, 15:47

1
voti

[6] Re: Erdős e progressioni aritmetiche

Messaggioda Foto Utentefairyvilje » 14 lug 2015, 22:59

Infatti, ho anche cercato su qualche libro che ho ma non avevo trovato nulla :). Grazie.
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
12,9k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2683
Iscritto il: 24 gen 2012, 19:23

0
voti

[7] Re: Erdős e progressioni aritmetiche

Messaggioda Foto UtenteIanero » 14 lug 2015, 23:00

Grazie a te per l'interesse :D
Servo, dai a costui una moneta, perché ha bisogno di trarre guadagno da ciò che impara.
Euclide.
Avatar utente
Foto UtenteIanero
7.754 5 8 13
Master EY
Master EY
 
Messaggi: 4110
Iscritto il: 21 mar 2012, 15:47

3
voti

[8] Re: Erdős e progressioni aritmetiche

Messaggioda Foto UtenteIanero » 9 set 2015, 15:47

C'è un problema con il Lemma, per fortuna risolvibile.
La dimostrazione non è corretta perché non tiene conto di crescite di tipo diverso da quella della potenza/radice.
Ad esempio mi è stato fatto notare giustamente da un Prof. che esistono successioni del tipo:

a_n=n \log n

che hanno media degli spazi infinita ma con la serie associata agli inversi ugualmente divergente.

Occorre pertanto modificare la dimostrazione del Lemma (in realtà l'ho rifatta in modo completamente diverso) per tenere conto di queste occasioni.
Ciò che occorre realmente sfruttare è la seconda ipotesi, ovvero che i vari a_n siano tutti naturali.

Infatti i termini di a_n=n \log n non sono affatto tutti naturali. Gli unici di questo insieme appartengono alla sottosuccessione estratta:

a_n=b^n n

dove con b ho indicato la base, intera positiva, del logaritmo.

Questo era solo un indizio, procedo con la nuova dimostrazione del Lemma:

Lemma: Dato un insieme numerabile di interi positivi A la serie associata \sum_{a_n \in A} \frac{1}{a_n} diverge se e solo se gli elementi di A sono distribuiti in modo tale che la media degli spazi tra essi sia finita.

s_n=a_{n+1}-a_n

\overline{s_n}^N = \frac{\sum_{n=1}^{N} s_n }{N}

\overline{s_n}^\infty = \lim_{N \rightarrow \infty} \frac{\sum_{n=1}^{N} s_n }{N}

Dimostriamo prima che se \overline{s_n}^\infty < \infty allora \sum_{a_n \in A} \frac{1}{a_n} = \infty...



s_M=\max_i s_i

\sum_{a_n \in A} \frac{1}{a_n} \geq \sum^\infty _{n=1} \frac{1}{s_M \cdot n} = \infty

Dimostriamo invece adesso che se \overline{s_n}^\infty = \infty allora \sum_{n \in A} \frac{1}{n} < \infty...

poiché siamo nei naturali il caso peggiore che si possa presentare è quello di spazi crescenti (perché per ipotesi la media deve divergere) con incrementi unitari (minimo possibile per restare nei naturali) effettuati ad intervalli non regolari.

Si tratta quindi di una successione definita come segue:

a_n=\left\{\begin{matrix}a_{n+1}=a_n+1 \; , \; 0<n \leq l_1
\\ a_{n+1}=a_n+2 \; , \; l_1<n \leq l_2
\\ a_{n+1}=a_n+3 \; , \; l_2<n \leq l_3
\\ ...
\\ a_{n+1}=a_n+k \; , \; l_{k-1}<n \leq l_k
\\ ...

\end{matrix}\right.

con l_i \in \mathbb{N}, a_0 \in \mathbb{N}, k \in \mathbb{N}.



Considero la permutazione \left \{ l_1', l_2',... \right \} di \left \{ l_1, l_2,... \right \} che verifica l'_{i+1} \leq l_i' per ogni i. Si ha quindi che l_1' = \max_i l_i.

Ora si ha che:

\sum_{a_{n} \in A}^{}{\frac{1}{a_{n}}}=\sum_{n=1}^{l_{1}}{\frac{1}{n}}+\sum_{n=l_{1}+1}^{l_{2}}{\frac{1}{2n}}+\sum_{n=l_{2}+1}^{l_{3}}{\frac{1}{3n}}+... \leq

\leq \sum_{n=1}^{l_{1}'}{\frac{1}{n}}+\sum_{n=l_{1}'+1}^{l_{2}'}{\frac{1}{2n}}+\sum_{n=l_{2}'+1}^{l_{3}'}{\frac{1}{3n}}+... \leq

\leq \sum_{n=1}^{l_{1}'}{\frac{1}{n}}+\sum_{n=l_{1}'+1}^{2l_{1}'}{\frac{1}{2n}}+\sum_{n=2l_{1}'+1}^{3l_{1}'}{\frac{1}{3n}}+...\; =

= H_{l_{1}'}+\frac{1}{2}\left( H_{2l_{1}'}-H_{l_{1}'} \right)+\frac{1}{3}\left( H_{3l_{1}'}-H_{2l_{1}'} \right)+...=

= \sum_{k=1}^{\infty }{\frac{H_{k\cdot l_{1}'}-H_{\left( k-1 \right) \cdot l_{1}'}}{k}}<\; \infty

Che è convergente per il criterio del confronto.

dove H_{n}=\sum_{k=1}^{n}{\frac{1}{k}}, H_0=0.

Questo conclude la dimostrazione con entrambe le implicazioni.
Servo, dai a costui una moneta, perché ha bisogno di trarre guadagno da ciò che impara.
Euclide.
Avatar utente
Foto UtenteIanero
7.754 5 8 13
Master EY
Master EY
 
Messaggi: 4110
Iscritto il: 21 mar 2012, 15:47

1
voti

[9] Re: Erdős e progressioni aritmetiche

Messaggioda Foto Utentefairyvilje » 9 set 2015, 15:54

Ci sono dei problemi con latex :).
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
12,9k 4 9 12
G.Master EY
G.Master EY
 
Messaggi: 2683
Iscritto il: 24 gen 2012, 19:23

0
voti

[10] Re: Erdős e progressioni aritmetiche

Messaggioda Foto UtenteIanero » 9 set 2015, 15:57

Credo di aver risolto, ti si vede tutto?
Servo, dai a costui una moneta, perché ha bisogno di trarre guadagno da ciò che impara.
Euclide.
Avatar utente
Foto UtenteIanero
7.754 5 8 13
Master EY
Master EY
 
Messaggi: 4110
Iscritto il: 21 mar 2012, 15:47

Prossimo

Torna a Matematica generale

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti