Somme de carrés, A048153
Bonjour
Est-il vrai que si $n \in \mathbb {N^*}$
alors $a(n):=\sum _{ [[0,n]]} ( i^2)_n \leq \frac {n(n-1)}{2}$
(où $(i^2)_n$ est le reste de la division euclidienne ordinaire de $i^2$ par $n$) ?
$a:=A048153$ de OEIS.
Il semble que $a(n):=\sum _{ [[0,n]]} ( i^2)_n \leq \frac {n(n-1)}{2}$ avec égalité ssi $n$ est sans carré et tous ses diviseurs premiers sont congrus à $1$ ou $2\mod4$.
Merci d'avance pour vos réponses.
Cordialement
Paul
Est-il vrai que si $n \in \mathbb {N^*}$
alors $a(n):=\sum _{ [[0,n]]} ( i^2)_n \leq \frac {n(n-1)}{2}$
(où $(i^2)_n$ est le reste de la division euclidienne ordinaire de $i^2$ par $n$) ?
$a:=A048153$ de OEIS.
Il semble que $a(n):=\sum _{ [[0,n]]} ( i^2)_n \leq \frac {n(n-1)}{2}$ avec égalité ssi $n$ est sans carré et tous ses diviseurs premiers sont congrus à $1$ ou $2\mod4$.
Merci d'avance pour vos réponses.
Cordialement
Paul
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
\begin{align*}
S_n &= \sum_{b=1}^{n-1} \left( b^2 \bmod n \right) = n \sum_{b=1}^{n-1} \left \{ \frac{b^2}{n} \right \} \\
&= n \sum_{a=1}^{n-1} \; \sum_{\substack{b=1 \\ b^2 \equiv \, a \, (\textrm{mod} \, n)}}^{n-1} \left \{ \frac{a}{n} \right \} \\
&= \sum_{a=1}^{n-1} a \; \sum_{\substack{b=1 \\ b^2 \equiv \, a \, (\textrm{mod} \, n)}}^{n-1} 1.
\end{align*}
Lorsque $n$ est impair, le nombre de solutions de la congruence $b^2 \equiv \, a \, (\textrm{mod} \, n)$ vaut $\displaystyle \sum_{d \mid n} \mu(d)^2 (a/d) \leqslant 2^{\omega(n)}$, d'où la majoration
$$S_n \leqslant 2^{\omega(n)-1}n (n-1)$$
dans ce cas.
Voici ce que je vois, on a $( i^2)_n=i^2-n\lfloor \frac {i²}n\rfloor$ donc cela rivient à démontrer que
\begin{align*}
S_n &= \sum_{a=1}^{n-1} a \; \sum_{d \mid n} \mu(d)^2 \left( \frac{a}{d} \right) = \sum_{d \mid n} \mu(d)^2 \sum_{a=1}^{n-1} a \left( \frac{a}{d} \right) \\
&= \sum_{a=1}^{n-1} a + \sum_{\substack{d \mid n \\ d > 1}} \mu(d)^2 \sum_{a=1}^{n-1} a \left( \frac{a}{d} \right) = \frac{n(n-1)}{2} + \sum_{\substack{d \mid n \\ d > 1}} \mu(d)^2 \sum_{a=1}^{n-1} a \left( \frac{a}{d} \right).
\end{align*}
Une sommation d'Abel et l'inégalité de Polyá-Vinogradov fournissent
$$\left | \sum_{a=1}^{n-1} a \left( \frac{a}{d} \right)\right| \leqslant 2n \max_{t \leqslant n} \left| \sum_{a \leqslant t} \left( \frac{a}{d} \right)\right| \leqslant 4n \sqrt{d} \log (ed).$$
On reporte ci-dessus, ce qui donne
$$S_n = \frac{n(n-1)}{2} + O \left( n \log n \sum_{d \mid n } \mu(d)^2 \sqrt{d} \right) = \frac{n^2}{2} + O \left( n^{3/2+o(1)} \right).$$
J'ai commencé par chercher, en vain, à prouver l'inégalité de Gébrane qui équivaut clairement à la mienne. A166375 est aux parties entières ce qu'est A048153 aux restes.
Je n'ai pas le niveau pour comprendre tout ce que dit noix de totos mais il me semble comprendre que les trois propositions suivantes sont équivalentes pour tout $n$ impair :
$\sum _{ [[0,n]]} ( i^2)_n \leq \frac {n(n-1)}{2}$.
$\frac{1}{3}\left(n-1\right)\left(n-2\right)\le \sum _{i=1}^{n-1}\lfloor \frac{i^2}{n}\rfloor $.
$\sum_{\substack{d \mid n \\ d > 1}} \mu(d)^2 \sum_{a=1}^{n-1} a \left( \frac{a}{d} \right) \leq 0$.
Quant au cas où l'égalité est réalisée, il continue de me sembler que c'est lorsque $n$ est sans carré et ses diviseurs premiers sont congrus à $1$ ou $2$ modulo $4$.
Encore merci et dans l'espoir de vous lire à nouveau.
Cordialement
Paul
En effet il existe $b$ tel que $b^2\equiv -1\pmod n$ et l'application $k\mapsto bk\pmod n$ est une bijection de $\Z/n\Z$ dans lui-même.
On en déduit que $S_n=\displaystyle\sum_{k=1}^{n-1}(k^2\pmod n)=\sum_{k=1}^{n-1}(-k^2\pmod n)=\dfrac12\sum_{k=1}^{n-1}n=\dfrac{n(n-1)}2$.
J'ai choisi d'utiliser les caractères de Dirichlet, multiplicatifs donc (plus précisément ici : un caractère réel primitif), qui est la méthode classique. Elle ne fonctionne cependant pas à tous les coups.
Une autre voie est d'utiliser des caractères additifs, mais ce type de problème montre aussi les limites de ces outils : si le module est un nombre premier, les caractères additifs sont bien adaptés, mais dès que l'on généralise aux modules composés, ce qui est le cas ici puisqu'aucune contrainte n'était imposée sur $n$, un pgcd mal placé vient mettre le bazar dans les calculs.
Quoi qu'il en soit, on a là un bon problème proposé par Depasse !
Sur ce coup, je comprends!
et m'en veux d'autant plus de ne pas y avoir pensé tout seul.
Cordialement
Paul
Pour la (ma) petite histoire, j'ai eu la chance de rencontrer Guy Terjanian au début des années 80 qui m'a témoigné de la sympathie non pour mes compétences mais pour mon amour des mathématiques, un amour de jeunesse. Les amoureux ne sont pas toujours de bons amants! (je ne parle que de moi).
Il cherchait à résoudre Fermat et, comme je lui demandais s'il pensait que Fermat avait trouvé la solution (trop longue pour être écrite dans la marge), il me dit en douter profondément mais que, pour autant, il n'excluait pas qu'on puisse démontrer Fermat avec des outils "relativement élémentaires". D'ailleurs, en 1977, il avait prouvé Fermat en quelques lignes... dans le cas $n$ pair. Et il me dit: Tiens, on ne sait pas prouver "élémentairement" que la somme des non-carrés modulo $p= 3$ modulo $4$ excède la somme des carrés, on s'en sort seulement via les caractères, le nombre de classes et je ne sais pas s'il est idiot de chercher démonstration plus élémentaire. J'ai bien sûr cherché et n'ai rien trouvé.
Et puis, il y a quelques jours, cette histoire m'est revenue en mémoire et je me suis dit qu'il fallait peut-être cesser de n'envisager que les nombres premiers et regarder tous les naturels, que si on prouvait ma conjecture "élémentairement" on prouvait a fortiori élémentairement que la somme des non-carrés est supérieure à celle des carrés modulo $p$ premier congru à $3$ modulo $4$.
A suivre et merci à tous
Il est vrai que j'ai abordé ton problème avec des outils non élémentaires, mais il n'est peut-être pas impossible de le résoudre élémentairement (peut-être que certains ici y arriveront).
Disons que j'ai appliqué le "principe" de l'arithméticien : "une somme de parties fractionnaires ne se traite généralement pas élémentairement...sauf dans les (rares) cas où elle se traite élémentairement".
PS. Dans le jargon de la théorie des nombres, le vocable "élémentaire" signifie que l'on ne fait pas appel à la théorie des fonctions de la variable complexe.
Je ne sais pas si ce qui suit peut aider, mais rien que pour le plaisir de participer et de saluer au passage depasse, Jandri et ndt.
$$S_n=\dfrac{n(n-1)(2n-1)}{6}-(n-2)n\lfloor\sqrt{n(n-1)}\rfloor+n\sum_{k=1}^{n-2}\lfloor \sqrt{kn}\rfloor$$
On peut ainsi retrouver une approximation de la somme recherchée en étudiant $\sum_{k=1}^{n-2}\lfloor \sqrt{kn}\rfloor$. Je sais qu'il existe une belle formule close pour $\sum_{k=1}^{n-2}\lfloor \sqrt{k}\rfloor$ mais la technique utilisée pour cette dernière renvoie justement au problème initial et je ne vois pas pour l'instant comment faire avec le facteur $n$ en supplément.
Al-Kashi
(i) Il y a souvent assez peu de raison qu'il en existe une ;
(ii) une bonne égalité asymptotique fait tout aussi bien le job.
Je n'ai pas vérifié ton calcul, mais, selon la précision souhaitée tu pourrais le continuer avec :
(i) l'égalité triviale $\left \lfloor \sqrt{kn} \right \rfloor = \sqrt{kn} + O(1)$, ce qui te donnera un terme d'erreur en $O(n^2)$ ;
(ii) l'égalité $\left \lfloor \sqrt{kn} \right \rfloor = \sqrt{kn} - \tfrac{1}{2} - \psi \left ( \sqrt{kn} \right)$, où $\psi(x) := x - \lfloor x \rfloor - \frac{1}{2}$ est la $1$ère fonction de Bernoulli, qui peut te donner un terme d'erreur plus précis, mais c'est nettement plus difficile (je viens d'essayer rapidement, ça donne un $O(n^{38/21})$ sauf erreur).
$\dfrac{\Delta_{\ p^n}}{p^n}= \dfrac {p ^ {\lfloor \dfrac { n}{2} \rfloor} - 1}{2}$ est une jolie formule.
L'idéal serait qu'elle soit, de plus, juste.
Ici $n$ est un entier naturel, $p$ un premier congru à $1$ modulo $4$ et $\Delta_{\ p^n}=\frac {p^n ( p^n -1)}{2} - \sum _ 0^{p^n-1} i^2_{\ \ p^n}$
J'ai bien peur d'être victime d'esthétisme et ne m'étonnerais pas que ma conjecture soit vite infirmée!
Cordialement
Paul
Il me semble que c'est vrai si $n=1$. Je dis une sottise ?
Cordialement
Paul
C'est juste et facile à démontrer.
On montre d'abord par récurrence sur $n$ qu'il existe $a$ tel que $a^2\equiv-1\pmod{p^n}$.
L'application $x\mapsto (ax)\pmod{p^n}$ est une bijection de $[0,p^n-1]$ dans lui-même.
$S=\displaystyle \sum_{k=0}^{p^n-1}(k^2)_{p^n}=\sum_{k=0}^{p^n-1}((ak)^2)_{p^n}=\sum_{k=0}^{p^n-1}(-k^2)_{p^n}$
Si $p^n$ ne divise pas $k^2$ alors $(-k^2)_{p^n}=p^n-(k^2)_{p^n}$, si $p^n$ divise $k^2$ alors $(-k^2)_{p^n}=-(k^2)_{p^n}=0$.
Il y a $p^{\lfloor n/2\rfloor}$ valeurs de $k$ telles que $p^n$ divise $k^2$ (on distingue les cas $n$ pair et $n$ impair).
Par suite $S=p^n(p^n-p^{\lfloor n/2\rfloor})-S$.
En effet il existe $a$ tel que $a^2\equiv -1\pmod n$ et le même raisonnement fonctionne.
Le nombre de $k$ tels que $n$ divise $k^2$ est égal à $\displaystyle\prod_k p_k^{\lfloor e_k/2\rfloor}$ d'où $2S=n(n-\displaystyle\prod_k p_k^{\lfloor e_k/2\rfloor})$.
Je n'y aurais pas pensé si tu ne m'avais pas donné la bonne formule.
Cela démontre la conjecture initiale $\sum _{ [[0,n]]} ( i^2)_n \leq \frac {n(n-1)}{2}$ quand l'entier $n$ n'est divisible ni par $4$, ni par un nombre premier congru à $3$ modulo $4$.
J'ai remarqué que ton inégalité était déjà conjecturée mais seulement pour pour $n$ premier avec $n\equiv 3\mod 4$. Par exemple ce lien
même si tu me coupes l'herbe sous les pieds : j'arrivais, je crois, à une formule équivalente à celle de ton lien, mais à partir d'un calcul différent. Je vérifie ce que j'ai écrit et posterai j'espère bientôt.
Cordialement
Paul
pour relancer le fil, quelques gouttes d'eau:
$\Delta_{2(2n+1)}=2\Delta_{(2n+1)}$ (démontré)
$\dfrac{\Delta_{2^n}}{2^n}=(2^{\lfloor {\frac{n}{2}}\rfloor}-1) +(2^{\lfloor {\frac{n-1}{2}}\rfloor}-1) $ (démontré)
Si $p$ et $q$ sont premiers distincts, congrus à $3$ modulo $4$ et différents de $3$,
alors $\dfrac{\Delta_{pq}}{pq}=h(p)+h(q)$ et (EDIT) $\dfrac{\Delta_{3q}}{3q}=\frac{1}{3}+h(q)$ (à démontrer)
Le $\Delta$ d'un produit de premiers distincts congrus à $3$ modulo $4$ et différents de $3$ est un multiple de ce produit (conjecturé)
Merci pour vos futures aides!
Cordialement
Paul