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 '19 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 '19 at 18:19

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.

| cite | improve this answer | |
  • 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$ – Fedor Petrov Aug 1 '19 at 10:16
  • 1
    $\begingroup$ @FedorPetrov excellent observation and excellent diagnosis! I've corrected the error $\endgroup$ – Greg Martin Aug 1 '19 at 16:47
  • $\begingroup$ @GregMartin could you please explain the partial summation part in more detail? $\endgroup$ – Kristiyan Vasilev Aug 5 '19 at 20:36

Your Answer

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

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