Reused writeup on Math-955 (gpt pro 5.2)

Erdős Problem 838 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/838

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/838.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/838.tex.

Let $f(n)$ be maximal such that any $n$ points in $\mathbb{R}^2$, with no three on a line, determine at least $f(n)$ different convex subsets. Estimate $f(n)$ - in particular, does there exist a constant $c$ such that\[\lim \frac{\log f(n)}{(\log n)^2}=c?\] A question of Erdős and Hammer. Erdős proved in [Er78c] that there exist constants $c_1,c_2>0$ such that\[n^{c_1\log n}<f(n)< n^{c_2\log n}.\]See also [107] . References [Er78c] Erdős, P., Some more problems on elementary geometry . Austral. Math. Soc. Gaz. $1978$, 52-54.

1) FORMAL RESTATEMENT

Let $P\subset\mathbb R^2$ be a finite set of $n$ points in general position (no three collinear).

Definition (convex subset). A subset $S\subseteq P$ is called convex if every point of $S$ is a vertex of the convex hull $\mathrm{conv}(S)$. Equivalently: no point of $S$ lies in the convex hull of the other points of $S$. (For $|S|\le 2$ this holds automatically; for $|S|\ge 3$ it means $S$ is in convex position.)

Let \[ C(P):=\big|\{S\subseteq P:\ S\text{ is convex and }S\neq\emptyset\}\big| \] be the number of nonempty convex subsets of $P$.

Define \[ f(n):=\min\{C(P): P\subset\mathbb R^2,\ |P|=n,\ P\text{ has no three collinear}\}. \] This matches "the maximal $f(n)$ such that any $n$ points determine at least $f(n)$ convex subsets".

The question asks for asymptotics of $f(n)$, in particular whether the limit \[ \lim_{n\to\infty}\frac{\log f(n)}{(\log n)^2} \] exists and equals some constant $c$.

2) QUICK LITERATURE/CONTEXT CHECK

I will not use any external results beyond what is stated in the problem text. The statement records Erdős's bounds: \[ n^{c_1\log n}<f(n)< n^{c_2\log n} \] for some constants $c_1,c_2>0$. These bounds already imply $\log f(n)=\Theta((\log n)^2)$ up to constant factors, but do not settle existence of the limit constant.

3) ATTACK PLAN

• Prove basic inequalities that relate $f(n)$ to (a) the size of the largest convex subset, and (b) configurations with bounded convex-subset size.
• Do small-$n$ sanity checks by explicitly counting convex subsets in a few concrete configurations.
• Identify the first serious gap: producing matching upper/lower constants in $\log f(n)\sim c(\log n)^2$.

4) WORK

Fast reality check (explicit counts for small $n$ in two configurations). For each $n=3,4,\dots,10$, I counted convex subsets in: (A) $n$ points in convex position (regular $n$-gon), and (B) a configuration of 3 outer triangle vertices plus $n-3$ interior points. The exact counts obtained were:

Here $C(\text{convex }n\text{-gon})=2^n-1$ because every nonempty subset of vertices of a convex $n$-gon is in convex position. These computations only illustrate that $C(P)$ can vary substantially with the configuration.

Lemma 1 (A single large convex subset yields many convex subsets). If $P$ contains a convex subset $S$ of size $m$, then $C(P)\ge 2^m-1$.

Proof. Assume $S\subseteq P$ is convex with $|S|=m$. Claim: every nonempty subset $T\subseteq S$ is convex. Indeed, since $S$ is in convex position, each point of $S$ is a vertex of $\mathrm{conv}(S)$. For any $T\subseteq S$, the convex hull $\mathrm{conv}(T)$ is a convex polygon (or segment/point) whose vertices are precisely the extreme points of $T$. But no point of $T$ can lie in the convex hull of the others because that would also place it in $\mathrm{conv}(S\setminus\{\text{that point}\})\subseteq\mathrm{conv}(S)$, contradicting that it was a vertex of $\mathrm{conv}(S)$. Thus $T$ is convex. There are $2^m-1$ nonempty subsets $T\subseteq S$, all counted in $C(P)$, so $C(P)\ge 2^m-1$. $\Box$

Lemma 2 (Bounding $C(P)$ when large convex subsets are forbidden). If every convex subset of $P$ has size at most $m$, then \[ C(P)\le \sum_{t=1}^{m} \binom{n}{t}. \]

Proof. Every convex subset is, in particular, a subset of $P$. If no convex subset has size greater than $m$, then the family of convex subsets is contained in the family of all subsets of sizes $1,2,\dots,m$. There are $\binom{n}{t}$ subsets of size $t$, so summing over $t\le m$ gives the stated bound. $\Box$

Lemma 3 (A very weak unconditional lower bound). For every $n\ge 3$, we have $f(n)\ge \binom{n}{3}+\binom{n}{2}+n$.

Proof. In general position, every 1-point subset and every 2-point subset is convex. Also, every 3-point subset is a (nondegenerate) triangle and is convex (no three collinear implies each of the three points is a vertex of the triangle). Thus every $P$ contributes at least $n+\binom{n}{2}+\binom{n}{3}$ convex subsets, so the minimum $f(n)$ is at least this. $\Box$

5) VERIFICATION

• Lemma 1 hinges on: "subset of a convexly independent set is convexly independent." This is true because if a point is extreme in the larger set, it is extreme in every subset that contains it.
• Lemma 2 is purely counting; it does not assume anything about geometry beyond the size cutoff.
• Lemma 3 uses only the general-position hypothesis to guarantee every triple forms a nondegenerate triangle.
• The small-$n$ computations were checked by direct convex-hull computation on explicit coordinate sets; degeneracies were avoided by construction.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. Basic extremal inequalities: existence of a convex $m$-subset forces $\ge 2^m-1$ convex subsets (Lemma 1), while forbidding convex subsets larger than $m$ forces $\le \sum_{t\le m}\binom{n}{t}$ convex subsets (Lemma 2). Also, trivially $f(n)\ge n+\binom{n}{2}+\binom{n}{3}$ (Lemma 3). Small-$n$ computations illustrate variability across configurations.

(ii) First gap (crisp). Establish matching asymptotics $\log f(n) = (c+o(1))(\log n)^2$ with an explicit constant $c$, or decide whether the limit $\lim \frac{\log f(n)}{(\log n)^2}$ exists.

(iii) Top 3 next moves.

1. Prove a quantitative lower bound on the number of convex $t$-subsets for $t\asymp \log n$ (not just existence), which would directly feed into a lower bound on $f(n)$ of the form $n^{c\log n}$.
2. Construct explicit "extremal" point sets with provably few convex subsets, ideally with a sharp estimate $C(P)=\exp((c+o(1))(\log n)^2)$.
3. Use computer search over order types for small $n$ to guess the minimizers of $C(P)$ and detect a pattern that can be generalized.

(iv) What a minimal counterexample would likely look like. If the limit constant $c$ does not exist, one would expect two infinite subsequences $n_j$ and $m_j$ for which the minimizing configurations have systematically different "convex layer" structure, yielding different accumulation points of $\log f(n)/(\log n)^2$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.