# Covering a set with geometric progressions

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.

• You mean minimum, not maximum. Commented Jul 1, 2014 at 15:17
• The $n/2$ upper bound holds even for progressions with integer coefficients: consider progressions with ratio 2 and odd initial values. Commented Jul 1, 2014 at 15:41
• You can get the upper bound of $3n/8$ by pairing off odd numbers in $(n/2,n)$. Then for each odd number below $n/2$ use the geometric progression with ratio $2$ starting from it. Commented Jul 1, 2014 at 15:53
• One can improve the lower bound slightly. Let $S$ be the set of integers which are either square-free or have the form $2^3 3^2 m$, where $m$ is square-free and not divisible by $2$ or $3$. Then $S$ has density $\delta>6/\pi^2$ and still contains no more than two elements in any one geometric progression, so you get $a_n/n\geq \delta/2$. I do not know the maximal density of a subset of $\mathbf{N}$ with no more than two elements in any geometric progression. Commented Jul 1, 2014 at 17:47
• arxiv.org/pdf/1311.4331v1.pdf may also be of some interest. Commented Jul 2, 2014 at 0:47

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.

• You might as well use odd x which are multiples of 25 and are greater than n/4 instead of waiting till n/2. You can treat other multiples of squares this way as well, especially the odd multiples of 9 greater than n/4 and less than 9n/25. Commented Jul 2, 2014 at 5:24