Skip to main content
7 of 11
fixed a typo
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.

Edit 1. 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 2. 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$.

Edit 3. With reference to Edit 2, let me note that the limit $\frac{1}{n} |{\sf L}(nX)|$ as $n \to \infty$ need not be infinite (and, on a second thought, it sounds much more plausible that it's always finite). Indeed, consider the case when $X = [\![0, m]\!]$ for some $m \in \mathbf N^+$. Then $nX = [\![0, mn]\!]$ for all $n \in \mathbf N^+$, and hence $\frac{1}{n} |{\sf L}(nX)| \to m$ as $n \to \infty$, since it can be proved (this is not for free) that ${\sf L}([\![0, k]\!]) = [\![2,k]\!]$ for every integer $k \ge 2$.

Edit 4. Yes, of course: The limit in Edit 2 is always finite. Indeed, let $n \in \mathbf N^+$ and suppose that $nX = X_1 + \cdots + X_k$ for some non-zero sets $X_1, \ldots, X_k \subseteq \mathbf N$ (either atoms or not). Then $X \ne \{0\}$, $X_i$ is finite and non-empty for each $i$, and $$n \max X = \max X_1 + \cdots + \max X_k \ge k,$$ which, in turn, yields $ \frac{1}{n}|{\sf L}(nX)| \le \max X$.

Salvo Tringali
  • 10.5k
  • 2
  • 29
  • 64