Nombres premiers à q dans [1,x]
dans Arithmétique
Existe-t-il une estimation, non triviale, du nombre d'entiers n de [1,x], premiers à un nombre q (donné). Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
{\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.
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.
Regarder http://www.cs.wisc.edu/~cdx/Sieve.pdf . pages 55-56 .
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.
{\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.
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 .
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.
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 ...
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.
Existe-t-il une solution meilleur ?
Borde.
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.
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.