we-solve (beta)

Math-643-A5 · revision r1 · on Math-643

gpt pro 5.2 attempt on Math-643, version 2

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. Round-2 Objective
  2. Round-1 Foundation Used
  3. New Insight / Tool (Round-2)
  4. Attack Plan (Round-2)
  5. Work (Round-2)
  6. A parallelogram lemma in the "triangle" $a+b\le M$
  7. Many same-difference small-sum pairs force many bad sums
  8. A structural necessary condition for $Q2$
  9. Adversarial Verification
  10. Final
  11. Completion Estimate
  12. References

Round-2 Objective

Path pursued: (C) obstruction/correction (necessary structural conditions).

Round 1 left the main gap: either prove the lower bound in $Q1$ for all infinite $A\subseteq\mathbb N$, or build a single infinite $A$ with $|\{1,\dots,N\}\setminus B|=o(N^{1/2})$.

In this round I focus on extracting a fatal-looking structural obstruction that any putative counterexample to $Q1$/$Q2$ would have to satisfy, and I prove it cleanly. Concretely: small complement forces an "almost injectivity" constraint on certain difference patterns among the pairs representing the initial segment. This reduces $Q2$ to the existence of an infinite nested family of finite sets with a strong triangular Sidon/Golomb-ruler property. This is new, explicit, and would settle the problem if one can rule out (or construct) such families.

Round-1 Foundation Used

I rely on the following Round 1 items (as stated there):
  • Lemma 14.1: for each $N$, membership of $n\le N$ in $B$ depends only on $A\cap[1,N]$.
  • Lemma 14.2: the "small-number" obstruction in terms of $\min A$.
  • Lemma 14.3: the pair-counting bound in the fully collision-free regime.
No Round 1 proofs are reproved.

New Insight / Tool (Round-2)

The new tool is a deterministic "parallelogram" mechanism converting repeated differences among small-sum pairs into guaranteed multiple representations inside the same initial segment. This is a local-to-local propagation statement (unlike the global energy heuristics sketched in Round 1).

In particular, when one restricts attention to pairs $(a,b)$ with $a+b\le M$, repeated differences cannot be "hidden" by pushing induced collisions above $M$; they necessarily create a collision within $[1,M]$.

Attack Plan (Round-2)

Gap after Round 1. The principal gap is the absence of either
  • a general lower bound $|[1,N]\setminus B|\gg_\varepsilon N^{1/2-\varepsilon}$ $Q1$, or
  • an explicit infinite construction with $|[1,N]\setminus B|=o(N^{1/2})$ $Q2$.

Round 2 target. Assume toward $Q2$ that $|[1,N]\setminus B|$ is very small (e.g. $o(N^{1/2})$) along a sequence. Using Lemma 14.1, pass to the finite truncation $S:=A\cap[1,M]$ with $M\asymp N$. Prove that small complement forces strong difference constraints on the graph of pairs $(a,b)$ with $a+b\le M$.

Why this helps. It converts $Q2$ into the existence of a nested family $S_M\subset[1,M]$ with:

  1. $|[1,M]\setminus B(S_M)|=o(\sqrt M)$, and
  2. an "almost Golomb ruler" constraint on differences among the pairs realizing $B(S_M)$.
Any future resolution can now aim directly at ruling out (or constructing) such objects.

Work (Round-2)

Throughout, for a finite set $S\subseteq\mathbb N$ we write \[ r_S(n):=|\{\{a,b\}:a,b\in S,\ a\le b,\ a+b=n\}|, \qquad B(S):=\{n\in\mathbb N:r_S(n)=1\}. \] When additionally $S\subseteq[1,M]$ we abbreviate $\mathrm{Bad}(S;M):=[1,M]\setminus B(S)$.

A parallelogram lemma in the "triangle" $a+b\le M$

Lemma (Parallelogram collision forces a bad sum inside the same initial segment): Let $M\ge 2$ and let $S\subseteq[1,M]$. Fix an integer $d\ge 1$. Assume there exist two distinct starting points $a<c$ such that \[ a,a+d,c,c+d\in S\quad\text{and}\quad 2a+d\le M,\ \ 2c+d\le M. \] Then the integer \[ n:=a+c+d \] lies in $[1,M]$ and satisfies $r_S(n)\ge 2$, hence $n\in\mathrm{Bad}(S;M)$.
Proof: First, the two displayed inequalities imply $a,c\le (M-d)/2$, hence \[ n=a+c+d\le (M-d)/2+(M-d)/2+d=M. \] Now note the two (unordered) representations \[ n=a+(c+d)=(a+d)+c. \] Because $d\ge 1$ and $a<c$, the pairs $\{a,c+d\}$ and $\{a+d,c\}$ are distinct, so $r_S(n)\ge 2$. ∎
Remark (Why the "triangle" condition matters): Lemma Lemma (Parallelogram collision forces a bad sum inside the same initial segment) fails without the constraints $2a+d,2c+d\le M$: if two pairs have the same difference but lie high up in $[1,M]$, the induced collision sum $a+c+d$ could exceed $M$ and thus not contribute to $\mathrm{Bad}(S;M)$. The triangle condition prevents this escape.

Many same-difference small-sum pairs force many bad sums

For $d\ge 1$ define the set of admissible starting points \[ P_d(S;M):=\{a\in S: a+d\in S\ \text{and}\ \ 2a+d\le M\}. \] Equivalently, $a\in P_d(S;M)$ iff the unordered pair $\{a,a+d\}$ is a representation of some $n\le M$.
Corollary (Same difference inside $a+b\le M$ yields many distinct bad sums): Let $M\ge 2$, $S\subseteq[1,M]$, and $d\ge 1$. Write $k_d:=|P_d(S;M)|$. If $k_d\ge 2$, then there exist $k_d-1$ distinct integers $n\le M$ with $r_S(n)\ge 2$. In particular, \[ k_d-1\le |\mathrm{Bad}(S;M)|. \]
Proof: List $P_d(S;M)=\{a_1<\cdots<a_{k_d}\}$. For each $j\in\{2,\dots,k_d\}$ apply Lemma Lemma (Parallelogram collision forces a bad sum inside the same initial segment) to the two pairs $(a_1,a_1+d)$ and $(a_j,a_j+d)$. This shows that \[ n_j:=a_1+a_j+d\le M \] and $r_S(n_j)\ge 2$. The integers $n_j$ are distinct because $a_j$ are distinct. Thus $\{n_2,\dots,n_{k_d}\}$ is a set of $k_d-1$ distinct bad sums, giving $k_d-1\le |\mathrm{Bad}(S;M)|$. ∎

A structural necessary condition for $Q2$

We now translate Corollary cor:distinct-bad-from-one-d into a concrete obstruction for any putative counterexample.
Proposition (Small complement forces "triangular" near-Golomb behavior): Let $A\subseteq\mathbb N$ be infinite, and let $M\ge 2$. Set $S:=A\cap[1,M]$ and $E_M:=|\mathrm{Bad}(S;M)|=|[1,M]\setminus B|$. Then:
  1. (Size lower bound.) The truncation $S$ must satisfy \[ \binom{|S|+1}{2}\ \ge\ M-E_M. \] Equivalently, \begin{equation} \label{wsref-0-65-71-3a-73-69-7a-65-2d-6c-62} |S|\ \ge\ \frac{\sqrt{1+8(M-E_M)}-1}{2}. \end{equation} In particular, if $E_M=o(\sqrt M)$ along a sequence $M\to\infty$, then \[ |A\cap[1,M]|\ \ge\ (\sqrt2+o(1))\sqrt M. \]

  2. (Per-difference multiplicity bound in the triangle.) For every integer $d\ge 1$ one has \begin{equation} \label{wsref-0-65-71-3a-70-65-72-2d-64-2d-62-6f-75-6e-64} |P_d(S;M)|\le E_M+1. \end{equation} Equivalently: among the pairs $\{a,a+d\}\subseteq S$ that actually contribute to sums $\le M$, the fixed difference $d$ occurs at most $E_M+1$ times.

  3. (Reduction of $Q2$ to an "almost triangular Golomb ruler" family.) If $Q2$ holds, i.e. there exists $A$ with $E_M=o(\sqrt M)$ as $M\to\infty$, then there is an infinite sequence $M_j\to\infty$ and finite sets $S_j\subseteq[1,M_j]$ with $S_j=A\cap[1,M_j]$ such that \begin{equation} \label{wsref-0-65-71-3a-74-72-69-61-6e-67-75-6c-61-72-2d-67-6f-6c-6f-6d-62-2d-66-61-6d-69-6c-79} |S_j|=(\sqrt2+o(1))\sqrt{M_j} \quad\text{and}\quad \sup_{d\ge 1}|P_d(S_j;M_j)|=o(\sqrt{M_j}). \end{equation} In particular, all differences inside the "triangle" $a+(a+d)\le M_j$ have sub-$\sqrt{M_j}$ multiplicity.

Proof: $1$ Each $n\in B\cap[1,M]$ has exactly one representation $n=a+b$ with $a\le b$ and $a,b\in S$. Distinct $n$ give distinct unordered pairs $\{a,b\}$. Thus the number of such pairs is exactly $|B\cap[1,M]|=M-E_M$. But $S$ has only $\binom{|S|+1}{2}$ unordered pairs total, hence $\binom{|S|+1}{2}\ge M-E_M$. Solving the quadratic yields (eq:size-lb).

$2$ Fix $d\ge 1$. Let $k_d=|P_d(S;M)|$. If $k_d\le 1$ there is nothing to prove. If $k_d\ge 2$, Corollary cor:distinct-bad-from-one-d produces $k_d-1$ distinct integers in $\mathrm{Bad}(S;M)$, so $k_d-1\le E_M$, i.e. $k_d\le E_M+1$.

$3$ If $E_M=o(\sqrt M)$, then $1$ implies $|S|\ge (\sqrt2+o(1))\sqrt M$. Also, $2$ implies $\sup_d |P_d(S;M)|\le E_M+1=o(\sqrt M)$. Taking a subsequence $M_j\to\infty$ gives (eq:triangular-golomb-family). ∎

Remark (Interpretation): Equation (eq:triangular-golomb-family) is a concrete necessary condition for any counterexample to $Q1$/$Q2$: the truncations must have nearly minimal size $\sim \sqrt{2M}$ (forced by mere counting) and must avoid large multiplicities of fixed differences among those pairs that actually land inside $[1,M]$. This is reminiscent of constructing near-extremal Golomb rulers/Sidon-type objects, but in the triangular region $a+b\le M$ rather than in the full difference set.

Adversarial Verification

I check the new statements against edge cases and quantifiers.
  • Ordered/unordered issue. Everything is stated for unordered representations with $a\le b$ (Round 1 convention). In Lemma Lemma (Parallelogram collision forces a bad sum inside the same initial segment) the two representations are by two distinct unordered pairs because $d\ge 1$ and $a<c$; thus $r_S(n)\ge 2$ is valid under the unordered convention.

  • The case $d=0$. The parallelogram mechanism fails for $d=0$ because $a+a=c+c$ type equal-difference does not produce two distinct unordered pairs for the cross-sum. Accordingly Lemma Lemma (Parallelogram collision forces a bad sum inside the same initial segment) and the corollary explicitly require $d\ge 1$.

  • Range check. The triangle hypotheses $2a+d\le M$ and $2c+d\le M$ are precisely what guarantees $n=a+c+d\le M$; without them the derived collision could lie above $M$ and would not contribute to $\mathrm{Bad}(S;M)$.

  • Per-$d$ bound in Proposition Proposition (Small complement forces "triangular" near-Golomb behavior)$2$. Potential pitfall: bad sums produced for a fixed $d$ could coincide with each other, invalidating $k_d-1\le E_M$. This is addressed: for fixed $d$ we produced sums $n_j=a_1+a_j+d$ with distinct $a_j$, hence distinct $n_j$. Overlaps with bad sums coming from other differences do not affect the inequality $k_d-1\le E_M$ because it is a bound for a fixed $d$.

  • Use of Round 1 Lemma 14.1. Proposition Proposition (Small complement forces "triangular" near-Golomb behavior) is stated directly for $S=A\cap[1,M]$ and $E_M=|[1,M]\setminus B|$; by Lemma 14.1 this $E_M$ indeed depends only on the truncation $S$, so the reduction is well-posed.
No hidden assumptions were found beyond $A\subseteq\mathbb N$ and the adopted representation convention.

Final

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 establishes a new, fully rigorous obstruction: if one hopes for $|\{1,\dots,N\}\setminus B|=o(N^{1/2})$, then the truncations $S=A\cap[1,M]$ must simultaneously have size $(\sqrt2+o(1))\sqrt M$ (forced by counting) and must satisfy a strong per-difference multiplicity constraint (eq:per-d-bound) inside the triangle $a+(a+d)\le M$. This reduces $Q2$ to the existence of an infinite nested family of finite sets with "almost triangular Golomb ruler" behavior (eq:triangular-golomb-family).

What remains open is whether such families exist; ruling them out (or constructing them) would resolve $Q1$/$Q2$.

Completion Estimate

COMPLETION: 55%

References

No external theorems beyond elementary counting were invoked in Round 2.