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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .