← All problems

Erdős Problem #870 — Minimal additive bases with logarithmic representation growth

47 years old · traced to

Let k≥3k\geq 3 be an integer, and let AA be a set of nonnegative integers. Say that AA is an additive basis of order kk if every sufficiently large integer is a sum of exactly kk elements of AA. Such a basis is minimal if no proper subset of it is also a basis of order kk. Write rA(n)r_A(n) for the number of representations of nn as a sum of at most kk elements of AA, as in the question. Is it true that for every k≥3k\geq 3 there is a constant c(k)>0c(k)>0 such that every additive basis AA of order kk satisfying, for some NN and every integer n≥Nn\geq N,

rA(n)≥c(k)log⁡nr_A(n)\geq c(k)\log n

contains a minimal basis of order kk? 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 f(n)f(n) is the number of representations n=ai+ajn=a_i+a_j with ai≤aja_i\leq a_j; 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 rA(n)r_A(n), which is stated as counting representations with at most kk summands. Erdős and Nathanson, “Partitions of Bases into Disjoint Unions of Bases” (1988) Erdős Problems #870

References

Progress summary

Never refreshed

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.