8
$\begingroup$

Consider a finite set $S$ of nonnegative integers.

What is the maximum natural density of an infinite subset of $\mathbb{Z}$ which does not contain any translation of $S$?

Of course, this will depend on $S$, but maybe there is a simple algorithm or characterization. I am also interested about the same question in $\mathbb{Z}^k$.

Have the above questions been researched in any form? I didn't come up with a search query which returns anything.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Have you tried searching in terms of 2-letter words rather than integers? Do you know the density of the greedy (translation-free) set? $\endgroup$
    – Yaakov Baruch
    Commented Nov 29, 2020 at 13:43
  • 1
    $\begingroup$ If you are okay with dilates of $S$, then this sounds like a Furstenberg-Katznelson-Weiss over the integers, which has been studied by Akos Magyar (see, for example, here: projecteuclid.org/euclid.dmj/1229530283 ). Maybe Magyar has studied undilated problem as well. $\endgroup$
    – Anurag Sahay
    Commented Nov 29, 2020 at 17:27

1 Answer 1

Reset to default
5
$\begingroup$

The question is equivalent to finding the minimum density of a covering of $\mathbb{Z}$ by translations of $-S$. This problem has been studied for the integers and also for other groups; see for example

Wolfgang M. Schmidt and David M. Tuller, Covering and packing in $\mathbb{Z}^n$ and $\mathbb{R}^n$, http://dx.doi.org/10.1007%2Fs00605-009-0099-x

Béla Bollobás, Svante Janson and Oliver Riordan, On covering by translates of a set, https://doi.org/10.1002/rsa.20346

Improve this answer
$\endgroup$
1

You must log in to answer this question.

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