Erdős Problem #425 — Product-Sidon subsets of an interval
For an integer , write and let be the number of primes at most . Define to be the largest cardinality of a set for which distinct two-element subsets have distinct products; equivalently, the map
is injective. The first question is whether there is a constant such that, as ,
Here the set bound is written using throughout, resolving the in the first set notation of the original wording. Bloom, Erdős Problem #425 Erdős, On Some Applications of Graph Theory to Number Theoretic Problems
The second question concerns a fixed integer . Is it true that, for every such fixed , there is a constant such that for all sufficiently large , every whose products on distinct -element subsets are distinct satisfies
The constant is allowed to depend on ; the asymptotic parameter is . Bloom, Erdős Problem #425 Erdős, On Some Applications of Graph Theory to Number Theoretic Problems
Background
This is a multiplicative counterpart of Sidon-type questions: the defining restriction forbids repeated products from distinct pairs, rather than repeated sums. The primes give a natural baseline, since unique factorization makes the products of distinct prime pairs different, yielding a set of size . The problem asks how much larger a product-distinct set can be. Erdős’s work places the question among problems where number-theoretic factorization and graph-theoretic restrictions can be used together. Bloom, Erdős Problem #425 Erdős, On Some Applications of Graph Theory to Number Theoretic Problems
In the 1968 work reprinted in 1969, Erdős describes the pair-product upper bound as a refinement of an earlier number-theoretic and graph-theoretic argument. One ingredient is an extremal estimate for graphs without a rectangle, that is, without a cycle of length four. This graph condition is a useful structural connection: multiplicative product coincidences can be studied through constraints on the graph encoding the relevant factorizations. Erdős, On Some Applications of Graph Theory to Number Theoretic Problems
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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.