Perles configuration

The Perles configuration

In geometry, the Perles configuration is a system of nine points and nine lines in the Euclidean plane for which every combinatorially equivalent realization has at least one irrational number as one of its coordinates. It can be constructed from the diagonals and symmetry lines of a regular pentagon, and their crossing points. All of the realizations of the Perles configuration in the projective plane are equivalent to each other under projective transformations.

The Perles configuration is the smallest configuration of points and lines that cannot be realized with rational coordinates. It is named after Micha Perles, who used it to construct an eight-dimensional convex polytope that cannot be given rational number coordinates and that have the fewest vertices (twelve) of any known irrational polytope.

Construction

One way of constructing the Perles configuration is to start with a regular pentagon and its five diagonals. These diagonals form the sides of a smaller inner pentagon nested inside the outer pentagon. Each vertex of the outer pentagon is situated opposite from a vertex of the inner pentagon. The nine points of the configuration consist of four out of the five vertices of each pentagon and the shared center of the two pentagons. Two opposite vertices are omitted, one from each pentagon.

The nine lines of the configuration consist of the five lines that are diagonals of the outer pentagon and sides of the inner pentagon, and the four lines that pass through the center and through opposite pairs of vertices from the two pentagons.

Projective invariance and irrationality

A realization of the Perles configuration is defined to consist of any nine points and nine lines with the same intersection pattern. That means that a point and line intersect each other in the realization, if and only if they intersect in the configuration constructed from the regular pentagon. Every realization of this configuration in the Euclidean plane or, more generally, in the real projective plane is equivalent, under a projective transformation, to a realization constructed in this way from a regular pentagon. A more detailed proof of this fact assigns arbitrary projective coordinates to the two outer points on the four-point line, the center point of the configuration, and one of the remaining two outer points. These points determine the position of one middle point on the four-point line, and one then defines a parameter specifying in terms of these coordinates the position of the fourth point on this line. This parameter cannot be chosen arbitrarily, but by calculating in terms of its value the projective coordinates of the remaining points, collinearity of the points constrains it to obey a quadratic equation, the equation satisfied by the golden ratio. The two solutions to this equation both produce configurations of the same type, with rearranged points.

Because the cross-ratio, a number defined from any four collinear points, does not change under projective transformations, every realization has four points having the same cross-ratio as the cross-ratio of the four collinear points in the realization derived from the regular pentagon. But, these four points have $1+\varphi$ as their cross-ratio, where $\varphi$ is the golden ratio, an irrational number. Every four collinear points with rational coordinates have a rational cross ratio, so the Perles configuration cannot be realized by rational points.

Answering a question of Branko Grünbaum, József Solymosi has proved that the Perles configuration is the smallest possible irrational configuration of points and lines: every configuration of eight or fewer points in the Euclidean plane, and lines through subsets of these points, has a combinatorially equivalent configuration with points that have rational numbers as their coordinates.

Applications

In polyhedral combinatorics

Perles used his configuration to construct an eight-dimensional convex polytope with twelve vertices that can similarly be realized with real coordinates but not with rational coordinates. The points of the configuration, three of them doubled and with signs associated with each point, form the Gale diagram of the Perles polytope.

Ernst Steinitz's proof of Steinitz's theorem can be used to show that every three-dimensional polytope can be realized with rational coordinates, but it is now known that there exist irrational polytopes in four dimensions. Therefore, the Perles polytope does not have the smallest possible dimension among irrational polytopes. However, the Perles polytope has the fewest vertices of any known irrational polytope.

In discrete geometry

The existence of irrational configurations such as the Perles configuration forms a counterexample to a 2021 conjecture of M. Mirzaei and A. Suk, on the maximum number of point-line incidences among $n$ points and $n$ lines. Without restriction, this maximum number is proportional to $n^{4/3}$, but Mirzaei and Suk conjectured that forbidding any smaller point–line configuration from appearing would lead to an asymptotic reduction in the number of incidences. When the forbidden configuration is an irrational configuration, such as the Perles configuration, this is not true. This is because there are systems of $n$ points arranged in an integer grid and $n$ lines that avoid the Perles configuration (because of its irrationality) and yet have a number of incidences proportional to $n^{4/3}$.

As part of a proof that recognizing the visibility graphs of finite point sets is hard for the existential theory of the reals, Cardinal & Hoffmann (2017) showed how to convert problems of straightening pseudoline arrangements into this visibility graph recognition problem. The same conversion, applied to the Perles configuration, produces finite point sets for which any other point set with the same visibility graph must include an irrational coordinate, preventing the problem from being solved merely by searching all point configurations in a large enough integer grid.

Other

A matroid defined from the Perles configuration, and its dual matroid, has been applied in characterizing certain classes of matroids that are linear matroids over the finite field $\mathbb {F} _{4}$ and over all sufficiently large fields. This is not true of the Perles matroid: it is representable over $\mathbb {F} _{4}$ but not representable over the rational numbers. Its unrepresentability is inherited by any other matroid within which the Perles matroid appears as a matroid minor. In tropical geometry, this matroid has been used to separate variant analogues of matrix rank from each other.

In graph drawing, the Perles configuration has been used to show that drawing a planar graph with the minimum line cover number, the number of lines needed to cover all the edges of the drawing, may require irrational coordinates. In particular, one such graph may be formed by the diagonals and symmetry lines of the regular pentagon, before the removal of one of these lines to form the Perles configuration. The vertices of this graph are 16 crossing points of these lines (including the nine points of the Perles configuration); its edges connect pairs of consecutive points along each line. Covering the edges of this graph with only ten lines forces the drawing to contain a copy of the Perles configuration and therefore to have an irrational vertex.

In coding theory, the Perles configuration appears in an enumeration of 9-point configurations used to count maximum distance separable codes over finite fields.

History and related work

The Perles configuration was introduced by Micha Perles in the 1960s. It is not the first known example of an irrational configuration of points and lines. Mac Lane (1936) describes an 11-point example, obtained by applying Von Staudt's algebra of throws to construct a configuration corresponding to the square root of two.

There is a long history of study of regular projective configurations, finite systems of points and lines in which each point touches equally many lines and each line touches equally many points. However, despite being named similarly to these configurations, the Perles configuration is not regular: most of its points touch three lines and most of its lines touch three points, but there is one line of four points and one point on four lines. In this respect it differs from the Pappus configuration, which also has nine points and nine lines, but with three points on every line and three lines through every point. Not every abstractly-described system of points and lines has a planar realization; the Möbius–Kantor configuration of eight points and eight lines does not. It is known that every regular configuration with three lines per point and at most 13 points, if realizable in the Euclidean plane at all, can be realized with rational coordinates. Grünbaum has conjectured that this is true for all numbers of points, but this remains an open problem.

References

• Berger, Marcel (2010), "I.4 Three configurations of the affine plane and what has happened to them: Pappus, Desargues, and Perles", Geometry revealed, Berlin, New York: Springer-Verlag, pp. 17–23, doi:10.1007/978-3-540-70997-8, ISBN 978-3-540-70996-1, MR 2724440
• Cardinal, Jean; Hoffmann, Udo (2017), "Recognition and complexity of point visibility graphs", Discrete & Computational Geometry, 57 (1): 164–178, doi:10.1007/s00454-016-9831-1, MR 3589061
• Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander (2023), "The complexity of drawing graphs on few lines and few planes", Journal of Graph Algorithms and Applications, 27 (6): 459–488, doi:10.7155/jgaa.00630, MR 4631653
• Grace, Kevin (2021), "The templates for some classes of quaternary matroids", Journal of Combinatorial Theory, Series B, 146: 286–363, doi:10.1016/j.jctb.2020.09.011, MR 4155284
• Grünbaum, Branko (2003), Convex polytopes, Graduate Texts in Mathematics, vol. 221 (Second ed.), New York: Springer-Verlag, pp. 93–95, ISBN 978-0-387-00424-2, MR 1976856
• Iampolskaia, Anna V.; Skorobogatov, Alexei N.; Sorokin, Evgenii A. (1995), "Formula for the number of [9,3] MDS codes", IEEE Transactions on Information Theory, 41 (6): 1667–1671, doi:10.1109/18.476239; the Perles configuration is listed as the "type 11" overdetermined 9-point configuration
• Mac Lane, Saunders (1936), "Some interpretations of abstract linear dependence in terms of projective geometry", American Journal of Mathematics, 58 (1): 236–240, doi:10.2307/2371070, JSTOR 2371070, MR 1507146
• Shitov, Yaroslav (2023), "A separation between tropical matrix ranks", Proceedings of the American Mathematical Society, 151 (2): 489–499, arXiv:1712.03071, doi:10.1090/proc/16156, MR 4520003
• Solymosi, József (2025), "On Perles' configuration", SIAM Journal on Discrete Mathematics, 39 (2): 912–920, arXiv:2408.09370, doi:10.1137/24M1686851, MR 4898682
• Ziegler, Günter M. (2008), "Nonrational configurations, polytopes, and surfaces", The Mathematical Intelligencer, 30 (3): 36–42, arXiv:0710.4453, doi:10.1007/BF02985377, MR 2437198