Finite geometry

Last updated
Finite affine plane of order 2, containing 4 "points" and 6 "lines". Lines of the same color are "parallel". The centre of the figure is not a "point" of this affine plane, hence the two green "lines" don't "intersect". Order 2 affine plane.svg
Finite affine plane of order 2, containing 4 "points" and 6 "lines". Lines of the same color are "parallel". The centre of the figure is not a "point" of this affine plane, hence the two green "lines" don't "intersect".

A finite geometry is any geometric system that has only a finite number of points. The familiar Euclidean geometry is not finite, because a Euclidean line contains infinitely many points. A geometry based on the graphics displayed on a computer screen, where the pixels are considered to be the points, would be a finite geometry. While there are many systems that could be called finite geometries, attention is mostly paid to the finite projective and affine spaces because of their regularity and simplicity. Other significant types of finite geometry are finite Möbius or inversive planes and Laguerre planes, which are examples of a general type called Benz planes, and their higher-dimensional analogs such as higher finite inversive geometries.

Contents

Finite geometries may be constructed via linear algebra, starting from vector spaces over a finite field; the affine and projective planes so constructed are called Galois geometries. Finite geometries can also be defined purely axiomatically. Most common finite geometries are Galois geometries, since any finite projective space of dimension three or greater is isomorphic to a projective space over a finite field (that is, the projectivization of a vector space over a finite field). However, dimension two has affine and projective planes that are not isomorphic to Galois geometries, namely the non-Desarguesian planes. Similar results hold for other kinds of finite geometries.

Finite planes

Finite affine plane of order 3, containing 9 points and 12 lines. Hesse configuration.svg
Finite affine plane of order 3, containing 9 points and 12 lines.

The following remarks apply only to finite planes. There are two main kinds of finite plane geometry: affine and projective. In an affine plane, the normal sense of parallel lines applies. In a projective plane, by contrast, any two lines intersect at a unique point, so parallel lines do not exist. Both finite affine plane geometry and finite projective plane geometry may be described by fairly simple axioms.

Finite affine planes

An affine plane geometry is a nonempty set X (whose elements are called "points"), along with a nonempty collection L of subsets of X (whose elements are called "lines"), such that:

  1. For every two distinct points, there is exactly one line that contains both points.
  2. Playfair's axiom: Given a line and a point not on , there exists exactly one line containing such that
  3. There exists a set of four points, no three of which belong to the same line.

The last axiom ensures that the geometry is not trivial (either empty or too simple to be of interest, such as a single line with an arbitrary number of points on it), while the first two specify the nature of the geometry.

The simplest affine plane contains only four points; it is called the affine plane of order 2. (The order of an affine plane is the number of points on any line, see below.) Since no three are collinear, any pair of points determines a unique line, and so this plane contains six lines. It corresponds to a tetrahedron where non-intersecting edges are considered "parallel", or a square where not only opposite sides, but also diagonals are considered "parallel".

The affine plane of order 3 is known as the Hesse configuration.

More generally, a finite affine plane of order n has n2 points and n2 + n lines; each line contains n points, and each point is on n + 1 lines.

Finite projective planes

A projective plane geometry is a nonempty set X (whose elements are called "points"), along with a nonempty collection L of subsets of X (whose elements are called "lines"), such that:

  1. For every two distinct points, there is exactly one line that contains both points.
  2. The intersection of any two distinct lines contains exactly one point.
  3. There exists a set of four points, no three of which belong to the same line.
Duality in the Fano plane: Each point corresponds to a line and vice versa. Fano plane Hasse diagram.svg
Duality in the Fano plane: Each point corresponds to a line and vice versa.

An examination of the first two axioms shows that they are nearly identical, except that the roles of points and lines have been interchanged. This suggests the principle of duality for projective plane geometries, meaning that any true statement valid in all these geometries remains true if we exchange points for lines and lines for points. The smallest geometry satisfying all three axioms contains seven points. In this simplest of the projective planes, there are also seven lines; each point is on three lines, and each line contains three points.

The Fano plane Fano plane.svg
The Fano plane

This particular projective plane is sometimes called the Fano plane . If any of the lines is removed from the plane, along with the points on that line, the resulting geometry is the affine plane of order 2. The Fano plane is called theprojective plane of order 2 because it is unique (up to isomorphism). In general, the projective plane of order n has n2 + n + 1 points and the same number of lines; each line contains n + 1 points, and each point is on n + 1 lines.

A permutation of the Fano plane's seven points that carries collinear points (points on the same line) to collinear points is called a collineation of the plane. The full collineation group is of order 168 and is isomorphic to the group PSL(2,7) ≈ PSL(3,2), which in this special case is also isomorphic to the general linear group GL(3,2) ≈ PGL(3,2).

Order of planes

A finite plane of ordern is one such that each line has n points (for an affine plane), or such that each line has n + 1 points (for a projective plane). One major open question in finite geometry is:

Is the order of a finite plane always a prime power?

This is conjectured to be true.

Affine and projective planes of order n exist whenever n is a prime power (a prime number raised to a positive integer exponent), by using affine and projective planes over the finite field with n = pk elements. Planes not derived from finite fields also exist (e.g. for ), but all known examples have order a prime power. [1]

The best general result to date is the Bruck–Ryser theorem of 1949, which states:

If n is a positive integer of the form 4k + 1 or 4k + 2 and n is not equal to the sum of two integer squares, then n does not occur as the order of a finite plane.

The smallest integer that is not a prime power and not covered by the Bruck–Ryser theorem is 10; 10 is of the form 4k + 2, but it is equal to the sum of squares 12 + 32. The non-existence of a finite plane of order 10 was proven in a computer-assisted proof that finished in 1989 – see ( Lam 1991 ) for details.

The next smallest number to consider is 12, for which neither a positive nor a negative result has been proved.

History

Individual examples can be found in the work of Thomas Penyngton Kirkman (1847) and the systematic development of finite projective geometry given by von Staudt (1856).

The first axiomatic treatment of finite projective geometry was developed by the Italian mathematician Gino Fano. In his work [2] on proving the independence of the set of axioms for projective n-space that he developed, [3] he considered a finite three dimensional space with 15 points, 35 lines and 15 planes (see diagram), in which each line had only three points on it. [4]

In 1906 Oswald Veblen and W. H. Bussey described projective geometry using homogeneous coordinates with entries from the Galois field GF(q). When n + 1 coordinates are used, the n-dimensional finite geometry is denoted PG(n, q). [5] It arises in synthetic geometry and has an associated transformation group.

Finite spaces of 3 or more dimensions

For some important differences between finite plane geometry and the geometry of higher-dimensional finite spaces, see axiomatic projective space. For a discussion of higher-dimensional finite spaces in general, see, for instance, the works of J.W.P. Hirschfeld. The study of these higher-dimensional spaces (n ≥ 3) has many important applications in advanced mathematical theories.

Axiomatic definition

A projective spaceS can be defined axiomatically as a set P (the set of points), together with a set L of subsets of P (the set of lines), satisfying these axioms : [6]

The last axiom eliminates reducible cases that can be written as a disjoint union of projective spaces together with 2-point lines joining any two points in distinct projective spaces. More abstractly, it can be defined as an incidence structure (P, L, I) consisting of a set P of points, a set L of lines, and an incidence relation I stating which points lie on which lines.

Obtaining a finite projective space requires one more axiom:

In any finite projective space, each line contains the same number of points and the order of the space is defined as one less than this common number.

A subspace of the projective space is a subset X, such that any line containing two points of X is a subset of X (that is, completely contained in X). The full space and the empty space are always subspaces.

The geometric dimension of the space is said to be n if that is the largest number for which there is a strictly ascending chain of subspaces of this form:

Algebraic construction

A standard algebraic construction of systems satisfies these axioms. For a division ring D construct an (n + 1)-dimensional vector space over D (vector space dimension is the number of elements in a basis). Let P be the 1-dimensional (single generator) subspaces and L the 2-dimensional (two independent generators) subspaces (closed under vector addition) of this vector space. Incidence is containment. If D is finite then it must be a finite field GF(q), since by Wedderburn's little theorem all finite division rings are fields. In this case, this construction produces a finite projective space. Furthermore, if the geometric dimension of a projective space is at least three then there is a division ring from which the space can be constructed in this manner. Consequently, all finite projective spaces of geometric dimension at least three are defined over finite fields. A finite projective space defined over such a finite field has q + 1 points on a line, so the two concepts of order coincide. Such a finite projective space is denoted by PG(n, q), where PG stands for projective geometry, n is the geometric dimension of the geometry and q is the size (order) of the finite field used to construct the geometry.

In general, the number of k-dimensional subspaces of PG(n, q) is given by the product: [8]

which is a Gaussian binomial coefficient, a q analogue of a binomial coefficient.

Classification of finite projective spaces by geometric dimension

The smallest projective three-space

PG(3,2) but not all the lines are drawn Fano3space.png
PG(3,2) but not all the lines are drawn

The smallest 3-dimensional projective space is over the field GF(2) and is denoted by PG(3,2). It has 15 points, 35 lines, and 15 planes. Each plane contains 7 points and 7 lines. Each line contains 3 points. As geometries, these planes are isomorphic to the Fano plane.

Square model of Fano 3-space 150614-PG-3-2-schoolgirls-arrangement.png
Square model of Fano 3-space

Every point is contained in 7 lines. Every pair of distinct points are contained in exactly one line and every pair of distinct planes intersects in exactly one line.

In 1892, Gino Fano was the first to consider such a finite geometry.

Kirkman's schoolgirl problem

PG(3,2) arises as the background for a solution of Kirkman's schoolgirl problem, which states: "Fifteen schoolgirls walk each day in five groups of three. Arrange the girls’ walk for a week so that in that time, each pair of girls walks together in a group just once." There are 35 different combinations for the girls to walk together. There are also 7 days of the week, and 3 girls in each group. Two of the seven non-isomorphic solutions to this problem can be stated in terms of structures in the Fano 3-space, PG(3,2), known as packings. A spread of a projective space is a partition of its points into disjoint lines, and a packing is a partition of the lines into disjoint spreads. In PG(3,2), a spread would be a partition of the 15 points into 5 disjoint lines (with 3 points on each line), thus corresponding to the arrangement of schoolgirls on a particular day. A packing of PG(3,2) consists of seven disjoint spreads and so corresponds to a full week of arrangements.

See also

Notes

  1. Laywine, Charles F.; Mullen, Gary L. (1998-09-17). Discrete Mathematics Using Latin Squares. John Wiley & Sons. ISBN   9780471240648.
  2. Fano, G. (1892), "Sui postulati fondamentali della geometria proiettiva", Giornale di Matematiche, 30: 106–132
  3. Collino, Conte & Verra 2013 , p. 6
  4. Malkevitch Finite Geometries? an AMS Featured Column
  5. Oswald Veblen (1906) Finite Projective Geometries, Transactions of the American Mathematical Society 7: 241–59
  6. Beutelspacher & Rosenbaum 1998 , pp. 6–7
  7. also referred to as the Veblen–Young axiom and mistakenly as the axiom of Pasch ( Beutelspacher & Rosenbaum 1998 , pgs. 6–7). Pasch was concerned with real projective space and was attempting to introduce order, which is not a concern of the Veblen–Young axiom.
  8. Dembowski 1968 , p. 28, where the formula is given, in terms of vector space dimension, by Nk+1(n + 1, q).

Related Research Articles

<span class="mw-page-title-main">Euclidean space</span> Fundamental space of geometry

Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension n, which are called Euclidean n-spaces when one wants to specify their dimension. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes. The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics.

<span class="mw-page-title-main">Projective plane</span> Geometric concept of a 2D space with a "point at infinity" adjoined

In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect at a single point, but there are some pairs of lines that do not intersect. A projective plane can be thought of as an ordinary plane equipped with additional "points at infinity" where parallel lines intersect. Thus any two distinct lines in a projective plane intersect at exactly one point.

<span class="mw-page-title-main">Steiner system</span> Block design in combinatorial mathematics

In combinatorial mathematics, a Steiner system is a type of block design, specifically a t-design with λ = 1 and t = 2 or (recently) t ≥ 2.

<span class="mw-page-title-main">Projective space</span> Completion of the usual space with "points at infinity"

In mathematics, the concept of a projective space originated from the visual effect of perspective, where parallel lines seem to meet at infinity. A projective space may thus be viewed as the extension of a Euclidean space, or, more generally, an affine space with points at infinity, in such a way that there is one point at infinity of each direction of parallel lines.

<span class="mw-page-title-main">Projective geometry</span> Type of geometry

In mathematics, projective geometry is the study of geometric properties that are invariant with respect to projective transformations. This means that, compared to elementary Euclidean geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts. The basic intuitions are that projective space has more points than Euclidean space, for a given dimension, and that geometric transformations are permitted that transform the extra points to Euclidean points, and vice-versa.

<span class="mw-page-title-main">Affine space</span> Euclidean space without distance and angles

In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related to parallelism and ratio of lengths for parallel line segments.

<span class="mw-page-title-main">Projective linear group</span> Construction in group theory

In mathematics, especially in the group theoretic area of algebra, the projective linear group (also known as the projective general linear group or PGL) is the induced action of the general linear group of a vector space V on the associated projective space P(V). Explicitly, the projective linear group is the quotient group

<span class="mw-page-title-main">Fano plane</span> Geometry with 7 points and 7 lines

In finite geometry, the Fano plane is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines cannot exist with this pattern of incidences in Euclidean geometry, but they can be given coordinates using the finite field with two elements. The standard notation for this plane, as a member of a family of projective spaces, is PG(2, 2). Here PG stands for "projective geometry", the first parameter is the geometric dimension and the second parameter is the order.

In geometry, a striking feature of projective planes is the symmetry of the roles played by points and lines in the definitions and theorems, and (plane) duality is the formalization of this concept. There are two approaches to the subject of duality, one through language and the other a more functional approach through special mappings. These are completely equivalent and either treatment has as its starting point the axiomatic version of the geometries under consideration. In the functional approach there is a map between related geometries that is called a duality. Such a map can be constructed in many ways. The concept of plane duality readily extends to space duality and beyond that to duality in any finite-dimensional projective geometry.

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. Such involutions sometimes have fixed points, so that the dual of A is A itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

In geometry, an affine plane is a system of points and lines that satisfy the following axioms:

<span class="mw-page-title-main">Incidence structure</span> Abstract mathematical system of two types of objects and a relation between them

In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore all the properties of this geometry except for the relation of which points are on which lines for all points and lines. What is left is the incidence structure of the Euclidean plane.

<span class="mw-page-title-main">Incidence geometry</span> Field of mathematics which studies incidence structures

In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An incidence structure is what is obtained when all other concepts are removed and all that remains is the data about which points lie on which lines. Even with this severe limitation, theorems can be proved and interesting facts emerge concerning this structure. Such fundamental results remain valid when additional concepts are added to form a richer geometry. It sometimes happens that authors blur the distinction between a study and the objects of that study, so it is not surprising to find that some authors refer to incidence structures as incidence geometries.

In mathematics, in the field of geometry, a polar space of rank n (n ≥ 3), or projective indexn − 1, consists of a set P, conventionally called the set of points, together with certain subsets of P, called subspaces, that satisfy these axioms:

<span class="mw-page-title-main">Space (mathematics)</span> Mathematical set with some added structure

In mathematics, a space is a set with some added structure. While modern mathematics uses many types of spaces, such as Euclidean spaces, linear spaces, topological spaces, Hilbert spaces, or probability spaces, it does not define the notion of "space" itself.

<span class="mw-page-title-main">Galois geometry</span>

Galois geometry is the branch of finite geometry that is concerned with algebraic and analytic geometry over a finite field. More narrowly, a Galois geometry may be defined as a projective space over a finite field.

In mathematics, a Hall plane is a non-Desarguesian projective plane constructed by Marshall Hall Jr. (1943). There are examples of order p2n for every prime p and every positive integer n provided p2n > 4.

In geometry, specifically projective geometry, a blocking set is a set of points in a projective plane that every line intersects and that does not contain an entire line. The concept can be generalized in several ways. Instead of talking about points and lines, one could deal with n-dimensional subspaces and m-dimensional subspaces, or even more generally, objects of type 1 and objects of type 2 when some concept of intersection makes sense for these objects. A second way to generalize would be to move into more abstract settings than projective geometry. One can define a blocking set of a hypergraph as a set that meets all edges of the hypergraph.

<span class="mw-page-title-main">PG(3,2)</span> Smallest 3D projective space

In finite geometry, PG(3,2) is the smallest three-dimensional projective space. It can be thought of as an extension of the Fano plane. It has 15 points, 35 lines, and 15 planes. It also has the following properties:

A frequently studied problem in discrete geometry is to identify ways in which an object can be covered by other simpler objects such as points, lines, and planes. In projective geometry, a specific instance of this problem that has numerous applications is determining whether, and how, a projective space can be covered by pairwise disjoint subspaces which have the same dimension; such a partition is called a spread. Specifically, a spread of a projective space , where is an integer and a division ring, is a set of -dimensional subspaces, for some such that every point of the space lies in exactly one of the elements of the spread.

References