7
$\begingroup$

What is known about the minimal number $f(n)$ of geometric progressions needed to cover $\{1,2,\ldots,n\}$, as a function of $n$?

So a geometric progression can contain at most two primes. This automatically gives a lower bound on the minimal number $f(n)$ of geometric progressions needed to cover the integers $\{1,2,\ldots,n\}$, at least asymptotically, because of the prime number theorem. But this seems like a very crude bounding technique. I don't expect a closed-form formula for $f(n)$ is known. But what about its asymptotics? Can we say that $f(n) = \Theta (g(n))$ for some easy to understand function $g(n)$? Or give some fairly tight asymptotic upper and lower bounds for $f(n)$, even if there is an asymptotic growth rate gap between the two bounds?

UPDATE: From the link given in the comment, we have $f(n) \geq cn$ always for some constant $0 < c < 1$. And clearly $f(n) \leq n$. So then the interesting question seems to become, what is the best constant $d \leq 1$ we can find so that we can say $f(n) \leq dn$ holds for large enough $n$?

$\endgroup$
4
  • 2
    $\begingroup$ This is answered at Math Overflow $\endgroup$
    – Winther
    Commented Aug 5, 2015 at 22:32
  • $\begingroup$ @Winther Thanks for this, I'll update the question asking for an explicit non-trivial upper bound on $f(n)$, since it is obvious from your link that $f(n) = \Theta(n)$, and the lower bound is the more interesting but still an upper-bound $f(n) \leq cn$ for some $c < 1$ would be good. $\endgroup$
    – user2566092
    Commented Aug 5, 2015 at 22:40
  • $\begingroup$ For any two integers (e.g. $i$ and $n-i$) there exist a geometrical progression containing both of them (e.g. $i\left(\frac{n-i}{i}\right)^k$) so $f(n) \leq \frac{n}{2}$. Combinding this with the MO bound we have $0.3n\leq f(n) \leq 0.5n$ $\endgroup$
    – Winther
    Commented Aug 5, 2015 at 22:59
  • $\begingroup$ @Winther Thanks a second time, this shows the upper bound constant is less than or equal to $1/2$. The argument is basically straightforward, so hopefully better constants can be proved. $\endgroup$
    – user2566092
    Commented Aug 5, 2015 at 23:05

2 Answers 2

Reset to default
3
$\begingroup$

Just some thoughts.

By quoting the other question, I would say that the asymptotic depends on the distribution of $$ V(n) = \max_p \max\left\{m\in\mathbb{N}:p^m\mid n\right\} $$ that is concentrated around small values - the crude bound the OP mentions is equivalent to say that $V$ is concentrated around $1$, so we need many sequences (i.e. intersections between a geometric progression and $\{1,\ldots,n\}$) with small length ($1+1$).

I think this is useful: if the sequence $A=\{a_1,a_2,\ldots,a_l\}$ is the intersection between a geometric progression and $\{1,\ldots,100\}$, we have: $$\sum_{a\in A}V(a)\geq\binom{l}{2},$$ hence if $A_1,\ldots,A_k$ cover $\{1,\ldots, n\}$, we have $l_1+\ldots+l_k\geq n$ and: $$ \sum_{k}\sum_{a\in A_k} V(a) \geq \sum_k\binom{l_k}{2}, $$ so both the $L^1$ and $L^2$-norm of $(l_1,\ldots,l_k)$ are constrained.

My conjecture is that $k$ behaves like $\displaystyle\frac{n}{\mathbb{E}[V]+1}$, and it is quite trivial that $\mathbb{E}[V]=\Theta(1)$.

Stealing 6005's argument in the other question, no geometric progression can take more than two squarefree values, and since there are about $\frac{6}{\pi^2}n$ squarefree integers in $\{1,\ldots,n\}$, $k\geq\frac{3}{\pi^2}n$.

$\endgroup$
5
  • $\begingroup$ I am wondering if your ideas can be used to improve the concrete bound for the case of $n = 100$? Perhaps it will give $n = 37$? Unfortunately, I do not fully follow your arguments as I am inexperienced in analytic number theory, but I trust you will have some intuitions? Here is a link to the specific case: math.stackexchange.com/questions/1386381/… $\endgroup$
    – Colm Bhandal
    Commented Aug 7, 2015 at 12:44
  • 1
    $\begingroup$ @ColmBhandal: the interesting fact is that $\mathbb{E}[V]$ is around $1.65$ for $n=100$, so if my conjecture holds, $37$ progressions are both needed and sufficient to cover $[1,100]$. $\endgroup$
    – Jack D'Aurizio
    Commented Aug 7, 2015 at 15:21
  • $\begingroup$ Interesting consequence. Though I still would need a few hours study to get my head around the arguments made in favour of the conjecture. $\endgroup$
    – Colm Bhandal
    Commented Aug 8, 2015 at 0:50
  • $\begingroup$ perhaps you should have a look at the other thread. $37$ is out of the bound found so far. Does this throw doubt on the conjecture? $\endgroup$
    – Colm Bhandal
    Commented Aug 9, 2015 at 17:40
  • $\begingroup$ What is $\mathbb E[V]$? $\endgroup$
    – san
    Commented Oct 2, 2015 at 22:27
3
$\begingroup$

I wrote a program that computes $f(n)$ for larger $n$. It generates feasible geometric progressions (sets) and then uses simulated annealing to solve (near optimally) the resulting set covering problem. From other answers (like http://math.stackexchange.com/questions/1386381/cover-1-2-100-with-minimum-number-of-geometric-progressions) we already know that $f(100)=36$. For larger $n$, I was able to compute some good upper bounds on $f(n)$. I found that $f(1000) \leq 362$ and $f(10000) \leq 3620$. After seeing these numbers I suddenly realised that $f(n) \approx n/e$, which was rather surprising! I also submitted a sequence to OEIS: https://oeis.org/A309095

Here is my Java code to compute $f(n)$: https://pastebin.com/b23ugGZN

$\endgroup$
9
  • $\begingroup$ Dmitry do you have a link to your code, or a link to a deeper explanation of what you've done? $\endgroup$
    – Colm Bhandal
    Commented Jul 15, 2019 at 15:44
  • 2
    $\begingroup$ I have added a link to my Java code. Enjoy! $\endgroup$
    – Dmitry Kamenetsky
    Commented Jul 17, 2019 at 2:49
  • $\begingroup$ "Solve near optimally" means that the solution is achieved in optimal time or that it is nearly the optimal solution (probabilistic(?))? Or is it always the optimal solution? $\endgroup$
    – san
    Commented Jul 20, 2019 at 4:46
  • 1
    $\begingroup$ I used integer linear programming to confirm $f(1000)=362$ and $f(10000)=3621$. $\endgroup$
    – RobPratt
    Commented Jul 21, 2019 at 0:22
  • 1
    $\begingroup$ OK, yes. Optimal is 3620. I used the following formulation. Let $P$ denote the set of geometric progressions of length $\ge 3$. Let binary variable $x_p$ indicate whether progression $p\in P$ is selected, and let $s_i$ denote a slack variable for not covering element $i \in \{1,\dots,n\}$. (Pairs of uncovered elements can be covered with trivial 2-term progressions.) Then the problem is to minimize $\sum_p x_p + 0.5 \cdot \sum_i s_i$ subject to $\sum_{p: i \in p} x_p + s_i \ge 1$ for all $i$. $\endgroup$
    – RobPratt
    Commented Jul 22, 2019 at 21:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .