A New Operator
One of the key elements to forming a 3-Triangulation is a special operator, the circular operator. Although it is briefly described in the NS1D0 paper, a longer discussion of the requirements of this operator is found in an earlier paper by the same authors.
This operator, which I will mark with the lowercase o and occasionally call the “circular operator,” must obey several properties. It must be binary (meaning it operates on two operands), it must be closed (meaning that every possible output of the operator must be a possible input to the operator), it must be commutative (meaning that a o b must equal b o a), and it must be idempotent (meaning that a o a = a). The final property of the operator is a bit more complex. It states that for every pair of values a and b in the input set, the equations
a o x = b, and
b o y = a
Must fulfill exactly one of these requirements:
a) There are two solutions for x and none for y
b) There are two solutions for y and none for x, or
c) There is one solution for x and none for y.
The easiest way to observe these requirements is through an example. The following table is taken from the paper 3-Triangulations and a Generalization of Bose’s Method.
For any two operands i and j, i o j can be found by going to the intersection of row i and column j, much like a multiplication table. Clearly, the operation is binary, as there is no way to obtain a calculation of any number of operands other than two. Observe that every output is a number between 0 and 6 inclusive, as are the input, making the operation closed. You can see that obtaining i o j will yield the same results as j o i, meaning that the operation is commutative, and that j o j will always yield j, meaning that it is idempotent.
The final requirement is best illustrated by example. Let us take a = 5 and b = 2. We can see that 5 o x = 2 has two solutions by looking at row 5. In that row we see the number 2 appears twice, at columns 0 and 4. Therefore, x can be 0 or 4. If we look at row 2, on the other hand, we will see that 5 does not appear at all, meaning that 2 o y = 5 has no solutions. Therefore, a, b = 5, 2 fits requirement a. For an example of a pair that fits requirement b, we can look at a, b = 2, 5; and for an example that fits requirement c, we can look at a, b = 2, 1.
How does this connect?
An operator with these properties and the associated input set can be used to create a 3-Triangulation (from which we can obtain an Steiner Triple System). We can generate the operator from an NS1D0 sequence of order n and with inductor x[1], x[2], … x[n-1] using this equation:
i o j = { i ; if i = j
{ i – x[i- j] + (n+1)/2 ; if i != j
The operation is defined on the sequence from 0 to n-1, inclusive. An in-depth exploration of why this operator meets the requirements can be found in the NS1D0 paper; but all of the requirements arise from the rules of NS1D0 sequences.
What is next?
Now that we have the circle operator defined for a given NS1D0 sequence and sequence of numbers, we have all the needed steps to define a 3-Triangulation. From there, it is a simple algorithm (using the sign-inductor to create the Steiner Triple System), arising from the shared properties of the two systems. Next week I plan to cover 3-Triangulations and the algorithm for creating Steiner Triple Systems from them.
Comments