7
$\begingroup$

Let $F$ denote the Fourier transform over some group. What is known about the following quantity?

$$\gamma:=\inf_{x\neq 0}\frac{\|Fx\|_1}{\|F|x|\|_1}$$

Here, $|x|$ denotes the pointwise absolute value of $x$. We know $\gamma\leq1$ since $x$ can be pointwise nonnegative. In the case where $F$ is the DFT, we also know $\gamma>0$ by a compactness argument, and computer simulations give $\gamma\leq0.72$ by taking $x$ to be some random bandlimited even function.

EDIT: Following Josep's comment, we actually know $\gamma\geq1/\sqrt{n}$ in the DFT case by passing to the 2-norm and applying Parseval.

I would mostly like to know if $\gamma\gg0$ (i.e., there exists a constant $\epsilon>0$ independent of $n$ such that $\gamma\geq\epsilon$), since this would imply that $\|Fx\|_1$ is small (i.e., $Fx$ is concentrated) only if $\|F|x|\|_1$ is also small. This would confirm my intuition that phase doesn't play much of a role in the concentration of a function's spectrum. Presumably, this question is natural enough to have been studied already.

$\endgroup$
3
  • $\begingroup$ If you are working in a finite dimensional space, you can use the equivalence between the 1-norm and the 2-norm. $\endgroup$
    – user75485
    Jun 30, 2015 at 8:58
  • $\begingroup$ @Dustin : Is there any physical motivation for this question, I mean, for example applying on a signal etc? $\endgroup$
    – Rajesh D
    Jul 1, 2015 at 15:16
  • $\begingroup$ @RajeshD - My motivation is to find better uncertainty principles, which definitely find applications in signal processing (analyzing sparse signals, compressed sensing, etc). $\endgroup$ Jul 1, 2015 at 21:50

2 Answers 2

5
$\begingroup$

Observe that if $n$ and $m$ are relatively prime, $\gamma_{nm}\leq \gamma_n \gamma_m$ because you can combine functions on $\mathbb Z/n$ and $\mathbb Z/m$ using the Chinese remainder theorem.

So if we show $\gamma_n \leq 1- \epsilon$ for some $\epsilon$ and all sufficiently large $n$, then we can make $\gamma_n$ arbitrarily small.

Probably $x(t) = \sin( 2\pi t/n)$ works for this. I think it's clear that in this case the ratio is asymptotic to

$$ \frac{ \sum_{k \in \mathbb Z}\left| \int_{0}^{2 \pi} \sin (x) e^{ i k x} \right|}{ \sum_{k \in \mathbb Z}\left| \int_{0}^{2 \pi} |\sin (x)| e^{ i k x} \right|}$$

where the numerator is clearly $2\pi$ and the denominator is

$$ \sum_{k \in 2 \mathbb Z} \left|\frac{-4}{k^2-1}\right|= 8 $$

This gives $\pi/4$, agreeing with Dustin's numerical experiments, which is bounded away from $1$.


The asymptotic statement is from the Poisson summation-like formula. If $f$ is a function on the unit circle, and $f_n$ is the function on $\mathbb Z/n$ you get by restricting it to the $n$ roots of unity, then

$$\hat{f_n} ( a) =\sum_{k \in \mathbb Z} \hat{f} ( a + nk)$$

so

$$ \lim_{n \to \infty} ||\hat{f}_n||_1 = || \hat{f} ||_1$$

The integral I found the calculations too fiddly so I just did it on wolframalpha, but you can do it by breaking up $[0,2\pi]$ into $[0,\pi]$ and $[\pi, 2\pi]$. The sum is by telescoping from $\frac{1}{k-1} - \frac{1}{k+1} = \frac{2}{k^2-1}$.


Here's a method for arbitrary $\mathbb Z/n$. Let $a_1, \dots, a_k$ be elements of $\mathbb Z/n$ and consider

$$x(t) = \prod_{i=1}^k \sin (a_k x/n) $$

Supposing that $\sum_{i=1}^k \pm a_i$ is nonvanishing, the $L^1$ norm of $Fx$ is $1 $ if you normalize it properly.

Now I claim for any group homomorphism $G \to H$, given a function on $H$, the Fourier transform of its pullback to $G$ can be computed on a character of $G$ by summing the Fourier transform of $H$ over all characters of $H$ that pull back to that character of $G$. This is the same as the Poisson summation formula and is proved the same way. Here I'm normalizing by the measure of the group.

Apply this to the map $\mathbb Z/n \to (\mathbb R/\mathbb Z)^n$ that sends $t$ to $(a_1t/n, \dots, a_kt/n)$

Let $g(m)$ be the Fourier transform of $|\sin x|$. Then the Fourier transform of $\left| \prod_{i=1}^k sin x_i \right| $ is $\prod_{i=1}^k g(m_i)$.

$$F |x| ( \xi) = \sum_{(y_1, \dots, y_k) \in \mathbb Z^k } 1_{\sum_{i=1}^k a_i y_i \equiv \xi } \prod_{i=1}^k g(y_i)$$

This is the sum of $\prod_{i=1}^k g(y_i)$ over the lattice in $\mathbb Z^k$ satisfying the condition $\sum_{i=1}^k a_i y_i \equiv \xi $.

Now we know that $\prod_{i=1}^k g(y_i)$ has $L_1$ norm $ (4/\pi)^k$, and at most $(2/3) (4/\pi)^k$ of its mass is in the box where $|y_i| < Ck$, because $1-O(1/k)$ of the mass of $g(y)$ is in the box where $|Y| < k $.

So as long as no equation of the form $\sum_{i=1}^k y_i a_i =0$ for $y_i$ not all $0$ but $|y_i| < 2 C k$ holds, then no two points in that box get sent to the same $\chi$, so the $L_2$ norm goes down by at most $1-2/3$ (in the worst case where everything outside the box cancels something inside the box.)

When can we find $a_1, \dots, a_k$ such that no such equation holds? If $n=p$ is a prime then by selecting $a_1, \dots, a_k$ randomly, the probability of any given equation holds is $1/p$, so as long as $p > (2 C k)^k$ then sometimes none of the equations hold.

If we're not a prime then we can just do the Chinese Remainder Theorem thing, or do the probabilistic argument more carefully.

$\endgroup$
1
  • $\begingroup$ The calculations here look similar to those used to disprove the (related) Hardy-Littlewood majorant conjecture, which was first done by Bachelis: ams.org/mathscinet-getitem?mr=320636 $\endgroup$
    – Terry Tao
    Jul 1, 2015 at 1:41
3
$\begingroup$

I believe no such constant exists. $\newcommand{\cF}{{\mathcal F}}\newcommand{\FA}{{\rm A}}$

Let $G$ be a LCA group with Pontryagin dual $\Gamma$, let $\cF_\Gamma: L^1(\Gamma)\to C_0(G)$ be the Fourier transform for $\Gamma$, and let $\FA(G)$ denote the image $\cF_\Gamma(L^1(\Gamma))$ equipped with the norm pushed forward from $L^1(\Gamma)$. Then if I understood your question correctly, it is equivalent — via Fourier inversion, etc — to asking if there exists some contant $\epsilon>0$ such that $\Vert\,|x|\,\Vert_{\FA(G)} \leq \epsilon^{-1}\Vert x \Vert_{\FA(G)}$ for all $x$.

In the older language of "functions operating in Banach algebras", this asks if the function $x\mapsto |x|$ operates in the Banach algebra $\FA(G)$, and as mentioned in my answer to someone else's MO question the answer is negative for $G={\bf T}$ or $G={\bf R}$.

My gut feeling is that if we take $f_n(t):= |\sin (2\pi n t)|$ for $t\in {\bf R}/{\bf Z} \cong {\bf T}$, then $\Vert f_n\Vert_{\FA({\bf R}/{\bf Z})} \to +\infty$ as $n\to + \infty$, but I haven't tried to do explicit estimates to prove this. Update: my closing paragraph was not thought through properly, as Will Sawin has pointed out in comments.

$\endgroup$
5
  • 1
    $\begingroup$ Thanks! I'm not sure I agree with your gut, though. Taking $x_a(t):=\operatorname{sin}(2\pi at/n)$, simulations suggest that $\inf_{a,n}\|F_nx_a\|_1/\|F_n|x_a|\|_1=\pi/4$, where $F_n$ denotes the DFT over $\mathbb{Z}/n\mathbb{Z}$. $\endgroup$ Jun 30, 2015 at 14:14
  • 1
    $\begingroup$ Doesn't $||f_n||_{A(\mathbb R/\mathbb Z)} = ||f_1||_{A(\mathbb R/\mathbb Z)}$ because the Fourier transofrm of $||f_n||$ is the Fourier transform of $||f_1||$ with extra zeroes? $\endgroup$
    – Will Sawin
    Jun 30, 2015 at 22:09
  • $\begingroup$ @WillSawin - I have a lot more intuition about the Fourier transform of $\sin(2\pi n\cdot)$ than I do about $f_n$. Perhaps you conflated the two? $\endgroup$ Jun 30, 2015 at 23:58
  • $\begingroup$ @DustinG.Mixon For any function $f$, if we let $f_n$ be $f$ composed with multiplication by $n$ then there is a simple formula for $\hat{f}_n$. $\endgroup$
    – Will Sawin
    Jul 1, 2015 at 0:05
  • $\begingroup$ @WillSawin Good point. I'll update my answer $\endgroup$
    – Yemon Choi
    Jul 1, 2015 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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