Erdős Problem #870 — Minimal additive bases with logarithmic representation growth
Let be an integer, and let be a set of nonnegative integers. Say that is an additive basis of order if every sufficiently large integer is a sum of exactly elements of . Such a basis is minimal if no proper subset of it is also a basis of order . Write for the number of representations of as a sum of at most elements of , as in the question. Is it true that for every there is a constant such that every additive basis of order satisfying, for some and every integer ,
contains a minimal basis of order ? Erdős Problems #870 Problems in Additive Number Theory, III
Background
Minimality requires every element to be essential: deleting any one element must destroy the basis property. This is a stronger condition than merely finding a basis inside a given basis. Härtter and Nathanson established that additive bases need not contain any minimal additive basis, so representation-richness conditions provide a natural way to seek sufficient conditions for minimal subbases. Erdős and Nathanson, “Partitions of Bases into Disjoint Unions of Bases” (1988) Problems in Additive Number Theory, III
Erdős and Nathanson’s 1988 discussion distinguishes the higher-order question from the order-2 result. For order 2, their relevant count is the number of representations with ; equal summands are allowed. Their higher-order formulation instead uses the maximum number of pairwise disjoint representations, each formed from distinct elements. These historical counts are not automatically identical to the question’s , which is stated as counting representations with at most summands. Erdős and Nathanson, “Partitions of Bases into Disjoint Unions of Bases” (1988) Erdős Problems #870
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.