Is this a known combinatorial problem?

Question

Let $M\subset\mathbb{N}$ be a finite set. For every positive integer $n$ set $$D_n(M)=\{W\subset \mathbb{N} \text{ finite }|\ \forall\ i=0,\ldots,n-1\ \exists\ w\in W: w\in M+i\},$$ where $M+i=\{m+i|\ m\in M\}$. I would like to understand $$d_n(M)=Min\{|W|\ | \ W\in D_n(M)\}.$$ I am mainly interested in the asymptotic behaviour of the $d_n(M)$'s. So I would like to know $$d(M)=\lim_{n\to\infty}\frac{d_n(M)}{n}.$$

For example, for $M=\{1,2\}$ we have $(d_1(M),d_2(M),\ldots)=(1,1,2,2,3,3,\ldots)$ and so $d(M)=\frac{1}{2}$.

My question is, if this is (related to) a known combinatorial problem? It seems a fairly natural problem to me, so I could well imagine that it has been treated in the literature. I encountered it when trying to explicitly compute some value in an algebraic-geometric example.

I would like to know things like, is the sequence of first differences $\Delta d_n(M)=d_n(M)-d_{n-1}(M)$ always periodic?

Answer 1

Yes this is a known combinatorial problem. You should look into the literature of covering or tiling groups by translates of a finite set. Your function $d(M)$ is commonly known as the "covering density". Newman called it "codensity" in his article "Complements of finite sets of integers", Michigan Math J 14 (1967), 481–486.

In particular it is true that there is a periodic covering achieving the covering density, from which I believe your observation follows. This was proved in

W. M. Schmidt and D. M. Tuller, "Covering and packing in $\mathbb Z^n$ and $\mathbb R^n$ I", Monatsh Math 153 (2008), 265–281

and also in section 5 of

B. Bollobas, S. Janson, O. Riordan, "On covering by translates of a set", Random Structures Algorithms 38:1-2 (2011), 33–67.

The sets which achieve $d(M)=\frac{1}{|M|}$ are the ones which tile $\mathbb Z$ by translations, and recognizing such sets is a notorious problem. I hope this helps.