Skip to content

Erdős Problem #441

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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

Fix an integer \(N\geq1\). How many distinct positive integers can be selected from \([1,N]\) if the least common multiple of every pair of selected integers is at most \(N\)? Erdős Problem 441 asks for the largest possible cardinality \(g(N)\), and whether a particular construction of small integers and even integers is always extremal. This is different from Problem #440: there the least common multiple was tested only on consecutive members of an infinite sequence; here every pair in a finite set must pass the bound.

The condition is not simply that the product \(ab\) be at most \(N\), because \(\mathrm{lcm}(a,b)=ab/\gcd(a,b)\). Numbers that share a large common divisor can coexist even when their ordinary product exceeds \(N\). On the other hand, distinct large coprime numbers tend to violate the condition. The tension creates an extremal question that mixes divisibility and finite-set combinatorics.

A small example

Take \(N=8\) and select \(A=\{1,2,4,8\}\). Every smaller member divides each larger member, so for any \(a,b\in A\) the least common multiple is the larger of the two and is at most \(8\). Thus \(g(8)\geq4\). This is a complete exact verification of the pairwise condition, but it is not on its own an exhaustive proof that no larger set exists.

Erdős's proposed construction for large \(N\) takes all integers up to approximately \(\sqrt{N/2}\), together with the even integers from that threshold up to approximately \(\sqrt{2N}\). If both numbers are in the small part, their product is at most \(N/2\). If one lies in each part, their product is at most \(N\). If both are even and at most \(\sqrt{2N}\), their greatest common divisor is at least \(2\), and consequently their least common multiple is at most \(ab/2\leq N\). All pairs therefore satisfy the condition.

The number of selected integers in this construction is

\[ \sqrt{N/2}+\frac{\sqrt{2N}-\sqrt{N/2}}{2}+O(1) =\sqrt{9N/8}+O(1). \]

The calculation gives a rigorous lower bound for \(g(N)\) with a leading constant \(\sqrt{9/8}\), but does not prove exact finite optimality.

What is known

Erdős posed the question in 1951 and revisited it in later work, including Old and New Problems and Results in Combinatorial Number Theory with Graham (1980), printed page 87. He proved an early bound \(g(N)\leq2\sqrt N+O(1)\); Choi subsequently improved it. Chen (1998) established the sharp leading asymptotic

\[ g(N)\sim\sqrt{9N/8}. \]

Chen and Dai (2006) strengthened the upper error estimate to \(g(N)\leq\sqrt{9N/8}+O(\sqrt{N/\log N}\log\log N)\). These are published bounds for the extremal cardinality, not merely numerical experiments.

The proposed construction is nevertheless not always exactly optimal. Chen and Dai (2007) proved that infinitely many \(N\) permit sets larger than Erdős's particular construction, with an advantage linked to iterated logarithms. Thus the originally suggested exact extremality is disproved while its leading asymptotic is correct. The maintained Erdős Problem #441 explains both outcomes. It would be incorrect to describe the entire question simply as “proved” or “disproved” without distinguishing the asymptotic formula from exact attainment.

GCL's current state

The original GCL issue #1711 pins catalogue entry #441 to teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen label is disproved, referring to the proposed exact extremal construction. The maintained page records the asymptotic proof as well. The original issue identifies no #441 statement file in the admitted FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020; no formal compilation is claimed here.

The authenticated first source return on the original issue is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1711#issuecomment-6158548964. Its mathematical purpose is to hold the exact counterclaim and the asymptotic result together without conflating them. Accepted coverage remains a V2-ledger decision separate from this unaccepted six-section manuscript.

What remains

A bounded fixture should enumerate all subsets of \([1,N]\) for \(N\leq16\), rejecting a candidate immediately when some pair has least common multiple greater than \(N\). Independently compute the same predicate using prime-exponent maxima rather than only gcd, and record the largest cardinalities and lexicographically first maximizers. Confirm the valid set \(\{1,2,4,8\}\) at \(N=8\) and calculate Erdős's construction under a declared rounding convention.

The documentary task must compare Chen's 1998 leading formula with the Chen–Dai 2007 infinitely-often nonoptimality theorem. An upper bound with big-O error is not an exact finite maximizer statement. Success requires exact pair checks and source-concordant asymptotic quantifiers. A missed pair, a mistaken replacement of lcm by product, or a claim that asymptotic optimality implies exact optimality is a falsification condition. Stop at finite and source checks.

Sources and claim boundaries

Historical Erdős work and Erdős–Graham (1980), p.87. Resolving research: Chen (1998), Chen–Dai (2006, 2007), as documented at Erdős Problem #441. Frozen custody: GCL original issue #1711, teorth catalogue, and the authenticated RESULT/1 return when posted. The \(N=8\) construction and pairwise proof are exact. The asymptotic and infinitely-often theorem are attributed to published authors, not independently rederived. No mathematical novelty, certified Lean proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1711 — 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.

Back to catalogue · Compendium introduction