← All problems

Erdős Problem #121 — Avoiding an odd number of factors with square product

32 years old · traced to

For positive integers NN and kk, let Fk(N)F_k(N) be the maximum cardinality of a set A⊆{1,…,N}A\subseteq\{1,\ldots,N\} such that no kk distinct elements of AA have a product that is a square. Thus the forbidden product uses distinct elements, and “square” means a perfect square of an integer. For each fixed odd integer k≥5k\geq 5, the question is whether

Fk(N)=(1−o(1))N(N→∞),F_k(N)=(1-o(1))N\qquad (N\to\infty),

equivalently, whether Fk(N)/N→1F_k(N)/N\to1. The case k=5k=5 is included; the general question asks this for every fixed odd k≥5k\geq5. Tao (2025)

Background

Erdős, Sárközy, and Sós initiated the systematic study of these extremal quantities and conjectured that the near-full-density behavior for odd kk continues beyond k=3k=3. They proved F2(N)=(6/π2+o(1))NF_2(N)=(6/\pi^2+o(1))N and F3(N)=(1−o(1))NF_3(N)=(1-o(1))N, and obtained asymptotics for even k≥4k\geq4. Earlier, Erdős had shown F4(N)=o(N)F_4(N)=o(N), using the fact that any subset of {1,…,N}\{1,\ldots,N\} of size much larger than NN contains a nontrivial solution of ab=cdab=cd. Erdős Problems #121 Tao (2025)

A related problem asks for the largest set containing no odd number of distinct elements whose product is a square. Its extremal function has an asymptotic density strictly below 11, established by Granville and Soundararajan; this is a different condition from forbidding one specified odd number kk of factors. In particular, a result for that broader prohibition does not by itself give an upper bound on Fk(N)F_k(N): a set avoiding every odd number of factors also avoids kk factors, so its maximum size is at most Fk(N)F_k(N). Erdős Problems #121 Tao (2025)

References

T. Tao, On product representations of squares, arXiv:2405.11610 (2024).

Source: T. Tao, On product representations of squares, arXiv:2405.11610 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.