<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}

\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}}}



\usepackage{cite}
\usepackage{authblk}
%\usepackage[ruled,vlined]{algorithm2e}
\usepackage{mathtools}
\usepackage{bm}
\usepackage[usenames]{color}

\usepackage{cleveref}



\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\abs}[1]{\left|#1\right|}

\newcommand{\E}{\mathbb E}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Ac}{\mathcal A}
\newcommand{\Lc}{\mathcal L}

\newcommand{\Dc}{\mathcal D}
\newcommand{\Ic}{\mathcal I}
\newcommand{\Hc}{\mathcal H}


\crefname{conjecture}{conjecture}{conjectures}
\Crefname{conjecture}{Conjecture}{Conjectures}

\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}

\begin{center}
\vskip 1cm{\Large\bf
Indecomposability Over the Max-Min Semiring
}
\vskip 1cm

\begin{minipage}{3in}
\begin{center}
Benjamin Baily\\
Department of Mathematics \\
University of Michigan \\
 530 Church Street \\
Ann Arbor, MI 48109 \\
USA \\
\href{mailto:bbaily@umich.edu}{\tt bbaily@umich.edu}\\
\end{center}
\end{minipage}\ \quad \
\begin{minipage}{3in}
    \begin{center}
        Justine Dell \\
Department of Mathematics \\
University of California San Diego\\
9500 Gilman Drive \\
La Jolla, CA 92093 \\
USA \\
\href{mailto:jsdell@ucsd.edu}{\tt jsdell@ucsd.edu}\\
    \end{center}
\end{minipage}
\vskip .15in

\begin{minipage}{3in}
\begin{center}
    Henry L. Fleischmann
 \\
Department of Computer Science \\
Carnegie Mellon University \\
5000 Forbes Avenue \\
Pittsburgh, PA 15213 \\
USA \\
\href{mailto:henryfl@umich.edu}{\tt henryfl@umich.edu} \\
\mbox{}\\
\end{center}
\end{minipage}\ \quad \
\begin{minipage}{3in}
    \begin{center}
        Faye Jackson and Ethan Pesikoff \\
Department of Mathematics \\
University of Chicago \\
5734 South University Avenue \\
Chicago, IL 60637 \\
USA \\
\href{mailto:alephnil@uchicago.edu}{\tt alephnil@uchicago.edu}\\\href{mailto:epesikoff@uchicago.edu}{\tt epesikoff@uchicago.edu} \\
    \end{center}
\end{minipage}
\vskip .15in

\begin{minipage}{3in}
    \begin{center}
        Steven J. Miller \\
Department of Mathematics and Statistics \\
Williams College \\
18 Hoxsey Street \\
Williamstown, MA 01267 \\
USA \\
\href{mailto:sjm1@williams.edu}{\tt sjm1@williams.edu}\\
    \end{center}
\end{minipage}\ \quad \
\begin{minipage}{3in}
    \begin{center}
        Luke Reifenberg \\
Department of Mathematics \\
University of Notre Dame \\
255 Hurley Building\\
Notre Dame, IN 46556 \\
USA \\
\href{mailto:lreifenb@nd.edu}{\tt lreifenb@nd.edu} \\
    \end{center}
\end{minipage}
\end{center}

\vskip .1 in

\begin{abstract}
    For sets $A, B\subset \N$, their sumset is $A + B := \{a+b: a\in A, b\in B\}$. If we cannot write a set $C$ as $C = A+B$ with $|A|, |B|\geq 2$, then we say that $C$ is (additively) \textit{indecomposable}. The question of whether a given set $C$ is indecomposable arises naturally in additive combinatorics. Equivalently, we can formulate this question as one about the indecomposability of Boolean polynomials, which has been discussed in previous work by Kim and Roush as well as Shitov.

    We use combinatorial and probabilistic methods to prove that almost all polynomials are indecomposable over the max-min semiring, generalizing work of Shitov and proving a conjecture by Applegate, LeBrun, and Sloane concerning lunar numbers.
\end{abstract}


\section{Introduction}\label{sec:intro}
Given a positive integer $b$, let $\Ac_b$ denote the set $\{0, \dots, b-1\}$ equipped with the operations $\oplus, \otimes$, where $t\oplus u = \max(t,u), t\otimes u = \min(t,u)$. Previous work \cite{KR05,Shi14} has discussed the factorization of polynomials over the \textit{Boolean semiring} $\Ac_2[x]$. Understanding the factorization of Boolean polynomials proves useful in both the classical setting of factoring polynomials over fields \cite{gao} as well as in tropical geometry \cite{speyer}. The study of factorization of Boolean polynomials corresponds naturally with the study of sumsets within additive combinatorics, an active area of research \cite{shkredov,granville}.

More generally, Applegate, LeBrun, and Sloane define a \textit{lunar number} to be an element of the polynomial semiring $\Ac_b[x]$. In this paper, we show that almost all lunar numbers are indecomposable, and as a consequence we confirm Applegate, LeBrun, and Sloane's conjectured estimate for the number of degree-$n$ lunar primes in base $b$.

\subsection{Preliminaries}

Since we deal with asymptotic estimates throughout this paper, we first adopt one standard notation for asymptotic analysis.
\begin{definition}
If $f, g$ are nonnegative real-valued functions and there exists a constant $C&gt;0$ such that $f \leq Cg$, then we write $f\lesssim g$.
\end{definition}
We now define the term \textit{lunar number}.
\begin{definition}
    The semiring $\Ac_b = (\{0,\dots, b-1\}, \oplus, \otimes)$ is defined by the operations
    \begin{align*}
        t \oplus u &amp;\coloneqq \max(t,u) \\
        t \otimes u &amp;\coloneqq \min(t,u),
    \end{align*}
    where $\{0,\dots, b-1\}$ is equipped with the usual linear order. The additive identity and multiplicative identity are $0_{\Ac_b} = 0$ and $1_{\Ac_b} = b-1$, respectively. The semiring of \textit{lunar numbers}, then, is the polynomial semiring $\Lc_b:= \Ac_b[x]$.

   For each $n\geq 0$, we define the set $\Lc_b^n\subseteq \Lc_b$ of lunar numbers of degree at most $n$:
   \[
   \Lc_b^n = \left\{\bigoplus_{i=0}^n a_ix^i \text{ such that }a_i\in \Ac_b \text{ for all }i\right\}.
   \]
   For example, we have $\Ac_b = \Lc_b^0$ and $\Lc_b = \bigcup_{n\geq 0}\Lc_b^n$.
\end{definition}

\begin{remark}
     Originally, Applegate, LeBrun, and Sloane referred to these elements as \textit{dismal numbers}. Finding the old name too depressing, the authors have since renamed these objects \textit{lunar numbers}. See the links section of \seqnum{A087636}.
\end{remark}

\begin{example}
    Working in $\Lc_3$, the product of $1 \oplus 2x$ with $2 \oplus 1x$ is
    \begin{align*}
        (1\oplus 2x) \otimes (2 \oplus 1x) = 1 \oplus (2x \oplus 1x) \oplus 1x^2 = 1 \oplus 2x \oplus 1x^2.
    \end{align*}
    Written in the notation of lunar arithmetic used by Applegate, LeBrun, and Sloane, this is
    \begin{center}
    \begin{tabular}{ccc}
        &amp; 2 &amp; 1  \\
        $\bm{\times}_3$ &amp; 1 &amp; 2  \\
        \hline
        &amp; 2 &amp; 1 \\
        1 &amp; 1 &amp; \\
        \hline
        1 &amp; 2 &amp; 1
    \end{tabular}
    \end{center}
    where $21$ represents the polynomial $1 \oplus 2x$.
\end{example}

\begin{definition}\label{defn:ind-prime}
    Let $f \in \Lc_b$. Provided that $h$ is not a \textit{unit} and that in every decomposition $h = f\otimes g$ for $f,g \in \Lc_b$ at least one of $f,g$ is a \textit{unit}, we say that $h$ is \textit{prime}. This corresponds to the definition of a \textit{lunar prime} given by Applegate, LeBrun, and Sloane \cite[p.\ 7]{ALS11}. A \textit{monomial} is an element of $\Lc_b$ of the form $tx^n$ for some $t\in \Ac_b, n\in \Z^{\geq 0}$. Provided that $h$ is not a \textit{monomial} and that in every decomposition $h = f\otimes g$ for $f,g \in \Lc_b$ at least one of $f,g$ is a \textit{monomial}, we say that $h$ is \textit{indecomposable}.
\end{definition}
\begin{remark}
If $h$ is a lunar prime that is not a monomial, then $h$ is also indecomposable by definition. On the other hand, there is only one prime monomial in $\Lc_b$: the monomial $(b-1)x$. Therefore, to bound the number of lunar primes, it suffices to bound the number of indecomposable lunar numbers.
\end{remark}
\begin{example}\label{example:ind}
    Fix a base $b\geq 2$. First, we see that $1 \oplus x \oplus x^2$ is decomposable in $\Lc_b$, since
    \[
        (1 \oplus x) \otimes (1 \oplus x) = 1 \oplus x \oplus x \oplus x^2 = 1 \oplus x \oplus x^2.
    \]
    In contrast, $1 \oplus x \oplus x^3$ is indecomposable.
\end{example}

The question of whether a polynomial is indecomposable within $\Lc_2$ corresponds precisely to whether a certain subset of $\N$ is indecomposable as a sumset. We recall the definition of the sum of $A,B \subseteq \Z$ and indecomposability of sets below.
\begin{definition}\label{defn:sumset}
    Let $A, B\subset G$ for some Abelian group $G$. Their \textit{sumset} is the set $A+B \coloneqq \{a+b: a\in A, b\in B\}$.
\end{definition}
\begin{definition}[see {\cite[Definition 3]{Gro19}}]\label{defn:irreducible}
Let $S\subset \N$ such that $S\neq \emptyset$. If $S = A+B$ implies either $A$ or $B$ is a singleton, then $S$ is indecomposable.
Note that in Gross's thesis \cite{Gro19}, indecomposability is referred to as Ostmann irreducibility.
% \footnote{In Gal Gross's paper, indecomposability is referred to as Ostmann irreducibility.}

\end{definition}
With these definitions in mind, one may associate with a finite nonempty subset $A \subseteq \N$ the polynomial $\sum_j 1_A(j) x^j$, where $1_A(j) = 1$ if $j \in A$, and $1_A(j) = 0$ if $j \not\in A$. Then the semiring $\Lc_2$ is isomorphic to the semiring of finite subsets of $\N$ under union and set addition \cite{Gro19}. Under this isomorphism, the notion of indecomposability of a polynomial exactly matches that of indecomposability of a set.


Furthermore, just as products of Boolean polynomials correspond to sums of sets, products of min-max polynomials correspond to sums of \textit{multisets}. Gal Gross has previously provided a full account of this correspondence \cite{Gro19}.


\subsection{Summary of results}

In 2008, Shitov studied the proportion of degree $n$ polynomials over $\Ac_2$ which are prime.
\begin{theorem}[Shitov {\cite[Theorem~2.5]{Shi14}}]\label{thm:Shitov}
    As $n\to \infty$, the proportion of degree $n$ polynomials in $\Lc_2$ with nonzero constant term which are prime tends to 1.
\end{theorem}
\Cref{thm:Shitov} answers a question of K. H. Kim and F. W. Roush posed in 2005 \cite{KR05}. Remarkably, the proof uses only elementary combinatorics and probability. In particular, Hoeffding's inequality plays a key role in the proof, allowing Shitov to control the degrees of the factors making up composite polynomials. Our contribution is to generalize Shitov's result to the setting of lunar arithmetic in higher bases.
\begin{theorem}\label{thm:gen-Shitov}
Fix an integer $b\geq 2$. Then as $n\to \infty$, the proportion of polynomials in $\Lc_b^n$ which are indecomposable tends to 1.
\end{theorem}
The proportion of polynomials in $\Lc_b^n$ which have degree $n$ is $\frac{b-1}{b}$, so \Cref{thm:gen-Shitov} is equivalent to the statement that the proportion of degree $n$ polynomials in $\Lc_b$ which are indecomposable tends to 1. \Cref{thm:gen-Shitov} implies a conjecture of Applegate, LeBrun, and Sloane concerning lunar primes \cite{ALS11} as a corollary.
\begin{corollary}[Applegate et al.\ {\cite[Conjecture~1]{ALS11}}]\label{conj:lunar-prime-conj}
Let $\pi_b(n)$ denote the number of degree $n-1$ prime lunar numbers in $\Lc_b$. Then, for fixed $b \geq 2$, we have the asymptotic estimate $\pi_b(n)\sim (b-1)^2b^{n-2}$ as $n \to \infty$.
\end{corollary}
In \Cref{sec:Shitov}, we prove \Cref{thm:gen-Shitov} by partitioning the collection of decomposable polynomials in $\Lc_b^n$ into several subcollections and bounding the size of each. We do this by applying Hoeffding's inequality and a generalization of one of Shitov's lemmas \cite[Lemma~2.6]{Shi14}. We then prove \Cref{conj:lunar-prime-conj} as a consequence of \Cref{thm:gen-Shitov} in \Cref{subs:lunar}.



\section{Indecomposability in \texorpdfstring{$\Lc_b^n$}{Lbn}}\label{sec:Shitov}
We begin with some conventions.

\begin{definition}
    Let $f\in \Lc_b$. Then $\abs{f}$ denotes the number of nonzero coefficients of $f$.
\end{definition}

\begin{definition}[Applegate, LeBrun, and Sloane {\cite[p.\ 6]{ALS11}}]\label{defn:digit-map}
    A \textit{base-$b$ digit map} is a nondecreasing function from $\Ac_b$ to itself. Let $d$ be a digit map such that $d(0) = 0$. If we set $b' = d(b-1) + 1$, we have $d(b) = 1_{\Ac_{b'}}$. Consequently, by restricting the codomain to $\Ac_{b'}$, we obtain a semiring homomorphism.

    Moreover, such a digit map extends naturally to a map $d: \Lc_b\to \Lc_{b'}$ by the rule
    \[
    d\left(\bigoplus_{i=0}^n a_ix^i\right) = \bigoplus_{i=0}^n d(a_i)x^i.
    \]
    This theory can be extended to include all nondecreasing functions from $\N\cup \{\infty\}$ to itself, though we do not need this extended notion for our application.
\end{definition}
\begin{theorem}[Applegate, LeBrun, and Sloane {\cite[Thm.\ 3]{ALS11}}]\label{thm:prime-promotion}
    If $d$ is a base-$b$ digit map and $f,g\in \Lc_b$, then
    \[
    d(f)\oplus d(g) = d(f\oplus g) \text{ and } d(f)\otimes d(g) = d(f\otimes g).
    \]
\end{theorem}
 \Cref{thm:prime-promotion} provides a framework for our proof, allowing us to reduce the problem of factoring polynomials over $\Lc_b$ to factoring polynomials over $\Lc_2$.

\begin{definition}\label{defn:canonical-digit-maps}
    Fix an integer $b\geq 2$. We define the digit maps $s_i$ for each $1\leq i\leq b-1$.
    \begin{align}
        s_i(n)\ :=\ \begin{cases}
        0, &amp; n &lt; i;\\
        1, &amp; n \geq i.
        \end{cases}
    \end{align}
As discussed in \Cref{defn:digit-map}, these digit maps extend naturally to maps $s_i: \Lc_b\to \Lc_2$. For $f\in \mathcal \Lc_b$, we additionally define $f_i = s_i(f)$. These polynomials, which can be thought of as the ``$i$-level support of $f$'', are indicator functions for where the coefficients of $f$ are at least $i$.
\end{definition}
\begin{remark}
By Shitov's result, almost all degree-$n$ polynomials in $\Lc_2$ are indecomposable.  Additionally, for $h\in \Lc_b$, we have that $h = f\otimes g$ implies $h_1 = f_1\otimes g_1$, and $f_1,g_1$ are monomials if and only if $f,g$ are. As a consequence, if $h_1$ is indecomposable, so is $h$. If the polynomials $h_1$ were uniformly distributed in $\Lc_2^n$, then we would have
\[\mathrm{Prob}(\{f\in \Lc_b^n: f\text{ indecomposable}\}) \geq \mathrm{Prob}(\{g\in \Lc_2^n: g\text{ indecomposable}\}),\]
where the probability measure is the uniform measure on the finite set $\Lc_b^n$. The polynomials $h_1$, however, are not uniformly distributed in $\Lc_2^n$. Hoeffding's inequality and its corollary \cref{eqn:hoeffding-support} imply that if $f$ is a random degree-$n$ polynomial in $\Lc_b$, the polynomial $f_1$ will almost surely have approximately $\frac{(b-1)(n+1)}{b}$ nonzero coefficients, whereas a degree-$n$ polynomial chosen uniformly from $\Lc_2$ will have approximately $\frac{n+1}{2}$ nonzero coefficients. In fact, polynomials with more nonzero coefficients are much more likely to be decomposable.

Instead, we consider the polynomials $f_a$, where $a = \floor{b/2}$. When $b = 2a$, \Cref{thm:gen-Shitov} is a corollary of \Cref{thm:Shitov} and \Cref{lemma:close-factors-2}. When $b = 2a+1$, \Cref{thm:gen-Shitov} is not a direct corollary of \Cref{thm:Shitov}, but our proof is along the lines of Shitov's argument.
\end{remark}


To conclude our setup, we use the following convention for referencing the coefficients of polynomials. Throughout the remainder of this paper, let
\begin{align*}
    f\ =\ \bigoplus_{k=0}^\infty \alpha_kx^k,\ \,\ \, g\ =\ \bigoplus_{k=0}^{\infty} \beta_kx^k,\ \,\ \, h\ =\ \bigoplus_{k=0}^\infty \gamma_kx^k,\ \,\ \, \sigma = \bigoplus_{k=0}^\infty \delta_kx^k,
\end{align*}
for notational convenience. Additionally, set $\alpha'_i = \alpha_i\otimes 1$ and similarly for each other coefficient. This way we have, for instance:
\[
f_1\ =\ \bigoplus_{k=0}^\infty \alpha'_kx^k,\ \,\ \, g_1\ =\ \bigoplus_{k=0}^{\infty} \beta'_kx^k,\ \,\ \, h_1\ =\ \bigoplus_{k=0}^\infty \gamma'_kx^k,\ \,\ \, \sigma_1 = \bigoplus_{k=0}^\infty \delta'_kx^k.
\]
We may now begin in earnest. In the proof of one lemma, Shitov shows the following statement, which will be of great use to us.
\begin{corollary}[Shitov {\cite[p.\ 1185]{Shi14}}]\label{cor:close-factors}
 For $d\in \R^+$, the number of pairs of Boolean polynomials $(f,g)$ satisfying the following conditions is at most $n^{2d+1}2^{\gcd(k,n)}$.
\begin{enumerate}
    \item The constant terms of $f,g$ are nonzero;
    \item $\deg f = k &gt; 0, \deg g = n-k$;
    \item $\abs{f\otimes g} \leq \abs{f} + \abs{g} + d$.
\end{enumerate}
\end{corollary}


We now generalize \Cref{cor:close-factors} to our setting.

\begin{lemma}\label{lemma:close-factors-2}
    The number of pairs of Boolean polynomials $(f,g)$ satisfying the following conditions is at most $n^{2d+2}2^k$ for every $d&gt;0$.
    \begin{enumerate}
        \item The constant term of $f$ is nonzero;
        \item $\deg f = k&gt;0, \deg g = n-k$;
        \item $\abs{f\otimes g} \leq \abs{f} + \abs{g} + d$.
    \end{enumerate}
\end{lemma}

\begin{proof}
     Write $g = x^j\otimes (1 + \cdots + x^{n-k-j})$ and define $\bar g$ by $g = x^j\otimes \bar g$. Then clearly $\abs{f\otimes g} = \abs{f\otimes \bar g}$ and $\abs{g} = \abs{\bar g}$. By \Cref{cor:close-factors}, there are at most $n^{2d+1}2^{\gcd(k,n-j)}$ pairs $(f,\bar g)$ satisfying the hypotheses of the corollary. Since there are at most $n$ choices for $j$, the number of pairs $(f,g)$ satisfying the hypotheses of this lemma is at most $\sum_{j=0}^{n-1} n^{2d+1}2^{\gcd(k,n-j)} \leq n^{2d+2}2^k$.
\end{proof}

The final ingredient for our proof is Hoeffding's inequality.

\begin{proposition}[Hoeffding's Inequality {\cite[Thm.\ 2]{Hoe63}}]
Let $X_n$ be a sum of $n$ independent Bernoulli random variables $X$ with $\E[X] = p$. Then $\mathrm{Prob}(\abs{X_n-np} &gt; \epsilon n) \leq 2e^{-2\epsilon^2 n}$.
\end{proposition}

When we choose a degree $n-1$ polynomial $f$ uniformly at random from $\Lc_b$, the quantity $\abs{f_i}$ is a sum of $n$ independent Bernoulli random variables $Z_i$ with $\mathbb E[Z_i] = \frac{b-i}{b}$. As a consequence, if $f$ is a degree $n-1$ polynomial chosen uniformly from $\Lc_b$, then
\begin{equation}\label{eqn:hoeffding-support}
 \mathrm{Prob}\left(\abs{\abs{f_i}- \frac{(b-i)n}{b}} &gt; \epsilon n\right) \leq 2e^{-2\epsilon^2n}.
\end{equation}
We now prove a quantitative version of \Cref{thm:gen-Shitov}. Let $\Sigma_b^n$ denote the set of decomposable lunar numbers of base $b$ and degree at most $n$.
\begin{proposition}\label{prop:quantitative-gen-Shitov}
Fix $b,n\geq 2$ and let $a = \lfloor b/2\rfloor$. Then for every $d,v&gt;0$ we have
\begin{align*}
    \abs{\Sigma_b^n}\ \lesssim b^{n+1}\ \left (n^2e^{\frac{-d^2}{4(n+2)}} + n^{2d+4}2^{\frac{d}{2}-\frac{n+1}{3}}+ vn^{2d+2}2^vb^{\frac{d}{2}-\frac{n}{b}} + n^22^{-v} \right).
\end{align*}
\end{proposition} We partition $\Sigma_b^n$ into two subsets, then control the size of each. Let $\Dc_b^n\subseteq \Sigma_b^n$ denote the set of $h$ that admit a factorization $h = f\otimes g$ such that $f_a,g_a$ are not monomials and let $\Ic_b^n = \Sigma_b^n\setminus \Dc_b^n$.
\begin{remark}
    When $b = 2a$, the size of $\Dc_b^n$ is easy to control. As each $h\in \Dc_b^n$ has a factorization $h = f\otimes g$ such that $h_a=f_a\otimes g_a$ is nontrivial, we have that $s_a(\Dc_b^n)\subseteq\Sigma_2^n$ (though the inclusion may be strict, as $h_a = \overline{f}\otimes \overline{g}$ may not lift to a factorization of $h$). As the cardinality of $s_a^{-1}(f)$ is $a^{n+1}$ for all $f\in \Lc_2^n$, we have
    \[
    \frac{|\Dc_b^n|}{b^n} \leq \frac{|s_a^{-1}(\Sigma_2^n)|}{b^n} = \frac{a^{n+1}|\Sigma_2^n|}{b^n} = \frac{a|\Sigma_2^n|}{2^n},
    \]
    a quantity which goes to zero as a consequence of \Cref{thm:Shitov}.
\end{remark}
\begin{definition}
    Let $d\in \mathbb{R}^+$. A polynomial $h\in \Lc_b^n$ is $d$-\textit{Hoeffding extremal} if there exists $1\leq i\leq b-1$ such that
    \begin{equation}\label{eq:extremal}
        \abs{|h_i| - \frac{(b-i)n}{b}} &gt; \frac{d}{2},
    \end{equation}
or if $h$ admits a factorization $h = f\otimes g$ such that
\begin{equation}\label{eq:extremal-2}
        \abs{|f_i| + |g_i| - \frac{(b-i)(n+1)}{b}} &gt; \frac{d}{2}.
    \end{equation}
Let $\Hc_b^n(d)$ denote the set of all $h\in \Lc_b^n$ that are $d$-Hoeffding extremal.
\end{definition}
We will show individually that $\Hc_b^n(d), \Dc_b^n\setminus \Hc_b^n(d)$, and $\Ic_b^n\setminus \Hc_b^n(d)$ are small, from which it follows that $\Sigma_b^n$ is small.
\begin{lemma}
    For fixed $b$ and all $d\in \R^+$, we have $|\Hc_b^n(d)| \lesssim n^2e^{\frac{-d^2}{4(n+2)}}b^n$.
\end{lemma}
\begin{proof}
    Let $i\in \{1,\ldots, b\}$. By \Cref{eqn:hoeffding-support} with $\epsilon = \frac{d}{2(n+1)}$, the number of polynomials $h$ satisfying \Cref{eq:extremal} for a given value of $i$ is at most $e^{\frac{-d^2}{4(n+1)}}b^{n+1}$. To bound the number of $h = f\otimes g$ such that $h$ is $d$-Hoeffding extremal due to \Cref{eq:extremal-2}, it suffices to bound the number of pairs $(f,g)$ such that $\deg f\otimes g\leq n$  and $(f_i,g_i)$ satisfies \Cref{eq:extremal-2}.

    For each $m\leq n$, we bound the number of pairs $(f,g)$ with $\deg f\otimes g = m$. If we fix $\deg f = k$, then we must have $\deg g = m-k$ as $\deg (f\otimes g) = m$. The set of pairs $(f,g)\in (\Lc_b)^2$ such that $\deg f = k, \deg g = m - k$ is in bijection with $\Lc_b^{m+1}$ with the bijection given below:
         \begin{align*}
            \phi(f,g) &amp; \ =\  f \oplus \left(((b-1) x^{k+1})\otimes g\right)\\
            \phi^{-1}(h) &amp;\ = \ \left(\bigoplus_{j=0}^k \gamma_jx^j, \bigoplus_{j=k+1}^{m+1} \gamma_jx^{j-k-1}\right).
         \end{align*}
         Moreover, $\abs{f_i} + \abs{g_i} = \abs{(\phi(f,g))_i}$.
         Thus, choosing $\epsilon = \frac{d}{2(m+2)}$ and applying \Cref{eqn:hoeffding-support}, we obtain that there are at most $2e^{\frac{-d^2}{4(m+2)}}b^{m+2}$ such pairs $(f,g)$ with $\deg f = k, \deg g = m-k$. As there are $m$ choices for $\deg f$, $b$ choices for $i$, and $n$ choices for $m$, we have
         \[
         |\Hc_b^n| \leq e^{\frac{-d^2}{4(n+1)}}b^{n+1} + \sum_{m=1}^n 2me^{\frac{-d^2}{4(m+2)}}b^{m+3} \lesssim \sum_{m=1}^n me^{\frac{-d^2}{4(m+2)}}b^{m+1} \leq n^2e^{\frac{-d^2}{4(n+2)}}b^{m+1}.
         \]
\end{proof}
\begin{lemma}
    If $h = f\otimes g\in \Sigma_b^n\setminus \Hc_b^n(d)$ and $1\leq i\leq b-1$, then $|h_i| \leq |f_i| + |b_i|+ d$.
\end{lemma}
\begin{proof}
We have $\abs{h_i} &lt; \frac{(b-a)(n+1)}{b} + d/2$ and $\abs{f_a} + \abs{g_a} &gt; \frac{(b-a)(n+2)}{b} - d/2 \geq |h_i| - d$.
\end{proof}
\begin{lemma}
    For fixed $b$ and all $d&gt;0$, we have $|\Dc_b^n\setminus \Hc_b^n(d)|\leq n^{2d+4}2^{\frac{d}{2}-\frac{n}{3}}b^{n+1}$.
\end{lemma}
\begin{proof}
    Let $h\in \Dc_b^n\setminus \Hc_b^n(d)$ and fix a nontrivial factorization $h_a = f_a\otimes g_a$. We count the number of pairs $(f_a, g_a)$ with $\deg h_a = m$ for each $2\leq m\leq n$. Since $h$ is not $d$-Hoeffding extremal, we have $\abs{h_a}\leq \abs{f_a} + \abs{g_a} + d$. It follows that the pair $(f_a,g_a)$ satisfies the hypotheses of \Cref{lemma:close-factors-2}. Being non-monomials, $f_a,g_a$ must both have positive degree, so $\deg f = m-\deg g \leq m-1$. Using the fact that $\gcd(\deg f_a, m) \leq \frac{m}{2}$ for $1\leq \deg f_a\leq m-1$, the number of possible choices for $h_a$ is at most
         \[\sum_{\deg f_a = 1}^{m-1} m^{2d+2}2^{\gcd(\deg f_a,m)} \ \leq\ m^{2d+3}2^{\frac{m}{2}}.\]
         The total number of possibilities for $h_a$, therefore, is bounded by
         \[
         \sum_{m=2}^n m^{2d+3}2^{\frac{m}{2}} \leq n^{2d+4}2^{\frac{n}{2}}.
         \]
         Once $h_a$ is known, if $\abs{h_a} = k$, there are $a^{n+1-k}(b-a)^k$ choices for $h$. This is because each 0 coefficient of $h_a$ can correspond to any coefficient in $\{0,\ldots, a-1\}$, and each 1 corresponds to a coefficient in $\{a, \ldots, b-1\}$. Let $s$ denote the quantity $\frac{(b-a)(n+1)}{b} + d/2$. As $h$ is not $d$-Hoeffding extremal, we have $k\leq s$.
        Recalling that $a = \floor{b/2}$, we have $a \leq b/2\leq (b-a)$, with equality of all terms when $b$ is even, we see that the quantity $a^{n+1-k}(b-a)^k$ is maximized when $k$ is maximized. This gives the following upper bound:
         \begin{align*}
          a^{n+1-k}(b-a)^k&amp;\ \leq\ a^{n+1-s}(b-a)^s\ =\
        a^{\frac{n+1}{2}}(b-a)^{\frac{n+1}{2}}\left(\frac{b-a}{a}\right)^{\left(\frac{b-a}{b}-\frac{1}{2}\right)(n+1)} \left(\frac{b-a}{a}\right)^{\frac{d}{2}}.
         \end{align*}
        By the AM-GM inequality, we have $a^{\frac{n+1}{2}}(b-a)^{\frac{n+1}{2}}\leq \left(\frac{b}{2}\right)^{n+1}$. For $b\geq 2$, we have the bounds $1\leq \frac{b-a}{a}\leq 2$ and $0\leq \frac{b-a}{b} - \frac{1}{2} \leq \frac{1}{6}$,
        thus for every $b\geq 2$ we have $\left(\frac{b-a}{a}\right)^{(\frac{b-a}{b}-\frac{1}{2})(n+1)}\leq 2^{\frac{n+1}{6}}$. Altogether, this yields
        \begin{align*}
            \abs{\Dc_b^n\setminus \Hc_b^n(d)} &amp;\ \leq\ n^{2d+4}2^{\frac{n}{2}}\left(\frac{b}{2}\right)^{n+1} \left(\frac{b-a}{a}\right)^{\frac{d}{2}}\left(\frac{b-a}{a}\right)^{(\frac{b-a}{b}-\frac{1}{2}){n+1}} \\
            &amp;\leq  n^{2d+4}2^{\frac{n}{2}}\left(\frac{b}{2}\right)^{n+1} 2^{\frac{n+1}{6}+\frac{d}{2}} \leq n^{2d+4}2^{\frac{d}{2}-\frac{n}{3}}b^{n+1}.
        \end{align*}
\end{proof}
\begin{lemma}\label{lem:low-deg}
    For all $d,v\in \R^+$, the number of lunar numbers in $\Sigma_b^n\setminus \Hc_b^n(d)$ that can be factored as $h = f\otimes g$ where $\deg f\leq v$ is at most $vn^{2d+3}2^v(b-1)^{\frac{(b-1)n}{b} + \frac{d}{2}}$.
\end{lemma}
\begin{proof}
    Let $h\in \Ic_b^n\setminus \Hc_b^n(d)$ such that $\deg h = m$. Let $h = f\otimes g$ be a nontrivial factorization where $\deg f \leq v$. As $h$ is not $d$-Hoeffding extremal and $f_1,g_1$ are both not monomials, the factorization $h_1 = f_1\otimes g_1$ satisfies the hypotheses of \Cref{lemma:close-factors-2}. Applying \Cref{lemma:close-factors-2} once for each choice of $1\leq k\leq v$, we conclude that the number of possible pairs $(f_1,g_1)$ with $\deg h_1 = m$ is at most $\sum_{k=1}^v m^{2d+2}2^{\gcd(k, m)}\leq vm^{2d+1}2^v$. Summing over all possible values of $m$, the number of pairs $(f_1,g_1)$ is at most
    \[
    \sum_{m=2}^n vm^{2d+2}2^v \leq vn^{2d+3}2^v.
    \]
    Each pair $(f_1,g_1)$ corresponds to $(b-1)^{|f_1| + |g_1|}$ possible pairs $(f,g)$, and since $(f_1,g_1)$ do not satisfy \Cref{eq:extremal-2}, the claim follows.
\end{proof}
\begin{lemma}
    For all $d,v\in \R^+$, we have $|\Ic_b^n\setminus \Hc_b^n(d)| \lesssim vn^{2d+2}2^vb^{\frac{(b-1)n}{b} + \frac{d}{2}} + n^22^{-v}b^{n+1}$.
\end{lemma}
\begin{proof}
    For fixed $k$, there are at most $(k+1)(a-1)^kb$ possible lunar numbers $f$ with $\deg f \leq k$ and $|f_a| \leq 1$: pick the index of the coefficient with no constraint, then pick its value from $\{0,\dots, b-1\}$, then pick the remaining coefficients from $\{0,\dots, a-1\}$. Additionally, there are $b^{n+1-k}$ lunar numbers $g$ of degree $\leq n-k$. It follows that there are at most $(k+1)a^kb^{n-k+2}$ lunar numbers $h$ such that $\deg h\leq n, h = f\otimes g, \deg f = k,$ and $|f_a| \leq 1$. As
    \[
    \sum_{k=v}^n (k+1)a^kb^{n-k+2} \leq n(n+1)(a-1)^vb^{n-v+2} \lesssim n^2b^{n+1}2^{-v},
    \]
    the claimed bound follows from \Cref{lem:low-deg}.
\end{proof}
These bounds lead to an immediate proof of \Cref{prop:quantitative-gen-Shitov}. With the right choice of $d,v$, this gives us a proof of \Cref{thm:gen-Shitov}.

\begin{proof}
     Our goal is to show that ${\abs{\Sigma_{b,n}}}/{b^{n+1}}\to 0$, from which the result follows. Setting $d = 2\sqrt{n+2}\log n$ and $v = 3\log_2 n$, we then apply \Cref{prop:quantitative-gen-Shitov} to conclude $|\Sigma_{b,n}|/b^{n+1}\to 0$ for fixed $b$ as $n\to \infty$.

\end{proof}

\subsection{Proof of Conjecture \ref{conj:lunar-prime-conj}}\label{subs:lunar}
We are now prepared to state and prove \Cref{conj:lunar-prime-conj} using \Cref{thm:gen-Shitov}. Recall from \Cref{defn:ind-prime} the distinction between a prime polynomial (one factor is always a \textit{unit}) and an indecomposable polynomial (one factor is always a \textit{monomial}). Applegate, LeBrun, and Sloane discuss prime polynomials, but primality and indecomposability are sufficiently similar that our results can be applied to the conjecture \cite{ALS11}. These authors instead use the term \textit{pseudoprime} to refer to indecomposability. We choose to use the term indecomposability for its relation to ring theory more generally.

Motivating their conjecture, Applegate et al.\ observed that only certain polynomials can be prime by leveraging the fact that $b-1$ is the only unit in $\Lc_b$.
\begin{definition}\label{defn:prime-candidate}
    A \textit{prime candidate} of $\Lc_b$ is a polynomial with nonzero constant term and maximum coefficient $b-1$.
\end{definition}

It is easy enough to see that a lunar number is prime only if it is a prime candidate. If $h = a_jx^j \oplus \cdots \oplus a_{n-1}x^{n-1}$ for $j&gt;1$, then $h = (b-1)x^j\otimes (a_j \oplus \cdots \oplus a_{n-1}x^{n-j-1})$ which is a nontrivial factorization in their convention. Moreover, if $c&lt;b-1$ is the maximum coefficient of $h$, then $h = c\otimes h$.

They showed that, if $\pi^{\text{cand}}_b(n)$ is the number of prime candidates in base $b$ with degree $n-1$, then ${\pi^{\text{cand}}_b(n)} \sim {(b-1)^2b^{n-2}}$. Furthermore, their data suggests that almost all prime candidates are in fact prime as $n\to \infty$. See OEIS sequences \seqnum{A169912} and \seqnum{A087636} for the number of prime elements of $\Lc_2^n$ and $\Lc_{10}^n$. As evidence for this fact, Applegate et al.\ produced the following lower bound:
\begin{equation*}
    (b-1)^{n-2} + 2(b-2)^{n-2} + \cdots \leq \pi_b(n).
\end{equation*}
Moreover, they observed the following, which we re-prove here.
\begin{lemma}[Applegate, LeBrun, and Sloane {\cite[p.\ 10]{ALS11}}]\label{lemma:irreducible-prime-candidate}
    An indecomposable prime candidate is prime.
\end{lemma}
\begin{proof}
     If $h$ is indecomposable, then $h = fg$ implies either $f,g$ is a monomial. Without loss of generality, assume that $f$ is a monomial. Since the constant term of $h$ is nonzero, we must have that $f$ is a constant. Since the maximum coefficient of $h$ is $b-1$, we must also have that $f = b-1$, thus $h$ is prime.
\end{proof}
With this lemma, \Cref{conj:lunar-prime-conj} is a simple corollary of \Cref{thm:gen-Shitov}.

\begin{proof}
     For fixed $b$, the proportion of prime candidates of $\Lc_b^n$ which are decomposable is at most a quantity which vanishes as $n\to\infty$:
     \begin{equation}\label{eqn:vanishing-candidates}
         \frac{\pi_b(n)}{(b-1)^2b^{n-2}}\leq \frac{\abs{\Sigma_b^{n-1}}}{(b-1)^2b^{n-2}} \lesssim  \frac{\abs{\Sigma_b^{n-1}}}{b^n} \to 0.
     \end{equation}It follows that almost all prime candidates are prime.
\end{proof}


\section{Acknowledgments}
The authors of this work were supported by NSF grants DMS1561945 and DMS1659037. We thank the other participants of the 2021 Williams SMALL REU for constructive comments. Thanks to Leo Goldmakher for helpful feedback throughout. Thanks also to the referees for valuable feedback across several versions which allowed us to greatly simplify the article. Finally, we are grateful to the OEIS \cite{oeis}, in particular sequence \seqnum{A169912}, without which we may never have made the connection between lunar arithmetic and sumsets which inspired this project.


\begin{thebibliography}{10}

\bibitem{ALS11}
David~L. Applegate, Marc LeBrun, and Neil J.~A. Sloane, Dismal arithmetic, {\em
  J. Integer Sequences} {\bf 14} (2011), 
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL14/Sloane/carry2.html}{Article 11.9.8}.

\bibitem{gao}
Shuhong Gao and Alan G.~B. Lauder, Decomposition of polytopes and polynomials,
  {\em Discrete Comput. Geom.} {\bf 26} (2001), 89--104.

\bibitem{granville}
Andrew Granville and Aled Walker, A tight structure theorem for sumsets, {\em
  Proc. Amer. Math. Soc.} {\bf 149} (2021), 4073--4082.

\bibitem{Gro19}
Gal Gross, Maximally additively reducible subsets of the integers, Master's
  thesis, University of Toronto (Canada), 2019.

\bibitem{Hoe63}
Wassily Hoeffding, Probability inequalities for sums of bounded random
  variables, {\em J. Amer. Statist. Assoc.} {\bf 58} (1963), 13--30.

\bibitem{KR05}
Ki~H. Kim and Fred~W. Roush, Factorization of polynomials in one variable over
  the tropical semiring, arxiv preprint arXiv:math/0501167 [math.CO], 2005.
\newblock \url{https://arxiv.org/abs/math/0501167}.

\bibitem{oeis}
{OEIS Foundation Inc.}, The {O}n-{L}ine {E}ncyclopedia of {I}nteger
  {S}equences, 2025.
\newblock Published electronically at \url{https://oeis.org}.

\bibitem{Shi14}
Yaroslav Shitov, How many boolean polynomials are irreducible?, {\em Internat.
  J. Algebra Comput.} {\bf 24} (2014), 1183--1189.

\bibitem{shkredov}
Ilya~D. Shkredov, Any small multiplicative subgroup is not a sumset, {\em
  Finite Fields Appl.} {\bf 63} (2020), 101645.

\bibitem{speyer}
David Speyer and Bernd Sturmfels, Tropical mathematics, {\em Math. Mag.} {\bf
  82} (2009), 163--173.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11B13; Secondary 15A80.

\noindent \emph{Keywords: }
sumset, irreducible set, lunar arithmetic.
\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A087636} and \seqnum{A169912}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 2 2023;
revised versions received 
January 3 2023; March 25 2024; March 2 2025; March 11 2025.
Published in {\it Journal of Integer Sequences}, March 26 2025.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}  
</pre></body></html>