Proof 1: For \( n = 2 \times 3 \times 5 \times 7 \times \dots \times p_k \), Show that \( \log(n) < p_k \)
Theorem:
Let \( n \) be the product of the first \( k \) prime numbers:
\( n = p_1 \times p_2 \times \dots \times p_k \),
where \( p_k \) is the \( k \)-th prime number. Then:
\( \log(n) < p_k \).
Proof:
-
Express \( \log(n) \) as a Sum:
Using the property of logarithms for products:
\( \log(n) = \log(p_1 \times p_2 \times \dots \times p_k) = \log(p_1) + \log(p_2) + \dots + \log(p_k) \).
-
Define Chebyshev's Function \( \theta(x) \):
Chebyshev's function is defined as:
\( \theta(x) = \sum_{\substack{p \leq x \\ p \text{ is prime}}} \log(p) \).
For \( x = p_k \):
\( \theta(p_k) = \sum_{i=1}^{k} \log(p_i) \).
-
Apply Chebyshev's Inequality:
Chebyshev proved that for all \( x \geq 2 \):
\( \theta(x) < x \).
Therefore, for \( x = p_k \):
\( \theta(p_k) = \sum_{i=1}^{k} \log(p_i) < p_k \).
-
Conclude the Inequality:
Thus:
\( \log(n) = \theta(p_k) < p_k \).
Conclusion:
For \( n = p_1 \times p_2 \times \dots \times p_k \), it holds that:
\( \boxed{\log(n) < p_k} \).
Proof 2: For Highly Composite Numbers \( n \), Show that \( \log(n) > p_k \) for Large \( n \)
Statement:
Let \( n \) be a highly composite number with prime factorization:
\( n = p_1^{j_1} \times p_2^{j_2} \times \dots \times p_k^{j_k} \),
where \( p_i \) are prime numbers in increasing order (\( p_1 = 2, \, p_2 = 3, \, \dots \)), and the exponents satisfy \( j_1 \geq j_2 \geq \dots \geq j_k \geq 1 \), with at least one exponent \( j_i > 1 \).
Then, for highly composite numbers \( n \), it holds that:
\( \log(n) > p_k \).
Proof:
-
Express \( \log(n) \):
The natural logarithm of \( n \) is:
\( \log(n) = \sum\limits_{i=1}^{k} j_i \ln(p_i) \).
-
Split the sum:
We split the sum into two parts:
\( \log(n) = \underbrace{\sum\limits_{i=1}^{k} \ln(p_i)}_{\theta(p_k)} + \underbrace{\sum\limits_{i=1}^{k} (j_i - 1) \ln(p_i)}_{\Delta} \),
where:
- \( \theta(p_k) = \sum\limits_{i=1}^{k} \ln(p_i) \) is Chebyshev's function.
- \( \Delta = \sum\limits_{i=1}^{k} (j_i - 1) \ln(p_i) \) represents the contribution from exponents greater than 1.
-
Estimate \( \delta_k = p_k - \theta(p_k) \):
From the Prime Number Theorem and known estimates, we have:
\( |\delta_k| \leq C \dfrac{p_k}{\ln p_k} \),
where \( C > 0 \) is a constant. For our purposes, we choose \( C = 0.1 \).
-
Estimate \( \Delta \):
Let \( r \) be the number of exponents \( j_i > 1 \), and let \( j_{\text{min}} = \min\{j_i : j_i > 1\} \geq 2 \). Then:
\( \Delta = \sum\limits_{i=1}^{k} (j_i - 1) \ln(p_i) \geq (j_{\text{min}} - 1) \sum\limits_{i=1}^{r} \ln(p_i) \).
Since \( p_i \geq 2 \), we have:
\( \sum\limits_{i=1}^{r} \ln(p_i) \geq r \ln(2) \),
thus:
\( \Delta \geq (j_{\text{min}} - 1) r \ln(2) \).
-
Compare \( \Delta \) and \( |\delta_k| \):
We need to show that:
\( \Delta > |\delta_k| \implies (j_{\text{min}} - 1) r \ln(2) > C \dfrac{p_k}{\ln p_k} \).
-
Relate \( p_k \) and \( k \):
The \( k \)-th prime satisfies approximately:
\( p_k \approx k \ln k \),
and thus:
\( \ln p_k \approx \ln(k \ln k) \approx \ln k + \ln \ln k \).
-
Estimate \( \dfrac{p_k}{\ln p_k} \):
We have:
\( \dfrac{p_k}{\ln p_k} \approx \dfrac{k \ln k}{\ln k + \ln \ln k} \approx k \).
Therefore:
\( |\delta_k| \leq C k \).
-
Compare \( \Delta \) and \( |\delta_k| \):
From our estimates:
\( \Delta \geq (j_{\text{min}} - 1) r \ln(2) \).
To ensure \( \Delta > |\delta_k| \), we need:
\( (j_{\text{min}} - 1) r \ln(2) > C k \).
-
Relate \( r \) and \( k \):
Let \( r = \alpha k \), where \( 0 < \alpha \leq 1 \). Then:
\( (j_{\text{min}} - 1) \alpha k \ln(2) > C k \implies (j_{\text{min}} - 1) \alpha \ln(2) > C \).
-
Set conditions on \( \alpha \) and \( j_{\text{min}} \):
To satisfy the inequality, we need:
\( \alpha > \dfrac{C}{(j_{\text{min}} - 1) \ln(2)} \).
Since \( j_{\text{min}} - 1 \geq 1 \) and \( \ln(2) \approx 0.6931 \), we obtain:
\( \alpha > \dfrac{0.1}{0.6931} \approx 0.1443 \).
-
Conclusion:
For highly composite numbers, \( \alpha \) is often greater than the required value, so \( \Delta > |\delta_k| \), and thus:
\( \log(n) = \theta(p_k) + \Delta = p_k - \delta_k + \Delta > p_k \).
Therefore, \( \log(n) > p_k \).
Example to Illustrate the Proof:
Let \( n = 2^5 \times 3^4 \times 5^3 \times 7^2 \times 11^2 \times 13 \times 17 \times 19 \).
- Primes (\( p_i \)): \( 2, 3, 5, 7, 11, 13, 17, 19 \).
- Exponents (\( j_i \)): \( 5, 4, 3, 2, 2, 1, 1, 1 \).
- Number of primes (\( k \)): \( 8 \).
- Number of exponents greater than 1 (\( r \)): \( 5 \).
- Largest prime (\( p_k \)): \( 19 \).
Calculate \( \theta(p_k) \):
\(
\theta(p_k) = \sum_{i=1}^{8} \ln(p_i) \approx 16.0875.
\)
Calculate \( \Delta \):
\(
\Delta = (5 - 1)\ln(2) + (4 - 1)\ln(3) + (3 - 1)\ln(5) + (2 - 1)\ln(7) + (2 - 1)\ln(11) \approx 13.6308.
\)
Calculate \( \delta_k \):
\(
\delta_k = p_k - \theta(p_k) = 19 - 16.0875 = 2.9125.
\)
Compare \( \Delta \) and \( \delta_k \):
\(
\Delta = 13.6308 > \delta_k = 2.9125.
\)
Compute \( \log(n) \):
\(
\log(n) = \theta(p_k) + \Delta = 16.0875 + 13.6308 = 29.7183.
\)
Compare \( \log(n) \) and \( p_k \):
\(
\log(n) = 29.7183 > p_k = 19.
\)
Verify the condition for \( \alpha \):
We have \( \alpha = \dfrac{r}{k} = \dfrac{5}{8} = 0.625 \), which is greater than \( 0.1443 \). Therefore, the condition is satisfied.
Conclusion:
This example illustrates the validity of the proof that for highly composite numbers \( n \), it holds that \( \log(n) > p_k \).
\( \boxed{\log(n) > p_k} \).
Dôkaz 1: Pre \( n = 2 \times 3 \times 5 \times 7 \times \dots \times p_k \) platí \( \log(n) < p_k \)
Tvrdenie:
Nech \( n \) je súčin prvých \( k \) prvočísel:
\( n = p_1 \times p_2 \times \dots \times p_k \),
kde \( p_k \) je \( k \)-té prvočíslo. Potom platí:
\( \log(n) < p_k \).
Dôkaz:
-
Vyjadrenie \( \log(n) \) ako súčet:
Využitím vlastnosti logaritmu pre súčin:
\( \log(n) = \log(p_1 \times p_2 \times \dots \times p_k) = \log(p_1) + \log(p_2) + \dots + \log(p_k) \).
-
Definovanie Chebyshevovej funkcie \( \theta(x) \):
Chebyshevova funkcia je definovaná ako:
\( \theta(x) = \sum_{\substack{p \leq x \\ p \text{ je prvočíslo}}} \log(p) \).
Pre \( x = p_k \):
\( \theta(p_k) = \sum_{i=1}^{k} \log(p_i) \).
-
Uplatnenie Chebyshevovej nerovnosti:
Chebyshev dokázal, že pre všetky \( x \geq 2 \) platí:
\( \theta(x) < x \).
Preto pre \( x = p_k \):
\( \theta(p_k) = \sum_{i=1}^{k} \log(p_i) < p_k \).
-
Záver nerovnosti:
Teda:
\( \log(n) = \theta(p_k) < p_k \).
Záver:
Pre \( n = p_1 \times p_2 \times \dots \times p_k \) platí:
\( \boxed{\log(n) < p_k} \).
Dôkaz 2: Pre vysoko-zložené čísla \( n \) platí \( \log(n) > p_k \) pre veľké \( n \)
Tvrdenie:
Nech \( n \) je vysoko-zložené číslo s prvočíselným rozkladom:
\( n = p_1^{j_1} \times p_2^{j_2} \times \dots \times p_k^{j_k} \),
kde \( p_i \) sú prvočísla v rastúcom poradí (\( p_1 = 2, \, p_2 = 3, \, \dots \)) a exponenty spĺňajú \( j_1 \geq j_2 \geq \dots \geq j_k \geq 1 \), pričom aspoň jeden exponent \( j_i > 1 \).
Potom pre vysoko-zložené čísla \( n \) platí:
\( \log(n) > p_k \).
Dôkaz:
-
Vyjadrenie \( \log(n) \):
Prirodzený logaritmus čísla \( n \) je:
\( \log(n) = \sum\limits_{i=1}^{k} j_i \ln(p_i) \).
-
Rozdelenie súčtu:
Rozdelíme súčet na dve časti:
\( \log(n) = \underbrace{\sum\limits_{i=1}^{k} \ln(p_i)}_{\theta(p_k)} + \underbrace{\sum\limits_{i=1}^{k} (j_i - 1) \ln(p_i)}_{\Delta} \),
kde:
- \( \theta(p_k) = \sum\limits_{i=1}^{k} \ln(p_i) \) je Chebyshevova funkcia.
- \( \Delta = \sum\limits_{i=1}^{k} (j_i - 1) \ln(p_i) \) predstavuje príspevok od exponentov väčších ako 1.
-
Odhad \( \delta_k = p_k - \theta(p_k) \):
Z Veľkej vety o prvočíslach a známych odhadov vieme, že:
\( |\delta_k| \leq C \dfrac{p_k}{\ln p_k} \),
kde \( C > 0 \) je konštanta. Pre naše účely zvolíme \( C = 0{,}1 \).
-
Odhad \( \Delta \):
Nech \( r \) je počet exponentov \( j_i > 1 \) a \( j_{\text{min}} = \min\{j_i : j_i > 1\} \geq 2 \). Potom:
\( \Delta = \sum\limits_{i=1}^{k} (j_i - 1) \ln(p_i) \geq (j_{\text{min}} - 1) \sum\limits_{i=1}^{r} \ln(p_i) \).
Keďže \( p_i \geq 2 \), platí:
\( \sum\limits_{i=1}^{r} \ln(p_i) \geq r \ln(2) \),
teda:
\( \Delta \geq (j_{\text{min}} - 1) r \ln(2) \).
-
Porovnanie \( \Delta \) a \( |\delta_k| \):
Potrebujeme ukázať, že:
\( \Delta > |\delta_k| \implies (j_{\text{min}} - 1) r \ln(2) > C \dfrac{p_k}{\ln p_k} \).
-
Vzťah medzi \( p_k \) a \( k \):
Pre \( k \)-té prvočíslo platí približne:
\( p_k \approx k \ln k \),
a teda:
\( \ln p_k \approx \ln(k \ln k) \approx \ln k + \ln \ln k \).
-
Odhad \( \dfrac{p_k}{\ln p_k} \):
Máme:
\( \dfrac{p_k}{\ln p_k} \approx \dfrac{k \ln k}{\ln k + \ln \ln k} \approx k \).
Teda:
\( |\delta_k| \leq C k \).
-
Porovnanie \( \Delta \) a \( |\delta_k| \):
Z odhadov máme:
\( \Delta \geq (j_{\text{min}} - 1) r \ln(2) \).
Pre \( \Delta > |\delta_k| \) potrebujeme:
\( (j_{\text{min}} - 1) r \ln(2) > C k \).
-
Vzťah medzi \( r \) a \( k \):
Nech \( r = \alpha k \), kde \( 0 < \alpha \leq 1 \). Potom:
\( (j_{\text{min}} - 1) \alpha k \ln(2) > C k \implies (j_{\text{min}} - 1) \alpha \ln(2) > C \).
-
Nastavenie podmienok pre \( \alpha \) a \( j_{\text{min}} \):
Pre splnenie nerovnosti potrebujeme:
\( \alpha > \dfrac{C}{(j_{\text{min}} - 1) \ln(2)} \).
Keďže \( j_{\text{min}} - 1 \geq 1 \) a \( \ln(2) \approx 0{,}6931 \), dostaneme:
\( \alpha > \dfrac{0{,}1}{0{,}6931} \approx 0{,}1443 \).
-
Záver:
Pre vysoko-zložené čísla je \( \alpha \) často väčšie ako požadovaná hodnota, preto platí \( \Delta > |\delta_k| \) a teda:
\( \log(n) = \theta(p_k) + \Delta = p_k - \delta_k + \Delta > p_k \).
Teda \( \log(n) > p_k \).
Príklad na ilustráciu dôkazu:
Nech \( n = 2^5 \times 3^4 \times 5^3 \times 7^2 \times 11^2 \times 13 \times 17 \times 19 \).
- Prvočísla (\( p_i \)): \( 2, 3, 5, 7, 11, 13, 17, 19 \).
- Exponenty (\( j_i \)): \( 5, 4, 3, 2, 2, 1, 1, 1 \).
- Počet prvočísel (\( k \)): \( 8 \).
- Počet exponentov väčších ako 1 (\( r \)): \( 5 \).
- Najväčšie prvočíslo (\( p_k \)): \( 19 \).
Výpočet \( \theta(p_k) \):
\(
\theta(p_k) = \sum_{i=1}^{8} \ln(p_i) \approx 16{,}0875.
\)
Výpočet \( \Delta \):
\(
\Delta = (5 - 1)\ln(2) + (4 - 1)\ln(3) + (3 - 1)\ln(5) + (2 - 1)\ln(7) + (2 - 1)\ln(11) \approx 13{,}6308.
\)
Výpočet \( \delta_k \):
\(
\delta_k = p_k - \theta(p_k) = 19 - 16{,}0875 = 2{,}9125.
\)
Porovnanie \( \Delta \) a \( \delta_k \):
\(
\Delta = 13{,}6308 > \delta_k = 2{,}9125.
\)
Výpočet \( \log(n) \):
\(
\log(n) = \theta(p_k) + \Delta = 16{,}0875 + 13{,}6308 = 29{,}7183.
\)
Porovnanie \( \log(n) \) a \( p_k \):
\(
\log(n) = 29{,}7183 > p_k = 19.
\)
Overenie podmienky pre \( \alpha \):
Máme \( \alpha = \dfrac{r}{k} = \dfrac{5}{8} = 0{,}625 \), čo je väčšie ako \( 0{,}1443 \). Podmienka je teda splnená.
Záver:
Tento príklad ilustruje platnosť dôkazu, že pre vysoko-zložené čísla \( n \) platí \( \log(n) > p_k \).
\( \boxed{\log(n) > p_k} \).