Erdős Problem #338

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

An ordinary basis permits repeated summands. Its restricted order requires pairwise distinct elements within each representation and is the least uniform bound on the number used. All basis statements concern sufficiently large positive target integers. [S1] [S2]

Statement recorded in the supplied source.

The restricted order of a basis is the least integer $t$ (if it exists) such that every large integer is the sum of at most $t$ distinct summands from $A$. What are necessary and sufficient conditions that this exists? Can it be bounded (when it exists) in terms of the order of the basis? What are necessary and sufficient conditions that this is equal to the order of the basis? [S1]

Short English statement

When can every sufficiently large integer be represented by boundedly many distinct basis elements, and how does that bound compare with ordinary basis order?

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 2060 (EP-338), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 T. F. Bloom, Erdős Problems, Problem 338, https://www.erdosproblems.com/338. Reference from the supplied record; the live problem page was not independently checked for this compilation.

• S3 Hegyvári, Norbert and Hennecart, François and Plagne, Alain, Answer to a question by {B}urr and {E}rdős on restricted addition, and related results. Combin. Probab. Comput. (2007), 747--756. Bibliographic information from the supplied record.

• S4 Hennecart, François, On the restricted order of asymptotic bases of order two. Ramanujan J. (2005), 123--130. Bibliographic information from the supplied record.

• S5 Kelly, John B., Restricted bases. Amer. J. Math. (1957), 258-264. Bibliographic information from the supplied record.

• S6 Pall, Gordon, On Sums of Squares. Amer. Math. Monthly (1933), 10-18. Bibliographic information from the supplied record.