I’ve just uploaded to the arXiv my paper “On product representations of squares“. This short paper answers (in the negative) a (somewhat obscure) question of Erdös. Namely, for any , let be the size of the largest subset of with the property that no distinct elements of multiply to a square. In a paper by Erdös, Sárközy, and Sós, the following asymptotics were shown for fixed :
Thus the asymptotics for for odd were not completely settled. Erdös asked if one had for odd . The main result of this paper is that this is not the case; that is to say, there exists such that any subset of of cardinality at least will contain distinct elements that multiply to a square, if is large enough. In fact, the argument works for all , although it is not new in the even case. I will also note that there are now quite sharp upper and lower bounds on for even , using methods from graph theory: see this recent paper of Pach and Vizer for the latest results in this direction. Thanks to the results of Granville and Soundararajan, we know that the constant cannot exceed the Hall-Montgomery constant
and I (very tentatively) conjecture that this is in fact the optimal value for this constant. This looks somewhat difficult, but a more feasible conjecture would be that the asymptotically approach the Hall-Montgomery constant as , since the aforementioned result of Granville and Soundararajan morally corresponds to the case.
In the end, the argument turned out to be relatively simple; no advanced results from additive combinatorics, graph theory, or analytic number theory were required. I found it convenient to proceed via the probabilistic method (although the more combinatorial technique of double counting would also suffice here). The main idea is to generate a tuple of distinct random natural numbers in which multiply to a square, and which are reasonably uniformly distributed throughout , in that each individual number is attained by one of the random variables with a probability of . If one can find such a distribution, then if the density of is sufficienly close to , it will happen with positive probability that each of the will lie in , giving the claim.
When , this strategy cannot work, as it contradicts the arguments of Erdös, Särközy, and Sós. The reason can be explained as follows. The most natural way to generate a triple of random natural numbers in which multiply to a square is to set
for some random natural numbers . But if one wants all these numbers to have magnitude , one sees on taking logarithms that one would need
which by elementary linear algebra forces
so in particular each of the would have a factor comparable to . However, it follows from known results on the “multiplication table problem” (how many distinct integers are there in the multiplication table?) that most numbers up to do not have a factor comparable to . (Quick proof: by the Hardy–Ramanujan law, a typical number of size or of size has factors, hence typically a number of size will not factor into two factors of size .) So the above strategy cannot work for .
However, the situation changes for larger . For instance, for , we can try the same strategy with the ansatz
Whereas before there were three (approximate) equations constraining three unknowns, now we would have four equations and six unknowns, and so we no longer have strong constraints on any of the . So in principle we now have a chance to find a suitable random choice of the . The most significant remaining obstacle is the Hardy–Ramanujan law: since the typically have prime factors, it is natural in this case to choose each to have prime factors. As it turns out, if one does this (basically by requiring each prime to divide with an independent probability of about , for some small , and then also adding in one large prime to bring the magnitude of the to be comparable to ), the calculations all work out, and one obtains the claimed result.
