← All problems

Erdős Problem #697 — Density threshold for divisibility by restricted congruence divisors

1 year old · traced to

For a positive integer mm and a real number α\alpha, define

Am,α={n∈N:there is an integer d with d≡1(modm), 1<d<exp⁡(mα), d∣n}.A_{m,\alpha}=\{n\in\mathbb N: \text{there is an integer }d\text{ with }d\equiv 1\pmod m,\ 1<d<\exp(m^\alpha),\ d\mid n\}.

Let δ(m,α)\delta(m,\alpha) be the natural density of Am,αA_{m,\alpha}, namely lim⁡X→∞X−1#{n∈Am,α:n≤X}\lim_{X\to\infty}X^{-1}\#\{n\in A_{m,\alpha}:n\le X\}. This density exists: the admissible dd form a finite set, and Am,αA_{m,\alpha} is a finite union of sets of multiples, hence periodic. The threshold assertion, with the directions stated correctly, is that for each fixed α\alpha,

lim⁡m→∞δ(m,α)=0if α<1log⁡2,lim⁡m→∞δ(m,α)=1if α>1log⁡2.\lim_{m\to\infty}\delta(m,\alpha)=0\quad\text{if }\alpha<\frac1{\log 2}, \qquad \lim_{m\to\infty}\delta(m,\alpha)=1\quad\text{if }\alpha>\frac1{\log 2}.

The limits in the supplied statement are reversed; increasing α\alpha enlarges Am,αA_{m,\alpha}, consistent with the corrected direction. No assertion here concerns the boundary α=1/log⁡2\alpha=1/\log 2. Erdős Problems #697

Background

The question is recorded as Erdős Problem #697 and attributed to Erdős’s 1979 paper. The problem page reports that Erdős claimed the density tends to zero at α=1\alpha=1; Hall subsequently established the sharper threshold result. The monotonicity in α\alpha is immediate from the increasing divisor cutoff, so a zero limit below a threshold and a one limit above it are the compatible orientation. Erdős Problems #697

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.