Previously I have mentioned the following problem in an addition to the list of [Contest problems with connections to deeper mathematics](https://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/178158#178158). 


*Is there an infinite bounded sequence $(P\_n) \subset \mathbb{R}^2$ having $d(P\_i,P\_j) \cdot \sqrt{|i-j|} > 1$ for all $i \neq j$?*


It is not too hard to see that there is no such sequence if the square root is replaced by an exponent $< 1/2$. If on the other hand this exponent is raised by an $\varepsilon$, diophantine approximations apply and prove that $P\_n := (C\{n\sqrt{2}\},C\{n\sqrt{3}\})$ with $C \gg\_{\varepsilon} 0$ is an explicit sequence with the desired property. This follows easily by the two-dimensional case of Schmidt's theorem (although this does not say how large $C$ needs to be). Similarly, metric diophantine approximation yields the same with $\sqrt{2}$ and $\sqrt{3}$ replaced by Lebesgue-generic points of $[0,1]$; this is considerably easier to prove, giving a non-explicit construction, but still with an $\varepsilon$.


What should the answer be with $\varepsilon = 0$? 



Is there a bounded sequence of points in the plane with pairwise distances at least $1/\sqrt{|i-j|}$?
It seems that such a sequence exists. 


**1.** Firstly, we take an auxiliary sequence $a(n)=\{(n+1)\sqrt2\}$ for $n\geq 0$. For every $m>n$ the standard estimate yields, say,
$$
 |a(m)-a(n)|=|(m-n)\sqrt2-p|=\frac{|2(m-n)^2-p^2|}{(m-n)\sqrt2+p}>\frac1{10|m-n|};
$$
here $p=[(m+1)\sqrt2]-[(n+1)\sqrt2]\leq 8(m-n)$.


**2.** Now we construct the sequence of points $P\_i=(x\_i,y\_i)$ as follows. Let $i=\overline{\dots i\_2i\_1i\_0}$ be the binary representation of $i$. Set $m(i)=\overline{\dots i\_4i\_2i\_0}$ and $n(i)=\overline{\dots i\_5i\_3i\_1}$, and put $x\_i=a(m(i))$ and $y\_i=a(n(i))$.


Now take any $i>j$. Let $s$ be the minimal integer such that $2^{2s}\geq i-j$, hence $2^s<2\sqrt{i-j}$. Set $i'=\overline{\dots i\_{2s+1}i\_{2s}}=[i/2^{2s}]$ and $j'=\overline{\dots j\_{2s+1}j\_{2s}}=[j/2^{2s}]$. Then $j'\leq i'\leq j'+1$.


Assume that $i'=j'$. We have either $m(i)\neq m(j)$ or $n(i)\neq n(j)$ (w.l.o.g., $m(i)\neq m(j)$), and $|m(i)-m(j)|<2^s$ since $m(i)$ and $m(j)$ differ only in the last $s$ digits. Then we have 
$$
 d(P\_i,P\_j)\geq |x\_i-x\_j|=|a(m(i))-a(m(j))|>\frac1{10|m(i)-m(j)|}> \frac1{10\cdot 2^s}
 >\frac1{20\sqrt{i-j}}.
$$


Now assume that $i'=j'+1$; then it is easy to see that either $m(i')=m(j')+1$ or $n(i')=n(j')+1$ (it depend on the parity of the last index $k\geq 2s$ for which $i\_k\neq j\_k$; w.l.o.g. $m(i')=m(j')+1$). Then we have $0<m(i)-m(j)<2^{s+1}$, so similarly we get
$$
 d(P\_i,P\_j)\geq |x\_i-x\_j|=|a(m(i))-a(m(j))|>\frac1{10|m(i)-m(j)|}>\frac1{10\cdot 2^{s+1}}
 >\frac1{40\sqrt{i-j}}.
$$


Thus in any case we have $d(P\_i,P\_j)\cdot \sqrt{i-j}>\frac1{40}$. 


Now it remains to scale the whole picture with ratio 40.


