For any postive integer $n$ and for any postive real numbers $x_{1},x_{2},\cdots,x_{n}$, show that
$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left\{\dfrac{x_{i}}{x_{j}}\right\}\le \dfrac{9}{14}n^2$$
Let
\begin{align}
x_{i}&=1+i\varepsilon, &
i&=1,2,\cdots,\tfrac{2}{7}n \,,\\
x_{j}&=2-\left(j+\tfrac{2}{7}n\right)\varepsilon, &
j&=\tfrac{2}{7}n+1,\cdots,\tfrac{5}{7}n \,,\\
x_{k}&=4-\left(k+\tfrac{10}{7}n\right)\varepsilon,&
k&=\tfrac{5}{7}n+1,\cdots,n \,,
\end{align}
then
$$\sum_{i,j=1}^{n}\left\{\frac{x_{i}}{x_{j}}\right\}\to\frac{9}{14}n^2,\quad\varepsilon\to 0^+,\;n\to+\infty.$$
This inequality discovered by a Chinese student, and maybe this coefficient $\dfrac{9}{14}$ is the best.
Maybe
$$ \left(\{x\}-\frac{1}{2}\right)^2 =\frac{1}{12}+\sum_{m\geq 1}\frac{\cos(2\pi m x)}{\pi^2 m^2}$$
ADD it: conjecture:
$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left\{\dfrac{x_{i}}{x_{j}}\right\}\le \dfrac{9}{14}n^2-\dfrac{1}{7}\int_{0}^{1}\left(\left(\sum_{i=1}^{n}\cos{(a(x_{i}-t))}\right)^2+\left(\sum_{i=1}^{n}\sin{(a(x_{i}-t))}\right)^2\right)dt?$$
where $a=\arccos{(-\frac{3}{4})}$
But it still failed. The problem seems to be related to the series form of Bernoulli polynomials? Would love to see any better ideas. Thank you all.
Best Answer
OK, here is a fairly simple proof that for any positive integer $n$ and any positive real numbers $x_1,\ldots,x_n$, $$ \sum_{i,j=1}^{n}\left\{\frac{x_i}{x_j}\right\}\leq \frac{9}{14}n^2\,.$$ That the constant $\frac{9}{14}$ cannot be improved has already been shown by the OP. I wonder if the Chinese student who invented the problem had the same one in mind.
Consider the function $$ f(z)=\begin{cases} 1+z,&0\le z\le 1/2 \\ z+\frac 1z-1, &\frac 12\le z\le 2 \\ 1+\frac 1z, &z\ge 2 \end{cases} $$ Note that $f(z)=f(1/z)$ and $f(z)\ge\{z\}+\{1/z\}$ for all $z>0$. We shall show that $$ \sum_{i,j}f(x_i/x_j)u_i u_j\le \frac 97\|u\|_{\ell^1}^2 $$ for all non-negative sequences $u$ with finite support and for all $x_j>0$.
Note that $f$ is a nice continuous function that is increasing near $0$, decreasing near $+\infty$ and convex except for two singular points $\frac 12$ and $2$. The last property allows one to choose any subset of $x_j$, replace them by $tx_j$ and move $t$ up or down to increase (or, at least, keep constant) the LHS until some ratio between the moving $x_j$ and the stationary ones becomes $2$ or $\frac 12$. Doing that a few times, we'll arrive to the situation when the graph in which $i$ is joined with $j$ if and only if $x_i/x_j\in\{\frac 12,2\}$ is connected (otherwise just move a connected component until acquiring a new edge). In normal English that means that all $x_j$ are just powers of $2$ (times some irrelevant positive common factor).
Thus, subtracting $1$ from each entry, we see that our matrix entries are just $2^{-|i-j|}$ for $i\ne j$ and $0$ for $i=j$. where $1\le i,j\le m$ (we unite the $u_j$ for colliding $x_j$, of course). Let's call that matrix $A(m)$. We want to show that $$ \langle A(m)u,u\rangle=\sum_{i,j}A(m)_{ij}u_iu_j\le\frac 27\|u\|_{\ell^1}^2 $$ now.
It is time to move $u_i$. Notice first of all that we do not need zeroes in the middle: we can just move the support chunks together increasing the coefficient at each product $u_iu_j$ discarding the zero tail afterwards and reducing $m$. Next, assuming that we have full support, take some vector $v$ with sum $0$ and replace $u$ by $u+tv$. The RHS will not change until we kill one entry. The LHS will become $$ \langle A(m)u,u\rangle+2t\langle A(m)u,v\rangle+t^2\langle A(m)v,v\rangle $$ so, we cannot improve it and kill an entry only if $A(m)$ is negative definite on the zero sum subspace of $\mathbb R^m$. The last property fails for $m\ge 4$: just take $v=(2,1,-1,-2,0,0,\dots)$ to get $\langle A(m)v,v\rangle=0$. Thus we are interested in $m=2,3$ only. According to the last displayed formula, to find the optimal $u$, we need just to solve $A(m)u=e$ where $e$ is the vector of all $1$'s (the trivial instance of the Lagrange multiplier idea). For $m=2$, we get $u=(2,2)$ with the constant $\frac 14$ (Alexei's example). For $m=3$, we get $u=(1,\frac 32,1)$ and the ratio $\frac 27$ (the Chinese student example).
That's it.