19
$\begingroup$

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.

$\endgroup$
14
  • 2
    $\begingroup$ You mean minimum, not maximum. $\endgroup$ – Richard Stanley Jul 1 '14 at 15:17
  • 2
    $\begingroup$ The $n/2$ upper bound holds even for progressions with integer coefficients: consider progressions with ratio 2 and odd initial values. $\endgroup$ – Emil Jeřábek Jul 1 '14 at 15:41
  • 4
    $\begingroup$ 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. $\endgroup$ – Lucia Jul 1 '14 at 15:53
  • 2
    $\begingroup$ 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. $\endgroup$ – Sean Eberhard Jul 1 '14 at 17:47
  • 4
    $\begingroup$ arxiv.org/pdf/1311.4331v1.pdf may also be of some interest. $\endgroup$ – Gerry Myerson Jul 2 '14 at 0:47
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Jul 2 '14 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.