Completeness of nonharmonic Fourier Series I have the following question:
The Exponential System $(\exp(2\pi i n \cdot ))_{n\in \mathbb{Z}}$ constitutes an orthonormal basis of $L^2([-1/2,1/2])$. 
Thus, certainly the oversampled system $\Phi:=(\exp(\pi i n \cdot ))_{n\in \mathbb{Z}}$ is complete in $L^2([-1/2,1/2])$. 
Suppose that $S\subset \mathbb{Z}$ be arbitrary and let $S^c:=\mathbb{Z}\setminus S$. Define $\Phi^S:=(\exp(\pi i n \cdot ))_{n\in S}$ and $\Phi^{S^c}:=(\exp(\pi i n \cdot ))_{n\in S^c}$.
I want to show the following:
For every $S\subset \mathbb{Z}$, at least one of the systems $\Phi^S$, $\Phi^{S^c}$ is complete in $L^2([-1/2,1/2])$ (meaning that the orthogonal complement of its span is trivial).  
Can someone help me with this?
EDIT: I can prove the statement using complex variables techniques but would very much apprechiate a more elementary proof.
 A: This is closely related to the so called Muntz-Szasz phenomenon. Suppose we are given an increasing sequence of positive real numbers
$$ (R):\;\; 0 <r_0<r_1<\cdots $$
We denote by $C_R([0,1])$ the vector subspace of $C([0,1])$   spanned by the "monomials'' $x^{r_k}$, $k\geq 0$.   Then the Muntz-Szasz theorem says that  $C_R([0,1])$ is dense in $C([0,1])$ if and only if
$$\sum_{k=0}^\infty \frac{1}{r_k}=\infty.\tag{1} $$
Intuitively, the condition (1)   says that   the set $R$  has to be   "dense enough".    For example, the set 
$$ \bigl\lbrace 2^k;k\geq 0\bigr\rbrace $$   is "too rare", and there are  "too few'' monomials to span a dense subset.
The nicest presentation of this theorem that I have seen is in W. Feller's  paper 

On Muntz's theorem and completely monotone functions, Amer. Math. Monthly, vol. 75(1968), 342-350.

His proof is based on the  following simple principle: A subset $\mathscr{F}\subset C([0,1])$ is dense in $C([0,1])$ if and only if  the only finite Borel measure  $\mu$ on $[0,1]$ such  that
$$\int_0^1 f(x) \mu(dx) =0,\;\;\forall  f\in\mathscr{F}, $$
is the trivial measure.
It looks to me that you need to answer the following question: suppose we are given a subset $\newcommand{\bZ}{\mathbb{Z}}$ $S \subset \bZ$ such that $0\in\bZ$ and $S$ is symmetric  i.e., $n\in S$ iff $-n\in S$.   Describe conditions on $S$ implying  the the subset of $C^0(S^1)$ spanned by  the monomials $z%s$, $s\in S$ is dense  in $C(S^1)$.
Personally, I am tempted to claim that this happens if and only if
$$\sum_{s\in S\setminus\{0\}}\frac{1}{|s|}=\infty. $$
Moreover,  it looks  plausible that a strategy   similar to the one used by  Feller might give you the answer.
Update.   Apparently there have been quite a bit of work  describing sufficient conditions guaranteeing that a sequence of  exponentials $\newcommand{\ii}{\boldsymbol{i}}$ $(\lbrace\;\exp(\ii \lambda_n x)\;\rbrace$ is dense in $L^2([a,b])$.   I refer to the old book

N. Levinson: Gap and Density theorems, Amer. Math. Soc., 1940

or the more recent survey

R. Redheffer: Completeness of Sets of Complex Exponentials, Adv. in Math., 24(1977), 1-62.

Here is a nice result from Levinson's book.
Suppose that $\lambda_n$ is a sequence of positive numbers. For any $u>0$ we denote by $\Lambda(u)$ the number of terms  $\lambda_n$ that are $<u$. Then the collection  $(\lbrace\;\exp(\ii \lambda_n x)\;\rbrace$ is dense in $L^2([a,a+\ell])$ if
$$\limsup_{R\to\infty}\left\lbrace\int_1^R\frac{\Lambda(u)}{u^{1/2}}\left(\frac{1}{u}+\frac{1}{R}\right) du-\frac{4\ell} {3\pi}R^{1/2}\right\rbrace=\infty. $$
In particular, this happens if
$$\liminf_{n\to\infty}\frac{n}{\lambda_n}>\frac{\ell}{2\pi}. $$
A: Let $e_n:=\exp(\pi i n t)$ and by $[(e_n)_{n\in S}]$ denote the closed linear span. 
Claim. $[(e_n)_{n\in S}]=L_2[-1/2, 1/2]$ if and only if $e_{\lambda}\in [(e_n)_{n\in S}]$ for some $\lambda \in S^c$. 
Indeed, suppose $e_{\lambda}\in [(e_n)_{n\in S}]$ for some $\lambda \in S^c$. Then dividing by $e_{\lambda}$ we see that 1 can be approximated by linear combinations of $e_{n-\lambda}$ for $n\in S^c$. Note that $n-\lambda\neq 0$. Then by integration we can approximate function $t$ by linear combinations of  $e_{n-\lambda}$ for $n\in S^c$. Indeed, if $1\sim \sum_{k\in F} c_k e_{k-\lambda}$ for some finite $F\subset S^c$ ($\sim$ means approximation with some error $\epsilon$, and $c_k$'s coefficients), then
$\int_{-1/2}^t 1 du\sim \sum_{k\in F}c_k \int_{-1/2}^t\exp(\pi i (k-\lambda) u)du$. The last integral is $\sum_{k\in F} c'_k e_{k-\lambda}+A$ for some other coefficients $c'_k$ and constant $A$. (The point is you are integrating non-zero exponents.) In any case you get an approximation of $t$ by $e_{k-\lambda}$'s. Repeat this by integrating again to get $t^2, t^3, \ldots$. So the conclusion is any polynomial $p(t)$ can be approximated by $e_{k-\lambda}$'s and thus $e_{\lambda}p(t)\in [(e_n)_{n\in S^c}]$. Now for an arbitrary $f$, $e_{-\lambda}f$ can be approximated by a polynomial $p$, and so it follows by above that $f\in [(e_n)_{n\in S^c}]$ as claimed. 
Now to prove that  either $[(e_n)_{n\in S^c}]=L_2[-1/2, 1/2]$ or $[(e_n)_{n\in S}]=L_2[-1/2, 1/2]$ we need to observe that there must be a $e_{\lambda}$ in one set which belongs to the closed linear span of the other set. I thought this was obvious at first but I don't see how at the moment.
A: Update: I now realize that the Beurling-Malliavin Theorem that I review below doesn't completely answer your question. I'll leave it up anyway since it might be of some interest in this context.
To answer your question, we can proceed as follows: if neither $S$ nor $S^c$ gave me a complete set of exponentials, then I can find $f\in L^2(-1/2,1/2)$, $f\not=0$, such that
$$
F(z) = \int_{-1/2}^{1/2} f(x) e^{i\pi xz}\, dx
$$
has zeros at all $z\in S$, and there is a similarly defined function $G$ that has zeros at all $z\in \mathbb Z\setminus S$. The entire functions $F$ and $G$ are in the Paley-Wiener space $PW_{1/2}$ (which can be defined as the Fourier transforms of functions from $L^2(-1/2,1/2)$). Their product $FG$ is in $PW_1$; this is easy to check either by noting that $f*g\in L^2(-1,1)$ or by verifying the conditions from the Paley-Wiener theorem (note that $F,G$ are bounded on $\mathbb R$, so $FG\in L^2(\mathbb R)$).
By the sampling theorem, $FG$ can thus be recovered from its values on $\mathbb Z$. Since $(FG)(n)=0$ for all $n\in\mathbb Z$, it follows that $FG\equiv 0$, so since both functions are entire, at least one of them is identically equal to zero, contrary to our assumption.

Completeness of exponentials has of course been studied extensively, and one of the classical highlights is the Beurling-Malliavin Theorem, reviewed for example here.
Define $R(S)$ as the supremum of those $R>0$ (if there are any) for which $e^{i\pi nx}$, $n\in S$, spans a dense subspace of $L^2(-R,R)$. Then
$$
R(S)=D(S) , \quad\quad\quad\quad (1)
$$
where $D$ is the Beurling-Malliavin density of $S$ (there's no factor of $\pi$ in (1) because you incorporated this in the exponent).
From the definition of $D$, as reviewed in the linked paper, it follows that if $I_n=(a_n,a_n+L_n)\subseteq (0,\infty)$ are disjoint intervals with $\sum (L_n/a_n)^2=\infty$ and $\# (I_n\cap S)\ge d L_n$, then $D\ge d$.
Since, trivially, $\# (I_n\cap A)\ge (1/2-\epsilon)L_n$ for at least one of $A=S$ or $S^c$ for all long intervals $I_n$, it is immediate from the definition that $D(S)\ge 1/2$ or $D(S^c)\ge 1/2$ (for example, start with intervals $(2^n, 2^{n+1})$ and keep those that have sufficiently many points of $S$ or $S^c$, whichever choice works in the end).
