← All problems

Erdős Problem #338 — Restricted orders of additive bases

21 years old · traced to

Let A⊆Z≥0A\subseteq\mathbb Z_{\ge 0} be an asymptotic additive basis: its order h=ord⁡(A)h=\operatorname{ord}(A) is the least positive integer such that every sufficiently large integer is a sum of at most hh elements of AA, with repetitions allowed. Equivalently, for some NN,

∀n≥N∃s∈{1,…,h}, a1,…,as∈An=a1+⋯+as.\forall n\ge N\quad \exists s\in\{1,\ldots,h\},\ a_1,\ldots,a_s\in A\quad n=a_1+\cdots+a_s.

The restricted order ord⁡R(A)\operatorname{ord}_R(A), if it exists, is the least positive integer tt for which the same eventual representation property holds with the additional requirement that the summands are pairwise distinct:

∀n≥N′∃s∈{1,…,t}, a1,…,as∈A pairwise distinctn=a1+⋯+as.\forall n\ge N'\quad \exists s\in\{1,\ldots,t\},\ a_1,\ldots,a_s\in A\text{ pairwise distinct}\quad n=a_1+\cdots+a_s.

The questions are: what necessary and sufficient conditions on AA ensure that ord⁡R(A)\operatorname{ord}_R(A) exists; if it exists, is it bounded in terms of hh; and what necessary and sufficient conditions ensure ord⁡R(A)=h\operatorname{ord}_R(A)=h? Also, if A∖FA\setminus F is a basis for every finite F⊆AF\subseteq A, must AA 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 44 and restricted order 55, whereas the triangular numbers have both orders equal to 33. In the opposite direction, for each h≥3h\ge 3, the set consisting of 11 together with the positive multiples of hh is a basis of order hh but has no restricted order: sums of distinct elements have residue modulo hh only 00 or 11, so they cannot represent every sufficiently large integer. Erdős Problems #338 Erdős and Graham (1980)

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.