Maximally Additively Reducible Subsets of the Integers

Gal Gross Department of Mathematics University of Toronto Toronto, ON M5S 2E4 Canada

               g.gross@mail.utoronto.ca

Abstract

Let A, B ⊆ ℕ be two finite sets of natural numbers. We say that B is an additive divisor of A if there exists some C ⊆ ℕ with A = B + C, where ‘+’ denotes the sumset operation, also called Minkowski sum or pairwise sum. We prove that among subsets of {0, 1, …, k} containing 0 as an element, the full set {0, 1, …, k} has the most additive divisors. To remove the restriction of having 0 as an element, we first prove a correspondence between the sumset operation and binary lunar multiplication. Lunar arithmetic (originally named “dismal arithmetic”) is a kind of min/max arithmetic introduced by Applegate, LeBrun, and Sloane. The number of binary lunar divisors is related to restricted compositions of integers—restricted in that the first part must be greater or equal to all other parts. We establish some bounds on the number of such compositions and conclude that {1, …, k} has the most additive divisors among all subsets of {0, 1, …, k}. These two results prove two conjectures of LeBrun et al. regarding the maximal number of lunar binary divisors, a special case of a more general conjecture about lunar divisors in arbitrary bases. We prove this third conjecture by introducing a sumset-like operation for multisets.

1 Introduction

Definition 1. Let (G, +) be a commutative group, and let A, B ⊆ G be subsets. The sumset (also called Minkowski sum) of A and B, denoted A + B, is the set of pairwise sums:

A + B := {a + b : a ∈ A, b ∈ B}.

(In particular, A + ∅ = ∅ for any A ⊆ G.) The difference set of A and B, denoted A − B, is the set

A − B := {a − b : a ∈ A, b ∈ B}.

Notation 2. In this paper, we shall use the backward slash, A \ B, to denote the relative complement:

A \ B := {a ∈ A : a ∉ B}.

Here is another way of thinking about the sumset of A and B, which will become important later in the paper. For each b ∈ B we are shifting the elements of A by b to form the set A + {b}, then we take the union A + B = ⋃_{b∈B}(A + {b}). Figure 1a contains a graphical representation of this process, and Figure 1b some examples of the operations above with the integers as the ambient group.

0 1 2 3 4 5 6 ⋯ ● ● {0, 2} + {1} ● ● {0, 2} + {2} ● ● {0, 2} + {4} ● ● ● ● ● {0, 2} + {1, 2, 4}

(a) Graphical representation of {0, 2} + {1, 2, 4}.

\begin{aligned}\{1, 2, 3\} & + & \{1, 2, 3\} & = & \{2, 3, 4, 5, 6\}; \\ \{1, 2, 3\} & − & \{1, 2, 3\} & = & \{−2, −1, 0, 1, 2\}; \\ \{1, 2, 3\} & \ & \{1, 2, 3\} & = & ∅; \\ \{2, 3\} & + & \{1, 3, 7\} & = & \{3, 4, 5, 6, 9, 10\}; \\ \{2, 3\} & − & \{1, 3, 7\} & = & \{−5, −4, −1, 0, 1, 2\}; \\ \{1, 3, 7\} & − & \{2, 3\} & = & \{−2, −1, 0, 1, 4, 5\}; \\ \{0, 2\} & + & \{1, 2, 4\} & = & \{1, 2, 3, 4, 6\}. \end{aligned}

(b) Examples of the operations, with ℤ as the ambient group.

Figure 1: Examples of sumsets, difference sets, and relative complement, with ℤ as the ambient group.

Classical additive number theory studies direct problems: given a certain set A, what can we say about its sumset A + A, or iterated sumsets nA := A + ⋯ + A (with n summands, for some n ∈ ℕ)? (We recommend Nathanson’s book [12] for an excellent introduction.) In contrast, inverse problems in additive number theory aim to extract information about a set A from information about its sumsets. (Nathanson’s second volume [13] deals with inverse problems, while Tao and Vu’s book [17] gives an overview of both direct and inverse problems.) One such inverse problem is the question: which subsets are sumsets? The asymptotic version of this question was first raised by Ostmann [14].

Definition 3. A set A ⊆ ℕ^{+} of positive integers is said to be Ostmann reducible if there are sets B, C ⊆ ℕ^{+} each with more than one element, such that A = B + C. Otherwise, the set A is said to be Ostmann irreducible. Similarly, we call a set A ⊆ ℕ^{+} asymptotically (additively) reducible if there are some sets B, C ⊆ ℕ^{+} each with more than one element, and a natural number m ∈ ℕ such that

(B + C) ∩ [m, ∞) = A ∩ [m, ∞).

Otherwise, the set A is said to be asymptotically (additively) irreducible.

Let P denote the set of prime numbers. It is easy to see that P is Ostmann irreducible (because 2, 3 ∈ P), and Ostmann conjectured that it is in fact asymptotically irreducible. This conjecture is sometimes referred to as the “inverse Goldbach problem”, and it remains unsolved. The conjecture has since been placed in the wider context of the “sum-product phenomenon” as exemplified by Erdős and Szemerédi [4] (Elsholtz [3] reviewed some more recent progress).

Regardless of any multiplicative structure, Wirsing [18] has proved that almost all subsets of ℕ are asymptotically irreducible, and hence also Ostmann irreducible. (To interpret “almost all”, one identifies subsets of ℕ with their binary encoding, and thus with the interval [0, 2] ⊆ ℝ. We use a similar encoding in Section 3 below.)

Rather than asking which sets are irreducible, this paper is concerned with the opposite question: given some k ∈ ℕ, which subsets A ⊆ {0, …, k} ⊆ ℕ are maximally reducible?

Definition 4. Let A ⊆ ℕ be a set of natural numbers. We say that a set B ⊆ ℕ is an additive divisor (or sumset divisor, or divisor, or factor) for A, if there exists some set C ⊆ ℕ such that A = B + C. We then call B + C a factorization of A.

Every set A ⊊ ℕ has a trivial factorization A = A + {0}. If the trivial factorization is the only possible factorization of A we say that A is (additively) irreducible, otherwise we say that A is (additively) reducible.

If the set A is finite, we let d(A) denote the number of sumset divisors of A.

The trivial factorization A = A + {0} shows that every set A ≠ {0} has at least two divisors. Additively irreducible sets have exactly two divisors (except {0} which has exactly one divisor). In Ostmann’s definition, Definition 3, shifting a set is considered a trivial factorization and is thus excluded from consideration—that is the meaning of the restriction that each set must have more than one element. We place no restrictions on the nature of our divisors. As an example, the set {2, 3} is Ostmann irreducible, but additively reducible since {2, 3} = {1} + {1, 2}.

We now fix some k ∈ ℕ and consider the set of all subsets of {0, …, k}. In Section 2 we introduce an operation called “k-promotion”, acting on divisors of subsets which have 0 as an element. Theorem 13 of Section 2 shows that among those subsets which have 0 as an element, the full set {0, 1, …, k} has the most divisors. At first blush it may appear unsurprising that the full set has the most divisors, but if we remove the restriction that 0 is an element this is no longer the case. Theorem 30 in Section 5 shows that {1, …, k} has the most divisors among all subsets of {0, …, k}.

In Section 3 we assign each finite subset of ℕ a binary number, and Theorem 1 proves that the sumset operation corresponds to binary lunar multiplication. Lunar multiplication is an operator defined by Applegate, LeBrun, and Sloane [1] in their study of alternative systems of arithmetic in which long addition and long multiplication can be performed without “carries”. This new correspondence connects the number of sumset divisors to the number of lunar divisors. In their paper, Applegate, LeBrun, and Sloane established a correspondence between the number of binary lunar divisors of 11 ⋯ 1|_{2} with k repetitions of the digit 1, and the number of restricted compositions of k. The compositions are restricted in that the first part must be greater or equal to all other parts. In Section 4 we study the link between such compositions and generalized Fibonacci numbers. We use this link to establish some bounds leading to the proof of Theorem 30 in Section 5, which states that {1, …, k} has the most divisors among all subsets of {0, …, k}.

Due to the correspondence between sumset divisors and binary lunar divisors, Theorem 13 and Theorem 30 resolve two conjectures of Applegate, LeBrun, and Sloane, reproduced in Section 3 as Conjecture 16 and Conjecture 15. These conjectures are a binary version of a more general Conjecture 14, since lunar arithmetic can be defined for arbitrary bases. Section 6 prepares the groundwork for proving this general conjecture by further exploring the restricted compositions from Section 4. Theorem 31 establishes a new recurrence relation for the function enumerating such restricted compositions. Section 6 discusses in detail the following interesting combinatorial interpretation of Theorem 31: the table enumerating these restricted compositions can be easily constructed using properties of the forward difference from the finite calculus. Bounds established by using this new recurrence allow us to prove Conjecture 14 in Theorem 47 of Section 7. Theorem 37 of Section 7 extends the correspondence between sumsets and binary lunar multiplication to arbitrary bases by using multisets instead of sets, and introducing a sumset operation on multisets.

We conclude with some open questions in Section 8.

2 Divisors of 0-rooted sets

Notation 5. Fix some k ∈ ℕ. Throughout the paper we let [k] denote the full interval

[k] := [0, k] ∩ ℕ = {0, …, k}.

Definition 6. We say that a set A ⊆ ℕ of nonnegative integers is 0-rooted if min A = 0.

For any k ∈ N, we denote by Z_{k} the collection of 0-rooted sets whose maximal element is k:

Z_{k} := {A ⊆ ℕ : min A = 0, max A = k}.

For convenience we also introduce the notation Z_{≤k} for the collection of 0-rooted sets whose maximal element does not exceed k:

Z_{≤k} := ⋃_{ℓ≤k} Z_{ℓ}.

We let Z denote the collection of finite 0-rooted sets:

Z := ⋃_{k∈ℕ} Z_{k}.

An interesting feature of 0-rooted sets is that the divisors are subsets. Indeed, suppose A ∈ Z is a 0-rooted set, with a factorization A = B + C for some B, C ⊆ ℕ. Since the only way to obtain 0 by adding natural numbers is 0+0 = 0, we must have 0 ∈ B, C so that B, C are themselves 0-rooted. Moreover, since 0 ∈ C we have that B = B + {0} ⊆ B + C = A, and similarly C ⊆ A. Thus, the divisors of a 0-rooted set A are always subsets of A.

The purpose of this section is to prove that among the 0-rooted sets Z_{≤k}, the full interval [k] has the most divisors. The key idea is a procedure for converting divisors of any set A ∈ Z_{≤k} into divisors of [k]. We call this procedure k-promotion.

Definition 7. Let k ∈ ℕ, and let A ∈ Z_{≤k}. Suppose that B, C ⊆ ℕ such that A = B + C, and such that max B ≤ max C. We now define a new set C_{B} as the union of three sets C, B_{1}, and B_{2}, where

B_{1} = ([k] \ A) ∩ [max B − 1],
B_{2} = (([k] \ A) − {max B}) ∩ ℕ.

That is, C_{B} is constructed by the following algorithm:

for each s ∈ [k] \ A:

if s < max B, append s to C;

if s ≥ max B, append s − max B to C.

Note that set C_{B} resulting from the k-promotion procedure depends not only on the set B, but also on the set A, and on the natural number k. Some examples of the procedure are shown in Figure 2.

B  C  A  B  C_{B}  [k]
{0, 3} + {0, 4} = {0, 3, 4, 7} ↝ {0, 3} + {0, 1, 2, 3, 4} = [7]
{0, 3} + {0, 4} = {0, 3, 4, 7} ↝ {0, 3} + {0, 1, 2, 3, 4, 5} = [8]
{0, 3} + {0, 1, 3} = {0, 1, 3, 4, 6} ↝ {0, 3} + {0, 1, 2, 3}  = [6]
{0, 1, 3} + {0, 3} = {0, 1, 3, 4, 6} ↝ {0, 1, 3} + {0, 2, 3}  = [6]

Figure 2: Examples of k-promotion.

In the top row A is regarded as a subset of Z_{≤7}, while in the next it is regarded as a subset of Z_{≤8}. In the bottom two rows A is regarded as a subset of Z_{≤6}. Its divisors {0, 3} and

{0, 1, 3} share the same maximal element, so either one of them could be promoted.

Lemma 8. Let k ∈ ℕ, and let A ∈ Z_{≤k}. Suppose that B, C ⊆ ℕ such that A = B + C, and such that max B ≤ max C. Then B + C_{B} = [k].

Proof. Since C ⊆ C_{B} we have A = B + C ⊆ B + C_{B}. Moreover, by construction, [k] \ A ⊆ B + C_{B}. Thus, [k] = A ∪ ([k] \ A) ⊆ B + C_{B}.

To prove the reverse inclusion, note that max(B + C_{B}) = max B + max C_{B}. By construction, max C_{B} ≤ max{k − max B, max C} so that

max B + max C_{B} ≤ max{k, max B + max C} = max{k, max A} ≤ k.

Moreover, min(B + C_{B}) = 0. Thus, B + C_{B} ⊆ [k].

Each factor C of A appears in one or more factorizations. We may apply the promotion procedure to each such factorization, each time obtaining a factor of [k]. We let F_{A}(C) denote the resulting sets of factor of [k]. Some examples follow the formal definition below.

Definition 9. Let k ∈ ℕ, and let A ∈ Z_{≤k}. Suppose C is a factor of A. We define the set F_{A}(C) by the following algorithm:

For each B ⊆ A such that B + C = A:

if max B ≥ max C, let C ∈ F_{A}(C);
if max B ≤ max C, let C_{B} ∈ F_{A}(C).

(Note that this means that if there is some B with max B = max C, then both C and C_{B} are elements of F_{A}(C).)

We note that, as with the promotion procedure itself, F_{A}(C) depends not only on the set A and the factor C, but also on the integer k. Figure 3 presents some examples of F_{A}(C) for different choices of C.

A = {0, 2, 3, 4, 5, 6} = {0, 2, 3} + {0, 2, 3} F_{A}({0, 2, 3}) = {{0, 2, 3} , {0, 1, 2, 3}};
= {0, 2} + {0, 3, 4}  F_{A}({0, 2}) = {{0, 2}};
= {0, 2} + {0, 2, 3, 4}. F_{A}({0, 3, 4}) = {{0, 1, 3, 4}};
F_{A}({0, 2, 3, 4}) = {{0, 1, 2, 3, 4}}.

Figure 3: Examples of F_{A}(C) for A = {0, 2, 3, 4, 5, 6} ∈ Z_{≤6}.

Theorem 10. Let k ∈ ℕ, and let A ∈ Z_{≤k}. If C and D are different divisors of A, then F_{A}(C) ∩ F_{A}(D) = ∅.

Proof. First note that for A = [k] and any divisor C of A we have F_{A}(C) = {C} so the claim follows. Assume therefore that A ⊊ [k], so in particular [k] \ A ≠ ∅. Suffice it to show that no element of F_{A}(C) is an element of F_{A}(D).

Step 1: C ∈ F_{A}(C) ⟹ C ∉ F_{A}(D). Suppose that C ∈ F_{A}(C). Then there exists some B ⊆ A with max B ≥ max C and B + C = A. By assumption, C ≠ D, and all other elements of F_{A}(D) are the result of k-promotion; that is, are of the form D_{E} for some E ⊆ A with max E ≤ max D and D + E = A. Since D ⊆ D_{E}, if D ⊈ C we are done. Assume therefore that D ⊆ C, so in particular max D ≤ max C. We therefore have the chain of inequalities:

max E ≤ max D ≤ max C ≤ max B.

On the other hand, we also know that

max A = max D + max E = max B + max C.

Therefore, none of the inequalities in the chain above can be strict, so we have a chain of equalities:

max E = max D = max C = max B.

Let us denote this common maximal value by m. Consider now the algorithmic construction of the set D_{E}. For any s ∈ [k] \ A there are two options:

• s < m, in which case s ∈ D_{E}. Since s ∉ A ⊇ C, this shows that C ≠ D_{E}.

• s ≥ m, in which case s − m ∈ D_{E}. Assume for contradiction that s − m ∈ C. Since m ∈ B we would then have s = m + (s − m) ∈ B + C = A, a contradiction. Thus, s − m ∉ C and C ≠ D_{E}.

We conclude that C ∈ F_{A}(C) ⟹ C ∉ F_{A}(D), as we wanted to show.

Step 2: The rest of F_{A}(C). All other elements of F_{A}(C) are of the form C_{B} for some suitable B ⊆ A, so we will now show that C_{B} ∈ F_{A}(C) implies C_{B} ∉ F_{A}(D). First note that by the argument above, if D ∈ F_{A}(D) we know that D ∉ F_{A}(C). All other elements of F_{A}(D) are of the form D_{E} for some suitable E ⊆ A. Specifically, we are assuming that there exist some B, E ⊆ A such that

A = B + C and max B ≤ max C,
A = D + E and max D ≥ max E.

Assume for contradiction that C_{B} = D_{E}.

First, suppose that C ⊆ D. Since C ≠ D by assumption, there must exist some d ∈ D such that d ∉ C. Since D ⊆ A we have d ∉ [k] \ A. However, since D ⊆ D_{E} we have d ∈ D_{E} = C_{B}, so there must be some s ∈ [k]\A with d = s−max B. Now, s = d+max B ∉ A implies max B ∉ E. Therefore, max E ≠ max B. However, [k] = C_{B} + B = D_{E} + E implies

k = max C_{B} + max B = max D_{E} + max E.

Since C_{B} = D_{E} we have max C_{B} = max D_{E} which implies max B = max E, a contradiction. We conclude that if C ⊆ D we must have C_{B} ≠ D_{E}, as we wanted to show.

On the other hand if C ⊈ D, there is some c ∈ C such that c ∉ D. Analogous argument to the one above then shows that max E ≠ max B, which again contradicts the assumption C_{B} = D_{E}.

Theorem 10 is enough to establish the maximality of d([k]) among the sets in Z_{≤k}. The following two lemmas will help show that d([k]) is also the unique maximum among the sets in Z_{≤k}.

Lemma 11. Let k ∈ ℕ be an odd number such that k ≥ 3. Then the set F_{k} := {0, (k + 1)/2} is a factor of [k] which does not arise from k-promotion. That is, for any A ∈ Z_{≤k} such that A ⊊ [k], and any divisor C of A, we have F_{k} ∉ F_{A}(C).

Proof. It is clear that F_{k} is a factor of [k], since

[k] = [(k − 1)/2] + F_{k}.

Let A ∈ Z_{≤k} such that A ⊊ [k], and let C be a divisor of A. Assume for contradiction that F_{k} ∈ F_{A}(C). Then either:

• C = F_{k} and C ∈ F_{A}(C). That is, there exists some B ⊆ A for which B + F_{k} = A and max B ≥ max F_{k}. But max F_{k} = (k + 1)/2 and (k + 1)/2 + (k + 1)/2 = k + 1 > k = max A. This is a contradiction.

• F_{k} = C_{B} for some B ⊆ A such that B + C = A and max B ≤ max C. Since C ⊆ C_{B} = F_{k} we must have C ⊆ {0, (k + 1)/2}. Moreover, since C is a divisor of A, it must be 0-rooted. We therefore have two options:

– Suppose C = {0}. The assumption max B ≤ max C forces B = {0}, in which case the k-promotion procedure results in C_{B} = [k] ≠ F_{k} (since k ≥ 3), a contradiction.

– Suppose C = F_{k}. Lemma 8 gives [k] = B + C_{B} = B + F_{k}. Since C = F_{k} we also have A = B + C = [k], contradicting the assumption that A ⊊ [k].

These contradictions show that F_{k} ∉ F_{A}(C).

In contrast with the odd case, it is straightforward to verify that all factors of the interval [4], for example, arise from a process of 4-promotion. We must weaken the hypothesis in the previous lemma from an absolute statement to a relative one:

Lemma 12. Let k ∈ ℕ be an even number such that k ≥ 4. Then for any A ∈ Z_{≤k} with A ⊊ [k], there exists some set F_{k}, such that F_{k} is a divisor of [k] and F_{k} ∉ F_{A}(C) for any divisor C of A.

Proof. We distinguish between two cases: A = [k] \ {2}, and A ≠ [k] \ {2}.

• A = [k] \ {2}. In this case we choose F_{k} = {0, 2}. Observe that this is indeed a factor

of [k], since (for example)

[k] = [k − 2] + F_{k}.

Now, fix some divisor C of A. If A = B + C is a factorization of A, then B, C ⊆ A and B, C are 0-rooted sets, and so 2 ∉ C (for otherwise 2 = 0 + 2 ∈ B + C ∈ A). Therefore F_{k} could only be an element of F_{A}(C) if F_{k} = C_{B} for a suitable B. Assume therefore that there exists some B ⊆ A with A = B + C, max B ≤ max C, and F_{k} = C_{B}. Since C ⊆ C_{B} = F_{k} and 2 ∉ C, we must have C = {0}. Since max B ≤ max C we also have B = {0}. But then A = B + C = {0}, contradicting the assumption that A = [k] \ {2} for k ≥ 4. This contradiction proves that F_{k} ∉ F_{A}(C) for any factor C of A.

• A ≠ [k] \ {2}. In this case we choose F_{k} = {0, 1, 3, 5, …, k − 1}. Observe that this is indeed a factor of [k], since (for example)

[k] = {0, 1} + F_{k}.

Now, fix some divisor C of A, and assume for contradiction that F_{k} ∈ F_{A}(C). We have the following two possibilities:

– F_{k} = C and C ∈ F_{A}(C). That is, there exists some B ⊆ A with B + F_{k} = A and max B ≥ max F_{k}. Since max F_{k} = k − 1 we obtain

max A = max B + max F_{k} ≥ (k − 1) + (k − 1) = 2k − 2.

Since max A ≤ k we also have 2k − 2 ≤ k, so that k ≤ 2. This contradicts the assumption that k ≥ 4.

– F_{k} = C_{B} for some B ⊆ A such that A = B + C and max B ≤ max C. Lemma 8 then implies [k] = B + C_{B} = B + F_{k}. In particular,

k = max([k]) = max B + max F_{k} = max B + (k − 1)

shows that max B = 1. Since B is also 0-rooted (being a divisor of A) we must have B = {0, 1}. Having determined the set B, we now turn our attention to the set C. Since C ⊆ C_{B}, we know that A = B + C ⊆ B + C_{B} = [k]. However, A ⊊ [k], so we must have C ⊊ C_{B} = F_{k}. We now show that the only element of F_{k} missing from C is 1. Indeed, since C is 0-rooted (being a divisor of A), we know that 0 ∈ C. All other elements of F_{k} are of the form 2x + 1 for some natural number x ∈ ℕ. Suppose 2x + 1 ∈ C_{B} \ C, and assume for contradiction that x > 0. Then we claim that 2x + 1, 2x + 2 ∉ A. This is because

A = B + C = {0, 1} + C,

and all nonzero elements of C are odd numbers. Then, from the k-promotion procedure, we have 2x = (2x + 1) − max B ∈ C_{B} = F_{k}. But the only even element in F_{k} is 0, contradicting the assumption that x > 0. This contradiction shows that the only possible element of F_{k} missing from C is 1. In other words, C = {0, 3, 5, …, k − 1}. But then

A = B + C = [k] \ {2},

contradicting our assumption that A ≠ [k] \ {2}.

We conclude that F_{k} ∉ F_{A}(C) for any factor C of A.

For any A ∈ Z_{≤k} with A ⊊ [k], we have found a divisor F_{k} of [k], such that F_{k} ∉ F_{A}(C) for any divisor C of A.

We can now conclude that every other set in Z_{≤k} has fewer divisors than [k].

Theorem 13. The set [k] is the unique maximum of d(·) in Z_{≤k}.

Proof. Given some 0-rooted set A ⊊ [k], we have a map C ↦ F_{A}(C) taking each divisor of A to a nonempty set of divisors of [k]. Theorem 10 shows that if C, D are different divisors of A, then F_{A}(C) and F_{A}(D) are disjoint. Therefore,

d([k]) ≥ ∑_{C divides A} card F_{A}(C) ≥ ∑_{C divides A} 1 = d(A).

This proves that [k] is a maximum of d(·) in Z_{≤k}.

Next, it is easy to see by direct computation that [k] is the unique maximum of d(·) for k = 0, 1, 2 (with 1, 2, 3 factors respectively). Lemma 11 and Lemma 12 show that [k] is the unique maximum of d(·) for k ≥ 3.

3 Lunar arithmetic

We now introduce lunar arithmetic^{1}, a type of min/max carry-less arithmetic defined and studied by Applegate, LeBrun, and Sloane [1]. The following paragraph recounts the definitions from their paper [1, Section 2] with a slight change of notation.

Given a natural number b ≥ 2, one starts with a set of digits D_{b} = {0, 1, …, b − 1} equipped with two binary operations, defined as follows: base b lunar addition, denoted ⊕_{b}, is the max operator on digits. That is, for any p, q ∈ D_{b},

p ⊕_{b} q = max{p, q}.

Base b lunar multiplication, denoted ⊗_{b}, is the min operator on digits. That is, for any p, q ∈ D_{b},

p ⊗_{b} q = min{p, q}.

As with any positional counting system, a base b lunar number is identified with a polynomial in D_{b}[X], i.e., a formal expression of the form ∑_{i=0}^{m} p_{i}X^{i}, where p_{i} ∈ D_{b} (for all 0 ≤ i ≤ m). Such an expression is also written in positional notation as p_{m}p_{m−1} ⋯ p_{1}p_{0}|_{b}. We can identify lunar numbers with natural numbers by evaluating the polynomial at the base b. Suppose P = ∑_{i=0}^{m} p_{i}X^{i} and Q = ∑_{j=0}^{n} q_{j}X^{j} are two lunar numbers, and assume without loss of generality that m ≤ n. The lunar sum of P and Q, denoted by P ⊕_{b} Q, is defined by performing digit-wise lunar addition:

1Originally published under the name dismal arithmetic, the authors have come to prefer the name “lunar arithmetic” instead [7]. Relevant OEIS [16] entries have also been renamed.

P ⊕_{b} Q = ∑_{j=0}^{n}(p_{j} ⊕_{b} q_{j})X^{j},

where p_{i} = 0 for i > m. Figure 4a (reproduced from Applegate, LeBrun, and Sloane [1, Figure 1a]) shows an example of base 10 lunar addition. Note the similarity to the traditional “long addition” of school arithmetic, except there are no carries. The lunar product of P and Q, denoted by P ⊗_{b} Q, is defined by convolution of digits, in an analogous way to multiplication in traditional arithmetic:

P ⊗_{b} Q = ∑_{ℓ=0}^{m+n} r_{ℓ}X^{ℓ},

where

r_{0} = p_{0} ⊗_{b} q_{0},
r_{1} = (p_{0} ⊗_{b} q_{1}) ⊕_{b} (p_{1} ⊗_{b} q_{0}),
⋮

That is, for any 0 ≤ ℓ ≤ m + n, we have

r_{ℓ} = (p_{0} ⊗_{b} q_{ℓ}) ⊕_{b} (p_{1} ⊗_{b} q_{ℓ−1}) ⊕_{b} ⋯ ⊕_{b} (p_{ℓ} ⊗_{b} q_{0}),

where p_{i} = 0 for i > m and q_{j} = 0 for j > n. Figure 4b (reproduced from Applegate, LeBrun, and Sloane [1, Figure 1b]) shows an example of base 10 lunar multiplication. Note the similarity to the traditional “long multiplication” of school arithmetic, except there are no carries.

\begin{aligned}& 169 \\ ⊕_{10} & 248 \\ & 269 \end{aligned}

(a) Base 10 lunar addition.

169

⊗_{10}  248

168

⊕_{10} 144
⊕_{10} 122

12468

(b) Base 10 lunar multiplication.

Figure 4: Examples in base 10 lunar arithmetic (from Applegate, LeBrun, and Sloane [1, Figure 1]).

Applegate, LeBrun, and Sloane proved [1, Theorem 1] that (D_{b}[X], ⊕_{b}, ⊗_{b}) is a commutative semiring; that is, that ⊕_{b} and ⊗_{b} are commutative and associative operations on D_{b}[X], and that ⊗_{b} distributes over ⊕_{b}. They then defined and studied different analogues of number-theoretic constructions including “primes, number of divisors, sum of divisors, and the partition function.” [1, Abstract] In particular, they defined d_{b}(n) as the number of lunar divisors (i.e., with respect to lunar multiplication) of n in base b. Section 6 of their paper [1, Section 6] contains a series of conjectures about the properties of d_{b}(n), which we reproduce below for ease of reference.

Conjecture 14 ([1, Conjecture 12]). In any base b ≥ 3, among all k-digit numbers n, d_{b}(n) has a unique maximum at n = (b^{k} − 1)/(b − 1) = 111 ⋯ 1|_{b}.

Conjecture 15 ([1, Conjecture 13]). In base 2, among all k-digit numbers n, the maximal value of d_{2}(n) occurs at n = 2^{k} − 2 = 111 ⋯ 10|_{2}, and this is the unique maximum for n ≠ 2, 4.

Conjecture 16 ([1, Conjecture 14]). In base 2, among all odd k-digit numbers n, d_{2}(n) has a unique maximum at n = 2^{k} − 1 = 111 ⋯ 11|_{2}.

Conjecture 17 ([1, Conjecture 14]). In base 2, among all odd k-digit numbers n, if k ≥ 3 and k ≠ 5, the second-largest value of d_{2}(n) occurs at n = 2^{k} −3 = 111 ⋯ 101|_{2}, and possibly other values of n.

The sequence d_{2}(1|_{2}), d_{2}(11|_{2}), d_{2}(111|_{2}), … from Conjecture 16 in particular appears to count many different combinatorial phenomena. Applegate, LeBrun, and Sloane [1, Remark after Theorem 16] mentioned several different contexts and referred to sequences \underline{A007059} and \underline{A079500} of the OEIS [16]. Frosini and Rinaldi [5] constructed explicit bijections between several of these combinatorial interpretations. As we discuss in Section 4 below, Applegate, LeBrun, and Sloane counted d_{2}(1 ⋯ 1|_{2}) by exhibiting a generating function for the sequence, based on an argument originally due to Richard Schroeppel.

We now prove that binary lunar multiplication corresponds to sumset addition, a new context for lunar arithmetic. This correspondence immediately proves Conjecture 16 by using Theorem 13; see Corollary 19. We then build on this result, and the investigation of Applegate, LeBrun, and Sloane to prove Conjecture 15; see Theorem 30. Finally, Section 7 extends this correspondence to lunar multiplication in other bases, which ultimately allows us to prove Conjecture 14; see Theorem 47. Conjecture 17 remains open.

Let F denote the collection of finite subsets of ℕ, and let B_{2} denote the set of binary numbers, written using the digits in D_{2} = {0, 1}. There is a natural bijection β_{2} : F → B_{2} based on the idea of encoding membership as a binary sequence. First, define β_{2}(∅) = 0. Next, for any nonempty P ∈ F we define the binary number β_{2}(P) = p_{max P} ⋯ p_{1}p_{0}|_{2}, where p_{i} for 0 ≤ i ≤ max P is defined as follows:

p_{i} = \begin{cases}1, & if i ∈ P; \\ 0, & if i ∉ P. \end{cases}

Let P, Q ∈ F. The key observation, which we prove in Theorem 18, is

β_{2}(P + Q) = β_{2}(P) ⊗_{2} β_{2}(Q).  (1)

It is most intuitive why this should be the case when interpreting P + Q as ⋃_{q∈Q}(P + {q}). We then have a natural correspondence between sumsets and long multiplication, as is demonstrated in the example in Figure 5.

0 1 2 3 4 5 6 ⋯ ● ● {0, 2} + {1} ● ● {0, 2} + {2} ● ● {0, 2} + {4} ● ● ● ● ● {0, 2} + {1, 2, 4}

(a) Graphical representation of {0, 2} + {1, 2, 4}.

101

⊗_{2}  10110

000

⊕_{2}  101
⊕_{2}  101
⊕_{2} 000
⊕_{2} 101

1011110

(b) Binary lunar representation of {0, 2} + {1, 2, 4}.

Figure 5: Two representations of sumsets.

Theorem 18. The map β_{2} : F → B_{2} is a monoid-isomorphism, where F is equipped with the sumset operation and B_{2} is equipped with binary lunar multiplication.

Proof. Note that the fact that (F, +) is a commutative monoid follows from the fact that (ℕ, +) is a commutative monoid. The fact that (B_{2}, ⊗_{2}) is a commutative monoid follows from the fact that (D_{2}[X], ⊕_{2}, ⊗_{2}) is a commutative semiring. It is also easy to see (e.g., by considering the inverse map) that the map β_{2} is a bijection, and it remains to prove that it is a monoid-homomorphism.

We have β_{2}({0}) = 1|_{2}, so the neutral elements are mapped to each other. Next, let P, Q ∈ F. We need to prove Equation (1) holds. The result is clear when P = ∅ or Q = ∅. Assume therefore that P, Q ≠ ∅, and the corresponding binary numbers are β_{2}(P) = ∑_{i=0}^{max P} p_{i}2^{i} and β_{2}(Q) = ∑_{j=0}^{max Q} q_{j}2^{j}. By definition of lunar multiplication we have

β_{2}(P) ⊗_{2} β_{2}(Q) = ∑_{ℓ=0}^{max P +max Q} r_{ℓ}2^{ℓ},

where, for any 0 ≤ ℓ ≤ max P + max Q, we have

r_{ℓ} = (p_{0} ⊗_{2} q_{ℓ}) ⊕_{2} (p_{1} ⊗_{2} q_{ℓ−1}) ⊕_{2} ⋯ ⊕_{2} (p_{ℓ} ⊗_{2} q_{0})
= max{min{p_{i}, q_{j}} : i + j = ℓ}.

(As always, p_{i} = 0 for i > max P, and q_{j} = 0 for j > max Q). Let us now compare the ℓ-th digit of β_{2}(P) ⊗_{2} β_{2}(Q) and the ℓ-th digit of β_{2}(P + Q).

• According to the convolution product above, r_{ℓ} = 1 if and only if there exist i, j ∈ ℕ with i + j = ℓ, such that p_{i} = 1 and q_{j} = 1.

• By definition of the mapping β_{2}, the ℓ-th digit of β_{2}(P +Q) is 1 if and only if ℓ ∈ P +Q; that is, if and only if there exist i, j ∈ ℕ with i + j = ℓ, such that i ∈ P and j ∈ Q. Again, by the definition of the mapping β_{2}, this happens if and only if p_{i} = 1 and q_{j} = 1.

We see that by the definition of the map β_{2} these two conditions are in fact the same, so β_{2}(P + Q) = β_{2}(P) ⊗_{2} β_{2}(Q) as we wanted to show.

The least significant digit of an odd binary number must be 1, so the monoid-isomorphism β_{2} identifies odd binary numbers with 0-rooted sets. In this correspondence the length of the binary number corresponds to the maximal element of the 0-rooted set (with an offset of 1, since 0|_{2} is of length 1). Thus, Conjecture 16 becomes an immediate corollary of Theorem 13 above.

Corollary 19. In base 2, among all odd k-digit numbers n, d_{2}(n) has a unique maximum at n = 2^{k} − 1 = 111 ⋯ 11|_{2}.

4 Counting d([k])

In Section 5 we find the maximum of d(·) among all subsets of [k], not just the 0-rooted ones. One important part of the proof is the observation, already made by Applegate, LeBrun, and Sloane [1, Theorem 15], that d(11 ⋯ 10|_{2}) = 2d(11 ⋯ 1) with k occurrences of 1 on each side of the equality. Translated to the language of sumsets the equality reads d([k] \ {0}) = 2d([k − 1]). We then prove the inequality 2d([k − 1]) > d([k]). The purpose of the current section is to help us establish this inequality by highlighting the connection between the sequence d([k]) and Fibonacci numbers of higher-order.

Recall that a composition of a positive natural number n ∈ ℕ^{+} is an ordered tuple of positive natural numbers (c_{1}, c_{2}, …, c_{m}) such that n = ∑_{i=1}^{m} c_{i}. If the length of the tuple is m, the composition is called an m-composition. Each of the entries c_{i} in the composition is called a part of the composition. It is an easy exercise to show that the total number of compositions of n (of any length) is 2^{n−1}. Placing different restrictions on such compositions leads to a rich theory. For example, one may restrict the length of a composition, the size of the parts, the type of the parts, the arrangement of the parts, and so forth. In particular, integer partitions are integer compositions arranged in a non-decreasing order. Other types of restrictions have to do with the so-called “statistics” of the composition: If (c_{1}, c_{2}, …, c_{m}) is a composition of n, we say that a rise occurs in position i (for 1 ≤ i ≤ m − 1) if c_{i+1} > c_{i}, a fall in position i is defined analogously as c_{i+1} < c_{i}, and a level in position i occurs when c_{i+1} = c_{i}. In the context of compositions, statistics have to do with the number of such rises and falls. Another type of restriction one may place on compositions is to demand that certain patterns be avoided. MacMahon [11] was among the first mathematicians to study such questions in detail, and we also refer the reader to the recent book of Heubach and Mansour [8] for an excellent survey of the field.

LeBrun conjectured that d_{2}(11 ⋯ 11|_{2}), with n occurrences of 1, counts the number of compositions of n with the added restriction that the first part is greater or equal to all other parts. Figure 6 shows an example of such a correspondence. For ease of reference we shall use the appellation headstrong compositions to refer to compositions where the first part is greater or equal to all other parts. The number of headstrong compositions of n is sequence \underline{A079500} of the OEIS [16]. LeBrun’s conjecture was proved by Schroeppel [1, Theorem 16] and again by Frosini and Rinaldi [5]. For the sake of completion, we reproduce the proof below translated to the language of sumsets.

Theorem 20 (Schroeppel, 2001). For any n ∈ ℕ, the number d([n]) equals the number of headstrong compositions of n + 1.

Proof. Step 1 : Associate a divisor with each headstrong composition. Suppose (c_{1}, c_{2}, …, c_{m}) is a headstrong composition of n + 1. We define the following two sets:

A := {n + 1} − {c_{1}, (c_{1} + c_{2}), …, (c_{1} + c_{2} + ⋯ + c_{m})}
= {0, c_{m}, (c_{m} + c_{m−1}), …, (c_{m} + c_{m−1} + ⋯ + c_{2})};
B := [c_{1} − 1].

We claim that A + B = [n]. Indeed, it is clear that A + B ⊆ [n]. To prove the reverse inclusion, consider any 0 ≤ j ≤ n, and let i be the smallest index 1 ≤ i ≤ m such that (n+1)−(c_{1}+c_{2}+⋯+c_{i}) ≤ j. Note that such an index i always exists since c_{1}+⋯+c_{m} = n+1 by the definition of a composition. Let a denote (n − 1) − (c_{1} + ⋯ + c_{i}), and we clearly have a ∈ A. Let b denote j − a, and our task is now to prove that b ∈ B, for then we have j = a + b, and we are done. We distinguish between two cases:

• Suppose i = 1, so (n + 1) − c_{1} ≤ j < n + 1, and subtracting a from this inequality we find 0 ≤ b < c_{1}, so that b ∈ [c_{1} − 1] = B.

• Suppose i > 1, so that by the minimality of i we have

(n + 1) − (c_{1} + c_{2} + ⋯ + c_{i}) ≤ j < (n + 1) − (c_{1} + c_{2} + ⋯ + c_{i−1}),

and subtracting a from this inequality we fine 0 ≤ b < c_{i}. Since (c_{1}, c_{2}, …, c_{m}) is a headstrong composition we have c_{i} ≤ c_{1} so that 0 ≤ b < c_{1} and once again b ∈ [c_{1}−1] = B.

Step 2: Associate a headstrong composition with each divisor.

Suppose that A+B = [n] for some sets A, B, in which case we also have A+[max B] = [n]. Suppose A = {a_{0}, a_{1}, …, a_{ℓ}} with a_{0} < a_{1} < ⋯ < a_{ℓ}. We have the telescoping sum:

n + 1 = (max B + 1) + (a_{ℓ} − a_{ℓ−1}) + (a_{ℓ−1} − a_{ℓ−2}) + ⋯ + (a_{1} − a_{0}).

(Note that [n] is a 0-rooted set and so all of its divisors are also 0-rooted, which means a_{0} = 0.) Thus, we obtain a composition of n + 1, namely:

(max B + 1, a_{ℓ} − a_{ℓ−1}, a_{ℓ−1} − a_{ℓ−2}, …, a_{1} − a_{0}),

and we claim it is a headstrong composition. To prove this, fix some index 1 ≤ r ≤ ℓ and we need to show that max B + 1 ≥ a_{r} − a_{r−1}. We have n ≥ a_{r} > a_{0} = 0 and therefore a_{r} − 1 ∈ [n] = A + B, so we may choose some a ∈ A and b ∈ B such that a + b = a_{r} − 1. Since a < a_{r} and a ∈ A, we have a ≤ a_{r−1}. Therefore,

max B + 1 ≥ b + 1 = a_{r} − a ≥ a_{r} − a_{r−1},

as we wanted to prove.

Step 3: Bijection. Notice that the procedure from Step 1 and the procedure from Step 2 are inverses of each other. Therefore, we have a bijection between divisors of [n] and headstrong compositions of n + 1.

Headstrong compositions of 4  Divisors of [3]
(4)  ↝ {0};
(3, 1)  ↝ {0, 1};
(2, 2)  ↝ {0, 2};
(2, 1, 1)  ↝ {0, 1, 2};
(1, 1, 1, 1)  ↝ {0, 1, 2, 3}.

Figure 6: Example of the correspondence between the 5 divisors of [3] and the 5 headstrong compositions of 4.

As Applegate, LeBrun, and Sloane remarked [1, Remark (i) following Theorem 16], the bijection in the proof shows that the following corollary holds. It will be further used in Section 5 as it plays an important role in the proof of Conjecture 15.

Corollary 21. The number of divisors of [n] whose cardinality is exactly m equals the number of headstrong compositions of n + 1 with exactly m parts.

Headstrong compositions were first studied by Knopfmacher and Robbins [10] who derived generating functions and asymptotics for them. The (ordinary) generating function for the number of headstrong compositions of n, for a positive natural number n ≥ 1, is given by the coefficient of z^{n} in

∑_{ℓ=1}^{∞} \frac{(1 − z)z^{ℓ}}{1 − 2z + z^{ℓ+1}} .

(Here ℓ corresponds to the leading term of the composition.) By comparing generating functions it is easy to see that the number of headstrong compositions of n with leading term ℓ is given by F (ℓ, n), the n-th element of the generalized Fibonacci sequence F (ℓ, ·) defined by the recurrence relation

F (ℓ, n) = \begin{cases}0, & if 1 ≤ n < ℓ; \\ 1, & if n = ℓ; \\ ∑_{i=1}^{ℓ} F (ℓ, n − i), & if n > ℓ. \end{cases}

It is traditional to start enumerating the Fibonacci sequence at the index 0, i.e., F_{0} = 0, F_{1} = 1, and so forth. However, since 0 is not allowed to be a part of a composition, the generating function in the sum above starts at the index ℓ = 1, and to maintain a simple equality we shall also start our indexing of the generalized Fibonacci sequence at 1; so the Fibonacci sequence, for example, will start F_{1} = 0, F_{2} = 1, and so forth. Note that the Fibonacci sequence, \underline{A000045} in the OEIS [16], is exactly F (2, ·) according to the recurrence above. Similarly, F (3, ·) are the so-called “Tribonacci numbers”, \underline{A000073} in the OEIS [16]. Table 1 below displays the first few entries of the table for F (ℓ, n), reproduced from the entry for the generalized Fibonacci sequence, \underline{A092921} in the OEIS [16].

\begin{matrix}F (ℓ, n) & n = 1 & n = 2 & n = 3 & n = 4 & n = 5 & n = 6 & n = 7 & n = 8 & n = 9 & n = 10 \\ ℓ = 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ ℓ = 2 & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \\ ℓ = 3 & 0 & 0 & 1 & 1 & 2 & 4 & 7 & 13 & 24 & 44 \\ ℓ = 4 & 0 & 0 & 0 & 1 & 1 & 2 & 4 & 8 & 15 & 29 \\ ℓ = 5 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 4 & 8 & 16 \end{matrix}

Table 1: First entries of the table for the generalized Fibonacci sequence F (ℓ, n).

To obtain d([n]) = d_{2}(11 ⋯ 1|_{2}) (with n + 1 occurrences of 1), simply sum the (n + 1)-th column in Table 1. Note that this immediately implies that d([n + 1]) > d([n]) for any natural number n ∈ ℕ. One can also prove that the number of headstrong compositions of n with leading term ℓ is given by F (ℓ, n) without using generating functions by the following reasoning. Each headstrong composition of n with leading term ℓ can be obtained by appending 1 to the end of a headstrong composition of n − 1 with leading term ℓ; or by appending 2 to the end of a headstrong composition of n − 2 with leading term ℓ; so on until we append ℓ to the end of a headstrong composition of n−ℓ with leading term ℓ. We are not double-counting since the compositions differ in their last term. We can prove inductively that all headstrong compositions of n with leading term ℓ are obtained in this manner.

In summary, the total number of headstrong compositions of n is given by ∑_{ℓ=1}^{n} F (ℓ, n) = ∑_{ℓ≥1} F (ℓ, n). As mentioned in the beginning of this section, this characterization simplifies the proof that 2d([k − 1]) > d([k]), as a consequence of the following lemma.

Lemma 22. For n ≥ ℓ we have 2F (ℓ, n) ≥ F (ℓ, n+1), and the inequality is strict for n ≥ 2ℓ.

Proof. Since the claim holds trivially for ℓ = 1, we may assume that ℓ ≥ 2. Since F (ℓ, ℓ) = F (ℓ, ℓ+1) = 1, the claim is clearly true for n = ℓ. For n > ℓ we have by definition of F (ℓ, n):

F (ℓ, n + 1) = ∑_{i=1}^{ℓ} F (ℓ, n + 1 − i)

= F (ℓ, n) + ∑_{i=1}^{ℓ−1} F (ℓ, n − i)

= 2F (ℓ, n) − F (ℓ, n − ℓ) ≤ 2F (ℓ, n),

with strict inequality for n ≥ 2ℓ.

Lemma 22 gives a lower bound on F (ℓ, n) in terms of the next element of the sequence, F (ℓ, n + 1), and Lemma 23 gives an upper bound; these lemmas together show that

\frac{1}{2}F (ℓ, n + 1) ≤ F (ℓ, n) ≤ \frac{2}{3}F (ℓ, n + 1).  (2)

Inequality (2) will be used to show that [k] \ {0} is d(·)-maximal among all non-0-rooted subsets of [k]. These bounds are not asymptotically tight; the reader may recall that F (2, n)/F (2, n + 1) → 1/ϕ, where ϕ = (1 + \sqrt{5})/2 ≈ 1.618 is the golden ration. By considering the characteristic equation of the linear recurrence, Wolfram [19] found that F (ℓ, n)/F (ℓ, n + 1) → 1/r, where r is the single positive real root of x^{ℓ} − ∑_{i=0}^{ℓ−1} x^{i} = 0, though we shall not use this result.

Lemma 23. For any ℓ > 1 and n > ℓ we have 3F (ℓ, n) ≤ 2F (ℓ, n + 1). Equality holds if and only if ℓ = 2 and n = 4.

Proof. We have F (2, 3) = 1, F (2, 4) = 2, F (2, 5) = 3, which proves the claim for ℓ = 2 and n ≤ 4.

If ℓ = 2 and n > 4, then n − 1 ≥ 2ℓ so Lemma 22 shows that

2F (ℓ, n + 1) = 2F (ℓ, n) + 2F (ℓ, n − 1) > 3F (ℓ, n).

Assume therefore that ℓ ≥ 3. If n = ℓ + 1 we have

2F (ℓ, ℓ + 2) = 4 > 3 = 3F (ℓ, ℓ + 1).

On the other hand, if n ≥ ℓ + 2 we have by Lemma 22:

2F (ℓ, n + 1) ≥ 2F (ℓ, n) + 2F (ℓ, n − 1) + 2F (ℓ, n − 2)
≥ 3F (ℓ, n) + 2F (ℓ, ℓ)
> 3F (ℓ, n).

This completes the proof.

5 Divisors of non-0-rooted sets

Most of the groundwork for proving Theorem 30 is now done. The remaining key observation is the relationship between the divisors of a non-0-rooted set and the 0-rooted set obtained by shifting its elements. In the language of lunar arithmetic, this translates to the relationship of trailing zeros, and Applegate, LeBrun, and Sloane observed:

Lemma 24 ([1, Lemma 15]). If the base b expansion of n ends with exactly r ≥ 0 zeros, so that n = mb^{r}, with b |̸m, then

d_{b}(n) = (r + 1)d_{b}(m).  (3)

They give a short proof based on lunar arithmetic. For completeness, Lemma 26 proves the binary case in the language of sumsets.

Notation 25. We denote

[k+] := [k] \ {0} = {1, 2, …, k}.

For any positive natural number 1 ≤ k ∈ ℕ, we let Z_{k}^{+} denote the collection of sets of positive natural numbers whose maximal element is k:

Z_{k}^{+} := {A ⊆ ℕ : min A > 0, max A = k}.

Finally, we denote

Z_{≤k}^{+} := ⋃_{0<ℓ≤k} Z_{ℓ}^{+}.

Note that we have a partition of P([k]), the collection of subsets of [k], given by

P([k]) = {∅} ⊔ Z_{≤k} ⊔ Z_{≤k}^{+}.

(We use “⊔” to denote disjoint union.)

Lemma 26 (Based on [1, Lemma 15]). Let A be a finite subset of ℕ, and let r := min A. Then,

d(A) = (r + 1)d(A − {r}).

Proof. Note that A − {r} ∈ Z is a 0-rooted set. Suppose B, C are sets such that B + C = A − {r}. Then, for any 0 ≤ s ≤ r, we have that B + {s} is a divisor of A, since

(B + {s}) + (C + {r − s}) = (B + C) + {r} = (A − {r}) + {r} = A.

Now, suppose B and B′ are divisors of A−{r}, and s, s′ are numbers such that 0 ≤ s, s′ ≤ r. We claim that B + {s} = B′ + {s′} if and only if B = B′ and s = s′. To see this, assume without loss of generality that s ≤ s′. Then we can rewrite B + {s} = B′ + {s′} as B = B′ + {s′ − s}. However, both B and B′ are 0-rooted, so we must have s′ − s = {0}, which then implies B = B′.

We have found that each divisor of A − {r} gives rise to r + 1 divisors of A, and they are all distinct, so that d(A) ≥ (r + 1)d(A − {r}).

Conversely, suppose that B, C are sets such that B + C = A. Let b, c denote the minimal elements of B, C respectively, so that b + c = min A = r. We therefore have

(B − {b}) + (C − {c}) = (B + C) − {r} = A − {r}.

That is, the map F ↦ F − min F maps divisors of A to divisors of A − {r}. Since 0 ≤ min F ≤ r (and F ≠ F′ implies F − {s} ≠ F′ − {s} for any 0 ≤ s ≤ r), each divisor of A − {r} is the image of at most (r + 1) divisors of A. That is, d(A) ≤ (r + 1)d(A − {r}).

A particular case of Lemma 26 is the equality d([k+]) = 2d([k − 1]), mentioned in the beginning of Section 4. The following theorem implies that [k+] has more divisors than any set in Z_{≤k}.

Theorem 27. For any positive natural number k ≥ 1 we have

2d([k − 1]) ≥ d([k]),

and the inequality is strict for k > 1.

Proof. Note that d([0]) = 1 and d([1]) = 2, which proves the claim for k = 1. Assume therefore that k ≥ 2. We have seen in Section 4 that

d([k − 1]) = ∑_{ℓ=1}^{k} F (ℓ, k).

By Lemma 22 we have 2F (ℓ, k) ≥ F (ℓ, k + 1) so that

2d([k − 1]) − d([k]) = ∑_{ℓ=1}^{k}(2F (ℓ, k) − F (ℓ, k + 1)) − F (k + 1, k + 1).

Now, F (1, ·) is the constant 1 sequence, so 2F (1, k) − F (1, k + 1) = 1. Moreover, F (k + 1, k + 1) = 1 by definition. Thus,

2d([k − 1]) − d([k]) = ∑_{ℓ=2}^{k}(2F (ℓ, k) − F (ℓ, k + 1)).

Since k ≥ 2 the sum is nonempty, and Lemma 22 shows that each term in the sum is nonnegative. In fact, the sum includes the term 2F (k, k) − F (k, k + 1) = 2 − 1, so it is positive.

To show that [k+] is the maximum of d(·) in Z_{≤k}^{+}, we use Lemma 23.

Theorem 28. For any 1 ≤ r ≤ k we have

2d([k − 1]) ≥ (r + 1)d([k − r]).

Equality holds if and only if r = 1, or k = 3 and r = 2.

Proof. Since d([0]), d([1]), d([2]) = 1, 2, 3 respectively, it is easy to verify that the claim holds for k ≤ 3. In particular, for k = 3 and r = 2 we have

3d([1]) = 3 · 2 = 2 · 3 = 2d([2]).

Suppose therefore that k ≥ 4. The claim holds trivially with equality for r = 1. We shall prove strict inequality holds for r ≥ 2 by induction on r. To prove the base case r = 2, recall that F (1, ·) = F (k, k) = F (k, k + 1) = 1 (for any positive k). We have by Lemma 23:

3d([k − 2]) = 3 ∑_{ℓ=1}^{k−1} F (ℓ, k − 1)

= 3 + 3 + ∑_{ℓ=2}^{k−2} 3F (ℓ, k − 1)

< 2(F (1, k) + F (k − 1, k) + F (k, k)) + ∑_{ℓ=2}^{k−2} 2F (ℓ, k)

= 2 ∑_{ℓ=1}^{k} F (ℓ, k)

= 2d([k − 1]).

(Note that the strict inequality is justified by Lemma 23, since the sum contains at least one element different from F (2, 4).)

For the induction step, suppose that for some r ≥ 2 we know that for all k ≥ max(4, r) we have (r + 1)d([k − r]) < 2d([k − 1]). Note that 3d([k − 2]) ≤ 2d([k − 1]) for any k ≥ 2 (it is only when we require the inequality to be strict that we need k ≥ 4). Thus, if r + 1 ≤ k, we have

(r + 2)d([k − r − 1]) = (r − 1)d([k − r − 1]) + 3d([k − r − 1])
≤ (r − 1)d([k − r]) + 2d([k − r])
= (r + 1)d([k − r])
< 2d([k − 1]).

This completes the induction step.

Theorem 29. For any nonempty set A ⊊ [k+] we have

d([k+]) ≥ d(A),

and the inequality is strict for k ≠ 3.

Proof. Let a := min A, and note that A ⊊ [k+] implies a ≥ 1. By Lemma 26 and Theorem 13 we have

d(A) = (a + 1)d(A − {a}) ≤ (a + 1)d([max A − {a}])

and the inequality is strict if A − {a} ≠ [max A − a]. Moreover, d([max A − a]) ≤ d([k − a]) and the inequality is strict if max A ≠ k. Therefore, by Theorem 28 we have

d(A) ≤ (a + 1)d([k − a]) ≤ 2d([k − 1]) = d([k+]),

and the inequality is strict if k ≠ 3 and a > 1.

In summary, d(A) ≤ d([k+]) and if k ≠ 3 equality may only hold if a = 1, and max A = k, and A−{1} = [k−1]; but this contradicts the assumption that A ⊊ [k+]. This contradiction proves that the inequality is strict for k ≠ 3.

It is also true that for k = 3 the inequality can fail to be strict. For example, d([3+]) = 6 = d({2, 3}). We may now prove Conjecture 15.

Theorem 30. For any natural number k ≥ 1, the set [k+] is the maximum of d(·) in P([k]) \ {∅}, and it is the unique maximum for k ≠ 1, 3.

Equivalently, in base 2, among all k-digit numbers n, the maximal value of d_{2}(n) occurs at n = 2^{k} − 2 = 111 ⋯ 10|_{2}, and it is the unique maximum for n ≠ 2, 4.

Proof. By Lemma 26 we have d([k+]) = 2d([k−1]), and by Theorem 27 we have 2d([k−1]) ≥ d([k]) with strict inequality for k > 1. By Theorem 13 we know that [k] is the unique maximum of d(·) in Z_{≤k}, so we conclude that d([k+]) ≥ d(A) for any A ∈ Z_{≤k}, and the inequality is strict for k > 1.

Next, Theorem 29 shows that for any A ∈ Z_{≤k}^{+} we have d([k+]) ≥ d(A), and the inequality is strict if k ≠ 3 (and A ≠ [k+]).

Since P([k]) = {∅} ⊔ Z_{≤k} ⊔ Z_{≤k}^{+}, we conclude that [k+] is the maximum of d(·) in P([k]) \ {∅}, and it is the unique maximum for k ≠ 1, 3.

6 The triangle of headstrong compositions

In Section 7 we prove Conjecture 14. One important part of the proof is the observation that d_{b} can be given in terms of powers of base 2 divisors; see Theorem 43. Theorem 43 generalizes a result from Applegate, LeBrun, and Sloane [1, Theorem 17], whose proof compares headstrong compositions by the number of parts, rather than simply count the total number. The purpose of this section is to help us establish a new, more convenient recurrence relation for these numbers, and use it to derive some bounds.

Since 0 is not allowed as a part of a composition, a composition of a positive natural number n may have at most n parts. Letting the rows indicate n, and the columns the number of parts, we obtain a triangle of compositions. In the case of unrestricted compositions it is easy to see that the triangle thus obtained is the Pascal triangle of binomial coefficients, sequence \underline{A007318} of the OEIS [16]. We are interested in the triangle of headstrong compositions, enumerated in sequence \underline{A184957} of the OEIS [16]. The first few rows of the triangle are reproduced in Table 2. We let H(n, p) denote the number of headstrong p-compositions of the integer n. Recall from Section 4 that F (·, n) enumerates headstrong compositions by leading term, so summing the rows of table 2 leads to the same result as summing the columns of table 1. Thus, we have the equality ∑_{p=1}^{n} H(n, p) = ∑_{ℓ=1}^{n} F (ℓ, n), even though the rows and columns of these two tables do not in general agree.

H(n, p) p = 1 p = 2 p = 3 p = 4 p = 5 p = 6 p = 7 p = 8 p = 9 p = 10
n = 1  1
n = 2  1  1
n = 3  1  1  1
n = 4  1  2  1  1
n = 5  1  2  3  1  1
n = 6  1  3  4  4  1  1
n = 7  1  3  6  7  5  1  1
n = 8  1  4  8  11  11  6  1  1
n = 9  1  4  11  17  19  16  7  1  1
n = 10  1  5  13  26  32  31  22  8  1  1

Table 2: Triangle of H(n, p), the number of headstrong p-compositions of n.

We are after the following recurrence relation:

Theorem 31. Let p, n be positive natural numbers, and let H(n, p) denote the number of headstrong p-compositions of the integer n, as above. We have

H(n, p) = \begin{cases}0, & if p > n; \\ 1, & if p = n; \\ 1, & if p = 1. \end{cases}

In all other cases, i.e., n > p > 1, we have

H(n, p) = ∑_{j=1}^{n−p} H(n − p, j)\binom{p − 1}{j − 1}.  (4)

Before proving Theorem 31, let us explain its meaning in terms of the triangle of headstrong compositions, Table 2. It is well-known how to generate a given row in Pascal’s triangle by use of the previous row. Similarly, but more complicated, one can generate a given diagonal of the triangle of headstrong compositions by use of the row above it. To introduce this procedure we first recall that given a function f : ℕ → ℝ, its first forward difference, denoted Δf, is another function Δf : ℕ → ℝ defined by

Δf(n) := f(n + 1) − f(n).

One then defines the k-th order first forward difference recursively by

Δ^{k}f := Δ(Δ^{k−1}f).

We can conveniently extend this notation by adopting the convention that Δ^{0}f = f. Starting with the sequence given by the function f, and writing the sequence represented by Δ^{k}f in row k we obtain the difference table for the sequence f. It is conventional to align the table in a similar manner to Pascal’s triangle, so that the difference of two items appears in between them; thereby a difference triangle is obtained (of course, it is only by curtailing the sequence that the shape of a triangle emerges). An example with f(n) = ∑_{j=0}^{n} j^{2} the sequence of the sum of the first n squares is shown in Table 3.

Δ^{0}f 0  1  5  14  30  55
Δ^{1}f  1  4  9  16  25
Δ^{2}f  3  5  7  9
Δ^{3}f  2  2  2
Δ^{4}f  0  0

Table 3: Difference table for the sum of squares f(n) = ∑_{j=0}^{n} j^{2}.

There are many analogies between forward differences and differentiation. The h-th forward difference plays an important role in the analysis of difference equations, numerical methods for solving differential equations, and in statistics. We refer the interested reader to Graham, Knuth, and Patashnik’s book [6] for an introduction, and to Jordan’s classic book [9] for an extensive treatment of the so-called “finite calculus”. One easy analogy we shall exploit is the fact that f(n) is a polynomial of degree m if and only if Δ^{m+1}f = 0. In which case, the entire difference table can be recovered from its first diagonal. The first diagonal of the difference table consists of the first entry in each row; in Table 3 the first diagonal is (0, 1, 3, 2, 0). In general, if the first diagonal is (a_{0}, a_{1}, …, a_{m}, 0) the sequence is given by

f(n) = ∑_{j=0}^{m} a_{j}\binom{n}{j}.  (5)

(Here we adopt the convention that \binom{n}{j} = 0 for j > n.) This formula, as well as the fact that Δ^{m+1}f = 0 if and only if f(n) is a polynomial of degree m, can easily be proven by induction on the degree m. As an example, applying this formula to the first diagonal (0, 1, 3, 2, 0) of Table 3 we obtain the familiar formula for the sum of the first n squares:

f(n) = 0\binom{n}{0} + 1\binom{n}{1} + 3\binom{n}{2} + 2\binom{n}{3} = \frac{1}{6}n(n + 1)(2n + 1).

Below we shall apply these ideas to the triangle of headstrong compositions. Because of the enumeration we adopted in Section 4, we shall be working with sequences whose first element has the index 1, rather than the index 0. That is, the sequence will be represented by a function f : ℕ \ {0} → ℝ, and Equation (5) will therefore take the form

f(n) = ∑_{j=0}^{m} a_{j}\binom{n − 1}{j}.  (6)

We are now in a position to explain the recurrence from Theorem 31. First, by the definition of H(n, p) as the number of headstrong p-compositions of n, it is clear that H(n, 1) = 1 and H(n, n) = 1 for any positive natural number n. It is also clear that H(n, p) = 0 for any p > n. We take these facts as our initial data, and we obtain the first column and the first diagonal of Table 2, the triangle of headstrong p-compositions of n, as shown in Table 4a.

The (r + 1)-st diagonal of the triangle of headstrong p-compositions of n is given by the entries

H(r + 1, 1), H(r + 2, 2), H(r + 3, 3), …

The corresponding sequence is given by the function f(m) = H(r + m, m) for m ≥ 1. The recurrence formula in Theorem 31 can be interpreted as follows: if we construct the difference table for the sequence f(m), the first diagonal of the difference table is the r-th row of the triangle of headstrong p-compositions of n.

Thus, starting with the initial data as in Table 4a, we can recover the second diagonal from Equation (6). That is, entry s in the sequence corresponding to the second diagonal will be given by the formula 1 · \binom{s−1}{0}, so the second diagonal is the constant sequence 1, as shown in Table 4b.

We now know the second row of the triangle H(n, p), which means we can recover the third diagonal. Entry s in the sequence corresponding to the third diagonal will be given by the formula

1 · \binom{s − 1}{0} + 1 · \binom{s − 1}{1} = s,

as shown in Table 4c.

We now know the third row of the triangle H(n, p), which means we can recover the fourth diagonal. Entry s in the sequence corresponding to the fourth diagonal will be given by the formula

1 · \binom{s − 1}{0} + 1 · \binom{s − 1}{1} + 1 · \binom{s − 1}{2} = \frac{s^{2} − s + 2}{2},

as shown in Table 4d.

In this manner one may recover the whole triangle H(n, p) in Table 2 from the initial data, and this is the claim in Theorem 31.

1

1  1
1 H(3, 2)  1
1 H(4, 2) H(4, 3)  1
1 H(5, 2) H(5, 3) H(5, 4)  1
1 H(6, 2) H(6, 3) H(6, 4) H(6, 5) 1

(a) Initial data.

1  1
1  1  1
1 H(4, 2)  1  1
1 H(5, 2) H(5, 3)  1  1
1 H(6, 2) H(6, 3) H(6, 4) 1 1

(b) Filled 2nd diagonal.

1

1  1
1  1  1
1  2  1  1
1 H(5, 2)  3  1 1
1 H(6, 2) H(6, 3) 4 1 1

(c) Filled 3rd diagonal.

1

1 1
1 1 1
1 2 1 1
1 2 3 1 1
1 3 4 4 1 1

(d) Filled table.

Table 4: Recovering the triangle H(n, p) of headstrong p-compositions of n from its initial data.

In order to prove Theorem 31 we shall use generating functions. For that purpose we introduce the sequence C(n, p, s), the number of p-compositions of n such that no part exceeds s. The appearance of Pascal’s triangle already signifies the importance of compositions in probability. The sequence C(n, p, s) is another example, it arises in the solution of the following Montmort-Moivre^{2} type problem: consider p urns, each containing s balls labeled 1, …, s. If one ball is drawn uniformly at random from each of the p urns, what is the probability that the sum of the labels is n? The process of answering the Montmort-Moivre puzzle leads to a definition of C(n, p, s), which has been studied by statisticians in this context. The sequence already appears in Jordan’s book [9], and is expanded upon in an article by Charalambides [2]; we also refer the reader to the more recent work of Rao and Agarwal [15] which considered generalizations where each part is bounded above and below. Below we shall use the generating function of C(n, p, s), given by

g(z) = (z + z^{2} + ⋯ + z^{s})(z + z^{2} + ⋯ + z^{s}) ⋯ (z + z^{2} + ⋯ + z^{s})

= z^{p} \frac{(1 − z^{s})^{p}}{(1 − z)^{p}} .

Proof of Theorem 31. As we have already remarked, it follows directly from the definition of H(n, p) as the number of headstrong p-compositions of n, that H(n, 1) = 1, that H(n, n) = 1, and that H(n, p) = 0 for any p > n. It remains to prove Equation (4) for n > p > 1.

2A similar formulation with a deck of cards is sometimes referred to as Simon Newcomb type problem, popularized in [11].

It is easy to see that for p > 1 we have

H(n, p) = ∑_{s=1}^{n−1} C(n − s, p − 1, s).

(The idea is that given an (p−1)-composition of n−s, no part of which exceeds s, prepending s turns it into a headstrong p-composition of n. The converse, chopping off the head of a headstrong composition, shows that this is a bijection.) The generating function for C(n, p, s) therefore gives us a generating function for H(n, p):

f(z) = ∑_{s=1} z^{s}z^{p−1} \frac{(1 − z^{s})^{p−1}}{(1 − z)^{p−1}} = ∑_{s=1} z^{p+s−1} (\frac{1 − z^{s}}{1 − z} )^{p−1} .

Observe that this generating function gives the correct result for p = 1 as well, so it is indeed the generating function for H(n, p). On the other hand, the hypothesized recurrence for n > p > 1,

H(n, p) = ∑_{j=1} H(n − p, j)\binom{p − 1}{j − 1}

= 1 + ∑_{j=2} H(n − p, j)\binom{p − 1}{j − 1}

= 1 + ∑_{j=2} (\binom{p − 1}{j − 1} ∑_{s=1} C(n − p − s, j − 1, s)) ,

gives the generating function

h(z) = z^{p} + ∑_{s=1} z^{p+s} + ∑_{j=2} (\binom{p − 1}{j − 1} ∑_{s=1} z^{p+s}z^{j−1} \frac{(1 − z^{s})^{j−1}}{(1 − z)^{j−1}} ) .

(Note that the coefficient of z^{p} accounts for the case n = p, while ∑_{s=1} z^{p+s} accounts for the cases where n > p and p = 1.) However, this is the same as the generating function for H(n, p), since

h(z) = z^{p} + ∑_{s=1} z^{p+s} ∑_{j=1} \binom{p − 1}{j − 1} (z \frac{1 − z^{s}}{1 − z} )^{j−1}

= z^{p} + ∑_{s=1} z^{p+s} (1 + z \frac{1 − z^{s}}{1 − z} )^{p−1}

= ∑_{s=1} z^{p+s−1} (\frac{1 − z^{s}}{1 − z} )^{p−1} .

That is, h(z) = f(z), and the proof is complete.

Using Theorem 31 we may now prove a relation between the rows of the triangle of headstrong compositions that will play a key role in our proof of Conjecture 14.

Corollary 32. Let b ≥ 2 be a natural number. Then, for any positive natural number n,

∑_{p=1}^{n+1} H(n + 1, p)b^{p} > 2 ∑_{p=1}^{n} H(n, p)b^{p}.  (7)

Proof. When n = 1, the claim reduces to 2b < b + b^{2}, and when n = 2 it reduces to 2b+2b^{2} < b+b^{2} +b^{3}. Assume therefore that n > 2. For n > p > 0 we have n+1 > p+1 > 1, and applying Theorem 31:

H(n + 1, p + 1) = ∑_{j=1} H(n − p, j)\binom{p}{j − 1}

= ∑_{j=1} H(n − p, j)\binom{p − 1}{j − 1} + ∑_{j=2} H(n − p, j)\binom{p − 1}{j − 2}

= H(n, p) + ∑_{j=2} H(n − p, j)\binom{p − 1}{j − 2}.

The last step is justified, since the recurrence formula in Equation (4) is valid in all cases where n > p > 0, including the case p = 1 with the conventions \binom{0}{0} = 1 and \binom{p}{j} = 0 for j < 0. Note that the last summand is 0 unless n − ℓ > 1, reflecting the fact that H(n + 1, n) = H(n, n − 1) = 1; i.e., plug p = n − 1 into Inequality (7) above.

For convenience, let h(n, p) denote the second summand:

h(n, p) := ∑_{j=2} H(n − p, j)\binom{p − 1}{j − 2}.

We find that

∑_{p=1}^{n+1} H(n + 1, p)b^{p} = b + ∑_{p=1}^{n} H(n + 1, p + 1)b^{p+1}

= b + ∑_{p=1}^{n}(H(n, p) + h(n, p))b^{p+1}

= b + b ∑_{p=1}^{n} H(n, p)b^{p} + b ∑_{p=1}^{n} h(n, p)b^{p}.

By assumption, b ≥ 2, and since all summands are nonnegative we have

∑_{p=1}^{n+1} H(n + 1, p)b^{p} = b + b ∑_{p=1}^{n} H(n, p)b^{p} + b ∑_{p=1}^{n} h(n, p)b^{p}

≥ b + b ∑_{p=1}^{n} H(n, p)b^{p}

≥ b + 2 ∑_{p=1}^{n} H(n, p)b^{p}

> 2 ∑_{p=1}^{n} H(n, p)b^{p}.

This is exactly the inequality we wanted to prove.

7 Sumsets arrays

We have seen that sumset addition corresponds to binary lunar multiplication, and this correspondence can be used to analyze lunar divisors. Lunar arithmetic is defined for arbitrary bases b ≥ 2. We now extend the correspondence by showing that lunar multiplication in higher bases corresponds to multiset addition. Recall that a multiset is a “set with repetitions.” While {1, 1, 2} and {1, 2}, for example, represent the same set, they represent two different multisets. A set of natural numbers can be identified with a function f : ℕ → {0, 1} that decides set-membership, i.e., n is an element of the set if and only if f(n) = 1.

Definition 33. A multiset of natural numbers is a function f : ℕ → ℕ. We say that a natural number n ∈ ℕ is an element of the multiset, if f(n) > 0. We call the value f(n) the multiplicity of n. A multiset that is not a set, i.e., f(n) > 1 for at least one n ∈ ℕ, is called a proper multiset.

All multisets in this section will be finite multisets of natural numbers. There is a grading of multisets by multiplicity.

Notation 34. For any natural number b, we let M^{b} denote the collection of finite multisets (of natural numbers) with the property that no element of the multiset has multiplicity greater than b. Formally,

M^{b} := {f : ℕ → ℕ : f(ℕ) ⊆ [b], and f(j) = 0 for all but finitely many j ∈ ℕ}.

Note that M^{1} is simply the collection of finite subsets of natural numbers, while M^{0} = {∅}. We have the grading

M^{0} ⊊ M^{1} ⊊ M^{2} ⊊ · · · .

We adopt the following notation, analogous to the notation from Section 3. For any natural number k, let M_{k} denote the collection of multisets of natural numbers whose maximal element is k:

M_{k} := {f : ℕ → ℕ : f(k) > 0 and f(j) = 0 for any j > k}.

For convenience we also introduce

M_{≤k} := ⋃_{ℓ≤k} M_{ℓ},

the collection of multisets of natural number whose maximal element does not exceed k. The collection of all finite nonempty multisets of natural numbers is then denoted by M:

M := ⋃_{k∈ℕ} M_{k}.

Finally, we may combine superscripts and subscripts, so that M_{k}^{b} is the collection of multisets of natural numbers whose maximal element is k and such that the multiplicity of any element does not exceed b:

M_{k}^{b} := M_{k} ∩ M^{b}.

Such a multiset M ∈ M_{k}^{b} can be viewed as extending a function f : [k] → [b] to a multiset f : ℕ → ℕ by the rule that f(j) = 0 for any j > k. Note that we have the disjoint union:

M^{b} \ {∅} = ⨆_{k∈ℕ} M_{k}^{b}.

We are now faced with the question of how to define an addition operation for multisets. One approach is to simply treat multisets as sets, for example {1, 1, 2} + {2} = {3, 3, 4}, and also {1, 1, 2} + {2, 2} = {3, 3, 4}. Such a definition ignores multiplicity, and thus fails to take advantage of the extra structure of multisets. In contrast, Definition 36 below takes multiplicity into account, and allows different interactions between “multiplicity levels”, so that {1, 1, 2} + {2} = {3, 4}, while {1, 1, 2} + {2, 2} = {3, 3, 4}. Definition 36 is most transparent when one views finite multisets as an array of sets, as in the following definition.

Definition 35. Let b be a natural number, and f ∈ M^{b} a multiset. The b-ary array representation of f is an ordered b-tuple of (F_{1}, F_{2}, …, F_{b}) where the coordinate F_{i} (for 1 ≤ i ≤ b) is defined as follows: for any natural number n, we have n ∈ F_{i} if and only if f(n) ≥ i.

For ease of readability, it is often convenient to represent the array (F_{1}, F_{2}, …, F_{b}) as a column vector, and we shall do so in the figures below. The array representation depends on b as well as on the multiset f. For example, {1, 1, 2} has an array representation ({1, 2}, {1}) when viewed as a multiset in M^{2}, but it has the array representation ({1, 2}, {1}, ∅) when viewed as a multiset in M^{3}. Note that one feature of the array representation is that the coordinates form a descending chain F_{1} ⊇ F_{2} ⊇ ⋯ ⊇ F_{b}. We are now ready to define multisumsets, it is simply the coordinate-wise sumset operation.

Definition 36. Let f, g ∈ M be two finite multisets of natural numbers. Let b be the largest multiplicity of any element in f or in g; that is, b is the smallest natural number such that f, g ∈ M^{b}. Let F = (F_{1}, F_{2}, …, F_{b}) and G = (G_{1}, G_{2}, …, G_{b}) be the b-ary array representations for f and g, respectively.

The multisumset of f and g, denoted f + g, is the multiset corresponding to the array F + G := (F_{1} + G_{1}, F_{2} + G_{2}, …, F_{b} + G_{b}).

Figure 7 gives an example of the multisumset operation, showing how it takes advantage of different “multiplicity levels”.

(\begin{matrix}\{1, 2\} \\ \{1\} \end{matrix}) + (\begin{matrix}\{2\} \\ ∅ \end{matrix}) = (\begin{matrix}\{3, 4\} \\ ∅ \end{matrix})

(a) The multisumset {1, 1, 2} + {2} = {3, 4}.

(\begin{matrix}\{1, 2\} \\ \{1\} \end{matrix}) + (\begin{matrix}\{2\} \\ \{2\} \end{matrix}) = (\begin{matrix}\{3, 4\} \\ \{3\} \end{matrix})

(b) The multisumset {1, 1, 2} + {2, 2} = {3, 3, 4}.

Figure 7: Examples of the multisumset operation via the array representation of multisets, here displayed as column vectors.

It is easy to see that the multisumset operation makes M^{b} into a commutative monoid. We have a correspondence between the multisumset operation on M^{b} and base (b + 1) lunar multiplication, extending Theorem 18. Extending the notation of Theorem 18, we let B_{b+1} denote the set of base (b+1) numbers, written using the digits in D_{b+1} = {0, 1, …, b}. There is a natural bijection β_{b+1} : M^{b} → B_{b+1} based on the idea of encoding multiplicity as a base (b + 1) sequence. First, define β_{b+1}(∅) = 0|_{b+1}. Next, let f ∈ M^{b} be a finite nonempty multiset, and let k be its maximal element, so f ∈ M_{k}^{b}. We define the base (b + 1) number β_{b+1}(f) by encoding the multiplicity of each element

β_{b+1}(f) := f(k)f(k − 1) ⋯ f(1)f(0)|_{b+1}.

For example, the multiset {1, 1, 2} will be encoded as the base 3 number 120|_{3}. Another example, the multiset corresponding to 169|_{10} is {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2}.

Let f, g ∈ M, and let b be the smallest natural number such that f, g ∈ M^{b}. The key observation, which we prove in Theorem 37, is a generalization of Equation (1):

β_{b+1}(f + g) = β_{b+1}(f) ⊗_{b+1} β_{b+1}(g).  (8)

Figure 8 shows an example of a multisumset in M^{9} and the corresponding base 10 lunar multiplication, demonstrating Equation (8).

Theorem 37. For any positive natural number b, the map β_{b+1} : M^{b} → B_{b+1} is a monoidisomorphism between M^{b} equipped with the multisumset operation, and base (b + 1) numbers equipped with lunar multiplication ⊗_{b+1}.

Proof. Fix some positive natural number b. It is easy to see that the map β_{b+1} is a bijection—for example, by considering the inverse map—so it remains to show it is a monoidhomomorphism. Let 0 denote the multiset {0, 0, …, 0} with b repetitions of 0. We have β_{b+1}(0) = b|_{b+1}, which is the maximal digit in D_{b+1}. This shows that the neutral elements are mapped to each other.

Next, let f, g ∈ M^{b}, and we need to prove that Equation (8) holds. This is easy to see if one of f, g is the empty multiset. Assume therefore that each of f, g has at least one element. Let r, s denote the maximal elements of f, g, respectively. Consider the base (b + 1) lunar product β_{b+1}(f) ⊗_{b+1} β_{b+1}(g) = t:

f(r) ⋯ f(0)|_{b+1} ⊗_{b+1} g(s) ⋯ g(0)|_{b+1} = t_{r+s} ⋯ t_{0}|_{b+1}.

Let F = (F_{1}, …, F_{b}) be the set array representation of f, and let G = (G_{1}, …, G_{b}) be the set array representation of g. The base (b + 1) number corresponding to the multisumset F + G is the (r + s)-digit number β_{b+1}(f + g). By definition of the mapping β_{b+1}, for any 0 ≤ j ≤ r + s, the j-th digit of β_{b+1}(f + g) is the multiplicity of j in the multisumset f + g. By definition of the multisumset operation, the multiplicity of j in the multisumset f + g equals the number of indices i (for 1 ≤ i ≤ b) such that F_{i} + G_{i} contains j. Consider all possible representations of j as the sum of two natural numbers:

0 + j, 1 + (j − 1), 2 + (j − 2), …, j + 0.

When constructing the set F_{1} + G_{1}, the specific sum ℓ + (j − ℓ) (for 0 ≤ ℓ ≤ j), in this specific order, appears as part of the construction if and only if f(ℓ) ≥ 1 and g(j − ℓ) ≥ 1. The specific sum ℓ + (j − ℓ) appears in the construction of F_{2} + B_{2} if and only if f(ℓ) ≥ 2 and g(j − ℓ) ≥ 2. In general, the specific sum ℓ + (j − ℓ) will appear in the construction of F_{i} + G_{i} for exactly min{f(ℓ), g(j − ℓ)}-many indices. The number of indices i such that F_{i} + G_{i} contains j is therefore

max{min{f(0), g(j)}, min{f(1), g(j − 1)}, …, min{f(j), g(0)}}.

However, by the definition of the lunar arithmetic operations, this is exactly

t_{j} = (f(0) ⊗_{b+1} g(j)) ⊕_{b+1} (f(1) ⊗_{b+1} g(j − 1)) ⊕_{b+1} ⋯ ⊕_{b+1} (f(j) ⊗_{b+1} g(0)).

This proves that β_{b+1}(f + g) = β_{b+1}(f) ⊗_{b+1} β_{b+1}(g), as we wanted to show.

(\begin{matrix}\{0, 1, 2\} \\ \{0, 1\} \\ \{0, 1\} \\ \{0, 1\} \\ \{0, 1\} \\ \{0, 1\} \\ \{0\} \\ \{0\} \\ \{0\} \end{matrix})+(\begin{matrix}\{0, 1, 2\} \\ \{0, 1, 2\} \\ \{0, 1\} \\ \{0, 1\} \\ \{0\} \\ \{0\} \\ \{0\} \\ \{0\} \\ ∅ \end{matrix}) = (\begin{matrix}\{0, 1, 2, 3, 4\} \\ \{0, 1, 2, 3\} \\ \{0, 1, 2\} \\ \{0, 1, 2\} \\ \{0, 1\} \\ \{0, 1\} \\ \{0\} \\ \{0\} \\ ∅ \end{matrix})

(a) Multiset addition in M^{9}.

⊗_{10}  248

168

⊕_{10} 144
⊕_{10} 122

12468

(b) Base 10 lunar multiplication.

Figure 8: Two representations of multiset addition.

Having defined multisumset we can define divisors in a way analogous to Definition 4.

Definition 38. Let f ∈ M be a finite multiset of natural numbers. We say that the multiset g ∈ M is a divisor (or multisumset divisor, or factor) of f, if there exists some multiset h ∈ M such that f = g + h. We then call g + h a factorization of f.

Multiplicity may be lost in the process of multiset addition. For example {1, 1, 2} + {2, 2} = {3, 3, 4} and also {1, 1, 2} + {2, 2, 2} = {3, 3, 4}; in fact, {1, 1, 2} + {2, 2, …, 2} = {3, 3, 4} as long as the second set has at least two 2’s. Thus, it only make sense to count the number of divisors up to a given multiplicity level, i.e., when we restrict ourselves to M^{b}.

Definition 39. Let f ∈ M be a finite multiset of natural numbers, and let b be a positive natural number. We say that the multiset g ∈ M is a b-divisor of f, if g ∈ M^{b} and there exists some multiset h ∈ M such that f = g + h.

If f ≠ 0 is not the constant 0 function, we let d_{b}(f) denote the number of b-divisors of f.

The constant 0-function corresponds to the empty-set, which has any multiset as a divisor and so must be excluded from the definition above. Observe that if f ∉ M^{b} then d_{b}(f) = 0, since one cannot gain multiplicity. If f is a set rather than a proper multiset, so that f ∈ M^{1}, then d_{1}(f) = d(f) in agreement with Definition 4. Note that the notation d_{b}(·) has now been overloaded; it denotes the number of lunar divisors for a base b lunar number, and the number of b-divisors for a multiset. If f ∈ M^{b} is nonempty, Theorem 37 implies that

d_{b}(f) = d_{b+1}(β_{b+1}(f)).

Since any set is a divisor for ∅, an array with more empty entries will have more divisors, as is shown in the next lemma.

Lemma 40. Let b be a positive natural number, f ∈ M^{b} a multiset, and F = (F_{1}, F_{2}, …, F_{b}) its b-ary array representation. Suppose f ≠ 0 is not the constant zero function, so that F_{1} ≠ ∅.

Let f^{∗} ∈ M^{b} be the multiset given by the b-ary array representation F^{∗} = (F_{1}, ∅, …, ∅). Then d_{b}(f^{∗}) ≥ d_{b}(f), and the inequality is strict if F_{2} ≠ ∅.

Proof. Let g ∈ M^{b} be a b-divisor of f, with array representation G = (G_{1}, G_{2}, …, G_{b}). That is, there exists some h ∈ M^{b} with array representation H = (H_{1}, H_{2}, …, H_{b}) such that f = g + h, which means, by definition of the multisumset operation, F = G + H. Letting h^{∗} ∈ M^{b} denote the multiset given by the array representation H^{∗} = (H_{1}, ∅, …, ∅) we have f^{∗} = g + h^{∗}. Thus, every b-divisor g of f is also a b-divisor of f^{∗}. That is, d_{b}(f^{∗}) ≥ d_{b}(f).

If F_{2} ≠ ∅ then for any b-divisor g of f we must also have G_{2} ≠ ∅. Thus, f^{∗} itself is a b-divisor of f^{∗} that is not a b-divisor of f. We therefore have in this case d_{b}(f^{∗}) > d_{b}(f).

Notation 41. Let b be a positive natural number. We let [k]_{b} denote the multiset f ∈ M^{b} with b-ary array representation ([k], ∅, …, ∅).

The correspondence from Theorem 37 gives β_{b+1}([k]_{b}) = 11 ⋯ 1|_{b+1}, where 1 repeats k+1 times. Conjecture 14 states that this is the d_{b+1}(·)-maximal element among all (k + 1)-digit lunar numbers in base (b+1). Applegate, LeBrun, and Sloane used headstrong compositions H(n, p) to count the number of divisors of 11 ⋯ 1|_{b}:

Theorem 42. [1, Theorem 17]

d_{b} (\frac{b^{k} − 1}{b − 1}) = d_{b}(\underbrace{11 … 1}_{k}|_{b}) = ∑_{p=1}^{k} H(k, p)(b − 1)^{p}.  (9)

Applegate, LeBrun, and Sloane calculated [1, Table 10] the first few values of d_{b}(11 ⋯ 1|_{b}), which we reproduce in Table 5. We have already remarked on the combinatorial nature of the first column of Table 5 as counting headstrong compositions, sequence \underline{A079500} of the OEIS [16]. One wonders whether other columns have similarly interesting combinatorial interpretations. For example, the second column is sequence \underline{A186523} of the OEIS [16], and has no other combinatorial interpretation as of yet. Applegate, LeBrun, and Sloane pointed out that the rows may also be of interest; the second, third, and fourth rows are sequences \underline{A002378}, \underline{A027444}, and \underline{A186636} of the OEIS [16], respectively.

b = 2 b = 3 b = 4 b = 5 b = 6 b = 7 b = 8  b = 9 b = 10
k = 1 1  2  3  4  5  6  7  8  9
k = 2 2  6  12  20  30  42  56  72  90
k = 3 3  14  39  84  155  258  399  584  819
k = 4 5  34 129 356  805  1590  2849  4744  7461
k = 5 8  82 426 1508 4180 9798 20342 38536 67968
k = 6 14 206 1434 6452 21830 60594 145586 313544 619902
k = 7 24 526 4890 27828 114580 375954 1044246 2555080 5660208

Table 5: The number of base b lunar divisors of 11 ⋯ 1|_{b} with k repetitions of the digit 1. Reproduced from Applegate, LeBrun, and Sloane [1, Table 10].

Lemma 40 shows that in order to prove the maximality of d_{b}([k]_{b}) among sets in M_{≤k}^{b}, it suffices to prove its maximality among sets of the form (A, ∅, …, ∅) with A a finite nonempty subset such that max A ≤ k. Theorem 43 shows how to count the number of divisors of such multisets in terms of the number of divisors of the set A. Note that by Corollary 21, Equation (9) is a special case of Equation (10).

Theorem 43. Let b be a positive natural number, and let f ∈ M^{b} be a nonempty set, i.e., not a proper multiset. Thus, f has the b-ary array representation F = (F_{1}, ∅, …, ∅). Then,

d_{b}(f) = ∑_{G divisor of F_{1}} b^{card G}.  (10)

Proof. Let S be a finite set of natural numbers, and let c = card S. Fix an enumeration S = {s_{1}, …, s_{c}} of the elements of S. Consider all possible descending chains of length b:

S = S_{1} ⊇ S_{2} ⊇ ⋯ ⊇ S_{b}.

The question of which sets in the chain contain a given s ∈ S is answered by a single number 1 ≤ ℓ ≤ c; namely, the largest natural number ℓ such that s ∈ S_{ℓ}. Thus, each chain is uniquely identified with a sequence (ℓ_{1}, ℓ_{2}, …, ℓ_{c}) where each entry 1 ≤ ℓ_{i} ≤ b, and there are a total of b^{c} such possible sequences.

Let G be a divisor of F_{1}, so that there exists some H with F_{1} = G + H. Each descending chain G = G_{1} ⊇ G_{2} ⊇ ⋯ ⊇ G_{b} gives rise to a b-divisor g of f with the b-ary array representation (G_{1}, G_{2}, …, G_{b}), since

(G, G_{2}, …, G_{b}) + (H, ∅, …, ∅) = (F_{1}, ∅, …, ∅).

Conversely, if (G_{1}, G_{2}, …, G_{b}) is the array representation of a b-divisor of f, then

G_{1} ⊇ G_{2} ⊇ ⋯ ⊇ G_{b},

and G_{1} is a divisor of F_{1}.

Theorem 43 allows us to carry over our knowledge of divisors of sumsets to divisors of multisumsets. For example, Theorem 13 proves that [k] is d(·)-maximal in Z_{≤k}, and Corollary 44 is the corresponding statement for multisets.

Corollary 44. Let b be a positive natural number, and let f ∈ M_{≤k}^{b} be a nonempty 0-rooted set, i.e., it has array representation (A, ∅, …, ∅) for some A ∈ Z_{≤k}. Then d_{b}(f) ≤ d_{b}([k]_{b}), and the inequality is strict for f ≠ [k]_{b}.

Proof. The k-promotion procedure from Definition 7 either adds elements to the promoted set, or leaves the set as is. Thus, with the notation as in Definition 9, for every divisor C of A there corresponds a divisor C′ ∈ F_{A}(C) of [k] with card C′ ≥ card C, and Theorem 10 shows that different divisors of A give rise to different divisors of [k]. The claim now follows by Equation (10), and the observation from Lemma 11 and Lemma 12 that there are divisors of [k] that do not arise from k-promotion.

Next, Corollary 45 generalizes Lemma 26, and gives a more explicit version of Equation (3).

Corollary 45. Let b be a positive natural number, and let f ∈ M^{b} be a nonempty set, i.e., it has set array representation (A, ∅, …, ∅), for some finite nonempty set of natural numbers A. Let a := min A. Then,

d_{b}(f) = (a + 1) ∑_{C divisor of A − {a}} b^{card C}.

Proof. According to the proof of Lemma 26, each divisor C of B − {a} gives rise to a divisor B + {s} of A, for 0 ≤ s ≤ a. Moreover, all divisors of A are obtained in this manner. Since card B = card (B + {s}), we are done by Equation (10).

The stage is now set for proving the maximality of d_{b}([k]_{b}) among all sets in M_{≤k}^{b}.

Theorem 46. Let b be a positive natural number b ≥ 2, and let f ∈ M_{≤k}^{b} be a nonempty set, i.e., f has the set array representation (A, ∅, …, ∅) for some A ∈ Z_{≤k} ⊔ Z_{≤k}^{+}. Then d_{b}(f) ≤ d_{b}([k]_{b}), and the inequality is strict for f ≠ [k]_{b}.

Proof. Let a := min A. If a = 0, then A ∈ Z_{≤k} and the claim reduces to Corollary 44. Otherwise, a > 0 so that f ≠ [k]_{b}, and we have by Corollary 45

d_{b}(f) = (a + 1) ∑_{B divisor of A − {a}} b^{card B}.

Let n := max A − a, so that A − {a} ∈ Z_{n}. By Corollary 21 we have

d_{b}(f) = (a + 1) ∑_{p=1}^{n} H(n, p)b^{p}.

On the other hand,

d_{b}([k]_{b}) = ∑_{p=1}^{k} H(n + a, p)b^{p} ≥ ∑_{p=1}^{n+a} H(n + a, p)b^{p}.

By Corollary 32 we know that

∑_{p=1}^{n+1} H(n + 1, p)b^{p} > 2 ∑_{p=1}^{n} H(n, p)b^{p},

and by induction it follows that

∑_{p=1}^{n+a} H(n + a, p)b^{p} > 2^{a} ∑_{p=1}^{n} H(n, p)b^{p}

≥ (a + 1) ∑_{p=1}^{n} H(n, p)b^{p}.

(The last inequality is valid since a > 0, and 2^{s} ≥ s + 1 for any s ≥ 1.) We conclude that d_{b}([k]_{b}) > d_{b}(f).

We can now prove Conjecture 14.

Theorem 47. Let b, k be natural numbers such that b ≥ 2, and let f ∈ M_{≤k}^{b} be a nonempty multiset, i.e., f ≠ 0 is not the constant 0 function. Then d_{b}(f) ≤ d_{b}([k]_{b}), and the inequality is strict if f ≠ [k]_{b}.

Equivalently, in any base b + 1 ≥ 3, among all (k + 1)-digit numbers n, d_{b+1}(n) has a unique maximum at n = ((b + 1)^{k+1} − 1)/((b + 1) − 1) = 11 ⋯ 1|_{b+1} (with k + 1 repetitions of the digit 1).

Proof. Let F = (F_{1}, F_{2}, …, F_{b}) be the array representation of f, and let f^{∗} ∈ M_{≤k}^{b} be the multiset given by the b-ary array representation F^{∗} = (F_{1}, ∅, …, ∅). Lemma 40 gives d_{b}(f^{∗}) ≥ d_{b}(f) and the inequality is strict if F_{2} ≠ ∅. Theorem 46 then gives d_{b}([k]_{b}) ≥ d_{b}(f^{∗}) and the inequality is strict if f^{∗} ≠ [k]_{b}. Thus, d_{b}(f) ≤ d_{b}([k]_{b}) and the inequality is strict if f ≠ [k]_{b}.

8 Further questions

We have found that {1, …, k} has the most additive divisors among all subsets of {0, 1, …, k}. It is natural to restrict the size of the set instead of its maximal element, and one may then ask: among all sets of a given size k, which have the most number of divisors? We expect the answer to be the arithmetic progressions, and if true this would be an additional tool in quantifying additive structure. We thank Almut Burchard for this observation.

We have seen that sumset divisors of finite subsets of ℕ correspond to binary lunar divisor, as proved in Theorem 18. The setting of lunar arithmetic naturally inspires number-theoretic questions. This paper investigated divisibility questions for sumsets. Applegate, LeBrun, and Sloane [1] investigated a whole panoply of number-theoretic constructions for lunar numbers. Do other constructions have natural sumset counterparts? If so, may lunar arithmetic lead to new insights on sumsets? We single out two important examples. One, sumsets of the form A+A, also denoted 2A, are of particular importance in additive number theory and additive combinatorics. They correspond to binary lunar squares, sequence \underline{A067398} of the OEIS [16], mentioned briefly in Section 4 of Applegate, LeBrun, and Sloane’s paper [1, Section 4].

Two, irreducible finite subsets of ℕ, as defined in Definition 4, correspond to binary lunar primes, sequence \underline{A171000} of the OEIS [16]. Applegate, LeBrun, and Sloane investigated lunar primes in different bases [1, Section 3]. We have mentioned in Section 1 above Wirsing’s proof [18] that almost all subsets of ℕ are asymptotically irreducible. If we restrict our attention to finite subsets only, Applegate, LeBrun, and Sloane made a more precise conjecture:

Conjecture 48 ([1, Conjecture 10]). Let π_{b}(k) denote the number of base b lunar primes with k digits. Then,

π_{b}(k) ∼ (b − 1)^{2}b^{k−2}.

In particular, this predicts that about half of all subsets of [k] are irreducible.

Theorem 13 undergirds many of the results of this paper, as the proofs of Theorem 30 and Theorem 47 proceed via reductions to the 0-rooted case. The load-bearing part of the proof of Theorem 13 is the k-promotion procedure from Definition 7. However, this procedure is somewhat unique for the full interval [k]. For example,

{0, 2} + {0, 4} = {0, 2, 4, 6},

and even though {0, 2, 4, 6} ⊆ {0, 2, 3, 4, 5, 6}, an attempt to promote these to factors of {0, 2, 3, 4, 5, 6} is unsuccessful:

{0, 2} + {0, 1, 3, 4} = [6].

This is the difficulty in proving Conjecture 17 regarding the runner-up to d([k]); the number of divisors of the runner-up is enumerated in sequence \underline{A188524} of the OEIS [16]. Is there a way to generalize the promotion procedure to other sets?

Section 4 describes a bijection between divisors of [k] and headstrong compositions, which is expanded upon in Section 6. Is there a similar bijection between divisors of arbitrary sets and different kinds of compositions? What are the possible combinatorical interpretations of the different columns of Table 5, such as sequence \underline{A186523} of the OEIS [16]? What about the rows of Table 5? These kind of questions may be another possible way of making inroads into resolving Conjecture 17 via direct counting. Indeed, Applegate, LeBrun, and Sloane [1, Theorem 18] constructed a generating function for d_{2}(2^{k} − 3) by considering a subtle relation with restricted compositions, which is then used to prove the asymptotic relation d_{2}(2^{k} − 3)/d_{2}(2^{k} − 1) → 1/5. Sequence \underline{A188288} of the OEIS [16] enumerates d_{2}(2^{k} − 3).

9 Acknowledgments

Many thanks to Professor Almut Burchard for her expert guidance and unflagging positivity.

I would also like to thank Professor Leo Goldmakher for teaching me about sumsets at the University of Toronto. In 2015 he invited me to visit Williams College, where the question about comparing the number of divisors sumsets may have was first raised at a brainstorming session with Professor Goldmakher and a team of students participating in the SMALL Undergraduate Research Project: Huy Pham, Sophia Dever, and Vidya Venkatesh.

I am also grateful to Brady Haran for his delightful Numberphile videos. It was one of his interviews of Neil Sloane [7] which prompted this paper.

Finally, sincere thanks to the anonymous referee for their careful and thorough reading, and for the helpful suggestions about how to improve the clarity of the writing.

References

[1] D. Applegate, M. LeBrun, and N. J. A. Sloane, Dismal arithmetic, J. Integer Sequences 14 (2011), Article 11.9.8.

[2] Ch. A. Charalambides, On the enumeration of certain compositions and related sequences of numbers, Fibonacci Quart. 20 (1982), 132–146.

[3] C. Elsholtz, Additive decomposability of multiplicatively defined sets, Funct. Approx. Comment. Math. 35 (2006), 61–77.

[4] P. Erdős and E. Szemerédi, On sums and products of integers, in P. Erdős, L. Alpár, G. Halász, and A. Sárközy, eds., Studies in Pure Mathematics, Birkhäuser, 1983, pp. 213–218.

[5] A. Frosini and S. Rinaldi, On the sequence \underline{A079500} and its combinatorial interpretations, J. Integer Sequences 9 (2006), Article 06.3.1.

[6] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[7] B. Haran, Primes on the moon (lunar arithmetic), video, 2018, https://www.

numberphile.com/videos/lunar-arithmetic.

[8] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

[9] C. Jordan, Calculus of Finite Differences, Chelsea, 1965.

[10] A. Knopfmacher and N. Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287–295.

[11] P. A. MacMahon, Combinatory Analysis I, Cambridge University Press, 1915.

[12] M. B. Nathanson, Additive Number Theory: The Classical Bases, Springer, 1996.

[13] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer, 1996.

[14] H. H. Ostmann, Additive Zahlentheorie, Springer, 1956.

[15] K. Srinivasa Rao and A. K. Agarwal, On a generalized composition function, J. Indian Math. Soc. 67 (2000), 99–106.

[16] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

    at https://oeis.org.

[17] T. Tao and V. H. Vu, Additive Combinatorics, Cambridge University Press, 2010.

[18] E. Wirsing, Ein metrischer Satz über Mengen ganzer Zahlen, Arch. Math. 4 (1953), 392–398.

[19] D. A. Wolfram, Solving generalized Fibonacci recurrences, Fibonacci Quart. 36 (1998), 129–145.

2010 Mathematics Subject Classification: Primary 11P70; Secondary 05A17, 05A19, 05A20, 11A63, 11B39. Keywords: Sumset, Minkowski sum, lunar arithmetic, dismal arithmetic, carryless arithmetic, divisor, composition, restricted composition, generalized Fibonacci sequence, multiset.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A002378}, \underline{A007059}, \underline{A007318}, \underline{A027444}, \underline{A067398}, \underline{A079500}, \underline{A092921}, \underline{A171000}, \underline{A184957}, \underline{A186523}, \underline{A186636}, \underline{A188288}, \underline{A188524}.)

Received January 17 2020; revised versions received January 18 2020; August 6 2020; August 23 2020; October 17 2020. Published in Journal of Integer Sequences, October 18 2020.

Return to Journal of Integer Sequences home page.