Skip to content

Projective plane solutions

The problems were here.

P1. Show that for a finite affine plane there is an \(n\gt 1\) such that (1) every line contains \(n\) points, (2) every point lies on \(n+1\) lines, (3) there are \(n^2\) points in total, (4) there are \(n^2+n\) lines in total, (5) the lines fall into \(n+1\) disjoint classes of \(n\) lines each, such that the lines in each class are parallel, and the lines in different classes intersect. (This is known as an affine plane of order \(n\).)

Let the three non-collinear points given by axiom (C) be \(A_{11},A_{12},A_{21}\). Let \(L_1\) be the line through \(A_{11},A_{12}\). Suppose there are \(n-1\) lines parallel to \(L_1\), namely \(L_2,\dots,L_n\). Then every point not on \(L_1\) must line on one of these lines by axiom (B). In particular, suppose \(A_{21}\) lies on \(L_2\). So \(n\gt 1\).

Let \(K_1\) be the line through \(A_{11},A_{21}\). For each \(2\le i\le n, L_1\) is the line through \(A_{11}\) parallel to \(L_i\), so \(K_1\) is not parallel to \(L_i\) and hence meets it at a point \(A_{i1}\). That gives \(n\) points on \(K_1\). There cannot be any others or there would be another line parallel to \(L_1\) through it.

Through each point \(A_i\) with \(i\gt 1\) on \(L_1\) there must be a line \(K_i\) parallel to \(K_1\). This line \(K_i\) is not the line \(L_i\) through \(A_i\) parallel to \(L_j\), so it must meet \(L_j\) in a point \(A_{ij}\). The \(n^2\) points \(A_{ij},1\le i,j\le n\) must be all the points, for every point must lie on one of the \(L_i\), and, by a similar argument to that above, on one of the \(K_j\).

Now consider the lines through \(A_{ij}\). \(L_i\) is the line through \(A_{ij}\) parallel to \(L_k\) (for \(k\ne i\)), so any other line through \(A_{ij}\) must meet \(L_k\) and hence must pass through one of the \(n\) points \(A_{kl}\). Hence there are \(n+1\) lines through \(A_{ij}\). Each of these lines apart from \(L_i\) must intersect the \(n\) lines \(L_k\) just once and so contains exactly \(n\) points (remember that every point lies on some \(L_h\)). So we have established (1), (2), (3).

There are \(n^2\) points, each on \(n+1\) lines, and \(n\) points on each line, so the total number of lines must be \(n^2(n+1)/n=n^2+n\), which is (4). Clearly any of the \(L_i\) belongs to a class on \(n\) parallel lines. Any other line \(L\) must intersect \(L_1\) at one of the points \(A_{1i}\). Any line parallel to \(L\) must intersect \(L_1\) at some point \(A_{1j}\) with \(j\ne i\). Similarly, there is a line parallel to \(L\) through any \(A_{1j}\) with \(j\ne i\). So \(L\) belongs to a family of just \(n\) parallel lines, which completes (5). \(\Box\)

P2. (1) Show that if we remove a single line and its points from a projective plane of order \(n\gt 1\), then we get an affine plane of order \(n\).
(2) Given an affine plane of order \(n\), we add a single line \(L_{\infty}\) containing \(n+1\) points. All the lines in a given class of parallel lines pass through the same point on \(L_{\infty}\), and lines in different classes pass through different points on \(L_{\infty}\). Show that this construction gives a projective plane of order \(n\).

(1): Let the deleted line be \(L_{\infty}\). Call \(G\) the system after deleting \(L_{\infty}\) and its points. Any two points \(P,Q\) not on \(L_{\infty}\) are joined by a unique line in the projective plane, and hence by a unique line in \(G\). That establishes axiom (A).

Given a point \(P\) and a line \(L\) in \(G\) which does not contain it, let \(Q\) be the point in the projective plane at the intersection of \(L\) and \(L_{\infty}\). Let \(M\) be the line in the projective plane through \(P\) and \(Q\). Since \(Q\) is not in \(G\), the lines \(L\) and \(M\) have no point of intersection in \(G\), in other words, they are parallel in \(G\). That establishes axiom (B).

Finally, the projective plane has \(n^n+n+1-(n+1)=n^2\ge 4\) points apart from those on \(L_{\infty}\). Take any two of them \(A,B\). There are \(n\ge 2\) lines through \(A\) apart from the line \(AB\). Take one of them \(L\). It has at least 3 points on it, and hence at least one apart from \(A\) and the intersection of \(L\) and \(L_{\infty}\). That point, \(A\) and \(B\) are not collinear, which gives axiom (C).

(2): For each of the \(n+1\) classes \(C_i\) of parallel lines, take a new point \(P_i\) which lies on the \(n\) lines in the class and on none of the lines in the other classes. Also take a new line \(L_{\infty}\) through all \(n+1\) points \(P_i\). It is easy to check that that gives a projective plane of order \(n\).

Bookmark and Share
2012 04 29 John Scholes Maths Comments (0) Permalink

Latin square solutions (2)

The problems were here. The solutions to the “Easy exercises” were here.

P1. Show how to construct a pair of orthogonal Latin squares of order \(2n+1\).

Take \(M\) to be \((a_{ij})\) where \(a_{ij}=i+j\) reduced mod \(2n+1\). Similarly take \(M’\) to be \((b_{ij})\) where \(b_{ij}=j-i\) reduced mod \(2n+1\). Obviously \(M\) and \(M’\) are Latin squares, for if \(a_{ij}=a_{ik}\) then \(i+j=i+k\bmod 2n+1\) and hence \(j=k\). Similarly if \(a_{ik}=a_{jk}\), and similarly for \(M’\). Now suppose that \(a_{ij}=a_{rs},b_{ij}=b_{rs}\), then \(i+j=r+s\) and \(j-i=s-r\bmod 2n+1\), so adding \(2j=2s\bmod 2n+1\) and hence \(j=s\). Hence also \(i=r\). So \(M\) and \(M’\) are orthogonal. Note that we need the odd order in order to be able to divide out the factor 2. \(\Box\)

P2. Show how to construct a pair of orthogonal Latin squares of order \(4n\).

Let \(F\) be a finite field with \(2^m\) elements. Use symbols \(0,1,\dots,2^m-1\) for the elements of the field. Now put \(a_{ij}=i+j\), where addition is the field operation, not ordinary integer addition (recall that the additive group of \(F\) is \(C_2\times\dots\times C_2\)). Put \(b_{ij}=i+i+j\), again using the field addition. Then \(M=(a_{ij}),M’=(b_{ij})\) are obviously Latin squares. Suppose \(a_{ij}=a_{rs},b_{ij}=b_{rs}\). Then \(i+j=r+s,i+i+j=r+r+s\), subtracting gives \(i=r\), and hence \(j=s\). So they are orthogonal.

Lemma Given two \(m\times m\) MOLS \((a_{ij}),(b_{ij})\) where \(0\le i,j\lt m\) and \(0\le a_{ij},b_{ij}\lt m\), and two \(n\times n\) MOLS \((c_{rs}),(d_{rs})\) where \(0\le r,s\lt n\) and \(0\le c_{rs},d_{rs}\lt n\), we can construct two \(mn\times mn\) MOLS.

For any integer \(k\) in the range \(0\le k\lt mn\) we temporarily use the notation \(\{k\}\) to mean the residue of \(k\bmod n\) and \(k’\) to mean the largest integer not exceeding \(k/n\), so that \(k=k’n+\{k\}\) with \(0\le k’\lt m\) and \(0\le \{k\}\lt n\).

Define \(x_{kl}=na_{k’l'}+c_{\{k\}\{l\}}\) for \(0\le k,l\lt mn\). Suppose \(x_{kh}=x_{kl}\). Then \(c_{\{k\}\{h\}}=c_{\{k\}\{l\}}\bmod n\) and hence \(c_{\{k\}\{h\}}=c_{\{k\}\{l\}}\). But \((c_{rs})\) is a Latin square, so \(\{h\}=\{l\}\). Also \(x_{xh}-c_{\{k\}\{h\}}=x_{xl}-c_{\{k\}\{l\}}\), so \(a_{k’h'}=a_{k’l'}\). But \((a_{ij})\) is a Latin square, so \(h’=l’\). Hence \(h=l\). Similarly, if \(x_{hl}=x_{kl}\) then \(h=k\). So \((x_{kl})\) is a Latin square. Similarly, so is \((y_{kl})\) where \(y_{kl}=nb_{k’l'}+d_{\{k\}\{l\}}\).

We claim that \((x_{kl})\) and \((y_{kl})\) are orthogonal. For suppose \(x_{kl}=x_{uv}\) and \(y_{kl}=y_{uv}\). Then \(na_{k’l'}+c_{\{k\}\{l\}}=na_{u’v'}+c_{\{u\}\{v\}}\). Hence, as before, \(a_{k’l'}=a_{u’v'},c_{\{k\}\{l\}}=c_{\{u\}\{v\}}\). Similarly, \(b_{k’l'}=b_{u’v'},d_{\{k\}\{l\}}=d_{\{u\}\{v\}}\). But \((c_{rs}),(d_{rs})\) are orthogonal, so \(\{k\}=\{u\}, \{l\}=\{v\}\). Since \((a_{ij}),(b_{ij})\) are orthogonal, \(k’=u’,l’=v’\). Hence \(k=l,u=v\). \(\Box\)

So take \(4n=2^m(2k+1)\). We can construct a pair of MOLS of order \(2k+1\) by the solution to the previous problem and a pair order \(2^m\) by the method at the start of this solution. Then use the Lemma to derive a pair of order \(4n\). \(\Box\)

P3. Show that there are \(n-1\) mutually orthogonal Latin squares of order \(n\) for \(n\) a prime power.

Take \(F_n\) to be the finite field with \(n=p^k\) elements, where \(p\) is prime. Label the elements \(0,1,\dots,n\) (with 0 the additive identity). Take the \(i,j\) element of the \(n\times n\) array \(M_k\) to be \(ki+j\), for \(k\ne 0\) and the multiplication and addition being the field operations (not ordinary integer multiplication and addition). \(M_k\) is obviously a Latin square. Moreover, \(M_h,M_k\) are orthogonal. For if \(hi+j=hr+s\) and \(ki+j=kr+s\), then subtracting we get \((h-k)i=(hik)r\), but \(h\ne k\), so we may divide by \(h-j\) to get \(i=r\) and hence also \(j=s\). \(\Box\)

P4. Construct a set of 8 MOLS of order 9.

To construct the field with 9 elements we want a monic irreducible quadratic. \(x^2+1\) is the obvious choice. So the elements are \(0,1,2,x,x+1,x_2,2x,2x+1,2x+2\). We label these \(0,1,\dots,8\) in that order. Using the solution of the previous problem, we get \(M_1-M_8\), which we display as superimposed pairs to save space:

\(M_1,M_2=\left(\begin{array}{ccccccccc} 0_0&1_1&2_2&3_3&4_4&5_5&6_6&7_7&8_8\\1_2&2_0&0_1&4_5&5_3&3_4&7_8&8_6&6_7\\2_1&0_2&1_0&5_4&3_5&4_3&8_7&6_8&7_6\\3_6&4_7&5_8&6_0&7_1&8_2&0_3&1_4&2_5\\4_8&5_6&3_7&7_2&8_0&6_1&1_5&2_3&0_4\\5_7&3_8&4_6&8_1&6_2&7_0&2_4&0_5&1_3\\6_3&7_4&8_5&0_6&1_7&2_8&3_0&4_1&5_2\\7_5&8_3&6_4&1_8&2_6&0_7&4_2&5_0&3_1\\8_4&6_5&7_3&2_7&0_8&1_6&5_1&3_2&4_0\end{array}\right)\), \(M_3,M_4=\left(\begin{array}{ccccccccc} 0_0&1_1&2_2&3_3&4_4&5_5&6_6&7_7&8_8\\3_4&4_5&5_3&6_7&7_8&8_6&0_1&1_2&2_0\\6_8&7_6&8_7&0_2&1_0&2_1&3_5&4_3&5_4\\2_5&0_3&1_4&5_8&3_6&4_7&8_2&6_0&7_1\\5_6&3_7&4_8&8_0&6_1&7_2&2_3&0_4&1_5\\8_1&6_2&7_0&2_4&0_5&1_3&5_7&3_8&4_6\\1_7&2_8&0_6&4_1&5_2&3_0&7_4&8_5&6_3\\4_2&5_0&3_1&7_5&8_3&6_4&1_8&2_6&0_7\\7_3&8_4&6_5&1_6&2_7&0_8&4_0&5_1&3_2\end{array}\right)\), \(M_5,M_6=\left(\begin{array}{ccccccccc} 0_0&1_1&2_2&3_3&4_4&5_5&6_6&7_7&8_8\\5_6&3_7&4_8&8_0&6_1&7_2&2_3&0_4&1_5\\7_3&8_4&6_5&1_6&2_7&0_8&4_0&5_1&3_2\\8_1&6_2&7_0&2_4&0_5&1_3&5_7&3_8&4_6\\1_7&2_8&0_6&4_1&5_2&3_0&7_4&8_5&6_3\\3_4&4_5&5_3&6_7&7_8&8_6&0_1&1_2&2_0\\4_2&5_0&3_1&7_5&8_3&6_4&1_8&2_6&0_7\\6_8&7_6&8_7&0_2&1_0&2_1&3_5&4_3&5_4\\2_5&0_3&1_4&5_8&3_6&4_7&8_2&6_0&7_1\end{array}\right)\), \(M_7,M_8=\left(\begin{array}{ccccccccc} 0_0&1_1&2_2&3_3&4_4&5_5&6_6&7_7&8_8\\7_8&8_6&6_7&1_2&2_0&0_1&4_5&5_3&3_4\\5_4&3_5&4_3&8_7&6_8&7_6&2_1&0_2&1_0\\4_7&5_8&3_6&7_1&8_2&6_0&1_4&2_5&0_3\\2_3&0_4&1_5&5_6&3_7&4_8&8_0&6_1&7_2\\6_2&7_0&8_1&0_5&1_3&2_4&3_8&4_6&5_7\\8_5&6_3&7_4&2_8&0_6&1_7&5_2&3_0&4_1\\3_1&4_2&5_0&6_4&7_5&8_3&0_7&1_8&2_6\\1_6&2_7&0_8&4_0&5_1&3_2&7_3&8_4&6_5\end{array}\right)\).

P5. There is a projective plane of order \(n\) if and only if there is a complete set of MOLS of order \(n\).

Suppose we are given \(n\times n\) MOLS \(M_1,\dots,M_{n-1}\). We show how to construct an affine plane of order \(n\). Take the \(n^2\) points to be \((x,y)\) with \(0\le x,y\le n-1\). Define the line \(L_{ij}\) for \(1\le i\le n-1,0\le j\le n-1\) to contain the points \((x,y)\) for which \(M_i\) has \(j\) in row \(x\), col \(y\). \(j\) occurs just once in each row of \(M_i\), so \(L_{ij}\) has \(n\) points. Define the line \(X_i\) as \(\{(i,0),(i,1),\dots,(i,n-1)\}\) and the line \(\{(0,j),(1,j),\dots,(n-1,j)\}\). That gives us a total of \(n^2+n\) lines each with \(n\) points. Obviously the \(n\) lines \(X_i\) are all parallel, and the \(n\) lines \(Y_j\) are all parallel. The \(n\) lines \(L_{i1},L_{i2},\dots,L_{i,n-1}\) are all parallel because if \((x,y)\in L_{ij}\) and \(L_{ik}\), then \(M_i\) has \(j\) at \(x,y\) and \(i\) at \(x,y\), which is impossible unless \(i=j\).

Obviously \(X_i\) meets \(Y_j\) at \((i,j)\), and it must meet \(L_{jk}\) because \(M_j\) must have \(k\) somewhere in row \(i\). Similarly, \(Y_i\) must meet \(L_{jk}\) because \(M_j\) must have \(k\) somewhere in col \(i\). Finally, \(L_{hi}\) and \(L_{jk}\) meet for \(h\ne j\) because \(M_h\) and \(M_j\) are orthogonal, so for some position \((x,y)\) we have \(i\) in |(M_h\) and \(k\) in \(M_j\).

We have established axiom (B) for an affine plane (see here for the three axioms). Since \(n\gt 1\) there are certainly 3 non-collinear points, eg \((0,0),(0,1),(1,0)\), which establishes axiom (C). It remains to show axiom (A), that there is a unique line through any two distinct points. Note first that there is at most one, because we have just shown that distinct lines intersect in at most one point. Each line contains \(n(n-1)/2\) pairs of points, so altogether the lines contain \((n^2+n)(n^2-n)/2=n^2(n^2-1)/2\) pairs. But that is the total number of pairs, so each pair appears in at least one line.

So we have shown how to construct an affine plane of order \(n\). As explained here (problem 2), we can easily extend this to a projective plane of order \(n\) by adding a line of \(n+1\) points “at infinity”.

Conversely, suppose we have a projective plane of order \(n\). We can remove a line and the \(n+1\) points on it to get an affine plane of order \(n\). Label the \(n+1\) classes of parallel line by \(0,1,\dots,n\). Label the lines in each class by \(0,1,\dots,n-1\). Label the point at the intersection of line \(i\) in class 0 and line \(j\) in classs \(n\) as \((i,j)\). That labels all \(n^2\) points. Now for \(1\le k\le n-1\) place symbol \(h\) at row \(i\), col \(j\) of square \(M_k\) if line \(h\) of class \(k\) contains the point \((i,j)\).

If \(M_k\) contains the same symbol \(h\) at cols \(j\) and \(j’\) of row \(i\) for \(j\ne j’\), then line \(h\) of class \(k\) contains the two distinct points \((i,j),(i,j’)\). But these two points both lie on line \(i\) of class 0 (at the intersections with lines \(j,j’\) respectively of class \(n\). Contradiction (since two distinct lines cannot have two distinct points in common). Similarly, if \(M_k\) contains the same symbol at rows \(i,i’\) with \(i\ne i’\) and col \(j\). So each \(M_k\) is a Latin square.

Now suppose \(M_k\) contains the same symbol \(h\) at both row \(i\), col \(j\) and row \(i’\), col \(j’\), and that \(M_{k’}\) (with \(k\ne k’\)) contains the symbol \(h’\) (not necessarily \(\ne h\)) at the same two locations. Then line \(h\) of class \(k\) contains the two distinct points \((i,j),(i’,j’)\) and so does line \(h’\) of class \(k’\). Contradiction. So \(M_k\) and \(M_{k’}\) are orthogonal. \(\Box\)

P6. There is a projective plane of order \(n\) if \(n\) is a prime power.

This follows from P3 and P5. We also showed it directly here using homogeneous coordinates.

Bookmark and Share
2012 04 28 John Scholes Maths Comments (0) Permalink

Projective planes

A projective plane is a set of points and a set of lines together with an incidence relation (each point does or does not lie on each of the lines), satisfying three axioms:

(A) there is a unique line through any two distinct points;
(B) any two distinct lines intersect in a unique point;
(C) there are four points, no three collinear (a “quadrilateral”).

As discussed in an earlier post (under E3), (C) is simply to exclude two families of “degenerate projective planes”, which are systems satisfying (A) and (B), but not (C). We showed that a finite projective plane must have \(n^2+n+1\) points and the same number of lines, with \(n+1\) points on each line and \(n+1\) lines through each point. This is called a projective plane of order \(n\).

However, projective planes do not exist for all \(n\). The conjecture is that they only exist for \(n\) a prime power, but a century of work has still not succeeded in proving or disproving it.

We also showed that any finite field \(F\) can be used to construct a projective plane. If the field has \(n\) elements, then the plane has order \(n\). Such a plane is often referred to as the projective plane over \(F\) and sometimes written as \(PG(2,F\). The 2 refers to the fact that it is a plane. Finite (and infinite) projective geometries of higher dimension also exist, but we will not be discussing them in the near future.

The plane over a finite field \(F_n\) has a natural system of “homogeneous coordinates” \((a,b,c)\), with \(a,b,c\in F_n\) and not all (\a,b,c\) zero. These coordinates fall into \(n^2+n+1\) equivalence classes, taking \((a,b,c)\) and \((ka,kb,kc)\) to describe the same point (for any \(0\ne k\in F_n\). It is often convenient to take the first non-zero coordinate to be 1, so that there are \(n^2\) points \((1,b,c)\), \(n\) points \((0,1,c)\) and 1 point \((0,0,1)\).

One can use these coordinates to prove Desargues’ theorem: two triangles are centrally perspective if and only if they are axially perspective (see here for more detail). Curiously, no “geometric” proof is known. But it turns out that there are finite projective planes for which Desargues’ theorem is false. We gave an example with 91 points (order 9).

Indeed, we will prove in a later post that a Desarguesian plane of order \(n\) must be the (unique) plane over the (unique) finite field of \(n\) elements. So Desarguesian planes only exist for prime power orders.

On the other hand, it is fairly straightforward to show that there is a complete set of \(n\times n\) mutually orthogonal \(n\times n\) Latin squares (MOLS) if and only there is a projective plane of order \(n\). There is also an easy way of constructing such a set of MOLS directly from a finite field with \(n\) elements.

Many finite projective planes have been constructed which are not Desarguesian, and hence are not isomorphic to the planes over the finite fields, but all non-Desarguesian planes found so far have had prime power order. On the other hand, relatively little progress has been made in proving that non-Desarguesian planes must have prime power order.

It is surprisingly difficult even to show that there is no projective plane of order 6. But there is a proof of reasonable length that there is no pair of orthogonal Latin squares of order 6, which I will give in a later post (Stinson, J Comb Th A 36 (1984) p373). So a fortiori there can be no complete set of MOLS of order 6 and hence no projective plane of order 6.

For a while it was thought that this approach might work for other \(n\), but in 1979 Zhu Lie published (in Chinese) an elegant proof that for \(n\gt 6\) there is always a pair of MOLS of order \(n\).

So the conjecture that all finite projective planes have prime power order is still widely believed to be true.

The infinite analogue of the result that a finite Desarguesian plane must be the plane over a field is that a Desarguesian plane must be over a division ring (or “skew field”, ie a structure which satisfies all the field axioms except that the multiplication is not necessarily commutative). The finite result seems to flow from the algebraic result (which we will also prove in a later post) that any finite division ring is a field.

On the other hand it is always true (for both finite and infinite projective planes) that if Pappus’ Theorem holds, then the plane must be over a field.

We will discuss Pappus’ Theorem and its relation to Desargues’ Theorem further in a later post. For now, we just briefly state it:

if \(A,B,C\) are collinear, and \(A’,B’,C’\) are collinear, then the intersection of \(BC’\) and \(B’C\), the intersection of \(AC’\) and \(A’C\), and the intersection of \(AB’\) and \(A’B\) are collinear.

Here are the two simplest projective plane. The plane of order 2, with 7 points is known as Fano’s plane:

pt coords lines
1 (0,0,1) \(L_2,L_4,L_6\)
2 (0,1,0) \(L_1,L_4,L_5\)
3 (0,1,1) \(L_3,L_4,L_7\)
4 (1,0,0) \(L_1,L_2,L_3\)
5 (1,0,1) \(L_2,L_5,L_7\)
6 (1,1,0) \(L_1,L_6,L_7\)
7 (1,1,1) \(L_3,L_5,L_6\)

We can choose the point labels so that they contain the homogeneous coordinates! The table can also be read with points and lines interchanged.

This is also possible for the plane of order 3, with 13 points:

The diagram is already getting messy and does not add much to the table showing the lines which contain each point:

This table can also be read with points and lines interchanged. L1 contains the points 3, 6, 9, 12 etc and has the coordinates (0,0,1).

Problems

An affine plane is a set of points and a set of lines with an incidence relation, satisfying these three axioms:

(A) there is a unique line through any two distinct points;
(B) given a point \(P\) and a line \(L\) not containing it, there is a unique line through \(P\) parallel to \(L\);
(C) there are three non-collinear points.

Two lines are said to be parallel if they do not meet.

1. Show that for a finite affine plane there is an \(n\gt 1\) such that (1) every line contains \(n\) points, (2) every point lines on \(n+1\) lines, (3) there are \(n^2\) points in total, (4) there are \(n^2+n\) lines in total, (5) there are \(n-1\) lines parallel to any given line, so that the lines fall into \(n+1\) classes, each of \(n\) parallel lines. Such an affine plane is said to have order \(n\).

2. (1) Show that if we remove a single line and its points from a projective plane of order \(n\), then we get an affine plane of order \(n\).
(2) Given an affine plane of order \(n\), we add a single line \(L\) (often called the “line at infinity”) containing \(n+1\) points. There is a one-one correspondence between the \(n+1\) classes of lines and the points on the line at infinity, so that all the lines in a given class pass through the same point on the line at infinity and lines in different classes pass through different points. Show that this construction gives a projective plane of order \(n\).

Bookmark and Share
2012 04 27 John Scholes Maths Comments (0) Permalink

Desargues theorem

The theorem is: Two disjoint triangles (ie having no vertices in common) are in perspective axially if and only if they are in perspective centrally.

This is illustrated in the figure above. The two triangles are ABC and abc. “Centrally perspective” means that the lines Aa, Bb, Cc meet at a single point, the “perspective centre”. “Axially perspective” means that the corresponding sides meet in three points which are collinear. The line on which the three points of intersection lie is the “perspective axis”.

This does not quite work in ordinary Euclidean geometry because of the difficulty that two distinct lines do not necessarily meet. They may be parallel. It almost works in “projective geometry”, which has the axiom that two lines always meet in a unique point. It does work for the real projective plane. This can be defined in various equivalent ways, one of which is by specifying homogeneous coordinates.

The usual proof for the real projective plane uses these homogenous coordinates. These are coordinates \((a,b,c)\) with real \(a,b,c\) not all zero. The coordinates \(a,b,c\) and \(ka,kb,kc\) for any non-zero \(k\) are regarded as the same. A line also has a coordinate triple \(p,q,r\), again with not all coordinates zero and with multiplication by a constant giving the same line. The point \(a,b,c\) lies on the line \(p,q,r\) if and only if \(pa+qb+rc=0\).

It is easy to check that these coordinates satisfy the projective axioms (any two distinct points lie on just one line, and any two distinct lines meet in just one point).

We can arbitrarily assign the coordinates \((1,0,0)\) to \(A\), \((0,1,0)\) to \(B\), \((0,0,1)\) to \(C\), since they are non-collinear, and there is no loss of generality in taking the perspective centre \(P\) as \((1,1,1)\). Now we can take the other triangle to be \(A’B'C’\) with coordinates respectively \((1,a,a),(b,1,b),(c,c,1)\) for some \(a,b,c\) all non-zero. It is easy to check that \(P,A,A’\) lie on the line \((0,1,-1)\), whilst \(P,B,B’\) lie on the line \((1,0,-1)\), and \(P,C,C’\) lie on the line \((1,-1,0)\).

Now \(AB\) is the line \((0,0,1\), and \(A’B'\) is the line \((a(b-1),(a-1)b,1-ab)\), so they meet at the point \((a-1)b,a(b-1),0)\). Similarly, \(BC\) is the line \((1,0,0)\), and \(B’C'\) is the line \((1-bc,b(c-1),c(b-1))\), so they meet at the point \((0,(b-1)c,-b(c-1))\). Similarly, \(CA\) is the line \((0,1,0)\), and \(C’A'\) is the line \((a(c-1),1-ac,c(a-1))\), so they meet at the point \(((a-1)c,0,-a(c-1))\). So the perspective axis is \((a(b-1)(c-1),(a-1)b(c-1),(a-1)(b-1)c)\).

That establishes the “if”. The proof of the “only if” is similar. Or one can just observe that it is the dual of the “if” result and so follows automatically.

However, the interesting part is that the result is false for some finite projective planes. The simplest example is the “non-Desarguesian” plane of order 9, which has 91 lines and 91 points. Any sketch is going to look a mess, one has to give the geometry as a list of lines. The points are simply numbered from 0 to 90, and the lines from L0 to L90. The list of the points on each line is given below.

Now take the perspective centre to be the point 0, and the two triangles to be 1,11,19 and 2,17,41. To check that 0 is a perspective centre, note that: 0,1,2 is L0; 0,11,17 is L1; 0,19,41 is L2. Now the side 1,11 is L11 and 2,17 is L27 and L21,L27 meet at 46. Similarly, 1,19 is L10, and 2,41 is L24 and L10,L24 meet at 20. Finally, 11,19 is L20 and 17,41 is L89 and L20,L89 meet at 30. But 20,30,46 are not collinear. It is easy to check that 20,30 is L41, but 20,46 is L88, and 30,46 is L73.

But any finite projective plane derived in the obvious way from a finite field does satisfy Desargues theorem. For given a finite field \(F\) with \(n\) elements take \(X\) to be the set of all homogeneous coordinates \((a,b,c)\) with \(a,b,c\in F\). Evidently \(X\) has \(n^2+n+1\) elements, which we may take to be: the \(n^2\) elements \((1,b,c)\); the \(n\) elements \((0,1,c)\); and the single element \((0,0,1)\). We may take \(X\) to be the points. Similarly, take \(Y\), a duplicate of \(X\), to be the lines. We say that the point \((a,b,c)\) and the line \((l,m,n)\) are incident if and only if \(la+mb+nc=0\). If we replace \((a,b,c)\) by \((ka,kb,kc)\) for \(k\ne 0\), the condition \(la+mb+nc=0\) is unaffected, and similarly for \((l,m,n)\), so incidence is well-defined.

It is easy to check that the line \((b_1c_2-b_2c_1,a_2c_1-a_1c_2,a_1b_2-a_2b_1)\) is the unique line containing the points \((a_1,b_1,c_1)\) and \((a_2,b_2,c_2)\). Similarly, \((b_1c_2-b_2c_1,a_2c_1-a_1c_2,a_1b_2-a_2b_1)\) is the unique point lying on the lines \((a_1,b_1,c_1)\) and \((a_2,b_2,c_2)\). There are obviously four points, no three on a line, for example the points \(A,B,C,P\) above (which exist for any finite field). So the structure satisfies the three axioms for a projective plane.

Recall that the conjecture is that there is a finite projective plane of order \(n\) (meaning with \(n+1\) points on each line, \(n+1\) lines through each point, and \(n^2+n+1\) points and \(n^2+n+1\) lines in total) if and only if \(n\) is a prime power. Since there is a finite field with \(n\) elements if and only if \(n\) is a prime power, and one can use a finite field with \(n\) elements to construct a projective plane of order \(n\), that raises the hope that one might be able to use a projective plane of order \(n\) to construct a field with \(n\) elements.

Indeed we will prove in a later post that one can prove that any Desarguesian finite projective plane (more usually shortened to simply Desarguesian plane) of order \(n\) can be used to construct a finite field of order \(n\), so in particular must have \(n\) a prime power.

This suggests that there might be non-Desarguesian planes of order \(n\) not a prime power, but none have yet been found, although several families of non-Desarguesian finite projective planes have been found, all with prime power order. In other other direction, it has been proved that there is no projective plane of order 6 or 10 and nor of order \(n=4k+1\) or \(4k+2\) unless \(n\) can be written as the sum of two squares (the Bruck-Ryser theorem). The case 6 can be dealt with quite shortly (and we will cover it in a later post), but the case 10 has only been dealt with by computer search. The next unsolved case is 12. Estimates suggest that it is currently beyond the scope of computer search.

In the other direction a number of weaker structures than fields (such as near-fields and semi-fields, which we will look at in a later post) have been used to construct non-Desarguesian planes. But so far no one has found a geometrical method of showing that these structures are required for a plane.

The projective plane of order 9 exhibited below is a “Hughes plane”, after Daniel Hughes who showed in 1955 (pdf) that such planes exist for all \(n=p^k\), where \(p\) is an odd prime and \(k\) is even. The points are \(0,1,\dots,90\) and the lines are \(L0,L1,\dots,L90\). The listing below gives the points on each line.

L0 0 1 2 3 4 5 6 7 8 9
L1 0 10 11 12 13 14 15 16 17 18
L2 0 19 34 35 36 37 38 39 40 41
L3 0 20 27 42 55 56 57 58 59 60
L4 0 21 33 48 54 61 76 78 89 90
L5 0 22 30 43 49 63 68 72 79 80
L6 0 23 28 44 50 69 70 77 81 82
L7 0 24 29 45 51 64 73 74 83 84
L8 0 25 31 46 52 62 67 75 85 86
L9 0 26 32 47 53 65 66 71 87 88
L10 1 10 19 20 21 22 23 24 25 26
L11 1 11 34 42 43 44 45 46 47 48
L12 1 12 28 35 55 61 62 63 64 65
L13 1 13 31 41 54 56 74 80 82 88
L14 1 14 33 36 50 58 68 73 85 87
L15 1 15 29 37 52 59 71 76 79 81
L16 1 16 27 38 51 66 72 77 86 89
L17 1 17 32 39 49 57 69 75 78 83
L18 1 18 30 40 53 60 67 70 84 90
L19 2 10 35 42 49 50 51 52 53 54
L20 2 11 19 27 28 29 30 31 32 33
L21 2 13 21 34 57 62 70 71 72 73
L22 2 14 22 37 48 60 64 69 86 88
L23 2 12 24 39 47 58 67 80 81 89
L24 2 18 20 41 45 61 75 77 79 87
L25 2 16 26 40 44 56 63 76 83 85
L26 2 15 25 36 43 55 66 78 82 84
L27 2 17 23 38 46 59 65 68 74 90
L28 3 10 29 34 56 61 66 67 68 69
L29 3 11 26 36 52 57 64 77 80 90
L30 3 12 25 33 38 42 70 79 83 88
L31 3 13 24 30 35 44 59 78 86 87
L32 3 14 23 27 41 47 49 62 76 84
L33 3 15 20 28 39 48 53 72 74 85
L34 3 16 19 43 54 60 65 73 75 81
L35 3 17 22 31 40 45 50 55 71 89
L36 3 18 21 32 37 46 51 58 63 82
L37 4 10 31 38 48 57 63 81 84 87
L38 4 11 22 35 58 66 70 74 75 76
L39 4 12 26 29 41 46 50 60 72 78
L40 4 13 19 47 51 55 69 79 85 90
L41 4 14 20 30 34 52 65 82 83 89
L42 4 15 23 32 40 42 61 73 80 86
L43 4 16 21 28 36 45 49 59 67 88
L44 4 17 24 33 37 43 53 56 62 77
L45 4 18 25 27 39 44 54 64 68 71
L46 5 10 33 40 47 59 64 72 75 82
L47 5 11 21 39 50 56 65 79 84 86
L48 5 12 20 31 37 44 49 66 73 90
L49 5 13 22 27 36 46 53 61 81 83
L50 5 14 19 42 63 67 71 74 77 78
L51 5 15 26 30 38 45 54 58 62 69
L52 5 16 24 32 41 48 52 55 68 70
L53 5 17 25 28 34 51 60 76 80 87
L54 5 18 23 29 35 43 57 85 88 89
L55 6 10 28 41 43 58 71 83 86 90
L56 6 11 20 40 51 62 68 78 81 88
L57 6 12 22 32 34 54 59 77 84 85
L58 6 13 23 33 39 45 52 60 63 66
L59 6 14 21 29 38 44 53 55 75 80
L60 6 15 19 46 49 56 64 70 87 89
L61 6 16 25 30 37 47 50 57 61 74
L62 6 17 26 27 35 48 67 73 79 82
L63 6 18 24 31 36 42 65 69 72 76
L64 7 10 27 37 45 65 70 78 80 85
L65 7 11 25 41 53 59 63 69 73 89
L66 7 12 23 30 36 48 51 56 71 75
L67 7 13 20 32 38 43 50 64 67 76
L68 7 14 24 28 40 46 54 57 66 79
L69 7 15 21 31 35 47 60 68 77 83
L70 7 16 22 29 39 42 62 82 87 90
L71 7 17 19 44 52 58 61 72 84 88
L72 7 18 26 33 34 49 55 74 81 86
L73 8 10 30 39 46 55 73 76 77 88
L74 8 11 24 38 49 60 61 71 82 85
L75 8 12 21 27 40 43 52 69 74 87
L76 8 13 26 28 37 42 68 75 84 89
L77 8 14 25 32 35 45 56 72 81 90
L78 8 15 22 33 41 44 51 57 65 67
L79 8 16 23 31 34 53 58 64 78 79
L80 8 17 20 29 36 47 54 63 70 86
L81 8 18 19 48 50 59 62 66 80 83
L82 9 10 32 36 44 60 62 74 79 89
L83 9 11 23 37 54 55 67 72 83 87
L84 9 12 19 45 53 57 68 76 82 86
L85 9 13 25 29 40 48 49 58 65 77
L86 9 14 26 31 39 43 51 59 61 70
L87 9 15 24 27 34 50 63 75 88 90
L88 9 16 20 33 35 46 69 71 80 84
L89 9 17 21 30 41 42 64 66 81 85
L90 9 18 22 28 38 47 52 56 73 78

Bookmark and Share
2012 04 23 John Scholes Maths Comments (0) Permalink

Latin square solutions (1)

The four “Easy exercises” and six (harder) “Problems” were here. This post gives the solutions to the exercises.

Lemma 1 Given any two MOLS of order \(n\) we can derive two MOLS with one in reduced form and the other having the first row \(1,\dots,n\)

Consider the superimposed array (like the example of order 4 in the earlier post). By permuting its columns and then its rows, we can get one of the Latin squares into reduced form. Then by permuting the symbols used for the other Latin Square we can get its top row to \(1,\dots,n\). This permutation preserves both its Latin property and its orthogonality to the other Latin square. \(\Box\)

E1 Show that it is impossible to construct two MOLS of order 2.

It is obvious that the only Latin square with top row \(1,2\) is \(\left(\begin{array}{cc} 1&2\\2&1\end{array}\right)\), but this square is not orthogonal to itself because the pair \(2,2\) appears twice and the pair \(2,1\) does not appear. \(\Box\)

E2 Show that there are at most \(n-1\) MOLS of order \(n\).

Suppose there were \(n\). For each square we can permute its symbols to get the top row as \(1,\dots,n\). This will preserve the Latin property and will not affect the squares orthogonality to the other squares. Now consider the first cell in the second row. If any two squares have the same symbol \(k\) in this cell, then they are not orthogonal, because they also have the same symbol \(k\) in the cell in column \(k\) of the top row. So all squares must have a different symbol in the first cell in the second row. That means one of them must have the symbol 1, but it also has the symbol 1 in the first cell of the top row, so it is not Latin. Contradiction. \(\Box\)

E3 Find all degenerate finite projective planes, in other words, finite sets of points and lines which satisfy (A) any two distinct lines intersect in just one point, (B) any two distinct points lie on just one line, but which do not satisfy (C) there are four points, no three of which lie on the same line.

Note that any configuration of points and lines satisfying (A) and (B) has a dual configuration obtained by interchanging points and lines, but preserving “incidence” (the property of a point being on a line). So if the original configuration has a point A and a line L, then in the dual configuration the line A contains the point L if and only if point A lies on line L in the original. A configuration is self-dual if it is the same as its dual.

All degenerate configurations fall into two infinite families :

(1) a point \(P\) not lying on a line \(L\) and \(n\ge 0\) lines through \(P\), each meeting \(L\) in one point (so a total of \(n+1\) points and \(n+1\) lines. For each \(n\) this configuration is self-dual;

(2) a point \(P\) lying on a line \(L\), \(n\ge 0\) additional lines passing through \(P\) and \(m\ge 0\) additional points lying on \(L\). Both \(P\) and \(L\) are optional, so the configuration includes as special cases: the empty configuration (no lines or points); a single point \(P\) with zero or more lines passing through it; and a single line \(L\) with zero or more points on it. Every configuration in (2) is self-dual or dual to another configuration in (2).

It is obvious that configurations in (1) or (2) are degenerate since they do not satisfy (C). If we require that at most two points lie on any line, then a configuration in (1) includes at most 3 points and a configuration in (2) at most two.

It is clear that the empty configuration, a single point, a single line, and a single point lying on a single line are all covered in (2). A single point and a single line which does not contain it is covered by (1).

If a configuration includes two points, then it must also include a line \(L\) containing them. Suppose all the points in the configuration lie on \(L\). If all the lines pass through one of these points, then we have (2). (Note that if there are just two lines, then this case is also in (1). If we want to make (1) and (2) disjoint families, then in (1) we must require \(n\ne 1\)). If not, then \(L\) contains two points \(P\) and \(Q\) each with another line through them. But these lines must meet at a point \(R\) not on \(L\). Contradiction. So that exhausts possible configurations with all the points on \(L\).

So suppose we have a line \(L\) containing (at least) two points and a point \(P\) not on \(L\). Then for each point \(A\) on \(L\) there is a line containing \(P\) and \(A\), so we have (1). If we add another point not on \(L\) and not on any of the lines \(PA\), then the configuration is not degenerate. So the only case we need to consider is adding a point to one of the lines \(PA\).

If \(L\) contains only two points \(A,B\), then adding one or more additional points to \(PA\) gives another configuration in (1) (relabel \(B\) as \(P\) and the line \(PA\) as \(L\)). But if we add a point \(Q\) to \(PA\) and a point \(R\) to \(PB\) then the points \(A,B,Q,R\) satisfy (C), so the configuration is not degenerate. Similarly, if \(L\) has at least three points \(A,B,C\) and we add a point \(Q\) to \(PA\), then the lines \(QC\) and \(PB\) must intersect in a point \(R\) and the points \(A,B,Q,R\) satisfy (C). \(\Box\)

E4 Suppose that a particular line in a finite projective plane contains just \(n+1\) points with \(n\ge 2\). show that: (1) every line contains just \(n+1\) points, (2) every point is on just \(n+1\) lines, (3) there are a total of \(n^2+n+1\) points and \(n^2+n+1\) lines.

Call the particular line \(L\). Take \(P\) to be any point not on \(L\) – such a point must exist to avoid degeneracy. Any line through \(P\) must intersect \(L\) and any two distinct lines through \(P\) must meet \(L\) in two different points. Conversely, given any point on \(L\) there is a line through it and \(P\). So the number of lines through \(P\) is the same as the number of points on \(L\). Hence there are \(n+1\) lines through \(P\). Moreover, any other point \(X\) (not \(P\) or a point on \(L\)) must lie on one of the lines through \(P\), because otherwise the line \(PX\) would meet \(L\) in an additional point.

At least one of the lines through \(P\) must have a third point to avoid degeneracy. So suppose the points on \(L\) are \(A_1,\dots,A_{n+1}\) and that the additional point \(K_1\) lies on \(PA_1\). Now every line through \(K_1\) must cut \(L\) in a distinct point, so there must be exactly \(n+1\) lines through \(K_1\). There is nothing special about \(K_1\), so every on a line through \(P\) (except possibly \(P\) itself or one of the points \(A_i\)) must have exactly \(n+1\) lines through it.

Each of the \(n+1\) lines through \(K_1\) must cut the line \(PA_i\) (for \(i\ne 1\)) in a distinct point, so each of the lines \(PA_i\), except possibly, \(PA_1\) has exactly \(n+1\) points. Now \(n\ge 2\), so \(A_2,A_3\) exist and \(K_1A_2\) must meet \(PA_3\) in a point \(K_3\). By the same argument as above there are exactly \(n+1\) lines through \(K_3\) and hence exactly \(n+1\) points on \(PA_1\).

But \(P\) was any point not on \(L\). We are given that \(L\) has \(n+1\) points. Any other line must meet at least one of \(PA_1,PA_2\) in a point not on \(L\) and the argument above shows that any line through that point has exactly \(n+1\) points. That establishes (1).

We have already shown that any point \(P\) not on \(L\) has exactly \(n+1\) lines, so to establish (2) we need only show that each \(A_i\) is on exactly \(n+1\) lines. But there is a one-one correspondence between lines through \(A_i\) and points on \(PA_j\) for \(j\ne i\), so there are exactly \(n+1\) lines through \(A_i\). That establishes (2).

We have already shown that all the points line on one of the \(n+1\) lines through \(P\). Each such line has \(n\) points apart from \(P\), so the total number of points is \(n(n+1)+1=n^2+n+1\). Similarly every line apart from \(L\) itself meets \(L\) in one of the points \(A_i\). \(n\) lines (apart from \(L\) itself) pass through each \(A_i\), so there are a total of \((n+1)n+1=n^2+n+1\) lines. \(\Box\)

Bookmark and Share
2012 04 22 John Scholes Maths Comments (0) Permalink