Indecomposability Over the Max-Min Semiring

Benjamin Baily Department of Mathematics

University of Michigan 530 Church Street Ann Arbor, MI 48109

USA

bbaily@umich.edu

Justine Dell Department of Mathematics University of California San Diego 9500 Gilman Drive La Jolla, CA 92093 USA

                                jsdell@ucsd.edu

Henry L. Fleischmann Department of Computer Science

Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213

USA

henryfl@umich.edu

Faye Jackson and Ethan Pesikoff Department of Mathematics University of Chicago 5734 South University Avenue Chicago, IL 60637 USA

                             alephnil@uchicago.edu
                             epesikoff@uchicago.edu

Steven J. Miller Department of Mathematics and

Statistics Williams College 18 Hoxsey Street

Williamstown, MA 01267

USA

sjm1@williams.edu

Luke Reifenberg Department of Mathematics University of Notre Dame 255 Hurley Building Notre Dame, IN 46556 USA

                                lreifenb@nd.edu

Abstract

For sets A, B ⊂ ℕ, their sumset is A + B := {a + b : a ∈ A, b ∈ B}. If we cannot write a set C as C = A + B with |A|, |B| ≥ 2, then we say that C is (additively) 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.

1 Introduction

Given a positive integer b, let A_{b} denote the set {0, …, b − 1} equipped with the operations ⊕, ⊗, where t ⊕ u = max(t, u), t ⊗ u = min(t, u). Previous work [6, 8] has discussed the factorization of polynomials over the Boolean semiring A_{2}[x]. Understanding the factorization of Boolean polynomials proves useful in both the classical setting of factoring polynomials over fields [2] as well as in tropical geometry [10]. The study of factorization of Boolean polynomials corresponds naturally with the study of sumsets within additive combinatorics, an active area of research [3,9].

More generally, Applegate, LeBrun, and Sloane define a lunar number to be an element of the polynomial semiring A_{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.

1.1 Preliminaries

Since we deal with asymptotic estimates throughout this paper, we first adopt one standard notation for asymptotic analysis.

Definition 1. If f, g are nonnegative real-valued functions and there exists a constant C > 0 such that f ≤ Cg, then we write f ≲ g.

We now define the term lunar number.

Definition 2. The semiring A_{b} = ({0, …, b − 1}, ⊕, ⊗) is defined by the operations

t ⊕ u := max(t, u)
t ⊗ u := min(t, u),

where {0, …, b − 1} is equipped with the usual linear order. The additive identity and multiplicative identity are 0_{A_{b}} = 0 and 1_{A_{b}} = b − 1, respectively. The semiring of lunar numbers, then, is the polynomial semiring L_{b} := A_{b}[x].

For each n ≥ 0, we define the set L_{b}^{n} ⊆ L_{b} of lunar numbers of degree at most n:

L_{b}^{n} = {⨁_{i=0}^{n} a_{i}x^{i} such that a_{i} ∈ A_{b} for all i} .

For example, we have A_{b} = L_{b}^{0} and L_{b} = ⋃_{n≥0} L_{b}^{n}.

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

Example 4. Working in L_{3}, the product of 1 ⊕ 2x with 2 ⊕ 1x is

(1 ⊕ 2x) ⊗ (2 ⊕ 1x) = 1 ⊕ (2x ⊕ 1x) ⊕ 1x^{2} = 1 ⊕ 2x ⊕ 1x^{2}.

Written in the notation of lunar arithmetic used by Applegate, LeBrun, and Sloane, this is

\begin{aligned}& 2 & 1 \\ ×_{3} & 1 & 2 \\ & 2 & 1 \\ 1 & 1 \\ 1 & 2 & 1 \end{aligned}

where 21 represents the polynomial 1 ⊕ 2x.

Definition 5. Let f ∈ L_{b}. Provided that h is not a unit and that in every decomposition h = f ⊗ g for f, g ∈ L_{b} at least one of f, g is a unit, we say that h is prime. This corresponds to the definition of a lunar prime given by Applegate, LeBrun, and Sloane [1, p. 7]. A monomial is an element of L_{b} of the form tx^{n} for some t ∈ A_{b}, n ∈ ℤ^{≥0}. Provided that h is not a monomial and that in every decomposition h = f ⊗ g for f, g ∈ L_{b} at least one of f, g is a monomial, we say that h is indecomposable.

Remark 6. 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 L_{b}: the monomial (b − 1)x. Therefore, to bound the number of lunar primes, it suffices to bound the number of indecomposable lunar numbers.

Example 7. Fix a base b ≥ 2. First, we see that 1 ⊕ x ⊕ x^{2} is decomposable in L_{b}, since

(1 ⊕ x) ⊗ (1 ⊕ x) = 1 ⊕ x ⊕ x ⊕ x^{2} = 1 ⊕ x ⊕ x^{2}.

In contrast, 1 ⊕ x ⊕ x^{3} is indecomposable.

The question of whether a polynomial is indecomposable within L_{2} corresponds precisely to whether a certain subset of ℕ is indecomposable as a sumset. We recall the definition of the sum of A, B ⊆ ℤ and indecomposability of sets below.

Definition 8. Let A, B ⊂ G for some Abelian group G. Their sumset is the set A + B := {a + b : a ∈ A, b ∈ B}.

Definition 9 (see [4, Definition 3]). Let S ⊂ ℕ such that S ≠ ∅. If S = A + B implies either A or B is a singleton, then S is indecomposable. Note that in Gross’s thesis [4], indecomposability is referred to as Ostmann irreducibility.

With these definitions in mind, one may associate with a finite nonempty subset A ⊆ ℕ the polynomial ∑_{j} 1_{A}(j)x^{j}, where 1_{A}(j) = 1 if j ∈ A, and 1_{A}(j) = 0 if j ∉ A. Then the semiring L_{2} is isomorphic to the semiring of finite subsets of ℕ under union and set addition [4]. 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 multisets. Gal Gross has previously provided a full account of this correspondence [4].

1.2 Summary of results

In 2008, Shitov studied the proportion of degree n polynomials over A_{2} which are prime.

Theorem 10 (Shitov [8, Theorem 2.5]). As n → ∞, the proportion of degree n polynomials in L_{2} with nonzero constant term which are prime tends to 1.

Theorem 10 answers a question of K. H. Kim and F. W. Roush posed in 2005 [6]. 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.

Theorem 11. Fix an integer b ≥ 2. Then as n → ∞, the proportion of polynomials in L_{b}^{n} which are indecomposable tends to 1.

The proportion of polynomials in L_{b}^{n} which have degree n is \frac{b−1}{b}, so Theorem 11 is equivalent to the statement that the proportion of degree n polynomials in L_{b} which are indecomposable tends to 1. Theorem 11 implies a conjecture of Applegate, LeBrun, and Sloane concerning lunar primes [1] as a corollary.

Corollary 12 (Applegate et al. [1, Conjecture 1]). Let π_{b}(n) denote the number of degree n − 1 prime lunar numbers in L_{b}. Then, for fixed b ≥ 2, we have the asymptotic estimate π_{b}(n) ∼ (b − 1)^{2}b^{n−2} as n → ∞.

In Section 2, we prove Theorem 11 by partitioning the collection of decomposable polynomials in L_{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 [8, Lemma 2.6]. We then prove Corollary 12 as a consequence of Theorem 11 in Section 2.1.

2 Indecomposability in L_{b}^{n}

We begin with some conventions.

Definition 13. Let f ∈ L_{b}. Then |f| denotes the number of nonzero coefficients of f.

Definition 14 (Applegate, LeBrun, and Sloane [1, p. 6]). A base-b digit map is a nondecreasing function from A_{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_{A_{b′}}. Consequently, by restricting the codomain to A_{b′}, we obtain a semiring homomorphism.

Moreover, such a digit map extends naturally to a map d : L_{b} → L_{b′} by the rule

d (⨁_{i=0}^{n} a_{i}x^{i}) = ⨁_{i=0}^{n} d(a_{i})x^{i}.

This theory can be extended to include all nondecreasing functions from ℕ ∪ {∞} to itself, though we do not need this extended notion for our application.

Theorem 15 (Applegate, LeBrun, and Sloane [1, Thm. 3]). If d is a base-b digit map and f, g ∈ L_{b}, then

d(f) ⊕ d(g) = d(f ⊕ g) and d(f) ⊗ d(g) = d(f ⊗ g).

Theorem 15 provides a framework for our proof, allowing us to reduce the problem of factoring polynomials over L_{b} to factoring polynomials over L_{2}.

Definition 16. Fix an integer b ≥ 2. We define the digit maps s_{i} for each 1 ≤ i ≤ b − 1.

s_{i}(n) := \begin{cases}0, & n < i; \\ 1, & n ≥ i. \end{cases}  (1)

As discussed in Definition 14, these digit maps extend naturally to maps s_{i} : L_{b} → L_{2}. For f ∈ L_{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.

Remark 17. By Shitov’s result, almost all degree-n polynomials in L_{2} are indecomposable. Additionally, for h ∈ L_{b}, we have that h = f ⊗ g implies h_{1} = f_{1} ⊗ 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 L_{2}^{n}, then we would have

Prob({f ∈ L_{b}^{n} : f indecomposable}) ≥ Prob({g ∈ L_{2}^{n} : g indecomposable}),

where the probability measure is the uniform measure on the finite set L_{b}^{n}. The polynomials h_{1}, however, are not uniformly distributed in L_{2}^{n}. Hoeffding’s inequality and its corollary eq. (2) imply that if f is a random degree-n polynomial in L_{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 L_{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 = ⌊b/2⌋. When b = 2a, Theorem 11 is a corollary of Theorem 10 and Lemma 19. When b = 2a + 1, Theorem 11 is not a direct corollary of Theorem 10, but our proof is along the lines of Shitov’s argument.

To conclude our setup, we use the following convention for referencing the coefficients of polynomials. Throughout the remainder of this paper, let

f = ⨁_{k=0}^{∞} α_{k}x^{k}, g = ⨁_{k=0}^{∞} β_{k}x^{k}, h = ⨁_{k=0}^{∞} γ_{k}x^{k}, σ = ⨁_{k=0}^{∞} δ_{k}x^{k},

for notational convenience. Additionally, set α′_{i} = α_{i} ⊗ 1 and similarly for each other coefficient. This way we have, for instance:

f_{1} = ⨁_{k=0}^{∞} α′_{k}x^{k}, g_{1} = ⨁_{k=0}^{∞} β′_{k}x^{k}, h_{1} = ⨁_{k=0}^{∞} γ′_{k}x^{k}, σ_{1} = ⨁_{k=0}^{∞} δ′_{k}x^{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. Corollary 18 (Shitov [8, p. 1185]). For d ∈ ℝ^{+}, the number of pairs of Boolean polynomials (f, g) satisfying the following conditions is at most n^{2d+1}2^{gcd(k,n)}.

1. The constant terms of f, g are nonzero;

2. deg f = k > 0, deg g = n − k;

3. |f ⊗ g| ≤ |f| + |g| + d.

We now generalize Corollary 18 to our setting. Lemma 19. The number of pairs of Boolean polynomials (f, g) satisfying the following conditions is at most n^{2d+2}2^{k} for every d > 0.

1. The constant term of f is nonzero;

2. deg f = k > 0, deg g = n − k;

3. |f ⊗ g| ≤ |f| + |g| + d. Proof. Write g = x^{j} ⊗ (1 + ⋯ + x^{n−k−j}) and define ḡ by g = x^{j} ⊗ ḡ. Then clearly |f ⊗ g| = |f ⊗ ḡ| and |g| = \left|{ \atop ḡ}\right|. By Corollary 18, there are at most n^{2d+1}2^{gcd(k,n−j)} pairs (f, ḡ) 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 ∑_{j=0}^{n−1} n^{2d+1}2^{gcd(k,n−j)} ≤ n^{2d+2}2^{k}.

The final ingredient for our proof is Hoeffding’s inequality. Proposition 20 (Hoeffding’s Inequality [5, Thm. 2]). Let X_{n} be a sum of n independent Bernoulli random variables X with 𝔼[X] = p. Then Prob(|X_{n} − np| > ϵn) ≤ 2e^{−2ϵ^{2}n}.

When we choose a degree n − 1 polynomial f uniformly at random from L_{b}, the quantity |f_{i}| is a sum of n independent Bernoulli random variables Z_{i} with 𝔼[Z_{i}] = \frac{b−i}{b}. As a consequence, if f is a degree n − 1 polynomial chosen uniformly from L_{b}, then

Prob (||f_{i}| − \frac{(b − i)n}{b}| > ϵn) ≤ 2e^{−2ϵ^{2}n}.  (2)

We now prove a quantitative version of Theorem 11. Let Σ_{b}^{n} denote the set of decomposable lunar numbers of base b and degree at most n.

Proposition 21. Fix b, n ≥ 2 and let a = ⌊b/2⌋. Then for every d, v > 0 we have

|Σ_{b}^{n}| ≲ b^{n+1} (n^{2}e^{\frac{−d^{2}}{4(n+2)}} + n^{2d+4}2^{\frac{d}{2} − \frac{n+1}{3}} + vn^{2d+2}2^{v}b^{\frac{d}{2} − \frac{n}{b}} + n^{2}2^{−v}) .

We partition Σ_{b}^{n} into two subsets, then control the size of each. Let D_{b}^{n} ⊆ Σ_{b}^{n} denote the set of h that admit a factorization h = f ⊗ g such that f_{a}, g_{a} are not monomials and let I_{b}^{n} = Σ_{b}^{n} \ D_{b}^{n}.

Remark 22. When b = 2a, the size of D_{b}^{n} is easy to control. As each h ∈ D_{b}^{n} has a factorization h = f ⊗g such that h_{a} = f_{a}⊗g_{a} is nontrivial, we have that s_{a}(D_{b}^{n}) ⊆ Σ_{2}^{n} (though the inclusion may be strict, as h_{a} = \overline{f} ⊗\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 ∈ L_{2}^{n}, we have

\frac{|D_{b}^{n}|}{b^{n}} ≤ \frac{|s_{a}^{−1}(Σ_{2}^{n})|}{b^{n}} = \frac{a^{n+1}|Σ_{2}^{n}|}{b^{n}} = \frac{a|Σ_{2}^{n}|}{2^{n}},

a quantity which goes to zero as a consequence of Theorem 10.

Definition 23. Let d ∈ ℝ^{+}. A polynomial h ∈ L_{b}^{n} is d-Hoeffding extremal if there exists 1 ≤ i ≤ b − 1 such that

||h_{i}| − \frac{(b − i)n}{b}| > \frac{d}{2},  (3)

or if h admits a factorization h = f ⊗ g such that

||f_{i}| + |g_{i}| − \frac{(b − i)(n + 1)}{b}| > \frac{d}{2}.  (4)

Let H_{b}^{n}(d) denote the set of all h ∈ L_{b}^{n} that are d-Hoeffding extremal.

We will show individually that H_{b}^{n}(d), D_{b}^{n} \ H_{b}^{n}(d), and I_{b}^{n} \ H_{b}^{n}(d) are small, from which it follows that Σ_{b}^{n} is small.

Lemma 24. For fixed b and all d ∈ ℝ^{+}, we have |H_{b}^{n}(d)| ≲ n^{2}e^{\frac{−d^{2}}{4(n+2)}} b^{n}.

Proof. Let i ∈ \{1, …, b\}. By Equation (2) with ϵ = \frac{d}{2(n+1)}, the number of polynomials h

satisfying Equation (3) 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 ⊗ g such that h is d-Hoeffding extremal due to Equation (4), it suffices to bound the number of pairs (f, g) such that deg f ⊗ g ≤ n and (f_{i}, g_{i}) satisfies Equation (4).

For each m ≤ n, we bound the number of pairs (f, g) with deg f ⊗ g = m. If we fix deg f = k, then we must have deg g = m − k as deg(f ⊗ g) = m. The set of pairs (f, g) ∈ (L_{b})^{2} such that deg f = k, deg g = m − k is in bijection with L_{b}^{m+1} with the bijection given below:

ϕ(f, g) = f ⊕ (((b − 1)x^{k+1}) ⊗ g)
ϕ^{−1}(h) = (⨁_{j=0}^{k} γ_{j}x^{j}, ⨁_{j=k+1}^{m+1} γ_{j}x^{j−k−1}) .

Moreover, |f_{i}| + |g_{i}| = |(ϕ(f, g))_{i}|. Thus, choosing ϵ = \frac{d}{2(m+2)} and applying Equation (2), 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

|H_{b}^{n}| ≤ e^{\frac{−d^{2}}{4(n+1)}} b^{n+1} + ∑_{m=1}^{n} 2me^{\frac{−d^{2}}{4(m+2)}} b^{m+3} ≲ ∑_{m=1}^{n} me^{\frac{−d^{2}}{4(m+2)}} b^{m+1} ≤ n^{2}e^{\frac{−d^{2}}{4(n+2)}} b^{m+1}.

Lemma 25. If h = f ⊗ g ∈ Σ_{b}^{n} \ H_{b}^{n}(d) and 1 ≤ i ≤ b − 1, then |h_{i}| ≤ |f_{i}| + |b_{i}| + d.

Proof. We have |h_{i}| < \frac{(b−a)(n+1)}{b} + d/2 and |f_{a}| + |g_{a}| > \frac{(b−a)(n+2)}{b} − d/2 ≥ |h_{i}| − d.

Lemma 26. For fixed b and all d > 0, we have |D_{b}^{n} \ H_{b}^{n}(d)| ≤ n^{2d+4}2^{\frac{d}{2} − \frac{n}{3}} b^{n+1}.

Proof. Let h ∈ D_{b}^{n} \ H_{b}^{n}(d) and fix a nontrivial factorization h_{a} = f_{a} ⊗ g_{a}. We count the number of pairs (f_{a}, g_{a}) with deg h_{a} = m for each 2 ≤ m ≤ n. Since h is not d-Hoeffding extremal, we have |h_{a}| ≤ |f_{a}| + |g_{a}| + d. It follows that the pair (f_{a}, g_{a}) satisfies the hypotheses of Lemma 19. Being non-monomials, f_{a}, g_{a} must both have positive degree, so deg f = m−deg g ≤ m−1. Using the fact that gcd(deg f_{a}, m) ≤ \frac{m}{2} for 1 ≤ deg f_{a} ≤ m−1, the number of possible choices for h_{a} is at most

∑_{deg f_{a}=1}^{m−1} m^{2d+2}2^{gcd(deg f_{a},m)} ≤ m^{2d+3}2^{\frac{m}{2}} .

The total number of possibilities for h_{a}, therefore, is bounded by

∑_{m=2}^{n} m^{2d+3}2^{\frac{m}{2}} ≤ n^{2d+4}2^{\frac{n}{2}} .

Once h_{a} is known, if |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, …, a − 1}, and each 1 corresponds to a coefficient in \{a, …, 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 ≤ s. Recalling that a = ⌊b/2⌋, we have a ≤ b/2 ≤ (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:

a^{n+1−k}(b − a)^{k} ≤ a^{n+1−s}(b − a)^{s} = a^{\frac{n+1}{2}} (b − a)^{\frac{n+1}{2}} (\frac{b − a}{a})^{(\frac{b−a}{b} − \frac{1}{2})(n+1)} (\frac{b − a}{a})^{\frac{d}{2}} .

By the AM-GM inequality, we have a^{\frac{n+1}{2}} (b − a)^{\frac{n+1}{2}} ≤ (\frac{b}{2})^{n+1}. For b ≥ 2, we have the bounds

1 ≤ \frac{b−a}{a} ≤ 2 and 0 ≤ \frac{b−a}{b} − \frac{1}{2} ≤ \frac{1}{6}, thus for every b ≥ 2 we have (\frac{b−a}{a})^{( \frac{b−a}{b} − \frac{1}{2} )(n+1)} ≤ 2^{\frac{n+1}{6}} . Altogether, this yields

|D_{b}^{n} \ H_{b}^{n}(d)| ≤ n^{2d+4}2^{\frac{n}{2}} (\frac{b}{2})^{n+1} (\frac{b − a}{a})^{\frac{d}{2}} (\frac{b − a}{a})^{( \frac{b−a}{b} − \frac{1}{2} )n+1}

≤ n^{2d+4}2^{\frac{n}{2}} (\frac{b}{2})^{n+1} 2^{\frac{n+1}{6} + \frac{d}{2}} ≤ n^{2d+4}2^{\frac{d}{2} − \frac{n}{3}} b^{n+1}.

Lemma 27. For all d, v ∈ ℝ^{+}, the number of lunar numbers in Σ_{b}^{n} \ H_{b}^{n}(d) that can be factored as h = f ⊗ g where deg f ≤ v is at most vn^{2d+3}2^{v}(b − 1)^{\frac{(b−1)n}{b} + \frac{d}{2}} .

Proof. Let h ∈ I_{b}^{n} \ H_{b}^{n}(d) such that deg h = m. Let h = f ⊗ g be a nontrivial factorization where deg f ≤ v. As h is not d-Hoeffding extremal and f_{1}, g_{1} are both not monomials, the factorization h_{1} = f_{1} ⊗ g_{1} satisfies the hypotheses of Lemma 19. Applying Lemma 19 once for each choice of 1 ≤ k ≤ v, we conclude that the number of possible pairs (f_{1}, g_{1}) with deg h_{1} = m is at most ∑_{k=1}^{v} m^{2d+2}2^{gcd(k,m)} ≤ vm^{2d+1}2^{v}. Summing over all possible values of m, the number of pairs (f_{1}, g_{1}) is at most

∑_{m=2}^{n} vm^{2d+2}2^{v} ≤ 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 Equation (4), the claim follows.

Lemma 28. For all d, v ∈ ℝ^{+}, we have |I_{b}^{n} \ H_{b}^{n}(d)| ≲ vn^{2d+2}2^{v}b^{\frac{(b−1)n}{b} + \frac{d}{2}} + n^{2}2^{−v}b^{n+1}.

Proof. For fixed k, there are at most (k+1)(a−1)^{k}b possible lunar numbers f with deg f ≤ k and |f_{a}| ≤ 1: pick the index of the coefficient with no constraint, then pick its value from {0, …, b−1}, then pick the remaining coefficients from {0, …, a−1}. Additionally, there are b^{n+1−k} lunar numbers g of degree ≤ n − k. It follows that there are at most (k + 1)a^{k}b^{n−k+2} lunar numbers h such that deg h ≤ n, h = f ⊗ g, deg f = k, and |f_{a}| ≤ 1. As

∑_{k=v}^{n}(k + 1)a^{k}b^{n−k+2} ≤ n(n + 1)(a − 1)^{v}b^{n−v+2} ≲ n^{2}b^{n+1}2^{−v},

the claimed bound follows from Lemma 27.

These bounds lead to an immediate proof of Proposition 21. With the right choice of d, v, this gives us a proof of Theorem 11.

Proof. Our goal is to show that |Σ_{b,n}|/b^{n+1} → 0, from which the result follows. Setting d = 2\sqrt{n + 2} log n and v = 3 log_{2} n, we then apply Proposition 21 to conclude |Σ_{b,n}|/b^{n+1} → 0 for fixed b as n → ∞.

2.1 Proof of Conjecture 12

We are now prepared to state and prove Corollary 12 using Theorem 11. Recall from Definition 5 the distinction between a prime polynomial (one factor is always a unit) and an indecomposable polynomial (one factor is always a monomial). Applegate, LeBrun, and Sloane discuss prime polynomials, but primality and indecomposability are sufficiently similar that our results can be applied to the conjecture [1]. These authors instead use the term 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 L_{b}.

Definition 29. A prime candidate of L_{b} is a polynomial with nonzero constant term and maximum coefficient b − 1.

It is easy enough to see that a lunar number is prime only if it is a prime candidate. If h = a_{j}x^{j} ⊕ ⋯ ⊕ a_{n−1}x^{n−1} for j > 1, then h = (b − 1)x^{j} ⊗ (a_{j} ⊕ ⋯ ⊕ a_{n−1}x^{n−j−1}) which is a nontrivial factorization in their convention. Moreover, if c < b−1 is the maximum coefficient of h, then h = c ⊗ h.

They showed that, if π_{b}^{cand}(n) is the number of prime candidates in base b with degree n − 1, then π_{b}^{cand}(n) ∼ (b − 1)^{2}b^{n−2}. Furthermore, their data suggests that almost all prime candidates are in fact prime as n → ∞. See OEIS sequences \underline{A169912} and \underline{A087636} for the number of prime elements of L_{2}^{n} and L_{10}^{n}. As evidence for this fact, Applegate et al. produced the following lower bound:

(b − 1)^{n−2} + 2(b − 2)^{n−2} + ⋯ ≤ π_{b}(n).

Moreover, they observed the following, which we re-prove here.

Lemma 30 (Applegate, LeBrun, and Sloane [1, p. 10]). An indecomposable prime candidate is prime.

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.

With this lemma, Corollary 12 is a simple corollary of Theorem 11.

Proof. For fixed b, the proportion of prime candidates of L_{b}^{n} which are decomposable is at most a quantity which vanishes as n → ∞:

\frac{π_{b}(n)}{(b − 1)^{2}b^{n−2}} ≤ \frac{|Σ_{b}^{n−1}|}{(b − 1)^{2}b^{n−2}} ≲ \frac{|Σ_{b}^{n−1}|}{b^{n}} → 0.  (5)

It follows that almost all prime candidates are prime.

3 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 [7], in particular sequence \underline{A169912}, without which we may never have made the connection between lunar arithmetic and sumsets which inspired this project.

References

[1] David L. Applegate, Marc LeBrun, and Neil J. A. Sloane, Dismal arithmetic, J. Integer Sequences 14 (2011), Article 11.9.8.

[2] Shuhong Gao and Alan G. B. Lauder, Decomposition of polytopes and polynomials, Discrete Comput. Geom. 26 (2001), 89–104.

[3] Andrew Granville and Aled Walker, A tight structure theorem for sumsets, Proc. Amer. Math. Soc. 149 (2021), 4073–4082.

[4] Gal Gross, Maximally additively reducible subsets of the integers, Master’s thesis, University of Toronto (Canada), 2019.

[5] Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30.

[6] 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. https://

    arxiv.org/abs/math/0501167.

[7] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2025. Published electronically at https://oeis.org.

[8] Yaroslav Shitov, How many boolean polynomials are irreducible?, Internat. J. Algebra Comput. 24 (2014), 1183–1189.

[9] Ilya D. Shkredov, Any small multiplicative subgroup is not a sumset, Finite Fields Appl. 63 (2020), 101645.

[10] David Speyer and Bernd Sturmfels, Tropical mathematics, Math. Mag. 82 (2009), 163– 173.

2020 Mathematics Subject Classification: Primary 11B13; Secondary 15A80. Keywords: sumset, irreducible set, lunar arithmetic.

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

Received January 2 2023; revised versions received January 3 2023; March 25 2024; March 2 2025; March 11 2025. Published in Journal of Integer Sequences, March 26 2025.

Return to Journal of Integer Sequences home page.