1
$\begingroup$

I'm reading this paper (https://arxiv.org/pdf/2302.07211.pdf) and the authors mention a simple identity that looks like it should be trivial to prove but I'm having trouble with a sign that I can't get to disappear. We let $G$ be a finite abelian group and define the convolution of $f,g:G\to {\bf R}$ by $$ (f*g)(x) = {\bf E}_{y\in G} f(y) g(x-y)$$ and the difference convolution by $$ (f\circ g)(x) = {\bf E}_{y\in G} f(y) g(x+y).$$ The claim is that for $f,g,h:G\to {\bf R}$, we have $$\langle f,g*h\rangle = \langle f\circ h, g\rangle.$$

Attempt at a proof. I just expanded and got $$\eqalign{ \langle f, g*h \rangle &= {\bf E}_{x\in G} f(x) (g*h)(x) \cr &= {\bf E}_{x\in G} f(x) {\bf E}_{y\in G} g(y) h(x-y) \cr &= {\bf E}_{y\in G} g(-y) {\bf E}_{x\in G} f(x) h(y+x) \cr &= {\bf E}_{y\in G} g(-y) (f\circ h)(y) \cr }$$ I changed a sum over $y$ to a sum over $-y$ somewhere in there but I didn't have to, and I would have gotten the $-y$ and $y$ switched in the last line. The problem remains that the signs are different inside the arguments, which I think prevents us from reducing this further? I'm sure I'm missing something obvious, and would appreciate any pointers! Thanks in advance.

$\endgroup$
3
  • 2
    $\begingroup$ It seems to me as if either one of the definitions or equalities is wrong. Given the current definitions. the equality which holds is: $\langle f,g*h\rangle = \langle h\circ f, g\rangle.$ $\endgroup$ Aug 9, 2023 at 9:06
  • 1
    $\begingroup$ @user3257842 Thanks! I suppose more generally, we can say that while $(f*g)(x) = (g*f)(x)$, the argument has to be inverted to do the same for difference convolution: $(f\circ g)(x) = (g\circ f)(-x)$. If you copied your comment to an answer, I'd be happy to accept it! $\endgroup$
    – marcelgoh
    Aug 11, 2023 at 14:40
  • $\begingroup$ I've added a more detailed answer where I tried to explain the (rather sketchy) reasoning behind how I figured the correct equality. $\endgroup$ Aug 26, 2023 at 16:48

1 Answer 1

1
$\begingroup$

Either one of the definitions or one of the equalities is wrong. Given the current definitions, the equality which holds is:

$$\langle f,g*h\rangle = \langle h\circ f, g\rangle$$


To get a better intuition for these definitions, we can examine their effects on translated Dirac delta functions. Define:

$$\delta_{a}(x) = \delta(x-a)$$ This gives us: $$\delta_{a}(x) =\begin{cases} \infty & x = a \\ 0 & x\neq a \end{cases} $$

This is a delta situated at point $a$. We can use then our definitions to compute:

$$\delta_{a}*\delta_{b} = \delta_{a+b}\\ \delta_{a}\circ \delta_{b} = \delta_{b - a}$$

We see that the convolution acts as a sum, and the difference convolution acts as a difference (but oddly, one taken between the second and first term). The dot product obeys:

$$\langle \delta_{a}, \delta_{b} \rangle = \begin{cases} \infty & a = b \\ 0 & a\neq b \end{cases} $$

so it may be considered as a sort of equality check between dirac deltas. From $$(f\circ g)(x) = (g\circ f)(-x)$$ we may conclude that composition with $h(x) = -x$ corresponds to flipping of the sign. Ie. $g- f = -(f-g)$, or $\delta_{a}(-x) = \delta_{-a}(x)$. Finally, the equality between two dot products can be considered as a sort of logical equivalence of statements.

This is a rather ad-hoc analogy, but it gives us a quick and dirty way to translate between equivalences involving sums and differences , and equalities involving convolutions and difference convolutions.
For example:

$$ (f = g + h) \Leftrightarrow (f - h = g)$$ translates to: $$\langle f,g*h\rangle = \langle h\circ f, g\rangle$$

This is an incomplete analogy and doesn't always work exactly (the number of terms of each type on the left side must be equal to the one on the right), but we can use it to get a lot of "theorems for free", with due checking of course.

$$(a = b) \land (f = g) \Leftrightarrow (f + a = g + b)\\ \langle a,b\rangle \;\langle f,g\rangle = \langle f*a,\; g* b\rangle$$


$$(a-b)-c = a - (b+c)\\ c \circ (b\circ a) = (b*c) \circ a$$


$$a - b = a + (-b) \\ b \circ a = a * \bar{b}\\ \text{ where }\\ \bar{b}(x) = b(-x)$$.

$\endgroup$
1
  • $\begingroup$ Thanks! I'm still slowly wading through that paper and these observations are really helpful! $\endgroup$
    – marcelgoh
    Aug 28, 2023 at 18:37

You must log in to answer this question.

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