Erdős Problem #328
Status Solved · erdosproblems.comLLM status Solved from source status
Erdős problems openaigpt 6 astra ultra 100% cataloguedSolvedSolvedStatement
Suppose $A\subseteq\mathbb N$ and $C>0$ satisfy \[r_A(n)=(1_A*1_A)(n)=|\{(a,b)\in A^2:a+b=n\}|\le C \] for every $n$. Must there be a finite partition $A=A_1\cup\cdots\cup A_t$, with $t$ depending only on $C$, such that $r_{A_i}(n)<C$ for every $i,n$? Convolution counts ordered pairs; this convention is essential to the example below.
Restatement from Math-5581-A1 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 1
GPT 6 Astra Ultra attempt on Math-5581
Erdős Problem #328: lowering the convolution bound by partitioning
Elementary counterexample to the stated universal assertion, 24 September 2026.1) Statement and convention
Suppose $A\subseteq\mathbb N$ and $C>0$ satisfy \[r_A(n)=(1_A*1_A)(n)=|\{(a,b)\in A^2:a+b=n\}|\le C \] for every $n$. Must there be a finite partition $A=A_1\cup\cdots\cup A_t$, with $t$ depending only on $C$, such that $r_{A_i}(n)<C$ for every $i,n$? Convolution counts ordered pairs; this convention is essential to the example below.2) A bounded-representation set
Take $C=2$ and $A=\{3^j:j\ge0\}$. If $i\ne j$, the sum $3^i+3^j$ has base-three digits 1 in exactly positions $i,j$. If $i=j$, the sum is $2\cdot3^i$, with a single digit 2. These expansions have no carries and are unique. Hence every sum of two elements of $A$ has a unique unordered representation. Its number of ordered representations is two when the elements differ and one when they agree. In particular $r_A(n)\le2$ for all $n$.3) Every admissible part would be a singleton
If a part $B\subseteq A$ contains distinct $a,b$, then both $(a,b)$ and $(b,a)$ contribute to $r_B(a+b)$, so $r_B(a+b)\ge2$. Therefore $r_B(n)<2$ for every $n$ forces $|B|\le1$. A finite union of such parts cannot cover infinite $A$.Even the finite version has no bound depending only on $C$: the set $\{3^0,\ldots,3^{m-1}\}$ satisfies the same hypothesis with $C=2$ but requires at least $m$ parts. Thus the asserted uniform partition theorem fails in both the infinite and finite settings.
4) Scope of the resolution
SOLVED in the negative for the literal universal assertion. The counterexample verifies every hypothesis and excludes every finite partition, even when its size is allowed to depend on $A$. No assertion for an individually prescribed $C>2$ is proved here. The source records the much stronger Nešetřil--Rödl result covering the substantive larger bounds; that theorem is not reconstructed or presented as an elementary consequence of this example. This writeup resolves the question as worded, which permits $C=2$.Source: https://www.erdosproblems.com/328, checked 23 September 2026. The problem is attributed to Erdős and Newman. No novelty or independent Lean verification is claimed.
The estimate refers to disproving the stated assertion, not to proving the stronger all-$C$ theorem.