Équivalent d'une somme
dans Analyse
Bonjour à tous,
En cette période d'oraux de tous concours, je vous propose une petite amusette : donnez un équivalent de $\displaystyle \sum_{i=1}^ni\mathrm{E}\left(\dfrac{n}{i}\right)$ ($\mathrm{E}$ désigne la partie entière).
Bien à vous.
En cette période d'oraux de tous concours, je vous propose une petite amusette : donnez un équivalent de $\displaystyle \sum_{i=1}^ni\mathrm{E}\left(\dfrac{n}{i}\right)$ ($\mathrm{E}$ désigne la partie entière).
Bien à vous.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
\frac{1}{2}\sum_{i=1}^n E\Big(\frac{n}{i}\Big)^2 + \frac{1}{2}\sum_{i=1}^n E\Big(\frac{n}{i}\Big).
$$
Mes excuses au modérateur Jacquot pour le titre.
Amicalement
Rappel du titre original: Petit amusement, équivalent d'une somme
J'essaye d'avoir une page d'accueil bien homogène, avec des titres explicites si possible... Excuse le petit coup de ciseaux
Le calcul de cette somme m'a intéressé, et ce fut pour moi un labeur dépassant franchement le "petit" amusement !
En regardant ce qui se passe pour $n$ assez gros, je suis arrivé au même résultat comme suit:
$\displaystyle \sum_{i=1}^ni\mathrm{E}\left(\dfrac{n}{i}\right) \approx \sum_{i=n/2}^n i+\sum_{i=n/3}^{n/2} 2i +\sum_{i=n/3}^{n/4}3i + \dots $
$ \approx \frac 1 2 (n -\frac n 2)(n +\frac n 2)+\frac 2 2 (\frac n 2 -\frac n 3)(\frac n 2 +\frac n 3)+\frac 3 2 (\frac n 3 -\frac n 4)(\frac n 3 +\frac n 4)+\dots $
$ \approx \frac 1 2 (n^2 -\frac {n^2} 4)+\frac 2 2 (\frac {n^2} 4 -\frac {n^2} 9)+\frac 3 2 (\frac {n^2} 9 -\frac {n^2}{16})+\dots $
$\approx \dfrac{n^2}2\Big( 1+\dfrac 1 4+\dfrac 1 9+\dots +\dfrac 1{n^2}\Big)$
$\approx \dfrac{n^2}2\times\dfrac{\pi^2}6$
Je doutais cependant à cause des multiples approximations.
Merci en tous cas pour cette question intéressante.
Amicalement. jacquot
Aucun souci pour le changement de titre.
On peut diminuer le nombre d'approximations en se ramenant le problème au calcul de $\displaystyle\int_0^1t.\mathrm{E}\left(\dfrac{1}{t}\right)\mathrm{d}t$
Amicalement,
Guillaume
\sum_{k=1}^n k \left \lfloor \frac{n}{k} \right \rfloor = \frac{n^2}{2} \zeta(2) + O \left ( n (\log n)^{2/3} \right ).
$$ Il suffit d'écrire $$\sum_{k=1}^n k \left \lfloor \frac{n}{k} \right \rfloor = \sum_{k=1}^n \sigma(k)
$$ où $\sigma(k)$ désigne la somme des diviseurs de $k$, puis d'appliquer un résultat profond dû à Walfisz.
C'est le record actuel, et on ne peut l'améliorer tant que l'on n'aura pas amélioré la région sans zéro de la fonction zêta de Riemann.
{\bf Référence}. \textsc{O. Bordellès}, {\it Arithmetic Tales}, Springer, 2012, Theorem 6.43 page 340.
[Corrigé selon ton indication ($\zeta(2)$ au numérateur). AD]
Je suis épaté par la qualité de la majeure partie des interventions sur ce forum, je découvre encore beaucoup de choses, moi, humble petit amateur de mathématiques encore à l'école (de Palaiseau..).
Mais, moi, je n'y suis pour rien, j'ai juste recopié l'estimation à partir du bouquin indiqué, et il y est aussi stipulé que, pour arriver à avoir une telle précision, il est nécessaire de traiter des sommes d'exponentielles par la méthode dite de Vinogradov !
J'ai lu ça dans le bouquin cité en référence, et c'est largement au-dessus du niveau L1/L2 (et même M2...).
Je détaille : $E(\frac{n}{i})$ est le nombre de multiples de $i$ inférieurs à $n$. On peut alors réécrire la somme (que je noterai $S_n$) :
\[ S_n = \displaystyle \sum_{i=1}^n \sum_{k \text{ tels que }ik \leqslant n} i = \sum_{\text{couples } (i,k) \text{ tels que }ik \leqslant n} i = \sum_{k=1}^n \sum_{i=1}^{E(\frac{n}{k})} i = \sum_{k=1}^n \dfrac{E(\frac{n}{k})\left(E(\frac{n}{k})+1\right)}{2} \]
Donc $\displaystyle \dfrac{1}{n^2} S_n = \sum_{k=1}^n \dfrac{E(\frac{n}{k})\left(E(\frac{n}{k})+1\right)}{2n^2}$.
Or, à $k$ fixé, $ \dfrac{E(\frac{n}{k})\left(E(\frac{n}{k})+1\right)}{2n^2} \underset{n\rightarrow +\infty}{\longrightarrow} \dfrac{1}{2k^2}$. On conclut avec le théorème de convergence dominée sur les séries.
On peut ainsi calculer $S(n)$ pour de grandes valeurs de $n$ rapidement.
Si mon programme est bon, on doit avoir par exemple $S(10^{12}) = 822\, 467\, 033\, 425\, 357\, 340\, 138\, 978$, ce qui correspond bien à l'équivalent trouvé ($\dfrac{\pi^2}{12}=0{,}8224670334241...$)
La suite $\displaystyle \left( \dfrac{1}{n}\sum_{i=1}^ni\mathrm{E}\left( \dfrac{n}{i} \right) \right)_{n\in\mathbb{N}*}$ converge [c’est presque une somme de Riemann] vers $\displaystyle\int_0^1t.\mathrm{E}\left(\dfrac{1}{t}\right)\mathrm{d}t$.
Un découpage de cette intégrale analogue à celui que vous avez fait fait apparaître assez vite $\zeta(2)$.
Même début que Guego, sauf que j'utilise ensuite la formule évidente $\lfloor t \rfloor = t + O(1)$ ce qui donne
\begin{align*}
\sum_{k=1}^n \sigma(k) &= \frac{1}{2} \sum_{k=1}^n \left \lfloor \frac{n}{k} \right \rfloor \left( \left \lfloor \frac{n}{k} \right \rfloor + 1 \right ) \\
&= \frac{n^2}{2} \sum_{k=1}^n \frac{1}{k^2} + O \left ( n \sum_{k=1}^n \frac{1}{k} \right ) \\
&= \frac{n^2}{2} \left ( \zeta(2) - \sum_{k=n+1}^\infty \frac{1}{k^2} \right ) + O \left( n \log n \right ) \\
&= \frac{n^2}{2} \left ( \zeta(2) + O \left ( \frac{1}{n} \right ) \right ) + O \left( n \log n \right ) \\
&= \frac{n^2 \zeta(2)}{2} + O ( n \log n).
\end{align*}
Du coup, je m'aperçois que, dans mon premier message plus haut, il faut mettre le $\zeta(2)$ au numérateur (et non au dénominateur). SI un modérateur pouvait s'en charger, merci !
[C'est corrigé. AD]
On a $\displaystyle \sum_{i=1}^{n}iE(\frac{i}{n}) = n^{2} \times \frac{1}{n}\sum_{i=1}^{n} \frac{i}{n}E(\frac{1}{i/n})$.
Or $E(\frac{1}{t})$ est Riemann-intégrable sur $[\alpha, 1]$ pour tout $\alpha > 0$, en tant que fonction monotone, donc $tE(\frac{1}{t})$ aussi.
De plus, $1-t < tE(\frac{1}{t}) \leq 1$ donc $tE(\frac{1}{t})$ se prolonge en $0$ par continuité avec la valeur $1$. Donc la fonction prolongée est Riemann-intégrable sur $[0,1]$, et par le théorème des sommes de Riemann on a $\displaystyle \lim\limits_{n \rightarrow +\infty} \frac{1}{n}\sum_{i=1}^{n} \frac{i}{n}E(\frac{1}{i/n}) = \int_{0}^{1} tE(\frac{1}{t}) dt$.
On fait le changement de variable $x = \frac{1}{t}$ (théorème de changement de variable pour une intégrale impropre, $1/t$ est bien un C1 difféomorphisme), et alors $\displaystyle \int_{0}^{1} tE(\frac{1}{t}) dt = \int_{1}^{+\infty} \frac{E(x)}{x^{3}} dx$.
Or $\displaystyle \int_{1}^{+\infty} \frac{E(x)}{x^{3}} dx = \lim\limits_{N \rightarrow +\infty} \int_{1}^{N} \frac{E(x)}{x^{3}} dx = \lim\limits_{N \rightarrow +\infty} \sum_{n=1}^{N-1} \int_{n}^{n+1} \frac{n}{x^{3}} dx$.
Après quelques calculs on trouve que $\displaystyle \int_{n}^{n+1} \frac{n}{x^{3}} dx = \frac{3}{n} - \frac{3}{n+1} + \frac{3}{(n+1)^2}$.
Et donc en sommant le tout on a $\displaystyle \sum_{n=1}^{N-1} \int_{n}^{n+1} \frac{n}{x^{3}} dx = 3 - \frac{3}{N} + \sum_{n=1}^{N-1} \frac{3}{(n+1)^{2}} = 3 - \frac{3}{N} + \sum_{n=1}^{N} \frac{3}{n^{2}} - 3 \underset{N \to +\infty}{\longrightarrow} 3 - 0 + \frac{3\pi^{2}}{6} - 3 = \frac{3\pi^{2}}{6}$.
CQFD :)o
Edit : J'ai été grillé par Guillaume02 pendant que j'écrivais 8-) Je mets vraiment beaucoup de temps à écrire, mon message avait commencé lorsqu'il suggérait d'étudier l'intégrale
Edit 2 : Et évidemment je me suis planté dans le calcul puisque je ne trouve pas la même chose que vous. Je vais essayer de voir où est l'erreur.
Edit 3 : Par ailleurs j'ai fait un changement de variable sur une fonction non continue (et qui a même une infinité de de points où elle est discontinue), je n'ai en mémoire aucun théorème qui me permet de le faire, il est donc possible que ce changement de variable soit ne soit pas justifié. A creuser ...
[À ton service. AD]
J'ai peut-être lu ça dans les livres de Roger Godement mais je ne suis vraiment pas sûr.
Edit : La fonction n'est pas monotone !!!
Edit 2 : Oui mais la fonction a une limite à gauche et à droite en tout point, donc elle est réglée, donc ça devrait marcher quand même !
Dans ton intégration tu as multiplié par 3 au lieu de diviser par 2 l'erreur doit venir de là.
Je corrigerai quand j'aurai le temps.
Quelqu'un peut me confirmer en revanche ce que je dis sur le changement de variable dans l'intégrale ? J'avoue que je n'ai pas complètement confiance dans ma justification.
Avec le théorème de convergence dominée, il n'y a plus qu'à calculer l'intégrale.
Comme les intervalles $]1/(n+1),1/n]$ forment une partition de $]0,1]$, on a
$\int_0^1 f(x)\ dx=\sum_{n\ge 1}\int_{]1/(n+1),1/n]} f(x)\ dx=\sum_{n\ge 1} \frac12(\frac1{(n+1)^2}+\frac1{n(n+1)})=\frac12(\frac{\pi^2}6-1+1)$. (la 2e série est télescopisque).
1. Au lieu d'utiliser la trivialité $\lfloor t \rfloor = t + O(1)$, on utilise la formule plus précise $\lfloor t \rfloor = t - \psi(t) - \frac{1}{2}$, où $t \longmapsto \psi(t)$ est la première fonction de Bernoulli. En remplaçant les parties entières dans mon calcul plus haut par cette estimation, on arrive à
$$\sum_{n \leqslant x} \sigma(n) = \frac{x^2 \zeta(2)}{2} - x \sum_{d \leqslant \sqrt x} \frac{1}{d} \psi \left ( \frac{x}{d} \right ) + O(x).$$
2. Walfisz s'est alors attaqué à la somme du 2nd membre. On note d'abord que
(i) L'estimation triviale due à l'inégalité triangulaire montre que cette somme est en $O(\log x)$ et on retrouve le terme d'erreur obtenu plus haut. Il faut donc trouver comment faire mieux que l'inégalité triangulaire.
(ii) La fonction $\psi$ est très oscillante, et les premières valeurs de l'indice apportent la plus grosse contribution à la somme. L'idée est alors de découper cette somme en deux (an allant pas trop loin), de façon à ce que la seconde somme soit majorable plus facilement.
3. Walfisz s'est alors tourné vers l'analyse de Fourier : la fonction $\psi$ étant impaire et $1$-périodique, elle admet un développement en série de Fourier. Malheureusement, $\psi$ a des discontinuités en chaque entier et la convergence n'est pas uniforme (contrairement à ce qui se passe pour les autres fonctions de Bernoulli). On travaille alors plutôt avec les sommes partielles de la séries de Fourier, pour lesquelles on dispose d'outils performants.
4. Ainsi, Walfisz ramène le problème à estimer des sommes d'exponentielles de la forme $\sum_{N < n \leqslant N_1} e^{2 i \pi x/n}$ (avec $N < N_1 \leqslant 2N$), pour lesquelles on applique la méthode de Vinogradov qui fournit le résultat exceptionnel suivant :
$$\sum_{N < n \leqslant N_1} e^{2 i \pi x/n} \ll N \exp \left ( -c_0 \, \frac{\log^3 N}{(\log x/N)^2} \right ).$$
On remonte alors à la somme initiale par sommation partielle et le tour est joué.
[Edit: introduction tronquée. jacquot]
Je n'ai pas le niveau d'un duroc pour faire tout ça tout seul !
PS : Je suis d'accord pour dire que Duroc semble très bien connaître le sujet, il pourrait presque avoir écrit le bouquin
Mon pauvre Egoroff : ne cherche pas, tu ne trouveras pas qui je suis...à moins de devenir, toi aussi, un modérateur et on en revient donc à ce que je disais dans l'autre fil ! (tu)
Je cherchais, sans succès, un moyen de trouver simplement et rapidement les valeurs de $k$ pour lesquelles:
l'équation $E\Big(\dfrac{N}{x}\Big)=k$ n'a pas de solution avec $N>0$ entier fixé , $x$ entier inconnu et $E()$ la fonction partie entière.
Le script Pari-GP qui suit permet de calculer $\sum_{k=1}^{n} \sigma(k)$ lorsque $n$ est un carré.
(cela permet, entre autres, de calculer rapidement $\sum_{k=1}^{10^{12}} \sigma(k)$ proposée par Guego et qui donne le même résultat)
PS:
Je ne prétends pas que ce script ne peut pas optimisé pour des calculs plus rapides.
Mon script python est le suivant :
Par exemple, pour $n=10^9$ (qui n'est pas un carré) :
Il y aurait un truc à optimiser dans ton code par exemple:
Sur l'exécution complète du premier while tu auras calculé plusieurs fois les mêmes nombres.
Et je suis un peu surpris de la suite:
Tu n'utilises pas totalement la formule :
$$\sum_{i=1}^{n} \sigma(i)=\sum_{k=1}^{n} f\Big(E\Big(\dfrac{n}{i}\Big)\Big)$$
où $$f(x)=\dfrac{x(x+1)}{2}$$
Par ailleurs, combien de fois les while bouclent?
Soit $\alpha >1$ réel et on note $\sigma_\alpha(n) := \sum_{d \mid n} d^\alpha$. Montrer que
$$\sum_{n \leqslant x} \sigma_\alpha(n) = \frac{\zeta(\alpha+1)}{\alpha+1} \, x^{\alpha+1} + O \left ( x^\alpha \right ).$$
En principe, il calcule $ \sum_{k=1}^{n} \sigma(k)$ pour tout $n>1$ entier
PS:
Pour ceux qui veulent le tester et qui connaissent très peu Pari-GP.
Sous Windows, Il faut créer un fichier par exemple, toto.txt, mettre le listing du script dedans et le mettre dans le répertoire:
C:/Program Files/PARI/examples
(les antislash ne fonctionnent pas en mode latex, mais il faut remplacer / par un antislash)
Pour qu'il soit pris en compte par Pari-GP il faut exécuter l'instruction:
read("toto.txt") et la fonction sigm() devient disponible (attention au fait qu'il existe déjà une fonction sigma())
On conclut avec le théorème de convergence dominée sur les séries.
Quelqu'un aurait-il l'amabilité de détailler cette phrase ?
Je vous en remercie d'avance
Cordialement
Tu as une suite double $a_{i,j}$ telle que, pour tout $i$, $a_{i,j}$ converge vers $b_i$ (lorsque $j$ tend vers $+\infty$), et telle que, pour tout $i$ et $j$, $|a_{i,j}| \leqslant c_i$ où $c_i$ ne dépend pas de $j$ et est le terme général d'une série convergente.
Alors la série $\sum b_i$ converge et $\displaystyle \sum_{i=0}^{+\infty} a_{i,j} \xrightarrow[j \rightarrow +\infty]{} \ \sum_{i=0}^{+\infty} b_i$.
Je propose une démonstration du théorème de Guego.
Pour $x \geq 0$, soit $\displaystyle F_{n}(x) = \sum_{i=0}^{n}a_{i,E(x)}$, et $\displaystyle F(x) = \sum_{i=0}^{+\infty}a_{i,E(x)}$ qui est une série absolument convergente pour tout $x$ car $|a_{i,E(x)}| \leq c_{i}$ et $c_{i}$ est le terme d'une série convergente. Donc $F_n(x)$ converge simplement vers $F(x)$.
Or on a $\displaystyle |F(x) - F_{n}(x)| = |\sum_{i=n+1}^{+\infty}a_{i,E(x)}| \leq \sum_{i=n+1}^{+\infty}c_{i}$ qui converge vers $0$. Donc $F_{n}(x)$ converge uniformément vers $F(x)$.
Par ailleurs il est facile de voir que $\lim\limits_{x \rightarrow +\infty} a_{i,E(x)} = b_{i}$.
Le théorème d'interversion des limites pour les séries de fonctions convergeant uniformément montre que :
$\displaystyle \sum_{i=0}^{+\infty} b_i$ existe,
et $\displaystyle \lim\limits_{x \rightarrow +\infty} F(x) = \sum_{i=0}^{+\infty} b_i$.
En particulier $F(j)$ converge vers $\displaystyle \sum_{i=0}^{+\infty} b_i$ lorsque $j$ tend vers $+\infty$, ce qui termine la démonstration car $\displaystyle F(j) = \sum_{i=0}^{+\infty} a_{i,j}$.
Qu'en pensez-vous ?