6
$\begingroup$

There are many pairs $X, Y$ of infinite subsets of $\mathbb{N}:=\{0,1,2\dots\}$ such that any $n\in\mathbb{N}$ writes uniquely as $n=x+y$, with $x\in X$ and $y\in Y$. An example of such a pair is $(X,2X)$ where $X$ is the (set of values of the) Moser-de Bruijn sequence A000695, numbers that are sum of distinct powers of $4$ (the decomposition being clear thinking to the binary expansions of $n,x,y$). More generally, one can fix $S\subset N$, both infinite and co-infinite, and take $X$ and $Y$ as the set of numbers whose binary expansion have support in $S$, resp. in its complement (the above example corresponds to the choice of the set of odd numbers for $S$). This shows that there are uncontably many such pairs.

A more general construction is: fix a sequence $(p_i)_{i\in\mathbb{N}}$ of integers $p_i>1$. Let $X$ and $Y$ be the set of numbers respectively $x$ and $y$ of the form
$$x:= n_0+p_0p_1n_2+p_0p_1p_2p_3n_4 + p_0p_1p_2p_3p_4p_5n_6+\dots$$ $$y:= p_0n_1+p_0p_1p_2n_3+p_0p_1p_2p_3p_4n_5+\dots\phantom{xxxxxxxxxxx} $$ where $0\le n_k<p_k$ for all $k\in\mathbb{N}$. Again, the decomposition comes to the fact that any $n\in\mathbb{N}$ has a unique expansion with $0\le n_k<p_k$ as $$n = n_0+p_0n_1+ p_0p_1n_2+p_0p_1p_2n_3 + p_0p_1p_2p_3n_4 +\dots$$

However, I suspect there could be more examples, not of the above form.

Question: is there any such pair $X,Y$ which is not of this form? If so, what is the more general construction?

$\endgroup$
2
  • 7
    $\begingroup$ Yes, this is the result from an older answer mathoverflow.net/questions/50798/… $\endgroup$ Commented Nov 24, 2018 at 16:29
  • 2
    $\begingroup$ Thank you, Gjergji... I'd up-vote that beautiful old answer of yours, but it seems I've already done that time! My fault, I should have searched more carefully. So I voted to close my own question :( $\endgroup$ Commented Nov 24, 2018 at 18:14

0