The short answer if you don’t feel like reading a post with some actual mathematics in it is that I don’t know.
Now for the longer answer. A subset of is called a Sidon set if the only solutions of the equation with are the trivial ones with and or and . Since the number of pairs with is and whenever , it is trivial that if is a Sidon set, then , which gives an upper bound for of around .
There is also a matching lower bound, up to a constant. I think it is due to ErdŎs. One notes first that the subset of defined by is a Sidon set inside . Indeed, if , then and . Assuming the quadruple is not degenerate, , so we can divide the first equation by the second to deduce that , and that implies that and , so the quadruple is degenerate for a different reason.
Thus, we can find a Sidon subset of of size , which is the square root of the size of . We can now regard this set as a subset of , and then map each point to the number . It is easy to check that the resulting set is a Sidon subset of .
Much more is known about this: the correct bound is now known up to a constant. However, that is not the theme of this post. What I want to discuss is whether any kind of converse of this result is true. That is, can one say that a Sidon set of size close to must be constructed in some kind of quadratic way?
Some very weak evidence in favour of a conclusion like that is that random methods fail miserably to produce Sidon sets of anything like size . Indeed, let’s pick a subset of randomly by choosing each element with probability . The total number of quadruples with taken from is roughly (since apart from a few edge effects and can be chosen more or less freely and they determine ), and each nondegenerate one has a probability . So the expected number of nondegenerate quadruples with is roughly . For this to be smaller than (so we can remove a point from each one and still have plenty of left), we need to be significantly smaller than , which gives a bound of , which gives us .
There are several other ways to see that random sets of size are very different indeed from Sidon sets, which suggests that Sidon sets of size close to must have interesting structure. But what is that structure?
It isn’t easy even to state a conjecture here, since before we map the subset of to the integers, we can apply an invertible linear transformation to it. It is hard to think of a way of characterizing the kinds of sets that can arise like this, let alone thinking about how to make the structure looser when the set has size only . (Additive combinatorialists will immediately recognise that I am inspired by Freiman’s theorem here.)
But today … make that yesterday as a night has passed since I wrote those two words … I was at a talk given by Javier Cilleruelo, thanks to which I learnt of an example that places a much more serious constraint on any conjecture one might hope to make. The example is one I sort of knew already, since it is based on a brilliant argument of Imre Ruzsa, who created an infinite Sidon set such that the asymptotic size of is around . (As with the finite case, is very easy; the true answer is conjectured to be ; Ruzsa was the first person to beat and his exponent has not been improved.) What Cilleruelo mentioned in passing was that you can use some of Ruzsa’s ideas in an easy way to get a pretty decent example in the finite case. This is something I hadn’t realized. I presume Ruzsa himself was well aware of it, but I don’t remember it being mentioned in his paper (though I haven’t looked at the paper for many years, so he might have done). What I find particularly interesting is that the example is completely different from the graph-of- type examples.
Since the construction is simple (to understand, that is) and rather gorgeous, I thought it merited a blog post. And maybe it can also serve as an advertisement for Ruzsa’s amazing paper.
It begins with the observation that the logarithms of the primes form a Sidon set of reals: if are primes with , then either and or and ; therefore, the same is true if .
“So what?” it is tempting to say. After all, the logs of the primes are not integers. Indeed, there are far more of them than there are integers.
However, at this point a principle comes in that I often feel doesn’t deserve to be as incredibly fundamentally useful as it in fact is: that two distinct integers must differ by at least 1. It’s not too much of an exaggeration to say, for example, that to prove that a concrete number is irrational or transcendental you have to find some way of reducing the problem to this principle. (That is, you say that if your number is rational/algebraic then there must be two distinct integers that have difference less than 1.) For this problem we make a much simpler use of the principle. If , then , since are integers. Since the derivative of is , that tells us that and differ by at least . (One could be a bit more careful here: I think Cilleruelo stated a bound of .)
Note what we now have that’s better: instead of merely knowing that in nondegenerate cases, we have a lower bound on the difference. This allows us to approximate and discretize.
So let’s start with all the logs of the primes up to , of which there are about by the prime number theorem. If we multiply those by say , then all the differences between the distinct sums, which were previously at least , are now at least . Therefore, if we move each number to the nearest integer, the differences will be altered by at most 2, so will be at least 1. So we have a Sidon set! It is a subset of the integers up to and it has size around , so this construction gives a Sidon subset of of size around .
The moral of this is that to prove a structural result about Sidon sets of density close to , then one would probably have to insist on close meaning “within a constant of” (which one would then relax to some slow-growing function later). Or alternatively, one would look for a much more general notion of structure, but I don’t see an obvious generalization of the two examples I now know. Another moral is that it’s worth looking for more examples of dense Sidon sets before even trying to make a conjecture.