La precisión de la aproximación a la inclusión-exclusión de la fórmula en el primer tamiz

Question

Esta cosa surgió en una combinatoria curso que estoy tomando.

Elegir un conjunto fijo de números primos $p_1,p_2,\dots,p_k$ y deje $A_n$ ser el número de enteros en $\{1,2,\dots,n\}$ que no son divisibles por cualquiera de las $p_i$'s. $A_n$ está dado por $ n - \sum_{1\leq i_1 \leq k} \lfloor \frac{n}{p_{i_1}} \rfloor + \sum_{1\leq i_1 < i_2 < k} \lfloor \frac{n}{p_{i_1}p_{i_2}}\rfloor - \dots $. Ahora, si $n$ es divisible por cada uno de los $p_i$'s, entonces tenemos la más simple expresión : $A_n = n \prod_{i=1}^{k}(1-\frac{1}{p_i})$(añade después : nota no estoy asumiendo $n = \prod_{i=1}^{k}p_i$ aquí, esto se cumple siempre que $n = c \prod_{i=1}^{k} p_i $ para algunos entero c, ya que cada una de las $\lfloor \frac{n}{p_{i_1} \dots p_{i_j}} \rfloor = \frac{n}{p_{i_1} \dots p_{i_j}}\ )$.

Otro estudiante señaló que incluso si $n$ no ha $\prod_{i=1}^{k} p_i$ como un factor, la aproximación a $B_n = n \prod_{i=1}^{k}(1-\frac{1}{p_i})$ $A_n$es bastante estrecha en algunos casos específicos. Es fácil ver que $\lim_{n\to\infty}\frac{A_n - B_n}{n}=0$$\lim_{n\to\infty}\frac{1}{n}\lfloor \frac{n}{p_{i_1}p_{i_2}\dots p_{i_j}} \rfloor \to \frac{1}{p_{i_1}p_{i_2} \dots p_{i_j}},$, sin embargo, que no es lo suficientemente fuerte como para implicar que $A_n - B_n$ va a estar siempre cerca. Es allí cualquier manera de analizar qué tan bien esta aproximación se llevará a cabo en general? Estoy interesado en el peor de los casos para las pequeñas y de tamaño moderado $n$.

Sólo para dar una idea de cómo cerrar $A_n$ $B_n$ puede conseguir, suponiendo que el conjunto de los números primos es $\{2,3,7\}$ tenemos (suponiendo que mi programa es correcto):

n     A(n)     B(n)
17    5    4.86  
27    8    7.71  
37    11      10.57  
107   31      30.57  
1111  318     317.43  
3001  858     857.43  
4007  1145    1144.86  
5000  1429    1428.57 .

Answer 1

Para ayudar con la notación que va a cambiar su $k$$m$, por lo que tenemos

$$ A_n = n - \sum \lfloor \frac{n}{p_i} \rfloor + \sum \lfloor \frac{n}{p_i p_j} \rfloor - \sum \lfloor \frac{n}{p_i p_j p_k} \rfloor + \cdots, $$

donde las sumatorias son más distintos de los números primos en nuestro set $ \lbrace p_1,p_2,\ldots,p_m \rbrace ,$ y

$$ B_n = n \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right). $$

El uso de $ x \ge \lfloor x \rfloor > x – 1 $ hemos

$$ A_n \ge n - \sum \frac{n}{p_i} + \sum \frac{n}{p_i p_j} - \binom{m}{2} -
\sum \frac{n}{p_i p_j p_k} + \sum \frac{n}{p_i p_j p_k p_l} - \binom{m}{4} + \cdots.$$

Tomando nota de que $$\binom{m}{0}+\binom{m}{2}+\binom{m}{4} \cdots = 2^{m-1},$$

obtenemos $A_n \ge B_n – 2^{m-1}.$ así mismo, se $A_n \le B_n + 2^{m-1}$ y de ahí que podamos obligado

$$ \left| \frac{A_n – B_n}{n} \right| \le \frac{2^{m-1}}{n} = O(1/n).$$

Sin embargo, si tomamos $n \equiv -1 \textrm{ mod } \prod_{i=1}^m p_i$, entonces tenemos

$$A_n – B_n = \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right) = \text{a constant.} \quad (1)$$

Así que la diferencia es una constante infinitamente a menudo.

EDITAR: Ya que las diferencias entre el $ \lfloor \frac{n}{p_i p_j \ldots} \rfloor $ y el $ \frac{n}{p_i p_j \ldots} $ son de un máximo de al $n \equiv -1 \textrm{ mod } \prod_{i=1}^m p_i$ parece que nos han

$$A_n – B_n \le \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right), \quad (2)$$

con la igualdad cuando la $n \equiv -1 \textrm{ mod } \prod_{i=1}^m p_i.$ I no tiene una prueba de esta última afirmación, aunque tengo una prueba de (1), en el que espero ser capaz de modificar la prueba (2).

EDIT2: no pude encontrar una prueba de (2) porque, lamentablemente, no es cierto! Sin embargo, (1) es exacta para el $n.$

EDIT3:

He aquí una gran mejoría en mi anterior comentario, que creo que soluciona el problema por completo.

Supongamos $n \equiv -r \textrm{ mod } \prod_{i=1}^m p_i, $ donde$ 0 \le r < \prod_{i=1}^m p_i$, entonces tenemos

$$A_n – B_n \le r \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right).$$

He demostrado esto simplemente por la expansión de $A_n – B_n$ y haciendo las sumatorias. También, creo que la fórmula exacta para ser

$$A_n – B_n = \delta + r \prod_{i=1}^m \left( 1- \frac{1}{p_i} \right) - \Phi_P(r),$$

donde $\delta = 1$ al $r$ es coprime a todas las $p_i$ $0$ lo contrario, y $\Phi_P(r)$ es el número de enteros positivos $\le r$ cuales son coprime a la $p_i.$

Tenga en cuenta que cuando $n=711,$ $r=9,$ $\delta = 0$ y $\Phi_P(9) = 2,$ $P=\lbrace 2,3,5 \rbrace,$ por lo que la fórmula anterior da $$A_{711}-B_{711} = 9 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \left( 1 - \frac{1}{5} \right) – 2 = 0.4$$ lo cual está de acuerdo con su $190-189.6 = 0.4$

Cuando $n=107,$ $r=19,$ $\delta = 1$ y $\Phi_P(19) = 6,$ $P=\lbrace 2,3,7 \rbrace,$ así tenemos $$A_{107}-B_{107} = 1 + 19 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \left( 1 - \frac{1}{7} \right) – 6 = 0.42857\ldots,$$

que también está de acuerdo con las cifras redondeadas que has dado en la pregunta.

Lo siento, no tengo tiempo para escribir hasta la plena prueba.

Answer 2

Esto podría ser ligeramente fuera de la tangente, pero es sin duda en el espíritu de su mensaje, y se encuentra en el principio de la mayoría de los textos en el tamiz de la teoría.

Cuando su conjunto fijo de números primos es la primera $k$ primos y $n = p_{k}^2$ $B_{n}$ es el término principal de la criba de Eratóstenes-Legendre, que da una aproximación de la cantidad de números primos en el intervalo de $[p_{k}, p_{k}^2]$. En esta configuración Merten del teorema da una asintótica para $B_{n}$. (Se llama Merten del Tercer teorema en la página de la Wikipedia). Sin embargo, una apelación a la primer número teorema muestra que esta es una medida bastante mala aproximación, y que $B_{n}$ sobreestima el número de números primos por un factor de $2e^{-\gamma}$ donde $\gamma$ es el de Euler-Mascheroni constante.

Terry Tao tiene un buen blog sobre por qué el uso repetido de la inclusión-exclusión en el principio de los rendimientos de no obtener resultados óptimos.