forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 23 Σεπ 2018, 02:44

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 8 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Μεγάλα σύνολα πρώτων
ΔημοσίευσηΔημοσιεύτηκε: 25 Ιουν 2010, 19:02 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 01 Ιουν 2008, 21:18
Δημοσ.: 1160
Τοποθεσια: Αθήνα
Δίνεται ένα σύνολο P πρώτων αριθμών τέτοιο που \sum_{p\in P}\frac{1}{p}=\infty. Αν f(x) είναι το πλήθος των n\leq x που δεν διαιρούνται με κανέναν p\in P, να δειχτεί ότι \lim_{x\to\infty }\frac{f(x)}{x}=0.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Μεγάλα σύνολα πρώτων
ΔημοσίευσηΔημοσιεύτηκε: 25 Ιουν 2010, 21:22 
Χωρίς σύνδεση

Εγγραφη: 18 Φεβ 2009, 01:42
Δημοσ.: 49
Καταρχάς τό σύνολον P είναι άπειρο, P=\{p_1<p_2<\cdots<p_n<\cdots\}. Θέτουμε γιά κάθε n, f_n(x) νά είναι τό πλήθος τών θετικών ακεραίων \leq x οι οποίοι δέν διαιρούνται από κανέναν από τούς p_1,p_2,\ldots,p_n. Προφανώς f(x)\leq f_n(x). Συμβολίζουμε μέ q_n τό γινόμενον τών p_1,p_2,\ldots,p_n, καί έχουμε ότι f_n(q_n)=f_n\left(\prod_{1\leq i\leq n}p_i\right) είναι ακριβώς τό πλήθος τών k\in\{1,\ldots,q_n\} που είναι σχετικώς πρώτα μέ τό q_n. Τό πλήθος αυτό μάς δίνει η συνάρτησις \phi τού Euler, f_n(q_n)=\phi(q_n)=\prod_{1\leq i\leq n}(p_i-1).
Παρατηρούμε επίσης ότι γιά κάθε m\geq 1, f_n(mq_n)=m\cdot f_n(q_n), αφού άν k\in\{1,\ldots, mq_n\} μπορούμε νά γράψουμε k=lq_n + k&#39; μέ 0\leq l<m καί k&#39;\in\{1,\ldots,q_n\}, καί τότε τό k είναι σχετικώς πρώτο μέ τό q_n άν καί μόνον άν τό k&#39; είναι σχετικώς πρώτο μέ τό q_n.

Γιά νά τελειώσουμε, παρατηρούμε ότι επειδή \sum_{1\leq i<\infty}\frac{1}{p_i}=\infty, ισχύει \lim_{n\to\infty}\frac{f_n(q_n)}{q_n}=\lim_{n\to\infty}\prod_{1\leq i\leq n}\left(1-\frac{1}{p_i}\right)=0, άρα γιά κάθε \varepsilon>0 υπάρχει n_0(\varepsilon) ώστε \frac{f_{n_0}(q_{n_0})}{q_{n_0}}<\varepsilon/2. Τότε γιά κάθε x>q_{n_0}, υπάρχει μοναδικό m\geq 1 ώστε mq_{n_0}<x\leq (m+1)q_{n_0}, καί άρα \frac{f(x)}{x}\leq\frac{f_{n_0}(x)}{x}\leq \frac{f_{n_0}((m+1)q_{n_0})}{mq_{n_0}}= \frac{(m+1)f_{n_0}(q_{n_0})}{mq_{n_0}}<\frac{m+1}{m}\varepsilon/2\leq\varepsilon.


Τελευταία επεξεργασία απο Σελάν@ την 15 Ιούλ 2010, 11:47, επεξεργάστηκε 1 φορές συνολικά.

Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Μεγάλα σύνολα πρώτων
ΔημοσίευσηΔημοσιεύτηκε: 14 Ιούλ 2010, 16:13 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 04 Μάιος 2006, 13:21
Δημοσ.: 666
Συγχαρητηρια Βεατρικη !

Ομοια δειχνεται και η f(x) \leq \frac{x}{\exp (\sum_{p \in P, p \leq \log x}1/p)}+O(x^{\log 2})

Ένα δεύτερο ερώτημα είναι αν υπαρχει αντιπαραδειγμα για το αντίστροφο της άσκησης.


Τελευταία επεξεργασία απο sofos την 14 Ιούλ 2010, 17:09, επεξεργάστηκε 2 φορές συνολικά.

Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Μεγάλα σύνολα πρώτων
ΔημοσίευσηΔημοσιεύτηκε: 14 Ιούλ 2010, 16:35 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 01 Ιουν 2008, 21:18
Δημοσ.: 1160
Τοποθεσια: Αθήνα
Το πιο απλό φράγμα είναι x\prod_{p\leq t, p\in P}\left ( 1-\frac{1}{p}\right )+O(2^t) για κάθε t\geq 2. Μετά μπορείς να επιλέξεις t=\log x και να πεις ότι το γινόμενο φράσσεται από \exp\big ( -\sum_{p\leq\log x,p\in P}\frac{1}{p}\big ).


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Μεγάλα σύνολα πρώτων
ΔημοσίευσηΔημοσιεύτηκε: 14 Ιούλ 2010, 17:10 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 04 Μάιος 2006, 13:21
Δημοσ.: 666
ναι αυτο ειχα υποψη,

ειναι ασκηση στο βιβλιο ασκησεων του Murty

το βασικο ερωτημα ομως ειναι για την ισχυ του αντιστροφου


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Μεγάλα σύνολα πρώτων
ΔημοσίευσηΔημοσιεύτηκε: 14 Ιούλ 2010, 21:09 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 01 Ιουν 2008, 21:18
Δημοσ.: 1160
Τοποθεσια: Αθήνα
Ίσως να βγει αν στη θέση του Ερατοσθένη χρησιμοποιήσεις τον Brun. Αυτός δίνει και κάτω φράγματα, δες π.χ. στο 4ο κεφάλαιο του Tenenbaum (σελ. 58). Θα πας να εκτιμήσεις από κάτω το πλήθος των n\leq x που είναι πρώτοι προς το P(y)=\prod_{p\in P,p\leq y}p. Μετά υποθέτοντας ότι η \sum_{p\in P}\frac{1}{p} συγκλίνει, κοιτάς αν η f(x)/x είναι μακριά απ' το μηδέν. Μπορεί να δουλεύει μπορεί και όχι.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Μεγάλα σύνολα πρώτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Ιούλ 2010, 11:43 
Χωρίς σύνδεση

Εγγραφη: 18 Φεβ 2009, 01:42
Δημοσ.: 49
Μπορεί νά λέω καί βλακείες, αλλά μού φαίνεται πως αντιπαράδειγμα δέν πρόκειται νά βρείς, αφού ισχύει καί τό αντίστροφο τής ασκήσεως. Δηλαδή

Παράθεση:
Δίνεται ένα σύνολο P πρώτων αριθμών τέτοιο που \sum_{p\in P}\frac{1}{p}<\infty. Αν f(x) είναι το πλήθος των n\leq x που δεν διαιρούνται με κανέναν p\in P, τότε υπάρχουν σταθερά \alpha\in (0,1) καί x_0\geq 1 ώστε γιά κάθε x>x_0 νά ισχύει \frac{f(x)}{x}\geq\alpha.


Τά πρώτα που χρησιμοποιήσαμε γιά τό ευθύ μπορούμε νά τά ξαναγράψουμε χωρίς νά χαλάσει τίποτε:
έστω P=\{p_1<p_2<\cdots<p_n<\cdots\}, πεπερασμένο ή άπειρο. Θέτουμε γιά κάθε n, f_n(x) νά είναι τό πλήθος τών θετικών ακεραίων \leq x οι οποίοι δέν διαιρούνται από κανέναν από τούς p_1,p_2,\ldots,p_n. Προφανώς f(x)\leq f_n(x). Συμβολίζουμε μέ q_n τό γινόμενον τών p_1,p_2,\ldots,p_n, καί έχουμε ότι f_n(q_n)=f_n\left(\prod_{1\leq i\leq n}p_i\right) είναι ακριβώς τό πλήθος τών k\in\{1,\ldots,q_n\} που είναι σχετικώς πρώτα μέ τό q_n. Τό πλήθος αυτό μάς δίνει η συνάρτησις \phi τού Euler, f_n(q_n)=\phi(q_n)=\prod_{1\leq i\leq n}(p_i-1).

Παρατηρούμε επίσης ότι γιά κάθε m\geq 1, f_n(mq_n)=m\cdot f_n(q_n), αφού άν k\in\{1,\ldots, mq_n\} μπορούμε νά γράψουμε k=lq_n + k&#39; μέ 0\leq l<m καί k&#39;\in\{1,\ldots,q_n\}, καί τότε τό k είναι σχετικώς πρώτο μέ τό q_n άν καί μόνον άν τό k&#39; είναι σχετικώς πρώτο μέ τό q_n. Άρα άν x>q_n, θά υπάρχει μοναδικό m\geq 1 ώστε mq_n<x\leq (m+1)q_n, καί τότε \frac{f_n(x)}{x}\geq\frac{f_n(mq_n)}{(m+1)q_n}= \frac{mf_n(q_n)}{(m+1)q_n}\geq\frac{1}{2}\prod_{1\leq i\leq n}\left(1-\frac{1}{p_i}\right).

Επειδή τώρα \sum_{1\leq i<\infty}\frac{1}{p_i}<\infty, ισχύει γιά κάθε n ότι \prod_{1\leq i\leq n}\left(1-\frac{1}{p_i}\right)\geq\lim_{n\to\infty}\prod_{1\leq i\leq n}\left(1-\frac{1}{p_i}\right)=\alpha>0. Γιά τόν ίδιο λόγο επίσης, υπάρχει n_0 ώστε \sum_{n_0<i<\infty}\frac{1}{p_i}<\frac{\alpha}{4}.

Θέτουμε g(x) νά είναι το πλήθος των n\leq x που δεν διαιρούνται με κανέναν p_i\in P, i>n_0. Τό συμπλήρωμα αυτού τού συνόλου είναι ακριβώς τά πολλαπλάσια τών p_i\in P, i>n_0, άρα x-g(x)\leq\sum_{n_0<i<\infty}(\textrm{\gr πολ/σια τού }p_i\leq x) \leq\sum_{n_0<i<\infty}\frac{x}{p_i}<\frac{\alpha}{4}x. Ας θυμηθούμε ότι εμείς ψάχνουμε τό πλήθος f(x) τής τομής δύο συνόλων, αυτού που περιέχει τά n\leq x τά οποία δέν διαιρούνται από κανέναν από τούς p_1,\ldots,p_{n_0}, καί αυτού που περιέχει τά n\leq x τά οποία δέν διαιρούνται από κανέναν p_i\in P, i>n_0. Από τά παραπάνω, τό πρώτο σύνολο έχει πληθάριθμο f_{n_0}(x)\geq\frac{\alpha}{2}x γιά κάθε x>q_{n_0}, ενώ τό δεύτερο σύνολο έχει πληθάριθμο g(x)\geq (1-\frac{\alpha}{4})x. Έπεται ότι η τομή τους θά 'χει πληθάριθμο f(x)\geq\frac{\alpha}{4}x, αρκεί νά θεωρήσουμε x>q_{n_0}.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Μεγάλα σύνολα πρώτων
ΔημοσίευσηΔημοσιεύτηκε: 15 Ιούλ 2010, 16:33 
Χωρίς σύνδεση

Εγγραφη: 18 Φεβ 2009, 01:42
Δημοσ.: 49
Τώρα που τό ξανασκέφτομαι, άν επαναλάβουμε τήν παραπάνω απόδειξι πιό προσεκτικά, μπορούμε νά βρούμε ακριβώς τό \lim_{x\to\infty}\frac{f(x)}{x} δείχνοντας ότι είναι ίσο μέ \prod_{p\in P}(1-\frac{1}{p})=\alpha.
Πράγματι, γιά κάθε \varepsilon>0 υπάρχει n_0\equiv n_0(\varepsilon) ώστε νά ισχύουν ταυτοχρόνως τά εξής:
i) \prod_{1\leq i\leq n_0}(1-\frac{1}{p_i})\leq\sqrt{1+\varepsilon}\prod_{p\in P}(1-\frac{1}{p}),
ii) \sum_{n_0<i<\infty}\frac{1}{p_i}<\frac{\varepsilon\alpha}{2}.
Τότε, άν ορίσουμε τήν συνάρτησι g όπως πρίν, θά έχουμε ότι x-g(x)<\frac{\varepsilon\alpha}{2}x γιά κάθε x\geq 1.

Βρίσκουμε φυσικόν m_0 ώστε νά ισχύει 1-\frac{\varepsilon}{2}\leq\frac{m_0}{m_0+1}<\frac{m_0+1}{m_0}\leq \sqrt{1+\varepsilon}. Τότε γιά κάθε x>m_0q_{n_0} ισχύει (1-\frac{\varepsilon}{2})\alpha\leq(1-\frac{\varepsilon}{2})\prod_{1\leq i\leq n_0}(1-\frac{1}{p_i}) \leq\frac{f_{n_0}(x)}{x}\leq\sqrt{1+\varepsilon}\prod_{1\leq i\leq n_0}(1-\frac{1}{p_i})\leq (1+\varepsilon)\prod_{p\in P}(1-\frac{1}{p}).

Άρα αρχικώς \frac{f(x)}{x}\leq\frac{f_{n_0}(x)}{x}\leq (1+\varepsilon)\prod_{p\in P}(1-\frac{1}{p}) γιά κάθε x>m_0q_{n_0}. Επίσης, χρησιμοποιώντας πάλι ότι f(x) είναι ο πληθάριθμος ενός υποσυνόλου τών n\leq x τό οποίο αποτελεί τήν τομή δύο συνόλων, τού ενός μέ πληθάριθμο f_{n_0}(x)\geq (\alpha-\frac{\varepsilon\alpha}{2})x, καί τού άλλου μέ πληθάριθμο g(x)> (1-\frac{\varepsilon\alpha}{2})x, έχουμε τελικώς ότι f(x)\geq (1-\varepsilon)\alpha\cdot x (αφού η ένωσις τών συμπληρωμάτων τών παραπάνω συνόλων έχει τό πολύ (1-\alpha+2\frac{\varepsilon\alpha}{2})x στοιχεία).


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 8 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group