Erdős Problem #40

Erdős Problem #40 --- Round 5

1) ROUND-5 OBJECTIVE

Path (C): obstruction / correction by ruling out the natural reduction from the remaining $B_2[\lambda]$-core to the Sidon problem.

Round 4 reduced the unresolved subpolynomial sector of Problem #40 to the existence of an infinite $B_2[\lambda]$ set whose counting function is $N^{1/2-o(1)}$ in the strong "for all sufficiently large $N$" sense. The most promising next step is therefore to test whether this remaining $B_2[\lambda]$-problem can be collapsed to the Sidon problem (Problem #39) by a structural theorem.

In this round I show that two of the most natural reduction principles are false:

• bounded-representation sets need not be finite unions of Sidon sets;
• even a strong local Sidon-richness property (every finite subset contains a large Sidon subset) still does not force such a decomposition.

Thus the Round 4 exact core is genuinely broader than the Sidon case, and any eventual reduction to Problem #39 would require a new global density-preserving theorem of a different kind.

2) ROUND-4 FOUNDATION USED

I rely on the following Round 4 results without re-proving them.

• Round 4 exact subpolynomial reformulation: Problem #40 fails for some subpolynomial $g(N)\to\infty$ if and only if there exists an integer $\lambda\ge 1$ and an infinite set $A\subset\mathbb N$ with $A\in B_2[\lambda]$ and \[ |A\cap[1,N]|\gg_{\varepsilon} N^{1/2-\varepsilon} \qquad\text{for every }\varepsilon>0. \]
• Round 4 one-way link: a positive answer to Problem #39 implies a negative answer to Problem #40 for some subpolynomial $g$.
• Round 4 gap: the converse direction remained open; in particular, it was unclear whether the Round 4 $B_2[\lambda]$-core was essentially equivalent to the Sidon problem.

3) NEW INSIGHT / TOOL (ROUND-5)

The new ingredient is a recent theorem of Reiher--Rödl--Schacht on Ramsey-type generalised Sidon sets. Specialised to $k=2$, it yields the following.

Theorem thm:RRS is new relative to the previous rounds. It gives a bounded-representation set that is locally very Sidon-rich, yet whose finite colourings always contain a colour class with repeated two-sums.

4) ATTACK PLAN (ROUND-5)

The exact gap left after Round 4 was:

Can the remaining $B_2[\lambda]$-core be reduced to Problem #39 by converting bounded-representation sets into Sidon sets?

Round 5 attacks this by testing two precise reduction principles.

1. $P1$ For each fixed $\lambda\ge 2$, every $B_2[\lambda]$ set is a finite union of Sidon sets.
2. $P2$ There exists $\delta>0$ such that every set $X\subset\mathbb N$ with the local property \[ \forall\text{ finite }Y\subset X\ \exists\text{ Sidon }Z\subset Y\text{ with }|Z|\ge \delta |Y| \] is a finite union of Sidon sets.

If either principle were true, then the Round 4 $B_2[\lambda]$-core would be much closer to Problem #39. I will prove that both are false, with $P2$ already false for $\delta=1/4$. This rules out an entire class of natural local-to-global reduction strategies.

5) WORK (ROUND-5)

5.1. Notation.

For $S\subset\mathbb N$ let \[ \rho_{S,2}(n):=|\{(a,b)\in S^2:a\le b,\ a+b=n\}|. \] Thus $S$ is Sidon exactly when $\sup_n \rho_{S,2}(n)\le 1$, and $S\in B_2[\ell]$ exactly when $\sup_n \rho_{S,2}(n)\le \ell$.

5.2. A structural obstruction.

5.3. Two false reduction principles.

Proposition Proposition immediately yields the following.

5.4. Consequence for Problem #40.

Round 4 identified the unresolved core of Problem #40 as the possible existence of a dense $B_2[\lambda]$ set with counting function $N^{1/2-o(1)}$. Corollaries Corollary (Failure of finite Sidon decomposition) and Corollary (Failure of the Alon--Erdős local-to-global principle) show that this core cannot be collapsed to Problem #39 by either of the two most obvious mechanisms:

1. (i) decomposing bounded-representation sets into finitely many Sidon pieces;
2. (ii) proving only a local positive-density Sidon extraction statement for finite subsets.

This yields the following corrected structural formulation.

6) ADVERSARIAL VERIFICATION

• Compatibility of notation: The external theorem uses $\rho_{X,2}(n)$ to count nondecreasing representations, which is exactly the standard $B_2[\ell]$ convention used in the previous rounds after converting from ordered counts.

• Colouring vs covering: In Proposition Proposition(b), the sets $S_1,\dots,S_r$ may overlap. Choosing for each $x\in X$ a single colour $c(x)$ produces colour classes $X_i\subset S_i$, which is enough because subsets of Sidon sets are Sidon.

• Local property is genuinely strong: Corollary Corollary (Failure of the Alon--Erdős local-to-global principle) does not merely say that some finite subsets of $X$ contain large Sidon subsets; it says every finite subset does, with a fixed proportion $1/4$.

• No density conclusion is being smuggled in: Theorem thm:RRS says nothing about $|X\cap[1,N]|$, so Round 5 does not solve the remaining density question of Problem #40. It only rules out two natural ways of reducing that density question to the Sidon case.

• Could there still be some deeper equivalence with Problem #39? Yes. Round 5 does not exclude all possible future reductions. It excludes only reductions based on finite Sidon decomposition or on the local positive-density extraction principle above.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 5 gives a substantive structural advance beyond Round 4:

The unresolved subpolynomial sector of Problem #40 is not presently reducible to the Sidon problem by the two most natural local-to-global mechanisms. In fact, for every $\ell\ge 2$ there exists an infinite $B_2[\ell]$ set that is locally Sidon-rich (every finite subset contains a Sidon subset of size at least one quarter) but is nevertheless not a finite union of Sidon sets.

Thus the remaining core of Problem #40 must be treated as a genuinely generalised Sidon problem, not merely as Problem #39 in disguise.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 76%

9) REFERENCES

1. T. F. Bloom (ed.), Erdős Problem #39 and Erdős Problem #40, Erdős Problems website, accessed 2026-03-07.
2. C. Reiher, V. Rödl, and M. Schacht, Ramsey-type problems for generalised Sidon sets, arXiv:2409.04809v3 $2025$, to appear in Proceedings of the American Mathematical Society.

OBJECTIVE AND SOURCE REVIEW

Erdős #40; independent attempt, 2026-09-23. Which functions $g(N)\to\infty$ force unbounded two-sum representation counts from $A(N)\gg\sqrt N/g(N)$? I read the complete supplied 40.tex, including its distinction between local Sidon extraction and finite Sidon decomposition. The cited Reiher--Rödl--Schacht paper was located at its primary arXiv page. Here I give an elementary quantitative extraction bound and explicitly measure its loss; I do not assume a decomposition theorem.

WORK: A FINITE ALTERATION BOUND

Let $S$ contain $n$ integers and have at most $\lambda$ unordered representations of any sum, with repetitions allowed. For $n\ge8\lambda$, $S$ contains a Sidon subset of size at least \[ \frac{n^{2/3}}{4\lambda^{1/3}}. \] For each sum, join every two distinct unordered representations to form a forbidden configuration. Two distinct representations cannot share an element unless they are identical. Hence configurations have either four distinct elements or three distinct elements of the form $a+c=2b$. The total number of representation pairs is at most \[ \sum_s\binom{r(s)}2\le\frac{\lambda-1}2\sum_s r(s) \le\frac{\lambda n^2}{2}. \] The three-element configurations number at most $\lambda n$, since their middle element determines a diagonal representation and there are at most $\lambda-1$ alternatives. Select each element independently with probability $p=(8\lambda n)^{-1/3}$. Then delete one vertex from each retained forbidden configuration. The expected size left is at least \[ pn-\frac{\lambda n^2p^4}{2}-\lambda np^3 =\frac{15}{16}pn-\frac18\ge\frac12pn =\frac{n^{2/3}}{4\lambda^{1/3}}. \] The displayed inequality uses $pn\ge1$, which follows from $n\ge8\lambda$. Some realization therefore has the claimed size. Removing all configurations makes every unordered sum unique.

ADVERSARIAL VERIFICATION AND REMAINING GAP

Diagonal representations require three-vertex configurations and cannot be hidden in a four-uniform hypergraph. The separate $\lambda np^3$ term handles them. With $n=A(N)=N^{1/2-o(1)}$, this lemma gives only $N^{1/3-o(1)}$ points at each cutoff. Further, the extracted subsets at different cutoffs need not be nested. Thus this standard alteration argument neither constructs a single infinite dense Sidon set nor resolves the near-square-root $B_2[\lambda]$ problem. It identifies two separate missing requirements: density preservation and compatibility across scales.

SOURCES CHECKED

Complete local source: gpt_pro_5.4/40.tex. Official statement checked through its indexed page, https://www.erdosproblems.com/40. Reiher--Rödl--Schacht primary abstract: https://arxiv.org/abs/2409.04809. No external theorem is needed in the proof above, and no literature novelty is claimed.

FINAL

UNRESOLVED. A self-contained extraction estimate is verified, with an explicit exponent loss that prevents it from settling the original problem.

COMPLETION ESTIMATE

Subjective progress, not a probability or a measured fraction of a proof. COMPLETION: 8%

Erdős Problem #40 --- Round 2

1) ROUND-2 OBJECTIVE

Path (B): counterexample / disproof for an infinite family of functions $g$.

Round 1 isolated that first-moment bounds are far too weak in the regime $|A\cap[1,N]|\asymp \sqrt N/g(N)$ with $g(N)\to\infty$, and suggested that any negative answer should come from building a set $A$ with uniformly bounded additive representation counts (a "$B_2[O(1)]$" construction) while keeping the required lower bound on $|A\cap[1,N]|$.

In this round I implement that disproof track for a large explicit class of growth functions $g$, using a theorem of Erdős--Rényi on infinite $B_2[g]$ sequences.

2) ROUND-1 FOUNDATION USED

I use the following vetted Round 1 items.

• Lemma 40.1: For $m=|A\cap[1,N]|$, some $n\le 2N$ has at least $m^2/(2N-1)$ ordered representations using summands $\le N$.
• Lemma 40.2: If $(1_A\!\ast\!1_A)(n)\le R$ for all $n$, then $|A\cap[1,N]|<\sqrt{2RN}$ for all $N$.
• Round 1 gap: no construction was given that meets the hypothesis $|A\cap[1,N]|\gg \sqrt N/g(N)$ (for all large $N$) while keeping $(1_A\!\ast\!1_A)(n)$ bounded.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a classical probabilistic-existence theorem (quoted in a standard survey) constructing infinite sets with bounded two-term representation function and prescribed polynomial growth.

External Theorem (Erdős--Rényi, 1960; quoted as Theorem 8.2 in Sárközy--Sós). For every $\varepsilon>0$ there exists an integer $\lambda=\lambda(\varepsilon)$ and an infinite set $A\subset\mathbb N$ such that:

1. (i) $A$ is a $B_2[\lambda]$ set: every $n\in\mathbb N$ has at most $\lambda$ solutions $a\le a'$ with $a,a'\in A$ to $a+a'=n$.
2. (ii) (Polynomial density) There exists $N_0(\varepsilon)$ such that for all $N\ge N_0(\varepsilon)$, \[|A\cap[1,N]|>N^{\frac12-\varepsilon}.\]

4) ATTACK PLAN (ROUND-2)

• Gap to close from Round 1: exhibit any divergent $g(N)$ for which the implication in Problem 40 fails.
• Plan: Fix $\varepsilon>0$ and take $g(N)=N^{\varepsilon}$. Apply the external theorem above to obtain a set $A$ with $|A\cap[1,N]|\ge N^{1/2-\varepsilon}$ for all large $N$. Convert the $B_2[\lambda]$ property into a uniform bound on the ordered convolution $(1_A\ast 1_A)(n)$, showing $\limsup_n (1_A\ast 1_A)(n)<\infty$.
• Extension: the same $A$ also disproves the implication for any $g$ that eventually dominates $N^{\varepsilon}$ (since the required lower bound $\sqrt N/g(N)$ is then even weaker).

5) WORK (ROUND-2)

5.1. From $B_2[\lambda]$ to bounded ordered convolution.

For a set $A\subset\mathbb N$, write \[r_A(n):=(1_A\ast 1_A)(n)=|\{(a,b)\in A\times A: a+b=n\}|\] for the ordered two-sum representation function. Also write \[R_A(n):=|\{(a,a')\in A\times A: a\le a',\ a+a'=n\}|\] for the nondecreasing (unordered) representation count.

5.2. A disproof for $g(N)=N^{\varepsilon}$.

Fix any $\varepsilon>0$ and set \[g(N):=N^{\varepsilon},\qquad N\in\mathbb N. \] Then $g(N)\to\infty$. Let $A\subset\mathbb N$ be the set produced by the Erdős--Rényi theorem in §3, with the corresponding $\lambda=\lambda(\varepsilon)$.

5.3. A necessary restriction on $g$.

The same argument yields an immediate corollary clarifying where a positive answer might still live.

6) ADVERSARIAL VERIFICATION

• Ordered vs unordered counts: The only conversion step is Lemma 5.1. The map $(a,b)\mapsto(\min\{a,b\},\max\{a,b\})$ has fibers of size $\le 2$, so $r_A(n)\le 2R_A(n)$ is tight and correct.
• Quantifiers in the hypothesis: The Erdős--Rényi theorem gives a lower bound $|A\cap[1,N]|>N^{1/2-\varepsilon}$ for all $N\ge N_0(\varepsilon)$, matching the "$\forall N\ge N_0$" hypothesis in Problem 40. Taking $c=1$ is valid.
• $g(N)\to\infty$: For $g(N)=N^{\varepsilon}$ this is immediate.
• Does boundedness hold for all $n$ or only large $n$? The $B_2[\lambda]$ property is for all $n\in\mathbb N$, so $\sup_n (1_A\ast 1_A)(n)\le 2\lambda$ holds globally. This certainly implies the failure of $\limsup_n(1_A\ast 1_A)(n)=\infty$.
• Interaction with Round 1 Lemma 40.2: Lemma 40.2 gives $|A\cap[1,N]|\ll \sqrt N$ under bounded representation. Our constructed set has $|A\cap[1,N]|\asymp N^{1/2-\varepsilon}$, which is consistent.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 gives an explicit infinite family of divergent functions for which the implication in Problem 40 fails:

for every fixed $\varepsilon>0$, taking $g(N)=N^{\varepsilon}$ (or any $g$ eventually $\ge N^{\varepsilon}$) does not force $\limsup_n (1_A\ast 1_A)(n)=\infty$.

The remaining open regime is when $g(N)$ is subpolynomial ($g(N)=N^{o(1)}$), e.g. $g(N)=(\log N)^C$ or $g(N)=\log\log N$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 40%

9) REFERENCES

1. P. Erdős and A. Rényi, Additive properties of random sequences of positive integers, Acta Arith. 6 $1960$, 83--110.
2. A. Sárközy and V. T. Sós, On additive representation functions, in: The Mathematics of Paul Erdős I (R. L. Graham et al., eds.), Springer, 1997. (See Theorem 8.2 therein for the Erdős--Rényi construction used above.)

Erdős Problem #40 --- Round 3

1) ROUND-3 OBJECTIVE

Path (C): fatal obstruction / minimal correction.

Round 2 produced a rigorous counterexample family showing that the implication in Problem #40 fails whenever the density parameter $g(N)$ is polynomially large (e.g. $g(N)=N^\varepsilon$). In Round 3, the most promising way to finish the classification as far as current progress allows is therefore not to chase further counterexamples ad hoc, but to:

• isolate a clean structural equivalence between "failure of Problem #40 for $g$" and the existence of a sufficiently dense bounded representation ($B_2[\lambda]$) set;
• deduce from Round 2 that no $g$ with a positive power growth rate can work;
• state the resulting minimal corrected form: any candidate $g$ must be subpolynomial ($g(N)=N^{o(1)}$).

This closes a conceptual gap left after Round 2: it identifies precisely what remains open after the polynomial counterexamples.

2) ROUND-1/2 FOUNDATION USED

I rely on the following Round 1/2 items without re-proving them.

• Round 1 Lemma 40.2: If $(1_A\!\ast\!1_A)(n)\le R$ for all $n$, then $|A\cap[1,N]|<\sqrt{2RN}$ for all $N$.
• Round 2 Lemma 5.1: If $A\in B_2[\lambda]$ (unordered representations $\le\lambda$) then the ordered representation function satisfies $(1_A\ast 1_A)(n)\le 2\lambda$ for all $n$.
• Round 2 Proposition 5.2 and Corollary 5.3: for every fixed $\varepsilon>0$ the implication in Problem #40 fails for $g(N)=N^{\varepsilon}$ (indeed, for every $g$ with $g(N)\ge N^{\varepsilon}$ eventually), by an Erdős--Rényi $B_2[\lambda]$ construction.

3) NEW INSIGHT / TOOL (ROUND-3)

The new ingredient is a reduction that turns Problem #40 into an existence/nonexistence statement about dense infinite $B_2[\lambda]$ sets, plus a monotonicity principle.

4) ATTACK PLAN (ROUND-3)

• Gap after Round 2: we had a family of counterexamples, but no structural characterisation of what a positive answer would have to exclude.
• Round 3 goal: use Lemma lem:reduction and Lemma lem:mono to:
  1. reformulate Problem #40 as a question about how dense a bounded-representation ($B_2[\lambda]$) set can be while still satisfying a uniform lower bound at all large $N$;
  2. upgrade the Round 2 corollary into a clean "no polynomial $g$ can work" statement.
• Why this helps: it isolates the remaining open regime as a single extremal question about dense infinite $B_2[\lambda]$ sets, clarifying what must be improved to settle the problem.

5) WORK (ROUND-3)

5.1. A clean necessary condition on $g$.

Define the (asymptotic) power-growth exponent of $g$ by \[\alpha(g):=\liminf_{N\to\infty} \frac{\log g(N)}{\log N}\in[0,\infty].\] Note that $\alpha(g)>0$ is equivalent to: there exists $\varepsilon>0$ such that $g(N)\ge N^{\varepsilon}$ for all sufficiently large $N$.

5.2. Minimal corrected statement and remaining open regime.

Combining Lemma lem:mono, Lemma lem:reduction, and Theorem thm:polyfails yields the following sharp "frontier" formulation.

6) ADVERSARIAL VERIFICATION

• Quantifiers in Lemma lem:reduction: Problem #40 assumes $|A\cap[1,N]|\gg \sqrt N/g(N)$ for all sufficiently large $N$. This is exactly the statement that the ratio $g(N)|A\cap[1,N]|/\sqrt N$ has positive liminf. Using limsup or limsup only would be incorrect; the proof uses the liminf version.

• Bounded convolution $\Rightarrow B_2[\lambda]$: If $r_A(n)\le R$ for all $n$, then unordered representations satisfy $R_A(n)\le r_A(n)\le R$, so $A\in B_2[R]$ is valid.

• Monotonicity direction: The direction in Lemma lem:mono(a) is the one actually used: weakening the hypothesis (larger $g$) cannot repair a counterexample. The contrapositive (b) is consistent.

• No hidden dependence on $N$: In Theorem thm:polyfails we use a fixed $\varepsilon>0$ extracted from $\alpha(g)>0$; this matches the Round 2 construction which provides a single fixed $B_2[\lambda(\varepsilon)]$ set.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 3 upgrades Round 2 from a family of counterexamples to a structural description:

Problem #40 is false for every $g(N)\to\infty$ with positive power-growth rate $\alpha(g)>0$ (in particular for every polynomially growing $g$), and the only remaining possible regime is subpolynomial $g(N)=N^{o(1)}$.

The remaining core question is equivalent to understanding how dense an infinite bounded-representation $B_2[\lambda]$ set can be while maintaining a uniform lower bound at all large $N$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

1. P. Erdős and A. Rényi, Additive properties of random sequences of positive integers, Acta Arith. 6 $1960$, 83--110.
2. A. Sárközy and V. T. Sós, On additive representation functions, in: The Mathematics of Paul Erdős I (R. L. Graham et al., eds.), Springer, 1997. (See Theorem 8.2 for the Erdős--Rényi construction of dense $B_2[\lambda]$ sequences.)
3. T. F. Bloom (ed.), Erdős Problem #40 (problem statement and status), Erdős Problems website, accessed 2026-01-20.