Después de estudiar el artículo de Kanold de 1967 sobre la función de Jacobsthal, (e inspirándome en un preprint http://arxiv.org/abs/1208.5342 que discuto más adelante,) encontré un argumento, en su mayor parte muy simple, que da algunos resultados agradables para el esfuerzo dado. Aunque Kanold merece parte del crédito por el argumento, todavía no he visto una declaración suya ni de nadie que dé estos resultados, así que los presento aquí. (Kanold escribió varios artículos sobre la función de Jacobsthal, muchos de los cuales estoy rastreando, que podrían tener este argumento. Estoy dispuesto a aceptar ayuda para obtener copias electrónicas de ellos). Este es el post que prometí hace unos meses en un suplemento a una pregunta de Timothy Foo, Análogos de la función de Jacobsthal .
Para obtener el máximo efecto ooh-aah, supongo que $n$ es libre de cuadrados y tiene $k \gt 2$ factores primos, uno de los cuales llamo Peter, o $p$ para abreviar. $1+tn$ es coprimo de $n$ para cualquier número entero $t$ . También lo son la mayoría de los números enteros de la forma $1 + tn/p$ con la excepción de los múltiplos de $p$ y esos múltiplos no aparecen como términos consecutivos. Así, todo intervalo de longitud $2n/p (=g(p)n/p)$ tiene al menos un número entero coprimo a $n$ de la forma $1+tn/p$ .
Vayamos más lejos con esto. Dejemos que $d \gt 1$ y dividir $n$ y que $f=n/d$ . (Aquí utilizo $n$ squarefree para obtener $f$ coprimo a $d$ .) A continuación, los números de la forma $1+tf$ forman una progresión aritmética, son coprimos de $f$ y (como puede verse multiplicando por $f$ en el anillo de los enteros mod $d$ ) no puedes elegir $g(d)$ miembros consecutivos de esta progresión sin golpear algo coprimo a $d$ también. Así que $g(n) \leq g(d)f = g(d)n/d$ .
Mientras estoy aquí, permítanme afilar la desigualdad, suponiendo que $f \gt 1$ y $d \gt 1$ son coprimos: hay $\phi(f)$ totients $c$ de $f$ en el intervalo $[0,f]$ por lo que puedo repetir el argumento con $c+tf$ en lugar de $1+tf$ . En el peor de los casos, utilizando todos $\phi(f)$ progresiones, obtengo $g(fd) \leq g(d)f - f + g(f)$ que mejora ligeramente el límite de Kanold $g(d)f -\phi(f)+1$ y lo iguala cuando $f$ es primo. (Por supuesto, para $n=fd$ Realmente quiero $g(n)$ estar cerca $O(g(d)+g(f))$ pero aún no sé cómo demostrarlo con la aritmética de la escuela primaria).
¿Cómo utilizar esta desigualdad? Elige el divisor mayor $d$ para la que se puede calcular cómodamente (una subcuadrática en $k$ límite superior para) $g(d)$ ; elijo $d$ para contener la mayoría de los grandes factores primos de $n$ : encontrar primo $q$ dividiendo $n$ para que $\sigma^{-1}(d)=\sum_{p \text{ prime,} p|n, p \geq q} 1/p$ es inferior a $1 + 1/2q$ un argumento rutinario da como resultado $g(d)$ es $O(qk)$ . Lo feo es demostrar que $q \lt k^{0.5}$ (o bien $d=n$ ), que $n/d \lt 2^{3q/2}$ que para grandes $k$ se acerca a $2^{3(k^{\epsilon + 1/e})/2}$ y que asintóticamente $g(n)$ es $O(e^{k^{1/e}+D\log(k)})$ . Esto no es difícil después de utilizar uno de los teoremas de Mertens y una función de Chebyshev; sólo que no es bonito. (También para $n$ , $\epsilon + 1/e$ puede estar cerca de $1/2$ pero con paciencia $\epsilon$ tenderá a cero).
Esto da un límite que es asintóticamente mejor que mis primeros esfuerzos en esto, mejora ligeramente ( $k^{0.5}$ sustituido por $Ck^{0.37}+ D\log(k)$ en el límite de Kanold de $2^\sqrt{k}$ para $k$ no demasiado grande, y no necesita el requisito de Kanold de que $k > e^{50}$ . Hasta que uno elige $d$ Sospecho que incluso Legendre conocía el uso de la inversa multiplicativa para transformar una progresión aritmética general en una secuencia (efectivamente) consecutiva de números enteros y seguir conservando la propiedad que nos interesa aquí, ser una unidad en un anillo determinado (o faltarle tanto).
(Una de las ventajas de dejar reposar esto unos meses antes de publicarlo es que puedo añadir observaciones interesantes como: Si pudiera reducir la desigualdad a $g(n) \leq g(d)g(n/d)$ podría iterar el estimación simple anterior para obtener un límite explícito de $O(k^c)$ donde $c$ es un número positivo menor que 3. O como: usando un trabajo más avanzado combinado con lo anterior, puedo obtener $g(n) \leq e^{k^{e^{-a}}}Ck^{a}$ para algunos números enteros $a$ que parece mejor que $Ck^{4\log\log{k}}$ si no te fijas demasiado).
Además, se puede utilizar un ordenador para refinar ligeramente el método y obtener estimaciones que funcionen bastante bien para valores pequeños de $n$ donde pequeño significa $k<100$ . Sin embargo, asintóticamente, los límites superiores de Stevens y los míos acaban superando este límite.
También se ha producido un buen resultado en el University College de Dublín, que voy a interpretar brevemente. Fintan Costello y Paul Watts han encontrado una forma de presentar recursivamente una función afín y, a continuación, han calculado numéricamente una cota inferior de esta función que implica una cota superior de la función de Jacobsthal calculada sobre algunos valores particulares. Les agradezco que me hayan recordado el uso de un inverso multiplicativo mod $d$ para $f$ por lo que merecen una "parte de la acción".
Estos autores trabajan en (y a veces fuera de) el intervalo entero $BM = [b+1,b+2,\ldots,b+m]$ . Dado un cuadrado libre $n$ y sus factores primos distintos, enumerados en cierto orden como $q_1$ a $q_k$ define $Q_i$ como $\prod_{0 \lt j \leq i} q_j$ . Un método para calcular el tamaño $\pi(b,m,n)$ del conjunto $CP(b,m,n)$ que tiene esos enteros en $BM$ coprimo a $n$ es hacer el argumento estándar de inclusión-exclusión: si representamos por $F(b,m,d)$ los múltiplos de $d$ en $BM$ y decir que hay $f(b,m,d)$ muchos de esos múltiplos, y abusando de alguna notación, escribo entonces $CP(b,m,n) = \sum_{d | n} sgn(d,F(b,m,d))$ . Aquí $sgn$ es sugerir que se añadan elementos del conjunto $F(b,m,d)$ si $d$ tiene un número par de factores primos, y restándolos en cambio cuando $d$ tiene un número impar de factores primos.
Para establecer la expresión recurrente, Costello y Watts utilizan sólo algunos de los términos del lado derecho de la ecuación abusada y reorganizan el resto de los términos. En mi interpretación de su trabajo, empiezan con la identidad de conjuntos múltiples
$$CP(b,m,n) \cup \biguplus_{0 \lt i \leq k} F(b,m,q_i) = BM \uplus \biguplus_{0 \lt i \lt j \leq k} RCP(i,j)$$
donde $RCP(i,j)$ es $F(b,m,q_iq_j) \cap CP(b,m,Q_{i-1})$ o el subconjunto de $BM$ que tiene esos múltiplos de $q_iq_j$ cuyo factor primo más próximo en común con $n$ es $q_i$ .
Esta identidad se cumple si consideramos un miembro de $BM$ que tiene exactamente $t$ factores primos distintos en común con $n$ . Si $t$ es $0$ entonces el miembro sólo aparece una vez en $CP(b,m,n)$ y de forma similar sólo una vez en $BM$ . En caso contrario, se produce exactamente $t$ veces en el lado izquierdo en $t$ términos distintos $F(b,m,q_i)$ y si $l$ es más pronto tal que $q_l$ es un factor primo del miembro, el miembro sólo aparece una vez en cada uno de $t-1$ establece $RCP(l,j)$ (recuerda $l$ llega antes que $j$ ) y sólo una vez en $BM$ .
Ahora el término $RCP(i,j)$ es un subconjunto de una progresión aritmética $A$ con diferencia común $q_iq_j$ . Utilizando la técnica anterior de multiplicar por un inverso adecuado de $q_iq_j$ en el anillo de enteros mod $Q_{i-1}$ , $A$ se corresponde con un intervalo entero que comienza cerca de algún número entero $c_{ijbm}$ de longitud $f(b,m,q_iq_j)$ que preserva el estado de coprimalidad con respecto a $Q_{i-1}$ a saber, el tamaño de $RCP(i,j)$ es $\pi(c_{ijbm},f(b,m,q_iq_j),Q_{i-1})$ . Utilización de la $\pi$ para el tamaño de $CP$ y traduciendo los otros conjuntos a números se obtiene la fórmula numérica recurrente de Costello y Watts: $$\pi(b,m,n) = m - \sum_{0 \lt i \leq k} f(b,m,q_i) + \sum_{0 \lt i \lt j \leq k} \pi(c_{ijbm},f(b,m,q_iq_j),Q_{i-1})$$ .
Siguiendo el trabajo de Hagedorn, que calculó $h(k)=g(P_k)$ para $k$ inferior a 50, donde $P_k$ es el $k$ primorial, Costello y Watts utilizan su fórmula y algunos análisis de coincidencia de residuos primos para calcular una desigualdad para $\pi_{min}(m,n)$ que es el mínimo sobre todos los números enteros $b$ de $\pi(b,m,n)$ . Subestiman $f(b,m,q_iq_j)$ por $\lfloor m/q_iq_j \rfloor$ ignore el $c$ utilizando $\pi_min$ saca el $i=1$ términos de la suma doble y reescribir esa parte para incluir un término $E$ dependiendo únicamente de $m$ y el $p_i$ que surge de observar cuándo las estimaciones de los tamaños de los $F(b,m,p_i)$ y $F(b,m,2p_i)$ se pueden mejorar, y llegar a (una versión refinada, utilizando $p$ 's para $q$ 's, de) la desigualdad $$m - \sum_{0 \lt i \leq k} \lceil \frac{m}{p_i} \rceil + \sum_{1 \lt i \leq k} \lfloor \frac{m}{2p_i} \rfloor + E + \sum_{1 \lt i \lt j \leq k} \pi_{min}(\lfloor \frac{m}{p_ip_j} \rfloor,P_{i-1}) \leq \pi_{min}(m,P_k)$$ .
Con esta desigualdad, Costello y Watts calculan $\pi_{low}$ una aproximación de límite inferior a $\pi_{min}$ . Desde $h(k) \leq m$ si $\pi_{min}(m,P_k) \gt 0$ informática $\pi_{low}(m,P_k)$ para varios $m$ dará un límite superior a $h(k)$ . Dicen que sus cálculos para $k \leq 10000$ sugiera $h(k) \leq Ck^2 \log k$ donde $C$ es una constante inferior a $0.3$ . Aunque estos datos se obtienen utilizando datos del trabajo de Hagedorn, incluso sin eso su algoritmo arroja valores que suponen una gran mejora respecto a los límites conocidos y fácilmente computables, incluso los enumerados anteriormente.
Un punto a explorar es cómo funcionaría un algoritmo basado en esta aproximación con diferentes ordenaciones de los factores primos. Sospecho que si los primos más grandes van primero se obtendrán resultados más ajustados. Otro punto a explorar es ver si hay un término mejor $F$ que suplantará $E$ y algunos de los términos recurrentes en la suma doble. La idea de reescribir el $\pi$ recursivamente, aunque no es nueva, cobra nueva vida en esta forma de doble suma, y sugiere revisar algunos enfoques antiguos con la vista puesta en la computabilidad.
Gerhard "Ask Me About Coprime Integers" Paseman, 2013.02.05
