Abstract Cyclotomy

We start this abstract chapter with a very practical or pragmatic consideration. Up to now it has been a secret, how the signs of our root expressions are determined. The pragmatic answer is: by computing trigonometric functions. After all, the Gaussian periods are sums of roots of unity $\zeta^k,$ given by \[\zeta^k = \cos(2k\pi/p) + \I\sin(2k\pi/p) \eqndot\] The values of the periods are real numbers, which we could immediately see in case of the 17-gon, and which will soon be generally proven. Hence, one has a reference value for every period by taking the sum of the particular cosines – the more so, if one is going to write a computer program anyway. The signs are simply set in that way as to get equality between the square root expressions and the corresponding sums of the cosines.

As an example we look at the preceding chapter and compute the periods $p_{3,0}$ and $p_{3,4}$ of the 17-gon. On the one hand you have \[p_{3,0} = \zeta^1 + \zeta^{16} = \cos(2\pi/17) + \cos(32\pi/17) = 1,86494 \eqncomma\] \[p_{3,4} = \zeta^{13} +\zeta^{4} = \cos(26\pi/17) + \cos(8\pi/17) = 0,18453 \eqncomma\] and on the other hand \[p_{3,0}^{\pm} = \tfrac{p_{2,0} + \sqrt{p_{2,0}^2 - 4p_{2,1}}}{2}\eqncomma\] \[p_{3,4}^{\pm} = \tfrac{p_{2,0} - \sqrt{p_{2,0}^2 - 4p_{2,1}}}{2}\eqncomma\] where the $\pm$ signals that the sign is not yet determined.

The expressions $p_{3,0}^{\pm}$ and $p_{3,4}^{\pm}$ can be computed numerically, by inserting the values of $p_{2,0}$ etc. Within the achievable precision we get either \[p_{3,0}^{\pm} = 1,86494 \quad \text{and} \quad p_{3,4}^{\pm} = 0,18453\] or \[p_{3,0}^{\pm} = 0,18453 \quad \text{and} \quad p_{3,4}^{\pm} = 1,86494 \eqndot\] In the first case we can keep the signs as they are, in the second case we have to exchange the signs.

This method has the additional benefit, that after each step one can verify that the square root expressions are correctly calculated. After chosing the proper sign, the value of the square root expression and of the cosine sum must be equal, within the limit of the achievable precision. Note that when the periods of a certain level are computed we already know the values of all periods of smaller level and can use them for the numerical calculation of the actual square root expression.

Main Theorem

We cannot avoid to imitate the style of common mathematical textbooks in what follows, specifying at first a theorem  and after that the proof itself. You may even know textbooks, where the crucial statement of the theorem comes out of the blue, and you have to concoct the motivation by yourself. Hopefully, the practical part, concerning the 17-gon, has been motivation enough to formulate the following theorem, which we will prove in several steps.

By the way, if you are happy with the experimental proof, given in form of the Java program, you may skip the rest of the chapter. It is not needed to understand the Java program, but of course, it is beautiful mathematics.

In exactly the same manner as with the regular 17-gon, this yields the representation of a Gaussian period of level $k$ as square root expression of periods of the level $k-1.$ So the following corollary is an immediate consequence of the theorem.

The above statements are, so to say, the exact formulation of the descent (or rather ascent ?) from the $0$th period, which is the sum of all roots of unity $\zeta^{p-1}+\zeta^{p-2}+\dots+\zeta^2+\zeta=-1$ to the period of highest level and shortest length $\zeta + \zeta^{p-1},$ which is equal to $2cos(2\pi/p).$ Every step is done only by inserting square roots and forming linear combinations of periods of lower level. Hence, every step can be realized as a construction with ruler and compass, and thus it is legitimate to speak about the sequence of square root expressions as a description of a Euclidean construction of the regular $p$-gon.

The Product of Gaussian Periods

We already have seen, that there is nothing to prove for the sum of Gaussian periods, so we concentrate on the product. There is a whole lot of similar proofs, beginning with the original in [Gauß 1801], followed by the classical [Bachmann 1872]. In [Bewersdorff 2013] Bachmann's proof is translated to modern terminology and slightly simplified.

However, we want to show a little bit more than the proofs quoted. To get the equations for the solution of the cyclotocmic problem, it is sufficient to have the product to be a linear combination with rational coefficients, and only this part is shown in the said books. In the theorem above we required the coefficients to be positive integers  or $0$ – and that's necessary for us, in order the very simple algorithm, we are going to implement in Java, to do the job.

Our strategy is embarked in [Gottlieb 1999]. However, Gottlieb does not give a general proof but presents the method only for the 257-gon. Thus we follow in our considerations at first [Bachmann 1872] and later on [Bewersdorff 2013] and [Gottlieb 1999].

Because the presentation would be rather confusing, taking the fixed primitive element $3$, we use the general primitive element $\omega$ in this chapter. Hence we deal with the following items:

Definition of $p_{n,m}$

For the Gaussian period $p_{n,m}$ we need a handy definition. We got the 1st period by splitting the 0th period into summands with even and odd powers of $\omega.$ To simplify the notation we write only the set of exponents, in other words the powers of the primitive element, and use for this set the same notation as for the Gaussian period, only marked with an asterisk: \[p_{1,0}^*:= \{\omega^0, \omega^2, \dots, \omega^{2^N-2}\}\eqncomma\] \[p_{1,1}^*:= \{\omega^1, \omega^3, \dots, \omega^{2^N-1}\}\eqndot\] or abbreviated: \[p_{1,0}^* = \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 0\pmod 2\}\eqncomma\] \[p_{1,1}^* = \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 1\pmod 2\}\eqndot\] Stepping further to the 2nd period, we again take from the set of powers belonging to $p_{1,0}$ those at the 1st, 3rd, 5th place etc. or those at the 2nd, 4th, 6th place etc. respectively. Hence we now collect the $k$th powers of the primitive element, sorted$\pmod 4$: \[p_{2,0}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 0\pmod 4\}\eqncomma\] \[p_{2,2}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 2\pmod 4\}\eqncomma\] \[p_{2,1}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 1\pmod 4\}\eqncomma\] \[p_{2,3}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 3\pmod 4\}\eqndot\] Generally we have: \[p_{n,m}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv m\pmod{2^n}\}\eqncomma\] consequently \[p_{n,m}=\sum_{\omega^k \in p_{n,m}^*}{\zeta^{\omega^k}}\eqncomma\] and thus we finally gave the justification for the queer enumeration scheme of the $p_{n,m}.$

Splitting of Periods

Let's now look, how the splitting of a period $p_{n-1,m}$ fits into this notation: We have \[p_{n-1,m}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv m\pmod{2^{n-1}}\}\eqncomma\] or by applying the definition of the congruence (and reducing $\omega^k\pmod{p}$, of course): \[p_{n-1,m}^*= \{\omega^k: k = m + x2^{n-1}, \quad x=0,1,2,\dots\}\eqndot\] The splitting separates the even and odd values of $x$: \[p_{n,m_0}^*= \{\omega^k: k = m + x2^{n-1}, \quad x=0,2,4,\dots\}\eqncomma\] and \[p_{n,m_1}^*= \{\omega^k: k = m + x2^{n-1}, \quad x=1,3,5,\dots\}\eqndot\] In the first set, we take one factor $2$ of the even $x$ into the power $2^{n-1}$, leaving $x$ to take the values $0,1,2,\dots$: \[p_{n,m_0}^*= \{\omega^k: k = m + x2^{n}, \quad x=0,1,2,\dots\}\eqndot\] In the second set, for odd $x$, we split $x2^{n-1}=2^{n-1}+(x-1)2^{n-1},$ where $x-1$ is even and can be handled as before: \[p_{n,m_1}^*= \{\omega^k: \quad k = m + 2^{n-1} + x2^{n}, \quad x=0,1,2,\dots\}\eqndot\] Translating back into the congruence notation we see that \[p_{n,m_0}^*=p_{n,m}^*\] and \[p_{n,m_1}^*=p_{n,m+2^{n-1}}^*\eqndot\]

We did not specify limits for the $x$ in the above set descriptions. Because we required the $\omega^k$ to be reduced$\pmod{p}$ they come out automatically. We will show that the $\omega^{m+x2^n}\pmod{p}$ are all different, if $0 \leq x \leq 2^{N-n} - 1.$ To do so, we apply the first remarkable property of the preceding chapter, namely that $\omega^{m+x2^n} \equiv \omega^{m+x'2^n} \pmod{p}$ if and only if $m+x2^n \equiv m+x'2^n \pmod{p-1}.$ Hence, we calculate: \begin{align*} m+2^nx &\equiv m+2^nx' \pmod{2^N}\\ 2^nx &\equiv 2^nx' \pmod{2^N}\\ \end{align*} Of course, one can not cancel down in this equation, because $2^N$ isn't a prime (and thus the ring of congruence classes $\mathbb{Z}/{2^N}\mathbb{Z}$ is no field). But we can apply the division rule for congruence classes of the preceding chapter with $\gcd(2^n,2^N) =2^n$ and get \[ x \equiv x' \pmod{2^{N-n}} \eqndot \] Hence, there are $2^{N-n}$ different exponents $\omega^k\pmod{p},$ and we have indeed a complete Gaussian period.

Gaussian periods are Real Numbers

After this preparation we now are able to show in general, that the numeric value of those Gaussian periods is a real number. As we have seen, this is an essential precondition for the square root expressions to represent constructible points.

Using the notation from above we write a period of level $n$ in form of the following sum: \[p_{n,m} = \sum_{\genfrac{}{}{0pt}{1}{0\leq k \lt 2^N}{k \equiv m\pmod{2^n}}}\zeta^{\omega^k}\eqndot \] For every root of unity $\zeta^{\omega^k}$ its complex conjugate is $\zeta^{-\omega^k}.$ Applying the second remarkable property of a primitive element from the preceding chapter we have \[-\omega^k \equiv \omega^{(p-1)/2}\omega^k \equiv \omega^{(p-1)/2+k}\pmod{p} \] and because of $(p-1)/2 = 2^N/2 = 2^{N-1}$ we get \[-\omega^k \equiv \omega^{2^{N-1}+k}\pmod{p} \eqndot\] Now $2^n$ divides $2^{N-1}$ so that from $k \equiv m\pmod{2^n}$ it follows $k + 2^{N-1} \equiv m\pmod{2^n}.$ Hence, the sum above does not change, if we take $k' = k+2^{N-1}$ as new index of summation (except for a shift of the start and end index). But this is the same as summing up the conjugates of the roots of unity instead of the roots itself. Therefore, $p_{n,m}$ is its own complex conjugate and thus a real number.

Proof of the Theorem – Step One

As we have seen above, the splitting of $p_{n-1,m}$ results in the two periods $p_{n,m}$ and $p_{n,m+2^{n-1}},$ and we are interested in the product of exactly these two periods.

Let's remember what we want to demonstrate: \[ p_{n,m} \cdot p_{n,m+2^{n-1}} = c_0\,p_{n-1,0} + c_1\,p_{n-1,1} + \dots + c_g\,p_{n-1,g} \] with $c_0, c_1, \dots , c_g \in \mathbb{N}_o.$ In other words, the product of the two interesting periods of level $n$ is a linear combination of periods of level $n-1$ with positive integer coefficients (including 0).

In order to get an idea, how we could prove the theorem, we step back to the example of the 17-gon, and remember, how we established the fact, that the product $p_{1,0} \cdot p_{1,1}$ is $4$ times the period $p_{0,0}$. We did so by counting the different products or rather their exponents in the multiplication table. Marking the fields with a pencil (if necessary), one could see, that the multiplication table splits into $4$ disjoint sets, each containing all roots (or rather their exponents) of the period $p_{0,0}.$ Coloring the exponents belonging to one instance of $p_{0,0}$ with the same color, one gets:

Of course, we did not color the different instances of $p_{0,0}$ haphazardly, this would be rather stupid, and would give us no hint, how to proceed with the proof. We will explain the coloring scheme soon. But at first, to apply any method of counting, we must be sure that every field in the multiplication table, that is every product, contains a root (or an exponent) that belongs to a period of lower level (in our example $p_{0,0}$), in particular we must be sure that the exponent is not zero.

This may really happen, as can be seen when multiplying two other periods, occurring in the preceding chapter. Let's take the product $p_{1,0} \cdot p_{1,0} = p_{1,0}^2$:

Note, that the exponent $0$ gives the root of unity $\zeta^0 = 1.$ Applying again the pencil marking procedure, we get for the product $$p_{1,0}^2 = 3p_{1,0}+4p_{1,1}+8 = 3p_{1,0}+4p_{1,1}-8(p_{1,0} + p_{1,1}) = -5p_{1,0} - 4p_{1,1},$$ if we replace the number $8$ with $-8\cdot p_{0,0}$^[1]. So we got at least the representation of the product as linear combination of periods of the same level with integer coefficients. We will now prove, as a first step, that this weaker kind of representation is indeed always possible:

Proof of Lemma 1

We remember that the number of summands of the period of level $0$ is $2^N$, in level $1$ it is $2^N/2 = 2^{N-1}$ etc. Generally in level $n$ it is $2^{N-n}.$ Using the above notation we have for the powers of $\omega^k$: \[p_{n,m}^* = \{\omega^m, \omega^{m+2^n}, \omega^{m+2\cdot 2^n}, \dots, \omega^{m+(2^{N-n}-1)2^n}\}\]

As a shorthand we define \[L_n := 2^{N-n}-1\eqncomma\] because the term $2^{N-n}-1,$ the number of the summands of periods of level $n$ minus one, will appear rather often and is cumbersome to write out. Because the $N$ as exponent of the Fermat prime $p=2^N+1$ is fixed once and for all, it doesn't appear in this notation.

Hence, we can write the period \[p_{n,m} = \zeta^{\omega^m}+\zeta^{\omega^{m+2^n}}+\zeta^{\omega^{m+2\cdot 2^n}}+\dots+\zeta^{\omega^{m+L_n 2^n}} \] or shorter: \[p_{n,m} = \sum_{s=0}^{L_n}\zeta^{\omega^{m+s 2^n}} = \sum_{s=0}^{L_n}\zeta^{\omega^{m}\omega^{s 2^n}} \] The product of two periods is \begin{align*} p_{n,m}p_{n,k} &= (\sum_{s=0}^{L_n}\zeta^{\omega^{m}\omega^{s 2^n}})(\sum_{t=0}^{L_n}\zeta^{\omega^{k}\omega^{t 2^n}})\\ &= \sum_{s=0}^{L_n}\sum_{t=0}^{L_n}\zeta^{\omega^{m}\omega^{s 2^n}+\omega^{k}\omega^{t 2^n}}\\ \end{align*} We now replace the index of summation in the second sum by $t=s+h$ and sum over $h.$ That does not change the value of the sum, because the exponents of $\omega$ are computed$\pmod{p}$ anyway: $$ \begin{align*} p_{n,m}p_{n,k} &= \sum_{s=0}^{L_n}\sum_{h=0}^{L_n}\zeta^{(\omega^{m}+\omega^{k}\omega^{h 2^n})\omega^{s 2^n}}\\ &= \sum_{h=0}^{L_n}\sum_{s=0}^{L_n}\zeta^{(\omega^{m}+\omega^{k}\omega^{h 2^n})\omega^{s 2^n}}\\ &= \sum_{h=0}^{L_n} p_{n,m_h}^{\circ}\\ \end{align*} $$ We write $p_{n,m_h}^{\circ}$ for the expression after the sigma, to indicate that we do not yet know, if it's a Gaussian period or not. However, it is a Gaussian period, if we have \[\omega^{m}+\omega^{k}\omega^{h 2^n} \not\equiv 0 \pmod{p}\] for the term in the exponent, because in this case, by definition of the primitive element $\omega,$ there exists a representation \[\omega^{m}+\omega^{k}\omega^{h 2^n} \equiv \omega^{m_h} \pmod{p}\] with a suitable $m_h.$ In this case we can replace $p_{n,m_h}^{\circ}$ by a proper Gaussian period $p_{n,m_h}.$

On the other hand, if $\omega^{m}+\omega^{k}\omega^{h 2^n} \equiv 0 \pmod{p},$ all exponents are $0,$ thus all powers are $1$ and the sum is $p_{n,m_h}^{\circ}=2^{N-n}.$

Now the sum of all  Gaussian periods of level $n$ equals the Gaussian period of level $0$ and the latter equals $-1.$ Hence we can write for $2^{N-n}$: \[2^{N-n} = -2^{N-n}\sum_{s=0}^{2^n-1} p_{n,s} \] and get alltogether a representation of the product of two arbitrary  Gaussian periods of level $n$ as linear combination of periods of the same level $n$ with integer coefficients. ∎

However, the question arises, under what circumstances the case $\omega^{m}+\omega^{k}\omega^{h 2^n} \equiv 0 \pmod{p}$ is possible at all. Let's do a little calculation: \begin{align*} \omega^{m}+\omega^{k}\omega^{h 2^n} &\equiv 0 \pmod{p} \\ \omega^{m} &\equiv -\omega^{k+h 2^n} \pmod{p} \\ \end{align*} Now, per definition $\omega^{k+h 2^n} \in p_{n,k}^*,$ and as we have seen above, also $-\omega^{k+h 2^n} \in p_{n,k}^*,$ and thus $\omega^{m} \in p_{n,k}^*.$ Hence, the case $\omega^{m}+\omega^{k}\omega^{h 2^n} \equiv 0 \pmod{p}$ is possible only if $p_{n,m} = p_{n,k},$ in other words, if we multiply a period with itself. Thus, if $m \neq k$ holds, the signs of the periods in the sum \[p_{n,m}p_{n,k} = \sum_{h=0}^{L_n} p_{n,m_h} \] are positive or zero. So we have

That's especially true for $p_{n,m} \cdot p_{n,m+2^{n-1}},$ the case that we care about most. In addition, we even know, how often every period $p_{n,m_h}$ appears in the sum, namely as often, as there are different solutions of the congruence^[2] \[\omega^{m_h} \equiv \omega^{m}+\omega^{k}\omega^{h 2^n} \pmod{p}\] for the same $m_h\pmod{p}$ and different values of $h.$ In any case, this multiplicity of the summand $p_{n,m_h}$ is a positive integer, including $0.$

Proof of the Theorem – Step Two

The product is a sum of a number of summands of the form \[\zeta^{\omega^a}\zeta^{\omega^b} = \zeta^{\omega^a+\omega^b}\eqncomma\] with the exponents taken$\pmod{p}.$ Our special concern is \[a \equiv m\pmod{2^n} \quad \text{und} \quad b \equiv m+2^{n-1}\pmod{2^n}\] or by definition of the congruence relation \[a = 2^nx+m\] and \[b = 2^ny+m+2^{n-1}\] with suitable $x,y \in \mathbb{N}_o.$

So we can go back to our multiplication table and write it down for the general case of the product $p_{n,m} \cdot p_{n,m+2^{n-1}}$:

By Lemma 2 we know that the term $\omega^a+\omega^b = \omega^{2^nx + m} + \omega^{2^ny+m+2^{n-1}}$ cannot be zero in our special case, so there exists an $\omega^s$ with $\omega^s = \omega^a + \omega^b,$ and this $\omega^s$ is exponent of a summand of a period of level $n,$ and because this period is daughter of a period of level $n-1,$ it is also exponent of a summand of a period of level $n-1.$ Hence, we can start our enumeration of the summands of a period of level $n-1$ by picking any product from the multiplication table. But we do already know, how to step from one summand within a Gaussian period of level $n-1$ to the next, namely by raising the summand (the root of unity) to the power of $\omega^{2^{n-1}},$ or equivalently, by multiplying the exponent with $\omega^{2^{n-1}}.$

So we take the above $\omega^s,$ and look at its product $\omega^s \cdot \omega^{2^{n-1}}$: $$ \begin{align*} \omega^{s+2^{n-1}} &\equiv (\omega^a+\omega^b)\omega^{2^{n-1}}&\pmod{p}\\ &\equiv \omega^{2^nx+m+2^{n-1}} + \omega^{2^ny+m+2^{n-1}+2^{n-1}}&\pmod{p}\\ &\equiv \omega^{2^nx+m+2^{n-1}} + \omega^{2^ny+m+2^{n}}&\pmod{p}\\ &\equiv \omega^{2^n(y+1)+m}+\omega^{2^nx+m+2^{n-1}}&\pmod{p}\\ &\equiv \omega^{a'}+\omega^{b'}&\pmod{p} \end{align*} $$ with $a'$ and $b'$ being exponents occuring in $p_{m,n}$ and $p_{m,n+2^{n-1}}$ respectively.

Repeating this multiplication, one gets $\omega^{s+2(2^{n-1})},$ repeating once again $\omega^{s+3(2^{n-1})}$ etc. In other words, the exponents of $\omega$ walk through the whole congruence class of $s \pmod{2^{n-1}},$ therefore the associated roots of unity walk through the summands of the period $p_{n-1,s}.$

With every multiplication the above calculation may be repeated analogously, and one can observe, how the $x$ and $y$ change their values, giving the following table: \[ \begin{array}{ccccccccc} \omega^s &\rightarrow& \omega^{s+2^{n-1}} &\rightarrow& \omega^{s+2(2^{n-1})} &\rightarrow& \omega^{s+3(2^{n-1})} &\rightarrow& \dots \\ x &\rightarrow& y+1 &\rightarrow& x+1 &\rightarrow& y+2 &\rightarrow& \dots \\ y &\rightarrow& x &\rightarrow& y+1 &\rightarrow& x+1 &\rightarrow& \dots \\ \end{array} \] Because the $x$ and $y$ may be interpreted as column number or row number respectively, this is just the system, how we have colored the multiplication table in case of the example given above: Picking one field from the table in column $x$ and row $y,$ which belongs to a product with exponent $\omega^s,$ then moving to the field $(y+1,x),$ which belongs to $\omega^s \cdot \omega^{2^{n-1}},$ then moving to $(y+1,x+1)$ and so on. Of course, as the $x$ and $y$ enumerate the exponents of a period of level $n,$ they have to be taken$\pmod{2^{N-n}},$ which is just the heights and width of the multiplication table. Thus, when the above process leaves the table on the right, one enters the table in the same height on the left, and the same with bottom and top. Therefore, the process repeats itself after $2^{N-n+1}$ steps, and we have colored the complete period of level $n-1.$ Then we pick a field not yet colored, and repeat the process with this starting point and so on.

It is very instructive, to follow the way of a certain product in the example, applying the multiplication by $\omega^{2^{n-1}}.$ Because in that table two periods of level $1$ are multiplied, this is simply the multiplication of the exponent by $3 \pmod{17},$ in other words a step to the right within the sequence of the exponents of the $0$th Gaussian period: \[ 1,3,9,{10},{13},{5},{15},{11},{16},{14},{8},{7},{4},{12},{2},{6} \] and from $6$ back to $1.$ For example, if you start with the $7,$ belonging to the pair $(11,13)$ and colored in light blue, and continue with the likewise colored $4, 12$ etc., the back and forth jumping over the diagonal will give you a vivid illustration of the above calculations.

What remains to be shown is, that the above process splits the multiplication table into disjoint sets. That every set contains the exponents of a period of level $n-1$ is already clear by construction. To prove the disjointedness, we observe that the sequence \[ \begin{array}{ccccccccc} \omega^s &\rightarrow& \omega^{s+2^{n-1}} &\rightarrow& \omega^{s+2(2^{n-1})} &\rightarrow& \omega^{s+3(2^{n-1})} &\rightarrow& \dots \\ x &\rightarrow& y+1 &\rightarrow& x+1 &\rightarrow& y+2 &\rightarrow& \dots \\ y &\rightarrow& x &\rightarrow& y+1 &\rightarrow& x+1 &\rightarrow& \dots \\ \end{array} \] can be split into two sequences: \[ \begin{array}{ccccccccc} \omega^s &\rightarrow& \omega^{s+2(2^{n-1})} &\rightarrow& \omega^{s+4(2^{n-1})} &\rightarrow& \omega^{s+6(2^{n-1})} &\rightarrow& \dots \\ x &\rightarrow& x+1 &\rightarrow& x+2 &\rightarrow& y+3 &\rightarrow& \dots \\ y &\rightarrow& y+1 &\rightarrow& y+2 &\rightarrow& y+3 &\rightarrow& \dots \\ \end{array} \] and \[ \begin{array}{ccccccccc} \omega^{s+2^{n-1}} &\rightarrow& \omega^{s+3(2^{n-1})} &\rightarrow& \omega^{s+5(2^{n-1})} &\rightarrow& \omega^{s+7(2^{n-1})} &\rightarrow& \dots \\ y+1 &\rightarrow& y+2 &\rightarrow& y+3 &\rightarrow& y+4 &\rightarrow& \dots \\ x &\rightarrow& x+1 &\rightarrow& x+2 &\rightarrow& x+3 &\rightarrow& \dots \\ \end{array} \] That's nothing else as two diagonal stripes within the table (taking into account the overflow from right to left and bottom to top, of course). Denoting the width and height of the table with $w$, these diagonal stripes are equivalence classes of the relation $$ \begin{align*} (x,y) &\sim (x',y') :\iff \\ & \exists a \in \mathbb{N}_o \quad\text{with}\quad x' - x \equiv a\pmod{w} \quad\text{and}\quad y'-y \equiv a\pmod{w} \\ \end{align*} $$ You may want to prove, that this is indeed an equivalence relation.