Sidon-like Sets

Additive Combinatorics

What is the largest set avoiding a linear equation? This general question is a central one in additive combinatorics. Indeed the search of extremal structures gives it a combinatorial flavor, while the presence of an additive equation makes such a question ripe for additive techniques. Such questions include well-studied subjects such as sum-free sets, Sidon sets, and sets avoiding arithmetic progressions. In 1993, Ruzsa made an effort to put these examples into a general framework. In what follows, we focus on Sidon sets and their generalizations, as developed by Ruzsa in the same paper.

We fix {k \geq 2} and consider the linear equation

\displaystyle x_1 + \ldots + x_k = y_1 + \ldots + y_k \ \ \ \ \ (1)

Following, Ruzsa, we say a solution is trivial if the {x_i} are a permutation of the {y_i}. We set {r(N) = r_k(N)} to be the size of the largest set of {[N]} with only trivial solutions to (1). We set {R(N) = R_k(N)} to be the size of the largest set of {[N]} with no solutions to (1) in {A} with {x_1 , \ldots , x_k , y_1 , \ldots y_k} distinct. It follows from these definitions that

\displaystyle r(N) \leq R(N).

We will show below that {R_k(N) \ll_k r(N)}, while it is not known It is not known if {R_k(N) \ll r_k(N)}. Indeed one may feel that most of the solutions to (1) where the variables lie in a set {A} come when the variables are distinct, since otherwise we have imposed an additional constraint. This idea does work well for sets with additive structure, but has shortcomings for general sets. Furthermore, it was shown by Timmons that {r_3(N) \neq (1 + o(1)) R_3(N)}.

For a set {A \subset [N]}, we let {n(A)} be the number of nontrivial solutions to (1) in {A} and let {N(A)} be the number of solutions to (1) with distinct variables.

We briefly remark that in Wooley’s efficient congruencing proof of Vinogradov’s mean value theorem, he estimates quantities similar to {N(A)} (where {A} is the set of {k^{\rm th}} powers), as applications of Hensel’s lemma require the variables to be distinct (modulo a certain prime). Indeed there are some overlapping techniques (see Lemma 1 below).

To start, we first consider the case {k=2}. A set with {n(A) = 0} is known in the additive combinatorics literature as a Sidon set. Thus {r_{A-A}(x) \leq 1} for {x \neq 0}. There is a nice construction due to Ruzsa (modifying a previous construction of Erdős), which is just one of several known constructions.

Example 1 (Large Sidon Set): Let {p} be a prime. Let {g} be a primitive root in {\mathbb{F}_p}. One can check the set of residues in the cyclic group of order {p(p-1)}, defined via the Chinese remainder theorem, by

\displaystyle x = k \ {\rm mod} \ p-1 , \ x = g^k \ {\rm mod} \ p , \ \ \ 0 \leq k \leq p-1,

forms a Sidon set in the cyclic group modulo {p(p-1)} and hence in {\mathbb{Z}}. {\spadesuit}

On the other hand, we have the following upper bound.

Theorem 1: Let {A \subset [N]} be a Sidon set. Then

\displaystyle |A| \leq N^{1/2} + N^{1/4} + 1. \ \ \ \spadesuit

Proof: We follow an argument of Green, which will rely on some basic Fourier analysis (we follow notation from Chapter 4 of Tao and Vu’s book on additive combinatorics). Let {1 \leq u \leq N} and consider {A} as a subset of {Z : = \mathbb{Z} / (N+u) \mathbb{Z}}. Let {I = \{1 , \ldots , u\}}. We have by Parseval,

\displaystyle (N+u)^2\sum_{x \in Z} 1_A * 1_{-A}(x) 1_I * 1_{-I}(x) = (N+u)^3 \sum_{\xi} |\widehat{1_A}(\xi)|^2 |\widehat{1_I}(\xi)|^2 \geq \frac{|A|^2 |I|^2}{N+u},\ \ \ \ \ (2)

in the last step isolating the {\xi = 0} term. Since {A} is a Sidon set we have

\displaystyle (N+u)1_{A} * 1_{-A}(x) \leq 1,

for {0 < |x| \leq u} (note this is not true for other values of {x \in Z}). Thus

\displaystyle (N+u)^2\sum_{x \in Z} 1_A * 1_{-A}(x) 1_I * 1_{-I}(x) \leq |A| u + u^2.\ \ \ \ \ (3)

Combining (2) and (3) and choosing the optimal choice of {u = \lfloor N^{3/4} \rfloor} gives the desired result. {\spadesuit}

Green remarks in his paper that above proof only assumes that {r_{A-A}(x) \leq 1} for {0 < x < N^{3/4}} instead of the full Sidon set property. Combining Example 1 and Theorem 1, we find

\displaystyle N^{1/2} \leq r_2(N) \leq N^{1/2} + N^{1/4} + 1.

It is a famous question of Erdős to improve these bounds (in particular the lower bound), which has been stuck for over fifty years (modulo a improvement by Cilleruelo to {N^{1/2} + N^{1/4} + 1/2}). It seems likely that both the lower and upper bound are not optimal and that the truth lies somewhere between {N^{1/2} + C} and {N^{1/2} + O(N^{\epsilon})} for any {C\geq 1} and {\epsilon > 0}. One can see this blog post of Gowers and the comments within for interesting discussion of this problem.

We now consider general {k} and start with a lower bound.

Proposition 1 (Random sets): For {N} large enough,

\displaystyle r(N) \geq \frac{1}{2}8^{-1/(2k-1)} N^{1/(2k-1)} . \ \ \ \spadesuit

Proof: We use the alteration method, which is discussed in Alon and Spencer’s book on the Probabilistic Method. Choose {A \subset [N]} where each element is chosen independently at random with probability

\displaystyle p = 8^{-1/(2k-1)}\frac{N^{1/(2k-1)}}{N}.

The number of solutions to (1) in {[N]} is at most {N^{2k-1}}, so the expected number of solutions to (1) is at most {p^{2k}N^{2k-1}}. By Markov,

\displaystyle \mathbb{P}(n(A) > 2p^{2k}N^{2k-1}) < \frac{1}{2}.

On the other hand, by say Chebyshev,

\displaystyle \mathbb{P}(|A| < \frac{1}{2} p N) < \frac{1}{2},

for {N} large enough. By the union bound, we may choose an {A} such that {|A| \geq pn/2} and {n(A) \leq 2p^{2k} N^{2k-1}}. By our choice of {p}, we have {n(A) \leq |A|/2}. For each nontrivial solution of (1), we delete an element (the so-called alteration) of {A} that renders it no longer a solution and call the resulting set {A'}. Thus {n(A') = 0} and so {r(N) \geq |A'| \geq pN/2}, as desired. {\spadesuit}

Ruzsa remarks that the probabilistic construction above probably never gives the correct order of magnitude for {r(N)}, where (8) is replaced by a suitable linear equation. We already saw this above, as Example one gives a Sidon set of size {N^{1/2}} while the random construction gives one of size about {N^{1/3}}. Moreover, with an explicit construction, Bose and Chowla showed the following improvement to Proposition 1:

\displaystyle r(N) \geq (1 + o(1)) N^{1 / k},

(see this survey of Kevin O’ Bryant for more information). Timmons showed that

\displaystyle R(N) \geq (2^{1 - 1/k} + o(1))N^{1/k},

by pasting together two sets from the aforementioned Bose-Chowla construction.

We now turn to upper bounds. We let {T_k(A)} be the number of solutions in {A} to (1) For any set with {n(A) = 0}, we have that {T_k(A) \leq k!|A|^k} and so by Cauchy Schwarz

\displaystyle |A|^{2k} \leq |kA| T_k(A) \leq k N k! |A|^k.\ \ \ \ \ (4)

It follows that

\displaystyle r(N) \leq (k! k )^{1/k} N^{1/k},

and thus

\displaystyle r(N) \asymp_k N^{1/k}.

This argument fails to bound {R(N)}, as was observed by Ruzsa, who provided an alternative argument, which we recall below. The basic idea is to still use (4), and to show that {T_k(A)} is still small for sets with {N(A) = 0}. We will need the following lemma.

Lemma 1 (Hölder): Let {f} be a function on the torus. Then

\displaystyle \int |f|^{2k-2} \leq \left( \int |f|^{2k} \right)^{1 - 1/(k-1)} \left(\int |f|^2 \right)^{1/(k-1)}.

To prove this, apply Hölder’s inequality to {|f|^{2k} = |f|^{2k - 2/(k-1)} |f|^{2/(k-1)}} with powers {(k-2)/(k-1)} and {k-1}. Note that one can always interpolate an upper bound for {\int |f|^p} in terms of {\int |f|^u} and {\int |f|^v} as long as {u < p < v}.

Proposition 2: We have

\displaystyle R(N) \leq (1 + o(1) )k^{2 - 1/k} N^{1/k}. \ \ \ \spadesuit

Proof: Suppose that {N(A) = 0} (though we will not make use of this until the end). By (4), it is enough to show

\displaystyle T_k(A) \leq (1 + o(1))k^{2k-2} |A|^k.

Note that

\displaystyle T_k(A) = \int |f|^{2k} , \ \ \ f(x) = \sum_{a\in A} e^{2 \pi i a}.

By Lemma 1 and Parseval, it is enough to show

\displaystyle T_k(A) \leq (1 + o(1))k^2 |A| \int |f|^{2k-2}.

The idea is that {N(A) = 0} allows us to eliminate a variable at a cost of only {k^2 |A|}, as opposed to the trivial bound of {|A|^2}.

We let

\displaystyle s(n) = \#\{(x_1 , \ldots , x_k) \in A^k : x_1 + \ldots + x_k = n, \ \ x_i \ \text{distinct} \},

and

\displaystyle \sigma(n) = \#\{(x_1 , \ldots , x_k) \in A^k : x_1 + \ldots + x_k = n\}.

Note we have

\displaystyle T_k(A) = \sum_n \sigma(n)^2.

By the triangle inequality in {\ell^2}, it is enough to show

\displaystyle \sum_n (\sigma(n) - s(n))^2 \leq k^4 \int |f|^{2k-2} , \ \ \ \sum_n s(n)^2 \leq k^2 |A| \int |f|^{2k-2} .\ \ \ \ \ (5)

Note the second term is the larger of the two for {|A|} large.

We dispose of the first inequality. Note {\sigma(n) - s(n)} is the number of solutions to {x_1 + \ldots + x_k = n} with some {x_i = x_j}. There are at most {k^2} choices for the indices and then after relabelling we find

\displaystyle 2x_1 + x_2 + \ldots + x_{k-1} = n.

Thus

\displaystyle \sum_n (\sigma(n) - s(n))^2 \leq k^4 \int |f(2x)|^2 |f(x)|^{2k-4} \leq k^4 \int |f|^{2k-2},

by Hölder’s inequality.

Now we finally use that {N(A) = 0}. Suppose we have a solution to (1) with distinct {x_i} and distinct {y_j}. Since {N(A) = 0}, this implies {x_i = y_j} for some {1 \leq i , j \leq k}. Thus

\displaystyle \sum_n s(n)^2 \leq k^2 |A| \int |f|^{2k-2},

since we have {k^2} choices for {i,j} and {|A|} choices for {x_i}. {\spadesuit}

The best bound for {r(N)} (for {k} large) is due to Green and is of the form

\displaystyle r(N) \leq (1 + o_N(1)) (1 + o_k(1)) \frac{k}{2e} N^{1/k},\ \ \ \ \ (6)

an improvement to the constant in (4). On the other hand, the best bound for {R(N)} is in a recent paper of Schoen and Shkredov:

\displaystyle R(N) \leq 16 k^{3/2} N^{1/k}, \ \ \ N \ \text{large enough}\ \ \ \ \ (7)

adopting ideas from Timmons as well as Ruzsa’s original work. Schoen and Shkredov implicitly mention the following question.

Question 1: Let {A \subset \mathbb{Z}} such that {N(A) = 0}. Does there exist a large {B \subset A} (say {|B| \geq |A| / 2}) such that {B} has no solutions to

\displaystyle x_1 + \ldots + x_{\ell} = y_1 + \ldots + y_{\ell},\ x_i, y_j \ \text{distinct} \ \ \ 1 \leq \ell \leq k.\ \ \ \ \ (8)

An affirmative answer would allow one to apply (5) and then (4) to {B} and eventually get improved bounds for {R(N)} comparable to what is known for {r(N)} (i.e. the same as (6) up to the absolute constant). Schoen and Shkredov are not able to solve Question 1, but are able to show that (8) holds for many {\ell} and then apply a suitable version of Erdős-Ko-Rado to obtain (7). Underlying their argument is the simple observation that a solution to (1) with {k = m} can be added to a solution with {k = n} to create a new solution with {k = m + n}.

We illustrate part of the argument in the {k=4} case, which is significantly simpler than the general case and already handled by Timmons.

Proposition 3: One has

\displaystyle R_4(N) \leq (1 + o(1)) 2^{1/8} 4^{5/8} N^{1/4}.

Proof: We let {A \subset [N]} with {N(A) = 0}. By the first part of (5) and Lemma 1, we have

\displaystyle T_4(A) \leq (1 + o(1))\sum_n s(n)^2.

By the second part of (5),

\displaystyle \sum_n s(n)^2 \leq 16 |A| \int |f|^{6} \leq 16 |A| (\int |f|^8 )^{1/2} (\int |f|^4)^{1/2},

and so

\displaystyle T_4(A) \leq 16^2 |A|^2 \int |f|^4.

Suppose first that {A} has no solutions to (8) with {\ell = 2}. Then

\displaystyle \int |f|^4 \leq 4 |A|^2 .

Indeed there are at most {2|A|^2} solutions to {a+b= c+d} with either {a=b} or {c=d} and also {\leq 2|A|^2} trivial solutions. It follows that

\displaystyle T_4(A) \leq 4^5 |A|^4.

Combining this with (4) gives the desired result. Now suppose {A} does have a solution to (8) with {\ell =2}, say

\displaystyle x_1 + x_2 = y_1 + y_2. \ \ \ \ \ (9)

Delete these four elements from {A} to create {A'}. Now we claim {A'} does not have a solution to (8) with {\ell = 2}. Indeed if there were, say

\displaystyle a_1 + a_2 = b_1 + b_2,

then adding this to (9) yields

\displaystyle a_1 + a_2 + x_1 + x_2 = b_1 + b_2 + y_1 + y_2,

which contradicts {N(A) = 0}. Thus we may apply the above argument to {A'} to obtain

\displaystyle T_4(A') \leq (1+o(1)) 4^5 |A'|^4,

and the Proposition follows from (4). {\spadesuit}

Leave a Reply