Happy new year to everyone who is still following this blog! For this new post (coming after a nontrivial break), I thought I should perhaps try something different, and so I decided that it might be a good idea to discuss an open problem which I like, and which has been on the back of my mind lately.
Long story short, it’s a problem that Oleksiy Klurman and I came up with together a few years ago, and which we excitedly shared with some of our friends at various workshops and conferences, but we never really got a chance to write it down anywhere (mostly because we couldn’t prove anything particularly interesting about it..). In the meantime, one of us started a blog, so we thought the other day that we might finally have an opportunity to say some things about this problem in a sufficiently formal way and perhaps voice some of our frustrations.
To put this into context, let me start by introducing some notation and discussing some classical results about Sidon sets. For a set of real numbers , let denote the size of the largest subset of with the property that there are no nontrivial solutions to the equation , where are pairwise distinct from each other. Such a set is called an additive Sidon subset of , so thus denotes the size of the largest additive Sidon subset of . One of the most classical problems in additive combinatorics is to determine for sufficiently large positive integers . For brevity, we will denote this function in this case by .
Let’s discuss a few things about this . First, since all the pairwise sums live in the interval , it is easy to see that , which implies that . In 1941, Erdos and Turan refined this simple observation and proved that . This was further sharpened by Lindstrom, who established the inequality
which is the best known upper bound for . In order to produce a good lower bound for , one needs to construct a large subset of with all of its two element subset sums distinct. In their paper already cited above, Erdos and Turan proceeded as follows. Fix a prime , and let be the unique integer in congruent to modulo . It is not hard to check that is a Sidon set contained in the interval . In particular, for and sufficiently large this construction already leads to the fact that
holds for all sufficiently large. This is essentially a Freiman isomorphism from the parabola in . Three different constructions due to Singer, Bose, and Ruzsa, all with a similar algebraic flavor, lead to a slightly better lower bound for than the one above, which is of the form
While all of these results are quite classical, determining whether the correct size of is closer to the upper bound or to the lower bound (i.e. if the lower order term in Lindstrom’s upper bound is required) and what all these extremal Sidon sets might look like are still major open problems. We refer the interested reader to this consult this nice survey of O’Bryant and this beautiful blog post of Gowers for more information.
Similarly, one can play the same game with multiplication. For a set of real numbers , let us now define to be the size of the largest subset of with the property that there are no nontrivial solutions to the equation , where are pairwise distinct from each other. Naturally, we will call a multiplicative Sidon subset of , so like before simply stands for the size of the largest multiplicative Sidon subset of .
When , the story of turns out to be a bit more pleasant than the story of . At first glance, this is perhaps not too surprising. First of all, it is easy to see that is much larger than . For example, one can consider to be the set of prime numbers inside the interval . This is a multiplicative Sidon set and, by the Prime number theorem, ; therefore, we know that , which is somewhat promising. Indeed, in 1938 (three years before his additive Sidon paper with Turan), Erdos had in fact already started the study this quantity and managed to further improve upon this simple construction by showing that
for some absolute constant , where stands as usual for the number of primes in . Moreover, in the same paper he also proved that , upper bound which 31 years later he himself refined to , thus establishing the correct order of magnitude of the lower order term, namely
So, to (abruptly) summarize: while for we are still fairly troubled regarding the correct order of magnitude and the nature of the largest additive Sidon subsets in , for the multiplicative Sidon story we know quite well what is, and we also know that these extremal sets are intimately connected with the primes.
But what do we know about and for other sets of reals ? When is multiplicatively structured, say , we have that and , so the roles are in some sense reversed. Needless to say, this situation resembles quite well the dichotomy that motivated the celebrated sum-product conjecture of Erdos and Szemeredi, which roughly states that no set has a polynomial saving for both the size of the sum set and the size of the product set, over the trivial quadratic upper bound. So perhaps, one can formulate an analogous conjecture.. (and, of course, that’s what we did!).
Conjecture. (KP) For every set of reals , is there an absolute constant such that
for every ?
It is perhaps important to mention that we couldn’t find this anywhere in the literature, but that we did not look terribly hard for a reference (as I said, we more or less just asked around!). So, not only that we’d be (very) excited if someone can solve it, but we’d also be quite grateful if anyone knows a reference where something along these lines has been already asked.
In the remaining time/space, I’d like to draw attention towards a particularly tantalizing special case, which seems already quite tricky. Suppose is a set of reals with small doubling, namely , where may possibly depend on . We know that there are such sets with , so the question here is: can one prove that we always have for every ?
By using Solymosi’s theorem that every set satisfies , where stands for the number quadruples with and , , , pairwise distinct, it is not difficult to prove that every set with contains a multiplicative Sidon subset of size for every . Indeed, one can take a random subset of , obtained by choosing each element of to be part of with probability independently, and then removing one element from each multiplicative quadruple in . The end result is some smaller (random) set with no multiplicative quadruples, which on average will have size
for some absolute constant . Thus, there must exist a multiplicative Sidon subset of of at least that size. Using the fact that and optimizing for in terms of then proves the claim. And surprise, surprise, this is more or less the only nontrivial thing that we could say! We think that one can maybe hope to use ideas from the proof of Solymosi’s sum-product theorem more directly rather than the result itself as a blackbox in order to do better than , but we couldn’t find any such argument. Even when is small enough to allow the application of Freiman’s theorem, we didn’t know how to use the generalized arithmetic progression structure of to do any better (except perhaps in some situations where one adds some further assumptions on ). So, any ideas would be very welcome!
That being said, I’d also like to add that a friendlier direction which seems to be still worth investigating is the “dual” regime where , where is an absolute positive constant. By the multiplicative variant of Freiman’s theorem, must in this case lie in a multiplicative subgroup of of small rank (bounded only in terms of ), so by quantitative variants of Schmidt’s subspace theorem such as the one due to Amoroso and Viada it is also not too difficult to find “almost Sidon sets” of size . To be more precise, for every , there exists some positive integer and a subset of of size with the property that each sum of two distinct elements in has multiplicity at most . This also follows from a probabilistic deletion argument in the style of the one above, although it is a bit more technical. Nevertheless, it seems likely that finite subsets of multiplicative subgroups of of small rank might actually have linear size additive Sidon subsets for some “easier” reasons (e.g. the primordial subset , which is contained in a rank multiplicative subgroup, is Sidon itself due to the uniqueness of binary representations).
Later edit: In a comment, Oliver Roche-Newton already provided a simple construction which shows that the original conjecture cannot be true as stated for any : there exists a set with no additive/multiplicative Sidon subsets of size greater than . This set however does not have small additive or multiplicative doubling, so the two particular cases described above could still be true. It also still remains to see whether there exists such that
for some absolute constant . This would already be quite interesting (and in the spirit of the sum-product theorem of Erdos and Szemeredi). That being said, it is perhaps also useful to add that
follows from a more general result of Komlos, Sulyok and Szemeredi which implies that holds for all sets of integers . It is not difficult to see that once we have this over the integers, also holds for all sets of reals (by using a diophantine approximation argument, for example). Since (ignoring small issues), this also implies .
Later edit 2: In the meantime, I’ve also become aware of improved constructions by Oliver Roche-Newton+Audie Warren and (independently) Ben Green+Sarah Peluse which show that the original conjecture cannot be true as stated for any : there exists a set with no additive/multiplicative Sidon subsets of size greater than . Moreover, these constructions also have small additive doubling, so they also show the (rather curious) fact that the exponent obtained via probabilistic deletion and Solymosi’s theorem which I sketched (for the size of the largest multiplicative Sidon subset in when ) is actually sharp. More updates to come. (I hope!)