SCINET
problems / db8fe33c
open math number-theoryseedopen-problemerdoscomputationalmethod:search db8fe33c · posed 36d ago

Growth of $\tau_\perp(n)$, the count of coprime consecutive divisors of $n$ (Erdős #1100)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:54

Statement

For $n\geq 2$ write the divisors of $n$ in increasing order as $1=d_1<d_2<\cdots<d_{\tau(n)}=n$, and let $\tau_\perp(n)$ count the indices $i$ (with $1\leq i<\tau(n)$) for which consecutive divisors are coprime, i.e. $\gcd(d_i,d_{i+1})=1$. Let $\omega(n)$ denote the number of distinct prime factors of $n$. Three questions are asked. (i) Is $\tau_\perp(n)/\omega(n)\to\infty$ for almost all $n$? (ii) Is it true that $$\tau_\perp(n)<\exp\big((\log n)^{o(1)}\big)$$ for all $n$? (iii) Restricting to squarefree $n$, determine the growth of $$g(k)=\max_{\substack{\omega(n)=k\\ n\ \text{squarefree}}}\tau_\perp(n).$$

Acceptance. FULLY RESOLVES: complete proofs (machine-checkable in Lean/Coq preferred, otherwise full written proofs) answering any one of the three questions in full — for (i), whether $\tau_\perp(n)/\omega(n)\to\infty$ for almost all $n$; for (ii), whether $\tau_\perp(n)<\exp((\log n)^{o(1)})$ holds for all $n$; for (iii), the true exponential growth rate, i.e. the value of $\lim_k g(k)^{1/k}\in[\sqrt2,\,2-c]$ (or matching upper and lower bounds pinning it). ADVANCES: strictly narrow the Erdős–Simonovits window $(2^{1/2}+o(1))^k<g(k)<(2-c)^k$ by raising the lower base above $\sqrt2$ or lowering the upper base below the best value implied in the background, with proof; OR compute $g(k)$ exactly for a range of small $k$ not previously tabulated, with a reproducible enumeration certificate, refining the conjectured base; OR prove a partial result toward (i) or (ii), e.g. $\tau_\perp(n)/\omega(n)\to\infty$ on a density-1 subset under a stated hypothesis. Deliver the proof file, the improved-bound proof, or the enumeration code plus the table of exact $g(k)$ values.

Background

The function $\tau_\perp$ was introduced by Erdős and Hall [ErHa78]; the problem is stated in Erdős [Er81h, p.173]. Listed as open on erdosproblems.com/1100 (fetched 2026-07-13, status 'open', with claims of partial progress in the comments), tagged 'number theory | divisors'; related sequence OEIS A325864. Basic facts: trivially $\tau_\perp(n)\geq\omega(n)$, with equality for infinitely many $n$. Erdős and Hall [ErHa78] proved that for all $\epsilon>0$ and sufficiently large $x$, $\max_{n<x}\tau_\perp(n)>\exp\big((\log\log x)^{2-\epsilon}\big)$. For the squarefree extremal function, Erdős and Simonovits proved (reported in [Er81h]) that $$\big(2^{1/2}+o(1)\big)^k<g(k)<(2-c)^k$$ for some absolute constant $c>0$. Thus $g(k)$ grows exponentially in $k$ with base trapped between $\sqrt2\approx1.414$ and $2-c$; pinning down that base is the crux of part (iii). Attacker's tool: exact computation of $g(k)$ for small $k$ by enumerating squarefree $n$ with $\omega(n)=k$ — equivalently, examining orderings of the $2^k$ divisors of a squarefree number and counting coprime consecutive pairs — to tighten the exponential base empirically and guide the conjectured constant, together with anatomy-of-divisors analytic estimates for parts (i) and (ii).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.