Cubrir un conjunto con progresiones geométricas

Question

Considere el conjunto $S_n=\{1,2,\cdots ,n\}$ . ¿Cuál es el número mínimo de progresiones geométricas distintas que cubren $S_n$ ? Llamemos a este número $a_n$ . Me preguntaba sobre este número después de hacer un problema de la MO Allrussian, 1995.

¿Puede el conjunto $\{1,2,\cdots,100\}$ estar cubierto con $12$ ¿progresiones geométricas?

Resulta sencillo después de observar el hecho de que no puede haber tres primos en una progresión geométrica. Por lo tanto, el problema se replantea a la contradicción obvia $$\pi(100)\le 24$$ Ahora había buscado un poco y aquí se ha demostrado que $a_{100}\ge 24$ . Ahora me gustaría tener algunas asintóticas, o referencias, o mejores límites en $a_n$ .

También he encontrado el hecho de que $$a_n\ge \left\lfloor{\frac{3n}{\pi^2}}\right\rfloor$$

Lo cual es obvio ya que cualquier progresión geométrica contiene como máximo $2$ números libres de cuadrados y hay alrededor de $\dfrac{6n}{\pi^2}$ números libres al cuadrado menores que $n$ . Obsérvese que supera el límite dado. ¿Pero es posible algo mejor? Gracias de antemano.

Answer 1

Podemos reducir el límite superior de Lucía de $3/8$ un poco más allá como sigue. Comience por tomar el $n/4$ progresiones geométricas de razón común $2$ comenzando en cada número impar a lo sumo $n/2$ . A continuación, para cada número impar $x$ en el rango $[n/2,25n/49]$ divisible por $25$ incluyen la progresión $\{x,(7/5)x,(7/5)^2x\}$ . Empareja los números restantes de impar. Si he sumado esto correctamente obtengo $3/8 - 1/(4900)$ como límite superior.

Como he explicado en mi comentario se puede mejorar el límite inferior $3/\pi^2$ ligeramente considerando un conjunto de enteros $S$ más grande que los cuadrados libres, pero que no contenga tres términos de una progresión geométrica. He aquí una construcción algo general de dicho conjunto. Sea $Q\subset\mathbf{Z}_{\geq0}^2$ sea cualquier conjunto sin tres puntos en una línea. Ahora dejemos que $p_1,p_2,\dots$ sean los primos y que $$S = \left\{\text{integers }n= \prod p_i^{e_i} \text{ such that } (e_1,e_2)\in Q, (e_3,e_4)\in Q,\dots\right\}.$$ Entonces $S$ no tiene tres términos de ninguna progresión geométrica, y se podría escribir una expresión tipo producto de Euler para la densidad de $S$ en términos de $Q$ . Tenga en cuenta que $Q$ contiene $$\{(0,0),(1,0),(0,1),(1,1)\}$$ entonces $S$ contiene todos los enteros libres de cuadrados, pero $Q$ también podría ser mayor. Tomando $$Q = \{(0,0),(1,0),(0,1),(1,1),(2,3)\},$$ la densidad de $S$ es $$\prod_{i=1}^\infty \left(1-\frac{1}{p_{2i-1}}\right) \left(1-\frac{1}{p_{2i}}\right)(1 + p_{2i-1}^{-1} + p_{2i}^{-1} + p_{2i-1}^{-1} p_{2i}^{-1} + p_{2i-1}^{-2} p_{2i}^{-3}),$$ que, en cualquier caso, está acotado por debajo de $$ \frac{1 + 2^{-1} + 3^{-1} + 2^{-1} 3^{-1} + 2^{-2} 3^{-3}}{1 + 2^{-1} + 3^{-1} + 2^{-1} 3^{-1}} \prod_{p} \left(1-\frac{1}{p^2}\right) = \frac{217}{36\pi^2}.$$ Así, $\frac{217}{72\pi^2}$ es un límite inferior.

Este problema se menciona como problema 2014.2.1 en http://arxiv.org/pdf/1406.3558v2.pdf aunque es de suponer que otros también lo han reflexionado.