Let $\omega(m)$ be the number of prime factors of $m$ regardless of multiplicity. I'm interested in the behavior of the finite sequence $(\omega(n-r)\omega(n+r))_{0\leq r\leq n-1}$ for a given integer $n$: denoting by $M_{\omega}(n):=\sup_{r\in[0,n-1]\cap\mathbb{Z}}\omega(n-r)\omega(n+r)$, does this finite sequence reach each integral value of $[1,M_{\omega}(n)]$ for infinitely many integers $n$? Can techniques from probabilistic number theory allow to prove this set of integers $n$ has positive natural density? Can density $1$ be reached?
$\begingroup$
$\endgroup$
2
asked May 31, 2022 at 18:55
-
1$\begingroup$ Numerical search suggests 23 the largest such $n$ (none others up to 5000 or so), and some vague heuristics seem to suggest such integers would be very rare. Hoping for positive natural density, let alone density 1, seems way overly optimistic. $\endgroup$– WojowuCommented May 31, 2022 at 19:23
-
2$\begingroup$ Thank you. Maybe you can post the "vague heuristics" you refer to as an answer. $\endgroup$– Sylvain JULIENCommented May 31, 2022 at 19:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
I would expect there are only finitely many such $n$. A numerical search suggests the complete set of such integers is $\{1,2,3,4,5,7,16,17,19,23\}$ - there are no others below 10000. Here is an argument that such numbers, if they exist, should be rare.
First, observe that any prime appearing in such sequence must arise from one of $\omega(n\pm r)$ being equal to $1$. We have $\omega(k)\leq\frac{\log k}{\log\log k}+O(1)$ (because the product of $m$ distinct primes is, by PNT, at least $m^m$ or so), this means that all primes appearing in that sequence are $\leq\frac{\log n}{\log\log n}+O(1)$. By PNT again, this means that if all integers up to $M_\omega(n)$ arise as in the question, then $M_\omega(n)\leq (1+o(1))\frac{\log n}{\log\log n}+O(1)$
On the other hand, there are many possible products of $\approx\frac{\log n}{\log\log n}$ products of "small" primes which one could form and be smaller than $n$. For any such product $P$, we have $\omega(P)\approx\frac{\log n}{\log\log n}$. In order for $M_\omega(n)$ to satisfy the required bound, we would need $\omega(2n-P)$ for all of these products to be equal to $1$, i.e. $2n-P$ would need to be a prime power for all such products $P$. To me this seems exceedingly unlikely, although it cannot be excluded by an obvious counting argument. Someone versed in sieve theory might be able to prove an appropriate impossibility result formally.
Update: as fedja points out in the comment, we can in fact quite easily arrange (by taking a lot of primes and then modifying which small primes we include) for $P$ to have the same residue class modulo (say) $30$ as $2n$. Then $30\mid 2n-P$ so that $\omega(2n-P)\geq 3$, which by the argument above gives a contradiction for large $n$. I'm sure this argument can be made explicit, which could give that 23 is indeed the largest number like you ask for.
-
3$\begingroup$ Just notice that a "product $P$ of small primes" can be anything you want modulo any particular number, so $2n-P$ can be always made divisible by $30$, say, and your proof shows that, indeed, there are only finitely many such $n$ :-) $\endgroup$– fedjaCommented May 31, 2022 at 20:47
-
$\begingroup$ @fedja That's a good point! I tried some explicit constructions of that sort by taking $n$ to have a small prime factor, but I didn't think to try and make $2n-P$ hit a specific residue class in general! I have added a note to the answer to acknowledge this. $\endgroup$– WojowuCommented May 31, 2022 at 20:58