The n-Category Café

Last time we discovered that when $N$ is an odd prime, the curve divides up into $\frac{N-1}{2}$ blocks, corresponding to the elements of the projective group of units. Each block consists of a central $N$-gon with a fraction of the form $\frac{u}{0}$, surrounded by the $N$ possible $N$-gons whose fractions are of the form $\frac{p}{v}$, where $u$ and $v$ are units, $uv=1$ and $p$ can be anything.

However, when $N$ is not prime, things aren’t quite so simple. I’ll makes some general remarks, and then we’ll look at a few examples to get the idea.

Some General Remarks

The first and nicest thing to say is that the group of projective units acts freely on the tiles, and so we can always split up $X(N)$ into identical separate blocks, one for each projective unit, with each block consisting of whole tiles. We never need to divide a tile between two blocks, or identify one part of a tile with another part of the same tile, or anything like that.

• For suppose a unit $u$ stabilises some fraction $\frac{p}{q}$, that is, $\left(\begin{array}{cc}v& 0\\ 0& u\end{array}\right)\left(\begin{array}{c}p\\ q\end{array}\right)=\left(\begin{array}{c}p\\ q\end{array}\right)$. Then we have $vp=p$ and $uq=q$. (We could also have $vp=-p$ and $uq=-q$, but then we could just use $-u$ instead of $u$.) But $v=\frac{1}{u}$, so, multiplying the first equation by $u$, we have $p=up$.

Lifting up to the integers, this implies $up=aN+p$ and $uq=bN+q$ for some $a$ and $b$, hence $u=\frac{aN}{p}+1$ and $u=\frac{bN}{q}+1$. Equating the two formulas for $u$, and multiplying by $pq$, we get $aNq=bNp$, so $aq=bp$. Now, as we said when introducing mod-$N$-reduced fractions, $p$ and $q$ cannot share any factors that are factors of $N$. But $aq=bp$. So any factors of $N$ that are in $q$ must be in $b$, since they have to appear on the RHS somewhere, and they cannot be in $p$. Hence in $\frac{bN}{q}$, any factors of $N$ that are removed by its division by $q$ will be restored by the multiplication by $b$, so $\frac{bN}{q}$ is actually an integer multiple of $N$, hence is $0$ mod $N$. Since $u=\frac{bN}{q}+1$, this gives $u=1$ mod $N$. QED •

The second, and also very nice, thing to say is that, to get a block that includes one fraction from each orbit of the projective group of units—which is what we need if our blocks are to reflect that action and also join up to make the whole surface—we don’t need to go very far out from the central point with denominator $0$. To be precise: we can construct one block to consist of all the fractions with denominator $1$ and some of the fractions in contact with them, and nothing more.

• The argument goes like this: first, any two adjacent fractions must have mutually coprime denominators. Remember that two fractions $\frac{a}{b}$ and $\frac{c}{d}$ are adjacent iff $\mid ad-bc\mid =1$, and obviously this can’t happen if $b$ and $d$ share any factor larger than $1$. Second, by the mediancy relations, if $\frac{a}{b}$ is adjacent to $\frac{p}{q}$, then the other fractions adjacent to $\frac{p}{q}$ will all be of the form $\frac{a+mp}{b+mq}$ for some $m$. But since $b$ and $q$ are coprime relative to $N$, the numbers $b+mq$ must include a unit of ${\mathbb{Z}}_N$ among them. The action of the inverse of this unit on $X(N)$ will then carry the fraction with that unit denominator to a fraction with denominator $1$, and hence carry the adjacent fraction, $\frac{p}{q}$, to a fraction adjacent to a fraction with denominator $1$. So every orbit contains, among its elements, a fraction which is adjacent to a fraction with denominator $1$, and when picking representatives of our orbits to form one of the blocks of $X(N)$, we need only pick fractions with denominator $1$ and (some of the) fractions adjacent to fractions with denominator $1$. (In fact, the latter set includes the former set!) All other blocks will then be images of that block under the action of the projective group of units. •

So the blocks can be constructed with a certain simplicity—we don’t need to construct blocks with long, wandering tendrils or with parts inside other blocks or anything like that.

Next, to add a bit more detail and perhaps give a feel for the way this works out in practice, I’ll give a detailed example of orbits for one $N$, and then we’ll calculate the numbers of orbits in the general case, and then I’ll give a few more examples.

The Blocks for Non-Prime $N$

Start with $N$ is $15$. ($15$? Why? Because this is the smallest $N$ with at least two prime factors, both larger than $2$ and not the same as each other—which ensures that it’s interesting, but not too interesting.)

For $N=15$, the units are $1$, $2$, $4$, $7$, $8$, $11$, $13$ and $14$, so for representative of projective units (i.e. mod $\{1,-1\}$) we can just take the first four of these. Corresponding to these are the four matrices $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$, $\left(\begin{array}{cc}8& 0\\ 0& 2\end{array}\right)$, $\left(\begin{array}{cc}4& 0\\ 0& 4\end{array}\right)$, $\left(\begin{array}{cc}13& 0\\ 0& 7\end{array}\right)$.

First, to get our bearings, we’ll look at just the orbits of denominators. In other words, we’ll look at the orbits of the integers mod $15$ mod $\{1,-1\}$ under multiplication by the projective units. Then we’ll look at the orbits of fractions themselves, corresponding to faces.

As I mentioned last time, these orbits correspond to factors of $N$: in this case

$1$
$3$
$5$
$15$

(Of course, $15=0$ mod $15$.)

The orbits of denominators are what we get when multiplying each of these by each of the four units, viz. (after eliminating duplicates):

$1\to 1,2,4,7$
$3\to 3,6$
$5\to 5$
$0\to 0$

(e.g. $5\cdot 7=35\equiv 5$, $3\cdot 2=6$, $3\cdot 4=12\equiv 3$, etc).

What about the orbits of fractions (i.e. faces of the tiling)? For the sake of showing the full pattern, I’ll give a big table of all of them, grouped by orbit of denominators. In the tables below, each orbit occupies a column. To the left, I’ve put the matrix corresponding to the appropriate element of the projective group of units.

Orbits of denominator $1$

There are $15$ of these:

$\begin{array}{|cccccccccccccccc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{0}{1}& \frac{1}{1}& \frac{2}{1}& \frac{3}{1}& \frac{4}{1}& \frac{5}{1}& \frac{6}{1}& \frac{7}{1}& \frac{8}{1}& \frac{9}{1}& \frac{10}{1}& \frac{11}{1}& \frac{12}{1}& \frac{13}{1}& \frac{14}{1}\\ \left(\begin{array}{cc}8& 0\\ 0& 2\end{array}\right)& \frac{0}{2}& \frac{8}{2}& \frac{1}{2}& \frac{9}{2}& \frac{2}{2}& \frac{10}{2}& \frac{3}{2}& \frac{11}{2}& \frac{4}{2}& \frac{12}{2}& \frac{5}{2}& \frac{13}{2}& \frac{6}{2}& \frac{14}{2}& \frac{7}{2}\\ \left(\begin{array}{cc}4& 0\\ 0& 4\end{array}\right)& \frac{0}{4}& \frac{4}{4}& \frac{8}{4}& \frac{12}{4}& \frac{1}{4}& \frac{5}{4}& \frac{9}{4}& \frac{13}{4}& \frac{2}{4}& \frac{6}{4}& \frac{10}{4}& \frac{14}{4}& \frac{3}{4}& \frac{7}{4}& \frac{11}{4}\\ \left(\begin{array}{cc}13& 0\\ 0& 7\end{array}\right)& \frac{0}{7}& \frac{13}{7}& \frac{11}{7}& \frac{9}{7}& \frac{7}{7}& \frac{5}{7}& \frac{3}{7}& \frac{1}{7}& \frac{14}{7}& \frac{12}{7}& \frac{10}{7}& \frac{8}{7}& \frac{6}{7}& \frac{4}{7}& \frac{2}{7}\\ \hline\end{array}$

Orbits of denominator $3$

There are $5$ of these:

$\begin{array}{|cccccc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{1}{3}& \frac{2}{3}& \frac{4}{3}& \frac{5}{3}& \frac{8}{3}\\ \left(\begin{array}{cc}8& 0\\ 0& 2\end{array}\right)& \frac{8}{6}& \frac{1}{6}& \frac{2}{6}& \frac{10}{6}& \frac{4}{6}\\ \left(\begin{array}{cc}4& 0\\ 0& 4\end{array}\right)& \frac{11}{3}& \frac{7}{3}& \frac{14}{3}& \frac{10}{3}& \frac{13}{3}\\ \left(\begin{array}{cc}13& 0\\ 0& 7\end{array}\right)& \frac{13}{6}& \frac{11}{6}& \frac{7}{6}& \frac{5}{6}& \frac{14}{6}\\ \hline\end{array}$

Orbits of denominator $5$

There are $3$ of these:

$\begin{array}{|cccc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{1}{5}& \frac{2}{5}& \frac{3}{5}\\ \left(\begin{array}{cc}8& 0\\ 0& 2\end{array}\right)& \frac{7}{5}& \frac{14}{5}& \frac{6}{5}\\ \left(\begin{array}{cc}4& 0\\ 0& 4\end{array}\right)& \frac{4}{5}& \frac{8}{5}& \frac{12}{5}\\ \left(\begin{array}{cc}13& 0\\ 0& 7\end{array}\right)& \frac{13}{5}& \frac{11}{5}& \frac{9}{5}\\ \hline\end{array}$

Orbits of denominator $15$ (aka $0$)

There is just one orbit here:

$\begin{array}{|cc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{1}{0}\\ \left(\begin{array}{cc}8& 0\\ 0& 2\end{array}\right)& \frac{8}{0}\\ \left(\begin{array}{cc}4& 0\\ 0& 4\end{array}\right)& \frac{4}{0}\\ \left(\begin{array}{cc}13& 0\\ 0& 7\end{array}\right)& \frac{13}{0}\\ \hline\end{array}$

Observe that there are $15$ orbits based on denominator $1$, $5$ orbits based on denominator $3$, $3$ orbits based on denominator $5$, and $1$ orbit based on denominator $0$, aka $15$. Or, in other words, there are $\frac{N}{d}$ orbits based on denominator $d$, for each $d\mid N$. It would be be nice if this was generally true. Is it? …

Numbers of Orbits

Well, almost. It’s true for squarefree $N$ (i.e. with no repeated prime factors). If there are higher powers of a prime in $N$, it needs a little adjusting.

So, generally, how many orbits are there for a given factor $d\mid N$?

I’d like to do the calculation, but it’s a bit involved, so I’ll just give the final answer here, and put the calculations at the end.

Suppose that the prime decomposition of $N$ is $N={\prod }_i{p}_i^{n_i}$. Suppose we want to know the number of orbits based on a factor $d\mid N$. (That is, with denominator equal to some projective unit times $d$). Let the prime composition of $d$ be given by $d={\prod }_i{p}_i^{m_i}$. Then the number of orbits is the product of a factor for each prime, viz.:

For each $i$, a factor of $\begin{array}{c}{p}_i^{n_i-m_i}\\ p_i^{n_i-m_i}-p_i^{n_i-m_i-1}\\ p_i^{n_i-m_i}\end{array}\}$ if $\{\begin{array}{c}{m}_i=0\\ 0<m_i<n_i\\ m_i=n_i\end{array}$.

Examples of Orbits in the Case of Higher Powers of Primes

Let’s take a look at a couple of examples of higher powers of primes.

For example, $8=2^3$, so we have one prime ($2$), we have $n_1=3$, and $m_1$ can be $0$, $1$, $2$, or $3$, giving the following numbers of orbits for corresponding factors:

$\begin{array}{cc}\mathrm{factor}& \mathrm{orbits}\\ 1& 2^{3-0}=8\\ 2& 2^{3-1}-2^{3-1-1}=2\\ 4& 2^{3-2}-2^{3-2-1}=1\\ 0& 2^{3-3}=1\end{array}$

Likewise, for $9=3^2$ we expect:

$\begin{array}{cc}\mathrm{factor}& \mathrm{orbit}\\ 1& 3^{2-0}=9\\ 3& 3^{2-1}-3^{2-1-1}=2\\ 0& 3^{2-2}=1\end{array}$

To check this, let’s do the same exercise as we did for $N=15$, but this time for $N=8$ and $N=9$.

For $N=8$:

The projective units are $\{1,3\}$. Convenient matrices are $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$ and $\left(\begin{array}{cc}3& 0\\ 0& 3\end{array}\right)$. The factors are $\{1,2,4,8\}$.

Orbits of denominator $1$:

$\begin{array}{|ccccccccc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{0}{1}& \frac{1}{1}& \frac{2}{1}& \frac{3}{1}& \frac{4}{1}& \frac{5}{1}& \frac{6}{1}& \frac{7}{1}\\ \left(\begin{array}{cc}3& 0\\ 0& 3\end{array}\right)& \frac{0}{3}& \frac{3}{3}& \frac{6}{3}& \frac{1}{3}& \frac{4}{3}& \frac{7}{3}& \frac{2}{3}& \frac{5}{3}\\ \hline\end{array}$

Orbits of denominator $2$:

$\begin{array}{|ccc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{1}{2}& \frac{3}{2}\\ \left(\begin{array}{cc}3& 0\\ 0& 3\end{array}\right)& \frac{5}{2}& \frac{7}{2}\\ \hline\end{array}$

Orbits of denominator $4$:

$\begin{array}{|cc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{1}{4}\\ \left(\begin{array}{cc}3& 0\\ 0& 3\end{array}\right)& \frac{3}{4}\\ \hline\end{array}$

Orbits of denominator $8$ (aka $0$):

$\begin{array}{|cc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{1}{0}\\ \left(\begin{array}{cc}3& 0\\ 0& 3\end{array}\right)& \frac{3}{0}\\ \hline\end{array}$

And for $N=9$:

The projective units are $\{1,2,4\}$. We can represent these with matrices $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$, $\left(\begin{array}{cc}5& 0\\ 0& 2\end{array}\right)$ and $\left(\begin{array}{cc}7& 0\\ 0& 4\end{array}\right)$. The factors of $9$ are of course $1$, $3$ and $9$, and here are the corresponding orbits:

Orbits of denominator $1$:

$\begin{array}{|cccccccccc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{0}{1}& \frac{1}{1}& \frac{2}{1}& \frac{3}{1}& \frac{4}{1}& \frac{5}{1}& \frac{6}{1}& \frac{7}{1}& \frac{8}{1}\\ \left(\begin{array}{cc}5& 0\\ 0& 2\end{array}\right)& \frac{0}{2}& \frac{5}{2}& \frac{1}{2}& \frac{6}{2}& \frac{2}{2}& \frac{7}{2}& \frac{3}{2}& \frac{8}{2}& \frac{4}{2}\\ \left(\begin{array}{cc}7& 0\\ 0& 4\end{array}\right)& \frac{0}{4}& \frac{7}{4}& \frac{5}{4}& \frac{3}{4}& \frac{1}{4}& \frac{8}{4}& \frac{6}{4}& \frac{4}{4}& \frac{2}{4}\\ \hline\end{array}$

Orbits of denominator $3$:

$\begin{array}{|ccc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{1}{3}& \frac{2}{3}\\ \left(\begin{array}{cc}5& 0\\ 0& 2\end{array}\right)& \frac{4}{3}& \frac{8}{3}\\ \left(\begin{array}{cc}7& 0\\ 0& 4\end{array}\right)& \frac{7}{3}& \frac{5}{3}\\ \hline\end{array}$

Orbits of denominator $9$ (aka $0$):

$\begin{array}{|cc|}\hline \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)& \frac{1}{0}\\ \left(\begin{array}{cc}5& 0\\ 0& 2\end{array}\right)& \frac{5}{0}\\ \left(\begin{array}{cc}7& 0\\ 0& 4\end{array}\right)& \frac{7}{0}\\ \hline\end{array}$

So our formula is confirmed: the extreme cases ($1$ and $8$ for $N=8$, and $1$ and $9$ for $N=9$) had $\frac{N}{d}$ orbits, but the intermediate cases ($2$ and $4$ for $N=8$, and $3$ for $N=9$ had, respectively, $2$, $1$ and $1$ fewer orbits than expected, corresponding to the term $p_i^{n_i-m_i-1}$.

How did we get there?

Calculation of the Numbers of Orbits

Finally, we’ll calculate those formulas we gave above. How many orbits are there for a given $d\mid N$?

• Well, the number of orbits is the total number of fractions whose denominators are multiples of $d$ by (projective) units, divided by the total number of projective units. And the number of fractions is the number of possible denominators, multiplied by the number of possible numerators. So let’s go through these in turn.

• First, the projective units. Suppose the prime decomposition of $N$ is $N={\prod }_i{p}_i^{n_i}$. There are $p_i^{n_i}-p_i^{n_i-1}$ elements in the unit group of ${\mathbb{Z}}_{p_i^{n_i}}$, and the unit group of ${\mathbb{Z}}_N$ is the direct product of these, so there are ${\prod }_i(p_i^{n_i}-p_i^{n_i-1})$ elements in the unit group, and half this projectively.

To summarise: for each $i$, a factor of $p_i^{n_i}-p_i^{n_i-1}$.

• Secondly, how many denominators? Although the denominators will all be multiples of $d$ by a projective unit, we can’t simply take the total number of projective units, because some multiples will be the same as each other. E.g. see above for $N=15$, $d=5$, where multiplying $5$ by the various projective units always gives the same result, viz. $5$. So instead, we’ll consider all multiples $kd$ of $d$, $0\le k\le \frac{N}{d}$, and eliminate the ones we don’t want, namely the ones that are larger factors of $N$ than $d$ itself is.

What we want is for $k$ to not contain any factors of $N$ (hence, a fortiori, no prime factors of $N$). Since some of these factors may already have been “used up” by $d$—mod $N$, $kd$ obviously can’t contain more prime factors than are already present in $N$—what we really want is for $k$ to be coprime to $\frac{N}{d}$, i.e. a unit in ${\mathbb{Z}}_{\frac{N}{d}}$.

So, let the prime decomposition of $d$ be $d={\prod }_i{p}_i^{m_i}$, where $m_i\le n_i$. Then $\frac{N}{d}={\prod }_i{p}_i^{n_i-m_i}$, and in this case the number of denominators that we want to keep is ${\prod }_{i:m_i<n_i}(p_i^{n_i-m_i}-p_i^{n_i-m_i-1})$. (Notice the restriction in the product to the values of $i$ with $m_i<n_i$. Obviously if $m_i=n_i$ then the corresponding factor in $\frac{N}{d}$, viz. $p^{n_i-m_i}=p^0=1$, is trivial, and gives $1$ unit, not $p^0-p^{-1}$ units!) Actually, since we are working projectively, we should halve the number of denominators. This will cancel the factor of $\frac{1}{2}$ in the number of projective units.

To summarise: for each $i$, a factor of $\begin{array}{c}{p}_i^{n_i-m_i}-p_i^{n_i-m_i-1}\\ 1\end{array}\}$ if $\{\begin{array}{c}{m}_i<n_i\\ m_i=n_i\end{array}$.

• Finally, for the numerators. These need to be coprime to $d$, but otherwise can be anything $\le N$. So, e.g., if $d$ is even, we remove all multiples of $2$ (of which there are $\frac{N}{2}$); if $d$ is a multiple of $3$, we remove the multiples of $3$ (of which there are $\frac{N}{3}$); and if $d$ is a multiple of both $2$ and $3$ then we remove both but, by an inclusion-exclusion principle, need to add back on the multiples of both (of which there are $\frac{N}{6}$), which will have got removed twice. In short, for each prime appearing in the decomposition of $d$, i.e. each $p_i$ with $m_i>0$, we have a factor of $(p_i^{n_i}-p_i^{n_i-1})$; and for each prime $p_i$ with $m_i=0$, we have a factor of $p_i^{n_i}$ (we don’t need to specially remove multiples of these, since they don’t appear in the decomposition of $d$).

To summarise the numerators: for each $i$, a factor of $\begin{array}{c}{p}_i^{n_i}\\ p_i^{n_i}-p_i^{n_i-1}\end{array}\}$ if $\{\begin{array}{c}{m}_i=0\\ m_i>0\end{array}$.

Let’s put all this together. We’ll look at the case for a single prime factor $p_i$, since for multiple prime factors we can simply multiply the single-factor results together.

There are three cases: $m_i=0$, $m_i=n_i$, and $0<m_i<n_i$. We’ll look at these in turn.

If $m_i=0$, we have $m_i<n_i$, giving a factor of $(p_i^{n_i-m_i}-p_i^{n_i-m_i-1})$ for the denominator. We have a factor of $p_i^{n_i}$ from the numerator, and divide by a factor of $(p_i^{n_i}-p_i^{n_i-1})$ for the units. (There are factors of $\frac{1}{2}$ because we are doing things projectively, but they cancel.) So we get $\frac{(p_i^{n_i-m_i}-p_i^{n_i-m_i-1})p_i^{n_i}}{(p_i^{n_i}-p_i^{n_i-1})}=\frac{p_i^{n_i-m_i-1}}{p_i^{n_i-1}}{p}^{n_i}=p^{n_i-m_i}$.

At the opposite extreme, for $m_i=n_i$, we have a factor of $1$ for the denominators; we have $m_i>0$, giving $(p_i^{n_i}-p_i^{n_i-1})$ for the numerators, and again dividing by $(p_i^{n_i}-p_i^{n_i-1})$ for the units. So we get $\frac{1\cdot (p_i^{n_i}-p_i^{n_i-1})}{(p_i^{n_i}-p_i^{n_i-1})}=1=p^{n_i-m_i}$ (since $n_i-m_i=0$).

For squarefree $N$, where $n_i=1\forall i$, these are the only cases we need consider, so we always have a factor of $p^{n_i-m_i}$, or in other words, the number of orbits is $\frac{N}{d}$.

However, in other cases, we will have examples of $0<m_i<n_i$. For these cases, we have $(p_i^{n_i-m_i}-p_i^{n_i-m_i-1})$ for the denominators, $(p_i^{n_i}-p_i^{n_i-1})$ for the numerators, and divide by $(p_i^{n_i}-p_i^{n_i-1})$ for the units, giving a factor of $(p_i^{n_i-m_i}-p_i^{n_i-m_i-1})$ in the number of orbits. •

To summarise our final result:

For each $i$, a factor of $\begin{array}{c}{p}_i^{n_i-m_i}\\ p_i^{n_i-m_i}-p_i^{n_i-m_i-1}\\ p_i^{n_i-m_i}\end{array}\}$ if $\{\begin{array}{c}{m}_i=0\\ 0<m_i<n_i\\ m_i=n_i\end{array}$.

Well, goshdarn it, I’ve run out of time again, and no pretty pictures yet. I’ll finish off this section next time. For now, I’ll leave you with the following view of the $N=15$ case to ponder. Look at how the denominators are distributed around the central face.