Does the amount of positive integers $x \le n$ without middle divisors divided by $n$ converge to $\frac{3}{4}$?

Question

I recently came across an interesting conjecture that stated that the amount of positive integers $x$ on the interval $[1,n]$ such that $x$ does not have a $2$-middle divisor divided by $n$ approaches $\frac{3}{4}$ as $n$ approaches infinity. First, for clarification, $d|x$ is a $\lambda$-middle divisor if and only if $$\sqrt{\frac{x}{\lambda}} < d \le \sqrt{\lambda x}$$ More information here. The conjecture can be expressed in mathematical notation by first defining a set $A_n$ where $n\in\mathbb{Z^+}$. $$A_n := \left\{x\in\mathbb{Z^+}, x \leq n : (\nexists d|x)\left[\sqrt{\frac{x}{2}} < d \leq \sqrt{2x}\right]\right\}$$ The conjecture may now be stated as $$\lim_{n\to\infty} \frac{|A_n|}{n} = \frac{3}{4}$$ At this, I noticed that the set contains all odd primes up to $n$, so I defined a new set, $$B_n := \{x\in A_n : x \notin \mathbb{P}\}$$ and added its cardinality to the prime counting function $\pi(n)$ minus $1$ for the exclusion of the single even prime. $$\lim_{n\to\infty} \frac{|B_n| + \pi(n) - 1}{n} = \frac{3}{4}$$ I then separated everything except $|B_n|$ from the numerator and attempted to solve it independently. $$\lim_{n\to\infty} \frac{\pi(n) - 1}{n} = \lim_{n\to\infty} \frac{{\rm {li}}(n) - 1 + O\left(ne^{-\sqrt{\ln n}/15}\right)}{n} = \lim_{n\to\infty} \left(\frac{{\rm {li}}(n) - 1}{n} + O\left(e^{-\sqrt{\ln n}/15}\right)\right)$$ Since $e^{-\sqrt{\ln n}/15}$ converges to $0$, we may remove the big O notation portion of the limit. $$\lim_{n\to\infty} \frac{{\rm {li}}(n) - 1}{n} \overset{LH}{=} \lim_{n\to\infty} \frac{1}{\ln(n)} = 0 \implies \lim_{n\to\infty} \frac{|B_n|}{n} = \frac{3}{4}$$ I wasn't expecting this result. If the conjecture is true, then the non-prime elements of $A_n$ are infinite as $n$ approaches infinity. This is where I am not sure how to continue. Is this conjecture true? Is there a way to prove or disprove that the amount of elements in $B_n$ is infinite as $n$ approaches infinity without proving the conjecture?

Edit: I have now found that the product of any two primes $p_1$ and $p_2$ such that $p_2 > 2p_1$ is also in this set. If these two primes do not satisfy the inequality, then the product is guaranteed not to be in the set. This means we can define a new set, $$C_n := \{x \in B_n : (\nexists p_1, p_2 \in \mathbb{P})[x = p_1 p_2]\}$$ This allows us to simplify the limit to $$\lim_{n\to\infty} \left[\frac{|C_n|}{n} - \sum_{p \text{ prime}}^{\sqrt{n/2}} \frac{\pi\left(\frac{n}{p}\right) - \pi\left(2p\right)}{n} \right] = \frac{3}{4}$$ Let $p_k$ represent the $k$-th prime. $$\lim_{n\to\infty} \left[\frac{|C_n|}{n} - \sum_{k=1}^{\pi\left(\sqrt{n/2}\right)} \frac{\pi\left(\frac{n}{p_k}\right) - \pi\left(2p_k\right)}{n} \right] = \frac{3}{4}$$ I am unsure how to simplify this further or if it is of use to do so.

Answer 1

For every $x\in\mathbb{N}$ and every $y\in\{x,x+1,\ldots,2x\}$, draw a directed edge from $x$ to $xy$. Clearly $x$ has edges to $x+1$ distinct numbers, all between $x^2$ and $2x^2$. Having a $2$-middle-divisor is equivalent to having at least one incoming edge. (It's possible for a number to have more than one; for instance, $72$ has edges from $6$ and $8$.) If we restrict attention to numbers $\le n$, then the total in-degree of numbers in this range is equal to the total out-degree. For every $m\le \sqrt{n/2}$ the out-degree is $m+1$, and for $\sqrt{n/2} < m \le \sqrt{n}$, the outdegree is $n/m-m$; the total is $$ \sum_{m=1}^{\sqrt{n/2}}(m+1) + \sum_{m=\sqrt{n/2}}^{\sqrt{n}}(n/m - m) \sim \frac{1}{2}m^2\big\vert_{1}^{\sqrt{n/2}} + n\log m\big\vert_\sqrt{n/2}^{\sqrt{n}}-\frac{1}{2}m^2\big\vert_{\sqrt{n/2}}^{\sqrt{n}}\sim \frac{1}{4}n+n\log\sqrt{2}-\frac{1}{2}n+\frac{1}{4}n=n\log\sqrt{2}\approx 0.3466n. $$ This is also the total in-degree... so we know that the asymptotic fraction of numbers with $2$-middle divisors is at most $\log\sqrt{2}$. To improve this estimate, we need to calculate the asymptotic fraction of numbers with multiple incoming edges.

Answer 2

OK, as promised, here is an explanation why the limit is actually $1$ (though to bring the ratio above $3/4$, you need to go to about $10^7$).

Let's start with elementary general nonsense about sums of iid non-negative random variables. Assume that we have the sum $S_K=\sum_{k=1}^K X_k$ where $X_k>0$ have the same distribution as some fixed random variable $X$.

Claim 1: Let $A,\Delta>0$. Let $p=\sup\{P\{X\in [a,a+\Delta]\}\, :\, a\ge \frac AK\}$. Then $P\{S_K\in [A,A+\Delta]\}\le Kp$.

Proof: To get to $A$ and above, our random sum should have at least one term greater than or equal to $\frac AK$. Thus $$ P\{S_K\in [A,A+\Delta]\}\le \sum_{m=1}^K P\{X_m\in[\max A-S_{K,m},\frac AK,A-S_{K,m}+\Delta]\} $$ where $S_{K,m}=X_1+\dots+X_{m-1}+X_{m+1}+\dots+X_K$. Since $X_m$ and $S_{K,m}$ are independent and the random interval $[\max A-S_{K,m},\frac AK,A-S_{K,m}+\Delta]$ lies to the right of $\frac AK$ and has length at most $\Delta$, each term on the RHS is at most $p$ and the claim follows.

Claim 2: Let $A,\Delta>0$. Let $B>A+\Delta$. Let $p=\sup\{P\{X\in [a,a+\Delta]\}\, :\, a\ge \frac {\min(A,B-A-\Delta)}K\}$. Let $K<L$ Then $P\{S_K\in [A,A+\Delta], S_L\in[B,B+\Delta]\}\le K(L-K)p^2$.

Proof: Note that $S_K$ and $S_L-S_K$ are independent and whenever $S_K\in [A,A+\Delta]$ (an event of probability $\le Kp$ by Claim 1), we have $P\{S_L-S_K\in [B-S_K,B-S_K+\Delta]\}\le (L-K)p$ (by the same Claim 1).

Fix $\varepsilon>0$. Choose integers $q,\pi_0>0$ so that $\sum_{\pi\le\pi_0} \pi^{-q}+\sum_{\pi>\pi_0}\pi^{-2}<\varepsilon$. Here and below $\pi$ will run over primes. Call a number $x$ bad if $x$ is divisible by $\pi^q$ with some $\pi\le\pi_0$ or by $\pi^2$ with $\pi>\pi_0$. The upper density of bad numbers is at most $\varepsilon$. Let us now estimate the number of good $x$ between $\frac n2$ and $n$ that have a middle divisor. That middle divisor is certainly between $\frac 12\sqrt n$ and $2\sqrt n$.

Let $\Pi=\sum_{\pi\le n}\pi^{-1}=\log\log n+O(1)$. Consider the random variable $X$ that takes value $\log\pi$ with probability $\Pi^{-1}\pi^{-1}$. Fix $K>0$ and consider the distribution of $S_K$. Note that for every good integer $x$ with exactly $K$ primes (not necessarily distinct) in its prime factorization, $\log x$ can be a value of $S_K$ and that the probability assigned to that value is at least $c(q,\pi_0)\Pi^{-K}\frac{K!}{x}$ (there are at least $\frac{K!}{(q!)^{\pi_0}}$ ways to represent $\log x$ as the sum of $K$ logarithms of primes (the denominator is due to possible repetitions of small primes up to $\pi_0$ each of which can repeat up to $q_0$ times) and the probability that the variables $X_k$ follow some particular pattern is just $\Pi^{-K}$ times the product of the corresponding inverse primes, the latter one being $\frac 1x$.

Note also that the probability that $X$ is in the interval $[\log a, \log a+\log 4]$ is at most $\frac 1{\Pi a}$ times the number of primes between $a$ and $4a$, the latter being at most $C\frac a{\log a}$ by the Chebyshev's bound (we do not need the full strength of the Prime Number Theorem here). Thus, this probability is bounded by $\frac 1{\Pi\log a} $.

Fix $K>0$ and consider the probability that $S_K\in[\log n-\log 2,\log n]$. On the one hand, by Claim 1, it does not exceed $$ K\frac 1{\Pi\frac{\log n-\log 2}{K}}\le \frac {2K^2}{\Pi\log n}\,, $$ say. On the other hand, by the previous remark, it is at least the number $N_K$ of good $x\in[\frac n2,n]$ with prime factorization of length $K$ times $cK!\Pi^{-k}n^{-1}$. It follows that $$ N_K\le CK^2\frac{\Pi^{K-1}}{K!}\frac n{\log n}=C\Pi \frac{\Pi^{K-2}}{(K-2)!}\frac n{\log n}\,. $$ Choose a small $\delta>0$ and consider $K-2>e^\delta \Pi$ first. The sum of the corresponding $N_K$ is bounded by $C\frac n{\log n}\Pi$ times $$ \sum_{K-2>e^\delta \Pi} \Pi \frac{\Pi^{K-2}}{(K-2)!}\le \exp{-\delta e^\delta \Pi}\sum_{K\ge 2} \frac{[e^\delta\Pi]^{K-2}}{(K-2)!} =\exp(e^\delta(1-\delta)\Pi)\,. $$ The crucial part is that $e^\delta(1-\delta)=1-\eta<1$ for every $\delta>0$, so, since $\Pi=\log\log n+O(1)$, we have $\exp(1-\eta)\Pi=O(\log^{1-\eta}n)$ and, thereby, $$ \sum_{K:K-2\ge e^{\delta}\Pi}N_K=O(n\log^{-\eta}n\log\log n)=o(n) $$ as $n\to\infty$. We have just recovered the classical result that the density of $x$ for which the length of their prime factorization noticeably exceeds $\log\log x$ is zero. Of course, this is well-known and the bound we got can be tightened but I just wanted to do it as a warm-up.

Now we see that we are only interested in good $x\in[\frac n2,n]$ with prime factorisations of length $L\le e^{2\delta}\Pi$, say that have a middle divisor (I switched from $K$ to $L$ to make the notation below the same as in Claim 2).

The fact that $x$ has a divisor between $\frac 12\sqrt n$ and $2\sqrt n$ means that we can have $\log x=S_L$ with $S_K\in [\frac 12\log n-\log 2,\frac 12\log n+\log 2]$. Fix such $K$ (there are about $\Pi\approx\log\log n$ possible choices) and consider the probability that $S_K\in [\frac 12\log n-\log 2,\frac 12\log n+\log 2]$ and $S_L\in [\log n-\log 2,\log n]$. By Claim 2 and the following remarks, we can bound it from above by $CK^2L^2\Pi^{-2}\log^{-2}n$. On the other hand, if we can arrange the summation of $X_k$ ($k=1,\dots,L$) to $\log x$ so that $S_K$ is close to $\frac 12\log n$ at all, then we can arrange it in at least $cK!(L-K)!$ ways (just rearrange the first $K$ and the last $L-K$ summands independently; as before, the constant is there to take care of possible repetition of primes $\pi\le\pi_0$). Thus, the number $N_{K,L}$ of good $x$ between $\frac n2$ and $n$ is bounded by $$ Cn(\log\log n)^2\log^{-2}n\frac {\Pi^L}{L!}\frac{L!}{K!(L-K!)}\,. $$ Adding these bounds over all $K$ from $1$ to $L-1$, we find that the number of good $x\in[\frac n2,n]$ with prime factorization of length $L$ and a middle divisor is at most $$ Cn(\log\log n)^2\log^{-2}n\frac {\Pi^L}{L!}2^L\,. $$ Summing upon $L$ up to $e^{2\delta}\Pi$ and estimating $2^L\le C\exp(e^{2\delta} \log 2\log\log n)$, we get the bound $$ Cn(\log\log n)^2\log^{-2}n e^\Pi \exp(e^{2\delta} \log 2\log\log n)\approx Cn(\log\log n)^2\log^{\log 2-1}n $$ so we still have a power of $\log n$ gain.

This is all very crude, as I said. You can do better estimates at the expence of longer proofs. The observation that we typically have only $\log\log x$ prime divisors and, thereby, only $\log x^{\log 2}$ divisors rather than $\log x$ predicted by the average count is very old and goes back at least to Besikovich.