# Sets that are not sum of subsets

Let $$\mathcal P$$ be the set of finite subsets of $$\mathbb Z_{\geq 0}$$ , each of them contains $$0$$. We say that $$A \in \mathcal P$$ is indecomposable if it is not $$B+C$$ (the sum set of $$B,C$$) with $$B,C\in \mathcal P$$ and $$B,C\neq \{0\}$$.

It is easy to see which small cardinality sets are indecomposable. If $$|A|=2$$, then it is indecomposable. If $$A=\{0, x, y\}$$ with $$0, A is indecomposable iff $$y\neq 2x$$. If $$A=\{0, A is indecomposable iff $$z\neq x+y$$.

My questions are:

Questions: have these sets been studied before? Are there nice characterizations? Do they have interesting counts, for instance, the number of indecomposable sets whose largest element is $$n$$?

• Do you mean $\ \{0\}\in P\$ ? Oct 31, 2021 at 5:01
• @WlodAA: I mean each set contains $0$ in it. Oct 31, 2021 at 5:20
• OK, I should have realized that! Evidently, $B=C$ is allowed. Oct 31, 2021 at 6:10
• You may want to search for "power monoids". I'll try to provide further details later as time permits. Oct 31, 2021 at 7:46
• @WlodAA: all finite subsets. Oct 31, 2021 at 8:49

There are three questions in the OP, and I'll try to address each of them in as comprehensive a way as I can. I'll be glad to add in further details (and references) if requested.

Preliminaries on free monoids.

We write $$\mathscr F(X)$$ for the free monoid on an alphabet $$X$$. We refer to the elements of $$\mathscr F(X)$$ as $$X$$-words (or simply words), and to the identity of $$\mathscr F(X)$$, denoted by $$\varepsilon_X$$, as the empty word. We use the symbol $$\ast$$ for the operation of $$\mathscr F(X)$$, and assume that $$\mathscr F(X)$$ has been realized in such a way that $$X \subseteq \mathscr F(X)$$. In so doing, a non-empty $$X$$-word $$\mathfrak z$$ can be uniquely factored as $$z_1 \ast \cdots \ast z_n$$ for some $$z_1, \ldots, z_n \in X$$, where $$n$$ is a positive integer called the length of $$\mathfrak z$$ and denoted by $$\|\mathfrak z\|$$. Besides, we set $$\|\varepsilon_X\| := 0$$.

Pills of factorization theory.

Let $$H$$ be a multiplicatively written monoid; in particular, one may want to think about the case where $$H$$ is the multiplicative monoid of a (unital) ring, or the multiplicative monoid of the non-zero elements of a domain (note that $$H$$ need not be commutative).

An atom of $$H$$ is a non-unit $$a \in H$$ with the property that $$a \ne xy$$ for all non-units $$x, y \in H$$ (see Note (0)). Atoms are basically a monoid-theoretic abstraction of what (most) people in commutative algebra keep calling irreducible elements; the origins of the term are commonly traced back to the early work of P.M. Cohn on unique factorization in non-commutative domains (see Note (1)).

Let $$\mathscr A(H)$$ be the set of atoms of $$H$$. An atomic factorization of an element $$x \in H$$ is a word $$\mathfrak a \in \mathscr F(\mathscr A(H))$$ such that $$\pi_H(\mathfrak a) = x$$, where $$\pi_H$$ is the unique monoid homomorphism $$\mathscr F(H) \to H$$ such that $$\pi_H(z) = z$$ for every $$z \in H$$ (see Note (2)); we write $$\mathsf L_H(x)$$ for the set of (atomic) lengths of $$x$$, that is, the set of all integers $$k \ge 0$$ for which there is an atomic factorization $$\mathfrak a$$ of $$x$$ with $$\|\mathfrak a\| = k$$. We refer to $$\mathscr L(H) := \{\mathsf L_H(x): x \in H\} \setminus \{\emptyset\}$$ as the system of sets of (atomic) lengths of $$H$$; this is probably the most fundamental invariant commonly used in factorization theory to describe the departure of $$H$$ from a condition of "factoriality".

Power monoids.

Given a monoid $$H$$, the set of all subsets of $$H$$ is itself a monoid, herein denoted by $$\mathcal P(H)$$ and called the full power monoid of $$H$$, when endowed with the binary operation of setwise multiplication $$(X, Y) \mapsto \{xy: x \in X,\, y \in Y\}.$$ Apart from trivial cases, the structure of $$\mathcal P(H)$$ is rather complicated, and a first step towards understanding it better is to consider submonoids of this object that are in some sense tamer, including the reduced power monoid $$\mathcal P_{{\rm fin}, 1}(H) := \{X \in \mathcal P(H): 1_H \in X \text{ and } |X| < \infty\}.$$ In a way, "power monoids" have been around for a while; after all, they are the "natural framework" beyond some of the main questions of interest in arithmetic combinatorics (see Seva's answer for some references). However, it's only very recently that, to the best of my knowledge, power monoids have been explicitly considered as (algebraic) structures in their own right; in particular, this is definitely true if we restrict attention to the study of their properties from the point of view of factorization theory.

The OP is about the special case where $$H$$ is the additive monoid $$(\mathbf N, +)$$ of the non-negative integers; in fact, what the OP is calling an indecomposable subset of $$\mathbf N$$ is but an atom of the restricted power monoid of $$(\mathbf N, +)$$, which I'll denote herein by $$\mathcal P_{{\rm fin},0}(\mathbf N)$$ and write additively (in contrast with the previous section). One open problem in this area is the conjecture formulated in Sect. 5 of

• Fan and T., Power monoids: A bridge between factorization theory and arithmetic combinatorics, J. Algebra 512 (Oct 2018), 252-294.

The conjecture states that every non-empty finite subset $$L$$ of $$\mathbf N_{\ge 2}$$ belongs to the system of sets of lengths of $$\mathcal P_{{\rm fin},0}(\mathbf N)$$; that is, there exists a finite subset $$X$$ of $$\mathbf N$$ with $$0 \in X$$ such that $$k \in L$$ if and only if $$X = A_1 + \cdots + A_k$$ for some atoms $$A_1, \ldots, A_k$$ of $$\mathcal P_{{\rm fin},0}(\mathbf N)$$. Not much is known about this problem, apart from the fact that the conjecture is true when $$L$$ is either the (discrete) interval $$[\![2, n ]\!]$$, the singleton $$\{n\}$$, or the two-element set $$\{2, n+1\}$$, where $$n$$ is an arbitrary integer $$\ge 2$$. Related questions are discussed in

• Antoniou and T., On the Arithmetic of Power Monoids and Sumsets in Cyclic Groups, Pacific J. Math. 312 (2021), No. 2, 279-308,

where, in particular, one can read a lot more about minimal atomic factorizations in the restricted power monoid of a finite group (see Note (3)).

Questions (freely quoted from the OP).

Q1: Have indecomposable subsets of the non-negative integers been studied before?

All sorts of questions about atomic factorizations require, in the first place, an adequate understanding of the atoms of the monoid under consideration. So I'd say that the answer to this question is rather yes than no.

Q2: Are there nice characterizations of the indecomposable subsets of the non-negative integers?

I'm afraid this question is hopeless, at least if taken literally. In a sense (see the next question), there are way too many atoms in $$\mathcal P_{{\rm fin}, 0}(\mathbf N)$$ for any sensible characterization to be feasible. However, it's possible to construct (infinite) families of "well-structured atoms", which can often be used to prove a number of cute little things; the two papers cited in the section "Power monoids" discuss some of these constructions.

Q3: Is there anything in the know about the number of indecomposable subsets of the non-negative integers whose maximum is $$\leq n$$?

Given $$n \in \mathbf N$$, let $$\alpha(n)$$ be the number of atoms of $$\mathcal P_{{\rm fin}, 0}(\mathbf N)$$ in the interval $$[\![0, n ]\!]$$. Qinghai Zhong and I have a manuscript (resting in peace in our drawers for a couple of years or so) where we prove a lower bound on $$\alpha(n)$$ that, in particular, implies that $$\alpha(n)/2^n \to 1$$ as $$n \to \infty$$. This is a "density result", suggesting that most elements of $$\mathcal P_{{\rm fin}, 0}(\mathbf N)$$ are in fact atoms (note that $$2^n$$ is the total number of subsets of $$[\![0, n ]\!]$$ containing $$0$$).

Notes.

(0) A unit of $$H$$ is an element $$u \in H$$ with $$uv = vu = 1_H$$ for some $$v \in H$$, where $$1_H$$ is the identity of $$H$$; and a non-unit is, unsurprisingly, an element that is not a unit.

(1) Out of the "comfort zone" of integral domains (and, more generally, of commutative "nearly cancellative" monoids), it is useful and, to some extent, even necessary to distinguish atoms from the related notion of "irreducible", where we take an irreducible of $$H$$ to be a non-unit element $$a \in H$$ such that, if $$a = xy$$ for some $$x, y \in H$$, then either $$a$$ and $$x$$ generate the same principal $$s$$-ideal (i.e., $$HaH = HxH$$), or so do $$a$$ and $$y$$. To my knowledge, the significance of this distinction was first realized by D.D. Anderson and S. Valdes-Leon in

• Factorization in commutative rings with zero divisors, Rocky Mountain J. Math. 26 (1996), No. 2, 439-480.

However, Anderson and Valdes-Leon's paper (as most of the papers in this business) is entirely about the case where $$H$$ is a commutative monoid (more precisely, the multiplicative monoid of a commutative ring). For the non-commutative part of the story and beyond, I can only address the interested reader to a recent preprint of mine on monoids and preorders (arXiv link).

(2) In this context, $$\pi_H$$ is usually referred to as the factorization homomorphism of $$H$$.

(3) Power monoids are "highly non-cancellative" monoids, so much so that the classical theory of factorization breaks down dramatically when applied to them (if, for instance, $$H$$ is a finite monoid, then $$XH = HX = H$$ for every non-empty $$X \subseteq H$$); this "conceptual breakdown" doesn't even spare the notion of atomic factorization defined in the section "Pills of factorization theory", which has eventually led to the introduction of the refined notion of minimal atomic factorization in the PJM paper I'm referring to. The good news is that $$\mathcal P_{{\rm fin}, 0}(\mathbf N)$$ is commutative and "nearly cancellative", which implies that, in this particular case, atomic factorizations and minimal atomic factorizations are one and the same thing.

• Fantastic, and exactly what I need. I wish I can upvote more. Quick question: doesn't the result you mentioned in answer to Ques 3 implies that most elements of $P$ are not atoms? Did you mean to write the limit goes to $1$? Oct 31, 2021 at 16:43
• Yes, sorry for the confusion, I meant to write that the limit goes to $1$. Meanwhile, I've also added a "Note (3)", since referring to minimal atomic factorizations (without at least explaining what they are meant for) sounded a bit pointless. Oct 31, 2021 at 17:07
• Salvo: great! Do you have time in near future to discuss some more specific questions? Oct 31, 2021 at 17:19
• Hailong: I would be absolutely delighted. Oct 31, 2021 at 17:22
• Does the definition of reduced power monoids have a minor typo (an X where there should be an H?), or an I misunderstanding? Nov 1, 2021 at 19:31

Sure, this has been studied, and various generalizations are known (infinite sets, three and more set summands, abelian groups other than the group of integers, asymptotic decompositions). You can check, say, the paper of Elsholtz and Harper Additive decompositions of sets with restricted prime factors and the references therein for a pretty comprehensive overview.

There seem to be more open questions and conjecture than results in this area. To mention just two, Ostmann's conjecture dating back to 1968 states that the set of prime numbers is asymptotically additively indecomposable, and Sarkozy has conjectured that the set of quadratic residues modulo a prime is indecomposible. (There is a nice argument of Shkredov showing that the set of quadratic residues cannot be represented as $$A+A$$, but it is not known whether it can be represented, say, as $$A-A$$; see this paper.) Two more links: Large sets in finite fields are sumsets by Alon, and Problem 4.11 here.

• Thanks, the references certainly look relevant, I will try to read more. +1 Oct 31, 2021 at 8:01
• Much of the literature (see also Ostmann mathscinet.ams.org/mathscinet-getitem?mr=98721, Sárközy mathscinet.ams.org/mathscinet-getitem?mr=179147 ) is about decomposing infinite sets. It seems the question is more about the finite case. A result by Wirsing mathscinet.ams.org/mathscinet-getitem?mr=58655 implies as a special case that almost all finite sets are not sumsets, (compare also Question 3 in Salvo Tringali's answer.) Nov 1, 2021 at 8:35
• @ChristianElsholtz Hello! Didn't Wirsing prove that "almost all subsets of $\mathbf{N}$ (in the sense of measure) are not sumsets"? In such case, the family of finite sets would be itself a measure zero set.. Sep 19, 2022 at 21:29