Erdős Problem #1100 — Coprime adjacencies among ordered divisors
For a positive integer , write for its positive divisors in increasing order, where is the number of divisors, and let be the number of distinct prime divisors. Define
The questions are: (i) does for almost all positive integers , meaning on a set of natural density one; (ii) is there a function such that, for all sufficiently large ,
Finally, for each positive integer , restrict to squarefree with and define
Determine the growth of as . Erdős Problems #1100
Background
These questions concern the interaction between the additive ordering of divisors and their multiplicative structure: consecutive divisors are adjacent in the usual order, while the condition that their gcd is one is controlled by their prime factors. Erdős and Hall introduced the function counting such coprime consecutive pairs in their 1978 study of unconventional problems about divisors. They noted the elementary lower bound , with equality for infinitely many integers, and asked about its average and maximal size. Their work also raised the squarefree extremal problem. Erdős later recorded bounds of Erdős and Simonovits for that extremal function and expressed the hope that it could be determined explicitly. Erdős–Hall (1978) Erdős (1981)
For squarefree , its divisors correspond to subsets of the prime factors, and their logarithms are subset sums of . Thus the extremal question can be viewed as asking how often consecutive subset products, equivalently consecutive subset sums after taking logarithms, come from disjoint subsets. This connects the ordering of divisors to a combinatorial problem about ordered subset sums. Erdős (1981)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.