covers of $Z^\infty$ - MathOverflow

covers of $Z^\infty$

2010-09-02T01:11:38Z

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 .

Answer by Dmitri for covers of $Z^\infty$

2010-09-02T10:05:28Z

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.

Answer by Justin Moore for covers of $Z^\infty$

2010-11-12T05:11:30Z

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\}$.