How to make perfect CDSs

None of the semi-affine CDSs are perfect. The modulus of a semi-affine CDS of size s is s^2-1, which is a bit more than the modulus s^2-s+1 we need for a perfect CDS. On this page we will try to explain a construction method for perfect CDSs of certain sizes, which is vaguely similar to the method on the previous page.

Consider the sequence that starts with 0,0 and 1, and in which every element is the sum of the three numbers before it:

   0   0   1   1   2   4   7  13  24  44  81 149 274 504 927 ...

Now construct the modular version, say for q=3. This sequence eventually repeats itself (it has period 26) but we only need the portion between two occurences of two consecutive zeroes:

   0   0   1   1   2   1   1   1   0   2   0   2   1   0   0  ...

Mark every element in the sequence which is equal to zero (yes, I do mean 0, not 1 as in the semi-affine case). Write down the positions of these marks:

 sequence :  0  0  1  1  2  1  1  1  0  2  0  2  1 ( 0  0 ...)
 marks    :  #  #                    #     #
 numbering:  0  1  2  3  4  5  6  7  8  9 10 11 12 (13)

You have just constructed the perfect CDS {0,1,8,10} with modulus 13. This is its difference table:

   0   1   8  10   (13)
  12   0   7   9
   5   6   0   2
   3   4  11   0

As before, this trick only works when q is a prime number. Moreover, for most prime numbers we probably need another sequence.

Meet the rest of the family!

Fibonacci's nephews were determined by 2 different numbers A and B. The sequences we use for perfect CDSs are determined by a triple (A,B,C) - they are appropriately called `linear recurrences of degree three'. The general rule now reads :

Every number in the sequence is equal to A times the previous number plus B times the number before that, plus C times the number which stands 3 positions in front of the original number. The sequence always starts with 0,0,1.

The example above made use of the (1,1,1)-series. The next example uses (1,0,1) with q=2:

 sequence : 0  0  1  1  1  2  3  4  6  9 13 19 28 41 60 88 ...
 mod 2    : 0  0  1  1  1  0  1 (0  0  1  1  1  0  1  0  0 ... 
 marks    : #  #           #
 numbering: 0  1  2  3  4  5  6 (7)

This gives us the perfect CDS {0,1,5} modulo 7.

In general, for any prime q we may find an (A,B,C)-sequence such that the second consecutive pair of zeroes occurs at position q^2+q+1 (if we start counting positions at 0). Such a sequence - when taken modulo q - always generates a perfect CDS of modulus q^2+q+1 and size q+1 when you apply the procedure as sketched above.

For any given prime number q there are many (A,B,C)-sequences with the required properties, but there is no general rule to find them. The following rules may help to guide your search:

It is only necessary to try sequences with A,B in the range 0..q-1 and C in the range 1..q-1. Moreover, it is of no use to try a sequence with both A and B equal to zero.
If there is a number z such that z^3 (z cubed) equals A*z^2 +B*z +C (mod q) then the sequence will NOT work.

A last word of warning! The size of the CDS generated is one more than the prime number q - with semi-affine CDSs they were equal. So, although 5 is prime, you cannot use this method to construct a perfect CDS of size 5. The case q=5 leads to a CDS of size 6!

Problems

Build a perfect CDS of size 6.
Write down all shifts of the CDS of size 4 and draw a picture of the resulting semi-linear space. What would be the axioms for such a semi-linear space?
Verify that these axioms also hold in the `Fano'-plane depicted on the right.

Projective planes

97/01/03 - Kris Coolsaet