Let $S= \{x_0,\dots,x_n\}$ be a finite subset of $[0,1]$ , $x_0=0$ and $x_1=1$ such that every distance between pair of elements of $S$ occurs at least twice, except for the distance $1$, then we are to show that $S$ is a subset of $\mathbb{Q}$.


Let $V$ be the $\mathbb{Q}$-vector space generated by $S$ and let $\leq$ be any total order on $V$ compatible with addition (forall $x,y,z \in V$, if $x \leq y$ then $x+z \leq y+z$, and more generally, any reasoning you are used to involving $+$ and $\leq$ is valid).
Then, for this particular total order, there is a unique pair $(x_i,x_j) \in S^2$ such that $x_i - x_j$ is the greatest distance between pair of elements of $S$ :

Since $S$ is finite and $\leq$ is total, the set $\{x-y, (x,y)\in S^2\}$ is finite so it has a maximal element $x_i - x_j$ for some pair $(x_i,x_j) \in S^2$.
Then we show it is unique : suppose there is $(x_k,x_l) \in V^2$ such that $(x_i - x_j) = (x_k - x_l)$.
Then $(x_i - x_j) + (x_i - x_j) = (x_k - x_l) + (x_i - x_j) = (x_k - x_j) + (x_i - x_l)$. Since $(x_i - x_j)$ is maximal, $(x_k - x_j) \leq (x_i - x_j)$ and $(x_i - x_l) \leq (x_i - x_j)$. If any of those two inequalities were strict, we would get the contradiction $(x_i - x_j) + (x_i - x_j) < (x_i - x_j) + (x_i - x_j)$, so they have to be equalities, which implies that $(x_k,x_l) = (x_i,x_j)$.

Now, the hypothesis on $S$ says that the only pairs $(x_i,x_j)$ such that $x_i-x_j$ is unique are the pairs $(0,1)$ and $(1,0)$. So it implies that for any total order on $V$ compatible with addition, this greatest distance is always $1$ or $-1$.

So we only need to show that if $V \neq \mathbb{Q}$, there must exist total orders $\leq$ on $V$ such that the greatest distance for $\leq$ is not $1$ or $-1$ :

Since $S$ generates $V$, and $(x_1 = 1)$ is free, we can add elements of $S$ to $(x_1)$ to form a basis $(e_1, \ldots, e_m) = (x_{i_1}, \ldots, x_{i_{m-1}},x_1)$ of $V$.

  • Pick the lexicographical order induced by this basis. It is caracterised by the property that $0 < \sum a_i e_i$ if and only if the first nonzero coefficient is positive.
    In particular, $(x_{i_1} - x_0) = x_{i_1} > \pm x_1 = \pm (x_1 - x_0) = \pm 1$, so neither $1$ nor $-1$ can be the greatest distance for $\leq$.

  • Define a linear application $f : V \to \mathbb{R}$ with $f(1) = 1$ and $f(x_{i_k}) = \pi^k$. Since $\pi$ is transcendental, this map $f$ is injective. Pick the order defined by $x \leq y \Leftrightarrow f(x) \leq_\mathbb{R} f(y)$, where $\leq_\mathbb{R}$ is the usual order on $\mathbb{R}$. But then, since $f(x_{i_1}) >_\mathbb{R} f(x_1)$, we have again $(x_{i_1} - x_0) = x_{i_1} > \pm x_1 = \pm (x_1 - x_0) = \pm 1$.

  • $\begingroup$ first of all In the problem it is given that the points are in [0,1] so the greatest no $(x_i-x_j)$ is the unique no 1, there is nothing to prove in it ,secondly I do not understand why in lexicographic order a number which is not a rational number then why that will not be in [0,1]? $\endgroup$ – Marso Apr 15 '12 at 19:13
  • $\begingroup$ Over all I have not understood properly. $\endgroup$ – Marso Apr 15 '12 at 20:18

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.