# A characteristic function

of Moessner's sieve

#### prerequisites: The posts A dual to Moessner’s sieve and Rotating Pascal’s triangle and the binomial coefficient

*“It might be worth-while to point out*

*that the purpose of abstracting is not to be vague,*

*but to create a new semantic level*

*in which one can be absolutely precise”*

– **Edsger W. Dijkstra, 1972 (EWD340)**

### 1. Introduction

The goal of this post is to introduce a characteristic function of Moessner’s sieve, which computes the entries of a given Moessner triangle without needing to compute the prefix of the sieve.

The post is structured as follows. In Section
2, we derive the operational description
of a characteristic function of Moessner’s sieve, which we then formalize in
Section 3 as the two Haskell functions
`moessnerEntry`

and `rotatedMoessnerEntry`

. The post is concluded in Section
4.

### 2. Characterizing Moessner triangles

In order to come up with a *characteristic function* of the triangles generated
by *Moessner’s sieve*, we first have to uncover the patterns by which they are
constructed. Hence, let us examine the first three *Moessner triangles* created
by applying Moessner’s sieve of *rank* \(5\) – yielding *successive powers* of
\(4\) – on the sequence of \(1\)s,

and see if we can discover any properties that help us characterize the
triangles. As previously pointed out in this series of posts and by Hinze,^{1}
we can observe that the initial triangle generated by Moessner’s sieve is always
equal to the rotated Pascal’s triangle, having a depth equal to the rank of the
Moessner triangle plus one. Furthermore, we also notice that the subsequent
Moessner triangles exhibit Pascal-like properties, i.e., Pascal’s rule holds for
all triangles, as every entry is the sum of its immediate western and northern
neighbors, as previously illustrated and originally noted by Long.^{2}
Knowing that the Moessner triangles behave in a Pascal-like fashion, hints at a
possible binomial coefficient-like characteristic function, parameterized over
the first row and column of a given Moessner triangle. If we again focus on
Figure \ref{char-eq:sieve-rank-six-three-triangles}, it is trivial to see that
the first row of every Moessner triangle is filled with \(1\)s, while we need to
discover a new property in order to characterize the first column of every
triangle.

Returning to the initial Moessner triangle, we know from the equivalence between Pascal’s triangle and the binomial coefficient, that the hypotenuse of the triangle will always enumerate the coefficients of the monomials of the binomial expansion of \((1 + t)^r\), where \(r\) is equal to the rank of the triangle, and \(t\) is a variable. Using the initial Moessner triangle of Figure \ref{char-eq:sieve-rank-six-three-triangles} as an example, we get the binomial expansion,

\[\definecolor{solarizedgray}{RGB}{88,110,117} \begin{equation*} \color{solarizedgray} (1 + t)^4 \color{lightgray} = \color{solarizedgray} 1 \color{lightgray} \cdot t^4 + \color{solarizedgray} 4 \color{lightgray} \cdot t^3 + \color{solarizedgray} 6 \color{lightgray} \cdot t^2 + \color{solarizedgray} 4 \color{lightgray} \cdot t^1 + \color{solarizedgray} 1 \color{lightgray}\cdot t^0 \color{solarizedgray}, \end{equation*}\]where the values of the hypotenuse, \((1,4,6,4,1)\), do indeed enumerate the binomial coefficients of the expansion. Incidentally, the hypotenuse also enumerates the actual terms of the binomial expansion when \(t = 1\),

\[\begin{align*} \color{solarizedgray} (1 + 1)^4 &= \color{solarizedgray} 1 \cdot 1^4 \color{lightgray} + \color{solarizedgray} 4 \cdot 1^3 \color{lightgray} + \color{solarizedgray} 6 \cdot 1^2 \color{lightgray} + \color{solarizedgray} 4 \cdot 1^1 \color{lightgray} + \color{solarizedgray} 1 \cdot 1^0 \\ \color{solarizedgray} &= \color{solarizedgray} 1 \color{lightgray} + \color{solarizedgray} 4 \color{lightgray} + \color{solarizedgray} 6 \color{lightgray} + \color{solarizedgray} 4 \color{lightgray} + \color{solarizedgray} 1, \end{align*}\]which raises the question of what happens if we let \(t\) denote the triangle index, starting from \(t = 1\). As it turns out, letting \(t = 2\),

\[\begin{align} \tag{2}\label{eq:binomial-expansion-example} \color{solarizedgray} (1 + 2)^4 &= \color{solarizedgray} 1 \cdot 2^4 \color{lightgray} + \color{solarizedgray} 4 \cdot 2^3 \color{lightgray} + \color{solarizedgray} 6 \cdot 2^2 \color{lightgray} + \color{solarizedgray} 4 \cdot 2^1 \color{lightgray} + \color{solarizedgray} 1 \cdot 2^0\\ \color{solarizedgray} &= \color{solarizedgray} 16 \color{lightgray} + \color{solarizedgray} 32 \color{lightgray} + \color{solarizedgray} 24 \color{lightgray} + \color{solarizedgray} 8 \color{lightgray} + \color{solarizedgray} 1 \end{align}\]results in the terms of the binomial expansion to be equal to the values found in the hypotenuse of the second Moessner triangle, \((16,32,24,8,1)\), in Figure \ref{char-eq:sieve-rank-six-three-triangles}. We can observe that this property holds for all triangles,

\[\begin{align*} \color{solarizedgray} (1 + 3)^4 &= \color{solarizedgray} 1 \cdot 3^4 \color{lightgray} + \color{solarizedgray} 4 \cdot 3^3 \color{lightgray} + \color{solarizedgray} 6 \cdot 3^2 \color{lightgray} + \color{solarizedgray} 4 \cdot 3^1 \color{lightgray} + \color{solarizedgray} 1 \cdot 3^0\\ \color{solarizedgray} &= \color{solarizedgray} 81 \color{lightgray} + \color{solarizedgray} 108 \color{lightgray} + \color{solarizedgray} 54 \color{lightgray} + \color{solarizedgray} 12 \color{lightgray} + \color{solarizedgray} 1, \end{align*}\]as seen here for \(t = 3\), and was recently pointed out by Danvy et al.^{3} as
a characterization of the values dropped in the individual triangles of
Moessner’s sieve. Combining this observation with the fact that the entries of a
Moessner triangle are created using Pascal’s rule, leads us to the realization
that the first column of the \((1 + t)\)th Moessner triangle enumerates the
partial sums of the monomials of the binomial expansion \({(1 + t)}^r\),

as seen in Figure \ref{eq:partial-sums-hpyotenuses}, where \((1,4,6,4,1)\) partially sums to \((1,5,11,15,16)\), and \((1,8,24,32,16)\) partially sums to \((1,9,33,65,81)\).

Having characterized how every Moessner triangle is constructed using Pascal’s rule, where the first row of a triangle is a sequence of \(1\)s and the first column is a partial sum parameterized over the binomial expansion, we are ready to formalize the characteristic function in Haskell.

### 3. Defining a characteristic function

Synthesizing the observations made in the previous section, we now present two
characteristic functions of Moessner’s sieve. First, we define a characteristic
function that is analogous to our existing `binomialCoefficient`

function,
`moessnerEntry`

, followed by a rotated version, `rotatedMoessnerEntry`

, defined
both as its own formalization and defined in terms of the first characteristic
function, `moessnerEntry`

, similar to what we did when we defined
`rotatedBinomialCoefficient`

.

### 3.1 Moessner entry

In order to translate the informal description of the characteristic function
made in Section 2 into some Haskell code,
we first define it in an analogous way to the existing
`binomialCoefficient`

function. As such, we rotate the first two Moessner
triangles of Figure \ref{char-eq:sieve-rank-six-three-triangles} into a
Pascal-like configuration,

where we use the same row-and-entry indexing scheme, `n`

and `k`

, as in the case
of the `binomialCoefficient`

function,

Just like the `binomialCoefficient`

function, we have four combinations of `n`

and `k`

being either equal to `0`

or greater than `0`

, where the only difference
from the `binomialCoefficient`

function is the additional case where `n > 0`

and
`k == 0`

, corresponding to the first column of a rotated Moessner triangle as
discussed in the previous section. While we simply return `1`

in the case of the
`binomialCoefficient`

function, we instead have to add the appropriate monomial
of the last row of the previous triangle. For example, in Figure
\ref{char-eq:moessner-triangles-pascal-like} the value `11`

in the third row of
the second triangle is obtained by adding `5`

, located immediately above it, and
the value `6`

, located at the third entry of the last row of the previous
triangle. This is the exact same behavior as we saw in Figure
\ref{eq:partial-sums-hpyotenuses}, but for the rotated Moessner triangles.

Combining the logic of the four cases of `n`

and `k`

, yields the following
binomial coefficients-like characteristic function of the Pascal-like Moessner
triangle,

indexed using the row and column indices `n`

and `k`

, where `r`

denotes the rank
of the triangle and `t`

the triangle index. The `monomial`

function, used
in the new case of `n > 0 && k == 0`

, is defined as,

and computes a single monomial of the binomial expansion \({(1 + t)}^r\), when
given a rank, `r`

, a triangle index, `t`

, and an index, `n`

, of a monomial in
the expansion.

To illustrate this, we compute the fourth element from the right in the binomial expansion of Formula \ref{eq:binomial-expansion-example}, \(4 \cdot 2^3\), by letting \(r = 4\), \(t = 2\), and \(n = 3\), yielding the expected result:

Likewise, if we want to compute the third entry of the fourth row of the second
triangle in Figure \ref{char-eq:moessner-triangles-pascal-like}, having value
\(7\), we let \(r = 4\), \(t = 1\), \(n = 3\), and \(k = 2\), and pass them to
`moessnerEntry`

:

Thus, the above results demonstrate the correctness of our first formalization of a characteristic function of Moessner’s sieve.

Having defined a binomial coefficient-like characteristic function of Moessner’s sieve, we move on to define its rotated counterpart, which provides a more appropriate indexing scheme when describing the entries of the triangles generated by Moessner’s sieve.

### 3.2 Rotated Moessner entry

In order to rotate the characteristic function `moessnerEntry`

in an analogous
fashion to `binomialCoefficient`

, we observe once again that
`binomialCoefficient`

and `moessnerEntry`

exhibit the same triangular structure,
which means the relation between `moessnerEntry`

and its rotated counterpart,
`rotatedMoessnerEntry`

, is identical to the existing relation between
`binomialCoefficient`

and `rotatedBinomialCoefficient`

,

Thus, we can simply define the rotated version of `moessnerEntry`

using the same
transformation as above,

where `n`

denotes the rank, `t`

the triangle index, `r`

the row index, and `c`

the column index.

Similarly, we can also define `rotatedMoessnerEntry`

by reusing the
formalization we lifted from the rotated Pascal’s triangle,

and observe that the only case that has changed is the case where `c == 0`

,
corresponding to the case `n > 0 && k == 0`

we discussed in the previous
section, i.e. the first column of each Moessner triangle. This brings us to the
following formalization of `rotatedMoessnerEntry`

,

which we can use to calculate the entries of the triangles in Figure \ref{char-eq:sieve-rank-six-three-triangles}, without first having to compute the whole prefix of Moessner’s sieve.

To illustrate the application of our final formalization, we want to calculate the entry, \(108\), located in the second column of the fourth row in the third triangle in Figure \ref{char-eq:sieve-rank-six-three-triangles}, which we do by passing the following values \(n = 4\), \(t = 2\), \(r = 3\), and \(c = 1\) to our characteristic function of Moessner’s sieve,

and obtain the expected result of \(108\).

Now that we have defined our two characteristic functions of Moessner’s sieve,
`moessnerEntry`

and `rotatedMoessnerEntry`

, we are ready to conclude this post.

### 4. Conclusion

In this post, we have introduced two characteristic functions of Moessner’s
sieve, `moessnerEntry`

and `rotatedMoessnerEntry`

, which computes the entries of
a given Moessner triangle without having to compute the prefix of Moessner’s
sieve.

The characteristic functions were derived by observing that every Moessner triangle behaves in a Pascal-like way combined with the fact that the values dropped in the traditional Moessner’s sieve enumerate the monomials of the binomial expansion.

This post was a small excerpt from my Master’s thesis, in which I also prove the correctness of the above characteristic functions, and use the characteristic function in my proof of Moessner’s idealized theorem.

Mathematics

- « Previous |
- Archive |
- Next »