What are dense Sidon subsets of {1,2,…,n} like?

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 A of \{1,2,\dots,n\} is called a Sidon set if the only solutions of the equation a+b=c+d with a,b,c,d\in A are the trivial ones with a=c and b=d or a=d and b=c. Since the number of pairs a\leq b with a,b\in A is |A|(|A|+1)/2 and 2\leq a+b\leq 2n whenever a,b\in A, it is trivial that if A is a Sidon set, then |A|(|A|+1)/2\leq 2n, which gives an upper bound for |A| of around 2\sqrt{n}.

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 \Gamma of \mathbb{Z}_p^2 defined by \Gamma=\{(x,x^2):x\in\mathbb{Z}_p\} is a Sidon set inside \mathbb{Z}_p^2. Indeed, if (x,x^2)+(y,y^2)=(z,z^2)+(w,w^2), then x^2-z^2=w^2-y^2 and x-z=w-y. Assuming the quadruple is not degenerate, x\ne z, so we can divide the first equation by the second to deduce that x+z=w+y, and that implies that x=w and z=y, so the quadruple is degenerate for a different reason.

Thus, we can find a Sidon subset of \mathbb{Z}_p^2 of size p, which is the square root of the size of \mathbb{Z}_p^2. We can now regard this set as a subset of \{0,1,\dots,p-1\}^2, and then map each point (x,y) to the number 1+x+2py. It is easy to check that the resulting set is a Sidon subset of \{1,2,\dots,2p^2\}.

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 \sqrt{n} 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 \sqrt{n}. Indeed, let’s pick a subset A of \{1,2,\dots,n\} randomly by choosing each element with probability p. The total number of quadruples x+y=z+w with x,y,z,w taken from \{1,2,\dots,n\} is roughly n^3 (since apart from a few edge effects x,y and z can be chosen more or less freely and they determine w), and each nondegenerate one has a probability p^4. So the expected number of nondegenerate quadruples x+y=z+w with x,y,z,w\in A is roughly p^4n^3. For this to be smaller than |A|/2 (so we can remove a point from each one and still have plenty of A left), we need p^4n^3 to be significantly smaller than pn, which gives a bound of p=cn^{-2/3}, which gives us |A|=cn^{1/3}.

There are several other ways to see that random sets of size n^{1/2} are very different indeed from Sidon sets, which suggests that Sidon sets of size close to n^{1/2} 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 \mathbb{Z}_p^2 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 \sqrt{n}/1000. (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 S such that the asymptotic size of S\cap\{1,2,\dots,n\} is around n^{\sqrt{2}-1}. (As with the finite case, n^{1/3} is very easy; the true answer is conjectured to be n^{1/2-o(1)}; Ruzsa was the first person to beat n^{1/3+o(1)} 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-x^2 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 p,q,r,s are primes with pq=rs, then either p=r and q=s or p=s and q=r; therefore, the same is true if \log p+\log q=\log r+\log s.

“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 pq\ne rs, then |pq-rs|\geq 1, since p,q,r,s are integers. Since the derivative of \log x is 1/x, that tells us that \log(pq) and \log(rs) differ by at least 1/2pq. (One could be a bit more careful here: I think Cilleruelo stated a bound of 1/(pqrs)^{1/2}.)

Note what we now have that’s better: instead of merely knowing that \log p+\log q\ne\log r+\log s 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 m, of which there are about m/\log m by the prime number theorem. If we multiply those by say 6m^2, then all the differences between the distinct sums, which were previously at least 1/2m^2, are now at least 3. 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 m^2\log m and it has size around m/\log m, so this construction gives a Sidon subset of \{1,2,\dots,n\} of size around n^{1/2}/(\log n)^{3/2}.

The moral of this is that to prove a structural result about Sidon sets of density close to n^{1/2}, 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.

About these ads

25 Responses to “What are dense Sidon subsets of {1,2,…,n} like?”

  1. Gil Kalai Says:

    Tim, Do you believe that every sidon set with n^{1/3+t} t>0 already has structure? A second question: maybe easier than structure would be an upper bound on the number of sidon sets of the required size?

    • gowers Says:

      A recent result of David Conlon’s and mine gives at least something in this kind of direction. We show that if G is an Abelian group of order n and A is a random subset of G of size C(n\log n)^{1/3}, then with high probability every Freiman homomorphism from A to another Abelian group extends to a Freiman homomorphism on G. This is completely untrue for Sidon sets, since then every map is a Freiman homomorphism. However, the property that all Freiman homomorphisms extend is much stronger than the property of not being Sidon, so the bound you can get this way on the number of Sidon sets is almost certainly far too weak. I imagine that as with other problems of this kind the number of Sidon sets is roughly comparable to the number of subsets of a single maximal Sidon set — that is, 2^{cn^{1/2}}. I don’t even have a guess if you try to count Sidon sets of size n^t for 1/3<t<1/2 (but I haven’t thought about it, so maybe it’s easy to come up with a sensible conjecture).

    • Rob Says:

      Dear Tim and Gil,

      Another result in this direction was obtained recently by Kohayakawa, Lee, Rodl and Samotij (see Theorem 2.1):

      https://www.dpmms.cam.ac.uk/~ws299/papers/Sidon.pdf

      I think they also get some structural information about a ‘typical’ (in a weak sense) Sidon set of a given size, but it sounds like you’re hoping for something much stronger…

    • Klas Markström Says:

      I took a look at some old data on Sidon sets which I had on my laptop, I once had a long wait in an airport which led to some simple computer experiments with Sidon sets, and from those data it looks like c is 4.1… in the estimate for the number of Sidon sets.

      However this is data from what my laptop could do at the time so they are only for n up to 44, for general Sidon sets.

  2. Terence Tao Says:

    A characterisation of dense Sidon sets may also lead to progress on another intractable Erdos problem, namely to determine if there is an additive basis A of the natural numbers of order 2 (i.e. A+A=N) with bounded multiplicity function r_2 (i.e. every natural number is expressible as the sum of two elements of A in a bounded number of ways).

    Note though that if we relax the Sidon property to that of having multiplicity that grows at most logarithmically, then random examples start working again thanks to Chernoff. This already rules out a lot of analytical techniques (e.g. Fourier analysis), as they have a hard time distinguishing between multiplicity 1 and logarithmic multiplicity. I’m not sure what that leaves one with; algebraic methods such as the polynomial method are a remote possibility, but I haven’t seen them used for inverse sumset problems before, only for direct sumset inequalities.

  3. Mark Lewko Says:

    This is vaguely reminiscent of the some theorems and conjectures loosely attached to the name “inverse sieve.” One assertion of this form states roughly that if A \subset [N] such that A has size near \sqrt{N} and misses a constant fraction of the residue classes mod p for small p then A is contained in the image of a quadratic polynomial. Helfgott and Venkatesh have some results in this direction.  With this in mind, one might try to prove that a large Sidon set (or some appropriate subset and transformations thereof) must be ill-distributed mod p for small p. I have no intuition suggesting if this is plausible.

    • Klas Markström Says:

      One of my old programs looked for Sidon sets such that every initial segment is as balanced as possible mod p, no residue classes differing by more than 1.
      There are of course fewer such sets but their sizes seem to grow at a rate comparable with that of general Sidon sets, perhaps smaller by some p-dependent factor. The same looks plausible when one uses several prime at the same time.

      Here are two examples which are balanced mod 2, 3, and 5
      {1, 8, 15, 34, 42, 53, 65, 96, 109, 112, 113, 114}
      {1, 8, 15, 24, 47, 64, 66, 77, 85, 88, 113, 114}

    • Ben Green Says:

      Mark, this is an interesting idea, and I like this conjecture of Helfgott and Venkatesh very much. However I suspect that *very* dense Sidon sets, of size really close to the maximum of $\sqrt{N}$, are rather well-distributed in residue classes to small moduli.
      See

      http://arxiv.org/pdf/math/9808061.pdf

  4. gowers Says:

    Hmm, I’ve just realized something that has a big influence on any conjecture one might wish to make, even in the case of sets of size c\sqrt{n}. If you have a Sidon subset of \{1,2,\dots,n\} of that size, then you can create a Sidon subset of, say, \{1,2,\dots,5n\} by multiplying every element of your original set by 5 and arbitrarily adding 0, 1 or -1 to it. So there’s no hope of quadratic structure: the best one can hope for is a set that can be approximated by something quadratic. (Of course, then there are other things one can do like multiplying one of these perturbed examples by some appropriate a mod 5n, so things get even worse.)

    • Klas Markström Says:

      Looking at the data for n=44 the size distribution for all Sidon sets is unimodal, the most common size is 7 and the maximum is 9. Here is the list of {size, number of Sidon sets} pairs for n=44.
      {{0, 1}, {1, 44}, {2, 946}, {3, 13 244}, {4, 129 360}, {5, 845 408},
      {6, 3 157 104}, {7, 4 748 144}, {8, 1 462 854}, {9, 27 202}}

      For larger n I only had data for restricted Sidon set, the ones which are well distributed mod p, but they show a similar distribution.

      Again this is for very(!) small n, but it looks like as “close” to maximum size one might need to be close by something additive rather than a factor.

  5. Thomas Says:

    1) I think the size of the Sidon set constructed is around n^{1/2}/(\log n)^{3/2} in the penultimate paragraph.

    Thanks — corrected now.

    2) You can also construct quite nasty examples from iterating \exp, \log and the floor functions. For example, you can start from the primes p\leq m and instead of \lfloor \log p\rfloor I think one obtains a Sidon set of roughly the same density by considering \lfloor \exp(\lfloor \log p\rfloor)\rfloor. You could also take \lfloor \exp ( x)\rfloor where x is taken from a Sidon set of a completely different nature. I imagine one could repeat this process. It’s difficult to guess what kind of structure is preserved by repeated logarithms and floor functions…

    • Thomas Says:

      Actually, what I wrote in 2) isn’t properly correct as it stands, but I see a similar problem with the example in the post. Namely, how can one guarantee that the set actually has size at least $m/\log m$? For many different $p\leq m$ are such that the integer part of $\log p$ are the same. Surely one needs the primes to be spaced at least some multiplicative constant apart, whence one only gets a set of size around $\log m$?

  6. Neil Calkin Says:

    Erdos and Turan originally showed $n^{1/2} + O(n^{1/4})$ as an upper bound. Lindstrom gave a beautiful really short proof of an upper bound of $n^{1/2} + n^{1/4} +1$, which looks like it is really loose, and could be tightened, but it’s deceptive.
    IErdos offered $500 for a proof of an upper bound of $n^{1/2} + O(1)$.

    • Ben Green Says:

      Indeed, it seems very hard to improve Lindstrom’s result in any way. Erdos conjecture is surely false, as most likely one can dilate a Sidon subset of Z/qZ of size q^{1/2} so as to have a gap of size q^{1/2}logloglog q (say), and then “unwrap” so as to get a Sidon set of size q^{1/2} in an interval of length appreciably smaller than q. However, I have no idea how to achieve this with any of the known constructions of large Sidon sets modulo q. Being able to find such large gaps is most likely a generic property (i.e. has nothing to do with being Sidon) but I have no idea how to prove that either.

    • obryant Says:

      As a point of history, the Erdos-Turan proof and the Lindstrom proof both give n^{1/2}+n^{1/4}+1 (iirc, the “+1″ can be improved to “+1/2″), although E-T only noted n^{1/2}+O(n^{1/4}).

    • Seva Says:

      I wonder whether one can use Ben’s idea in conjunction with Ruzsa’s
      construction, as follows. Let $p$ be a prime, and consider indices (discrete
      logarithms) with respect to a fixed primitive root modulo $p$. With every
      integer $x\in[1,p-1]$ associate the residue class of $(p-1)x+p\,{\rm
      ind}\,(x)$ modulo $p(p-1)$. The set of all $p-1$ resulting elements of
      ${\mathbb Z}_{p(p-1)}$ is a Sidon set. Define $\varphi\colon
      [1,p-1]\to{\mathbb Z}_{p-1}$ by $\varphi(x)=x+{\rm ind}\, x\pmod {p-1}$.
      Writing $(p-1)x+p\,{\rm ind}\,(x)=(x+{\rm ind}\,(x))p -x$, we see that to
      answer Erdos’ question, it suffices to show that the full image
      $\varphi([1,p-1])$ misses some, say, $\log\log\log p$ consecutive elements of
      ${\mathbb Z}_{p-1}$. A simple heuristic shows that is most certainly true (a
      typical element of ${\mathbb Z}_{p-1}$ is missing in $\varphi([1,p-1])$ with
      probability about $1/e$), but is there a hope to \emph{prove} this? Notice
      also that we do not need to have the result for all pairs $(p,g)$ (where $g$
      is a primitive root modulo $p$), but just for any infinite sequence of such
      pairs.

    • Seva Says:

      (This comment is identical to that I posted yesterday, but with a proper formatting attempted.)

      I wonder whether one can use Ben’s idea in conjunction with Ruzsa’s construction, as follows. Let p be a prime, and consider indices (discrete logarithms) with respect to a fixed primitive root modulo p. With every integer x\in[1,p-1] associate the residue class of (p-1)x+p\,{\rm ind}\,(x) modulo p(p-1). The set of all p-1 resulting elements of {\mathbb Z}_{p(p-1)} is a Sidon set. Define \varphi\colon [1,p-1]\to{\mathbb Z}_{p-1} by \varphi(x)=x+{\rm ind}\, x\pmod {p-1}. Writing (p-1)x+p\,{\rm ind}\,(x)=(x+{\rm ind}\,(x))p -x, we see that to answer Erdos’ question, it suffices to show that the full image \varphi([1,p-1]) misses some, say, \log\log\log p consecutive elements of {\mathbb Z}_{p-1}. A simple heuristic shows that is most certainly true (a typical element of {\mathbb Z}_{p-1} is missing in \varphi([1,p-1]) with probability about 1/e), but is there a hope to prove this? Notice also that we do not need to have the result for all pairs (p,g) (where g is a primitive root modulo p), but just for any infinite sequence of such pairs.

  7. David Roberts Says:

    “the logs of the primes are not integers. Indeed, there are far more of them than there are integers.” Not quite right. There are exactly the same number of integers and logs of primes. I suspect that the ‘them’ is meant to refer to reals. :-)

    • Benoît Régent-Kloeckner Says:

      What Tim Gowers meant is that in a given interval [0,N], there are far more logs of prime than integer.

    • David Roberts Says:

      Ah, I see! But the discussion at that point was about infinite Sidon sets, so I was distracted. Thanks, Benoît.

  8. Ben Green Says:

    Tim, I think there are constructions of Sidon subsets of $\{1,…,N\}$ of size about $\sqrt{N}$ coming from finite fields, due to Bose and Chowla. Consider $F_p$ inside $F_{p^2}$, and let $a$ be a generator of the multiplicative group of $F_{p^2}$. Let $S \subseteq Z/(p^2 – 1)Z$ be the set of all $s$ such that $a^s – a \in F_p$. Then this is a Sidon set (in fact it is Sidon modulo $p^2 – 1$). Ruzsa has some other constructions too. I certainly believe that all large Sidon sets are “algebraic” in some way that I am unable to make precise. This example of Ruzsa shows that one cannot hope for too much in that direction. I must say that I wasn’t previously aware of it either, despite having read Ruzsa’s paper in detail some years ago.

  9. obryant Says:

    There’s an idea I’ve been sitting on for years, and haven’t been able to turn it into anything. First let me give a dubious heuristic-y construction of a Sidon set, and then I’ll give an actual example to demonstrate that, at least, the idea isn’t idiotic.

    Let (X,T,\mu) be a dynamical system, and suppose that T is ergodic, and that \mu(X)=1. Let E \subseteq X be an arbitrary set (measurable, of course), and let x be a randomly chosen point of X. Now let S be the set of integers \{ n : 0\leq n \leq N, T^n x \in E\} where N is parameter to be named later. Since T is ergodic, the expected size of S is N\mu(E); perhaps we can take N \approx 1/\mu(E)^2 so that |S| \approx \sqrt{N}. I claim that S is pressured to be a Sidon set, at least after removing a small number of elements.

    Why? Suppose that a,b,c,d are all in S, and a-c=d-b > 0, contrary to the claimed Sidon-ness of S (set k=a-c). This means that the two points T^c x, T^b x are both in E, and so are “close together”. But also T^k maps these two close points to T^a x, T^d x, which are not only close to each other but close to the original two points. My intuition is that if T is sufficiently strongly mixing, then it should be very rare (i.e., very few x) that a small power of T maps two points in E to two points in E. Caveat: I don’t know what “sufficiently strongly mixing”, “very rare”, or “small power” actually need to mean to make this work, if indeed there is any way to make it work.

    So here’s the promised example, which is really a Bose-Chowla set in disguise. Let X=[0,1) \times [0,1), \mu Lebesgue measure, and define T(y,z) to be (4y+z,2y+2z) \mod 1. This is a linear map with determinant 6, so it is ergodic. Set N=289, and let E be any of the sets \{(y,z) : k/17 \leq y < (k+1)/17\} with 1\leq k 16 (or replace the special role played by y with z, that works, too). Let x=(0,1/17). (Above, I suggested taking random x and fixed E, but here I'm taking one x and many E's. Oh well.) All 32 of the resulting sets are Sidon sets!

    All of the constructions of Sidon sets that give \sqrt{N} are based on finite fields, and the error term in the maximum possible size of a Sidon set are from the gaps between prime numbers. Any construction that gives \sqrt{N} without using primes would be interesting, and possibly the first improvement since the early 1940s.

  10. yan Says:

    Hi Dr Gowers
    my name is Yan, I read “what is implied by “implies””you wrote
    And I have a question for you. Can you just spend a little bit time and give me some help?
    it is annoying question about vacuous proof.

    for example, let’s prove ∅ is the subset of every set A.
    This statement can be translated into another way:for every x, if x is the element of ∅,then x is the element of A.
    since x is the element of ∅ is always false. So this statement is vacuous true.
    My problem is why can‘t we substitue x by non-exist things,for example, what if x represents unicorn?then unicorn is an element of ∅ will be true not false?so x is the element of empty set is not always true

    by this problem, can we get the conclusion that all the varibles in the statement can just be substituted by exist things? which means the scope of a variable can just be exist thing?

    I appreciate your help Dr Gowers~

  11. Another way of looking at the alephs « cartesian product Says:

    [...] What are dense Sidon subsets of {1,2,…,n} like? (gowers.wordpress.com) [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,541 other followers

%d bloggers like this: