Let $\omega(m)$ be the number of distinct prime divisors of a positive integer $m>1$. I am interested in the relative orders in which the numbers $\omega(n+1),...,\omega(n+k)$ can occur.

Given a positive integer $k\geq 2$ and a permutation $\sigma$ of $\{1,2,...,k\}$, are there infinitely many positive integers $n$ such that $$\omega(n+\sigma(1))<\omega(n+\sigma(2))<...<\omega(n+\sigma(k))?\quad \quad \quad (1)$$

The result should of course be true as there is no reason to expect correlation between the prime factorizations of consecutive numbers, but I do not know how to prove this. An easy remark is that if one can find for any $k$ and $\sigma$ one $n$ with the desired property, then there are infinitely many $n$ satisfying the claim. An obvious generalization is

Given $k$ and a permutation $\sigma$ of $\{1,2,...,k\}$, is the natural density of those $n$ that satisfy $(1)$ equal to $\frac{1}{k!}$?

This seems very likely since the Erdös-Kac theorem says that $\frac{\omega(n)-\log \log n}{\sqrt{\log \log n}}$ is distributed according to the standard normal distribution. If the random variables $\frac{\omega(n+i)-\log \log n}{\sqrt{\log \log n}}$ were independent even in some weak sense, question 1 would be resolved.

An affirmative answer to my first question would follow from Dickson's conjecture, but my guess is that the answer is known unconditionally, and Dickson's conjecture is a very strong assumption anyway.

I would also like to know whether there is an elementary proof of the special case of question 1 that the sequence $\{\omega(n)\}_{n=2}^{\infty}$ contains arbitrarily long strictly increasing subsequences consisting of consecutive terms.

  • 3
    $\begingroup$ I think just about any of the standard proofs of the Erdos-Kac theorem would extend to give the joint gaussian distribution of the $\frac{\omega(n+i)-\log\log n}{\sqrt{\log\log n}}$, which would give a positive anwswer to your questions. $\endgroup$ – Terry Tao Jun 11 '14 at 2:25
  • 2
    $\begingroup$ To add a tiny bit to Terry Tao's comment: Look for example at this paper by Rizwan Khan (cms.math.ca/cmb/v53/khanB9034.pdf ) where a problem on the simultaneous distribution of $\omega(n+i)$ is considered. Khan wants all of these to be very close to $\log \log (n+i)$ (and with some uniformity) but the method will work in your problem too. $\endgroup$ – Lucia Jun 11 '14 at 2:34
  • $\begingroup$ This is very helpful. Thanks to both of you. $\endgroup$ – Joni Teräväinen Jun 11 '14 at 3:41
  • $\begingroup$ Isn't $k=2$ easy with primes? Take $n=p-1$, $\sigma(1)=1$. $\endgroup$ – joro Jun 11 '14 at 9:35
  • $\begingroup$ Yes, $k=2$ is quite trivial. In the case $k=3, \sigma=id$, the choise $n+1=2^m$ leads to an elementary proof. For $k>3$ and $\sigma=id$ I haven't found an elementary proof. $\endgroup$ – Joni Teräväinen Jun 11 '14 at 16:50

Your Answer

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

Browse other questions tagged or ask your own question.