Nombres premiers à q dans [1,x]

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.



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par borde.

Le facteur $2^{\omega(q)} $ est énorme !



Edité 1 fois. La dernière correction date de il y a cinq années et a été effectuée par AD.

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.



Edité 3 fois. La dernière correction date de il y a six années et a été effectuée par borde.

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.



Edité 2 fois. La dernière correction date de il y a six années et a été effectuée par borde.

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.



Edité 2 fois. La dernière correction date de il y a six années et a été effectuée par borde.

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.



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par borde.

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.

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.

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.

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.



Edité 1 fois. La dernière correction date de il y a six années et a été effectuée par AD.