MnLargeSymbols’164 MnLargeSymbols’171

# On Power Monoids and their Automorphisms

###### Abstract.

Endowed with the binary operation of set addition, the family of all finite
subsets of $\mathbb{N}$ containing $0$ is itself a monoid, herein denoted by
$\mathcal{P}_{{\rm fin},0}(\mathbb{N})$, whose identity element is the
singleton $\\{0\\}$.

We establish that the only non-trivial automorphism of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ is the involution $X\mapsto\max
X-X$. The proof uses ideas from additive combinatorics and an unconventional
induction on what we call the boxing dimension of a finite set
$X\subseteq\mathbb{N}$, that is, the smallest number of intervals whose union
is $X$.

###### Key words and phrases:

Automorphism groups, endomorphisms, power monoids, sumsets.

###### 2020 Mathematics Subject Classification:

Primary 11B13. Secondary 20M13, 39B52

##  1\. Introduction

Endowed with the binary operation of setwise multiplication
$(X,Y)\mapsto\\{xy\colon x\in X,\kern 1.00006pty\in Y\\}$, the finite subsets
of a (multiplicatively written) monoid $H$ containing the identity $1_{H}$
form a (multiplicatively written) monoid, hereby denoted by
$\mathcal{P}_{\mathrm{fin},1}(H)$ and called the reduced (finitary) power
monoid of $H$. (We refer to Howie’s monograph [12] for generalities on
monoids.)

Reduced power monoids are the most basic items in a complex hierarchy of
“highly non-cancellative” monoids, generically referred to as power monoids.
These structures have been first explicitly considered by Tamura and Shafer in
the late 1960s [16] and more recently investigated in a series of papers by
Fan and Tringali [8], Antoniou and Tringali [3], Bienvenu and Geroldinger [4],
and Tringali and Yan [19].

There are many reasons why power monoids are mathematically fascinating.
First, they provide a natural algebraic framework for a number of important
problems in additive combinatorics and related fields, like Sárközy’s
conjecture [15, Conjecture 1.6] on the “additive irreducibility” of the set of
quadratic residues modulo $p$ for all but finitely many primes
$p\in\mathbb{N}$. Second, the arithmetic of power monoids — with emphasis on
questions concerned with the possibility or impossibility of factoring certain
sets as a product of other sets that, in a sense, cannot be “broken down into
smaller pieces” — is a rich topic in itself and has been pivotal to an ongoing
radical transformation [18, 5, 6, 17, 7] of the “abstract theory of
factorization”, a subfield of algebra so far (largely) confined to commutative
domains and cancellative commutative monoids [9, 11, 2]. Third, power monoids
(and, more generally, power semigroups) have long been known to play a central
role in the theory of automata and formal languages [1, 14].

In the present paper, we address the problem of determining the automorphism
group of $\mathcal{P}_{\mathrm{fin},1}(H)$. (Unless specified otherwise, a
morphism will always mean a _monoid homomorphism_ , cf. Remark 2.1(1).) Apart
from being an interesting question in itself (the automorphisms of an object
in a certain category are a measure of the “symmetries” of the object itself
and their investigation is a fundamental problem in many areas of
mathematics), it is not unlikely that a better understanding of the algebraic
properties of power monoids will lead to a better understanding of other
aspects of their theory.

To set the stage, let $\mathrm{Aut}(M)$ be the automorphism group of a monoid
$M$. It is not difficult to show (see the proof of [19, Proposition 1.1])
that, for each $f\in\mathrm{Aut}(H)$, the function

$\mathcal{P}_{\mathrm{fin},1}(H)\to\mathcal{P}_{\mathrm{fin},1}(H)\colon
X\mapsto f(X)$

is an automorphism of $\mathcal{P}_{\mathrm{fin},1}(H)$, henceforth referred
to as the augmentation of $f$. Accordingly, we call an automorphism of
$\mathcal{P}_{\mathrm{fin},1}(H)$ inner if it is the augmentation of an
automorphism of $H$.

So, we have a well-defined map
$\Phi\colon\mathrm{Aut}(H)\to\mathrm{Aut}(\mathcal{P}_{\mathrm{fin},1}(H))$
sending an automorphism of $H$ to its augmentation. In addition, it is easily
checked that

$\Phi(g\circ f)(X)=g\circ
f(X)=g(f(X))=g(\Phi(f)(X))=\Phi(g)(\Phi(f)(X))=\Phi(g)\circ\Phi(f)(X),$

for all $f,g\in\mathrm{Aut}(H)$ and $X\in\mathcal{P}_{\mathrm{fin},1}(H)$. If,
on the other hand, $f(x)\neq g(x)$ for some $x\in H$ and we take
$X:=\\{1_{H},x\\}$, then
$\Phi(f)(X)=\\{1_{H},f(x)\\}\neq\\{1_{H},g(x)\\}=\Phi(g)(X)$ and hence
$\Phi(f)\neq\Phi(g)$.

In other words, $\Phi$ is an injective (group) homomorphism from
$\mathrm{Aut}(H)$ to $\mathrm{Aut}(\mathcal{P}_{\mathrm{fin},1}(H))$. It is
therefore natural to ask if $\Phi$ is also surjective and hence an
isomorphism, which is tantamount to saying that every automorphism of
$\mathcal{P}_{\mathrm{fin},1}(H)$ is inner. Unsurprisingly, this is not
generally the case and determining
$\mathrm{Aut}(\mathcal{P}_{\mathrm{fin},1}(H))$ is usually much more
complicated than determining $\mathrm{Aut}(H)$, as we are going to demonstrate
in the basic case where $H$ is the additive monoid $(\mathbb{N},+)$ of non-
negative integers.

More precisely, let us denote by $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$
the reduced power monoid of $(\mathbb{N},+)$. In contrast to what we have done
so far with $\mathcal{P}_{\mathrm{fin},1}(H)$, we will write
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ additively, so that the operation
on $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ maps a pair $(X,Y)$ of finite
subsets of $\mathbb{N}$ containing $0$ to their sumset

$X+Y:=\\{x+y\colon x\in X,\kern 1.00006pty\in Y\\}.$

We establish in Theorem 2.5 that an endomorphism of $\mathcal{P}_{{\rm
fin},0}(\mathbb{N})$ is an automorphism if and only if it is surjective, if
and only if it is injective and sends $\\{0,1\\}$ to $\\{0,1\\}$. Then, in
Theorem 3.2, we prove that the only non-trivial automorphism of
$\mathcal{P}_{{\rm fin},0}(\mathbb{N})$ is the involution
$X\mapsto\allowbreak\max X-\allowbreak X$. Since the automorphism group of
$(\mathbb{N},+)$ is trivial, this shows in particular that the automorphisms
of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ are not all inner. The proof
uses an unconventional induction on the boxing dimension of a finite set
$X\subseteq\mathbb{N}$, that is, the smallest number of (discrete) intervals
whose union is $X$.

We have striven to make our arguments as elementary and self-contained as
possible, up to a classical theorem of Nathanson [13], commonly known as the
_Fundamental Theorem of Additive Combinatorics_ , that enters the proof of
Lemma 2.2. We propose directions for further research in Sect. 4.

### Notation and terminology.

We denote by $\mathbb{N}$ the (set of) non-negative integers, by
$\mathbb{N}^{+}$ the positive integers, and by $|\cdot|$ the cardinality of a
set. If $a,b\in\mathbb{Z}\cup\\{\pm\infty\\}$, we let $\llbracket
a,b\rrbracket:=\\{x\in\allowbreak\mathbb{Z}\colon\allowbreak a\leq x\leq b\\}$
be the (discrete) interval from $a$ to $b$. Given $h\in\mathbb{N}$ and
$k\in\mathbb{Z}$, we use $hX$ for the $h$-fold sum and $k\times
X:=\allowbreak\\{kx\colon x\in X\\}$ for the $k$-dilate of a set
$X\subseteq\mathbb{Z}$, resp. Moreover, we put $-X:=-1\times X$ and
$X^{+}:=X\smallsetminus\\{0\\}$. Further notation and terminology, if not
explained, are standard or should be clear from the context.

##  2\. Preliminaries

In this section, we work out a variety of preliminaries that will be used in
Sect. 3 to prove Theorem 3.2 (that is, the main result of the paper). We start
with a short list of remarks.

######  Remarks 2.1.

(1) Let $H$ and $K$ be (multiplicatively written) monoids. A _semigroup_
homomorphism from $H$ to $K$ is, by definition, a function $f$ from $H$ to $K$
that satisfies the functional equation:  $f(xy)=f(x)f(y),\qquad\text{for all
}x,y\in H.$ (1) A solution to Eq. (1) will send the identity $1_{H}$ of $H$ to
an idempotent of $K$. So, if the only idempotent of $K$ is the identity
$1_{K}$, then any semigroup homomorphism from $H$ to $K$ is also a _monoid_
homomorphism (namely, it maps $1_{H}$ to $1_{K}$). This happens, in
particular, when $K$ is the reduced power monoid of $(\mathbb{N},+)$. In fact,
if $2X=X$ for some $X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, then $2\max
X=\max X$ and hence $\max X=0$, which forces $X$ to be the singleton $\\{0\\}$
(i.e., the identity of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$).

(2) The only automorphism of $(\mathbb{N},+)$ is the identity function on
$\mathbb{N}$, because $(\mathbb{N},+)$ is a cyclic monoid generated by $1$ and
isomorphisms map generators to generators. Yet, the automorphism group of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ is non-trivial, for it contains the
reversion map
$\textrm{rev}\colon\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})\to\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})\colon
X\mapsto\max X-X.$ In fact, $\mathrm{rev}(\cdot)$ is an involution (or self-
inverse function); and it is clear that, for all
$X,Y\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$,
$\mathrm{rev}(X+Y)=\max(X+Y)-(X+\allowbreak Y)=\allowbreak(\max X-\allowbreak
X)+\allowbreak(\max Y-\allowbreak
Y)=\mathrm{rev}(X)+\allowbreak\mathrm{rev}(Y).$ Since
$\mathrm{rev}(\\{0,1,3\\})=\\{0,\allowbreak 2,\allowbreak 3\\}$, we thus get
from item (1) that $\mathrm{rev}(\cdot)$ is an automorphism of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ of order $2$ (we will see in
Theorem 3.2 that $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ has no other non-
trivial automorphism).

(3) Let $H$ be a (multiplicatively written) monoid. If $x$ and $y$ are fixed
points of an endomorphism $f$ of $H$, then so is, of course, the product $xy$.
Thus, the set of fixed points of $f$ is a submonoid of $H$.

We continue with a series of simple lemmas that will be crucial in the
subsequent analysis (the first of these lemmas is, by the way, a minor
generalization of [19, Lemma 2.2]).

######  Lemma 2.2.

If $A\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ and $\\{0,\max A\\}\subseteq
B\subseteq A$, then $(k+1)A=kA+B$ for all large $k\in\mathbb{N}$.

###### Proof.

Set $a:=\max A$ and $q:=\gcd A$. Since $kA+\\{0,a\\}\subseteq
kA+B\subseteq(k+1)A$ for every $k\in\mathbb{N}$, it suffices to show that
$(k+1)A\subseteq kA+\\{0,a\\}$ when $k$ is large enough. We may also suppose
$A\neq\\{0\\}$, or else $kA=\allowbreak\\{0\\}$ for all $k\in\mathbb{N}$ and
the conclusion is obvious. Accordingly, $q$ is a positive integer and there is
no loss of generality in assuming that $q=1$, since taking
$\hat{A}:=\\{x/q\colon x\in A\\}\subseteq\mathbb{N}$ and
$\hat{a}:=\max\hat{A}$ yields that (i) $\gcd\hat{A}=\allowbreak 1$ and (ii)
$(k+1)A\subseteq kA+\\{0,a\\}$, for some $k\in\mathbb{N}$, if and only if
$(k+1)\hat{A}\subseteq k\hat{A}+\\{0,\hat{a}\\}$.

Consequently, we gather from the Fundamental Theorem of Additive Combinatorics
[13] that there exist non-negative integers $c$, $d$, and $k_{0}$ and sets
$C\subseteq\llbracket 0,c-2\rrbracket$ and $D\subseteq\llbracket
0,d-2\rrbracket$ such that

$kA=C\cup\llbracket c,ka-d\kern 1.00006pt\rrbracket\cup(ka-D),\qquad\text{for
each }k\in\\{k_{0},k_{0}+1,\ldots\\}.$ (2)

Now, fix an integer $h\geq\max\\{k_{0},1+(c+d)/a\\}$ and pick $x\in(h+1)A$.
Since $h\geq k_{0}$, Eq. (2) holds for both $k=h$ and $k=h+1$. So, either
$x\in C\cup\llbracket c,ha-d-1\rrbracket$, and it is then evident that $x\in
hA$; or $x-\allowbreak a\in\allowbreak\llbracket(h-1)a-d,ha-d\kern
1.00006pt\rrbracket\cup(ha-D)\subseteq hA$ and then $x\in hA+a$, where we are
especially using that $h\geq\allowbreak 1+\allowbreak(c+d)/a$ and hence
$(h-1)a-d\geq c$. In both cases, the conclusion is that $x\in hA+\\{0,a\\}$,
which finishes the proof because $x$ is an arbitrary element in $(h+1)A$. ∎

######  Lemma 2.3.

Any automorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ sends
$2$-element sets to $2$-element sets.

###### Proof.

Let $\phi$ be an automorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$
and fix $a\in\mathbb{N}^{+}$. We need to show that $B:=\phi(\\{0,\allowbreak
a\\})=\allowbreak\\{0,b\\}$ for some (non-zero) $b\in\mathbb{N}$. For, set
$n:=|B|-1$. Clearly, $n$ is a positive integer, because $0\in B$ and
$B\neq\phi(\\{0\\})=\\{0\\}$ (by the injectivity of $\phi$). Accordingly, let
$b_{1},\ldots,b_{n}$ be an enumeration of the positive elements of $B$ with
$b_{n}=\max B$. By Lemma 2.2, we have that $(k+1)B=kB+\\{0,b_{n}\\}$ for some
$k\in\mathbb{N}$.

Put $A:=\phi^{-1}(\\{0,b_{n}\\})$, where $\phi^{-1}$ is the (functional)
inverse of $\phi$. Since $\phi^{-1}$ is, in turn, an automorphism of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ with $\phi^{-1}(B)=\\{0,a\\}$, we
get from the above that

$(k+1)\\{0,a\\}=(k+1)\phi^{-1}(B)=k\phi^{-1}(B)+\phi^{-1}(\\{0,b_{n}\\})=k\\{0,a\\}+A.$

It follows that $\\{0\\}\subsetneq A\subseteq(k+1)\\{0,a\\}$ and $\max
A=(k+1)a-ka=a$; and noticing that $a$ is the least non-zero element of
$(k+1)\\{0,a\\}$, this yields $A=\\{0,\allowbreak a\\}$ and hence
$B=\allowbreak\phi(\\{0,a\\})=\phi(A)=\\{0,b_{n}\\}$. ∎

######  Lemma 2.4.

Let $f$ be an endomorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ and
fix $X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$. The following hold:

  1. (i)

$f(X)+kf(\\{0,1\\})=(k+\max X)f(\\{0,1\\})$ for every integer $k\geq\max X$.

  2. (ii)

$\max f(X)=\max X\cdot\max f(\\{0,1\\})$.

###### Proof.

(i) Let $k\in\mathbb{N}$. We have $\\{0,\max X\\}\subseteq
X\subseteq\llbracket 0,\max X\rrbracket$ and $k\kern
1.00006pt\\{0,1\\}=\llbracket 0,k\rrbracket$. If $k\geq\max X$, then

$\llbracket 0,k+\max X\rrbracket=\llbracket 0,k\rrbracket\cup(\max
X+\llbracket 0,k\rrbracket)\subseteq X+k\kern
1.00006pt\\{0,1\\}\subseteq\llbracket 0,k+\max X\rrbracket,$

which shows that

$X+k\kern 1.00006pt\\{0,1\\}=\llbracket 0,k+\max X\rrbracket=(k+\max
X)\\{0,1\\}.$

Using that $f(A+B)=f(A)+f(B)$ for all
$A,B\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, this suffices to conclude.

(ii) Since $\max(A+B)=\max A+\max B$ for all
$A,B\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, we get from item (i) that

$\max f(X)+k\cdot\max f(\\{0,1\\})=(k+\max X)\cdot\max f(\\{0,1\\})$

for every integer $k\geq\max X$. Clearly, this is enough to finish the proof.
∎

Our first theorem gives a characterization of the automorphisms of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ that is of independent interest and
complementary to the main result (Theorem 3.2).

######  Theorem 2.5.

The following are equivalent for an endomorphism $f$ of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$:

  1. (a)

$f$ is injective and $f(\\{0,1\\})=\\{0,1\\}$.

  2. (b)

$f$ is surjective.

  3. (c)

$f$ is an automorphism.

###### Proof.

Obviously, “(a) and (b)” $\Rightarrow$ (c) $\Rightarrow$ (b). So, it suffices
to show that (a) $\Rightarrow$ (b) $\Rightarrow$ (a). For, denote by
$\mathscr{S}_{A}$ the family of all subsets $B$ of a set
$A\in\allowbreak\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ such that
$\\{0,\allowbreak\max A\\}\subseteq\allowbreak B$. We will use without further
comment that, since $\mathscr{S}_{A}$ is a finite family, a function
$\mathscr{S}_{A}\to\mathscr{S}_{A}$ is injective if and only if it is
surjective.

(a) $\Rightarrow$ (b): Pick $Y\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ and
put $k:=\max Y$ and $\mathscr{S}_{k}:=\mathscr{S}_{\llbracket 0,k\rrbracket}$.
We need to check that $Y=f(X)$ for some
$X\in\allowbreak\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$. To this end, we
have from Lemma 2.4(ii), along with the hypothesis that $f(\\{0,\allowbreak
1\\})=\allowbreak\\{0,1\\}$, that $\max f(X)=\max X=k$ and hence
$f(X)\in\mathscr{S}_{k}$ for every $X\in\mathscr{S}_{k}$. Thus, the
restriction of $f$ (which is supposed to be injective) to the family
$\mathscr{S}_{k}$ yields a well-defined injection $f_{k}$ from
$\mathscr{S}_{k}$ to itself. It follows that $f_{k}$ is bijective; and since
$Y\in\mathscr{S}_{k}$, we find that there exists $X\in\mathscr{S}_{k}$ such
that $Y=\allowbreak f_{k}(X)=\allowbreak f(X)$, as wished.

(b) $\Rightarrow$ (a): Set $h:=\max f(\\{0,1\\})\in\mathbb{N}$. By Lemma
2.4(ii), $\max f(A)=h\max A$ for each
$X\in\allowbreak\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$. So, the
surjectivity of $f$ implies that $h=\allowbreak 1$ and
$f(\\{0,1\\})=\\{0,1\\}$; in fact, if $h=0$ then $f$ is identically zero, and
if $h\geq 2$ then $\max f(A)\neq\allowbreak 1$ for all
$A\in\allowbreak\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$. It remains to see
that $f$ is also injective.

Assume $f(X)=f(Y)$ for some $X,Y\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$.
We need to verify that $X=Y$. For, set $k:=f(X)$ and
$\mathscr{S}_{k}:=\mathscr{S}_{\llbracket 0,k\rrbracket}$. It follows from the
above that $\max f(A)=\max A=k$ for all $A\in\mathscr{S}_{k}$. Consequently,
the sets $X$ and $Y$ are both in $\mathscr{S}_{k}$, and the restriction of $f$
to $\mathscr{S}_{k}$ yields a well-defined surjection $f_{k}$ from
$\mathscr{S}_{k}$ to itself. Similarly as in the proof of the implication (a)
$\Rightarrow$ (b), it follows that $f_{k}$ is a bijection; and since
$f_{k}(X)=f(X)=f(Y)=f_{k}(Y)$, we conclude of necessity that $X=Y$, as wished.
∎

######  Corollary 2.6.

If $f$ is an automorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, then
the following hold:

  1. (i)

$\max X=\max f(X)$ for every $X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$.

  2. (ii)

$\\{0,k\\}$ and $\llbracket 0,k\rrbracket$ are fixed points of $f$ for all
$k\in\mathbb{N}$.

  3. (iii)

Either $f(\\{0,2,3\\})=\\{0,1,3\\}$ or $f(\\{0,2,3\\})=\\{0,2,3\\}$.

###### Proof.

(i) This is a straightforward consequence of Lemma 2.4(ii) and Theorem 2.5.

(ii) Pick $k\in\mathbb{N}$. By Theorem 2.5, we have $f(\\{0,1\\})=\\{0,1\\}$.
Since $\llbracket 0,k\rrbracket=k\kern 1.00006pt\\{0,1\\}$, it is thus clear
that $f(\llbracket 0,k\rrbracket)=kf(\\{0,1\\})=\llbracket 0,k\rrbracket$; and
since $\\{0,k\\}+\llbracket 0,k\rrbracket=\llbracket 0,2k\rrbracket=2\kern
1.00006pt\llbracket 0,k\rrbracket$, we find that

$f(\\{0,k\\})+\llbracket 0,k\rrbracket=f(\\{0,k\\}+\llbracket
0,k\rrbracket)=2f(\llbracket 0,k\rrbracket)=\llbracket 0,2k\rrbracket.$ (3)

In particular, we get from Eq. (3) that $\max f(\\{0,k\\})=2k-k=k$. So,
recalling from Lemma 2.3 that an automorphism of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ sends $2$-elements sets to
$2$-elements sets, we obtain that $f(\\{0,\allowbreak
k\\})=\allowbreak\\{0,k\\}$. In other words, we have shown that $\\{0,k\\}$
and $\llbracket 0,k\rrbracket$ are both fixed points of $f$.

(iii) Set $Y:=f(\\{0,2,3\\})$. We gather from item (ii) that
$f(\\{0,3\\})=\\{0,3\\}$ and $f(\llbracket 0,3\rrbracket)=\llbracket
0,3\rrbracket$, and from item (i) that $\max Y=3$. By the injectivity of $f$,
it follows that $\\{0,3\\}\subsetneq Y\subsetneq\llbracket 0,3\rrbracket$.
Therefore, the only possibility is that either $Y=\\{0,1,3\\}$ or
$Y=\\{0,2,3\\}$. ∎

One consequence of Corollary 2.6(i) is that every
$f\in\mathrm{Aut}(\mathcal{P}_{\mathrm{fin},0}(\mathbb{N}))$ gives rise to a
well-defined function
$f^{\ast}\colon\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})\to\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$,
henceforth referred to as the reversal of $f$, by taking $f^{\ast}(X):=\max
X-\allowbreak f(X)$ for all $X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$.
This leads us to the following.

######  Lemma 2.7.

The reversal of an automorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$
is itself an automorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$.

###### Proof.

Let $f$ be an automorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$. On
account of Remark 2.1(1), the reversal $f^{\ast}$ of $f$ is then clearly an
endomorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, as it is readily
seen that, for all $X,Y\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$,

$f^{\ast}(X+Y)=\max(X+Y)-(X+Y)=(\max X-X)+(\max Y-Y)=f^{\ast}(X)+f^{\ast}(Y).$

In addition, we have that, for each
$X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$,

$f^{\ast}(f^{\ast}(X))=\max f^{\ast}(X)-f^{\ast}(X)=\max f(X)-(\max
X-f(X))=f(X),$ (4)

which yields $f^{\ast}\circ f^{\ast}=f$ and shows that $f^{\ast}$ is a
bijection (since $f$ is so). Hence,
$f^{\ast}\in\mathrm{Aut}(\mathcal{P}_{\mathrm{fin},0}(\mathbb{N}))$. ∎

Given $X\subseteq\mathbb{Z}$, we denote by $\Delta(X)$ the gap set (or
difference set) of $X$, i.e., the set of all _positive_ integers $d$ such that
$\\{x,x+d\\}=X\cap\llbracket x,\allowbreak x+\allowbreak d\rrbracket$ for some
$x\in\mathbb{Z}$. Accordingly, we define
$\mathrm{max\>gap}(X):=\sup\Delta(X)$, where $\sup\varnothing:=0$. It is a
simple exercise (and we leave it to the reader) to show that

$\\{0,\max X+h\\}\subseteq X+\llbracket 0,h\rrbracket\subseteq\llbracket
0,\max X+h\rrbracket,\qquad\text{for all
}X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})\text{ and }h\in\mathbb{N};$ (5)

and the right-most inclusion in Eq. (5) is strict if and only if
$h\leq\mathrm{max\>gap}(X)-2$. In the sequel, we shall often use these
observations without further comment.

######  Lemma 2.8.

If $f\in\mathrm{Aut}(\mathcal{P}_{\mathrm{fin},0}(\mathbb{N}))$, then
$\mathrm{max\>gap}(X)=\mathrm{max\>gap}(f(X))$ for every
$X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$.

###### Proof.

Pick $X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$. Since the inverse of $f$
is itself an automorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, it
suffices to prove $\mathrm{max\>gap}(X)\leq\mathrm{max\>gap}(f(X))=:d$. For,
set $X^{\prime}:=X+\llbracket 0,d-2\rrbracket$ and suppose to the contrary
that $d<\mathrm{max\>gap}(X)$. Since $f(\\{0\\})=\allowbreak\\{0\\}$, the gap
set of $X$ is then a non-empty finite subset of $\mathbb{N}^{+}$ and hence $d$
is a _positive_ integer. If, on the other hand, $X$ or $f(X)$ were intervals,
then we would gather from Corollary 2.6(ii) and the injectivity of $f$ that
$X=f(X)$ and hence $\mathrm{max\>gap}(X)=d$, which is absurd. So, $d$ is an
integer $\geq 2$ and we get from Corollary 2.6(i) (and the remarks before this
lemma) that

$f(\llbracket 0,d-2+\max X\rrbracket)=\llbracket 0,d-2+\max
f(X)\rrbracket=f(X)+\llbracket 0,d-2\rrbracket=f(X^{\prime}),$

which, again by the injectivity of $f$, implies $\llbracket 0,d-2+\max
X\rrbracket=X^{\prime}$. This is however a contradiction, because we are
supposing $d<\mathrm{max\>gap}(X)$ and hence $X^{\prime}$ is not an interval.
∎

By Corollary 2.6(ii), the automorphisms of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ can belong to one of two classes,
i.e., either they fix the set $\\{0,2,3\\}$ or they map $\\{0,2,3\\}$ to
$\\{0,1,3\\}$. Our next goal is to show (in Lemma 2.10) that an automorphism
in the first class must also fix certain sets of the form
$\\{0\\}\cup\llbracket b,c\rrbracket$ with $b,\allowbreak c\in\mathbb{N}$.

######  Proposition 2.9.

For all $a,n\in\mathbb{N}$ with $n\geq a+1$, it holds that

$\sum_{i=0}^{n-1}\\{0,a+i,a+i+1\\}=\\{0\\}\cup\bigl{\llbracket}a,na+\tfrac{1}{2}n(n+1)\bigr{\rrbracket}.$
(6)

###### Proof.

Let $A$ be the set on the left-hand side of Eq. (6). For each $j\in\llbracket
1,n\rrbracket$, we have

$\begin{split}A_{j}&:=\bigcup_{k=0}^{n-j}\kern
1.00006pt\sum_{i=k}^{k+j-1}\\{a+i,a+i+1\\}=\bigcup_{k=0}^{n-j}\sum_{i=0}^{j-1}(a+k+i+\llbracket
0,1\rrbracket)=\bigcup_{k=0}^{n-j}\left(aj+jk+\tfrac{1}{2}(j-1)j+\llbracket
0,j\rrbracket\right)\\\
&\phantom{:}=aj+\tfrac{1}{2}(j-1)j+\bigcup_{k=0}^{n-j}(jk+\llbracket
0,j\rrbracket)=aj+\tfrac{1}{2}(j-1)j+\llbracket
0,(n-j+1)j\rrbracket;\end{split}$

in particular, $A_{j}$ is an interval contained in $A$, with

$m_{j}:=\min A_{j}=aj+\frac{1}{2}(j-1)j\qquad\text{and}\qquad M_{j}:=\max
A_{j}=m_{j}+(n-j+1)j.$ (7)

Since $\min A^{+}=a$ and $\max
A=\sum_{i=0}^{n-1}(a+i+1)=na+\frac{1}{2}n(n+1)$, it follows that

$B:=\\{0\\}\cup A_{1}\cup\cdots\cup A_{n}\subseteq
A\subseteq\\{0\\}\cup\left\llbracket
a,na+\tfrac{1}{2}n(n+1)\right\rrbracket=:A^{\prime}.$ (8)

Now, we need to show that $A=A^{\prime}$ (recall that $n\geq a+1$). If $n=1$
(and hence $a=0$), then it is readily checked that $A=A^{\prime}=\\{0,1\\}$
(and we are done). So, we may suppose $n\geq 2$.

The function $\phi\colon\mathbb{R}\to\mathbb{R}:x\mapsto(n-x)x$ is increasing
for $x\leq\frac{1}{2}n$ and decreasing for $x\geq\frac{1}{2}n$, whence the
minimum of $\phi$ over the closed interval $[1,n-1]$ is given (by symmetry) by
$\phi(1)=n-1\geq\allowbreak a$. Therefore, it is straightforward from Eq. (7)
that, for all $j\in\llbracket 1,n-1\rrbracket$,

$m_{j+1}=a(j+1)+\tfrac{1}{2}j(j+1)=m_{j}+a+j\leq m_{j}+(n-j)j+j=M_{j}.$

Recalling that $A_{1},\ldots,A_{n}$ are intervals and considering that
$m_{1}=a$ and $M_{n}=an+\frac{1}{2}n(n+1)$, we thus find that
$B=\\{0\\}\cup\llbracket m_{1},M_{1}\rrbracket\cup\cdots\cup\llbracket
m_{n},M_{n}\rrbracket=\\{0\\}\cup\llbracket m_{1},M_{n}\rrbracket=A^{\prime}$,
which, by Eq. (8), yields $A=A^{\prime}$ (as wished) and completes the proof.
∎

######  Lemma 2.10.

Assume $\\{0,2,3\\}$ is a fixed point of an automorphism $f$ of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$. The following hold:

  1. (i)

If $1\in X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, then $1\in f(X)$.

  2. (ii)

$f(\\{0,a,a+1\\})=\\{0,a,a+1\\}$ for every $a\in\mathbb{N}$.

  3. (iii)

$\\{0\\}\cup\left\llbracket a,na+\frac{1}{2}n(n+1)\right\rrbracket$ is a fixed
point of $f$ for all $a,n\in\mathbb{N}$ with $n\geq a+1$.

###### Proof.

(i) Let $X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ and $k\in\mathbb{N}$.
It is routine to show (by induction on $k$) that $k\\{0,\allowbreak
2,3\\}=\\{0\\}\cup\allowbreak\llbracket 2,\allowbreak 3k\rrbracket$ (we leave
the details to the reader). It is thus clear that, if $1\in X$ and
$k\geq(2+\max X)/3$, then

$\llbracket 0,3k+\max X\rrbracket=(\\{0,1\\}\cup\\{\max
X\\})+(\\{0\\}\cup\llbracket 2,3k\rrbracket)\subseteq
X+k\\{0,2,3\\}\subseteq\llbracket 0,3k+\max X\rrbracket;$

to wit, $X+k\\{0,2,3\\}$ is the interval $\llbracket 0,3k+\max X\rrbracket$
and hence, by Corollary 2.6(ii), a fixed point of $f$. So, by the hypothesis
that $f$ is a homomorphism with $f(\\{0,2,3\\})=\\{0,2,3\\}$, we conclude
that, if $1\in X$ and $k$ is a sufficiently large integer, then

$1\in f(X+k\\{0,2,3\\})=f(X)+k\\{0,2,3\\}=f(X)+(\\{0\\}\cup\llbracket
2,3k\rrbracket).$ (9)

But this is only possible if $1\in f(X)$, since the least _positive_ element
of the set on the right-most side of Eq. (9) is no smaller than the minimum
between $2$ and the least positive element of $f(X)$.

(ii) Pick $a\in\mathbb{N}$ and set $X:=\\{0,a,a+1\\}$ and $Y:=f(X)$. We need
to prove $Y=X$. If $a=0$ or $a=1$, then $X$ is an interval and we are done by
Corollary 2.6(ii). So, assume from now on that $a\geq 2$.

By Lemmas and 2.8, we have $\max Y=\max X=a+1$ and
$\delta:=\mathrm{max\>gap}(Y)=\mathrm{max\>gap}(X)=a\geq 2$. It follows that
$Y$ does not contain any integer $y$ in the interval $\llbracket
2,a-1\rrbracket$, or else we would find that
$\delta\leq\allowbreak\min(y,\allowbreak a+\allowbreak 1-\allowbreak
y)\leq\allowbreak a-1<\delta$ (which is impossible). Considering that the
functional inverse $f^{-1}$ of $f$ is an automorphism of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ sending $Y$ to $X$, we gather on
the other hand from item (i) that $1\notin Y$. So putting it all together, we
conclude from Corollary 2.6(ii) that $\\{0,a+1\\}\subsetneq
Y\subseteq\allowbreak\\{0,\allowbreak a,\allowbreak a+1\\}=\allowbreak X$,
which shows that $Y=X$ (as wished) and finishes the proof.

(iii) Given $a,n\in\mathbb{N}$ with $n\geq a+1$, we have from Proposition 2.9
that $\\{0\\}\cup\bigl{\llbracket}a,na+\frac{1}{2}n(n+1)\bigr{\rrbracket}$ can
be written as the sum of the sets $\\{0,a+i,\allowbreak a+\allowbreak i+1\\}$
as $i$ ranges over the interval $\llbracket 0,n-1\rrbracket$. By item (ii) and
Remark 2.1(3) (specialized to $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$),
this is enough to prove the claim. ∎

##  3\. Main result

Given a set $S\subseteq\mathbb{Z}$, we denote by $\mathrm{b.dim}(S)$ the
smallest integer $k\geq 0$ for which there exist $k$ (discrete) intervals
whose union is $S$, with the understanding that if no such $k$ exists then
$\mathrm{b.dim}(S):=\infty$. We call $\mathrm{b.dim}(S)$ the boxing dimension
of $S$. A couple of remarks are in order.

######  Remark 3.1.

(1) The boxing dimension of a set $S\subseteq\mathbb{Z}$ is zero if and only
if $S$ is empty, and it is one if and only if $S$ is an interval. More
generally, let us say that two sets $X,Y\subseteq\mathbb{Z}$ are well
separated if $|x-y|\geq 2$ for all $x\in X$ and $y\in Y$ (so, well-separated
sets are disjoint). It is then easily checked that the boxing dimension of $S$
is equal to a certain integer $k\geq 0$ if and only if there is a _unique_ way
to write $S$ as a union of $k$ well-separated non-empty intervals (we leave
the details to the reader).
For instance, the sets $A:=\\{0,5\\}\cup\mathbb{N}_{\geq 7}$ and
$B:=\\{-2,2,3\\}$ are well separated, with $\text{bim}(A)=3$ and
$\text{bim}(B)=2$. To the contrary, the (set of) even integers and the odd
integers are not well separated, and the boxing dimension of each of them is
infinite.

(2) It is obvious that $\mathrm{b.dim}(X\cup
Y)\leq\mathrm{b.dim}(X)+\allowbreak\mathrm{b.dim}(Y)$ for all
$X,Y\subseteq\mathbb{Z}$, a property we refer to as _subadditivity_ (in
analogy with other notions of “dimension” in union-closed families of sets).

The proof of the next theorem (that is, the main theorem of the paper) is
essentially an induction on the boxing dimension of a set
$X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$.

######  Theorem 3.2.

The only automorphisms of the reduced power monoid
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ of $(\mathbb{N},+)$ are the
identity $X\mapsto X$ and the reversion map $X\mapsto\max X-X$.

###### Proof.

Denote by $\Gamma$ the set of automorphisms of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ that fix $\\{0,2,3\\}$. We get from
Corollary 2.6(iii) and Lemma 2.7 that
$\mathrm{Aut}(\mathcal{P}_{\mathrm{fin},0}(\mathbb{N}))=\Gamma\cup\Gamma^{\prime}$,
where $\Gamma^{\prime}$ is the relative complement of $\Gamma$ in
$\mathrm{Aut}(\mathcal{P}_{\mathrm{fin},0}(\mathbb{N}))$. In view of Remark
2.1, it is therefore enough to show that the only automorphism in $\Gamma$ is
the identity function $X\mapsto X$, whose reversal is nothing but the
reversion map $X\mapsto\max X-X$.

For, let $f\in\Gamma$ and $X\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, and
put $Y:=f(X)$, $r:=\mathrm{b.dim}(X)-1$, $s:=\mathrm{b.dim}(Y)-1$, and
$t:=\allowbreak\min(r,\allowbreak s)$. We get from Corollary 2.6(i) that
$\mu:=\max(X)=\max(Y)$. Moreover, $r$ and $s$ are non-negative integers, as
the empty set is the only set whose boxing dimension is zero. Hence, by Remark
3.1, there exist non-decreasing sequences $x_{0},x_{1},\ldots,x_{2r+1}$ and
$y_{0},y_{1},\ldots,y_{2s+1}$ of integers such that

  1. (I)

$x_{2i-1}+2\leq x_{2i}$ for each $i\in\llbracket 1,r\rrbracket$ and
$y_{2j-1}+2\leq y_{2j}$ for each $j\in\llbracket 1,s\rrbracket$;

  2. (II)

$X=\llbracket x_{0},x_{1}\rrbracket\cup\cdots\cup\llbracket
x_{2r},x_{2r+1}\rrbracket$ and $Y=\llbracket
y_{0},y_{1}\rrbracket\cup\cdots\cup\llbracket y_{2s},y_{2s+1}\rrbracket$.

In particular, it is clear that $x_{0}=y_{0}=0$ and $x_{2r+1}=y_{2s+1}=\mu$.
We proceed by induction on $r$.

If $r=0$, then $X$ is an interval and we have from Corollary 2.6(ii) that
$X=f(X)=Y$ (as wished). So, let $r\geq\allowbreak 1$, assume for the sake of
induction that $f(S)=S$ for all $S\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$
with $\mathrm{b.dim}(S)\leq r$, and suppose by way of contradiction that
$X\neq Y$. Accordingly, there is a smallest index $v\in\allowbreak\llbracket
1,2t+1\rrbracket$ such that $x_{v}\neq y_{v}$; otherwise, since $x_{0}\leq
x_{1}\leq\cdots\leq x_{2r+1}$ and $y_{0}\leq y_{1}\leq\cdots\leq y_{2s+1}$, we
would get from conditions (I) and (II) that $X=X\cap\llbracket
0,\mu\rrbracket=Y\cap\llbracket 0,\mu\rrbracket=Y$ (which is absurd). We will
distinguish two cases, depending on whether $v$ is even or odd. But first,
some observations are in order.

To start with, there is no loss of generality in assuming that $x_{v}<y_{v}$;
otherwise, we could replace $f$ by its functional inverse $f^{-1}$, upon
considering that $f^{-1}$ is an automorphism of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ with the same fixed points of $f$.
Next, it is clear that $r\leq s$, or else $Y$ is fixed by $f$ (by the
inductive hypothesis) and hence $f(Y)=\allowbreak Y=\allowbreak f(X)$, which
is still an absurdity (since $f$ is injective and $X\neq Y$). It follows that
$1\leq\allowbreak v\leq\allowbreak 2r$, because $v=2r+1$ would imply
$\mu=x_{2r+1}<y_{2r+1}\leq y_{2s+1}=\mu$ (which is impossible). Lastly, we may
suppose that, if $X^{\prime}$ is another set in
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ with
$\mathrm{b.dim}(X^{\prime})=\mathrm{b.dim}(X)$ and $X^{\prime}\neq
f(X^{\prime})$, then $\mathrm{b.dim}(Y)\leq\mathrm{b.dim}(f(X^{\prime}))$;
otherwise, we trade $X$ for $X^{\prime}$ and iterate the argument until the
condition is satisfied (since $\mathrm{b.dim}(Y)<\infty$, this shall
eventually happen after finitely many iterations). In other words, we may
assume that $X$ is $\mathrm{b.dim}$_-cominimal_ in the (non-empty) family
$\mathscr{S}_{r}$ of all $S\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ with
$\mathrm{b.dim}(S)=r+\allowbreak 1$ and $S\neq f(S)$, by which we mean that
$\mathrm{b.dim}(Y)\leq\mathrm{b.dim}(f(S))$ for every $S\in\mathscr{C}_{r}$.

Case 1: $v=2u$ for some $u\in\llbracket 1,r\rrbracket$. Put
$d:=x_{2u}-x_{2u-1}-1$ and $I:=\llbracket
0,r\rrbracket\smallsetminus\\{u-1,u\\}$, and set

$X_{1}:=\llbracket x_{2(u-1)},x_{2u+1}+d\rrbracket\qquad\text{and}\qquad
X_{2}:=\bigcup_{i\in I}\llbracket x_{2i},x_{2i+1}+d\rrbracket.$

(If $I=\varnothing$, then $X_{2}=\varnothing$.) Using that $X=\llbracket
x_{0},x_{1}\rrbracket\cup\cdots\cup\llbracket x_{2r},x_{2r+1}\rrbracket$ and
$x_{2u-1}+d=x_{2u}-1$, we have

$X+\llbracket 0,d\rrbracket=\bigcup_{i=0}^{r}(\llbracket
x_{2i},x_{2i+1}\rrbracket+\llbracket
0,d\rrbracket)=\bigcup_{i=0}^{r}\llbracket
x_{2i},x_{2i+1}+d\rrbracket=X_{1}\cup X_{2}.$ (10)

In a similar way, $Y=\llbracket y_{0},y_{1}\rrbracket\cup\cdots\cup\llbracket
y_{2s},y_{2s+1}\rrbracket$ leads to

$Y+\llbracket 0,d\rrbracket=\bigcup_{j=0}^{s}\llbracket
y_{2j},y_{2j+1}+d\rrbracket.$ (11)

It follows from Eq. (10) and Remark 3.1(2) that

$\mathrm{b.dim}(X+\llbracket
0,d\rrbracket)\leq\mathrm{b.dim}(X_{1})+\mathrm{b.dim}(X_{2})\leq
1+(r-1)<\mathrm{b.dim}(X).$

Consequently, we conclude from the inductive hypothesis and Corollary 2.6(ii)
that

$X+\llbracket 0,d\rrbracket=f(X+\llbracket 0,d\rrbracket)=f(X)+f(\llbracket
0,d\rrbracket)=Y+\llbracket 0,d\rrbracket.$

This is however impossible, as we get from Eqs. (10) and (11) that $x_{2u}$ is
in $X+\llbracket 0,d\rrbracket$ but not in $Y+\allowbreak\llbracket
0,d\rrbracket$ (note that
$y_{2u-1}+d=x_{2u-1}+(x_{2u}-x_{2u-1}-1)<x_{2u}<y_{2u}$).

Case 2: $v=2u+1$ for some $u\in\llbracket 0,r-1\rrbracket$. We will establish
the existence of a set $S\in\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ with
$\mathrm{b.dim}(S)=\mathrm{b.dim}(X)$ and
$\mathrm{b.dim}(f(S))<\mathrm{b.dim}(Y)$ such that $S\neq f(S)$, thus
contradicting that $X$ is $\mathrm{b.dim}$-cominimal in the family
$\mathscr{S}_{r}$ and finishing the proof. To begin, put

$a:=\min(x_{2r},y_{2u+1}+1)\qquad\text{and}\qquad
b_{0}:=y_{2u+1}+\max(x_{2r},y_{2s}).$

Next, let $b$ be an integer $\geq b_{0}$ and set $Z:=\\{0\\}\cup\llbracket
y_{2u+1}+1,b\rrbracket$. Since $x_{0},\ldots,x_{2r+1}$ and
$y_{0},\allowbreak\ldots,\allowbreak y_{2s+1}$ are non-decreasing sequences of
non-negative integers with $x_{0}=y_{0}=\allowbreak 0$ and
$x_{2r+1}=y_{2s+1}=\mu$, we have

$\begin{split}X^{\prime}&:=\bigcup_{i=0}^{r}\llbracket
x_{2i}+y_{2u+1}+1,x_{2i+1}+b\rrbracket\subseteq\llbracket
y_{2u+1}+1,\mu+b\rrbracket\subseteq\llbracket
y_{2u+1}+1,b\rrbracket\cup\llbracket b+1,\mu+b\rrbracket\\\
&\phantom{:}\subseteq\llbracket
x_{0}+y_{2u+1}+1,x_{1}+b\rrbracket\cup\llbracket
x_{2r}+y_{2u+1}+1,x_{2r+1}+b\rrbracket\subseteq X^{\prime}\end{split}$ (12)

and, in an analogous fashion,

$\begin{split}Y^{\prime}&:=\bigcup_{j=0}^{s}\llbracket
y_{2j}+y_{2u+1}+1,y_{2j+1}+b\rrbracket\subseteq\llbracket
y_{2u+1}+1,\mu+b\rrbracket\subseteq\llbracket
y_{2u+1}+1,b\rrbracket\cup\llbracket b+1,\mu+b\rrbracket\\\
&\phantom{:}\subseteq\llbracket
y_{0}+y_{2u+1}+1,y_{1}+b\rrbracket\cup\llbracket
y_{2s}+y_{2u+1}+1,y_{2s+1}+b\rrbracket\subseteq Y^{\prime}.\end{split}$ (13)

From the above and condition (II) (cf. the derivation of Eqs. (10) and (11) in
Case 1), it follows that

$X+\llbracket y_{2u+1}+1,b\rrbracket=X^{\prime}=\llbracket
y_{2u+1}+1,\mu+b\rrbracket=Y^{\prime}=Y+\llbracket y_{2u+1}+1,b\rrbracket.$
(14)

So, letting $X_{\ast}:=\llbracket
x_{0},x_{1}\rrbracket\cup\cdots\cup\llbracket
x_{2(r-1)},x_{2(r-1)+1}\rrbracket$ and noticing that

$X=X_{\ast}\cup\llbracket
x_{2r},x_{2r+1}\rrbracket\qquad\text{and}\qquad\llbracket
x_{2r},x_{2r+1}\rrbracket\cup\llbracket y_{2u+1}+1,\mu+b\rrbracket=\llbracket
a,\mu+b\rrbracket,$ (15)

we find that

$X+Z=X\cup(X+\llbracket
y_{2u+1}+1,b\rrbracket)\stackrel{{\scriptstyle\eqref{equ:double-
equality}}}{{=}}X\cup\llbracket
y_{2u+1}+1,\mu+b\rrbracket\stackrel{{\scriptstyle\eqref{equ:decomposing-X}}}{{=}}X_{\ast}\cup\llbracket
a,\mu+b\rrbracket.$ (16)

Likewise, taking $Y^{\ast}:=\llbracket
y_{2u},y_{2u+1}\rrbracket\cup\cdots\cup\llbracket y_{2s},y_{2s+1}\rrbracket$
and considering that

$Y_{\ast}:=Y\smallsetminus Y^{\ast}=\bigcup_{j=0}^{u-1}\llbracket
y_{2j},y_{2j+1}\rrbracket\qquad\text{and}\qquad Y^{\ast}\cup\llbracket
y_{2u+1}+1,\mu+b\rrbracket=\llbracket y_{2u},\mu+b\rrbracket,$ (17)

it is seen that

$Y+Z=Y\cup(Y+\llbracket
y_{2u+1}+1,b\rrbracket)\stackrel{{\scriptstyle\eqref{equ:double-
equality}}}{{=}}Y\cup\llbracket
y_{2u+1}+1,\mu+b\rrbracket\stackrel{{\scriptstyle\eqref{equ:decomposing-Y}}}{{=}}Y_{\ast}\cup\llbracket
y_{2u},\mu+b\rrbracket.$ (18)

In view of Remark 3.1(2), we thus get from Eq. (16) that

$\mathrm{b.dim}(X+Z)\leq\mathrm{b.dim}(X_{\ast})+\mathrm{b.dim}(\llbracket
a,b\rrbracket)=r+1=\mathrm{b.dim}(X),$ (19)

and from Eq. (18) that

$\mathrm{b.dim}(Y+Z)\leq\mathrm{b.dim}(Y_{\ast})+\mathrm{b.dim}(\llbracket
y_{2u},\mu+b\rrbracket)=u+1\leq(r-1)+1\leq s<\mathrm{b.dim}(Y).$ (20)

Now, Eqs. (19) and (20) imply, by the inductive hypothesis and the
$\mathrm{b.dim}$-cominimality of $X$, that

$f(X+\allowbreak Z)=X+Z.$ (21)

In view of Lemma 2.10(iii), we may on the other hand choose the integer $b$
(subjected to the constraint $b\geq b_{0}$) in such a way that the
$2$-interval $Z$ is a fixed point of $f$. Together with Eq. (21), this yields

$X+Z=f(X+Z)=f(X)+f(Z)=Y+Z,$

which is, however, impossible and finishes the proof. In fact,
$x_{2u+1}+1\notin X+Z$, because $X+Z\subseteq X\cup\allowbreak\llbracket
a,\allowbreak b\rrbracket$ by Eq. (16) and $x_{2u+1}+1\notin X\cup\llbracket
a,b\rrbracket$ (using that $a\geq x_{2r}>x_{2u+1}+1$). Yet, $x_{2u+1}+1\in
Y+\allowbreak Z$, because $y_{2u}=x_{2u}$ and hence $x_{2u+1}+1\in\llbracket
y_{2u},2\mu\rrbracket\subseteq Y+Z$ by Eq. (18). ∎

######  Remark 3.3.

By Theorems 2.5 and 3.2, the only _surjective_ endomorphisms of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ are the identity and the reversion
map (i.e., the automorphisms). Determining the _injective_ endomorphisms looks
more challenging (and it is not even clear if any non-trivial characterization
is possible at all).

To begin, it is fairly easy to check that, if $f$ is an injective endomorphism
(e.g., one of the automorphisms) of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$, then so is the function $k\times
f\colon\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})\to\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})\colon
X\mapsto k\times\allowbreak X$ for an arbitrary
$k\in\allowbreak\mathbb{N}^{+}$; and it is only slightly more difficult to
show that the same is true of the function

$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})\to\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})\colon
X\mapsto\\{0,\max f(X)\\}+f(X).$ (22)

In particular, we have that $k\times X=k\times Y$, for some
$k\in\mathbb{N}^{+}$ and $X,Y\subseteq\mathbb{N}$, if and only if $X=Y$; and
on the other hand, $\\{0,\max f(X)\\}+f(X)=\\{0,\max f(Y)\\}+f(Y)$ yields
$\max f(X)=\max f(Y)$ and hence $f(X)=f(Y)$, which implies by the injectivity
of $f$ that $X=Y$.

With this said, we get from the above that an injective endomorphism of
$\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ need not send $n$-element sets to
$n$-element sets, which makes characterizing this kind of morphisms a delicate
matter.

##  4\. Prospects for future research

We have found (Theorem 3.2) that the automorphism group of the reduced power
monoid $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ of the additive monoid
$(\mathbb{N},+)$ of non-negative integers has order $2$, the only non-trivial
automorphism of $\mathcal{P}_{\mathrm{fin},0}(\mathbb{N})$ being the reversion
map $X\mapsto\max X-X$. In fact, there is some evidence that the result can be
pushed a little further. More precisely, recall that a numerical monoid is a
submonoid $S$ of $(\mathbb{N},+)$ such that $\mathbb{N}\smallsetminus S$ is a
finite set. We then have the following:

######  Conjecture.

The automorphism group of the reduced power monoid of a numerical monoid
_properly_ contained in $\mathbb{N}$ is trivial (that is, the only
automorphism is the identity).

Moreover, regardless or whether the conjecture is true or not, we are
naturally led to consider an “inverse problem” that is probably woven much
deeper in the theory:

######  Question 1.

For which groups $G$ does there exist a monoid $H$ such that the automorphism
group of the reduced power monoid $\mathcal{P}_{\mathrm{fin},1}(H)$ of $H$ is
isomorphic to $G$?

We know from Sect. 1 that the automorphism group of the monoid $H$ embeds in
the automorphism group of $\mathcal{P}_{\mathrm{fin},1}(H)$. Yet, it is not
quite clear how this can help to answer the problem, as we gather from Theorem
3.2 that the latter group can be larger than the former.

## References

  * [1] J. Almeida, _Some Key Problems on Finite Semigroups_ , Semigroup Forum 64 (2002), 159–179.
  * [2] D.F. Anderson and F. Gotti, “Bounded and finite factorization domains”, pp. 7–57 in: A. Badawi and J. Coykendall, _Rings, Monoids, and Module Theory_ , Springer Proc. Math. Stat. 382, Springer, 2022.
  * [3] A.A. Antoniou and S. Tringali, _On the Arithmetic of Power Monoids and Sumsets in Cyclic Groups_ , Pacific J. Math. 312 (2021), No. 2, 279–308.
  * [4] P.-Y. Bienvenu and A. Geroldinger, _On algebraic properties of power monoids of numerical monoids_ , Israel J. Math., to appear (https://arxiv.org/abs/2205.00982).
  * [5] L. Cossu and S. Tringali, _Abstract Factorization Theorems with Applications to Idempotent Factorizations_ , Israel J. Math., to appear (https://arxiv.org/abs/2108.12379).
  * [6] L. Cossu and S. Tringali, _Factorization under Local Finiteness Conditions_ , J. Algebra 630 (Sept. 2023), 128–161.
  * [7] L. Cossu and S. Tringali, _On the finiteness of certain factorization invariants_ , Ark. Mat., to appear (https://arxiv.org/abs/2301.09961).
  * [8] Y. Fan and S. Tringali, _Power monoids: A bridge between Factorization Theory and Arithmetic Combinatorics_ , J. Algebra 512 (Oct. 2018), 252–294.
  * [9] A. Geroldinger and F. Halter-Koch, _Non-Unique Factorizations. Algebraic, Combinatorial and Analytic Theory_ , Pure Appl. Math. 278, Chapman & Hall/CRC, 2006.
  * [10] A. Geroldinger and M.A. Khadam, _On the arithmetic of monoids of ideals_ , Ark. Mat. 60 (2022), No. 1, 67–106.
  * [11] A. Geroldinger and Q. Zhong, _Factorization theory in commutative monoids_ , Semigroup Forum 100 (2020), 22–51.
  * [12] J.M. Howie, _Fundamentals of Semigroup Theory_ , London Math. Soc. Monogr. Ser. 12, Oxford Univ. Press, 1995.
  * [13] M.B. Nathanson, _Sums of finite sets of integers_ , Amer. Math. Monthly 79 (1972), No. 9, 1010–1012.
  * [14] J.-E. Pin, “$BG=PG$: A success story”, pp. 33–47 in: J. Fountain, _Semigroups, Formal Languages and Groups_ , NATO ASI Ser., Ser. C, Math. Phys. Sci. 466, Kluwer, 1995.
  * [15] A. Sárközy, _On additive decompositions of the set of quadratic residues modulo $p$_, Acta Arith. 155 (2012), No. 1, 41–51.
  * [16] T. Tamura and J. Shafer, _Power semigroups_ , Math. Japon. 12 (1967), 25–32; Errata, _ibid._ 29 (1984), No. 4, 679.
  * [17] S. Tringali, _A characterisation of atomicity_ , Math. Proc. Cambridge Phil. Soc. 175 (2023), No. 2, 459–465.
  * [18] S. Tringali, _An abstract factorization theorem and some applications_ , J. Algebra 602 (July 2022), 352–380.
  * [19] S. Tringali and W. Yan, _A conjecture of Bienvenu and Geroldinger on power monoids_ , Proc. Amer. Math. Soc., to appear (https://arxiv.org/abs/2310.17713).