Problem 56

Let $N\geq p_k$ where $p_k$ is the $k$ th prime. Suppose $A\subseteq \{1,\ldots,N\}$ is such that there are no $k+1$ elements of $A$ which are relatively prime. An example is the set of all multiples of the first $k$ primes. Is this the largest such set?

Source: erdosproblems.com/56

Number theory
Intersecting families

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN).

AhKh94: Ahlswede, Rudolf and Khachatrian, Levon H., On extremal sets without coprimes. Acta Arith. 66 (1994), 89-99.
AhKh95: Ahlswede, Rudolf and Khachatrian, Levon H., Maximal sets of numbers not containing $k+1$ pairwise coprime integers. Acta Arith. 72 (1995), 77-100.
Er92b: Erdős, Paul, Some of my favourite problems in various branches of combinatorics. Matematiche (Catania) (1992), 231-240.
Er95: Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186.
Gu04: Guy, Richard K., Unsolved problems in number theory. Third edition, Problem Books in Mathematics, Springer, New York (2004), xviii+437 pp.; doi:10.1007/978-0-387-26677-0. Section B26 "Densest set with no $l$ pairwise coprime", printed p. 125, where the book states the conjecture and the offer of a prize. Library home: Guy 2004.

Problem 56

Status

Proof claims

Discussion