Maksymalna gęstość zestawu bez ustalonego wzoru

Question

Rozważmy zbiór skończony $S$ nieujemnych liczb całkowitych.

Jaka jest maksymalna naturalna gęstość nieskończonego podzbioru $\mathbb{Z}$ który nie zawiera żadnego tłumaczenia $S$?

Oczywiście będzie to zależeć od $S$, ale może istnieje prosty algorytm lub charakterystyka. Interesuje mnie również to samo pytanie w$\mathbb{Z}^k$.

Czy powyższe pytania zostały zbadane w jakiejkolwiek formie? Nie wymyśliłem zapytania, które nic nie zwraca.

Answer 1

Pytanie jest równoważne znalezieniu minimalnej gęstości pokrycia $\mathbb{Z}$ przez tłumaczenia $-S$. Ten problem został zbadany dla liczb całkowitych, a także dla innych grup; zobacz na przykład

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

Béla Bollobás, Svante Janson i Oliver Riordan, O pokryciu przekładami zbioru, https://doi.org/10.1002/rsa.20346