请输入您要查询的字词:

 

单词 FiniteProjectivePlane
释义

finite projective plane


Finite projective planes from axioms

Let us start from the beginning and assume we are given a set of n things called points and a set of ν things called lines, with anincidence relationPlanetmathPlanetmath between them (a point is incidentMathworldPlanetmath with a line iff the line is incident with the point) that satisfies only two axioms, the two unique incidence properties:

  • For any two distinct points,there is exactly one line through both of them.

  • For any two distinct lines,there is exactly one point on both of them.

Given these http://planetmath.org/node/6940projective planeMathworldPlanetmath axioms we can apply the De Bruijn–Erdős theorem twice (once with the rôle of points and lines swapped) which tells us we must have n=ν, and one of two possible configurationsMathworldPlanetmathPlanetmath:

  • One “degenerate” solution has one special line0 and n-1 ordinary lines i, and a special pointP0 and n-1 ordinary points Pi. Each Pi (i0) isincident with its own i and with 0; each i(i0) with its own Pi and with P0. Now 0 isincident with every point except 0 while P0 isincident with every line except 0.

  • The other solution is a projective plane:

    • the number of points and the number oflines are of the form q2+q+1 for some integer q;

    • each point is incident with q+1lines and each line with q+1 points.

One usually avoids the degenerate case by demanding there is a quadranglein the plane: four points no three of which lie on the same line. This, or asimilarMathworldPlanetmathPlanetmathPlanetmath non-triviality clause, can then be adopted as a third axiom.Unfortunately it also has the effect of excluding projective planes of orders q=0 and 1. TheDe Bruijn–Erdös (http://planetmath.org/DeBruijnErdHosTheorem)theorem actually makes an additional assumptionPlanetmathPlanetmath: thatno two lines are incident with the same set of points (and when applied duallythat no two points are incident with the same set of lines). That is not aproblem for a line incident with more than one point or vice versa, becausethen the axioms forbid it. We just get some more degenerate cases consistingof multipleMathworldPlanetmathPlanetmath lines intersecting one point or none, or vice versa; the insistenceon a quadrangle catches these too.

I will not prove the whole theorem here, but under the assumptionthat a quadrangle exists it is not hard show the interesting part,that those numbers q+1 and q2+q+1 drop out by necessity.The same construction can also be used to give coordinatesMathworldPlanetmathPlanetmath to thepoints and lines of the plane (see below).

Projective planes as bipartite graphs

Projective planes are, apart from anything else, also bipartite graphsMathworldPlanetmath: let theq2+q+1 points be represented by “black” nodes (vertices) of the graph,and let the q2+q+1 lines also be nodes, “white” ones say.Edges will represent incidence between a “black” and a “white” node,so there are (q2+q+1)(q+1)=q3+2q2+2q+1 edges in all.

  • In a bipartite graph, nodes of the same color have even distanceMathworldPlanetmath.This is 0 for any node and itself and must be 2 for any twodistinct nodes of the same color: for any two points there is a pathvia the line they share, and for any two lines a path via the pointthey share. So distance 4 does not occur.

    For nodes of opposite color we can have 1 (if the point lies on theline) or 3 (otherwise); we can’t have distance 5 which would imply4 for some nodes. So the graph has diameterMathworldPlanetmathPlanetmath (maximum distance) 3.

  • In a bipartite graph, all cycles (if any) have even length. Wedon’t have 2-cycles (this is not a multigraphMathworldPlanetmath) but no 4-cycleseither, by the following argument: such a cycle PQmwould mean two lines intersecting in two different points, andvice versa. So the girth (minimum cycle length) is 6(showing there indeed are 6-cycles for q2 is left asexercise for the reader).

These two conditions, diameter 3 and girth 6, are not only necessary forthe graph to represent a projective plane, they are also sufficient, and therefore forman alternative formulation of what it means to be a projective plane.

These graphs could be called the bipartite analogue of Moore graphsMathworldPlanetmath ofdiameter 2 and girth 5; many of the same arguments can be used [vG03].

Coördinates for finite projective planes

The details on how to impose coordinates on a projective plane can be found in [Hal59, dRe96], or in this entry (http://planetmath.org/IntroducingCoordinatesInAProjectivePlane). We summarize it for a finite projective plane below:

Setup: Use a set Q of q different symbols for coordinate values, two of which are 0 and 1. Start with four points O, I, X, Y forming a quadrangle. XY is the “line at infinityMathworldPlanetmath.

Construction: O and I are given coordinates (0,0) and (1,1), and the other points on OI (except its intersectionMathworldPlanetmathPlanetmath with ) arbitrarily (c,c) with unique cQ. For any point P not on , let YPintersect OI at (a,a), and let XP intersect OI at (b,b). Then P will be given (a,b). For the coordinates of points on , intersect the lines joining (0,0) with (1,m), for all mQ, with , calling the intersection (m). Finally, Y gets coordinate () (instead of () in the literature).

Lines not through Y are given coordinates [m,k] where (m) and (0,k) are their intersections with and with OY respectively; lines through Y (other than ) get coordinates [k] going by theirintersection (k,0) with OX. The line gets [] (instead of [] in the literature).

Coordinates from bipartite graphs

The whole business with coordinates becomes a bit more transparent when we tryto actually construct the thing as a bipartite graph, starting from one edge,Y say.

There are q more points (other than Y) incident to , let’s callthem Ym where m ranges over the q different values of the set Q.Again, each Ym is incident to q more lines (apart from ), let’scall those mb where b is another subscript from Q.Likewise there are q more lines (other than ) incident to Y, let’scall them x and to each of them are incident q more points (apartfrom Y) which we can label Yxy.

This immediately produces the incidence list of the preceding sectionMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath.Pictorially, for q=2 (with the “to be assessed” portion filled inas thinner lines):



YxyxYYmmb


We already have 0 containing all points Y0y, and in additionPlanetmathPlanetmath if wewanted we could easily arrange for 00 to be incident with all theYx0 (just renumber the labels y in the sets Yx0 for every x),and for 10 to be incident with all the Ycc (just look at whichYxy are incident with 10, then exercise the freedom we still haveto relabel all the x, matching each time the corresponding y there). Thisreproduces the entire coordinatisation.

Projective planes as permutation systems

Five sides of the hexagonMathworldPlanetmath are self-evident. On the left we have thesingle edge Y, along the top we fan out in two stages to q and q2items, along the bottom we also fan out in two stages to q and q2 items,and the hard part is the right. We have by now accounted for 2q2+2q+1 edgesso we know there must be exactly q3 more edges, between some ofthose q2 points and some of those q2 lines. But where?

For q=2 it is simple enough to avoid 4-cycle clashes (and the diagram showswhat is, up to isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath, the only solution). In general, it is an openproblem to find all possible solutions.

From the projective plane properties it is easy to see that any point Yxy must, forevery value of m, be incident to no more than one of the mb (becauseif it was incident to two they would intersect both in our Yxy and intheir shared Ym at the bottom). On the other hand, Yxy needs q moremates so it needs to choose exactly one mb for every value of m.

By exactly the same reasoning, any mb needs to be incident with, forevery value of x, at most one and then exactly one Yxy. In other words,the projective plane structureMathworldPlanetmath takes the form of, for each pair of values x and m,a bijectionMathworldPlanetmath ψxm between the y indices and the b indices.

This is not yet the only constraint. A closer analysis [vG03] showsthat, in order to prevent any two lines meeting in more than one point or anytwo points in more than two lines, all compound bijections of the form

ψxmψxm-1ψxmψxm-1

(for mm and xx) must be derangementsMathworldPlanetmath, i.e. permutationsMathworldPlanetmath that do not leave any index in place. It is not hard to seethis is just a device to prevent 4-cycles. And careful scrutiny of the graphshows that, after arranging 5 of 6 edges along trees fanning out as above, andafter recognising there are those bijections along the sixth edge, thesederangement shenanigans stop the only remaining gap for 4-cycles to lurk.

This could be called the permutation groupMathworldPlanetmath interpretationMathworldPlanetmath of projective plane structure.The algebraic version appears in the next section.

Planar ternary rings

We’ve been giving our points and lines cooordinates from a set Q of q different labels. We can give Q the structure of a ternary ring, that is, a set with a ternary operation pqr, by defining

y=xmb(x,y)is on[m,b](1)

Thus, geometric properties of a projective plane may not be analyzed algebraically. See this entry (http://planetmath.org/TernaryRingOfAProjectivePlane) for more detail. Conversely, every ternary ring determines a projective plane with coordinates as above, so that algebraic properties of the ring can be interpreted geometrically. For more detail on this, see this entry (http://planetmath.org/ProjectivePlaneOfATernaryRing).

Fields and division rings are examples of ternary rings. But there are other classes of algebraic structuresPlanetmathPlanetmath intermediate between fields and ternary rings. See [dRe96] for a survey. There are four different projective planes known of order 9, many more of order 16, and so on.

Finding all PTRs in general remains of course just as hard as finding projective planes!

Finite projective planes as incidence structures

Finite projective planes can be defined as(simple square) 2-(q2+q+1,q+1, 1) designs,or what’s the same thing, Steiner systemsMathworldPlanetmath S(2,q+1,q2+q+1).This way, we already assume in the definition that each “block”(line) contains exactly q+1 points, from which it follows by calculation thatthe number of lines that contain a given point is also q+1, and that thetotal number of lines equals the total number of points.

Also, the unique incidence property that every two points lie together onexactly one line is given, and the dual one that every two lines meet inexactly one point then follows from the numbers and the properties that definea design or Steiner system.

We took a different route to projective planes above: we saw we only need to start withthese two unique incidence properties, and can prove from them thatthe number of points on a line and the number of lines through a point are bothfixed (i.e. that the projective plane and its dual are both designs).

Finite projective planes as incidence matrices

Consider an arbitrary projective plane of order q.We know there are n=q2+q+1 points and the same number of lines. Let Abe an n×n matrix of which the rows and columns represent lines andpoints of the plane, and give the value 1 to entries at intersections wherethe point (represented by the column) lies on the line (represented by therow), and leave the other entries zeros. Such an A is known as theincidence matrixMathworldPlanetmath of the plane.

AA has rows and columns both representing lines, and the entrieshere are the dot productsMathworldPlanetmath of any two rows of A, i.e. the number of pointsany two lines l and m have in common, which is q+1 when l=m and 1otherwise, by the projective plane properties.

AA=(q+1111q+1111q+1)=J+qI

where I is the identity matrixMathworldPlanetmath (ones along the diagonalMathworldPlanetmath, zeros everywhereelse) and J is the matrix filled with ones in every entry. Note AAhas this same value for every projective plane with n points and n lines,while A on its own of course varies if there is more than one plane of thesame order, as the plane is fully determined by its incidence matrix. Also,AA having this value is the only thing needed to make the planespecified by A satisfy the projective plane properties; it is a fully equivalentMathworldPlanetmathPlanetmathPlanetmathformulation of those properties.

The determinantMathworldPlanetmath of A is best evaluated via that of AA,because (detA)2=(detA)(detA)=detAA, and we knowevery entry of AA. The eigenvaluesMathworldPlanetmathPlanetmathPlanetmathPlanetmath of any n×n matrix ofthe form J+qI are easily seen to be

  • q+n (once) with eigenvectorMathworldPlanetmathPlanetmathPlanetmath 𝐱 for which x0=x1=x2

  • q (multiplicityMathworldPlanetmath n-1) for the complementaryPlanetmathPlanetmath eigenspaceMathworldPlanetmathx0+x1+x2=0

by letting the matrix act on these eigenvectors. This gives

detAA=qn-1(q+n)

which in our case (n=q2+q+1) amounts to

detAA=qq2+q(q2+2q+1)

As q2+q is even and the other factor a square, we get an integer

detA=±qq2+q2(q+1)=±q(q+12)(q+1)

where the sign is moot, as A has no correspondence between its columns androws.

Existence

The Bruck–Ryser theorem [BR49] states that

If q is the order of a projective plane, and q1 or 2(mod  4), then q isthe sum of two integer squares (one of which can be 02).

It can be proven [BR49, Cam94] using the incidence matrix A, by aclever rearrangement of 𝐱AA𝐱 (plus one extra term) for anarbitrary vector 𝐱, on which gradually constraints are imposed fourcomponentsMathworldPlanetmath at a time using the fact that each integer is a sum of foursquares. The argument only works when q2+q+1=n-1(mod  4), hence theconstraint on q (mod 4).

Interestingly, there is a partial converse [HR54]: whenever q isallowed by the theorem (either congruentMathworldPlanetmathPlanetmath 0 or 3 (mod 4), or congruent 1or 2 (mod 4) and a sum of two squares), there always is a rationaln×n matrix A (where n=q2+q+1) such that AA=M. Of course,the matrix is only a proper incidence matrix if that rational matrix only hasentries 0 and 1.

The theorem doesn’t rule out any potential projective plane orders q0 or 3(mod  4),but does rule out a large number of q1 or 2(mod  4), starting withn=6,14,21,22. Note in passing that it is easy to prove no primepower falls foul of Bruck–Ryser, which is just as well, as (classical)planes exist for all those orders.

The only other order ruled out to date is 10, via an epic computer searchby Lam, Swiercz and Thiel (readhttp://www.cecm.sfu.ca/organics/papers/lam/index.htmlhttp://www.cecm.sfu.ca/organics/papers/lam/index.htmlfor Lam’s account).

All projective planes actually found to date, even the non-classical ones,have an order q that is the power of a prime. The prime power conjecturesays this is the case for all projective planes. It is still open.

References

  • 1
  • BR49 R. H. Bruck & H. J. Ryser,“The non-existence of certain finite projective planes”Can. J. Math.12 (1949) pp 189–203
  • HR54 M. Hall, Jr. & H. J. Ryser,“Normal completions of incidence matrices”Amer. J. Math. 76 (1954) pp 581–9
  • Hal59 Marshall Hall, Jr., The Theory of Groups,Macmillan 1959
  • Cam94 Peter J. Cameron,Combinatorics: topics, techniques, algorithms,
    Camb. Univ. Pr. 1994, ISBN  0 521 45761 0
    http://www.maths.qmul.ac.uk/ pjc/comb/http://www.maths.qmul.ac.uk/ pjc/comb/
    (solutions, errata &c.)
  • CD96 Charles J. Colbourn and Jeffrey H. Dinitz, eds.
    The CRC Handbook of Combinatorial Designs,
    CRC Press 1996, ISBN  0 8493 8948 8
    http://www.emba.uvm.edu/ dinitz/hcd.htmlhttp://www.emba.uvm.edu/ dinitz/hcd.html
    (errata, new results)
    the reference work on designs incl. Steiner systems,proj. planes
  • dRe96 Marialuisa J. de Resmini,“Projective Planes, Nondesarguesian”,pp 708–718 in the previous reference
  • vG03 Marijke van Gans, M.Phil.(Qual.) thesis,Birmingham 2003
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 0:23:24