Somme des sommes des diviseurs et restes.
dans Arithmétique
Arithméticiens,
En cette fin d'année, je vous propose de déterminer la somme:
$$\sum_{n=1}^{a} \Big(\sigma(n)+(a)_n\Big)$$
où $a$ est un entier naturel donné, la fonction $\sigma(n)$ représente la somme des diviseurs positifs de $n$ et $(a)_n$ le reste de la division euclidienne de $a$ par $n$.
Bonne recherche,
Al-Kashi
En cette fin d'année, je vous propose de déterminer la somme:
$$\sum_{n=1}^{a} \Big(\sigma(n)+(a)_n\Big)$$
où $a$ est un entier naturel donné, la fonction $\sigma(n)$ représente la somme des diviseurs positifs de $n$ et $(a)_n$ le reste de la division euclidienne de $a$ par $n$.
Bonne recherche,
Al-Kashi
Réponses
-
Non pas que je me sente capable de trouver un résultat convaincant avant les autres, mais histoire d'y réfléchir un peu quand même, tu comptes $1$ et $n$ dans $\sigma(n)$ ou pas ?
-
Oui, on compte tous les diviseurs, y compris $1$ et $n$.
Si tu calcules les quelques premiers termes à la main, ou à la machine, tu vas très vite trouver la bonne conjecture ! -
C'est ce que je voulais faire, mais je n'étais pas sûr avec les diviseurs, parce que parfois on choisit d'/il faut enlever $1$ et/ou $n$ pour trouver quelque chose de cohérent.
-
Je crois effectivement avoir trouvé la bonne conjecture, je ne vais pas l'écrire ici pour l'instant histoire de laisser les autres chercher un peu. En attendant, je vais chercher une démonstration.
-
Je ne suis pas très arithméticien, mais, comme tout le monde semble parti s'embrasser sous le gui, il me semble qu'on peut écrire : $$
\begin{align}
\sigma(n) & = \sum_{k=1}^a k \cdot 1_{k|n} \\
(a)_n & = \sum_{i=1}^a \big(1 - n \cdot 1_{n|i} \big)
\end{align}
$$ et Fubiniser. -
Bonsoir
Tout d'abord merci pour votre participation.
Comme cela est précisé dans l'énoncé, on compte tous les diviseurs positifs de $n$.
Comme l'a précisé marsup, on remarque très vite qu'il s'agit de prouver que : $$
\sum_{n=1}^{a} \Big(\sigma(n)+(a)_n\Big)=a^2.
$$ On obtient alors : $$
\sum_{n=1}^{a} \sigma(n)=a^2-\sum_{n=1}^{a}(a)_n.
$$ La preuve de ce résultat que j'ai obtenue est assez élémentaire. Il me semble d'après mes maigres connaissances que la fonction $\sum\sigma(n)$ intervient dans quelques problèmes arithmétiques connus.
Al-Kashi -
Une bête interversion des sommations ("fubiniser", comme dit Marsup, bien qu'ici le terme est un peu pompeux :-)) fournit, en reprenant les notations d'Al-Kashi
$$\sum_{n \leqslant a} (a)_n = \sum_{n \leqslant a} \left( a - n\left \lfloor \frac{a}{n} \right \rfloor \right) = a^2 - \sum_{n \leqslant a} n \sum_{k \leqslant a/n} 1= a^2 - \sum_{m \leqslant a} \sum_{d \mid m} d = a^2 - \sum_{m \leqslant a} \sigma(m)$$
comme annoncé.
Supplément. En utilisant le meilleur développement asymptotique actuellement connu de la valeur moyenne de la somme des diviseurs, on obtient
$$\sum_{n \leqslant a} (a)_n = a^2 \left(1 - \tfrac{1}{2} \zeta(2) \right) + O \left( a (\log a)^{2/3} \right).$$
Noter que $1 - \frac{1}{2} \zeta(2) \approx 0,1775 \dotsc$ -
Bonjour noix de totos,
Merci pour ta contribution. La preuve que j'ai obtenue est la suivante. En comparant $(a) _k$ et $(a-1)_k$ j'avais remarqué la relation $\sum_{k\leq a} (a)_k=\sum_{k\leq a} (a-1)_k+a-\sigma(a)$ qui permet d'obtenir le résultat proposé.
Reste une question à laquelle je n'ai pas la réponse. Une telle formule a-t-elle un intérêt ?
La seule chose qui me semble évidente est qu'en pratique si je veux calculer par exemple $\sum_{k\leq 100}\sigma(k)$ je préférerais calculer $100^2-\sum_{k\leq 100}(100)_k$ que l'on peut simplifier en $100^2-\sum_{k< 50}(100)_k-\sum_{k<50}k$.
Al-Kashi -
En ce qui me concerne, le seul intérêt que j'y ai vu (certes assez rapidement) est l'obtention de la formule asymptotique ci-dessus (mais qui, elle-même, ne semble pas avoir d'application particulière).
Ou bien on peut prendre le problème à l'envers : si tu es capable de déterminer un développement asymptotique pour la somme $\sum_{n \leqslant a} (a)_n$, indépendamment de celle de la somme des diviseurs et meilleure que celle-ci, alors tu améliorerais le développement de $\sum_{n \leqslant x} \sigma(n)$, chose qui n'a pas été faite depuis 60 ans...
À noter également que le raisonnement que j'ai fait se généralise, en procédant exactement pareil, sous la forme
$$\sum_{n \leqslant N} \left( \sigma_k(n) + n^k \left \{ \frac{N}{n} \right \} \right) = N \sum_{n \leqslant N} n^{k-1}$$
où $k \in \mathbb{Z}_{\geqslant 1}$, $t \longmapsto \{t\}$ désigne la partie fractionnaire et $\sigma_k(n) := \displaystyle \sum_{d \mid n} d^k$ est la somme des puissances $k$-èmes des diviseurs.
On retrouve ton identité en prenant $k=1$. -
Merci pour toutes ces précisions noix de totos. J'étais déjà très intéressé par cette somme, voilà que je le suis encore plus. Par contre je peux mettre une croix sur mon objectif initial qui était d'obtenir une formule simple pour $\sum_{k \leq a} (a)_k$.
Al-Kashi -
J'avoue avoir été un peu espiègle dans mon message précédent, au moment du paragraphe "Ou bien on peut prendre le problème à l'envers ..." (mais j'ai une excuse : c'est le nouvel an).
Cette somme, ou plutôt son terme d'erreur, est effectivement le noeud du problème. S'il est facile de majorer ce terme d'erreur en $\ll a \log a$, il est autrement bien plus difficile d'améliorer ce résultat. Walfisz a réussi cet exploit à la fin des années 50, et est resté invaincu depuis, et pour cause : son résultat fait intervenir de façon très profonde une région sans zéro de la fonction $\zeta$ de Riemann, et, comme on le sait, celle-ci reste inexpugnablement bloquée à la région déterminée en 1958 par Vinogradov et Korobov. -
Bonjour
À en croire mes brouillons, il me semble avoir une idée pour une approximation de $\sum_{k \leq a} (a)_k$ qui fait apparaître les valeurs $\zeta (2), a^2$ et $\ln(a)$. Par contre je n'arrive pas à estimer précisément le terme d'erreur. Je vais essayer dans un premier temps de programmer tout cela pour avoir une idée du terme d'erreur. Bien évidemment, vu ce qui a été dit par noix de totos concernant l'utilisation de résultats très profonds de la fonction $\zeta$, je n'espère pas obtenir un résultat meilleur que les précédents.
Je reste néanmoins très motivé par ce problème et cette identité que j'ai proposée car je n'aurais pas pu l'étudier directement avec mes maigres connaissances en arithmétiques en passant directement par la somme $\sum \sigma(k)$
Al-Kashi -
Bonsoir
L'idée est la suivante : on regroupe les termes ayant des quotients identiques en remarquant que les valeurs $n$ comprises entre $\big\lfloor\dfrac{a}{k}\big\rfloor+1$ et $\big\lfloor\dfrac{a}{k-1}\big\rfloor$ ont pour quotient $k-1$ dans la division de $a$ par $n$. On obtient ainsi : $$
\sum_{k\leq a}(a)_{k}=a^2-\dfrac{1}{2}\sum_{k=2}^{k=a+1}\Big(\big\lfloor\frac{a}{k}\big\rfloor+1+\big\lfloor\frac{a}{k-1}\big\rfloor\Big)\Big(\big\lfloor\frac{a}{k-1}\big\rfloor-\big\lfloor\frac{a}{k}\big\rfloor\Big)(k-1)
$$ J'ai ensuite utilisé l'approximation ci-dessous pour laquelle je n'arrive pas à obtenir le terme d'erreur précis :
\begin{align*}
\sum_{k\leq a}(a)_{k}&\approx a^2-\dfrac{1}{2}\sum_{k=2}^{k=a+1}\Big(\frac{a}{k}+1+\frac{a}{k-1}\Big)\Big(\frac{a}{k-1}-\frac{a}{k}\Big)(k-1) \\
&\approx a^2-\dfrac{1}{2}\sum_{k=2}^{k=a+1}\Big(\frac{a}{k}+1+\frac{a}{k-1}\Big)\Big(a-\frac{a(k-1)}{k}\Big) \\
&\approx a^2-\dfrac{1}{2}\sum_{k=2}^{k=a+1}\Big(\frac{a^2}{k}+a+\frac{a^2}{k-1}-\frac{a^2(k-1)}{k^2}-\frac{a(k-1)}{k}-\frac{a^2}{k}\Big) \\
&\approx a^2-\dfrac{1}{2}\sum_{k=2}^{k=a+1}\Big(\frac{a^2}{k-1}-\frac{a^2(k-1)}{k^2}+\frac{a}{k}\Big) \\
&\approx a^2-\dfrac{a^2}{2}\sum_{k=2}^{k=a+1}\frac{1}{k^2}-\dfrac{a}{2}\sum_{k=2}^{k=a+1}\frac{1}{k}-\dfrac{a^2}{2}+\dfrac{a^2}{2(a+1)} \\
&\approx \dfrac{a^2(a+2)}{2(a+1)}-\dfrac{a^2}{2}\sum_{k=2}^{k=a+1}\frac{1}{k^2}-\dfrac{a}{2}\sum_{k=2}^{k=a+1}\frac{1}{k} \\
&\approx \dfrac{a^2(a+2)}{2(a+1)}-\dfrac{a^2}{2}\zeta(2)-\dfrac{a}{2}(\ln(a+1)-1)
\end{align*} Encore une fois, je le précise, je n'ai pas l'ambition d'obtenir des résultats nouveaux dans ce domaine mais simplement de tenter des choses assez élémentaires qui auront peut-être l'intérêt de vulgariser ceci.
Al-Kashi
[Ne pas abuser des expressions centrées. AD] -
Ben oui, mais justement, tout le problème est là : quelle erreur obtient-on lorsque l'on enlève les parties entières ? C'est bien là tout l'enjeu de ces types de calcul...
La méthode usuelle : remplacer les $\lfloor x \rfloor$ par $x - \frac{1}{2} - \psi(x)$, où $\psi$ indique, comme je l'ai déjà dit, la $1$ère fonction de Bernoulli, puis déterminer l'erreur fournie par les sommes contenant ces fonctions $\psi$, et c'est ça qui est délicat. -
Un livre accessible, tout en ne faisant pas l'impasse sur les éventuelles difficultés, est le suivant : https://www.amazon.fr/Introduction-Analytic-Number-Theory-Apostol/dp/0387901639/ref=sr_1_4?__mk_fr_FR=ÅMÅŽÕÑ&crid=2KBKKLN4R4ICM&keywords=tom+apostol&qid=1579244613&sprefix=tom+apostol,aps,237&sr=8-4
J'aime bien aussi https://www.amazon.fr/Arithmetic-Universitext-Bordell¨¨s-Olivier-Paperback/dp/B010WEXK6E/ref=sr_1_2?__mk_fr_FR=ÅMÅŽÕÑ&keywords=olivier+bordellès&qid=1579244657&sr=8-2 mais le prix amazon est devenu déraisonnable.
Enfin, celui-ci aussi https://www.amazon.fr/Analytic-Number-Theory-Exploring-Integers/dp/0821875779/ref=sr_1_2?__mk_fr_FR=ÅMÅŽÕÑ&keywords=De+Koninck+et+Luca&qid=1579244721&sr=8-2, malgré une critique amazon un peu dure, je trouve. -
Merci noix de totos, je vais essayer d'aller feuilleter ces 3 livres et en choisir un. Dommage que le livre d'Olivier ne soit pas en français. Ce sera une bonne excuse pour me remettre à l'anglais.
Al-Kashi -
Bonjour,
pour le plaisir de participer.
Si $S(0):=0$
$\ \ \ \ $et, pour tout $a\in \mathbb N^*$,
$\ \ \ $ $S(a):=\sum_{k=1}^{a} (a)_k$ et $\Delta(a):=S(a)-S(a-1)$
alors $$\Delta+\sigma=2\ Id-1.
$$ Par téléscopage $\ \displaystyle \sum_{k=1}^{a}\big(\Delta(k)+\sigma(k)\big)=\sum_{k=1}^{a}(2\ Id-1)(k)\ $ donne $$
\sum_{k=1}^{a} \big((a)_k+\sigma(k)\big)=a^2.$$
edit: correction d'une coquille: j'avais écrit $2 (Id-1)(k)$ au lieu de $(2 Id - 1)(k)$; par ailleurs, merci une fois de plus, Alain -
Bonjour,
@ndt: Aurais-tu une référence en ligne sur la majoration `facile' en $a\log a$?
Je te pose la question car, sauf erreur de ma part, j'ai réussi à obtenir ce terme d'erreur et je voulais comparer aux méthodes classiques pour vérifier si la méthode que j'ai employée n'est rien d'autre que l'une de celles-ci.
En te remerciant,
Al-Kashi -
Les trois références ci-dessus effectuent ce calcul, tant il est classique, mais on pourrait même le faire ici (et, à mon avis, j'ai déjà dû certainement le faire sous cette identité ou une autre).
-
Je n'ai pas encore eu le temps de feuilleter les références, mais je le ferai dès que possible.Ce qui suit doit donc y correspondre.
\begin{align*}
\sum_{k\leq a}(a)_{k}&=a^2-\dfrac{1}{2}\sum_{k=2}^{k=a+1}\Big(\big\lfloor\frac{a}{k}\big\rfloor+1+\big\lfloor\frac{a}{k-1}\big\rfloor\Big)\Big(\big\lfloor\frac{a}{k-1}\big\rfloor-\big\lfloor\frac{a}{k}\big\rfloor\Big)(k-1) \\
&=a^2-\dfrac{1}{2}\sum_{k=2}^{k=a+1}\Big(\big\lfloor\frac{a}{k-1}\big\rfloor^2-\big\lfloor\frac{a}{k}\big\rfloor^2\Big)(k-1)-\dfrac{1}{2}\sum_{k=2}^{k=a+1}\Big(\big\lfloor\frac{a}{k-1}\big\rfloor-\big\lfloor\frac{a}{k}\big\rfloor\Big)(k-1) \\
&=a^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\big\lfloor\frac{a}{k}\big\rfloor^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\big\lfloor\frac{a}{k}\big\rfloor
\end{align*}
On a alors :
\begin{align*}
a^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\Big(\frac{a}{k}\Big)^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\frac{a}{k}\leq \sum_{k\leq a}(a)_{k}\leq a^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\Big(\frac{a}{k}-1\Big)^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\Big(\frac{a}{k}-1\Big)\\
a^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\Big(\frac{a}{k}\Big)^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\frac{a}{k}\leq \sum_{k\leq a}(a)_{k}\leq a^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\Big(\frac{a}{k}\Big)^2-\dfrac{1}{2}\sum_{k=1}^{k=a}\frac{a}{k}+\sum_{k=1}^{k=a}\frac{a}{k} \\
\end{align*}
Ceci donne l'approximation déjà citée par ndt mais ici simplement en $O \left( a (\log a)\right)$
Al-Kashi -
L'idée est là mais tu peux être plus rapide.
D'abord, d'après mes messages plus haut, il suffit d'estimer la somme $\displaystyle \sum_{n \leqslant a} \sigma(n)$. Par interversion des sommes, on a
\begin{align*}
\sum_{n \leqslant a} \sigma(n) &= \sum_{n \leqslant a} \sum_{d \mid n} d = \sum_{n \leqslant a} n \sum_{d \mid n} \frac{1}{d} \\
& = \sum_{d \leqslant a} \frac{1}{d} \sum_{k \leqslant a/d} kd \\
& = \sum_{d \leqslant a} \frac{1}{2} \left \lfloor \frac{a}{d} \right \rfloor \left( \left \lfloor \frac{a}{d} \right \rfloor + 1 \right) \\
& = \frac{a^2}{2} \sum_{d \leqslant a} \frac{1}{d^2} + O \left( a \sum_{d \leqslant a} \frac{1}{d} \right) \\
& = \frac{\zeta(2)}{2} a^2 + O (a \log a).
\end{align*} -
A oui en effet, c'est bien plus rapide (tu).Merci.
Al-Kashi -
Le procédé ci-dessus est à la base des raisonnements en théorie multiplicative des nombres. On peut y ajouter des variantes plus ou moins compliquées (principe de l'hyperbole de Dirichlet, sommation de Perron, etc).
-
Ça fait longtemps que Bordes n'est pas passé sur le forum
-
Pas tant que ça :-D
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 23
+15 Invités