Erdős problem #334 — live-page audit, exact finite certificate, and obstruction

Date of audit: 2026-07-28 UTC.

Claim labels used below:

• (a) elementary-rigorous: a complete argument is given here and uses only

elementary facts.

• (b) rigorous-modulo-named-theorem: the deduction is complete once the

explicitly named theorem is accepted.

• (c) plausible/structural-unverified: heuristic or literature-search

diagnosis, not a theorem.

• (d) computational-only: exact finite computation, reproducible by the

standalone checker, but not promoted to an asymptotic theorem.

0. Mandatory live-page collision check

I fetched the live page erdosproblems.com/334 through the Bright Data browser path because a direct datacenter request is Cloudflare-walled. The page was last edited 03 April 2026.

The page's question clause, verbatim, is:

Find the best function $f(n)$ such that every $n$ can be written as $n=a+b$ where both $a,b$ are $f(n)$-smooth

Its parenthetical defines $f(n)$-smooth to mean not divisible by any prime $p>f(n)$. Thus this records the exact mathematical content of the live statement while keeping the direct quotation short. The live status fields were:

• OPEN;
• 0 claimed proofs for this problem;
• Currently working on this problem: None;
• Interested in collaborating: None;
• two comments.

Thus the task's mandatory stop condition did not trigger.

The known result printed on the live page is that Erdős asked for $f(n)\leq n^{1/3}$, and Balog proved

where $4/(9\sqrt e)=0.2695691820\ldots$. The page says it is likely that $f(n)\leq n^{o(1)}$ and points to Problem 59 in Ben Green's list.

The two comments, which the page itself warns are not verified, say:

1. On 03 March 2026, my99n linked OEIS A062241 and a proof claiming

A062241 is bounded by the negative-pseudosquare sequence A045535. The comment says the site was updated in response.

1. On 19 November 2025, Woett reported finding no binary improvement over

Balog, mentioned Sárközy's much smaller smoothness bound for a sum of three terms, and explained the least-quadratic-nonresidue obstruction.

I independently checked the useful mathematical parts of both comments below; I do not treat the comments themselves as authorities.

1. Precise normalization

Let $P^+(m)$ be the greatest prime factor of $m>1$, and set $P^+(1)=1$. The original Erdős source and the page-linked OEIS entry use positive summands, so for $n\geq2$ define

This is the pointwise best version of the page's $f(n)$. Also define

Then, (a),

The finite computation is most naturally stated in terms of $G(y)$.

2. Primary-source literature check

Original formulations

• In [Erdős, Problems and results on consecutive integers, p.272

(1976)](https://doi.org/10.5486/PMD.1976.23.3-4.15), the scan explicitly asks whether, for every $\alpha$, every sufficiently large $n$ is $a+b$ with positive $a,b$ and $P^+(ab)<n^{1/\alpha}$.

• In [Erdős, Some new problems and results in number theory, p.55

(1982)](https://combinatorica.hu/~p_erdos/1982-32.pdf), Erdős uses the equivalent threshold formulation: the least integer not representable with prime factors below a bound should exceed every fixed power of that bound.

• The other source cited on the live page is Erdős--Graham,

Old and new problems and results in combinatorial number theory (1980), p.70, MR 0592420.

Best binary theorem located

I retrieved the primary scan of A. Balog, On additive representation of integers, Acta Math. Hungar. 54 (1989), 297--301. Its theorem is exactly: for each fixed $\epsilon>0$, every sufficiently large $N$ is $a+b$ with

Balog's proof invokes Fouvry's large-modulus distribution theorem. On the first page Balog also observes that the method cannot prove even an $N^\epsilon$ bound and says new ideas are needed for the conjectured subpolynomial scale. This directly verifies the live page's bibliographic and exponent claims.

Ben Green's current 100 Open Problems, Problem 59 (PDF most recently updated December 2025) still identifies Balog's exponent as the record. Green also states the quadratic-nonresidue barrier proved elementarily in Section 5 below.

Related work that does not improve the binary theorem

The primary abstract for G. N. Sárközy, On sums with small prime factors, Acta Math. Hungar. 67 (1995), 333--345, gives the ternary theorem

This is three summands, not two.

I searched the exact Balog title/DOI and its citation graph, then inspected the plausible later primary pages. The Hildebrand--Tenenbaum survey (1993) and Baker's survey (2009) concern smooth-number distribution more broadly; Sárközy (1995) is ternary; Balog--Rivat--Sárközy (2014) studies arithmetic properties of sums chosen from large sets; Győry--Hajdu--Sárközy (2020) studies additive decomposability of the smooth-number set itself; and Blomer--Grimmelt--Li--Rydin Myerson concerns a smooth number plus two almost-prime squares. None states a better all-integers binary exponent for this problem. This is a scoped literature-search miss, not a proof that no overlooked paper exists.

Verified identifiers:

• Balog 1989: DOI

10.1007/BF01952060, MR 1029092.

• Sárközy 1995: DOI

10.1007/BF01874496.

• Erdős 1976: DOI

10.5486/PMD.1976.23.3-4.15, MR 0453671.

• Erdős 1982: Lecture Notes in Mathematics 938, pp.50--74, MR 0665438.

3. An elementary negative-pseudosquare obstruction

Lemma (a)

Let $y\geq2$ and let $m$ be a positive integer such that

Then $m$ is not the sum of two positive $y$-smooth integers.

Proof

Suppose otherwise. Since $m$ is odd, write the even summand as $2^kA$ and the odd summand as $B$, where $k\geq1$ and $A,B$ are odd:

If an odd prime $q$ divided both $A$ and $B$, then $q\mid m$; but the hypothesis $\left(\frac{-m}{q}\right)=1$ excludes zero. Hence $(A,B)=1$.

Using the Jacobi symbol, with the convention $\left(\frac{x}{1}\right)=1$, every prime factor of $A$ and $B$ is at most $y$, so

Put $a=(A-1)/2$ and $b=(B-1)/2$. Multiplying the two displayed identities and applying quadratic reciprocity gives

But $2^kA+B\equiv7\pmod8$ makes the right side of (1) equal to $-1$ in every case:

• if $k=1$ and $A\equiv1\pmod4$, then $B\equiv5\pmod8$, $a,b$ are even,

and $\left(\frac2B\right)=-1$;

• if $k=1$ and $A\equiv3\pmod4$, then $B\equiv1\pmod8$, $a$ is odd,

$b$ is even, and $\left(\frac2B\right)=1$;

• if $k=2$, then $B\equiv3\pmod8$, $b$ is odd,

$a+b+ab$ is odd, and $\left(\frac2B\right)^2=1$;

• if $k\geq3$, then $B\equiv7\pmod8$, again $a+b+ab$ is odd, while

$\left(\frac2B\right)^k=1$.

This contradiction proves the lemma. $\square$

This also proves, from scratch, the inequality between the two OEIS sequences mentioned in the live comment: a negative pseudosquare for all odd primes at most $y$ supplies a nonrepresentable integer for $S_y+S_y$.

4. Explicit exact pointwise value

Set

The checker verifies $M\equiv7\pmod8$ and the following explicit square roots:

For every column,

Therefore the lemma proves that $M$ has no representation by two 79-smooth positive integers.

On the other hand, there is the explicit representation

Thus (d), with all finite arithmetic exposed above and rechecked by the standalone program,

The lower bound is the negative-pseudosquare lemma through prime 79; the displayed sum gives the upper bound 83. Since the optimum is a greatest prime factor and there is no prime strictly between 79 and 83, equality follows.

This is an exact pointwise result, not a solution of the asymptotic problem.

5. Exact finite prefix theorem and table

The main finite computation proves (d)

Equivalently:

• every $2\leq n<131\,486\,759$ is the sum of two positive 73-smooth

integers;

• $131\,486\,759$ is not the sum of two positive 79-smooth integers.

The first assertion is stronger than the needed coverage for $y=79$, and the second is stronger than the needed obstruction for $y=73$, so together they prove both equalities.

The standalone program also independently verifies this selected exact table:

These agree with the corresponding entries of the page-linked A062241, but the checker does not import or trust OEIS data.

Exact coverage certificate

The program generates all 73-smooth integers through $M$ by recursively choosing the exponent of each prime at most 73. There are exactly 727,473. It makes the integer bitset

Let $A=S_{73}\cap[1,100000]$; $|A|=14,543$. It computes, using exact arbitrary-precision integer operations,

The assertion

target = (1 << M) - 4          # bits 2,...,M-1
assert target & ~covered == 0

is therefore an exact certificate that every integer from 2 through $M-1$ is $a+b$ with $a,b\in S_{73}$.

For nonrepresentation, the program independently generates all 808,372 79-smooth integers through $M$ and runs an exact sorted two-pointer pair-sum test. It finds no pair summing to $M$. The displayed negative-pseudosquare roots are a second, structural check.

The sequence fingerprints (little-endian unsigned 64-bit encoding) are:

S_73 through M:
09be484f732a4d2395261d4b00cabec3bf903066b655481508b3953628fc7a4a

S_79 through M:
3a501c077244d50a1744266a5bb4b4373d412e8670bc23b97ec9110d9d9fcc91

6. General lower-bound construction

For $Y\geq2$, put

Congruence proposition (a)

If $p$ is prime and

then

Indeed $p\equiv7\pmod8$, so $2$ and $-1$ have Legendre symbols $+1$ and $-1$, respectively, modulo $p$. For every odd prime $q\leq Y$, quadratic reciprocity and $p\equiv-1\pmod q$ give

Thus every positive $Y$-smooth integer below $p$ is a quadratic residue modulo $p$. If $p=a+b$ with $a,b$ both $Y$-smooth, then $a/b\equiv-1\pmod p$ would be a quotient of two quadratic residues. That would make $-1$ a residue, contradiction.

Consequences

• (b), modulo Dirichlet's theorem: for every fixed $Y$, infinitely many

primes lie in the reduced progression $-1\bmod Q_Y$, so infinitely many primes satisfy $F(p)>Y$. In particular $F$ is unbounded.

• (b), modulo Linnik's theorem and Chebyshev's estimate: choose the

least prime $p_Y\equiv-1\bmod Q_Y$. Linnik gives $p_Y\ll Q_Y^L$ for an absolute $L$, while $\log Q_Y=O(Y)$. Hence, along an infinite sequence of primes $p\equiv7\pmod8$,

\[ F(p)\gg\log p. \]

This lower-bound construction is likely standard in this circle of ideas; no novelty claim is made for it.

7. Quadratic-nonresidue reduction and the exact analytic wall

Let $p\equiv3\pmod4$ be prime, and suppose $p=a+b$ with $a,b$ positive and $y$-smooth. If every prime factor of $ab$ were a quadratic residue modulo $p$, then both $a$ and $b$ would be residues, and $a/b\equiv-1\pmod p$ would make $-1$ a residue. This is impossible. Therefore (a)

for primes $p\equiv3\pmod4$, where $n(p)$ is the least positive quadratic nonresidue modulo $p$.

Consequently (a):

• a uniform bound $F(n)\leq n^{0.1}$ would imply

$n(p)\leq p^{0.1}$ for every sufficiently large prime $p\equiv3\pmod4$;

• the conjectural $F(n)=n^{o(1)}$ would imply Vinogradov's

least-quadratic-nonresidue conjecture on that prime class.

The current unconditional Burgess exponent is

so even exponent $0.1$ for problem #334 would cross a notorious existing barrier. This is a necessary-condition obstruction, not a proof that a least-nonresidue breakthrough alone would suffice for the smooth-sum problem.

The exact missing analytic statement is uniform pointwise positivity of the binary smooth-number convolution

when $y=N^\epsilon$, for every fixed $\epsilon>0$ and every sufficiently large $N$. Available density estimates for smooth numbers, or estimates valid for almost all $N$, do not exclude isolated zeros of this binary convolution. Sárközy's third variable supplies averaging that is absent here; Balog's two-variable weighted argument reaches exponent $4/(9\sqrt e)$ but explicitly stalls before $N^\epsilon$.

This is the substantive wall: one needs a new uniform binary distribution lemma strong enough to overcome both the parity/exceptional-target issue and the least-quadratic-nonresidue consequence.

8. Standalone verification and measured cost

Checker: erdos334_wave8t_reverify.py

Run from the repository root:

python runs/erdos334_wave8t_reverify.py --workers 4

The final run printed:

PASS: all asserted finite smooth-sum certificates verified
total_elapsed_seconds = 53.898

Measured by /usr/bin/time:

wall=54.02 s
cpu_user=146.61 s
cpu_sys=27.46 s
maxrss_kb=177236

SHA-256 of the checker used for that run:

c623a667cfff452b7d7020fc8448f858a84fb6d5f543b7a4eb8ff4d06d67470c

The checker uses only the Python standard library. It independently:

1. generates primes by trial division;
2. generates smooth numbers from unique factorization;
3. divides every generated value back down by the allowed primes;
4. performs exact bitset coverage (no FFT or floating point);
5. performs an independent two-pointer nonrepresentation test;
6. checks every displayed modular square root and both explicit

factorizations.

For scale only, the page-linked OEIS reports the next much larger candidate $G(83)=508\,095\,719$; I did not certify that value. A from-scratch count gives 1,736,092 83-smooth integers through that candidate and 42,988 of them through 500,000. Extrapolating from the measured exact-bitset throughput, a comparable coverage run would cost roughly 0.5--1.5 core-hours and 0.7--1.0 GiB aggregate RAM, or below about US$0.15 at $0.10 per core-hour. More importantly, verifying any finite next term cannot settle the required uniform asymptotic statement.

9. Honest conclusion

The open problem is not solved. What is established here is:

• (d) an explicit exact value

$F(131\,486\,759)=83$, with a displayed representation and an independent negative-pseudosquare obstruction;

• (d) the exact finite prefix

$G(73)=G(79)=131\,486\,759$, plus the selected verified table above;

• (a)/(b) a clean congruence construction forcing $F(p)>Y$, and hence

$F(p)\gg\log p$ infinitely often modulo Linnik's theorem;

• (a) the precise reduction $n(p)\leq F(p)$ for

$p\equiv3\pmod4$, isolating why substantially improving Balog is tied to the least quadratic nonresidue problem.

PARTIAL: Exact computation proves G(73)=G(79)=131,486,759 and F(131,486,759)=83; a congruence construction gives F(p)≫log p infinitely often modulo Linnik, while the uniform n^{o(1)} question remains blocked by binary smooth-convolution and least-quadratic-nonresidue barriers.