Erdos 1975 problems results combinatorial number theory

../

---

P. Erdős: Problems and results in combinatorial number theory, Journées Arithmétiques de Bordeaux (Conf., Univ. Bordeaux, Bordeaux, 1974), Astérisque, Nos. 24--25 , pp. 295--310, Soc. Math. France, Paris, 1975 MR 51 #10275; Zentralblatt 305.10050.

This survey collects problems and results in four chapters, mostly around van der Waerden's theorem. Chapter I reviews r_k(n) bounds (Salem-Spencer, Behrend, Roth, Szemeredi) and states Szemeredi's regularity lemma together with Szemeredi's new theorem f_3(n;6,3) = o(n^2), Ruzsa's lower bound f_3(n;6,3) > cn r_3(n), and the general conjecture f_3(n;k,k-3) = o(n^2) with c_1 n r_{k-3}(n) < f_3(n;k,k-3) < c_2 n r_{k-3}(n) for every k >= 6, of which Ruzsa proved only the lower bound, for k = 6, 7 and 8. Chapter II offers a prize (printed p. 301) for a proof or disproof of the conjecture that every sequence with divergent sum of reciprocals contains arbitrarily long arithmetic progressions, and records that if no a_i is a distinct sum of other a's then sum 1/a_i < 103 (reportedly improved to 5, false with 2), plus the divisibility problem where a_j + a_k is never 0 mod a_i, for which Erdos and Sarkozy prove A(X) = o(X) and conjecture that sum 1/a_i < infinity and that A(X) < X^{1-e} infinitely often, with the finite conjecture n <= [X/3]+1 unresolved (best possible, if true, by the n+1 integers 2n, ..., 3n). Chapter III covers Hindman's theorem (with Baumgartner's simple proof and the note that the chapter's results "are not yet published") and asks whether every sequence of positive upper density admits an integer t and an infinite subsequence with all sums a_i + a_j + t again in the sequence, and whether the reals can be 2-colored with no set of power aleph_1 all of whose pairwise sums lie in one class, adding that Erdős could prove a negative statement under the continuum hypothesis by the methods of his paper with Hajnal and Rado. Chapter IV notes Spencer's proof (added in proof) that for all k, r there is a sequence without a (k+1)-term progression such that any r-coloring gives a monochromatic k-term progression, alongside the Erdős--Hajnal graph analog, printed there as a question about coloring a graph's vertices, which Erdős reports as settled by Folkman for two colors and by Nešetřil and Rödl in general. These passages are the sources of problems 1178 (the f_3(n;k,k-3) = o(n^2) conjecture, the r = 3 case of d_r(e) = (r-2)e+3), 876 (the sum-free reciprocal-sum result), 12 and 13 (the a_j + a_k = 0 mod a_i divisibility problem and its finite form n <= [X/3]+1), 131 and 186 (item (vi): no a divides the sum of the other a's, and non-averaging sets), 350 (the February 1973 distinct-subset-sums conjecture), 656 (the positive-upper-density sumset question), 965 (the uncountable monochromatic-sumset question), 966 (Spencer's sequence), 924 (the graph analog) and 532 (Hindman's theorem). The scan is OCR'd and several displayed formulas are garbled, so numerical constants above are read from the surrounding prose.

The copy read for this card is a 16-page OCR scan (printed p. $n$ is PDF p. $n-294$) whose text layer garbles the displayed formulas. Read status: claims checked for the Chapter III passages on printed p. 305 (Hindman's theorem with Baumgartner's proof; the $\aleph_1$ question with Erdős's continuum-hypothesis sentence) and the Chapter IV passages on printed p. 306 (item (i) with its added-in-proof note; the graph question), read clause by clause on the page images (PDF pp. 11--12, at 130 and 300 dpi) on 2026-09-18; the passages are prose and read cleanly. Also claims checked, on the page images on 2026-09-18: the Chapter II divisibility passage on printed pp. 302--303 (PDF pp. 8--9) and item (vi) on printed p. 309 (PDF p. 15), recorded below. Also claims checked, on the page image (130 dpi, and 300 dpi for the digits) on 2026-09-18: the two Chapter II passages on printed p. 302 (PDF p. 8) recorded below for #876 and #350, the sum-free reciprocal-sum paragraph and the February 1973 conjecture on distinct subset sums; the printed constant is 103 (twice), as the digest above says, where Erdős's 1977 restatement (Number theory day, p. 52) prints 100. The rest of the digest records an earlier reading that was not repeated. No notice is printed in the file; the Numdam record of the article shows its bibliographic data and no copyright, license or conditions-of-use statement (http://www.numdam.org/item/AST_1975__24-25__295_0/, read 2026-10-02), and Numdam's conditions page, which speaks for every item the site hosts, states "Une partie importante des fonds numérisés est dans le domaine public et l'autre reste la propriété des auteurs et de la revue" and "Il est interdit de modifier les fichiers des textes intégraux" (https://www.numdam.org/conditions, read 2026-10-02), every other right reserved.

Source: https://users.renyi.hu/~p_erdos/1975-30.pdf.

Bears on. #965: printed p. 305 (PDF p. 11), page image: the problem, which Erdős says he had stated in an earlier paper: "Split the real numbers into two classes. Does there exist a set $\{a_\alpha\}$ $1\le\alpha<\omega_1$ of power $\aleph_1$ so that all the sums $a_{\alpha_1}+a_{\alpha_2}$, $1\le\alpha_1<\alpha_2<\omega_1$ belong to the same class ?" He recalls that he had been unable to settle it even under the continuum hypothesis, and reports that the methods of his paper with Hajnal and Rado give him, under the continuum hypothesis, the following statement, printed as one sentence: "the set of reals can be split into two disjoint classes $S_1$ and $S_2$ so that if $A,B$ with $|A|=\aleph_1$, $|B|=\aleph_0$ are any two sets of reals there always are real numbers $X_1\in S_1$, $Y_1,Y_2\in S_2$, $X_2\in S_2$ so $X_1+Y_1\in S_1$, $X_2+Y_2\in S_2$." (as printed; the conclusion names the classes $S_1$, $S_2$ and not the sets $A$, $B$); the site's key for the problem. The chapter's reference list (p. 306) names Erdős, Problems and results in combinatorial analysis, Proc. Symp. Pure Math. XIX (1971), 77--89, and Erdős, Hajnal and Rado, Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93--196. #966: printed p. 306 (PDF p. 12), page image, Chapter IV item (i): "Is it true that for every $k$ and $r$ there is a sequence without the property $A(k+1)$, but is such that if we split it into $r$ subsequences at least one of them has the property $A(k)$ ? (added in proof : Spencer has recently shown that such a sequence exists)."; the site's key for the problem. #924: printed p. 306 (PDF p. 12), page image, the sentences after item (i): Erdős traces item (i) to an older conjecture of his and Hajnal's: "Is it true that for every $\ell$ and $r$ there is a graph not containing a $K(\ell+1)$ (i. e. a complete graph of $\ell+1$ vertices) but if one colours its vertices by $r$ colours, then at least one colour contains a $K(\ell)$ ?" He reports that Folkman proved such a graph exists for $r=2$ and every $\ell$ (adding that Folkman probably had a proof for $r\le4$) and that Nešetřil and Rödl had recently settled the general case in a paper not yet published. ("vertices" as printed; the 1969 statement of the problem and the site's concern edge colorings); a site key for the problem. #532: printed p. 305 (PDF p. 11), page image, the top of the page: Erdős reports Hindman's recent proof of the Graham--Rothschild conjecture, that for any two-coloring of the integers there is an infinite sequence $a_1<a_2<\dots$ all of whose finite sums $\sum_i\varepsilon_ia_i$, $\varepsilon_i\in\{0,1\}$, lie in one class, and Baumgartner's simple proof of Hindman's theorem; he adds that the chapter's results "are not yet published"; a site key for the problem. #12: printed p. 302 (PDF p. 8), page image, the last paragraph of Chapter II: for an infinite sequence of integers $a_1<a_2<\dots$ with $a_j+a_k\not\equiv0\pmod{a_i}$ whenever $i<j<k$, and $A(X)=\sum_{a_i<X}1$, Erdős records that he and Sárközy proved $A(X)=o(X)$ and that they conjecture $\sum a_i^{-1}<\infty$ and $A(X)<X^{1-\varepsilon}$ for infinitely many $X$; he then turns to a finite problem that, he says, "causes unexpected difficulties"; a site key for the problem. The reciprocal-sum convergence and the $X^{1-\varepsilon}$ bound are conjectures on the page, not results. #13: printed p. 303 (PDF p. 9), page image, the finite problem that closes Chapter II, a conjecture: "Let $a_1<\dots<a_n<X$ and assume that for $i<j<r$ $a_j+a_r\not\equiv0\pmod{a_i}$, then $n\le[\frac X3]+1$." ("$a_n<X$" as printed). Erdős notes that the $n+1$ integers $2n,2n+1,\dots,3n$ would make the bound sharp if the conjecture holds, and that a proof had so far eluded them. If the condition is imposed for all distinct indices, without the order $k<r<s$, he observes that the $a$'s contain no three-term arithmetic progression, so $n=o(X)$ follows from $r_3(X)=o(X)$; and he reports Szemerédi's proof of $n\le[\frac X3]+1$ when $(a_r+a_s)/a_k$ is never an integer other than $2$; a site key for the problem. #131: item (vi), printed p. 309 (PDF p. 15), page image: a question Erdős says he asked several years earlier: "Let $a_1<\dots<a_n\le X$ be a sequence of integers. Assume that no $a$ divides the sum of the other $a$'s. Put $\max n=F(X)$." He had expected $F(X)$ to stay below a power of $\log X$, but Straus proved display (1), $F(X)>\exp((1+o(1))\sqrt{2\log X/\log2})$. Straus also observed, Erdős says, that the problem is "essentially equivalent" to one he finds much more interesting: "Let $1\le a_1<\dots<a_m\le X$ be a sequence of integers such that no $a$ is the arithmetic mean of any other $a$'s. Put $\max m=f(X)$. Determine or estimate $f(X)$." Straus proved that (1) holds for $f(X)$ too; Erdős and Straus proved $f(X)<cX^{3/4}$; Szemerédi had somewhat improved the exponent $3/4$; and Erdős thinks $f(X)=o(X^\varepsilon)$ probable but far out of reach; the site's key [Er75b, p. 309] for the problem. #656: printed p. 305 (PDF p. 11), page image, the question after Hindman's theorem, which Erdős says "perhaps" holds: every sequence of positive upper density has an integer $t$ and an infinite subsequence $a_{i_1}<a_{i_2}<\dots$ all of whose sums $a_{i_r}+a_{i_s}+t$ are again terms; a question on the page, not a result; a site key for the problem. #1178: printed pp. 299--300 (PDF pp. 5--6), page images, Chapter I: with $f_r(n;k,l)$ the least number of $r$-tuples on $n$ vertices that forces $k$ vertices spanning $l$ of them, the conjecture (7) of Sós, Brown and Erdős that $f_3(n;6,3)=o(n^2)$, which Szemerédi had just proved with his lemma; Ruzsa's $f_3(n;6,3)>cn\,r_3(n)$; the expectation that $f_3(n;k,k-3)=o(n^2)$ for every $k$; and the guess (8), $c_1n\,r_{k-3}(n)<f_3(n;k,k-3)<c_2n\,r_{k-3}(n)$ for every $k\ge6$, whose lower bound Ruzsa had proved for $k=6,7,8$. This is the $r=3$ case of the problem; a site key for the problem. #876: printed p. 302 (PDF p. 8), page image, the paragraph before the divisibility problem: for an infinite sequence of integers $a_1<\ldots$ in which no $a$ is a sum of distinct other $a$'s, Erdős writes "I proved that $\sum_ia_i^{-1}<103$", citing his Hungarian paper in Mat. Lapok 13 (1962), 28--38, with an English version to appear in his joint paper with Benkoski in Math. of Computation. He adds that he heard at the April 1974 meeting of the American Mathematical Society that $5$ can stand in place of $103$ but $2$ cannot, that he does not remember who proved this, and that the maximum of $\sum_ia_i^{-1}$ was suggested to be not much above $2$; the site's key [Er75b] for the problem's reciprocal-sum question, where the site's figures ($<100$, Sullivan's $<4$) are those of the 1977 restatement. #350: printed p. 302 (PDF p. 8), page image, the sentences that follow: the conjecture Erdős dates to February 1973, "if $a_1<a_2<\ldots<a_n$ is such that all the sums $\sum_{i=1}^n\varepsilon_ia_i$, $\varepsilon_i=0$ or $1$ are all distinct, then: $\max\sum_{i=1}^na_i^{-1}=2-2^{1-n}$ and the maximum is attained if and only if $a_i=2^{i-1}$", with Ryavec's simple analytic proof and the recent elementary proof of E. and G. Szekeres reported; the site's key [Er75b] for the problem, whose displayed bound $\sum1/n<2$ is the weaker form and whose commentary's refinement $2-2^{1-|A|}$ with the extremal set $\{1,2,\ldots,2^k\}$ is this conjecture with $a_i=2^{i-1}$. #186: item (vi), printed p. 309 (PDF p. 15), page image, the passage recorded above for #131: Straus's observation that the non-dividing problem is "essentially equivalent" to the non-averaging one, the definition of $f(X)$ ("no $a$ is the arithmetic mean of any other $a$'s"), Straus's lower bound (1) for $f(X)$, "Straus and I proved $f(X)<c^{3/4}$" (as printed, the $X$ dropped; the next sentence's "exponent $3/4$" shows $cX^{3/4}$ is meant), Szemerédi's improvement of the exponent and the expectation $f(X)=o(X^\varepsilon)$; the site's key [Er75b, p. 309] for the problem. The exponent $3/4$ printed here differs from the $2/3$ Erdős gives the same Erdős--Straus bound in his 1973, 1977 and 1980 accounts.

Results to transcribe.

• Szemeredi regularity lemma and (7): Statement of the regularity lemma, and Szemeredi's proof that f_3(n;6,3) = o(n^2), where f_3(n;6,3) is the least number of triples on n vertices forcing 6 vertices spanning 3 triples; Ruzsa disproved f_3(n;6,3) < n^{2-c} by showing f_3(n;6,3) > cn r_3(n).
• Conjecture (8): Conjecturally f_3(n;k,k-3) = o(n^2) for every k, with c_1 n r_{k-3}(n) < f_3(n;k,k-3) < c_2 n r_{k-3}(n) perhaps for every k >= 6 (printed p. 300); Ruzsa proved the lower bound for k = 6, 7, 8.
• Prize conjecture (printed p. 301, PDF p. 7, page image): Every increasing sequence with sum of reciprocals divergent contains arbitrarily long arithmetic progressions; a prize offered for a proof or disproof.
• Sum-free reciprocal bound (printed p. 302, PDF p. 8, page image): If no a_i is a distinct sum of other terms then sum 1/a_i < 103; reportedly improvable to 5 but not to 2, and the true maximum is thought to be near 2.
• Distinct subset sums (printed p. 302, PDF p. 8, page image): the February 1973 conjecture that if all sums sum epsilon_i a_i are distinct then max sum 1/a_i = 2 - 2^{1-n}, attained if and only if a_i = 2^{i-1}, with Ryavec's analytic proof and E. and G. Szekeres's elementary proof reported.
• Divisibility problem (pp. 302--303): If a_j + a_k is never 0 mod a_i for i<j<k, then Erdos and Sarkozy prove the counting function A(X) = o(X) and conjecture that sum 1/a_i < infinity and that A(X) < X^{1-e} for infinitely many X; the finite conjecture n <= [X/3]+1 is unproved (best possible, if true, by the n+1 integers 2n, ..., 3n), and Szemeredi proved it when (a_r+a_s)/a_k is never an integer other than 2.
• Chapters III-IV questions (printed pp. 305--306, PDF pp. 11--12): Open: an integer t and infinite subsequence of a positive-upper-density set with all a_i + a_j + t in the set; a 2-coloring of the reals with no aleph_1-sized set having monochromatic pairwise sums (p. 305, with Erdős's continuum-hypothesis sentence quoted above); Spencer's proof of the progression-coloring sequence is announced in proof (p. 306), followed by the graph question with Folkman's and Nešetřil--Rödl's resolutions as reported there.

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