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.

This entry was posted on July 13, 2012 at 11:50 am and is filed under Straight maths. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

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

Gil Kalai Says:
July 13, 2012 at 5:05 pm | Reply
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:
  July 13, 2012 at 11:22 pm
  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:
  July 16, 2012 at 1:01 am
  Dear Tim and Gil,
  
  Another result in this direction was obtained recently by Kohayakawa, Lee, Rodl and Samotij (see Theorem 2.1):
  
  Click to access 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:
  July 16, 2012 at 9:10 am
  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.
Terence Tao Says:
July 13, 2012 at 5:17 pm | Reply
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.
Mark Lewko Says:
July 14, 2012 at 5:42 am | Reply
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:
  July 16, 2012 at 9:17 am
  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:
  July 20, 2012 at 8:54 am
  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
  
  Click to access 9808061.pdf
gowers Says:
July 15, 2012 at 11:11 pm | Reply
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:
  July 16, 2012 at 9:39 am
  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.
Thomas Says:
July 16, 2012 at 7:53 am | Reply
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:
  July 16, 2012 at 10:52 am
  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$?
Neil Calkin Says:
July 16, 2012 at 3:43 pm | Reply
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:
  July 20, 2012 at 8:58 am
  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:
  July 21, 2012 at 6:05 am
  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:
  January 12, 2013 at 11:19 am
  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:
  January 13, 2013 at 8:38 am
  (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.
David Roberts Says:
July 17, 2012 at 8:24 am | Reply
“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:
  July 18, 2012 at 8:29 am
  What Tim Gowers meant is that in a given interval [0,N], there are far more logs of prime than integer.
- David Roberts Says:
  July 19, 2012 at 5:53 am
  Ah, I see! But the discussion at that point was about infinite Sidon sets, so I was distracted. Thanks, Benoît.
Ben Green Says:
July 20, 2012 at 8:46 am | Reply
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.
- obryant Says:
  July 21, 2012 at 5:21 am
  FYI, the constructions of Bose & Chowla (mod $q^2-1$ ), Singer (mod $q^2+q+1$ ), and Ruzsa (mod $p(p-1)$ ) are given in my now old survey/bibliography at Electronic Journal of Combinatorics (http://www.combinatorics.org/ojs/index.php/eljc/article/view/ds11).
obryant Says:
July 21, 2012 at 6:03 am | Reply
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.
yan Says:
July 21, 2012 at 7:18 am | Reply
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~
Another way of looking at the alephs « cartesian product Says:
September 17, 2012 at 5:57 pm | Reply
[…] What are dense Sidon subsets of {1,2,…,n} like? (gowers.wordpress.com) […]
jean-camille Says:
November 18, 2017 at 4:29 pm | Reply
If $S=\left\{S_i,\, 0\leq i\leq n\right\}$ , we define $P_S=S_0 + S_1.X+….+S_n.X^n$.

Maybe a conjecture could be of the form :
For any Sidon set $A$ , with $n=max(A)$ , such that $|A|\leq C(n^{1/2})$ there exists $Q\in \mathcal Q$ , such that $F(P_A-P_Q)\leq G((C(n^{1/2})-n^{1/2}))$ ,
Where
_ $C\,:\,\mathbb{R}\to \mathbb{R}$ is a fonction that we have to find , that is close to identity
_ $\mathcal{Q}$ is a set of Sidon sets with some quadratic property that we have to precise
_ $F$ is a increasing fonction from $(\mathbb{Z}[X],<_X)$ to $(\mathbb{R},<)$ , where $<_X$ is order relations that we also have to precise (for example we can take $R_1<_X R_2$ iff $R_1(1)\leq R_2(1)$ )
_ $G \,:\, \mathbb{R}\to \mathbb R$ is such that $G(a)$ is small when $a$ is small.

The idea is that if we get $|A|$ close to $n^{1/2}$ we can find a Sidon set with a quadratic structure close to $A$ . But maybe it is not enough and you want $A$ to have itself the "quadratic property", not just close to a set that has it….

We can also state a "skeleton" of direct conjecture – that could maybe help to find/solve the inverse problem that we try to formulate – as :

For any $A$ , there exists $Q\in mathcal{Q}$ such that
$|A|\leq H(Q)$ where $H(Q)$ is close to $n^{1/2}$ when $P_A-P_Q$ is small (for $<_X$ )
As I'm not familiar with the problem, I won't take the risk to give explicit $\mathcal{Q}$ , $C$ , $F,G,H....$ so I don't really "say something" neither. But just a direction, so that we might be able to discuss on the choice of each parameter.
- jean-camille Says:
  November 18, 2017 at 4:41 pm
  I fisrt took $G$ from $\mathbb{R^{\mathbb{R}}}\to \mathbb{R}$ and wrote the condition $F(P_A-P_Q)\leq G(C)$ , I think it was a better precaution, we just say that $G(C)$ is small when $C(n^{1/2}$ is close to $n^{1/2}$ instead of previous “ $G(a)$ is small when $a$ “is small”.
- gowers Says:
  November 23, 2017 at 7:21 pm
  As Ben Green points out above, it is too much to ask for quadratic behaviour. For example, consider the subset of $\{1,2,\dots,p-2)\}\times\mathbb F_p^*$ that consists of all points $(x,a^x)$ , where $a$ is a generator of the multiplicative group mod $p$ (which I have denoted by $\mathbb F_p^*$ ). Then if $(x,a^x)-(y,a^y)=(z,a^z)-(w,a^w)$ , then we have $x,y,d\in\{1,2,\dots,p-2\}$ such that $a^x-a^{x+d}=a^z-a^{z+d}$ , which gives us that $a^x(1-a^d)=a^z(1-a^d)$ , and therefore $a^x=a^y$ and therefore $x=y$ . This example can be embedded into the integers in the usual way, and shows that it is possible for an example to be non-quadratic in a fairly fundamental way. So a good conjecture would somehow have to come up with a definition that could unify this example with the quadratic one. It seems quite a good idea to focus on graphs of functions: I think it may be possible to convert any example into a graph by a process such as multiplying by a random number mod $p$ , for some prime $p$ close to $n$ , splitting up into intervals of length roughly $\sqrt n$ , and throwing away a certain proportion of the set so that each element lives in the first half of its interval and there is only one such element per interval.
Sidon-like Sets | George Shakan Says:
December 12, 2018 at 8:58 pm | Reply
[…] bound are not optimal and that the truth lies somewhere between and for any and . One can see this blog post of Gower’s and the comments within for interesting discussion of this […]
Sidon sets and sum-product phenomena – Cosmin Pohoata Says:
January 23, 2021 at 4:21 am | Reply
[…] refer the interested reader to this consult this nice survey of O’Bryant and this beautiful blog post of Gowers for more […]
The apparent structure of dense Sidon sets – Random Permutations Says:
July 14, 2021 at 2:34 pm | Reply
[…] “What are dense Sidon sets of {1, …, n} like?”, asked Tim Gowers on his blog almost ten years ago. A Sidon set is a set without any solutions to , which in additive combinatorics jargon means that it has minimal additive structure. Almost paradoxically, large sets with this property appear to be structured in another way, and that’s a bit of a mystery currently. […]