\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \usepackage[justification=centering]{caption} \usepackage{tikz} \usepackage{adjustbox} \usepackage{caption} \usepackage{subcaption} \usepackage{wasysym} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \newcommand{\stp}{\,\,\,} \newcommand{\demph}[1]{\textit{#1}} \newcommand{\mcal}[1]{\ensuremath{\mathcal{#1}}} \newcommand{\eqdef}{\ensuremath{:=}} \newcommand{\st}[2]{\ensuremath{\{#1\, :\, #2\}}} \newcommand{\pset}[1]{\ensuremath{\mcal{P}(#1)}} \DeclareMathOperator{\crd}{card} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\union}{\cup} \newcommand{\Union}{\bigcup} \newcommand{\dunion}{\sqcup} \newcommand{\dUnion}{\bigsqcup} \newcommand{\insect}{\cap} \newenvironment{mx}{\left(\begin{matrix}}{\end{matrix}\right)} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{notation}[theorem]{Notation} \begin{center} \vskip 1cm{\LARGE\bf Maximally Additively Reducible Subsets \\ \vskip .1in of the Integers } \vskip 1cm \large Gal Gross\\ Department of Mathematics\\ University of Toronto\\ Toronto, ON M5S 2E4\\ Canada\\ \href{mailto:g.gross@mail.utoronto.ca}{\tt g.gross@mail.utoronto.ca} \end{center} \vskip .2 in \begin{abstract} Let $A, B \subseteq \N$ be two finite sets of natural numbers. We say that $B$ is an \demph{additive divisor} of $A$ if there exists some $C \subseteq \N$ with $A = B+C$, where `$+$' denotes the \demph{sumset operation}, also called \demph{Minkowski sum} or \demph{pairwise sum}. We prove that among subsets of $\{0, 1, \ldots, k\}$ containing $0$ as an element, the full set $\{0, 1, \ldots, 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 \demph{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, \ldots, k\}$ has the most additive divisors among all subsets of $\{0, 1, \ldots, 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. \end{abstract} \section{Introduction}\label{sec:intro} \begin{definition} Let $(G, +)$ be a commutative group, and let $A, B \subseteq G$ be subsets. The \demph{sumset} (also called \demph{Minkowski sum}) of $A$ and $B$, denoted $A+B$, is the set of pairwise sums: \[A+B \eqdef \st{a+b}{a \in A, b \in B}.\] (In particular, $A+\emptyset = \emptyset$ for any $A \subseteq G$.) The \demph{difference set} of $A$ and $B$, denoted $A-B$, is the set \[A - B \eqdef \st{a - b}{a \in A, b \in B}.\] \end{definition} \begin{notation} In this paper, we shall use the backward slash, $A\setminus B$, to denote the relative complement: \[A\setminus B \eqdef \st{a \in A}{a \notin B}.\] \end{notation} Here is another way of thinking about the sumset of $A$ and $B$, which will become important later in the paper. For each $b \in B$ we are shifting the elements of $A$ by $b$ to form the set $A + \{b\}$, then we take the union $A + B = \Union_{b \in B}(A+\{b\})$. Figure \ref{fig:graphsumsets} contains a graphical representation of this process, and Figure \ref{fig:sumsetseg} some examples of the operations above with the integers as the ambient group. \begin{figure}[H] \centering \begin{subfigure}[b]{0.35\linewidth} \centering \begin{tikzpicture} \draw[step=0.5cm,color=gray] (-5,1.99) grid (-1,5); \node at (-1.25, +5.25) {\color{gray}$0$}; \node at (-1.75, +5.25) {\color{gray}$1$}; \node at (-2.25, +5.25) {\color{gray}$2$}; \node at (-2.75, +5.25) {\color{gray}$3$}; \node at (-3.25, +5.25) {\color{gray}$4$}; \node at (-3.75, +5.25) {\color{gray}$5$}; \node at (-4.25, +5.25) {\color{gray}$6$}; \node at (-4.75, +5.25) {\color{gray}$\cdots$}; \node at (-1.75, +4.25) {$\CIRCLE$}; \node at (-2.75, +4.25) {$\CIRCLE$}; \node at (+0.25, +4.25) {\small $\{0, 2\} + \{1\}$}; \node at (-2.25, +3.75) {$\CIRCLE$}; \node at (-3.25, +3.75) {$\CIRCLE$}; \node at (+0.25, +3.75) {\small $\{0, 2\}+\{2\}$}; \node at (-3.25, +2.75) {$\CIRCLE$}; \node at (-4.25, +2.75) {$\CIRCLE$}; \node at (+0.25, +2.75) {\small $\{0, 2\}+\{4\}$}; \draw[thick] (-5,+2.5) -- (-1,+2.5); \node at (-1.75, +2.25) {$\CIRCLE$}; \node at (-2.25, +2.25) {$\CIRCLE$}; \node at (-2.75, +2.25) {$\CIRCLE$}; \node at (-3.25, +2.25) {$\CIRCLE$}; \node at (-4.25, +2.25) {$\CIRCLE$}; \node at (+0.6, +2.25) {\small $\{0, 2\} + \{1, 2, 4\}$}; \end{tikzpicture} \caption{Graphical representation of $\{0, 2\}+\{1, 2, 4\}$.} \label{fig:graphsumsets} \end{subfigure}\hfill \begin{subfigure}[b]{0.55\linewidth} \centering \begin{tabular}{lclcl} $\{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\}$ &$\setminus$ &$\{1, 2, 3\}$ &$=$ &$\emptyset$;\\ $\{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{tabular} \caption{Examples of the operations, with $\Z$ as the ambient group.} \label{fig:sumsetseg} \end{subfigure} \caption{Examples of sumsets, difference sets, and relative complement, with $\Z$ as the ambient group.}\label{fig:sumsetintro} \end{figure} 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 \eqdef A+ \cdots + A$ (with $n$ summands, for some $n \in \N$)? (We recommend Nathanson's book \cite{Nat96} 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 \cite{Nat96b} deals with inverse problems, while Tao and Vu's book \cite{TaVu10} 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 \cite{Ost56}. \begin{definition}\label{def:reducible} A set $A \subseteq \N^+$ of positive integers is said to be \demph{Ostmann reducible} if there are sets $B, C \subseteq \N^+$ each with more than one element, such that $A = B+C$. Otherwise, the set $A$ is said to be \demph{Ostmann irreducible}. Similarly, we call a set $A \subseteq \N^+$ \demph{asymptotically (additively) reducible} if there are some sets $B, C \subseteq \N^+$ each with more than one element, and a natural number $m \in \N$ such that \[(B+C) \insect [m, \infty) = A \insect [m, \infty).\] Otherwise, the set $A$ is said to be \demph{asymptotically (additively) irreducible}. \end{definition} Let $P$ denote the set of prime numbers. It is easy to see that $P$ is Ostmann irreducible (because $2, 3 \in 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{\H o}s and Szemer{\'e}di \cite{ErSz83} (Elsholtz \cite{Els06} reviewed some more recent progress). Regardless of any multiplicative structure, Wirsing \cite{Wir53} has proved that almost all subsets of $\N$ are asymptotically irreducible, and hence also Ostmann irreducible. (To interpret ``almost all'', one identifies subsets of $\N$ with their binary encoding, and thus with the interval $[0, 2] \subseteq \R$. We use a similar encoding in Section \ref{sec:arith} below.) Rather than asking which sets are irreducible, this paper is concerned with the opposite question: given some $k \in \N$, which subsets $A \subseteq \{0, \ldots, k\} \subseteq \N$ are maximally reducible? \begin{definition}\label{def:divisor} Let $A \subseteq \N$ be a set of natural numbers. We say that a set $B \subseteq \N$ is an \demph{additive divisor} (or \demph{sumset divisor}, or \demph{divisor}, or \demph{factor}) for $A$, if there exists some set $C \subseteq \N$ such that $A = B+C$. We then call $B+C$ a \demph{factorization} of $A$. Every set $A \subsetneq \N$ has a trivial factorization $A = A+\{0\}$. If the trivial factorization is the only possible factorization of $A$ we say that $A$ is \demph{(additively) irreducible}, otherwise we say that $A$ is \demph{(additively) reducible}. If the set $A$ is finite, we let $d(A)$ denote the number of sumset divisors of $A$. \end{definition} The trivial factorization $A = A+\{0\}$ shows that every set $A \neq \{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 \ref{def:reducible}, 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 \in \N$ and consider the set of all subsets of $\{0, \ldots, k\}$. In Section \ref{sec:0rooted} we introduce an operation called ``$k$-promotion'', acting on divisors of subsets which have $0$ as an element. Theorem \ref{thm:dmax0} of Section \ref{sec:0rooted} shows that among those subsets which have $0$ as an element, the full set $\{0, 1, \ldots, 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 \ref{thm:maxdb2} in Section \ref{sec:non0rooted} shows that $\{1, \ldots, k\}$ has the most divisors among all subsets of $\{0, \ldots, k\}$. In Section \ref{sec:arith} we assign each finite subset of $\N$ a binary number, and Theorem \ref{eq:keycorrespondence} proves that the sumset operation corresponds to binary lunar multiplication. Lunar multiplication is an operator defined by Applegate, LeBrun, and Sloane \cite{ALS11} 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\cdots 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 \ref{sec:count} 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 \ref{thm:maxdb2} in Section \ref{sec:non0rooted}, which states that $\{1, \ldots, k\}$ has the most divisors among all subsets of $\{0, \ldots, k\}$. Due to the correspondence between sumset divisors and binary lunar divisors, Theorem \ref{thm:dmax0} and Theorem \ref{thm:maxdb2} resolve two conjectures of Applegate, LeBrun, and Sloane, reproduced in Section \ref{sec:arith} as Conjecture \ref{conj:maxb2odd} and Conjecture \ref{conj:maxdb2}. These conjectures are a binary version of a more general Conjecture \ref{conj:maxdb3}, since lunar arithmetic can be defined for arbitrary bases. Section \ref{sec:headstrong} prepares the groundwork for proving this general conjecture by further exploring the restricted compositions from Section \ref{sec:count}. Theorem \ref{thm:recurrence} establishes a new recurrence relation for the function enumerating such restricted compositions. Section \ref{sec:headstrong} discusses in detail the following interesting combinatorial interpretation of Theorem \ref{thm:recurrence}: 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 \ref{conj:maxdb3} in Theorem \ref{thm:maxdb3} of Section \ref{sec:multisets}. Theorem \ref{thm:keygeneral} of Section \ref{sec:multisets} 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 \ref{sec:questions}. \section{Divisors of $0$-rooted sets}\label{sec:0rooted} \begin{notation} Fix some $k \in \N$. Throughout the paper we let $[k]$ denote the full interval \[[k] \eqdef [0, k] \insect \N = \{0, \ldots, k\}.\] \end{notation} \begin{definition} We say that a set $A \subseteq \N$ of nonnegative integers is \demph{$0$-rooted} if $\min A = 0$. For any $k \in N$, we denote by $\mcal{Z}_k$ the collection of $0$-rooted sets whose maximal element is $k$: \[\mcal{Z}_k \eqdef \st{A \subseteq \N}{\min A = 0, \max A = k}.\] For convenience we also introduce the notation $\mcal{Z}_{\leq k}$ for the collection of $0$-rooted sets whose maximal element does not exceed $k$: \[\mcal{Z}_{\leq k} \eqdef \Union_{\ell \leq k}\mcal{Z}_\ell.\] We let $\mcal{Z}$ denote the collection of finite $0$-rooted sets: \[\mcal{Z} \eqdef \Union_{k \in \N}\mcal{Z}_k.\] \end{definition} An interesting feature of $0$-rooted sets is that the divisors are subsets. Indeed, suppose $A \in \mcal{Z}$ is a $0$-rooted set, with a factorization $A = B+C$ for some $B, C \subseteq \N$. Since the only way to obtain $0$ by adding natural numbers is $0 + 0 = 0$, we must have $0 \in B, C$ so that $B, C$ are themselves $0$-rooted. Moreover, since $0 \in C$ we have that $B = B + \{0\} \subseteq B+C = A$, and similarly $C \subseteq 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 $\mcal{Z}_{\leq k}$, the full interval $[k]$ has the most divisors. The key idea is a procedure for converting divisors of any set $A \in \mcal{Z}_{\leq k}$ into divisors of $[k]$. We call this procedure \demph{$k$-promotion}. \begin{definition}\label{def:promotion} Let $k \in \N$, and let $A \in \mcal{Z}_{\leq k}$. Suppose that $B, C \subseteq \N$ such that $A = B+C$, and such that $\max B \leq \max C$. We now define a new set $C_B$ as the union of three sets $C$, $B_1$, and $B_2$, where \begin{align*} B_1 &= ([k]\setminus A) \insect [\max B - 1],\\ B_2 &= (([k]\setminus A) - \{\max B\}) \insect \N. \end{align*} That is, $C_B$ is constructed by the following algorithm: \begin{description} \item[] for each $s \in [k]\setminus A$: \begin{description} \item[] if $s < \max B$, append $s$ to $C$; \item[] if $s \geq \max B$, append $s-\max B$ to $C$. \end{description} \end{description} \end{definition} 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 \ref{fig:kpromotion}. \begin{figure}[H] \centering \begin{adjustbox}{width=\columnwidth,center} \begin{tabular}{lclclclclcl} $B$ & & $C$ & & $A$ & & $B$ & & $C_B$ & & $[k]$ \\ $\{0, 3\}$ & $+$ & $\{0, 4\}$ & $=$ & $\{0, 3, 4, 7\}$ &$\leadsto$& $\{0, 3\}$ &$+$ & $\{0, 1, 2, 3, 4\}$ & $=$ & $[7]$ \\ $\{0, 3\}$ & $+$ & $\{0, 4\}$ & $=$ & $\{0, 3, 4, 7\}$ &$\leadsto$& $\{0, 3\}$ &$+$ & $\{0, 1, 2, 3, 4, 5\}$ & $=$ & $[8]$ \\ $\{0, 3\}$ & $+$ & $\{0, 1, 3\}$ & $=$ & $\{0, 1, 3, 4, 6\}$ &$\leadsto$& $\{0, 3\}$ &$+$ & $\{0, 1, 2, 3\}$ & $=$ & $[6]$ \\ $\{0, 1, 3\}$ & $+$ & $\{0, 3\}$ & $=$ & $\{0, 1, 3, 4, 6\}$ &$\leadsto$& $\{0, 1, 3\}$ &$+$ & $\{0, 2, 3\}$ & $=$ & $[6]$ \\ \end{tabular} \end{adjustbox} \caption{Examples of $k$-promotion.\\ {In the top row $A$ is regarded as a subset of $\mcal{Z}_{\leq 7}$, while in the next it is regarded as a subset of $\mcal{Z}_{\leq 8}$. In the bottom two rows $A$ is regarded as a subset of $\mcal{Z}_{\leq 6}$. Its divisors $\{0, 3\}$ and $\{0, 1, 3\}$ share the same maximal element, so either one of them could be promoted.}} \label{fig:kpromotion} \end{figure} \begin{lemma}\label{lem:promotionworks} Let $k \in \N$, and let $A \in \mcal{Z}_{\leq k}$. Suppose that $B, C \subseteq \N$ such that $A = B+C$, and such that $\max B \leq \max C$. Then $B+C_B = [k]$. \end{lemma} \begin{proof} Since $C \subseteq C_B$ we have $A = B+C \subseteq B+C_B$. Moreover, by construction, $[k]\setminus A \subseteq B+C_B$. Thus, $[k] = A \union ([k]\setminus A) \subseteq B+C_B$. To prove the reverse inclusion, note that $\max(B+C_B) = \max B + \max C_B$. By construction, $\max C_B \leq \max\{k - \max B, \max C\}$ so that \[\max B + \max C_B \leq \max\{k, \max B + \max C\} = \max\{k, \max A\} \leq k.\] Moreover, $\min(B+C_B) = 0$. Thus, $B+C_B \subseteq [k]$. \end{proof} 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. \begin{definition}\label{def:FAC} Let $k \in \N$, and let $A \in \mcal{Z}_{\leq k}$. Suppose $C$ is a factor of $A$. We define the set $F_A(C)$ by the following algorithm: \begin{description} \item For each $B \subseteq A$ such that $B+C = A$: \begin{description} \item if $\max B \geq \max C$, let $C \in F_A(C)$; \item if $\max B \leq \max C$, let $C_B \in F_A(C)$. \end{description} \end{description} (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)$.) \end{definition} 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 \ref{fig:FactorsC} presents some examples of $F_A(C)$ for different choices of $C$. \begin{figure}[H] \centering { \begin{align*} 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\}\}. \end{align*} } \caption{Examples of $F_A(C)$ for $A = \{0, 2, 3, 4, 5, 6\} \in \mcal{Z}_{\leq 6}$.} \label{fig:FactorsC} \end{figure} \begin{theorem}\label{thm:disjointfactors} Let $k \in \N$, and let $A \in \mcal{Z}_{\leq k}$. If $C$ and $D$ are different divisors of $A$, then $F_A(C) \insect F_A(D) = \emptyset$. \end{theorem} \begin{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 \subsetneq [k]$, so in particular $[k]\setminus A \neq \emptyset$. Suffice it to show that no element of $F_A(C)$ is an element of $F_A(D)$. \bigskip \noindent\emph{Step 1:} $C \in F_A(C) \implies C \notin F_A(D)$.\\ Suppose that $C \in F_A(C)$. Then there exists some $B \subseteq A$ with $\max B \geq \max C$ and $B+C = A$. By assumption, $C \neq 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 \subseteq A$ with $\max E \leq \max D$ and $D + E = A$. Since $D \subseteq D_E$, if $D\not\subseteq C$ we are done. Assume therefore that $D \subseteq C$, so in particular $\max D \leq \max C$. We therefore have the chain of inequalities: \[\max E \leq \max D \leq \max C \leq \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 \in [k]\setminus A$ there are two options: \begin{itemize} \item $s < m$, in which case $s \in D_E$. Since $s \notin A \supseteq C$, this shows that $C \neq D_E$. \item $s \geq m$, in which case $s-m \in D_E$. Assume for contradiction that $s-m \in C$. Since $m \in B$ we would then have $s = m+(s-m) \in B+C = A$, a contradiction. Thus, $s-m \notin C$ and $C \neq D_E$. \end{itemize} We conclude that $C \in F_A(C) \implies C \notin F_A(D)$, as we wanted to show. \bigskip \noindent\emph{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 \subseteq A$, so we will now show that $C_B \in F_A(C)$ implies $C_B \notin F_A(D)$. First note that by the argument above, if $D \in F_A(D)$ we know that $D \notin F_A(C)$. All other elements of $F_A(D)$ are of the form $D_E$ for some suitable $E \subseteq A$. Specifically, we are assuming that there exist some $B, E \subseteq A$ such that \begin{align*} A &= B+C \mbox{ and } \max B \leq \max C,\\ A &= D+E \mbox{ and } \max D \geq \max E. \end{align*} Assume for contradiction that $C_B = D_E$. First, suppose that $C \subseteq D$. Since $C \neq D$ by assumption, there must exist some $d \in D$ such that $d \notin C$. Since $D \subseteq A$ we have $d \notin [k]\setminus A$. However, since $D \subseteq D_E$ we have $d \in D_E = C_B$, so there must be some $s \in [k]\setminus A$ with $d = s - \max B$. Now, $s = d+\max B \notin A$ implies $\max B \notin E$. Therefore, $\max E \neq \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 \subseteq D$ we must have $C_B \neq D_E$, as we wanted to show. On the other hand if $C \not\subseteq D$, there is some $c \in C$ such that $c \notin D$. Analogous argument to the one above then shows that $\max E \neq \max B$, which again contradicts the assumption $C_B = D_E$. \end{proof} Theorem \ref{thm:disjointfactors} is enough to establish the maximality of $d([k])$ among the sets in $\mcal{Z}_{\leq k}$. The following two lemmas will help show that $d([k])$ is also the unique maximum among the sets in $\mcal{Z}_{\leq k}$. \begin{lemma}\label{lem:uniqueodd} Let $k \in \N$ be an odd number such that $k \geq 3$. Then the set $F_k \eqdef \{0, (k+1)/2\}$ is a factor of $[k]$ which does not arise from $k$-promotion. That is, for any $A \in \mcal{Z}_{\leq k}$ such that $A \subsetneq [k]$, and any divisor $C$ of $A$, we have $F_k \notin F_A(C)$. \end{lemma} \begin{proof} It is clear that $F_k$ is a factor of $[k]$, since \[[k] = [(k-1)/2] + F_k.\] Let $A \in \mcal{Z}_{\leq k}$ such that $A \subsetneq [k]$, and let $C$ be a divisor of $A$. Assume for contradiction that $F_k \in F_A(C)$. Then either: \begin{itemize} \item $C = F_k$ and $C \in F_A(C)$. That is, there exists some $B \subseteq A$ for which $B+F_k = A$ and $\max B \geq \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. \item $F_k = C_B$ for some $B \subseteq A$ such that $B+C = A$ and $\max B \leq \max C$. Since $C \subseteq C_B = F_k$ we must have $C \subseteq \{0, (k+1)/2\}$. Moreover, since $C$ is a divisor of $A$, it must be $0$-rooted. We therefore have two options: \begin{itemize} \item Suppose $C = \{0\}$. The assumption $\max B \leq \max C$ forces $B = \{0\}$, in which case the $k$-promotion procedure results in $C_B = [k] \neq F_k$ (since $k \geq 3$), a contradiction. \item Suppose $C = F_k$. Lemma \ref{lem:promotionworks} gives $[k] = B+C_B = B+F_k$. Since $C = F_k$ we also have $A = B+C = [k]$, contradicting the assumption that $A \subsetneq [k]$. \end{itemize} \end{itemize} These contradictions show that $F_k \notin F_A(C)$. \end{proof} 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: \begin{lemma}\label{lem:uniqueeven} Let $k \in \N$ be an even number such that $k \geq 4$. Then for any $A \in \mcal{Z}_{\leq k}$ with $A \subsetneq [k]$, there exists some set $F_k$, such that $F_k$ is a divisor of $[k]$ and $F_k \notin F_A(C)$ for any divisor $C$ of $A$. \end{lemma} \begin{proof} We distinguish between two cases: $A = [k]\setminus \{2\}$, and $A \neq [k]\setminus\{2\}$. \begin{itemize} \item $A = [k]\setminus\{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 \subseteq A$ and $B, C$ are $0$-rooted sets, and so $2 \notin C$ (for otherwise $2 = 0+2 \in B+C \in 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 \subseteq A$ with $A = B+C$, $\max B \leq \max C$, and $F_k = C_B$. Since $C \subseteq C_B = F_k$ and $2 \notin C$, we must have $C = \{0\}$. Since $\max B \leq \max C$ we also have $B = \{0\}$. But then $A = B+C = \{0\}$, contradicting the assumption that $A = [k]\setminus \{2\}$ for $k \geq 4$. This contradiction proves that $F_k \notin F_A(C)$ for any factor $C$ of $A$. \item $A \neq [k]\setminus \{2\}$. In this case we choose $F_k = \{0, 1, 3, 5, \ldots, 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 \in F_A(C)$. We have the following two possibilities: \begin{itemize} \item $F_k = C$ and $C \in F_A(C)$. That is, there exists some $B \subseteq A$ with $B+F_k = A$ and $\max B \geq \max F_k$. Since $\max F_k = k-1$ we obtain \[\max A = \max B + \max F_k \geq (k-1)+(k-1) = 2k-2.\] Since $\max A \leq k$ we also have $2k-2 \leq k$, so that $k \leq 2$. This contradicts the assumption that $k \geq 4$. \item $F_k = C_B$ for some $B \subseteq A$ such that $A = B+C$ and $\max B \leq \max C$. Lemma \ref{lem:promotionworks} 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 \subseteq C_B$, we know that $A = B+C \subseteq B+C_B = [k]$. However, $A \subsetneq [k]$, so we must have $C \subsetneq 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 \in C$. All other elements of $F_k$ are of the form $2x+1$ for some natural number $x \in \N$. Suppose $2x+1 \in C_B\setminus C$, and assume for contradiction that $x>0$. Then we claim that $2x+1, 2x+2 \notin 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 \in 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, \ldots, k-1\}$. But then \[A = B+C = [k]\setminus \{2\},\] contradicting our assumption that $A \neq [k]\setminus\{2\}$. \end{itemize} We conclude that $F_k \notin F_A(C)$ for any factor $C$ of $A$. \end{itemize} For any $A \in \mcal{Z}_{\leq k}$ with $A \subsetneq [k]$, we have found a divisor $F_k$ of $[k]$, such that $F_k \notin F_A(C)$ for any divisor $C$ of $A$. \end{proof} We can now conclude that every other set in $\mcal{Z}_{\leq k}$ has fewer divisors than $[k]$. \begin{theorem}\label{thm:dmax0} The set $[k]$ is the unique maximum of $d(\cdot)$ in $\mcal{Z}_{\leq k}$. \end{theorem} \begin{proof} Given some $0$-rooted set $A \subsetneq [k]$, we have a map $C \mapsto F_A(C)$ taking each divisor of $A$ to a nonempty set of divisors of $[k]$. Theorem \ref{thm:disjointfactors} shows that if $C, D$ are different divisors of $A$, then $F_A(C)$ and $F_A(D)$ are disjoint. Therefore, \[d([k]) \geq \sum_{C \mbox{ \scriptsize divides } A}\crd{F_A(C)} \geq \sum_{C \mbox{ \scriptsize divides } A}1 = d(A).\] This proves that $[k]$ is a maximum of $d(\cdot)$ in $\mcal{Z}_{\leq k}$. Next, it is easy to see by direct computation that $[k]$ is the unique maximum of $d(\cdot)$ for $k = 0, 1, 2$ (with $1, 2, 3$ factors respectively). Lemma \ref{lem:uniqueodd} and Lemma \ref{lem:uniqueeven} show that $[k]$ is the unique maximum of $d(\cdot)$ for $k \geq 3$. \end{proof} \section{Lunar arithmetic}\label{sec:arith} We now introduce \demph{lunar arithmetic}\footnote{Originally published under the name \demph{dismal arithmetic}, the authors have come to prefer the name ``lunar arithmetic'' instead \cite{Har18}. Relevant OEIS \cite{OEIS} entries have also been renamed.}, a type of min/max carry-less arithmetic defined and studied by Applegate, LeBrun, and Sloane \cite{ALS11}. The following paragraph recounts the definitions from their paper \cite[Section 2]{ALS11} with a slight change of notation. Given a natural number $b \geq 2$, one starts with a set of \demph{digits} $\mcal{D}_b = \{0, 1, \ldots, b-1\}$ equipped with two binary operations, defined as follows: base $b$ \demph{lunar addition}, denoted $\oplus_b$, is the max operator on digits. That is, for any $p, q \in \mcal{D}_b$, \[p\oplus_b q = \max\{p, q\}.\] Base $b$ \demph{lunar multiplication}, denoted $\otimes_b$, is the min operator on digits. That is, for any $p, q \in \mcal{D}_b$, \[p\otimes_b q = \min\{p, q\}.\] As with any positional counting system, a base $b$ \demph{lunar number} is identified with a polynomial in $\mcal{D}_b[X]$, i.e., a formal expression of the form $\sum_{i=0}^{m}p_iX^i$, where $p_i \in \mcal{D}_b$ (for all $0 \leq i \leq m$). Such an expression is also written in positional notation as $p_mp_{m-1}\cdots p_1p_0|_{b}$. We can identify lunar numbers with natural numbers by evaluating the polynomial at the base $b$. Suppose $P = \sum_{i=0}^{m}p_iX^i$ and $Q = \sum_{j=0}^{n}q_jX^j$ are two lunar numbers, and assume without loss of generality that $m \leq n$. The \demph{lunar sum} of $P$ and $Q$, denoted by $P\oplus_b Q$, is defined by performing digit-wise lunar addition: \[P\oplus_b Q = \sum_{j=0}^{n}(p_j \oplus_b q_j)X^j,\] where $p_i = 0$ for $i>m$. Figure \ref{fig:10lunarplus} (reproduced from Applegate, LeBrun, and Sloane \cite[Figure 1a]{ALS11}) 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 \demph{lunar product} of $P$ and $Q$, denoted by $P \otimes_b Q$, is defined by convolution of digits, in an analogous way to multiplication in traditional arithmetic: \[P\otimes_b Q = \sum_{\ell=0}^{m+n}r_\ell X^\ell,\] where \begin{align*} r_0 &= p_0 \otimes_b q_0, \\ r_1 &= (p_0 \otimes_b q_1) \oplus_b (p_1\otimes_b q_0), \\ &\ \vdots \end{align*} That is, for any $0 \leq \ell \leq m+n$, we have \[r_\ell = (p_0\otimes_b q_\ell)\oplus_b (p_1\otimes_b q_{\ell-1}) \oplus_b \cdots \oplus_b (p_\ell \otimes_b q_0),\] where $p_i = 0$ for $i>m$ and $q_j = 0$ for $j>n$. Figure \ref{fig:10lunartimes} (reproduced from Applegate, LeBrun, and Sloane \cite[Figure 1b]{ALS11}) 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{figure}[H] \centering \begin{subfigure}[b]{0.5\linewidth} \centering \begin{tabular}{lr} & $169$ \\ $\oplus_{10}$ & $248$ \\ \hline & $269$ \end{tabular} \caption{Base 10 lunar addition.} \label{fig:10lunarplus} \end{subfigure}\hfill \begin{subfigure}[b]{0.5\linewidth} \centering \begin{tabular}{lr} & $169$ \\ $\otimes_{10}$ & $248$ \\ \hline & $168$ \\ $\oplus_{10}$ & $144$\stp \\ $\oplus_{10}$ & $122$\stp\stp \\ \hline &$12468$ \end{tabular} \caption{Base 10 lunar multiplication.} \label{fig:10lunartimes} \end{subfigure} \caption{Examples in base 10 lunar arithmetic (from Applegate, LeBrun, and Sloane \cite[Figure 1]{ALS11}).}\label{fig:lunararithmetic} \end{figure} Applegate, LeBrun, and Sloane proved \cite[Theorem 1]{ALS11} that $(\mcal{D}_b[X], \oplus_b, \otimes_b)$ is a commutative semiring; that is, that $\oplus_b$ and $\otimes_b$ are commutative and associative operations on $\mcal{D}_b[X]$, and that $\otimes_b$ distributes over $\oplus_b$. They then defined and studied different analogues of number-theoretic constructions including ``primes, number of divisors, sum of divisors, and the partition function.'' \cite[Abstract]{ALS11} 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 \cite[Section 6]{ALS11} contains a series of conjectures about the properties of $d_b(n)$, which we reproduce below for ease of reference. \begin{conjecture}[\textrm{\cite[Conjecture 12]{ALS11}}]\label{conj:maxdb3} In any base $b \geq 3$, among all $k$-digit numbers $n$, $d_b(n)$ has a unique maximum at $n = (b^k-1)/(b-1) = 111\cdots 1|_b$. \end{conjecture} \begin{conjecture}[\textrm{\cite[Conjecture 13]{ALS11}}]\label{conj:maxdb2} In base $2$, among all $k$-digit numbers $n$, the maximal value of $d_2(n)$ occurs at $n = 2^k-2 = 111\cdots 10|_2$, and this is the unique maximum for $n\neq 2, 4$. \end{conjecture} \begin{conjecture}[\textrm{\cite[Conjecture 14]{ALS11}}]\label{conj:maxb2odd} In base 2, among all odd $k$-digit numbers $n$, $d_2(n)$ has a unique maximum at $n=2^k-1 = 111\cdots 11|_2$. \end{conjecture} \begin{conjecture}[\textrm{\cite[Conjecture 14]{ALS11}}]\label{conj:runnerupb2odd} In base 2, among all odd $k$-digit numbers $n$, if $k \geq 3$ and $k \neq 5$, the second-largest value of $d_2(n)$ occurs at $n=2^{k}-3 = 111\cdots 101|_2$, and possibly other values of $n$. \end{conjecture} The sequence $d_2(1|_2), d_2(11|_2), d_2(111|_2), \ldots$ from Conjecture \ref{conj:maxb2odd} in particular appears to count many different combinatorial phenomena. Applegate, LeBrun, and Sloane \cite[Remark after Theorem 16]{ALS11} mentioned several different contexts and referred to sequences \seqnum{A007059} and \seqnum{A079500} of the OEIS \cite{OEIS}. Frosini and Rinaldi \cite{FrRi06} constructed explicit bijections between several of these combinatorial interpretations. As we discuss in Section \ref{sec:count} below, Applegate, LeBrun, and Sloane counted $d_2(1\cdots 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 \ref{conj:maxb2odd} by using Theorem \ref{thm:dmax0}; see Corollary \ref{crl:maxb2odd}. We then build on this result, and the investigation of Applegate, LeBrun, and Sloane to prove Conjecture \ref{conj:maxdb2}; see Theorem \ref{thm:maxdb2}. Finally, Section \ref{sec:multisets} extends this correspondence to lunar multiplication in other bases, which ultimately allows us to prove Conjecture \ref{conj:maxdb3}; see Theorem \ref{thm:maxdb3}. Conjecture \ref{conj:runnerupb2odd} remains open. Let $\mcal{F}$ denote the collection of finite subsets of $\N$, and let $\mcal{B}_2$ denote the set of binary numbers, written using the digits in $\mcal{D}_2 = \{0, 1\}$. There is a natural bijection $\beta_2: \mcal{F} \to \mcal{B}_2$ based on the idea of encoding membership as a binary sequence. First, define $\beta_2(\emptyset) = 0$. Next, for any nonempty $P \in \mcal{F}$ we define the binary number $\beta_2(P) = p_{\max P}\cdots p_1p_0|_2$, where $p_i$ for $0 \leq i \leq \max P$ is defined as follows: \[p_i = \begin{cases} 1, &\mbox{ if } i \in P;\\ 0, &\mbox{ if } i \notin P. \end{cases}\] Let $P, Q \in \mcal{F}$. The key observation, which we prove in Theorem \ref{thm:keycorrespondence}, is \begin{equation}\label{eq:keycorrespondence} \beta_2(P+Q) = \beta_2(P)\otimes_2\beta_2(Q). \end{equation} It is most intuitive why this should be the case when interpreting $P+Q$ as $\Union_{q \in Q}(P+\{q\})$. We then have a natural correspondence between sumsets and long multiplication, as is demonstrated in the example in Figure \ref{fig:sumsetrep}. \begin{figure}[H] \centering \begin{subfigure}[b]{0.35\linewidth} \centering \begin{tikzpicture} \draw[step=0.5cm,color=gray] (-5,1.99) grid (-1,5); \node at (-1.25, +5.25) {\color{gray}$0$}; \node at (-1.75, +5.25) {\color{gray}$1$}; \node at (-2.25, +5.25) {\color{gray}$2$}; \node at (-2.75, +5.25) {\color{gray}$3$}; \node at (-3.25, +5.25) {\color{gray}$4$}; \node at (-3.75, +5.25) {\color{gray}$5$}; \node at (-4.25, +5.25) {\color{gray}$6$}; \node at (-4.75, +5.25) {\color{gray}$\cdots$}; \node at (-1.75, +4.25) {$\CIRCLE$}; \node at (-2.75, +4.25) {$\CIRCLE$}; \node at (+0.25, +4.25) {\small $\{0, 2\} + \{1\}$}; \node at (-2.25, +3.75) {$\CIRCLE$}; \node at (-3.25, +3.75) {$\CIRCLE$}; \node at (+0.25, +3.75) {\small $\{0, 2\}+\{2\}$}; \node at (-3.25, +2.75) {$\CIRCLE$}; \node at (-4.25, +2.75) {$\CIRCLE$}; \node at (+0.25, +2.75) {\small $\{0, 2\}+\{4\}$}; \draw[thick] (-5,+2.5) -- (-1,+2.5); \node at (-1.75, +2.25) {$\CIRCLE$}; \node at (-2.25, +2.25) {$\CIRCLE$}; \node at (-2.75, +2.25) {$\CIRCLE$}; \node at (-3.25, +2.25) {$\CIRCLE$}; \node at (-4.25, +2.25) {$\CIRCLE$}; \node at (+0.6, +2.25) {\small $\{0, 2\} + \{1, 2, 4\}$}; \end{tikzpicture} \caption{Graphical representation of $\{0, 2\}+\{1, 2, 4\}$.} \label{fig:graphsumsetsagain} \end{subfigure}\hfill \begin{subfigure}[b]{0.35\linewidth} \centering \begin{tabular}{lr} & $101$ \\ $\otimes_2$ & $10110$ \\ \hline & $000$ \\ $\oplus_2$ & $101$\stp \\ $\oplus_2$ & $101$\stp\stp \\ $\oplus_2$ & $000$\stp\stp\stp\\ $\oplus_2$ & $101$\stp\stp\stp\stp \\ \hline &$1011110$ \end{tabular} \caption{Binary lunar representation of $\{0, 2\}+\{1, 2, 4\}$.} \label{fig:binsumsets} \end{subfigure} \caption{Two representations of sumsets.}\label{fig:sumsetrep} \end{figure} \begin{theorem}\label{thm:keycorrespondence} The map $\beta_2: \mcal{F} \to \mcal{B}_2$ is a monoid-isomorphism, where $\mcal{F}$ is equipped with the sumset operation and $\mcal{B}_2$ is equipped with binary lunar multiplication. \end{theorem} \begin{proof} Note that the fact that $(\mcal{F}, +)$ is a commutative monoid follows from the fact that $(\N, +)$ is a commutative monoid. The fact that $(\mcal{B}_2, \otimes_2)$ is a commutative monoid follows from the fact that $(\mcal{D}_2[X], \oplus_2, \otimes_2)$ is a commutative semiring. It is also easy to see (e.g., by considering the inverse map) that the map $\beta_2$ is a bijection, and it remains to prove that it is a monoid-homomorphism. We have $\beta_2(\{0\}) = 1|_2$, so the neutral elements are mapped to each other. Next, let $P, Q \in \mcal{F}$. We need to prove Equation \eqref{eq:keycorrespondence} holds. The result is clear when $P = \emptyset$ or $Q = \emptyset$. Assume therefore that $P, Q \neq \emptyset$, and the corresponding binary numbers are $\beta_2(P) = \sum_{i=0}^{\max P}p_i2^i$ and $\beta_2(Q) = \sum_{j=0}^{\max Q}q_j2^j$. By definition of lunar multiplication we have \[\beta_2(P)\otimes_2 \beta_2(Q) = \sum_{\ell=0}^{\max P + \max Q}r_\ell2^\ell,\] where, for any $0 \leq \ell \leq \max P + \max Q$, we have \begin{align*} r_\ell &= (p_0\otimes_2 q_\ell)\oplus_2 (p_1\otimes_2 q_{\ell-1}) \oplus_2 \cdots \oplus_2 (p_\ell \otimes_2 q_0)\\ &=\max\st{\min\{p_i, q_j\}}{i+j=\ell}. \end{align*} (As always, $p_i = 0$ for $i>\max P$, and $q_j = 0$ for $j>\max Q$). Let us now compare the $\ell$-th digit of $\beta_2(P)\otimes_2\beta_2(Q)$ and the $\ell$-th digit of $\beta_2(P+Q)$. \begin{itemize} \item According to the convolution product above, $r_\ell = 1$ if and only if there exist $i, j \in \N$ with $i+j = \ell$, such that $p_i = 1$ and $q_j = 1$. \item By definition of the mapping $\beta_2$, the $\ell$-th digit of $\beta_2(P+Q)$ is $1$ if and only if $\ell \in P+Q$; that is, if and only if there exist $i, j \in \N$ with $i+j = \ell$, such that $i \in P$ and $j \in Q$. Again, by the definition of the mapping $\beta_2$, this happens if and only if $p_i = 1$ and $q_j = 1$. \end{itemize} We see that by the definition of the map $\beta_2$ these two conditions are in fact the same, so $\beta_2(P+Q) = \beta_2(P)\otimes_2\beta_2(Q)$ as we wanted to show. \end{proof} The least significant digit of an odd binary number must be $1$, so the monoid-isomorphism $\beta_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 \ref{conj:maxb2odd} becomes an immediate corollary of Theorem \ref{thm:dmax0} above. \begin{corollary}\label{crl:maxb2odd} In base $2$, among all odd $k$-digit numbers $n$, $d_2(n)$ has a unique maximum at $n = 2^k - 1 = 111\cdots 11|_2$. \end{corollary} \section{Counting $d([k])$}\label{sec:count} In Section \ref{sec:non0rooted} we find the maximum of $d(\cdot)$ 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 \cite[Theorem 15]{ALS11}, that $d(11\cdots10|_2) = 2d(11\cdots1)$ with $k$ occurrences of $1$ on each side of the equality. Translated to the language of sumsets the equality reads $d([k]\setminus \{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 \demph{composition} of a positive natural number $n \in \N^+$ is an ordered tuple of positive natural numbers $(c_1, c_2, \ldots, c_m)$ such that $n = \sum_{i=1}^{m}c_i$. If the length of the tuple is $m$, the composition is called an \demph{$m$-composition}. Each of the entries $c_i$ in the composition is called a \demph{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 \demph{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, \ldots, c_m)$ is a composition of $n$, we say that a \demph{rise} occurs in position $i$ (for $1\leq i \leq m-1$) if $c_{i+1} > c_i$, a \demph{fall} in position $i$ is defined analogously as $c_{i+1} < c_i$, and a \demph{level} in position $i$ occurs when $c_{i+1} = c_i$. In the context of compositions, \demph{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 \cite{Mac15} 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 \cite{HeMa10} for an excellent survey of the field. LeBrun conjectured that $d_2(11\cdots 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 \ref{fig:headstrongdivisors} shows an example of such a correspondence. For ease of reference we shall use the appellation \demph{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 \seqnum{A079500} of the OEIS \cite{OEIS}. LeBrun's conjecture was proved by Schroeppel \cite[Theorem 16]{ALS11} and again by Frosini and Rinaldi \cite{FrRi06}. For the sake of completion, we reproduce the proof below translated to the language of sumsets. \begin{theorem}[Schroeppel, 2001] For any $n \in \N$, the number $d([n])$ equals the number of headstrong compositions of $n+1$. \end{theorem} \begin{proof} \leavevmode \vphantom{ } \\ \noindent \textit{Step 1}: Associate a divisor with each headstrong composition. Suppose $(c_1, c_2, \ldots, c_m)$ is a headstrong composition of $n+1$. We define the following two sets: \begin{align*} A &\eqdef \{n+1\} - \{c_1, (c_1+c_2), \ldots, (c_1+c_2+\cdots+c_m)\}\\ &=\{0, c_m, (c_m+c_{m-1}), \ldots, (c_m+c_{m-1}+\cdots+c_2)\};\\ B &\eqdef [c_1-1]. \end{align*} We claim that $A+B = [n]$. Indeed, it is clear that $A+B \subseteq [n]$. To prove the reverse inclusion, consider any $0\leq j\leq n$, and let $i$ be the smallest index $1 \leq i \leq m$ such that $(n+1)-(c_1+c_2+\cdots+c_i) \leq j$. Note that such an index $i$ always exists since $c_1+\cdots+c_m = n+1$ by the definition of a composition. Let $a$ denote $(n-1)-(c_1+\cdots+c_i)$, and we clearly have $a \in A$. Let $b$ denote $j-a$, and our task is now to prove that $b \in B$, for then we have $j = a+b$, and we are done. We distinguish between two cases: \begin{itemize} \item Suppose $i=1$, so $(n+1)-c_1 \leq j < n+1$, and subtracting $a$ from this inequality we find $0\leq b < c_1$, so that $b \in [c_1-1] = B$. \item Suppose $i>1$, so that by the minimality of $i$ we have \[(n+1) - (c_1+c_2+\cdots+c_i) \leq j < (n+1)-(c_1+c_2+\cdots+c_{i-1}),\] and subtracting $a$ from this inequality we fine $0 \leq b < c_i$. Since $(c_1, c_2, \ldots, c_m)$ is a headstrong composition we have $c_i \leq c_1$ so that $0 \leq b < c_1$ and once again $b \in [c_1-1] = B$. \end{itemize} \bigskip \noindent\textit{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, \ldots, a_\ell\}$ with $a_0a_0 = 0$ and therefore $a_r-1 \in [n] = A+B$, so we may choose some $a \in A$ and $b \in B$ such that $a+b = a_r-1$. Since $a < a_r$ and $a \in A$, we have $a\leq a_{r-1}$. Therefore, \[\max B+1 \geq b+1 = a_r-a \geq a_r-a_{r-1},\] as we wanted to prove. \bigskip \noindent \textit{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$. \end{proof} \begin{figure}[H] \centering \begin{tabular}{lcl} Headstrong compositions of $4$ & & Divisors of $[3]$\\ $(4)$ &$\leadsto$ &$\{0\}$;\\ $(3, 1)$ &$\leadsto$ &$\{0, 1\}$;\\ $(2, 2)$ &$\leadsto$ &$\{0, 2\}$;\\ $(2, 1, 1)$ &$\leadsto$ &$\{0, 1, 2\}$;\\ $(1, 1, 1, 1)$ &$\leadsto$ &$\{0, 1, 2, 3\}$. \end{tabular} \caption{Example of the correspondence between the $5$ divisors of $[3]$ and the $5$ headstrong compositions of $4$.} \label{fig:headstrongdivisors} \end{figure} As Applegate, LeBrun, and Sloane remarked \cite[Remark (i) following Theorem 16]{ALS11}, the bijection in the proof shows that the following corollary holds. It will be further used in Section \ref{sec:non0rooted} as it plays an important role in the proof of Conjecture \ref{conj:maxdb2}. \begin{corollary}\label{crl:cardinality} The number of divisors of $[n]$ whose cardinality is exactly $m$ equals the number of headstrong compositions of $n+1$ with exactly $m$ parts. \end{corollary} Headstrong compositions were first studied by Knopfmacher and Robbins \cite{KnRo05} 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\geq 1$, is given by the coefficient of $z^n$ in \[\sum_{\ell=1}^{\infty}\frac{(1-z)z^\ell}{1-2z+z^{\ell+1}}.\] (Here $\ell$ 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 $\ell$ is given by $F(\ell, n)$, the $n$-th element of the \demph{generalized Fibonacci sequence} $F(\ell, \cdot)$ defined by the recurrence relation \[F(\ell, n) = \begin{cases} 0, &\mbox{ if } 1 \leq n < \ell;\\ 1, &\mbox{ if } n=\ell;\\ \sum_{i=1}^{\ell}F(\ell, n-i), &\mbox{ if } n>\ell. \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 $\ell=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, \seqnum{A000045} in the OEIS \cite{OEIS}, is exactly $F(2, \cdot)$ according to the recurrence above. Similarly, $F(3, \cdot)$ are the so-called ``Tribonacci numbers'', \seqnum{A000073} in the OEIS \cite{OEIS}. Table \ref{tab:Fibonacci} below displays the first few entries of the table for $F(\ell, n)$, reproduced from the entry for the generalized Fibonacci sequence, \seqnum{A092921} in the OEIS \cite{OEIS}. \begin{table}[H] \centering \begin{adjustbox}{width=\columnwidth,center} \begin{tabular}{l|cccccccccc} $F(\ell, n)$& $n=1$ & $n=2$ & $n=3$ & $n=4$ & $n=5$ & $n=6$ & $n=7$ & $n=8$ & $n=9$ & $n=10$ \\ \hline $\ell=1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ & $1$ \\ $\ell=2$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ & $21$ & $34$ \\ $\ell=3$ & $0$ & $0$ & $1$ & $1$ & $2$ & $4$ & $7$ & $13$ & $24$ & $44$ \\ $\ell=4$ & $0$ & $0$ & $0$ & $1$ & $1$ & $2$ & $4$ & $8$ & $15$ & $29$\\ $\ell=5$ & $0$ & $0$ & $0$ & $0$ & $1$ & $1$ & $2$ & $4$ & $8$ & $16$\\ \end{tabular} \end{adjustbox} \caption{First entries of the table for the generalized Fibonacci sequence $F(\ell, n)$.}\label{tab:Fibonacci} \end{table} To obtain $d([n]) = d_2(11\cdots 1|_2)$ (with $n+1$ occurrences of $1$), simply sum the $(n+1)$-th column in Table \ref{tab:Fibonacci}. Note that this immediately implies that $d([n+1]) > d([n])$ for any natural number $n \in \N$. One can also prove that the number of headstrong compositions of $n$ with leading term $\ell$ is given by $F(\ell, n)$ without using generating functions by the following reasoning. Each headstrong composition of $n$ with leading term $\ell$ can be obtained by appending $1$ to the end of a headstrong composition of $n-1$ with leading term $\ell$; or by appending $2$ to the end of a headstrong composition of $n-2$ with leading term $\ell$; so on until we append $\ell$ to the end of a headstrong composition of $n-\ell$ with leading term $\ell$. 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 $\ell$ are obtained in this manner. In summary, the total number of headstrong compositions of $n$ is given by $\sum_{\ell=1}^{n}F(\ell, n) = \sum_{\ell\geq 1}F(\ell, 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. \begin{lemma}\label{lem:lowerbound} For $n \geq \ell$ we have $2F(\ell, n)\geq F(\ell, n+1)$, and the inequality is strict for $n \geq 2\ell$. \end{lemma} \begin{proof} Since the claim holds trivially for $\ell=1$, we may assume that $\ell \geq 2$. Since $F(\ell, \ell) = F(\ell, \ell+1) = 1$, the claim is clearly true for $n = \ell$. For $n>\ell$ we have by definition of $F(\ell, n)$: \begin{align*} F(\ell, n+1) &= \sum_{i=1}^{\ell}F(\ell, n+1-i)\\ &= F(\ell, n) + \sum_{i=1}^{\ell-1}F(\ell, n-i)\\ &= 2F(\ell, n) - F(\ell, n-\ell)\\ &\leq 2F(\ell, n), \end{align*} with strict inequality for $n \geq 2\ell$. \end{proof} Lemma \ref{lem:lowerbound} gives a lower bound on $F(\ell, n)$ in terms of the next element of the sequence, $F(\ell, n+1)$, and Lemma \ref{lem:upperbound} gives an upper bound; these lemmas together show that \begin{equation}\label{eq:fibinequality} \frac{1}{2}F(\ell, n+1) \leq F(\ell, n) \leq \frac{2}{3}F(\ell, n+1). \end{equation} Inequality \eqref{eq:fibinequality} will be used to show that $[k]\setminus\{0\}$ is $d(\cdot)$-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) \to 1/\phi$, where $\phi = (1+\sqrt{5})/2 \approx 1.618$ is the golden ration. By considering the characteristic equation of the linear recurrence, Wolfram \cite{Wol98} found that $F(\ell, n)/F(\ell, n+1) \to 1/r$, where $r$ is the single positive real root of $x^\ell - \sum_{i=0}^{\ell-1}x^i= 0$, though we shall not use this result. \begin{lemma}\label{lem:upperbound} For any $\ell > 1$ and $n > \ell$ we have $3F(\ell, n) \leq 2F(\ell, n+1)$. Equality holds if and only if $\ell=2$ and $n=4$. \end{lemma} \begin{proof} We have $F(2, 3) = 1$, $F(2, 4) = 2$, $F(2, 5) = 3$, which proves the claim for $\ell=2$ and $n \leq 4$. If $\ell=2$ and $n > 4$, then $n-1 \geq 2\ell$ so Lemma \ref{lem:lowerbound} shows that \[2F(\ell, n+1) = 2F(\ell, n)+2F(\ell, n-1) > 3F(\ell, n).\] Assume therefore that $\ell \geq 3$. If $n = \ell+1$ we have \[2F(\ell, \ell+2) = 4 > 3 = 3F(\ell, \ell+1).\] On the other hand, if $n \geq \ell+2$ we have by Lemma \ref{lem:lowerbound}: \begin{align*} 2F(\ell, n+1) &\geq 2F(\ell, n) + 2F(\ell, n-1) + 2F(\ell, n-2)\\ &\geq 3F(\ell, n)+2F(\ell, \ell)\\ &>3F(\ell, n). \end{align*} This completes the proof. \end{proof} \section{Divisors of non-$0$-rooted sets}\label{sec:non0rooted} Most of the groundwork for proving Theorem \ref{thm:maxdb2} 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: \begin{lemma}[\textrm{\cite[Lemma 15]{ALS11}}] If the base $b$ expansion of $n$ ends with exactly $r\geq 0$ zeros, so that $n = mb^r$, with $b\not|m$, then \begin{equation}\label{eq:trailing} d_b(n) = (r+1)d_b(m). \end{equation} \end{lemma} They give a short proof based on lunar arithmetic. For completeness, Lemma \ref{lem:shifting} proves the binary case in the language of sumsets. \begin{notation} We denote \[[k+]\eqdef [k]\setminus\{0\} = \{1, 2, \ldots, k\}.\] For any positive natural number $1 \leq k \in \N$, we let $\mcal{Z}_k^+$ denote the collection of sets of positive natural numbers whose maximal element is $k$: \[\mcal{Z}_k^+ \eqdef \st{A \subseteq \N}{\min A > 0, \max A = k}.\] Finally, we denote \[\mcal{Z}_{\leq k}^+\eqdef \Union_{0<\ell\leq k}\mcal{Z}_{\ell}^{+}.\] Note that we have a partition of $\pset{[k]}$, the collection of subsets of $[k]$, given by \[\pset{[k]} = \{\emptyset\} \dunion \mcal{Z}_{\leq k} \dunion \mcal{Z}_{\leq k}^+.\] (We use ``$\dunion$'' to denote disjoint union.) \end{notation} \begin{lemma}[Based on \textrm{\cite[Lemma 15]{ALS11}}]\label{lem:shifting} Let $A$ be a finite subset of $\N$, and let $r \eqdef \min A$. Then, \[d(A) = (r+1)d(A-\{r\}).\] \end{lemma} \begin{proof} Note that $A - \{r\} \in \mcal{Z}$ is a $0$-rooted set. Suppose $B, C$ are sets such that $B+C = A - \{r\}$. Then, for any $0 \leq s \leq 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 \leq s, s' \leq 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 \leq 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) \geq (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 \mapsto F - \min F$ maps divisors of $A$ to divisors of $A - \{r\}$. Since $0 \leq \min F \leq r$ (and $F \neq F'$ implies $F - \{s\} \neq F' - \{s\}$ for any $0 \leq s \leq r$), each divisor of $A - \{r\}$ is the image of at most $(r+1)$ divisors of $A$. That is, $d(A) \leq (r+1)d(A-\{r\})$. \end{proof} A particular case of Lemma \ref{lem:shifting} is the equality $d([k+]) = 2d([k-1])$, mentioned in the beginning of Section \ref{sec:count}. The following theorem implies that $[k+]$ has more divisors than any set in $\mcal{Z}_{\leq k}$. \begin{theorem}\label{thm:rootedandnonrooted} For any positive natural number $k \geq 1$ we have \[2d([k-1]) \geq d([k]),\] and the inequality is strict for $k>1$. \end{theorem} \begin{proof} Note that $d([0]) = 1$ and $d([1]) = 2$, which proves the claim for $k=1$. Assume therefore that $k \geq 2$. We have seen in Section \ref{sec:count} that \[d([k-1]) = \sum_{\ell=1}^{k}F(\ell, k).\] By Lemma \ref{lem:lowerbound} we have $2F(\ell, k) \geq F(\ell, k+1)$ so that \[2d([k-1]) - d([k]) = \sum_{\ell=1}^{k}(2F(\ell, k) - F(\ell, k+1)) - F(k+1, k+1).\] Now, $F(1, \cdot)$ 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]) = \sum_{\ell=2}^{k}(2F(\ell, k) - F(\ell, k+1)).\] Since $k \geq 2$ the sum is nonempty, and Lemma \ref{lem:lowerbound} 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. \end{proof} To show that $[k+]$ is the maximum of $d(\cdot)$ in $\mcal{Z}_{\leq k}^+$, we use Lemma \ref{lem:upperbound}. \begin{theorem}\label{thm:shiftingupperbound} For any $1 \leq r \leq k$ we have \[2d([k-1]) \geq (r+1)d([k-r]).\] Equality holds if and only if $r=1$, or $k=3$ and $r=2$. \end{theorem} \begin{proof} Since $d([0]), d([1]), d([2]) = 1, 2, 3$ respectively, it is easy to verify that the claim holds for $k \leq 3$. In particular, for $k=3$ and $r=2$ we have \[3d([1]) = 3\cdot 2 = 2\cdot 3 = 2d([2]).\] Suppose therefore that $k \geq 4$. The claim holds trivially with equality for $r=1$. We shall prove strict inequality holds for $r\geq 2$ by induction on $r$. To prove the base case $r=2$, recall that $F(1, \cdot) = F(k, k) = F(k, k+1) = 1$ (for any positive $k$). We have by Lemma \ref{lem:upperbound}: \begin{align*} 3d([k-2]) &= 3\sum_{\ell=1}^{k-1}F(\ell, k-1)\\ &=3+3+\sum_{\ell=2}^{k-2}3F(\ell, k-1)\\ &<2(F(1, k)+F(k-1, k)+F(k, k)) + \sum_{\ell=2}^{k-2}2F(\ell, k)\\ &=2\sum_{\ell=1}^{k}F(\ell, k)\\ &=2d([k-1]). \end{align*} (Note that the strict inequality is justified by Lemma \ref{lem:upperbound}, since the sum contains at least one element different from $F(2, 4)$.) For the induction step, suppose that for some $r\geq 2$ we know that for all $k\geq \max(4, r)$ we have $(r+1)d([k-r]) < 2d([k-1])$. Note that $3d([k-2])\leq 2d([k-1])$ for any $k \geq 2$ (it is only when we require the inequality to be strict that we need $k \geq 4$). Thus, if $r+1 \leq k$, we have \begin{align*} (r+2)d([k-r-1]) &= (r-1)d([k-r-1])+3d([k-r-1])\\ &\leq (r-1)d([k-r])+2d([k-r])\\ &=(r+1)d([k-r])\\ &<2d([k-1]). \end{align*} This completes the induction step. \end{proof} \begin{theorem}\label{thm:dmaxnon0} For any nonempty set $A \subsetneq [k+]$ we have \[d([k+]) \geq d(A),\] and the inequality is strict for $k \neq 3$. \end{theorem} \begin{proof} Let $a \eqdef \min A$, and note that $A \subsetneq [k+]$ implies $a \geq 1$. By Lemma \ref{lem:shifting} and Theorem \ref{thm:dmax0} we have \[d(A) = (a+1)d(A-\{a\}) \leq (a+1)d([\max A - \{a\}])\] and the inequality is strict if $A - \{a\} \neq [\max A - a]$. Moreover, $d([\max A - a]) \leq d([k-a])$ and the inequality is strict if $\max A \neq k$. Therefore, by Theorem \ref{thm:shiftingupperbound} we have \[d(A) \leq (a+1)d([k-a]) \leq 2d([k-1]) = d([k+]),\] and the inequality is strict if $k \neq 3$ and $a>1$. In summary, $d(A) \leq d([k+])$ and if $k \neq 3$ equality may only hold if $a = 1$, and $\max A = k$, and $A -\{1\} = [k-1]$; but this contradicts the assumption that $A \subsetneq [k+]$. This contradiction proves that the inequality is strict for $k \neq 3$. \end{proof} 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 \ref{conj:maxdb2}. \begin{theorem}\label{thm:maxdb2} For any natural number $k \geq 1$, the set $[k+]$ is the maximum of $d(\cdot)$ in $\pset{[k]}\setminus\{\emptyset\}$, and it is the unique maximum for $k \neq 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\cdots10|_2$, and it is the unique maximum for $n\neq 2,4$. \end{theorem} \begin{proof} By Lemma \ref{lem:shifting} we have $d([k+]) = 2d([k-1])$, and by Theorem \ref{thm:rootedandnonrooted} we have $2d([k-1]) \geq d([k])$ with strict inequality for $k>1$. By Theorem \ref{thm:dmax0} we know that $[k]$ is the unique maximum of $d(\cdot)$ in $\mcal{Z}_{\leq k}$, so we conclude that $d([k+]) \geq d(A)$ for any $A \in \mcal{Z}_{\leq k}$, and the inequality is strict for $k>1$. Next, Theorem \ref{thm:dmaxnon0} shows that for any $A \in \mcal{Z}_{\leq k}^+$ we have $d([k+]) \geq d(A)$, and the inequality is strict if $k \neq 3$ (and $A \neq [k+]$). Since $\pset{[k]} = \{\emptyset\} \dunion \mcal{Z}_{\leq k} \dunion \mcal{Z}_{\leq k}^+$, we conclude that $[k+]$ is the maximum of $d(\cdot)$ in $\pset{[k]}\setminus\{\emptyset\}$, and it is the unique maximum for $k \neq 1, 3$. \end{proof} \section{The triangle of headstrong compositions}\label{sec:headstrong} In Section \ref{sec:multisets} we prove Conjecture \ref{conj:maxdb3}. 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 \ref{thm:powers}. Theorem \ref{thm:powers} generalizes a result from Applegate, LeBrun, and Sloane \cite[Theorem 17]{ALS11}, 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 \seqnum{A007318} of the OEIS \cite{OEIS}. We are interested in the triangle of headstrong compositions, enumerated in sequence \seqnum{A184957} of the OEIS \cite{OEIS}. The first few rows of the triangle are reproduced in Table \ref{tab:headstrong}. We let $H(n, p)$ denote the number of headstrong $p$-compositions of the integer $n$. Recall from Section \ref{sec:count} that $F(\cdot, n)$ enumerates headstrong compositions by leading term, so summing the rows of table \ref{tab:headstrong} leads to the same result as summing the columns of table \ref{tab:Fibonacci}. Thus, we have the equality $\sum_{p=1}^n H(n, p) = \sum_{\ell=1}^{n}F(\ell, n)$, even though the rows and columns of these two tables do not in general agree. \begin{table}[H] \centering \begin{adjustbox}{width=\columnwidth,center} \begin{tabular}{l|ccccccccccc} $H(n, p)$& $p=1$ & $p=2$ & $p=3$ & $p=4$ & $p=5$ & $p=6$ & $p=7$ & $p=8$ & $p=9$ & $p=10$ \\ \hline $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$\\ \end{tabular} \end{adjustbox} \caption{Triangle of $H(n, p)$, the number of headstrong $p$-compositions of $n$.} \label{tab:headstrong} \end{table} We are after the following recurrence relation: \begin{theorem}\label{thm:recurrence} 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, &\mbox{ if } p > n;\\ 1, &\mbox{ if } p = n;\\ 1, &\mbox{ if } p=1. \end{cases}\] In all other cases, i.e., $n>p>1$, we have \begin{equation}\label{eq:recurrence} H(n, p) = \sum_{j=1}^{n-p}H(n-p, j){p-1\choose j-1}. \end{equation} \end{theorem} Before proving Theorem \ref{thm:recurrence}, let us explain its meaning in terms of the triangle of headstrong compositions, Table \ref{tab:headstrong}. 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: \N \to \R$, its \demph{first forward difference}, denoted $\Delta f$, is another function $\Delta f: \N \to \R$ defined by \[\Delta f(n) \eqdef f(n+1)-f(n).\] One then defines the \demph{$k$-th order first forward difference} recursively by \[\Delta^kf \eqdef \Delta(\Delta^{k-1}f).\] We can conveniently extend this notation by adopting the convention that $\Delta^0f = f$. Starting with the sequence given by the function $f$, and writing the sequence represented by $\Delta^kf$ in row $k$ we obtain the \demph{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) = \sum_{j=0}^{n}j^2$ the sequence of the sum of the first $n$ squares is shown in Table \ref{tab:difference}. \begin{table}[H] \centering \begin{tabular}{r|cccccccccccccccccc} $\Delta^0 f$ & $0$ & & $1$ & & $5$ & & $14$ & & $30$ & & $55$ \\ $\Delta^1 f$ & & $1$ & & $4$ & & $9$ & & $16$ & & $25$\\ $\Delta^2 f$ & & & $3$ & & $5$ & & $7$ & & $9$ \\ $\Delta^3 f$ & & & & $2$ & & $2$ & & $2$ \\ $\Delta^4 f$ & & & & & $0$ & & $0$ \end{tabular} \caption{Difference table for the sum of squares $f(n) = \sum_{j=0}^{n} j^2$.}\label{tab:difference} \end{table} 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 \cite{GKP94} for an introduction, and to Jordan's classic book \cite{Jor65} 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 $\Delta^{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 \ref{tab:difference} the first diagonal is $(0, 1, 3, 2, 0)$. In general, if the first diagonal is $(a_0, a_1, \ldots, a_m, 0)$ the sequence is given by \begin{equation}\label{eq:difference} f(n) = \sum_{j=0}^{m}a_j{n\choose j}. \end{equation} (Here we adopt the convention that ${n\choose j} = 0$ for $j>n$.) This formula, as well as the fact that $\Delta^{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 \ref{tab:difference} we obtain the familiar formula for the sum of the first $n$ squares: \[f(n) = 0{n\choose 0} + 1{n\choose 1} + 3{n\choose 2} + 2{n\choose 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 \ref{sec:count}, 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:\N\setminus\{0\} \to \R$, and Equation \eqref{eq:difference} will therefore take the form \begin{equation}\label{eq:difference1} f(n) = \sum_{j=0}^{m}a_j{n-1\choose j}. \end{equation} We are now in a position to explain the recurrence from Theorem \ref{thm:recurrence}. 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 \ref{tab:headstrong}, the triangle of headstrong $p$-compositions of $n$, as shown in Table \ref{tab:init}. 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), \ldots\] The corresponding sequence is given by the function $f(m) = H(r+m, m)$ for $m\geq1$. The recurrence formula in Theorem \ref{thm:recurrence} 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 \ref{tab:init}, we can recover the second diagonal from Equation \eqref{eq:difference1}. That is, entry $s$ in the sequence corresponding to the second diagonal will be given by the formula $1\cdot {s-1\choose 0}$, so the second diagonal is the constant sequence $1$, as shown in Table \ref{tab:init2}. 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\cdot{s-1\choose 0} + 1\cdot{s-1\choose 1} = s,\] as shown in Table \ref{tab:init3}. 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\cdot{s-1\choose 0}+1\cdot{s-1\choose 1}+1\cdot{s-1\choose 2} = \frac{s^2-s+2}{2},\] as shown in Table \ref{tab:init4}. In this manner one may recover the whole triangle $H(n, p)$ in Table \ref{tab:headstrong} from the initial data, and this is the claim in Theorem \ref{thm:recurrence}. \begin{table}[H] \centering \begin{subfigure}[b]{0.35\linewidth} \centering \begin{adjustbox}{width=1.1\columnwidth} \begin{tabular}{cccccc} $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$\\ \end{tabular} \end{adjustbox} \caption{Initial data.} \label{tab:init} \end{subfigure}\hfill \begin{subfigure}[b]{0.35\linewidth} \centering \begin{adjustbox}{width=1.1\columnwidth} \begin{tabular}{cccccc} $1$ & & & & & \\ $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$ \\ \end{tabular} \end{adjustbox} \caption{Filled $2$nd diagonal.} \label{tab:init2} \end{subfigure}\vspace{0.5cm} \begin{subfigure}[b]{0.35\linewidth} \centering \begin{tabular}{cccccc} $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$\\ \end{tabular} \caption{Filled $3$rd diagonal.} \label{tab:init3} \end{subfigure}\hfill \begin{subfigure}[b]{0.35\linewidth} \centering \begin{tabular}{cccccc} $1$ & & & & & \\ $1$ & $1$ & & & & \\ $1$ & $1$ & $1$ & & & \\ $1$ & $2$ & $1$ & $1$ & & \\ $1$ & $2$ & $3$ & $1$ & $1$ & \\ $1$ & $3$ & $4$ & $4$ & $1$ & $1$\\ \end{tabular} \caption{Filled table.} \label{tab:init4} \end{subfigure} \caption{Recovering the triangle $H(n, p)$ of headstrong $p$-compositions of $n$ from its initial data.} \label{tab:headstrongrecurrence} \end{table} In order to prove Theorem \ref{thm:recurrence} 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 \demph{Montmort-Moivre}\footnote{A similar formulation with a deck of cards is sometimes referred to as \demph{Simon Newcomb type problem}, popularized in \cite{Mac15}.} \demph{type problem}: consider $p$ urns, each containing $s$ balls labeled $1, \ldots, 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 \cite{Jor65}, and is expanded upon in an article by Charalambides \cite{Cha82}; we also refer the reader to the more recent work of Rao and Agarwal \cite{SrAg00} 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 \begin{align*} g(z) &= (z+z^2+\cdots + z^s)(z+z^2+\cdots + z^s)\cdots(z+z^2+\cdots +z^s)\\ &= z^p\frac{(1-z^s)^p}{(1-z)^p}. \end{align*} \begin{proof}[Proof of Theorem \ref{thm:recurrence}] 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 \eqref{eq:recurrence} for $n>p>1$. It is easy to see that for $p>1$ we have \[H(n, p) = \sum_{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)$: \begin{align*} f(z) = \sum_{s=1}z^sz^{p-1}\frac{(1-z^s)^{p-1}}{(1-z)^{p-1}} =\sum_{s=1}z^{p+s-1}\left(\frac{1-z^s}{1-z}\right)^{p-1}. \end{align*} 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$, \begin{align*} H(n, p) &=\sum_{j=1}H(n-p, j){p-1\choose j-1}\\ &=1+\sum_{j=2}H(n-p, j){p-1\choose j-1}\\ &=1+\sum_{j=2}\left({p-1\choose j-1}\sum_{s=1}C(n-p-s, j-1, s)\right), \end{align*} gives the generating function \[h(z) = z^p+\sum_{s=1}z^{p+s}+\sum_{j=2}\left({p-1\choose j-1}\sum_{s=1}z^{p+s}z^{j-1}\frac{(1-z^s)^{j-1}}{(1-z)^{j-1}}\right).\] (Note that the coefficient of $z^p$ accounts for the case $n = p$, while $\sum_{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 \begin{align*} h(z) &= z^p+\sum_{s=1}z^{p+s}\sum_{j=1}{p-1\choose j-1}\left(z\frac{1-z^s}{1-z}\right)^{j-1}\\ &= z^p+\sum_{s=1}z^{p+s}\left(1+z\frac{1-z^s}{1-z}\right)^{p-1}\\ &=\sum_{s=1}z^{p+s-1}\left(\frac{1-z^s}{1-z}\right)^{p-1}. \end{align*} That is, $h(z) = f(z)$, and the proof is complete. \end{proof} Using Theorem \ref{thm:recurrence} 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 \ref{conj:maxdb3}. \begin{corollary}\label{crl:rowsinequality} Let $b \geq 2$ be a natural number. Then, for any positive natural number $n$, \begin{equation}\label{eq:headstrongcoeffineq} \sum_{p=1}^{n+1}H(n+1, p)b^p>2\sum_{p=1}^{n}H(n, p)b^p. \end{equation} \end{corollary} \begin{proof} When $n=1$, the claim reduces to $2b 2$. For $n>p>0$ we have $n+1>p+1>1$, and applying Theorem \ref{thm:recurrence}: \begin{align*} H(n+1, p+1) &= \sum_{j=1}H(n-p, j){p\choose j-1}\\ &=\sum_{j=1}H(n-p, j){p-1\choose j-1}+\sum_{j=2}H(n-p, j){p-1\choose j-2}\\ &=H(n, p)+\sum_{j=2}H(n-p, j){p-1\choose j-2}. \end{align*} The last step is justified, since the recurrence formula in Equation \eqref{eq:recurrence} is valid in all cases where $n > p > 0$, including the case $p=1$ with the conventions ${0\choose 0} = 1$ and ${p\choose j} = 0$ for $j<0$. Note that the last summand is $0$ unless $n-\ell > 1$, reflecting the fact that $H(n+1, n) = H(n, n-1) = 1$; i.e., plug $p=n-1$ into Inequality \eqref{eq:headstrongcoeffineq} above. For convenience, let $h(n, p)$ denote the second summand: \[h(n, p) \eqdef \sum_{j=2}H(n-p, j){p-1\choose j-2}.\] We find that \begin{align*} \sum_{p=1}^{n+1}H(n+1, p)b^p &= b+\sum_{p=1}^{n}H(n+1, p+1)b^{p+1}\\ &=b+\sum_{p=1}^{n}(H(n, p)+h(n, p))b^{p+1}\\ &=b+b\sum_{p=1}^{n}H(n, p)b^p + b\sum_{p=1}^{n}h(n, p)b^p. \end{align*} By assumption, $b\geq 2$, and since all summands are nonnegative we have \begin{align*} \sum_{p=1}^{n+1}H(n+1, p)b^p &= b+b\sum_{p=1}^{n}H(n, p)b^p + b\sum_{p=1}^{n}h(n, p)b^p\\ &\geq b+b\sum_{p=1}^{n}H(n, p)b^p\\ &\geq b+2\sum_{p=1}^{n}H(n, p)b^p\\ &>2\sum_{p=1}^{n}H(n, p)b^p. \end{align*} This is exactly the inequality we wanted to prove. \end{proof} \section{Sumsets arrays}\label{sec:multisets} 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 \geq 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: \N \to \{0, 1\}$ that decides set-membership, i.e., $n$ is an element of the set if and only if $f(n) = 1$. \begin{definition} A \demph{multiset} of natural numbers is a function $f: \N \to \N$. We say that a natural number $n \in \N$ is an \demph{element} of the multiset, if $f(n) > 0$. We call the value $f(n)$ the \demph{multiplicity} of $n$. A multiset that is not a set, i.e., $f(n)>1$ for at least one $n\in \N$, is called a \demph{proper multiset}. \end{definition} All multisets in this section will be finite multisets of natural numbers. There is a grading of multisets by multiplicity. \begin{notation} For any natural number $b$, we let $\mcal{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, \[\mcal{M}^b \eqdef \st{f: \N \to \N}{f(\N) \subseteq [b], \mbox{ and } f(j) = 0 \mbox{ for all but finitely many $j \in \N$}}.\] Note that $\mcal{M}^1$ is simply the collection of finite subsets of natural numbers, while $\mcal{M}^0 = \{\emptyset\}$. We have the grading \[\mcal{M}^0 \subsetneq \mcal{M}^1 \subsetneq \mcal{M}^2 \subsetneq \cdots.\] We adopt the following notation, analogous to the notation from Section \ref{sec:arith}. For any natural number $k$, let $\mcal{M}_k$ denote the collection of multisets of natural numbers whose maximal element is $k$: \[\mcal{M}_k \eqdef \st{f: \N \to \N}{f(k)>0 \mbox{ and } f(j) = 0 \mbox{ for any } j>k}.\] For convenience we also introduce \[\mcal{M}_{\leq k} \eqdef \Union_{\ell \leq k}\mcal{M}_\ell,\] 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 $\mcal{M}$: \[\mcal{M}\eqdef \Union_{k \in \N}\mcal{M}_k.\] Finally, we may combine superscripts and subscripts, so that $\mcal{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$: \[\mcal{M}_k^b \eqdef \mcal{M}_k \insect \mcal{M}^b.\] Such a multiset $M \in \mcal{M}_k^b$ can be viewed as extending a function $f: [k] \to [b]$ to a multiset $f: \N \to \N$ by the rule that $f(j) = 0$ for any $j>k$. Note that we have the disjoint union: \[\mcal{M}^b\setminus\{\emptyset\} = \dUnion_{k \in \N}\mcal{M}_k^b.\] \end{notation} 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 \ref{def:multisumset} 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 \ref{def:multisumset} is most transparent when one views finite multisets as an array of sets, as in the following definition. \begin{definition} Let $b$ be a natural number, and $f \in \mcal{M}^b$ a multiset. The \demph{$b$-ary array representation} of $f$ is an ordered $b$-tuple of $(F_1, F_2, \ldots, F_b)$ where the coordinate $F_i$ (for $1 \leq i \leq b$) is defined as follows: for any natural number $n$, we have $n \in F_i$ if and only if $f(n) \geq i$. \end{definition} For ease of readability, it is often convenient to represent the array $(F_1, F_2, \ldots, 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 $\mcal{M}^2$, but it has the array representation $(\{1, 2\}, \{1\}, \emptyset)$ when viewed as a multiset in $\mcal{M}^3$. Note that one feature of the array representation is that the coordinates form a descending chain $F_1 \supseteq F_2 \supseteq \cdots \supseteq F_b$. We are now ready to define multisumsets, it is simply the coordinate-wise sumset operation. \begin{definition}\label{def:multisumset} Let $f, g \in \mcal{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 \in \mcal{M}^b$. Let $F = (F_1, F_2, \ldots, F_b)$ and $G = (G_1, G_2, \ldots, G_b)$ be the $b$-ary array representations for $f$ and $g$, respectively. The \demph{multisumset} of $f$ and $g$, denoted $f+g$, is the multiset corresponding to the array $F+G \eqdef (F_1 + G_1, F_2+G_2, \ldots, F_b + G_b)$. \end{definition} Figure \ref{fig:multisumset} gives an example of the multisumset operation, showing how it takes advantage of different ``multiplicity levels''. \begin{figure}[H] \centering \begin{subfigure}[b]{0.45\linewidth} \centering \[\begin{mx} \{1, 2\}\\ \{1\} \end{mx} + \begin{mx} \{2\} \\ \emptyset \end{mx} = \begin{mx} \{3, 4\}\\ \emptyset \end{mx}\] \caption{The multisumset $\{1, 1, 2\} + \{2\} = \{3, 4\}$.} \end{subfigure}\hfill \begin{subfigure}[b]{0.5\linewidth} \centering \[\begin{mx} \{1, 2\}\\ \{1\} \end{mx} + \begin{mx} \{2\} \\ \{2\} \end{mx} = \begin{mx} \{3, 4\}\\ \{3\} \end{mx}\] \caption{The multisumset $\{1, 1, 2\} + \{2, 2\} = \{3, 3, 4\}$.} \end{subfigure} \caption{Examples of the multisumset operation via the array representation of multisets, here displayed as column vectors.}\label{fig:multisumset} \end{figure} It is easy to see that the multisumset operation makes $\mcal{M}^b$ into a commutative monoid. We have a correspondence between the multisumset operation on $\mcal{M}^b$ and base $(b+1)$ lunar multiplication, extending Theorem \ref{thm:keycorrespondence}. Extending the notation of Theorem \ref{thm:keycorrespondence}, we let $\mcal{B}_{b+1}$ denote the set of base $(b+1)$ numbers, written using the digits in $\mcal{D}_{b+1} = \{0, 1, \ldots, b\}$. There is a natural bijection $\beta_{b+1}: \mcal{M}^b \to \mcal{B}_{b+1}$ based on the idea of encoding multiplicity as a base $(b+1)$ sequence. First, define $\beta_{b+1}(\emptyset) = 0|_{b+1}$. Next, let $f \in \mcal{M}^b$ be a finite nonempty multiset, and let $k$ be its maximal element, so $f\in\mcal{M}^b_{k}$. We define the base $(b+1)$ number $\beta_{b+1}(f)$ by encoding the multiplicity of each element \[\beta_{b+1}(f) \eqdef f(k)f(k-1)\cdots 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 \in \mcal{M}$, and let $b$ be the smallest natural number such that $f, g \in \mcal{M}^b$. The key observation, which we prove in Theorem \ref{thm:keygeneral}, is a generalization of Equation \eqref{eq:keycorrespondence}: \begin{equation}\label{eq:keygeneral} \beta_{b+1}(f+g) = \beta_{b+1}(f)\otimes_{b+1}\beta_{b+1}(g). \end{equation} Figure \ref{fig:keygeneral} shows an example of a multisumset in $\mcal{M}^9$ and the corresponding base $10$ lunar multiplication, demonstrating Equation \eqref{eq:keygeneral}. \begin{theorem}\label{thm:keygeneral} For any positive natural number $b$, the map $\beta_{b+1}: \mcal{M}^b \to \mcal{B}_{b+1}$ is a monoid-isomorphism between $\mcal{M}^b$ equipped with the multisumset operation, and base $(b+1)$ numbers equipped with lunar multiplication $\otimes_{b+1}$. \end{theorem} \begin{proof} Fix some positive natural number $b$. It is easy to see that the map $\beta_{b+1}$ is a bijection---for example, by considering the inverse map---so it remains to show it is a monoid-homomorphism. Let $\mathbf{0}$ denote the multiset $\{0, 0, \ldots, 0\}$ with $b$ repetitions of $0$. We have $\beta_{b+1}(\mathbf{0}) = b|_{b+1}$, which is the maximal digit in $\mcal{D}_{b+1}$. This shows that the neutral elements are mapped to each other. Next, let $f, g \in \mcal{M}^b$, and we need to prove that Equation \eqref{eq:keygeneral} 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 $\beta_{b+1}(f)\otimes_{b+1}\beta_{b+1}(g) = t$: \[f(r)\cdots f(0)|_{b+1}\otimes_{b+1}g(s)\cdots g(0)|_{b+1} = t_{r+s}\cdots t_0|_{b+1}.\] Let $F = (F_1, \ldots, F_b)$ be the set array representation of $f$, and let $G = (G_1, \ldots, 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 $\beta_{b+1}(f+g)$. By definition of the mapping $\beta_{b+1}$, for any $0 \leq j \leq r+s$, the $j$-th digit of $\beta_{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 \leq i \leq 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), \ldots, j+0.\] When constructing the set $F_1+G_1$, the specific sum $\ell+(j-\ell)$ (for $0\leq \ell\leq j$), in this specific order, appears as part of the construction if and only if $f(\ell) \geq 1$ and $g(j-\ell) \geq 1$. The specific sum $\ell+(j-\ell)$ appears in the construction of $F_2+B_2$ if and only if $f(\ell) \geq 2$ and $g(j-\ell)\geq 2$. In general, the specific sum $\ell+(j-\ell)$ will appear in the construction of $F_i+G_i$ for exactly $\min\{f(\ell), g(j-\ell)\}$-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)\}, \ldots, \min\{f(j), g(0)\}\}.\] However, by the definition of the lunar arithmetic operations, this is exactly \[t_j = (f(0)\otimes_{b+1}g(j))\oplus_{b+1}(f(1)\otimes_{b+1}g(j-1))\oplus_{b+1}\cdots\oplus_{b+1}(f(j)\otimes_{b+1}g(0)).\] This proves that $\beta_{b+1}(f+g) = \beta_{b+1}(f)\otimes_{b+1}\beta_{b+1}(g)$, as we wanted to show. \end{proof} \begin{figure}[H] \centering \begin{subfigure}[b]{0.35\linewidth} \centering \[ \begin{mx} \{0,1,2\} \\ \{0,1\} \\ \{0,1\} \\ \{0,1\} \\ \{0,1\} \\ \{0,1\} \\ \{0\} \\ \{0\} \\ \{0\} \end{mx} + \begin{mx} \{0,1,2\} \\ \{0,1,2\} \\ \{0,1\} \\ \{0,1\} \\ \{0\} \\ \{0\} \\ \{0\} \\ \{0\} \\ \emptyset \end{mx} = \begin{mx} \{0, 1, 2, 3, 4\} \\ \{0,1, 2, 3\} \\ \{0,1,2\} \\ \{0,1,2\} \\ \{0,1\} \\ \{0,1\} \\ \{0\} \\ \{0\} \\ \emptyset \end{mx} \] \caption{Multiset addition in $\mcal{M}^9$.} \end{subfigure}\hfill \begin{subfigure}[b]{0.35\linewidth} \centering \begin{tabular}{lr} & $169$ \\ $\otimes_{10}$ & $248$ \\ \hline & $168$ \\ $\oplus_{10}$ & $144$\stp \\ $\oplus_{10}$ & $122$\stp\stp \\ \hline &$12468$ \end{tabular} \caption{Base 10 lunar multiplication.} \end{subfigure} \caption{Two representations of multiset addition.}\label{fig:keygeneral} \end{figure} Having defined multisumset we can define divisors in a way analogous to Definition \ref{def:divisor}. \begin{definition}\label{def:multidivisor} Let $f\in\mcal{M}$ be a finite multiset of natural numbers. We say that the multiset $g \in \mcal{M}$ is a \demph{divisor} (or \demph{multisumset divisor}, or \demph{factor}) of $f$, if there exists some multiset $h\in\mcal{M}$ such that $f = g+h$. We then call $g+h$ a \demph{factorization} of $f$. \end{definition} 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, \ldots, 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 $\mcal{M}^b$. \begin{definition} Let $f \in \mcal{M}$ be a finite multiset of natural numbers, and let $b$ be a positive natural number. We say that the multiset $g \in \mcal{M}$ is a \demph{$b$-divisor} of $f$, if $g \in \mcal{M}^b$ and there exists some multiset $h \in \mcal{M}$ such that $f = g+h$. If $f \neq 0$ is not the constant $0$ function, we let $d_b(f)$ denote the number of $b$-divisors of $f$. \end{definition} 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 \notin \mcal{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 \in \mcal{M}^1$, then $d_1(f) = d(f)$ in agreement with Definition \ref{def:divisor}. Note that the notation $d_b(\cdot)$ 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 \in \mcal{M}^b$ is nonempty, Theorem \ref{thm:keygeneral} implies that \[d_b(f) = d_{b+1}(\beta_{b+1}(f)).\] Since any set is a divisor for $\emptyset$, an array with more empty entries will have more divisors, as is shown in the next lemma. \begin{lemma}\label{lem:empty} Let $b$ be a positive natural number, $f \in \mcal{M}^b$ a multiset, and $F = (F_1, F_2, \ldots, F_b)$ its $b$-ary array representation. Suppose $f \neq 0$ is not the constant zero function, so that $F_1 \neq \emptyset$. Let $f^* \in \mcal{M}^b$ be the multiset given by the $b$-ary array representation $F^* = (F_1, \emptyset, \ldots, \emptyset)$. Then $d_b(f^*) \geq d_b(f)$, and the inequality is strict if $F_2 \neq \emptyset$. \end{lemma} \begin{proof} Let $g \in \mcal{M}^b$ be a $b$-divisor of $f$, with array representation $G = (G_1, G_2, \ldots, G_b)$. That is, there exists some $h \in \mcal{M}^b$ with array representation $H = (H_1, H_2, \ldots, H_b)$ such that $f = g+h$, which means, by definition of the multisumset operation, $F = G+H$. Letting $h^* \in \mcal{M}^b$ denote the multiset given by the array representation $H^* = (H_1, \emptyset, \ldots, \emptyset)$ we have $f^* = g+h^*$. Thus, every $b$-divisor $g$ of $f$ is also a $b$-divisor of $f^*$. That is, $d_b(f^*) \geq d_b(f)$. If $F_2 \neq \emptyset$ then for any $b$-divisor $g$ of $f$ we must also have $G_2 \neq \emptyset$. 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)$. \end{proof} \begin{notation} Let $b$ be a positive natural number. We let $[k]_b$ denote the multiset $f \in \mcal{M}^b$ with $b$-ary array representation $([k], \emptyset, \ldots, \emptyset)$. \end{notation} The correspondence from Theorem \ref{thm:keygeneral} gives $\beta_{b+1}([k]_b) = 11\cdots1|_{b+1}$, where $1$ repeats $k+1$ times. Conjecture \ref{conj:maxdb3} states that this is the $d_{b+1}(\cdot)$-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\cdots1|_{b}$: \begin{theorem}{\textrm{\cite[Theorem 17]{ALS11}}} \begin{equation}\label{eq:ALST17} d_{b}\left(\frac{b^{k}-1}{b-1}\right) = d_{b}({\underbrace{11\ldots 1}_{k}}|_b) = \sum_{p=1}^{k}H(k, p)(b-1)^p. \end{equation} \end{theorem} Applegate, LeBrun, and Sloane calculated \cite[Table 10]{ALS11} the first few values of $d_b(11\cdots 1|_b)$, which we reproduce in Table \ref{tab:differentbases}. We have already remarked on the combinatorial nature of the first column of Table \ref{tab:differentbases} as counting headstrong compositions, sequence \seqnum{A079500} of the OEIS \cite{OEIS}. One wonders whether other columns have similarly interesting combinatorial interpretations. For example, the second column is sequence \seqnum{A186523} of the OEIS \cite{OEIS}, 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 \seqnum{A002378}, \seqnum{A027444}, and \seqnum{A186636} of the OEIS \cite{OEIS}, respectively. \begin{table}[H] \centering \begin{adjustbox}{width=1.0\columnwidth} \begin{tabular}{c|ccccccccc} & $b=2$ & $b=3$ & $b=4$ & $b=5$ & $b=6$ & $b=7$ & $b=8$ & $b=9$ & $b=10$\\ \hline $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$ \end{tabular} \end{adjustbox} \caption{The number of base $b$ lunar divisors of $11\cdots 1|_b$ with $k$ repetitions of the digit $1$. Reproduced from Applegate, LeBrun, and Sloane \cite[Table 10]{ALS11}.}\label{tab:differentbases} \end{table} Lemma \ref{lem:empty} shows that in order to prove the maximality of $d_b([k]_b)$ among sets in $\mcal{M}_{\leq k}^b$, it suffices to prove its maximality among sets of the form $(A, \emptyset, \ldots, \emptyset)$ with $A$ a finite nonempty subset such that $\max A \leq k$. Theorem \ref{thm:powers} 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 \ref{crl:cardinality}, Equation \eqref{eq:ALST17} is a special case of Equation \eqref{eq:powers}. \begin{theorem}\label{thm:powers} Let $b$ be a positive natural number, and let $f \in \mcal{M}^b$ be a nonempty set, i.e., not a proper multiset. Thus, $f$ has the $b$-ary array representation $F = (F_1, \emptyset, \ldots, \emptyset)$. Then, \begin{equation}\label{eq:powers} d_b(f) = \sum_{\mbox{\scriptsize $G$ {\rm divisor of} $F_1$}}b^{\crd{G}}. \end{equation} \end{theorem} \begin{proof} Let $S$ be a finite set of natural numbers, and let $c = \crd{S}$. Fix an enumeration $S = \{s_1, \ldots, s_c\}$ of the elements of $S$. Consider all possible descending chains of length $b$: \[S = S_1 \supseteq S_2 \supseteq \cdots \supseteq S_b.\] The question of which sets in the chain contain a given $s \in S$ is answered by a single number $1 \leq \ell\leq c$; namely, the largest natural number $\ell$ such that $s \in S_\ell$. Thus, each chain is uniquely identified with a sequence $(\ell_1, \ell_2, \ldots, \ell_c)$ where each entry $1 \leq \ell_i \leq 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 \supseteq G_2 \supseteq \cdots \supseteq G_b$ gives rise to a $b$-divisor $g$ of $f$ with the $b$-ary array representation $(G_1, G_2, \ldots, G_b)$, since \[(G, G_2, \ldots, G_b) + (H, \emptyset, \ldots, \emptyset) = (F_1, \emptyset, \ldots, \emptyset).\] Conversely, if $(G_1, G_2, \ldots, G_b)$ is the array representation of a $b$-divisor of $f$, then $$G_1 \supseteq G_2 \supseteq \cdots \supseteq G_b,$$ and $G_1$ is a divisor of $F_1$. \end{proof} Theorem \ref{thm:powers} allows us to carry over our knowledge of divisors of sumsets to divisors of multisumsets. For example, Theorem \ref{thm:dmax0} proves that $[k]$ is $d(\cdot)$-maximal in $\mcal{Z}_{\leq k}$, and Corollary \ref{crl:powers0rooted} is the corresponding statement for multisets. \begin{corollary}\label{crl:powers0rooted} Let $b$ be a positive natural number, and let $f \in \mcal{M}^b_{\leq k}$ be a nonempty $0$-rooted set, i.e., it has array representation $(A, \emptyset, \ldots, \emptyset)$ for some $A \in \mcal{Z}_{\leq k}$. Then $d_b(f) \leq d_b([k]_b)$, and the inequality is strict for $f \neq [k]_b$. \end{corollary} \begin{proof} The $k$-promotion procedure from Definition \ref{def:promotion} either adds elements to the promoted set, or leaves the set as is. Thus, with the notation as in Definition \ref{def:FAC}, for every divisor $C$ of $A$ there corresponds a divisor $C' \in F_{A}(C)$ of $[k]$ with $\crd{C'} \geq \crd{C}$, and Theorem \ref{thm:disjointfactors} shows that different divisors of $A$ give rise to different divisors of $[k]$. The claim now follows by Equation \eqref{eq:powers}, and the observation from Lemma \ref{lem:uniqueodd} and Lemma \ref{lem:uniqueeven} that there are divisors of $[k]$ that do not arise from $k$-promotion. \end{proof} Next, Corollary \ref{crl:shiftinggeneral} generalizes Lemma \ref{lem:shifting}, and gives a more explicit version of Equation \eqref{eq:trailing}. \begin{corollary}\label{crl:shiftinggeneral} Let $b$ be a positive natural number, and let $f \in \mcal{M}^b$ be a nonempty set, i.e., it has set array representation $(A, \emptyset, \ldots, \emptyset)$, for some finite nonempty set of natural numbers $A$. Let $a \eqdef \min A$. Then, \[d_b(f) = (a+1)\sum_{\mbox{\scriptsize $C$ {\rm divisor of} $A-\{a\}$}}b^{\crd C}.\] \end{corollary} \begin{proof} According to the proof of Lemma \ref{lem:shifting}, each divisor $C$ of $B - \{a\}$ gives rise to a divisor $B+\{s\}$ of $A$, for $0 \leq s \leq a$. Moreover, all divisors of $A$ are obtained in this manner. Since $\crd{B} = \crd{(B+\{s\})}$, we are done by Equation \eqref{eq:powers}. \end{proof} The stage is now set for proving the maximality of $d_b([k]_b)$ among all sets in $\mcal{M}_{\leq k}^b$. \begin{theorem}\label{thm:powersnon0rooted} Let $b$ be a positive natural number $b \geq 2$, and let $f \in \mcal{M}^b_{\leq k}$ be a nonempty set, i.e., $f$ has the set array representation $(A, \emptyset, \ldots, \emptyset)$ for some $A \in \mcal{Z}_{\leq k} \dunion \mcal{Z}^+_{\leq k}$. Then $d_b(f) \leq d_b([k]_b)$, and the inequality is strict for $f \neq [k]_b$. \end{theorem} \begin{proof} Let $a \eqdef \min A$. If $a = 0$, then $A \in \mcal{Z}_{\leq k}$ and the claim reduces to Corollary \ref{crl:powers0rooted}. Otherwise, $a>0$ so that $f \neq [k]_b$, and we have by Corollary \ref{crl:shiftinggeneral} \[d_b(f) = (a+1)\sum_{\mbox{\scriptsize $B$ {\rm divisor of} $A - \{a\}$}}b^{\crd B}.\] Let $n\eqdef \max A - a$, so that $A - \{a\} \in \mcal{Z}_{n}$. By Corollary \ref{crl:cardinality} we have \[d_b(f) = (a+1)\sum_{p=1}^{n}H(n, p)b^p.\] On the other hand, \[d_b([k]_b) = \sum_{p=1}^{k}H(n+a, p)b^{p} \geq \sum_{p=1}^{n+a}H(n+a, p)b^{p}.\] By Corollary \ref{crl:rowsinequality} we know that \[\sum_{p=1}^{n+1}H(n+1, p)b^p > 2\sum_{p=1}^{n}H(n, p)b^p,\] and by induction it follows that \begin{align*} \sum_{p=1}^{n+a}H(n+a, p)b^p &> 2^a\sum_{p=1}^nH(n, p)b^p\\ &\geq (a+1)\sum_{p=1}^{n}H(n, p)b^p. \end{align*} (The last inequality is valid since $a>0$, and $2^s \geq s+1$ for any $s\geq 1$.) We conclude that $d_b([k]_b) > d_b(f)$. \end{proof} We can now prove Conjecture \ref{conj:maxdb3}. \begin{theorem}\label{thm:maxdb3} Let $b, k$ be natural numbers such that $b \geq 2$, and let $f \in \mcal{M}^b_{\leq k}$ be a nonempty multiset, i.e., $f \neq 0$ is not the constant $0$ function. Then $d_b(f) \leq d_b([k]_b)$, and the inequality is strict if $f \neq [k]_b$. Equivalently, in any base $b+1 \geq 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\cdots 1|_{b+1}$ (with $k+1$ repetitions of the digit $1$). \end{theorem} \begin{proof} Let $F = (F_1, F_2, \ldots, F_b)$ be the array representation of $f$, and let $f^* \in \mcal{M}^b_{\leq k}$ be the multiset given by the $b$-ary array representation $F^* = (F_1, \emptyset, \ldots, \emptyset)$. Lemma \ref{lem:empty} gives $d_b(f^*) \geq d_b(f)$ and the inequality is strict if $F_2 \neq \emptyset$. Theorem \ref{thm:powersnon0rooted} then gives $d_b([k]_b) \geq d_b(f^*)$ and the inequality is strict if $f^* \neq [k]_b$. Thus, $d_b(f) \leq d_b([k]_b)$ and the inequality is strict if $f \neq [k]_b$. \end{proof} \section{Further questions}\label{sec:questions} We have found that $\{1, \ldots, k\}$ has the most additive divisors among all subsets of $\{0, 1, \ldots, 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 $\N$ correspond to binary lunar divisor, as proved in Theorem \ref{thm:keycorrespondence}. The setting of lunar arithmetic naturally inspires number-theoretic questions. This paper investigated divisibility questions for sumsets. Applegate, LeBrun, and Sloane \cite{ALS11} 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 \seqnum{A067398} of the OEIS \cite{OEIS}, mentioned briefly in Section 4 of Applegate, LeBrun, and Sloane's paper \cite[Section 4]{ALS11}. Two, irreducible finite subsets of $\N$, as defined in Definition \ref{def:divisor}, correspond to binary lunar primes, sequence \seqnum{A171000} of the OEIS \cite{OEIS}. Applegate, LeBrun, and Sloane investigated lunar primes in different bases \cite[Section 3]{ALS11}. We have mentioned in Section \ref{sec:intro} above Wirsing's proof \cite{Wir53} that almost all subsets of $\N$ are asymptotically irreducible. If we restrict our attention to finite subsets only, Applegate, LeBrun, and Sloane made a more precise conjecture: \begin{conjecture}[\textrm{\cite[Conjecture 10]{ALS11}}] Let $\pi_b(k)$ denote the number of base $b$ lunar primes with $k$ digits. Then, \[\pi_b(k) \sim (b-1)^2b^{k-2}.\] \end{conjecture} In particular, this predicts that about half of all subsets of $[k]$ are irreducible. Theorem \ref{thm:dmax0} undergirds many of the results of this paper, as the proofs of Theorem \ref{thm:maxdb2} and Theorem \ref{thm:maxdb3} proceed via reductions to the $0$-rooted case. The load-bearing part of the proof of Theorem \ref{thm:dmax0} is the $k$-promotion procedure from Definition \ref{def:promotion}. 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\}\subseteq \{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 \ref{conj:runnerupb2odd} regarding the runner-up to $d([k])$; the number of divisors of the runner-up is enumerated in sequence \seqnum{A188524} of the OEIS \cite{OEIS}. Is there a way to generalize the promotion procedure to other sets? Section \ref{sec:count} describes a bijection between divisors of $[k]$ and headstrong compositions, which is expanded upon in Section \ref{sec:headstrong}. 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 \ref{tab:differentbases}, such as sequence \seqnum{A186523} of the OEIS \cite{OEIS}? What about the rows of Table \ref{tab:differentbases}? These kind of questions may be another possible way of making inroads into resolving Conjecture \ref{conj:runnerupb2odd} via direct counting. Indeed, Applegate, LeBrun, and Sloane \cite[Theorem 18]{ALS11} 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) \to 1/5$. Sequence \seqnum{A188288} of the OEIS \cite{OEIS} enumerates $d_2(2^k-3)$. \section{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 \cite{Har18} 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. \begin{thebibliography}{99} \bibitem{ALS11} D.~Applegate, M.~LeBrun, and N.~J.~A.~Sloane, Dismal arithmetic, \emph{J.~Integer Sequences} {\bf 14} (2011), \href{https://cs.uwaterloo.ca/journals/JIS/VOL14/Sloane/carry2.html}{Article 11.9.8}. \bibitem{Cha82} Ch.~A.~Charalambides, On the enumeration of certain compositions and related sequences of numbers, \emph{Fibonacci Quart.} {\bf 20} (1982), 132--146. \bibitem{Els06} C.~Elsholtz, Additive decomposability of multiplicatively defined sets, \emph{Funct.~Approx.~Comment.~Math.} {\bf 35} (2006), 61--77. \bibitem{ErSz83} P.~Erd{\H o}s and E.~Szemer{\'e}di, On sums and products of integers, in P.~Erd{\H o}s, L.~Alp{\'a}r, G.~Hal{\'asz}, and A.~S{\'a}rk{\"o}zy, eds., \emph{Studies in Pure Mathematics}, Birkh{\"a}user, 1983, pp.\ 213--218. \bibitem{FrRi06} A.~Frosini and S.~Rinaldi, On the sequence \seqnum{A079500} and its combinatorial interpretations, \emph{J. Integer Sequences} {\bf 9} (2006), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Frosini/fros2.html}{Article 06.3.1}. \bibitem{GKP94} R.~L.~Graham, D.~E.~Knuth, and O.~Patashnik, \emph{Concrete Mathematics}, Addison-Wesley, 1994. \bibitem{Har18} B.~Haran, Primes on the moon (lunar arithmetic), video, 2018, \url{https://www.numberphile.com/videos/lunar-arithmetic}. \bibitem{HeMa10} S.~Heubach and T.~Mansour, \emph{Combinatorics of Compositions and Words}, CRC Press, 2010. \bibitem{Jor65} C.~Jordan, \emph{Calculus of Finite Differences}, Chelsea, 1965. \bibitem{KnRo05} A.~Knopfmacher and N.~Robbins, Compositions with parts constrained by the leading summand, \emph{Ars Combin.} {\bf 76} (2005), 287--295. \bibitem{Mac15} P.~A.~MacMahon, \emph{Combinatory Analysis I}, Cambridge University Press, 1915. \bibitem{Nat96} M.~B.~Nathanson, \emph{Additive Number Theory: The Classical Bases}, Springer, 1996. \bibitem{Nat96b} M.~B.~Nathanson, \emph{Additive Number Theory: Inverse Problems and the Geometry of Sumsets}, Springer, 1996. \bibitem{Ost56} H.~H.~Ostmann, \emph{Additive Zahlentheorie}, Springer, 1956. \bibitem{SrAg00} K.~Srinivasa Rao and A.~K.~Agarwal, On a generalized composition function, \emph{J.~Indian Math.~Soc.} {\bf 67} (2000), 99--106. \bibitem{OEIS} N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available at \url{https://oeis.org}. \bibitem{TaVu10} T.~Tao and V.~H.~Vu, \emph{Additive Combinatorics}, Cambridge University Press, 2010. \bibitem{Wir53} E.~Wirsing, Ein metrischer Satz {\"u}ber Mengen ganzer Zahlen, \emph{Arch.~Math.} {\bf 4} (1953), 392--398. \bibitem{Wol98} D.~A.~Wolfram, Solving generalized Fibonacci recurrences, \emph{Fibonacci Quart.} {\bf 36} (1998), 129--145. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11P70; Secondary 05A17, 05A19, 05A20, 11A63, 11B39. \noindent \emph{Keywords: } Sumset, Minkowski sum, lunar arithmetic, dismal arithmetic, carryless arithmetic, divisor, composition, restricted composition, generalized Fibonacci sequence, multiset. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000045}, \seqnum{A000073}, \seqnum{A002378}, \seqnum{A007059}, \seqnum{A007318}, \seqnum{A027444}, \seqnum{A067398}, \seqnum{A079500}, \seqnum{A092921}, \seqnum{A171000}, \seqnum{A184957}, \seqnum{A186523}, \seqnum{A186636}, \seqnum{A188288}, \seqnum{A188524}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 17 2020; revised versions received January 18 2020; August 6 2020; August 23 2020; October 17 2020. Published in {\it Journal of Integer Sequences}, October 18 2020. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}