# Proving $\sum_{i=1}^{n}\sum_{j=1}^{n}\left\{\frac{x_{i}}{x_{j}}\right\}\le \frac{9}{14}n^2$？

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.

• I think it is pretty clear that the question is "Is it true that $\sum \left\{ \tfrac{x_i}{x_j} \right\} \leq \tfrac{9}{14} n^2$ for all positive real numbers $(x_1, x_2, \ldots, x_n)$?" Also with an implied question: "What is the smallest constant which can replace $9/14$ here?" Commented Jan 3 at 16:20
• Perhaps $\{x\}+\{1/x\}<3/2$ provides a good bound. I think it gives $\frac{3}{2}\binom{n}{2}+n$, or $\frac34$ instead of$\frac{9}{14}$. Commented Jan 3 at 16:23
• @TheBestMagician: This gives the bound $(3/4)n^2 +O(n)$, which however is worse than $9/14<3/4$. Commented Jan 3 at 16:26
• If you put $c_m = \text{sup} \tfrac{1}{m(m-1)} \sum_{i,j=1}^m \left\{ \tfrac{x_i}{x_j} \right\}$, then we have $c_2 \geq c_3 \geq c_4 \geq \cdots$. The sup is over $\mathbb{R}_{>0}^m$. (Proof: Just take the sum $\sum_{i,j=1}^n \left\{ \tfrac{x_i}{x_j} \right\}$ and write it as a linear combination of the $\binom{n}{m}$ sums over $m$-element subsets of $\{ x_1, x_2, \ldots, x_n \}$.) So @TheBestMagician's observation is that $c_2 = 3/4$, and it seems like it would be worth computing the next few values of $c_m$. Commented Jan 3 at 16:33
• For the lower bound, if we take $n/2$ numbers slightly bigger than $1$ and $n/2$ numbers slightly less than $2$ then we can have a constant arbitrarily close to $\frac{5}{8}$ (which is very slightly less than $\frac{9}{14}$). Commented Jan 3 at 18:25

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.

• you're very smart. Commented Jan 4 at 13:53
• @TheSimpliFire Not really. I just picked up some tricks over the years and some of them work occasionally. You can easily do the same: just put everything you meet in your mouth and try to chew and swallow it. In mathematics, in the worst case scenario you'll get a slight indigestion and in the best case you'll grow wings or gills :lol: Commented Jan 4 at 14:01
• @fedja: This (your response to TheSimpliFire) is a nice attempt, but you must have noticed yourself, as everyone else has, I'm sure, that there is a certain type of (analysis) question, of which this one is a good example, that remains unanswered until you or Terry come along. Commented Jan 4 at 17:05
• So something is implausible about the claim "anyone can do it"... Commented Jan 4 at 17:06
• @ChristianRemling It is plausible, trust me. If you want to refute my claim, show me somebody who followed my (or Terry's) advice about how to approach math for 10 years or so and hasn't succeeded. About most people I certainly can only repeat Chesterton's famous quote "The Christian ideal has not been tried and found wanting. It has been found difficult and left untried.". And yeah, it does require certain effort to become Terry Tao. With me it is much easier: just be omnivorous and forget the ideas that some problems are not worth trying and that one's time is too valuable to play games. Commented Jan 4 at 18:02

Too long for a comment.

For $$c>0$$, the following two claims are equivalent.

Claim 1. An inequality $$\sum_{i=1}^{n}\sum_{j=1}^{n}\left\{\dfrac{x_{i}}{x_{j}}\right\}\leqslant cn^2$$ holds for all positive numbers $$x_1,\ldots,x_n$$.

Claim 2. An inequality $$\sum_{i=1}^{n}\sum_{j=1}^{n}\left\{\dfrac{x_{i}}{x_{j}}\right\}u_iu_j\leqslant cn\sum u_i^2$$ holds for all positive numbers $$x_1,\ldots,x_n$$ and all real $$u_1,\ldots,u_n$$.

Clearly, Claim 2 yields Claim 1 by taking $$u_i=1$$ for all $$i$$. Now assume that Claim 1 holds for all $$n$$. Proving Claim 2, we may suppose that $$u_i$$ are non-negative (otherwise replace $$u_i$$ to $$|u_i|$$, LHS can only increase and RHS does not change), and also rational (by continuity) and finally integer (by homogenuity). Then apply Claim 1 to a multiset containing $$u_i$$ elements equal to $$x_i$$ for all $$i=1,2,\ldots,n$$. We get $$\sum_{i=1}^{n}\sum_{j=1}^{n}\left\{\dfrac{x_{i}}{x_{j}}\right\}u_iu_j\leqslant c\left(\sum u_i\right)^2\leqslant cn\sum u_i^2,$$ that is, Claim 2 holds.

Now in order to use Bochner's positive definite kernel theorem we denote $$x_i=e^{t_i}$$, then Claim 2 deals with a symmetric matrix $$f(t_i-t_j)$$ for $$f(t):=(\{e^t\}+\{e^{-t}\})/2$$. If $$f(t)=\int_{\mathbb{R}} e^{it\xi}d\mu(\xi)$$ for a real signed measure $$\mu=\mu_+-\mu_-$$, then $$\sum_{j,k} f(t_j-t_k)u_ju_k=\int \left|\sum_{j=1}^n u_je^{it_j\xi}\right|^2d\mu(\xi)\leqslant cn\sum_{j=1}^n u_j^2$$ for $$c=\mu_+(\mathbb{R})$$.

Thus, if $$\mu_+(\mathbb{R})\leqslant 9/14$$, the inequality holds.

• you're smart. ${}{}$ Commented Jan 3 at 22:38
• So, we are to take the Fourier transform $\hat{f}$ of your function $f$, and then compute $\int \max(\hat{f}, 0)$? Commented Jan 4 at 1:56
• Ignoring convergence, $\int (\{e^t\}+\{e^{-t}\})/2 e^{iwt} dt = \int \{e^t \} \cos (wt) dt$, which is $\int_{-\infty}^0 e^t \cos(wt) dt + \sum_{n=1}^{\infty} \int_{\log n}^{\log (n+1)} (e^t-n) \cos(wt) dt$. Commented Jan 4 at 2:32
• If we stop the sum at $n=N-1$ instead of $n=\infty$, this is $\tfrac{1}{w} \sum_{n=2}^{N-1} \sin(w \log n) + \tfrac{N-1+w^2}{w(1+w^2)} \sin(w \log N) + \tfrac{N}{1+w^2} \cos (w \log N)$. (Thanks Mathematica!) To a naive combinatorialist like me, this doesn't look convergent. But I'm sure analysts have their ways to keep going :) Commented Jan 4 at 2:34
• maybe we can find $f(x,t)$ such $$\sum_{i,j=1}^{n}\{\frac{x_{i}}{x_{j}}\}\le\dfrac{9}{14}n^2-\int_{0}^{1}(\sum_{i=1}^{n}f(x_{i},t))^2dt?$$ Commented Jan 4 at 7:12

Update 04.01.2024

The answer below is incorrect, as it only takes into account sets with two groups of $$x_i$$. As fedja showed in his brilliant answer, certain sets with three groups (of relative size $$2,3,2$$) will give the OP's bound $$9/14$$. While the OP's present example does not give this value (but $$111/196$$, see my comments above), the set \begin{align} x_i=\begin{cases} 1+i \epsilon & 0 leads to $$S_\infty=\frac{9}{14}$$ as claimed.

I assume that $$\{x_i\}$$ denotes the fractional part of $$x_i>0$$. As already suggested by @AlekseiKulikov in the comments above, a maximal set of $$x_j$$ is \begin{align}\tag{1}\label{eq:1} x_i = \begin{cases} 1+i \epsilon & 0 < i \leq n/2 \\ 2-i \epsilon & n/2 < i \leq n, \end{cases} \end{align} with $$0<\epsilon\ll 1$$. Then, \begin{align}\tag{2}\label{eq:2} S_n=\lim_{\epsilon\to0^+}\frac{1}{n^2} \sum_{i,j=1}^n \left\{ \frac{x_i}{x_j} \right\} = \begin{cases} \frac 5 8 - \frac 1 {4n} & n \text{ even}\\ \frac 5 8 - \frac {n-3/8}{(2n-1)^2} & n \text{ odd,} \end{cases} \end{align} which goes to $$S_\infty=5/8$$ from below for large $$n$$. This is slightly smaller than $$9/14$$.
For arbitrary integer accumulation values $$x_+,x_-$$ instead of the integers $$1,2$$ in \eqref{eq:1}, the limiting values $$S_\infty(x_+,x_-)$$ are given by:
\begin{align} \begin{array}{c|cccccccccc} x_+ \, \backslash \, x_-& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 1 & \frac{1}{2} & \frac{5}{8} & \frac{7}{12} & \frac{9}{16} & \frac{11}{20} & \frac{13}{24} & \frac{15}{28} & \frac{17}{32} & \frac{19}{36} & \frac{21}{40} \\ 2 & \frac{3}{8} & \frac{1}{2} & \frac{13}{24} & \frac{5}{8} & \frac{19}{40} & \frac{7}{12} & \frac{25}{56} & \frac{9}{16} & \frac{31}{72} & \frac{11}{20} \\ 3 & \frac{1}{3} & \frac{13}{24} & \frac{1}{2} & \frac{25}{48} & \frac{17}{30} & \frac{5}{8} & \frac{37}{84} & \frac{49}{96} & \frac{7}{12} & \frac{49}{120} \\ 4 & \frac{5}{16} & \frac{3}{8} & \frac{25}{48} & \frac{1}{2} & \frac{41}{80} & \frac{13}{24} & \frac{65}{112} & \frac{5}{8} & \frac{61}{144} & \frac{19}{40} \\ 5 & \frac{3}{10} & \frac{19}{40} & \frac{17}{30} & \frac{41}{80} & \frac{1}{2} & \frac{61}{120} & \frac{37}{70} & \frac{89}{160} & \frac{53}{90} & \frac{5}{8} \\ 6 & \frac{7}{24} & \frac{1}{3} & \frac{3}{8} & \frac{13}{24} & \frac{61}{120} & \frac{1}{2} & \frac{85}{168} & \frac{25}{48} & \frac{13}{24} & \frac{17}{30} \\ 7 & \frac{2}{7} & \frac{25}{56} & \frac{37}{84} & \frac{65}{112} & \frac{37}{70} & \frac{85}{168} & \frac{1}{2} & \frac{113}{224} & \frac{65}{126} & \frac{149}{280} \\ 8 & \frac{9}{32} & \frac{5}{16} & \frac{49}{96} & \frac{3}{8} & \frac{89}{160} & \frac{25}{48} & \frac{113}{224} & \frac{1}{2} & \frac{145}{288} & \frac{41}{80} \\ 9 & \frac{5}{18} & \frac{31}{72} & \frac{1}{3} & \frac{61}{144} & \frac{53}{90} & \frac{13}{24} & \frac{65}{126} & \frac{145}{288} & \frac{1}{2} & \frac{181}{360} \\ 10 & \frac{11}{40} & \frac{3}{10} & \frac{49}{120} & \frac{19}{40} & \frac{3}{8} & \frac{17}{30} & \frac{149}{280} & \frac{41}{80} & \frac{181}{360} & \frac{1}{2} \\ \end{array}\end{align} The maximum value $$S_\infty=5/8$$ is taken for $$x_- = 2x_+$$.
• I think that this choice of $x_i$ gives the maximum possible value for the sum. Commented Jan 3 at 19:59