13
$\begingroup$

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 )

$\endgroup$
9
  • 4
    $\begingroup$ 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? $\endgroup$
    – D. Thomine
    Mar 18 '18 at 14:54
  • $\begingroup$ it seem Fourier series? $\endgroup$
    – math110
    Mar 18 '18 at 15:13
  • $\begingroup$ 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. $\endgroup$ Mar 18 '18 at 22:43
  • $\begingroup$ 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. $\endgroup$ Mar 18 '18 at 23:01
  • 1
    $\begingroup$ 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$. $\endgroup$
    – cactus314
    Mar 28 '18 at 16:00
3
$\begingroup$

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^-$.

$\endgroup$
5
  • $\begingroup$ I wonder your answer is hard for high school contest. $\endgroup$ Mar 24 '18 at 16:54
  • $\begingroup$ @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. $\endgroup$ Mar 24 '18 at 17:12
  • 1
    $\begingroup$ 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$. $\endgroup$ Sep 13 '18 at 14:10
  • $\begingroup$ I meant to say "second strategy". $\endgroup$ Sep 13 '18 at 14:16
  • 1
    $\begingroup$ 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$. $\endgroup$ Sep 13 '18 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.