← All problems

Erdős Problem #425 — Product-Sidon subsets of an interval

For an integer n≥1n\ge 1, write [n]={1,…,n}[n]=\{1,\ldots,n\} and let π(n)\pi(n) be the number of primes at most nn. Define F(n)F(n) to be the largest cardinality of a set A⊆[n]A\subseteq[n] for which distinct two-element subsets have distinct products; equivalently, the map

{a,b}⟼ab,{a,b}∈(A2),\{a,b\}\longmapsto ab,\qquad \{a,b\}\in\binom{A}{2},

is injective. The first question is whether there is a constant cc such that, as n→∞n\to\infty,

F(n)=π(n)+(c+o(1))n3/4(log⁡n)3/2.F(n)=\pi(n)+(c+o(1))\frac{n^{3/4}}{(\log n)^{3/2}}.

Here the set bound is written using nn throughout, resolving the NN 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 r≥2r\ge 2. Is it true that, for every such fixed rr, there is a constant CrC_r such that for all sufficiently large nn, every A⊆[n]A\subseteq[n] whose products on distinct rr-element subsets are distinct satisfies

∣A∣≤π(n)+Crn(r+1)/(2r)?|A|\le \pi(n)+C_r n^{(r+1)/(2r)}?

The constant is allowed to depend on rr; the asymptotic parameter is nn. 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 π(n)\pi(n). 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

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.