Erdoes #838 - working report - Erdős Problem a Day

Erdős problem #838 — wave w048

Date: 2026-07-31 UTC

Claim labels

[a] elementary-rigorous: proved here by elementary finite geometry,

counting, or asymptotics.

[b] rigorous-modulo-named-theorem: the deduction is rigorous modulo the

named published theorem or construction.

[c] plausible/structural-unverified: a literature-search conclusion or

unproved structural assertion; it is not claimed as a theorem.

[d] computational-only/source-verified: an exact computation, a direct

source observation, or a result conditional on the cited database being complete.

0. Mandatory live-page gate

[d: source-verified] I fetched the live problem page, its LaTeX view, its dynamic bibliography, and the linked discussion thread through the Bright Data cloud browser on 2026-07-31. The direct body text and the LaTeX view agreed.

The exact current statement, copied verbatim from the live LaTeX view, is:

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?\]

The page's exact known-results text is:

A question of Erd\H{o}s and Hammer. Erd\H{o}s proved in \cite{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].

The dynamic bibliography entry is:

[Er78c] Erdős, P., Some more problems on elementary geometry. Austral. Math. Soc. Gaz. (1978), 52-54.

The live status/activity fields were:

| field | live value | |---|---:| | status | OPEN | | comments | 3 | | claimed proofs | 0 | | interested in collaborating | None | | currently working on this problem | None |

The three comments, all explicitly labeled by the site as unverified user content, are:

nsingh, 12:58 on 20 May 2026: claims that the classical

Erdős--Szekeres bound and double counting give an explicit lower exponent $1/8$, choosing $r=\frac14\log_2 n$. The rendered comment contains several missing exponents/typographical algebra errors, so I do not use its claimed no-$o(1)$ formulation.

Zeraoulia Rafik, 11:26 on 28 April 2026: uses Suk's

$ES(k)=2^{k+o(k)}$, a random $T=\lfloor n^\alpha\rfloor$-subset, and double counting/entropy to claim \[ \liminf_{n\to\infty} \frac{\log_2 f(n)}{(\log_2 n)^2}\ge\frac14. \] It also records the classical-construction upper value $1$, hence the base-2 interval $[1/4,1]$, and gives the corresponding natural-log interval.

Nat Sothanaphan, 17:07 on 28 April 2026, replies exactly:

“Thanks. Standard check believed this to be correct.”

There was therefore no claimed proof, solved/falsified flag, current worker, or collaboration marker. The mandatory stop rule did not apply.

1. Convention and baseline

The original source and the Morris--Soltan survey clarify that a “convex subset” means a subset of at least three points in convex position: every selected point is a vertex of the selected set's convex hull. I use $N$ for the number of points below, reserving other letters for construction parameters.

Adding the empty set, singletons, or pairs would add only $1+N+\binom N2$, which has no effect on the asymptotic problem, but the exact finite table in Section 4 uses the original $k\ge3$ convention.

Let $ES(r)$ be the least integer forcing $r$ points in convex position. The comment's current lower constant checks out:

[b: modulo Suk's theorem] Let $L=\log_2 N$, fix $0<\alpha<1$, put $T=\lfloor N^\alpha\rfloor$, and take

r=(\alpha-o(1))L

so that $ES(r)\le T$. Every $T$-subset contains a convex $r$-subset. Double-counting pairs $(R,C)$, with $|R|=T$, $|C|=r$, and $C\subset R$, gives

\#\{\text{convex }r\text{-subsets}\} \ge \frac{\binom NT}{\binom{N-r}{T-r}} =\frac{\binom Nr}{\binom Tr}.

Consequently

\log_2 f(N) \ge \bigl(\alpha(1-\alpha)-o(1)\bigr)L^2.

Optimizing at $\alpha=1/2$ proves

\liminf_{N\to\infty} \frac{\log_2 f(N)}{(\log_2 N)^2}\ge\frac14. \tag{1}

Suk's actual primary theorem is stronger than the asymptotic form needed here:

ES(r)\le 2^{r+6r^{2/3}\log_2 r}

for all sufficiently large $r$.

2. Primary-source and literature audit

[d] Original question. I downloaded and read

Erdős, Some more problems on elementary geometry (1978), SHA-256 bf252ec2e8310b33570d7b2c495d5f173e5f7527fcd8e05358456b3ed50e08d1. Page 52 states the Hammer question; page 53 proves the two $N^{c\log N}$ bounds from the then-current Erdős--Szekeres estimates and asks whether the displayed logarithmic limit exists.

[d] Construction used below. I downloaded and read

Erdős--Szekeres, On some extremum problems in elementary geometry (1960/61), SHA-256 17a3e46b311dd7098b40b2dff8d5e9d6aa950dfe0454d3f279338dd6edc6c818. Section 2 explicitly constructs the cup--cap sets and then a $2^{m}$-point set with no convex $(m+2)$-gon. The journal pagination is 53--62.

[d] Modern Erdős--Szekeres input. Andrew Suk's primary paper exists as

arXiv:1604.08657 and JAMS DOI 10.1090/jams/869. I checked Theorem 1.1 in the PDF (SHA-256 aedfe844afac6f993b6a1cca35696a3509bf68fef01f2f05a011bdcc3d89c74a); it states the bound quoted above and hence $ES(r)=2^{r+o(r)}$.

[d] Later survey/restatement. Morris and Soltan's

2000 survey, DOI 10.1090/S0273-0979-00-00877-6 identifies the same function (there called $s(r)$) as the minimum number of convex subsets “of any number $n\ge3$ of points” and repeats Erdős's bounds and limit question. Dumitrescu and Tóth's 2017 paper on convex polygons in triangulations mentions only the same $\exp(\Theta(\log^2 N))$ fact in its introduction.

[d] Finite data source. The

Aichholzer--Aurenhammer--Krasser order-type database supplies one integer realization of every reflection class of realizable planar order types through ten points. Its completeness/reliability methodology is described in the database readme and in DOI 10.1023/A:1021231927255.

I searched exact phrases from the question, the exact 1978 title, citations of that title, “minimum number of subsets in convex position,” and formula/constant variants. [c] I found the original paper, the 2000 survey, later restatements, the live 2026 comments, and extensive fixed-$k$ Erdős--Szekeres literature, but no primary source improving the total-subset upper constant or giving the exact table in Section 4. This is a search miss, not a proof of novelty or absence from the literature.

3. Main progress: an improved asymptotic upper constant

3.1 The recursive cup--cap pieces

[b: rigorous modulo the explicit Erdős--Szekeres construction] Let $P_{a,b}$ be the recursively constructed cup--cap set in the 1960/61 paper. It has

M_{a,b}:=|P_{a,b}|=\binom{a+b-2}{a-1}. \tag{2}

When $a,b>1$, it is a union $A\cup B$ of separated copies

A=P_{a,b-1}, \qquad B=P_{a-1,b}.

All points of $A$ lie to the left of all points of $B$; $B$ lies high above every line determined by two points of $A$, and $A$ lies below every line determined by two points of $B$.

Let:

$C_{a,b}$ count nonempty concave chains (caps) in $P_{a,b}$;
$U_{a,b}$ count nonempty convex chains (cups);
$F_{a,b}$ count nonempty subsets in convex position.

For a boundary parameter $a=1$ or $b=1$, all three counts are $1$. The separation gives the elementary recurrences/upper recurrences

\begin{aligned} C_{a,b} &\le C_{a,b-1}+(1+M_{a,b-1})C_{a-1,b},\\ U_{a,b} &\le (1+M_{a-1,b})U_{a,b-1}+U_{a-1,b},\\ F_{a,b} &\le F_{a,b-1}+F_{a-1,b} +U_{a,b-1}C_{a-1,b}. \end{aligned} \tag{3}

For example, a cap that uses $B$ can use at most one point of $A$; otherwise it lies entirely in $A$. A convex-position subset meeting both parts must use a cup in $A$ and a cap in $B$, since those are respectively the surviving lower and upper hull chains.

3.2 A product bound for the recurrences

Put $t=a+b-2$ and define

Q_t(s):=\prod_{r=1}^{s}\left(1+\binom tr\right), \qquad Q_t:=Q_t(t-1). \tag{4}

[a] Lemma.

C_{a,b}\le 2^tQ_t(a-1),\qquad U_{a,b}\le 2^tQ_t(b-1),\qquad F_{a,b}\le 2^{3t}Q_t. \tag{5}

Proof. Expand the first recurrence in (3) down its lattice paths. There are at most $2^t$ paths. A step that decreases the first coordinate from $(p,q)$ contributes

1+\binom{p+q-3}{p-1} \le 1+\binom t{p-1}.

Along one path each value $p-1\in\{1,\ldots,a-1\}$ occurs at most once. This proves the cap bound. Reflecting the recursion proves the cup bound.

For the third bound, induct on $t$. The two $F$-terms have parameter $t-1$. In the cross term, the cup product uses indices $1,\ldots,b-2$ in row $t-1$; by binomial symmetry these are the high indices $a-1,\ldots,t-2$. The cap product uses the disjoint low indices $1,\ldots,a-2$. Their product is therefore at most $Q_{t-1}$, and

U_{a,b-1}C_{a-1,b} \le 2^{2(t-1)}Q_{t-1}.

Together with the inductive bounds for the two $F$-terms, this is less than $2^{3t}Q_t$. $\square$

3.3 Count the final $2^m$-point construction

The final Erdős--Szekeres set $X_m$ is the separated union

X_m=\bigcup_{k=1}^{m+1}G_k, \qquad G_k=P_{k,m+2-k}, \qquad |G_k|=\binom m{k-1}, \tag{6}

so $|X_m|=2^m$.

The slope separation proved in the original construction has the following necessary consequence. If a convex-position subset meets groups $G_i$ and $G_j$, $i<j$, and no group outside that interval, then:

its $G_i$-part is a cap;
its $G_j$-part is a cup;
it uses at most one point from every intermediate group.

Thus the number with extreme groups $i<j$ is at most

C_{i,m+2-i}\, U_{j,m+2-j}\, \prod_{k=i+1}^{j-1}\left(1+\binom m{k-1}\right). \tag{7}

In (5), the cap contributes the product indices $1,\ldots,i-1$. After binomial symmetry, the cup contributes $j-1,\ldots,m-1$. The middle groups contribute $i,\ldots,j-2$. These ranges are disjoint and cover $1,\ldots,m-1$, so every term in (7) is at most

2^{2m}Q_m. \tag{8}

A subset contained in a single group contributes at most $2^{3m}Q_m$ by (5). There are at most $(m+1)^2$ choices of one group or an ordered extreme pair. Hence the following explicit finite bound holds:

\boxed{ \#\{\text{nonempty convex subsets of }X_m\} \le (m+1)^2\,2^{3m} \prod_{r=1}^{m-1}\left(1+\binom mr\right). } \tag{9}

This overcounts singletons and pairs, so it is also an upper bound under the problem's $k\ge3$ convention.

3.4 Evaluate the product

[a] With $h(x)=-x\ln x-(1-x)\ln(1-x)$, the uniform entropy estimate for binomial coefficients and a Riemann sum give

\begin{aligned} \ln Q_m &=\sum_{r=1}^{m-1}\ln\left(1+\binom mr\right)\\ &=m\sum_{r=1}^{m-1}h(r/m)+o(m^2)\\ &=m^2\int_0^1h(x)\,dx+o(m^2) =\frac{m^2}{2}+o(m^2). \end{aligned} \tag{10}

Therefore (9) implies

\log_2 f(2^m) \le \left(\frac{1}{2\ln2}+o(1)\right)m^2. \tag{11}

For an arbitrary $N$, choose $m=\lceil\log_2N\rceil$ and take any $N$-point subset of $X_m$. Removing points cannot create new convex subsets. Since $m=\log_2N+O(1)$,

\boxed{ \limsup_{N\to\infty} \frac{\log_2 f(N)}{(\log_2N)^2} \le\frac1{2\ln2} =0.721347520444\ldots } \tag{12}

Combining (1) and (12), the verified current interval is

\boxed{ \frac14 \le \liminf_{N\to\infty}\frac{\log_2f(N)}{(\log_2N)^2} \le \limsup_{N\to\infty}\frac{\log_2f(N)}{(\log_2N)^2} \le \frac1{2\ln2}. } \tag{13}

With natural logarithms, this is

\frac1{4\ln2} \le\liminf\frac{\ln f(N)}{(\ln N)^2} \le\limsup\frac{\ln f(N)}{(\ln N)^2} \le\frac1{2(\ln2)^2}. \tag{14}

This improves the simple upper constant $1$ in the live comment. It does not prove that the limit exists and does not identify its value.

4. Exact computation through nine points

4.1 The checker

The standalone verifier is erdos838_wavew048_verify.py. It uses only the Python standard library.

For each database realization it:

computes every triple orientation with exact integer arithmetic and rejects

collinearity;

classifies every quadruple by the four signs of its affine dependence;
uses the fact that a general-position subset is convex iff all of its

four-subsets are convex;

counts all convex subsets by size using bit truth tables;
compares the resulting vector with the database's independent kgons

row;

recomputes every subset of the displayed minimizing realization again

using a direct monotone-chain convex hull algorithm.

Step 3 is rigorous: if a set is not in convex position, some selected point lies in the convex hull of the others; planar Carathéodory supplies three of the others whose triangle contains it, producing a nonconvex four-subset.

The script verifies SHA-256 hashes for all fourteen order-type/count files and five cited primary-source files. It then separately recomputes (3)--(9) through the requested finite parameter range.

4.2 Result

[d: exhaustive modulo database completeness] Scanning all 162,289 order types for $3\le N\le9$ gives:

| $N$ | exact computed $f(N)$ | one minimizing profile $(\#3,\#4,\ldots,\#N)$ | number of minimizing database order types | |---:|---:|---|---:| | 3 | 1 | $(1)$ | 1 | | 4 | 4 | $(4,0)$ | 1 | | 5 | 11 | $(10,1,0)$ | 1 | | 6 | 23 | $(20,3,0,0)$ | 1 | | 7 | 44 | $(35,9,0,0,0)$ | 2 | | 8 | 77 | $(56,20,1,0,0,0)$ | 12 | | 9 | 123 | $(84,36,3,0,0,0,0)$ | 1 |

At $N=8$, other minimizers distribute the same total as $(56,19,2,0,0,0)$ or $(56,21,0,0,0,0)$.

An explicit nine-point minimizing realization is

\begin{split} \{&(62614,7322),(2922,4014),(10209,14386),\\ &(20660,24299),(33336,29017),(30137,33324),\\ &(15334,45211),(14934,55621),(10934,61521)\}. \end{split} \tag{15}

Exact determinant and hull checks give 84 convex triangles, 36 convex quadrilaterals, 3 convex pentagons, and no larger convex subset, totaling 123.

The database authors' completeness proof is external to this checker, so the table is labeled computational rather than a self-contained theorem. The ten-point database has 14,309,547 realizations and a 572 MB coordinate file. Linear extrapolation from the measured nine-point run gives about 18 single-core minutes for the present pure-Python from-scratch scan (roughly 0.3 core-hours), beyond the requested few-minute budget; I did not run it.

4.3 Reproduction log

Command:

/usr/bin/time -v python runs/erdos838_wavew048_verify.py \
  --data-dir /tmp/erdos838_data

Observed on this VM:

n=9: 158817 order types; minimum=123;
  by size=(84, 36, 3, 0, 0, 0, 0);
  minimizer indices=(151740,); 8.253s
base-2 asymptotic upper constant = 1/(2 ln 2) = 0.721347520444
recurrences and finite product bounds checked through m=44
verified 5 primary-source hashes
ALL CHECKS PASSED in 8.418s
Maximum resident set size: 36560 kbytes

I also tested a clean-cache download on a fresh temporary directory; the source download and hash verification path passed.

5. What remains

The limit-existence question is still open. The concrete gap after this run is between the forced-count constant $1/4$ and the construction-count constant $1/(2\ln2)$.

The exact missing ingredients are now easy to state:

To improve the lower constant, one needs more than the present statement

that each $T$-set contains one $r$-set in convex position. A uniform lower bound on the number of such $r$-sets, strong when $r\asymp\log T$, would feed the same double count.

To improve the upper constant, one needs a point construction whose

recursive group-choice entropy is smaller than $\int_0^1h(x)\,dx=1/2$, or a sharper count showing that the product in (9) substantially overcounts the actual Erdős--Szekeres construction.

Neither (13) nor the finite table supplies the missing regularity or

submultiplicativity needed to force equality of liminf and limsup.

PARTIAL: proved a rigorous upper-constant improvement to $1/(2\ln2)=0.7213475\ldots$ in base-2 normalization and exhaustively computed $f(3),\ldots,f(9)=1,4,11,23,44,77,123$, but the limit and its value remain open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger