WorksMathematics
Erdős problem 859: a refutation of the logarithmic density law
Abstract
Let be the natural density of integers for which is a sum of distinct positive divisors of . We prove and , where . 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 are taken through positive integers.
Put
The subset is finite and contains no repeated divisor. If it exists, the natural density is
In his 1970 paper, printed page 130, Erdős introduces this set, notes the existence of its density, and proposes the asymptotic
as equation (33) [1]. This is Erdős Problem 859 [2]. The symbol 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 exists and is positive for every . There are no positive constants satisfying (1).
The proof supplies two complementary estimates. Set
Then the submitted development proves
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 is asserted here.
Density exists for an elementary reason
Lemma 2.1 (Periodicity). For fixed , membership in among positive integers depends only on the residue class modulo .
Proof. Every divisor appearing in a sum equal to is at most . Each positive integer divides . Consequently, if , then if and only if for every such . The same finite subsets of these divisors can be used for and , and their sums agree.
Let and choose the positive representatives . Writing with gives
For fixed , divide by and let tend to infinity. This proves
Thus the density is an exact finite residue-class average. Moreover, every positive multiple of belongs to , by using the single divisor . Hence for . In particular the logarithm of is defined. The Lean proof uses a periodic real-valued indicator and its average. The choice of counting rather than 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 be a finite set of primes. For , define
The Chinese remainder theorem shows that is exactly the natural density of integers whose prime divisors in are precisely . The coordinates are independent, with inclusion probability .
Proposition 3.1 (Finite witnesses and actual density). For each ,
Proof. A representation using divisors of remains valid for every multiple of . On the prime-divisibility pattern , the integer divides the sampled integer. Each successful pattern is therefore contained in . The patterns are disjoint and have the densities (6), proving the claim by finite addition.
Exponential tilting
For , set
Expanding a finite product proves , so this is a probability law. Its independent inclusion probabilities are . Under the original law, its likelihood ratio is . For every real ,
This follows by substituting the likelihood and applying the same finite product identity. The denominator is positive.
The critical tilt is . A logarithmic prime band has reciprocal-prime mass approaching , and its tilted expected prime count approaches . Thus 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 is the observed universe and is chosen from the observation , then for any function ,
For each fixed , the remaining coordinates retain their product law. Coordinates outside 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 eventually, and suppose , where and . Then
Proof. There is a positive sequence with for all sufficiently large . Taking logarithms yields
Since and , the last fraction tends to zero. The second claim follows from . □
Proof of Theorem 1.1, using the two estimates. Density existence and positivity were established above. Suppose (1) holds. Applying Lemma 4.1 with shows that the logarithmic rate has limit . Its lower limit is therefore . Equation (3) forces . The second part of the lemma gives . By (4) the same sequence tends to zero, so uniqueness of the limit gives , contradicting . □
This argument excludes every real exponent with a positive constant coefficient. Only positive exponents are needed for the original question. Values at , where , play no role in an eventual asymptotic statement.
The upper estimate: reducing sums to divisor intervals
For integers , write
These densities also exist by periodicity. Define the sum of the small divisors by .
Proposition 5.1 (Exact density bound). For and integers ,
Proof. If but , all the divisors in a representation of are at most . Thus . For every positive integer this gives
For each fixed positive , multiples of have density . Therefore the finite sum defining has limiting mean
Average the pointwise inequality and divide by to obtain (9). □
A finite dyadic reduction
For a positive integer , put for . The interval above is covered by these dyadic pieces. Integer rounding adds at most the single divisor at each step, whose multiples have density . The union bound and Proposition 5.1 yield
In particular, a uniform bound gives
The submitted proof supplies a nonnegative envelope , valid uniformly for , such that
Its divisor-interval analysis develops Ford-type bounds, including control of nonsquarefree contributions by powerful-number sums. Ford’s classical divisor-distribution work concerns [5]. The reduction above is what connects this counting problem to sums of distinct divisors.
For the limiting argument take . Then , , and eventually . After multiplying (11) by , its three terms tend to zero. The first does so by (12), the second because dominates logarithmic powers, and the third because . 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 and thickness , put
where denotes Lebesgue measure. This is a union of intervals around logarithms of actual divisors of the squarefree product . For every ,
Indeed, fix the selected subset outside . The remaining intervals are contained in one translate of . There are at most translations. Separating subsets according to the presence of one additional prime gives the second inequality.
Set , , and . The source proves constants and a threshold, uniform in finite prime sets and , such that
Three ingredients explain the saving. First, the disjoint intervals of lengths in cumulative prime-weight coordinates convert a sum over distinct primes to an integral over disjoint cells. Permutation symmetry supplies the factor for a -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 and the square-root factor in Stirling’s bound, the calculation leaves a factor , where is comparable to . 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 be the probability that the product of primes selected with probabilities , among primes at most , has a divisor in . 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 with
Combining this with (14), and absorbing rounding in the prime cutoff, gives absolute constants such that
for all sufficiently large . This is a probability for the finite prime law, whereas also includes integers with prime powers.
Restoring prime powers
Call powerful if every prime dividing occurs to exponent at least two, including . The useful summability bounds are
To see their scale, write a powerful integer uniquely as with squarefree. Then converges by comparison with . The elementary divisor bound proves the first claim. For the second use when .
Cap each prime valuation at a finite integer . The one-prime weights are
The final atom includes all valuations at least . 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 leaves primes of exponent zero or one. Their conditional inclusion probability is , at most . The total mass of the fixed powerful part is at most .
Every divisor has the form , with and a subset of the remaining primes whose product is . Monotonicity of the divisor-interval event and a union bound therefore give
The formal argument first obtains this domination in a finite capped model. The convergent majorants in (16) then bound it uniformly. If , then , so (15) is uniform over all these shifts. It follows that suitable positive constants satisfy
for every sufficiently large integer . The last exponent is . Each term in is eventually decreasing, and
Thus is an envelope in (12). The exponent is useful because the final dyadic union costs one factor of , 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 there are arbitrarily large integers with
Proof. Since the positive sequence tends to zero, it is eventually at most one. Thus once . This proves the lower bound on the lower limit. For each , (18) gives arbitrarily large for which the same quotient is at most . Its lower limit is consequently at most for every , proving equality. □
Proper divisor cubes and logarithmic coverage
Fix a tilt and write
The lower construction has a scale . A block event in disjoint logarithmic prime bands produces a core of selected primes at probability at least 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 , a divisor cube of is called -proper when
is injective on .
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 between old cube differences. Properness of the old cube forces . Then , 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 , supplies a logarithmic displacement . After adding the common baseline , 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 to at most . The second stage uses narrower windows. Suppose covers all but measure of an interval , and a random shift is supported on with density at most . On the interval obtained by trimming from each endpoint,
Indeed, an uncovered point must lie outside , and its shift-preimage must also lie outside . Since the shift-preimage belongs to , Fubini and the density bound give the product of the two missing measures. Hence at least half the shifts leave missing measure at most .
For widths , the normalized errors obey
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 .
The output is extremely small missing measure. If the complement of has measure less than in the range being used, every contained interval meets that union. An actual divisor then satisfies . 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 , write and
where is the distance to the nearest integer. Properness controls the size of this small-phase set. Let be an -proper signed cube and its cardinality. The polynomial
satisfies by orthogonality of distinct integer characters. For uniform signed coefficients, cancellation of cross terms and give
Assume , , and . Points within of have . Their Haar measure is at most . A finite grid-packing argument consequently gives, for every positive integer ,
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 .
Combining localization with the logarithmic mesh makes the following arithmetic statement hold for a range of reserve divisors . With ,
The mesh propagates a putatively small phase from smaller to larger divisors. At the endpoint , the quantity is an integer, so a nonzero residue cannot survive this propagation.
Fourier inversion gives bounded coefficients
Take a fair Boolean sum of the coins modulo . At frequency its normalized Fourier transform has absolute value
Here follows from and . Under (20), every nontrivial coefficient is at most in absolute value.
Take independent copies. The sum of the absolute values of their nontrivial Fourier coefficients is at most . Fourier inversion therefore assigns positive probability to every residue modulo . Each residue has a representative with .
Choose an integer with and . If , the representative of is at most . Adding a nonnegative multiple of the reserve divisor gives
A practical factor makes the summands distinct
A positive integer is practical if every integer between zero and is a sum of distinct divisors of . The source supplies such a divisor from small prime coordinates, independently of the rough-prime construction. It has and , and its probability cost is .
Lemma 6.2 (Distinct-divisor lifting). Suppose is practical, , and for every . Then is a sum of distinct divisors of .
Proof. For each , choose a subset of the divisors of with . The desired sum is . Every product divides . Coprimality makes its decomposition into a divisor of and a divisor of unique. Equality forces and . Thus no product is repeated. ∎
One elementary way to grow the seed starts from 210 = . If is practical and a fresh prime is adjoined, then is practical. For , write with and . Represent and by divisors of . The two groups, one multiplied by , are disjoint. Selected prime windows grow this seed past using only 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 and positive weights , let
Thus , and Proposition 3.1 gives . For , Hölder’s inequality, , and (8) yield the single change-of-measure bound
All stages of the construction belong to this one observable.
In the actual construction and the target sets escape to infinity. Logarithmically separated reserve divisors produce disjoint target intervals. Every interval with integer has reciprocal weight at least . Comparing the total weight supplied by these intervals to the harmonic weight of the whole target horizon gives on successful configurations. Together with the core probability and the later subexponential costs, this proves
The finite universe is chosen so that its prime cutoff has logarithmic-logarithmic size . Mertens’s estimate and (8) then give, for fixed ,
To see the coefficient, expand for fixed . The reciprocal-square errors have bounded sum. The first-order terms in give the displayed coefficient.
Rearrange (22), substitute (23)–(24), and take logarithms:
A positive weighted average has an entry at least as large as itself, so some in the horizon satisfies . The horizon has 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 and a Hölder parameter . Define
Its completed arithmetic construction and transfer estimates give, for each fixed , , and , arbitrarily large targets satisfying
To see the critical value of this rate, note that . Differentiation in at gives
For fixed , continuity in permits a choice strictly above with rate as close to this value as desired. First choose near one, then choose such a , 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:
| Lines | Declaration or interface |
| 24–44 | divisorSumSet_iff_of_modEq_factorial: periodicity. |
| 205–213 | divisorDensity, divisorSumSet_hasDensity: the canonical density. |
| 433–478 | bounded_coefficients_mem_divisorSumSet: practical-factor lifting. |
| 1590–1636 | Exact normalizer and tilted prime law. |
| 1719–1735 | primeTiltLikelihood_moment: exact likelihood moment. |
| 388–408 | divisorDensity_le_intervalDensity_add: the small-divisor split. |
| 694–709 | not_equivalent_of_liminf_and_scaled_limit: analytic contradiction. |
| 822–833 | counterexample_of_estimates: transfer to the native target. |
| 3364–3418 | Finite dyadic bound and endpoint corrections. |
| 29056–29111 | Uniform divisor-interval envelope transferred to density decay. |
| 29179–29190 | divisorDensity_critical_scaled_tendsto_zero. |
| 30083–30181 | Target-average observable and single Hölder transfer. |
| 35342–35355 | corePastHigh_event_probability_lower: combined good event. |
| 35890–35912 | coreArithmeticCoverage_exponential_eventually. |
| 29936–30016 | Frequent lower estimates and weighted extraction. |
| 34970–34980 | divisorDensity_liminf_eq_of_global_harmonic_lower. |
| 35944–35968 | Completed lower expectation and divisorDensity_log_rate_liminf. |
| 35981–35984 | Final 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]P. Erdős, Some extremal problems in combinatorial number theory (1970), pp. 123–133. The question is on p. 130, equation (33).
- [2]Erdős Problems, Problem 859, https://www.erdosproblems.com/859.
- [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]JenWIN, Erdős 859 counterexample submission, Conjectures, accepted 18 September 2026. Public result and review and archived accepted proof body.
- [5]K. Ford, Integers with a divisor in (y, 2y), version dated 13 March 2013.
- [6]PNT+ contributors, PrimeNumberTheoremAnd, Mertens development. The version used is a5154676af9aa3095150ee410cdda80555aa0642.