Fixed points of absolute set difference

Question

Let $\mathbb N = \{0,1,2,\dots \}$ and define the map $D:\mathcal{P}(\mathbb N) \to \mathcal{P}(\mathbb N)$ as

$$D(A) = \{|a_2-a_1| : \space (a_1, a_2)\in A^2\}$$

How to characterize the fixed points of $D$?

Answer 1

The empty set will be one. If $\emptyset \neq A = D(A)$, then $0\in A$. If $A$ has two nonzero elements $x$ and $y>x$, then $y-x \in A$. In fact, we can subtract $x$ from $y$ as many times as the result stays positive and still the result stays in $A$. That is, we can reduce $y$ $\pmod x$. Further, we can reduce $x$ modulo the natural number $ r = (y \pmod x) \in A$. This sounds like the Euclidian algorithm and leads to the fact that $\gcd(x,y) \in A$. This can be done for any two elements of $A$, so the $\gcd$ of the total set $A$ must also lie in $A$.

When dealing with $\gcd$'s we usually get the whole ideal generated by it, i.e $d\mathbb Z$. On the other hand, $D$ doesn't create any bigger numbers than there are already in $A$, so $D(A) \subset \overline M := \{0,1,2,\dots, M\}$ where $M=\sup A$ (and $\overline M$ is understood to be $\mathbb N$ if $A$ is unbounded and $\emptyset$ if $A$ is $\emptyset$).

Let's now make the guess:

$$\{A \subset \mathbb N : D(A)=A\} = \{A\subset \mathbb N : A=\gcd(A)\mathbb Z \cap \overline {\sup A}\}$$

Proof

"$\subset$":

Let's assume $D(A)=A$. If $A=\emptyset$, we are done, since the empty set is on the right hand side. So, let $A\neq \emptyset$ and $d=\gcd(A)$.

Let's first prove the inclusion $A \subset d\mathbb Z \cap \overline {\sup A}$.
Of course $A \subset \overline {\sup A}$.
We get that $d\in A$ by the Euclidian algorithm (do it for any two numbers in $A$ to get some number $d_1$; then do it for $d_1$ and another number of $A$ to get $d_2$ that is closer to $d$; the $\gcd$ of $A$ can be reached in finite number of steps (the numbers d_k decrease to $d$)).
If there is $x\in A$ that isn't a multiple of $d$, then $\gcd(d, x)<d$ but then $\gcd(A)<d$, a contradiction.
Hence $A \subset d\mathbb Z$.

Let's then prove the inclusion $d\mathbb Z \cap \overline {\sup A} \subset A$:
Let $x\in d\mathbb Z \cap \overline {\sup A}$ so $x=kd, k\in \mathbb N$ and $x \leq \sup A$. Now there is an $a\in A$ with $a\geq x$.
Since $d=\gcd(A)$, $a=td, t\in \mathbb N$. Take $d$ away from $a$ $\space \space$ $t-k (\geq0)$ times to get that $x\in D^{t-k}(A)=A$.

"$\supset$":

Assume $A=d\mathbb Z \cap \overline {\sup A}$. Again if $A=\emptyset$, $D(A)=A$ and we're done. So assume $A\neq \emptyset$. We need to show $D(A)=A$.

The inclusion $A\subset D(A)$ is clear, because $0=0d\in d\mathbb Z \cap \overline {\sup A} = A$, so every $a \in A$ is gotten as $|a-0|$ with $D$.

Let's then prove $D(A) \subset A$ and for that let $x\in D(A)$. So $x=a_2 - a_1$ for some $a_1, a_2 \in A$ (wlog assume $a_2\geq a_1$). From the assumption we get that $a_j=k_jd$ with $k_j \in \mathbb N$ for $j=1,2$. Hence,

$$x=(k_2-k_1)d.$$

But this means that $x\in d\mathbb Z$. Because in addition $0\leq x=a_2-a_1 \leq a_2 \leq \sup A$, we have $x \in \overline{sup A}$. These, with the assumption $d\mathbb Z \cap \overline {\sup A} = A$, mean that $x\in A$.