Pensez à lire la Charte avant de poster !
Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
1 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Nombres premiers à q dans [1,x]

Envoyé par lolo1975 
lolo1975
Nombres premiers à q dans [1,x]
il y a sept années
Existe-t-il une estimation, non triviale, du nombre d'entiers n de [1,x], premiers à un nombre q (donné). Merci.



Edité 1 fois. La dernière correction date de il y a sept années et a été effectuée par AD.
Re: Nombres premiers à q dans [1,x]
il y a sept années
Oui, la voici :

{\bf Prop}. {\it On a} : $$\sum_{n \leqslant x, \, (n,q) = 1} 1 = x \frac {\varphi(q)}{q} + O \left ( 2^{\omega(q)} \right ),$$ {\it où $\omega(q)$ désigne le nombre de facteurs premiers distincts de $q$}.


{\it Preuve}. En utilisant la fonction indicatrice des entiers $n$ premiers à $q$ et en intervertissant les sommes, il vient : $$\sum_{n \leqslant x, \, (n,q) = 1} 1 = \sum_{d \mid q} \mu(d) \sum_{k \leqslant x/d} 1 = \sum_{d \mid q} \mu(d) \left [ \frac {x}{d} \right ],$$ où $\mu$ est la fonction de Möbius et $[t]$ est la partie entière. L'estimation $[t] = t + O(1)$ conduit à : $$\sum_{n \leqslant x, \, (n,q) = 1} 1 = x \sum_{d \mid q} \frac {\mu(d)}{d} + O \left ( \sum_{d \mid q} |\mu(d)| \right ),$$ et on vérifie (par multiplicativité, par exemple) que : $$\sum_{d \mid q} \frac {\mu(d)}{d} = \frac {\varphi(q)}{q},$$ et $$\sum_{d \mid q} |\mu(d)| = 2^{\omega(q)}.$$

Borde.
lolo1975
Re: Nombres premiers à q dans [1,x]
il y a sept années
Le facteur $2^{\omega(q)} $ est énorme !
Re: Nombres premiers à q dans [1,x]
il y a sept années
Toutes ces estimations ne sont en effet valides que sous certaines conditions, c'est {\it général} dans ce type de problème.


Autrement dit, il n'existe pas (encore) de monde parfait où ces estimations ont un terme d'erreur uniformément valable pour tout entier $q$ !!!


Toutefois, il est connu que $2^{\omega(q)} = q^{(1+o(1)) \ln 2 / \ln \ln q}$, de sorte que cette estimation est non triviale si $x \gg q^{\epsilon}$, ce qui est très raisonnable, compte tenu de la rapidité du calcul effectué, non ?

Maintenant, on aurait pu améliorer ce calcul en utilisant $[t] = t - 1/2 - \psi(t)$ où $\psi(t)$ est la première fonction de Bernoulli. Si $q >1$, la somme correspondant au facteur $1/2$ ci-dessus est alors nulle, et il vient : $$\sum_{n \leqslant x, \, (n,q) = 1} 1 = \frac {x \varphi(q)}{q} - \sum_{d \mid q} \mu(d) \psi \left ( \frac {x}{d} \right ).$$

Malheureusement, une estimation non triviale de la dernière somme est extraordinairement difficile à obtenir.

Borde.
epsilon0
Re: Nombres premiers à q dans [1,x]
il y a sept années
Merci Borde .... pour tout .

Regarder [www.cs.wisc.edu] . pages 55-56 .
Re: Nombres premiers à q dans [1,x]
il y a sept années
De rien, epsilon0 !

Concernant le lien que tu as mis, ce mémoire de D.X. Charles "traîne" depuis longtemps sur le net, et, globalement, c'est un survol assez complet sur les méthodes de crible.

Je lui reproche néanmoins des notations parfois (voire souvent) assez tordues, une typo qui n'est pas très agréable, et des résultats qui ne sont pas toujours optimaux (en particulier au chapitre 4). De plus, dans sa version du théorème de Brun-Titchmarsh (voir chap 4), qui provient de l'article-phare de Montgomery-Vaughan {\it The large sieve}, Mathematika (1973), l'auteur oublie les restrictions importantes sur $q$ concernant la validité de cette inégalité. D'autre part, il aurait^pu (et dû) citer la très élégante version de cette inégalité, {\it issue du même article}, que Montgomery et Vaughan ont établi.

Enfin, tu auras remarqué que le théorème à la fin de la page 56 n'est valide que si $P^{+}(q) < x^{1/5}$, alors que le calcul ci-dessus est vrai pour $q^{\epsilon} \ll x$, avec $\epsilon$ tendant vers $0$ en $1/ \ln \ln q$.

Borde.
Re: Nombres premiers à q dans [1,x]
il y a sept années
A propos, je viens de retrouver un résultat dû à Suryanarayana (1974) sur ce sujet :

{\bf Notations}. $x \geqslant 1$ réel et $q \geqslant 2$ entier tels que $([x],q) = 1$ et on note : $$R(x,q) = \sum_{n \leqslant x, \, (n,q) = 1} 1 - \frac {x \varphi(q)}{q},$$

avec également $\{x\}$ la partie fractionnaire,$\delta(q)$ le nombre de diviseurs sans facteur carré de $q$ et $\displaystyle {\Psi(q) = q \prod_{p \mid q} \left ( 1 + \frac {1}{p} \right )}$ la fonction de Dedekind.



{\bf Th}. {\it Avec les notations ci-dessus, on a} : $$\frac {\Psi(q)}{q} - \frac {\delta(q)}{2} - \frac { \{x \} \varphi(q)}{q} \leqslant R(x,q) \leqslant \frac {\delta(q)}{2} - \frac {\Psi(q)}{q} - \frac { \{x \} \varphi(q)}{q} + 1.$$

Référence : {\bf D. Suryanarayana}, {\it On} $\Delta(x,n) = \varphi(x,n) - x \varphi(n)/n$, Proc. Amer. Math. Soc. {\bf 44}, (1974), 17-21.


L'on remarquera un terme d'erreur pas vraiment éloigné de celui donné ci-dessus.

Borde.
lolo1975
Re: Nombres premiers à q dans [1,x]
il y a sept années
Merci borde .
Dans la formule est ce que le terme de droite est égale a celle de gauche +1 ?
Pouvez vous nous parler de la methode de Hooley ? merci .
Re: Nombres premiers à q dans [1,x]
il y a sept années
Le terme principal de gauche (ie sans le terme avec partie fractionnaire, plus petit que les autres) est l'opposé de celui de droite.

D'autre part, si tu souhaites une {\it inégalité} asymptotique plutôt qu'une égalité, alors on peut, en utilisant les techniques usuelles de sommation de fonctions multiplicatives, arriver à une majoration du type : $$\sum_{n \leqslant x, \, (n,q) = 1} 1 \leqslant e^{\gamma} x \frac {\varphi(q)}{q} \left \{ 1 + O \left ( \frac {1}{\ln x} \right ) \right \}.$$

Par ailleurs, en utilisant des outils de convolution et la méthode de Rankin, je viens d'obtenir pour $3 \leqslant x \leqslant q$ la formule suivante : $$\sum_{n \leqslant x, \, (n,q) = 1} 1 = x \frac {\varphi(q)}{q} + O \left \{ x \left ( \frac {x}{(\ln x)^{\ln x}} \right )^{1 / \ln \ln q} \right \}.$$ Je cherche à avoir une estimation du même style pour $x\geqslant q$, plus intéressant.

Quant à la méthode de Hooley dont tu parles, sur laquelle souhaites-tu des renseignements ?

Borde.
lolo1975
Re: Nombres premiers à q dans [1,x]
il y a sept années
Merci Borde.
Peut-on estimer de même le nombre d'entiers n,de [1,x], tq a.n est congru à l mod( k ), avec a,l et k fixés...?
j'ai vu qq part que "la méthode de Hooley" utilise une estimation de la somme de nombre de diviseurs ...
lolo1975
Re: Nombres premiers à q dans [1,x]
il y a sept années
Hé Borde ... tu es la ....?
Re: Nombres premiers à q dans [1,x]
il y a sept années
Oups...Je n'avais pas vu que tu posais une autre question !...Ceci dit, il est évident que d'autres que moi peuvent répondre aussi, bien sûr !!

Il existe pas mal de méthodes dites "de Hooley", mais, dans ce contexte bien précis, cela ne me dit rien. Ceci dit, pour $a=1$, ton problème est assez simple à résoudre.

Borde.
epsilon0
Re: Nombres premiers à q dans [1,x]
il y a sept années
Le cas a=1 est simple, en general si a premier avec k c'est comme les restes chinois, les solutions sont de la forme n=n0+ m.k.l donc le nombre cherché est [(x-n0)/(k.l)] ... ( [x]= partie entière de x ).
Existe-t-il une solution meilleur ?
Re: Nombres premiers à q dans [1,x]
il y a sept années
Non, je ne pense pas, si ton problème initial porte bien sur les {\bf entiers}. En revanche, ce serait autrement plus compliqué si tu sommais sur les {\bf nombres premiers}.

Borde.
epsilon0
Re: Nombres premiers à q dans [1,x]
il y a sept années
Ma solution est juste donc !
Re: Nombres premiers à q dans [1,x]
il y a sept années
Oui, bien sûr!

Pour des estimations de sommes portant sur des nombres premiers en progressions arithmétiques $p \equiv a \pmod q$ avec $(a,q)=1$, alors plusieurs outils sont à notre disposition selon le niveau de difficulté souhaité (c'est-à-dire essentiellement quel type d'uniformité en $a$/en $q$ on souhaite).

Borde.
isotrope
Re: Nombres premiers à q dans [1,x]
il y a sept années
La solution de epsilon est fausse !
On suppose x non entier.
Le nombre d'entier $n \in [0,x]$ tq $a.n \equiv l \pmod k$ avec $(a,k)=1$ est le nombre de solutions, dans $[0,a.x]$ du système de restes chinois : $m \equiv l \pmod k$ et $m \equiv 0 \pmod a$. C'est aussi le nombre de $m=m_0+h.k.a \in [m_0,a.x+m_0]$ ( avec $m_0$ solution particulière ) donc c'est le nombre des $h \in [0,x/k]$ donc c'est $[x/k]+1$.
Alors que $[(x-m_0])/k]$ dépend de $m_0]$ !!! qui peut être grand...
J'attends vos remarques.
epsilon0
Re: Nombres premiers à q dans [1,x]
il y a sept années
oui... je crois ...
Auteur:

Votre adresse électronique:


Sujet:


Mesure anti-SPAM :
Recopiez le code que vous voyez dans le champ ci-dessous. Cette mesure sert à bloquer les robots informatiques qui tentent de polluer ce site.
 **     **  ********   **      **        **  **    ** 
 **     **  **     **  **  **  **        **  **   **  
 **     **  **     **  **  **  **        **  **  **   
 *********  **     **  **  **  **        **  *****    
 **     **  **     **  **  **  **  **    **  **  **   
 **     **  **     **  **  **  **  **    **  **   **  
 **     **  ********    ***  ***    ******   **    ** 
Message:
A lire avant de poster!
Liste des forums - Statistiques du forum

Total
Discussions: 95 517, Messages: 870 049, Utilisateurs: 8 936.
Notre dernier utilisateur inscrit ploufe.


Ce forum
Discussions: 2 953, Messages: 35 152.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page
Autres...