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?

  • $\begingroup$ Maybe we can define some discontinuous group action on R^n. $\endgroup$ – gary Sep 2 '11 at 5:56
  • $\begingroup$ t is n-tuple . If S has one element and S intersection t is null set , then it satisfies the condn ? $\endgroup$ – Anil Shanbhag Sep 2 '11 at 5:58
  • $\begingroup$ No, it won't satisfy the condition, if I understand your comment completely. $\endgroup$ – Ehsan M. Kermani Sep 2 '11 at 6:25
  • $\begingroup$ 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. $\endgroup$ – gary Sep 3 '11 at 23:01
  • 1
    $\begingroup$ The value of $n$ does not matter, since the additive groups of $\mathbb{R}^n$ and $\mathbb{R}$ are isomorphic. $\endgroup$ – 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)$.

  • $\begingroup$ 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. $\endgroup$ – t.b. Sep 4 '11 at 19:54
  • $\begingroup$ 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\}$". $\endgroup$ – t.b. Sep 4 '11 at 20:13
  • $\begingroup$ @Theo: Yep; I thought that I’d caught all of those. Fixed. $\endgroup$ – Brian M. Scott Sep 4 '11 at 20:16
  • $\begingroup$ @Brian: Probably I'm missing something, but why is $|T_\eta|< 2^\omega$ in the construction of $S_\xi$'s? $\endgroup$ – LostInMath Sep 4 '11 at 21:53
  • 1
    $\begingroup$ @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$. $\endgroup$ – 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.

  • 3
    $\begingroup$ 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$ $\endgroup$ – kneidell Sep 2 '11 at 7:27
  • $\begingroup$ @kneidell: hmm... so I just proved that it's not closed? $\endgroup$ – Proteus Sep 2 '11 at 7:31

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.