Projective planes

[ If you are not really interested in the geometrical aspects of CDSs but simply want to build more and more CDSs, you may skip this section (and your name will be Mud). ]

Let us have a closer look at the semi-linear space generated by a perfect CDS. Consider for example the shifts of the CDS {0,1,8,10} with modulus 13:

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

The drawing on the right represents the associated semi-linear space. Notice how the picture of the affine plane of order 3 is hidden inside this illustration. This indicates how the new semi-linear space could have been derived from the affine plane:

Add q points, one for each parallel class (of lines). In the picture these are point 9 for the blue class, point 6 for the red class, point 4 for the green class and point 10 for the black class. (These new points are called points at infinity - even in a finite plane.)
Extend each line so that it now also contains the point of infinity of the parallel class to which that line belongs.
Add a single line that contains all points at infinity (the purple line). This line is called the line at infinity.

The semi-linear space obtained in this way is called a projective plane of order q. It has q^2+q+1 points, q^2+q+1 lines and there are q+1 points on each line (take care, that is one more than the order) and q+1 lines through each point.

Defining axioms

Every projective plane has the following properties - as can easily be verified in the example above:

Two lines always intersect in exactly one point.
For any two points there is always exactly one line which contains both of them.

These properties are usually taken to be the definition of a projective plane (together with the requirement that each line contains at least 3 points). There is no need to know about affine planes (let alone semi-affine planes) to be able to study these planes - and well-studied they are indeed.

All the projective planes which are known at this time have an order q which is either a prime number or an integral power of a prime (i.e., a prime multiplied by itself a number of times - e.g., 8=2*2*2). Most of them are cyclic and as far as I know all the cyclic projective planes can be generated by one of the methods listed in these pages (a method for non-prime orders follows later). If there is a cyclic projective plane with an order which is not prime or a power of a prime, then its order must be really big.

It can be proved that there are no projective planes (not even non-cyclic ones) of order 6 or 10. Hence, there are no perfect CDSs of size 7 or 11.

Coordinates

It is also possible to assign coordinates to points of the projective planes generated here, although this is a little more complicated than in the semi-affine case. We shall illustrate this in the case q=3, i.e., the projective plane of order 3 with 4 points on each line and 13 points in total.

To each point we assign a triple of coordinates (x,y,z) and to each line we assign a similar triple [u,v,w]. All possible triples with x,y,z,u,v,w in the range 0..q-1 may be used, except (0,0,0) and [0,0,0]. Different points must always have different coordinate triples, but - and this is what makes it more difficult than in the semi-affine case - different coordinates may belong to the same point (or line) according to the following rule: If two sets of coordinates belong to the same point (or line), then you must be able to obtain one set from the other by multiplying each of the three coordinates by the same number, always using arithmetic modulo q.

For example, the triples (1,0,1) and (2,0,2) are coordinates of the same point, while (1,0,1) and (1,1,1) belong to different points. It can be proved that every point (and line) possesses exactly q-1 different coordinate triples.

The following table lists all coordinates of the 13 points and lines in the projective plane of order 3:

points                         lines
---------------------------------------------------------
p0    | (0,0,1) (0,0,2)        L0    | [0,0,1] [0,0,2]
p1    | (0,1,1) (0,2,2)        L1    | [0,1,1] [0,2,2]
p2    | (1,1,2) (2,2,1)        L2    | [1,1,2] [2,2,1]
p3    | (1,2,1) (2,1,2)        L3    | [1,2,1] [2,1,2]
p4    | (2,1,1) (1,2,2)        L4    | [2,1,1] [1,2,2]
p5    | (1,1,1) (2,2,2)        L5    | [1,1,1] [2,2,2]
p6    | (1,1,0) (2,2,0)        L6    | [1,1,0] [2,2,0]
p7    | (1,0,2) (2,0,1)        L7    | [1,0,2] [2,0,1]
p8    | (0,2,0) (0,1,0)        L8    | [0,2,0] [0,1,0]
p9    | (2,0,2) (1,0,1)        L9    | [2,0,2] [1,0,1]
p10   | (0,2,1) (0,1,2)        L10   | [0,2,1] [0,1,2]
p11   | (2,1,0) (1,2,0)        L11   | [2,1,0] [1,2,0]
p12   | (1,0,0) (2,0,0)        L12   | [1,0,0] [2,0,0]

The formula which is used to check whether a point p lies on a line L is the following:

   x * u + y * v + z * w = 0  (q)

where you may choose any of the q-1 coordinate triples (x,y,z) for p and any of the q-1 coordinate triples [u,v,w] for L.

Problems

We shall not further investigate the relation between the linear recurrence of degree 3 and the structure of the corresponding projective plane. However, the motivated reader should be able to adapt our story about semi-affine planes to make it work for projective planes. Here are some hints:

We have listed the coordinates of the points of the plane of order 3 in the same order as in the picture at the top of this page. Do you notice any relation between these coordinate triples and the elements of the (1,1,1)-sequence (modulo 3)?
What are the points on the line [1,0,0] (or [2,0,0] which is the same line)?

Other CDSs

97/01/03 - Kris Coolsaet