# 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 seems very interesting, perhaps from a question of expectation.

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$$. (this problem Creat by Xi Xi )

• Remark: it is enough to prove that, for any real number $x$, we have $n^{-1} \sum_{k=1}^n f(\{kx\}) > 1/12-1/(6n)$ with $f(t) = (t-1/2)^2$. Then the bound ways true when taking the average over $i$, and thus there exists a $k$ which satisfies the bound for all $i$. The bound above seems plausible; maybe try Fourier series? Mar 18 '18 at 14:54
• it seem Fourier series? Mar 18 '18 at 15:13
• Please improve your post by adding more context: where did the inequality aries? Why is it very interesting? Is it related to any other topics of interest? Posts that merely state a problem are discouraged on this site. Mar 18 '18 at 22:43
• There are a lot of different topics potentially involved here: probabilistic inequalities, geometric inequalities, Fourier-analytic inequalities and so on. Please add some attempt (and the contest in which this problem occurred), it would be a shame to see this question closed by lack of context. Mar 18 '18 at 23:01
• Looks like the formula for $[variance](en.wikipedia.org/wiki/Variance#Definition)$ indeed $\text{Var}(X) = \mathbb{E}[(X - \mathbb{E}[X])^2 ] = \mathbb{E}[X^2] - \mathbb{E}[X]^2$. And if we look $\{ k x\} \in [0,1]$ is essentially random but I get: $$\mathbb{E}[\{ kx\}] = \int_0^1 (x - 1/2)^2 \, dx = \frac{1}{6}$$ So at least the $\frac{1}{12}$ is reasonable. This could be a pigeonhole problem, if we could choose the correct regions of $[0,1]^n$. Mar 28 '18 at 16:00

Not a complete answer but two hopefully interesting geometric interpretations.

The problem is non-trivial only for $n\geq 3$.
Let $X=(x_1,\ldots,x_n)$. $X,2X,\ldots nX$ are collinear on a line through the origin in $\mathbb{R}^n$, and we have to prove that at least one of these points is sufficiently far from $E=\left(\frac{1}{2},\ldots,\frac{1}{2}\right)+\mathbb{Z}^n$, precisely at a distance $\geq\sqrt{\frac{n}{12}-\frac{1}{6}}$. On the other hand, if we assume that $X,2X,\ldots,nX$ all lie in $F$, a $\sqrt{\frac{n}{12}-\frac{1}{6}}$ neighbourhood of $E$, then $F\cap\frac{F}{2}\cap\ldots\cap\frac{F}{n}$ has to be non-empty. The distance between $\left(\frac{1}{2},\ldots\frac{1}{2}\right)$ and $\left(\frac{1}{4},\ldots\frac{1}{4}\right)$ is $\frac{\sqrt{n}}{4}$, hence if $F_\rho$ is a $\rho$-neighbourhood of $E$ and $\rho<\frac{2}{3}\cdot\frac{\sqrt{n}}{4}=\frac{\sqrt{n}}{6}$ then $F_\rho\cap\frac{F_\rho}{2}=\emptyset$. By imposing that $\frac{F_\rho}{a}\cap\frac{F_\rho}{b}\neq\emptyset$ for any $a,b\in[1,n]$ we may improve such bound till reaching the wanted conclusion.

As an alternative, we may cover $(0,1)^n$ with $n-1$ sets $A_1,A_2,\ldots,A_{n-1}$ with the same diameter $d$. By the pigeonhole principle at least two points among $X,2X,\ldots,nX\pmod{1}$ belong to the same $A_j$, hence by linearity there is some point among $X,2X,\ldots,nX$ with a distance $< d$ from $\mathbb{Z}^n$, hence with a distance $\geq\frac{\sqrt{n}}{2}-d$ from $E$.

It might be useful to consider that $$\left(\{x\}-\frac{1}{2}\right)^2 =\frac{1}{12}+\sum_{m\geq 1}\frac{\cos(2\pi m x)}{\pi^2 m^2}$$ By letting $x_0=0$ and $z_i=e^{2\pi i x_i}$ the question can be rephrased as $$\text{For some }k\in[1,n],\qquad p_k=\sum_{i=0}^{n}\text{Re}\,\text{Li}_2(z_i^k)>0.$$ Let us assume that the opposite inequality $p_k\leq 0$ holds for any $k\in[1,n]$ and let us consider $$f(u) = \sum_{m\geq 1}-\frac{p_m}{m}u^m=\text{Re}\sum_{m\geq 1}-\frac{u^m}{m}\sum_{i=0}^{n}\sum_{h\geq 1}\frac{z_i^{mh}}{h^2}=\sum_{i=0}^{n}\text{Re}\sum_{h\geq 1}\frac{-\log(1-uz_i^h)}{h^2}.$$ By the assumption all the coefficients of $f(u)$ up to $u^n$ are non-negative.
By formally exponentiating both sides $$\exp\left(\frac{6}{\pi^2}f(u)\right) = \prod_{i=0}^{n}\prod_{h\geq 1}\frac{1}{|1-uz_i^h|^{\frac{6}{\pi^2 h^2}}}=\frac{1}{|1-u|}\prod_{i=1}^{n}\prod_{h\geq 1}\frac{1}{|1-uz_i^h|^{\frac{6}{\pi^2 h^2}}}$$ where the modulus of the LHS is $\gg 1+o(|u|^n)$ as $u\to 0$. This gives $$\prod_{i=1}^{n}\prod_{h\geq 1}\frac{1}{|1-uz_i^h|^{\frac{6}{\pi^2 h^2}}} \gg |1-u|\left(1+o(|u|^n)\right)$$ leading to a contradiction for $u\to 0^+$ or $u\to 0^-$.

• I wonder your answer is hard for high school contest. Mar 24 '18 at 16:54
• @TakahiroWaki: it is for sure, and probably I am just missing an elementary solution. Just pointing out that the complex analytic machinery related to generating functions performs its magic here. Mar 24 '18 at 17:12
• It seems to me that the first strategy can't work. To get $\tfrac{\sqrt{n}}{2} - d > \sqrt{n/12}$, we need $d < \tfrac{3-\sqrt{3}}{6} \sqrt{n}$. A shape of diameter $d$ fits inside a ball of radius $d$, so its volume is at most $\tfrac{\pi^{n/2}}{(n/2)!} d^{n}$. We have $(n/2)! > \left( \tfrac{n}{2e} \right)^{n/2}$, so the volume is at most $(2 \pi e)^{n/2} \left( \tfrac{3-\sqrt{3}}{6} \right)^n \approx (0.873349)^n$ (please check my work!). So $n-1$ such sets cannot cover the cube of volume $1$. Sep 13 '18 at 14:10
• I meant to say "second strategy". Sep 13 '18 at 14:16
• How does the last inequality lead to a contradiction as $u \to 0$? Would the generating function idea work if instead of $k \in \{1,\dots,n\}$ we had $k \in \{1,\dots,\log n\}$, say? I don't think $k$ going up to any arbitrary function going to infinity with $n$. Sep 13 '18 at 18:31