Perles configuration

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.{{sfnp|Ziegler|2008}}

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.{{sfnp|Ziegler|2008}}

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.{{sfnp|Grünbaum|2003}} 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.{{sfnp|Ziegler|2008}}

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+\backslash varphi$ as their cross-ratio, where $\backslash 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.{{sfnp|Grünbaum|2003}}

Answering a question of Branko Grünbaum,{{sfnp|Grünbaum|2003}} 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.{{sfnp|Solymosi|2025}}

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.{{sfnp|Grünbaum|2003|page=96a}}

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.{{sfnp|Grünbaum|2003|page=96a}}

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\}$. Mirzaei and Suk conjectured that forbidding any smaller point–line configuration from appearing would lead to an asymptotic reduction in the number of incidences. However, their conjecture is false when the forbidden configuration is an irrational configuration, such as the Perles configuration. There exist systems of $n$ points arranged in an integer grid and $n$ lines through these points that have a number of incidences proportional to $n^\{4/3\}$. Because their points lie on a grid, these systems avoid the Perles configuration and any irrational configuration, in contradiction to the conjecture.{{sfnp|Solymosi|2025}}

As part of a proof that recognizing the visibility graphs of finite point sets is hard for the existential theory of the reals, {{harvtxt|Cardinal|Hoffmann|2017}} showed how to convert problems of testing whether pseudoline arrangements can be straightened into equivalent problems of visibility graph recognition. 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. Because of these irrational visibility graphs, it is not possible to test whether a graph is a visibility graph merely by checking all point configurations in a large enough integer grid.{{sfnp|Cardinal|Hoffmann|2017}}

A matroid can be defined from the Perles configuration, called the Perles matroid. It has the points of the configuration as its elements; a subset of at most three elements is independent when it does not consist of three points on one of the lines of the configuration. This matroid and its dual matroid have been applied in characterizing certain classes of matroids that are linear matroids over the finite field $\backslash mathbb\{F\}\_4$ and over all sufficiently large fields. The Perles matroid does not have this property: it is linear over $\backslash mathbb\{F\}\_4$ but not over the rational numbers. Its nonlinearity over the rationals is inherited by any other matroid within which the Perles matroid appears as a matroid minor.{{sfnp|Grace|2021}} In tropical geometry, this matroid has been used to separate variant analogues of matrix rank from each other.{{sfnp|Shitov|2023}}

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.{{sfnp|Chaplick|Fleszar|Lipp|Ravsky|2023|loc=Section 4|pp=472–477}}

In coding theory, the Perles configuration appears in an enumeration of 9-point configurations used to count maximum distance separable codes over finite fields.{{sfnp|Iampolskaia|Skorobogatov|Sorokin|1995}}

The Perles configuration was introduced by Micha Perles in the 1960s.{{harvtxt|Grünbaum|2003}}; {{harvtxt|Ziegler|2008}}; {{harvtxt|Berger|2010}} It is not the first known example of an irrational configuration of points and lines. {{harvtxt|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.{{harvtxt|Mac Lane|1936}}; {{harvtxt|Ziegler|2008}}

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.{{sfnp|Berger|2010}} 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.{{sfnp|Solymosi|2025}}

{{reflist}}

• {{Citation | last1=Berger | first1=Marcel | author1-link=Marcel Berger | title=Geometry revealed | publisher=Springer-Verlag | location=Berlin, New York | isbn=978-3-540-70996-1 | doi=10.1007/978-3-540-70997-8 |mr=2724440 | year=2010 | contribution = I.4 Three configurations of the affine plane and what has happened to them: Pappus, Desargues, and Perles | pages = 17–23}}
• {{citation

| last1 = Cardinal | first1 = Jean

| last2 = Hoffmann | first2 = Udo

| doi = 10.1007/s00454-016-9831-1

| issue = 1

| journal = Discrete & Computational Geometry

| mr = 3589061

| pages = 164–178

| title = Recognition and complexity of point visibility graphs

| volume = 57

| year = 2017| arxiv = 1503.07082

}}

• {{citation

| last1 = Chaplick | first1 = Steven

| last2 = Fleszar | first2 = Krzysztof

| last3 = Lipp | first3 = Fabian

| last4 = Ravsky | first4 = Alexander

| last5 = Verbitsky | first5 = Oleg

| last6 = Wolff | first6 = Alexander

| doi = 10.7155/jgaa.00630

| issue = 6

| journal = Journal of Graph Algorithms and Applications

| mr = 4631653

| pages = 459–488

| title = The complexity of drawing graphs on few lines and few planes

| volume = 27

| year = 2023| arxiv = 1607.06444

}}

• {{citation

| last = Grace | first = Kevin

| doi = 10.1016/j.jctb.2020.09.011

| journal = Journal of Combinatorial Theory

| mr = 4155284

| pages = 286–363

| series = Series B

| title = The templates for some classes of quaternary matroids

| volume = 146

| year = 2021| arxiv = 1902.07136

}}

• {{citation

| last = Grünbaum | first = Branko | authorlink = Branko Grünbaum

| edition = Second

| isbn = 978-0-387-00424-2

| location = New York

| mr = 1976856

| pages = 93–95

| publisher = Springer-Verlag

| series = Graduate Texts in Mathematics

| title = Convex polytopes

| title-link = Convex Polytopes

| volume = 221

| year = 2003}}

• {{citation

| last1 = Iampolskaia | first1 = Anna V.

| last2 = Skorobogatov | first2 = Alexei N.

| last3 = Sorokin | first3 = Evgenii A.

| doi = 10.1109/18.476239

| issue = 6

| journal = IEEE Transactions on Information Theory

| pages = 1667–1671

| title = Formula for the number of [9,3] MDS codes

| volume = 41

| year = 1995}}; the Perles configuration is listed as the "type 11" overdetermined 9-point configuration

• {{citation

| last = Mac Lane | first = Saunders | author-link = Saunders Mac Lane

| doi = 10.2307/2371070

| issue = 1

| journal = American Journal of Mathematics

| jstor = 2371070

| mr = 1507146

| pages = 236–240

| title = Some interpretations of abstract linear dependence in terms of projective geometry

| volume = 58

| year = 1936}}

• {{citation

| last = Shitov | first = Yaroslav

| arxiv = 1712.03071

| doi = 10.1090/proc/16156

| issue = 2

| journal = Proceedings of the American Mathematical Society

| mr = 4520003

| pages = 489–499

| title = A separation between tropical matrix ranks

| volume = 151

| year = 2023}}

• {{citation

| last = Solymosi | first = József | author-link = József Solymosi

| arxiv = 2408.09370

| doi = 10.1137/24M1686851

| issue = 2

| journal = SIAM Journal on Discrete Mathematics

| mr = 4898682

| pages = 912–920

| title = On Perles' configuration

| volume = 39

| year = 2025}}

• {{citation

| last = Ziegler | first = Günter M. | author-link = Günter M. Ziegler

| doi = 10.1007/BF02985377

| issue = 3

| journal = The Mathematical Intelligencer

| mr = 2437198

| pages = 36–42

| title = Nonrational configurations, polytopes, and surfaces

| volume = 30

| year = 2008| arxiv = 0710.4453

}}

Category:Configurations (geometry)

Category:Polyhedral combinatorics