17
$\begingroup$

Previously I have mentioned the following problem in an addition to the list of Contest problems with connections to deeper mathematics.

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$?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ Is it known (or a known open problem) whether there exist $a,b \in {\mathbb R} / {\mathbb Z}$ such that $P_n = (\{na\},\{nb\})$ works (i.e. a vector $v=(a,b)$ in the 2-torus such that $nv$ is at distance $> C /\sqrt{n}$ from the origin for some $C>0$ and all positive integers $0$)? $\endgroup$
    – Noam D. Elkies
    Commented Nov 18, 2014 at 3:04
  • $\begingroup$ @NoamD.Elkies: Actually I don't know the answer to this, and this could have been a part of the question. $\endgroup$
    – Vesselin Dimitrov
    Commented Nov 18, 2014 at 3:08
  • $\begingroup$ just an observation: taking $P_n=(10 \cos(n), 10 \sin(n) )$ gives a set of at 710 points and fails after that. Probably this has something to do with n \pmod \pi. $\endgroup$
    – joro
    Commented Nov 18, 2014 at 9:44
  • 2
    $\begingroup$ @joro: You cannot get an example lying on a circle (or on any rectifiable curve), because the smallest pairwise distance between $n$ points on such curve is $O(1/n)$. $\endgroup$
    – Ilya Bogdanov
    Commented Nov 18, 2014 at 11:01

1 Answer 1

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ In fact, in the second part we construct the sequence of integer points $(m(i),n(i))$ such that for all $i>j$ either $0<|m(i)-m(j)|<4\sqrt{i-j}$ or $0<|n(i)-n(j)|<4\sqrt{i-j}$. $\endgroup$
    – Ilya Bogdanov
    Commented Nov 18, 2014 at 13:31
  • $\begingroup$ Ilya: I happened to be investigating the properties of sending index $i=\overline{ \dots i_{6} i_5 i_4 i_3 i_2 i_1 i_0}$ to the point $(0.i_0 i_2 i_4\dots, 0.i_1 i_3 i_5\dots)$, in binay notation. It seems somewhat related to your idea. Could it work too? $\endgroup$
    – Yaakov Baruch
    Commented Nov 18, 2014 at 14:18
  • 1
    $\begingroup$ @Yaakov: No; it is close to my earlier (unsuccessful) attempt. Check what happens with the numbers $i=\overline{011\dots100}$ and $j=\overline{100\dots011}$ which differ by 7. My (hopefully working) recent approach is different --- see my first comment. $\endgroup$
    – Ilya Bogdanov
    Commented Nov 18, 2014 at 14:28
  • $\begingroup$ Ilya: thank you for the prompt reply. It's a very clever example! (By the way, how to you typeset "@"?) $\endgroup$
    – Yaakov Baruch
    Commented Nov 18, 2014 at 14:44
  • $\begingroup$ @Yaakov Baruch: I looked at that, too. A modification I haven't checked, but which seems to work is to use ternary digits, and use a map $i_6 i_5 i_4 i_3 i_2 i_1 i_0 \mapsto (0.(-i_0)(-i_2)(-i_4)(-i_6), 0.(-i_1)(-i_3)(-i_5))$. That is, choose a fixed encoding of the digits so that $.02222$ is not next to $.10000$. $\endgroup$
    – Douglas Zare
    Commented Nov 18, 2014 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .