Covering a set with geometric progressions

Question

Consider the set $S_n=\{1,2,\cdots ,n\}$. What is the minimum number of distinct geometric progressions that cover $S_n$? Let us call this number $a_n$. I was wondering about this number after doing a problem from the Allrussian MO, 1995.

Can the set $\{1,2,\cdots,100\}$ be covered with $12$ geometric progressions?

It becomes straightforward after observing the fact no three primes can be in a geometric progression. Hence the problem is restated to the obvious contradiction $$\pi(100)\le 24$$ Now I had searched a bit and here it is proven that $a_{100}\ge 24$. Now I would like some asymptotics, or references, or better bounds on $a_n$ .

I have also found the fact that $$a_n\ge \left\lfloor{\frac{3n}{\pi^2}}\right\rfloor$$

Which is obvious since any geometric progression contains at most $2$ squarefree numbers and there are about $\dfrac{6n}{\pi^2}$ squarefree numbers less than $n$. Note it surpasses the bound given. But is something better possible? Thanks in advance.

Answer 1

We can reduce Lucia's upper bound of $3/8$ a little further as follows. Begin by taking the $n/4$ geometric progressions of common ratio $2$ beginning at each odd number at most $n/2$. Then for each odd number $x$ in the range $[n/2,25n/49]$ divisible by $25$ include the progression $\{x,(7/5)x,(7/5)^2x\}$. Pair off the remaining odd numbers. If I've added this up correctly I get $3/8 - 1/(4900)$ as an upper bound.

As I explained in my comment one can improve the lower bound $3/\pi^2$ slightly by considering a set of integers $S$ larger than just the square-frees but still not containing any three terms of a geometric progression. Here is a somewhat general construction of such a set. Let $Q\subset\mathbf{Z}_{\geq0}^2$ be any set without three points on a line. Now let $p_1,p_2,\dots$ be the primes and let $$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\}.$$ Then $S$ has no three terms of any geometric progression, and one could write down an Euler-product-like expression for the density of $S$ in terms of $Q$. Note if $Q$ contains $$\{(0,0),(1,0),(0,1),(1,1)\}$$ then $S$ contains all square-free integers, but $Q$ could be larger as well. Taking $$Q = \{(0,0),(1,0),(0,1),(1,1),(2,3)\},$$ the density of $S$ is $$\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}),$$ which in any case is bounded below by $$ \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}.$$ Thus $\frac{217}{72\pi^2}$ is a lower bound.

This problem is mentioned as problem 2014.2.1 in http://arxiv.org/pdf/1406.3558v2.pdf, though presumably others have pondered it as well.