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)

Statement

Let $f(n)$ be the largest integer such that every set of $n$ points in the plane in general position (no three collinear) contains at least $f(n)$ distinct convex subsets — i.e. $f(n) = \min_{P}\,\#\{S\subseteq P : |S|\ge 3,\ S \text{ in convex position}\}$, the minimum, over all $n$-point configurations $P$, of the number of distinct subsets of $P$ whose points form the vertices of a convex polygon. Determine or estimate $f(n)$; in particular, does there exist a constant $c$ such that $$\lim_{n\to\infty}\frac{\log f(n)}{(\log n)^2}=c\ ?$$

This is a question of Erdős and Hammer, first posed in Erdős, "Some more problems on elementary geometry," *Austral. Math. Soc. Gaz.* 5 (1978), 52–54 [Er78c] (erdosproblems.com/838, citing only [Er78c]; "See also Erdős #107 — exact Erdős–Szekeres convex-polygon constant").

Facts

- Current status: OPEN. erdosproblems.com/838 (fetched directly 2026-07-02): "This is open, and cannot be resolved with a finite computation." No partial or complete solution is claimed anywhere in the record (3 forum comments, none containing a solution). - What is actually open is narrow and precise: not the growth *order* of $f(n)$, but the exact value of the limiting constant $c = \lim \log f(n)/(\log n)^2$ — i.e. whether $f(n)$'s quasi-polynomial exponent, as a function of $\log n$, converges to a fixed multiple of $\log n$ or merely oscillates between two different multiples. Erdős states this exact open question, word for word, immediately after proving the theorem below, in the same 1978 paper: *"Probably there is a constant $c$ so that $\lim_{n=\infty}\log f(n)/(\log n)^2=c$."* - What is SOLVED (fully proved, with a complete elementary proof, by Erdős himself in [Er78c]): there exist constants $c_1,c_2>0$ with $$n^{c_1\log n} < f(n) < n^{c_2\log n}. \tag{2}$$ This pins down that $f(n)$ grows quasi-polynomially — faster than any polynomial $n^k$, but slower than $\exp(n^{\epsilon})$ for any $\epsilon>0$ — a complete, two-sided, published theorem, not merely a claim. - The bound (2) is proved using, as a black box, the classical Erdős–Klein–Szekeres "happy ending" theorem Erdős #107 — exact Erdős–Szekeres convex-polygon constant: writing $m_k$ for the least integer forcing $k$ points in convex position among any $m_k$ points in general position, Erdős and Szekeres proved $$2^{k-2}+1 \le m_k \le \binom{2k-4}{k-2}+1. \tag{3}$$ Both directions of (2) are derived from (3) — the *lower*-bound side of (3) (an explicit $2^{k-2}$-point construction with no convex $k$-gon) drives the *upper* bound on $f(n)$; the *upper*-bound side of (3) (every set of $\gtrsim 4^k$ points contains a convex $k$-gon) drives the *lower* bound on $f(n)$, via double counting. See Solution below for the full argument. - Erdős immediately notes a companion, still less understood, quantity in the same paper: $h(n)$, the minimum number of empty convex subsets (convex subsets containing no other point of $P$ in their interior) forced in any $n$-point set — for which he states "I have no satisfactory bounds." This is a distinct counting question from Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7) (which asks only for the *existence* of one empty convex $k$-gon, for fixed $k$, not the *count* of all empty convex subsets of any size) and does not appear to have its own erdosproblems.com entry (checked #839, #840 — unrelated, different topics). - Independent secondary corroboration of the same two-sided bound, in the notation $s(r)$ instead of $f(n)$: W. Morris and V. Soltan, "The Erdős–Szekeres problem on points in convex position — a survey," *Bull. Amer. Math. Soc.* 37 (2000), 437–458 — indexed summary confirms "Erdős proves that there exist constants $a$ and $b$ so that $r^{a\log r} < s(r) < r^{b\log r}$" (full-text PDF was not independently retrievable; this is a secondary-source cross-check on the statement only, not the proof). - No newer literature, arXiv preprint, or improvement to $c_1,c_2$ (or resolution of the $c$-limit question) was found in a 2026-07-02 web search; the problem appears to remain exactly where Erdős left it in 1978.

Solution

*(of the proven sub-result (2) — the precise limiting constant in the Statement above remains open)*

Answer

$f(n) = n^{\Theta(\log n)}$, i.e. $f(n)$ lies between two quasi-polynomial bounds $n^{c_1\log n}$ and $n^{c_2\log n}$ for absolute constants $c_1,c_2>0$ — proved in full by Erdős, 1978 [Er78c].

The transferable technique — reduce a "count the distinct copies of structure X" question to a Ramsey/extremal theorem used as a black box, via matching constructions (upper bound) and double counting (lower bound):

1. Upper bound (construction side): plug an extremal Ramsey construction directly in as the counting instance. To *upper*-bound $f(n)$ (i.e. to exhibit one bad $n$-point configuration with few convex subsets), take the explicit Erdős–Szekeres extremal point set achieving the left side of (3): a set of $n=2^{k-2}$ points in general position containing no convex subset of more than $t=\lfloor\log_2 n\rfloor+1$ points. Since every convex subset this configuration has has size $\le t$, the total count is bounded by summing binomial coefficients up to size $t$: $$f(n) \;\le\; \sum_{i=0}^{t}\binom{n}{i} \;<\; n^{c_2\log n}.$$ The general lesson: if you already have an extremal construction proving a Ramsey-type theorem is tight (here, a large point set with a provably small maximum convex subset), it can usually be *reused directly* as the extremal instance for a "count distinct copies" question about the same structure, with essentially no extra work.

2. Lower bound (the harder, more transferable direction): double count incidences between medium-size random subsets and the small structure the Ramsey theorem guarantees inside each of them. Let $x_1,\dots,x_n$ be *any* $n$ points, and set $T=\lfloor\sqrt n\rfloor$. By the *upper*-bound side of (3), every subset of size $T$ contains a convex subset of size $r$ where $r > \log T/\log 4 \ge (\log n)/4$ — i.e. the Erdős–Szekeres theorem, applied as a black box to each $T$-subset individually, forces at least one convex $r$-subset inside it. Now double count the incidence set $\{(S,R) : S \text{ a } T\text{-subset},\, R\subseteq S \text{ a convex } r\text{-subset "found" inside } S\}$: - Counted by $T$-subsets: there are $\binom{n}{T}$ subsets $S$, each contributing $\ge 1$ pair, so the incidence count is $\ge \binom{n}{T}$. - Counted by convex $r$-subsets: a fixed convex $r$-subset $R=\{x_{i_1},\dots,x_{i_r}\}$ can be "found inside" at most $\binom{n-r}{T-r}$ different $T$-subsets $S\supseteq R$ (crudely: that's how many $T$-subsets contain $R$ at all). - Equating: (number of distinct convex $r$-subsets) $\times\binom{n-r}{T-r} \ge \binom{n}{T}$, so $$f(n) \;>\; \binom{n}{T}\Big/\binom{n-r}{T-r} \;>\; \left(\frac nT\right)^r \;>\; n^{c_1\log n}.$$ The general lesson — a reusable template well beyond this problem: **whenever a Ramsey/extremal theorem guarantees "every $m$-subset contains a copy of small structure $X$," double-counting the (subset, copy-of-$X$) incidence pairs — one side counted by subsets (a large binomial), the other by how many subsets can "contain" any single copy of $X$ (a smaller binomial) — forces the number of *distinct* copies of $X$ in the whole set to be large. This is a supersaturation-style argument built entirely from elementary double counting, using the Ramsey theorem only as a black box (no re-proof of Erdős–Szekeres is needed); it transfers immediately to any other "minimum number of distinct forced substructures" question for which a matching Ramsey/extremal theorem is already known. 3. Why the precise constant remains open.** Both directions above lose polynomial-in-the-exponent slack: the construction step (1) uses the extremal Erdős–Szekeres *lower* bound (tight, by Szekeres's still-unproven conjecture that (3)'s left inequality is exact — see Erdős #107 — exact Erdős–Szekeres convex-polygon constant), while the counting step (2) uses only the (weaker, unimproved-since-1935-in-base) *upper* bound side of (3). Since #107 itself is only resolved up to $2^{n+o(n)}$ (Suk 2017, Holmsen–Mojarrad–Pach–Tardos 2020 — see Erdős #107 — exact Erdős–Szekeres convex-polygon constant) rather than exactly $2^{n-2}+1$, any future sharpening of #107's exact constant would directly propagate into a sharpening of $c_1,c_2$ here — but even a fully resolved #107 would only pin down $c_1,c_2$ individually, not automatically establish that $\log f(n)/(\log n)^2$ *converges* to a single limit $c$ (the actual content of the still-open #838 question) rather than merely staying bounded between two constants forever.

Related

- Erdős #107 — exact Erdős–Szekeres convex-polygon constant — the Erdős–Klein–Szekeres "happy ending" theorem (3), $2^{k-2}+1\le m_k\le\binom{2k-4}{k-2}+1$, used as the black-box Ramsey theorem on both sides of the proof of (2) above (construction for the upper bound, incidence-counting target for the lower bound); itself still open in its exact form, so any future improvement there feeds directly into #838's constants $c_1,c_2$. - Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7) — the "empty convex hexagon" sibling problem (fully solved: $g(6)=30$, Heule–Scheucher 2024/Subercaseaux et al. 2024, building on Nicolás 2007/Gerken 2008/Horton 1983); a different quantity from #838's own unresolved "empty convex subset count" variant $h(n)$ (stated by Erdős in the same 1978 paper, no satisfactory bounds given, and apparently never separately catalogued), but the closest fully-cracked relative in the same "convex/empty-convex subset counting" family, and a template for what a full resolution of a sibling counting question can look like. - Additive-energy / pigeonhole averaging identity — $\sum_n r_A(n)=|A|^2$ forces large representation values on the dense side — a structurally similar "count two ways, equate" double-counting engine (representation-function identities forcing large values via averaging), useful as a comparison case for how elementary double-counting arguments are typically packaged in this wiki, though the concrete mechanism there (summing a representation function) differs from the incidence double-count used here.