Skip to content

Erdős Problem #1110

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Fix two coprime integers \(p>q\ge2\). Consider numbers of the form \(p^kq^\ell\), where both exponents are nonnegative integers.

Erdős Problem #1110 asks which integers can be expressed as sums of distinct numbers of this form, under a further restriction: none of the chosen summands may divide another. Such a collection of summands is called a divisibility antichain.

For pairs other than \(\{p,q\}=\{3,2\}\), the problem concerns the density of integers that cannot be represented, and whether infinitely many of those integers are also coprime to \(pq\).

A small example

For \(\{p,q\}=\{3,2\}\),

\[ 31=27+4=3^3+2^2. \]

Neither summand divides the other. In fact, the original problem includes a constructive argument showing every positive integer has such a representation using powers of \(2\) and \(3\).

Here is the induction. Represent zero with no summands. For even \(n=2m\), double every summand in an antichain representation of \(m\). For odd \(n\), let \(3^k\) be the largest power of \(3\) not exceeding \(n\) and use

\[ n=3^k+2\left(\frac{n-3^k}{2}\right). \]

Apply the induction to the integer inside parentheses and double its summands. Because each old summand is smaller than \(3^k\), the doubled summands have a lower exponent of \(3\) than \(k\). Hence \(3^k\) cannot divide any of them; being odd, it cannot be divisible by them. The entire representation remains an antichain.

The exact executable checker tests all integers from 1 through 1,024, verifying the sum, prime-power form, uniqueness and divisibility condition.

What is known

Erdős and Lewin (1996) proved that the set of nonrepresentable integers is finite if and only if the base pair is \(\{3,2\}\). That leaves finer questions about density and the occurrence of infinitely many coprime nonrepresentable integers.

Yu and Chen (2022), as summarized by the maintained catalogue, proved density-zero representability in broad regimes, including \(q>3\), \(q=3\) with \(p>6\), and \(q=2\) with \(p>10\). They also proved the existence of infinitely many coprime nonrepresentable integers except for certain small pairs not covered by their stated result.

For the special \((3,2)\) case, a separate quantitative question asks how large the smallest summand can be required to be. Later published work provides bounds and a reported sharp asymptotic. It is not the same as the nonrepresentability question.

GCL's current state

Authenticated source audit #2381 reconstructs the known elementary induction and independently verifies its output for all \(n\le1024\).

#1110 is a deterministic critical-review sample. The arithmetic replay does not certify the full published density theorems or the reported sharp minimum-summand asymptotic. Primary sources and independent review remain pending.

What remains

Read the original Erdős–Lewin (1996), Yu–Chen (2022), and relevant later papers with their exact parameter exclusions. Audit the induction proof's divisibility invariant, compare the reported sharp constant for the \((3,2)\) minimum-summand problem, and then conduct the source-specific critical review.

Sources and claim boundaries

Erdős Problem #1110, as maintained April 2026; Erdős–Lewin (1996); Yu–Chen (2022); Blecksmith–McCallum–Selfridge (1998); Yang–Zhao (2025); GCL return #2381. The elementary induction is a known result, not a novel GCL proof. Critical review pending; manuscript unaccepted.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2381 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
  • 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