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
Réponses
-
Dans la suite, on note $\{x\}$ la partie fractionnaire, et je renote ton $a(n)$ en $S_n$.
\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. -
Est-il difficile de démontrer que $a(n):=\sum _{ [[0,n]]} ( i^2)_n \leq \frac {n(n-1)}{2}$ ?
Voici ce que je vois, on a $( i^2)_n=i^2-n\lfloor \frac {i²}n\rfloor$ donc cela rivient à démontrer que$$\sum_{i=1}^{n-1} i^2 - \sum_{i=1}^{n-1} i \leq n\sum_{i=1}^{n-1} \lfloor \frac {i²}n\rfloor$$Autrement dit $\frac{1}{3}\left(n-1\right)\left(n-2\right)\le \sum _{i=1}^{n-1}\lfloor \frac{i^2}{n}\rfloor $edit A mort la 504 je viens de voir le message de noix de totosedit 2 J'ajoute il me semble qu'on a l’égalité si n est un nombre premier de la forme 4n+1
Le 😄 Farceur -
Je continue un chouia le message ci-dessus, en supposant toujours $n$ impair. D'après ci-dessus
\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).$$ -
Grand merci à tous deux pour votre attention à ma question et votre aide.
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 -
Je sais faire la partie "facile" : si $n$ est sans carré et ses diviseurs premiers sont congrus à $1$ ou $2$ modulo $4$ alors $a(n)=S_n=\dfrac{n(n-1)}2$.
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$. -
L'estimation asymptotique obtenue plus haut est cohérente avec ce que l'on trouve dans ce type de problème, qui est intéressant à plus d'un titre.
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 ! -
Merci Jandri
Sur ce coup, je comprends!
et m'en veux d'autant plus de ne pas y avoir pensé tout seul.
Cordialement
Paul
-
Je n'avais pas vu le dernier message de noix de totos. C'est bon pour mon ego!
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
-
Merci pour ton témoignage.
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.
-
Bonjour
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.On suppose ici que $n$ est tel que $kn$ n'est pas un carré parfait pour $0<k<n$
$$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.Bonne journée,
Al-Kashi -
Il faut savoir que la recherche d'une forme close n'est pas l'activité majoritaire de l'arithméticien, car :
(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). -
BonjourMerci pour ton retour ndt. N'ayant pas les connaissances suffisantes pour ce type d'approximation, j'ai juste essayé de comparer ton résultat à ta première approximation. Comment faut-il comprendre un terme d'erreur en $O \left( n^{3/2+o(1)} \right)$?Al-Kashi
-
C'est $n^{3/2+\varepsilon}$ avec $\varepsilon > 0$ aussi petit que tu veux.
-
Bonjour
$\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 -
Bonjour, pour n=1, c'est vrai ?
Le 😄 Farceur -
Bonjour Gebrane
Il me semble que c'est vrai si $n=1$. Je dis une sottise ?
Cordialement
Paul -
Rien de tel, mais je suis à moitié endormi, donc je la boucle pour ne pas dire des bêtises. Je verrais cela aprèsedit en ce matin, je vois bien que c'est juste pour n=1
Le 😄 Farceur -
@depasse
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$. -
Je pense qu'on peut généraliser à $n=\displaystyle\prod_k p_k^{e_k}$ et $n=2\displaystyle\prod_k p_k^{e_k}$ avec les $p_k$ premiers congrus à 1 modulo 4.
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})$. -
Ah Jandri, que serais-je sans toi qui toujours voles si rapidement et gentiment à mon secours!
-
J'avais cru que l'inégalité était évidente et j'avais utilisé $\lfloor \frac{i^2}{n}\rfloor>\frac{i^2}{n} - 1$, mais j'avais commis une erreur dans mes calculs. En réalité, on obtient plutôt la minoration suivante : $\frac{1}{3}\left(n-1\right)\left(n-2\right)-\frac 12 (n-1)\le \sum _{i=1}^{n-1}\lfloor \frac{i^2}{n}\rfloor$.Je commence à penser que cette inégalité est très difficile à démontrer, étant donné que même le spécialiste @noix de totos n'arrive pas à la prouver.Le 😄 Farceur
-
@depasse ton inégalité est démontrée pour n premier avec $n\equiv 3\mod 4$.
Le lien dit que ta somme est $\frac{n(n-1)}2+\sum_{a=1}^{n-1} a \left( \frac{a}{n} \right)$ avec $\sum_{a=1}^{n-1} a \left( \frac{a}{n} \right)=-nh\leq 0 $ pour $n>3$.
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( Tu peux remarquer que ta somme est inférieure à $\frac{n(n-1)}2\iff \sum_{a=1}^{n-1} a \left( \frac{a}{n} \right)\leq 0$.Le 😄 Farceur -
J'ajoute puisque un nombre premier est de la forme 3+4k ou 1+4k , l’inégalité est démontré pour les nombres premier. Pour revenir aux entiers, je pense on peut s'en sortir avec la généralisation de Jandri
Le 😄 Farceur -
Merci gebrane
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 -
Bonjour,
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
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 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
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 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
- 312 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
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 2
2 Invités