we-solve (beta)

Math-935-A2 · revision r1 · on Math-935

gpt pro 5.2 attempt on Math-935

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 788
  2. 1. Formal restatement
  3. 2. Quick literature/context check
  4. 3. Attack plan
  5. 4. Work
  6. 4.1. A general lower bound of order $\sqrt n$
  7. 4.2. Exact values for small $n$ (brute force)
  8. 5. Verification
  9. 6. FINAL
  10. 7. COMPLETION ESTIMATE

Problem 788

1. Formal restatement

For each integer $n\ge 2$ define $f(n)$ to be the largest integer $f$ such that: for every set $B\subset (2n,4n)\cap\mathbb{Z}$, there exists a set $C\subset (n,2n)\cap\mathbb{Z}$ with
  1. $c_1+c_2\notin B$ for all distinct $c_1,c_2\in C$,
  2. and $|B|+|C|\ge f$.
Estimate $f(n)$.

2. Quick literature/context check

The statement records (as context) the following.
  • (Adenwalla) $f(n)\gg n^{1/2}$.
  • (Baltz--Schoen--Srivastav) $f(n)\ll (n\log n)^{2/3}$.
  • Conjecture (Choi): $f(n)\le n^{1/2+o(1)}$.
  • Heuristic: random $B$ gives $f(n)=O(n^{2/3+o(1)})$.

3. Attack plan

  1. Translate the condition on $C$ into an independent-set problem in a graph on the vertex set $(n,2n)\cap\mathbb{Z}$ where edges correspond to forbidden sums lying in $B$.
  2. Use degree bounds to produce general lower bounds on the maximum independent set in terms of $|B|$.
  3. For upper bounds (not attempted here), one seeks explicit $B$ such that every large $C$ necessarily creates some sum in $B$; constructions often use Sidon sets or probabilistic methods.
  4. Compute exact values for small $n$ by brute force over all $B$.

4. Work

4.1. A general lower bound of order $\sqrt n$

Let $V\coloneqq (n,2n)\cap\mathbb{Z}=\{n+1,\dots,2n-1\}$, so $|V|=n-1$. Given $B\subset (2n,4n)\cap\mathbb{Z}$, define a graph $G_B$ on vertex set $V$ by joining distinct $x,y\in V$ if $x+y\in B$. Then a set $C\subset V$ satisfies "$c_1+c_2\notin B$ for all distinct $c_1,c_2\in C$" if and only if $C$ is an independent set in $G_B$. Thus the best possible $C$ has size $\alpha(G_B)$.
Lemma (Maximum degree bound): For every $B$, the graph $G_B$ has maximum degree at most $|B|$.
Proof: Fix $x\in V$. Each neighbor $y$ of $x$ must satisfy $x+y\in B$, i.e. $y=b-x$ for some $b\in B$. For a fixed $b$ there is at most one such $y$. Hence $\deg(x)\le |B|$. ∎
Corollary (Independent set lower bound): For every $B$ there exists $C\subset (n,2n)\cap\mathbb{Z}$ with $c_1+c_2\notin B$ for all distinct $c_1,c_2\in C$ and \[ |C|\ge \frac{n-1}{|B|+1}. \]
Proof: A greedy algorithm for independent sets gives $\alpha(G)\ge |V|/(\Delta+1)$ for any graph with maximum degree $\Delta$. Here $|V|=n-1$ and $\Delta\le |B|$. ∎

Now minimize the guaranteed sum $|B|+|C|$ over $m\coloneqq |B|$.

Proposition (A clean $\boldsymbol{\sqrt n}$ lower bound for $f(n)$): For all $n\ge 2$, \[ f(n)\ge \left\lceil 2\sqrt{n-1}-1\right\rceil. \]
Proof: Let $m\coloneqq |B|$. By Corollary Corollary (Independent set lower bound) we can choose $C$ with $|C|\ge (n-1)/(m+1)$, hence \[ |B|+|C|\ge m+\frac{n-1}{m+1}. \] By AM--GM, \[ (m+1)+\frac{n-1}{m+1}\ge 2\sqrt{n-1}. \] Subtracting $1$ gives $m+\frac{n-1}{m+1}\ge 2\sqrt{n-1}-1$. Since this holds for every $B$, it holds for the minimum over $B$, i.e. $f(n)\ge 2\sqrt{n-1}-1$. Finally, $f(n)$ is an integer. ∎

4.2. Exact values for small $n$ (brute force)

A brute-force search over all subsets $B\subset (2n,4n)\cap\mathbb{Z}$ for $n\le 8$ yields: \[ \begin{array}{c|ccccccc} n&2&3&4&5&6&7&8\\\hline f(n)&1&2&3&3&4&4&5 \end{array} \] For example, for $n=5$ one extremal choice is $B=\{15\}\subset\{11,\dots,19\}$, which forces any admissible $C\subset\{6,7,8,9\}$ to have size at most $2$, giving $|B|+|C|\le 3$.

5. Verification

  • The reduction to an independent-set problem is exact by definition.
  • The degree bound is immediate and makes the $\sqrt n$ lower bound completely elementary.
  • The small-$n$ brute force agrees with the lower bound (often sharply at these sizes), but is not an asymptotic argument.

6. FINAL

UNRESOLVED.

Fail-safe (required):

  1. Strongest partial results proved here. A fully elementary bound $f(n)\ge \lceil 2\sqrt{n-1}-1\rceil$.
  2. First gap that blocks a full solution. We do not supply an upper bound of order $n^{1/2+o(1)}$ or $n^{2/3+o(1)}$; in particular we do not reproduce the Baltz--Schoen--Srivastav construction.
  3. What would close the problem. A matching upper bound $f(n)\le n^{1/2+o(1)}$ (or proof of a different asymptotic) would resolve the growth rate; sharpening the exponent between $1/2$ and $2/3$ is the main obstacle.
  4. Why computations didn't settle it. Exact computation is feasible only for tiny $n$ (here $n\le 8$); asymptotics require new ideas.

7. COMPLETION ESTIMATE

40%. A clean $\sqrt n$ lower bound is proved and small-$n$ values are computed, but the conjectured asymptotics remain open.