## The Rudin (Hardy-Littlewood) Conjecture, Notes 2: A closer look at Λ(p)-sets.

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 ${\Lambda(p)}$-sets by studying some examples and discussing their properties. We will also discuss some basic question that have been studied in the literature of ${\Lambda(p)}$-sets.

1. Lacunary sequences and ${\Lambda(p)}$-sets.

Let us briefly recall the definition of ${\Lambda(p)}$-sets. For ${E\subset \mathbb Z}$, let ${f:\mathbb T \rightarrow {\mathbb C}}$ be an ${E}$-polynomial, that is ${\hat f(n)=0}$ for all ${n\notin E}$ and ${f}$ is a trigonometric polynomial. For ${0 we call ${E}$ a ${\Lambda(p)}$-set if there exists a ${q such that

$\displaystyle \|f\|_p\lesssim_p \|f\|_q, \ \ \ \ \ (1)$

for all ${E}$-polynomials ${f}$. Remember that if (1) holds for some ${0 then it holds for all such ${q}$ 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 ${\Lambda(p)}$-set. In particular the integers themselves are not a ${\Lambda(p)}$-set and this can be very easily verified by checking against the Dirichlet Kernel for which we have ${\|D_N\|_p \simeq N^\frac{1}{p'}}$, ${p'}$ being the dual exponent of ${1 and ${\|D\|_1\simeq \log N}$.

On the other hand, the easiest example of a ${\Lambda(p)}$-set is probably a lacunary sequence.

Definition 1 Let ${A=\{a_1,a_2,a_3\ldots\}}$ be a sequence of positive integers. The sequence ${\{a_k\}_{k=1} ^\infty}$ is called lacunary in the sense of Hadamard if there exists some constant ${\lambda>1}$ such that

$\displaystyle \frac{a_{k+1}}{a_k}>\lambda,\quad k=1,2,3,\ldots$

Now it is a classical result (due to Salem and Zygmund) that a Hadamard lacunary sequence ${A}$ is a ${\Lambda(p)}$-set. That is, we have

Theorem 2 (Salem, Zygmund) Let ${A=\{a_1,a_2,\ldots\}}$ be a lacunary sequence of positive integers. Then ${A}$ is a ${\Lambda(p)}$-set for all ${0.

We will present the proof here since it’s illustrative of the combinatorial nature of Rudin’s problem, at least in the case where ${p}$ is an even positive integer. As in the proof of Proposition 10 of the previous post, we define now the numbers ${r_k(E,n)}$ to be the number of the representations of the positive integer ${n}$ in the form

$\displaystyle n=n_{i_1}+n_{i_2}+\cdots+n_{i_k},$

where ${n_{i_1},\ldots,n_{i_k}\in E}$. Here there is a subtle point since different permutations of ${n_{i_1},\ldots,n_{i_k}}$ count’ as different representations. One can however the number of representations when say ${n_{i_1}\leq \cdots \leq n_{i_k}}$. All the other representations are just permutations of this one so it is enough to multiply by ${k!}$.

We have the following lemma:

Lemma 3 Let ${E=\{n_1,n_2,n_3\ldots \}}$ and ${f}$ be an ${E}$-function. Then for all positive integers ${h}$ we have that

$\displaystyle \begin{array}{rcl} \|f\|_{2h} \leq \max_{n}( r_h(E,n))^\frac{1}{2h} \|f\|_2 \end{array}$

Proof: Observe that we have

$\displaystyle \begin{array}{rcl} \|f\|_{2h} ^h &=& \big\| \big(\sum_{k\in E} a_k e^{ik\theta}\big)^h \big\|_2 \\ \\ &=& \bigg( \sum_{n\in\mathbb Z} \big| \sum_{\substack{n=n_1+\cdots+n_h\\n_1,\ldots,n_h\in E}} a_{n_1}\cdots a_{n_h}\big|^2\bigg)^\frac{1}{2}\\ \\ &\leq& \bigg( \sum_{n\in\mathbb Z} r_h(E,n) \sum_{\substack{n=n_1+\cdots+n_h\\n_1,\ldots,n_h\in E}} |a_{n_1}|^2\cdots |a_{n_h}|^2\bigg)^\frac{1}{2} \\ \\ &\leq& (\max_{n\in\mathbb Z} r_h(E,n) )^\frac{1}{2}\big(\sum_{n\in E}|a_n|^2\big)^\frac{h}{2}, \end{array}$

where we have used Cauchy-Schwartz in the first inequality. $\Box$

Lemma 3 allows us to construct ${\Lambda(p)}$-sets for ${p}$ an even integer by combinatorial means. In particular it is enough to construct sets ${E}$ such that every equation

$\displaystyle n=n_1+\cdots+n_h,$

has at most one solution (modulo permutations) with ${n_1,\ldots,n_h\in E}$. In fact we have the following proposition which is slightly more general:

Proposition 4 (Rudin) Let ${E}$ be a set of non-negative integers and let ${h>1}$ be a positive integer. If ${E}$ is a union of (a bounded number of) sets ${E_1,\ldots,E_t}$ such that for each ${i\in\{1,2,\ldots,t\}}$ the function ${r_h(E_i,n)}$ is a bounded function of ${n}$. Then ${E}$ is a ${\Lambda(2h)}$-set.

Proof: Obviously it is enough to prove the Proposition for ${t=1}$ and then use the triangle inequality. However, for ${t=1}$, the conclusion is just an application of Lemma 3. $\Box$

We will take up this issue later on, after we complete our discussion on lacunary sequences.

Proposition 4 allows to give an elementary proof of Theorem 2.

Proof of Theorem 2: Let us consider a lacunary set ${A}$ with ${n_{k+1}/n_k>h+1}$. Then for a positive integer ${h>1}$, and ${n}$ a positive integer, let us consider the equation

$\displaystyle a_1n_{k_1}+\cdots+a_m n_{k_m}=n, \ \ \ \ \ (2)$

with ${n_{k_1}>\cdots > n_{k_m}}$ in ${A}$ and positive integers ${a_j\geq 1}$ with ${a_1+\cdots+a_m=h}$. Now assume there are two different representations of ${n}$ as a sum of elements in ${A}$:

$\displaystyle \begin{array}{rcl} a_1 n_{k_1}+\cdots+a_m n_{k_m}=b_1n_{\ell_1}+\cdots+b_\tau n_{\ell_\tau}, \end{array}$

with ${a_1+\cdots+a_m=h=b_1+\cdots+b_\tau}$. Since we have assumed that the two representations are different, there will be a maximum element of ${A}$ 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

$\displaystyle \begin{array}{rcl} \gamma_1n_{\nu_1}+\cdots+\gamma_pn_{n_p}=0, \end{array}$

where ${\gamma_1\geq 1}$ and ${|\gamma_{\nu_j}|\leq h}$ for ${2\leq j \leq p}$. However this implies that

$\displaystyle \begin{array}{rcl} n_{\nu_1} & \leq & \gamma_1 n_{\nu_1}=| \gamma_2 n_{\nu_2}\cdots+\gamma_p n_{n_p}| \\ \\ &\leq & h \big(\frac{1}{\lambda}+\frac{1}{\lambda^2}\cdots+ \frac{1}{\lambda^p}\big)n_{\nu_1} \leq h\frac{n_{\nu_1}}{\lambda-1}, \end{array}$

which is impossible whenever ${\lambda>h+1}$. We conclude that for a lacunary sequence ${A}$ with lacunary constant ${\lambda>h+1}$, the representation of integers in the form (2) is unique up to permuations. we have ${r_h(A,n)\leq h!}$. However, every lacunary sequence can be written as a union of ${s\simeq \log h/\log \lambda}$ lacunary sequences ${A_1,\ldots,A_s}$ with lacunary constants ${\lambda_i>h+1}$ and ${r_h(A_i,n)\leq 1}$. Using Proposition 4 we conclude that for every ${A}$-polynomial ${f}$ we have

$\displaystyle \begin{array}{rcl} \|f\|_{2h} \lesssim_{s,h}\|f\|_2, \quad h\in\{1,2,\ldots\}. \end{array}$

In fact the implied constant can be calculated to something like ${\frac{\log h}{\log \lambda} h^\frac{1}{2}}$. $\Box$

Two more properties of lacunary sets are important in our discussion.

1.2. Sidon sets and ${\Lambda(p)}$-sets.

Lacunary sets actually satisfy a stronger property than the ${\Lambda(p)}$-property that is, they are Sidon sets:

Definition 5 Let ${E\subset \mathbb Z}$. Then ${E}$ is called a Sidon set if

$\displaystyle \begin{array}{rcl} \sum_{n\in E}|\hat f(n)|\lesssim \| f\|_\infty, \end{array}$

for all ${E}$-polynomials ${f}$.

The notion of a Sidon set is genuinely stronger than that of a ${\Lambda(p)}$-set, for all ${p<\infty}$, that is, there exist sets ${E}$ which are ${\Lambda(p)}$-sets for ${p<\infty}$ but are not Sidon sets. In [R], Rudin showed the following theorem

Theorem 6 (Rudin) Suppose that ${E\subset E}$ is a Sidon set with constant ${B}$, that is,

$\displaystyle \begin{array}{rcl} \sum_{n\in E}|\hat f(n)| \leq B \|f\|_\infty, \end{array}$

for all ${E}$-polynomials ${f}$. Then ${E}$ is a ${\Lambda(p)}$-set for all ${1. Furthermore we have that

$\displaystyle \begin{array}{rcl} \|f\|_p &\leq& B \sqrt{p} \|f\|_2, \quad 2

for all ${E}$-polynomials ${f}$

Rudin asked whether he opposite of Theorem 6, that i whether a set ${E}$ which satisfies the conclusion of Theorem 6 is necessarily a Sidon set. The answer is YES and this was proved by Pisier in [P]:

Theorem 7 (Pisier) Let ${E\subset \mathbb Z}$. Then ${E}$ is a Sidon set if and only if

$\displaystyle \begin{array}{rcl} \sup_{p>2} \frac{\|f\|_p}{\sqrt{p} \|f\|_2} <+\infty, \end{array}$

where the supremum is taken over all ${E}$-polynomials ${f}$.

It is not very hard to see that lacunary sets are actually Sidon sets. The proof can be found in [R].

2. ${\Lambda(p)}$-sets of maximal density.

An obvious fact about ${\Lambda(p)}$ set is the inclusion:

$\displaystyle 0

This is because of the definition of ${\Lambda(p)}$-sets and Lemma 4 of the previous post. A natural question is whether this inclusion is proper:

Question 8 (Rudin) Let ${1. Does there exist a ${E\subset \mathbb Z}$ which is a ${\Lambda(p)}$-set but not a ${\Lambda (q)}$-set for any ${q>p}$?

The question was originally posed by Rudin in [R]. The case ${1 is settled (in the negative) by the following theorem of Bachelis and Ebenstein [BE]:

Theorem 9 (Bachelis, Ebenstein) Let ${E\subset \mathbb Z}$. Then the set ${\{p\in(1,2):E\mbox{ is a } \Lambda(p)\mbox{-set}\}}$ is an open set.

Thus we are left with the range ${[2,\infty)}$ in Rudin’s question. Rudin himself answers the question in [R], in the special case where ${p=2h}$ is an even integer:

Theorem 10 (Rudin) For any positive integer ${h>1}$ there exist ${\Lambda(2h)}$-sets which are not ${\Lambda(2h+\epsilon)}$-sets for any ${\epsilon>0}$.

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 ${E\subset \mathbb Z}$ for which ${r_h(E,n)}$ is a bounded function of ${n}$, then Proposition 4 guarantees that ${E}$ is a ${\Lambda(2h)}$-set. In Theorem 8 of the the previous post we saw that, for ${2, a ${\Lambda(p)}$ set satisfies ${\alpha_E(N)\lesssim_p N^\frac{2}{p}}$. This means, that any ${N}$-term arithmetic progression contains at most ${N^\frac{2}{p}}$ elements of ${E}$. Based on this fact we give the following definition:

Definition 11 A ${\Lambda(p)}$-set ${E\subset \mathbb Z}$ has maximal upper density if

$\displaystyle \limsup_{N\rightarrow +\infty} \frac{\alpha_E(N)}{N^{\frac{2}{p}}}>0. \ \ \ \ \ (4)$

It is essential to notice here that a ${\Lambda(p)}$-set ${E}$ of maximal upper density cannot be a ${\Lambda(q)}$-set for any ${q>p}$ since ${\alpha_E(N)\lesssim_q N^\frac{2}{q}}$ if ${E}$ is a ${\Lambda(q)}$-set. Thus, in order to answer Rudin’s question 8 in the case where ${p=2h}$ is an even integer it is enough to construct ${\Lambda(2h)}$-sets of maximal upper density. We will now digress a bit in order to discuss the notion of ${B_h}$-set.

2.1. ${B_h}$-sets of maximal size.

For ${E\subset E}$, let us consider the equation

$\displaystyle n_1+\cdots+n_h=n,\quad n_1,\ldots,n_h\in E, \ \ \ \ \ (5)$

where ${n}$ is an integer and ${n_1\leq \cdots \leq n_h}$.

Definition 12 A set ${E\subset \mathbb Z}$ is called a ${B_h}$-sequence if for every ${n\in\mathbb Z}$, equation (5) has at most one solution such that ${n_1\leq n_2\leq \cdots \leq n_h}$.

Remark 1 ${B_2}$-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 ${B_h}$-notation to avoid ambiguity.

If ${E}$ is ${B_h}$-sequences then obviously ${r_h(E,n)\leq h!}$ which is the smallest possible value of ${r_h(E,n)}$. This interest in ${B_h}$ sequences lies here in the fact that ${B_h}$ sequences are ${\Lambda(2h)}$-sets. This is an immediate application of by Lemma 3. The following theorem of Bose and Chowla from [BC] constructs finite ${B_h}$-sets of maximal size:

Theorem 13 (Bose, Chowla) Let ${m =p^n}$ where ${p}$ is prime and ${h\geq 2}$ be a positive integer. There exist ${m}$ non-zero integers

$\displaystyle \begin{array}{rcl} d_1=1,d_2,\ldots,d_m, \end{array}$

such that the sums

$\displaystyle d_{i_1}+d_{i_2}+\cdots+d_{i_h},\quad 1\leq i_1\leq i_2 \leq \cdots \leq i_h\leq m, \ \ \ \ \ (6)$

are all distinct ${\mod (m^h-1)}$. By a suitable choice of representatives modulo ${m^h-1}$ the ${d}$‘s can be chosen to satisfy

$\displaystyle \begin{array}{rcl} 1=d_1

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 ${\Lambda(2h)}$-sets of maximal upper density

Of course the ${B_h}$-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 ${N=m^h}$ which contains ${m=N^\frac{1}{h}}$ 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 ${\Lambda(2h)}$ of maximal upper density, although we don’t claim anything about the $B_h$-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, ${N^\frac{1}{h}}$, and the dyadic pieces become arbitrarily large, the upper density of the set will be positive.

The first step is the following proposition:

Proposition 14 For any ${h\geq 2}$ and any positive integer ${N}$ there exists a ${\Lambda(2h)}$-set ${E\subset\{1,2,\ldots,N\}}$ with ${|E|\simeq N^\frac{1}{h}}$.

Proof: Fix your favorite prime ${p}$ and define the positive integer ${n}$ by ${p^n. From Theorem 13 there exists a set ${E\subset \{1,2,\ldots,(p^{n})^h-1\}}$ of size ${|E|=p^{n}}$. Since ${(p^{n})^h-1 \leq N-1}$ our set is contained in ${\{1,2,\ldots,N-1\}}$. On the other hand we have that

$\displaystyle N^\frac{1}{h} \geq |E|=p^n\geq \frac{1}{p} N^\frac{1}{h},$

that is ${|E|\simeq N^\frac{1}{h}}$. $\Box$

Corollary 15 (Bourgain) Let ${p=2h}$ where ${h> 1}$. Then there exists a ${\Lambda(2h)}$-set of maximal upper density.

Proof: Using Proposition 14 we construct for each ${N=2^{k-1}}$, ${k=1,2,\ldots,}$ a set ${E_k}$ which is contained in ${\{2^{k-1}+1,2^{k-1}+2,\ldots,2^k-1\}}$. For this, just translate the sets constructed in the Proposition by ${2^{k-1}}$. Note that each set ${E_k}$ has size ${|E_k|\simeq N^\frac{1}{h}\simeq_h 2^\frac{k}{h}}$. Now we define

$\displaystyle E:=\cup_{k=1} ^\infty E_k. \ \ \ \ \ (7)$

Observe that for ${\ell=2^k}$, the set ${E}$ has at least ${\simeq 2^\frac{k}{h}}$ terms in the arithmetic progression ${\{1,2\ldots,\ell\}}$. We conclude that ${E}$ has positive upper density. To see that ${E}$ is a ${\Lambda(2h)}$-set, let ${f}$ be an ${E}$-polynomial. Invoking the Littlewood-Paley inequalities we have for any

$\displaystyle h>1$

$\displaystyle \begin{array}{rcl} \|f \|_{2h} \lesssim_h \| S(f)\|_{2h}, \end{array}$

where ${S(f)}$ is the Littlewood-Paley square function:

$\displaystyle \begin{array}{rcl} S(f):=\bigg(\sum_{k=1} ^\infty \bigg| \sum_{2^{k-1}

Since ${f}$ is an ${E}$-polynomial and ${E\cap \{2^{k-1}+1,\ldots 2^k\}=E_k}$, we have for all ${k\geq 1}$

$\displaystyle \begin{array}{rcl} \sum_{2^{k-1}

Furthermore, since each one of the sets ${E_k}$ is a ${\Lambda(2h)}$-set with the same ${\Lambda(2h)}$-constant, we have

$\displaystyle \begin{array}{rcl} \bigg\| \sum_{2^{k-1}

We conclude that

$\displaystyle \begin{array}{rcl} \|f\|_{2h} &\lesssim_h& \bigg\|\bigg( \sum_{k=1} ^\infty \bigg| \sum_{n\in E_k } \hat f(n) e^{inx} \bigg|^2 \bigg)^\frac{1}{2} \bigg\|_{2h} \\ \\ &\lesssim_h& \bigg( \sum_{k=1} ^\infty \bigg\| \sum_{n\in E_k } \hat f(n) e^{inx} \bigg\|_{2h} ^2 \bigg)^\frac{1}{2} \\ \\ &\lesssim_h & \bigg( \sum_{k=1} ^\infty \bigg\| \sum_{n\in E_k } \hat f(n) e^{inx} \bigg\|_{2} ^2 \bigg)^\frac{1}{2}=\|f\|_2. \end{array}$

This shows that ${E}$ is a ${\Lambda(2h)}$-set and completes the proof of Corollary 15 and thus the one of Theorem 10. $\Box$

Remark 2 In [B], Bourgain extends the result of Rudin, Theorem 10, by proving that for any ${p>2}$ there exist ${\Lambda(p)}$-sets which are not ${\Lambda(p+\epsilon)}$-sets for any ${\epsilon>0}$. For this we need the analogue of Proposition 14 for any ${p>2}$. Bourgain proves this using the probabilistic arguments. In fact his proof shows that most’ subsets of ${\{1,2,\ldots,N\}}$ of size ${\sim N^\frac{2}{p}}$ have the ${\Lambda(p)}$-property.

3. References.

I'm a postdoc researcher at the Center for mathematical analysis, geometry and dynamical systems at IST, Lisbon, Portugal.
This entry was posted in math.CA, math.CO, math.NT, Mathematics, open problem, seminar notes, The Rudin (Hardy-Littlewood) Conjecture and tagged , , , , . Bookmark the permalink.

### 7 Responses to The Rudin (Hardy-Littlewood) Conjecture, Notes 2: A closer look at Λ(p)-sets.

1. Alex Iosevich says:

The last reference above should probably read: Rudin, W… instead of Walter, R…

2. Mark Lewko says:

Nice post! One very small typo: In remark 2, I think you mean that there exists a $\Lambda(p)$ set that is not a $\Lambda(p+\epsilon)$ set for $p>2$.

• Thanks for the correction Mark. Probably there are more. Also, this is a problem that I’m reading and trying to understand right now. As a result there might things in this post that are not very consistent, at least to specialists in the area. Judging from your recent article on the arxiv (with Allison Lewko) , I would guess that you understand $B_h$-sets a lot better than I do. I would ask you (if you can) to let me know about these inconsistencies as well. For example, the construction I give here is a $\Lambda(2h)$-set which is (at least in appearances) an infinite union of $B_h$-sets. Reading your paper I realize that this is probably deceiving, but at the moment I can’t really see what’s going on.

3. Mark Lewko says:

Ioannis– Thanks for the comments. The Bose-Chowla sets (glued together with the Littlewood-Paley theory) is an infinite union of $B_{h}$ sets, however it isn’t clear how one might go about showing that it isn’t a finite union of $B_{h}[G]$ sets (for any G). I haven’t thought too much about this, but it seems likely this construction is a finite union of $B_{h}[G]$ sets (you won’t have very many repeated sums between copies of each Bose-Chowla set since each copy is in a distinct dyadic interval). As you remark, in Rudin’s paper he uses the Bose-Chowla construction, but instead of gluing translates together with the Littlewood-Paley inequality, he takes unions of (very) disjoint dilations. He then shows that the resulting set is a $B_{h}[1]$ set (using that the dilations are very far apart) and hence is a $\Lambda(2h)$ set.

In general, Allison and I found that it is difficult to show a set isn’t a finite union of $B_{h}[G]$ sets (unless, say, the set is trivially too dense to be a finite union of $B_{h}[G]$). Bourgain’s constructions (from [2]) are a bit more dense than the Bose-Chowla construction. With the Bose-Chowla construction (say with h=2), if I recall correctly, you have that $\limsup |S \cap [1,N]| / N^{1/2} > 0$ (which is enough to guarantee that $S$ isn’t a $\Lambda(4+\epsilon$ set) but you don’t necessarily have that $\liminf S \cap [1,N]| / N^{1/2} > 0$. Bourgain’s construction gives you that $S \cap [1,N] >> N^{1/2}$. This is enough to allow one to conclude that his set isn’t a finite union of $B_{2}[1]$ sets by an old theorem of Erdos. It also seems likely that this is enough to imply that $S$ isn’t a finite union of $B_{2}[G]$ sets (for any G), however I don’t know how to prove this.

4. Mark. Thanks so much for taking the time and putting the effort to explain the situation! There is a subtle difference that you point out in your comment that I haven’t explained in the post (trying to keep things simple). I use a notion of ‘upper density’ exactly because you can see that the Littlewood-Paley union of the Bose-Chowla sets (say for $h=2$) satisfy $\limsup |S\cap[1,N]|/N^\frac{1}{2}>0$ but not necessarily $\liminf |S\cap[1,N]|/N^\frac{1}{2}>0$. Bourgain in “On Λ(p)-subsets of squares” proves for example that there are maximal density $\Lambda(p)$ sets contained in the squares for any $p>2$ where he uses the `lower density’, i.e. the $\liminf$ in the previous expressions. I don’t know enough about the proof of these results though to study whether these sets are or aren’t finite unions of $B_2[G]$-sets.

PS: When you refer to [2] in your comment, do you mean the same Bourgain article I cite here?

5. Mark Lewko says:

Yes, I meant the paper [B] (I’m not sure why I wrote [2]).