# Special subset of an Euclidean space

This is a nice problem that I found it somewhere and thought to share it with everyone!

Does there exist a subset $S \subset \mathbb{R}^n$ s.t. for every non-zero $t \in \mathbb{R}^n\;, \; S \cap (S+t)$ has precisely one element?

-
Maybe we can define some discontinuous group action on R^n. –  gary Sep 2 '11 at 5:56
t is n-tuple . If S has one element and S intersection t is null set , then it satisfies the condn ? –  Anil Shanbhag Sep 2 '11 at 5:58
No, it won't satisfy the condition, if I understand your comment completely. –  Ehsan M. Kermani Sep 2 '11 at 6:25
For one thing, S would have to be unbounded; otherwise, if $S\subset B(0,r)$ , then , tranlating by 2r, the self-intersection $S \cap (S+2r)$ would be empty. –  gary Sep 3 '11 at 23:01
The value of $n$ does not matter, since the additive groups of $\mathbb{R}^n$ and $\mathbb{R}$ are isomorphic. –  Dave Radcliffe Sep 4 '11 at 7:59

Edit: The original version of this assumed the Continuum Hypothesis. I have no idea why I thought that it was necessary: the same argument works perfectly well without it. I’ve made the necessary minor adjustments below.

Such a set can be constructed (if we assume the axiom of choice, but I take that for granted). Note first that the condition on $S$ is equivalent to the property $(\ast)$: for each non-zero $t \in \mathbb{R}^n$ there is a unique pair of points $x_t,y_t \in S$ such that $y_t = x_t + t$: $y_t$ is the unique point common to $S$ and $S+t$. I’ll construct $S$ to have this equivalent property.

Let $P$ be a subset of $\mathbb{R}^n \setminus \{0\}$ containing exactly one member of each pair $\{t,-t\}$ with $t \ne 0$. For $A \subseteq \mathbb{R}^n$ let $D(A) = P \cap (A-A)$; the $\pm t$ with $t \in D(A)$ are the translations already realized between points of $A$. Let $A^* = A \cup (A+D(A)) \cup (A-D(A))$; $A^*$ is $A$ together with the set of points in $\mathbb{R}^n$ that can reached from $A$ by translations already realized in $A$. Note that $A^*$ is countable whenever $A$ is. (In fact $A \subseteq (A+D(A)) \cup (A-D(A))$ if $A$ has at least two points.)

We can enumerate $P$ as $\{t_\xi:\xi < 2^\omega\}$. Suppose that $\eta < 2^\omega$, and for each $\xi < \eta$ we’ve constructed a set $S_\xi \subseteq \mathbb{R}^n$ such that:

$\qquad(a)_\xi$ $\vert S_\xi \vert < 2^\omega$;

$\qquad(b)_\xi$ $S_\xi \subseteq S_\zeta$ whenever $\xi < \zeta < \eta$; and

$\qquad(c)_\xi$ $t_\xi \in D(S_\xi)$.

Let $T_\eta = \bigcup\limits_{\xi<\eta} S_\xi$. If $t_\eta \in D(T_\eta)$, let $S_\eta = T_\eta$. Otherwise, $\vert T_\eta \vert < 2^\omega$, so $\vert T_\eta^* \vert < 2^\omega$, and we can choose $s_\eta,s_\eta' \in \mathbb{R}^n \setminus T_\eta^*$ such that $s_\eta' = s_\eta + t_\eta$ and $\frac12(s_\eta+s_\eta') \notin \{\frac12(x+y):x,y \in T_\eta\}$. Let $S_\eta = T_\eta \cup \{s_\eta,s_\eta'\}$; clearly $(a)_\eta - (c)_\eta$ are satisfied, and the construction goes through to $2^\omega$.

Now let $S = \bigcup\limits_{\xi< 2^\omega} S_\xi$; clearly $D(S) = P$. Suppose that for some $\eta < 2^\omega$ there are distinct pairs $x,x'$ and $y,y'$ in $S$ such that $x'=x+t_\eta$ and $y'=y+t_\eta$. No pair is added at stage $\eta$ if $t_\eta$ is already realized in $T_\eta$, and every point added after stage $\eta$ avoids $S_\eta \pm t_\eta$, so $x,x',y,y' \in T_\eta$. Let $\xi < \eta$ be minimal such that $x,x',y,y' \in S_\xi$. Then at least one of $x,x',y,y'$ must belong to $\{s_\xi,s_\xi'\}$, and since $\{s_\xi,s_\xi'\} \cap D(T_\xi) = \varnothing$, $\{s_\xi,s_\xi'\}$ must contain one point from each pair $\{x,x'\}$ and $\{y,y'\}$.

If $s_\xi = x$ and $s_\xi' = y$, then $y'-x' = (y+t_\eta)-(x+t_\eta) = y-x = t_\xi$. But in this case $x',y' \in T_\xi$, so $t_\xi \in D(T_\xi)$, and nothing would have been added at stage $\xi$. The case $s_\xi = x', s_\xi' = y'$ is obviously similar.

If $s_\xi = x$ and $s_\xi' = y'$, then $\frac12(s_\xi+s_\xi') = \frac12(x+y') = \frac12((x'-t_\eta) + (y + t_\eta)) = \frac12(x'+y)$; but in this case $x',y \in T_\xi$, so $s_\xi$ and $x_\xi'$ were chosen in such a way that $\frac12(s_\xi+s_\xi') \ne \frac12(x'+y)$. The case $s_\xi = x', s_\xi' = y$ is obviously similar.

It follows that $S$ satisfies $(\ast)$.

-
Brian, could you maybe have a look at this thread on path-connectedness versus arc-connectedness? There is some confusion in that there are two contradictory answers. –  t.b. Sep 4 '11 at 19:54
I think that there is a left-over of the previous CH-version when you're saying "We can enumerate $P$ as $\{t_{\xi} : \xi \lt \omega_1\}$". –  t.b. Sep 4 '11 at 20:13
@Theo: Yep; I thought that I’d caught all of those. Fixed. –  Brian M. Scott Sep 4 '11 at 20:16
@Brian: Probably I'm missing something, but why is $|T_\eta|< 2^\omega$ in the construction of $S_\xi$'s? –  LostInMath Sep 4 '11 at 21:53
@LostInMath: It’s not just that $\vert S_\xi\vert<2^\omega$ for all $\xi<\eta$; $\vert S_\xi\vert\le\vert\eta\vert$ (when $\eta\ge\omega$). Look at it this way: the $S_\xi$’s are nested, and each adds at most $2$ points to the union of the earlier ones, so $\vert T_\eta\vert\le 2\vert\eta\vert<2^\omega$. –  Brian M. Scott Sep 4 '11 at 23:56

If I write formally your problem, it states that for any $t\neq 0$ there exists a unique $s\in S$ such that $s+t\in S$. Let us denote such $s$ through $f(t)$, so $t\mapsto f(t)$ is uniquely defined for any $t\neq 0$.

Let $t',t''\neq 0$ be such that $t'+t''\neq 0$. What do we have: $$f(t')+t'\in S$$ $$f(t'')+t''\in S$$ so $$f(t')+f(t'')+(t'+t'')\in S$$ hence $$f(t')+f(t'') = f(t'+t'')$$ for all $t',t''\neq 0,t'+t''\neq 0$. Now you can see that $f(\mathbb R^n\setminus \{0\})\subseteq S$ for some additive function $f:\mathbb R^n\setminus\{0\}\to\mathbb R^n$.

But now, let pick up $t^*:f(t^*)\neq 0$. Then $f(t)+f(t^*) = f(t+t^*)\in S$ as well as $f(t-t^*)+f(t^*) = f(t)\in S$ which violates the uniqueness.

-
Hey @Proteus, I didn't quite figure out why you say that $S$ is closed under addition, i.e- why does $f(t')+t'\in S$ and $f(t'')+t''\in S$ implies $f(t')+f(t'')+(t'+t'')\in S$ –  kneidell Sep 2 '11 at 7:27
@kneidell: hmm... so I just proved that it's not closed? –  Proteus Sep 2 '11 at 7:31