Problem 1143

Let $p_1<\cdots<p_u$ be primes and let $k\geq 1$ . Let $F_k(p_1,\ldots,p_u)$ be such that every interval of $k$ positive integers contains at least $F_k(p_1,\ldots,p_u)$ multiples of at least one of the $p_i$ .

Estimate $F_k(p_1,\ldots,p_u)$ , particularly in the range $k=\alpha p_u$ for constant $\alpha>2$ .

Source: erdosproblems.com/1143

Number theory
Primes

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem OPEN and notes that no finite computation can resolve it; its commentary reports from [Va99] that Erdős and Selfridge found the exact bound for $2<\alpha<3$ and that very little is known for $\alpha>3$ , and gives no reference for the first. The reference is Theorem 1 of Section 6 of [Er78], recorded as the partial claim Erdős and Selfridge 1978; nothing is claimed for $\alpha\ge3$ .

Va99: Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999); the site cites item 1.8.
Er78: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, 1978), Congressus Numerantium XXI, Utilitas Math., Winnipeg (1978), 29--40; Section 6, Theorem 1, pp. 35--37. Not cited by the site. Rényi archive copy: https://users.renyi.hu/~p_erdos/1978-36.pdf. Library home: Erdős 1978.
Er86c: Erdős, P., Some problems on number theory. Analytic and elementary number theory (Marseille, 1983), Publ. Math. Orsay 86-1 (1986), 53--67; pp. 60--62 restate the theorem of [Er78] with its proof, and p. 62 adds a weaker bound for intervals of length at least $3p_u$ . Not cited by the site on this problem. Rényi archive copy: https://users.renyi.hu/~p_erdos/1986-15.pdf. Library home: Erdős 1986.
Ru95: Ruzsa, I. Z., Few multiples of many primes. Studia Sci. Math. Hungar. 30 (1995), 123--125. Not cited by the site. Library home: Ruzsa 1995.
GrRu17: Green, B. and Ruzsa, I. Z., On the arithmetic Kakeya conjecture of Katz and Tao. arXiv:1712.02108 (2017); Proposition 4.1. Not cited by the site. Library home: Green and Ruzsa 2017.

Problem 1143

Status

Proof claims

Discussion