January | 2009 | ∑idiot's Blog

Archive for January, 2009

Non-Functorial

January 31, 2009

In other words, I’m hosed.

I’ve been thinking about a category of ‘abstract locally complete partitions’. Fix $M=m\times \mathbb{R}^n$ , a disjoint union of copies of $\mathbb{R}^n$ indexed by elements of the finite set $m$ . My category is then supposed to consist of pairs $(\rho,f)$ where $\rho$ is a finite collection of affine spaces, $A_{\rho}=\coprod_{i\in s}A_i$ , along with a partition, $\Lambda$ , of the indexing set $s$ , and $f:A_{\rho}\rightarrow M$ an affine (on each component) map which is non-locally-constant. I interchangeably let $\rho$ refer to the collection of spaces, or the partition on that collection of spaces.

To describe non-locally-constant, I must first remind you that I let my partition $\Lambda$ on $s$ induce a partition on $A_{\rho}$ where $x\sim y$ iff the component containing $x$ is equivalent to the component containing $y$ , mod $\Lambda$ . That is, all points in a component $A_i$ are considered equivalent, and two components are equivalent as determined by $\Lambda$ . Now $f$ being non-locally-constant means that there exists $x,y$ equivalent mod $\Lambda$ but with $f(x)\neq f(y)$ .

Now, given such an object $(\rho,f)$ in my category, I would like to reduce it to a more restricted type of complete locally affine partition. In particular, I would like to reduce it to the case where

There are no more than $m$ zero-dimensional affine spaces in $A_{\rho}$ , and no more than $m$ non-zero-dimensional affine spaces in $A_{\rho}$ .
If $A_i$ is a component of $A_{\rho}$ that is not zero-dimensional, then the $\Lambda$ -equivalence class of $i$ is just $i$ itself.
My map $f$ takes distinct zero-dimensional spaces in $A_{\rho}$ to distinct components of $M$ . Similarly for non-zero-dimensional spaces.

To complete the description of my big category, I need to describe the morphisms. A map $\alpha$ from $(\rho,f)$ to $(\rho',f')$ will be an affine map $\alpha:A_{\rho}\rightarrow A_{\rho'}$ such that $f'\circ \alpha=f$ and $\overline{\alpha(\rho)}\leq \rho'$ – a property I will now further clarify. My $\rho$ consists of a partition of the space $A_{\rho}$ . By $\alpha(\rho)$ , I mean the transitive closure of the relation on $A_{\rho'}$ where whenever $x\sim y$ in $A_{\rho}$ then $f(x)\sim f(y)$ in $A_{\rho'}$ . This process gives me an equivalence relation $\alpha(\rho)$ on $A_{\rho'}$ . Any time I have an equivalence relation $\sigma$ on a (disjoint union of) affine space(s), I let $\overline{\sigma}$ denote the finest coarsening of $\sigma$ that is “locally affine” – meaning equivalence classes are (disjoint unions of) affine subspaces, and all equivalence classes in a given component are parallel (technically, there’s probably a little more than that, but it’s good enough for now I guess). So now we have the meaning of $\overline{\alpha(\rho)}$ , and by $\overline{\alpha(\rho)}\leq \rho'$ , I simply mean that $\overline{\alpha(\rho)}$ is coarser than $\rho'$ (by which I mean the equivalence relation on $A_{\rho'}$ .

So allow me to recap. My $\alpha$ is an affine map with a property saying that an appropriate triangle commutes ( $f'\circ \alpha=f$ ), and the affine closure of the image of the partition for $\rho$ is coarser than the partition for $\rho'$ . Since $\rho'$ is a “complete” locally affine partition (any two points in the same component are in the same equivalence class), this also forces $\overline{\alpha(\rho)}$ to be “complete”.

Of course, I’m not mentioning that this category is really “a category object in the category of topological spaces”. So really I have a space of objects, a space of morphisms, and enough maps between them to make sense of things. I’ll continue not mentioning that, saving it for another day.

Now, like I said, I want to be reducing any $(\rho,f)$ in my big category to get it down to a particularly nice form. One of the main steps I had been relying on turns out to not be allowed, because it isn’t functorial. I hardly knew one could write down “obvious” maps that weren’t functorial, but I’ve apparently done so rather frequently lately.

So, what is this construction? Given $(\rho,f)$ , one step I want to take is to replace any subset of the components of $A_{\rho}$ that are (1) all related by the partition, and (2) all map to the same component of $M$ . I want to replace such a subset by the affine span (direct sum in the category of affine spaces) of the spaces in it. This seems entirely reasonable. Given a bunch of affine spaces, and a map to an affine space, I get, for free, a map from the direct sum of the original affine spaces. That’s what direct sums do.

However, since I have disjoint unions as targets of maps $\alpha$ , I run into trouble. Consider, for example, $(\rho,f)$ where the space $A_{\rho}$ consists of three disjoint points, the equivalence relation has them all equivalent, and $f$ sends them all to the same component. Consider $(\rho',f')$ the same three points, the same $f$ , but only two of the points are equivalent. The obvious map $\alpha$ has $\overline{\alpha(\rho)}\leq \rho'$ , and the triangle commutes by construction. Now, when I take affine spans as mentioned, I end up with a single space in $\rho$ (a plane, the affine span of 3 points), and two spaces in $\rho'$ (a line (the span of two points), and a point). That’s a problem, because I no longer know what to do with $\alpha$ . As I mentioned before, given a map from a bunch of affine spaces to a single affine space, I get a map from the affine span to the single space. However, given a map from a bunch of affine spaces to a bunch of affine spaces, I no longer get a map from the affine span to the same bunch of spaces (the single affine span, being connected, can only end up in one of the target spaces).

So that’s upsetting. It’s not even the only thing I’ve written down recently that wasn’t a functor. Back to the drawing board, as a fella says.

Posted in Work | Leave a Comment »

My Problem with 0

January 28, 2009

In my research recently, I’ve been debating between two setups for a category. My category is supposed to have, as objects, a finite set $s$ of spaces, a partition $\Lambda$ of $s$ , and a map from the disjoint union of those spaces to a space $M$ . I tend to bundle all of this information up into $\rho$ (for the finite set, it’s partition, and the collection of spaces) and $f$ (the map to $M$ ). In my situation, $M$ is a disjoint union of copies of $\mathbb{R}^n$ . The spaces I have in $\rho$ have, for a while, been affine spaces. But there’s also always been a question about maybe having them be vector spaces. The difference, of course, is the existence of 0.

There are a few ways to think about affine spaces. The least precise is to say it is a vector space that forgot where its 0 is. With this idea, a pointed affine space is (essentially) a vector space. Every affine space has an underlying vector space, and given two points in the affine space, you can find their difference, which will be a vector in the underlying vector space. Since differences are defined in a vector space, every vector space is (essentially) an affine space whose underlying vector space is the one you started with.

Now, I have this collection of spaces (either vector or affine) and an affine map $f$ to $M$ – that is, the map is affine (linear after a linear translation) on each space in $\rho$ . Since I have an equivalence relation $\Lambda$ (by abuse of notation) on my spaces in $\rho$ , I can take the transitive closure of the image, $f(\Lambda)$ , and get an equivalence relation on $M$ . I then have this process in mind where I convert this equivalence relation on $M$ to one of a particularly nice form, which I have been calling ‘locally affine.’ For more, see my earlier writeup.

Part of the process to convert an equivalence relation to one that is locally affine involves looking at pairs of points that are parallel to some linear subspace of (a component of) $M$ . For reasons that deserve to be called ‘continuity’, this is not a great procedure to do in $M$ . If two points are parallel to some line, and you wiggle the two points a little, there’s no reason to assume they are still parallel. And that messes some things up (at least, can, and seems to with what I’ve been hoping to do), or, if nothing else, makes them uglier. So what I’ve been trying to accomplish, or approximate, is to do the similar operations on my original $\rho$ in my category of ‘abstract’ locally affine partitions. I would like to convert the original $\rho$ to something pretty similar, staying in the category I’m defining while not changing the (locally affine coarsening of the) image of the equivalence relation too much.

It’s tempting to assume that my spaces in $\rho$ are affine spaces, because a big part of making the locally affine partitions above is taking affine spans of things. Taking the affine span of a vector space would give me an affine space, but that would mean I’ve changed categories (from a category using vector spaces to a category using affine spaces). But taking the affine space of affine spaces causes no such problem. The problem with using affine spaces is that sometimes I also want to take linear spans, which is not defined for affine spaces. Taking linear spans only works if you have a 0. Grr. I’m going to have to start being more clever, or more careless. I wish I knew which.

Posted in Work | Leave a Comment »

Counting Cards

January 3, 2009

Over the past few days my roommate and I have been working on a business card Menger sponge origami project. This was most recently inspired by Thomas Hull‘s fun book ‘Project Origami‘, but it’s quite possible I’d heard of the project before I found the book. I know that in Hull’s book he finds formulas for the number of cards it takes to make various iterations of the sponge, but I wanted to try to come up with them again on my own, and thought I’d share my process.

Let $F_n$ be the number of cards showing on each face of a level $n$ sponge (recalling that level 0 is just an ordinary cube). The exterior faces of the Menger sponge are Sierpinski carpets, and it’s pretty easy to determine that $F_0=1$ and $F_n=8\cdot F_{n-1}$ . This means $F_n=8^n$ .

Next, let $U_n$ be the number of cards needed to make a completely unpanelled level $n$ sponge. So $U_0=6$ , and to make a level $n$ sponge requires 20 level $n-1$ sponges, so $U_n=20\cdot U_{n-1}$ . This makes $U_n=20^n\cdot 6$ .

Now I’d like to determine the number of cards needed for what I’ll call ‘interior panelled’ sponges. Let $I_n$ denote the number of cards for such a level $n$ sponge. A level $n$ sponge consists of lots of little cubes, some of the faces of which are showing (not stuck against faces of other little cubes). Some of the showing faces occur on the very exterior of the sponge (on the faces of the encompassing cube, if you want). So ‘interior panelled’ would be all of the faces except these very exterior ones. There’s no such thing as an interior panelled level 0 sponge, so we start at level 1, counting $I_1$ as follows: Begin with an unpanelled level 1 sponge ( $U_1=20\cdot 6$ cards), and panel the two interior faces of each of the 12 ‘edge’ level 0 cubes. So $I_1=U_1+2\cdot 12=20\cdot 6 +2\cdot 12=144$ .

What about the next iteration for $I_n$ ? Well, there are 20 ‘interior panelled’ $n-1$ sponges, and you need to panel 2 of the exterior faces of each of the 12 ‘edge’ cubes. The exterior faces, recall, require $F_{n-1}$ cards to panel. So $I_n=20\cdot I_{n-1}+2\cdot 12\cdot F_{n-1}$ . Since we know $F_{n-1}=8^{n-1}$ , we can clean this formula up a little: $I_n=20\cdot I_{n-1}+24\cdot 8^{n-1}$ .

Now we’re almost done. The overall goal is to have a fully panelled level $n$ sponge. Let $P_n$ denote the number of cards required. Since a fully panelled level $n$ cube is an interior panelled level $n$ cube, along with exterior panelling, it’s easy to count. There are 6 exterior faces, each requiring $F_n=8^n$ cards to panel, so $P_n=I_n+6\cdot 8^n$ .

So we’re down to two formulas:

$\begin{array}{rcl}I_n &=& 20\cdot I_{n-1}+24\cdot 8^{n-1} \\ P_n &=& I_n+6\cdot 8^n\end{array}$

At this point, I checked Hull’s book, and noticed he had only one formula – one for $P_n$ . So how do we get rid of $I_n$ ?

Solve the second equation for $I_n$ , obtaining $I_n=P_n-6\cdot 8^n$ (and so also $I_{n-1}=P_{n-1}-6\cdot 8^{n-1}$ ). Now substitute these two formulas in their appropriate places in the formula above for $I_n$ . This gives

$P_n-6\cdot 8^n=20(P_{n-1}-6\cdot 8^{n-1})+24\cdot 8^{n-1}$

which we simplify to

$P_n=20\cdot P_{n-1}-6\cdot 8^n,$

obtaining the formula that Hull’s book has (hurray!).

Perhaps there’s something more than can be done to understand this formula though (and Hull does have remarks like this as well). I’d really like my recurrence formula for $P_n$ to have $(n-1)$ s showing up, instead of that $n$ in the power for 8. So write $P_n=20\cdot P_{n-1}-6\cdot 8\cdot 8^{n-1}$ . How can we interpret this formula geometrically, in terms of the sponge? Well, we see that to make a panelled level $n$ sponge, we make 20 level $n-1$ sponges, and then remove some bits. In particular, we remove the panelling on faces of cubes that come together – that’s where the $8^{n-1}$ comes from, it is, after all $F_{n-1}$ , the number of panels on a face of an $n-1$ sponge. How many faces come together? Well, each of the 8 corner cubes (that lonely 8 in $6\cdot 8\cdot 8^{n-1}$ ) is 3-valent, meaning there are three ‘edges’ hitting that cube. At each of these 3 edges, we have two ( $3\cdot 2=6$ , in $6\cdot 8\cdot 8^{n-1}$ ) panelled faces coming together, and we must remove all of that panelling.

So there you have it – a formula for the number of cards to build a level $n$ Menger sponge. If you’re interested in building one, start gathering up cards. While the level 0 sponge (a cube) requires only 12 cards, a level 1 sponge already requires 192 cards. The level 2 sponge, that my roommate and I built, took 3456 cards, and the next level would require a staggering 66,048 cards. I’m in no hurry to start making one of those.

Tags:menger sponge, origami, recursive, sequence
Posted in Play | Leave a Comment »

∑idiot's Blog

Archive for January, 2009

Non-Functorial

My Problem with 0

Counting Cards

Top Posts

Archives

About

Follow “∑idiot's Blog”