4
$\begingroup$

Let $p_1, ... , p_n, ...$ be the prime numbers in order. Define $$ P_n = \prod_{k=1}^n p_k^q $$ It is known that $\omega(P_n) = n$ where $\omega(\cdot)$ is the little prime omega function. For a given, fixed, $q \in \mathbb{N}$ define $$ Q_n = \prod_{k=1}^n \left( p_k^q - 1 \right) $$ Can we say anything more specific about $\omega(Q_n)$ except to what can be generally said about the average values of $\omega$? At least, can we expect $$ \omega(Q_n) \sim \log(\log(Q_n)) = \log\left( \log\left( \prod_{k=1}^n \left( p_k^q - 1 \right) \right)\right) ? $$

You may assume, for start, that $q=1$ ...

Edit

I have made some limited numerical experiments: enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Let $\tau(n)=\sum_{d\mid n}1$.

H. Halberstam studied related problems in "On the distribution of additive number-theoretic functions. III.", J. Lond. Math. Soc. 31, 14-27 (1956). Given an irreducible polynomial $f$, he proved that $$\sum_{p \le n}\omega(f(p)) \sim \frac{n}{\log n} \log \log n$$ as $n \to \infty$. It is not hard to adapt this result to $\Omega$, which counts prime factors with multiplicities.

This relates to your problem because $$\Omega(Q_n) =\sum_{p\le p_n} \Omega( f_q(p))$$ where $f_q(n) = n^q-1$. While $f_q$ is not irreducible, it factors into $\tau(q)$ (irreducible) cyclotomic polynomials: $f_q(n) = \prod_{d \mid q} \phi_d(n)$. Thus Halberstam's work essentially shows $$\Omega(Q_n) \sim \tau(q) \frac{p_n}{\log p_n}\log \log p_n,$$ while $$\log \log Q_n \sim \log p_n.$$ Since $\Omega(Q_n)-\omega(Q_n)$ can be shown to be small, this shows that your conjecture is off by a factor of $\tau(q)$, in addition to a wrong leading behavior.

The relation $\omega(m)\sim \log \log m$ holds for 'typical' integers, but $Q_n$ is not typical, in particular it factors in a very special way.

Improve this answer
$\endgroup$
12
  • $\begingroup$ I have to admit that this is indeed more than I can understand at the moment ... I surely hope that my Edit 2 is wrong and that somehow $\omega(Q_n) $ is double logarithmic since this is some exponent in an algorithm I am developing. Who is $\phi(q)$ ? Is it large? I plan to consider $q$ as a constant ... $\endgroup$
    – C Marius
    Commented May 23 at 11:24
  • 1
    $\begingroup$ $\phi(q)$ is Euler's totient function evaluated at $q$. If $q$ is a prime, $\phi(q)=q-1$. In general, $\phi$ is a multiplicative function, which counts how many integers in $\{1,2,\ldots,q\}$ are coprime to $q$. My answer shows that $\Omega(Q_n) \sim \phi(q) \log \log Q_n$, so the rate is indeed doubly logarithmic in $Q_n$. Let me also add that $p_n \sim n \log n$ and so $\log \log Q_n \sim n \log \log n$. Let know if something is not clear. $\endgroup$
    – Ofir Gorodetsky
    Commented May 23 at 11:34
  • $\begingroup$ There is one thing ... $\log\log Q_n \leq \log \log P_n \leq \log \log\left( p_n^{n \cdot q}\right) = \log\left( n \cdot q \cdot \log(p_n)\right)$ ... is this correct? It looks different to your expansion ... do I make a wrong judgement ? $\endgroup$
    – C Marius
    Commented May 23 at 12:23
  • $\begingroup$ Can you pls hint at how you have computed $\log\log Q_n$ ? $\endgroup$
    – C Marius
    Commented May 23 at 15:59
  • 1
    $\begingroup$ @CMarius Let $f\colon (0,\infty)\to(0,\infty)$ be a non-decreasing function which is slowly varying, meaning: $\lim_{x \to \infty} f(cx)/f(x)=1$ for every $c>0$. Then I claim that $\sum_{p \le t} f(p) \sim f(t) t/\log t$. Now apply this with $f(x)=\log \log (x^n-1) \sim \log \log x$ and $t = p_n \sim n \log n$. To prove my claim, first note we have the upper bound $\sum_{p \le t} f(p) \le f(t) \sum_{p \le t} 1 \sim f(t) t/\log t$. For the lower bound, given $c>0$ observe $\sum_{p \le t} f(p) \ge \sum_{ct \le t} f(p) \ge f(ct-1) \sum_{ct \le p \le t} 1 \sim f(t) (1-c) t /\log t$ by the PNT. $\endgroup$
    – Ofir Gorodetsky
    Commented May 23 at 17:10

You must log in to answer this question.

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