Wiki
Wiki

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 km<cnlog⁡2/log⁡3k_m<cn^{\log2/\log3} (p. 3). It is the origin of Problem 791's function and conjecture, as Erdős 1973 reports them, and the paper whose constant c2=1c_2=1 Mrose 1979 (p. 118) records as the previous record before his 8/78/7.

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 hh 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 n2(k)n_2(k), 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 n=100n=100 (p. 6); Satz 4 with (13)--(16) (p. 8); the conjecture n2(k)=k2/4+O(k)n_2(k)=k^2/4+O(k) 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 2(x+y)+xz2(x+y)+xz 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 1≤x,y≤71\le x,y\le7 and 1≤z≤41\le z\le4, and in every case the system had the printed number of elements and its pairwise sums covered {0,…,n}\{0,\ldots,n\} for the printed nn; the parameter choices (7)--(8) and the even case of Satz 4's Folgerung reproduced (9) and (15) for k≤59k\le59. Nothing here is independently reviewed.

Contents

  • Introduction (pp. 1--4, page images). Schnirelmann's sum A+BA+B of sets of natural numbers, hAhA for the hh-fold sum, and the classical question (1), Γ⊆hA\Gamma\subseteq hA. The paper studies the converse: given Γ\Gamma and a fixed hh, find a set AA with Γ⊆hA\Gamma\subseteq hA having as few elements as possible, or as few below a given nn (p. 2). Zero is admitted as an element throughout, so all sets consist of natural numbers and 00. A set AA with Γ⊆hA\Gamma\subseteq hA is a Basis hh-ter Ordnung für Γ\Gamma; for N={0,1,…,n}N=\{0,1,\ldots,n\} it is a basis of order hh für die Zahl nn, and one with the fewest elements is a Minimalbasis hh-ter Ordnung für nn. Counting the (k2+k)/2(k^2+k)/2 sums aκ+aλa_\kappa+a_\lambda (κ≤λ\kappa\le\lambda) of kk numbers against the n+1n+1 elements of NN gives, for every basis of order 2, (2) k2+k2≥n+1\frac{k^2+k}2\ge n+1, that is (3) k≥2n+94−12k\ge\sqrt{2n+\frac94}-\frac12. Schur's conjecture (p. 2): the order of magnitude O(n)O(\sqrt n) is right, km<cnk_m<c\sqrt n for the size kmk_m of a minimal basis with a constant cc independent of nn. Stöhr's remark (p. 3): writing the natural numbers in base 3 gives km<cnlog⁡2/log⁡3<cn0.631k_m<cn^{\log2/\log3}<cn^{0.631}. The paper's results are summarized: § 1 proves Schur's conjecture in the sharper form (4) km<2nk_m<2\sqrt n (n>1n>1), with explicit bases whose elements are at most [n+12][\frac{n+1}2]; § 2 gives for Γ=Ω\Gamma=\Omega (all natural numbers) a basis of order 2 with fewer than n1/2+εn^{1/2+\varepsilon} elements below nn for n≥n0(ε)n\ge n_0(\varepsilon); §§ 3--5 improve the lower bound (3), or the upper bound (2), to n<(12−α)k2n<(\frac12-\alpha)k^2 for large kk with a definite α\alpha independent of nn and kk; §§ 6--8 extend §§ 1--2 to every h>2h>2: bases of order hh for NN with fewer than hnhh\sqrt[h]n elements, for Ω\Omega with fewer than n1/h+εn^{1/h+\varepsilon} elements below nn, and the "erweiterte Basis" property (5) (pp. 3--4), that every 0≤b≤n0\le b\le n 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 nn. Man bestimme ein System von möglichst wenig nichtnegativen ganzen Zahlen a1,a2,…,aka_1,a_2,\ldots,a_k derart, daß sich alle ganzen Zahlen 0,1,2,…,n0,1,2,\ldots,n als Summe von zwei Zahlen des Systems darstellen lassen." It is turned around: given kk, find the 2-basis of kk elements representing the longest interval 0,1,…,n0,1,\ldots,n; "Ist nämlich n2(k)n_2(k) die größte ganze Zahl derart, daß sich bei gegebenem kk alle Zahlen 0,1,2,…,n2(k)0,1,2,\ldots,n_2(k) durch eine Basis zweiter Ordnung mit kk Elementen darstellen lassen, so liefert die kleinste ganze Zahl kk, für die n2(k)≥nn_2(k)\ge n ist, zu gegebenem nn das gesuchte kk" (p. 4). The system counts the zero: (6) begins with 00 and has 2x+y2x+y elements, so Rohrbach's kk is the site's ∣A∣|A| and Kohonen's kk for Problem 791, and n2(k)n_2(k) is Kohonen's n(k)n(k) (Mrose's n2(k)n_2(k) counts positive elements and is Kohonen's n(k+1)n(k+1)). Definition: a system a1,…,aka_1,\ldots,a_k is symmetrisch if ak−aκa_k-a_\kappa belongs to it with each aκa_\kappa. Satz 1 (p. 4, quoted): "Jedes symmetrische System a1,a2,…,aka_1,a_2,\ldots,a_k, das eine Basis zweiter Ordnung für die Zahl aka_k ist, ist von selbst eine Basis zweiter Ordnung für die (letztmögliche) Zahl 2ak2a_k", by 2ak−g=(ak−aκ)+(ak−aλ)2a_k-g=(a_k-a_\kappa)+(a_k-a_\lambda). Satz 2 (p. 5, quoted): "Für jedes Paar natürlicher Zahlen x,yx,y ist das System (6) 0,1,2,…,x−10,1,2,\ldots,x-1; 2x−1,3x−1,…,(y+1)x−12x-1,3x-1,\ldots,(y+1)x-1; (y+2)x−1,(y+2)x,…,(y+3)x−2(y+2)x-1,(y+2)x,\ldots,(y+3)x-2 eine Basis zweiter Ordnung von 2x+y2x+y Elementen für die Zahl 2(y+3)x−4=2xy+6x−42(y+3)x-4=2xy+6x-4." Its Folgerung chooses (7) x=[k+44]x=[\frac{k+4}4], (8) y=k−2[k+44]y=k-2[\frac{k+4}4] and reaches (9) n=2xy+6x−4=k24+32k−γn=2xy+6x-4=\frac{k^2}4+\frac32k-\gamma with γ=2,74,2\gamma=2,\frac74,2 or 114\frac{11}4 for k≡0,1,2,3(mod4)k\equiv0,1,2,3\pmod4. Satz 3 (p. 5, quoted): "Die Anzahl der Elemente einer Minimalbasis zweiter Ordnung für eine natürliche Zahl n>1n>1 ist kleiner als 2n2\sqrt n." Proof (p. 6): the least kk with (10) k24+32k−114≥n\frac{k^2}4+\frac32k-\frac{11}4\ge n satisfies k2+4k−16<4nk^2+4k-16<4n, so k<−2+2n+5≤2nk<-2+2\sqrt{n+5}\le2\sqrt n for n≥4n\ge4, and n=2,3n=2,3 are checked directly. Example n=100n=100: k<18.6k<18.6, and the basis (6) with x=5x=5, y=8y=8, 0,1,2,3,4,9,14,19,24,29,34,39,44,49,50,51,52,530,1,2,3,4,9,14,19,24,29,34,39,44,49,50,51,52,53, reaches 106106. Shifting the elements above [ak+12][\frac{a_k+1}2] down gives a basis with elements at most [n+12][\frac{n+1}2]. The longer symmetric system (11) (pp. 6--7) continues (6) with z−1z-1 further rows of xx consecutive numbers, each after a jump of u=(y+3)x−1u=(y+3)x-1, and closes it symmetrically with a row of yy numbers spaced xx apart and a last row of xx consecutive numbers; Satz 4 (p. 8, quoted): "Für je drei natürliche Zahlen x,y,zx,y,z ist das System (11) eine Basis zweiter Ordnung von 2(x+y)+xz2(x+y)+xz Elementen für die Zahl (13) n=2xyz+2xy+8xz+2x−4z−2n=2xyz+2xy+8xz+2x-4z-2." With (14) 2(x+y)+xz=k2(x+y)+xz=k: for even k≥12k\ge12, x=2x=2, y=k−42−[k+24]y=\frac{k-4}2-[\frac{k+2}4], z=[k+24]z=[\frac{k+2}4] give (15) n=k24+2k−δn=\frac{k^2}4+2k-\delta, δ=6\delta=6 or 77; for odd k≥43k\ge43, x=3x=3 and a choice by k mod 12k\bmod12 give (16) n=k24+116k−δ′n=\frac{k^2}4+\frac{11}6k-\delta' with tabulated δ′\delta'. The paper then notes that (11) improves on (6) only in the term of (9) linear in kk, and states the conjecture (p. 9, quoted): "Es ist zu vermuten, daß n2(k)=k24+O(k)n_2(k)=\frac{k^2}4+O(k) ist."
  • § 2, an infinite 2-basis (pp. 9--10, page images). Satz 5 (p. 9): there are 2-bases of Ω\Omega such that for every ε>0\varepsilon>0 some n0(ε)n_0(\varepsilon) has (17) k(n)<n1/2+εk(n)<n^{1/2+\varepsilon} for all n≥n0n\ge n_0, k(n)k(n) counting the basis elements below nn. Proof: take an odd g>2g>2 with log⁡2/log⁡g≤ε/2\log2/\log g\le\varepsilon/2, a 2-basis BB of g−1g-1 from § 1 with l<2g−1l<2\sqrt{g-1} elements, and let AA be the numbers whose base-gg digits all lie in BB; digitwise representation shows A+A=ΩA+A=\Omega, and (21)--(23) give k(n)<(gn)1/2+log⁡2/log⁡gk(n)<(gn)^{1/2+\log2/\log g}. A closing remark (p. 10): replacing the 22 of (20) by the exact minimal-basis constant cc changes only log⁡2\log2 to log⁡c\log c in the exponent, "Nach (3) und (4) gilt aber für n≥n0n\ge n_0 sicher 1,4<c<21{,}4<c<2".
  • § 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 (k2+k)/2(k^2+k)/2 sums; only distinct sums count. Satz 6 (p. 11, quoted): "Gegeben seien zwei natürliche Zahlen k≥5k\ge5 und nn mit (24) n≤k2+k2−1n\le\frac{k^2+k}2-1, ferner kk voneinander verschiedene nichtnegative ganze Zahlen a1,a2,…,aka_1,a_2,\ldots,a_k. Dann können von den Summenwerten aκ+aλa_\kappa+a_\lambda, die nn nicht übertreffen, höchstens k22+1\frac{k^2}2+1 voneinander verschieden ausfallen." The proof splits on whether all aκ≤[n+12]a_\kappa\le[\frac{n+1}2] (Fall 1, pp. 11--13: coincidences aκ+aλ=aμ+aνa_\kappa+a_\lambda=a_\mu+a_\nu are counted through equal differences, giving the bound (29)) or k2≥1k_2\ge1 elements exceed [n+12][\frac{n+1}2] (Fall 2, pp. 13--14: those elements' sums exceed nn, and (31)--(32) with an elementary extreme-value argument finish k≥14k\ge14; 5≤k≤135\le k\le13 is checked directly). Folgerung (pp. 14--15, quoted): if the system is a 2-basis for nn, (24) holds by (2), so k22+1≥n+1\frac{k^2}2+1\ge n+1: "Für jede Basis zweiter Ordnung von kk Elementen für die Zahl nn gilt n≤k22n\le\frac{k^2}2, und insbesondere, etwas schärfer als (3), km≥2nk_m\ge\sqrt2\sqrt n."
  • § 4, the second method under a restriction (pp. 15--18, page images). For a 2-basis a1,…,aka_1,\ldots,a_k of n≡0(mod8)n\equiv0\pmod8, split [0,n][0,n] into eight equal intervals J1,…,J8J_1,\ldots,J_8 with ϱν\varrho_\nu elements in JνJ_\nu; the sums from ϱ\varrho elements must cover each initial segment, giving (33)--(36) and, with all elements below n/2n/2 ((37): ϱ5=⋯=ϱ8=0\varrho_5=\cdots=\varrho_8=0), the symmetric versions (34a)--(36a). Manipulating (38)--(43) with five-place values of 2,3,6\sqrt2,\sqrt3,\sqrt6 yields n<0.4666(k+1)2n<0.4666(k+1)^2 and, after a second squaring, (44) n<0.46532(k+1)2n<0.46532(k+1)^2 (p. 17); n≢0(mod8)n\not\equiv0\pmod8 is reduced to the largest multiple n′n' of 8 below nn, giving n<0.46533(k+1)2n<0.46533(k+1)^2 for large kk. Satz 7 (p. 18, quoted): "Bei jeder Basis zweiter Ordnung für die natürliche Zahl nn mit kk Basiselementen, die sämtlich nicht größer als [n+12][\frac{n+1}2] sind, gilt, sobald nur kk hinreichend groß ist, die Abschätzung (45) n<0,4654k2n<0{,}4654k^2."
  • § 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, ϱ5,…,ϱ8\varrho_5,\ldots,\varrho_8 need not vanish and (46) k=∑18ϱνk=\sum_1^8\varrho_\nu. The paper says (p. 18) that the method still gives n<(12−α)k2n<(\frac12-\alpha)k^2 for large kk with an explicit α\alpha independent of nn and kk, as in (45), but with a worse constant, and that it settles for proving the inequality it labels (47), quoted: "n<0,4992k2n<0{,}4992k^2 für genügend große kk"; a further refinement of the method, it adds, would surely do better. With η=ϱ5+⋯+ϱ8\eta=\varrho_5+\cdots+\varrho_8, the number of sums exceeding nn 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 A≥0.00081k2A\ge0.00081k^2 then n≤k2+k2−1−An\le\frac{k^2+k}2-1-A gives (47) directly, so (49) η<0.041k\eta<0.041k may be assumed, and an indirect argument from (50) n≥0.4992k2n\ge0.4992k^2 in the two cases ϱ3≥ϱ2\varrho_3\ge\varrho_2 (pp. 19--20) and ϱ2>ϱ3\varrho_2>\varrho_3 (pp. 20--23) ends in a contradiction in each, R<0R<0 (p. 20) and, after (65), R′<0R'<0 (p. 23); n≢0(mod8)n\not\equiv0\pmod8 is again reduced to n′n'.
  • §§ 6--8, higher order (pp. 23--30, page images). Satz 8 (p. 24): for natural numbers x1,…,xhx_1,\ldots,x_h and (66) d1=1d_1=1, dν=x1d1+x2d2+⋯+(xν−1+1)dν−1d_\nu=x_1d_1+x_2d_2+\cdots+(x_{\nu-1}+1)d_{\nu-1}, the system ShS_h of the rows 0,d1,2d1,…,x1d10,d_1,2d_1,\ldots,x_1d_1; x1d1+d2,…,x1d1+x2d2x_1d_1+d_2,\ldots,x_1d_1+x_2d_2; …; ∑1h−1xνdν+dh,…,∑1hxνdν\sum_1^{h-1}x_\nu d_\nu+d_h,\ldots,\sum_1^hx_\nu d_\nu is a basis of order hh with 1+x1+⋯+xh1+x_1+\cdots+x_h elements for (67) dh+1−1d_{h+1}-1, with a Zusatz on extending it by numbers at gaps at most dhd_h. Satz 9 (p. 25, quoted): "Es sei nh(k)n_h(k) die größte ganze Zahl mit der Eigenschaft, daß sich bei gegebenem kk alle Zahlen 0,1,2,…,nh(k)0,1,2,\ldots,n_h(k) durch eine Basis hh-ter Ordnung von kk Elementen darstellen lassen. Dann gilt nh(k)=O(kh)n_h(k)=O(k^h), genauer (kh)h<nh(k)<(k+h−1h)(\frac kh)^h<n_h(k)<\binom{k+h-1}h", the upper bound from (68) by counting hh-combinations with repetition, the lower from ShS_h with x2=⋯=xh=[kh]x_2=\cdots=x_h=[\frac kh], (69)--(70). Its Folgerung (pp. 25--26) gives (72) k<hnhk<h\sqrt[h]n for h≥3h\ge3, "in genauer Verallgemeinerung von Satz 3". § 7 defines the erweiterte Basis (73) and proves Satz 10 (p. 27), that ShS_h is one for its last element, with a Zusatz (p. 28); Satz 11 (p. 28) symmetrizes ShS_h about m=∑1h−1xνdν+xh+12dhm=\sum_1^{h-1}x_\nu d_\nu+\frac{x_h+1}2d_h into a basis of order hh with 2(1+∑1h−1xν)+xh2(1+\sum_1^{h-1}x_\nu)+x_h elements for n=2mhn=2mh, and p. 29 remarks that the dimension hh of (70) and (72) "ungeändert bleiben dürfte" under such refinements. § 8, Satz 12 (pp. 29--30): Ω\Omega has a basis of order hh with k(n)<n1/h+εk(n)<n^{1/h+\varepsilon} for n≥n0(ε)n\ge n_0(\varepsilon), by the base-gg 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 n2(k)n_2(k) (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, g(n)g(n) being "die kleinste ganze Zahl kk, für die n2(k)≥nn_2(k)\ge n ist," (printed p. 4, PDF p. 4; the count kk includes the zero, as the site's does), and supplies the classical bounds the site attributes to it. The upper bound g(n)2≤4ng(n)^2\le4n is Satz 3 (p. 5), "Die Anzahl der Elemente einer Minimalbasis zweiter Ordnung für eine natürliche Zahl n>1n>1 ist kleiner als 2n2\sqrt n", proved by the explicit basis (6) of Satz 2 with the parameters (7)--(8) and the range (9) n=k24+32k−γn=\frac{k^2}4+\frac32k-\gamma; it is not the trivial bound but a construction with a positive linear term. The lower bound (2+c)n≤g(n)2(2+c)n\le g(n)^2 is the Folgerung to Satz 6 (p. 15), "Für jede Basis zweiter Ordnung von kk Elementen für die Zahl nn gilt n≤k22n\le\frac{k^2}2", that is g(n)2≥2ng(n)^2\ge2n, sharpened by (47) (p. 18), "n<0,4992k2n<0{,}4992k^2 für genügend große kk": since g(n)→∞g(n)\to\infty, the minimal basis has n<0.4992 g(n)2n<0.4992\,g(n)^2 for large nn, so g(n)2>(2.0032…)ng(n)^2>(2.0032\ldots)n, the site's (2+c)n(2+c)n with c=0.0032c=0.0032 and the "g(n)>(1+ε)2ng(n)>(1+\varepsilon)\sqrt{2n} for some ε>0\varepsilon>0" of Erdős 1973 with ε≈0.0008\varepsilon\approx0.0008; Satz 7's 0.46540.4654 (p. 18) holds only for bases whose elements are at most [n+12][\frac{n+1}2] and is not the unconditional constant. The "in particular" question is the paper's conjecture (p. 9), "Es ist zu vermuten, daß n2(k)=k24+O(k)n_2(k)=\frac{k^2}4+O(k) ist", which is g(n)=2n+O(1)g(n)=2\sqrt n+O(1); Erdős 1973 reports it as "g(n)=2n+o(1)g(n)=2\sqrt n+o(1)" and the site as g(n)∼2n1/2g(n)\sim2n^{1/2}, and all three forms are refuted by Mrose's equation (3), n2(k)≥87(k2)2+O(k)n_2(k)\ge\frac87(\frac k2)^2+O(k). Satz 9 (p. 25) at h=2h=2, k24<n2(k)<k2+k2\frac{k^2}4<n_2(k)<\frac{k^2+k}2, is weaker on both sides than (9) and, for k≥5k\ge5, 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 n>1n>1 has fewer than 2n2\sqrt n 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 kk elements for nn has n≤k2/2n\le k^2/2, and n<0.4992k2n<0.4992k^2 once kk is large.
  • Conjecture (p. 9): n2(k)=k24+O(k)n_2(k)=\frac{k^2}4+O(k); refuted by Mrose 1979.
  • Satz 5 (p. 9): bases of order 2 for Ω\Omega with fewer than n1/2+εn^{1/2+\varepsilon} elements below nn for n≥n0(ε)n\ge n_0(\varepsilon).
  • Satz 9 (p. 25), with Satz 8 (p. 24) and (72) (p. 26): (kh)h<nh(k)<(k+h−1h)(\frac kh)^h<n_h(k)<\binom{k+h-1}h, and a minimal basis of order h≥3h\ge3 for nn has fewer than hnhh\sqrt[h]n elements.
  • Satz 10 (p. 27), with the definition (73) (p. 26) and Satz 11 (p. 28): ShS_h is an extended basis of order hh for its last element.
  • Satz 12 (pp. 29--30): a basis of order hh for Ω\Omega with fewer than n1/h+εn^{1/h+\varepsilon} elements below nn for n≥n0(ε)n\ge n_0(\varepsilon).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.