← All problems

Erdős Problem #1100 — Coprime adjacencies among ordered divisors

45 years old · traced to

For a positive integer nn, write 1=d1<d2<⋯<dτ(n)=n1=d_1<d_2<\cdots<d_{\tau(n)}=n for its positive divisors in increasing order, where τ(n)\tau(n) is the number of divisors, and let ω(n)\omega(n) be the number of distinct prime divisors. Define

τ⊥(n)=#{1≤i<τ(n):gcd⁡(di,di+1)=1}.\tau_\perp(n)=\#\{1\le i<\tau(n):\gcd(d_i,d_{i+1})=1\}.

The questions are: (i) does τ⊥(n)/ω(n)→∞\tau_\perp(n)/\omega(n)\to\infty for almost all positive integers nn, meaning on a set of natural density one; (ii) is there a function ε(n)→0\varepsilon(n)\to0 such that, for all sufficiently large nn,

τ⊥(n)<exp⁡((log⁡n)ε(n))?\tau_\perp(n)<\exp\big((\log n)^{\varepsilon(n)}\big)?

Finally, for each positive integer kk, restrict to squarefree nn with ω(n)=k\omega(n)=k and define

g(k)=max⁡n squarefreeomega(n)=kτ⊥(n).g(k)=\max_{\substack{n\text{ squarefree}\\omega(n)=k}}\tau_\perp(n).

Determine the growth of g(k)g(k) as k→∞k\to\infty. 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 τ⊥(n)≥ω(n)\tau_\perp(n)\geq\omega(n), 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 n=p1⋯pkn=p_1\cdots p_k, its divisors correspond to subsets of the prime factors, and their logarithms are subset sums of log⁡p1,…,log⁡pk\log p_1,\ldots,\log p_k. 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

Progress summary

Never refreshed

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.