Skip to main content
3 of 11
added 22 characters in body
Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64

The set of lengths of $nX$ gets larger and larger for every non-zero, non-empty, finite $X \subseteq \mathbf N$ with $0 \in \mathbf N$

Let $\mathcal P_{{\rm fin},0}(\mathbf N)$ be the monoid of non-empty, finite subsets of $\mathbf N$ with $0 \in \mathbf N$ equipped with the operation $$\mathcal P_{{\rm fin},0}(\mathbf N) \times \mathcal P_{{\rm fin},0}(\mathbf N) \to \mathcal P_{{\rm fin},0}(\mathbf N): (X, Y) \mapsto \{x+y: x \in X,\, y \in Y\},$$ which we'll denote, as usual, with the symbol "$+$".

We refer to a set $A \in \mathcal P_{{\rm fin},0}(\mathbf N)$ as an atom if (i) $A \ne \{0\}$ and (ii) $A \ne X+Y$ for all $X, Y \in \mathcal P_{{\rm fin},0}(\mathbf N) \setminus \bigl\{\{0\}\bigr\}$: Note that $\{0\}$ is the identity (and, in fact, the only unit) of $\mathcal P_{{\rm fin},0}(\mathbf N)$, so this is nothing but a special instance of the abstract notion of atom (or irreducible element) for an arbitrary monoid.

With this in mind, fix $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$. We take ${\sf L}(X) := \{0\}$ if $X = \{0\}$; otherwise, ${\sf L}(X)$ is the set of all $k \in \mathbf N^+$ for which there exist atoms $A_1, \ldots, A_k \in \mathcal P_{{\rm fin},0}(\mathbf N)$ such that $X = A_1 + \cdots + A_k$: In factorization theory, ${\sf L}(X)$ would be called the set of lengths of $X$ (relative to the atoms of $\mathcal P_{{\rm fin},0}(\mathbf N)$), which explains the title.

Q. Is it true that $|{\sf L}(nX)| \to \infty$ as $n \to \infty$, unless $X = \{0\}$?

Of course, it's enough to show that the answer is yes in the special case when $X$ is an atom, though I'm not so sure that this makes things any easier. What is perhaps more interesting is that a positive answer is equivalent to showing that there exists $n \in \mathbf N^+$ such that $|\mathsf L(nX)| \ge 2$: This comes as a consequence of a general, simple fact about sets of lengths in factorization theory.

Incidentally, it's probably worth mentioning that $\mathcal P_{{\rm fin},0}(\mathbf N)$ is a (reduced) BF-monoid, that is, $1 \le |\mathsf L(X)| < \infty$ for every non-zero $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$.

Edit. To be completely open, I believe that something much stronger is true: That the limit of $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ is positive (if not even equal to $\infty$) for every non-zero $X \in \mathcal P_{{\rm fin},0}(\mathbf N)$, where the existence of the limit follows from Fekete's lemma, the general property of sets of lengths alluded to in the above, and the basic fact that $|A+B| \ge |A| + |B|-1$ for all non-empty $A, B \subseteq \mathbf Z$.

Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64