0
$\begingroup$

Let $A$, $B$ be two finite subsets of integers. We denote by $C(A, B)$ the minimum number of shifts of $A$ to cover $B$. More formally, it can be written as

$$ C(A, B)=\min\{|S|: S\subseteq B-A,~\text{such that}~B\subseteq A+S\}. $$

The trivial lower bound for $C(A, B)$ is $|B|/|A|$. Random simulations show the following upper bound

$$ C(A, B)\leq \frac{|B-A|}{|A|}. $$

I googled covering number stuff, but do not see this upper bound. Inductive argument should work, but I can not prove it. Anybody knows this result or ideas to prove it?

$\endgroup$
4
  • 1
    $\begingroup$ I get |B| as an upper bound, with B an interval and A sparse enough. Do you have conditions on A and B? $\endgroup$ Apr 17, 2014 at 4:48
  • 1
    $\begingroup$ The standard Ruzsa covering lemma says that $B$ can be covered by at most $|B-A|/|A|$ translates of the set $A-A$. I am pretty sure that you cannot replace here $A-A$ with $A$, although I cannot think of a counterexample off the top of my head. $\endgroup$
    – Seva
    Apr 17, 2014 at 6:58
  • 1
    $\begingroup$ Exercise 2.4.1 in Tao and Vu gives a counterexample, showing you need at least an extra log factor - take $B$ to be $[1,N]$ and $A$ to be a random subset of $[1,N]$, taking elements with probability $3/4$. $\endgroup$ Apr 17, 2014 at 8:54
  • $\begingroup$ In general, we indeed can not replace $A-A$ by $A$ in Ruzsa's covering lemma. It is not hard to figure out counter examples of the conjecture I posted for cyclic groups. Actually, I did not believe such an upper bound in the beginning. I tried some examples by hand and also did random simulations, all show that it holds in the setting of finite subsets of integers. I am thinking about Exercise 2.4.1 in Tao and Vu's book to see that does it really provide a counter example. $\endgroup$
    – Jiange Li
    Apr 17, 2014 at 18:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.