Maximally additively reducible subsets of the integers

Gal Gross

REVIEW 2 major objections 4 minor 19 references

Maximally additively reducible subsets of the integers

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The interval $\{1,\ldots,k\}$ uniquely maximizes the number of additive divisors among all nonempty subsets of $\{0,\ldots,k\}$, except at $k=1$ and $k=3$.

desk verdict Solid binary-case results; the general-base proof has a repairable off-by-one. read the letter →

arxiv 1908.05220 v1 pith:ZTOFIJY4 submitted 2019-08-14 math.CO math.NT

Gal Gross This is my paper · ORCID

classification math.COmath.NT MSC 11P7005A17

keywords additivedivisorssumsetslunararithmeticheadstrongcompositionsrestrictedgeneralizedFibonaccinumbersinversenumbertheorymultisets

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks which finite set of integers is the most reducible: among all nonempty subsets of $\{0,\ldots,k\}$, which one can be written as a sumset $A+B$ in the greatest number of ways? The paper proves that the shifted interval $\{1,\ldots,k\}$ is the unique winner for every $k$ except $k=1$ and $k=3$, where the maximum is also attained elsewhere. Because sumset addition on binary digit sets corresponds exactly to lunar multiplication (the carry-free digitwise-min multiplication), the same theorem says that the binary number $2^k-2$ has more lunar divisors than every other $k$-digit binary number, uniquely except for $n=2$ and $n=4$. The argument is then lifted to arbitrary bases by replacing sets with multisets, proving that in every base $b \geq 3$ the all-ones repunit $(b^k-1)/(b-1)$ uniquely maximizes the number of lunar divisors among $k$-digit numbers. These results resolve the conjectured maxima for binary lunar divisors and for lunar divisors in every base $b\ge 3$, connecting an inverse question in additive number theory to a digitwise arithmetic system.

What carries the argument

The argument is carried by two linked objects. The first is $k$-promotion: for a set $A\subseteq[k]$ containing $0$, every factorization $A=B+C$ is transformed into a factorization of the full interval $[k]$, either by appending the missing elements of $[k]$ to $C$ or by shifting them by $\max(B)$. This produces disjoint families of divisors, so $[k]$ has at least as many divisors as any $0$-rooted set $A$, and the construction is strict enough to force uniqueness. The second object is the bijection between divisors of $[k]$ and headstrong compositions of $k+1$, compositions whose first part is at least as large as every other part; these are counted by the generalized Fibonacci numbers $F(n,k)$. Lemmas 13 and 14 convert properties of these numbers into the inequalities $2d([k-1])\geq d([k])$ and $3d([k-2])\leq 2d([k-1])$ that let $\{1,\ldots,k\}$ dominate all other subsets. For general bases the machinery widens to arrays of nested subsets: a multiset with maximum multiplicity $b$ is written as $b$ nested sets, multisumset addition is coordinatewise sumset addition, and a divisor of a plain set $A$ contributes $b^{\mathrm{card}\,B}$ divisors of the corresponding multiset.

What would settle it

Brute-force count $d(A)$ for every nonempty subset $A$ of $\{0,1,\ldots,6\}$: if any set other than $\{1,\ldots,6\}$ has $d(A)\ge d(\{1,\ldots,6\})$, then Theorem 19 is false. This is a finite computation, since $d(A)$ counts the distinct $B\subseteq\mathbb{N}$ for which some $C\subseteq\mathbb{N}$ satisfies $A=B+C$.

Watch

Extended reading notes

Core claim

The central discovery, stated on the paper's own terms, is that the interval $[k+]=\{1,\ldots,k\}$ maximizes the additive-divisor count $d(A)=\#\{B\subseteq\mathbb{N}:\exists C,\ A=B+C\}$ among all nonempty subsets of $[k]=\{0,\ldots,k\}$, and is the unique maximizer except for $k=1$ and $k=3$. In binary lunar arithmetic this is the statement that $n=2^k-2$ has strictly more divisors than any other $k$-digit binary number, the unique maximum outside $\{2,4\}$. The route is a two-stage reduction: first, $k$-promotion shows that the full interval $[k]$ is the unique maximum among sets containing $0$; second, the identity $d(A)=(\min A+1)d(A-\{\min A\})$ reduces sets without $0$ to sets with $0$, and inequalities on headstrong compositions show $2d([k-1])>d([k])$, so $\{1,\ldots,k\}$ outscores every $0$-rooted set. The same machinery, with multisets in place of sets, proves the base-independent statement: in every base $b \geq 3$ the repunit $(b^k-1)/(b-1)$ uniquely maximizes the number of base-$b$ lunar divisors among $k$-digit numbers.

Load-bearing premise

The proof of Theorem 17 assumes without proof that enlarging an interval by one element cannot decrease its number of additive divisors; if $d([k-j-1])$ ever exceeded $d([k-j])$, that induction step would collapse.

Editorial extensions

If this is right

For every $k\ne 1,3$, $d(\{1,\ldots,k\})$ is strictly larger than $d(A)$ for every other nonempty $A\subseteq\{0,\ldots,k\}$.
In binary lunar arithmetic, $2^k-2$ is the unique $k$-digit number with the maximal number of lunar divisors whenever $k\ne 1,3$.
In every base $b\ge 3$, the all-ones number $(b^k-1)/(b-1)$ is the unique $k$-digit maximum for the lunar divisor count.
Among odd $k$-digit binary numbers, $111\ldots111$ (that is, $2^k-1$) is the unique maximizer of $d_2$, as an immediate corollary of the $0$-rooted case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper leaves the runner-up problem open: for odd $k$-digit binary numbers, which number has the second-largest divisor count? The headstrong-composition triangle in Section 6 gives a plausible route, since ranking compositions by number of parts is exactly what controls the divisor counts.
The multiset correspondence suggests a testable extension: define additive divisors directly for finite multisets of integers and ask whether every multiset of height $b$ is dominated by the $b$-truncated interval; this would recast the base-$b$ theorem as a statement about all multisets.
The $k$-promotion construction is tailored to the interval $[k]$, so it is not obvious whether the maximizing set for an arbitrary ambient interval $\{a,\ldots,b\}$ is still a translate of an initial interval; a small computational experiment for a few asymmetric intervals would show whether the paper's strongest conclusion survives outside the symmetric setting.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take. The paper proves something real: the binary lunar divisor conjectures from LeBrun et al. are settled, and the sumset-to-lunar correspondence is a genuinely useful dictionary. The promotion procedure in Section 2 is the key new idea and it works. On my reading, Theorems 8 and 19 stand up; the reasoning is clear and the headstrong-composition bijection gives a nice handle on the counts.

The soft spots are in the general-base portion. Theorem 28, which is the load-bearing step for Conjecture 12, has a real off-by-one. Corollary 12 says the number of divisors of [n] of cardinality m is H(n+1,m), not H(n,m). In the proof of Theorem 28, after setting n = max(A) − r, the paper claims d(f) = (r+1)Σ_{m=1}^n H(n,m)b^m. That's not right even for A−{r} = [n]; the correct sum is over H(n+1,m). The expression for d([k]_b) is also off: it should be Σ_{m=1}^{k+1} H(k+1,m)b^m, not Σ_{m=1}^k H(n+r,m)b^m. The example A={1,2}, b=2, k=3 makes this concrete: the proof's formula gives 4, true d(f)=12, d([3]_2)=34. So Theorem 29 does not follow as written. The repair is in reach: use d(f) ≤ (r+1)Σ_{m=1}^{n+1} H(n+1,m)b^m and then iterate Corollary 21 with shifted indices. But the correction is not cosmetic, and the referee should ask for it.

There's a smaller gap in Theorem 17: the step d([k-j-1]) ≤ d([k-j]) is used without proof. That monotonicity is true (headstrong compositions of m embed into those of m+1 by increasing the first part), so it is a minor omission, not a flaw.

Who is this for? People working on additive combinatorics of finite sets, and fans of lunar/dismal arithmetic. The binary results are solid and deserve to be in the literature. The general-base theorem is probably true, but the proof as written is incomplete. I'd recommend engaging with it, and sending it to review, but the referee should insist on fixing the off-by-one before acceptance.

Referee Report

2 major / 4 minor

Summary. The paper studies additive divisors: for finite A ⊆ N, d(A) is the number of sets B for which there exists C with A = B+C. The main results are that among 0-rooted subsets of [k] the interval [k] uniquely maximizes d(·) for k≠1,2 (Theorem 8); among all nonempty subsets of [k] the shifted interval {1,...,k} uniquely maximizes d(·) except for k=1,3 (Theorem 19); and that in any base b≥3 the all-ones b-ary number uniquely maximizes the number of lunar divisors among k-digit numbers (Theorem 29), resolving Conjectures 12, 13, and 14 Part I of LeBrun et al. The proofs introduce a k-promotion procedure, a sumset-to-lunar multiplication correspondence, and a multiset-array model for base-b lunar arithmetic.

Significance. The paper connects two previously separate worlds: additive decomposability of finite sets and lunar (dismal) arithmetic. If the identified gaps are repaired, the results would resolve three conjectures from the lunar arithmetic literature and provide a clean, largely self-contained proof mechanism that re-derives Schroeppel's theorem and Lemma 15 of LeBrun et al. rather than quoting them. The headstrong-composition triangle and its recurrence (Theorem 20) are useful in their own right. The central claims are concrete and falsifiable, and the proofs are mostly constructive, which makes the paper a solid contribution to the combinatorics of sumsets and to the theory of lunar arithmetic.

major comments (2)

[§7, proof of Theorem 28] The proof of Theorem 28 contains an off-by-one error in the application of Corollary 12. Corollary 12 states that the number of divisors of [n] with cardinality m is H(n+1,m), not H(n,m), and it applies to the full interval [n], not to an arbitrary 0-rooted set A−{r}. Consequently the displayed identity d(f) = (r+1)Σ_{m=1}^n H(n,m)b^m is unjustified. The subsequent comparison d([k]_b) = Σ_{m=1}^k H(n+r,m)b^m is also incorrect; the correct expression involves H(k+1,m). A concrete check shows the failure: for A={1,2}, b=2, k=3, the proof's formula gives d(f)=4, whereas Corollary 27 gives d(f)=2(2+4)=12 and d([3]_2)=34, so the displayed chain 4 ≤ 6 cannot establish 12 ≤ 34. Since Theorem 29 depends on this comparison, the proof of Conjecture 12 is incomplete as written. A shifted-index repair using Corollary 26 followed by Corollary 21 iterated appears plausible, but it is not present in the manuscript.
[§5, proof of Theorem 17] The induction step of Theorem 17 uses the inequality d([k−j−1]) ≤ d([k−j]) without proof or citation. Specifically, in the chain (j+2)d([k−j−1]) ≤ (j−1)d([k−j]) + 2d([k−j]) the first term requires d([k−j−1]) ≤ d([k−j]). This monotonicity is true — every additive divisor of an interval maps to an additive divisor of a larger interval — but it is not stated or proved anywhere in the paper, and the induction step of Theorem 17, which underpins Theorem 18 and hence Theorem 19, depends on it. The gap is easily filled by a one-line composition argument or a short lemma, but as written the proof is incomplete.

minor comments (4)

[Throughout] There are several typos and name inconsistencies: 'cojecture' in §1, 'LeBrun'/'Le Brun' used inconsistently, 'Appelgate' in the references should be 'Applegate', 'Wirsig' should be 'Wirsing', and 'Fibonacci Quaterly' should be 'Fibonacci Quarterly'.
[§7, Definition preceding Theorem 22] The convention S+∅ = ∅ in multisumset addition is a deliberate choice, but it deserves more discussion because it departs from the usual set-plus-empty-set convention and it is essential for the descending-chain representation to be a monoid. A reader might reasonably expect S+∅ = S for all S under the set-array interpretation.
[§7, notation] The notation M_b, M_k, and M^b_k is introduced but the compound M^b_{\le k} used in Theorems 28 and 29 is not formally defined; it should be defined explicitly as the union of M^b_{\ell} for ℓ ≤ k.
[§5, proof of Theorem 17] The phrase 'for all k ≥ min(4,j)' in the induction statement is confusing. Since the induction is on j, the intended meaning is that the strict inequality holds for all k ≥ 4 (with small j handled separately); the formula should be rewritten for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's central claims are derived from independent combinatorial lemmas and re-proved external results, with no fitted inputs or load-bearing self-citations.

full rationale

The paper's main derivations are self-contained. The sumset-to-lunar correspondence (Theorem 9) is proved directly from the definitions of sumsets and lunar multiplication. Schroeppel's theorem (Theorem 11) and LeBrun et al.'s Lemma 15 are re-proved in the paper's own language rather than merely cited, so the paper does not import its central conclusions from unverified prior work. Theorem 8's k-promotion argument is an independent injective-mapping proof, and Corollary 26, Theorem 28, and Theorem 29 extend the argument to arbitrary bases via the multiset array formalism, again by explicit construction. The proof of Theorem 17 uses an unstated monotonicity d([k-j-1]) <= d([k-j]), and the proof of Theorem 28 appears to misapply Corollary 12 with an indexing error (H(n,m) rather than H(n+1,m), and applied to an arbitrary 0-rooted set rather than the full interval); these are correctness or repair issues, not circular reductions. No fitted parameter is renamed as a prediction, no central claim is forced by a self-citation, and no ansatz is smuggled in via citation. Thus the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The central claim rests on standard set arithmetic and the explicitly stated convention for sums with the empty set in the multiset section. No free parameters or invented entities are introduced.

assumptions (2)

domain assumption The natural numbers N in this paper are {0,1,2,...}, so that 0-rooted sets and intervals [k]={0,...,k} are meaningful.
The whole framework of min(A)=0 and the bijection to odd binary numbers relies on 0 being a natural number; see Section 2 and Theorem 9.
ad hoc to paper In multisumset addition, S + ∅ = ∅ for any set S (including nonempty S).
Stated in Section 7 before the definition of multisumset addition; it is essential for Lemma 24 and Theorem 25, and differs from the usual set-addition convention some readers might expect.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Maximally additively reducible subsets of the integers." pith.science (2026). https://pith.science/paper/ZTOFIJY4

@misc{pith2026190805220,
  author       = {Pith},
  title        = {Pith review of: Maximally additively reducible subsets of the integers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZTOFIJY4}},
  note         = {Machine review of arXiv:1908.05220}
}

abstract

Let $A, B \subseteq \mathbb{N}$ be two finite sets of natural numbers. We say that $B$ is an additive divisor for $A$ if there exists some $C \subseteq \mathbb{N}$ with $A = B+C$. We prove that among those subsets of $\{0, 1, \ldots, k\}$ which have $0$ as an element, the full interval $\{0, 1, \ldots,k\}$ has the most divisors. To generalize to sets which do not have $0$ as an element, we prove a correspondence between additive divisors and lunar multiplication, introduced by Appelgate, LeBrun and Sloane (2011) in their study of a kind of min/max arithmetic. The number of binary lunar divisors is related to compositions of integers which are restricted in that the first part is greater or equal to all other parts. We establish some bounds on such compositions to show that $\{1, \ldots, k\}$ has the most divisors among all subsets of $\{0, 1, \ldots, k\}$. These results resolve 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 resolve this third conjecture by generalizing from sum-sets to sum-multisets.

Figures

Figures reproduced from arXiv: 1908.05220 by the authors.

**Figure 1.** Example of k-promotion Now, each factor B of A appears in one or more factorizations. We may apply the procedure above to each such factorization. We let F(B) denote the resulting set of factors of [k]. That is, for each C ⊆ A such that B + C = A: if max(B) ≤ max(C) we let B ∈ F(B); if max(B) ≥ max(C) we let BC ∈ F(B) (where BC is given by the procedure described above). (Note that this means that if there is some C… view at source ↗

**Figure 2.** Example of F(B) for A = {0, 2, 3, 4, 5, 6} Theorem 5. If B, D are different divisors of A ∈ Z≤k, then F(B) ∩ F(D) = ∅. Proof. First note that for A = [k] and any divisor B of A we have F(B) = {B} so the claim follows trivially. Assume therefore that A ( [k]. We start by showing that B ∈ F(B) =⇒ B /∈ F(D). Suppose that B ∈ F(B). Then there exists some C with max(C) ≥ max(B) and B + C = A. We already know that B 6= D,… view at source ↗

**Figure 3.** Lunar arithmetic Le Brun et al. then show that ⊕ and ⊗ are commutative and associative, and ⊗ distributes over ⊕. They proceed to study analogues of number-theoretic constructions “including primes, number of divisors, sum of divisors, and the partition function.” [1] In particular, they define db(n) as the number of lunar divisors of n in base b. Section 6 of their paper contains a series of conjectures about the … view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Two representations of sumsets Theorem 9. β : F → B is a monoid-homomorphism, where F is equipped with the sumset operation, and B with the lunar multiplication operation [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

**Figure 5.** Figure 5: Two representations of multiset addition we have a ∈ Ai ⇐⇒ f(a) ≥ i. The multisumset operation is now defined coordinatewise. Given two such arrays A = (A1, . . . , Ab) and B = (B1, . . . , Bb) we define A + B = (A1 + B1, . . . , Ab + Bb), with the convention that S + …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[3]

Additive decomposability of multiplicatively deﬁn ed sets

Elsholtz C. (2006) “Additive decomposability of multiplicatively deﬁn ed sets.” Functiones et Approximatio 35: 61-77

work page 2006
[1]

Dismal Arithmetic

Appelgate D, LeBrun M, Sloane NJA. (2011). “Dismal Arithmetic.” Journal of Integer Sequences, 14, 11.9.8

work page 2011
[2]

On the enumeration of certain compositions and related sequences of numbers

Charalambides CHA. “On the enumeration of certain compositions and related sequences of numbers.” Fibonacci Quarterly, 20: 132-146

work page
[4]

Sums and products of integers

Erd˝ os P. Szemer´ edi E. “Sums and products of integers.”Studies in Pure Math- ematics. Birkh¨ uaser, 1983

work page 1983
[5]

On the sequence A079500 and its c ombinatorial interpretations

Frosini A, Rinaldi S. (2006). “On the sequence A079500 and its c ombinatorial interpretations.” Journal of Integer Sequences, 9, 06.3.1

work page 2006
[6]

Concrete Mathematics

Graham RL, Knuth DE, Patashnik O. Concrete Mathematics. Addison-Wesley Professional, 1994

work page 1994
[7]

Primes on the Moon (Lunar Arithmetic)

Haran, Brady. “Primes on the Moon (Lunar Arithmetic)”. Video interview with Neil Sloane published on Numberphile.com. www.numberphile.com/videos/lunar-arithmetic. Retrieved February 2019

work page 2019
[8]

Combinatorics of Compositions and Words

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

work page 2010

Show all 19 references

[9]

Calculus of Finite Diﬀerences

Jordan C. Calculus of Finite Diﬀerences. Chelsea, 1965

1965
[10]

Compositions with parts c ontrained by the leading summand

Knopfmacher A, Robbins N. (2005). “Compositions with parts c ontrained by the leading summand.” Ars Combinatoria, 76: 287-295

2005
[11]

Combinatory Analysis I

MacMahon PA. Combinatory Analysis I. Cambridge University Press, 1915

1915
[12]

Additive Number Theory: The Classical Bases

Nathanson Melvyn B. Additive Number Theory: The Classical Bases. Springer, 1996

1996
[13]

Additive Number Theory: Inverse Problems and the Geometry of Sumsets

Nathanson Melvyn B. Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Springer, 1996

1996
[14]

Additive Zahlentheorie

Ostmann HH. Additive Zahlentheorie. 2 Volumes. Springer, 1956

1956
[15]

The online encyclopedia of integer sequences

Sloane, NJA. The online encyclopedia of integer sequences. oeis.org
[16]

On a generalized compos ition func- tion

Srinivasa Rao K, Agarwal AK. (2000). “On a generalized compos ition func- tion.” Journal of the Indian Mathematical Society, 67: 99-106

2000
[17]

Additive Combinatorics

Tao T, Vu Van H. Additive Combinatorics. Cambridge University Press, 2010

2010
[18]

Ein metrischer Satz ber Mengen ganzer Zahle n

Wirsing E. (1953) “Ein metrischer Satz ber Mengen ganzer Zahle n.” Archiv der Mathematik, 7: 392-398

1953
[19]

Solving generalized Fibonacci recurrenc es

Wolfram, DA. (1998) “Solving generalized Fibonacci recurrenc es.” The Fi- bonacci Quaterly 36: 129-145. MAXIMALLY ADDITIVELY REDUCIBLE SUBSETS OF INTEGERS 31 Department of Mathematics, University of Toronto, Toronto , ON, Canada M5S 2E4 E-mail address : g.gross@mail.utoronto.ca

1998

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [3]

Additive decomposability of multiplicatively deﬁn ed sets

Elsholtz C. (2006) “Additive decomposability of multiplicatively deﬁn ed sets.” Functiones et Approximatio 35: 61-77

work page 2006

[2] [1]

Dismal Arithmetic

Appelgate D, LeBrun M, Sloane NJA. (2011). “Dismal Arithmetic.” Journal of Integer Sequences, 14, 11.9.8

work page 2011

[3] [2]

On the enumeration of certain compositions and related sequences of numbers

Charalambides CHA. “On the enumeration of certain compositions and related sequences of numbers.” Fibonacci Quarterly, 20: 132-146

work page

[4] [4]

Sums and products of integers

Erd˝ os P. Szemer´ edi E. “Sums and products of integers.”Studies in Pure Math- ematics. Birkh¨ uaser, 1983

work page 1983

[5] [5]

On the sequence A079500 and its c ombinatorial interpretations

Frosini A, Rinaldi S. (2006). “On the sequence A079500 and its c ombinatorial interpretations.” Journal of Integer Sequences, 9, 06.3.1

work page 2006

[6] [6]

Concrete Mathematics

Graham RL, Knuth DE, Patashnik O. Concrete Mathematics. Addison-Wesley Professional, 1994

work page 1994

[7] [7]

Primes on the Moon (Lunar Arithmetic)

Haran, Brady. “Primes on the Moon (Lunar Arithmetic)”. Video interview with Neil Sloane published on Numberphile.com. www.numberphile.com/videos/lunar-arithmetic. Retrieved February 2019

work page 2019

[8] [8]

Combinatorics of Compositions and Words

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

work page 2010