20
$\begingroup$

How to prove that for some $k, n_0$, for all $n \ge n_0$ it is never the case that all integers in $\{n, n+1, \dots, n + \lfloor (\log{n})^k \rfloor\}$ have exactly the same number of prime factors counted with multiplicity?

I can prove that for any $\epsilon \gt 0$, there exists $n_0$ such that for $n \ge n_0$ not all integers in $\{ n, \dots, n + \lfloor n^\epsilon \rfloor \}$ have the same number of prime factors: assuming that they all have $x$ prime factors, we must have $x \gt \log_2{n^\epsilon} = \epsilon \cdot \log_2{n}$ because the number in the interval divisible by the largest power of $2$ has at least that many factors. So the smallest prime factor of any number in that range is at most $n^\frac{1}{x} \le n^{\frac{1}{\epsilon \cdot \log_2{n}}} = 2^{\frac{1}{\epsilon}}$ which is constant, and for sufficiently large $n$ we have a contradiction. I think the same argument might work for even smaller intervals like $\{n, n+1, \dots, \lfloor n+n^\frac{1}{\log{\log{n}}} \rfloor\}$.

The harder problem with $(\log{n})^k$-size intervals is implied by Cramér's conjecture (since with $k \gt 2$ there would always be a prime and a non-prime) but not vice-versa and it seems like it might be tractable given that I can solve the $n^\epsilon$-size case. How to prove it?

$\endgroup$
3
$\begingroup$

The problem is difficult and there are only partial results. For example Heath-Brown showed that $$\Omega\left(n\right)=\Omega\left(n+1\right)$$ for infinite $n$ (Heath-Brown, A parity problem for sieve theory, Mathematika, 29, p. 1-6, 1982), where $\Omega(*)$ is the function that count the prime divisors with multiplicity. But is quite easy show that your sequence is rare (if exists). In fact, assume $$x=\Omega(n).$$ Using the the fact that $\Omega(*)$ is a completely additive arithmetic function, i. e. $$\Omega(ab)=\Omega(a)+\Omega(b),\,a,b\geq1,$$ we have $$\underset{k=n}{\overset{n+\left\lfloor \log\left(n\right)^{k}\right\rfloor }{\sum}}\Omega\left(k\right)=\Omega\left(n\left(n+1\right)\cdots\left(n+\left\lfloor \log\left(n\right)^{k}\right\rfloor \right)\right)$$and from hypothesis $$\underset{k=n}{\overset{n+\left\lfloor \log\left(n\right)^{k}\right\rfloor }{\sum}}\Omega\left(k\right)=x\left(\left\lfloor \log\left(n\right)^{k}\right\rfloor +1\right)$$so$$\Omega\left(n\right)=x=\frac{\Omega\left(n\left(n+1\right)\cdots\left(n+\left\lfloor \log\left(n\right)^{k}\right\rfloor \right)\right)}{\left(\left\lfloor \log\left(n\right)^{k}\right\rfloor +1\right)}.$$Now, on LHS we have $$\Omega\left(n\right)\sim\log\left(\log\left(n\right)\right)$$as $n\rightarrow \infty$ and on RHS $$\frac{\Omega\left(n\left(n+1\right)\cdots\left(n+\left\lfloor \log\left(n\right)^{k}\right\rfloor \right)\right)}{\left(\left\lfloor \log\left(n\right)^{k}\right\rfloor +1\right)}\sim\frac{\log\left(\sum_{k=n}^{n+\left\lfloor \log\left(n\right)^{k}\right\rfloor }\log\left(k\right)\right)}{\left\lfloor \log\left(n\right)^{k}\right\rfloor +1}\sim\frac{\log\left(n\log\left(n+\left\lfloor \log\left(n\right)^{k}\right\rfloor \right)\right)}{\log\left(n\right)^{k}}=\frac{\log\left(n\right)+\log\left(\log\left(n+\left\lfloor \log\left(n\right)^{k}\right\rfloor \right)\right)}{\log\left(n\right)^{k}}$$which tend to $0$ if $k>1$ and $n \rightarrow \infty$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.