Ruzsa 1999 erdos integers

../

question_p147: Ruzsa's record of Erdős's question whether the set of numbers of the form 2^m 3^n is an essential component, with the survey's definition of an essential component; the question of Problem 1146 in the survey's words, left unanswered by its author, who has no plausible guess.

---

Imre Z. Ruzsa, Erdős and the Integers, Journal of Number Theory 79 (1999), no. 1, 115--163, Article ID jnth.1999.2395 (printed on p. 115; DOI 10.1006/jnth.1999.2395); communicated by Alan C. Woods, received June 2, 1997, published online October 8, 1999; the author at the Mathematical Institute of the Hungarian Academy of Sciences, supported by a Hungarian National Foundation for Scientific Research grant (footnote, p. 115). The copyright line on p. 115 reads "Copyright © 1998 by the author. Reproduction of this article by any means for noncommercial purposes is permitted." Cited as [Ru99] on the problem pages. The paper is a survey of Erdős's work in number theory written after his death, and by its own introduction (p. 115) it describes "later achievements that grew out of his ideas" as well as his results, leaves out the statistical theory of partitions and irrationality, and calls itself "in many aspects incomplete". Its reference list (pp. 154--163) has no numbers; citations are by author and year, and "in citations if no author is given (or can be inferred), the author is Erdős" (p. 116). The source read for this card is the publisher's version of record; no preprint or repository version is known here.

The copy read for this card is the publisher's production PDF from the journal's open archive: 49 pages, printed pp. 115--163 = PDF pp. 1--49 (printed p. $n$ is PDF p. $n-114$), typeset from the journal's composition and distilled in September 1999 (Acrobat Distiller 3.02 per the file's metadata, modified November 2014), with a text layer that reads the prose cleanly and garbles the displays (Greek letters, the Schnirelmann-density symbol $\sigma$, subscripts, inequality signs and the prefix-superscript notation for $\log_2$ come out as stray digits and letters). Provenance: the copy was obtained free of charge on 2026-09-22 from the publisher's open archive through the library's acquisition, from https://www.sciencedirect.com/science/article/pii/S0022314X99923958; 440,151 bytes. The file prints "Copyright © 1998 by the author. Reproduction of this article by any means for noncommercial purposes is permitted." on p. 115, a permission for noncommercial reproduction and not a named license, every other right reserved.

Read status: claims checked for the title, the received and published dates and the copyright line (p. 115), the notation paragraph (p. 116), the definition of an essential component and the quotation from Halberstam and Roth (p. 146), the size result on essential components and the question on the numbers $2^m3^n$ (p. 147), and the opening of § 16 with the bounds on the distinct-subset-sums function $g(n)$ (p. 151), each read clause by clause on the page images of PDF pp. 1, 2, 32, 33 and 37 on 2026-09-22; the last page of the references (p. 163, PDF p. 49) was read on the page image. The rest of the survey (pp. 116--154) and the reference list (pp. 154--163) were read in the text layer for structure only, to map the sections and to locate the bibliography entries named below. The survey states results with pointers to the literature and gives proofs only in sketch; no proof was checked, and nothing here is independently reviewed.

Contents

• Introduction (pp. 115--116, page images). Scope and caveats: about 500 papers in number theory alone; since Erdős himself reported others' proofs and disproofs of his conjectures, the survey covers later work that grew out of his ideas as well as his own results, and it warns (p. 116, quoted) that "Whenever I say something is 'the record up to date,' this reflects my knowledge, which may be deficient". Notation (p. 116): "$\log_k$ denotes $k$ times iterated logarithm"; "$f\asymp g$ for functions $f$, $g$ means that $f/g$ is between positive bounds". The base-two logarithm is printed throughout as a prefix superscript, ${}^2\!\log n$; this card writes it $\log_2n$. The five parts: I. Primes; II. Divisors, sets of multiples, primitive sequences; III. Arithmetical functions; IV. Additive problems; V. Miscellaneous.
• Part I, Primes (pp. 116--122, text layer). § 1, The number of primes (p. 116): Erdős's proof of Chebyshev's theorem from Legendre's formula, and the elementary proof of the prime number theorem from Selberg's formula. § 2, Gaps between primes (p. 119): large gaps (Rankin's extra $\log_4$ factor), small gaps, and the Erdős--Turán results on the consecutive differences $d_n$.
• Part II, Divisors, sets of multiples, primitive sequences (pp. 122--127, text layer). § 3, Abundant numbers (p. 122); § 4, The existence of density (p. 124), the Davenport--Erdős theorem on sets of multiples; § 5, Primitive sequences (p. 125), Behrend's and Erdős's bounds; § 6, Statistical theory of divisors (p. 126), the question whether almost all integers have two divisors with $d<d'<2d$ and its answer by Maier and Tenenbaum.
• Part III, Arithmetical functions (pp. 127--138, text layer). § 7, Foundations of probabilistic number theory (p. 127): the Erdős--Wintner and Erdős--Kac theorems and their descendants. § 8, Individual functions (p. 134): $\varphi$, $\sigma$, $d(n)$, the number of distinct values of Euler's function, and related conjectures.
• Part IV, Additive problems (pp. 138--148; pp. 146--147 on the page images, the rest in the text layer). § 9, Classical additive theory (p. 138). § 10, Bases (p. 139): a basis of order $k$, Schnirelmann density $\sigma(B)=\inf_{n}B(n)/n$, Schnirelmann's inequality (10.1), Erdős's inequality (10.2), $\sigma(A+B)\ge\sigma(A)+\frac1{2k}\sigma(A)(1-\sigma(A))$ for a basis $B$ of order $k$ with $0\in B$, Plünnecke's improvement (10.3), thin bases with $r(n)\asymp\log n$ and the Erdős--Fuchs theorem. § 11, Sidon sets (p. 142): finite and infinite $B_2$ and $B_h$ sets, the Erdős--Turán bound, the Ajtai--Komlós--Szemerédi construction and the multiplicative analogue. § 12, Random sets (p. 144): additive complements and Lorentz's theorem, the Erdős--Rényi random sets, Erdős--Ulam, and the essential-component passage quoted on question_p147: a set $\mathscr V$ "is an essential component, if for every set $\mathscr A$ with $0<\sigma(\mathscr A)<1$ we have $\sigma(\mathscr A+\mathscr V)>\sigma(\mathscr A)$ (or an analogous requirement with asymptotic density)" (p. 146); every basis is one by Erdős's inequality, the converse is false by Linnik's thin essential component, the Erdős--Roth probabilistic proof was never published (quoted from Halberstam and Roth, 1966, p. 35), and the author's own 1987 paper gives the complete answer on size: "for every fixed $\varepsilon>0$ we can find an essential component with $V(x)=O((\log x)^{1+\varepsilon})$, but $V(x)=O((\log x)^{1+o(1)})$ is impossible (Ruzsa, 1987)" (p. 147). Then, quoted: "The simplest set with a chance to be an essential component is the collection of numbers in the form $2^m3^n$, and Erdős often asked whether it is an essential component or not; I do not even have a plausible guess." A filing observation, not a review verdict: p. 146 cites "Erdős' inequality (11.2)" for the fact that every basis is an essential component, but the inequality on bases is displayed as (10.2) on p. 140 and § 11 has no display numbered (11.2); the label is read here as a misprint for (10.2). § 13, Further additive--combinatorial questions (p. 147): arithmetical progressions from Erdős--Turán 1936 through Szemerédi, Behrend, Roth, Heath-Brown--Szemerédi and Gowers, the Erdős--Ginzburg--Ziv theorem, and the Erdős--Heilbronn conjecture with its proof by Dias da Silva and Hamidoune.
• Part V, Miscellaneous (pp. 148--154; p. 151 on the page image, the rest in the text layer). § 14, Consecutive integers, binomial coefficients (p. 148). § 15, Uniform distribution, discrepancy (p. 149): the Erdős--Turán inequality and the de Bruijn--Erdős splitting sequence. § 16, The kitchen sink (p. 151), named after the last chapter of Erdős and Spencer (1974): under that book's subheading "A $300 problem" it poses the question of the largest $k$ for which integers $0<a_1<\cdots<a_k\le n$ can have all $2^k$ subset sums distinct, writes $g(n)$ for this maximum, and records that the powers of $2$ and a counting argument give

$$1+[\log_2n]\le g(n)\le\log_2n+\log_2\log_2n+o(1),$$

that Erdős and Moser cut the $\log_2\log_2n$ term of the upper bound to half its size (their argument appeared in Erdős, 1956b), and that a Conway--Guy construction, reported in Guy (1982), adds one to the lower bound once $n\ge2^{21}$. The section continues with Factorisatio numerorum (Canfield--Erdős--Pomerance), few multiples of primes in an interval (Erdős--Selfridge), and further one-off questions (pp. 151--154).

• References (pp. 154--163; p. 163 on the page image, the rest in the text layer), unnumbered, by author and year. The entries the passages above name: P. Erdős, Problems and results in additive number theory, Colloque sur la Théorie des Nombres, Bruxelles, 1955, pp. 127--137 (1956b), filed as erdos_1956_problems_results_additive_number_theory; P. Erdős and J. Spencer, Probabilistic Methods in Combinatorics (1974); R. K. Guy, Sets of integers whose subsets have distinct sums, Theory and Practice of Combinatorics, North-Holland Math. Studies 60 (1982), 141--154; H. Halberstam and K. F. Roth, Sequences, Clarendon, 1966 (2nd ed., Springer, 1983); I. Z. Ruzsa, Essential components, Proc. London Math. Soc. 54 (1987), 38--56.

Compiled scope

The survey is compiled at statement depth for the two passages the citing problems consume: the essential-component definition and the $2^m3^n$ question (pp. 146--147), paged on question_p147, and the § 16 bounds on $g(n)$ (p. 151), recorded above. Both were read on the page images. The rest of the survey is mapped from its text layer; the survey gives no full proofs, and nothing here is independently reviewed.

Bears on. #1146: the survey is the problem's only cited source. The definition on p. 146 (PDF p. 32) is the problem's, with $\sigma$ the Schnirelmann density of § 10 (p. 139) and the asymptotic-density variant allowed in parentheses, and the question on p. 147 (PDF p. 33) is the problem's question in the survey's words: "The simplest set with a chance to be an essential component is the collection of numbers in the form $2^m3^n$, and Erdős often asked whether it is an essential component or not; I do not even have a plausible guess." The survey attributes the question to Erdős's repeated asking and gives no written source for it. It records no result on the set itself; the two results it states nearby, that every basis is an essential component (p. 146) and that essential components exist with $V(x)=O((\log x)^{1+\varepsilon})$ but not with $V(x)=O((\log x)^{1+o(1)})$ (p. 147, citing Ruzsa, 1987), leave the question open, and the page's status is unchanged. #1: § 16 (p. 151, PDF p. 37) states the distinct-subset-sums problem as the "$300 problem" of Erdős and Spencer's last chapter and records the bounds $1+[\log_2n]\le g(n)\le\log_2n+\log_2\log_2n+o(1)$ for the maximal number $g(n)$ of integers in $[1,n]$ with distinct subset sums, the Erdős--Moser halving of the $\log_2\log_2n$ term (Erdős, 1956b) and the Conway--Guy improvement of the lower bound by one for $n\ge2^{21}$ (Guy, 1982). In the problem's letters, $g(n)$ is the largest $|A|$ for $A\subseteq\{1,\ldots,N\}$ with $N=n$, and the conjecture $N\gg2^{|A|}$ reads $g(n)\le\log_2n+O(1)$; the survey does not state the conjecture itself, the prize, or any result beyond these bounds, and it bears on neither the 2026 disproof nor the page's status.

Results.

• Question (p. 147): is the set of numbers of the form $2^m3^n$ an essential component? With the definition of an essential component (p. 146).

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