Show that there exist $k\in\{1,2,\cdots,n\}$ such that $\frac{1}{n}\sum_{i=1}^{n}\left(\{kx_{i}\}-\frac{1}{2}\right)^2>\frac{1}{12}-\frac{1}{6n}$

The following question has post mathsatck :Nice problem, perhaps from a question of expectation.The problem seemed so elementary, but I had tried to solve it for a long time and eventually failed.I 'd like to get your help or help out here.Thanks!

Show that: for any real numbers $x_{1},x_{2},\cdots,x_{n}$, there exist $k\in\{1,2,\cdots,n\}$ such that $$\dfrac{1}{n}\sum_{i=1}^{n}\left(\{kx_{i}\}-\dfrac{1}{2}\right)^2>\dfrac{1}{12}-\dfrac{1}{6n},$$ where $\{x\}=x-\lfloor x\rfloor$.

• What is the original source? Note that the estimate is not sharp already for $n=2$. – Fedor Petrov Sep 13 '18 at 11:33
• It is said from Imo's gold creat and giver the new national team discuss it – function sug Sep 13 '18 at 12:12
• What is "posti mathsatck"? – Gerry Myerson Sep 13 '18 at 13:13
• @GerryMyerson I think, "posted on math.stackexchange":) – Fedor Petrov Sep 13 '18 at 13:48
• I'm happy to see that, after two days, OP has changed "posti" to "post". How long until we get some action on "mathsatck"? – Gerry Myerson Sep 15 '18 at 22:39

This isn't a full proof, but I expect it will get you most of the way there. Let $B_2(x)=x^2-x+\frac16$ be the 2nd Bernoulli polynomial, so the quantity that you're trying to estimate is $$\frac1n\sum_{i=1}^n \left(B_2(\{kx_i\}) + \frac1{12}\right) = \frac1n\sum_{i=1}^n B_2(\{kx_i\}) + \frac1{12}.$$ The reason I've written it this way is because there is a nice estimate for sums of Bernoulli polynomials paired against the Fejér kernel: for all $x\in\mathbb R$, $$\sum_{k=1}^K \left(1-\frac{k}{K+1}\right)B_2(\{kx\}) \ge -\frac1{12}.$$ This is a special case of a theorem that I first saw in a paper by Blanksby and Montgomery . Hindry and I give the proof of this specific case in , see Proposition 3.1 and Corollary 3.2. The proof uses the elementary theory of Fourier series.

So, if you average the $B_2$ part of the sum, weighted by the Fejér kernel, and flip the sums, you get $$\sum_{k=1}^K \left(1-\frac{k}{K+1}\right)\frac1n\sum_{i=1}^n B_2(\{kx_i\}) = \frac1n\sum_{i=1}^n\sum_{k=1}^K \left(1-\frac{k}{K+1}\right) B_2(\{kx_i\}) \ge -\frac1{12}.$$ This will give you a nice lower bound for the weighted average of your sums, and it remains to use this to deduce that at least one of the terms can't be too small.

BTW, Blanksby and Montgomery used their lemma to deduce a result related to Lehmer's conjecture on a lower bound for the height (Mahler measure) of an algebrac number, and Hindry and I used it for studying a conjecture of Lang on lower bounds for the canonical height of points on elliptic curves.

 Blanksby, P.E., Montgomery, H.L. :Algebraic integers near the unit circle. Acta Arith. 18, 355-369 (1971)

 Hindry, M, Silverman, J: The canonical height and integral points on elliptic curves, Inventiones Math 93, 419-450 (1988)

• @Silverman: the number $K$ is an arbitrary positive integer? – Venkataramana Sep 13 '18 at 15:52
• @Venkataramana Yes, in the inequality that I wrote, $K$ is an arbitrary positive integer. For the posted problem, clearly one would take $K=n$. But using a general $K$ will yield a more general result. And in many applications, including the applications in  and , the added flexibility is needed. – Joe Silverman Sep 13 '18 at 15:59
• @Silverman: thank you ; I was thinking of using $K=n$ (your estimate does solve the posted problem if we take $K=n$ , so why the phrase "isn't a full proof"?). – Venkataramana Sep 13 '18 at 16:08
• Since the sum of coefficients $\sum (1-k/(n+1))$ equals $n/2$, this gives exactly what is stated! (with non-strict inequality, but I guess this is not a big deal to make it strict studying when all equalities occur). – Fedor Petrov Sep 13 '18 at 16:08
• @Venkataramana I didn't do the substitution and check that it gave the desired result (due to having to stop typing and go do something else), so that's why I said it wasn't complete. – Joe Silverman Sep 13 '18 at 17:14

Here's an elementary proof of the inequality $$(1) \qquad\qquad \sum_{k=1}^{N-1} \left(1-\frac{k}{N}\right)B_2(\{kx\}) \ge \frac1{12N} - \frac1{12}. \qquad\qquad\phantom{(1)}$$ This is nearly the same as the inequality cited by Joe Silverman (with $N=K+1$), but with the lower bound improved from $-\frac1{12}$ to $\frac1{12N} - \frac1{12}$. This is best possible; equality holds iff $x = m/N$ for some integer $m$ with $\gcd(m,N)=1$. The slight improvement by $\frac1{12N}$ seems to be exactly what's needed to prove the inequality posed by function sug.

Proof: We prove for any $x_1,\ldots,x_N \in \bf R$ the inequality $$(2) \qquad\qquad\qquad \sum_{i=1}^N \sum_{j=1}^N B_2(\{x_i-x_j\}) \geq \frac1{6N}, \qquad\qquad\qquad\phantom{(2)}$$ with equality iff the $x_i \bmod 1$ are a permutation of $\{x_0 + (m/N): 0 \leq m < N\}$ for some $x_0$. To recover (1) from (2), set $x_k = kx$, remove the terms with $i=j$ (which contribute $N/6$ to the total), and divide by 2N.

Permuting the $x_i$ does not change the double sum in (2). If the $x_i \bmod 1$ are a permutation of $\{x_0 + (m/N): 0 \leq m < N\}$ then the sum in (2) is $N \sum_{i=0}^{N-1} B_2(i/N)$, which indeed equals $1/6N$. We next show that this is minimal. Permute the $x_i$ so that $x_1 \le x_2 \le x_3 \le \cdots \le x_N \le x_1 + 1$, and write the sum in (2) as $$\sum_{i=1}^N \sum_{j=1}^N B_2(\{x_{i+j}-x_j\}),$$ with the index $i+j$ taken $\!\!\mod N$. Then for each $i$ the fractional parts $\{x_{i+j}-x_j\}$ in the inner sum total $i$. Since $B_2$ is convex upwards, this inner sum is minimized when $\{x_{i+j}-x_j\} = i/N$ for each $j$. This is the case when each $x_m \equiv x_0 + m/N$, and that sufficient condition is also necessary at least when $i=1$. This completes the proof. $\Box$