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

I wonder if this has been studied:

What is the fewest number of unit cubes from which one can build an $n$-toroid?

The cubes must be glued face-to-face, and the boundary of the resulting object should be topologically equivalent to an $n$-torus, by which I mean a genus-$n$ handlebody in $\mathbb{R}^3$ (as per Kevin Walker's terminological correction). For example, 8 cubes are needed to form a 1-toroid:
           CuboidTorus1
And it seems that 13 cubes are needed for a 2-toroid:
           CuboidTorus2
I know how intricate is the analogous question for minimizing the number of triangles from which one can build a torus (cf. Császár's Torus), but I am hoping that my much easier question has an answer for arbitrary $n$. Thanks for ideas and/or pointers!

Addendum. Here is Steve Huntsman's 20-cube candidate for genus-5:
           CuboidTorus5

share|improve this question
8  
Some terminological nitpicks: "n-torus" usually means "n-dimensional torus", not a genus n surface. The standard term for what you're talking about is "genus n handlebody" (assuming that the 3-dimensional context has already been established). Also, what exactly do you mean by "cuboid"? The Wikipedia article lists two different definitions, and the answer to your question will depend on which definition you intend. From your figures it appears that by "cuboid" you just mean "cube". –  Kevin Walker Jun 6 '12 at 2:58
3  
@Steve: Your 20-cube "6-torus" (the symmetric one) is actually a "5-torus", or rather a genus 5 handlebody. –  Kevin Walker Jun 6 '12 at 3:01
10  
The "very porous" cube of side $2L+1$ has $4L^3+9L^2+6L+1$ cubes and genus $2L^3+3L^2$. This gives an asymptotic bound of $2n$ to get a genus-$n$ handlebody. –  Marco Golla Jun 6 '12 at 10:45
3  
Presumably an approximately spherical object made of the same porous material would give a slightly better asymptotic bound. –  Tom Goodwillie Jun 6 '12 at 14:00
3  
A very porous approximation to a sphere is less efficient (fewer holes per cube) than a very porous cube. This may be easier to see in the $2$-dimensional version. –  Douglas Zare Jun 7 '12 at 7:50

1 Answer 1

up vote 18 down vote accepted

Theorem. Let $c(g)$ be the minimum number of cubes such that the boundary of some configuration of $c(g)$ cubes is a genus $g$ surface. Then $c(g)/g \to 2$ as $g \to \infty$.

Proof. We write $\chi(X)$ for the compactly supported Euler characteristic of $X$, i.e.,

$\chi(X) = \sum (-1)^i \dim H^i_c(X, \mathbb{Q})$.

Note this is not a homotopy invariant: the compactly supported Euler characteristic of $\mathbb{R}^n$ is $(-1)^n$. It does however have the property that for reasonable finite disjoint union decompositions, $X = \coprod X_i$, we have $\chi(X) = \sum \chi(X_i)$.

Let $H_g$ be a closed genus $g$ handle-body. Then $$\chi(H_g) = 1-g.$$

On the other hand, let $K$ be a configuration of cubes. We write $K^0, K^1, K^2, K^3$ for the sets of vertices, edges, squares, and cubes, respectively, and $k^0, k^1, k^2, k^3$ for their cardinalities. Then

$$\chi(K) = k^0 - k^1 + k^2 - k^3$$

We will count $k^0, k^1, k^2, k^3$ by looking at the interior of the $2 \times 2$ cube around each vertex. That is, abutting some vertex $v$, there is $1$ vertex, $6$ edges, $12$ faces, and $8$ cubes. More to the point, each $i$-dimensional face abuts $2^i$ vertices. We write $K_v$ to mean the configuration localized at $v$; we write $K^i_v$ for the set of $i$-dimensional faces which abut the vertex $v$, and $k^i_v$ for its cardinality. Thus:

$$\chi(K) = \sum_{v \in \mathbb{Z}^3} \sum_{i=0}^3 (-2)^{-i} \cdot k^i_v $$

so we estimate

$$\frac{\chi(K)}{k^3} = \frac{\sum_{v \in \mathbb{Z}^3} \sum_{i=0}^3 (-2)^{-i} \cdot k^i_v }{\sum_{v \in \mathbb{Z}^3} 2^{-3} \cdot k^3_v } \ge \min_{v \in \mathbb{Z}^3} \sum_i \frac{(-2)^{-i} \cdot k^i_v }{2^{-3} \cdot k^3_v }$$

The above inequality comes from the following fact: a (weighted) average is greater than the minimum term being averaged. Thus for any $a_i, b_i$ with $b_i > 0$, we have

$$\frac{\sum_i a_i}{\sum_i b_i} = \sum_i \frac{a_i}{b_i} \cdot \frac{b_i}{\sum b_i} \ge \min_i \frac{a_i}{b_i}$$

Now let us analyze the possibilities for the right hand quantity

$$\tau(K_v) := \frac{8}{k_v^3} \cdot \left(k_v^0 - \frac{k_v^1}{2} + \frac{k_v^2}{4} - \frac{k_v^3}{8} \right) $$

In fact, in the $2\times 2$ cube around a vertex, there are, up to symmetry, only 9 possible configurations of cubes whose boundary is (locally at that vertex) topologically a manifold: one each for every number of boxes other than 4, and for 4 boxes, the square, and the tripod configuration where, if say $v = (0,0,0)$, the cubes are the ones with most negative coordinates $(-1,-1,-1)$, $(-1, -1, 0)$, $(-1, 0, -1)$, and $(0, -1, -1)$. Note that the neighborhood of every point in the interior of a very porous solid is a tripod configuration.

It remains to compute in each of these cases the above quantity. For example, in the configuration $C_1$ when there is one cube, there is one vertex abutting the central one, three edges, three faces, and one cube. Thus this contributes

$$ \tau(C_1) = \frac{8}{1} \cdot \left(1 - \frac{3}{2} + \frac{3}{4} - \frac{1}{8} \right) = 1$$

We tabulate the remaining cases:

$$ \tau(C_2) = \frac{8}{2} \cdot \left(1 - \frac{4}{2} + \frac{5}{4} - \frac{2}{8} \right) = 0$$

$$ \tau(C_3) = \frac{8}{3} \cdot \left(1 - \frac{5}{2} + \frac{7}{4} - \frac{3}{8} \right) = -\frac{1}{3}$$

$$ \tau(C_4) = \frac{8}{4} \cdot \left(1 - \frac{5}{2} + \frac{8}{4} - \frac{4}{8} \right) = 0$$

$$ \tau(C_4') = \frac{8}{4} \cdot \left(1 - \frac{6}{2} + \frac{9}{4} - \frac{4}{8} \right) = -\frac{1}{2}$$

$$ \tau(C_5) = \frac{8}{5} \cdot \left(1 - \frac{6}{2} + \frac{10}{4} - \frac{5}{8} \right) = -\frac{1}{5}$$

$$ \tau(C_6) = \frac{8}{6} \cdot \left(1 - \frac{6}{2} + \frac{11}{4} - \frac{6}{8} \right) = 0$$

$$ \tau(C_7) = \frac{8}{7} \cdot \left(1 - \frac{6}{2} + \frac{12}{4} - \frac{7}{8} \right) = \frac{1}{7}$$

$$ \tau(C_8) = \frac{8}{8} \cdot \left(1 - \frac{6}{2} + \frac{12}{4} - \frac{8}{8} \right) = 0$$

Here, $C_4'$ is the tripod configuration. We conclude that

$$\frac{1-g(K)}{\# K^3} = \frac{\chi(K)}{\# K^3} \ge -\frac{1}{2}$$

hence $\# K^3 \ge 2g(K) - 2$.

On the other hand, for any family of configurations in which the fraction of $v$ with $K_v \sim C_4'$ -- i.e., the probability that (the neighborhood of a given cube is a very porous solid) -- tends to 1, the estimates above are sharp and $\# K^3 /g(K) \to 2$.

(An explicit calculation for the very porous cube appears in the comments above.) $\blacksquare$

share|improve this answer
    
By "$K_1$ lines" do you mean "$K_1$ edges"? –  Joseph O'Rourke Aug 8 at 13:09
    
yeah, where an 'edge' is a length 1 interval. I changed it. –  Vivek Shende Aug 8 at 14:40
    
Impressive analysis! Kudos! –  Joseph O'Rourke Aug 8 at 23:15

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.