This is the second post on Rudin’s conjecture. For the first introductory notes see here. In this post I will try to build some more intuition on -sets by studying some examples and discussing their properties. We will also discuss some basic question that have been studied in the literature of -sets.
1. Lacunary sequences and -sets.
for all -polynomials . Remember that if (1) holds for some then it holds for all such and this is just a consequence of Hölder’s inequality.
It is pretty obvious that not every subset of the integers can be a -set. In particular the integers themselves are not a -set and this can be very easily verified by checking against the Dirichlet Kernel for which we have , being the dual exponent of and .
On the other hand, the easiest example of a -set is probably a lacunary sequence.
1.1. Hadamard lacunary sequences
Definition 1 Let be a sequence of positive integers. The sequence is called lacunary in the sense of Hadamard if there exists some constant such that
Now it is a classical result (due to Salem and Zygmund) that a Hadamard lacunary sequence is a -set. That is, we have
We will present the proof here since it’s illustrative of the combinatorial nature of Rudin’s problem, at least in the case where is an even positive integer. As in the proof of Proposition 10 of the previous post, we define now the numbers to be the number of the representations of the positive integer in the form
where . Here there is a subtle point since different permutations of `count’ as different representations. One can however the number of representations when say . All the other representations are just permutations of this one so it is enough to multiply by .
We have the following lemma:
Proof: Observe that we have
where we have used Cauchy-Schwartz in the first inequality.
Lemma 3 allows us to construct -sets for an even integer by combinatorial means. In particular it is enough to construct sets such that every equation
has at most one solution (modulo permutations) with . In fact we have the following proposition which is slightly more general:
Proposition 4 (Rudin) Let be a set of non-negative integers and let be a positive integer. If is a union of (a bounded number of) sets such that for each the function is a bounded function of . Then is a -set.
Proof: Obviously it is enough to prove the Proposition for and then use the triangle inequality. However, for , the conclusion is just an application of Lemma 3.
We will take up this issue later on, after we complete our discussion on lacunary sequences.
Proof of Theorem 2: Let us consider a lacunary set with . Then for a positive integer , and a positive integer, let us consider the equation
with in and positive integers with . Now assume there are two different representations of as a sum of elements in :
with . Since we have assumed that the two representations are different, there will be a maximum element of which only appears in one of the two representations or which appears more times in one or the other representation). We conclude an equality of the form
where and for . However this implies that
which is impossible whenever . We conclude that for a lacunary sequence with lacunary constant , the representation of integers in the form (2) is unique up to permuations. we have . However, every lacunary sequence can be written as a union of lacunary sequences with lacunary constants and . Using Proposition 4 we conclude that for every -polynomial we have
In fact the implied constant can be calculated to something like .
Two more properties of lacunary sets are important in our discussion.
1.2. Sidon sets and -sets.
Lacunary sets actually satisfy a stronger property than the -property that is, they are Sidon sets:
Definition 5 Let . Then is called a Sidon set if
for all -polynomials .
The notion of a Sidon set is genuinely stronger than that of a -set, for all , that is, there exist sets which are -sets for but are not Sidon sets. In [R], Rudin showed the following theorem
for all -polynomials . Then is a -set for all . Furthermore we have that
for all -polynomials
where the supremum is taken over all -polynomials .
It is not very hard to see that lacunary sets are actually Sidon sets. The proof can be found in [R].
2. -sets of maximal density.
An obvious fact about set is the inclusion:
This is because of the definition of -sets and Lemma 4 of the previous post. A natural question is whether this inclusion is proper:
The question was originally posed by Rudin in [R]. The case is settled (in the negative) by the following theorem of Bachelis and Ebenstein [BE]:
Theorem 9 (Bachelis, Ebenstein) Let . Then the set is an open set.
Thus we are left with the range in Rudin’s question. Rudin himself answers the question in [R], in the special case where is an even integer:
We will present a proof of Theorem 10 adopting a slightly different construction that the on in [R] although the ideas are very similar. First observe that if we construct a set for which is a bounded function of , then Proposition 4 guarantees that is a -set. In Theorem 8 of the the previous post we saw that, for , a set satisfies . This means, that any -term arithmetic progression contains at most elements of . Based on this fact we give the following definition:
Definition 11 A -set has maximal upper density if
It is essential to notice here that a -set of maximal upper density cannot be a -set for any since if is a -set. Thus, in order to answer Rudin’s question 8 in the case where is an even integer it is enough to construct -sets of maximal upper density. We will now digress a bit in order to discuss the notion of -set.
2.1. -sets of maximal size.
where is an integer and .
Definition 12 A set is called a -sequence if for every , equation (5) has at most one solution such that .
Remark 1 -sequences are mentioned in the literature as Sidon-sets. This is not to be confused with the notion of Sidon sets defined earlier in this post. We will stick to the -notation to avoid ambiguity.
If is -sequences then obviously which is the smallest possible value of . This interest in sequences lies here in the fact that sequences are -sets. This is an immediate application of by Lemma 3. The following theorem of Bose and Chowla from [BC] constructs finite -sets of maximal size:
such that the sums
are all distinct . By a suitable choice of representatives modulo the ‘s can be chosen to satisfy
The proof of this theorem lies beyond the purposes of this post. However the exposition in [BC] is really easy to follow and the article is freely available.
2.2. Constructing -sets of maximal upper density
Of course the -sequence constructed in Theorem 13 is a finite sequence and as such, it can’t have positive upper density. However, it has maximal size since there is an arithmetic progression of length which contains terms of the sequence. This will be enough for our purposes here since we can exploit the construction of theorem 13 in order to construct a of maximal upper density, although we don’t claim anything about the -properties of this set. The idea is to place such sets in dyadic pieces of the positive integers and glue them together. Since the size of these sets is maximal, , and the dyadic pieces become arbitrarily large, the upper density of the set will be positive.
The first step is the following proposition:
Proof: Fix your favorite prime and define the positive integer by . From Theorem 13 there exists a set of size . Since our set is contained in . On the other hand we have that
that is .
Proof: Using Proposition 14 we construct for each , a set which is contained in . For this, just translate the sets constructed in the Proposition by . Note that each set has size . Now we define
Observe that for , the set has at least terms in the arithmetic progression . We conclude that has positive upper density. To see that is a -set, let be an -polynomial. Invoking the Littlewood-Paley inequalities we have for any
where is the Littlewood-Paley square function:
Since is an -polynomial and , we have for all
Furthermore, since each one of the sets is a -set with the same -constant, we have
We conclude that
Remark 2 In [B], Bourgain extends the result of Rudin, Theorem 10, by proving that for any there exist -sets which are not -sets for any . For this we need the analogue of Proposition 14 for any . Bourgain proves this using the probabilistic arguments. In fact his proof shows that `most’ subsets of of size have the -property.
- [B] Bourgain, J., Bounded orthogonal systems and the -set problem, Acta Math. 162 (1989), no. 3-4, 227–245
- [BC] Bose, R. C., Chowla, S., Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962/1963)
- [BE] Bachelis, G., Ebenstein, S., On sets, Pacific J. Math. Volume 54, Number 1 (1974), 35-38.
- [R] Rudin, W., Trigonometric Series with Gaps, Indiana Univ. Math. J. 9 No. 2 (1960), 203–227.