Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 870

claims/: The 1 claim page of Problem 870, one per claimant's result; the problem's standing derives from them.

Statement. Let $k\geq 3$ and $A$ be an additive basis of order $k$ . Does there exist a constant $c=c(k)>0$ such that if $r(n)\geq c\log n$ for all large $n$ then $A$ must contain a minimal basis of order $k$ ? (Here $r(n)$ counts the number of representations of $n$ as the sum of at most $k$ elements from $A$ .)

Formulation. The site counts every representation of $n$ as a sum of at most $k$ elements of $A$ , and the standing judges the site's wording, the only Statement shown. Its source [ErNa88] (Part 3, Problem 3) asks instead whether an asymptotic basis of order $h>2$ , with every large integer a sum of $h$ elements, must contain a minimal basis of order $h$ when $f(n)\ge c\log n$ for a sufficiently large constant $c$ . Here $f(n)$ is the paper's count of representations, which for order $h$ (its abstract and Theorems 4 and 5) is the largest number of pairwise disjoint representations of $n$ as a sum of $h$ elements. Larsen argued on the problem's thread (2026-05-04) that Erdős meant representations by exactly $k$ terms. The pending claim answers only the site's at-most- $k$ wording and does not address the source's version.

Status. OPEN, the site's label. The derived standing departs from it because a pending full claim, Turturean, answers the site's wording no for every $k\ge3$ , which makes the problem claimed as disproved. The claim is not accepted: its Lean development is not built or audited here, one outside validation of it is reported on the problem's thread, and there is no refereed publication.

Source. erdosproblems.com/870, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #870, https://www.erdosproblems.com/870.

References.

[ErNa88] Erdős, Paul and Nathanson, Melvyn B., Partitions of bases into disjoint unions of bases. J. Number Theory 29 (1988), 1-9; Problem 3 of Part 3 is this question.
[ErNa79] Erdős, Paul and Nathanson, Melvyn B., Systems of distinct representatives and minimal bases in additive number theory. (1979), 89-107.
[Ha56] Härtter, Erich, Ein Beitrag zur Theorie der Minimalbasen. J. Reine Angew. Math. (1956), 170-204.
[Na74] Nathanson, Melvyn B., Minimal bases and maximal nonbases in additive number theory. J. Number Theory (1974), 324-333.

Formalization. The site shows no formal statement, and the community database lists the problem as not formalized. The claimant's own Lean 4 development, not built or audited here, is linked on the claim page.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (17)

Turturean answers the question no for every order k at least 3 problems/additive_bases/E0870/claims Additive Bases and Sidon Sets additive_bases/erdos_1979_systems_distinct_representatives_minimal_bases_additive Lemma 1 (p. 92): at most 2^s (3/4)^t transversals of the one- or two-element sets S_i meet every T_k Theorem 2 (p. 100): an asymptotic basis of order 2 with r(n) > c log n, c > 1/log(4/3), contains a minimal asymptotic basis of order 2 additive_bases/erdos_1988_partitions_bases_into_disjoint_unions_bases Part 3, Problem 3 (p. 8): must an asymptotic basis of order h > 2 with many representations contain a minimal asymptotic basis additive_bases/larsen_2026_robust_additive_bases_without_minimal_subbases Theorem 1 (p. 1): a set A with r_A(m) > epsilon log m for all large m that contains no minimal additive subbasis of order 2 additive_bases/turturean_2026_negative_answer_erdos_problem_870 Lemma 5.1 (p. 9): a finite interval of fillers covering every residue many times, with one rigid residue Proposition 2.3 (p. 3): an order-2 set with logarithmic exact representation counts, density zero and no minimal at-most-two subbasis Proposition 3.4 (pp. 5-6): a clustered order-2 input whose shifted sumsets survive the deletion of an element Proposition 4.1 (p. 8): for every C > 0 an order-3 basis with at least C log n representations and no minimal order-3 subbasis Proposition 5.2 (p. 9): for every k >= 4 and C > 0 an order-k basis with at least C log n representations and no minimal order-k subbasis Theorem 1.1 (p. 2): for every k >= 3 and every C > 0 an order-k basis with at least C log n representations and no minimal order-k subbasis

Graph