Un limite "diofantino"

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Un limite "diofantino"

Messaggio da Ido Bovski » 20 lug 2012, 12:45

EDIT: spostato in MNE, visto che c'è un limite. ma_go

Dati $a, b\in\mathbb{N}: (a, b)=1$, indichiamo con $S(n)$ il numero delle soluzioni non-negative dell'equazione
$$ax+by=n.$$
Calcolare
$$\lim_{n\to\infty} \frac{S(n)}{n}.$$

frod93
Messaggi: 42
Iscritto il: 17 lug 2012, 21:32
Località: Perugia

Re: Un limite "diofantino"

Messaggio da frod93 » 21 lug 2012, 00:21

In teoria (credo) l'equazione diofantea ha soluzioni solo se $ n = (a,b) $, quindi se $ n \to +\infty $ abbiamo $ S(n)=0 $ e l'intero limite va a $ 0 $. Erro? (probabile)
$Q.E.D.$

ant.py
Messaggi: 140
Iscritto il: 18 set 2011, 11:36

Re: Un limite "diofantino"

Messaggio da ant.py » 21 lug 2012, 02:29

frod93 ha scritto:In teoria (credo) l'equazione diofantea ha soluzioni solo se $ n = (a,b) $, quindi se $ n \to +\infty $ abbiamo $ S(n)=0 $ e l'intero limite va a $ 0 $. Erro? (probabile)

Beh si.. In realtà basta che $ gcd(a, b) | n $ affinché la diofaentea abbia infinite soluzioni; ora non so cosa cambia se consideriamo solo quelle non negative; è ovvio che bisogna prendere n più grande di una certa soglia (alcuni dicono ab - a - b ma non ne sono sicuro) ma non ho idee per il momento..

ps e poi se $ S(n) \to 0 $il limite era indeterminato :-P
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "

frod93
Messaggi: 42
Iscritto il: 17 lug 2012, 21:32
Località: Perugia

Re: Un limite "diofantino"

Messaggio da frod93 » 21 lug 2012, 11:48

ant.py ha scritto:ps e poi se $ S(n) \to 0 $il limite era indeterminato :-P
$ \frac{0}{\infty} $ non è inderetminata D:
$Q.E.D.$

ant.py
Messaggi: 140
Iscritto il: 18 set 2011, 11:36

Re: Un limite "diofantino"

Messaggio da ant.py » 21 lug 2012, 13:42

frod93 ha scritto:
ant.py ha scritto:ps e poi se $ S(n) \to 0 $il limite era indeterminato :-P
$ \frac{0}{\infty} $ non è inderetminata D:

Ahah hai ragione scusami :oops:

Ora aspettiamo qualcuno che risolva il problema.. O magari un hint :-P
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "

EvaristeG
Site Admin
Messaggi: 4791
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Un limite "diofantino"

Messaggio da EvaristeG » 21 lug 2012, 14:27

:) signori, ma proprio non sapete come addestrar codeste bestie?
Prima se ne conquista la fiducia con piccoli pezzetti del loro cibo preferito, ovvero i casi particolari:
a=b=1
si cercano le soluzioni di x+y=n NON NEGATIVE, quindi $ x,y\geq 0 $, che non è mica difficile calcolare, no?
(0,n), (1,n-1), (2,n-2), .... , (n,0)
che sono n+1, quindi S(n)=n+1 e dunque il limite in questo caso è 1.
a=1, b generico
volete x+by=n e diciamo che $ n\geq b $ altrimenti col fischio che sono non negative... bene, quindi x=n-by, ma $ x\geq 0 $ per cui $ n\geq by $ e quindi y andrà da 0 a $ [n/b] $ (dove con [d] indico la parte intera). Per ogni tale y c'è una x non negativa, e solo per quelle, quindi S(n)=[n/b] e dunque
$ \displaystyle\lim_{n\to\infty} \frac{S(n)}{n}=\lim_{n\to\infty}\frac{[n/b]}{n} $
ma
$ \displaystyle\frac{n-1}{b}\leq [n/b]\leq\frac{n}{b} $
epperò
$ \displaystyle\lim_{n\to\infty}\frac{(n-1)/b}{n}=\frac{1}{b}=\lim_{n\to\infty}\frac{n/b}{n} $
da cui, per il teorema dei carabinieri (è una vita che sogno di usarlo!)
$ \displaystyle\lim_{n\to\infty}\frac{S(n)}{n}=\frac{1}{b} $.
Il caso a generico, b=1 è identico, mutatis mutandis.

Tutto ciò, vergogna e vituperio, potevate farlo anche voi! da qui, orsù, che vi viene in mente per fare il caso generale? Che cambia da quello a questi? Spremetevi le meningi!

ant.py
Messaggi: 140
Iscritto il: 18 set 2011, 11:36

Re: Un limite "diofantino"

Messaggio da ant.py » 21 lug 2012, 15:29

Orsù , cavalier assai Valente, voglia accettare la mia più profonda stima, e voglia altresì ascoltare la castroneria che sto probabilmente per sparare riguardo il caso generale;

Siamo a $ \displaystyle x = \frac{n-by}{a} $.. Come lei ha già osservato, messere, si ha $ y \le [n/b] $

Qui abbiamo una condizione in più : ovvero é necessario che sia $ n - by \equiv 0 \pmod a $ , ovvero $ n \equiv by \pmod a $

Essendo $ \gcd(a,b) = 1 $, esiste l'inverso di b modulo a (giusto? Mi pare di si) .. Moltiplicando per $ b^{-1} $ si ha dunque

$ y \equiv nb^{-1} \pmod a $ Quindi di y adeguati ce ne sono uno ogni a (partendo da $ nb^{-1} $ fino a $ [n/b] $) di conseguenza ce ne sono $ \displaystyle [\frac{n}{ab}] $
e il limite vale $ \displaystyle \frac{1}{ab} $
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "

Avatar utente
Leonida
Messaggi: 61
Iscritto il: 12 set 2011, 19:37
Località: Maserada (Treviso)

Re: Un limite "diofantino"

Messaggio da Leonida » 21 lug 2012, 16:10

@ant.py: occhio, gli $y$ adeguati possono essere $ \displaystyle \left\lfloor \frac{n}{ab}\right\rfloor $ oppure $ \displaystyle\left\lfloor \frac{n}{ab}\right\rfloor +1 $. Ad esempio $ 2x +3y = 11 $ ha come soluzioni non negative $ (4,1) $ e $ (1,3) $ nonostante $ \left\lfloor \frac{11}{6}\right\rfloor = 1 $. Comunque il limite dovrebbe essere giusto :)
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"

EvaristeG
Site Admin
Messaggi: 4791
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Un limite "diofantino"

Messaggio da EvaristeG » 21 lug 2012, 20:57

un po' di decenza, suvvia...le cose si fan per bene.
Se di x come si deve ve n'è uno ogni a a partire da un dato c, fino a [n/b], allora ve ne saranno di sicuro
j=[[n/b]/a] più eventualmente un altro se $ c\leq [n/b]-ja $.
Ne convenite?
Comunque il limite sarà poi sempre lui.

Attenzione: ma è vero che [[n/b]/a]=[n/ba] oppure vi è solo andata bene perché tanto al limite va un po' tutto a ramengo?

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: Un limite "diofantino"

Messaggio da Ido Bovski » 22 lug 2012, 15:03

EvaristeG ha scritto:Attenzione: ma è vero che [[n/b]/a]=[n/ba] oppure vi è solo andata bene perché tanto al limite va un po' tutto a ramengo?
Par brutto lasciare il thread in sospeso, rispondo io.
E' vero: in generale, dati $\alpha\in\mathbb{R}$ e $k\in\mathbb{N}$, vale che $\left\lfloor \frac{\lfloor \alpha \rfloor}{k} \right\rfloor = \left\lfloor \frac{\alpha}{k} \right\rfloor$. Lo dimostro.
Abbiamo che $\frac{\alpha}{k}=\left\lfloor \frac{\alpha}{k} \right\rfloor+\lambda$, dove $\lambda\in\mathbb{R}\cap[0, 1)$, pertanto $\lfloor \alpha \rfloor=\left\lfloor k\left\lfloor \frac{\alpha}{k} \right\rfloor + k\lambda \right\rfloor=k\left\lfloor \frac{\alpha}{k} \right\rfloor+\lfloor k\lambda \rfloor$. Considerando ora che $0\le \frac{\lfloor k\lambda \rfloor}{k}<\lambda<1$, ne segue facilmente la tesi.

Robertopphneimer
Messaggi: 426
Iscritto il: 14 lug 2012, 15:43

Re: Un limite "diofantino"

Messaggio da Robertopphneimer » 28 lug 2012, 16:46

Evariste g che eleganza!! mi hai dato molte idee per molti problemi grazie :D
L'universo è come una sfera dove il centro è ovunque e la circonferenza da nessuna parte.
"Blaise Pascal"

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: Un limite "diofantino"

Messaggio da dario2994 » 30 lug 2012, 18:57

Robertopphneimer ha scritto:Evariste g che eleganza!!
:lol: :lol: :lol:
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Ancora meglio

Messaggio da <enigma> » 30 lug 2012, 19:47

E se invece l'equazione fosse $\displaystyle \sum_{i=1} ^k a_i x_i=n$ con $\gcd (a_1, \dots, a_k)=1$, quanto varrebbe $\displaystyle \lim _{n \rightarrow \infty} \frac {S(n)}{n^{k-1}}$?
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Robertopphneimer
Messaggi: 426
Iscritto il: 14 lug 2012, 15:43

Re: Un limite "diofantino"

Messaggio da Robertopphneimer » 30 lug 2012, 20:46

direi verrebbe una forma indeterminata...$ \frac{\infty}{\infty} $
L'universo è come una sfera dove il centro è ovunque e la circonferenza da nessuna parte.
"Blaise Pascal"

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: Ancora meglio

Messaggio da ma_go » 31 lug 2012, 12:11

<enigma> ha scritto:E se invece l'equazione fosse $\displaystyle \sum_{i=1} ^k a_i x_i=n$ con $\gcd (a_1, \dots, a_k)=1$, quanto varrebbe $\displaystyle \lim _{n \rightarrow \infty} \frac {S(n)}{n^{k-1}}$?
c'è una generalizzazione più debole, e teoricamente più maneggevole, che dovrebbe essere con $\gcd(a_i, a_j) = 1$ per ogni coppia di indici $1\le i,j \le n$. euristicamente mi verrebbe da dire che le due risposte non dovrebbero essere molto diverse, ma ci devo pensare un po' meglio.

Rispondi