Skip to main content
MathOverflow

Return to Answer

added 444 characters in body
Source Link
Greg Martin
Greg Martin
  • 12.8k
  • 1
  • 48
  • 72

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\log n), \end{align*}\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.

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\log n), \end{align*} where the last equality used partial summation.

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.

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.

added 17 characters in body
Source Link
Greg Martin
Greg Martin
  • 12.8k
  • 1
  • 48
  • 72

Fleshing out Wojowu's comment: set $K = \big\lfloor \frac{\log n}{\log p} \big\rfloor$. Since $$ 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) $$\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 \log\log n}2 + O(n\log n), \end{align*}\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\log n), \end{align*} where the last equality used partial summation.

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;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.

Fleshing out Wojowu's comment: set $K = \big\lfloor \frac{\log n}{\log p} \big\rfloor$. Since $$ 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) $$ 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 \log\log n}2 + O(n\log n), \end{align*} where the last equality used partial summation.

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

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\log n), \end{align*} where the last equality used partial summation.

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.

Source Link
Greg Martin
Greg Martin
  • 12.8k
  • 1
  • 48
  • 72

Fleshing out Wojowu's comment: set $K = \big\lfloor \frac{\log n}{\log p} \big\rfloor$. Since $$ 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) $$ 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 \log\log n}2 + O(n\log n), \end{align*} where the last equality used partial summation.

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