Explicit constructions of RIP matrices and related problems

Introduction

While most authors work with real signals and matrices, in this paper we work with complex matrices for convenience. Given a complex matrix $\Phi$ satisfying (1.1), the $2n\times 2N$ real matrix $\Phi^{\prime}$, formed by replacing each element $a+ib$ of $\Phi$ by the $2\times 2$ matrix $(\begin{smallmatrix}a&b\\ -b&a\end{smallmatrix})$, also satisfies (1.1) with the same parameters $k,\delta$.

Given $n,N,\delta$, we wish to find $n\times N$ RIP matrices of order $k$ with constant $\delta$, and with $k$ as large as possible. If the entries of $\Phi$ are independent Bernoulli random variables with values $\pm 1/\sqrt{n}$, then with high probability, $\Phi$ will have the required properties forFor convenience, we utilize the Vinogradov notation $a\ll b$, which means $a=O(b)$, and the Hardy notation $a\asymp b$, which means $b\ll a\ll b$.

See ; also for a proof based on the Johnson-Lindenstrauss lemma . The first result of similar type for these matrices is due to Kashin . See also for RIP matrices with rows randomly selected from the rows of a discrete Fourier transform matrix and for other random constructions of RIP matrices. The parameter $k$ cannot be taken larger; in fact

It is an open problem to find good explicit constructions of RIP matrices; see T. Tao’s Weblog for a discussion of the problem. We mention here that all known explicit examples of RIP matrices are based on constructions of systems of unit vectors (the columns of the matrix) with small coherence.

Matrices whose columns are unit vectors with small coherence are connected to a number of well-known problems, a few of which we describe below. Systems of vectors with small coherence are also known as spherical codes. Some other applications of matrices with small coherence may be found in .

Suppose that ${\mathbf{u}}_{1},\dots,{\mathbf{u}}_{N}$ are the columns of a matrix $\Phi$ and have coherence $\mu$. Then $\Phi$ satisfies RIP of order $k$ with constant $\delta=(k-1)\mu$.

For any $k$-sparse vector ${\mathbf{x}}$,

All explicit constructions of matrices with small coherence are based on number theory. There are many constructions producing matrices with

In particular, such examples have been constructed by Kashin , Alon, Goldreich, Håstad and Peralta , DeVore , and Nelson and Temlyakov . By Proposition 1, these matrices satisfy RIP with constant $\delta$ and order

It follows from random constructions of Erdős and Rényi for Turán’s problem (see Proposition 2 and (1.15) below) that for any $n,N$ there are vectors with coherence

By contrast, there is a universal lower bound

valid for $2\log N\leq n\leq N/2$ and all $\Phi$, due to Levenshtein (see also and ). Therefore, by estimating RIP parameters in terms of the coherence parameter we cannot construct $n\times N$ RIP matrices of order larger than $\sqrt{n}$ and constant $\delta<1$.

Using methods of additive combinatorics, we construct RIP matrices of order $k$ with $n=o(k^{2})$.

There is an effective constant $\varepsilon_{0}>0$ and an explicit number $n_{0}$ such that for any positive integers $n\geq n_{0}$ and $n\leq N\leq n^{1+\varepsilon_{0}}$, there is an explicit $n\times N$ RIP matrix of order $\lfloor n^{\frac{1}{2}+\varepsilon_{0}}\rfloor$ with constant $n^{-\varepsilon_{0}}$.

For application to sparse signal recovery, it is sufficient to take fixed $\delta<\sqrt{2}-1$ , and one needs an upper bound on $n$ in terms of $k,N$. By Theorem 1, for some $\varepsilon_{0}^{\prime}>0$, large $N$ and $N^{1/2-\varepsilon_{0}^{\prime}}\leq k\leq N^{1/2+\varepsilon_{0}^{\prime}}$, we construct explicit RIP matrices with $n\leq k^{2-\varepsilon_{0}^{\prime}}$.

The proof of Theorem 1 uses a result on additive energy of sets (Corollary 2, Theorem 4), estimates for sizes of sumsets in product sets (Theorem 5), and bounds for exponential sums over products of sets possessing special additive structure (Lemma 10).

We now return to the problem of constructing matrices with small coherence. By (1.6), the bound (1.4) cannot be improved if $\log n\gg\log N$, but there is a gap between bounds (1.6) and (1.4) when $\log n=o(\log N)$. For example, (1.4) is nontrivial only for $n\gg(\log N/\log\log N)^{2}$. Of particular interest in coding theory is the range $n=O(\log^{C}N)$ for fixed $C$, where there have been some improvements made to (1.4). A construction obtained by concatenating algebraic-geometric codes with Hadamard codes (see e.g. [23, Corollary 3] and Section 3 of ) produces matrices with coherence

which is nontrivial for $n\gg\log N$, and is better than (1.4) when $\log N\ll n\ll(\frac{\log N}{\log\log N})^{4}$. In the range $(\frac{\log N}{\log\log N})^{5/2}\ll n\ll(\frac{\log N}{\log\log N})^{5}$, Ben-Aroya and Ta-Shma improved both (1.4) and (1.7) by constructing binary codes (vectors with entries $\pm 1/\sqrt{n}$) with coherence

In this paper, we introduce very elementary constructions of matrices with coherence which matches (up to a $\log\log N$ factor) the bound (1.7). Our constructions, which are based on a method of Ajtai, Iwaniec, Komlós, Pintz and Szemerédi , have the added utility of applying to Turán’s power-sum problem and to the problem of finding thin sets with small Fourier coefficients. For the last two problems, our construction gives better estimates than existing explicit constructions in certain ranges of the parameters.

Roughly speaking, a set with small Fourier coefficients can be used to construct a set of numbers for Turán’s problem, and a set of numbers in Turán’s problem can be used to produce a matrix with small coherence. This is made precise below.

We next describe the problem of explicitly constructing thin sets with small Fourier coefficients. If $N$ is a positive integer and $S$ is a set (or multiset) of residues modulo $N$, we let

Given $N$, we wish to find a small set $S$ with $|f_{S}|$ also small.

Turán’s problem concerns the estimation of the function

where $n,N$ are positive integers. There is a vast literature related to Turán’s problem; see, e.g., , , (chapter 5), , .

If $S=\{t_{1},\dots,t_{n}\}$ is a multiset of integers modulo $N$ and $z_{j}=e^{2\pi it_{j}/N}$ for $1\leq j\leq n$, we see that

We also have the following easy connection between Turán’s problem and coherence.

Given any vector ${\mathbf{z}}=(z_{1},\ldots,z_{n})$ with $|z_{j}|=1$ for all $j$, the coherence $\mu$ of the $n\times N$ matrix with the columns

satisfies $\mu=n^{-1}M_{N-1}({\mathbf{z}})$.

Combining (1.9) and Proposition 2, for any multiset $S$ of residues modulo $N$, the vectors (1.10) satisfy

An application of Dirichlet’s approximation theorem shows that a set $S$ with $|S|<\log N$ must have $|f_{S}|\gg 1$. In , sets which are not much larger are explicitly constructed so that $|f_{S}|$ is small. Specifically, by [1, (1),(2)], for each primeA corresponding result when $N$ is composite is given in . $N$ there is a set $S$ with $|S|=O(\log N(\log^{*}N)^{13\log^{*}N})$ and

where $\log^{*}N$ is the integer $k$ so that the $k$-th iterate of the logarithm of $N$ lies in $[1,e)$. The proof uses an iterative procedure. By modifying this procedure, and truncating after two steps, we prove the following. To state our results, for brevity write

For sufficiently large prime $N$ and $\mu$ such that

a set $S$ of residues modulo $N$ can be explicitly constructed so that

The method from , if applied without modification (with two iterations of the basic lemma), produces a conclusion in Theorem 2 with

The bound on $|S|$ in Theorem 2 is better than (1.12) for $\mu\gg L_{1}^{-1/2}L_{2}$.

Together, the construction for Theorem 2 and (1.9) give explicit sets ${\mathbf{z}}$ for Turán’s problem. By further modifying the construction, we can do better.

For sufficiently large positive integer $N$ and $\mu$ such that

a multiset ${\mathbf{z}}=\{z_{1},\dots,z_{n}\}$ such that $|z_{1}|=\dots=|z_{n}|=1$, can be explicitly constructed so that

To put Theorem 3 in context, we briefly review what is known about $T(n,N)$. P. Erdős and A. Rényi used probabilistic methods to prove an upper estimate

Using the character sum bound of Katz , J. Andersson gave explicit examples of sets ${\mathbf{z}}$ which give

One can see that (1.16) supersedes (1.15) for $\log N\ll\log^{2}n$. Also, combining (1.16) with Proposition 2 provides yet another construction of matrices with coherence satisfying (1.4). On the other hand, by (1.6) and Proposition 2, we have the lower estimate

By comparison, the constructions in Theorem 3 are better than (1.16) in the range $n\ll L_{1}^{4}/L_{2}^{8}$, that is, throughout the range (1.14) (our constructions require $n$ to be prime, however).

The constructions in Theorem 3 also produce, by Proposition 2, explicit examples of matrices with coherence

which is close to the bound (1.7). By Proposition 1, these matrices satisfy RIP with constant $\delta$ and order

We prove Theorem 1 in Sections 2–6, Theorem 2 in Section 7 and Theorem 3 in Section 8.

Construction of the matrix in Theorem 1

We fix a large even number $m$. A value of $m$ can be specified; it depends on the constant $c_{0}$ in an estimate from additive combinatorics (Proposition 3, Section 4). Also, the value $m$ can be reduced if one proves a better version of the Balog–Szemerédi–Gowers lemma (Lemma 6 below).

and the sets $\curly A,\curly B$ will be defined below. Notice that the matrix $\Phi_{p}$ can be extended to a $n\times N$ matrix $\Phi$ by adding $n-p$ zero rows. Clearly, the matrices $\Phi_{p}$ and $\Phi$ have the same RIP parameters.

We notice that all elements of $\curly B$ are at most $p/2$, and

For $n\leq N\leq n^{1+\beta/2}$, take $\Phi$ to be the matrix formed by the first $N$ columns of $\Phi_{p}$, padded with $n-p$ rows of zeros.

In the next four sections, we show that $\Phi$ has the required properties for Theorem 1. First, in Section 3, we show that in (1.1) we need only consider vectors ${\mathbf{x}}$ whose components are 0 or 1 (emphflat vectors). We prove the following.

Let $k\geq 2^{10}$ and $s$ be a positive integer. Assume that the coherence parameter of the matrix $\Phi$ is $\mu\leq 1/k$. Also, assume that for some $\delta\geq 0$ and any disjoint $J_{1},J_{2}\subset\{1,\dots,N\}$ with $|J_{1}|\leq k,|J_{2}|\leq k$ we have

Then $\Phi$ satisfies the RIP of order $2sk$ with constant $44s\sqrt{\delta}\log k$.

and, for $a\in\curly A$ and $a_{1},\dots,a_{2m}\in\curly A\setminus\{a\}$,

with some $\gamma>0$, where $E(S,S)$ is the number of solutions of $s_{1}+s_{2}=s_{3}+s_{4}$ with each $s_{i}\in S$.

holds where $\varepsilon_{1}=c_{0}\gamma/20-43\alpha/m$.

The proof of Lemma 2 is quite involved, and will be handled in three subsequent sections. We next demonstate how Theorem 1 may be deduced from it.

We first prove (2.4) for the specific set $\curly A$ defined in (2.1), provided that $p>(2m)^{8m^{2}}$ (and thus $L\geq 2m$). We have to show that for any distinct $x,x_{1}\dots,x_{n}\in\{1,\dots,L\}$ and any nonzero integers $\lambda_{1},\dots,\lambda_{n}$ such that $n\geq 2m$ and $|\lambda_{1}|+\cdots+|\lambda_{n}|\leq 2m,$ the sum

All summands in the right-hand side of (2.6) but the first one are divisible by $x+x_{1}+U$. For the first summand we have

This shows that $V_{1}\neq 0\;(\bmod\;x_{0}+x_{1}+U)$. Therefore, $V\neq 0$. By assumption, $p\nmid D_{1}$, and

Condition (2.5) is satisfied due to Corollary 4 of Section 5 with $\gamma=\beta/50$. If $m>86000c_{0}^{-1}$ then Lemma 2 gives a nontrivial estimate with $\varepsilon_{1}>0$. Thus, $\Phi_{p}$ satisfies the conditions of Corollary 1 with $k=\lfloor\sqrt{p}\rfloor\geq\sqrt{n/2}$ and $\delta=p^{-\varepsilon_{1}}\leq(n/2)^{-\varepsilon_{1}}$ (using $p\geq 0.9n$ for large $n$, which follows from the prime number theorem). Let $\varepsilon_{0}=\varepsilon_{1}/5$. Let $n\leq N\leq n^{1+\varepsilon_{0}}$, and let $\Phi$ be the $n\times N$ matrix formed by taking the first $N$ columns of $\Phi_{p}$, then adding $n-p$ rows of zeros. Clearly, $\Phi$ satisfies the conditions of Corollary 1 with the same parameters as $\Phi_{p}$. By Lemma 1 with $s=\lfloor p^{\varepsilon_{1}/4}\rfloor$, Theorem 1 follows.

In Section 4 we introduce some notation and recall standard estimates in additive combinatorics, which will be applied to subsets of $\curly B$. Section 5 is devoted to the sumset theory of $\curly B$, from which we deduce (2.5). The completion of the proof of Lemma 2 is in Section 6. We give some preliminaries here.

where the summands with $a_{1}=a_{2}$ are excluded from the summation. We next break $\Omega_{1},\Omega_{2}$ into balanced sets. For $a\in\curly A$ and $i=1,2$, let

whenever $M_{1},M_{2}$ are powers of two and, for $i=1,2$ and for any $a_{i}\in A_{i}$,

Indeed, there are $O(\log^{2}p)$ choices for $M_{1},M_{2}$. To prove the cancellation in (2.8), we basically split into two cases: (i) some $B^{\prime}=\Omega_{i}(a_{j})$ has additive structure (that is, $E(B^{\prime},B^{\prime})$ is large), where the cancellation comes from the sum over $b_{1},b_{2}$ (with $a_{1},a_{2}$ fixed), and (ii) when $B^{\prime}$ does not have additive structure, in which case one gets dispersion of the phases from the dilation weights $1/(a_{1}-a_{2})$ (taking a large moment and using (2.4)). Incidentally, oscillations of the factor $(\frac{a_{1}-a_{2}}{p})$ play no role in the argument.

The Flat-RIP property

Let ${\mathbf{u}}_{1},\ldots,{\mathbf{u}}_{N}$ be the columns of an $n\times N$ matrix $\Phi$. Suppose that for every $j$, $\|{\mathbf{u}}_{j}\|_{2}=1$. We say that $\Phi$ satisfies the flat RIP of order $k$ with constant $\delta$ if for any disjoint $J_{1},J_{2}\subset\{1,\dots,N\}$ with $|J_{1}|\leq k,|J_{2}|\leq k$ we have

For technical reasons, it is more convenient to work with the flat-RIP than with the RIP. However, flat-RIP implies RIP with an increase in $\delta$. The flat-RIP property is closely related to the property that (1.1) holds for any ${\mathbf{x}}$ with entries which are zero or one and at most $k$ ones (see the calculation at the end of this section).

Let $k\geq 2^{10}$ and $s$ be a positive integer. Suppose that $\Phi$ satisfies flat-RIP of order $k$ with constant $\delta$. Then $\Phi$ satisfies RIP of order $2sk$ with constant $44s\delta\log k$.

First, by a convexity-type argument and our assumption,

provided that $|J_{1}|\leq k,|J_{2}|\leq k$, $0\leq x_{j},y_{j}\leq 1$ for all $j$. Next, suppose $|J_{1}|\leq k,|J_{2}|\leq k$, and $0\leq x_{j},y_{j}$ for all $j$. Without loss of generality assume that $\|{\mathbf{x}}\|_{2}=\|{\mathbf{y}}\|_{2}=1$, where $\|\cdot\|_{2}$ denotes the $l_{2}$ norm. For a positive integer $\nu$ let

Applying (3.2) to sets $J_{1,\nu},J_{2,\nu}$, we get

Let $t=\lfloor 3+\log k/(2\log 2)\rfloor$. By the Cauchy–Schwarz inequality we infer that

For the next step, suppose $x_{j},y_{j}$ take arbitrary complex values, $|J_{1}|\leq sk$ and $|J_{2}|\leq sk$. We partition $J_{1}$ and $J_{2}$ into $s$ subsets of cardinality at most $k$ each: $J_{1}=\cup_{\mu=1}^{s}J_{1,\mu}$, $J_{2}=\cup_{\mu=1}^{s}J_{2,\mu}.$ Next, for any $j$ we have

where $x_{j,\nu},y_{j,\nu}$ are non-negative. By (3.4) and the Cauchy–Schwarz inequality,

For any disjoint $J_{1},J_{2}\subset\{1,\dots,N\}$ with $|J_{1}|\leq k,|J_{2}|\leq k$ we have

Using the assumptions of the Lemma 1 directly rather than reducing it to Lemma 3, one can get a better constant for RIP; However, we do not need a stronger version of the corollary for our purposes.

Some definitions and results from additive combinatorics

For an (additive) abelian group $G$ we define the sum and the difference of subsets $A,B\subset G$:

We will use the following lemma which is a particular case of Plünecke – Ruzsa estimates (, Exercise 6.5.15).

For any nonempty set $A\subset G$ we have $|A+A|\leq|A-A|^{2}/|A|$.

If $A,B\subset G$, we define the (additive) energy $E(A,B)$ of the sets $A$ and $B$ as the number of solutions of the equation

Next, let $F\subset A\times B$. The $F$-restricted sum of $A$ and $B$ is defined as

Trivially $E(A,A)\leq|A|^{3}.$ If $E(A,A)$ is close to $|A|^{3}$ then $A$ must have a special additive structure.

(, Lemma 2.30) If $E(A,A)\geq|A|^{3}/K$ then there exists $F\subset A\times A$ such that $|F|\geq|A|^{2}/(2K)$ and $|A+_{F}A|\leq 2K|A|$.

The following lemma is a version of the Balog–Szemerédi–Gowers lemma which plays a very important role in additive combinatorics.

If $F\subset A\times A$, $|F|\geq|A|^{2}/L$ and $|A+_{F}A|\leq L|A|$. Then there exists a set $A^{\prime}\subset A$ such that $|A^{\prime}|\geq|A|/(10L)$ and $|A^{\prime}-A^{\prime}|\leq 10^{4}L^{9}|A|$.

Combining Lemma 5 and Lemma 6 gives the following.

If $E(A,A)\geq|A|^{3}/K$ then there exists a set $A^{\prime}\subset A$ such that $|A^{\prime}|\geq|A|/(20K)$ and $|A^{\prime}-A^{\prime}|\leq 10^{7}K^{9}|A|$.

By $1_{A}$ we denote the indicator function of the set $A$. With this notation, we have

An explicit version of Proposition 3, with $c_{0}=1/10430$, is given in .

Note that if $|A|<|B|$, we may decompose $B$ as a disjoint union of at most $2|B|/|A|$ sets $B_{j}$ with $|A|/2<|B_{j}|\leq|A|$ and apply (4.2) for each $B_{j}$. Hence

Applying the Cauchy–Schwarz inequality we get

It would be interesting to find best possible value for $c_{0}$ in Proposition 3. The example $A=B=\{1,\dots,[\sqrt{p}]\}$ shows that $c_{0}<1$.

Put $\lambda(p)=0$, and let $b$ be a permutation of $\{1,\ldots,p\}$ such that $\lambda(b_{1})\geq\dots\geq\lambda(b_{p})=0$. By (4.3), for $1\leq j\leq p-1$ we have $S_{j}\ll G_{j}$, where

Denote $u_{0}=\|\lambda\|_{2}^{-2}$. Notice that $1\leq u_{0}\leq p$ since $\|\lambda\|_{1}=1$. Separately considering $j\leq u_{0}$ and $j>u_{0}$ and using the Cauchy–Schwarz inequality, we get

Using a parameter $\Delta\geq 1$ which will be specified later we define the sets

Decompose $\mu=\mu_{-}+\mu_{0}+\mu_{+}$ where

The contribution to the sum in the theorem from $\mu_{-}$ and $\mu_{+}$ is negligible. First,

Using Young’s inequality (cf , Theorem 4.8), we find that

So, it suffices to estimate the contribution of $\mu_{0}$. We have

Hence, $|A|\leq\|\mu\|_{2}^{-2}\Delta^{2}$. Now we can use Corollary 2:

Combining the last inequality with (4.6) – (4.8) we get

Taking $\Delta=\max(1,S^{1/7})$ completes the proof of the theorem. ∎

A sumset estimate in product sets

The main result of this section is the following.

Then for any subsets $A,B\subset\curly C$ we have

Observe that for $A=B=\curly C$ we have $|A+B|=|A|^{\tau^{\prime}}|B|^{\tau^{\prime}}$ where

By Theorem 5, $\tau\leq\tau^{\prime}$. On the other hand, $\tau>1/2$. If $M\to\infty$ then

So, the asymptotic behavior of $2\tau_{M}-1$ as $M\to\infty$ is sharp. Likely, inequality (5.1) holds with $\tau=\tau^{\prime}$. This was proved in the case $M=2$ by Woodall .

For positive integers $K,L$ we define an $UR-$path as a sequence of pairs of integers $\curly P=((i_{1},j_{1})=(0,0),\ldots,(i_{K+L-1},j_{K+L-1})=(K-1,L-1))$ such that for any $n$ either $i_{n+1}=i_{n}+1,j_{n+1}=j_{n}$, or $i_{n+1}=i_{n},j_{n+1}=j_{n}+1$.

Let $KL\leq M^{2}$, $u_{0}\geq\dots\geq u_{K-1}\geq 0$, $v_{0}\geq\dots\geq v_{L-1}\geq 0$, $\tau=\tau_{M}$. Then there exists an $UR-$path $\curly P$ such that

We proceed by induction on $K+L$. For $K=1$ or $L=1$ the assertion is obvious. We prove it for $K,L$ with $\min(K,L)\geq 2$, $KL\leq M^{2}$ supposing that it holds for $(K,L)$ replaced by $(K-1,L)$ and $(K,L-1)$. Without loss of generality we assume that

By the induction supposition, there exists an $UR-$path $\curly P$ such that $i_{1}=1,j_{1}=0$ and

Similarly, $S\geq(u_{0}v_{0})^{\tau}+(1-v_{0})^{\tau}.$ Thus, $S\geq w^{2\tau}+(1-w)^{\tau}$ where

The function $f(x)=x^{2\tau}+(1-x)^{\tau}-1$ has negative third derivative on $$and$f(0)=f(1/M)=f(1)=0$. By Rolle’s theorem,$f$has no other zeros on$$, and since$f(u)>0$for$u$close to 1,$f(x)\geq 0$for$1/M\leq x\leq 1$. Therefore,$f(w)\geq 0$ as desired. ∎

We will need Lemma 7 only for $K=L=M$ (although for the proof it was convenient to have varying $K,L$).

Let $U_{0},\dots,U_{M-1}$, $V_{0},\dots,V_{M-1}$ be non-negative numbers, and $\tau=\tau_{M}$. Then

Lemma 8 has some similarity with inequality (2.1) from .

We order $U_{0},\dots,U_{M-1}$ and $V_{0},\dots,V_{M-1}$ in the descending order $u_{0}\geq\dots\geq u_{M-1}$ and $v_{0}\geq\dots\geq v_{M-1}$, respectively, where for some permutations $\pi$ and $\sigma$ of the set $\{0,\dots,M-1\}$ we have $u_{i}=U_{\pi_{i}},v_{j}=V_{\sigma_{j}}$. We consider an arbitrary $UR-$path $\curly P$ with $K=L=M$. Since $|\{\pi_{i_{1}},\dots,\pi_{i_{n}}\}|=i_{n}+1$ and $|\{\sigma_{j_{1}},\dots,\sigma_{j_{n}}\}|=j_{n}+1$,

Consequently, there is a permutation $\psi$ of $\{0,\dots,2M-2\}$ so that

Thus, for some $\kappa_{0}\in\{\pi_{i_{1}},\dots,\pi_{i_{n}}\}$ and $\lambda_{0}\in\{\sigma_{j_{1}},\dots,\sigma_{j_{n}}\}$ we have

But $U_{\kappa_{0}}=u_{i}$ for some $i\in\{i_{1},\dots,i_{n}\}$. Recalling that $i_{1}\leq i_{2}\leq\dots$ and $u_{1}\geq u_{2}\geq\dots$ we obtain $U_{\kappa_{0}}\geq u_{i_{n}}$. Similarly, $V_{\lambda_{0}}\geq v_{j_{n}}$. Therefore,

Now we are ready to prove Theorem 5. We proceed by induction on $r$. For $r=0$ the set $\curly C_{M,r}$ is a singleton, and there is nothing to prove. Now suppose that the assertion holds for $r$ replaced by $r-1\geq 0$. We consider arbitrary subsets $A,B\subset\curly C=\curly C_{M,r}$. For $i=0,\dots,M-1$ we denote

Let $D=A+B$. For $n=0,\dots,2M-2$ we denote

By the induction supposition, $|A_{i}+B_{j}|\geq(|A_{i}||B_{j}|)^{\tau}$. Hence,

The set $-B$ is a translate of some set $B^{\prime}\subset\curly B$, and $\curly B$ is Freiman isomorphic to $\curly C_{M,r}$. Hence, for any $B\subset\curly B$ we have $|B-B|=|B+B^{\prime}|\geq|B|^{2\tau_{M}}$. If $|B|>p^{1/4}$ then $|B-B|\geq|p|^{(2\tau_{M}-1)/4}|B|$. By (5.2) and a short calculation using $M\geq 2^{15}$, $p^{(2\tau_{M}-1)/4}\geq p^{\beta/5}$. ∎

Let $E(S,S)=|S|^{3}/K$. By Corollary 1, there is a set $B\subset S$ such that $|B|\geq|S|/(20K)$ and $|B-B|\leq 10^{7}K^{9}|S|$. If $K\leq p^{\beta/50}<p^{1/24}$ and $p$ is so large that $10^{7}\leq p^{\beta/50}$ then we get contradiction with Corollary 3. ∎

The proof of Lemma 2

We may assume $\varepsilon_{1}>0$, otherwise there is nothing to prove. Adopt the notation ($A_{i},M_{i},\Omega_{i}(a)$) from Section 2. If $|A_{1}|M_{1}<p^{1/2-\gamma/10}$, then by (2.9), $|S(A_{1},A_{2})|\leq 2p^{1-\gamma/10}$ and (2.8) holds (recall that $c_{0}<1$, hence $\varepsilon_{1}<\gamma/20$). Thus, we can assume that $|A_{1}|M_{1}\geq p^{1/2-\gamma/10}$, which implies, by (2.3), that

Let $W$ denote the double sum over $b_{1},b_{2}$. By the Cauchy–Schwarz inequality,

Another application of the Cauchy–Schwarz inequality gives

A third application of the Cauchy–Schwarz inequality, followed by Parseval’s identity yields a well-known inequality (cf. , Problem 14(a) for Chapter 6)

By (6.1), $|\Omega_{i}(a_{i})|\geq p^{1/3}$, and by Lemma 9 and (2.5),

Thus, if $|A_{1}|<p^{\gamma/2}$ and $|A_{2}|<p^{\gamma/2}$, then $|S(A_{1},A_{2})|\leq 4p^{1-\gamma/8}$ and (2.8) follows. Otherwise, without loss of generality we may assume that

The following lemma gives the necessary estimates to complete the proof of Lemma 2. For $a_{1}\in A_{1}$, set

The proof of Lemma 10 applies to more general sums, e.g. in $T(A,B)$ one may replace the Legendre symbol $(\frac{a_{1}-a_{2}}{p})$ with arbitrary complex numbers $\psi(a_{1},a_{2})$ with modulus $\leq 1$, and one may replace $\frac{1}{a_{1}-a_{2}}$ with different quantities $g(a_{1},a_{2})$ having the dissociative property (the analog of (2.4) holds).

Postponing the proof of Lemma 10, we show first how to deduce Lemma 2.

We take a maximal subset $B_{0}\subset\Omega_{1}(a_{1})$ so that (6.5) holds for $B=B_{0}$. Denote $B_{1}=\Omega_{1}(a_{1})\setminus B_{0}$. By Lemma 9, (2.9), and (2.3) we have

Now assume that (6.6) does not hold. By (2.9), we get

Applying now Corollary 1 and (2.9) we obtain the existence of a set $B_{1}^{\prime}\subset B_{1}$ such that

and $|B_{1}^{\prime}-B_{1}^{\prime}|\leq 10^{7}p^{27\alpha}|B_{1}|\leq p^{28\alpha}|B_{1}|$. Using Lemma 10 we get inequality (6.5) for $B=B_{1}^{\prime}$. Therefore, (6.5) is also satisfied for $B=B_{0}\cup B_{1}^{\prime}$, contradicting the choice of $B_{0}$.

Thus, we have shown that (6.6) must hold. Using (6.5) for $B=B_{0}$ and (6.7) we get

Summing on $a_{1}\in A_{1}$ and using (2.3) and (2.9), we obtain

Hence, for some complex numbers $\varepsilon_{y,\xi}$ of modulus $\leq 1$,

Then $|\zeta^{\prime}(z)|\leq\zeta(z)$. By Hölder’s inequality,

As $\zeta(z)=\sum_{\xi}1_{B-B}(z/\xi)$, we have by the triangle inequality,

Define the probability measure $\lambda_{1}$ by

with $a^{(1)},\dots,a^{(2m)}\in A_{2}$. By (2.4), this has only trivial solutions and thus

On the other hand, it follows from (6.3) and (6.4) that

Subsequent application of (6.9), (6.10) and (6.11) gives

By (6.3), $p^{1/4}\leq|B|^{1/2}p^{3\alpha}$. Recalling $\gamma\leq\alpha$, (2.9), (6.2) and (6.4), we conclude that

Plugging the last estimate into (6.8), we get

Thin sets with small Fourier coefficients

Denote by $(a^{-1})_{m}$ the inverse of $a$ modulo $m$. It is easy to see for relatively prime integers $a,b$ that

Let $P\geq 4$, $S\geq 2$, and $R$ be a positive integer. Suppose that for every prime $p\leq P$, $S_{p}$ is a set of integers in $(-p/2,p/2)$. Suppose $q$ is a prime satisfying $q\geq RP^{2}$. Then the numbers $r+s^{(p)}(p^{-1})_{q}$, where $1\leq r\leq R,P/2<p\leq P,s^{(p)}\in S_{p}$, are distinct modulo $q$.

Multiplying both sides by $p_{1}p_{2}$ gives

The right side is divisible by $p_{1}p_{2}$ and the absolute value of the right side is $<p_{1}p_{2}$, hence both sides are zero, $r_{1}=r_{2}$, $p_{1}=p_{2}$ and $s_{1}^{(p_{1})}=s_{2}^{(p_{2})}$. ∎

For brevity, we write $e(z)$ for $e^{2\pi iz}$ is what follows.

Let $P\geq 4$, $S\geq 2$, and $R$ be a positive integer. Suppose that for every prime $p\in(P/2,P]$, $S_{p}$ is a multiset of integers in $(-p/2,p/2)$, $|S_{p}|=S$ and $|f_{S_{p}}|\leq\varepsilon$. Suppose $q$ is a prime satisfying $q>P$. Then the multiset

where $V$ is the number of primes in $(P/2,P]$.

Since $|f_{T}(k)|=|f_{T}(q-k)|$, we may assume without loss of generality that $1\leq k<q/2$. We have

If $k\geq q/3$, we use the trivial bound $|B(p,k)|\leq S$ and conclude

Now assume $k\leq q/3$. If $p|k$, then $|B(p,k)|\leq S$. When $p\nmid k$, by (7.1),

Since there are $\leq\frac{\log k}{\log(P/2)}$ primes $p|k$ with $p>P/2$, we have

Combining our estimates for $|A(k)|$ and $|B(p,k)|$, we arrive at

For a specific choice of $S_{p}$, the inequality (7.2) can be strengthened.

Let $P\geq 4$ and $R$ be a positive integer. For every prime $p\in(P/2,P]$ denote by $S_{p}$ the set of all integers in $(-p/2,p/2)$. Suppose $q$ is a prime satisfying $q>P$. Then the multiset

where $V$ is the number of primes in $(P/2,P]$ and $W=4\frac{\log(q/2)}{\log(P/2)}$.

Again, we may assume without loss of generality that $1\leq k<q/2$. We use notation from the proof of Lemma 12. If $p|k$, we use the trivial estimate $|B(p,k)|\leq|S_{p}|\leq P$. Now there are $\leq\frac{\log(q/2)}{\log(P/2)}$ primes $p|k$ with $p>P/2$. When $p\nmid k$, by (7.1),

where it is assumed that $k(q^{-1})_{p}\in(-p/2,p/2)$. For $a=1,\dots,[(P-1)/2]$ we denote

Taking into account that $|e(u)-1|^{-1}\leq 1/(4u)$ for $u\in(0,1/2]$ we get

If $k(q^{-1})_{p}=\pm a$ then $k\pm aq$ is divisible by $p$. But $|k\pm aq|\leq Pq/2$. Therefore, the number of prime divisors $p>P/2$ of any number $k\pm aq$ is at most $\frac{\log q}{\log P/2}+1$ and for any $a$ we get

Combining our estimates for $|A(k)|$ and $|B(p,k)|$ ((7.3) and (7.5)), we arrive at

Applying Lemma 12 for all primes $q$ in a dyadic interval, we can then feed these multisets $T=T_{q}$ back into the lemma and iterate.

Using explicit estimates for counts of prime numbers , we have

For $P\geq 250$, there are more than $\frac{2P}{5\log(P/2)}$ primes in $(P/2,P]$. For any $P>2$, there are at most $0.76P/\log P$ primes in $(P/2,P]$.

Using Proposition 4 we obtain a more convenient version of Lemma 13.

Let $P\geq 250$. For every prime $p\in(P/2,P]$ denote by $S_{p}$ the set of all nonzero integers in $(-p/2,p/2)$. Suppose $q$ is a prime satisfying $q>P$ and suppose $R\geq 1+\log(1+0.26P/\log(2q))/2$ is a positive integer. Then the multiset

We use the notation of Lemma 13. By Proposition 4 we have

On the other hand, using Proposition 4 again we get

Now the inequality (7.6) follows from (7.7) and (7.4). ∎

Using just one iteration one can get the following effective result on thin sets with small Fourier coefficients, of nearly the same strength as (1.12).

For sufficiently large prime $N$ and $\mu$ such that $N^{-1/2}\log^{2}N\leq\mu<1$ there is a set $T$ of residues modulo $N$ so that

Clearly, $R\ll 1+\log(1/\mu)$. Let $T$ be the multiset constructed in Lemma 14. We have $|f_{T}|\leq\mu$. By Lemma 11, $T$ is a set. Moreover,

We choose real parameters $P_{0}$, $P_{1}$ and positive integers $R_{0}$, $R_{1}$ so that

For $P_{0}/2<p\leq P_{0}$, let $S_{p}$ be the set of integers in $(-p/2,p/2)$. By Lemmas 11, 14 and (7.8), for each prime $q\in(P_{1}/2,P_{1}]$, there is a set $T=S_{q}$ of residues modulo $q$ such that

By an application of Lemmas 11 and 12 with $P=P_{1}$, $\varepsilon=\varepsilon_{1}$, $q=N$, and $S=R_{0}\sum_{P_{0}/2<p\leq P_{0}}p$, together with (7.9), there is a set $T$ of residues modulo $N$ so that

so that (7.9) follows immediately. The condition (1.13) implies (7.8) for large enough $N$. ∎

Theorem 2 supersedes Corollary 5 for $\mu\gg L_{1}^{-1/2}L_{2}^{1/2}$.

An explicit construction for Turán’s problem

We follow the proof of Theorem 2 and Lemma 12. We choose real parameters $P_{0}$, $P_{1}$ and a positive integer $R_{0}$, so that

For $P_{0}/2<p\leq P_{0}$, let $S_{p}$ be the set of integers in $(-p/2,p/2)$. By Lemma 14 and (8.1), for each prime $q\in(P_{1}/2,P_{1}]$, there is a multiset $T=S_{q}$ of residues modulo $q$ such that

We have $|S_{q}|=S$ for all $q$, where $S=R_{0}\sum_{P_{0}/2<p\leq P_{0}}p$. Now define a multiset $\{z_{1},\dots,z_{n}\}$ as a union of multisets $\{e(s/q):s\in S_{q},q\in(P_{1}/2,P_{1}]\}$. We have, for $1\leq k\leq N$,

If $q|k$, then $B(q,k)=S$. When $q\nmid k$, by (8.3), $|B(q,k)|\leq\varepsilon_{1}S$. Therefore,

The sum over $q|k$ is estimated at the same way as in Lemma 12:

Combining (8.4), (8.5) and using Proposition 4 we arrive at

as required. Moreover, by Proposition 4 we have

Now we take $R_{0},P_{0},P_{1}$ the same as in the proof of Theorem 2 so that (8.2) follows immediately. The condition (1.14) implies (8.1) for large enough $N$. ∎

As in , one can construct thin sets $T$ modulo $N$ with $|T|=o(L_{1}L_{2})$ and $|f_{T}|$ small, by iterating Lemma 12. Roughly speaking, applying Lemma 14 followed by $r$ iterations of Lemma 12 produces sets $T$, with small $|f_{T}|$, as small as $|T|=O(L_{1}L_{r+1})$, where $L_{j}$ is the $j$-th iterate of the logarithm of $N$. We omit the details.

Acknowledgments. The authors thank Ronald DeVore, Zeev Dvir, Venkatesan Guruswami, Piotr Indyk, Sina Jafarpour, Boris Kashin, Howard Karloff, Imre Leader, Igor Shparlinski and Avi Wigderson for helpful conversations.

References