Sign up ×

Is it possible to cover $Z^\infty$ (the infinite direct sum of $Z$'s with the $l_1$-metric) by a finite set of collections of subsets $U^0,...,U^n$ such that each collection $U^i$ consists of uniformly bounded sets $U_j^i$ that are 4-disjoint (the distance between any two subsets $U_j^i$, $U_k^i$ in each $U^i$ is at least 4)? The motivation is here: .

share|cite|improve this question
Can you state precisely what's here the distance between two subsets A and B? Is it $\inf_{a\in A,b\in B}d(a,b)$? (Or rather a Hausdorff distance?). – Pietro Majer Sep 2 '10 at 7:02
Yes, it is the inf. – Mark Sapir Sep 2 '10 at 7:14
Example: if we replace 4 by 2, then 2 collections $U^0, U^1$ is enough. Each $U_j^i$ consists of a point. A point belongs to $U^i$ ($i=0,1$) iff the sum of its coordinates is $i$ modulo 2. Clearly each $U^i$ is $2$-disjoint. – Mark Sapir Sep 2 '10 at 7:20

2 Answers 2

up vote 15 down vote accepted

The answer is NO even if we replace $4$ by $3$. Let me sketch a proof. This is based upon the following lemma.

Lemma. Fix $S>0$ and for an integer $k$ conisder in $\mathbb Z^k$ sets $X$ of diameter at most $S$. Denote by $Vol(X)$ the number of points in $X$ and denote by $X1$ the set of points of distance at most $1$ from $X$. Now let $\delta(S,k)$ be the supremum over all $X$ of diameter at most $S$ of the ratio:

$$r(S,k)=sup_{X\subset \mathbb Z^k}\frac{Vol(X)}{Vol(X1)}.$$

I claim that for a fixed $S$, $lim_{k\to \infty}r(S,k)=0$.

Let us skip the proof of the lemma and instead deduce the claim. Suppose by contradiction that the answer is positive. Then for every $k$ we will get a solution to the problem in $\mathbb Z^k$ with the fixed number of sets ($U^0,...,U^n$) such that each $U^i_j$ is of the diameter at most $S$. Now, chose such $k$ that $r(S,k)<\frac{1}{2n}$ and let us deduce the contradiction.

From Lemma it follows that the supremum of asimptotic density of each set $U^i$ in $\mathbb Z^k$ is less than $\frac{1}{n+1}$. Indeed, since the distance between different components of $U^i$ is $4$, every point of $U^i1$ that does not belong to $U^i$ is on distance one from at most one component of $U^i$. And lemma gives us the inequality (that should be understood as assymptotic in $\mathbb Z^k$) $$Vol(U^i)<\frac{1}{2n} Vol(U^i1)\le \frac{1}{2n}Vol(\mathbb Z^k)$$ Hence $\mathbb Z^k$ can not be covered by $U^0,...,U^n$.

It is clear where this proof breakes if we conisder $2$-disjoint sets. In this case one point of $U^i1$ can be on distance $1$ to many components of $U^i$ and the above inequality will not hold. But for $3$-disjoint sets this works.

As for the proof of the lemma, I think, it should be rather standard.

share|cite|improve this answer
At first I was confused because I thought that the size of a set X was the same thing as the number of points in it, Vol(X). I guess that by size you mean the supremum of d(x,y) over x,y∈X (perhaps “diameter” is a better name?). – Tsuyoshi Ito Sep 2 '10 at 11:30
In the inequality, I guess that you mean (1/2n)Vol(ℤ^k) instead of Vol(ℤ^k). Also, in the paragraph preceding it, I think that the key point is that the sets U^i_0 1, U^i_1 1, U^i_2 1, … are pairwise disjoint, hence Vol(U^i 1) = Vol(bigcup_j U^i_j 1) = ∑_j Vol(U^i_j 1). – Tsuyoshi Ito Sep 2 '10 at 11:39
Yes, Tsuyoshi, you are completely rightm thanks!! – Dmitri Sep 2 '10 at 11:40
@Dmitri: Thanks! – Tsuyoshi Ito Sep 2 '10 at 11:42
Thank you, Dmitri! – Mark Sapir Sep 2 '10 at 13:43

In fact there is also a negative answer (again with 3 instead of 4) in the case of the countably infinite sum of Z_2. View the direct sum with the $\ell_1$-metric as being the collection of all finite subsets of N with the metric which counts the symmetric difference. Let $[N]^k$ denote all of the k-element subsets of N. Observe that it suffices to demonstrate that, for each k, if $[N]^k$ is partitioned into finitely many pieces, then there is a piece of the partition containing a sequence $a_i$ $(i < k)$ such that $a_0$ is disjoint from $a_{k-1}$ (thus $a_0$ and $a_{k-1}$ are 2k units apart) and $|a_i \Delta a_{i+1}| = 2$ of all $i < k-1$. But this follows easily from Ramsey's theorem: given any such partition, there is a subset b of N of cardinality 2k, all of whose k element sets are in one piece of the partition (in fact we can find an infinite b if we like). From this one can now easily construct the sequence of $a_i$ $(i < k)$: if $b = \{m_i : i < 2k\}$, then set $a_i = \{m_j : i \leq j < i+k\}$.

share|cite|improve this answer
@Justin: This implies the answer to my question because ${\mathbb Z}_2^\infty$ as a metric space embeds into ${\mathbb Z}^\infty$. Now we can refer to your proof also in our paper with A. Dranishnikov. Also see the related question: – Mark Sapir Nov 12 '10 at 15:14
Right --- I thought that was clear. I'll think about the other question --- it is interesting. Cheers. – Justin Moore Nov 12 '10 at 17:32

Your Answer


