WorksMathematics
Harmonic dyadic shifts and short sums of factorial divisors
Abstract
Let be the maximum, over , of the least number of distinct positive divisors of a practical integer whose sum is . We prove . The main ingredient is a finite entropy lemma. A law modulo with entropy at least in every -bit lower prefix becomes supported on more than half the group after independent copies, each multiplied by an independently chosen power of two. The shift distribution is harmonic. A divisor-digit construction supplies at linear factorial index. Positive quotient recursion, binary carrying, and a factorial radix then give the stated bound.
Statement, conventions, and source overlap
All unmarked logarithms are natural; has base two. A sum of no terms is zero. Local modular representations may repeat divisors. The final representations use distinct positive divisors.
For a practical , define
The original question often uses . For the two conventions agree: the smaller range already requires at least one term, while itself is a one-term divisor sum. For , the inclusive convention gives . We use the inclusive convention throughout.
Theorem 1. There are absolute constants and such that
Consequently the strict-power version of Erdős 18(c) holds with exponent 10.
The divisor-block construction and the positive quotient/radix framework are adapted from Kohlmeyer-Kruer, Section 3 and Sections 5-6. Plasma AI’s author-recorded L63 already gives an overlapping quantitative interface from short dyadic representatives to factorial divisor sums. We give the complete transfer argument for the parameters used here, and credit those earlier transfer mechanisms.
The separated-digit entropy obstruction L64 excludes a fixed positive entropy rate at this factorial scale. Our input rate tends to zero, and the harmonic additive shift lemma has polynomial cost in its reciprocal. The final law sums overlapping shifted inputs; it is not a single separated-digit family covered by that support bound. The source’s displayed multiplicative block expansion is also not used. The related L66 records a vanishing-rate residue estimate for the full odd-divisor law and a conditional multiplicative mixing criterion. That multiplicative criterion is not assumed here. Novelty of the harmonic additive argument remains to be assessed externally.
The use of entropy in additive combinatorics has a substantial prior history; see Tao, Green-Manners-Tao, and the multiscale convolution theorems of Hochman. Weighted sums over cyclic groups also appear in Abbe-Li-Madiman. We do not claim these general ideas as new. The proposed contribution here is the specific harmonic-shift estimate in Lemma 2, uniform as the lower-prefix entropy rate tends to zero, and its application to factorial divisors. A separate novelty report records the scope of the source comparisons; no global priority certification is claimed.
Harmonic shifts from lower-prefix entropy
For a finite random variable , let denote Shannon entropy in natural units. Conditional probabilities on zero-probability events can be chosen arbitrarily.
Lemma 2 (harmonic dyadic shifts). Let , let , and let be a law on . Suppose
Put
Take mutually independent pairs , , such that and are independent within each pair, has law , and
For
one has
In particular, if
then satisfies , and .
Proof. Write residues using their canonical binary digits, indexed from position zero. Given the lower bits of , let be the conditional probability that bit is one. Define
For binary entropy ,
Indeed, for ,
and ; use symmetry on the other half. Thus
The entropy chain rule and Cauchy-Schwarz give
Consequently, with ,
Fix . Let , and condition on
On any positive-probability atom, first fix . The remaining conditioning specifies one lower-prefix event for each separate input. Independence of the input pairs therefore preserves independence of the current input bits on that atom.
Let be the least nonnegative residue of modulo . These residues, and hence the carry
are -measurable. For all and the carry are zero. A carry may exceed one; only its known parity is used.
If , the current bit of the -th summand is bit of . If , it is zero. Thus, writing for the conditional sign-bias of that bit given its own lower prefix, and setting when ,
No independence of carries or output bits is asserted.
Unconditionally, each is a function of its own independent pair. Therefore
Equation (4) gives
A binary law with absolute sign-bias has entropy at least , by concavity. The output’s lower bits and the full shift vector are measurable under , so
This entropy comparison does not assume independence after conditioning only on the output prefix. Summing over , using the chain rule conditioned on the same full vector , and then , proves (2.2).
Under (2.3), . Entropy is at most log support size, hence
For every residue , the sets and intersect; thus is the whole group. □
The proof first bounds . Randomness in the unobserved shifts is therefore not being used as a hidden entropy source.
Divisor digits at linear factorial index
Fix
For every integer , put
These choices satisfy
For example, ; ; and in this range.
For , define
Lemma 3. Uniformly for and ,
Proof. We use the elementary bound
To verify it, the central binomial coefficient is at least . In its valuation at a prime , each prime-power term is zero or one, so the prime’s whole contribution is at most . Hence
Since and for , this proves (9).
Write . If , all integers through divide , so
here ensures .
Otherwise put . Then
Every product of distinct primes at most divides and is at most . Distinct prime subsets give distinct integers. With , (9) yields
In particular . Since
:::
Digit convention. Start at endpoint . Define successive endpoints
until , and let . Choose an initial digit uniformly among the odd integers in . Independently choose uniformly from , and set
The number includes the initial digit. A zero digit contributes no divisor term. Before the final block the endpoint doubles, so , giving the count below. Because all digits are below their block radices, there are no carries between blocks and
Each initial digit divides . Every later nonzero term divides , and
Thus is a positive sum of at most divisors of , where .
For , is uniform among odd residues, giving maximum mass . For , let be the last completed block endpoint at or below . If cuts a block, that block has length at most , so ; at , take . Fixing a residue fixes every completed digit. Independence and (8) give
The last inequality uses .
Take an independent uniform , and let be the actual positive integer; let be its residue. Then
and is a sum of at most divisors of . The possible integer value supplies a positive witness for residue zero.
Parity of an output residue determines the unique compatible value of , since is odd. Equation (11), and uniform parity at , therefore imply
In particular , as required in Lemma 2.
Short positive representatives of every dyadic residue
Apply Lemma 2 to this , taking
This satisfies (3): , , , and , so the right side of (3) is at most .
Each residue in the support of the shifted sum has an actual positive witness formed from shifted integers . Expanding their divisor representations gives at most terms. If and , then
All terms therefore divide the single common factorial
Its index does not multiply by the number of additive copies.
As covers the group, every residue modulo has a positive integer representative which is a sum, with repetition allowed, of at most
divisors of . Uniformly over the chosen residue,
There is also the smaller bound , but (15) suffices for the exponent proved below. This is the local representative interface overlapping L63. With the coarse height (15), the factorial index is linear, the count exponent is five, and the binary logarithmic height has one logarithmic overhead. The next sections independently give the corresponding transfer.
Exact positive lifting and distinct divisors
Lemma 4 (binary repetition removal). A sum of positive divisors of an integer is a sum of at most distinct positive divisors of
with the same value.
Proof. Write . Group the terms according to their odd part . In a group, the total is , where is a sum of at most powers , , hence . Its binary expansion has largest exponent at most . Each surviving digit gives an allowed divisor. Binary carrying reduces term count. The terms within a group are distinct; terms in different groups have different odd parts.
Lemma 5 (one exact integer). For every sufficiently large integer , put . Then is a sum of distinct divisors of .
Proof. Fix an absolute . For a current positive integer with bit length , take
Fix a threshold so that, for every ,
and ;
;
the upper bound in (15) is at most .
These are compatible eventual conditions. For the height condition, use
and, eventually, . The factorial contribution is at most ; the logarithm of the count in (15) is . Our fixed choice of , followed by a fixed sufficiently large , leaves ample margin below . All constants and thresholds are independent of the target .
Choose the positive representative from § 4. Since ,
Thus
Its bit length satisfies . Continue while , and represent the final bounded integer by a bounded number of copies of 1.
The potential drops by an absolute positive amount at each large stage. Indeed , and
There are stages. Each uses terms, so the total count before merging is
Every unscaled term divides the original , since ; the terminal copies of 1 do also. Let be a lifting exponent. Positivity in (16) implies
so , including the terminal stage. Every lifted term therefore divides .
Apply Lemma 4 with . The distinct resulting divisors divide . Increase the fixed starting threshold to so that . Among the integers after , at least are even. Hence
The sum and the count (17) are preserved. □
This proof includes all finitely many stopping cases by a fixed terminal constant. It never invokes the local cover at a zero or below .
Factorial radix and the global bound
First, factorials are practical with the inclusive convention. Let . For , . Given , write
Use the empty representation if ; otherwise scale an inclusive divisor representation of by . Every scaled divisor divides and is at least . If , the integer itself divides and is smaller than all scaled terms. Thus distinctness is preserved, and, for example, is a valid finite base bound.
Fix
Choose a fixed so that , , and all following eventual bounds hold for .
For any , write
A sufficiently large positive remainder has bit length
Thus eventually. Lemma 5 represents by distinct divisors of , hence of . The finitely many remainders outside Lemma 5’s range are themselves divisors once exceeds that fixed finite set; uses the empty sum. This is uniform over all .
Scale a distinct inclusive representation of by . Each high term is a divisor of and is at least . Every positive low term is smaller than , because its whole positive sum is . The families do not overlap. Therefore
The endpoint is included: it has , and also has its direct one-term representation.
For ,
There are radix steps down to the fixed base. Summing the uniform cost in (6.1) proves
as claimed in Theorem 1. □
Strict-power target and the other two questions
The pinned Formal Conjectures statement uses the inclusive endpoint and asks for a positive real with
for all sufficiently large natural . A set of divisors whose sum is witnesses its subset-sum condition directly; its infimum/minimum convention therefore has the upper bound proved here. Factorials are practical by Section 6, so no empty representation family is involved.
Choose and as in Theorem 1. For
one has , and consequently
Thus gives the formal strict-power quantifiers, including the endpoint . Reading the statement for this comparison is not a formalization or a Lean verification.
Corollary 6 (the three questions together). Theorem 1 implies affirmative answers to all three questions of Erdős Problem 18: (c) with strict exponent 10, (b) for every positive exponent, and (a) with strict exponent 10 along the factorials.
Proof. The implication for (c) was proved above. For (b), fix and write . The exponential series gives
once .
For (a), the elementary factorial estimate gives
Consequently for all sufficiently large . Set . Theorem 1 yields
once . Factorials are practical and form an unbounded sequence, so this supplies infinitely many witnesses for (a). □
Part (b) was proved earlier by Kohlmeyer and Kruer KK; see also the accepted part-(b) source record. The implication above does not claim a new discovery of (b). For (a), the earlier work of GPT-5.6 Sol Pro, prompted and posted by Liam Price, and the explicit account of Wouter van Doorn and GPT-6 Astra Pro VD give the stronger square-log-log bound on a suitable sequence of practical numbers. Our factorial corollary does not improve that general-sequence bound. The proposed new result is the bound at every large factorial in (c); it is not obtained by logically combining the statements of (a) and (b). The earlier greedy factorial bound of Hughes Hughes also does not supply a fixed polylogarithm.
Acknowledgments and AI assistance
The author list is Will Howe, Grant Huffman, Jensen Kohlmeyer, and Liam Kruer. No institutional affiliations are asserted. This manuscript was developed with Codex assistance. AI systems proposed mathematical arguments and performed informal checks, including separate checks of the entropy and arithmetic parts. AI review is not represented as external peer review or formal verification. The accompanying Lean development independently proves the quantitative bound and the three original statements. Its compiler receipts and axiom audits are provided with this draft; this is local verification, not sponsor acceptance.
We credit the divisor-digit construction and the positive lifting and factorial radix methods to Kohlmeyer and Kruer KK. The overlapping quantitative transfer criterion is recorded by Plasma AI L63. Its separated-digit obstruction L64 and multiplicative criterion L66 delimit, rather than supply, the new mixing step. The arguments required here are proved in the text.
Formal verification
The accompanying Lean 4.34.0 project proves the unconditional theorem Erdos18c.ninthPowerBound and the exact original statements Erdos18.erdos_18a, Erdos18.erdos_18b, and Erdos18.erdos_18c. It uses mathlib commit 5ed2965256430c3649e8675f9576b54eca72435. The printed axiom dependencies are propext, Classical.choice, and Quot.sound; no unproved problem-specific assumptions are introduced.
The formal proof realizes the harmonic mixing estimate using convolution and order-two translation differences. It then constructs the divisor digits and positive modular representatives. For the integer lifting and factorial recurrence it uses logarithmic potentials, with different absolute constants from the exposition. It obtains the same ninth-power conclusion. The code adapts credited infrastructure from Kohlmeyer and Kruer’s 18(b) source, whose SHA-256 is 4d6ee896174152 88e9f127beb3c0e0211c011f891889fcb43d0e16373bd14088.
The final statement file reproduces only the definitions and target types from the pinned Formal Conjectures source, and proves their equivalence to the internal definitions. It does not import the unproved conjectures. Build instructions, the source correspondence, and limitations of the local verification are recorded in the accompanying verification report.
References
References
- [1]J. Kohlmeyer and L. Kruer, Short sums of factorial divisors and Erdős Problem 18(b), manuscript dated 16 September 2026. Author-hosted PDF. The cited version has SHA-256 f89f4f46b9535c5c990a29bf0ddf1eb305123429a3b89dfb508e95c8cc9b2d6a.
- [2]Plasma AI, Polylogarithmic dyadic representatives imply short factorial sums, L63, updated 14 October 2026. Statement; proof. Author-recorded conditional result; accessed 1 November 2026.
- [3]Plasma AI, Subexponential support of short factorial divisor blocks, L64, updated 14 October 2026. Statement; proof. Accessed 1 November 2026.
- [4]Plasma AI, Full-divisor residue spread and a quantitative mixing criterion, L66, updated 14 October 2026. Statement; proof. Accessed 1 November 2026.
- [5]T. F. Bloom, Erdős Problem 18, problem record and proof-claim record, accessed 1 November 2026. These are problem/status sources, not proof inputs.
- [6]P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographies de L’Enseignement Mathématique 28, Université de Genève, 1980. Historical problem reference; no theorem from this book is used without proof here.
- [7]The Formal Conjectures Authors, Erdős Problem 18, Lean statements, commit a64e959c32c270df4dd0d96d2027481f15750534, Apache-2.0.
- [8]T. Tao, Sumset and inverse sumset theory for Shannon entropy, Combinatorics, Probability and Computing 19 (2010), 603-639, DOI 10.1017/S0963548309990642. arXiv:0906.4387. Background, not a quantitative input to Lemma 2.DOI
- [9]B. Green, F. Manners and T. Tao, Sumsets and entropy revisited, Random Structures & Algorithms 66 (2025), e21252, DOI 10.1002/rsa.21252. arXiv:2306.13403. Background on entropic doubling and homomorphisms.DOI
- [10]E. Abbe, J. Li and M. Madiman, Entropies of weighted sums in cyclic groups and an application to polar codes, Entropy 19 (2017), 235, DOI 10.3390/e19090235. arXiv:1512.00135. Related weighted-sum and source-polarization context.DOI
- [11]M. Hochman, On self-similar sets with overlaps and inverse theorems for entropy, Annals of Mathematics 180 (2014), 773-822, DOI 10.4007/annals.2014.180.2.7. Published paper, especially Theorems 2.7-2.9. Background, not an input to Lemma 2.DOI
- [12]W. van Doorn and GPT-6 Astra Pro, Practical numbers and Egyptian fractions, source manuscript, commit 56b455ae6949b76f41292d35829034ebb8663241, September 2026. The source credits Sparse Divisor Sums by GPT-5.6 Sol Pro, prompted and posted by Liam Price. No new priority for (a) is claimed here.
- [13]S. D. Hughes, Sums of distinct divisors of factorials, arXiv:2609.10902v1, 9 September 2026.arxiv.org/abs/2609.10902
- [14]Conjectures.io, Erdős 18(b), accepted result record, accessed 1 November 2026. Records acceptance for (b); no local replay is implied by citing the record.