Reused writeup on Math-937 (gpt pro 5.2)

Erdős Problem 791 --- collection record

PROVENANCE AND STATUS

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

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/791.tex.

REUSED SOURCE 1

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

FORMAL RESTATEMENT

Let $g(n)$ be the smallest integer $k$ such that there exists a set $A\subset\{0,1,\dots,n\}$ with $|A|=k$ and \[ \{0,1,\dots,n\} \subset A+A := \{a+a': a,a'\in A\}. \] Equivalently, every integer $t\in[0,n]$ can be written as $t=a+a'$ with $a,a'\in A$. The problem asks for estimates of $g(n)$ and in particular whether $g(n)\sim 2\sqrt n$.

QUICK LITERATURE/CONTEXT CHECK

From the problem statement: a simple counting gives $g(n)\ge (2n)^{1/2}$; a construction gives $g(n)\le 2\sqrt n+1$; and the claim $g(n)\sim 2\sqrt n$ is stated to be false (Mrose gives $g(n)^2\le \tfrac72 n$). Improved upper bounds with constants around $3.458\ldots$ are also quoted.

Below I reprove the elementary lower bound and a standard $2\sqrt n+O(1)$ construction, and I compute exact $g(n)$ for $n\le 25$.

ATTACK PLAN

1) Reprove the standard lower bound from the fact that $A+A$ has at most $\binom{|A|+1}{2}$ unordered sums.

2) Give an explicit two-scale construction (small interval + arithmetic progression) showing $g(n)\le 2\lceil\sqrt n\rceil+1$.

3) Reality check: brute-force exact $g(n)$ for $n\le 25$.

WORK

Lemma 791.1 (Counting lower bound). For every $n\ge 1$, \[ g(n)\ge \left\lceil\frac{\sqrt{8n+9}-1}{2}\right\rceil \ge \sqrt{2n}-1. \]

Proof. Let $A\subset\{0,\dots,n\}$ with $|A|=k$ and suppose $[0,n]\subset A+A$. Consider the set of unordered sums $a+a'$ with $a\le a'$. There are at most \[ \#\{\{a,a'\}: a,a'\in A\} = \binom{k+1}{2} = \frac{k(k+1)}{2} \] distinct such unordered pairs, hence at most $\binom{k+1}{2}$ distinct sums. But $A+A$ must contain $n+1$ distinct integers $0,1,\dots,n$. Therefore \[ \frac{k(k+1)}{2} \ge n+1. \] Solving the quadratic inequality gives $k\ge \frac{\sqrt{8n+9}-1}{2}$, and taking ceilings yields the first bound. The crude inequality $\frac{\sqrt{8n+9}-1}{2}\ge \sqrt{2n}-1$ follows by expanding squares. $\square$

Lemma 791.2 (A constructive upper bound $g(n)\le 2\lceil\sqrt n\rceil+1$). Let $m:=\lceil \sqrt n\rceil$. Define \[ A := \{0,1,2,\dots,m\}\ \cup\ \{0,m,2m,\dots,m^2\}\ \cap\ \{0,1,\dots,n\}. \] Then $|A|\le 2m+1$ and $[0,n]\subset A+A$. Consequently $g(n)\le 2\lceil\sqrt n\rceil+1$.

Proof. First, $A$ contains at most $m+1$ elements from $\{0,1,\dots,m\}$ and at most $m+1$ multiples of $m$, but $0$ is counted twice, so $|A|\le (m+1)+(m+1)-1=2m+1$.

Now fix any $t\in\{0,1,\dots,n\}$. Because $m^2\ge n\ge t$, we can write $t=qm+r$ with integers $q\in\{0,1,\dots,m\}$ and $r\in\{0,1,\dots,m-1\}$. Then $qm\in A$ and $r\in A$, hence $t=qm+r\in A+A$. This works for every $t\le n$. $\square$

Fast reality check (exact computation for $n\le 25$). I brute-forced the exact minimum $g(n)$ by searching over all subsets $A\subset\{0,\dots,n\}$ for $n\le 25$. The exact values found are:

(One witness set for each $n$ was produced by the brute force; omitted here for brevity.)

VERIFICATION

-- Lemma 791.1 counts unordered sums; using unordered pairs is necessary because ordered pairs can repeat the same sum.

-- Lemma 791.2: the representation $t=qm+r$ with $0\le q\le m$ and $0\le r<m$ is standard division with remainder, and the condition $t\le m^2$ ensures $q\le m$.

-- The brute-force search checked the condition $[0,n]\subset A+A$ exactly.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: \[\sqrt{2n}-1\ \le\ g(n)\ \le\ 2\lceil\sqrt n\rceil+1. \] (The statement quotes better known upper constants and that $g(n)\sim 2\sqrt n$ is false.)

(ii) First gap (crisp): Determine the correct constant $c$ (if it exists) in \[\lim_{n\to\infty} \frac{g(n)^2}{n}=c, \] or at least pin down $\liminf$ and $\limsup$ sharply.

(iii) Top 3 next moves:

1. Improve explicit constructions beyond the two-scale set in Lemma 791.2 by adding a third "scale" (a second step size) and optimize parameters to lower the constant in $|A|\le c\sqrt n$.
2. Prove stronger counting/entropy lower bounds that use not just $|A+A|$ but the local multiplicities of representations of sums.
3. Compute exact $g(n)$ further (e.g. up to $n=100$) and analyze the structure of extremal $A$ to guess the correct constant and suggest a construction.

(iv) Minimal counterexample structure to watch for: Any attempt to prove a sharp lower constant would need to rule out bases $A$ whose sumset $A+A$ is unusually "efficient" (many distinct sums with minimal collisions). Extremal $A$ empirically resemble unions of a short initial segment with a sparse progression; sharpening lower bounds likely requires showing every such hybrid incurs inevitable collisions.

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.