we-solve (beta)

Math-5430-A3 · revision r1 · on Math-5430

gpt pro 5.2 attempt on Math-5430

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #107
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. Lemma 107.1 (the case $n=4$: $f(4)=5$).
  7. Lemma 107.2 (monotonicity and trivial bounds).
  8. 5) VERIFICATION (FAST REALITY CHECK)
  9. 6) FINAL

Erdős Problem #107

1) FORMAL RESTATEMENT

For an integer $n\ge3$, let $f(n)$ be the least integer $N$ such that every set $P\subset\mathbb R^2$ of $N$ points with no three collinear contains $n$ points in convex position, i.e. $n$ points that are the vertices of a convex $n$-gon (equivalently, no one of the $n$ points lies in the convex hull of the other $n-1$).

The conjectured exact value is \[ f(n)=2^{n-2}+1\quad(n\ge3). \]

2) QUICK LITERATURE/CONTEXT CHECK

I only record what the problem text states:
  • Erdős--Szekeres proved the bounds $2^{n-2}+1\le f(n)\le \binom{2n-4}{n-2}+1$.
  • Several improvements exist; the best stated bound is $f(n)\le 2^{n+O(\sqrt{n\log n})}$.
No other results are assumed/proved here.

3) ATTACK PLAN

  • Proof track (full conjecture): show every set of $2^{n-2}+1$ points contains a convex $n$-gon, likely via a sharp recursion or a refined partial-order argument.
  • Disproof track: exhibit, for some $n$, a configuration of $2^{n-2}+1$ points with no convex $n$-gon.
In this writeup I give a complete proof of the base case $f(4)=5$ and basic structural lemmas, but I do not resolve the general conjecture.

4) WORK

Lemma 107.1 (the case $n=4$: $f(4)=5$).
One has $f(4)=5$.

Proof. Lower bound $f(4)\ge5$. There exists a $4$-point set with no convex quadrilateral: take three vertices of a triangle and a fourth point strictly inside that triangle. Any four-point subset is the whole set, and one point lies in the convex hull of the other three, so there is no convex $4$-gon. Thus $f(4)\ge5$.

Upper bound $f(4)\le5$. Let $P$ be any set of $5$ points with no three collinear. Consider all triangles formed by triples of points in $P$, and choose a triangle $\triangle ABC$ of minimum (Euclidean) area.

Claim: no other point of $P$ lies strictly inside $\triangle ABC$. Indeed, if some point $D\in P$ lies inside $\triangle ABC$, then the three triangles $\triangle ABD$, $\triangle BCD$, $\triangle CAD$ form a partition of $\triangle ABC$ into three nondegenerate triangles. In particular, each of these triangles has area strictly smaller than $\triangle ABC$, contradicting the minimality of $\triangle ABC$.

Therefore, the remaining two points of $P\setminus\{A,B,C\}$ lie outside the triangle $\triangle ABC$. Hence the convex hull $\operatorname{conv}(P)$ cannot be a triangle (a triangular convex hull would contain all points in or on that triangle, with at least two points inside, contradicting the claim). Thus $\operatorname{conv}(P)$ has at least $4$ vertices, and those $4$ vertices form a convex quadrilateral.

So every $5$-point set contains a convex $4$-gon, i.e. $f(4)\le5$. Together with the lower bound, $f(4)=5$. $\square$

Lemma 107.2 (monotonicity and trivial bounds).
For $n\ge3$:
  1. $f(n+1)\ge f(n)$.
  2. $f(n)\ge n$.

Proof. $2$ is immediate since fewer than $n$ points cannot contain $n$ points in convex position.

For $1$: by definition, any set of $f(n+1)$ points in general position contains $n+1$ points in convex position. Removing any one of these $n+1$ vertices leaves $n$ points still in convex position. Hence any set of $f(n+1)$ points contains a convex $n$-gon, so $f(n)\le f(n+1)$, i.e. $f(n+1)\ge f(n)$. $\square$

5) VERIFICATION (FAST REALITY CHECK)

  • $f(3)=3$: any $3$ noncollinear points form a triangle.
  • Lemma 107.1 gives $f(4)=5$.
  • The conjecture predicts $f(5)=2^{3}+1=9$, consistent with the statement in the problem text that Turán and Makai proved $f(5)=9$.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. A complete proof that $f(4)=5$ (Lemma 107.1), plus basic monotonicity/trivial bounds (Lemma 107.2).

(ii) Exact first gap. Proving (or disproving) the general identity $f(n)=2^{n-2}+1$ for all $n\ge3$.

(iii) Top 3 next moves (concrete targets).

  1. Re-prove the general Erdős--Szekeres upper bound $f(n)\le \binom{2n-4}{n-2}+1$ in a fully self-contained way as a stepping stone.
  2. Attempt to sharpen the induction/recursion to match the lower bound $2^{n-2}+1$.
  3. Computationally search for extremal configurations for $n=6,7$ to test structure and potential stability.

(iv) Minimal counterexample structure. A disproof would require some $n$ and an explicit set of $2^{n-2}+1$ points in general position containing no convex $n$-gon; it would have to beat the classical Erdős--Szekeres construction of size $2^{n-2}$ without creating a convex $n$-tuple.