Other CDSs

As was told on the previous page - what do you mean you didn't read it? - perfect CDSs do exist when q is 4 or 8 or 9 but they must be generated in a different way. Likewise, there are also semi-affine CDSs for those orders. It will probably not surprise you to hear that we again need linear recurrences, but of higher degree than 3. Degree 4 yields semi-affine CDSs of order p^2, with p a prime. Degree 6 yields semi-affine CDSs of order p^3, with p a prime, and - with a different technique - perfect CDSs of size p^2+1 as well. Degree 9 can be used to generate perfect CDSs of size p^3+1.

We shall simply illustrate the methods by means of some examples. The details are left to your imagination.

A semi-affine CDS of order 4.

We use the (1,0,0,1)-sequence modulo p=2:

  0  0  0  1  1  1  1  0  1  0  1  1  0  0  1 (0  0  0  1 ...

This sequence has period 15 (which is 4^2-1). Move this sequence 5 positions (which is 4+1) to the left and copy it underneath the original. Mark all columns with a zero in the first row and a one in the bottom row.

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

You end up with the semi-affine CDS {0,1,9,13} modulo 15.

A semi-affine CDS of order 9.

For q=9=3^2 you may use the (1,2,2,1)-sequence modulo 3 and move it over 10 positions. This yields {0,5,18,24,26,27,41,69,73} modulo 80. (Check it!)

A semi-affine CDS of order 8.

Use the (1,0,0,0,0,1)-sequence modulo p=2.

  000001111110101011001101110110100100111000101111001010001100001(000...

This sequence has period 63 (q^2-1 in general). Copy and shift it to the left 9(=q+1) positions and copy and shift it again. Mark all columns that contain 0,0,1 from top to bottom.

  000001111110101011001101110110100100111000101111001010001100001
  110101011001101110110100100111000101111001010001100001000001111 
  001101110110100100111000101111001010001100001000001111110101011
    #                       #     # #    #           #  ##

You end up with the semi-affine CDS {0,24,30,32,37,49,52,53} modulo 63.

A perfect CDS of size 5 (order q=4).

Use the same (1,0,0,0,0,1)-sequence modulo p=2. The period of this sequence is 63 (q^3-1). Take the first part of length q^2+q+1 (21 in this case) and write the next part of the same length underneath. Mark all columns that contain 2 zeroes.

  000001111110101011001
  101110110100100111000 101111001010001100001(000...
   #         # #    ##

The perfect CDS we have now obtained is {0,10,12,17,18} modulo 21.

A perfect CDS of size 9 (order q=8=p^3 with p=2).

For this method you will need a computer, so we will not go into great detail.

First you need to find a linear recurrence of degree 9 whose modular variant (modulo p) has a period of q^3-1. In this case this means a period of 511 and the next case (p=3,q=27) already needs a period of 19682. For a given prime there are many linear recurrences that work, but too few to risk searching them by hand. You won't need the entire sequence, but you need to check the period to make sure that you are working with a `good' sequence.

Now write the three initial segments of size q^2+q+1 of this sequence onto separate lines. Mark all columns that consist entirely of zeroes. You have found the perfect CDS you were looking for.

[ I know of at least one other method to generate CDSs for non-prime orders, but their construction involves the theory of `finite fields' an explanation of which would lead us way too far (maybe some other time?). Anyhow, the work involved is about the same: you also need a computer for the larger cases. ]

Problems

(Guess ?) Find a perfect CDS of size 9 using the method above.
Can you extrapolate the methods for q=p^3 to methods for q=p^4? Use them to find a semi-affine CDS of size 16 (and modulus 255).
Prove that these methods always work. [ I haven't seen these methods written down anywhere else and I haven't exactly written down a complete proof myself (yet). Mathematical Intuition tells me that they are correct, let us hope that she is right. ]

New sets for old: multipliers

97/01/03 - Kris Coolsaet