Modular arithmetic and semi-affine planes

Take heart, we are nearly there! On this page we will construct semi-affine planes using modular arithmetic and on the next we will show how you can number their points to obtain CDSs.

Take any prime number q, say 3. (Just to remind you: a number is prime if it has no divisors except for 1 and itself.) This number will serve as the modulus for the modular arithmetic in these pages. Introduce q^2-1 points (i.e., 8 in our example) and q^2-1 lines. Call the points a,b,c,d,e,f,g,h and the lines A,B,C,D,E,F,G,H. (In fact, you don't really need to give these points and lines a name, but its makes thinking about them a lot easier.)

To each point we shall associate a pair of numbers of the form (x,y), where x and y are both in the range 0..q-1. This pair is called the set of coordinates of that point. Any pair is allowed as a set of coordinates, except (0,0). Different points have different coordinates. In our case there are exactly 8 possible pairs which we will randomly assign to the 8 different points:

       a: (0,1)  b: (0,2)  c: (1,0)  d: (2,0)
       e: (1,1)  f: (1,2)  g: (2,1)  h: (2,2)

We shall do a similar thing with the lines: to each line we associate a pair [u,v] where both u and v are in the range 0..q-1. This pair is again called the set of coordinates of that line and again all pairs except [0,0] are allowed. We assign the 8 possible pairs to the 8 different lines as follows:

       A: [0,1]  B: [0,2]  C: [1,0]  D: [2,0]
       E: [1,1]  F: [1,2]  G: [2,1]  H: [2,2]

Now, we say that a point with coordinates (x,y) belongs to a line with coordinates [u,v] if the following statement holds (using modular arithmetic):

       x * u + y * v = 1  (q)

(As is customary in texts typed on computer, we use a star instead of a cross to indicate multiplication - so as not to confuse the cross with the letter `x'. From now on we shall always adopt this convention.)

An example might make this more clear

To check whether point c (1,0) belongs to line F [1,2] we compute 1*1 + 0*2 using arithmetic modulo 3. The answer is 1, hence c belongs to F. Also g (2,2) belongs to D [2,0], for 2*2 + 1*0 is 4 which equals 1 modulo 3. On the other hand, h (2,2) does not belong to H (2,2) for 2*2 + 2*2 = 8 = 2 (3) and this is not equal to 1.

To get a feeling for the subject you might now carefully compute the formula x*u+y*v for each of the eight points and eight lines. You should obtain the following results:

            Line   | Points on that line
            ----------------------------

            A[0,1] | a(0,1) e(1,1) g(2,1) 
            B[0,2] | b(0,2) f(1,2) h(2,2)
            C[1,0] | c(1,0) e(1,1) f(1,2)
            D[2,0] | d(2,0) g(2,1) h(2,2)
            E[1,1] | a(0,1) c(1,0) h(2,2)
            F[1,2] | b(0,2) c(1,0) g(2,1)
            G[2,1] | a(0,1) d(2,0) f(1,2) 
            H[2,2] | b(0,2) d(2,0) e(1,1)

Check that the picture on the right really corresponds to the entries in the list. Looks familiar, doesn't it?

You can use the same procedure to construct semi-affine planes of larger order. There is one snag! The order q must be prime (i.e., q=2,3,5,7,11,...) otherwise this construction does not work. So, although there is indeed a semi-affine plane of order 4, this is not the way to construct it. (A semi-affine plane of order 6 doesn't even exist at all!)

Problems

Check that you understand the construction above by building a semi-affine plane of order 5. List the coordinates of the points on each of the 24 lines. You may want to try to draw a picture of the plane, but be warned that it will look messy. There are far too many lines which are not `straight'.
What goes wrong when you apply this procedure to the case q=4?
Match the picture of the semi-affine plane of order 3 on this page with the picture we had before. Use this to assign numbers in the range 0..7 to the points a..h. List the coordinates of the points 0,1,2,...,7 (in that order) on separate lines. Do you notice anything peculiar?

Fibonacci turns up everywhere

97/01/02 - Kris Coolsaet