What is the best lower bound known for $$\prod_{p\equiv 3 \pmod 4} p^{v_p(n!)},$$ where the product is taken over all the primes(congruent to $3$ modulo $4$) less than or equal to $n$.

  • 1
    $\begingroup$ Although it's possible to make it work, $p \equiv 3 (\mod 4)$ (p \equiv 3 (\mod 4)) on its own produces terrible spacing. $p \equiv 3 \pmod 4$ (p \equiv 3 \pmod 4) isn't necessarily a lot better in subscripts, but it's the intended useage. I have edited accordingly. $\endgroup$
    – LSpice
    Jul 31, 2019 at 17:48
  • 4
    $\begingroup$ By Legendre's formula, $v_p(n!)\approx n/(p-1)$. Taking logarithms, you are then essentially asking for a lower bound for $n\sum_{p\equiv 3\pmod 4}\frac{\log p}{p-1}$, which can be estimated with partial summation and PNT in arithmetic progressions. Looking up the error bounds on the latter and bounding the error in Legendre, you can get the desired lower bound. $\endgroup$
    – Wojowu
    Jul 31, 2019 at 18:19

1 Answer 1


Fleshing out Wojowu's comment: set $K = \big\lfloor \frac{\log n}{\log p} \big\rfloor$. Since \begin{align*} v_p(n!) = \sum_{1\le k\le K} \bigg\lfloor \frac n{p^k} \bigg\rfloor &\ge \sum_{1\le k\le K} \bigg( \frac n{p^k} - 1 \bigg) \\ &= \frac n{p-1} - \frac n{p^K(p-1)} - K = \frac n{p-1} + O\bigg( \frac{\log n}{\log p} \bigg) \end{align*} for $p\le n$, we have \begin{align*} \log\prod_{p\equiv 3 \pmod 4} p^{v_p(n!)} &= \sum_{\substack{p\le n \\ p\equiv 3\pmod 4}} \bigg( \frac n{p-1} + O\bigg( \frac{\log n}{\log p} \bigg) \bigg) \log p \\ &= n \sum_{\substack{p\le n \\ p\equiv 3\pmod 4}} \frac{\log p}{p-1} + O\big( \pi(n;4,3) \log n \big) \\ &= \frac{n \log n}2 + O(n), \end{align*} where the last equality used partial summation: with $\theta(x;4,3) = \sum_{p\le x,\, p\equiv3\pmod 4} \log p \sim x/2$, \begin{align*} \sum_{\substack{p\le n \\ p\equiv 3\pmod 4}} \frac{\log p}{p-1} &= \int_2^n \frac1{t-1} \,d\theta(t;4,3) \\ &= \frac{\theta(t;4,3)}{t-1} \bigg|_2^n + \int_2^n \frac{\theta(t;4,3)}{(t-1)^2} \,dt \\ &= O(1) + \int_2^n \frac{t+O(t/\log^2t)}{(t-1)^2} \,dt \\ &= O(1) + \bigg( \log(t-1) - \frac1{t-1} \bigg) \bigg|_2^n + O(1) \\ &= \log n + O(1). \end{align*}

In hindsight, of course $n(\log n)/2$ should be the main term: we expect the product to be roughly the square root of $n!$, and $\log\sqrt{n!} \sim n(\log n)/2$ by Stirling's formula.

All the steps of this argument can be given with explicit constants in the inequalities if you want (including corresponding upper bounds); the partial summation step can start with an explicit lower bound for $\theta(n;4,3)$ found in this paper for example.

  • 2
    $\begingroup$ But our product does not exceed $\prod_p p^{\nu_p(n!)}=n!$, so its logarithm should not grow faster than $\log n!=n\log n+O(n)$. I guess your asymptotic formula for $\sum_{p\leqslant n, p=4k+3} \log p/p$ has to be corrected. $\endgroup$ Aug 1, 2019 at 10:16
  • 1
    $\begingroup$ @FedorPetrov excellent observation and excellent diagnosis! I've corrected the error $\endgroup$ Aug 1, 2019 at 16:47
  • $\begingroup$ @GregMartin could you please explain the partial summation part in more detail? $\endgroup$ Aug 5, 2019 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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