Skip to main content
final ? major round
Source Link
Gerhard Paseman
  • 13.2k
  • 3
  • 34
  • 66

$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(n)(1/2)^{2e(\alpha_n + \log(z))}$$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(1/2)^{2e(\alpha_n + \log(z))}$.

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt SB/(P-T)$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n}$$n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n)$.

$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(n)(1/2)^{2e(\alpha_n + \log(z))}$.

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt SB/(P-T)$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n}$.

$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(1/2)^{2e(\alpha_n + \log(z))}$.

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt SB/(P-T)$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n)$.

second major round
Source Link
Gerhard Paseman
  • 13.2k
  • 3
  • 34
  • 66

Proof sketch: For an interval $I$ having $l$ consecutive integers, and for a positive integer $t$ let $J_t$ be the number of (integer) multiples of $t$ inside $I$. Then $\text{ceil}{l/t} \ge J_t \ge \text{floor}{l/t}$$\text{ceil}(l/t) \ge J_t \ge \text{floor}(l/t)$. So the count of numbers in $I$ not coprime with $m$ is at most $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Now if $l \ge rn$, then the right hand side of the inequality is at least $l$, meaning at least 1 number in $I$ is coprime with $m$. End of Proof sketch.

Improvement? (Paseman): For sufficiently large $n$, $j(m) \le O^*(n^{(2 +2e \log(\log(p_n))})$$j(m) \le O^*(n^{(2 +2e \log(\log(p_n)))})$.

Stevens starts out using (equivalents of) $I$, $l$, and $J_t$ as above. He uses inclusion-exclusion to compute $L$, the number of integers coprime to $m$ in the interval $I$. For ease, I assume $m$ is squarefree, and here $\mu(t)$ is the M$\"{o}$biusMoebius function, so $\mu(t)$ is (-1) to the power of the number of distinct prime divisors of (squarefree) $t$. Thus,

Now Stevens defines $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$. As in the question above, this gives $P = \prod_{1 \le i \le n}(1 - 1/m_i}$$P = \prod_{1 \le i \le n}(1 - 1/m_i)$ (Recall that the distinct prime factors factors of $m$ are the $m_i$.) Then $T = P - T_s$, so

If we replace $(s+1)!$ with the smaller $((s+1)/e)^{s+1}$ and choose $s$ so that $s+1 \gt 2eh(n)$, then $T' = e^h(n)2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$$T' = e^{h(n)}2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$.

Also $P = \prod_{1 \le i \le n}(1 - 1/m_i} \gt \prod_{1 \le i \le n}(1 - 1/p_i} \gt 1/(\beta_n\log(p_n))$$P = \prod_{1 \le i \le n}(1 - 1/m_i) \gt \prod_{1 \le i \le n}(1 - 1/p_i) \gt 1/(\beta_n\log(p_n))$, so let $P' = 1/(\beta_n\log(p_n))$. Again the valid range of $n$ depends on the choice of $\beta_n$. For now choose them (say, $\beta_n = 3$) so that $P > P'$. (Stevens chose $1/n$ for $P'$.) Then $P- T \gt P' -T'$, and $SB' > SB$. We just need to find odd $s > 2eh(n) -1$ and ensure that $P' > T'$, and then combine everything. Stevens's form is similar to what is below; I will use my versions of $P'$ and $T'$. Writing $z$ for $\log(p_n)$,

$P' -T' = (\beta_n z)^{-1} - (e/2^{2e})^{\alpha_n} z^{-2e\log(2) + 1} $

$ = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$$P' -T' = (\beta_n z)^{-1} - (e/2^{2e})^{\alpha_n} z^{-2e\log(2) + 1} = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt \frac{SB}{P-T}$$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt SB/(P-T)$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n}$.

Now as to the choice of $\alpha_n$ and $\beta_n$. They were chosen generously: Mertens showed that $\sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + \delta$, where $B$ is a constant close to 0.26 and $\delta$ is an error bounded in size by a sum of two terms, the largest of which is $4/\log(p_n +1)$. So using Merten's estimate, $p_n + 1$ should be bigger than (some number not much larger than) $e^8$. Similarly, Mertens has an estimate on $\prod_{1 \le i \le n} (1 - 1/p_i)$, which is $e^{-(\gamma + \delta)}/\log(p_n)$, where $e^-\gamma$$e^{-\gamma}$ is close to 1/1.78 and $\delta$ is bounded by a sum of three terms, the largest of which is again $4/\log(p_n+1)$, again requiring that $p_n + 1$ be bigger than (something close to) $e^8$. However, computations seem to show that the constants chosen seem to allow the requiredrquired estimates to hold for $n \gt 30$ and some $n$ smaller than The 30. The major block is on $n \gt 2s \gt 2eh(n) - 1$.

Proof sketch: For an interval $I$ having $l$ consecutive integers, and for a positive integer $t$ let $J_t$ be the number of (integer) multiples of $t$ inside $I$. Then $\text{ceil}{l/t} \ge J_t \ge \text{floor}{l/t}$. So the count of numbers in $I$ not coprime with $m$ is at most $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Now if $l \ge rn$, then the right hand side of the inequality is at least $l$, meaning at least 1 number in $I$ is coprime with $m$. End of Proof sketch.

Improvement? (Paseman): For sufficiently large $n$, $j(m) \le O^*(n^{(2 +2e \log(\log(p_n))})$.

Stevens starts out using (equivalents of) $I$, $l$, and $J_t$ as above. He uses inclusion-exclusion to compute $L$, the number of integers coprime to $m$ in the interval $I$. For ease, I assume $m$ is squarefree, and here $\mu(t)$ is the M$\"{o}$bius function, so $\mu(t)$ is (-1) to the power of the number of distinct prime divisors of (squarefree) $t$. Thus,

Now Stevens defines $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$. As above, this gives $P = \prod_{1 \le i \le n}(1 - 1/m_i}$ (Recall that the distinct prime factors of $m$ are the $m_i$.) Then $T = P - T_s$, so

If we replace $(s+1)!$ with the smaller $((s+1)/e)^{s+1}$ and choose $s$ so that $s+1 \gt 2eh(n)$, then $T' = e^h(n)2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$.

Also $P = \prod_{1 \le i \le n}(1 - 1/m_i} \gt \prod_{1 \le i \le n}(1 - 1/p_i} \gt 1/(\beta_n\log(p_n))$, so let $P' = 1/(\beta_n\log(p_n))$. Again the valid range of $n$ depends on the choice of $\beta_n$. For now choose them (say, $\beta_n = 3$) so that $P > P'$. (Stevens chose $1/n$ for $P'$.) Then $P- T \gt P' -T'$, and $SB' > SB$. We just need to find odd $s > 2eh(n) -1$ and ensure that $P' > T'$, and then combine everything. Stevens's form is similar to what is below; I will use my versions of $P'$ and $T'$. Writing $z$ for $\log(p_n)$,

$P' -T' = (\beta_n z)^{-1} - (e/2^{2e})^{\alpha_n} z^{-2e\log(2) + 1} $

$ = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt \frac{SB}{P-T}$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n}$.

Now as to the choice of $\alpha_n$ and $\beta_n$. They were chosen generously: Mertens showed that $\sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + \delta$, where $B$ is a constant close to 0.26 and $\delta$ is an error bounded in size by a sum of two terms, the largest of which is $4/\log(p_n +1)$. So using Merten's estimate, $p_n + 1$ should be bigger than (some number not much larger than) $e^8$. Similarly, Mertens has an estimate on $\prod_{1 \le i \le n} (1 - 1/p_i)$, which is $e^{-(\gamma + \delta)}/\log(p_n)$, where $e^-\gamma$ is close to 1/1.78 and $\delta$ is bounded by a sum of three terms, the largest of which is again $4/\log(p_n+1)$, again requiring that $p_n + 1$ be bigger than (something close to) $e^8$. However, computations seem to show that the constants chosen seem to allow the required estimates to hold for $n \gt 30$ and some $n$ smaller than The major block is on $n \gt 2s \gt 2eh(n) - 1$.

Proof sketch: For an interval $I$ having $l$ consecutive integers, and for a positive integer $t$ let $J_t$ be the number of (integer) multiples of $t$ inside $I$. Then $\text{ceil}(l/t) \ge J_t \ge \text{floor}(l/t)$. So the count of numbers in $I$ not coprime with $m$ is at most $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Now if $l \ge rn$, then the right hand side of the inequality is at least $l$, meaning at least 1 number in $I$ is coprime with $m$. End of Proof sketch.

Improvement? (Paseman): For sufficiently large $n$, $j(m) \le O^*(n^{(2 +2e \log(\log(p_n)))})$.

Stevens starts out using (equivalents of) $I$, $l$, and $J_t$ as above. He uses inclusion-exclusion to compute $L$, the number of integers coprime to $m$ in the interval $I$. For ease, I assume $m$ is squarefree, and here $\mu(t)$ is the Moebius function, so $\mu(t)$ is (-1) to the power of the number of distinct prime divisors of (squarefree) $t$. Thus,

Now Stevens defines $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$. As in the question above, this gives $P = \prod_{1 \le i \le n}(1 - 1/m_i)$ (Recall that the distinct prime factors of $m$ are the $m_i$.) Then $T = P - T_s$, so

If we replace $(s+1)!$ with the smaller $((s+1)/e)^{s+1}$ and choose $s$ so that $s+1 \gt 2eh(n)$, then $T' = e^{h(n)}2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$.

Also $P = \prod_{1 \le i \le n}(1 - 1/m_i) \gt \prod_{1 \le i \le n}(1 - 1/p_i) \gt 1/(\beta_n\log(p_n))$, so let $P' = 1/(\beta_n\log(p_n))$. Again the valid range of $n$ depends on the choice of $\beta_n$. For now choose them (say, $\beta_n = 3$) so that $P > P'$. (Stevens chose $1/n$ for $P'$.) Then $P- T \gt P' -T'$, and $SB' > SB$. We just need to find odd $s > 2eh(n) -1$ and ensure that $P' > T'$, and then combine everything. Stevens's form is similar to what is below; I will use my versions of $P'$ and $T'$. Writing $z$ for $\log(p_n)$,

$P' -T' = (\beta_n z)^{-1} - (e/2^{2e})^{\alpha_n} z^{-2e\log(2) + 1} = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt SB/(P-T)$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n}$.

Now as to the choice of $\alpha_n$ and $\beta_n$. They were chosen generously: Mertens showed that $\sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + \delta$, where $B$ is a constant close to 0.26 and $\delta$ is an error bounded in size by a sum of two terms, the largest of which is $4/\log(p_n +1)$. So using Merten's estimate, $p_n + 1$ should be bigger than (some number not much larger than) $e^8$. Similarly, Mertens has an estimate on $\prod_{1 \le i \le n} (1 - 1/p_i)$, which is $e^{-(\gamma + \delta)}/\log(p_n)$, where $e^{-\gamma}$ is close to 1/1.78 and $\delta$ is bounded by a sum of three terms, the largest of which is again $4/\log(p_n+1)$, again requiring that $p_n + 1$ be bigger than (something close to) $e^8$. However, computations seem to show that the constants chosen seem to allow the rquired estimates to hold for $n \gt 30$ and some $n$ smaller than 30. The major block is on $n \gt 2s \gt 2eh(n) - 1$.

first major round
Source Link
Gerhard Paseman
  • 13.2k
  • 3
  • 34
  • 66

Aaron Meyerowitz was kind enough not only to do some computations for me but also to show me a better way to compute some quantities I was interested in to solve the problem. Inspired by his efforts, I convinced myself that a sequence of error terms I was using satisfied $E_{i+1}(x) \le 2E_i(x)$, which then led me to improve Westzynthius's result to $Q*2^g(n)$$Q*2^{g(n)}$ where $g(n)$ was $n/2 + O(log(n))$$n/2 + O(\log(n))$.

$m$ will be a positive integer, and I prefer $m \gt 1$. Jacobsthal's function $j(m)$ gives the smallest positive integer $j$ such that, for any interval $I$ of $j$ integers of the form $[a+1,\ldots,a+j]$, it is guaranteed that one of the integers in $I$ is coprime to $m$, i.e. $\gcd(m,a+i)=1$ for at least one $a+i \in I$. Let $\text{rad}(m) = \prod_{p \text{prime}, p \mid m} p$$\text{rad}(m) = \prod_{p \text{ prime,} p \mid m} p$ be the largest squarefree factor of $m$; $j(\text{rad}(m))=j(m)$ and also $j(m)$ is the size of the largest gap between consecutive members of the set of integers which are relatively prime to $m$. In my problem above, I wanted nice upper bounds on $j(P_n)$, or Jacobsthal's function evaluated at the $n$th primorial.

Proof sketch: For an interval $I$ having $l$ consecutive integers, and for a positive integer $t$ let $J_t$ be the number of (integer) multiples of $t$ inside $I$. Then $\ceil{l/t} \ge J_t \ge \floor{l/t}$$\text{ceil}{l/t} \ge J_t \ge \text{floor}{l/t}$. So the count of numbers in $I$ not coprime with $m$ is at most $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Now if $l \ge rn$, then the right hand side of the inequality is at least $l$, meaning at least 1 number in $I$ is coprime with $m$. End of Proof sketch.

Theorem (Stevens) $j(m) < 2n^{(2 + 2e\log(n)}$$j(m) < 2n^{(2 + 2e\log(n))}$.

Improvement? (Paseman): For sufficiently large $n$, $j(m) = O^*(n^{(2 +2e \log(\log(p_n))})$$j(m) \le O^*(n^{(2 +2e \log(\log(p_n))})$.

The reasons for the $O^*$ will appear, as I will discuss Stevens's proof and the improvement together. In discussing the improvement, I will ask that $n \gt 30$.

Stevens starts out using (equivalents of) $I$, $l$, and $J_t$ as above. He uses inclusion-exclusion to compute $L$, the number of integers coprime to $m$ in the interval $I$. For ease, I assume $m$ is squarefree, and here $\mu(t)$ is the M"{o}M$\"{o}$bius function, so $\mu(t)$ is (-1) to the power of the number of distinct prime divisors of (squarefree) $t$. Thus,

$L \ge lT_s - SB $

Where , where $T_s = \sum_{0 \le i \le s} (-1)^i (\sum_{t \mid m , \nu(t) = i} 1/t)$. and $SB = \sum_{1 \le i \le s} \binom{n}{s}$

Let's do $SB$. Stevens's replacement is $n^s$; mine is $\binom{n+1)}{s}$$\binom{n+1}{s}$ times a small fudge factor, which will be strictly less than $n^s$ for $s \gt 2$ and $n$ sufficiently larger than $2s$. The small fudge factor is from dominating the sum by a geometric series with common ratio $\binom{n+1}{s-2} / \binom{n+1}{s}$. This gives $(1 + \frac{s(s-1)}{(n+2)(n+3 -2s)}$$1 + (s(s-1))/((n+2)(n+3-2s))$.

Now Stevens defines $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$. As above, this gives $P = \prod{1 \le i \le n}(1 - 1/m_i}$$P = \prod_{1 \le i \le n}(1 - 1/m_i}$ (Recall that the distinct prime factors of $m$ are the $m_i$.) Then $T = P - T_s$, so

$ i! \sum_{t \mid m , \nu(t) = i} 1/t \le (\sum_{1 \le j \le n} 1/m_j)^i \le h(n)^i$, so $T \lt \sum_{s \lt i \le n} \frac{(\sum_{1 \le j \le n} 1/m_j)^i}{i!}$$ (i!)\sum_{t \mid m , \nu(t) = i} 1/t \le (\sum_{1 \le j \le n} 1/m_j)^i \le h(n)^i$, so $T \lt \sum_{s \lt i } \frac{h(n)^i}{i!} \le e^{h(n)}\frac{h(n)^{s+1}}{(s+1)!}$$T \lt \sum_{s \lt i \le n} ((\sum_{1 \le j \le n} 1/m_j)^i)/(i!)$,

so $T \lt \sum_{s \lt i } (h(n)^i)/(i!) \le e^{h(n)}(h(n)^{s+1})/((s+1)!)$.

If we replace $(s+1)!$ with the smaller $((s+1)/e)^{s+1}$ and choose $s$ so that $s+1 \gt 2eh(n)$, then $T' = e^h(n)2^(-s-1) \gt e^{h(n)}\frac{h(n)^{s+1}}{(s+1)!} \gt T$$T' = e^h(n)2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$.

Also $P = \prod{1 \le i \le n}(1 - 1/m_i} \gt \prod{1 \le i \le n}(1 - 1/p_i} \gt 1/\beta_n\log(p_n)$$P = \prod_{1 \le i \le n}(1 - 1/m_i} \gt \prod_{1 \le i \le n}(1 - 1/p_i} \gt 1/(\beta_n\log(p_n))$, so let $P' = 1/\beta_n\log(p_n)$$P' = 1/(\beta_n\log(p_n))$. Again the valid range of $n$ depends on the choice of $\beta_n$. For now choose them (say, $\beta_n = 3$) so that $P > P'$.
  (Stevens chose $1/n$ for $P'$).) Then $P- T \gt P' -T'$, and $SB' > SB$. We just need to find odd $s > 2eh(n) -1$ and ensure that $P' > T'$, and then combine everything. Stevens's form is similar to what is below; I will use my versions of $P'$ and $T'$. Writing $z$ for $\log(p_n)$,

$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(n)(1/2)^(2e(\alpha_n + \log(z)))$$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(n)(1/2)^{2e(\alpha_n + \log(z))}$.

Now $(1/2)^2e\log(z) = (z)^{-2e\log(2)}$$(1/2)^{2e\log(z)} = z^{-2e\log(2)}$. So

 $ = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$ $ = z^{-1} ( (\beta_n)^{-1} - (e^{\alpha_n})^{-2e\log(2) + 1} z^{-2e\log(2) + 2} ) $ 

$ = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$

$ = z^{-1} ( (\beta_n)^{-1} - (e^{\alpha_n})^{-2e\log(2) + 1} z^{-2e\log(2) + 2} ) $

$ \binom{n+1}{s} ( 1 +\frac{s(s-1)}{(n+2)(n+3 -2s)}) ) \frac{z}{(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}} \gt /frac{SB}{P-T}$$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt \frac{SB}{P-T}$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume n > 30, $n > 30,$ the fudge factor is at most 18/11, and when \beta_n=3$\beta_n=3$ and \alpha_n = 0.75$\alpha_n = 0.75$, the denominator of of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since \log(\log(p_n)) is$\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n}$.

Now as to the choice of \alpha_n$\alpha_n$ and \beta_n$\beta_n$. They were chosen generously: Mertens showed that \sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + delta$, where $B$$\sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + \delta$, where $B$ is a constant close to 0.26 and delta$\delta$ is an error bounded in size by a sum of two terms, the largest of which is 4/log(p_n +1)$4/\log(p_n +1)$. So using Merten's estimate, p_n + 1$p_n + 1$ should be bigger than (some number not much larger than e^8) $e^8$. Similarly, Mertens has an estimate on \prod_{1 \le i \le n} (1 - 1/p_i)$\prod_{1 \le i \le n} (1 - 1/p_i)$, which is e^{-(\gamma + delta)}/\log(p_n)$e^{-(\gamma + \delta)}/\log(p_n)$, where e^-\gamma $e^-\gamma$ is close to 1/1.78 and delta$\delta$ is bounded by a sum of three terms, the largest of which is is again 4/log(p_n+1)$4/\log(p_n+1)$, again requiring that p_n + 1$p_n + 1$ be bigger than (something close to) e^8 $e^8$. However, computations seem to show that the constants chosen seem to allow the required estimates to hold for n >30$n \gt 30$ and some n$n$ smaller than THe The major block is on n > 2s > 2eh(n) - 1$n \gt 2s \gt 2eh(n) - 1$.

Aaron Meyerowitz was kind enough not only to do some computations for me but also to show me a better way to compute some quantities I was interested in to solve the problem. Inspired by his efforts, I convinced myself that a sequence of error terms I was using satisfied $E_{i+1}(x) \le 2E_i(x)$, which then led me to improve Westzynthius's result to $Q*2^g(n)$ where $g(n)$ was $n/2 + O(log(n))$.

$m$ will be a positive integer, and I prefer $m \gt 1$. Jacobsthal's function $j(m)$ gives the smallest positive integer $j$ such that, for any interval $I$ of $j$ integers of the form $[a+1,\ldots,a+j]$, it is guaranteed that one of the integers in $I$ is coprime to $m$, i.e. $\gcd(m,a+i)=1$ for at least one $a+i \in I$. Let $\text{rad}(m) = \prod_{p \text{prime}, p \mid m} p$ be the largest squarefree factor of $m$; $j(\text{rad}(m))=j(m)$ and also $j(m)$ is the size of the largest gap between consecutive members of the set of integers which are relatively prime to $m$. In my problem above, I wanted nice upper bounds on $j(P_n)$, or Jacobsthal's function evaluated at the $n$th primorial.

Proof sketch: For an interval $I$ having $l$ consecutive integers, and for a positive integer $t$ let $J_t$ be the number of (integer) multiples of $t$ inside $I$. Then $\ceil{l/t} \ge J_t \ge \floor{l/t}$. So the count of numbers in $I$ not coprime with $m$ is at most $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Now if $l \ge rn$, then the right hand side of the inequality is at least $l$, meaning at least 1 number in $I$ is coprime with $m$. End of Proof sketch.

Theorem (Stevens) $j(m) < 2n^{(2 + 2e\log(n)}$.

Improvement? (Paseman): For sufficiently large $n$, $j(m) = O^*(n^{(2 +2e \log(\log(p_n))})$.

The reasons for the $O^*$ will appear, as I will discuss Stevens's proof and the improvement together. In discussing the improvement, I will ask that $n \gt 30$

Stevens starts out using (equivalents of) $I$, $l$, and $J_t$ as above. He uses inclusion-exclusion to compute $L$, the number of integers coprime to $m$ in the interval $I$. For ease, I assume $m$ is squarefree, and here $\mu(t)$ is the M"{o}bius function, so $\mu(t)$ is (-1) to the power of the number of distinct prime divisors of (squarefree) $t$. Thus,

$L \ge lT_s - SB $

Where $T_s = \sum_{0 \le i \le s} (-1)^i (\sum_{t \mid m , \nu(t) = i} 1/t)$. and $SB = \sum_{1 \le i \le s} \binom{n}{s}$

Let's do $SB$. Stevens's replacement is $n^s$; mine is $\binom{n+1)}{s}$ times a small fudge factor, which will be strictly less than $n^s$ for $s \gt 2$ and $n$ sufficiently larger than $2s$. The small fudge factor is from dominating the sum by a geometric series with common ratio $\binom{n+1}{s-2} / \binom{n+1}{s}$. This gives $(1 + \frac{s(s-1)}{(n+2)(n+3 -2s)}$.

Now Stevens defines $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$. As above, this gives $P = \prod{1 \le i \le n}(1 - 1/m_i}$ (Recall that the distinct prime factors of $m$ are the $m_i$.) Then $T = P - T_s$, so

$ i! \sum_{t \mid m , \nu(t) = i} 1/t \le (\sum_{1 \le j \le n} 1/m_j)^i \le h(n)^i$, so $T \lt \sum_{s \lt i \le n} \frac{(\sum_{1 \le j \le n} 1/m_j)^i}{i!}$, so $T \lt \sum_{s \lt i } \frac{h(n)^i}{i!} \le e^{h(n)}\frac{h(n)^{s+1}}{(s+1)!}$.

If we replace $(s+1)!$ with the smaller $((s+1)/e)^{s+1}$ and choose $s$ so that $s+1 \gt 2eh(n)$, then $T' = e^h(n)2^(-s-1) \gt e^{h(n)}\frac{h(n)^{s+1}}{(s+1)!} \gt T$.

Also $P = \prod{1 \le i \le n}(1 - 1/m_i} \gt \prod{1 \le i \le n}(1 - 1/p_i} \gt 1/\beta_n\log(p_n)$, so let $P' = 1/\beta_n\log(p_n)$. Again the valid range of $n$ depends on the choice of $\beta_n$. For now choose them (say, $\beta_n = 3$) so that $P > P'$.
  (Stevens chose $1/n$ for $P'$). Then $P- T \gt P' -T'$, and $SB' > SB$. We just need to find odd $s > 2eh(n) -1$ and ensure that $P' > T'$, and then combine everything. Stevens's form is similar to what is below; I will use my versions of $P'$ and $T'$. Writing $z$ for $\log(p_n)$,

$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(n)(1/2)^(2e(\alpha_n + \log(z)))$.

Now $(1/2)^2e\log(z) = (z)^{-2e\log(2)}$. So

 $ = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$ $ = z^{-1} ( (\beta_n)^{-1} - (e^{\alpha_n})^{-2e\log(2) + 1} z^{-2e\log(2) + 2} ) $ 

$ \binom{n+1}{s} ( 1 +\frac{s(s-1)}{(n+2)(n+3 -2s)}) ) \frac{z}{(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}} \gt /frac{SB}{P-T}$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume n > 30, the fudge factor is at most 18/11, and when \beta_n=3 and \alpha_n = 0.75, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since \log(\log(p_n)) is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n}$.

Now as to the choice of \alpha_n and \beta_n. They were chosen generously: Mertens showed that \sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + delta$, where $B$ is a constant close to 0.26 and delta is an error bounded in size by a sum of two terms, the largest of which is 4/log(p_n +1). So using Merten's estimate, p_n + 1 should be bigger than (some number not much larger than e^8. Similarly, Mertens has an estimate on \prod_{1 \le i \le n} (1 - 1/p_i), which is e^{-(\gamma + delta)}/\log(p_n), where e^-\gamma is close to 1/1.78 and delta is bounded by a sum of three terms, the largest of which is again 4/log(p_n+1), again requiring that p_n + 1 be bigger than (something close to) e^8. However, computations seem to show that the constants chosen seem to allow the required estimates to hold for n >30 and some n smaller than THe major block is on n > 2s > 2eh(n) - 1.

Aaron Meyerowitz was kind enough not only to do some computations for me but also to show me a better way to compute some quantities I was interested in to solve the problem. Inspired by his efforts, I convinced myself that a sequence of error terms I was using satisfied $E_{i+1}(x) \le 2E_i(x)$, which then led me to improve Westzynthius's result to $Q*2^{g(n)}$ where $g(n)$ was $n/2 + O(\log(n))$.

$m$ will be a positive integer, and I prefer $m \gt 1$. Jacobsthal's function $j(m)$ gives the smallest positive integer $j$ such that, for any interval $I$ of $j$ integers of the form $[a+1,\ldots,a+j]$, it is guaranteed that one of the integers in $I$ is coprime to $m$, i.e. $\gcd(m,a+i)=1$ for at least one $a+i \in I$. Let $\text{rad}(m) = \prod_{p \text{ prime,} p \mid m} p$ be the largest squarefree factor of $m$; $j(\text{rad}(m))=j(m)$ and also $j(m)$ is the size of the largest gap between consecutive members of the set of integers which are relatively prime to $m$. In my problem above, I wanted nice upper bounds on $j(P_n)$, or Jacobsthal's function evaluated at the $n$th primorial.

Proof sketch: For an interval $I$ having $l$ consecutive integers, and for a positive integer $t$ let $J_t$ be the number of (integer) multiples of $t$ inside $I$. Then $\text{ceil}{l/t} \ge J_t \ge \text{floor}{l/t}$. So the count of numbers in $I$ not coprime with $m$ is at most $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Now if $l \ge rn$, then the right hand side of the inequality is at least $l$, meaning at least 1 number in $I$ is coprime with $m$. End of Proof sketch.

Theorem (Stevens) $j(m) < 2n^{(2 + 2e\log(n))}$.

Improvement? (Paseman): For sufficiently large $n$, $j(m) \le O^*(n^{(2 +2e \log(\log(p_n))})$.

The reasons for the $O^*$ will appear, as I will discuss Stevens's proof and the improvement together. In discussing the improvement, I will ask that $n \gt 30$.

Stevens starts out using (equivalents of) $I$, $l$, and $J_t$ as above. He uses inclusion-exclusion to compute $L$, the number of integers coprime to $m$ in the interval $I$. For ease, I assume $m$ is squarefree, and here $\mu(t)$ is the M$\"{o}$bius function, so $\mu(t)$ is (-1) to the power of the number of distinct prime divisors of (squarefree) $t$. Thus,

$L \ge lT_s - SB $, where $T_s = \sum_{0 \le i \le s} (-1)^i (\sum_{t \mid m , \nu(t) = i} 1/t)$. and $SB = \sum_{1 \le i \le s} \binom{n}{s}$

Let's do $SB$. Stevens's replacement is $n^s$; mine is $\binom{n+1}{s}$ times a small fudge factor, which will be strictly less than $n^s$ for $s \gt 2$ and $n$ sufficiently larger than $2s$. The small fudge factor is from dominating the sum by a geometric series with common ratio $\binom{n+1}{s-2} / \binom{n+1}{s}$. This gives $1 + (s(s-1))/((n+2)(n+3-2s))$.

Now Stevens defines $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$. As above, this gives $P = \prod_{1 \le i \le n}(1 - 1/m_i}$ (Recall that the distinct prime factors of $m$ are the $m_i$.) Then $T = P - T_s$, so

$ (i!)\sum_{t \mid m , \nu(t) = i} 1/t \le (\sum_{1 \le j \le n} 1/m_j)^i \le h(n)^i$, so $T \lt \sum_{s \lt i \le n} ((\sum_{1 \le j \le n} 1/m_j)^i)/(i!)$,

so $T \lt \sum_{s \lt i } (h(n)^i)/(i!) \le e^{h(n)}(h(n)^{s+1})/((s+1)!)$.

If we replace $(s+1)!$ with the smaller $((s+1)/e)^{s+1}$ and choose $s$ so that $s+1 \gt 2eh(n)$, then $T' = e^h(n)2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$.

Also $P = \prod_{1 \le i \le n}(1 - 1/m_i} \gt \prod_{1 \le i \le n}(1 - 1/p_i} \gt 1/(\beta_n\log(p_n))$, so let $P' = 1/(\beta_n\log(p_n))$. Again the valid range of $n$ depends on the choice of $\beta_n$. For now choose them (say, $\beta_n = 3$) so that $P > P'$. (Stevens chose $1/n$ for $P'$.) Then $P- T \gt P' -T'$, and $SB' > SB$. We just need to find odd $s > 2eh(n) -1$ and ensure that $P' > T'$, and then combine everything. Stevens's form is similar to what is below; I will use my versions of $P'$ and $T'$. Writing $z$ for $\log(p_n)$,

$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(n)(1/2)^{2e(\alpha_n + \log(z))}$.

Now $(1/2)^{2e\log(z)} = z^{-2e\log(2)}$. So

$ = (\beta_n z)^{-1} - ((e^{\alpha_n})z)^{-2e\log(2) + 1}$

$ = z^{-1} ( (\beta_n)^{-1} - (e^{\alpha_n})^{-2e\log(2) + 1} z^{-2e\log(2) + 2} ) $

$ \binom{n+1}{s} ( 1 +(s(s-1))/((n+2)(n+3 -2s)) ) (z/[(\beta_n)^{-1} - (e^\alpha_n)^{-2e\log(2) + 1} z^{-2e\log(2) + 2}]) \gt \frac{SB}{P-T}$ and this gives a value for $l$ which in turn gives $L > 0$. Since for the improvement I assume $n > 30,$ the fudge factor is at most 18/11, and when $\beta_n=3$ and $\alpha_n = 0.75$, the denominator of the last fraction goes from some value above 1/5 to 1/3 as $n$ increases. So the whole expression is bounded by $9 \binom{n+1}{s} z$, or $9 \binom{n+1}{s} \log{p_n}$. Since $\log(\log(p_n)) $ is increasing, the whole ball of wax is bounded by $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n}$.

Now as to the choice of $\alpha_n$ and $\beta_n$. They were chosen generously: Mertens showed that $\sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + \delta$, where $B$ is a constant close to 0.26 and $\delta$ is an error bounded in size by a sum of two terms, the largest of which is $4/\log(p_n +1)$. So using Merten's estimate, $p_n + 1$ should be bigger than (some number not much larger than) $e^8$. Similarly, Mertens has an estimate on $\prod_{1 \le i \le n} (1 - 1/p_i)$, which is $e^{-(\gamma + \delta)}/\log(p_n)$, where $e^-\gamma$ is close to 1/1.78 and $\delta$ is bounded by a sum of three terms, the largest of which is again $4/\log(p_n+1)$, again requiring that $p_n + 1$ be bigger than (something close to) $e^8$. However, computations seem to show that the constants chosen seem to allow the required estimates to hold for $n \gt 30$ and some $n$ smaller than The major block is on $n \gt 2s \gt 2eh(n) - 1$.

Source Link
Gerhard Paseman
  • 13.2k
  • 3
  • 34
  • 66
Loading