Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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: http://front.math.ucdavis.edu/1008.3868 .

share|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
add comment

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|improve this answer
2  
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
2  
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
show 7 more comments

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|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: mathoverflow.net/questions/37529/covers-of-zk –  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
add comment

Your Answer

 
discard

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

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