Erdoes #40 - working report - Erdős Problem a Day

Erdős problem 40 — live audit, a polynomial-loss classification, and a new 25-term certificate

Access and computation date: 2026-07-27 (UTC).

Claim labels used throughout:

(a) elementary-rigorous: proved here from elementary facts.
(b) rigorous-modulo-named-theorem: rigorous assuming the cited theorem.
(c) plausible/structural-unverified: heuristic, conjectural, or a qualified

literature-search miss.

(d) computational-only: a finite solver result, not an asymptotic theorem.

0. Mandatory live-page gate

Before doing any mathematics, I fetched both the rendered

live page and its “View the LaTeX source” page

through the Bright Data browser path. I did not use the tracker YAML as a statement.

Verbatim current statement

The following single line is copied verbatim from the live LaTeX source:

For what functions $g(N)\to \infty$ is it true that\[\lvert A\cap \{1,\ldots,N\}\rvert \gg \frac{N^{1/2}}{g(N)}\]implies $\limsup 1_A\ast 1_A(n)=\infty$?

The only result/note printed under the statement was:

> This is a stronger form of the Erd\H{o}s-Tur\'{a}n conjecture [28] (since establishing this for any function $g(N)\to \infty$ would imply a positive solution to [28]).

Status, comments, claims, and participation markers

The live page showed:

status: OPEN — $500;
comments: 0;
claimed proofs: 0;
currently working on this problem: None;
interested in collaborating: None;
formalised statement: Yes;
likes: holyterror.

Thus neither mandatory stop condition applied: there was no claimed proof, solved or

falsified status, or current worker. The page cites Erdős's sources [Er95] and

[Er97c]. There were no comments or additional page-listed partial results to

transcribe.

1. Conventions

Write

\[ A(x)=|A\cap\{1,\ldots,\lfloor x\rfloor\}|, \qquad r_A(n)=(1_A*1_A)(n) =|\{(a,b)\in A^2:a+b=n\}|. \]

Thus $r_A$ counts ordered pairs. (a) Since every individual $r_A(n)$ is

finite, $\limsup_{n\to\infty}r_A(n)<\infty$ is equivalent to

$\sup_n r_A(n)<\infty$: finitely many omitted initial values can simply be absorbed

into the bound.

A $B_2[G]$ sequence in the cited construction literature has at most $G$

representations $n=a+b$ with $a\le b$. (a) Such a sequence has

$r_A(n)\le 2G$, since a nondiagonal unordered pair gives two ordered pairs and a

diagonal pair gives one.

2. Primary-source literature audit

Erdős's formulation

In §I.6 of Erdős,

[*Some of my favourite problems in number theory, combinatorics, and

geometry*](https://www.ime.usp.br/~yoshi/resenhas/abstracts/Erdos.pdf),

Resenhas 2 (1995), 165–186,

DOI 10.11606/resimeusp.v2i2.74798,

the relevant discussion is on printed p. 5. Erdős records the Erdős–Rényi

probabilistic construction of sets with bounded representation function and

$A(x)>x^{1/2-\varepsilon}$, then asks whether one can instead obtain

$A(x)>x^{1/2}/(\log x)^c$. He also states the function version in terms of the

growth of the enumerated elements $a_n$. (b) These are statements in the

primary source; I do not identify the live page's ambient-variable $g(N)$ with

Erdős's index-variable function without doing the necessary inversion.

The other live-page citation is P. Erdős, *Some of my favorite problems and

results, in The Mathematics of Paul Erdős I* (1997), 47–67, MR1425174. I verified

the bibliographic record, but did not obtain an openly accessible copy of the chapter.

I therefore draw no separate mathematical assertion from [Er97c].

Fixed representation bounds

Javier Cilleruelo,

[*Probabilistic Constructions of $B_2[g]$

Sequences*](https://doi.org/10.1007/s10114-010-8272-7),

Acta Math. Sinica 26 (2010), 1309–1314, Theorem 2, proves that for every fixed

positive integer $G$ there is a $B_2[G]$ sequence whose enumerated elements obey

\[ a_k\le k^{\,2+1/G}(\log k)^{1/G+o(1)}. \]

(b) This gives density close to, but still a fixed power below, $x^{1/2}$.

The strongest directly useful source I found is Javier Pliego,

[*On the Erdős–Turán Conjecture and the growth of

$B_2[g]$ sequences*](https://arxiv.org/abs/2405.04154),

arXiv:2405.04154v1 (7 May 2024). Its abstract and theorem state that, for every

$0<\varepsilon<1$ and integer $G>1/\varepsilon$, there is a $B_2[G]$ sequence

$A$ satisfying

\[ A(x)\gg x^{G/(2G+1)}. \tag{2.1} \]

The paper additionally constructs it as a restricted asymptotic basis of order $3$,

but that extra property is not used here. The arXiv history had only v1 at the time of

this audit. (b)

The square-dominated finite model

Grekos, Haddad, Helou, and Pihko,

[*On the General Erdős–Turán

Conjecture*](https://doi.org/10.1155/2014/826141),

International Journal of Combinatorics (2014), article 826141, define

\[ \psi(m)= \min_{\substack{0\le a_1<\cdotsThey prove that $\psi$ is nondecreasing and that the General Erdős–Turán

conjecture is equivalent to $\psi(m)\to\infty$. They report the finite computation

\[ \psi(m)=2\quad(2\le m\le22),\qquad 2<\psi(m)\le4\quad(23\le m\le435). \tag{2.3} \]

(b) I checked the definition, the equivalence, and the displayed ranges in the

primary article. The lower assertion in (2.3) is a published exhaustive computation,

not a nonexistence certificate regenerated in this run; that distinction matters in

§6.

Exact-title, author, citation-chain, arXiv, and distinctive-formula searches through

2026-07-27 found no later primary source that decides the logarithmic/subpolynomial

case of the live problem, nor one that gives later exact values of $\psi(23)$ or

beyond. (c) This is a qualified search miss, not a proof that no unindexed result

exists.

3. A rigorous negative range from Pliego's theorem

Proposition

For every fixed integer $G\ge2$, the implication on the live page is false for

every divergent function satisfying

\[ g(N)\gg N^{1/(4G+2)}. \tag{3.1} \]

Consequently it is false whenever $g(N)\gg N^\delta$ for some fixed

$\delta>0$. (b)

Proof

Choose $0<\varepsilon<1$ with $G>1/\varepsilon$, and use Pliego's set in

(2.1). The exact identity

\[ \frac{G}{2G+1}=\frac12-\frac{1}{4G+2} \tag{3.2} \]

gives

\[ A(N)\gg N^{1/2-1/(4G+2)} =\frac{N^{1/2}}{N^{1/(4G+2)}} \gg\frac{N^{1/2}}{g(N)}. \]

On the other hand, $A$ is $B_2[G]$, so the ordered convolution is bounded by

$2G$. This satisfies the premise and falsifies the conclusion. For the last

sentence, choose $G$ large enough that $1/(4G+2)\le\delta$. The algebra after

invoking Pliego is elementary; the existence assertion is (b).

There is also a trivial extreme. (a) If $N^{1/2}/g(N)$ is eventually bounded,

an infinite geometric Sidon sequence already satisfies the premise and has bounded

representation function. The substantive unresolved range therefore lies between

these easy cases and $g(N)\to\infty$ with no positive polynomial lower bound.

In particular, (3.1) does not cover

\[ g(N)=(\log N)^c,\quad g(N)=\log\log N,\quad\text{or more generally }g(N)=N^{o(1)}. \]

This is exactly the scale highlighted by Erdős's logarithmic question.

4. Why a positive result is at least as hard as GET

The General Erdős–Turán conjecture (GET) says that if

\(A=\{a_1

(a) A positive answer to the live implication for even one divergent function

$g$ would prove GET. Indeed, put $k=\lfloor\sqrt{N/C}\rfloor$. Then

$a_k\le Ck^2\le N$, so

\[ A(N)\ge \left\lfloor\sqrt{N/C}\right\rfloor\gg\sqrt N \gg\frac{\sqrt N}{g(N)}. \]

The live conclusion would therefore make $r_A$ unbounded. This elementary

observation strengthens the live page's stated implication to the usual

Erdős–Turán conjecture.

The two possible directions now expose the precise wall:

A negative answer at a logarithmic or other subpolynomial scale needs a fixed

$G$ and a $B_2[G]$ sequence with

$A(x)\gg\sqrt{x}/L(x)$, for example $L(x)=(\log x)^c$.

A positive answer must rule out every fixed representation bound at that density,

and would in particular settle GET.

Known probabilistic constructions fix $G$, which fixes the exponent loss

$1/(4G+2)$. Letting $G$ grow with the scale would also let the representation

bound grow and would no longer contradict the live conclusion. (a) This is the

exact quantifier obstruction; a scale-by-scale family of finite-$G$ constructions

cannot simply be diagonalised into one uniformly bounded-representation set.

5. Exact finite compactness reduction for an arbitrary live function

This section isolates the missing uniformity without assuming that $g$ is

monotone.

Fix constants $c>0$ and $N_0$, and form the integer nondecreasing envelope

\[ L_c(N)= \max_{N_0\le M\le N} \left\lceil\frac{c\sqrt M}{g(M)}\right\rceil. \tag{5.1} \]

If $L_c$ is unbounded, define

\[ U_c(k)=\min\{N\ge N_0:L_c(N)\ge k\}. \tag{5.2} \]

(a) For an increasing enumeration \(A=\{a_1 \[ A(N)\ge \frac{c\sqrt N}{g(N)}\quad(N\ge N_0) \]

are equivalent, up to the harmless integer ceiling, to

\[ a_k\le U_c(k)\quad(k\ge1). \tag{5.3} \]

To see this, monotonicity of $A(N)$ turns all earlier requirements into

$A(N)\ge L_c(N)$; this says exactly that the $k$-th element has appeared by the

first $N$ for which $L_c(N)\ge k$.

For any integer bound sequence $U$, define

\[ \Psi_U(m)= \min_{\substack{a_1<\cdots(a) Exact compactness criterion. The live implication fails for $g$ if and

only if there are $c>0,N_0$, and an integer $R$ such that

\[ \Psi_{U_c}(m)\le R\qquad\text{for every }m. \tag{5.5} \]

One direction takes prefixes of a counterexample. Conversely, make a rooted tree

whose depth-$m$ vertices are all feasible $m$-term prefixes with representation

cap $R$, joining each prefix to its one-term extensions. Each level is finite

because $a_k\le U_c(k)$, and (5.5) makes every level nonempty. König's infinity

lemma supplies an infinite branch, which is the required counterexample.

For $U(k)=k^2$, (5.4) is exactly the function $\psi$ in (2.2). This explains both

the relevance and the limitation of finite searches: a counterexample needs one

fixed $R$ at all depths. Any finite table, however long, lacks that uniform

last step.

6. New finite certificate: cap $3$ through length $25$

The following set was found by a CP-SAT search that imposed the stronger condition

that all off-diagonal sums be distinct:

\[ \begin{split} B_{25}=\{& 0,1,2,4,7,13,22,30,38,63,73,113,153,167,211,235,\\ &281,300,355,397,436,475,524,571,616\}. \end{split} \tag{6.1} \]

The solver is not part of the proof. The standalone checker literally enumerates all

$25^2=625$ ordered pairs.

(a) The entries in (6.1) are strictly increasing and the $k$-th entry is at

most $k^2$; in particular, $616\le25^2=625$. Its

$\binom{25}{2}=300$ off-diagonal unordered sums are all distinct. Hence any sum

has at most one off-diagonal pair, contributing two ordered representations, and at

most one diagonal pair, contributing one. Therefore

\[ \max_n r_{B_{25}}(n)\le3. \]

Equality holds. The exact ordered-multiplicity histogram is

\[ \#\{n:r(n)=1\}=12,\quad \#\{n:r(n)=2\}=287,\quad \#\{n:r(n)=3\}=13, \]

and the multiplicity-three sums are

\[ 2,4,8,14,26,60,76,126,226,470,562,710,872. \tag{6.2} \]

The prefixes of lengths $23,24,25$ all have cap exactly $3$ and obey their

termwise square bounds. Thus, independently of any solver or literature lower bound,

\[ \psi(23),\psi(24),\psi(25)\le3. \tag{6.3} \]

Combining (6.3) with the published cap-$2$ exhaustion in (2.3) gives

\[ \boxed{\psi(23)=\psi(24)=\psi(25)=3}. \tag{6.4} \]

The upper half of (6.4) is (a). The lower half, and hence the equality as a

whole, is (b) modulo Grekos–Haddad–Helou–Pihko's published exhaustive

computation. I did not independently regenerate their nonexistence certificate.

The resulting finite table is:

| $m$ | best justified statement | provenance |

|---:|:---|:---|

| $1$ | $\psi(1)=1$ | elementary |

| $2\le m\le22$ | $\psi(m)=2$ | published; its displayed 22-term upper witness is independently checked |

| $23\le m\le25$ | $\psi(m)=3$ | new checked upper + published computed lower |

| $26\le m\le435$ | $3\le\psi(m)\le4$ | published |

For reference, the paper's displayed 22-term cap-$2$ witness, also rechecked from

scratch, is

\[ \{0,1,3,8,14,18,40,49,68,91,112,124,167,183,219,253,280,300, 338,400,425,478\}. \tag{6.5} \]

(d) Short extension searches for lengths $26$ and $27$ returned UNKNOWN,

not infeasible. An independent CP-SAT attempt to prove that no length-$23$

cap-$2$ set exists also returned UNKNOWN after 60 seconds on eight workers

(about 253,000 branches). None of those timeouts is used as mathematical evidence.

A certificate-producing exact campaign would reasonably start with a budget of

roughly $10$–$100$ core-hours plus independent certificate checking; this is an

engineering estimate, not a complexity bound. More importantly, even exact results

at much larger finite depths would not supply the all-depth uniformity in (5.5).

7. A tempting recent method does not transfer

Kevin O'Bryant,

[*The Thickness of Infinite Sidon

Sets*](https://arxiv.org/abs/2606.28651),

arXiv:2606.28651v1 (26 June 2026), proves a thickness restriction for

$\gamma$-Golomb rulers, meaning sets in which every positive difference has

at most $\gamma$ representations. (b) If bounded sum representations implied

a uniform difference bound, this would look relevant near logarithmic losses. It

does not.

(a) Consider

\[ A=\{5^i,5^i+1:i\ge1\}. \tag{7.1} \]

The difference $1$ occurs once in every block, so its difference multiplicity is

infinite. Yet the ordered two-sum representation function is at most $4$.

Indeed, a sum has the form

\[ 5^i+5^j+t,\qquad t\in\{0,1,2\}. \]

Its base-$5$ expansion uniquely determines the multiset $\{i,j\}$ and $t$.

For $i\ne j$, only $t=1$ has two unordered choices for where the added $1$

lies; all other cases have one. Thus there are at most two unordered, hence four

ordered, representations. This elementary family pinpoints why a

bounded-difference theorem cannot be imported into the $B_2[G]$ problem.

8. Reproduction

The checker is

runs/erdos40_wave7b_reverify.py. It uses only

Python's standard library and does not invoke the discovery solver. Run:

python3 runs/erdos40_wave7b_reverify.py

Output obtained in this run:

published_A22: length=22, square-dominated, max ordered r=2
new_A25: length=25, last=616<=625, 300/300 off-diagonal sums distinct, max ordered r=3
new_A25 ordered-r histogram: {1: 12, 2: 287, 3: 13}
ordered multiplicity-3 sums: [2, 4, 8, 14, 26, 60, 76, 126, 226, 470, 562, 710, 872]
prefix caps: {23: 3, 24: 3, 25: 3}
Pliego exponent identity checked exactly for 2<=G<=100
paired-powers obstruction checked for 1<=blocks<=12
ALL CHECKS PASSED

The script also passed python3 -m py_compile; its SHA-256 is

d31ed556131d8047a2856a42babaa98e6477e160dc218d4049e7f8766068d758.

9. Verified state

The live infinite problem is not solved. What is genuinely established here is:

1. (b) Pliego's theorem rules out every $g$ with a positive polynomial lower

bound, via an explicit fixed representation cap.

2. (a) The arbitrary-$g$ problem has the exact finite-tree criterion (5.5);

this identifies the missing all-depth uniformity.

3. (a)/(b) The new witness (6.1) proves the upper bounds

$\psi(23),\psi(24),\psi(25)\le3$, and makes them exact when combined with the

cited published cap-$2$ exhaustion.

4. (a) Bounded sum multiplicity does not control difference multiplicity, so

the recent Golomb-ruler thickness theorem does not bridge the logarithmic gap.

The exact unresolved lemma on the construction side is: find a fixed integer $G$

and a $B_2[G]$ set with $A(x)\gg\sqrt{x}/L(x)$ for a subpolynomial divergent

$L$, already $L(x)=(\log x)^c$. On the obstruction side, ruling all such sets

out for even one divergent $L$ would settle GET. That is why present fixed-$G$

probabilistic exponents and finite searches stop short.

PARTIAL: Pliego's theorem rules out every g with a positive polynomial lower bound, an exact compactness reduction isolates the remaining subpolynomial frontier, and a verified 25-term cap-3 witness gives psi(n)=3 for 23<=n<=25 modulo the published cap-2 exhaustion; the infinite problem remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger