This is almost certainly routine to an analyst, so forgive me in advance.

Let $\alpha_i\in \mathbb{R}$. Consider the functional $$\varphi: L^1[0.9A,A]\to \mathbb{C}$$ via $$f\mapsto \sum_i \hat{f}(\alpha_i),$$ where by '$\hat{f}$' I mean the Fourier transform of $f$ regarded as a function on $\mathbb{R}$ (via extension by zero).

What can one say about the norm of $\varphi$?

I am wondering about the case where all $|\alpha_i| = O(1)$, $A$ is large, and the number of $\alpha_i$ is also large (comparable to $A$). As the title suggests, I'm hoping for a lower bound on $||\varphi||$. The thing that seemed most natural to me was to write this as integrating against a sum of exponentials (say $g(t)$, so that $||g||_\infty = ||\varphi||$) and then calculate the $L^2$ norm of $g$, but I can't bound the off-diagonal terms well enough.

The idea is that if, for some $t$ in the interval, $g(t)$ is very small, then some small-order derivative of $g$ should be bounded below so that $g((1\pm \delta)t)\gg_\delta A^{-O(1)}$ maybe. One could get a lower bound on some derivative via the nonvanishing of a Vandermonde determinant, but I think that would require too many derivatives.

Perhaps I am mistaken and there is an example with $||\varphi||\ll \exp(-c A)$?

Anyway, thanks much!

  • $\begingroup$ If we let the number go to $\infty$ and $A$ is fixed we have a good lower bound, and if $A$ is fixed and the number goes to $\infty$ then we also have a good lower bound. This makes it seem like there is a good lower bound $\endgroup$
    – Will Sawin
    Sep 23, 2015 at 3:38
  • $\begingroup$ Actually expressing it in terms of the $A$ variable is kind of strange. The really relevant variables are $O(1)/A$ (the maximum frequency after normalizing since $A=1$) and the number of $\alpha_i$. $\endgroup$
    – Will Sawin
    Sep 23, 2015 at 3:53

2 Answers 2


I think I can prove a polynomial bound using complex analysis. This really seems like it shouldn't work but it seems to.

The bound is that for all $\alpha_1, \dots, \alpha_n \in \mathbb R$

$$ \sup_{t \in [A,B]}\left| \sum_{i=1}^n e( \alpha_i t) \right| \geq n^{1-\frac{\pi}{4 \arctan {\sqrt{\frac{B}{A}}}-\pi}}$$

So in the special case $[.9A,A]$ this is $n^{-28.8313 \dots}$.

We may freely translate the $\alpha_i$, therefore, we assume $\min \alpha_i=0$. Form the holomorphic function

$$f(z) = \sum_{i=1}^n e(\alpha_i z)$$

We have the following estimates:

In the whole upper half plane, $|f(z)| \leq n$, as all the $\alpha_i$ are nonnegative so $e(\alpha_i z) \leq 1$.

On the imaginary line, $|f(z)| \geq 1$, as some $\alpha_i$ is zero giving $e(\alpha_i z) =1$ and the rest of the terms are positive reals.

Assume that for $z$ on the real line in the interval $[A,B]$, $|f(z)|<C$. (Then the same holds for $[-B,-A]$, which helps to get a better constant but isn't essential).

$f$ is holomorphic so $\log | f(z)|$ is subharmonic. Hence by the mean value theorem for subharmonic functions and the various bounds we stated on $f$:

$$ 0 \leq \log |f(it)| \leq\frac{t}{2\pi} \int_{-\infty}^{\infty} \frac{\log |f(s)|}{t^2+s^2}ds \leq \frac{t}{2\pi} \int_{-\infty}^{\infty} \frac{\log n}{t^2+s^2}ds+ 2\frac{t}{2\pi} \int_{A}^{B} \frac{\log C - \log n}{t^2+s^2}ds$$

$$ = \log n + \frac{\theta}{\pi} (\log C - \log n)$$

where $\theta$ is the hyperbolic angle between $A$ and $B$ from $it$. So we have:

$$0 \leq \log n + \frac{\theta}{\pi} (\log C - \log n)$$

$$ \frac{\theta}{\pi} (\log n - \log C) \leq \log n$$

$$ \log C \geq (1- \frac{\pi}{\theta}) \log n$$

$$C \geq n^{1-\pi/\theta}$$

as desired.

The optimal value of $\theta$ is a hyperbolic trigonometry problem which I may or may not have gotten the right answer to. Anyways it's some explicit formula.

Tao's example starting with, $\alpha_1=0$, $\alpha_2= \frac{1}{A+B}$ has an upper bound of the form $n^{\frac{\log \left|1- e\left(\frac{A}{A+B}\right)\right|}{\log 2}}$. My exponent is far from this as $A$ goes to $B$ so sharpness is an interesting question.

  • $\begingroup$ Wait --- do you mean +, rather than -, on all the (log C - log n) terms? Otherwise isn't the conclusion log C <= (1 + \theta/\pi) log n? $\endgroup$
    – alpoge
    Jan 19, 2016 at 14:46
  • $\begingroup$ Also why the 2 in front of the \int_A^B? $\endgroup$
    – alpoge
    Jan 19, 2016 at 14:50
  • 1
    $\begingroup$ @alpoge The $2$ is because there is also the interval $-B$ to $-A$. There's something messed up with the signs. Let me fix it. $\endgroup$
    – Will Sawin
    Jan 19, 2016 at 14:55
  • $\begingroup$ Also I think there should be a t in front of the Poisson integral, but obviously it doesn't matter cause you just take t = 1 anyway. This is amazing!!!!! $\endgroup$
    – alpoge
    Jan 19, 2016 at 14:56
  • $\begingroup$ @alpoge The signs are now right. Well technically to get the best constant taking $t= \sqrt{ab}$ so it matters some. $\endgroup$
    – Will Sawin
    Jan 19, 2016 at 14:57

One can indeed make $\|\phi\|$ exponentially small in $A$ (though the example I have requires an exponentially large number of frequencies $\alpha_i$).

We use the dual formulation, that is we find a sum of exponentials $g$ whose $L^\infty$ norm is small on $[0.9A, A]$. Firstly, if we consider the sum of just two exponentials $g_0(t) = 1 + e^{\pi i/A}$, then there is significant cancellation on $[0.9A,A]$, in particular $\|g_0\|_{L^\infty} \leq c < 1$ for some absolute constant $c<1$. If we then raise $g_0$ to the power $A$ (let's say $A$ is an integer) then we get a sum of exponentials $g_0^A$ whose frequencies are still bounded by 1, and whose sup norm decays exponentially fast in A.

I would expect exponential decay to be best possible, in particular the Vandermonde determinant approach probably gives such a bound. EDIT: it appears that one has the more general bound $\|\mu\|_1 \ll \exp(CA) \| \hat \mu \|_{L^\infty([0.9A,A])}$ for any nonnegative measure supported on $[-1,1]$, by using a variant of the real-variable proof of Hardy's uncertainty principle (see e.g. https://terrytao.wordpress.com/2009/02/18/hardys-uncertainty-principle/ ) to use $L^\infty$ control of $\hat \mu$ on $[0.9A,A]$ and a "doubling bound" to control $\hat \mu(0) = \|\mu\|_1$ with an exponential loss in constants, after first normalising $\|\mu\|_1=1$ to control error terms.

  • $\begingroup$ Cool! The regime I'm interested in has the number of frequencies bounded by $\eps A$, $\eps > 0$ small. In this case your example gives polynomial decay, which is acceptable to me. (I realize now that I left out a factor of $A^{-O(1)}$ in my speculation on the lower bound above.) Did you mean you also expect an exponential lower bound in this case to be best possible? Thanks much again! [I'm not sure if I did this "@..." construction correctly, hopefully it works!] $\endgroup$
    – alpoge
    Sep 23, 2015 at 17:05
  • $\begingroup$ By the way, I should mention that this Vandermonde approach doesn't use the fact that all the coefficients are $+1$, just that they are constant. Hence it would need knowledge about the gaps between the frequencies, because of examples like $1-e^{2\pi i \alpha t}$ with $\alpha = o(1/A)$ (or its powers, as above). What prevents such an example here is that if ${\alpha t}$ (the frac. part) is very close to $1/2$, then automatically $\alpha \gg 1/A$ and so by changing $t$ by a multiplicative constant we can move the fractional part by an additive constant. But I can't seem to make this precise :( $\endgroup$
    – alpoge
    Sep 23, 2015 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.