2
$\begingroup$

For $f\in [0,1]^n$ with $\sum_i f_i = 1$, define the self-convolution $g=f*f$ with $$g_i = \sum_{j,k \mid j+k \equiv i \bmod n} f_j \cdot f_k$$ and define the L2-norm as $$\|f\| = \sqrt{\sum_i f_i^2}.$$

My question is it true that $$\|g\|\le \|f\|^2 \text{?}$$

I arrived here by translating into the frequency domain where the convolution becomes multiplication as far as I understand. I also tried to get here with some facts about convolutions and Lp norms https://en.wikipedia.org/wiki/Young%27s_convolution_inequality but I got a much weaker bound.

EDIT: Sorry, my bound is definitely wrong. The L1-norm of $f,g$ is $1$, so the L2-norm will be at least $1/\sqrt{n}$. My real question: what bounds can we give for $||g||$ in terms of $||f||$?

I'd also be interested if someone can point out the problem with my original hypothesis. Here was my thought process: Let $F$ denote the fourier transform of $f$, and let $\circ$ denote point-wise multiplication. A basic fact of fourier analysis is $F\circ F = f*f$, and also $F,f$ have the same L2-norm. Now we compute $$||F\circ F||^2 = \sum_i F_i^4 \le \left(\sum_i F_i^2\right)^2$$ which seems to imply $$||f*f||\le ||f||^2.$$ Where have I gone wrong?

Also, it seems that maybe stronger bounds can be achieved for prime $n$. If so, please assume that $n$ is prime.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ $$ g_i = \sum_{j,k \mid j+k \equiv 0 \bmod n} f_j \cdot f_k$$ I wonder whether you meant $$ g_i = \sum_{j,k \mid j+k \equiv i \bmod n} f_j \cdot f_k \text{ ?}$$ As it is, the index $i$ appears on the left side and not on the right side. $\endgroup$
    – Michael Hardy
    Commented Aug 11, 2023 at 2:22
  • $\begingroup$ @MichaelHardy yes, that's what I meant $\endgroup$
    – Alek Westover
    Commented Aug 11, 2023 at 2:31
  • $\begingroup$ @AlekWestover Are you sure $F,f$ have the same L2-norm? You have to be careful with normalizations in fourier analysis. $\endgroup$
    – mathworker21
    Commented Aug 11, 2023 at 6:29
  • $\begingroup$ @mathworker21 ... Yes. The Pontryagin dual of $\mathbb Z_m$ is $\mathbb Z_m$, but the pairing uses counting measure in one and uniform measure in the other. $\endgroup$
    – Gerald Edgar
    Commented Aug 11, 2023 at 8:47

1 Answer 1

Reset to default
2
$\begingroup$

By Cauchy-Schwarz, $|g_i|\le \sum_{j=1}^n|f_j|^2$ and $\|g\|\le \sqrt n \|f\|^2$. This is sharp because for $f_i=1/n$ for all $1\le i\le n$ we get the equality.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This seems true, but very weak if f has large L2 norm say larger than n^{1/4}. Can anything be said in that regime? My intuition is that g should have smaller L2 norm than f and usually much smaller. Are there counter examples? $\endgroup$
    – Alek Westover
    Commented Aug 11, 2023 at 12:12
  • $\begingroup$ Sorry, I understood you wanted a bound $\|g\|\le c\|f\|^2$, for which $c=\sqrt n$ is trivially optimal. As $\|f\|$ increases, $f$ has to be more and more close to a face of the simplex $\{f: f_i\ge0,\sum_if_i=1\}$, that is, more and more coordinates of $f$ are small. So I guess it may be useful to consider the optimization problem $\max_f \|f*f\|$ with an additional constraint $\text{supp} f=J\subset\{1,\dots,n\}$. Note that the limit case $\|f\|=1$ implies $f=e_i$ for some $i$ and $\|f*f\|=1$. $\endgroup$
    – Pietro Majer
    Commented Aug 11, 2023 at 15:49
  • $\begingroup$ Thanks! I'll think about it. I like the supp f constraint $\endgroup$
    – Alek Westover
    Commented Aug 11, 2023 at 17:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .