covers of $Z^\infty$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:39:49Z http://mathoverflow.net/feeds/question/37449 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37449/covers-of-z-infty covers of $Z^\infty$ Mark Sapir 2010-09-02T01:11:38Z 2010-11-12T05:11:30Z <p>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: <a href="http://front.math.ucdavis.edu/1008.3868" rel="nofollow">http://front.math.ucdavis.edu/1008.3868</a> . </p> http://mathoverflow.net/questions/37449/covers-of-z-infty/37481#37481 Answer by Dmitri for covers of $Z^\infty$ Dmitri 2010-09-02T10:05:28Z 2010-09-02T11:44:45Z <p>The answer is NO even if we replace $4$ by $3$. Let me sketch a proof. This is based upon the following lemma.</p> <p>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: </p> <p>$$r(S,k)=sup_{X\subset \mathbb Z^k}\frac{Vol(X)}{Vol(X1)}.$$</p> <p>I claim that for a fixed $S$, $lim_{k\to \infty}r(S,k)=0$.</p> <p>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)&lt;\frac{1}{2n}$ and let us deduce the contradiction. </p> <p>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)&lt;\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$.</p> <p>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.</p> <p>As for the proof of the lemma, I think, it should be rather standard.</p> http://mathoverflow.net/questions/37449/covers-of-z-infty/45790#45790 Answer by Justin Moore for covers of $Z^\infty$ Justin Moore 2010-11-12T05:11:30Z 2010-11-12T05:11:30Z <p>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 &lt; 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 &lt; 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 &lt; k)$: if $b = \{m_i : i &lt; 2k\}$, then set $a_i = \{m_j : i \leq j &lt; i+k\}$.</p>