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?


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.

  • $\begingroup$ Thanks. That's precisely the type of answer I was hoping for. $\endgroup$ – anonymous Jul 20 '13 at 7:37
  • $\begingroup$ @anonymous I'm curious to know what kind of algebro-geomtric problem led you to this question. Also, if you need any other specific information, I can expand the current answer, or you can get in touch with me via email. $\endgroup$ – Gjergji Zaimi Jul 21 '13 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.