# Averaged Parseval Relation for Sampling a Function on Integers

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.

• 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? Jan 24 '19 at 15:53
• We can assume $f$ takes values on the unit circle and even that $supp~ f=[1,N].$ Jan 24 '19 at 20:09
• 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. Jan 24 '19 at 22:27
• Sorry $|f|$ is almost constant, but $f$ is not. Jan 24 '19 at 22:43
• but that doesn't matter for the $L^2$ estimates. 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$$.