Erdős Problem #437
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Erdős Problem 437 starts with strictly increasing positive integers \(1\leq a_1<\cdots<a_t\leq x\) and studies their cumulative products \(P_j=a_1a_2\cdots a_j\). How many of these \(P_j\) can be perfect squares? More specifically, is it possible, for any fixed \(\varepsilon>0\), to choose a sequence having more than \(x^{1-\varepsilon}\) square partial products when \(x\) is sufficiently large? The restriction \(a_j\leq x\) applies to every factor, not to the potentially enormous running products. Distinctness and increasing order rule out a trivial choice of repeated small square factors.
The key algebra is parity of prime valuations. An integer \(M\) is a square exactly when \(v_p(M)\) is even for every prime \(p\). Each new factor adds its prime-exponent parity vector to the running parity state over \(\mathbf F_2\). Thus the problem seeks many returns to the zero parity vector along a walk whose steps come from a strictly increasing sequence of distinct integers. This description explains why a collection of smooth numbers can be useful: shared small prime factors make cancellation of parities possible, without forcing each chosen number itself to be square.
A small example
A small exact example is the increasing sequence \((1,2,8,9)\). Its partial products are \(1,2,16,144\). Three are squares, since \(1=1^2\), \(16=4^2\) and \(144=12^2\). The factor \(8\) is not square, yet \(2\cdot8\) is square because the exponent of \(2\) changes from one to four. The final factor \(9\) is square and therefore preserves the square status. All calculations are integer exact and demonstrate the parity-vector mechanism directly.
The example does not establish the asymptotic question. A four-term prefix gives only three square running products, whereas the Erdős question asks for arbitrarily large families with almost linearly many square products in the scale of the largest allowed factor. An independent finite fixture can compare an integer-square-root test for every \(P_j\) against its factor-parity calculation. Agreement catches prime-factorization mistakes and incorrect square tests. The empty product should not be counted as a chosen prefix.
What is known
The historical source is P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), which remarked that \(o(x)\) square partial products is expected and not entirely trivial to establish. The maintained Erdős Problems #437 page reports a positive solution following the work of Bui, Pratt and Zaharescu (2024), highlighted by Terence Tao.
Write \(L(x)\) for the largest number of square partial products obtainable using factors up to \(x\), and let \(u(x)=\sqrt{\log x\log\log x}\). The reported estimates are
Since \(u(x)=o(\log x)\), both sides have the form \(x^{1-o(1)}\), so the lower bound indeed exceeds \(x^{1-\varepsilon}\) eventually for every fixed positive \(\varepsilon\). The constants in the two bounds differ; it would be unjustified to claim a single exact asymptotic from these inequalities.
The related Problem #841 concerns another square-prefix question and is not automatically covered by this theorem. Any analysis must distinguish the asymptotic maximum from the count of individually square terms in the selected sequence.
GCL's current state
The original GCL source issue #1707 fixes the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. The recorded status is proved, consistent with the maintained positive answer. The original issue records no #437 file in the admitted FormalConjectures snapshot 85f863718beeec7b58a3a1926ee92e3472bc2020. A later source cannot silently be substituted for this frozen provider.
The authenticated original-issue source return is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1707#issuecomment-6158406991. Its purpose is to preserve the exact question, primary-paper attribution and mathematical claim boundaries. It is not a newly produced proof of Bui–Pratt–Zaharescu, not a Lean replay and not an editorial admission. The source-specific publication remains contingent on the separate protected production and V2 ledger process.
What remains
A useful bounded follow-up is to build two independent counters for square partial products for \(x\leq30\). One multiplies integers and tests integer square roots. The other updates a prime-exponent parity vector, counting a square exactly when all parity bits vanish. Exhaustive maximization can be attempted only for a transparently stated small input range; the number of increasing factor sequences grows exponentially. The resulting finite maxima should be recorded with maximizing sequences and their exact partial products.
The source-review half of the task should read the Bui–Pratt–Zaharescu theorem and Tao's derivation, including all \(o(1)\) terms and the definition of \(L(x)\). The task succeeds when numerical fixtures agree and both constants appear on the correct sides of the bounds. It fails if a finite search is called an asymptotic proof, if repeated factors are accidentally allowed, or if the two different constants are replaced by an invented precise limit. Stop at this bounded source and arithmetic audit.
Sources and claim boundaries
Primary historical source: Erdős–Graham (1980). Maintained mathematical summary, attribution and explicit bounds: Erdős Problem #437, citing Bui–Pratt–Zaharescu (2024) and Tao. Related #841. Frozen provenance: GCL issue #1707, the teorth source snapshot, and authenticated issue return.
The finite example is verified elementary arithmetic. The asymptotic bounds are published or publicly attributed external research; neither original discovery nor independent formal certification is claimed. No protected merge or V2 editorial acceptance is asserted.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1707 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.