2
$\begingroup$

I asked this question in Mathematics StackExchange (link) about a month ago, but I have received no answer. It is about the following problem:

Problem: Are there sets $A,B$ of integers such that $A\cap B=\emptyset$ and $A\times B\rightarrow\mathbb{Z}$, $(a,b)\mapsto a+b$ is bijective?

The answer is "yes" as I will explain later. For some intuitive reason, I have thought this problem is somehow necessarily related with positional numeral systems (especially in negative base). I want to know this intuition is right or wrong.

Basically I ask the following 3 questions:

Q1: Find (other) examples of $A,B$ satisfying the conditions in the problem above. Are they related with positional numeral systems?

Q2: How to define that $A,B$ are "related with" a positional numeral system? Is the definition below appropriate?

Q3: Is a relationship necessary? In other words, do there such $A,B$ which are not related with any positional numeral system exist?

And there are conjectures below which had come up with when tackling these questions by myself. Probably they are easier to handle.

For Q1, we already have an example in a previous post in Mathematics StackExchange: $$ A=\{1+\sum_{i=0}^{N}a_{i}2^{2i}\;|\;a_{i}\in\{0,1\}\},\quad B=\{-1-\sum_{i=0}^{N}b_{i}2^{2i+1}\;|\;b_{i}\in\{0,1\}\}. $$ A little more generally, for any positive integer $r>1$, $$ A=\{1+\sum_{i=0}^{N}a_{i}r^{2i}\;|\;a_{i}\in\{0,1,\dotsc,r-1\}\},\quad B=\{-1-\sum_{i=0}^{N}b_{i}r^{2i+1}\;|\;b_{i}\in\{0,1,\dotsc,r-1\}\} $$ satisfies the conditions. Some more examples are given below. If you find any other example, please let me know.

For Q2, I've been using the following definition:

Definition. Let $A,B$ be sets of integers which satisfy the conditions in the problem above. We say $A,B$ are related with a positional numeral system in a base $q\in\mathbb{Z}$ ($|q|>1$), if there exist $\Lambda_{1},\Lambda_{2}\subset\mathbb{Z}_{\geq 0}$, $u_{1},u_{2}\in\mathbb{Z}$, and $\epsilon_{1},\epsilon_{2}\in\{-1,1\}$ such that $\mathbb{Z}_{\geq 0}=\Lambda_{1}\sqcup\Lambda_{2}$ (disjoint union), $u_{1}+u_{2}=0$, and $$ A=\{u_{1}+\epsilon_{1}\sum_{i\in\Lambda_{1}}a_{i}q^{i}\;|\;a_{i}\in\{0,1,\dotsc,|q|-1\}\},\quad B=\{u_{2}+\epsilon_{2}\sum_{i\in\Lambda_{2}}b_{i}q^{i}\;|\;b_{i}\in\{0,1,\dotsc,|q|-1\}\}. $$ For example, we have another example in the previous post: $$ A=\{a_{0}+\sum_{i=1}^{N}a_{i}2^{2i-1}\;|\;a_{0},a_{i}\in\{0,1\}\},\quad B=\{-1-\sum_{i=1}^{N}b_{i}2^{2i}\;|\;b_{i}\in\{0,1\}\}. $$ This is related with the negabinary by taking $q=-2$, $\Lambda_{1}=\{0,1,3,5,7,\cdots\}$, $\Lambda_{2}=\{2,4,6,8,\cdots\}$, $u_{1}=1$, $u_{2}=-1$, and $\epsilon_{1}=\epsilon_{2}=-1$ (here $a_{0}$ will be replaced with $1-a_{0}$). I've been thinking with this definition. But if you think we should change the definition, please suggest me.

The condition in the second sentence of the definition is not sufficient at all. In particular, $\Lambda_{1}\neq\emptyset$ and $\Lambda_{2}\neq\emptyset$ must be satisfied, as proved later. For the case that $q<-1$ and $\epsilon_{1}=\epsilon_{2}=1$, I conjecture the following:

Conjecture 1. For $q\in\mathbb{Z}_{<-1}$, $\Lambda_{1},\Lambda_{2}\subset\mathbb{Z}_{\geq 0}$ such that $\mathbb{Z}_{\geq 0}=\Lambda_{1}\sqcup\Lambda_{2}$ (disjoint union), and $u_{1}\in\mathbb{Z}$, put $$ A(q,\Lambda_{1},u_{1})=\{u_{1}+\sum_{i\in\Lambda_{1}}a_{i}q^{i}\;|\;a_{i}\in\{0,1,\dotsc,|q|-1\}\},\quad B(q,\Lambda_{2},-u_{1})=\{-u_{1}+\sum_{i\in\Lambda_{2}}b_{i}q^{i}\;|\;b_{i}\in\{0,1,\dotsc,|q|-1\}\}. $$ Then there exists a $u_{1}\in\mathbb{Z}$ such that $A(q,\Lambda_{1},u_{1})\cap B(q,\Lambda_{2},-u_{1})=\emptyset$ if and only if $\Lambda_{1}$ and $\Lambda_{2}$ are divided into even and odd except for a finite number of elements, i.e. there exists a positive integer $N$ and $\lambda,\mu\in\{1,2\}$ such that $\lambda\neq \mu$, $\{2n\;|\;n\in\mathbb{Z},\ n\geq N\}\subset\Lambda_{\lambda}$, and $\{2n+1\;|\;n\in\mathbb{Z},\ n\geq N\}\subset\Lambda_{\mu}$.

Can we prove this conjecture or find a counterexample? I'm almost convinced of this. I calculated while changing $q$, $\Lambda_{1}$, and $\Lambda_{2}$ using a computer, and in all cases which met the above condition I found $u_{1}$ to satisfy $A\cap B=\emptyset$, otherwise it failed. There have been no exceptions for now. For example:

(i) When $q=-2$, $\Lambda_{1}=\{2,4,5,7,9,11,13,\cdots,2n+1,\cdots\}$, and $\Lambda_{2}=\{0,1,3,6,8,10,12,14,\cdots,2n,\cdots\}$, we have $A\cap B=\emptyset$ for $u_{1}=-16$.

(ii) When $q=-3$, $\Lambda_{1}=\{2,4,5,7,9,11,13,\cdots,2n+1,\cdots\}$, and $\Lambda_{2}=\{0,1,3,6,8,10,12,14,\cdots,2n,\cdots\}$, we have $A\cap B=\emptyset$ for $u_{1}=-121$.

(iii) When $q=-2$, $\Lambda_{1}=\{0,1,3,4,6,8,10,12,14,\cdots,2n,\cdots\}$, and $\Lambda_{2}=\{2,5,7,9,11,13,\cdots,2n+1,\cdots\}$, we have $A\cap B=\emptyset$ for $u_{1}=8$.

(iv) When $q=-3$, $\Lambda_{1}=\{0,1,3,4,6,8,10,12,14,\cdots,2n,\cdots\}$, and $\Lambda_{2}=\{2,5,7,9,11,13,\cdots,2n+1,\cdots\}$, we have $A\cap B=\emptyset$ for $u_{1}=40$.

(v) When $q=-2$ or $-3$, $\Lambda_{1}=\{0,1,2,3\}$, and $\Lambda_{2}=\{4,5,6,7,8,\cdots\}$, we have $A\cap B\neq\emptyset$ for all $u_{1}$ in $|u_{1}|\leq 10000$.

(vi) When $q=-2$ or $-3$, $\Lambda_{1}=\{0,2,4,6\}$, and $\Lambda_{2}=\{1,3,5,7,8,9,10,11,12,\cdots\}$, we have $A\cap B\neq\emptyset$ for all $u_{1}$ in $|u_{1}|\leq 10000$.

(vii) When $q=-2$ or $-3$, $\Lambda_{1}=\{0,3,6,9,12,\cdots,3n,\cdots\}$, and $\Lambda_{2}=\{1,2,4,5,7,8,10,11,13,\cdots,3n+1,3n+2,\cdots\}$, we have $A\cap B\neq\emptyset$ for all $u_{1}$ in $|u_{1}|\leq 10000$.

(viii) When $q=-2$ or $-3$, $\Lambda_{1}=\{0,1,4,5,8,9,\cdots,4n,4n+1\cdots\}$, and $\Lambda_{2}=\{2,3,6,7,10,11,\cdots,4n+2,4n+3,\cdots\}$, we have $A\cap B\neq\emptyset$ for all $u_{1}$ in $|u_{1}|\leq 10000$.

To download a Python program I used, follow this link (if you don't mind to navigate a Japanese site) and click on the blue down-arrow icon or an open-folder icon; it requires Python 3 environment with NumPy.

For Q3, I think a relationship is necessary and have been trying to prove it. I explain what I have found or conjectured so far. In the following let $A,B$ be sets of integers such that $A\cap B=\emptyset$ and $A\times B\rightarrow\mathbb{Z}$, $(a,b)\mapsto a+b$ is bijective.

First there exists $u_{1}\in\mathbb{Z}$ such that $u_{1}\in A$, $-u_{1}\in B$, and $u_{1}\neq 0$ since $0\in A+B=\{a+b\;|\;a\in A,\ b\in B\}$ and $A\cap B=\emptyset$. We also have $A\neq\{u_{1}\}$ and $B\neq\{-u_{1}\}$; if $A=\{u_{1}\}$ then $u_{1}\in B$ by $2u_{1}\in A+B$, which contradicts to $A\cap B=\emptyset$. $B\neq\{-u_{1}\}$ is shown similarly. Moreover I want to show that both $A$ and $B$ are infinite, but it hasn't been successful yet. I conjecture the following:

Conjecture 2. Let $A,B$ be sets of integers such that $A\cap B=\emptyset$ and $A\times B\rightarrow\mathbb{Z}$, $(a,b)\mapsto a+b$ is bijective. Then we will have:

(1) $A<B$ or $A>B$. Here $A<B$ means that $a<b$ for all $a\in A$ and $b\in B$.

(2) $A\cup B\neq\mathbb{Z}$.

The reason I think (1) is true is that when calculating examples such as (i)-(iv) above and searching for $u_ {1}$ in ascending order of absolute values, it is found just when (1) is met. Probably (2) is much easier to prove than (1). If (2) holds, then there should be some gaps in $A\cup B$, so my rough strategy is to explore whether a base $q$ can be extracted from there.

Any help would be appreciated. Thank you very much for your attention.

$\endgroup$

1 Answer 1

2
$\begingroup$

Here is one kind of crazy example: Start with $A,B$ any two finite sets so that all the sums $a+b$ are distinct. $A=B=\emptyset$ for example. Now consider the integers in order $0,1,-1,2,-2,\cdots$ one at a time. For each, $t$, if it can already be written as $a+b$ go to the next. Otherwise pick any huge $N$ and put $ N+t$ in either $A$ or $B$ and $-N$ in the other. By huge I mean so large that there can’t be any repeated sums . For example $N$ greater than $2(|t|+m)$ should be fine where $m$ is the largest value of any $|a|$ or $|b|.$


For example, start with $$\begin{array}{llllllllllllll} A & \ \ 5^0& -5^1 & \ \ \ \ 5^2& -5^3& \ \ \ \ 5^4& -5^5& \ \ \ \ \ \ 5^6& \cdots \\ B & -5^0& 1+5^1& -1-5^2& 2+5^3& -2-5^4& 3+5^5& -3-5^6& \cdots \end{array}$$

This is not quite what you want, but we can throw away certain columns to get an example of what you do want.

For $m \in A \cup B$ let $I(m)$ be $[\frac34m,\frac{5}4 m]$ or $[\frac54m,\frac{3}4 m]$ according as $m$ is positive or negative.

Convince yourself that

  • Each integer can be obtained as $a+b$ in exactly one way by picking $a,b$ from the same column.
  • The intervals $I(m)$ are disjoint.
  • If $a$ and $b$ come from different columns, and $m$ is the one with largest absolute value, then $ a+b \in I(m).$
  • For an integer which can be written as $a+b$ with $a$ and $b$ from different columns, there is exactly one way to do it.

A particular column is $$(a,b)=(5^{2j},-j-5^{2j}) \text{ with }j \geq 0$$ or $$(a,b)=(-5^{2j-1},j+5^{2j-1}) \text{ with } j \gt 0.$$ When we get to such a pair we put its members in $A$ and $B$ then look ahead and delete any (much later) columns which use one of those two and an earlier member which was added to the other set.

After two steps we will have $A=\{1,-5\}$ and $B=\{-1,6\}.$ We see that we need to delete the columns for $j=-6,7.$ After three steps we will have $A=\{1,-5,25\}$ and $B=\{-1,6,-26\}.$ We see that the new additions require us to delete also the columns for $-31,-25,24,31.$ After the next step we delete $6$ columns, 3 for $j\in I(127)$ and another three for $j \in I(-125).$

$\endgroup$
2
  • $\begingroup$ Thank you very much! Then it seems that my intuition is wrong. Let me think of it a little more whether the way you suggested can construct $A,B$ which are not related any positional numeral system. If Conjecture 1 can be proved, probably it will be clearly shown by constructing an example that $A<B$ or $A>B$ is not satisfied. $\endgroup$ Nov 17, 2019 at 12:39
  • $\begingroup$ I read the edited answer. Thank you again! I got it before proving Conjecture 1. If $A,B$ are related with a positional numeral system (in my definition) and $u_{1}=1$, then $A\cup B$ must contain any of $2$, $0$, or $-2$. $\endgroup$ Nov 20, 2019 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.