This was asked a long time ago on math.stackexchange with no answers.

Let $f:\mathbb{Z}\rightarrow \mathbb{C}.$ Assume that the support of $f$ is finite, say it is $[1,N],$ and that $\mid f\mid$ is bounded (as well as being nonzero at each point in its support if necessary). Define the fourier transform $$\widehat{f}:[0,1)\rightarrow \mathbb{C}$$ by $$\widehat{f(t)}=\sum_{n\in \mathbb{Z}} f(n)~e^{2i \pi n t}.$$

Parseval states that $$ \sum_{n \in \mathbb{Z}} \mid f(n) \mid^2 = \int_0^1 \mid\widehat{f(t)} \mid^2 \,dt $$ holds. Now let $v$ be a positive integer $\geq 2,$ and let the "sampled" function be $$ f_v(n)=\left\{ \begin{array}{ccc} f(n), & \quad\mathrm{if}\quad & v|n,\\ & & \\ 0 & & \mathrm{otherwise}. \end{array} \right. $$ Let $f=f_1$ for simplicity. What is the Parseval relationship for this function, as expressed in terms of the transform of the original function?

Due to the comb structure, one will have a `sinc' structure for the transform, and the comb can be truncated to the support $[1,N],$ which can presumably be used together with the convolution theorem in the frequency domain.

What I am really interested in, however, is estimating from below, the following quantity $$ \sum_{v=1}^m \sum_{n \in \mathbb{Z}} \mid f_v(n) \mid^2 = \sum_{v=1}^m \sum_{n \in \mathbb{Z}} \mid \mathbb{1}\{n\!\!\pmod v=0~\}|^2 \mid f(n)\mid^2= $$ $$ =\sum_{v=1}^m \int_0^1 \mid \widehat{\Phi_v(t-t')} \mid^2 \mid\widehat{f(t')} \mid^2 \,dt' \geq $$ $$ \stackrel{hopefully}{\geq} A(N,m) \int_0^1 \mid\widehat{f(t')} \mid^2 \,dt' $$ using some kind of uncertainty relation. Here, $\widehat{\Phi_v(t)}$ is the fourier transform of the comb, i.e., the sinc type function.

We can take $m\ll N,$ a fractional power of $N$ or even a power of $\log N.$

Edit: Let $|f|>0,$ on $[1,N]$. and can even take it to be essentially constant in magnitude if it helps.

  • 1
    $\begingroup$ Isn't there a problem with your derivation near the end? The $L^2$ norm of the convolution $\widehat{\Phi_v} * \widehat{f}$ is not the integral you wrote. For $m \ll N$, if you take $f$ to be supported only at $f(1) = 1$ and $f(\mathrm{lcm}(\{1, \ldots, m\})+1) = 1$ and zero otherwise. The trivial lower bound of $A = 1$ seems to be sharp. So presumably you are more interested in when $m$ is large enough that $f_v$ has to be mostly non-trivial? $\endgroup$ Jan 24 '19 at 15:53
  • $\begingroup$ We can assume $f$ takes values on the unit circle and even that $supp~ f=[1,N].$ $\endgroup$
    – kodlu
    Jan 24 '19 at 20:09
  • $\begingroup$ If you assume $f$ is almost constant in magnitude, then pretty much all the $f(n)$ terms that appear in the summation can be replaced by $1$, no? Then the "combed" sum would be basically $\sum_{v = 1}^m N/v$ which shouldn't be too hard to estimate from below. $\endgroup$ Jan 24 '19 at 22:27
  • $\begingroup$ Sorry $|f|$ is almost constant, but $f$ is not. $\endgroup$
    – kodlu
    Jan 24 '19 at 22:43
  • $\begingroup$ but that doesn't matter for the $L^2$ estimates. $\endgroup$ Jan 25 '19 at 16:28

If one were to assume $|f|$ is almost constant on its support, then a rough estimate is available.

Assume for now $|f| = 1$ on its support. Similar argument can be made if we know that there exists some $C>0$ such that $C \inf_{n\in \{1, \ldots, N\}} |f(n)| \geq \sup_{n \in \{1, \ldots, N\}} |f(n)|$.

In the case $|f| = 1$ on its support, the sum of $\ell_2$ norms that the OP is interested becomes

$$ \sum_{\nu = 1}^m \underbrace{\lfloor \frac{N}{\nu} \rfloor}_{= \|f_\nu\|_2^2} $$

which by elementary inequalities gives

$$ N \sum_{\nu = 1}^m \frac{1}{\nu} \geq \sum_{\nu = 1}^m \lfloor \frac{N}{\nu} \rfloor \geq N \sum_{\nu = 1}^m \frac{1}{\nu} - m $$

The sum $\sum_{\nu = 1}^m \frac{1}{\nu}$ is the $n$th Harmonic number about which much is known. For a very rough estimate we have it is bounded

$$ \ln(m) + 1 \geq \sum_{\nu = 1}^m \frac{1}{\nu} \geq \ln(m) $$

So you get

$$ N \ln(m) + N \geq \sum_{\nu = 1}^m \lfloor \frac{N}{\nu} \rfloor \geq N \ln(m) - m $$

As you want to compare this to $\| f\|_{2}^2 = N$ in this case, you see that a very naive bound of

$$ A(N,m) \geq \ln(m) - \frac{m}{N} $$

would work. This can of course be sharpened using better estimates of the Harmonic numbers.

In the case you have $C > 1$, you see that the same argument leads to $A(N,m) \geq \frac1{C^2} (\ln(m) - \frac{m}{N})$ as a rough estimate. Of course, as I mentioned in the comments, there is the trivial lower bound of $A(N,m) \geq 1$, which seems sharp as $C \nearrow \infty$, at least when $m \ll N$.


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.