nombre de diviseurs du pgcd

borde

Bonjour,

Les sujets de théorie multiplicative des nombres se faisant rares ces derniers temps, je propose ce petit exercice à titre de passe-temps.


Dans la suite, $\tau(n)$ (resp. $\sigma(n)$) désigne le nombre (resp. la somme) des diviseurs (positifs) de $n$. Soit $N \geqslant 1$ entier.

Chacun connaît l'estimation : $$\sum_{n \leqslant N} \tau(n) \leqslant c_1 N \ln N$$ où $c_1>0$ est une constante absolue effectivement calculable (on peut prendre $c_1=2$ si $N \geqslant 6$, par exemple).

Cette estimation s'avère en fait être le bon ordre de grandeur puisque, via un théorème dû à Bottorff (1971), on a : $$\sum_{n \leqslant N} \tau(n) \geqslant N \ln N,$$ et le célèbre problème des diviseurs de Dirichlet énonce que : $$\sum_{n \leqslant N} \tau(n) = N \ln N + (2 \gamma -1) N + O(N^{1/2}),$$ l'exposant optimal dans le terme d'erreur n'étant toujours pas connu.


L'exercice proposé ci-dessous est une variante de ce calcul.


{\bf Enoncé}. Montrer que : $$\sum_{n \leqslant N} \tau(\mathrm{pgcd}(n,N)) \leqslant \frac {N^2}{\varphi(N)} \leqslant c_2 N \ln \ln N.$$ (on peut prendre $c_2 = 2,59$ dès que $N \geqslant 7$).


{\it Indication}. La fonction $\sigma$ n'est pas loin.


Good luck,


Borde.

borde

(Encore) peu de succès pour ce sujet.

Il y a plusieurs méthodes de résolution. Par exemple, on peut noter que la fonction arithmétique $f_N : n \mapsto f_N(n) = \tau (\mathrm {pgcd}(n,N))$ est clairement multiplicative, et il s'agit ni plus ni moins d'estimer une somme d'une fonction multiplicative (il y a beaucoup d'outils pour ça).

On peut aussi effectuer le changement de variable $d = \mathrm {pgcd}(n,N)$ et poser $n = kd$ et $N=hd$ avec $\mathrm {pgcd}(h,k)=1$.


Borde.

rémi

Merci pour les indications. J'aimerai que tu fasses un peu durer le suspense si possible car je n'ai pas énormément de temps mais en tous cas je regarde.

borde

OK.

Borde.

borde

Je donnerai une solution dans la soirée.

Borde.

bs

Et pourtant, le chapitre 4, y compris ses exemples et exercices, a été revisité avec attention, feuilles et crayon à la main...
A ce soir.

borde

Je comprends, et il est vrai qu'une réponse possible passe par une technique similaire au théorème 4.24.

Ceci dit, le peu de succès (apparent) rencontré par ce sujet montre l'une ou l'autre des deux choses suivantes :

(i) Le calcul n'est pas si évident que cela,

ou bien (non exclusif)

(ii) Il n'offre pas beaucoup d'intérêt.

Je pense pourtant qu'il est bon de voir la différence entre les deux sommes précédentes.


Pour ceux que cela peut intéresser, outre pour donner un exercice, cette somme se rencontre dans certains éléments de certaines matrices entières (appelées matrices de Redheffer), dont certains invariants (déterminants, valeurs propres et singulières, normes, etc) ont des significations arithmétiques fortes.


Borde.

rémi

Personnellement, je n'ai pu plancher que par petites tranches de 30 minutes et il faut bien le dire, bien qu'ayant ton livre, je n'ai pas encore planché sur tous les chapitres comme je le voudrais.

En tous cas merci de nous proposer ces exercices.

PS : Comme ça je pourrai comparer avec ce que j'aurai fait et si j'ai fait autrement, je viendrai exposer ma solution.

gilles benson

bonsoir, je n'ai pas cherché de solution à ta question , borde, ce qui ne veut pas dire que je ne le ferais pas dans un futur proche; répondre à ceci nécessite un certain investissement en temps et de la disponibilité intellectuelle. Ce qui est frustrant avec ce système de forum, c'est cet aspect implacable du défilement de chaque question qui repousse la précédente vers l'oubli; en postant un élément sérieux de réponse d'ici deux jours tu laisses le temps à certains de s'intéresser
à ta question sans passer par l'aspect consumériste vite lu, mal réfléchi, mal compris et pourtant solution non méritée à la fin...

borde

Je suis d'accord avec cette analyse, et c'est là le jeu du forum. Mais il est vrai que mes petites interventions bidons ci-dessus ont servi à le maintenir à flot (et ce n'était là que leur seul et unique but, évidemment, comme chacun a pu s'en rendre compte...), ce qui est une des caractéristiques du forum, et permet de ne pas laisser mourir un sujet trop vite.

D'autre part, il est fort possible que cet exercice (qui existe peut-être déjà dans la littérature, mais je ne l'ai pas vu dans mes archives) demande néanmoins du temps pour sa résolution.

J'ai fait ce calcul ce week-end, et sa résolution n'est pas immédiate. Voici une réponse possible parmi d'autres. Le changement $d = \mathrm{pgcd}(n,N)$ donne : $$\sum_{n \leqslant N} \tau(\mathrm{pgcd}(n,N)) = \sum_{d \mid N} \tau(d) \sum_{\substack { k \leqslant N/d \\ \mathrm {pgcd}(k,N/d) = 1}} 1 = \sum_{d \mid N} \tau(d) \varphi (N/d) = (\tau \ast \varphi)(N),$$ où $f \ast g$ est le produit de convolution de Dirichlet usuel.

A partir de là, ou bien on sait que $\tau \ast \varphi = \sigma$, ou bien on ne le sait pas, mais l'on déduit que la somme est multiplicative puisque $\tau$ et $\varphi$ le sont, et on la calcule alors sur les puissances de nombres premiers pour vérifier qu'elle vaut bien $\sigma$.

On a donc là une expression inédite de la somme des diviseurs d'un entier : $$\sum_{n \leqslant N} \tau(\mathrm{pgcd}(n,N)) = \sigma(N).$$

Pour la fin, il s'agit d'utiliser des résultats existants, comme par exemple :

(i) $$\frac {N^2}{\zeta(2) \varphi(N)} \leqslant \sigma(N) \leqslant \frac {N^2}{\varphi(N)}$$ (voir Hardy \& Wright),

(ii) Pour $N \geqslant 7$, on a : $$\sigma(N) < 2,59 N \ln \ln N$$ (résultat dû à Ivic),

(iii) Pour $N \geqslant 3$, on a : $$\frac {N}{\varphi(N)} < e^{\gamma} \ln \ln N + \frac {2,51}{\ln \ln N}$$ (résultat dû à Rosser \& Schoenfeld).


Il y a d'autres solutions possibles. S'il y en a qui en ont trouvé d'autres, qu'ils n'hésitent pas à les mettre.


Merci à tous,


Borde.

B.......t

Et si on mettait ppcm à la place de pgcd ...

rémi

Borde, je n'ai pas trouvé mieux. On s'y attendait
Maintenant je voudrai répondre à tes interrogations:
En effet le calcul n'est pas si évident que cela. Comme bs j'avais parié sur le chapitre 4 de ton livre et a priori c'était une bonne idée.
Par rapport à la réponse que tu donnes je me suis rendu compte que, pour moi du moins, poser $d = \mathrm{pgcd}(n,N)$ (qui est assez naturel) n'était pas si facilement manipulable par manque d'habitude sans doute.
Sorti de cette difficulté, on arrivait en effet facilement à : $$\sum_{n \leqslant N} \tau(\mathrm{pgcd}(n,N)) = \sigma(N).$$
Ensuite conclure de la même manière que toi m'est impossible car mes connaissances sont moindres et je ne connaissais pas ces inégalités. Je n'ai malheureusement pas (encore) le Hardy & Wright mais évidemment ça donne envie de se le procurer.
(En passant, c'est mieux en français ou en anglais en admettant qu'on se débrouiile assez en anglais).
Pour conclure oui c'est intéressant mais à mon avis un peu au dessus du niveau moyens de ceux aiment l'arithmétique ici (je ne sais pas ce qu'en pense les autres ?).
Ceci dit ce type de question aide à progresser mais est aussi propice au manque de réponse je crois.

Si on remplace par ppcm ne m'a malheureusement pas plus inspiré mais par contre je n'ai pas d'intuition sur par quel bout le prendre.

borde

Bonsoir à tous,

Rémi : OK pour ton argumentation, qui rejoint celle de Gilles plus haut.

Benoit : le calcul me semble plus délicat, mais voici une minoration possible. Pour faire comme les anglo-saxons, je note $(n,N)$ (resp. $[n,N]$) le pgcd (resp. le ppcm) de $n$ et $N$. On a : $$\sum_{n \leqslant N} \tau ([n,N]) \geqslant \tau(N) \sum_{\substack {n \leqslant N \\ (n,N) = 1}} \tau(n) \geqslant \tau(N) \left ( \prod_{p \mid N} 3^{-1} \right ) \sum_{n \leqslant N} \mu^2(n) \tau(n) \gg \tau(N) 3^{-\omega(N)} N \ln N,$$ sauf erreur, bien entendu ($\mu$ est la fonction de Möbius et $\omega(n)$ compte le nombre de facteurs premiers (distincts) de $n$).


Borde.

B......t

C'est pas glop donc.

Pour le pgcd ton calcul se généralise facilement sauf erreur:

$$\sum_{n \leqslant N} \sigma_{z+1}(\mathrm{pgcd}(n,N)) = N\sigma_{z}(N)$$


Où $\sigma_z$ dénote la somme des diviseurs à la puissance $z$.

B.........t

Ca me fait penser à un déterminant : soit $f$ une fonction définie sur $\N$ et soit la matrice carrée $M_n$ d'ordre $n$ de terme $m_{i,j}=f(\mathrm{pgcd}(i,j))$. Alors il existe une formule pour le déterminant de $M_n$ que je vous laisse chercher. Je donnerai la réponse ce soir.