prerequisites: 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,

\[\begin{equation} \tag{1}\label{char-eq:sieve-rank-six-three-triangles} \begin{array}{*{5}{r}} 1 & 1 & 1 & 1 & \textbf{1} \\ 1 & 2 & 3 & \textbf{4} & \\ 1 & 3 & \textbf{6} & & \\ 1 & \textbf{4} & & & \\ \textbf{1} & & & & \end{array} \begin{array}{*{5}{r}} 1 & 1 & 1 & 1 & \textbf{1} \\ 5 & 6 & 7 & \textbf{8} & \\ 11 & 17 & \textbf{24} & & \\ 15 & \textbf{32} & & & \\ \textbf{16} & & & & \end{array} \begin{array}{*{5}{r}} 1 & 1 & 1 & 1 & \textbf{1} \\ 9 & 10 & 11 & \textbf{12} & \\ 33 & 43 & \textbf{54} & & \\ 65 & \textbf{108} & & & \\ \textbf{81} & & & & \end{array} \end{equation}\]

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,

\[\begin{equation*} \color{black} (1 + t)^4 \color{lightgray} = \color{black} 1 \color{lightgray} \cdot t^4 + \color{black} 4 \color{lightgray} \cdot t^3 + \color{black} 6 \color{lightgray} \cdot t^2 + \color{black} 4 \color{lightgray} \cdot t^1 + \color{black} 1 \color{lightgray}\cdot t^0 \color{black}, \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{black} (1 + 1)^4 &= \color{black} 1 \cdot 1^4 \color{lightgray} + \color{black} 4 \cdot 1^3 \color{lightgray} + \color{black} 6 \cdot 1^2 \color{lightgray} + \color{black} 4 \cdot 1^1 \color{lightgray} + \color{black} 1 \cdot 1^0 \\ \color{black} &= \color{black} 1 \color{lightgray} + \color{black} 4 \color{lightgray} + \color{black} 6 \color{lightgray} + \color{black} 4 \color{lightgray} + \color{black} 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{black} (1 + 2)^4 &= \color{black} 1 \cdot 2^4 \color{lightgray} + \color{black} 4 \cdot 2^3 \color{lightgray} + \color{black} 6 \cdot 2^2 \color{lightgray} + \color{black} 4 \cdot 2^1 \color{lightgray} + \color{black} 1 \cdot 2^0\\ \color{black} &= \color{black} 16 \color{lightgray} + \color{black} 32 \color{lightgray} + \color{black} 24 \color{lightgray} + \color{black} 8 \color{lightgray} + \color{black} 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{black} (1 + 3)^4 &= \color{black} 1 \cdot 3^4 \color{lightgray} + \color{black} 4 \cdot 3^3 \color{lightgray} + \color{black} 6 \cdot 3^2 \color{lightgray} + \color{black} 4 \cdot 3^1 \color{lightgray} + \color{black} 1 \cdot 3^0\\ \color{black} &= \color{black} 81 \color{lightgray} + \color{black} 108 \color{lightgray} + \color{black} 54 \color{lightgray} + \color{black} 12 \color{lightgray} + \color{black} 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\),

\[\begin{equation} \tag{3}\label{eq:partial-sums-hpyotenuses} \color{lightgray} \begin{array}{*{5}{r}} 1 & 1 & 1 & 1 & \color{black}{1} \\ 1 & 2 & 3 & \color{black}{4} & \\ 1 & 3 & \color{black}{6} & & \\ 1 & \color{black}{4} & & & \\ \color{black}{1} & & & & \end{array} \color{black}{\Rightarrow} \color{lightgray} \begin{array}{*{5}{r}} \color{black}{1} & 1 & 1 & 1 & \color{black}{1} \\ \color{black}{5} & 6 & 7 & \color{black}{8} & \\ \color{black}{11} & 17 & \color{black}{24} & & \\ \color{black}{15} & \color{black}{32} & & & \\ \color{black}{16} & & & & \end{array} \color{black}{\Rightarrow} \color{lightgray} \begin{array}{*{5}{r}} \color{black}{1} & 1 & 1 & 1 & 1 \\ \color{black}{9} & 10 & 11 & 12 & \\ \color{black}{33} & 43 & 54 & & \\ \color{black}{65} & 108 & & & \\ \color{black}{81} & & & & \end{array} \color{black} \end{equation}\]

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,

\[\begin{equation} \tag{4}\label{char-eq:moessner-triangles-pascal-like} \begin{array}{*{9}{c}} &&&& 1 &&&& \\ &&& 1 && 1 &&& \\ && 1 && 2 && 1 && \\ & 1 && 3 && 3 && 1 & \\ 1 && 4 && 6 && 4 && 1 \end{array} \qquad \begin{array}{*{9}{c}} &&&& 1 &&&& \\ &&& 5 && 1 &&& \\ && 11 && 6 && 1 && \\ & 15 && 17 && 7 && 1 & \\ 16 && 32 && 24 && 8 && 1 \end{array} \end{equation}\]

where we use the same row-and-entry indexing scheme, n and k, as in the case of the binomialCoefficient function,

binomialCoefficient :: Int -> Int -> Int
binomialCoefficient n k
  | n < k = 0
  | k == 0 = 1
  | n > 0 && k > 0 = binomialCoefficient (n - 1) k +
                     binomialCoefficient (n - 1) (k - 1)

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,

moessnerEntry :: Int -> Int -> Int -> Int -> Int
moessnerEntry r t n k
  | n < k = 0
  | k == n = 1
  | n > 0 && k == 0 = monomial r t n + moessnerEntry r t (n - 1) 0
  | n > 0 && k > 0 = moessnerEntry r t (n - 1) k +
                     moessnerEntry r t (n - 1) (k - 1)

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,

monomial :: Int -> Int -> Int -> Int
monomial r t n = (binomialCoefficient r n) * (t ^ n)

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:

monomial 4 2 3 == 32

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:

moessnerEntry 4 1 3 2 == 7

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,

rotatedBinomialCoefficient :: Int -> Int -> Int
rotatedBinomialCoefficient r c = binomialCoefficient (r + c) c

Thus, we can simply define the rotated version of moessnerEntry using the same transformation as above,

rotatedMoessnerEntry :: Int -> Int -> Int -> Int -> Int
rotatedMoessnerEntry n t r c = moessnerEntry n t (r + c) c

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,

rotatedBinomialCoefficient :: Int -> Int -> Int
rotatedBinomialCoefficient r c
  | r == 0 = 1
  | c == 0 = 1
  | r > 0 && c > 0 = rotatedBinomialCoefficient (r - 1) c +
                     rotatedBinomialCoefficient r (c - 1)

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,

rotatedMoessnerEntry :: Int -> Int -> Int -> Int -> Int
rotatedMoessnerEntry n t r c
  | r == 0 = 1
  | c == 0 = monomial n t (r + c) +
             rotatedMoessnerEntry n t (r - 1) 0
  | r > 0 && c > 0 = rotatedMoessnerEntry n t (r - 1) c +
                     rotatedMoessnerEntry n t r (c - 1)

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,

rotatedMoessnerEntry 4 2 3 1 == 108

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.

  1. See “Concrete Stream Calculus: An extended study” (2010) by Ralf Hinze. ↩

  2. See “On the Moessner Theorem on Integral Powers” (1966) by Calvin T. Long. ↩

  3. See “A Characterization of Moessner’s sieve” (2014) by Danvy et al. ↩