An upper bound for Jacobsthal's Function
by Hans-Joachim Kanold
The untranslated article is here.
Paul Erdos: Let $n$ be any integer. Jacobsthal defines $g(n)$ to be the least integer so that amongst any $g(n)$ consecutive integers $a, a+1, \dots, a+g(n)-1$ there is at least one which is relatively prime to $n$
Paul Erdos has shown that for almost all $n$, the order of magnitude of $g(n)$ is the same as $\frac{n}{\varphi(n)}V(n)$ with $\varphi(n)$, the well-known Euler function, and with $V(n)$ the number of different prime divisors of $n$.
"Almost all” means: all natural numbers $n$ with the exception of a set of natural density zero. Note [3] investigated relationships between $g(n)$ and prime numbers in arithmetic sequences. (Note 3: KANOLD, H.-J.: Über Primzahlen in arithmetischen Folgen. Math. Ann. 156, 393-395 (1964), t57, 358-362 (t965).)
The present work aims to provide further estimates of $g(n)$ to be derived.
We can rely on square-free arguments $n>1$ restricted.
Let:
(1) $n = p_1 p_2 \dots p_k$ with $2 \le p_1 < p_2 < \dots < p_k$ the canonical decomposition of $n$ into a product of prime numbers
Furthermore, for the shortcut:
(2) $g(n) = g$
And: $g(p_1) = 2$ applies, we can now also assume $k > 1$. Based on the definition of $g$ there exists (at least) one natural number $a$ so that:
(3) $(a,n) = (a+g,n) = 1$; and $(a + \gamma) > 1$ for $\gamma; = 1, \dots, g-1$.
With the known function of Möbius we get a first basic relationship:
(4) $g -1 = - \sum\limits_{d|n\text{, }d>1}\mu(d)\left(\left[\frac{a+g-1}{d}\right]-\left[\frac{a}{d}\right]\right)$
We now introduce the following abbreviated terms.
(5) $\frac{a+g-1}{d} - \left[\frac{a+g-1}{d}\right] = \Theta_d; \frac{a}{d} - \left[\frac{a}{d}\right] = \vartheta_d$
From (3), for $d > 1$, it follows:
(6) $0 \le \Theta_d \le 1 - \frac{2}{d}; \frac{1}{d} \le \vartheta_d \le 1 - \frac{1}{d}$
Because $\Theta_d = 1 - \frac{1}{d}$ leads to $d|a+g$, the second basic relationship is:
(7) $(g-1)\frac{\varphi(n)}{n} = \sum_\limits{d|n\text{, }d>1}\mu(d)(\Theta_d - \vartheta_d)$
Let:
(8) $(a+\gamma, n) = \delta_{\gamma} \text{ } (\gamma = 1, \dots, g-1)$
then according to (1) and (3) always:
(9) $\delta_{\gamma} \ge p_1; \delta_{\gamma} | p_1 \dots p_k; V(\delta_{\gamma}) \ge 1$
We look at the product:
(10) $\Delta = \delta_1 \delta_2 \dots \delta_{g-1}$
And ask: How often is $(1 \le K \le k)$ in $\Delta$? The number of multiples of $p_K$ which is not larger than $a + g - 1$ are given by $\left[\frac{a+g-1}{p_K}\right]$; the number of multiples that are not greater than $a$ is $\left[\frac{a}{p_K}\right]$. So:
(11) $\Delta = \prod\limits_{K=1}^k {p_K}^{\left[\frac{a+g-1}{p_K}\right] - \left[\frac{a}{p_K}\right]}$
The number of $\Delta$ contained prime numbers, each according to its multiplicity counted, is therefore
(12) $\sum\limits_{K=1}^{k} \left(\left[\frac{a+g-1}{p_K}\right] - \left[\frac{a}{p_K}\right]\right)$
According to (3) it is of course:
(13) $\left[\frac{a}{p_K}\right] = \left[\frac{a-1}{p_K}\right]$; $\left[\frac{a+g-1}{p_K}\right] = \left[\frac{a+g}{p_K}\right]$
If we denote, as in the introduction, with $V(m)$ the number of different prime divisors of a natural number $m$, then we get the third basic relationship:
(14) $\sum\limits_{\gamma = 1}^{g-1}V(\delta_{\gamma}) =$ $\sum\limits_{K=1}^{k}$ $ \left(\left[\frac{a+g-1}{p_K}\right] - \left[\frac{a}{p_K}\right]\right)$ $= (g-1)\sum\limits_{K=1}^{k}\frac{1}{p_K} + \sum\limits_{K=1}^k \left( \vartheta_{p_K} - \Theta_{p_K} \right)$
For the abbreviation we use:
(15) $\frac{1}{g-1}\sum\limits_{\gamma=1}^{g-1} V(\delta_{\gamma}) -$ $\sum\limits_{K=1}^k \frac{1}{p_K} = \frac{1}{g-1}\sum\limits_{K=1}^k$ $( \vartheta_{p_K} - \Theta_{p_K} ) = \xi$
Let $d | n, d \nmid a + \gamma$ for $\gamma = 1, \dots, g-1$. It follows:
(16) $\Theta_d - \vartheta_d = \frac{g-1}{d}$
Let $d | n, d> 1$ and:
(17) $d | a + \gamma_d$; $d | a + g - {\gamma`}_d$; $1 \le \gamma_d \le g - {\gamma'}_d$; $1 \le \gamma_d, {\gamma'}_d \le \text{min}\{d-1, g-1\},$
It follows from (5):
(18) $\vartheta_d = 1 - \frac{\gamma_d}{d}$; $\Theta_d = \frac{{\gamma'}_d - 1}{d}$; $\Theta_d - \vartheta_d = \frac{\gamma_d - {\gamma'}_d -1}{d} - 1$
According to (17):
(19) $\gamma_d + {\gamma'}_d \le \text{min}\{g; 2d-2\}$; $0 \le g - \gamma_d - {\gamma'}_d \equiv 0 \pmod d$
II. We now want to derive some simple estimates from the basic relationships.
Lemma 1: It always applies that: $0 < |\xi| < 1$
Proof: We first show that $\xi(g-1)$ cannot be completely, therefore also in particular $\xi$ not equal to zero. From (15) we get:
(20) $p_1 \dots p_k \sum\limits_{\gamma = 1}^{g-1}V(\delta_{\gamma}) - (g-1) \sum\limits_{K=1}^k \frac{p_1\dots p_k}{p_K} = \xi(g-1)p_1 \dots p_k$
Furthermore,
(21) $\left(\sum\limits_1^k \frac{p_1 \dots p_k}{p_K}, p_1 \dots p_k \right) = 1$
Would now be $\xi(g-1)$ completely, so would be:
(22) $p_1 \dots p_k | g-1$; $g-1 \ge n$
But that would mean that there is a sequence of length $n$ which does not contain a number that is relatively prime to $n$, which is obviously a contradiction, since every such sequence has exactly $\varphi(n)$ to $n$ must contain coprime numbers. It is always (cf. [2]).
(23) $g \ge k+1$
After (6) and (15) follows
(24) $|\xi| \le \frac{1}{k} \sum\limits_1^k |\vartheta_{p_K} - \Theta_{p_K}| \le \frac{1}{k} \sum\limits_1^k \left(1 - \frac{1}{p_K} \right) < 1$
The complete proof of the above proposition.
Lemma 2: Let $k>1$. For $\xi < 0$ applies $g < \frac{k-3}{|\xi|} -2$, For $\xi > 0$ applies $g < \frac{k-1}{\xi} + 2$
Proof: Because of $g(p_1 \dots p_k) > g \left(\frac{p_1 \dots p_k}{p_K} \right)$ for any $K \in \{ 1, \dots, k \}$ are for $d = p_K$ the prerequisites (17) are met. According to (15), (17) to (19) we obtain:
(25) $g - 1 = \frac{1}{\xi} \sum\limits_1^k \left( 1 - \frac{\gamma_{p_K} + {\gamma'}_{p_K} -1}{p_K} \right)$; $2 \le \gamma_{p_K} + {\gamma'}_{p_K} \equiv g \pmod {p_K}$
Let $\xi > 0$. Were $\gamma_{p_K} + {\gamma'}_{p_K} = 2$ for all $K=1, \dots, k$ then it would be for $k > 1$ that means $g - 2 > 0$
(26) $n = p_1 \dots p_k | g-2$, $g-2 \ge n$
which leads to a contradiction as in (23). Thus, according to (9), (15) and (25) we have
(27) $g-1 < \frac{1}{\xi} \left( k - \sum\limits_1^k \frac{1}{p_K} \right) = \frac{k}{\xi} - \frac{1}{\xi} \left( \frac{1}{g-1} \sum\limits_1^{g-1} V(\delta_{\gamma}) - \xi\right) \le \frac{k}{\xi} - \frac{1}{\xi}(1 - \xi);$ $g < \frac{k-1}{\xi} + 2$
Let $\xi < 0$. From (25) we obtain (28):
(28) $g-1 = \frac{1}{|\xi|} \left( \sum\limits_1^k \frac{\gamma_{p_K} - {\gamma'}_{p_K}-1}{p_K} -k \right)$
Were $\gamma_{p_K} + {\gamma'}_{p_K} = 2p_K - 2 [cf. (19)] for $K=1, \dots, k$, so would be
(29) $p_K | g - 2p_K+2$; $n=p_1 \dots p_k | g+2$; $g+2 \ge n$
Then there would be a sequence of natural numbers of length $n-3$, which does not contain a number that is coprime to $n$. We would have:
(30) $n - \varphi(n) \ge n - 3$; $3 \ge \varphi(n) = (p_1 - 1) \dots (p_k - 1)$
Because $p_3 -1 \ge 4$, it follows $k \le 2$; because of $|\xi| = \sum\limits_1^k \frac{1}{p_K} - \frac{1}{g-1} \sum\limits_1^{g-1} V(\delta_{\gamma} \le \sum\limits_1^k \frac{1}{p_K} - 1$
but delivers
(31) $1 + |\xi| \le \sum\limits_1^k \frac{1}{p_K} \le \frac{1}{2} + \frac{1}{3}$
a contradiction. Therefore, according to (28)
(32) $g - 1 < \frac{1}{|\xi|} \left( \sum\limits_1^k \frac{2p_K - 3}{p_K} - k\right) = \frac{1}{|\xi|} \left( k - 3 \sum\limits_1^k \frac{1}{p_K} \right) \le \frac{1}{|\xi|} (k - 3 - 3|\xi|)$; $g < \frac{k-3}{|\xi|} - 2$
This proves the Lemma 2. A simple consequence is
Lemma 3: Let $k > 1$. For $\xi \ge \frac{1}{k+1}$ or $\xi \le \frac{-1}{k+3}$ follows $g \le k^2$
Proof: If $\xi \le \frac{-1}{k+3}$, then Lemma 2 provides:
(33) $g < (k-3)(k+3) - 2 = k^2 - 11 < k^2$
If $\xi \ge \frac{1}{l+1}$, then follows:
(34) $g < (k-1)(k+1) + 2 = k^2 + 1$; $g \le k^2$
From a slightly different structure is the:
Lemma 4: If $m$ and $n$ are two coprime natural numbers, then $g(mn) \le \text{min} \{ mg(n) - \varphi(m) + 1; ng(m) - \varphi(n) + 1 \} $
Proof: We imagine a sequence of length $mg(n) = mg$ given $a+1, a+2, \dots, a+mg.$ We arrange these ms numbers in a rectangular scheme:
(35)
$a+1 \qquad \qquad \qquad \qquad a+2, \dots, \dots, \dots, a+m$
$a+m+1 \qquad \qquad \qquad a+m+2, \dots,\dots, \dots, a+2m$
$\vdots$
$a+(g-1)m + 1 \qquad a+(g-1)m+2,\dots,\dots,\dots,a+gm$
Each column of (35) consists of numbers belonging to the same residue class $\text{mod}$ $m$. There are exactly $\varphi(m)$ columns whose numbers are all relatively prime to $m$ Let the residue classes be:
(36) $a + r_1, a + r_2, \dots, a + r_{\varphi}$ $(\varphi = \varphi(m))$
with $1 \le r_1 < r_2 < \dots < r_{\varphi} \le m$ is relatively prime to $m$. We then extract the following sub-scheme from (35).
(37)
$a + r_1\qquad \qquad \qquad \qquad a + r_2, \dots, \dots, \dots, a + r_{\varphi}$
$a + m + r_1\qquad \qquad \qquad a + m + r_2, \dots, \dots, \dots, a + m + r_{\varphi}$
$\vdots$
$a+(g-1)m + r_1\qquad a+(g-1)m + r_2, \dots, \dots, \dots, a+(g-1)m + r_{\varphi}$
All numbers in (37) are relatively prime to $m$. Now consider any column of (37).
(38) $a + \gamma m + r_i$; $\gamma = 0, 1, \dots, g-1$; $i \in \{ 1, \dots, \varphi \}$
Because of $(m,n)=1$ a natural number $v_i$ find that:
(39) $a + r_i + v_in \equiv 0 \pmod m$
is fulfilled. Then we look at the consecutive numbers:
(40) $\frac{a + r_i + v_i n}{m} + \gamma$
Among these numbers, there is always at least one that is relatively prime to $n$. Therefore, in each column of (37) there is at least one number that is relatively prime to $mn$. This gives
(41) $g(mn) \le mg(n) - \varphi(m) + 1$
Because of the symmetry in $m$ and $n$, Lemma 4 is proved. If $m$ is equal to a prime number $p$, then we get
(42) $g(pn) \le pg(n) - p + 2$
III We now want to estimate the function $p$ for small values of $k$. We start with
Lemma 5: If $(n,6)=1$; $1 < k \le 11$; Then $g < 2k$
Proof: According to the prerequisite $p_1 \ge 5$. For $k=2,3,4$ is from the numbers $a + 1, a + 2, \dots, a + k + 1$ at most one by $p_1,$ or $p_2, \dots,$ or $p_k$ divisible.
So we have for $1 < k \le 4$
(43) $k+1 \le g \le k+1$, i.e. $g = k+1 < 2k$
So that: $5 \le k \le 11$. We have $p_3 \ge 11$ ; $p_4 \ge 13$; $p_5 \ge 17$; $\dots$ so
(44) $p_{k-2} > 2k$ for $k = 5, \dots 11$
Now consider a sequence of length $2k-1$:
(45) $a+1, a+2, \dots, a + 2k-1$,
then at most one of these numbers is $p_k$ or $p_{k-1}$ or $p_{k-2}$ is divisible. Were $g-1 \ge 2k - 1$, then we could choose the sequence (45) such that of these numbers at least $2k-4$ not to $p_1 p_2 \dots p_{k-3}$are relatively prime. Since none of the prime numbers $p_3 \dots p_{k-3}$ can be contained in more than two of the numbers (45), at least 6 of these numbers must not be $p_1 p_2$ be relatively prime. For $k\le 7$ at most two of the numbers are divided by $p_2$ divisible; then follows $2k-1 \ge 16$, thus a contradiction to $k \le 7$. For $k=8, 9, 10, 11$ applies instead of (44)
(46) $p_{k-3} > 2k$
Of the numbers (45) at least $2k-5$ not to $p_1 \dots p_{k-4}$ At least 7 of these numbers do not have to be $p_1 p_2$ be relatively prime, at least 4 must be divided by $p_1$ be divisible. This gives $p_1 = 5$; $k \ge 9$. For $k=9, 10, 11$ is
(47) $p_{k-4} \ge 2k-1$
Of the numbers (45) at least $2k-6$ not to $p_1 \dots p_{k-5}$ At least 8 are not to $p_1 p_2$ coprime, at least 5 must go through $p_1 = 5$ divisible. Only the following case remains:
(48) $k=11$; $a+1 \equiv 0 \pmod 5$
none of the numbers $a + \gamma + v\times 5$ $(\gamma = 2, 3, 4, 5$; $v = 0, 1, 2, 3)$ is too $p_2 \dots p_{11}$ Exactly 3 of these numbers must be divided by $p_2 = 7$ be divisible by ; of the remaining 13 numbers, one each is $p_{11}$ or $p_{10}$ or $p_9, \dots $ or $p_6 (\ge 19)$ So 7 numbers must be divided by $p_3, p_4, p_5$ be divisible. This provides $p_3 \ge 11$ a contradiction. This completely proves the Lemma 5.
Theorem 1: For $1 < k \le 12$, it follows that $g\le k^2$
Proof: Assume $(n,6)=1$ According to Lemma 5, for $1 < k \le 11$
(49) $g \le 2k - 1 < k^2$
For $k=12, p_1 \ge 7$ we receive directly
(50) $\sum\limits_1^{12} \frac{1}{p_K} < 1 - \frac{1}{3}$
which according to Lemma 2 leads to
(51) $g \le 34 < k^2$
The case $k=12, p_1 = 5$ leads according to lemmas 4 and 5 to
(52) $g \le 5(2\times 11 - 1) - 3 = 102 < k^2$
Be now $(n,6)=2$. Lemma 4 leads to
(53) $g \le 2g(p_2 \dots p_k)$
so for $k=2$ to $g \le 4 = k^2$ and for $3 \le k \le 12$ according to (49) to
(54) $g \le 2(2k-3) = 4k-6 < k^2$
Let $(n,6)=3$. One can immediately see that for $k=2$ the equation:
(55) $g=3$ $(<k^2)$
applies; for $3 \le k \le 12$ is according to (49) and Lemma 4
(56) $g \le 3(2k-3)-1 = 6k - 10 < k^2$
Finally, $(n,6)=6$, i.e. $p_1 = 2, p_2 = 3$ According to (53) $k=2$ the equation $g=2^2$ fulfilled; for $k=3$ is according to (55) immediately $g \le 2\times 3 < 3^2$ is evident. For $4 \le k \le 13$ we obtain from (56), with $k-1$ instead of $k$,
(57) $g \le 12k -32 \le k^2$ for $k = 4, 8, 9, 10, 11, 12, 13$
We therefore still have to prove the theorem in the cases
(58) $k = 5,6,7$; $p_1 = 2, p_2 = 3$
where according to (53) it is sufficient to show that
(59) $g(p_3 \dots p_k) \le \frac{k^2}{2}$
is fulfilled. According to the fourth proposition,
(60) $g(p_3 \dots p_k) \le 3g(p_3 \dots p_k) - 1$
There $p_3 \ge 5$ must be is for $k=5,6$ also $g(p_3 \dots p_k) = k-1$ what to
(61) $g \le 2 \times 3(k-1) - 2 = 6k - 8 < k^2$
Finally, for k = 7 we have the estimates
(62) $g(p_3 \dots p_7) \le 7 = k$; $g \le 6\times 7 - 2 = 40 < k^2$
This proves Theorem 1.
IV. In this section we want to obtain more general results. We start with
Theorem 2: There are $q_1, q_2, \dots$ the prime numbers ordered by size; $n=p_1 \dots p_k$ with $p_1 < \dots < p_k$ given such that $p_1 \ge q_{l + 1}, 1 < k \le l^e$ is valid. Then $g \le k^2$
Proof: From B. Rosser [4]:
(Note: B. Rosser showed that the $n$th prime is greater than $n \log n$: link, Pierre Dusart improved on this result in 1999: link)
(63) $\sum\limits_{v=1}^m \frac{1}{q_v} = \log \log m + B_m$, $B_m > B_{m+1}$ $(m \ge 2)$;
for $m=1$ of course applies
(64) $\sum\limits_{v=1}^1 \frac{1}{q_v} = \frac{1}{2}$.
For $l \ge 1$ we get, with $q_{l+1} = p_1 < \dots < p_k$,
(65) $\sum\limits_1^k \frac{1}{p_K} \le \sum\limits_{v=l+1}^{l+k} \frac{1}{q_v} = \log \frac{\log) l + k)}{\log l} - \sum\limits_{\gamma = l}^{l+k-1} (B_{\gamma} - B_{\gamma + 1}),$
According to (63)
(66) $B_{\gamma} - B_{\gamma + 1} = \log \log (\gamma + 1) - \log \log \gamma - \frac{1}{q_{\gamma + 1}}$.
According to Taylor’s theorem,
(67) $\log \log(\gamma + 1) = \log \log \gamma + \frac{1}{\gamma \log \gamma} - \frac{1}{2} \frac{1 + \log(\gamma + \vartheta_{\gamma})}{(\gamma + \vartheta_{\gamma})^2 {\log}^2 (\gamma + \vartheta_{\gamma}) }$
with a certain $\vartheta_{\gamma}$, the $0 < \vartheta_{\gamma} < 1$ is enough. This means
(68) $\sum\limits_1^k \frac{1}{p_K} \le \log \frac{\log(l + k)}{\log l} - \sum\limits_{\gamma = l}^{l+k-1} \left( \frac{1}{\gamma \log \gamma} - \frac{1}{q_{\gamma + 1}} - \frac{1}{2} \frac{1 + \log \gamma}{{\gamma}^2 {\log}^2 \gamma} \right)$
Note that according to B. Rosser [4]
(69) $q_{\gamma + 1} > (\gamma + 1)\log(\gamma + 1)$
is fulfilled, then (68) becomes
(70) $\sum\limits_1^k \frac{1}{p_K} < \log \frac{\log(l+k)}{\log l} - \frac{1}{l \log l} + \frac{1}{(l + k)\log(l+k)} + \frac{1}{2} \sum\limits_l^{l+k-1} \frac{1 + \log \gamma}{{\gamma}^2 {\log}^2 \gamma}$,
because still
(71) $\sum\limits_{\gamma = 1}^{l+k-1} \frac{1 + \log \gamma}{{\gamma}^2 {\log}^2 l} \le \frac{1 + \log l}{l^2 {\log}^2 l} + \int_l^{l+k} \frac{1 + \log x}{x^2 {\log}^2 x}{d}x = \frac{1}{l \log l} \left(1 + \frac{1}{l} + \frac{1}{l \log l} + \frac{1}{l \log l} \right) - \frac{1}{(l+k)\log(l + k)}$
is correct, (70) also provides the estimate
(72) $\sum\limits_{1}^{k} \frac{1}{p_K} < \log \frac{\log (l + k)}{\log l} + \frac{1}{2(l+k)\log(l+k)} - \frac{1}{2l\log l}\left(1 - \frac{1}{l} - \frac{1}{l \log l}\right) < \log\left( \frac{\log k}{\log l} + \frac{l}{k \log l} \right) + \frac{1}{2(l+k)\log(l + k)} - \frac{1}{2l\log l}\left( 1 - \frac{1}{l} - \frac{1}{l \log l} \right)$.
According to Theorem 1 we can $k \ge 13$; $l \ge 3$ presuppose. If first
(73) $13 \le k \le l^{7/3} - l$, so $l \ge 4$
then we have
(74) $\frac{\log(l+k)}{\log l} \le 2,334$; $\sum\limits_1^k \frac{1}{p_K} < \log 2,334 + \frac{1}{2(l+k)\log l} - \frac{1}{2l \log l}\left( 1 - \frac{1}{l} - \frac{1}{l \log l} \right) < 0.85 + \frac{1}{4^2 \log 4} < 0.9 = 1 - \frac{1}{10}$,
which according to Proposition 2 leads to $g < 10(k-1) +2 < 10k < k^2$ leads. Now to:
(75) $l^{7/3} - l < k \le l^{7/3}$, i.e. $l \ge 4$;
According to (72) it follows that $\log \frac{\log(l + l^{7/3})}{\log l} < \log \left( \frac{7}{3} + \frac{1}{l^{4/3}\log l} \right) < \log \frac{7}{3} + \frac{3}{7l^{4/3}\log l}$ also:
(76) $\sum\limits_1^k \frac{1}{p_K} < \log \frac{7}{3} + \frac{3}{7l^{4/3}\log l} + \frac{3}{7l^{7/3}\times 2\log l} - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} - \frac{6}{7l^{1/3}} - \frac{3}{7l^{4/3}} \right) < 0.9$,
what again to $g < 10k < k^2$ now
(77) $l^{7/3} < k \le l^{5/2} -l$ i.e. $\log \frac{\log(l+k)}{\log l} \le \log \frac{5}{2} < 0.92$
In this case we see from (72)
(78) $\sum\limits_1^k \frac{1}{p_K} < 0.92 + \frac{3}{14l^{7/3}\log l} - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} \right) = 0.92 - \frac{1}{2l \log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} - \frac{3}{7l^{4/3}} \right) < 0.92 - \frac{7}{60l \log l} < 1 - \frac{1}{12.5}$
which according to Proposition 2 immediately
(79) $g < 12.5k < k^2$
delivers. For
(80) $\text{max} \{ l^{7/3}; l^{5/2}-1 \} < k < l^{5/2}$
becomes
(81) $\sum \frac{1}{p_K} < 0.92 + \frac{2}{5l^{3/2}\log l} + \frac{1}{5l^{5/2}\log l} - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} \right) = 0.92 - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} - \frac{2}{5l^{3/2}} - \frac{4}{5l^{1/2}} \right) < 0.92 + \frac{0.1809}{2l \log l} < 0.95$
for $k \ge 19$ according to Lemma 3, the inequality $g \le k^2$ fulfilled. For $k \le 18$ is $l^{7/3}< 18$ only fulfilled for $l \le 3$
Then it follows from (80)
(82) $12 < \text{max} \{ 9 \sqrt[3]{3}; 9\sqrt{3} - 3 \} < k < 9\sqrt{13} < 16$
In the cases $l=3, k=13, 14, 15$ we can estimate directly:
(83) $g < 5k < k^2$
We can assume for the rest of the proof
(84) $l^{5/2} < k \le l^e$
According to (72)
(85) $\sum \frac{1}{p_K}$
$ < \log \left( e + \frac{1}{ll^{e-1}\log l} \right) + \frac{1}{5l^{5/2}\log l} - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} \right)$ $< 1 - \frac{1}{2l \log l}$ $ \left( 1 - \frac{1}{l} - \frac{1}{l \log l} - \frac{2}{el^{e-2}} - \frac{2}{5l^{3/2}} \right)$
For $l \ge 5$ is $\frac{1}{l} + \frac{1}{l \log l} + \frac{2}{el^{e-2}} + \frac{2}{5l^{3/2}} < \frac{1}{5} + \frac{1}{8} + \frac{2}{2.7 \times 5^{3/2}} + \frac{2}{25 \times \sqrt{5}} < 0.62$ i.e. we have the estimates
(86) $\sum \frac{1}{p_K} < 1 - \frac{0.38}{2l \log l}$; $g < \frac{l \log l}{0.19} k \le k^2$
because $\frac{\log l}{l} \le \frac{\log 5}{5} < 0.322 < 0.19l^{1/2}$ is fulfilled. For $l = 3,4$ we get from (84) and $p_1 \ge q_{l + 1}$
(87) $p_1 = 7$ or $11$; $16 \le k \le 19$ or $33 \le k \le 53$.
For $l=3$, it follows:
(88) $\sum\limits_1^{19} \frac{1}{p_K} \le \frac{1}{7} + \frac{1}{11} + \dots + \frac{1}{79} < 0.8$; $g < 5k < k^2$
(88) $\sum\limits_1^{19} \frac{1}{p_K} \le \frac{1}{7} + \frac{1}{11} + \dots + \frac{1}{79} < 0.8$; $g < 5k < k^2$
For $l=4$, it follows:
(89) $\sum\limits_1^{53} \frac{1}{p_K} \le \frac{1}{11} + \frac{1}{13} + \dots + \frac{1}{269} < 1 - \frac{1}{30}$; $g < 30k < k^2$
This confirms the second theorem.
Theorem 3: Let $n = p_1 \dots p_k$, $1 < k^{0.6} < p_1 < \dots < p_k$ Then $g(p_1 \dots p_k) \le k^2$.
Proof: We write
(90) $\pi(k^{0.6}) = l$
and know from Theorem 2 that $k \le l^{e}$ the assertion of the above theorem follows. Therefore we now ask the question: For which $l$ is:
(91) $l < \pi(l^{0.6e})$
fulfilled? Be first, with $0.6e = \alpha (1.63 < \alpha < 1.632)$
(92) $l^{\alpha} \ge e^{100} $
Then, according to B. Rosser [4]:
(93) $\pi(l^{\alpha}) \ge \frac{l^{\alpha}}{\alpha \log l + 2}$
We get
(94) $l < \frac{l^{\alpha}}{\alpha \log l + 2} \le \pi(l^{\alpha})$
Because $\alpha l \log l + 2l < l^{\alpha}$, $\frac{\alpha}{a-1} \frac{\log l^{\alpha-1}}{l^{\alpha-1}} + \frac{2}{l^{\alpha - 1}} \le \frac{1.632}{0.63} \times \frac{10}{e^{10}} + \frac{2}{e^{10}} < 1$ fulfilled is. Now:
(95) $17 \le l^{\alpha} < e^{100}$
Then we have, according to B. ROSSER [4]
(96) $\pi(l^{\alpha}) \ge \frac{l^{\alpha}}{\alpha \log l} > l$; $\alpha \log l < l^{\alpha -1}$
because the function $\frac{\log x}{x}$ for $1 < x$ is positive and at $x = e$ the maximum $\frac{1}{e}$
Because the above adjustment is equivalent to:
(97) $\frac{\alpha}{\alpha - 1} \times \frac{\log l^{\alpha - 1}}{l^{\alpha - 1}} \le \frac{\alpha}{\alpha - 1} \times \frac{1}{e} \le \frac{0.6e}{0.63} \times \frac{1}{e} = \frac{60}{63} < 1$
Is now
(98) $l^{1.63} < l^{\alpha} < 17$; $l < 6$
then we investigate for which $l \le 5$ according to (91)
(99) $l < \pi(l^{1.6})$
applies. It is
(100) $5^{1.6} > 13$; $\pi(13) = 6$
For $l=2,3,4$ we carry out the proof directly with estimation of $\sum\limits_1^{k} \frac{1}{p_K}$ and Application of Proposition 2. Because of Theorem 1 we can $k \ge 13$; $l = \pi(k^{0.6}) \ge \pi(\sqrt{13}) \ge \pi(3) = 2$ This proves Theorem 3.
Theorem 4: For all $n = p_1 \dots p_k$, $g(n) \le 2^k = \sum\limits_{d|n} 1$. For $k \ge e^{50}$ is $g(n) < 2^{\sqrt{k}}$.
Proof: For $k=1,2$ the statement is correct. So let $k \ge 3$. Furthermore,
(101) $p_1 < \dots < p_i \le (k-i)^{0.6} < p_{i+1} < \dots < p_k$.
From Lemma 4, it follows that:
(102) $g(n) \le p_1 \dots p_i g(p_{i+1} \dots p_k) - (p_1 - 1) \dots (p_i - 1) + 1$
From Theorem 3 we get
(103) $g(n) \le p_1 \dots p_i(k-i)^2$
It is known
(104) $p_1 \dots p_i < 4^{(k-i)0.6}$
Therefore follows
(105) $g(n) < 2^{2(k-i)0.6} \times (k-i)^2 \le 2^k$
if
(106) $2^{2(k-i)0.6} \times (k-i)^2 \le 2^{2k^{0.6}} \times k^2 \le 2^k$; $k^2 \le 2^{k^{0.6}(k^{0.4}-2)}$; $2\log k \le k^{0.6} (K^{0.4} - 2) \log 2$; $\frac{\log k^{0.6}}{k^{0.6}}\le 0.3 \times (k^{0.4} - 2) \log 2$
applies. Because $\frac{\log k^{0.6}}{k^{0.6}} \le \frac{1}{e} < 0.368 < 0.3 \times 1.8 \log 2$ is correct, it follows that $k^{0.4} - 2 \ge 1.8$; $k \ge 29$ immediately the claim. For $3 \le k \le 12$ the assertion of the theorem is also fulfilled, namely for $k=4, \dots, 12$ according to Theorem 1, for $k=3$ because of $g(p_1 p_2 p_3) \le 6$. Now $13 \le k \le 28$ provided. We get according to (101)
(107) $p_i \le 28^{0.6} < 10$
With this we have
(108) $p_1 \dots p_i \le 2 \times 3 \times 5 \times 7 = 210$; $g(n) < 210k^2$
For $k \ge 18$ is:
(109) $210k^2 \le 2^k$
Because $\frac{\log 210}{k} + \frac{2 \log k}{k} < \frac{5.35 + 5.8}{18} < \log 2$ is fulfilled. For $13 \le k \le 17$, it follows:
(110) $p_i \le 17^{0.6} < 7$; $p_1 \dots p_i \le 30$; $g(n) < 30k^2 \le 2^k$,
because $\frac{\log 30 + 2 \log k}{k} < \frac{3.41 + 5.14}{13} > \log 2$ applies:
For $k \ge e^{50}$ we write, similar to the proof of Theorem 3:
(111) $l = \pi(k^{0.48})$; $l < \pi(l^{0.48e})$; $\alpha = 0.48e$ $(1.3 < \alpha < 1.31)$
According to B. Rosser [4]
(112) $\pi(l^{\alpha}) \ge \frac{l^{\alpha}}{\alpha \log l + 2}$; $\frac{\alpha}{\alpha - 1} \times \frac{\log l^{\alpha - 1}}{l^{\alpha - 1}} + \frac{2}{l^{\alpha - 1}} < \frac{1.31}{0.3} \times \frac{\log l^{\alpha - 1}}{l^{\alpha - 1}} + \frac{2}{l^{\alpha - 1}}$; $k^{0.48} \ge e^{24}$; $l \ge \pi(e^{24}) \ge \frac{e^{24}}{26}$; $l^{\alpha - 1} > l^{0.3} > \left( \frac{e^{24}}{26} \right)^{0.3} > e^{20-0.3} = e^6 > 400$; $\frac{131}{30} \times \frac{6}{400} + \frac{2}{400} < 1$
We therefore have the following result:
(113) Out of $k \ge e^{50}$; $k^{0.48}< p_1 < \dots < p_k$, it follows that $g(p_1 \dots p_k) \le k^2$
Let $p_1 < \dots < p_j \le (k-j)^{0.48} < p_{j+1} < \dots < p_k$ so it follows that:
$g \le p_1 \dots p_j \times (k-j)^2 < 2k^{0.48} \times k^2 \le 2^{\sqrt{k}}$
There $2k^{0.48} \log 2 + 2\log k \le \sqrt{k}\log 2$; $2\log k \le k^{0.48}(k^{0.02}-2) \log 2$; $k^{0.02} \ge e > 2.7$; $2 \log k \le 0.7 \times k^{0.48} \log 2$; $\frac{1}{0.24} \times \frac{\log k^{0.48}}{k^{0.48}} < 0.7 \log 2$; $\frac{1}{0.24} \times \frac{24}{e^{24}} < 0.7 \log 2$ is valid. This proves Theorem 4.
As a simple consequence of the last theorem we get:
(114) Out of $k \ge 18$, it follows that $n > g^4$
Proof: It is
(115) $n \ge 2 \times 3 \times \dots \times 31 \times 37^{k - 11} > 2^{42}\times 37^{k-11} > 2^{5k-18} \ge 2^{4k} \ge g^4$
If we imagine the divisors $d$ of $n$ arranged according to size, then $2^{k-1}$ this divisor is greater than $\sqrt{n} > g^2$ if $k \ge 18$ is fulfilled. For each divisor $d$ from $n$ with $d > g^2$ is either according to (16):
(116) $0 < \Theta_d - \vartheta_d = \frac{g-1}{d} < \frac{g-1}{g^2} < \frac{1}{g}$
or according to (17) and (18)
(117) $\Theta_d - \vartheta_d = \frac{g-1}{d} - 1$; $0 < 1 + \Theta_d - \vartheta_d < \frac{g-1}{g^2} < \frac{1}{g}$
The estimates in this work can be improved with greater computational effort, in particular it can be shown that $1 < k^{1/2} < p_1 < \dots < p_k$ also $g < k^{1.7}$ it follows for $k > 659^2$ This bound for k can probably be lowered by further calculations.
No comments:
Post a Comment