What is a Non-Sum-One-Difference-Zero Sequence?

Introduction

In 2002, Feliu Sagols and Charles J. Colbourn proposed the non-sum-one-difference-zero sequence, also known as NS1D0 sequences (2002). In this paper, the authors define the NS1D0 sequence. They further show that an NS1Do sequence can be used to produce an anti-Pasch Steiner Triple System. Finally, they show a relationship between NS1D0 sequences and the classic N-Queens Problem. In this article, we will exam what an NS1D0 sequence is, how to make an anti-Pasch Steiner Triple System, and lastly why we might want to. You can read more about Steiner Triple Systems here. If you have never worked with them before please read that introduction first.

NS1D0 Rules

Feliu Sagols and Charles J. Colbourn, give four rules for an NS1D0 sequence (2002). We will expand these into six rules. This makes it a little easier to talk about the sequences because there are will be no compound rules. Each is simple and distinct.

Let $n$ be an odd integer and $n>1$. An NS1D0(n) sequence is an ordered list of unique integers selected from 0 to $n-1$ that meets the following requirements. We call the input to this function $n$ the order of the sequence.

  1. The sequence must contain exactly $\frac{n-1}{2}+1$ integers
  2. The sequence must start with 0
  3. The sequence must end in 1
  4. The sequence cannot include $\left \lceil \frac{n}{2} \right \rceil$. (The ceiling symbol means round up.)
  5. For any number $1 < x < n$ you can have either $x$ or $((1-x) \mod n)$, but not both.
  6. For each integer $j=1,2,3,\cdots,n-1$ only one of the numbers $j$ or $(-j \mod n)$ can be expressed as $(a_{k} - a_{k-1}) \mod n$ where $k$ in an index into the array $(k=1,2,\cdots,(n-1)/2)$. Additionally, only one $k$ value can map to each pair $(j, -j \mod n)$.

Some of these rules use modular arithmetic. It is useful review the meaning of this operator, especially related to negative numbers.

The expression $a \mod b$ gives the modulo (remainder of division) from $\frac{a}{b}$. This is easy to define for positive numbers.

The quotient is the fraction rounded down to the nearest integer.

Let’s experiment with $a=9$ and $b=2$.

\[\left \lfloor \frac{a}{b} \right \rfloor = \left \lfloor \frac{9}{2} \right \rfloor = 4\]

The quotient is 4. The remainder is

\[a - q * b = 9 - 2 * 4 = 9-8 = 1\]

Therefore $9 \mod 2 = 1$

What happens when we ask $-1 \mod 2$.

\[\left \lfloor \frac{a}{b} \right \rfloor = \left \lfloor \frac{-1}{2} \right \rfloor = 0\] \[-1 - 0 * 2 = -1\]

That is what the formula says, but we still have a negative number. There is an alternative solution to this modulo problem.

\[(-1 \mod 2) = 1\]

Since the first value $-1$ is less than the second value $2$, we can say the mod is $2-1=1$.

Think of the values as a circle. If we are working modulo $2$ then the possible values are $0,1$. When we ask for $-1 \mod 2$ we are moving backwards from the end of the sequence 1 step.

For example, we want to find $(-6 \mod 9)$. Since this problem is modulo 9, the possible values are $0,1,2,3,4,5,6,7,8$. If we start at the end and count back 6 positions we get to $3$. We get $(-6 \mod 9)=3$.

We can define our modulo algorithm. Python would do this correctly, but not all languages handle negatives the same way.

def mod(a,b):
    if b==0:
        raise Exception("Bad Input!")
    if a >= 0:
        q = math.floor(a/b)
        r = a - q * b
        return r
    r = mod(abs(a),b)
    if r!=0:
        r = b - r
    return r

The easiest way to explain the rules is by example. We will generate some sequences. Since $n > 1$ and $n$ must be odd, the smallest number we can try is 3.

Creating NS1D0(3)

For NS1D0(3), the possible numbers we can select for our sequence are: $0,1,2$. By rule 4, the sequence cannot include

\[\left \lceil \frac{n}{2} \right \rceil = \left \lceil \frac{3}{2} \right \rceil=2\]

By Rule 1, the sequence must contain $\frac{3-1}{2}+1=\frac{2}{2}+1=2$ values. Rule 2 says the sequence must start with $0$ and Rule 3 says it must end in $1$. There is only one sequence possible.

\[\text{NS1D0(3)} = \lbrace (0, 1) \rbrace\]

This sequence trivially means rules 5 and 6. It is not a useful example to explain those two rules.

Creating NS1D0(5)

Things get a little more interesting with order 5. All the values from $0$ to $5-1$ are: $0, 1, 2, 3, 4$. One and Zero have reserved positions which leaves us with $2,3,4$. By rule 4 we need to remove $\left \lceil \frac{5}{2} \right \rceil=3$. This leaves us with just $2,4$. By Rule 1, the sequence must contain $\frac{5-1}{2}+1=\frac{4}{2}+1=3$ values.

To make a sequence that starts with 0, ends with 1, and contains 3 values, we don’t have many options.

Potential Sequences
$(0, 2, 1)$
$(0, 4, 1)$

Next, we need to check Rule 5: “For any number $1 < x < n$ you can have either $x$ or $((1-x) \mod n)$, but not both.”

$x$ $((1-x) \mod n)$
$2$ $((1-2) \mod 5)=4$
$3$ $((1-3) \mod 5)=3$
$4$ $((1-4) \mod 5)=2$

Neither of our two sequences contain the pairs (2,4), (3,3), or (4,2).

Lastly, we need to check Rule 6: “For each integer $j=1,2,3,\cdots,n-1$ only one of the numbers $j$ or $(-j \mod n)$ can be expressed as $(a_{k} - a_{k-1}) \mod n$ where $k$ in an index into the array $(k=1,2,\cdots,(n-1)/2)$.”

We will first generate the pairs we need to check for.

$j$ $-j \mod n$
$1$ $-1 \mod 5=4$
$2$ $-2 \mod 5=3$
$3$ $-3 \mod 5=2$
$4$ $-4 \mod 5=1$

There are two pairs here (1,4) and (2,3) that cannot appear when we account for the Rule 6 calculation. We now need to iterate each sequence for $(k=1,2,\cdots,(n-1)/2)$.

Potential Sequence $k$ $(a_{k} - a_{k-1}) \mod n$
$(0, 2, 1)$ $1$ $(a_{1} - a_{0}) \mod 5=2-0 \mod 5 = 2$
$(0, 2, 1)$ $2$ $(a_{2} - a_{1}) \mod 5=1-2 \mod 5 = 4$
$(0, 4, 1)$ $1$ $(a_{1} - a_{0}) \mod 5=4-0 \mod 5 = 4$
$(0, 4, 1)$ $2$ $(a_{2} - a_{1}) \mod 5=1-4 \mod 5 = 2$

Neither sequence can compute both numbers in one of the Rule 6 pairs. Both are value.

\[\text{NS1D0(5)} = \lbrace (0, 2, 1), (0, 4, 1) \rbrace\]

Creating NS1D0(7)

Order 7 is the first time rules 5 and 6 really make an impact.

Since the value $n=7$ we much select integers from the following set ${0, 1, 2, 3, 4, 5, 6}$.

The length of the sequence is given by Rule 1.

\[\frac{7-1}{2}+1 = \frac{6}{2}+1 = 3+1 = 4\]

We need to have a sequence with exactly 4 elements.

\[(?, ?, ?, ?)\]

Rule 2 says the sequence must start with 0.

\[(0, ?, ?, ?)\]

Rule 3 says the sequence must end with 1.

\[(0, ?, ?, 1)\]

Rule 4 asy that $\left\lceil \frac{7}{2} \right\rceil=4$ cannot appear in the sequence.

After following rules 1-4, we are left with ${2, 3, 5, 6}$ to fill in the last two blanks.

Rule 5 says there are certain pairs that cannot appear in the sequence.

Rule 5: For any number $1 < x < n$ you can have either $x$ or $((1-x) \mod n)$, but not both.

We can generate the pairs and see what we get. There is no point in testing 4 because it was already eliminated.

  • $x=2$ and $(1-2 \mod 7)=6$
  • $x=3$ and $(1-3 \mod 7)=5$
  • $x=5$ and $(1-5 \mod 7)=3$
  • $x=6$ and $(1-6 \mod 7)=2$

We cannot select both (2 and 6). We also cannot select both (3 and 5). We look at all the ways we can fill in the last two blanks and eliminate any that break this rule

  • $(0, 2, 3, 1)$
  • $(0, 2, 5, 1)$
  • $(0, 2, 6, 1)$ breaks Rule 5
  • $(0, 3, 2, 1)$
  • $(0, 3, 5, 1)$ breaks Rule 5
  • $(0, 3, 6, 1)$
  • $(0, 5, 2, 1)$
  • $(0, 5, 3, 1)$ breaks Rule 5
  • $(0, 5, 6, 1)$
  • $(0, 6, 2, 1)$ breaks Rule 5
  • $(0, 6, 3, 1)$
  • $(0, 6, 5, 1)$

We are down to the following options.

  • $(0, 2, 3, 1)$
  • $(0, 2, 5, 1)$
  • $(0, 3, 2, 1)$
  • $(0, 3, 6, 1)$
  • $(0, 5, 2, 1)$
  • $(0, 5, 6, 1)$
  • $(0, 6, 3, 1)$
  • $(0, 6, 5, 1)$

We have one rule left. We need to eliminate sequences that break Rule 6.

Rule 6: For each integer $j=1,2,3,\cdots,n-1$ only one of the numbers $j$ or $(-j \mod n)$ can be expressed as $(a_{k} - a_{k-1}) \mod n$ where $k$ in an index into the array $(k=1,2,\cdots,(n-1)/2)$. Additionally, only one $k$ value can map to each pair $(j, -j \mod n)$.

It helps to generate the pairs $j$ and $(-j \mod n)$ first.

  • $j=1$ and $(-1 \mod 7)=6$
  • $j=2$ and $(-2 \mod 7)=5$
  • $j=3$ and $(-3 \mod 7)=4$
  • $j=4$ and $(-4 \mod 7)=3$
  • $j=5$ and $(-5 \mod 7)=2$
  • $j=6$ and $(-6 \mod 7)=1$

Now we subtract the pairs in the sequence to see if any of these numbers come up.

Test Sequence 1: $(0, 2, 3, 1)$

$(2-0) \mod 7 = 2$

$(3-2) \mod 7 = 1$

$(1-3) \mod 7 = 5$

This sequence fails because 5 and 2 both appear!

Test Sequence 2: $(0, 2, 5, 1)$

$(2-0) \mod 7 = 2$

$(5-2) \mod 7 = 3$

$(1-5) \mod 7 = 3$

This sequence fails because 3 appears twice.

Test Sequence 3: $(0, 3, 2, 1)$

$(3-0) \mod 7 = 3$

$(2-3) \mod 7 = 6$

$(1-2) \mod 7 = 6$

This sequence fails because 6 appears twice.

Test Sequence 4: $(0, 3, 6, 1)$

$(3-0) \mod 7 = 3$

$(6-3) \mod 7 = 3$

$(1-6) \mod 7 = 2$

This sequence fails because 3 appears twice.

Test Sequence 5: $(0, 5, 2, 1)$

$(5-0) \mod 7 = 5$

$(5-2) \mod 7 = 4$

$(1-2) \mod 7 = 6$

This sequence passes the test.

Test Sequence 6: $(0, 5, 6, 1)$

$(5-0) \mod 7 = 5$

$(6-5) \mod 7 = 1$

$(1-6) \mod 7 = 2$

This sequence fails because 5 and 2 both appear!

Test Sequence 7: $(0, 6, 3, 1)$

$(6-0) \mod 7 = 6$

$(3-6) \mod 7 = 4$

$(1-3) \mod 7 = 5$

This sequence passes the test.

Test Sequence 8: $[0, 6, 5, 1]$

$(6-0) \mod 7 = 6$

$(5-6) \mod 7 = 6$

$(1-5) \mod 7 = 3$

This sequence fails because 6 appears twice.

After applying Rule 6 we learn:

  • $(0, 2, 3, 1)$ Breaks Rule 6
  • $(0, 2, 5, 1)$ Breaks Rule 6
  • $(0, 3, 2, 1)$ Breaks Rule 6
  • $(0, 3, 6, 1)$ Breaks Rule 6
  • $(0, 5, 2, 1)$
  • $(0, 5, 6, 1)$ Breaks Rule 6
  • $(0, 6, 3, 1)$
  • $(0, 6, 5, 1)$ Breaks Rule 6

After eliminating all sequences that break the rules, we are left with two NS1D0(7) sequences.

\[\text{NS1D0}(7)=\lbrace (0, 5, 2, 1), (0, 6, 3, 1)\rbrace\]

Solutions to NS1D0(9)

There are six sequences for order 9.

  • $(0, 2, 3, 6, 1)$
  • $(0, 6, 2, 3, 1)$
  • $(0, 2, 6, 7, 1)$
  • $(0, 3, 4, 8, 1)$
  • $(0, 4, 7, 8, 1)$
  • $(0, 7, 8, 4, 1)$

Number of Sequences

We have computed the number of sequences that exist for different orders of $n$. Thanks to my CS361 Fall 2022-2023 class for helping with this list.

Order Total Sequences
$\text{NS1D0(3)}$ 1
$\text{NS1D0(5)}$ 2
$\text{NS1D0(7)}$ 2
$\text{NS1D0(9)}$ 6
$\text{NS1D0(11)}$ 14
$\text{NS1D0(13)}$ 80
$\text{NS1D0(15)}$ 304
$\text{NS1D0(17)}$ 1,636
$\text{NS1D0(19)}$ 2,004,500

What to do with an NS1D0 Sequence

Ok, you have a NS1D0 sequence. Now, what can you do with it? We can make an anti-Pasch Steiner Triple System.

We need to generate a variety of values to make our anti-Pasch Steiner Triple System. Actually, first we will make a Steiner Triple System. Then we will check our NS1D0 sequence to predict if the result will be anti-Pasch or not.

Inductor

An inductor is a sequence $x_1, x_2, \cdots, x_{n-1}$ generated from NS1D0(n)=$(a_0, a_1, \cdots, a_{(n-1)/2})$. The inductor sequence is defined for $1 \le i \le \frac{n-1}{2}$ where

$x_{a_i - a_{i-1}} = a_i$ and $x_{a_{i-1}-a_{i}} = a_{i-1}$

For this example, we select our first NS1D0(7) sequence $(0, 5, 2, 1)$ as an example.

$a=(a_0=0, a_1=5, a_2=2, a_3=1)$

Since we have $n=7$, then the inductor takes values from $1 \le i \le 3$ to generate $x_1, x_2, \cdots, x_{6}$. If the subscript is negative it is computed $\mod n$.

$i$ $x_{a_i - a_{i-1}} = a_i$ Result
1 $x_{a_1 - a_{0}} = a_1$ $x_{5-0}=x_{5}=5$
2 $x_{a_2 - a_{1}} = a_2$ $x_{2-5}=x_{-3}=x_{4}=2$
3 $x_{a_3 - a_{2}} = a_3$ $x_{1-2}=x_{-1}=x_{6}=1$
$i$ $x_{a_{i-1}-a_{i}} = a_{i-1}$ Result
1 $x_{a_{0}-a_{1}} = a_{0}$ $x_{0-5}=x_{-5}=x_{2}=0$
2 $x_{a_{1}-a_{2}} = a_{1}$ $x_{5-2}=x_{3}=5$
3 $x_{a_{2}-a_{3}} = a_{2}$ $x_{2-1}=x_{1}=2$

Puts the values in $x$ in order we get

$x=(x_{1}=2, x_{2}=0, x_{3}=5, x_{4}=2, x_{5}=5, x_{6}=1)$

For $(0, 5, 2, 1)$ we have the inductor $x=(2,0,5,2,5,1)$

Our second NS1D0(7) sequence $(0, 6, 3, 1)$ creates $x=(0,3,6,3,1,6)$.

The algorithm to generate an inductor is given below. It clearly as an $O(n)$ runtime. Note that $x$ is formally indexed starting at $x_1$ but arrays traditionally start at $x_{0}$. To account for this with minimal issues later, we place a $-1$ into position $x_0$ as a placeholder. This will make off-by-one errors easier to avoid in later steps.

def inductor(A,n):
    X=[-1 for x in range(0,n)]
    X[0]=-1 #Buffer Space
    for i in range(1,(n-1)//2+1):
        index = mod((A[i]-A[i-1]),n)
        value = A[i]
        X[index]=value
        index = mod((A[i-1]-A[i]),n)
        value = A[i-1]
        X[index]=value
    return X

3-Triangulation

The inductor sequence is used to make a function called a 3-triangulation that will be used in a later set. The value of $x_{i-j}$ in this formula will be taken from the inductor.

$i \circ j = \begin{cases} i-x_{(i-j) \mod n}+\lceil \frac{n}{2} \rceil & i \neq j \ i & i= j \end{cases}$

The three triangulation can be shown as a square (Colbourn 1999). Note: In code we will call this circ(i,j).

Sequence $(0, 5, 2, 1)$ generates the following triangulation.

circ(Row,Col)0123456
00362642
13140305
26425141
32053625
46316403
54042051
62515316

Sequence $0, 6, 3, 1$ generates the a different triangulation.

circ(Row,Col)0123456
00531514
15164262
23620530
31403164
45251420
51636253
64204036

Sign Inductor

A sign inductor of a sequence NS1D0(n) is a sequence $S=(s_1, s_2, \cdots, s_{n-1})$ such that for all $1 \le i \le \frac{n-1}{2}$ we have $s_{a_i-a_{i-1}} =s_{a_{i-1}-a_{i}}=\text{sign}((-1)^{i-1})$.

We generate the sign inductor of our first NS1D0(7) sequence $(0, 5, 2, 1)$ as an example.

Remember that $A=(a_0=0, a_1=5, a_2=2, a_3=1)$. As always, negative numbers are $\mod n$.

$i$ $s_{a_i-a_{i-1}}$ $s_{a_{i-1}-a_{i}}$ $(-1)^{i-1}$
1 $s_{a_{1}-a_{0}}=s_{5}$ $s_{a_{0}-a_{1}}=s_{2}$ $(-1)^{1-1}=1$
2 $s_{a_{2}-a_{1}}=s_{4}$ $s_{a_{1}-a_{2}}=s_{3}$ $(-1)^{2-1}=-1$
3 $s_{a_{3}-a_{2}}=s_{6}$ $s_{a_{2}-a_{3}}=s_{1}$ $(-1)^{3-1}=1$

We have the sign inductor for this sequence

$S = (s_{1}=1, s_{2}=1, s_{3}=-1, s_{4}=-1 , s_{5}=1 , s_{6}=1)$

The sign inductor sequence for $(0, 5, 2, 1)$ is $(1,1,-1,-1,1,1)$.

The sign inductor sequence for $(0, 6, 3, 1)$ is $(1,1,-1,-1,1,1)$.

The algorithm to generate a sign inductor is given below. It clearly as an $O(n)$ runtime. Again, we use a placeholder value at $s_0$ to account for zero indexed arrays.

def signInductor(A,n):
    S=[-1 for x in range(0,n)]
    S[0]=0 #Buffer Space
    for i in range(1,(n-1)//2+1):
        index01 = mod(A[i]-A[i-1],n)
        index02 = mod(A[i-1]-A[i],n)
        sign = (-1)**(i-1)
        S[index01]=sign
        S[index02]=sign
    return S

Once we have the sign inductor we can create a signing function.

$\sigma(i,j) = s_{(i-j)\mod n}$

We will use this function in a later step.

Building a Stiener Triple System

We now have all the tools we need to build a Steiner Triple System. We will return to our order 3 sequence for this example. Once the general algorithm has been given it can be used with any sequence tha meets our requirements.

\[\text{NS1D0(3)} = \lbrace (0, 1) \rbrace\]

We have our inductor sequence.

\[X=[1,0]\]

We have our sign inductor sequence.

\[S=[1,1]\]

We know the size of the sequence $\text{NS1D0(3)}$ means $n=3$.

We are going to make $STS(3n)$. This only works when $n \mod 4 = 3$ (Sagol and Colbourn 2002). We can find an $\text{NS1D0}(5)$ sequence but since $5 \mod 4 = 1$ we won’t get the Steiner Triple System we desire.

The order of the Steiner Triple System is $v$. We want to make $STS(v)$ where $v=3n$. We need to create a $n$ by $3$ array of elements from $1,2,\cdots,v$ (Colbourn 1999). We will call this array $M$.

\[M=\begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \\ \end{bmatrix}\]

We already know how to make $i \circ j$ and $\sigma(i,j)$ from the inductor sequences.

The first set of triples are made by selecting elements from $M$ as $a$ goes from $0$ to $n-1$.

\[\lbrace M[a][0], M[a][1], M[a][2] \rbrace\]

Now, we need to make three sets by selecting $a$ and $b$ where $b$ goes from $0$ to $n-1$ and $a$ goes from $0$ to $b-1$. We make three triples for each pair $a$ and $b$.

\(\lbrace M[a][0], M[a \circ b][(0+\sigma(a,b)) \mod 3], M[b][0] \rbrace\) \(\lbrace M[a][1], M[a \circ b][(1+\sigma(a,b)) \mod 3], M[b][1] \rbrace\) \(\lbrace M[a][2], M[a \circ b][(2+\sigma(a,b)) \mod 3], M[b][2] \rbrace\)

Once we put all these pairs together we get the following Steiner Triple System.

\[STS(9)= \lbrace \lbrace 1, 4, 7 \rbrace, \lbrace 2, 5, 8 \rbrace, \lbrace 3, 6, 9 \rbrace, \lbrace 1, 6, 2 \rbrace, \lbrace 4, 9, 5 \rbrace, \lbrace 7, 3, 8 \rbrace, \lbrace 1, 5, 3 \rbrace, \lbrace 4, 8, 6 \rbrace, \lbrace 7, 2, 9 \rbrace, \lbrace 2, 4, 3 \rbrace, \lbrace 5, 7, 6 \rbrace, \lbrace 8, 1, 9 \rbrace \rbrace\]

The full algorithm for generating a Stiener Triple System from an NS1D0 sequence is given below.

def makeSTS(ns1d0):
    n = determineSize(ns1d0)
    if mod(n,4)!=3:
        raise Exception("Cannot use this size")
    I = inductor(ns1d0,n)
    S = signInductor(ns1d0,n)
    v = 3*n
    M = createElements(v)
    circ = makeCircle(I,n)
    sigma = makeSigma(S,n)
    #Create Steiner Triple Syste
    STS = makeSet()
    for a in range(0,n):
        t = makeSet(M[a][0],M[a][1],M[a][2])
        STS = union(STS,makeSet(t))
    for b in range(0,n):
        for a in range(0,b):
            for j in range(0,3):
                val1 = M[a][j]
                val2 = M[circ(a,b)][mod(j+sigma(a,b),3)]
                val3 = M[b][j]
                t = makeSet(val1,val2,val3)
                STS = union(STS,makeSet(t))
    return STS

anti-Pasch Steiner Triple Systems

Finally, we ask if the Steiner Triple System is anti-Pasch. This is where we will have a big advantage. Determining if the NS1D0 sequence produces a anti-Pasch system is a $O(n^2)$ question (Sagol and Colbourn 2002).

A Pasch configuration is a set of $6$ elements orgnaized into $4$ triples. Take the elements $a,b,c,d,e,f$ then the configuration is the blocks $\lbrace a,b,c \rbrace$, $\lbrace a, d, e \rbrace$, $\lbrace f, d,b \rbrace$, and $\lbrace f,c,e \rbrace$ (Sagol and Colbourn 2002). An anti-Pasch Steiner Triple System does not contain the Pasch configuration.

There are five properties that need to be true of the Inductor and Sign Inductor sequences for them to generate an anti-Pasch Steiner Triple System (Sagol and Colbourn 2002). Let $X$ be the Inductor and $S$ be the Sign Inductor. There cannot exist two numbers $a,b \in \lbrace 0,1,2,\cdots,n-1 \rbrace$ such that one of the properties is satisfied. The indexes of $X[i]$ and $S[j]$ must be selected such that $X[0]$ and $S[0]$ never appear. Let $h=\lceil \frac{n}{2} \rceil$.

As given in (Sagol and Colbourn 2002):

AP-1:

\(-h+a-b+X[-h+b+X[-h-b+X[-h+b+X[-a]]]] = 0\) \(S[h-b-X[-h-b+X[-h+b+X[-a]]]] = S[h-b-X[-a]] \neq S[-a] = S[h+b-X[-h+b+X[-a]]]\)

AP-2:

\(h+X[a]-X[a-b]-X[a-b-X[a-b]+X[b]] = 0\) \(S[a-b]=S[b]=S[a-b-X[a-b]+X[b]] \neq S[a]\)

AP-3:

\(X[a]-X[b]-X[b+X[a]-X[b]]+X[a-X[a]+X[b]]=0\) \(S[a]=S[b]\) \(S[b+X[a]-X[b]]=S[a-X[a]+X[b]]\)

AP-4:

\(-h+a+X[-h-a+X[-h+X[a]]]=0\) \(S[-h-a+X[-h+X[a]]]=S[-h+X[a]] \neq S[a]\)

AP-5:

\(-h-a+X[-h+X[-h+X[a]]]=0\) \(S[a]=S[-h+X[a]]=S[-h+X[-h+X[a]]]\)

We just have two variables and $n$ values to loop over. All the calculations are obviously $O(1)$, which means testing for the anti-Pasch property is $O(n^2)$.

Conclusion

If you happen to have an NS1D0 sequence laying around your house collecting dust, you can upcycle it into a Steiner Triple System. The requirements of the NS1D0 sequences are very strict. This means there might be some potential to find an algorithm to construct them directly. Testing if our NS1D0 sequence will generate an anti-Pasch Steiner Triple System is also easier than checking the system directly.

References

Colbourn, Charles, et al. Triple Systems (Oxford Mathematical Monographs). 1st ed., Clarendon Press, 1999.

Sagols, Feliu and Charles J. Colbourn. “NS1D0 Sequences and Anti-Pasch Steiner Triple Systems.” Ars Comb. 62 (2002): 17-31.