Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Rohrbach 1937 ein beitrag zur additiven zahlentheorie
conjecture: Rohrbach's conjecture, printed on p. 9, that n_2(k) = k^2/4 + O(k), the range of the best finite additive 2-basis of k elements; equivalently g(n) = 2 sqrt(n) + O(1), the "in particular" question of Problem 791, which Mrose's 1979 construction refutes.
inequality_47: Rohrbach's lower bounds for the size of a finite additive 2-basis: every 2-basis of k elements for {0, ..., n} has n <= k^2/2 (Folgerung to Satz 6), and n < 0.4992 k^2 once k is large (inequality (47)), so g(n)^2 >= 2n and g(n)^2 > (2.0032...) n for large n, the "(2 + c) n" of Problem 791.
satz_10: Rohrbach's extended bases: the system S_h of Satz 8 represents every integer from 0 to its last element as a signed sum of h of its elements for every prescribed sign pattern except all minus, with a Zusatz for enlarged systems and Satz 11's symmetrization doubling the range.
satz_12: Rohrbach's order-h form of Satz 5: the natural numbers have an additive basis of order h whose counting function below n is less than n^(1/h + epsilon) for all n >= n_0(epsilon), from a finite h-basis of g - 1 used as the digit set in base g.
satz_3: Rohrbach's upper bound: a minimal additive 2-basis for {0, ..., n} has fewer than 2 sqrt(n) elements for every n > 1, proved by the explicit symmetric basis (6) of Satz 2, whose k elements reach k^2/4 + 3k/2 - gamma with gamma at most 11/4.
satz_5: Rohrbach's infinite analogue of Satz 3: the natural numbers have additive bases of order 2 whose counting function below n is less than n^(1/2 + epsilon) for all n >= n_0(epsilon), built from a finite 2-basis of g - 1 by allowing only its elements as base-g digits.
satz_9: Rohrbach's bounds for the longest interval 0, ..., n_h(k) covered by an additive basis of order h with k elements, (k/h)^h < n_h(k) < binom(k+h-1, h), from the explicit system S_h of Satz 8, and their Folgerung (72) that a minimal basis of order h >= 3 for n has fewer than h n^(1/h) elements.
H. Rohrbach, Ein Beitrag zur additiven Zahlentheorie, Math. Z. 42 (1937), no. 1, 1--30, DOI 10.1007/BF01160061; received 9 April 1936 ("Eingegangen am 9. April 1936", p. 30); the author "in Berlin" (p. 1). The title page prints "Ein Beitrag zur additiven Zahlentheorie. Von Hans Rohrbach in Berlin." with the running footer "Mathematische Zeitschrift. 42." Cited as [Ro37] on the problem page. The title reads "A contribution to additive number theory". The source read for this card is the publisher's version of record at https://doi.org/10.1007/BF01160061; no preprint is known here. GDZ serves a free scan of the same print (volume https://gdz.sub.uni-goettingen.de/id/PPN266833020_0042, article LOG_0004), linked from EuDML at https://eudml.org/doc/168701 (both read 2026-10-07); its cover sheet allows use "strictly for noncommercial educational, research and private purposes" and forbids further reproduction without written permission, so it is not an openly licensed copy. The paper has no reference list: it names Schnirelmann, Khintchine, Landau, Romanoff, Schur, Davenport and Erdős in the introduction (p. 1), attributes the conjecture it proves to a remark of I. Schur after a lecture on additive number theory (p. 2), and credits A. Stöhr with the ternary-digit construction giving (p. 3). It is the origin of Problem 791's function and conjecture, as Erdős 1973 reports them, and the paper whose constant Mrose 1979 (p. 118) records as the previous record before his .
The copy read for this card is the publisher's scan of the printed article: 30 pages, printed pp. 1--30 = PDF pp. 1--30 (printed and PDF page numbers agree), a 2005 scan (the file's metadata names a TIFF source and a January 2005 creation date) with an OCR text layer that locates the prose and garbles nearly every formula (umlauts, square roots, fractions, subscripts, binomial coefficients and inequality signs come out as stray letters and digits; the section sign § is read as "w"). Provenance: obtained from the publisher on 2026-09-22 as a DRM-free production PDF through the library's acquisition, from https://doi.org/10.1007/BF01160061; 1,425,144 bytes. No notice is printed in the file; the publisher's article page shows the article paywalled with a reprints-and-permissions link, no open-access or Creative Commons statement and no article copyright line, only the site footer "© 2026 Springer Nature" (https://link.springer.com/article/10.1007/BF01160061, read 2026-10-02), every other right reserved.
Read status: claims checked for the definitions of a basis of order and a minimal basis, the counting bounds (2) and (3) and Schur's conjecture (p. 2); Stöhr's bound, inequality (4) and the summary of §§ 3--8 (p. 3); the problem of § 1, its inverse formulation through , the definition of a symmetric system and Satz 1 (p. 4); Satz 2 with the system (6), the Folgerung (7)--(9) and Satz 3 (p. 5); the proof of Satz 3 and the example (p. 6); Satz 4 with (13)--(16) (p. 8); the conjecture and Satz 5 (p. 9); Satz 6 (p. 11) and its Folgerung (pp. 14--15); inequality (44) (p. 17); Satz 7, the opening of § 5 and inequality (47) (p. 18); Satz 8 (p. 24); Satz 9 (p. 25); inequality (72) (p. 26); Satz 10 (p. 27), Satz 11 (p. 28) and Satz 12 (pp. 29--30), each read clause by clause on the page images of PDF pp. 1--11, 14--19 and 23--30 on 2026-09-22. The proofs of Satz 1, Satz 2 and Satz 3 (pp. 4--6) were read in full on the page images and followed; the construction (11) and the proof of Satz 4 (pp. 6--8) were read on the page images and the count and the range (13) were recomputed from the printed rows. The proof of Satz 6 (pp. 11--14), the eight-interval method of § 4 and the case analysis of § 5 (pp. 15--23) and the proofs of Satz 9 to Satz 12 (pp. 25--30) were read for structure only; PDF pp. 12--13 and 20--22 were read in the text layer alone, and none of the numerical inequalities of §§ 3--5 was checked. A filing check, not a review verdict: the systems (6) and (11) as printed on pp. 5 and 7 were built for all and , and in every case the system had the printed number of elements and its pairwise sums covered for the printed ; the parameter choices (7)--(8) and the even case of Satz 4's Folgerung reproduced (9) and (15) for . Nothing here is independently reviewed.
Contents
- Introduction (pp. 1--4, page images). Schnirelmann's sum of sets of natural numbers, for the -fold sum, and the classical question (1), . The paper studies the converse: given and a fixed , find a set with having as few elements as possible, or as few below a given (p. 2). Zero is admitted as an element throughout, so all sets consist of natural numbers and . A set with is a Basis -ter Ordnung für ; for it is a basis of order für die Zahl , and one with the fewest elements is a Minimalbasis -ter Ordnung für . Counting the sums () of numbers against the elements of gives, for every basis of order 2, (2) , that is (3) . Schur's conjecture (p. 2): the order of magnitude is right, for the size of a minimal basis with a constant independent of . Stöhr's remark (p. 3): writing the natural numbers in base 3 gives . The paper's results are summarized: § 1 proves Schur's conjecture in the sharper form (4) (), with explicit bases whose elements are at most ; § 2 gives for (all natural numbers) a basis of order 2 with fewer than elements below for ; §§ 3--5 improve the lower bound (3), or the upper bound (2), to for large with a definite independent of and ; §§ 6--8 extend §§ 1--2 to every : bases of order for with fewer than elements, for with fewer than elements below , and the "erweiterte Basis" property (5) (pp. 3--4), that every is a signed sum $\varepsilon_1a_{\alpha_1}+\cdots+ \varepsilon_ha_{\alpha_h}$ for each sign pattern other than all minus.
- § 1, finite 2-bases (pp. 4--9, page images). The problem, quoted (p. 4): "Gegeben ist eine natürliche Zahl . Man bestimme ein System von möglichst wenig nichtnegativen ganzen Zahlen derart, daß sich alle ganzen Zahlen als Summe von zwei Zahlen des Systems darstellen lassen." It is turned around: given , find the 2-basis of elements representing the longest interval ; "Ist nämlich die größte ganze Zahl derart, daß sich bei gegebenem alle Zahlen durch eine Basis zweiter Ordnung mit Elementen darstellen lassen, so liefert die kleinste ganze Zahl , für die ist, zu gegebenem das gesuchte " (p. 4). The system counts the zero: (6) begins with and has elements, so Rohrbach's is the site's and Kohonen's for Problem 791, and is Kohonen's (Mrose's counts positive elements and is Kohonen's ). Definition: a system is symmetrisch if belongs to it with each . Satz 1 (p. 4, quoted): "Jedes symmetrische System , das eine Basis zweiter Ordnung für die Zahl ist, ist von selbst eine Basis zweiter Ordnung für die (letztmögliche) Zahl ", by . Satz 2 (p. 5, quoted): "Für jedes Paar natürlicher Zahlen ist das System (6) ; ; eine Basis zweiter Ordnung von Elementen für die Zahl ." Its Folgerung chooses (7) , (8) and reaches (9) with or for . Satz 3 (p. 5, quoted): "Die Anzahl der Elemente einer Minimalbasis zweiter Ordnung für eine natürliche Zahl ist kleiner als ." Proof (p. 6): the least with (10) satisfies , so for , and are checked directly. Example : , and the basis (6) with , , , reaches . Shifting the elements above down gives a basis with elements at most . The longer symmetric system (11) (pp. 6--7) continues (6) with further rows of consecutive numbers, each after a jump of , and closes it symmetrically with a row of numbers spaced apart and a last row of consecutive numbers; Satz 4 (p. 8, quoted): "Für je drei natürliche Zahlen ist das System (11) eine Basis zweiter Ordnung von Elementen für die Zahl (13) ." With (14) : for even , , , give (15) , or ; for odd , and a choice by give (16) with tabulated . The paper then notes that (11) improves on (6) only in the term of (9) linear in , and states the conjecture (p. 9, quoted): "Es ist zu vermuten, daß ist."
- § 2, an infinite 2-basis (pp. 9--10, page images). Satz 5 (p. 9): there are 2-bases of such that for every some has (17) for all , counting the basis elements below . Proof: take an odd with , a 2-basis of from § 1 with elements, and let be the numbers whose base- digits all lie in ; digitwise representation shows , and (21)--(23) give . A closing remark (p. 10): replacing the of (20) by the exact minimal-basis constant changes only to in the exponent, "Nach (3) und (4) gilt aber für sicher ".
- § 3, the first lower-bound method (pp. 11--15; pp. 11, 14 and 15 on the page images, pp. 12--13 in the text layer). The counting bound (3) uses all sums; only distinct sums count. Satz 6 (p. 11, quoted): "Gegeben seien zwei natürliche Zahlen und mit (24) , ferner voneinander verschiedene nichtnegative ganze Zahlen . Dann können von den Summenwerten , die nicht übertreffen, höchstens voneinander verschieden ausfallen." The proof splits on whether all (Fall 1, pp. 11--13: coincidences are counted through equal differences, giving the bound (29)) or elements exceed (Fall 2, pp. 13--14: those elements' sums exceed , and (31)--(32) with an elementary extreme-value argument finish ; is checked directly). Folgerung (pp. 14--15, quoted): if the system is a 2-basis for , (24) holds by (2), so : "Für jede Basis zweiter Ordnung von Elementen für die Zahl gilt , und insbesondere, etwas schärfer als (3), ."
- § 4, the second method under a restriction (pp. 15--18, page images). For a 2-basis of , split into eight equal intervals with elements in ; the sums from elements must cover each initial segment, giving (33)--(36) and, with all elements below ((37): ), the symmetric versions (34a)--(36a). Manipulating (38)--(43) with five-place values of yields and, after a second squaring, (44) (p. 17); is reduced to the largest multiple of 8 below , giving for large . Satz 7 (p. 18, quoted): "Bei jeder Basis zweiter Ordnung für die natürliche Zahl mit Basiselementen, die sämtlich nicht größer als sind, gilt, sobald nur hinreichend groß ist, die Abschätzung (45) ."
- § 5, the general case (pp. 18--23; pp. 18, 19 and 23 on the page images, pp. 20--22 in the text layer). Without the restriction, need not vanish and (46) . The paper says (p. 18) that the method still gives for large with an explicit independent of and , as in (45), but with a worse constant, and that it settles for proving the inequality it labels (47), quoted: " für genügend große "; a further refinement of the method, it adds, would surely do better. With , the number of sums exceeding is at least (48) $A=\frac{\eta^2+\eta}2+\varrho_8(\varrho_2+\varrho_3+\varrho_4)+ \varrho_7(\varrho_3+\varrho_4)+\varrho_6\varrho_4$; if then gives (47) directly, so (49) may be assumed, and an indirect argument from (50) in the two cases (pp. 19--20) and (pp. 20--23) ends in a contradiction in each, (p. 20) and, after (65), (p. 23); is again reduced to .
- §§ 6--8, higher order (pp. 23--30, page images). Satz 8 (p. 24): for natural numbers and (66) , , the system of the rows ; ; …; is a basis of order with elements for (67) , with a Zusatz on extending it by numbers at gaps at most . Satz 9 (p. 25, quoted): "Es sei die größte ganze Zahl mit der Eigenschaft, daß sich bei gegebenem alle Zahlen durch eine Basis -ter Ordnung von Elementen darstellen lassen. Dann gilt , genauer ", the upper bound from (68) by counting -combinations with repetition, the lower from with , (69)--(70). Its Folgerung (pp. 25--26) gives (72) for , "in genauer Verallgemeinerung von Satz 3". § 7 defines the erweiterte Basis (73) and proves Satz 10 (p. 27), that is one for its last element, with a Zusatz (p. 28); Satz 11 (p. 28) symmetrizes about into a basis of order with elements for , and p. 29 remarks that the dimension of (70) and (72) "ungeändert bleiben dürfte" under such refinements. § 8, Satz 12 (pp. 29--30): has a basis of order with for , by the base- digit construction of § 2 with (72). The paper ends with the received date; there is no reference list.
Compiled scope
The paper is compiled at statement depth for the results Problem 791 consumes: the formulation through (p. 4), Satz 3 (p. 5) with the construction (6) of Satz 2 behind it, the conjecture of p. 9, the Folgerung to Satz 6 (p. 15) and inequality (47) with Satz 7 (p. 18), read on the page images and paged on satz_3, inequality_47 and conjecture. The proofs of Satz 1 to Satz 3 were followed; the proofs of §§ 3--5 were read for structure only and their numerical inequalities were not checked. Satz 4 is recorded as a statement read on the page images. The main results of §§ 2 and 6--8 are paged on their own result pages: Satz 5 (p. 9) on satz_5, Satz 8, Satz 9 and (72) (pp. 24--26) on satz_9, Satz 10 and Satz 11 (pp. 26--29) on satz_10 and Satz 12 (pp. 29--30) on satz_12; the proofs of Satz 5, Satz 8, Satz 9 and (72) were followed on the page images, and those of Satz 10 to Satz 12 read for structure. Nothing here is independently reviewed.
Bears on. #791: the paper defines the problem's function in the site's exact form, being "die kleinste ganze Zahl , für die ist," (printed p. 4, PDF p. 4; the count includes the zero, as the site's does), and supplies the classical bounds the site attributes to it. The upper bound is Satz 3 (p. 5), "Die Anzahl der Elemente einer Minimalbasis zweiter Ordnung für eine natürliche Zahl ist kleiner als ", proved by the explicit basis (6) of Satz 2 with the parameters (7)--(8) and the range (9) ; it is not the trivial bound but a construction with a positive linear term. The lower bound is the Folgerung to Satz 6 (p. 15), "Für jede Basis zweiter Ordnung von Elementen für die Zahl gilt ", that is , sharpened by (47) (p. 18), " für genügend große ": since , the minimal basis has for large , so , the site's with and the " for some " of Erdős 1973 with ; Satz 7's (p. 18) holds only for bases whose elements are at most and is not the unconditional constant. The "in particular" question is the paper's conjecture (p. 9), "Es ist zu vermuten, daß ist", which is ; Erdős 1973 reports it as "" and the site as , and all three forms are refuted by Mrose's equation (3), . Satz 9 (p. 25) at , , is weaker on both sides than (9) and, for , the Folgerung to Satz 6, and the problem page does not use it. The problem page reads these statements on the page images at statement depth; the proof of Satz 3 was followed, and the proofs of §§ 3--5 were not checked.
Results.
- Satz 3 (p. 5): a minimal 2-basis for has fewer than elements, from the symmetric basis (6) of Satz 2 with (7)--(9).
- Inequality (47) (p. 18), with the Folgerung to Satz 6 (p. 15) and Satz 7 (p. 18): every 2-basis of elements for has , and once is large.
- Conjecture (p. 9): ; refuted by Mrose 1979.
- Satz 5 (p. 9): bases of order 2 for with fewer than elements below for .
- Satz 9 (p. 25), with Satz 8 (p. 24) and (72) (p. 26): , and a minimal basis of order for has fewer than elements.
- Satz 10 (p. 27), with the definition (73) (p. 26) and Satz 11 (p. 28): is an extended basis of order for its last element.
- Satz 12 (pp. 29--30): a basis of order for with fewer than elements below for .
No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.