MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ where each $U^i$ consists of uniformly bounded $\lambda$-disjoint sets $U_j^i$ ("$\lambda$-disjoint" means $dist(U_j^i, U_l^i)\ge \lambda$ for every $i,j\not=l$), $\lambda$ is fixed, $>1$?

In, we show (Lemma 3.7) that for $k<2^{\lambda-1}$, the minimal $c$ is $k$. The question is what happens for $k\ge 2^{\lambda-1}$.

Update: The answer is not known even if $\lambda=3$.

share|cite|improve this question
Maybe you can clarify the question. Can the constant implicit in "uniformly bounded" depend on $k$? I'm guessing that if it can't, you're left with your previous question. – Peter Shor Sep 2 '10 at 22:42
Yes, the "uniformly bounded" constant can depend on $k$. The number of collections of 4-disjoint sets should be independent on $k$. – Mark Sapir Sep 2 '10 at 22:58
In line 4 there is a typo, where it should read $\lambda$ instead of $4$. – Gjergji Zaimi Sep 7 '10 at 14:00
Thanks, Gjergji, I've fixed that. – Mark Sapir Sep 7 '10 at 17:44
Actually for $\lambda=4$ the answer is also unknown. – Mark Sapir Sep 21 '10 at 2:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.