Problem 121

Let $F_{k}(N)$ be the size of the largest $A\subseteq \{1,\ldots,N\}$ such that the product of no $k$ many distinct elements of $A$ is a square. Is $F_5(N)=(1-o(1))N$ ? More generally, is $F_{2k+1}(N)=(1-o(1))N$ ?

Source: erdosproblems.com/121

Number theory
Squares

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved on the site (label DISPROVED (LEAN); page last edited 17 October 2025). Tao's Theorem 1.2 (2024) gives, for every $k\geq 4$ , a constant $c_k>0$ with $F_k(N)\leq(1-c_k+o(1))N$ , so neither $F_5(N)$ nor $F_{2k+1}(N)$ for any $k\ge2$ is $(1-o(1))N$ ; the paper appeared in Acta Math. Hungar. 175 (2025), and Thomas Bloom, the site's curator, attributes the negative answer to it. The site's (LEAN) suffix is a catalog label; the outside Lean proof it refers to, which this corpus has not built, is linked from the claim page and described under Formalization. The claim page Tao 2024 records the acceptance.

ESS95: Erdős, P. and Sárközy, A. and Sós, V. T., On product representations of powers. I. European J. Combin. (1995), 567-588.
Er38: P. Erdős, On sequences of integers no one of which divides the product of two others and on related problems. Tomsk. Gos. Univ. Ucen Zap. (1938), 74-82.
GrSo01: Granville, Andrew and Soundararajan, K., The spectrum of multiplicative functions. Ann. of Math. (2) 153 (2001), no. 2, 407-470, DOI 10.2307/2661346.
Ha96: Hall, R. R., Proof of a conjecture of Heath-Brown concerning quadratic residues. Proc. Edinburgh Math. Soc. (2) (1996), 581-588.
Ru77: Ruzsa, I. Z., General multiplicative functions. Acta Arith. 32 (1977), 313-347.
Ta24: Tao, T., On product representations of squares. arXiv:2405.11610 (2024); Acta Math. Hungar. 175 (2025), no. 1, 142--157, DOI 10.1007/s10474-025-01505-7. Library home: Tao 2024.

Problem 121

Status

Proof claims

Discussion