Inductors and Sign Inductors
The next step in the process of finding Steiner Triple Systems from NS1D0 sequences is creating two more sequences: an inductor sequence and a sign-inductor sequence. Each of these are key in creating a “3-Triangulation,” a concept I will discuss in more depth in the future. Each of these sequences is tied to an NS1D0 sequence and generated from it. Furthermore, they both share these two properties:
1. They have length n – 1, where n is the order of the NS1D0 sequence that formed them.
2. They are numbered from 1 to n – 1, rather than numbered starting at 0, as the NS1D0 sequence is.
For this post, I will again be using the bracketed notation to denote elements of the three sequences. Specifically, an element of an NS1D0 sequence will be denoted with a[n], an element of an inductor sequence will be denoted with x[n], and an element of a sign-inductor sequence will be denoted with s[n]. For any cases of nested brackets, I will alternate between [square brackets] and {curly brackets} for reading convenience.
Inductor Sequences
The inductor sequence of an NS1D0 sequence is key to developing a special operator (which will be the topic of next week’s post) for the creation of a 3-Triangulation from that sequence. We will first discuss the creation of the sequence, and then discuss why it is guaranteed to be defined for any NS1D0 sequence as well as one of its properties.
For a given NS1D0 sequence of order n, an inductor sequence is generated as such:
For all i, 1<= i <= (n-1 )/2, x[ a{i} – a{i-1} ] = a[i] and x[ a{i – 1} – a{i} ] = a[i – 1].
Since that is rather dense, we will use an illustrative example, the NS1D0 sequence of order 7 [0,5,2,1]:
We start with an empty sequence with 6 spaces: __ __ __ __ __ __
For i = 1; a[i] = a[1] = 5, and a[i – 1] = a[0] = 0.
We take those values and insert them into x[ a{i} – a{i-1} ] = a[i] to get:
x[5-0] = 5.
We also insert them into x[ a{i – 1} – a{i} ] = a[i – 1]:
X[0-5] = 0
(The indices are in modulo n + 1 arithmetic, which can be interpreted as simply counting negative indices from the other end of the sequence.)
This makes our sequence look like this: __ 0 __ __ 5 __.
i = 2 yields:
x[-3] = 2
x[3] = 5.
Which makes our sequence __ 0 5 2 5 __.
i = 3 yields
x[-1] = 1
x[1] = 2
Which yields our final sequence: 2 0 5 2 1.
We can see that this sequence will have all of its terms filled based on rule 4 of determining NS1D0 sequences: For every integer c such that 1 <= c < n, exactly one of c OR ((-c) % n) must be expressed as the difference of two consecutive elements in the sequence.
Each NS1D0 sequence of order n and length (n + 1)/ 2 will have (n – 1)/2 differences. Given that we use the negative and positive form of each difference (e.g. 3 and -3), we will have n – 1 indices, the appropriate length for the inductor sequence. We simply have to show that there will be no overlap between them. The fourth rule of the NS1D0 sequences guarantees that this will be the case for all NS1D0 sequences.
The inductor sequence of a given NS1D0 sequence has an interesting property: it will contain a single 0 and a single 1, and every other number from the NS1D0 sequence twice. This arises from the fact that every i inserts a[i] and a[i-1] into the sequence, leading to 0 only being added to the sequence for i = 1, 1 being added to the sequence only for the final i, and every other number being reached with an i index and an i – 1 index. This property is extremely important for the formation of the circle operator I will discuss next week.
Sign-Inductor Sequences
The sign-inductor also plays a key role in the generation of the Steiner Triple System, and is generated in a similar way to the generation of the inductor sequence.
For a given NS1D0 sequence of order n, a sign-inductor sequence is generated as such:
For all i, 1<= i <= (n-1 )/2, s[ a{i} – a{i-1} ] = s[ a{i – 1} – a{i} ] = sign((-1)^i-1)
W will use the same illustrative example, the NS1D0 sequence of order 7 [0,5,2,1]:
We start with an empty sequence with 6 spaces: __ __ __ __ __ __
For i = 1, a[i] = 5, a[i- 1] = 0. Therefore, we take s[5-0] and s[0-5], and set both to the sign of -1^0 (+). This gives us the sequence __ + __ __ + __.
For i = 2, a[i] = 2, a[i- 1] = 5. Therefore, we take s[2-5] and s[5-2], and set both to the sign of -1^1 (-). This gives us the sequence __ + - - + __.
Finally, for i = 3, a[i] = 1, a[i- 1] = 2. Therefore, we take s[1-2] and s[2-1], and set both to the sign of -1^2 (+). This gives us the sequence + + - - + +.
We can see that each term in the sign-inductor will be defined for the same reason as each term in the inductor being defined.
Comentarios