Erdős #651 — higher-dimensional Erdős–Szekeres convex-position numbers are subexponential for d≥3 (disproved)

Statement

For $k\ge2$, let $f_k(n)$ be the smallest integer such that any $f_k(n)$ points in general position in $\mathbb{R}^k$ contain $n$ points in convex position (i.e. which determine a convex polytope). Erdős asked [Er97e]: is it true that $$f_k(n) > (1+c_k)^n$$ for some constant $c_k>0$ — i.e. does the exponential-growth lower-bound behavior of the classical plane case ($k=2$) persist in every fixed dimension $k$? (erdosproblems.com/651, direct fetch.)

Facts

- Status: DISPROVED — solved in the negative, even for $k=3$ (erdosproblems.com/651). - Origin: [Er97e], Erdős's own 1997 problem list. - Trivial monotonicity noted on the site: $f_2(n) > f_3(n) > \cdots$ — adding an ambient dimension can only make it easier to find $n$ points in convex position, so $f_k(n)$ is non-increasing in $k$; the question was whether it still decays only *polynomially slower* than exponentially (i.e. stays exponential with a dimension-dependent rate $c_k$), not whether it decreases at all. - The $k=2$ case is the Erdős–Klein–Szekeres "Happy Ending" problem, Erdős #107 — exact Erdős–Szekeres convex-polygon constant — separately tracked, still open: conjectured $f_2(n)=2^{n-2}+1$; Erdős–Szekeres proved $2^{n-2}+1\le f_2(n)\le\binom{2n-4}{n-2}+1$; Suk (2017) nearly settled the exponential rate with $f_2(n)\le2^{(1+o(1))n}$; current best upper bound $f_2(n)\le2^{n+O(\sqrt{n\log n})}$ (Holmsen–Mojarrad–Pach–Tardos) (erdosproblems.com/107, direct fetch). - Resolving result: Cosmin Pohoata and Dmitrii Zakharov, "Convex polytopes from fewer points," arXiv:2208.04878 (2022), published *Duke Mathematical Journal* 174(3) (Feb 2025), DOI 10.1215/00127094-2024-0034, prove $$ES_d(n) = 2^{o(n)}\quad\text{for all }d\ge3,$$ where $ES_d(n)$ is exactly $f_d(n)$ in the notation above (arxiv.org/abs/2208.04878, direct fetch). In particular $f_3(n)\le2^{o(n)}$, which directly falsifies the $k=3$ instance of Erdős's question — no constant $c_3>0$ can make $f_3(n)>(1+c_3)^n$ hold, since $2^{o(n)}$ eventually undercuts *any* fixed exponential base $>1$. - Related sibling "convex position" family problems on the same site: Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7) — the *empty*-convex-polygon variant (also disproved, via Horton's 1983 construction showing $g(k)$ fails to exist for $k\ge7$), and Erdős #838 — f(n), the minimum number of distinct convex subsets of n points (open precise growth rate; two-sided quasi-polynomial bound SOLVED by Erdős 1978 via double counting against the Erdős–Szekeres theorem) (cross-linked from #107's "See also"). - A separate, complementary line of work gives exact/near-exact small values and computational lower bounds for the same function family via SAT solvers: Manfred Scheucher, "A SAT attack on higher dimensional Erdős–Szekeres numbers," arXiv:2105.08406, e.g. $g^{(3)}(7)=13$ — this is finite-case verification, orthogonal to and not competing with Pohoata–Zakharov's asymptotic $2^{o(n)}$ upper bound.

Solution

The disproof is an explicit subexponential upper-bound construction/argument, not a counterexample point set — Pohoata and Zakharov show that *for every fixed $d\ge3$*, $2^{o(n)}$ points in $\mathbb{R}^d$ in general position always suffice to force $n$ points in convex position, which is asymptotically far below any exponential lower bound $(1+c_d)^n$, killing Erdős's conjecture for every $k\ge3$ at once (arxiv.org/abs/2208.04878).

The transferable technique — "projection, 2-D positive-fraction argument, lift back": 1. Reduce the induction to the base case $d=3$. Because a convex point set in $\mathbb{R}^d$ can be built from convex substructure one dimension down, the paper's main engineering effort is proving $ES_3(n)=2^{o(n)}$; the bound for all higher $d\ge3$ follows by bootstrapping this 3-D case upward (arxiv.org/pdf/2208.04878, Theorem 1.1 → Theorem 1.2 structure). 2. Project $\mathbb{R}^3$ point sets down to $\mathbb{R}^2$ and run a *Suk-style* argument — the same "cups-and-caps"/positive-fraction Erdős–Szekeres machinery Suk used in 2017 to nearly settle the *planar* case ($f_2(n)\le2^{(1+o(1))n}$) — on the projected configuration (WebSearch-corroborated summary of the paper's method, cross-checked against arxiv.org/pdf/2208.04878's Horton-set / positive-fraction-ES content). 3. **The key extra ingredient is a Ramsey-type statement about points in space with *convexly ordered planar projections*** — i.e. a structural theorem guaranteeing that a large enough 3-D point set (in general position) contains a large sub-configuration whose projection to some 2-plane is *itself* in convex position in a controllable, ordered way. This is what lets the 2-D subexponential machinery be "lifted back" to certify genuine 3-D convex position, rather than merely planar convex position of a shadow. 4. Why dimension $\ge3$ breaks the classical exponential lower bound. The $2^{n-2}+1$ planar lower bound comes from an explicit exponentially-large point set (the Erdős–Szekeres construction, and separately Horton's construction for the empty-polygon variant Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7)) that is carefully built to *avoid* large convex subsets using strictly 2-D combinatorial structure (nested "caps" avoiding "cups", or Horton's recursive near-collinear layering). Both known planar extremal constructions rely on genuinely 2-dimensional degeneracy-avoidance that does not survive being embedded generically in one extra dimension — an added dimension gives too much room for *some* projection or sub-configuration to be forced into convex position, which is exactly what the projection-and-lift argument exploits algorithmically rather than just observing qualitatively. 5. Net effect — an exponential-vs-subexponential dimension gap. The result is a clean structural dichotomy: convex-position Ramsey numbers are governed by an essentially 2-dimensional-only exponential extremal phenomenon; the moment one more coordinate is available ($d\ge3$), the extremal behavior collapses to $2^{o(n)}$, uniformly in $d$.

Why this is the reusable part for downstream/open problems. The core transferable move — *find a lower-dimensional Ramsey/positive-fraction sub-statement, project down to invoke it, then use a "convexly-ordered-projection" structural lemma to lift the conclusion back up* — is a general template for showing higher-dimensional Ramsey-type geometric quantities collapse relative to their planar analogues. Any open problem asking whether a $\mathbb{R}^2$-calibrated extremal/Ramsey bound "persists" unchanged into $\mathbb{R}^d$, $d\ge3$, is a natural candidate for the same projection-plus-lift attack; the finite-case SAT/computational-lower-bound line (Scheucher, arXiv:2105.08406) is the complementary tool for checking whether small-$n$ exact values already hint at the same collapse before attempting the general asymptotic argument.

Related

- Erdős #107 — exact Erdős–Szekeres convex-polygon constant — the $k=2$ case (Erdős–Klein–Szekeres "Happy Ending" problem); still open; this page's $k=3$ disproof is precisely a statement that the plane's exponential lower-bound phenomenon does *not* generalize past $k=2$, making #107 the one genuinely exceptional dimension in this family. - Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7) — sibling disproved "empty convex polygon" problem in the plane (Horton's construction kills existence for $k\ge7$); same convex-position problem family, same site tag convex, same style of "explicit extremal construction/argument disproves an Erdős conjecture" resolution. - Pór–Valtr positive-fraction Erdős–Szekeres theorem: dense clusters, not just points, in convex position — Suk's 2-D technique that the Pohoata–Zakharov proof imports as its planar sub-argument after projecting down. - concept/horton-sets — the extremal near-collinear construction underlying the classical planar lower bounds (Erdős #107 — exact Erdős–Szekeres convex-polygon constant, Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7)) that the higher-dimensional argument shows cannot be replicated once $d\ge3$. - concept/dimension-reduction — the general "project, solve in lower dimension, lift back via a structural transfer lemma" technique family this page's Solution documents; the transferable engine for this problem and a candidate template for other Ramsey/extremal geometric quantities suspected to collapse in higher dimension. - SAT/CP-SAT-based finite counterexample search and verification — Scheucher's computational companion approach (arXiv:2105.08406) giving exact/near-exact small-$n$ values for the same $f_k(n)$ family, complementary to (not competing with) the asymptotic proof documented here.