19 February 2016

prerequisites: The post An introduction to Moessner’s theorem and Moessner’s sieve

“The poet doesn’t invent.”
“He listens.”
– Jean Cocteau

1. Introduction

The goal of this post is to introduce a dual to Moessner’s sieve that simplifies the initial configuration of Moessner’s sieve, by starting from two seed tuples instead of an initial sequence, and creates a result sequence of Moessner triangles, each constructed column by column, instead of a result sequence of successive powers, constructed row by row.

The post is structured as follows. In Section 2, we motivate the redefinition of Moessner’s sieve as a procedure for generating a sequence of so-called Moessner triangles, instead of a sequence of successive powers. As a result, we introduce two triangle creation procedures, which construct individual Moessner triangles either row by row or column by column. In Section 3, we first show how our triangle creation procedures give rise to a new and simpler initial configuration of Moessner’s sieve, which we then use as inspiration for the final formalization of the dual of Moessner’s sieve. The post is concluded in Section 4.

2. From successive powers to triangles

In this section, we first motivate the idea of looking at Moessner’s sieve as a procedure for generating a sequence of Moessner triangles, as opposed to a sequence of successive powers, and then formalize the core operations of the sieve that create the individual Moessner triangles.

2.1 Generating a sequence of triangles with Moessner’s sieve

In order to motivate the idea of redefining Moessner’s sieve as a procedure for generating a sequence of Moessner triangles, we start by looking at an example application of Moessner’s sieve.

Given an initial sequence of s, we apply Moessner’s sieve of rank on it,

which yields the result sequence of successive powers of (the rank minus one). As seen from this description, we traditionally view Moessner’s sieve as a procedure which takes an initial sequence consisting of an arithmetic progression, as first shown by Long,1 and returns a result sequence of successive powers, by repeatedly dropping and partially summing the elements of the initial sequence. Now, instead of focusing solely on the elements of the result sequence, we want to view Moessner’s sieve as generating a sequence of triangles, each of which we call a Moessner triangle. The Moessner triangles appear as a result of preserving the alignment of the entries of the intermediate result sequences in Moessner’s sieve, while performing the repeated dropping of elements, as seen in Figure \ref{eq:dual-moessner-sieve-five}. Hence, we can pick the first triangle created in the above example,

and describe it as a set of tuples, marked by . We can then translate the above representation into the following types in Haskell,

1
2
type Tuple = [Int]
type Triangle = [Tuple]

which we use for the remainder of this post, when referring to Moessner triangles in the context of Moessner’s sieve. Lastly, we say that a Moessner triangle’s rank is equal to its depth minus one - or one less than the drop index of Moessner’s sieve - and therefore the Moessner triangles in Figure \ref{eq:dual-moessner-sieve-five} all have rank .

Thus, we have now defined what we mean by a Moessner triangle in the context of Moessner’s sieve and defined a notation for the Triangle and Tuple types. In the next sections, we define procedures for creating individual tuples and combining them into triangles.

2.2 Make tuple

Before defining our makeTuple procedure, we first return to the triangles in Figure \ref{eq:dual-moessner-sieve-five} and observe that we can view each of them as being constructed from two seed tuples: a horizontal seed tuple corresponding to a slice of the initial sequence, and a vertical seed tuple corresponding to the dropped elements, marked with boldface, of the previous triangle. For example, the triangle shown in Figure \ref{eq:moessner-triangle-tuples} can be seen as the result of adding a horizontal seed tuple of s and a vertical seed tuple of s – since no elements have been dropped before the creation of the first triangle,

From Figure \ref{eq:triangle-creation-example}, we notice that the rows and columns of the triangle are created in the exact same fashion – as the partial sums of the previous row/column together with an accumulator. Specifically, the th horizontal tuple (row) of the result triangle is created by partially summing all but the last entry of the th horizontal tuple, while using the th value of the vertical seed tuple as the accumulator value. For example, we can obtain the second horizontal tuple, , of the result triangle, by partially summing the first horizontal tuple, ,

where we ignore the last element, , and use the second entry in the vertical tuple, , as the accumulator for the partial summation. The same approach can be used for obtaining the th vertical tuple (column) by partially summing the th vertical tuple. This is also the reason why we have added an extra in the initial vertical seed tuple - to ensure symmetry with respect to this procedure. By reducing Moessner’s sieve to this core operation, which works for both rows and columns, we can translate our description above into the following Haskell function,

1
2
3
4
5
6
makeTuple :: Tuple -> Int -> Tuple
makeTuple xs a = case xs of
  [] -> []
  (x:[]) -> []
  (x:xs') -> let a' = x + a
             in a' : (makeTuple xs' a')

which takes a Tuple, xs, and a number, a, as the accumulator, and returns a new Tuple as described. With this definition, the above example calculation then becomes,

1
makeTuple [1,2,3,4] 0 == [1,3,6]

Having defined a procedure for creating tuples, corresponding to individual rows or columns in a Moessner triangle, we move on to define procedures for creating a whole triangle as a list of tuples.

2.3 Create triangle

As already mentioned in the previous section, we can construct individual rows or columns of a Moessner triangle using the same procedure, makeTuple, which means that we can create a triangle by either repeatedly applying makeTuple on the horizontal seed tuple while using the vertical seed tuple as the list of accumulator values, or vice versa,

As a result of this observation, we define two triangle creation procedures that each take two Tuples, xs and ys, corresponding to the horizontal seed tuple and vertical seed tuple, respectively, and repeatedly applies makeTuple on these. For the first procedure, createTriangleHorizontally, we repeatedly create a new Tuple, based on the elements of xs, while using the values of ys as accumulators, and cons the result onto the result Tuple. In this way, xs holds the intermediate result of each recursive call, while the head of ys is removed for each recursive call. The algorithm terminates when there is one element or less left in ys and the result of the procedure is a list of horizontal Tuples representing a Triangle. Translating the above description into Haskell, we obtain the following definition,

1
2
3
4
5
6
createTriangleHorizontally :: Tuple -> Tuple -> Triangle
createTriangleHorizontally xs ys = case ys of
  [] -> []
  (y:[]) -> []
  (y:ys') -> let xs' = makeTuple xs y
             in xs' : (createTriangleHorizontally xs' ys')

which creates a Moessner triangle in a row by row fashion. For the second procedure, createTriangleVertically, we simply switch the roles of the xs and ys described above, and obtain the dual procedure,

1
2
3
4
5
6
createTriangleVertically :: Tuple -> Tuple -> Triangle
createTriangleVertically xs ys = case xs of
  [] -> []
  (x:[]) -> []
  (x:xs') -> let ys' = makeTuple ys x
             in ys' : (createTriangleVertically xs' ys')

creating the same Triangle represented as a list of vertical Tuples. The duality of createTriangleHorizontally and createTriangleVertically is now evident as the definitions of the two procedures are completely identical except that the xs and ys have switched roles.

To illustrate this, if we give the seed tuples in Figure \ref{eq:moessner-triangle-with-tuples} as arguments to our two new definitions, we obtain the following calculations,

1
2
3
4
5
6
createTriangleHorizontally [1,1,1,1,1] [0,0,0,0,0] == [
  [1,2,3,4],
  [1,3,6],
  [1,4],
  [1]
]

and

1
2
3
4
5
6
createTriangleVertically [1,1,1,1,1] [0,0,0,0,0] == [
  [1,1,1,1],
  [2,3,4],
  [3,6],
  [4]
]

where the results correspond to enumerating the entries of the result Moessner triangle in Figure \ref{eq:moessner-triangle-with-tuples} either row by row or column by column, respectively.

Thus, we have now defined the inner workings of the dual of Moessner’s sieve, specifically the procedures makeTuple and createTriangleVertically which works column by column, when creating a Moessner triangle, while the traditional version of Moessner’s sieve works row by row when creating a sequence of successive powers. Our next step is now to formalize the dual of Moessner’s sieve using the dual triangle creation procedure, createTriangleVertically.

3 The dual of Moessner’s sieve

In this section, we formalize the dual of Moessner’s sieve as a procedure for creating a sequence of Moessner triangles, using createTriangleVertically, which starts from a minimal initial configuration. Hence, we first make the case for simplifying the initial configuration of Moessner’s sieve and then define the procedures which combined yields the dual of Moessner’s sieve.

3.1 Simplifying the initial configuration

Before proceeding to state the final dual of Moessner’s sieve, we first investigate whether our new approach affords a simpler initial configuration of Moessner’s sieve. Hence, we again turn our attention to the Moessner triangle in Figure \ref{eq:moessner-triangle-with-tuples}, and notice that the seed tuple containing s, is only a part of the input and not a part of the output, which we ideally would like in order to properly mimic the traditional version of Moessner’s sieve. Fortunately, as we demonstrated in the previous post, we can obtain the sequence of s by partially summing a followed by s, and apply this generalization to the case of the procedure createTriangleHorizontally,

where we divide the sequence of a followed by s into equally sized horizontal seed tuples, one for each triangle, and add an extra to the vertical seed tuples.

If we use this simplified configuration for the two initial Moessner triangles of Figure \ref{eq:dual-moessner-sieve-five},

we discover a consistent property where the seed tuples are always located outside of the result triangles, while the result triangles contain exactly the values we want to capture with the sieve. As such, we define the rank of a seed tuple to be equal to its length minus two - or the rank of the generated Moessner triangle - meaning that the seed tuples in Figure \ref{eq:dual-moessner-sieve-simple} all have rank .

However, we do notice a small inconsistency in the two triangles in Figure \ref{eq:dual-moessner-sieve-simple}, since the initial horizontal seed tuple consists of a followed by s while all subsequent horizontal seed tuples consist of plain s. Fortunately, we know from Long and Hinze2 that the first triangle created by Moessner’s sieve is always Pascal’s triangle, which allows us to swap the two seed tuples for the initial triangle, as Pascal’s triangle is symmetric:

Thus, we obtain an initial configuration where the horizontal seed tuples are always s, for all created Moessner triangles, and the whole sieve is bootstrapped from a single seed value, , located at the top of the first vertical seed tuple.

Having reduced the initial configuration of Moessner’s sieve to this extremely simple set of seed tuples, we are ready to define the last procedures needed to formalize our dual of Moessner’s sieve.

3.2 Hypotenuse of triangles

As seen in Figure \ref{eq:dual-moessner-sieve-final}, the values of the hypotenuse of the first Moessner triangle, , are used as the vertical seed tuple for the next Moessner triangle. Thus, we need a procedure which takes a Triangle and returns its hypotenuse as a Tuple. This is implemented in a straightforward fashion by going through each Tuple, t, of a Triangle, ts, and aggregating the last values of each Tuple into a new Tuple, which is then returned,

1
2
3
4
hypotenuse :: Triangle -> Tuple
hypotenuse ts = case ts of
  [] -> []
  (t:ts') -> (last t) : (hypotenuse ts')

For example, if we feed the triangle,

to hypotenuse, we get the tuple, , when reading it column by column, which we can also express with the following piece of Haskell code,

1
2
3
hypotenuse $
  createTriangleVertically [0,0,0,0,0,0] [1,4,6,4,1,0] ==
  [16,32,24,8,1]

All we have left to do now is to compose createTriangleVertically and hypotenuse into a procedure which creates a list of Triangles, which is the dual of Moessner’s sieve.

3.3 Create triangles

By combining createTriangleVertically and hypotenuse we can define a final procedure, createTrianglesVertically, which given two seed tuples, xs and ys, and a length argument, n, returns a list of n Moessner triangles. The procedure works by applying createTriangleVertically on the two input tuples, xs and ys, which creates the initial Moessner triangle whose hypotenuse is then used as the ys seed tuple of the next triangle, while the xs remain unchanged, as these are always s. For each triangle created, we decrement the value of n and terminate the procedure when n == 0. This description brings us to the following definition,

1
2
3
4
5
6
createTrianglesVertically :: Int -> Tuple -> Tuple -> [Triangle]
createTrianglesVertically n xs ys
  | n == 0 = []
  | n  > 0 = let ts  = createTriangleVertically xs ys
                 ys' = reverse $ 0 : hypotenuse ts
             in ts : createTrianglesVertically (n - 1) xs ys'

which is exactly the dual of Moessner’s sieve that we wanted, since it creates a sequence of Moessner triangles by constructing one triangle at a time – in a column by column fashion.

Visualizing the sieve of Figure \ref{eq:dual-moessner-sieve-five}, using our new dual sieve, yields the following three Moessner triangles,

where we have explicitly added the seed tuples of each triangle. Finally, we can now emulate this dual sieve by passing the same arguments to createTrianglesVertically and obtain,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
createTrianglesVertically 3 [0,0,0,0,0,0] [1,0,0,0,0,0] == [
  [
    [1,1,1,1,1],
    [1,2,3,4],
    [1,3,6],
    [1,4],
    [1]
  ],
  [
    [1,5,11,15,16],
    [1,6,17,32],
    [1,7,24],
    [1,8],
    [1]
  ],
  [
    [1,9,33,65,81],
    [1,10,43,108],
    [1,11,54],
    [1,12],
    [1]
  ]
]

which lists the entries of the three Moessner triangles in the sieve above, each of which is enumerated column by column.

Thus, we have now defined a dual to Moessner’s sieve that creates a sequence of Moessner triangles, instead of a sequence of successive powers, where each triangle is created column by column, instead of row by row, and which has an initial configuration consisting of two seed tuples having just one non-zero value, , located at the top of the vertical seed tuple, from which the whole sieve is subsequently constructed.

4 Conclusion

In this post, we have introduced a dual to Moessner’s sieve, which simplifies the initial configuration of Moessner’s sieve, by starting from two seed tuples, and creates a sequence of Moessner triangles, each constructed column by column, instead of a sequence of successive powers, constructed row by row.

The dual of Moessner’s sieve was obtained by first observing that the traditional Moessner’s sieve implicitly constructs triangles, called Moessner triangles, when we preserve the alignment of the elements of the intermediate result sequences while repeatedly dropping elements in the sequence. Combining this observation with the fact that each row and column in a Moessner triangle can be created using the same procedure, makeTuple, led to the definition of two symmetric triangle creation procedures, createTriangleHorizontally and createTriangleVertically, each taking two tuples, one corresponding to a slice of an initial sequence and one corresponding to the hypotenuse of the previous triangle, if any. By further combining the tuple-based approach with the observation that Moessner’s sieve can be initialized from a sequence of a followed by s, and the observation that the first triangle created by Moessner’s sieve is always Pascal’s triangle, resulted in a minimal initial configuration of Moessner’s sieve starting from a single seed value, , while all other values of the respective seed tuples are . Lastly, by using the new initial configuration together with the procedure createTriangleVertically paved the way for defining the dual procedure of Moessner’s sieve, createTrianglesVertically, which creates a sequence of Moessner triangles instead of a sequence of successive powers.

This post - and the previous - was a small excerpt from my Master’s thesis, in which I also prove the equivalence relation of the two triangle creation procedures.

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

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