Problem 535

Let $r\geq 3$ , and let $f_r(N)$ denote the size of the largest subset of $\{1,\ldots,N\}$ such that no subset of size $r$ has the same pairwise greatest common divisor between all elements. Estimate $f_r(N)$ .

Source: erdosproblems.com/535

Number theory

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label. The bounds in hand are Erdős's 1964 theorem, $N^{c_r/\log\log N}<f_r(N)<N^{3/4+\varepsilon}$ for every fixed $r\ge3$ and $\varepsilon>0$ (Erdős (1964)), the improvement of the upper exponent to $1/2+\varepsilon$ by Abbott and Hanson (Abbott and Hanson (1970); not held, attested by Erdős's 1973 survey and by the site), and the site's derivation of $f_r(N)\le N^{C_r\log\log\log N/\log\log N}$ , hence $f_r(N)\le N^{o(1)}$ , from the Alweiss–Lovett–Wu–Zhang sunflower bound inserted into Erdős's 1964 argument (the site's derivation, which the corpus has not checked). Erdős conjectured that the lower bound gives the right order. No source determining the order of $f_r(N)$ , and no proof claim, was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

Er64: Erdős, P., On a problem in elementary number theory and a combinatorial problem. Math. Comp. 18 (1964), no. 88, 644--646 (received 20 March 1964). The Theorem and display (4), p. 644; the proof and the construction, p. 645; displays (7) and (8) and the closing question, p. 646. Library home: Erdős 1964.
Er62: Erdős, P., Számelméleti megjegyzések IV. Extremális problémák a számelméletben, I. Mat. Lapok 13 (1962), 228--255; problem 14, printed pp. 236--238. The 1962 origin of the question, cited by [Er64] as its reference [1]; not a key of the site's page. Library home: Erdős 1962.
AbGa67: Abbott, H. L. and Gardner, B., An extremal problem in number theory. Canad. Math. Bull. 10 (1967), no. 2, 173--177 (received 17 November 1966). Displays (1)--(3), Theorem 1 and Theorem 2, pp. 173--174; proofs, pp. 174--176. Read at Cambridge Core. The site cites this paper on Problem 536 only. Library home: Abbott and Gardner 1967.
AbHa70: Abbott, H. L. and Hanson, D., An extremal problem in number theory. Bull. London Math. Soc. 2 (1970), no. 3, 324--326, DOI 10.1112/blms/2.3.324 (Crossref record of 2026-09-18). Not held; no open copy was found (see Search scope). The exponent $1/2$ is quoted second-hand from [Er73], p. 123, and from the site.
AbHa67: "No reference found" in the site's own reference data; the site's /bibs/AbHa67 endpoint returned HTTP 404 on 2026-09-18. A dangling key; see the Current assessment for what it may denote.
Ab66: Abbott, H. L., Some remarks on a combinatorial theorem of Erdős and Rado. Canad. Math. Bull. 9 (1966), no. 2, 155--160. Not held and not requested; cited by [AbGa67] for the lower bound (2) and by [Er73] for improved bounds on the sunflower function.
ALWZ20: Alweiss, R., Lovett, S., Wu, K. and Zhang, J., Improved bounds for the sunflower lemma. arXiv:1908.08483v3 (31 August 2021); Ann. of Math. (2) 194 (2021), no. 3, DOI 10.4007/annals.2021.194.3.5; an extended abstract appeared in the proceedings of STOC 2020, 624--630. Theorem 1.4, p. 2 of the preprint. Library home: Alweiss 2020.
BCW21: Bell, T., Chueluecha, S. and Warnke, L., Note on sunflowers. Discrete Math. 344 (2021), no. 7, 112367 (the published record as the reference list of [ALWZ20] gives it); preprint arXiv:2009.09327 (v2, 18 March 2021). Not held; its bound $(Cr\log w)^w$ is quoted from [ALWZ20], p. 12, and from the thread.
Er69: Erdős, P., Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, 1968), Springer, Berlin (1969), 77--82; display (11) on printed p. 81 (PDF p. 5 of the Rényi archive's file). Library home: Erdős 1969 (its Bears-on row for this problem names display (11)).
Er70: Erdős, P., Some extremal problems in combinatorial number theory. Mathematical Essays Dedicated to A. J. Macintyre, Ohio Univ. Press (1970), 123--133; display (1) on printed p. 124. Library home: Erdos 1970.
Er73: Erdős, P., Problems and results on combinatorial number theory. A Survey of Combinatorial Theory (Fort Collins 1971), North-Holland (1973), Chapter 12, 117--138; Section 4, printed pp. 123--124. Library home: Erdos 1973 (its Bears-on row for this problem names Section 4, pp. 123--124).
ErRa60: Erdős, P. and Rado, R., Intersection theorems for systems of sets. J. London Math. Soc. 35 (1960), 85--90. Not held; the sunflower bound $g(k,t)<k!(t-1)^{k+1}$ is quoted from [Er64], display (2).

Problem 535

Status

Proof claims

Discussion