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: