Conjecture $ \sum _{i=1}^{n-1}\lfloor \frac{i^2}{n}\rfloor \ge \frac{\left(n-1\right)\left(n-2\right)}3$ where $n\in\mathbb N^*$

Question

This is a question I also asked on MSE . If it is frowned upon to ask the same question on both threads, you can vote to close this thread.

Let $n \in \mathbb {N^*}$ and $$S_n = \sum_{k=1}^{n-1} (k^2 \bmod n)$$

with the first values 0, 1, 2, 2, 10, 13, 14, 12, 24, 45, 44, 38, 78, 77, 70, 56, 136, 129, 152, 130, 182, 209, 184, 148, 250, 325, 288, 294, 406, 365, 372, 304, 484, 561, 490, 402, 666, 665, 572, 540, 820, 805, 860, 726, 840, 897, 846, 680, 980, 1125

​​and it appears that $$S_n\leq \frac {n(n-1)}2$$

We can show that $$S_n\leq \frac {n(n-1)}2\iff \sum _{i=1}^{n-1}\left\lfloor \frac{i^2}{n}\right\rfloor \ge \frac{\left(n-1\right)\left(n-2\right)}3$$ we have equality if $n$ is prime and $n \equiv 1 \mod 4$

Do you think this inequality is true?

Addition :

We fix a prime number $p$ that satisfies $p \equiv 1 \pmod{4}$. Let $\forall n \in \mathbb{N}^*$, $S_n$ be defined as the sum from $k = 0$ to $p^n - 1$ of $(k^2)_{p^n}$. Numerically, it appears that $2S_n = p^n(p^n - p^{\lfloor n/2 \rfloor})$. If we can prove this equality, we can deduce inequality (the object of the thread) in many cases

Answer 1

$\newcommand{\qr}[2]{\left( \tfrac{#1}{#2} \right)}$I'll prove the result for $n$ odd and square free; the general case should be doable by a messier version of the same approach. I'll attack the version of the problem where we want to show that $$\sum_{k=0}^{n-1} (k^2 \bmod n) \leq \binom{n}{2}.$$

Fix $n$. For any integer $j$, let $S(j)$ be the number of square roots of $j$ modulo $n$. So the goal is to show that $$\sum_{j=0}^{n-1} j S(j) \leq \binom{n}{2}.$$ If $n=p$ is an odd prime, we have $$S(j) = 1 + \qr{j}{p}$$ where $\qr{j}{p}$ is the quadratic residue symbol. More generally, if $n = p_1 p_2 \cdots p_r$ is an odd square free number, then, by the Chinese remainder theorem, $$S(j) = \prod_{i=1}^r \left( 1 + \qr{j}{p_i} \right) = \sum_{d|n} \qr{j}{d}.$$ (Here $\qr{j}{d}$ is the Jacobi symbol.) So we want to show $$\sum_{j=0}^{n-1} j \sum_{d|n} \qr{j}{d} \leq \binom{n}{2}.$$ Interchanging summation, we want to show that $$\sum_{d|n} \sum_{j=0}^{n-1} j \qr{j}{d} \leq \binom{n}{2}.$$ Now, the $d=1$ summand is $\sum_{j=0}^{n-1} j = \binom{n}{2}$. So it will suffice to show that the other summands are negative.

For $d>1$, the Jacobi symbol $\qr{j}{d}$ take the values $1$ and $-1$ equally often on the residues modulo $d$. Thus, $$\sum_{j=ad}^{ad+d-1} j \qr{j}{d} = \sum_{j=0}^{d-1} (ad+j) \qr{j}{d} = ad \sum_{j=0}^{d-1} \qr{j}{d} + \sum_{j=0}^{d-1} j \qr{j}{d} = \sum_{j=0}^{d-1} j \qr{j}{d}.$$ So, if we group the sum $\sum_{j=0}^{n-1} j \qr{j}{d}$ into blocks of length $d$, we get $$\sum_{j=0}^{n-1} j \qr{j}{d} = \frac{n}{d} \sum_{j=0}^{d-1} j \qr{j}{d}.$$ So we are reduced to proving that $$\sum_{j=0}^{d-1} j \qr{j}{d} \leq 0. \quad (\ast)$$

If $d \equiv 1 \bmod 4$ (but $d>1$), so that $\qr{j}{d} = \qr{d-j}{d}$, then we can average the $j$ and $d-j$ terms in $(\ast)$ to get $$\sum_{j=0}^{d-1} j \qr{j}{d} = \sum_{j=0}^{d-1} \frac{d}{2} \qr{j}{d} = \frac{d}{2} \sum_{j=0}^{d-1} \qr{j}{d} = 0.$$ So the hard part is to prove $(\ast)$ for $d \equiv 3 \bmod 4$.

By a result of Dirichlet, for $d>3$ squarefree, $\equiv 3 \bmod 4$, we have $$\sum_{j=0}^{d-1} j \qr{j}{d} = - d h$$ where $h$ is the class number of $\mathbb{Q}(\sqrt{-d})$. See Wikipedia or me. This is one of a number of similar formulas -- see my answer here for relations between them when $d \equiv 7 \bmod 8$, and similar formulas could be worked out for other residue classes. In particular, $\sum_{j=0}^{d-1} j \qr{j}{d} < 0$, as desired.

Answer 2

Here is a modest start. If $n\geq 7$ is a prime congruent to $3$ modulo $4$, then $$S_n=\sum_{\ell=1}^{n-1}\left(\left(\frac{\ell}{n}\right)+1\right)\ell=\frac{n(n-1)}{2}+\sum_{\ell=1}^{n-1}\left(\frac{\ell}{n}\right)\ell=\frac{n(n-1)}{2}-nh_{\mathbb{Q}(\sqrt{-n})},$$ using (6.2) of VIII.6 in Fröhlich-Taylor: Algebraic number theory.

Answer 3

Another modest suggestion: Set $f(n)=\sum_{i=1}^{n-1}\lfloor i^2/n\rfloor-(n-1)(n-2)/3$. Then it seems to be the case that $f(ab)\ge f(a)+f(b)$ for all positive integers $a$ and $b$. (Checked for all $a,b$ where $ab\le75000$.) Since $f(n)\ge0$ for all primes $n$, one is reduced to prove this inequality. Maybe some clever manipulation of \begin{equation} \sum_{i=1}^{ab-1}\left\lfloor\frac{i^2}{ab}\right\rfloor=\sum_{0\le i<b, 0\le j<a}\left\lfloor\frac{(ai+j)^2}{ab}\right\rfloor \end{equation} yields some progress/insight?

Two more empirical observations (similar to Henri Cohen's comment regarding $p^n$ for $p\equiv3\pmod{4}$): It seems to be that \begin{equation} f(3^n) = \frac{5 - (-1)^n}{6}\cdot3^{\lfloor n/2\rfloor} - \frac{2}{3} \end{equation} and \begin{equation} f(p^n) = \frac{p^{\lfloor n/2\rfloor}-1}{2} \end{equation} for $p\equiv1\pmod 4$.