Skip to content

Erdős Problem #446

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: number theory, divisors.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Fix a positive integer \(n\). What fraction of all positive integers are divisible by at least one integer lying strictly between \(n\) and \(2n\)? Erdős Problem 446 calls this natural density \(\delta(n)\) and asks how fast it decreases when \(n\) grows. It also asks about the density \(\delta_1(n)\) of integers having exactly one divisor in that interval, conjecturing that \(\delta_1(n)\) might be negligible compared with \(\delta(n)\).

The strict interval \((n,2n)\) matters: a divisor equal to \(n\) or \(2n\) does not count. For each fixed \(n\), the divisibility condition involves only finitely many possible divisors, so the natural densities exist and may be calculated using inclusion–exclusion. The difficult question concerns the asymptotic behavior of these densities as the interval of allowed divisors moves to larger values.

The two questions have different answers. The exact order of magnitude of \(\delta(n)\) is known, and the assertion \(\delta_1(n)=o(\delta(n))\) is false. Indeed, integers with exactly one eligible divisor account for a positive proportion of those with at least one, uniformly in the asymptotic sense proved by Ford.

A small example

Take \(n=3\). The only integers strictly between \(3\) and \(6\) are \(4\) and \(5\). Therefore an integer is counted by \(\delta(3)\) exactly when it is divisible by \(4\) or by \(5\). Inclusion–exclusion gives

\[ \delta(3)=\frac14+\frac15-\frac1{20}=\frac25. \]

To have exactly one eligible divisor, an integer must be divisible by exactly one of \(4\) and \(5\). The density is therefore

\[ \delta_1(3)=\left(\frac14-\frac1{20}\right)+\left(\frac15-\frac1{20}\right)=\frac7{20}. \]

The conditional proportion is \(\delta_1(3)/\delta(3)=7/8\). This is an exact finite-modulus calculation, not a proof that the corresponding proportion remains large for arbitrary growing \(n\).

The computation generalizes to any fixed \(n\): all divisibility indicators are periodic modulo the least common multiple of the integers in \((n,2n)\), so a finite residue-class enumeration can compute each \(\delta_r(n)\) exactly. That period quickly becomes enormous, making direct enumeration impractical for large \(n\), and motivating the analytic estimates.

What is known

Besicovitch (1934) showed that the lower limit of \(\delta(n)\) is zero; Erdős (1935) proved the stronger conclusion \(\delta(n)\to0\). Erdős (1960) established a logarithmic decay exponent:

\[ \delta(n)=(\log n)^{-\alpha+o(1)}, \qquad \alpha=1-\frac{1+\log\log2}{\log2}=0.08607\ldots. \]

Tenenbaum (1984) refined the estimates, and Kevin Ford (2008) obtained the correct order of magnitude,

\[ \delta(n)\asymp \frac{1}{(\log n)^\alpha(\log\log n)^{3/2}}. \]

This is an order-of-magnitude equivalence with implicit positive constants, not a claim that the quotient converges to one.

Ford also disproved the second conjecture. More generally, if \(\delta_r(n)\) counts integers with exactly \(r\) divisors in \((n,2n)\), then for each fixed positive \(r\) he proved \(\delta_r(n)\gg_r\delta(n)\). Taking \(r=1\) shows that \(\delta_1(n)/\delta(n)\) cannot tend to zero. The maintained Erdős Problems #446 page records both conclusions and distinguishes the earlier Erdős and Tenenbaum stages.

GCL's current state

The original source issue #1716 pins catalogue problem #446 to teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The protected assignment records a solved classification, consistent with Ford's mathematical theorem. It identifies no #446 statement file in the admitted FormalConjectures provider revision 85f863718beeec7b58a3a1926ee92e3472bc2020, so no GCL Lean replay can be claimed from that source snapshot.

The authenticated original issue audit is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1716#issuecomment-6158643495. This article separately records the logarithmic growth-rate theorem and the disproof of the single-divisor conjecture. That distinction is necessary for honest source fidelity. A published mathematical result is not the same thing as GCL mathematical certification or admission to the protected V2 editorial ledger.

What remains

An exact bounded computation should take \(n=2,\ldots,8\), enumerate the eligible divisors in \((n,2n)\), and compute \(\delta_r(n)\) through inclusion–exclusion or a residue table modulo their least common multiple. Compare the counts with an independent direct divisibility scan over one complete period. The fixture must reproduce \(\delta(3)=2/5\) and \(\delta_1(3)=7/20\), with the correct exclusion of endpoints.

The documentary task is to inspect Ford's 2008 result, stating the exact range of \(n\), the implicit constants in the \(\asymp\) notation and the dependence of the lower bound for \(\delta_r(n)\) on the fixed integer \(r\). Verify which earlier estimate belongs to Erdős or Tenenbaum. Acceptance is exact finite consistency and a primary-source theorem table; falsification includes counting repeated eligible divisors incorrectly, using a closed instead of open interval, or treating an order-of-magnitude theorem as an exact limiting ratio. Stop at the source and finite-density checks.

Sources and claim boundaries

Historical Erdős writings, Besicovitch (1934), Tenenbaum (1984), and Ford (2008), summarized at Erdős Problem #446. Original printed problem: Erdős–Graham (1980), p.89. Related questions #448, #692, and #693. Frozen GCL issue #1716, teorth catalogue, and original authenticated source return.

The \(n=3\) density calculations are exact. Ford's asymptotic and fixed \(r\) theorems are attributed external research, not independently reproved by GCL. No new theorem, certified Lean build, protected merge or V2 admission is asserted.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1716 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction