Erdős Problem #338 — Restricted orders of additive bases
Let be an asymptotic additive basis: its order is the least positive integer such that every sufficiently large integer is a sum of at most elements of , with repetitions allowed. Equivalently, for some ,
The restricted order , if it exists, is the least positive integer for which the same eventual representation property holds with the additional requirement that the summands are pairwise distinct:
The questions are: what necessary and sufficient conditions on ensure that exists; if it exists, is it bounded in terms of ; and what necessary and sufficient conditions ensure ? Also, if is a basis for every finite , must have restricted order, and does the answer change if all these bases have the same order? Erdős and Graham (1980)
Background
Erdős and Graham raised the restricted-order questions in their 1980 discussion of additive bases. The distinction is between allowing a basis representation to reuse an element and requiring each chosen element to occur only once; the latter can fail even when the unrestricted representations are uniformly short. Their discussion also contrasts restricted order with exact order, where every sufficiently large integer must be represented using exactly a fixed number of terms. These are different notions, and results about exact order do not by themselves answer the restricted-order questions. Erdős and Graham (1980)
Two classical examples illustrate that restricted order need not equal ordinary order even when it exists: the squares have ordinary order and restricted order , whereas the triangular numbers have both orders equal to . In the opposite direction, for each , the set consisting of together with the positive multiples of is a basis of order but has no restricted order: sums of distinct elements have residue modulo only or , so they cannot represent every sufficiently large integer. Erdős Problems #338 Erdős and Graham (1980)
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.