betaFeedback

WorksMathematics

Harmonic dyadic shifts and short sums of factorial divisors

Abstract

Let h(N)h(N) be the maximum, over 1≤R≤N1\le R\le N, of the least number of distinct positive divisors of a practical integer NN whose sum is RR. We prove h(n!)=O((log⁡n)9)h(n!)=O((\log n)^9). The main ingredient is a finite entropy lemma. A law modulo 2k2^k with entropy at least gLlog⁡2gL\log 2 in every LL-bit lower prefix becomes supported on more than half the group after O(g−2(log⁡k)2)O(g^{-2}(\log k)^2) independent copies, each multiplied by an independently chosen power of two. The shift distribution is harmonic. A divisor-digit construction supplies g≍1/log⁡kg\asymp1/\log k 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; log⁡2\log_2 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 N≥1N \ge1, define

h(N)=max⁡1≤R≤Nmin⁡{∣D∣:D is a set of positive divisors of N, ∑d∈Dd=R}.h(N) = \max_{1 \le R \le N} \min\{|D| : D \text{ is a set of positive divisors of } N,\ \sum_{d \in D} d = R\}.

The original question often uses R<NR < N. For N≥2N \ge2 the two conventions agree: the smaller range already requires at least one term, while NN itself is a one-term divisor sum. For N=1N = 1, the inclusive convention gives h(1)=1h(1) = 1. We use the inclusive convention throughout.

Theorem 1. There are absolute constants Ch>0C_h > 0 and n0n_0 such that

h(n!)≤Ch(log⁡n)9(n≥n0).h(n!) \le C_h(\log n)^9 \qquad(n \ge n_0).

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 YY, let H(Y)H(Y) denote Shannon entropy in natural units. Conditional probabilities on zero-probability events can be chosen arbitrarily.

Lemma 2 (harmonic dyadic shifts). Let k,r≥1k,r \ge1, let 0<g≤10 < g \le1, and let XX be a law on Z/2kZ\mathbb{Z}/2^k\mathbb{Z}. Suppose

H(Xmod2L)≥gLlog⁡2(1≤L≤k).(1)H(X \mathbin{\mathrm{mod}} 2^L) \ge gL\log2 \qquad(1 \le L \le k). \tag*{(1)}

Put

Lk=∑a=0k−11a+1.\mathcal{L}_k = \sum_{a=0}^{k-1} \frac{1}{a+1}.

Take mutually independent pairs (Ai,Xi)(A_i,X_i), 1≤i≤r1 \le i \le r, such that AiA_i and XiX_i are independent within each pair, XiX_i has law XX, and

P(Ai=a)=1(a+1)Lk,0≤a<k.\mathbb{P}(A_i=a) = \frac{1}{(a+1)\mathcal{L}_k}, \qquad0 \le a < k.

For

S=∑i=1r2AiXi(mod2k),S = \sum_{i=1}^{r} 2^{A_i}X_i \pmod{2^k},

one has

H(S)≥klog⁡2(1−exp⁡[−rg2(log⁡2)22Lk]).(2)H(S) \ge k\log2\left(1-\exp\left[-\frac{rg^2(\log2)^2}{2\mathcal{L}_k}\right]\right). \tag*{(2)}

In particular, if

r≥2Lklog⁡(2k)g2(log⁡2)2,(3)r \ge\frac{2\mathcal{L}_k\log(2k)}{g^2(\log2)^2}, \tag*{(3)}

then B=supp⁡SB=\operatorname{supp} S satisfies ∣B∣>2k−1|B|>2^{k-1}, and B+B=Z/2kZB+B=\mathbb{Z}/2^k\mathbb{Z}.

Proof. Write residues using their canonical kk binary digits, indexed from position zero. Given the lower tt bits of XX, let ptp_t be the conditional probability that bit tt is one. Define

ut=E[2min⁡(pt,1−pt)].u_t=\mathbb{E}[2\min(p_t,1-p_t)].

For binary entropy H(p)=−plog⁡p−(1−p)log⁡(1−p)H(p)=-p\log p-(1-p)\log(1-p),

H(p)≤2min⁡(p,1−p).H(p)\le2\sqrt{\min(p,1-p)}.

Indeed, for 0≤p≤1/20\le p\le1/2,

−plog⁡p≤(2/e)p,−(1−p)log⁡(1−p)≤p≤p,-p\log p\le(2/e)\sqrt{p}, \qquad-(1-p)\log(1-p)\le p\le\sqrt{p},

and 1+2/e<21+2/e<2; use symmetry on the other half. Thus

EH(pt)≤2ut.\mathbb{E}H(p_t)\le\sqrt{2u_t}.

The entropy chain rule and Cauchy-Schwarz give

gLlog⁡2≤∑t<LEH(pt)≤2L∑t<Lut.gL\log2 \le\sum_{t<L} \mathbb{E}H(p_t) \le\sqrt{2L\sum_{t<L}u_t}.

Consequently, with cg=g2(log⁡2)2/2c_g = g^2(\log2)^2/2,

∑t<Lut≥cgL.(4)\sum_{t<L}u_t \ge c_gL. \tag*{(4)}

Fix 0≤j<k0 \le j < k. Let A=(A1,…,Ar)\mathbf{A}=(A_1,\ldots,A_r), and condition on

Gj=σ(A,Xi mod 2max⁡(j−Ai,0):1≤i≤r).\mathcal{G}_j=\sigma\left(\mathbf{A},X_i\bmod2^{\max(j-A_i,0)}:1\le i\le r\right).

On any positive-probability atom, first fix A=a\mathbf{A}=\mathbf{a}. 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 ℓi\ell_i be the least nonnegative residue of 2AiXi2^{A_i}X_i modulo 2j2^j. These residues, and hence the carry

Cj=⌊∑iℓi2j⌋,C_j=\left\lfloor\frac{\sum_i\ell_i}{2^j}\right\rfloor,

are Gj\mathcal{G}_j-measurable. For j=0j=0 all ℓi\ell_i and the carry are zero. A carry may exceed one; only its known parity is used.

If Ai≤jA_i\le j, the current bit of the ii-th summand is bit j−Aij-A_i of XiX_i. If Ai>jA_i>j, it is zero. Thus, writing γi,j\gamma_{i,j} for the conditional sign-bias of that bit given its own lower prefix, and setting γi,j=1\gamma_{i,j}=1 when Ai>jA_i>j,

E[(−1)Sj∣Gj]=(−1)Cj∏iγi,j.(5)\mathbb{E}\left[(-1)^{S_j}\mid\mathcal{G}_j\right]=(-1)^{C_j}\prod_i\gamma_{i,j}. \tag*{(5)}

No independence of carries or output bits is asserted.

Unconditionally, each γi,j\gamma_{i,j} is a function of its own independent pair. Therefore

E[∣E[(−1)Sj∣Gj]∣]=(1−βj)r,βj=1Lk∑a=0juj−aa+1.\mathbb{E}\left[\left|\mathbb{E}\left[(-1)^{S_j}\mid\mathcal{G}_j\right]\right|\right]=(1-\beta_j)^r,\qquad\beta_j=\frac{1}{L_k}\sum_{a=0}^{j}\frac{u_{j-a}}{a+1}.

Equation (4) gives

βj≥∑t=0jut(j+1)Lk≥cgLk.(6)\beta_j\ge\frac{\sum_{t=0}^{j}u_t}{(j+1)L_k}\ge\frac{c_g}{L_k}. \tag*{(6)}

A binary law with absolute sign-bias zz has entropy at least (1−z)log⁡2(1-z)\log2, by concavity. The output’s lower jj bits and the full shift vector are measurable under Gj\mathcal{G}_j, so

H(Sj∣S mod 2j,A)≥H(Sj∣Gj)≥log⁡2[1−(1−βj)r]≥log⁡2[1−e−rcg/Lk].\begin{aligned} H(S_j\mid S\bmod2^j,\mathbf{A}) &\ge H(S_j\mid\mathcal{G}_j)\\ &\ge\log2\left[1-(1-\beta_j)^r\right]\\ &\ge\log2\left[1-e^{-rc_g/L_k}\right]. \end{aligned}

This entropy comparison does not assume independence after conditioning only on the output prefix. Summing over jj, using the chain rule conditioned on the same full vector A\mathbf{A}, and then H(S)≥H(S∣A)H(S)\ge H(S\mid\mathbf{A}), proves (2.2).

Under (2.3), H(S)≥(k−12)log⁡2H(S)\ge(k-\frac{1}{2})\log2. Entropy is at most log support size, hence

∣B∣≥2k/2>2k−1.|B|\ge2^k/\sqrt{2}>2^{k-1}.

For every residue xx, the sets BB and x−Bx-B intersect; thus B+BB+B is the whole group. □

The proof first bounds H(S∣A)H(S\mid\mathbf{A}). Randomness in the unobserved shifts is therefore not being used as a hidden entropy source.

Divisor digits at linear factorial index

Fix

C0=e100,k0=⌈e1000⌉.C_0=e^{100},\qquad k_0=\left\lceil e^{1000}\right\rceil.

For every integer k≥k0k\ge k_0, put

m=⌈C0k⌉,c=8log⁡m,g=c4=2log⁡m,b0=⌊log⁡2m⌋.m=\left\lceil C_0k\right\rceil,\qquad c=\frac{8}{\log m},\qquad g=\frac{c}{4}=\frac{2}{\log m},\qquad b_0=\left\lfloor\log_2m\right\rfloor.

These choices satisfy

c≤13,g≤12,2≤b0<k,b0≥4/c,1log⁡k≤g≤2log⁡k.(7)c\le\frac{1}{3},\qquad g\le\frac{1}{2},\qquad2\le b_0<k,\qquad b_0\ge4/c,\qquad\frac{1}{\log k}\le g\le\frac{2}{\log k}. \tag*{(7)}

For example, log⁡m≤log⁡k+101≤2log⁡k\log m\le\log k+101\le2\log k; b0≥log⁡m−1≥12log⁡m=4/cb_0\ge\log m-1\ge\frac{1}{2}\log m=4/c; and log⁡2m≤32(log⁡k+101)<k\log_2m\le\frac{3}{2}(\log k+101)<k in this range.

For 1≤ℓ≤k1\le\ell\le k, define

Dℓ={0}∪{d:d∣m!, 1≤d<2ℓ}.D_\ell=\{0\}\cup\{d:d\mid m!,\ 1\le d<2^\ell\}.

Lemma 3. Uniformly for k≥k0k\ge k_0 and 1≤ℓ≤k1\le\ell\le k,

∣Dℓ∣≥2cℓ.(8)|D_\ell|\ge2^{c\ell}. \tag*{(8)}

Proof. We use the elementary bound

π(m)≥m2log⁡m(m≥100).(9)\pi(m)\ge\frac{m}{2\log m}\qquad(m\ge100). \tag*{(9)}

To verify it, the central binomial coefficient is at least 2m/(m+1)2^m/(m+1). In its valuation at a prime pp, each prime-power term is zero or one, so the prime’s whole contribution is at most p⌊log⁡pm⌋≤mp^{\lfloor\log_p m\rfloor}\le m. Hence

2mm+1≤(m⌊m/2⌋)≤mπ(m).\frac{2^m}{m+1}\le\binom{m}{\lfloor m/2\rfloor}\le m^{\pi(m)}.

Since log⁡2>2/3\log2>2/3 and m/6>log⁡(m+1)m/6>\log(m+1) for m≥100m\ge100, this proves (9).

Write a=log⁡2ma=\log_2m. If ℓ≤2a+2\ell\le2a+2, all integers through mm divide m!m!, so

∣Dℓ∣≥min⁡(m+1,2ℓ)≥2ℓ/3≥2cℓ;|D_\ell|\ge\min(m+1,2^\ell)\ge2^{\ell/3}\ge2^{c\ell};

here a≥2a\ge2 ensures 2a+2≤3a2a+2\le3a.

Otherwise put v=⌊(ℓ−1)/a⌋v=\left\lfloor(\ell-1)/a\right\rfloor. Then

ℓ2a≤v≤ka.\frac{\ell}{2a}\le v\le\frac{k}{a}.

Every product of vv distinct primes at most mm divides m!m! and is at most mv≤2ℓ−1m^v\le2^{\ell-1}. Distinct prime subsets give distinct integers. With P=π(m)P=\pi(m), (9) yields

Pv≥C02log⁡2,log⁡(P/v)>40.\frac{P}{v}\ge\frac{C_0}{2\log2},\qquad\log(P/v)>40.

In particular P≥vP\ge v. Since

(Pv)≥(P/v)v,\binom{P}{v}\ge(P/v)^v,
log⁡2∣Dℓ∣≥vlog⁡2(P/v)≥20ℓlog⁡m≥cℓ.\log_2|D_\ell|\ge v\log_2(P/v)\ge\frac{20\ell}{\log m}\ge c\ell.

:::

Digit convention. Start at endpoint b0b_0. Define successive endpoints

bs+1=min⁡(2bs,k)b_{s+1}=\min(2b_s,k)

until bL=kb_L=k, and let ℓs=bs+1−bs\ell_s=b_{s+1}-b_s. Choose an initial digit d0d_0 uniformly among the odd integers in [1,2b0)[1,2^{b_0}). Independently choose ds+1d_{s+1} uniformly from DℓsD_{\ell_s}, and set

U=d0+∑s=0L−12bsds+1.U=d_0+\sum_{s=0}^{L-1}2^{b_s}d_{s+1}.

The number J=L+1J=L+1 includes the initial digit. A zero digit contributes no divisor term. Before the final block the endpoint doubles, so J≤2+log⁡2kJ\leq2+\log_2 k, giving the count below. Because all digits are below their block radices, there are no carries between blocks and

1≤U<2k,U is odd,J+1≤3log⁡k.(10)1\leq U<2^k,\qquad U\text{ is odd},\qquad J+1\leq3\log k. \tag*{(10)}

Each initial digit divides m!m!. Every later nonzero term divides 2km!2^k m!, and

2km!∣(m+2k)!.2^k m!\mid(m+2k)!.

Thus UU is a positive sum of at most JJ divisors of M!M!, where M=m+2kM=m+2k.

For 2≤j≤b02\leq j\leq b_0, U mod 2jU\bmod2^j is uniform among odd residues, giving maximum mass 21−j≤2−gj2^{1-j}\leq2^{-gj}. For j>b0j>b_0, let bb be the last completed block endpoint at or below jj. If jj cuts a block, that block has length at most bb, so b≥j/2b\geq j/2; at j=kj=k, take b=kb=k. Fixing a residue fixes every completed digit. Independence and (8) give

max⁡aP(U=a mod 2j)≤2−(b0−1)∏completed appended blocks∣Dℓ∣−1≤21−cb≤21−cj/2≤2−cj/4=2−gj.(11)\max_a\mathbb{P}(U=a\bmod2^j)\leq2^{-(b_0-1)} \prod_{\text{completed appended blocks}}|D_{\ell}|^{-1} \leq2^{1-cb}\leq2^{1-cj/2}\leq2^{-cj/4}=2^{-gj}. \tag*{(11)}

The last inequality uses j>b0≥4/cj>b_0\geq4/c.

Take an independent uniform E∈{0,1}E\in\{0,1\}, and let V=U+EV=U+E be the actual positive integer; let X=V mod 2kX=V\bmod2^k be its residue. Then

1≤V≤2k,1\leq V\leq2^k,

and VV is a sum of at most J+1J+1 divisors of M!M!. The possible integer value V=2kV=2^k supplies a positive witness for residue zero.

Parity of an output residue determines the unique compatible value of EE, since UU is odd. Equation (11), and uniform parity at j=1j=1, therefore imply

max⁡aP(X=a mod 2j)≤2−gj(1≤j≤k).(12)\max_a\mathbb{P}(X=a\bmod2^j)\leq2^{-gj}\qquad(1\leq j\leq k). \tag*{(12)}

In particular H(X mod 2j)≥gjlog⁡2H(X\bmod2^j)\geq gj\log2, as required in Lemma 2.

Short positive representatives of every dyadic residue

Apply Lemma 2 to this XX, taking

r=⌈20(log⁡k)4⌉.r=\left\lceil20(\log k)^4\right\rceil.

This satisfies (3): Lk≤2log⁡kL_k\leq2\log k, log⁡(2k)≤2log⁡k\log(2k)\leq2\log k, g−1≤log⁡kg^{-1}\leq\log k, and log⁡2>2/3\log2>2/3, so the right side of (3) is at most 18(log⁡k)418(\log k)^4.

Each residue in the support BB of the shifted sum has an actual positive witness formed from rr shifted integers ViV_i. Expanding their divisor representations gives at most r(J+1)r(J+1) terms. If d∣M!d \mid M! and 0≤a<k0 \leq a < k, then

2ad∣2kM!∣(M+2k)!.2^a d \mid2^k M! \mid(M+2k)!.

All terms therefore divide the single common factorial

F(k)!=(m+4k)!,F(k)≤A0k,A0=C0+5.(13)F(k)! = (m+4k)!, \qquad F(k) \leq A_0 k, \qquad A_0 = C_0+5. \tag*{(13)}

Its index does not multiply by the number of additive copies.

As B+BB+B covers the group, every residue modulo 2k2^k has a positive integer representative SS which is a sum, with repetition allowed, of at most

2r(J+1)≤200(log⁡k)5(14)2r(J+1) \leq200(\log k)^5 \tag*{(14)}

divisors of F(k)!F(k)!. Uniformly over the chosen residue,

S≤⌈200(log⁡k)5⌉F(k)!.(15)S \leq\lceil200(\log k)^5\rceil F(k)!. \tag*{(15)}

There is also the smaller bound S≤r22kS \leq r2^{2k}, 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 w≥1w \geq1 positive divisors of an integer NN is a sum of at most ww distinct positive divisors of

2⌊log⁡2w⌋N2^{\lfloor\log_2 w\rfloor}N

with the same value.

Proof. Write N=2vNoddN=2^vN_{\mathrm{odd}}. Group the terms according to their odd part d∣Noddd \mid N_{\mathrm{odd}}. In a group, the total is dAddA_d, where AdA_d is a sum of at most ww powers 2a2^a, 0≤a≤v0 \leq a \leq v, hence Ad≤w2vA_d \leq w2^v. Its binary expansion has largest exponent at most v+⌊log⁡2w⌋v+\lfloor\log_2 w\rfloor. 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. □\square

Lemma 5 (one exact integer). For every sufficiently large integer R>0R>0, put T=⌈log⁡2(R+1)⌉T=\lceil\log_2(R+1)\rceil. Then RR is a sum of O((log⁡T)7)O((\log T)^7) distinct divisors of (4T)!(4T)!.

Proof. Fix an absolute D≥16A0/log⁡2D \geq16A_0/\log2. For a current positive integer RiR_i with bit length TiT_i, take

ki=⌊TiDlog⁡(Ti+2)⌋.k_i=\left\lfloor\frac{T_i}{D\log(T_i+2)}\right\rfloor.

Fix a threshold T0T_0 so that, for every Ti≥T0T_i \geq T_0,

  • ki≥k0k_i \geq k_0 and ki≥Ti/[2Dlog⁡(Ti+2)]≥2k_i \geq T_i/[2D\log(T_i+2)] \geq2;

  • F(ki)≤TiF(k_i) \leq T_i;

  • the upper bound in (15) is at most 2Ti/22^{T_i/2}.

These are compatible eventual conditions. For the height condition, use

log⁡(F(ki)!)≤A0kilog⁡(A0ki)\log(F(k_i)!) \le A_0 k_i \log(A_0 k_i)

and, eventually, log⁡(A0ki)≤2log⁡Ti\log(A_0 k_i) \le2\log T_i. The factorial contribution is at most 2A0Ti/D2A_0T_i/D; the logarithm of the count in (15) is O(log⁡log⁡Ti)O(\log\log T_i). Our fixed choice of DD, followed by a fixed sufficiently large T0T_0, leaves ample margin below (Ti/2)log⁡2(T_i/2)\log2. All constants and thresholds are independent of the target RR.

Choose the positive representative Si≡Ri(mod2ki)S_i \equiv R_i \pmod{2^{k_i}} from § 4. Since Ri≥2Ti−1R_i \ge2^{T_i-1},

0<Si≤2Ti/2<Ri.0 < S_i \le2^{T_i/2} < R_i.

Thus

Ri=Si+2kiRi+1,0<Ri+1<Ri/2ki.(16)R_i = S_i + 2^{k_i}R_{i+1}, \qquad0 < R_{i+1} < R_i/2^{k_i}. \tag*{(16)}

Its bit length satisfies Ti+1≤Ti−kiT_{i+1} \le T_i-k_i. Continue while Ti≥T0T_i \ge T_0, and represent the final bounded integer by a bounded number of copies of 1.

The potential (log⁡Ti)2(\log T_i)^2 drops by an absolute positive amount at each large stage. Indeed ki/Ti≫1/log⁡Tik_i/T_i \gg1/\log T_i, and

(log⁡Ti)2−(log⁡Ti+1)2≥(ki/Ti)log⁡Ti≫1.(\log T_i)^2 - (\log T_{i+1})^2 \ge(k_i/T_i)\log T_i \gg1.

There are O((log⁡T)2)O((\log T)^2) stages. Each uses O((log⁡T)5)O((\log T)^5) terms, so the total count before merging is

w=O((log⁡T)7).(17)w = O((\log T)^7). \tag*{(17)}

Every unscaled term divides the original T!T!, since F(ki)≤Ti≤TF(k_i) \le T_i \le T; the terminal copies of 1 do also. Let ei=∑s<ikse_i=\sum_{s<i} k_s be a lifting exponent. Positivity in (16) implies

R≥2eiRi≥2ei,R \ge2^{e_i}R_i \ge2^{e_i},

so ei≤Te_i \le T, including the terminal stage. Every lifted term therefore divides 2TT!2^T T!.

Apply Lemma 4 with b=⌊log⁡2w⌋=O(log⁡log⁡T)b=\lfloor\log_2 w\rfloor=O(\log\log T). The distinct resulting divisors divide 2T+bT!2^{T+b}T!. Increase the fixed starting threshold to T1≥T0T_1\ge T_0 so that b≤⌊T/2⌋b\le\lfloor T/2\rfloor. Among the 3T3T integers after TT, at least ⌊3T/2⌋\lfloor3T/2\rfloor are even. Hence

2T+bT!∣(4T)!.2^{T+b}T! \mid(4T)!.

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 kik_i or below k0k_0.

Factorial radix and the global bound

First, factorials are practical with the inclusive convention. Let H(n)=h(n!)H(n)=h(n!). For n=1n=1, H(1)=1H(1)=1. Given 0≤R≤n!0\le R\le n!, write

R=na+r,0≤r<n,0≤a≤(n−1)!.R=na+r,\qquad0\le r<n,\qquad0\le a\le(n-1)!.

Use the empty representation if a=0a=0; otherwise scale an inclusive divisor representation of aa by nn. Every scaled divisor divides n!n! and is at least nn. If r>0r>0, the integer rr itself divides n!n! and is smaller than all scaled terms. Thus distinctness is preserved, and, for example, H(n)≤nH(n)\le n is a valid finite base bound.

Fix

c0=log⁡216,ℓ=⌊c0nlog⁡n⌋,m′=n−ℓ,Q=n!m′!.c_0=\frac{\log2}{16},\qquad\ell=\left\lfloor\frac{c_0n}{\log n}\right\rfloor,\qquad m'=n-\ell,\qquad Q=\frac{n!}{m'!}.

Choose a fixed n∗n_* so that ℓ≥c0n/(2log⁡n)≥1\ell\ge c_0n/(2\log n) \ge1, m′≥1m' \ge1, and all following eventual bounds hold for n≥n∗n \ge n_*.

For any 0≤R≤n!0 \le R \le n!, write

R=aQ+r,0≤r<Q,0≤a≤m′!.R = aQ + r,\qquad0 \le r < Q,\qquad0 \le a \le m'!.

A sufficiently large positive remainder has bit length

T(r)=⌈log⁡2(r+1)⌉≤log⁡2Q+1≤ℓlog⁡nlog⁡2+1≤n/16+1.T(r) = \lceil\log_2(r+1)\rceil\le\log_2 Q + 1 \le\frac{\ell\log n}{\log2} + 1 \le n/16 + 1.

Thus 4T(r)<n4T(r) < n eventually. Lemma 5 represents rr by O((log⁡n)7)O((\log n)^7) distinct divisors of (4T(r))!(4T(r))!, hence of n!n!. The finitely many remainders outside Lemma 5’s range are themselves divisors once nn exceeds that fixed finite set; r=0r=0 uses the empty sum. This is uniform over all r<Qr<Q.

Scale a distinct inclusive representation of aa by QQ. Each high term is a divisor of n!n! and is at least QQ. Every positive low term is smaller than QQ, because its whole positive sum is r<Qr<Q. The families do not overlap. Therefore

H(n)≤H(n−ℓ)+O((log⁡n)7).(18)H(n) \le H(n-\ell) + O((\log n)^7). \tag*{(18)}

The endpoint R=n!R=n! is included: it has a=m′!,r=0a=m'!, r=0, and also has its direct one-term representation.

For n≥n∗n \ge n_*,

(log⁡n)2−(log⁡(n−ℓ))2≥(ℓ/n)log⁡n≥c0/2.(\log n)^2 - (\log(n-\ell))^2 \ge(\ell/n)\log n \ge c_0/2.

There are O((log⁡n)2)O((\log n)^2) radix steps down to the fixed base. Summing the uniform cost in (6.1) proves

h(n!)=O((log⁡n)9),h(n!) = O((\log n)^9),

as claimed in Theorem 1. □

Strict-power target and the other two questions

The pinned Formal Conjectures statement uses the inclusive endpoint 1≤R≤N1 \le R \le N and asks for a positive real CC with

practicalH⁡(n!)<(log⁡n)C\operatorname{practicalH}(n!) < (\log n)^C

for all sufficiently large natural nn. A set of divisors whose sum is RR 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 Ch≥1C_h \ge1 and n0≥3n_0 \ge3 as in Theorem 1. For

n≥max⁡{n0,⌈eCh+1⌉},n \ge\max\{n_0,\lceil e^{C_h+1}\rceil\},

one has log⁡n>Ch\log n > C_h, and consequently

practicalH⁡(n!)≤Ch(log⁡n)9<(log⁡n)10.\operatorname{practicalH}(n!) \le C_h(\log n)^9 < (\log n)^{10}.

Thus C=10>0C=10>0 gives the formal strict-power quantifiers, including the endpoint n!n!. 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 ε>0\varepsilon> 0 and write x=log⁡nx = \log n. The exponential series gives

nε=eεx≥(εx)1010!>Chx9n^{\varepsilon} = e^{\varepsilon x} \ge\frac{(\varepsilon x)^{10}}{10!} > C_h x^9

once x>10!Chε−10x > 10!C_h\varepsilon^{-10}.

For (a), the elementary factorial estimate (n+1)!≥2n(n + 1)! \ge2^n gives

log⁡log⁡((n+1)!)≥log⁡n+log⁡log⁡2.\log\log((n + 1)!) \ge\log n + \log\log2.

Consequently log⁡(n+1)≤4log⁡log⁡((n+1)!)\log(n + 1) \le4\log\log((n + 1)!) for all sufficiently large nn. Set y=log⁡log⁡((n+1)!)y = \log\log((n + 1)!). Theorem 1 yields

h((n+1)!)≤Ch49y9<y10h((n + 1)!) \le C_h4^9y^9 < y^{10}

once y>Ch49y > C_h4^9. 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. [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. [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. [3]Plasma AI, Subexponential support of short factorial divisor blocks, L64, updated 14 October 2026. Statement; proof. Accessed 1 November 2026.
  4. [4]Plasma AI, Full-divisor residue spread and a quantitative mixing criterion, L66, updated 14 October 2026. Statement; proof. Accessed 1 November 2026.
  5. [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. [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. [7]The Formal Conjectures Authors, Erdős Problem 18, Lean statements, commit a64e959c32c270df4dd0d96d2027481f15750534, Apache-2.0.
  8. [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. [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. [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. [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. [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. [13]S. D. Hughes, Sums of distinct divisors of factorials, arXiv:2609.10902v1, 9 September 2026.arxiv.org/abs/2609.10902
  14. [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.

Paper details

vlnc:W_arjk8eqm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex, Plasma AI

View statement
Looking for related papers…
Contents