we-solve (beta)

Math-5388-A13 · revision r1 · on Math-5388

gpt pro 5.4 attempt on Math-5388, version 8

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 11)
  2. 1) ROUND-11 OBJECTIVE
  3. 2) Round-10 FOUNDATION USED
  4. 3) NEW INSIGHT / TOOL (ROUND-11)
  5. (i) Minimal mod-$3$ Sidon embedding.
  6. (ii) Exact objective formula at the cube roots of unity.
  7. 4) ATTACK PLAN (ROUND-11)
  8. 5) WORK (ROUND-11)
  9. 5.1 The exact mod-$3$ embedding theorem
  10. 5.2 Exact reformulation of the first question
  11. 5.3 Fourier identity at the cube roots of unity
  12. 5.4 The remaining open inequality, rewritten exactly
  13. 6) ADVERSARIAL VERIFICATION
  14. (i) The naive mod-$2$ embedding really fails.
  15. (ii) No hidden use of the unresolved first question.
  16. (iii) Why this is beyond Round 10.
  17. (iv) What a future proof or disproof would now have to do.
  18. 7) FINAL
  19. 8) COMPLETION ESTIMATE (MANDATORY)
  20. 9) REFERENCES

Erdős Problem #43 (Round 11)

1) ROUND-11 OBJECTIVE

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

Round 10 exhausted the translation-invariant support-size quadratic-form route, but it still did not isolate the combinatorial core of the first question. In this round I attempted a full proof or a counterexample for \[ \binom{|A|}{2}+\binom{|B|}{2}\le \binom{f(N)}{2}+O(1), \] for Sidon sets $A,B\subset [N]$ with $(A-A)\cap(B-B)=\{0\}$.

I do not have a gap-free proof or disproof of this first question. The strict new progress in this round is an exact reformulation of the problem as a Sidon problem in two residue classes modulo $3$, together with an exact Fourier identity at the cube roots of unity. This isolates the remaining difficulty more sharply than any previous round: after Round 10's kernel barriers, the unresolved issue is now exactly a fixed-frequency extremal problem for Sidon sets lying in two congruence classes.

2) Round-10 FOUNDATION USED

I explicitly use the following previous-round results.

  • Round 4/5: the second question is false (Barreto's construction), so only the first question remains unresolved.
  • Round 2: from $(A-A)\cap(B-B)=\{0\}$ one gets cross-sum injectivity: the map $(a,b)\mapsto a+b$ from $A\times B$ is injective.
  • Round 9/10: the whole translation-invariant support-size / positive-definite-kernel framework has been optimised and exhausted; any eventual proof of the first question must exploit structure beyond those averaged kernel bounds.
I do not restate the proofs of these ingredients.

3) NEW INSIGHT / TOOL (ROUND-11)

There are two genuinely new ingredients in this round.

(i) Minimal mod-$3$ Sidon embedding.
The pair condition is exactly equivalent to the statement that \[ C:=3A\cup (3B+1) \] is a Sidon set. Thus Problem 43 can be reformulated as a problem about Sidon subsets of $[3N+1]$ supported on the two residue classes $0,1\pmod 3$.
(ii) Exact objective formula at the cube roots of unity.
If $C\subset [3N+1]$ is such a Sidon set, write \[ a:=|C\cap 3\mathbb Z|, \qquad b:=|C\cap (3\mathbb Z+1)|, \qquad s:=|C|=a+b, \qquad \omega:=e^{2\pi i/3}. \] Then \[ \binom{a}{2}+\binom{b}{2} = \#\{d>0:d\in C-C,\ 3\mid d\} = \frac{s^2-3s+2\left|\sum_{c\in C}\omega^c\right|^2}{6}. \] So the first question is equivalent to bounding a single Fourier coefficient at frequency $1/3$ for Sidon sets occupying two residue classes mod $3$.

This is strictly new: previous rounds ruled out averaged kernel methods, but they did not identify this exact residue-class/Fourier reformulation.

4) ATTACK PLAN (ROUND-11)

Exact gap left after Round 10. The missing piece was not another averaged inequality, but a precise description of what quantity actually controls \[ \binom{|A|}{2}+\binom{|B|}{2} \] after all support-size kernel arguments have been exhausted.

Round 11 plan.

  1. Prove the exact mod-$3$ embedding theorem \[ (A,B)\ \text{feasible} \iff C:=3A\cup(3B+1)\ \text{is Sidon}. \]
  2. Re-express the target quantity both combinatorially (as the number of $0\pmod 3$ differences of $C$) and analytically (via $|\sum_{c\in C}\omega^c|^2$).
  3. Show that this reformulation is minimal: the naive mod-$2$ embedding fails, so mod $3$ is the first place where the sum types separate.

This overcomes the earlier obstacle by turning the unresolved part of Problem 43 into one exact extremal problem on Sidon sets in two residue classes, rather than a vague search for stronger kernels.

5) WORK (ROUND-11)

Throughout this section, $[N]=\{1,\dots,N\}$.

5.1 The exact mod-$3$ embedding theorem

Theorem (Minimal residue-class embedding): Let $A,B\subset \mathbb Z$ be finite sets. The following are equivalent:
  1. $A$ and $B$ are Sidon and $(A-A)\cap(B-B)=\{0\}$.
  2. The set \[ C:=3A\cup(3B+1) \] is Sidon.
More generally, the same equivalence holds with $3$ replaced by any integer $m\ge 3$ and $3B+1$ replaced by $mB+1$.
Proof: Assume first that $A$ and $B$ are Sidon and $(A-A)\cap(B-B)=\{0\}$. By the Round 2 cross-sum injectivity lemma, the map $(a,b)\mapsto a+b$ on $A\times B$ is injective.

We show that $C=3A\cup(3B+1)$ is Sidon. Suppose \[ x_1+x_2=x_3+x_4 \qquad (x_i\in C). \] Reducing modulo $3$, the unordered pair-types are distinguished:

  • two elements from $3A$ give sum $0\pmod 3$;
  • one element from $3A$ and one from $3B+1$ give sum $1\pmod 3$;
  • two elements from $3B+1$ give sum $2\pmod 3$.
Hence the two representations have the same type.

If both are of type $3A+3A$, then dividing by $3$ gives an equality of two sums in $A+A$, and Sidonicity of $A$ forces the same unordered pair. The type $3B+1+3B+1$ is identical.

If both are of mixed type, we have \[ 3a_1+(3b_1+1)=3a_2+(3b_2+1), \] so $a_1+b_1=a_2+b_2$. Since $A+B$ is injective, $(a_1,b_1)=(a_2,b_2)$. Thus the mixed representation is unique as well. Therefore $C$ is Sidon.

Conversely, assume that $C=3A\cup(3B+1)$ is Sidon.

First, $A$ is Sidon: if $a_1+a_2=a_3+a_4$, then \[ 3a_1+3a_2=3a_3+3a_4, \] and since $C$ is Sidon, the two unordered pairs in $3A$ are equal; dividing by $3$ gives $\{a_1,a_2\}=\{a_3,a_4\}$. The same argument shows that $B$ is Sidon.

Next, $A+B$ is injective. If $a_1+b_1=a_2+b_2$, then \[ 3a_1+(3b_1+1)=3a_2+(3b_2+1). \] Since $C$ is Sidon and each side is a mixed representation (one residue $0\pmod 3$, one residue $1\pmod 3$), the two ordered pairs coincide; hence $a_1=a_2$ and $b_1=b_2$.

Finally, if $d\in (A-A)\cap(B-B)$, say $d=a_1-a_2=b_2-b_1$, then \[ a_1+b_1=a_2+b_2. \] Injectivity of $A+B$ implies $a_1=a_2$ and $b_1=b_2$, so $d=0$. Thus $(A-A)\cap(B-B)=\{0\}$.

The proof for $mA\cup(mB+1)$ with any $m\ge 3$ is identical, since the sum-types have residues $0,1,2\pmod m$ and are therefore distinct. ∎

Remark: The modulus $3$ is minimal. For $m=2$, the same-colour sum-types $0+0$ and $1+1$ are both $0\pmod 2$, so the clean residue separation fails.

5.2 Exact reformulation of the first question

For a finite set $C\subset \mathbb Z$, define \[ D_0(C):=\#\{d>0:d\in C-C,\ 3\mid d\}. \]

Corollary (Problem 43 as a mod-$3$ Sidon problem): The first question of Problem 43 is equivalent to the following statement:
If $C\subset [3N+1]$ is Sidon and $C\subset 3\mathbb Z\cup (3\mathbb Z+1)$, then \[ D_0(C)\le \binom{f(N)}{2}+O(1). \]
Moreover, if $C=3A\cup(3B+1)$, then \[ D_0(C)=\binom{|A|}{2}+\binom{|B|}{2}. \]
Proof: If $(A,B)$ is feasible, Theorem Theorem (Minimal residue-class embedding) produces a Sidon set $C=3A\cup(3B+1)\subset [3N+1]$.

A positive difference of $C$ is divisible by $3$ if and only if it comes from two elements of the same residue class mod $3$, i.e. either from two elements of $3A$ or from two elements of $3B+1$. Since $A$ and $B$ are Sidon, these positive differences are all distinct within each class, and because the original difference sets are disjoint, they are distinct across the two classes as well. Thus \[ D_0(C)=\binom{|A|}{2}+\binom{|B|}{2}. \]

Conversely, if $C\subset [3N+1]$ is Sidon and lies in $3\mathbb Z\cup(3\mathbb Z+1)$, define \[ A:=\{a:3a\in C\}, \qquad B:=\{b:3b+1\in C\}. \] Then $C=3A\cup(3B+1)$, so Theorem Theorem (Minimal residue-class embedding) shows that $(A,B)$ is feasible, and the same counting argument gives \[ D_0(C)=\binom{|A|}{2}+\binom{|B|}{2}. \] This is exactly the original optimisation problem. ∎

5.3 Fourier identity at the cube roots of unity

Let $\omega:=e^{2\pi i/3}$, so $1+\omega+\omega^2=0$ and \[ \Re(\omega)=-\frac12. \]

Proposition (Exact Fourier formula): Let $C\subset [3N+1]$ be Sidon and assume $C\subset 3\mathbb Z\cup(3\mathbb Z+1)$. Write \[ a:=|C\cap 3\mathbb Z|, \qquad b:=|C\cap (3\mathbb Z+1)|, \qquad s:=|C|=a+b. \] Then \[ \sum_{c\in C}\omega^c = a+\omega b, \qquad \left|\sum_{c\in C}\omega^c\right|^2 = a^2+b^2-ab. \] Consequently, \begin{equation} \label{wsref-0-65-71-3a-66-6f-75-72-69-65-72-44} D_0(C)=\binom{a}{2}+\binom{b}{2} =\frac{s^2-3s+2\left|\sum_{c\in C}\omega^c\right|^2}{6}. \end{equation}
Proof: Every element of $C\cap 3\mathbb Z$ contributes $1$ to $\sum_{c\in C}\omega^c$, and every element of $C\cap(3\mathbb Z+1)$ contributes $\omega$. Hence \[ \sum_{c\in C}\omega^c=a+\omega b. \] Taking squared modulus and using $\omega+\overline\omega=-1$ gives \[ \left|a+\omega b\right|^2 =a^2+b^2+ab(\omega+\overline\omega) =a^2+b^2-ab. \]

Let \[ M:=\left|\sum_{c\in C}\omega^c\right|^2. \] Then \[ M=a^2+b^2-ab, \qquad s^2=(a+b)^2=a^2+b^2+2ab. \] Subtracting yields \[ 3(a^2+b^2)=s^2+2M. \] Therefore \[ a^2+b^2=\frac{s^2+2M}{3}. \] Finally, \[ D_0(C)=\binom{a}{2}+\binom{b}{2}=\frac{a^2+b^2-a-b}{2} =\frac{1}{2}\left(\frac{s^2+2M}{3}-s\right) =\frac{s^2-3s+2M}{6}, \] which is exactly (eq:fourierD). ∎

Corollary (Equal-size condition as an exact Fourier constraint): With notation as above, \[ a=b \qquad\Longleftrightarrow\qquad \left|\sum_{c\in C}\omega^c\right|=\frac{|C|}{2}. \]
Proof: By Proposition Proposition (Exact Fourier formula), \[ \left|\sum_{c\in C}\omega^c\right|^2=a^2+b^2-ab. \] Also, \[ \frac{|C|^2}{4}=\frac{(a+b)^2}{4}. \] Subtracting, \[ a^2+b^2-ab-\frac{(a+b)^2}{4} =\frac{3(a-b)^2}{4}. \] Thus \[ \left|\sum_{c\in C}\omega^c\right|^2=\frac{|C|^2}{4} \quad\Longleftrightarrow\quad a=b. \] Taking square roots proves the claim. ∎

5.4 The remaining open inequality, rewritten exactly

By Corollary cor:mod3reform and Proposition Proposition (Exact Fourier formula), the first question of Problem 43 is equivalent to the statement that for every Sidon set $C\subset [3N+1]$ contained in $3\mathbb Z\cup(3\mathbb Z+1)$, \begin{equation} \label{wsref-0-65-71-3a-72-65-77-72-69-74-74-65-6e-2d-6f-70-65-6e} \frac{|C|^2-3|C|+2\left|\sum_{c\in C}\omega^c\right|^2}{6} \le \binom{f(N)}{2}+O(1). \end{equation}

This is now the exact unresolved core left after Round 10. The point is that previous barrier theorems only controlled support size and total mass via averaged kernels, whereas (eq:rewritten-open) shows that the decisive statistic is a single rigid Fourier coefficient at frequency $1/3$, together with the Sidon constraint and the restriction to two residue classes.

6) ADVERSARIAL VERIFICATION

(i) The naive mod-$2$ embedding really fails.
Take the small feasible pair \[ A=\{1,2,5\}, \qquad B=\{1,3,8\}. \] Then $A$ and $B$ are Sidon and $(A-A)\cap(B-B)=\{0\}$, but \[ (2A-1)\cup 2B = \{1,2,3,6,9,16\} \] is not Sidon, since \[ 1+3=2+2. \] So parity is the wrong ambient modulus; the mod-$3$ embedding theorem above is genuinely new and genuinely minimal.
(ii) No hidden use of the unresolved first question.
Theorem Theorem (Minimal residue-class embedding), Corollary cor:mod3reform, and Proposition Proposition (Exact Fourier formula) are all exact elementary equivalences and identities. None of them assumes the desired $O(1)$ bound.
(iii) Why this is beyond Round 10.
Round 10 classified support-length kernel lower bounds. The new mod-$3$ reformulation shows that even after those barriers, there remains a very specific unresolved statistic, namely \[ \left|\sum_{c\in C}\omega^c\right|, \] for Sidon sets $C$ in two residue classes. This isolates the obstruction much more sharply than "some stronger kernel is needed."
(iv) What a future proof or disproof would now have to do.
A proof of the first question must control the fixed-frequency quantity in (eq:rewritten-open) for Sidon sets in two residue classes. A disproof would need an infinite family of such sets for which the left-hand side of (eq:rewritten-open) exceeds $\binom{f(N)}{2}$ by an unbounded amount. I do not have either in this round.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

I cannot honestly upgrade Problem 43 to a full 100% resolution in this round: the first question remains open in my work here. The strict new progress beyond Round 10 is an exact and minimal reformulation:

  • feasible pairs $(A,B)$ are exactly Sidon sets of the form $C=3A\cup(3B+1)$;
  • the target quantity is exactly the number of positive $0\pmod 3$ differences of $C$;
  • equivalently, \[ \binom{|A|}{2}+\binom{|B|}{2} = \frac{|C|^2-3|C|+2\left|\sum_{c\in C}e^{2\pi i c/3}\right|^2}{6}. \]
This isolates the remaining unresolved core as a fixed-frequency extremal problem for Sidon sets in two residue classes modulo $3$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 96%

9) REFERENCES

  • Round 10 write-up supplied in this task.
  • T. F. Bloom, Erdős Problem #43, official problem page and discussion thread.
  • No external theorem beyond elementary roots-of-unity algebra is used in the new Round 11 work.