Si alguien me hubiera dicho hace meses que el trabajo sobre la función de Jacobsthal de Jacobsthal proporciona límites para una versión generalizada de este problema, yo podría me habría alejado del problema y no habría hecho nada más. Pero así son las cosas, me he enseñado a mí mismo bastante, y compartiré algo de ello.
Aaron Meyerowitz tuvo la amabilidad no sólo de hacer algunos cálculos sino también para mostrarme una mejor manera de calcular algunas cantidades que me interesaban para resolver el problema. Inspirado por sus esfuerzos, me convencí de que una secuencia de términos de error que estaba utilizando satisfacía $E_{i+1}(x) \le 2E_i(x)$ que luego me llevó a mejorar el resultado de Westzynthius a $Q*2^{g(n)}$ donde $g(n)$ fue $n/2 + O(\log(n))$ .
Aaron también me señaló hacia una secuencia en la Online Encyclopedia of Integer Sequences que me llevó a Hagedorn de 2009 sobre el cálculo de ciertos valores de la función de Jacobsthal. de Jacobsthal.
http://www.tcnj.edu/~hagedorn/papers/JacobPaper.pdf Como resultado, tengo una respuesta a 2 de mis preguntas y una mejora de un resultado de la bibliografía. Para la pregunta 1, la respuesta es sí, hay otros trabajos que dan límites superiores demostrables del orden de $2^{\text{polylog}(n)}$ . Para la pregunta 2, la respuesta también es afirmativa; un resultado de 1977 de Harlan Stevens da un límite explícito en el que un paso importante utiliza la equivalente de las desigualdades de Bonferroni. He revisado su argumento y decidí modificarlo para obtener un resultado asintóticamente mejor. (Otros trabajos, especialmente los de Iwaniec, ofrecen límites superiores asintóticos aún mejores, pero no dan constantes explícitas, por lo que es difícil decir con precisión cuando esos límites son mejores). A continuación expongo la mayor parte del argumento de Stevens y algunos materiales relacionados.
$m$ será un número entero positivo, y prefiero $m \gt 1$ . Función de Jacobsthal $j(m)$ da el número entero positivo más pequeño $j$ tal que, para cualquier intervalo $I$ de $j$ enteros de la forma $[a+1,\ldots,a+j]$ se garantiza que uno de los enteros de $I$ es coprimo de $m$ es decir $\gcd(m,a+i)=1$ durante al menos un $a+i \in I$ . Sea $\text{rad}(m) = \prod_{p \text{ prime,} p \mid m} p$ sea el mayor factor libre de cuadrados de $m$ ; $j(\text{rad}(m))=j(m)$ y también $j(m)$ es el tamaño de el mayor espacio entre miembros consecutivos del conjunto de enteros que están relativamente primos de $m$ . En mi problema anterior, quería buenos límites superiores en $j(P_n)$ o la función de Jacobsthal evaluada en el $n$ primorial.
Hay muchos resultados accesibles en $j(m)$ . Por ejemplo, si si $m_1,\ldots,m_n$ son todas las factores primos de $m$ (y por tanto de $\text{rad}(m)$ ), y cada una de ellas es mayor que $n$ , entonces se utiliza el Teorema Chino del Resto para demostrar $j(m) \ge n+1$ y de hecho para tal $m$ , $j(m) = n+1$ . Esto se puede generalizar con un poco de ayuda: digamos $m$ y $r \gt 1 $ son tales que $\sum_{1 \le i \le n} 1/m_i \lt (1 - 1/r)$ . Entonces $j(m) \le rn$ . Dado que introducirá notación que se utilizará más adelante, esbozo una demostración.
Esbozo de prueba: Para un intervalo $I$ teniendo $l$ enteros consecutivos, y para un entero positivo $t$ deje $J_t$ sea el número de múltiplos (enteros) de $t$ en $I$ . Entonces $\text{ceil}(l/t) \ge J_t \ge \text{floor}(l/t)$ . Por tanto, el recuento de números en $I$ no coprimo con $m$ es como máximo $n + \sum_{1 \le i \le n} l/m_i \lt n + l(1-1/r)$ . Ahora bien $l \ge rn$ entonces el lado derecho de la desigualdad es al menos $l$ , lo que significa que al menos 1 número en $I$ es coprimo con $m$ . Fin del esbozo de prueba .
Se puede hacer mejor, ya que para primos pequeños $m_1$ y $m_2$ puede haber varios de $m_1m_2$ dentro del intervalo. Kanold, Jacobsthal, Erdos y otros han hecho algunas mejoras en este campo. Sin embargo, ahora muestro el resultado de Harlan Stevens.
Teorema (Stevens) $j(m) < 2n^{(2 + 2e\log(n))}$ .
¿Mejora? (Paseman): Para suficientemente grande $n$ , $j(m) \le O^*(n^{(2 +2e \log(\log(p_n)))})$ .
Las razones de la $O^*$ aparecerá, ya que discutiré la prueba de Stevens y la mejora juntos. Al discutir la mejora, voy a pedir que $n \gt 30$ .
Stevens comienza utilizando (equivalentes de) $I$ , $l$ y $J_t$ como arriba. Utiliza la inclusión-exclusión para calcular $L$ el número de enteros coprimo a $m$ en el intervalo $I$ . Para facilitar las cosas, asumo que $m$ es libre de cuadrados, y aquí $\mu(t)$ es la función de Moebius, por lo que $\mu(t)$ es (-1) a la potencia del número de divisores primos distintos de (libre de cuadrados) $t$ . Así,
$L = \sum_{t \mid m} \mu(t)J_t$ .
Ahora Stevens cita a Landau para usar lo que yo considero una desigualdad de Bonferroni. Rompiendo la suma por $\nu(t)$ el número de factores primos distintos de $t$ se tiene por impar valores de $s$ lo siguiente:
$L \ge \sum_{0 \le i \le s} (-1)^i ( \sum_{t \mid m , \nu(t) = i} J_t) $ .
Utilizando la estimación $\mid J_t - l/t \mid \le 1$ (excepto para $t=1$ cuando $l=J_t$ ),
$L \ge lT_s - SB $ donde $T_s = \sum_{0 \le i \le s} (-1)^i (\sum_{t \mid m , \nu(t) = i} 1/t)$ . y $SB = \sum_{1 \le i \le s} \binom{n}{s}$
Ahora normalmente uno encuentra $s$ para que $T_s$ y $SB$ puede estimarse bien, y entonces se dice que para cualquier $l > SB/T_s$ , $L$ será positivo, dando que $SB/T_s$ (o la estimación apropiada) es un límite superior para $j(m)$ . Stevens no hace eso. En su lugar, reescribe $T_s$ como $P - T$ encuentra estimaciones para $T',P',$ y $SB'$ para que $ SB'/(P' - T') \ge SB/T_s$ garantiza que $P' > T'$ y luego concluye que $j(m) \le SB'/(P' - T')$ . Haré lo mismo, salvo que utilizaré estimaciones más estimaciones más precisas.
Vamos a hacer $SB$ . El sustituto de Stevens es $n^s$ el mío es $\binom{n+1}{s}$ por un pequeño factor de error, que será estrictamente inferior a $n^s$ para $s \gt 2$ y $n$ suficientemente mayor que $2s$ . El pequeño factor de error se debe a que la suma está dominada por una serie geométrica con relación común $\binom{n+1}{s-2} / \binom{n+1}{s}$ . Esto da $1 + (s(s-1))/((n+2)(n+3-2s))$ .
Ahora Stevens define $P = \sum_{0 \le i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$ . Como en la pregunta anterior, esto da $P = \prod_{1 \le i \le n}(1 - 1/m_i)$ (Recordemos que los factores primos distintos de $m$ son los $m_i$ .) Entonces $T = P - T_s$ Así que
$T = \sum_{s \lt i \le n} (-1)^i \sum_{t \mid m , \nu(t) = i} 1/t$ .
Ahora Stevens estima $T$ por $T' > T$ primero sustituyendo la suma interna (y desechando $(-1)^i$ ), y entonces teniendo el índice de la suma exterior pase por $n$ . A continuación, utiliza el teorema de Taylor con resto en $e^{h(n)}$ para una determinada elección de $h(n)$ para llegar a un término compacto que limite el suma infinita. Entonces $s$ se restringe para llegar a un $T'$ que limita $T$ pero sigue siendo pequeño.
Allá vamos. Para $n$ suficientemente grande
$ (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$ , así que $T \lt \sum_{s \lt i \le n} ((\sum_{1 \le j \le n} 1/m_j)^i)/(i!)$ ,
así que $T \lt \sum_{s \lt i } (h(n)^i)/(i!) \le e^{h(n)}(h(n)^{s+1})/((s+1)!)$ .
Stevens eligió $\log(n) > \sum_{1 \le j \le n} 1/p_j \ge \sum_{1 \le j \le n} 1/m_j$ para $n > 2$ para usar como $h(n)$ . Yo elijo $\alpha_n + \log(\log(p_n))$ para $h(n)$ y hablaremos de la constante positiva $\alpha_n < 1$ y los valores permitidos de $n$ más tarde. (Pensando en $\alpha_n = 0.75$ es bueno). Ahora vamos a $T'$ .
Si sustituimos $(s+1)!$ con el más pequeño $((s+1)/e)^{s+1}$ y elija $s$ para que $s+1 \gt 2eh(n)$ , entonces $T' = e^{h(n)}2^{-s-1} \gt e^{h(n)}(h(n)^{s+1})/((s+1)!) \gt T$ .
Tambié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))$ , de modo que $P' = 1/(\beta_n\log(p_n))$ . De nuevo, el intervalo válido de $n$ depende del elección de $\beta_n$ . Por ahora elígelos (digamos, $\beta_n = 3$ ) de modo que $P > P'$ . (Stevens eligió $1/n$ para $P'$ .) Entonces $P- T \gt P' -T'$ y $SB' > SB$ . Sólo tenemos que encontrar a impar $s > 2eh(n) -1$ y garantizar que $P' > T'$ y luego combinarlo todo. La forma de Stevens es similar a la que aparece a continuación; yo utilizaré mis versiones de $P'$ y $T'$ . Escribir $z$ para $\log(p_n)$ ,
$P' - T' = 1/(\beta_n z) - e^{\alpha_n}z(1/2)^{2e(\alpha_n + \log(z))}$ .
Ahora $(1/2)^{2e\log(z)} = z^{-2e\log(2)}$ . Así que
$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}$
$ = z^{-1} ( (\beta_n)^{-1} - (e^{\alpha_n})^{-2e\log(2) + 1} z^{-2e\log(2) + 2} ) $
Puesto que tendremos $n$ lo suficientemente grande como para que $\beta_n \lt (e^{\alpha_n})^{2e\log(2) - 1}$ y puesto que $z^{2e\log(2) - 2}\gt 1$ obtenemos que $P' - T' > 0$ .
Ahora a juntarlo todo. Si $s$ es impar y $s+1 \gt 2e(\alpha_n + \log(\log(p_n)))$ entonces
$ \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)$ y esto da un valor para $l$ que a su vez da $L > 0$ . Ya que para la mejora asumo $n > 30,$ el factor de manipulación es como máximo 18/11, y cuando $\beta_n=3$ y $\alpha_n = 0.75$ el denominador de la última fracción pasa de algún valor por encima de 1/5 a 1/3 como $n$ aumenta. Así que toda la expresión está limitada por $9 \binom{n+1}{s} z$ o $9 \binom{n+1}{s} \log{p_n}$ . Desde $\log(\log(p_n)) $ es creciente, toda la bola de cera está limitada por $n^{2e(\log\log(p_n) + \alpha_n) +1}\log(p_n)$ .
En cuanto a la elección de $\alpha_n$ y $\beta_n$ . Fueron elegidos generosamente: Mertens demostró que $\sum_{1 \le i \le n} 1/p_i \lt \log\log(p_n) + B + \delta$ donde $B$ es una constante cercana a 0,26 y $\delta$ es un error cuyo tamaño está limitado por la suma de dos términos, el mayor de los cuales es $4/\log(p_n +1)$ . Así que usando la estimación de Merten, $p_n + 1$ debe ser mayor que (algún número no mucho mayor que) $e^8$ . Del mismo modo, Mertens tiene una estimación sobre $\prod_{1 \le i \le n} (1 - 1/p_i)$ que es $e^{-(\gamma + \delta)}/\log(p_n)$ donde $e^{-\gamma}$ se aproxima a 1/1,78 y $\delta$ está limitada por una suma de tres términos, el mayor de los cuales es de nuevo $4/\log(p_n+1)$ lo que requiere que $p_n + 1$ ser mayor que (algo parecido a) $e^8$ . Sin embargo, los cálculos parecen demostrar que las constantes elegidas parecen permitir el rquired para $n \gt 30$ y algunos $n$ inferior a 30. El bloque principal está en $n \gt 2s \gt 2eh(n) - 1$ .
Agradezco cualquier aportación constructiva y la comprobación de errores. Lo revisaré en las próximas semanas.
Gerhard "Almost Ready To Shelve This" Paseman, 2011.02.25
