betaFeedback

WorksMathematics

Erdős problem 859: a refutation of the logarithmic density law

Abstract

Let dtd_t be the natural density of integers nn for which tt is a sum of distinct positive divisors of nn. We prove lim inf⁡t→∞(−log⁡dt)/log⁡log⁡t=δ\liminf_{t\to\infty}(-\log d_t)/\log\log t=\delta and (log⁡t)δdt→0(\log t)^\delta d_t\to0, where δ=1−(1+log⁡log⁡2)/log⁡2\delta=1-(1+\log\log2)/\log2. Together these exclude every pure logarithmic power asymptotic with a positive leading coefficient. This exposition gives the exact finite prime model and the density and change-of-measure reductions. It explains the divisor-interval saving and the arithmetic construction and links to the complete formal proof.

The question and the result

All logarithms are natural. Limits in the target parameter tt are taken through positive integers.

Put

At={n≥1:∃S⊆{d≥1:d∣n}, ∑d∈Sd=t}.A_t=\left\{n\ge1:\exists S\subseteq\{d\ge1:d\mid n\},\ \sum_{d\in S}d=t\right\}.

The subset SS is finite and contains no repeated divisor. If it exists, the natural density is

dt=lim⁡N→∞#(At∩{1,…,N})N.d_t=\lim_{N\to\infty}\frac{\#(A_t\cap\{1,\ldots,N\})}{N}.

In his 1970 paper, printed page 130, Erdős introduces this set, notes the existence of its density, and proposes the asymptotic

dt∼c1(log⁡t)c2,c1,c2>0,(1)d_t\sim\frac{c_1}{(\log t)^{c_2}},\qquad c_1,c_2>0, \tag*{(1)}

as equation (33) [1]. This is Erdős Problem 859 [2]. The symbol ∼\sim means that the ratio of the two sides tends to one. A bound up to constants would be a different assertion.

Theorem 1.1 (Accepted result). The density dtd_t exists and is positive for every t≥1t\ge1. There are no positive constants c1,c2c_1,c_2 satisfying (1).

The proof supplies two complementary estimates. Set

δ=1−1+log⁡log⁡2log⁡2,0<δ<1.(2)\delta=1-\frac{1+\log\log2}{\log2},\qquad0<\delta<1. \tag*{(2)}

Then the submitted development proves

lim inf⁡t→∞−log⁡dtlog⁡log⁡t=δ,(3)\liminf_{t\to\infty}\frac{-\log d_t}{\log\log t}=\delta, \tag*{(3)}
(log⁡t)δdt⟶0.(4)(\log t)^\delta d_t\longrightarrow0. \tag*{(4)}

The distinction between a lower limit in (3) and an ordinary limit is essential. Neither a full limit for that expression nor an exact replacement asymptotic for dtd_t is asserted here.

Density exists for an elementary reason

Lemma 2.1 (Periodicity). For fixed t≥1t \ge1, membership in AtA_t among positive integers depends only on the residue class modulo t!t!.

Proof. Every divisor appearing in a sum equal to tt is at most tt. Each positive integer d≤td \le t divides t!t!. Consequently, if n≡m(modt!)n \equiv m \pmod{t!}, then d∣nd \mid n if and only if d∣md \mid m for every such dd. The same finite subsets of these divisors can be used for nn and mm, and their sums agree.

Let M=t!M=t! and choose the positive representatives 1,…,M1,\ldots,M. Writing N=qM+rN=qM+r with 0≤r<M0 \le r<M gives

#(At∩[1,N])=q#(At∩[1,M])+O(M).\#(A_t \cap[1,N])=q\#(A_t \cap[1,M])+O(M).

For fixed tt, divide by NN and let NN tend to infinity. This proves

dt=#(At∩[1,t!])t!(5)d_t=\frac{\#(A_t\cap[1,t!])}{t!} \tag*{(5)}

Thus the density is an exact finite residue-class average. Moreover, every positive multiple of tt belongs to AtA_t, by using the single divisor tt. Hence 1/t≤dt≤11/t \le d_t \le1 for t≥1t \ge1. In particular the logarithm of dtd_t is defined. The Lean proof uses a periodic real-valued indicator and its average. The choice of counting 0≤n<N0 \le n<N rather than 1≤n≤N1 \le n \le N changes only a bounded number of terms and therefore preserves the density.

An exact finite model for prime divisibility

The lower construction uses finite probability spaces. Let PP be a finite set of primes. For T⊆PT \subseteq P, define

μP(T)=∏p∈T1p∏p∈P∖T(1−1p),nT=∏p∈Tp.(6)\mu_P(T)=\prod_{p\in T}\frac{1}{p}\prod_{p\in P\setminus T}\left(1-\frac{1}{p}\right),\qquad n_T=\prod_{p\in T}p. \tag*{(6)}

The Chinese remainder theorem shows that μP(T)\mu_P(T) is exactly the natural density of integers whose prime divisors in PP are precisely TT. The coordinates are independent, with inclusion probability 1/p1/p.

Proposition 3.1 (Finite witnesses and actual density). For each t≥1t \ge1,

∑T⊆PμP(T)1{nT∈At}≤dt.\sum_{T\subseteq P}\mu_P(T)1_{\{n_T\in A_t\}}\le d_t.

Proof. A representation using divisors of nTn_T remains valid for every multiple of nTn_T. On the prime-divisibility pattern TT, the integer nTn_T divides the sampled integer. Each successful pattern is therefore contained in AtA_t. The patterns are disjoint and have the densities (6), proving the claim by finite addition.

Exponential tilting

For λ>0\lambda>0, set

ZP(λ)=∏p∈P(1+λ−1p),μP,λ(T)=λ∣T∣μP(T)ZP(λ).(7)Z_P(\lambda)=\prod_{p\in P}\left(1+\frac{\lambda-1}{p}\right),\qquad\mu_{P,\lambda}(T)=\frac{\lambda^{|T|}\mu_P(T)}{Z_P(\lambda)}. \tag*{(7)}

Expanding a finite product proves ∑Tλ∣T∣μP(T)=ZP(λ)\sum_T\lambda^{|T|}\mu_P(T)=Z_P(\lambda), so this is a probability law. Its independent inclusion probabilities are zp=λ/(p+λ−1)z_p=\lambda/(p+\lambda-1). Under the original law, its likelihood ratio is Lλ(T)=λ∣T∣/ZP(λ)L_\lambda(T)=\lambda^{|T|}/Z_P(\lambda). For every real qq,

EP,1Lλq=ZP(λq)ZP(λ)q.(8)\mathbb{E}_{P,1}L_\lambda^q=\frac{Z_P(\lambda^q)}{Z_P(\lambda)^q}. \tag*{(8)}

This follows by substituting the likelihood and applying the same finite product identity. The denominator is positive.

The critical tilt is λ∗=1/log⁡2\lambda_* = 1/\log2. A logarithmic prime band u<log⁡p≤2uu < \log p \le2u has reciprocal-prime mass approaching log⁡2\log2, and its tilted expected prime count approaches λlog⁡2\lambda\log2. Thus λ>λ∗\lambda> \lambda_* makes that expected count exceed one. The construction uses this excess to build a rich system of divisor logarithms while keeping the probability cost explicit.

Conditioning on an adaptively chosen window

One later prime window is selected after observing earlier primes. If A⊆PA \subseteq P is the observed universe and Q(S)⊆P∖AQ(S) \subseteq P \setminus A is chosen from the observation S⊆AS \subseteq A, then for any function GG,

EP,λG(T∩A,T∩Q(T∩A))=∑S⊆AμA,λ(S)∑U⊆Q(S)μQ(S),λ(U)G(S,U).\mathbb{E}_{P,\lambda}G(T\cap A,T\cap Q(T\cap A))=\sum_{S\subseteq A}\mu_{A,\lambda}(S)\sum_{U\subseteq Q(S)}\mu_{Q(S),\lambda}(U)G(S,U).

For each fixed SS, the remaining coordinates retain their product law. Coordinates outside A∪Q(S)A\cup Q(S) sum to one. Consequently a bound uniform over successful past observations can be applied conditionally, without paying a union bound over all past configurations.

The contradiction from the two estimates

This section converts (3)–(4) into the refutation. The proofs of those two inputs are discussed in the next sections and are provided by the linked Lean artifact.

Lemma 4.1 (An asymptotic power determines the logarithmic rate). Let at>0a_t>0 eventually, and suppose at∼c(log⁡t)−pa_t\sim c(\log t)^{-p}, where c>0c>0 and p∈Rp\in\mathbb{R}. Then

−log⁡atlog⁡log⁡t⟶p,(log⁡t)pat⟶c.\frac{-\log a_t}{\log\log t}\longrightarrow p,\qquad(\log t)^p a_t\longrightarrow c.

Proof. There is a positive sequence ut→1u_t\to1 with at=c(log⁡t)−puta_t=c(\log t)^{-p}u_t for all sufficiently large tt. Taking logarithms yields

−log⁡atlog⁡log⁡t=p−log⁡c+log⁡utlog⁡log⁡t.\frac{-\log a_t}{\log\log t}=p-\frac{\log c+\log u_t}{\log\log t}.

Since log⁡ut→0\log u_t\to0 and log⁡log⁡t→∞\log\log t\to\infty, the last fraction tends to zero. The second claim follows from (log⁡t)pat=cut(\log t)^p a_t=cu_t. □

Proof of Theorem 1.1, using the two estimates. Density existence and positivity were established above. Suppose (1) holds. Applying Lemma 4.1 with at=dta_t=d_t shows that the logarithmic rate has limit c2c_2. Its lower limit is therefore c2c_2. Equation (3) forces c2=δc_2=\delta. The second part of the lemma gives (log⁡t)δdt→c1(\log t)^\delta d_t\to c_1. By (4) the same sequence tends to zero, so uniqueness of the limit gives c1=0c_1=0, contradicting c1>0c_1>0. □

This argument excludes every real exponent pp with a positive constant coefficient. Only positive exponents are needed for the original question. Values at t=1t=1, where log⁡t=0\log t=0, play no role in an eventual asymptotic statement.

The upper estimate: reducing sums to divisor intervals

For integers 0≤y≤t0\le y\le t, write

B(y,t)={n≥1:∃d∣n, y<d≤t},D(y,t)=dens⁡B(y,t).B(y,t)=\{n\ge1:\exists d\mid n,\ y<d\le t\},\qquad D(y,t)=\operatorname{dens} B(y,t).

These densities also exist by periodicity. Define the sum of the small divisors by Sy(n)=∑1≤d≤yd∣ndS_y(n)=\sum_{\substack{1\le d\le y\\d\mid n}}d.

Proposition 5.1 (Exact density bound). For t>0t>0 and integers 0≤y≤t0\le y\le t,

dt≤D(y,t)+yt.(9)d_t\le D(y,t)+\frac{y}{t}. \tag*{(9)}

Proof. If n∈Atn \in A_t but n∉B(y,t)n \notin B(y,t), all the divisors in a representation of tt are at most yy. Thus Sy(n)≥tS_y(n) \ge t. For every positive integer nn this gives

t1At(n)≤t1B(y,t)(n)+Sy(n).t\mathbf{1}_{A_t}(n) \le t\mathbf{1}_{B(y,t)}(n) + S_y(n).

For each fixed positive dd, multiples of dd have density 1/d1/d. Therefore the finite sum defining SyS_y has limiting mean

lim⁡N→∞1N∑n=1NSy(n)=∑d=1yd⋅1d=y.\lim_{N\to\infty}\frac{1}{N}\sum_{n=1}^{N}S_y(n)=\sum_{d=1}^{y}d\cdot\frac{1}{d}=y.

Average the pointwise inequality and divide by tt to obtain (9). □

A finite dyadic reduction

For a positive integer JJ, put yj=⌊t/2j+1⌋y_j=\lfloor t/2^{j+1}\rfloor for 0≤j<J0\le j<J. The interval above ⌊t/2J⌋\lfloor t/2^J\rfloor is covered by these dyadic pieces. Integer rounding adds at most the single divisor 2yj+12y_j+1 at each step, whose multiples have density 1/(2yj+1)1/(2y_j+1). The union bound and Proposition 5.1 yield

dt≤∑j=0J−1(D(yj,2yj)+12yj+1)+2−J.(10)d_t\le\sum_{j=0}^{J-1}\left(D(y_j,2y_j)+\frac{1}{2y_j+1}\right)+2^{-J}. \tag*{(10)}

In particular, a uniform bound D(yj,2yj)≤M(t)D(y_j,2y_j)\le M(t) gives

dt≤JM(t)+J2⌊t/2J⌋+1+2−J.(11)d_t\le JM(t)+\frac{J}{2\lfloor t/2^J\rfloor+1}+2^{-J}. \tag*{(11)}

The submitted proof supplies a nonnegative envelope M(t)M(t), valid uniformly for t≤y≤t\sqrt{t}\le y\le t, such that

(log⁡log⁡t)(log⁡t)δM(t)⟶0.(12)(\log\log t)(\log t)^\delta M(t)\longrightarrow0. \tag*{(12)}

Its divisor-interval analysis develops Ford-type bounds, including control of nonsquarefree contributions by powerful-number sums. Ford’s classical divisor-distribution work concerns D(y,2y)D(y,2y) [5]. The reduction above is what connects this counting problem to sums of distinct divisors.

For the limiting argument take J=⌈log⁡2log⁡t⌉J=\lceil\log_2\log t\rceil. Then J=O(log⁡log⁡t)J=O(\log\log t), 2−J≤1/log⁡t2^{-J}\le1/\log t, and eventually ⌊t/2J⌋≥t\lfloor t/2^J\rfloor\ge\sqrt{t}. After multiplying (11) by (log⁡t)δ(\log t)^\delta, its three terms tend to zero. The first does so by (12), the second because t\sqrt{t} dominates logarithmic powers, and the third because δ<1\delta<1. This proves (4) from the stated envelope. The Lean source provides the full envelope proof and exact rounded-endpoint estimates.

Logarithmic support and its weighted size

For a finite prime set SS and thickness h≥0h\ge0, put

Lh(S)=⋃U⊆S[∑p∈Ulog⁡p,∑p∈Ulog⁡p+h],Lh(S)=∣Lh(S)∣,L_h(S)=\bigcup_{U\subseteq S}\left[\sum_{p\in U}\log p,\sum_{p\in U}\log p+h\right],\qquad L_h(S)=|L_h(S)|,

where ∣⋅∣|\cdot| denotes Lebesgue measure. This is a union of intervals around logarithms of actual divisors of the squarefree product nSn_S. For every I⊆SI\subseteq S,

Lh(S)≤2∣S∣−∣I∣(h+∑p∈Ilog⁡p),Lh(S∪{p})≤2Lh(S).(13)L_h(S)\le2^{|S|-|I|}\left(h+\sum_{p\in I}\log p\right),\qquad L_h(S\cup\{p\})\le2L_h(S). \tag*{(13)}

Indeed, fix the selected subset outside II. The remaining intervals are contained in one translate of [0,h+∑p∈Ilog⁡p][0,h+\sum_{p\in I}\log p]. There are at most 2∣S∣−∣I∣2^{|S|-|I|} translations. Separating subsets according to the presence of one additional prime gives the second inequality.

Set wp=1/(p−1)w_p = 1/(p-1), w(S)=∏p∈Swpw(S) = \prod_{p\in S} w_p, and Zh(P)=∑S⊆Pw(S)Lh(S)Z_h(P) = \sum_{S\subseteq P} w(S)L_h(S). The source proves constants Cs,Cc>0C_s,C_c > 0 and a threshold, uniform in finite prime sets P⊆[2,N]P \subseteq[2,N] and h≥0h \ge0, such that

Zh(P)≤2h+Cs(h+Cc)(log⁡N)2−δ(log⁡log⁡N)5/4.(14)Z_h(P) \le2h + C_s(h+C_c)\frac{(\log N)^{2-\delta}}{(\log\log N)^{5/4}}. \tag*{(14)}

Three ingredients explain the saving. First, the disjoint intervals of lengths 1/(p−1)1/(p-1) in cumulative prime-weight coordinates convert a sum over distinct primes to an integral over disjoint cells. Permutation symmetry supplies the factor 1/k!1/k! for a kk-element prime set. Tuples with repeated primes are not assigned an arithmetic meaning. Second, an ordered-coordinate barrier bounds the measure of configurations whose prefix subset sums have large support. Third, a bin-occupancy estimate controls exceptionally crowded cells. With the occupancy cutoff of order v1/4v^{1/4} and the square-root factor in Stirling’s bound, the calculation leaves a factor v−5/4v^{-5/4}, where vv is comparable to log⁡log⁡N\log\log N. The manuscript gives these steps as Lemmas 3.3–3.6 and Proposition 3.7 [3], and the formal source proves their finite counterparts.

Stopping primes and the squarefree estimate

Let R(y)R(y) be the probability that the product of primes selected with probabilities 1/p1/p, among primes at most 2y2y, has a divisor in (y,2y](y,2y]. Select the largest prime in a witnessing divisor. Its smaller prime factors provide a point in logarithmic support. A reciprocal-prime interval estimate controls the possible stopping primes, and a support-weighted fourth moment controls configurations with an unfavorable denominator. The resulting formal estimate has an absolute constant CC with

R(y)≤C(log⁡(2y))2Zlog⁡2({p:p≤2y}).R(y) \le\frac{C}{(\log(2y))^2} Z_{\log2}(\{p:p\le2y\}).

Combining this with (14), and absorbing rounding in the prime cutoff, gives absolute constants C1,C2C_1,C_2 such that

R(y)≤C1(log⁡(2y))2+C2(log⁡(2y))δ(log⁡log⁡(2y))5/4.(15)R(y) \le\frac{C_1}{(\log(2y))^2}+\frac{C_2}{(\log(2y))^\delta(\log\log(2y))^{5/4}}. \tag*{(15)}

for all sufficiently large yy. This is a probability for the finite prime law, whereas D(y,2y)D(y,2y) also includes integers with prime powers.

Restoring prime powers

Call b≥1b \ge1 powerful if every prime dividing bb occurs to exponent at least two, including b=1b=1. The useful summability bounds are

∑b powerfulτ(b)b<∞,∑b powerfulb>L1b≪L−1/4.(16)\sum_{b\ \mathrm{powerful}}\frac{\tau(b)}{b}<\infty,\qquad\sum_{\substack{b\ \mathrm{powerful}\\b>L}}\frac{1}{b}\ll L^{-1/4}. \tag*{(16)}

To see their scale, write a powerful integer uniquely as a2c3a^2c^3 with cc squarefree. Then ∑b powerfulb−3/4\sum_{b\ \mathrm{powerful}} b^{-3/4} converges by comparison with ∑a,c≥1a−3/2c−9/4\sum_{a,c\ge1}a^{-3/2}c^{-9/4}. The elementary divisor bound τ(b)≪b1/4\tau(b)\ll b^{1/4} proves the first claim. For the second use b−1≤L−1/4b−3/4b^{-1}\le L^{-1/4}b^{-3/4} when b>Lb>L.

Cap each prime valuation at a finite integer cp≥2c_p\ge2. The one-prime weights are

νp,cp(e)={(1−1/p)p−e,0≤e<cp,p−cp,e=cp.\nu_{p,c_p}(e)= \begin{cases} (1-1/p)p^{-e}, & 0\le e<c_p,\\ p^{-c_p}, & e=c_p. \end{cases}

The final atom includes all valuations at least cpc_p. The Chinese remainder theorem identifies these weights with actual residue-class densities. Large enough caps determine all divisors in the interval under consideration exactly.

Fixing the powerful part bb leaves primes of exponent zero or one. Their conditional inclusion probability is 1/(p+1)1/(p+1), at most 1/p1/p. The total mass of the fixed powerful part is at most 1/b1/b.

Every divisor has the form fa(U)fa(U), with f∣bf \mid b and UU a subset of the remaining primes whose product is a(U)a(U). Monotonicity of the divisor-interval event and a union bound therefore give

D(y,2y)≤∑b powerfulb≤y1b∑f∣bR(y/f)+∑b powerfulb>y1b.D(y,2y) \le\sum_{\substack{b\ \mathrm{powerful}\\b\le\sqrt{y}}} \frac{1}{b}\sum_{f\mid b} R(y/f) + \sum_{\substack{b\ \mathrm{powerful}\\b>\sqrt{y}}} \frac{1}{b}.

The formal argument first obtains this domination in a finite capped model. The convergent majorants in (16) then bound it uniformly. If f∣b≤yf\mid b\le\sqrt{y}, then y≤y/f≤y\sqrt{y}\le y/f\le y, so (15) is uniform over all these shifts. It follows that suitable positive constants satisfy

D(y,2y)≤F(y):=A1(log⁡y)2+A2(log⁡y)δ(log⁡log⁡y)5/4+A3y1/8.(17)D(y,2y) \le F(y) := \frac{A_1}{(\log y)^2}+\frac{A_2}{(\log y)^\delta(\log\log y)^{5/4}}+\frac{A_3}{y^{1/8}}. \tag*{(17)}

for every sufficiently large integer yy. The last exponent is (y)−1/4=y−1/8(\sqrt{y})^{-1/4}=y^{-1/8}. Each term in FF is eventually decreasing, and

(log⁡y)δlog⁡log⁡y F(y)=A1log⁡log⁡y(log⁡y)2−δ+A2(log⁡log⁡y)−1/4+A3(log⁡y)δlog⁡log⁡yy1/8⟶0.(\log y)^\delta\log\log y\,F(y)=A_1\frac{\log\log y}{(\log y)^{2-\delta}}+A_2(\log\log y)^{-1/4}+A_3\frac{(\log y)^\delta\log\log y}{y^{1/8}}\longrightarrow0.

Thus M(t)=F(t)M(t)=F(\sqrt{t}) is an envelope in (12). The exponent 5/45/4 is useful because the final dyadic union costs one factor of log⁡log⁡t\log\log t, leaving a factor tending to zero.

The lower construction: why the exponent cannot increase

The upper estimate alone would allow a faster logarithmic decay. The complementary construction prevents any larger exponent from holding uniformly at large targets. For every ε>0\varepsilon>0 there are arbitrarily large integers tt with

dt≥exp⁡(−(δ+ε)log⁡log⁡t)=(log⁡t)−(δ+ε).(18)d_t\ge\exp\bigl(-(\delta+\varepsilon)\log\log t\bigr)=(\log t)^{-(\delta+\varepsilon)}. \tag*{(18)}

Proposition 6.1. Equations (4) and (18) imply (3).

Proof. Since the positive sequence (log⁡t)δdt(\log t)^\delta d_t tends to zero, it is eventually at most one. Thus −log⁡dt/log⁡log⁡t≥δ-\log d_t/\log\log t\ge\delta once log⁡log⁡t>0\log\log t>0. This proves the lower bound on the lower limit. For each ε>0\varepsilon>0, (18) gives arbitrarily large tt for which the same quotient is at most δ+ε\delta+\varepsilon. Its lower limit is consequently at most δ+ε\delta+\varepsilon for every ε>0\varepsilon>0, proving equality. □

Proper divisor cubes and logarithmic coverage

Fix a tilt λ∗<λ<2\lambda_*<\lambda<2 and write

J(λ)=λlog⁡2−1−log⁡(λlog⁡2).J(\lambda)=\lambda\log2-1-\log(\lambda\log2).

The lower construction has a scale k→∞k\to\infty. A block event in disjoint logarithmic prime bands produces a core of kk selected primes at probability at least exp⁡(−(J(λ)+o(1))k)\exp(-(J(\lambda)+o(1))k) under the tilted law. The prefix counts obey a ballot-type condition. Carefully placed single-prime suffixes control the endpoint size of the product. Section 4.2 of the manuscript gives explicit choices of the block lengths and the other parameters [3]. The accepted source verifies their eventual inequalities.

For a positive integer HH, a divisor cube of bb is called HH-proper when

(cd)d∣b⟼∑d∣bcdd(c_d)_{d\mid b}\longmapsto\sum_{d\mid b}c_d d

is injective on {−H,…,H}{d:d∣b}\{-H,\ldots,H\}^{\{d:d\mid b\}}.

This condition means that the many bounded signed combinations are actually distinct integers. It is stronger than the divisors themselves being distinct. The construction removes improper cores at a probability cost negligible compared with the block event. A first failed extension by a new prime would give a nontrivial equation U+pV=0U+pV=0 between old cube differences. Properness of the old cube forces V≠0V\ne0. Then U≠0U\ne0, and the bad new prime must divide one of a controlled finite collection of nonzero integers. The very large prime windows make the total forbidden mass small. Properness passes to divisor subcubes by extending coefficients by zero.

In the same base window, a supercritical tilted selection has a positive amount of logarithmic support with probability bounded below. The source uses second-moment estimates for smoothed subset sums to establish this finite statement. The event of containing a suitable proper core and the event of having large support are increasing in the selected prime set. Positive correlation for a finite product law can therefore combine them.

Prime pairs fill most of a logarithmic interval

A pair of fresh primes pip_i, qiq_i supplies a logarithmic displacement gi=log⁡pi−log⁡qig_i=\log p_i-\log q_i. After adding the common baseline ∑ilog⁡qi\sum_i \log q_i, choosing a subset of these displacements is the same as choosing one prime from each pair. The resulting points are logarithms of actual divisors.

The first stage reduces the uncovered fraction of an interval of length LL to at most 2−102^{-10}. The second stage uses narrower windows. Suppose AA covers all but measure EE of an interval II, and a random shift gg is supported on [−w,w][-w,w] with density at most 2/w2/w. On the interval I′I' obtained by trimming ww from each endpoint,

∣I′∖(A∪(A+g))∣≤2E2/w.\lvert I'\setminus(A\cup(A+g))\rvert\le2E^2/w.

Indeed, an uncovered point must lie outside AA, and its shift-preimage must also lie outside AA. Since the shift-preimage belongs to II, Fubini and the density bound give the product of the two missing measures. Hence at least half the shifts leave missing measure at most 4E2/w4E^2/w.

For widths wj=L/2j+4w_j=L/2^{j+4}, the normalized errors obey

zj+1≤2j+6zj2,z0≤2−10,zj≤2−(3⋅2j+j+7).z_{j+1}\le2^{j+6}z_j^2,\qquad z_0\le2^{-10},\qquad z_j\le2^{-(3\cdot2^j+j+7)}.

The last inequality follows by induction. Reciprocal-prime estimates couple the continuous comparison shifts to the actual prime-pair law with a bounded displacement error, which is absorbed by thickening the support intervals. Duplicate-prime samples are removed before interpreting pairs arithmetically. The selected windows and the number of stages make the combined extra cost exp⁡(−o(k))\exp(-o(k)).

The output is extremely small missing measure. If the complement of ⋃d∣n0[log⁡d,log⁡d+h]\bigcup_{d\mid n_0}[\log d,\log d+h] has measure less than ω\omega in the range being used, every contained interval [x−ω,x][x-\omega,x] meets that union. An actual divisor then satisfies x−(h+ω)≤log⁡d≤xx-(h+\omega)\le\log d\le x. This gives the logarithmic mesh needed by the arithmetic argument.

Small Fourier phases and a fresh prime window

For a nonempty system of distinct positive integer weights w1,…,wNw_1,\ldots,w_N, write W=∑iwiW=\sum_i w_i and

Fw={θ∈R/Z:∑i∥wiθ∥2≤Y−2}.F_w=\left\{\theta\in\mathbb{R}/\mathbb{Z}:\sum_i\lVert w_i\theta\rVert^2\le Y^{-2}\right\}.

where ∥x∥\lVert x\rVert is the distance to the nearest integer. Properness controls the size of this small-phase set. Let CC be an HH-proper signed cube and M=(2H+1)NM=(2H+1)^N its cardinality. The polynomial

Φ(θ)=1M∑x∈Ce2πixθ\Phi(\theta)=\frac{1}{M}\sum_{x\in C}e^{2\pi i x\theta}

satisfies ∫R/Z∣Φ∣2=1/M\int_{\mathbb{R}/\mathbb{Z}}|\Phi|^2=1/M by orthogonality of distinct integer characters. For uniform signed coefficients, cancellation of cross terms and cos⁡u≥1−u2/2\cos u\ge1-u^2/2 give

Re⁡Φ(θ)≥1−2π2H2∑i∥wiθ∥2.\operatorname{Re}\Phi(\theta)\ge1-2\pi^2H^2\sum_i\lVert w_i\theta\rVert^2.

Assume Y>0Y>0, Y≥32HY\ge32H, and YW≥2YW\ge2. Points within 1/(YW)1/(YW) of FwF_w have ∣Φ∣≥3/4|\Phi|\ge3/4. Their Haar measure is at most 16/(9M)16/(9M). A finite grid-packing argument consequently gives, for every positive integer qq,

#{0≤a<q:dist⁡(a/q,FW)≤1/q}≤6(q+YW)M.(19)\#\{0 \le a < q : \operatorname{dist}(a/q,F_W) \le1/q\} \le\frac{6(q+YW)}{M}. \tag*{(19)}

These estimates connect the arithmetic properness of the core to control of rational phases.

The construction next observes the previous prime configuration and chooses a fresh high-prime window. Bounds such as (19), applied to several core prefixes, control rational approximants at all required denominator scales. Selected high primes multiply an old phase by several fresh residues. The only phases surviving all these tests lie near zero. The conditional identity in § 3 justifies applying the uniform estimate to this adaptively chosen window. Lemma 4.7 of the manuscript and the source’s high-prime declarations provide the detailed probability and scale estimates. This stage also costs exp⁡(−o(k))\exp(-o(k)).

Combining localization with the logarithmic mesh makes the following arithmetic statement hold for a range of reserve divisors r∣n0r \mid n_0. With Dr={d:d∣n0, d<r}D_r = \{d : d \mid n_0,\ d < r\},

∑d∈Dr∥ad/r∥2>Y−2(1≤a<r).(20)\sum_{d\in D_r} \lVert ad/r\rVert^2 > Y^{-2} \qquad(1 \le a < r). \tag*{(20)}

The mesh propagates a putatively small phase from smaller to larger divisors. At the endpoint rr, the quantity ar/r=aar/r = a is an integer, so a nonzero residue cannot survive this propagation.

Fourier inversion gives bounded coefficients

Take a fair Boolean sum of the coins d∈Drd \in D_r modulo rr. At frequency aa its normalized Fourier transform has absolute value

∏d∈Dr∣cos⁡(πad/r)∣≤exp⁡(−2∑d∈Dr∥ad/r∥2).\prod_{d\in D_r} \lvert\cos(\pi ad/r)\rvert\le\exp\left(-2\sum_{d\in D_r}\lVert ad/r\rVert^2\right).

Here ∣cos⁡(πx)∣≤e−2∥x∥2\lvert\cos(\pi x)\rvert\le e^{-2\lVert x\rVert^2} follows from ∣sin⁡(πx)∣≥2∥x∥\lvert\sin(\pi x)\rvert\ge2\lVert x\rVert and 1−u≤e−u1-u \le e^{-u}. Under (20), every nontrivial coefficient is at most e−2/Y2e^{-2/Y^2} in absolute value.

Take ℓr=⌈Y2log⁡(2r)⌉\ell_r = \lceil Y^2\log(2r)\rceil independent copies. The sum of the absolute values of their nontrivial Fourier coefficients is at most (r−1)e−2ℓr/Y2≤(r−1)/(2r)2<1(r-1)e^{-2\ell_r/Y^2} \le(r-1)/(2r)^2 < 1. Fourier inversion therefore assigns positive probability to every residue modulo rr. Each residue has a representative ∑d∈Drcdd\sum_{d\in D_r} c_d d with 0≤cd≤ℓr0 \le c_d \le\ell_r.

Choose an integer ZZ with ℓr≤Z\ell_r \le Z and 4ℓr∑d∈Drd≤Zr4\ell_r\sum_{d\in D_r}d \le Zr. If Zr/4≤t≤3Zr/4Zr/4 \le t \le3Zr/4, the representative of tt is at most Zr/4≤tZr/4 \le t. Adding a nonnegative multiple of the reserve divisor rr gives

t=br+∑d∈Drcdd,0≤b≤Z,0≤cd≤Z.(21)t = br+\sum_{d\in D_r}c_dd,\qquad0 \le b \le Z,\quad0 \le c_d \le Z. \tag*{(21)}

A practical factor makes the summands distinct

A positive integer b0b_0 is practical if every integer between zero and b0b_0 is a sum of distinct divisors of b0b_0. The source supplies such a divisor from small prime coordinates, independently of the rough-prime construction. It has b0≥Zb_0 \ge Z and gcd⁡(b0,n0)=1\gcd(b_0,n_0)=1, and its probability cost is exp⁡(−o(k))\exp(-o(k)).

Lemma 6.2 (Distinct-divisor lifting). Suppose b0b_0 is practical, gcd⁡(b0,n0)=1\gcd(b_0,n_0)=1, and 0≤cd≤b00 \le c_d \le b_0 for every d∣n0d \mid n_0. Then ∑d∣n0cdd\sum_{d\mid n_0} c_d d is a sum of distinct divisors of b0n0b_0n_0.

Proof. For each dd, choose a subset EdE_d of the divisors of b0b_0 with cd=∑e∈Edec_d=\sum_{e\in E_d}e. The desired sum is ∑d∣n0∑e∈Edde\sum_{d\mid n_0}\sum_{e\in E_d}de. Every product dede divides b0n0b_0n_0. Coprimality makes its decomposition into a divisor of n0n_0 and a divisor of b0b_0 unique. Equality de=d′e′de=d'e' forces d=d′d=d' and e=e′e=e'. Thus no product is repeated. ∎

One elementary way to grow the seed starts from 210 = 2⋅3⋅5⋅72 \cdot3 \cdot5 \cdot7. If bb is practical and a fresh prime p≤b+1p \le b + 1 is adjoined, then bpbp is practical. For 0≤m≤bp0 \le m \le bp, write m=qp+rm = qp + r with q≤bq \le b and r<p≤b+1r < p \le b + 1. Represent qq and rr by divisors of bb. The two groups, one multiplied by pp, are disjoint. Selected prime windows grow this seed past ZZ using only O(log⁡log⁡Z)O(\log\log Z) stages. The manuscript and Lean source supply the quantitative success estimates. Lemma 6.2 converts (21) into the required representations by distinct divisors.

Harmonic averaging preserves the rate

For a nonempty finite target set H\mathcal{H} and positive weights wtw_t, let

F(T)=∑t∈Hwt1{nT∈At}∑t∈Hwt,d‾=∑t∈Hwtdt∑t∈Hwt.F(T) = \frac{\sum_{t\in\mathcal{H}} w_t\mathbf{1}_{\{n_T\in A_t\}}}{\sum_{t\in\mathcal{H}} w_t}, \qquad\overline{d} = \frac{\sum_{t\in\mathcal{H}} w_t d_t}{\sum_{t\in\mathcal{H}} w_t}.

Thus 0≤F≤10 \le F \le1, and Proposition 3.1 gives EP,1F≤d‾\mathbb{E}_{P,1}F \le\overline{d}. For q>1q > 1, Hölder’s inequality, Fq/(q−1)≤FF^{q/(q-1)} \le F, and (8) yield the single change-of-measure bound

EP,λF=EP,1(LλF)≤d‾1−1/q(ZP(λq)ZP(λ)q)1/q.(22)\mathbb{E}_{P,\lambda}F = \mathbb{E}_{P,1}(L_\lambda F) \le\overline{d}^{1-1/q}\left(\frac{Z_P(\lambda^q)}{Z_P(\lambda)^q}\right)^{1/q}. \tag*{(22)}

All stages of the construction belong to this one observable.

In the actual construction wt=1/tw_t = 1/t and the target sets escape to infinity. Logarithmically separated reserve divisors produce disjoint target intervals. Every interval [N/4,3N/4][N/4,3N/4] with integer N≥4N \ge4 has reciprocal weight at least 1/41/4. Comparing the total weight supplied by these intervals to the harmonic weight of the whole target horizon gives F(T)≥exp⁡(−o(k))F(T) \ge\exp(-o(k)) on successful configurations. Together with the core probability and the later subexponential costs, this proves

EPk,λFk≥exp⁡(−(J(λ)+o(1))k).(23)\mathbb{E}_{P_k,\lambda}F_k \ge\exp\left(-(J(\lambda)+o(1))k\right). \tag*{(23)}

The finite universe is chosen so that its prime cutoff has logarithmic-logarithmic size klog⁡2+o(k)k\log2 + o(k). Mertens’s estimate and (8) then give, for fixed λ,q\lambda,q,

log⁡EPk,1Lλq=(λq−1−q(λ−1)+o(1))klog⁡2.(24)\log\mathbb{E}_{P_k,1}L_\lambda^q = \left(\lambda^q - 1 - q(\lambda- 1) + o(1)\right)k\log2. \tag*{(24)}

To see the coefficient, expand log⁡(1+(u−1)/p)=(u−1)/p+O(u(p−2))\log(1+(u-1)/p)=(u-1)/p+O(u(p^{-2})) for fixed u>0u>0. The reciprocal-square errors have bounded sum. The first-order terms in log⁡ZPk(λq)−qlog⁡ZPk(λ)\log Z_{P_k}(\lambda^q)-q\log Z_{P_k}(\lambda) give the displayed coefficient.

Rearrange (22), substitute (23)–(24), and take logarithms:

−log⁡d‾k≤qJ(λ)+(λq−1−q(λ−1))log⁡2q−1k+o(k).-\log\overline{d}_k \le\frac{qJ(\lambda)+\left(\lambda^q-1-q(\lambda-1)\right)\log2}{q-1}k+o(k).

A positive weighted average has an entry at least as large as itself, so some tkt_k in the horizon satisfies dtk≥d‾kd_{t_k}\ge\overline{d}_k. The horizon has log⁡log⁡tk≥klog⁡2\log\log t_k \ge k\log2 and its lower endpoint tends to infinity. This gives arbitrarily large targets with the rate bound used below.

The rate optimization in the source

The formal development uses a tilt λ\lambda and a Hölder parameter q>1q>1. Define

λ∗=1log⁡2,J(λ)=λlog⁡2−1−log⁡(λlog⁡2),R(λ,q)=qJ(λ)/log⁡2+λq−1−q(λ−1)q−1.\lambda_*=\frac{1}{\log2}, \qquad J(\lambda)=\lambda\log2-1-\log(\lambda\log2), \qquad R(\lambda,q)=\frac{qJ(\lambda)/\log2+\lambda^q-1-q(\lambda-1)}{q-1}.

Its completed arithmetic construction and transfer estimates give, for each fixed λ∗<λ<2\lambda_*<\lambda<2, q>1q>1, and ε>0\varepsilon>0, arbitrarily large targets satisfying

−log⁡dtlog⁡log⁡t≤R(λ,q)+ε.\frac{-\log d_t}{\log\log t}\le R(\lambda,q)+\varepsilon.

To see the critical value of this rate, note that J(λ∗)=0J(\lambda_*)=0. Differentiation in qq at q=1q=1 gives

lim⁡q↓1R(λ∗,q)=λ∗log⁡λ∗−λ∗+1=1−1+log⁡log⁡2log⁡2=δ.\lim_{q\downarrow1}R(\lambda_*,q)=\lambda_*\log\lambda_*-\lambda_*+1=1-\frac{1+\log\log2}{\log2}=\delta.

For fixed q>1q > 1, continuity in λ\lambda permits a choice strictly above λ∗\lambda_{*} with rate as close to this value as desired. First choose qq near one, then choose such a λ\lambda, and finally let the finite construction scale grow. This order keeps the parameters fixed during the construction’s limiting estimates. It supplies (18) and therefore the required lower limit.

The detailed block estimates, support comparisons, and multiscale phase bounds occupy a substantial part of the 36,197-line accepted submission. Sections 3–4 of the supplied manuscript give a longer prose treatment [3]. The present account proves the elementary reductions and develops the main construction and transfer mechanisms, while identifying the technical estimates used at each stage.

Formal source, scope, and attribution

The complete proof is available as the accepted Lean source. It proves the negation of the native declaration Erdos859.erdos_859. The statement quantifies over a density function as well as over the positive constants. The submission constructs the density independently and uses uniqueness of limits to identify any claimed density function with it. The refutation therefore concerns the asymptotic itself.

Guide to the submitted file

The following line numbers refer to the immutable submitted Main.lean. Within the namespace Erdos859Verification, the principal declarations are:

LinesDeclaration or interface
24–44divisorSumSet_iff_of_modEq_factorial: periodicity.
205–213divisorDensity, divisorSumSet_hasDensity: the canonical density.
433–478bounded_coefficients_mem_divisorSumSet: practical-factor lifting.
1590–1636Exact normalizer and tilted prime law.
1719–1735primeTiltLikelihood_moment: exact likelihood moment.
388–408divisorDensity_le_intervalDensity_add: the small-divisor split.
694–709not_equivalent_of_liminf_and_scaled_limit: analytic contradiction.
822–833counterexample_of_estimates: transfer to the native target.
3364–3418Finite dyadic bound and endpoint corrections.
29056–29111Uniform divisor-interval envelope transferred to density decay.
29179–29190divisorDensity_critical_scaled_tendsto_zero.
30083–30181Target-average observable and single Hölder transfer.
35342–35355corePastHigh_event_probability_lower: combined good event.
35890–35912coreArithmeticCoverage_exponential_eventually.
29936–30016Frequent lower estimates and weighted extraction.
34970–34980divisorDensity_liminf_eq_of_global_harmonic_lower.
35944–35968Completed lower expectation and divisorDensity_log_rate_liminf.
35981–35984Final target, supplied with both proved estimates.

Table 1.

The submission was accepted on 18 September 2026 and completed production verification that day. Approval was recorded on 21 September. The public verification report [4] records successful Lean kernel, permitted-axiom, and statement-comparison checks. Its environment used Lean 4.33.1. This exposition does not report a new independent kernel replay.

The supplied manuscript also describes a separate companion build. The verification record and line references here refer specifically to the accepted production submission, whose SHA-256 digest is

c8011826d105daecca4de0f0a58cc4acd887eafd1a78a9e8c9095c399ca97aea.

Supporting prime estimates include an explicitly credited adaptation from the PNT+ project, with the cited upstream revision and Apache-2.0 license recorded in the submitted file [6]. The divisor-interval analysis uses established mathematics associated with Ford’s work. The public submitter credit is JenW1N. This TeX edition follows the expanded Conjectures.io exposition, which accompanies Justin Sun Prize submission JSP-000712.

References

  1. [1]P. Erdős, Some extremal problems in combinatorial number theory (1970), pp. 123–133. The question is on p. 130, equation (33).
  2. [2]Erdős Problems, Problem 859, https://www.erdosproblems.com/859.
  3. [3]L. Kruer and J. Kohlmeier, Divisor sums and a counterexample to Erdős problem 859, author-supplied working manuscript, 18 September 2026, 27 pp., especially Sections 2–5.
  4. [4]JenWIN, Erdős 859 counterexample submission, Conjectures, accepted 18 September 2026. Public result and review and archived accepted proof body.
  5. [5]K. Ford, Integers with a divisor in (y, 2y), version dated 13 March 2013.
  6. [6]PNT+ contributors, PrimeNumberTheoremAnd, Mertens development. The version used is a5154676af9aa3095150ee410cdda80555aa0642.

Paper details

vlnc:W_up4d6mhw
Version
v1 · latest
Published
Fresh — published within the last 30 days
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

Not recorded for this paper

View statement
Looking for related papers…
Contents