Automated Symmetric Constructions in Discrete Geometry
Bernardo Subercaseaux , Ethan Mackey , Long Qian and Marijn J. H. Heule · 2025
Read Automated Symmetric Constructions in Discrete Geometry by Bernardo Subercaseaux , Ethan Mackey , Long Qian and Marijn J. H. Heule (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00224.txt.
Introduction
Bernardo Subercaseaux and co-authors present a computer method for symmetric point sets in geometry, in a 2025 paper. Some classic puzzles ask for point sets that meet strict rules and are as large or small as a set type allows. Past computer searches used logic solvers but did not build in rotational symmetry.
Their method codes symmetry straight into the search, which cuts the variables to solve. A second local search tool then turns the abstract design into real points. The pair found new best sets for two known puzzles, one with twenty one points where twenty three was the prior best. Symmetry also makes the sets easier for people to read.
Catalog record
| CREATOR | Bernardo Subercaseaux , Ethan Mackey , Long Qian and Marijn J. H. Heule |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-00224
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Automated Symmetric Constructions in Discrete Geometry Bernardo Subercaseaux , Ethan Mackey , Long Qian and Marijn J. H. Heule Abstract . We present a computational methodology for obtaining rotationally symmetric sets of points satisfying discrete geometric constraints, and demonstrate its applicability by discovering new solutions to some well-known problems in combinatorial geometry. Our approach takes the usage of SAT solvers in discrete geometry further by directly embedding rotational symmetry into the combinatorial encoding of geometric configurations. Then, to realize concrete point sets corresponding to abstract designs provided by a SAT solver, we introduce a novel local-search realizability solver, which shows excellent practical performance despite the intrinsic ∃ ℝ \exists\mathbb{R} -completeness of the problem. Leveraging this combined approach, we provide symmetric extremal solutions to the Erdős-Szekeres problem, as well as a minimal odd-sized solution with 21 points for the everywhere-unbalanced-points problem, improving on the previously known 23-point configuration. The imposed symmetries yield more aesthetically appealing solutions, enhancing human interpretability, and simultaneously offer computational benefits by significantly reducing the number of variables required to encode discrete geometric problems. 1. Introduction Symmetric solutions to combinatorial problems present several benefits: they tend to be easier to grasp and generalize [ 6 , 27 ] , and can even be easier to compute since they have fewer degrees of freedom (i.e., optimization variables) [ 26 , 7 , 8 ] . In the words of Turing awardee Alan J. Perlis, “Symmetry is a complexity-reducing concept; seek it everywhere” [ 15 ] . Despite theese benefits, it can be hard to prove in advance that a given problem will have symmetric solutions. This is especially the case in Ramsey theory, where the existence of objects avoiding certain patterns is often proven by (pseudo)random constructions, or asymmetric inductive arguments. For example, Schur number k , a classic Ramsey-theoretical problem, asks for the largest integer n such that there exists a k -coloring of \{1,\ldots,n\} with no monocromatic solution to x+y=z , and the following palindromic 3 -coloring is optimal since S(3)=13 : {\color[rgb]{1,0,0}1}\;{\color[rgb]{0,0.6,0}2}\;{\color[rgb]{0,0.6,0}3}\;{\color[rgb]{1,0,0}4}\;{\color[rgb]{0,0,1}5}\;{\color[rgb]{0,0,1}6}\;{\color[rgb]{0,0.6,0}7}\;{\color[rgb]{0,0,1}8}\;{\color[rgb]{0,0,1}9}\;{\color[rgb]{1,0,0}10}\;{\color[rgb]{0,0.6,0}11}\;{\color[rgb]{0,0.6,0}12}\;{\color[rgb]{1,0,0}13}. Interestingly, for all known Schur numbers S(k) , there is an optimal coloring that is palindromic (symmetric w.r.t. i\mapsto n\!-\!i\!+\!1 ) [ 9 ] . However, this is not known to be true for all k . A comparable phenomenon has been observed for van der Waerden numbers [ 8 ] . In this article we show that a similar situation seems to occur in certain discrete geometry problems, and that such symmetric solutions can be found automatically . We will consider two problems in discrete geometry described below. (a) Asymmetric construction of 16 points in general position without a convex 6 -gon [ 28 ] . (b) 4-fold symmetric construction that minimizes the number of convex pentagons [ 21 ] . (c) A 12-point 2-EU configuration with a 3-fold symmetry [ 2 ] . Lines connect collinear points. Figure 1 . Examples of geometric constructions with and without symmetry. Erdős-Szekeres. For each integer k\geq 3 , the problem is to find g(k) , the smallest integer such that any set of g(k) points in the plane, without three on a common line, contains k points in convex position. This long-standing problem dates back to the 1930s, with Klein’s proof of g(4)=5 , popularly known as the happy-ending theorem . The only further values known are g(5)=9 and g(6)=17 [ 23 ] . Erdős and Szekeres conjectured that g(k)=2^{k-2}+1 for every k , which matches the three known datapoints, and proved this to be a lower bound [ 14 ] . The Erdős-Szekeres upper-bound construction is however asymmetric and hard to visualize even for small values of k . For example, an asymmetric construction of showing g(6)>16 , currently in the Wikipedia page of the Happy Ending problem [ 28 ] , is shown in Figure 1(a) . In contrast, our symmetric constructions are presented in Section 6 ( Figure 4 ). Interestingly, Subercaseaux et al. [ 21 ] provided a symmetric construction for minimizing the number of convex pentagons amongst n points, and both the work of Morris and Soltan [ 14 ] as well as Scheucher [ 18 ] exhibited symmetric (or almost symmetric) extremal constructions for variants of the Erdős-Szekeres problem. In this work, we present a much more systematic approach to symmetry in discrete geometry. Everywhere-unbalanced-points. Given a set S of n points in the plane, we denote by L(S) the set of lines that touch at least two points of S . The “imbalance” \Delta(\ell) of a line \ell\in L(S) is the difference between the number of points that are on one side of \ell and the number of points on the other side. We say that S is k -everywhere-unbalanced ( k -EU, for short) if \Delta(\ell)\geq k for all lines \ell\in L(S) . The main open problem is whether k -EU sets exist for all k . This question can be traced back to Kupitz, who asked whether a 2 -EU pointset exists [ 12 ] . Alon answered affirmatively (see Figure 1(c) ), showing that 2 -EU sets with 4s points exist for every odd value of s\geq 3 , and his construction has an s -fold rotational symmetry [ 2 ] . Pinchasi proved that k -EU sets, if they exist, must have \Omega(2^{2^{k}}) points [ 16 ] , and recently Conlon and Lim showed an almost-matching upper bound when considering pseudolines instead of lines [ 4 ] . It is still open, however, whether a k -EU set exists for any k\geq 3 . 1.1. Our contributions and methodology We present a computational methodology for obtaining rotationally symmetric constructions for discrete geometric problems, which we apply to the aforementioned problems as well as other variants, e.g., 9 points in general position without an empty convex 5 -gon. The methodology consists of two stages: Symmetric combinatorial encoding: We first encode the geometric properties of the problems as instances of boolean satisfiability (SAT), following a recent line of work. We impose rotational symmetry in the encoding itself, which was initially explored by one of the authors [ 13 ] . To do this efficiently, we prove that the axioms of Knuth’s CC systems [ 11 ] can be encoded with O(n^{4}) many clauses without assuming a left-to-right ordering of the points as in previous work [ 10 ] . For the everywhere-unbalanced-points problem, we use SAT for the first time and prove, for instance, that Alon’s 12 -point construction uses the minimum number of points for a 2 -EU set. Realizability: Going from the solutions to the SAT instances to actual pointsets turns out to be harder, both in theory and in practice. To tackle this we developed Localizer , a local-search solver for the \exists\mathbb{R} -complete realizability problem, and through an experimental evaluation show it is highly performant compared to the general-purpose local-search formulation used in previous work [ 21 ] . Our solver does not handle collinear points, and thus to realize solutions of the everywhere-unbalanced-points problem (which necessarily involves collinearity), we use a different ad-hoc approach. We show symmetric solutions for the Erdős-Szekeres problem on 16 points without convex 6 -gons, and furthermore we enumerate and classify them, showing that s -fold symmetric