gpt 6 astra ultra attempt on Math-294

Erdös-Szekeres conjecture

Definitions and mathematical statement

A planar point set is in general position when no three points are collinear. A subset is in convex position when every one of its points is a vertex of its convex hull. Let $\operatorname{ES}(n)$ be the least $N$ such that every $N$-point general-position set contains an $n$-point subset in convex position. The conjecture is \[ \operatorname{ES}(n)=2^{n-2}+1\qquad(n\ge3). \] The selected polygon need not be empty of other points of the original set. Both the universal guarantee at this threshold and sharpness immediately below it are involved in the exact value; an asymptotic exponent alone is weaker.

Formulation and concept references: [S1].

Short English statement

Is $2^{n-2}+1$ the exact number of general-position planar points needed to force $n$ of them into convex position?

Research attempt

Scope and literature check.

This attempt was prepared by GPT-6 Astra Ultra on 27 September 2026. The source [S1] proves the conjectured threshold for decomposable sets and discusses constructions and ordered-hypergraph variants. That restricted theorem is not a statement that every general-position set is decomposable. The selected polygon need not be empty. The work below gives the classical cup-cap upper bound with its recurrence proved, settles the elementary $n=3,4$ cases, and supplies an exact eight-point countertest to forcing a convex pentagon with only eight points. It does not claim the full exponential threshold for arbitrary $n$.

By a small rotation, any finite general-position set can be arranged to have distinct horizontal coordinates. This preserves all orientation signs and convex-position subsets. Order points by that coordinate. A $k$-cup is a sequence of $k$ points whose consecutive slopes strictly increase; a $k$-cap has strictly decreasing consecutive slopes. Every such sequence is in convex position: its edges form a strictly convex lower, respectively upper, chain, closed by the segment joining the endpoints. The strict inequalities follow from no three points being collinear.

The cup-cap recurrence, with the extension step explicit.

Let $f(k,l)$ be the maximum size of an ordered general-position point set having neither a $k$-cup nor an $l$-cap, for $k,l\ge2$. For $k=2$ or $l=2$, any two points give the forbidden two-point chain, so $f(2,l)=f(k,2)=1$. For $k,l\ge3$, partition a set $P$ with neither forbidden chain into $A$, the endpoints of $(k-1)$-cups, and $B=P\setminus A$. The set $B$ contains no $(k-1)$-cup, so $|B|\le f(k-1,l)$.

We claim $A$ contains no $(l-1)$-cap. If $q_1,\ldots,q_{l-1}$ were such a cap, choose a $(k-1)$-cup ending at $q_1$ and let $p$ be its penultimate point. If the slope $pq_1$ were less than the slope $q_1q_2$, appending $q_2$ would create a $k$-cup. Equality is ruled out by general position. Thus the slope $pq_1$ is greater, and $p,q_1,q_2,\ldots,q_{l-1}$ is an $l$-cap, a contradiction. Also $A$ contains no $k$-cup because $P$ does not. Therefore \[ f(k,l)\le f(k-1,l)+f(k,l-1). \tag{1} \] Pascal's recurrence with the boundary values proves \[ f(k,l)\le\binom{k+l-4}{k-2}. \tag{2} \] In particular every set of $\binom{2n-4}{n-2}+1$ points has an $n$-cup or an $n$-cap, and hence \[ \operatorname{ES}(n)\le\binom{2n-4}{n-2}+1. \tag{3} \] This establishes a universal finite upper bound with an actual extension argument, rather than appealing to a vague Ramsey principle.

The cup-cap bound is sharp for its stronger forcing target.

The recurrence also has a matching construction. Suppose $P_1$ avoids a $(k-1)$-cup and an $l$-cap, and $P_2$ avoids a $k$-cup and an $(l-1)$-cap. Put a sufficiently small affine copy of $P_1$ to the left of a sufficiently small affine copy of $P_2$, with the second copy raised high enough that every joining slope from $P_1$ to $P_2$ is larger than every slope internal to either copy. This can be achieved by first fixing the copies in disjoint narrow horizontal intervals, shrinking their vertical spreads, and then increasing their vertical separation. A generic small perturbation avoids mixed collinear triples while retaining the strict inequalities.

A cup using both copies has at most one point in $P_2$, because a joining slope followed by an internal slope in $P_2$ would decrease. Its portion in $P_1$ has at most $k-2$ points, so it has fewer than $k$ points. A cap using both has at most one point in $P_1$, and its portion in $P_2$ has at most $l-2$ points, so it has fewer than $l$ points. The copies individually avoid the larger forbidden chains as well. Starting with the one-point boundary examples constructs \[ f(k,l)=\binom{k+l-4}{k-2}. \tag{4} \] The construction may be made rational, since it uses finitely many strict polynomial inequalities and rational points are dense.

Equation $4$ is not the conjectured value of $\operatorname{ES}(n)$. A convex polygon generally consists of both an upper chain and a lower chain between its extreme horizontal vertices; it need not be a cup or cap of all its vertices. Thus avoiding an $n$-cup and an $n$-cap does not imply avoiding every convex $n$-gon. Treating $4$ as a lower bound matching $3$ for the polygon problem would change the target.

The elementary exact cases.

Three general-position points are a triangle, so $\operatorname{ES}(3)=3$. For $n=4$, a triangle together with one point strictly inside it is a four-point set with no convex quadrilateral. It remains to prove that five points always suffice.

If their convex hull has at least four vertices, choose four hull vertices. Otherwise the hull is a triangle $ABC$, with two interior points $P,Q$. The segments from $P$ to the vertices partition the triangle into three smaller triangles. Relabel so that $Q$ lies strictly inside $ABP$; general position prevents it from lying on one of the three partition segments. The segment $CQ$ enters $ABP$ through either $AP$ or $BP$. It cannot enter through $AB$, since $C$ and $Q$ lie on the same side of the line $AB$. It cannot pass through an endpoint, by general position. If it crosses $AP$, the segments $CQ$ and $AP$ cross in their interiors, so $A,C,P,Q$ form a convex quadrilateral with those diagonals. If it crosses $BP$, use $B,C,P,Q$ instead. Therefore \[ \operatorname{ES}(4)=5. \tag{5} \] Other points may lie inside the selected quadrilateral, which is permitted by the original question.

A finite lower example at the next parameter.

Consider the eight integer points \[ (1,7),\ (4,5),\ (6,1),\ (6,2),\ (7,6),\ (8,5),\ (11,3),\ (13,2). \tag{6} \] The accompanying exact script checks all $\binom83=56$ determinants \[ \det\begin{pmatrix}b_1-a_1&b_2-a_2\\c_1-a_1&c_2-a_2\end{pmatrix} \] and finds none zero. It then checks all $\binom85=56$ five-point subsets by the monotone-chain convex-hull algorithm, using integer orientation signs, and finds no hull with five vertices. Thus $6$ is a reproducible certificate that $\operatorname{ES}(5)\ge9$. The proof of the certificate is finite exhaustive arithmetic, not a picture judged by eye or a floating-point angle test.

To reproduce the hull test, sort a subset lexicographically; append points in order to a lower chain, deleting the penultimate point whenever the last three have nonpositive cross product. Repeat in reverse order for the upper chain and join them without repeating the endpoints. For a general-position set this returns exactly its convex-hull vertices. A subset is in convex position exactly when the returned vertex count equals its cardinality. The original random search only discovered the coordinates; exhaustive verification of this fixed output is the certificate.

This example alone proves no nine-point upper bound and no formula for larger $n$. The established literature gives stronger small-case and general lower results than are independently reproved here. We do not confuse the limits of this finite check with the limits of what is known in [S1] and its references.

Why the recurrence does not yield the conjectured exponent.

The central binomial coefficient in $3$ has order $4^{n-2}/\sqrt n$, whereas the conjecture asks for essentially $2^{n-2}$. The endpoint partition remembers only whether a cup of a certain length ends at a point. It discards the interaction between upper and lower chains, even though that interaction creates convex polygons which are neither whole cups nor whole caps.

A proof improving $3$ to the conjectured threshold must exploit this lost information. Simply solving the same recurrence more accurately cannot do so, because $4$ shows the recurrence is already sharp for its own cup-cap avoidance problem. Likewise a disproof in a larger class of ordered hypergraphs, as discussed in [S1], need not be geometrically realizable by planar points with their orientation signs. Realizability is an additional requirement, not an automatic consequence of a combinatorial coloring.

Verification and final status.

The recurrence proof checks the endpoint extension and both boundary parameters. The construction checks every possible transition between the two clusters. The finite script checks $6$ by integer determinants and all five-subsets, and verifies the numerical Pascal recurrence. No general-position assumption is inferred from rounded coordinates.

UNRESOLVED. The checked results are $3$--$5$ and the explicit eight-point lower example. The first missing step is a universal bound on the combined upper/lower-chain structure at the conjectured number of points. Concrete next targets are a state refinement of the endpoint partition that retains both chains, a proof extending decomposable-set arguments to arbitrary configurations, or a realizable orientation certificate contradicting the threshold. None is supplied here.

Sources

• S1 Baek and Balko, The Erdos-Szekeres Conjecture Revisited (SoCG 2025). https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.13. Formulation source.