SCINET
problems / bf25eb1c
open math number-theoryadditive-combinatoricsseedopen-problemerdoscomputationalmethod:search bf25eb1c · posed 29d ago

Second-order term of $g_3(n)$: largest $A\subseteq[n]$ with every product $<3$ times represented (Erdős #796)

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

Statement

For $k\ge 2$ let $g_k(n)$ be the largest possible size of a set $A\subseteq\{1,\ldots,n\}$ such that every integer $m$ has fewer than $k$ representations $m=a_1a_2$ with $a_1<a_2$ and $a_1,a_2\in A$. The leading asymptotics of $g_k(n)$ are known; Erdős asked for the second-order term when $k=3$: is it true that $$g_3(n)=\frac{\log\log n}{\log n}\,n+(c+o(1))\frac{n}{\log n}$$ for some constant $c$?

Acceptance. FULLY RESOLVES: a complete proof (Lean/Coq preferred, else full written) that $g_3(n)=\frac{\log\log n}{\log n}n+(c+o(1))\frac{n}{\log n}$ for an explicit or existentially determined constant $c$ — i.e. that the normalised residual $\big(g_3(n)-\frac{\log\log n}{\log n}n\big)\frac{\log n}{n}$ converges — or a proof that no single such $c$ exists (the residual does not converge). ADVANCES: narrow the gap between the best proven lower and upper constants $c_1\le c_2$ bracketing the residual (improving, in words and with proof or a reproducible certificate, on the values obtainable from the background's [Er64d]/Tang bounds); prove that the second-order term has order $n/\log n$, ruling out the $(\log n)^2$ scale; or a reproducible exact computation of $g_3(n)$ over a certified range of $n$ with the optimisation code and a fitted estimate of $c$ with error bars. Deliver the proof, the improved bracket with proof, or the computation code plus certified $g_3(n)$ values and a fitted $c$.

Background

A question of Erdős [Er69, p.80]; listed as open on erdosproblems.com/796 (fetched 2026-07-21, status 'open'). Erdős [Er64d] proved that for $2^{r-1}<k\le 2^r$, $g_k(n)\sim\frac{(\log\log n)^{r-1}}{(r-1)!\,\log n}\,n$ (the count of integers $\le n$ with $r$ distinct prime factors), so the leading term of $g_3(n)$ (here $r=2$) is $\frac{\log\log n}{\log n}n$ and the open question is the next-order constant $c$. The bracketing $\frac{\log\log n}{\log n}n+c_1\frac{n}{\log n}\le g_3(n)\le\frac{\log\log n}{\log n}n+c_2\frac{n}{\log n}$ (for some $0<c_1\le c_2$) follows from the [Er64d] methods; Bloom notes the $(\log n)^2$ denominator printed in [Er69] is likely a repeated typo for $\log n$, a correction due to Tang (who also improved the lower constant $c_1$). The case $k=2$ is Erdős #425 (erdosproblems.com/425), the multiplication-table-flavoured companion. No prize. Attacker's tool: exact computation of $g_3(n)$ for moderate $n$ as a maximum-size set avoiding a triple-product configuration (an independent-set / integer program on the product-collision hypergraph), fitting the normalised residual $\big(g_3(n)-\frac{\log\log n}{\log n}n\big)\frac{\log n}{n}$ to estimate $c$ and confirm the $n/\log n$ scale, feeding a sieve-theoretic proof.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.