Affine Planes of Prime Power Order

/*
 * Affine planes of prime power order (Stinson, Theorem 6.2)
 * [This works for primes and for 2^2, 2^3, 2^4, 3^2 and 5^2,
 *   but not for other prime powers.]
 */

/* affine_plane(Q, Blocks) is true if Blocks constitute a c(Q^2,Q,2,2,Q^2+Q) */
/*   covering design, which is an affine plane of order Q.                   */
/* e.g. affine_plane(3, [[1,2,3],[1,4,7],[1,5,9],[1,6,8],[2,4,9],[2,5,8],    */
/*                       [2,6,7],[3,4,8],[3,5,7],[3,6,9],[4,5,6],[7,8,9]]).  */
affine_plane(Q, []):-
  \+ is_prime(Q), Q =\= 4, Q =\= 8, Q =\= 16, Q =\= 9, Q=\= 25, !,
  fail.
affine_plane(Q, Blocks):-
  Q_1 is Q - 1,
  findall(Block, block(Q, Q_1, Block), Blocks0),
  findall(Point, base_element(Q_1, Point), PointSet),
  normalize(Blocks0, PointSet, Blocks1),
  sort(Blocks1, Blocks).
  
block(Q, Q_1, Block):-
  for(0, Q_1, A),
  for(0, Q_1, B),
  findall(Point, point_1(A, B, Q, Q_1, Point), Block).
block(_, Q_1, Block):-
  for(0, Q_1, C),
  findall(Point, point_2(C, Q_1, Point), Block).
  
point_1(A, B, 4, Q_1, p(X,Y)):-!, % Y = A * X + B in GF(2^2)
  for(0, Q_1, X),
  P is A * 4 + X,
  nth_member([0,0,0,0,0,1,2,3,0,2,3,1,0,3,1,2], P, Q), % Multiplication table
  R is Q * 4 + B,
  nth_member([0,1,2,3,1,0,3,2,2,3,0,1,3,2,1,0], R, Y). % Addition table
point_1(A, B, 8, Q_1, p(X,Y)):-!, % Y = A * X + B in GF(2^3)
  for(0, Q_1, X),
  P is A * 8 + X,
  Mul=[0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,0,2,4,6,5,7,1,3,0,3,6,5,1,2,7,4,
       0,4,5,1,7,3,2,6,0,5,7,2,3,6,4,1,0,6,1,7,2,4,3,5,0,7,3,4,6,1,5,2],
  nth_member(Mul, P, Q),
  R is Q * 8 + B,
  Add=[0,1,2,3,4,5,6,7,1,0,3,2,5,4,7,6,2,3,0,1,6,7,4,5,3,2,1,0,7,6,5,4,
       4,5,6,7,0,1,2,3,5,4,7,6,1,0,3,2,6,7,4,5,2,3,0,1,7,6,5,4,3,2,1,0],
  nth_member(Add, R, Y).
point_1(A, B, 16, Q_1, p(X,Y)):-!, % Y = A * X + B in GF(2^4)
  for(0, Q_1, X),
  P is A * 16 + X,
  Mul=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
       0,2,4,6,8,10,12,14,3,1,7,5,11,9,15,13,0,3,6,5,12,15,10,9,11,8,13,14,7,
       4,1,2,0,4,8,12,3,7,11,15,6,2,14,10,5,1,13,9,0,5,10,15,7,2,13,8,14,11,4,
       1,9,12,3,6,0,6,12,10,11,13,7,1,5,3,9,15,14,8,2,4,0,7,14,9,15,8,1,6,13,
       10,3,4,2,5,12,11,0,8,3,11,6,14,5,13,12,4,15,7,10,2,9,1,0,9,1,8,2,11,3,
       10,4,13,5,12,6,15,7,14,0,10,7,13,14,4,9,3,15,5,8,2,1,11,6,12,0,11,5,14,
       10,1,15,4,7,12,2,9,13,6,8,3,0,12,11,7,5,9,14,2,10,6,1,13,15,3,4,8,0,13,
       9,4,1,12,8,5,2,15,11,6,3,14,10,7,0,14,15,1,13,3,2,12,9,7,6,8,4,10,11,5,
       0,15,13,2,9,6,4,11,1,14,12,3,8,7,5,10],
  nth_member(Mul, P, Q),
  R is Q * 16 + B,
  Add=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,0,3,2,5,4,7,6,9,8,11,10,13,12,
       15,14,2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13,3,2,1,0,7,6,5,4,11,10,9,8,
       15,14,13,12,4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11,5,4,7,6,1,0,3,2,13,12,
       15,14,9,8,11,10,6,7,4,5,2,3,0,1,14,15,12,13,10,11,8,9,7,6,5,4,3,2,1,0,
       15,14,13,12,11,10,9,8,8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,9,8,11,10,
       13,12,15,14,1,0,3,2,5,4,7,6,10,11,8,9,14,15,12,13,2,3,0,1,6,7,4,5,11,10,
       9,8,15,14,13,12,3,2,1,0,7,6,5,4,12,13,14,15,8,9,10,11,4,5,6,7,0,1,2,3,
       13,12,15,14,9,8,11,10,5,4,7,6,1,0,3,2,14,15,12,13,10,11,8,9,6,7,4,5,2,3,
       0,1,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0],
  nth_member(Add, R, Y).
point_1(A, B, 9, Q_1, p(X,Y)):-!, % Y = A * X + B in GF(3^2)
  for(0, Q_1, X),
  P is A * 9 + X,
  Mul=[0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,0,2,1,6,8,7,3,5,4,
       0,3,6,7,1,4,5,8,2,0,4,8,1,5,6,2,3,7,0,5,7,4,6,2,8,1,3,
       0,6,3,5,2,8,7,4,1,0,7,5,8,3,1,4,2,6,0,8,4,2,7,3,1,6,5],
  nth_member(Mul, P, Q),
  R is Q * 9 + B,
  Add=[0,1,2,3,4,5,6,7,8,1,2,0,4,5,3,7,8,6,2,0,1,5,3,4,8,6,7,
       3,4,5,6,7,8,0,1,2,4,5,3,7,8,6,1,2,0,5,3,4,8,6,7,2,0,1,
       6,7,8,0,1,2,3,4,5,7,8,6,1,2,0,4,5,3,8,6,7,2,0,1,5,3,4],
  nth_member(Add, R, Y).
point_1(A, B, 25, Q_1, p(X,Y)):-!, % Y = A * X + B in GF(5^2)
  for(0, Q_1, X),
  P is A * 25 + X,
  Mul=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,
       10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,0,2,4,1,3,10,12,14,11,13,
       20,22,24,21,23,5,7,9,6,8,15,17,19,16,18,0,3,1,4,2,15,18,16,19,17,5,8,6,
       9,7,20,23,21,24,22,10,13,11,14,12,0,4,3,2,1,20,24,23,22,21,15,19,18,17,
       16,10,14,13,12,11,5,9,8,7,6,0,5,10,15,20,3,8,13,18,23,1,6,11,16,21,4,9,
       14,19,24,2,7,12,17,22,0,6,12,18,24,8,14,15,21,2,11,17,23,4,5,19,20,1,7,
       13,22,3,9,10,16,0,7,14,16,23,13,15,22,4,6,21,3,5,12,19,9,11,18,20,2,17,
       24,1,8,10,0,8,11,19,22,18,21,4,7,10,6,14,17,20,3,24,2,5,13,16,12,15,23,
       1,9,0,9,13,17,21,23,2,6,10,19,16,20,4,8,12,14,18,22,1,5,7,11,15,24,3,0,
       10,20,5,15,1,11,21,6,16,2,12,22,7,17,3,13,23,8,18,4,14,24,9,19,0,11,22,
       8,19,6,17,3,14,20,12,23,9,15,1,18,4,10,21,7,24,5,16,2,13,0,12,24,6,18,
       11,23,5,17,4,22,9,16,3,10,8,15,2,14,21,19,1,13,20,7,0,13,21,9,17,16,4,
       12,20,8,7,15,3,11,24,23,6,19,2,10,14,22,5,18,1,0,14,23,7,16,21,5,19,3,
       12,17,1,10,24,8,13,22,6,15,4,9,18,2,11,20,0,15,5,20,10,4,19,9,24,14,3,
       18,8,23,13,2,17,7,22,12,1,16,6,21,11,0,16,7,23,14,9,20,11,2,18,13,4,15,
       6,22,17,8,24,10,1,21,12,3,19,5,0,17,9,21,13,14,1,18,5,22,23,10,2,19,6,
       7,24,11,3,15,16,8,20,12,4,0,18,6,24,12,19,7,20,13,1,8,21,14,2,15,22,10,
       3,16,9,11,4,17,5,23,0,19,8,22,11,24,13,2,16,5,18,7,21,10,4,12,1,15,9,23,
       6,20,14,3,17,0,20,15,10,5,2,22,17,12,7,4,24,19,14,9,1,21,16,11,6,3,23,
       18,13,8,0,21,17,13,9,7,3,24,15,11,14,5,1,22,18,16,12,8,4,20,23,19,10,6,
       2,0,22,19,11,8,12,9,1,23,15,24,16,13,5,2,6,3,20,17,14,18,10,7,4,21,0,23,
       16,14,7,17,10,8,1,24,9,2,20,18,11,21,19,12,5,3,13,6,4,22,15,0,24,18,12,
       6,22,16,10,9,3,19,13,7,1,20,11,5,4,23,17,8,2,21,15,14],
  nth_member(Mul, P, Q),
  R is Q * 25 + B,
  Add=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,1,2,3,
       4,0,6,7,8,9,5,11,12,13,14,10,16,17,18,19,15,21,22,23,24,20,2,3,4,0,1,7,
       8,9,5,6,12,13,14,10,11,17,18,19,15,16,22,23,24,20,21,3,4,0,1,2,8,9,5,6,
       7,13,14,10,11,12,18,19,15,16,17,23,24,20,21,22,4,0,1,2,3,9,5,6,7,8,14,
       10,11,12,13,19,15,16,17,18,24,20,21,22,23,5,6,7,8,9,10,11,12,13,14,15,
       16,17,18,19,20,21,22,23,24,0,1,2,3,4,6,7,8,9,5,11,12,13,14,10,16,17,18,
       19,15,21,22,23,24,20,1,2,3,4,0,7,8,9,5,6,12,13,14,10,11,17,18,19,15,16,
       22,23,24,20,21,2,3,4,0,1,8,9,5,6,7,13,14,10,11,12,18,19,15,16,17,23,24,
       20,21,22,3,4,0,1,2,9,5,6,7,8,14,10,11,12,13,19,15,16,17,18,24,20,21,22,
       23,4,0,1,2,3,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,0,1,2,3,4,5,6,
       7,8,9,11,12,13,14,10,16,17,18,19,15,21,22,23,24,20,1,2,3,4,0,6,7,8,9,5,
       12,13,14,10,11,17,18,19,15,16,22,23,24,20,21,2,3,4,0,1,7,8,9,5,6,13,14,
       10,11,12,18,19,15,16,17,23,24,20,21,22,3,4,0,1,2,8,9,5,6,7,14,10,11,12,
       13,19,15,16,17,18,24,20,21,22,23,4,0,1,2,3,9,5,6,7,8,15,16,17,18,19,20,
       21,22,23,24,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,17,18,19,15,21,22,23,
       24,20,1,2,3,4,0,6,7,8,9,5,11,12,13,14,10,17,18,19,15,16,22,23,24,20,21,
       2,3,4,0,1,7,8,9,5,6,12,13,14,10,11,18,19,15,16,17,23,24,20,21,22,3,4,0,
       1,2,8,9,5,6,7,13,14,10,11,12,19,15,16,17,18,24,20,21,22,23,4,0,1,2,3,9,
       5,6,7,8,14,10,11,12,13,20,21,22,23,24,0,1,2,3,4,5,6,7,8,9,10,11,12,13,
       14,15,16,17,18,19,21,22,23,24,20,1,2,3,4,0,6,7,8,9,5,11,12,13,14,10,16,
       17,18,19,15,22,23,24,20,21,2,3,4,0,1,7,8,9,5,6,12,13,14,10,11,17,18,19,
       15,16,23,24,20,21,22,3,4,0,1,2,8,9,5,6,7,13,14,10,11,12,18,19,15,16,17,
       24,20,21,22,23,4,0,1,2,3,9,5,6,7,8,14,10,11,12,13,19,15,16,17,18],
  nth_member(Add, R, Y).
point_1(A, B, Q, Q_1, p(X,Y)):- % Q is prime
  for(0, Q_1, X),
  Y is (A * X + B) mod Q.

point_2(C, Q_1, p(C,Y)):-
  for(0, Q_1, Y).
  
base_element(Q_1, p(X,Y)):-
  for(0, Q_1, X),
  for(0, Q_1, Y).

normalize([], _, []).
normalize([Xs|Xss], PointSet, [Ns|Nss]):-
  normalize_1(Xs, PointSet, Ns),
  normalize(Xss, PointSet, Nss).
  
normalize_1([], _, []).
normalize_1([X|Xs], PointSet, [N|Ns]):-
  nth_member(PointSet, N0, X), !,
  N is N0 + 1,
  normalize_1(Xs, PointSet, Ns).

/* for(I, J, K) is true if K is an integer between I and J inclusive.        */
for(I, J, I):-I =< J.
for(I, J, K):-I < J, I1 is I + 1, for(I1, J, K).

/* is_prime(P) is true if P is a prime number.                               */
is_prime(2):-!.
is_prime(P):-
  P > 2,
  P mod 2 =:= 1,
  SqrtP is sqrt(P),
  is_prime_1(3, P, SqrtP).

is_prime_1(I, _, SqrtP):-
  I > SqrtP, !.
is_prime_1(I, P, SqrtP):-
  P mod I > 0,
  I1 is I + 2,
  is_prime_1(I1, P, SqrtP).

/* nth_member(+Xs, ?N, ?X) is true if X is the N-th (base 0) element of      */
/*   the list Xs.                                                            */
nth_member(Xs, N, X):-nth_member_1(Xs, X, 0, N).

nth_member_1([X|_], X, I, I).
nth_member_1([_|Xs], X, I0, I):-
  I1 is I0 + 1,
  nth_member_1(Xs, X, I1, I).

LPA Index     Home Page

Valid HTML 4.01 Strict