Problem 338

../

claims/: The 4 claim pages of Problem 338, one per claimant's result; the problem's standing derives from them.

---

Statement. 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?

Status. Open, the site's label (OPEN; page last edited 2025-09-14). Two accepted partial claims and two pending partial claims are recorded, and a partial claim derives no standing. [[problems/additive_bases/E0338/claims/1957_04_01_kelly|Kelly's restricted order of bases of order two]] (Amer. J. Math. 79 (1957); refereed) proves that every basis of order $2$ in the classical sense, every nonnegative integer being a sum of two elements, has a restricted order, at most $4$, and that an asymptotic basis of order $2$ whose counting function is at least $Cx/\log\log x$ has one at most $3$. [[problems/additive_bases/E0338/claims/2005_03_01_hennecart|Hennecart's restricted order of asymptotic bases of order two]] (Ramanujan J. 9 (2005); refereed) settles the order-$2$ case: every asymptotic basis of order $2$ has a restricted order, at most $4$, and $4$ is attained. The site's remarks credit the bound $4$ for asymptotic bases to Kelly and the example attaining it to Hennecart [He05]. [[problems/additive_bases/E0338/claims/2026_07_28_white|White's restricted order of eventually periodic sets]], a working report of 2026-07-28, settles for eventually periodic sets the statement's first question and the two questions of the site's remarks (a restricted order exists exactly when the subgroup generated by the periodic pattern and the subset sums of the exceptional elements fill the residues; it is at most the period when every finite removal leaves a basis, and equals the order when every such removal leaves a basis of the same order), gives for the third question only that sufficient condition, and gives a basis of order $3$ with restricted order $6$ that stays a basis after every finite removal. [[problems/additive_bases/E0338/claims/2026_10_01_veljjanoski|Veljjanoski's restricted order for robust bases of positive density]], a write-up of 2026-10-01, states that a set of positive lower density $\delta$ which stays a basis after the removal of any finite set has restricted order at most $3\lceil8/\delta^2\rceil-2$, so that a counterexample to the site's question on such bases must have lower density zero; the three questions of the statement are not claimed there. As of 2026-10-06 the proof-claim entry of 2026-10-01 had no comments, and the forum thread held the author's comment of the same day and three comments of 2026-08-17 reporting block constructions with large restricted order at orders $4$ to $8$, a literature list, and White's report.

Source. erdosproblems.com/338, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #338, https://www.erdosproblems.com/338.

References.

• [HHP07] Hegyvári, Norbert and Hennecart, Fran\c cois and Plagne, Alain, Answer to a question by Burr and Erdős on restricted addition, and related results. Combin. Probab. Comput. (2007), 747-756.
• [He05] Hennecart, Fran\c cois, On the restricted order of asymptotic bases of order two. Ramanujan J. (2005), 123-130.
• [Ke57] Kelly, John B., Restricted bases. Amer. J. Math. 79 (1957), no. 2, 258-264, DOI 10.2307/2372681.
• [Pa33] Pall, Gordon, On Sums of Squares. Amer. Math. Monthly (1933), 10-18.
• [Sc54] Schinzel, A., Sur la décomposition des nombres naturels en sommes de nombres triangulaires distincts. Bull. Acad. Polon. Sci. Cl. III. (1954), 409-410.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• hegyvari_2007_answer_question_burr_erdos_restricted_addition
• hegyvari_2007_answer_question_burr_erdos_restricted_addition / theorem_4