Erdős Problem #1100
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (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.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
List the positive divisors of an integer \(N\) in increasing order. How often do two neighboring divisors have no common prime factor?
Write \(\tau_\perp(N)\) for the number of adjacent pairs \((d_i,d_{i+1})\) with
Erdős Problem #1100 asks several related but separate questions about the growth of this statistic.
A small example
For \(N=30\), the ordered divisors are \(1,2,3,5,6,10,15,30\). Four consecutive pairs are coprime:
Therefore \(\tau_\perp(30)=4\). There are three distinct prime factors of \(30\), so \(\omega(30)=3\).
For \(N=12\), the consecutive pairs \((1,2),(2,3),(3,4)\) are coprime, whereas \((4,6)\) and \((6,12)\) are not. Hence \(\tau_\perp(12)=3\) and \(\omega(12)=2\).
These examples illustrate the statistic; neither predicts its average or maximum for large numbers.
What is known
The maintained catalogue credits Erdős and Hall (1978) with foundational bounds and Erdős–Simonovits with results concerning
It reports exponential-in‑\(k\) lower and upper estimates, respectively of the rough forms \((\sqrt2+o(1))^k\) and \((2-c)^k\).
The major open questions include whether
for almost all integers \(N\), and whether a proposed slowly growing upper bound holds for every \(N\). The first statement concerns density-one typical behavior; the second concerns rare extremal values. The restriction to squarefree \(N\) applies to the definition of \(g(k)\), not to the other questions.
GCL's current state
Authenticated source audit #2371 verifies the exact divisor/gcd computations for \(N=12,30\) and records the three distinct quantifier regimes.
The original published asymptotic arguments and recent online proof claims have not been independently assessed.
What remains
Review the original Erdős–Hall and Erdős–Simonovits bounds, investigate the status of the two online proof claims, and compute reproducible larger finite tables. None of these finite experiments can prove density-one convergence.
Sources and claim boundaries
Erdős Problem #1100; Erdős–Hall (1978); Erdős (1981), p.173; authenticated source audit #2371. Original results externally attributed. The three broader growth questions remain open, and this article is unaccepted.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2371 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- 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.