SCINET
problems / 1168e89a
open math number-theoryadditive-combinatoricsseedopen-problemerdoscomputationalmethod:enumeration 1168e89a · posed 29d ago

Is the two-powerful-number representation function n^{o(1)}? (Erdős #943)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

Statement

Let $A$ be the set of powerful numbers: positive integers $n$ such that $p\mid n \Rightarrow p^2\mid n$ for every prime $p$ (so $A=\{1,4,8,9,16,25,27,32,36,\ldots\}$). Let $1_A\ast 1_A(n)=\#\{(a,b): a,b\in A,\ a+b=n\}$ be the additive representation function counting ordered ways to write $n$ as a sum of two powerful numbers. Is it true that $$1_A\ast 1_A(n)=n^{o(1)}?$$ That is, does the number of representations of $n$ as a sum of two powerful numbers grow slower than any fixed positive power of $n$: for every $\epsilon>0$ is there a constant $C_\epsilon$ with $1_A\ast 1_A(n)\leq C_\epsilon n^\epsilon$ for all $n$?

Acceptance. FULLY RESOLVES: a complete proof that $1_A\ast 1_A(n)=n^{o(1)}$ (for every $\epsilon>0$ a $C_\epsilon$ with $1_A\ast 1_A(n)\leq C_\epsilon n^\epsilon$ for all $n$) — machine-checkable (Lean/Coq, e.g. extending the existing formalisation) preferred, else a full written proof; OR a disproof exhibiting an explicit infinite family $n_k$ and a constant $c>0$ with $1_A\ast 1_A(n_k)\geq n_k^{c}$, together with proof. ADVANCES (each must strictly beat what is stated in the background): (a) an unconditional upper bound $1_A\ast 1_A(n)\leq n^{\theta+o(1)}$ for an explicit constant $\theta<1/2$ (below the trivial exponent), with proof; (b) a reproducible search establishing a record lower bound — an explicit $n$ (with the list of its powerful summand pairs) achieving $1_A\ast 1_A(n)$ larger than any previously exhibited value, delivered with the enumeration program and a certificate of completeness of the representation count. Deliver the proof, or the search code plus the record $n$ and its full representation list.

Background

Posed by Erdős [Er76d]; listed as open on erdosproblems.com/943 (fetched 2026-07-21, status 'open'). Powerful numbers (Golomb, 1970) are sparse: the count of powerful $m\leq x$ is $\tfrac{\zeta(3/2)}{\zeta(3)}x^{1/2}+O(x^{1/3})$, so $A$ has density of order $x^{1/2}$. On average the sumset representation function is therefore bounded, but the conjecture concerns the pointwise MAXIMUM: whether some $n$ can be written as $a+b$ with $a,b$ powerful in more than $n^{o(1)}$ ways. A trivial upper bound is $1_A\ast 1_A(n)\leq\#\{a\in A: a\leq n\}=O(n^{1/2})$, so the content is to beat exponent $1/2$ all the way down to $o(1)$. The problem sits in the same neighbourhood as SciNet's additive-representation-function problems (e.g. Erdős #66 at erdosproblems.com/66), but is specifically about the set of powerful numbers, not a general additive basis. A Lean formalisation of the statement exists in the DeepMind formal-conjectures project. Attacker's tool: enumerate powerful numbers $a=x^2y^3$ up to $N$, tabulate the convolution $1_A\ast 1_A(n)$ for all $n\leq N$, and hunt for $n$ with anomalously many representations to force the growth from below; on the analytic side, bound the number of solutions of $x_1^2 y_1^3 + x_2^2 y_2^3 = n$ via the geometry of these thin binary forms.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.