Square-free part of n!
Few days ago, while doing exercise with Indonesian IMO 2017 Team, we came across this problem (which is from Tuymaada Olympiad 2015).
This is actually a hard competition problem, as no one in the competition got a non-zero point. Similar question also being asked in math.stackexchange , with a mention of OEIS A055204 ().
Last week, I presented (a somewhat imprecise (or perhaps incomplete) solution in front of our IMO Team, I used an equivalent form of Prime Number Theorem, this one : $\lim_{n \rightarrow \infty} \frac{\psi(n)}{n}=1$, where $\psi(n)$ is Chebyshev Second Function.
On this post, I will present a more elementary solution, using Stirling's Approximation.
The first guess is to assume at worse, any prime numbers $p \leq n$ appears in the square-free part of $n!$. Thus we have
\[a=\prod_{\substack{p \leq n \\ \text{$p$ prime}}} p \]
There is a known (elementary) bound for the above (due to Paul Erdos) which states that $\prod_{p \leq n} p< 4^n$ (this can be proved by elementary mean, using induction and inequality ${n \choose \lfloor n/2 \rfloor} \leq (1+1)^n=2^n$). However this approximation is not enough for our purpose. Even a more sophisticated bound like $e^n$, is still not a good enough for this problem.
The squarefree part of $n!$, which we will be denoted as $e(n!)$ is the product of primes $p$ with $v_p(n!) \equiv 1 \pmod 2$, here $v_p(x)$ denotes the p-adic valuation of $x$, i.e $k=v_p(x)$ is the largest power of $k$ such that $p^k | x$.
We propose the following bound:
Proof: First notice that the product $C_1(n) C_2(n) \cdots C_i(n) \cdots$ actually has a finite terms, this is because for large $i$ (to be precise when $i > \log_2 n$), $C_i(n)$ has no terms i.e an empty product, indeed when $i$ is large, there is no prime $p$ satisfying $\frac{n}{2k} < p^i \leq \frac{n}{2k-1}$. Similarly the product $\prod_{k=1}^{\infty}$ also has finite terms, since for large enough $k$, the interval $\frac{n}{2k} < p^i \leq \frac{n}{2k-1}$ would be empty.
Let $v=\lfloor \log_2 n \rfloor$ the above product can be written as
\[ \frac{C_1(n)}{\prod_{i=2}^v C_i(n)} \leq e(n!) \leq \prod_{i=1}^v C_i(n)\]
We first prove the upper-bound, let $p$ be a prime less than $n$, with $v_{p}(n!)$ is odd, we will prove that $p$ must be present on the product $C_1(n) C_2(n) \cdots C_v(n)$. Observe that whenever $p$ does not appear in the product, this means that $p$ does not appear on any of $C_{1}(n), C_2(n), ..., C_v(n)$. Since $C_i(n)$ filters all those prime $p$, whose multiple of $p^i$ appears odd many times on interval $[1,n]$, this means the prime $p$ does not appear on $C_{i}(n)$ whenever multiple of $p^i$ appears even many times on interval $[1,n]$.
But if the multiple of $p^i$ appears even many times for all $i$, their total contribution to the total power of $p$ on $n!$ must also be even, which means $v_p(n!)$ must be even , contradiction.
For the lower bound, we observe first that this lower bound, may or may not be an integer. First let, $p$ be a prime which appears on the numerator of $\frac{C_1(n)}{C_2(n) C_3(n) \cdots C_v(n)}$, therefore $p$ appears on the product $C_1(n)$ but is not cancelled out by $C_2(n) C_3(n) \cdots C_v(n)$. Therefore the multiple of $p$ appears odd many times, but multiple of $p^2$, $p^3$, ... $p^v$ appears even many times. This means the total contribution of $p$ to the power of $p$ in $n!$ must be odd, and hence $v_p(n!)$ is odd. This concludes the lemma.
Next observe that using our lemmas (here $v=\lfloor \log_2 n \rfloor$):
\[\begin{align*}\sum_{i=1}^{\infty}\log C_i(n) &= \log C_1(n) C_2(n) \cdots C_v(n) \\ &= \log \left( \prod_{i=1}^v \prod_{k=1}^{\infty} \prod_{\frac{n}{2k} < p^i \leq\frac{n}{2k-1}} p \right) \\ &= \log \left( \prod_{k=1}^{\infty} \prod_{i=1}^v \prod_{\frac{n}{2k} < p^i \leq\frac{n}{2k-1}} p \right) \\ &= \sum_{k=1}^{\infty} \psi\left(\frac{n}{2k-1} \right) - \psi\left(\frac{n}{2k} \right) \\ &= \sum_{k=1}^{\infty} \psi(n/k) - 2 \sum_{k=1}^{\infty}\psi(n/2k) \\ &=T(n)-2T(n/2) \\ &= n \log n -n + O(\log n) - 2 (n/2 \log n/2 - n/2+O(\log n/2)) \\ &= n \log 2 +O(\log n). \end{align*}\]
Now we return to the problem, we want to estimate $e(n!)$ , and from lemma 1 we have
\[2 \log C_1(n) - \sum_{i=1}^{\infty}\log C_i(n) < \log e(n!) < \sum_{i=1}^{\infty}\log C_i(n) \]
The right-hand-side is easily spot on from the last paragraph. The left-hand-side need more careful estimation, which I'm going to elaborate on a separate post.
Let $n!=ab^2$ where $a$ is a squarefree integer, prove that for any $\varepsilon>0$ the inequality
\[2^{(1-\varepsilon)n} < a < 2^{(1+\varepsilon)n}\]
holds for sufficiently large $n$.
This is actually a hard competition problem, as no one in the competition got a non-zero point. Similar question also being asked in math.stackexchange , with a mention of OEIS A055204 ().
Last week, I presented (a somewhat imprecise (or perhaps incomplete) solution in front of our IMO Team, I used an equivalent form of Prime Number Theorem, this one : $\lim_{n \rightarrow \infty} \frac{\psi(n)}{n}=1$, where $\psi(n)$ is Chebyshev Second Function.
On this post, I will present a more elementary solution, using Stirling's Approximation.
The first guess is to assume at worse, any prime numbers $p \leq n$ appears in the square-free part of $n!$. Thus we have
\[a=\prod_{\substack{p \leq n \\ \text{$p$ prime}}} p \]
There is a known (elementary) bound for the above (due to Paul Erdos) which states that $\prod_{p \leq n} p< 4^n$ (this can be proved by elementary mean, using induction and inequality ${n \choose \lfloor n/2 \rfloor} \leq (1+1)^n=2^n$). However this approximation is not enough for our purpose. Even a more sophisticated bound like $e^n$, is still not a good enough for this problem.
The squarefree part of $n!$, which we will be denoted as $e(n!)$ is the product of primes $p$ with $v_p(n!) \equiv 1 \pmod 2$, here $v_p(x)$ denotes the p-adic valuation of $x$, i.e $k=v_p(x)$ is the largest power of $k$ such that $p^k | x$.
We propose the following bound:
Lemma 1 For any $n$ we have
\[ \frac{C_1(n)}{C_2(n) C_3(n) \cdots C_i(n) \cdots } \leq e(n!) \leq C_1(n) C_2(n) \cdots C_i(n) \cdots \]
\[C_v(n) = \prod_{k=1}^{\infty} \prod_{\frac{n}{2k} < p^v \leq\frac{n}{2k-1}} p \]
Proof: First notice that the product $C_1(n) C_2(n) \cdots C_i(n) \cdots$ actually has a finite terms, this is because for large $i$ (to be precise when $i > \log_2 n$), $C_i(n)$ has no terms i.e an empty product, indeed when $i$ is large, there is no prime $p$ satisfying $\frac{n}{2k} < p^i \leq \frac{n}{2k-1}$. Similarly the product $\prod_{k=1}^{\infty}$ also has finite terms, since for large enough $k$, the interval $\frac{n}{2k} < p^i \leq \frac{n}{2k-1}$ would be empty.
Let $v=\lfloor \log_2 n \rfloor$ the above product can be written as
\[ \frac{C_1(n)}{\prod_{i=2}^v C_i(n)} \leq e(n!) \leq \prod_{i=1}^v C_i(n)\]
We first prove the upper-bound, let $p$ be a prime less than $n$, with $v_{p}(n!)$ is odd, we will prove that $p$ must be present on the product $C_1(n) C_2(n) \cdots C_v(n)$. Observe that whenever $p$ does not appear in the product, this means that $p$ does not appear on any of $C_{1}(n), C_2(n), ..., C_v(n)$. Since $C_i(n)$ filters all those prime $p$, whose multiple of $p^i$ appears odd many times on interval $[1,n]$, this means the prime $p$ does not appear on $C_{i}(n)$ whenever multiple of $p^i$ appears even many times on interval $[1,n]$.
But if the multiple of $p^i$ appears even many times for all $i$, their total contribution to the total power of $p$ on $n!$ must also be even, which means $v_p(n!)$ must be even , contradiction.
For the lower bound, we observe first that this lower bound, may or may not be an integer. First let, $p$ be a prime which appears on the numerator of $\frac{C_1(n)}{C_2(n) C_3(n) \cdots C_v(n)}$, therefore $p$ appears on the product $C_1(n)$ but is not cancelled out by $C_2(n) C_3(n) \cdots C_v(n)$. Therefore the multiple of $p$ appears odd many times, but multiple of $p^2$, $p^3$, ... $p^v$ appears even many times. This means the total contribution of $p$ to the power of $p$ in $n!$ must be odd, and hence $v_p(n!)$ is odd. This concludes the lemma.
Next observe that using our lemmas (here $v=\lfloor \log_2 n \rfloor$):
\[\begin{align*}\sum_{i=1}^{\infty}\log C_i(n) &= \log C_1(n) C_2(n) \cdots C_v(n) \\ &= \log \left( \prod_{i=1}^v \prod_{k=1}^{\infty} \prod_{\frac{n}{2k} < p^i \leq\frac{n}{2k-1}} p \right) \\ &= \log \left( \prod_{k=1}^{\infty} \prod_{i=1}^v \prod_{\frac{n}{2k} < p^i \leq\frac{n}{2k-1}} p \right) \\ &= \sum_{k=1}^{\infty} \psi\left(\frac{n}{2k-1} \right) - \psi\left(\frac{n}{2k} \right) \\ &= \sum_{k=1}^{\infty} \psi(n/k) - 2 \sum_{k=1}^{\infty}\psi(n/2k) \\ &=T(n)-2T(n/2) \\ &= n \log n -n + O(\log n) - 2 (n/2 \log n/2 - n/2+O(\log n/2)) \\ &= n \log 2 +O(\log n). \end{align*}\]
Now we return to the problem, we want to estimate $e(n!)$ , and from lemma 1 we have
\[2 \log C_1(n) - \sum_{i=1}^{\infty}\log C_i(n) < \log e(n!) < \sum_{i=1}^{\infty}\log C_i(n) \]
The right-hand-side is easily spot on from the last paragraph. The left-hand-side need more careful estimation, which I'm going to elaborate on a separate post.
Post a Comment: