Convolution of indicator functions with values in a finite field

Question

This is something I haven't seen online yet, indicator functions with values in a finite field. Probably for a good reason, but I would like to know why, and if there are still things that can be said. For instance what can we say of the relationship (if any) between the support of the convolution of two indicator functions with values in a finite field vs the addition of the sets they indicate.

More precisely: Let $F$ be a finite field and let $A, B$ be sets with additive cyclic structure, say $A, B \subseteq \mathbb{Z}_N$ with $N$ coprime to the characteristic of $F$. Define the "characteristic functions" $1_A, 1_B : \mathbb{Z}_N \to F$ by $1_A(x) = 1$ if $x \in A$, and $1_A(x) = 0$ otherwise. Similarly for $1_B$. Is there any relationship/proposition we can infer between the set $A + B$ and the support of the (cyclic) convolution $$ 1_A \ast 1_B(k) = \sum_{j \in \mathbb{Z}_N} 1_A(j) 1_B(k-j)? $$ For instance, if $1_A \ast 1_B(k) = 0$ for all $k \in \mathbb{Z}_N$, would this say anything at all about $A + B$?

Note in the case of the usual characteristic functions with values in $\mathbb{R}$ we have the nice property that $A + B$ is precisely the support of $1_A \ast 1_B$. So I wondered whether we can at least get something (although probably not quite this I imagine) when the values of the characteristic functions are either the additive or multiplicative identity in a finite field. Thanks!

Remark: Recall that the convolution here is taken modulo $p$, where $p$ is the characteristic of the field. Moreover note that the support of $1_A \ast 1_B$ is contained in $A + B$, since, if the convolution is non-zero modulo $p$, it is non-zero in $\mathbb{R}$ and so the support lies in $A + B$ by the fact mentioned above. This however does not say anything on whether or not the support is empty modulo $p$...

Answer 1

Note that $1_A(j)1_B(k-j)$ is nonzero if and only if $j\in A$ and $k-j\in B$, which implies that $k$ is in $A+B$. Even if $1_A(j)1_B(k-j)$ is nonzero, their sum could be zero if one takes the finite field aspect into account. Thus the support of the convolution is no bigger than $A+B$. Here is an example that shows that things break down.

Let $\mathbb{F}$ be the field of three elements and $n=5$. Let $A = \{0,1,2\}$ and $B = \{0,1,2,3\}$. Then $A+B = \{0,1,2,3,4\}$ and the above analysis shows that $1_A(j)1_B(k-j)$ is nonzero if and only if $k\in \{0,\ldots,4\}$. However in that case

\begin{align} (1_A\ast 1_B)(k) &= \sum_{j=0}^{4} 1_A(j)1_B(k-j) \\ &= 1_A(0)1_B(k) + 1_A(1)1_B(k-1) + 1_A(2)1_B(k-2). \end{align}

If $k = 4$, then the first term is zero but the second two are nonzero so the convolution is nonzero (since $\mathbb{F}$ is characteristic $3$). Taking instead $k=3$, all three terms are nonzero and so they sum to one modulo $3$. Same goes for $k=2$. You can play this game whenever $n > \operatorname{char}(\mathbb{F})$. You just have to modify it a bit but the idea is that you want to have $A$ and $B$ to have at an overlap of $\operatorname{char}(\mathbb{F})$ when shifting. (Meaning let $A$ and $B$ have at least $\operatorname{char}(\mathbb{F})$ elements.) If both $A$ and $B$ have support less than $\operatorname{char}(\mathbb{F})$, then the support of their convolution should be $A+B$.

---

In the case that $n < \operatorname{char}(\mathbb{F})$, you get the analogous result from $\mathbb{R}$. This is easy to see by breaking $A$ and $B$ into a union of singletons. This will make it clear how things shake out. In general, $1_A = \sum_{a\in A} 1_{\{a\}}$. Thus your convolution is nothing more than

\begin{align} (1_A\ast 1_B)(k) &= \sum_{j\in\mathbb{Z}_n} \left(\sum_{a\in A}1_{\{a\}}\right)(j)\left(\sum_{b\in B}1_{\{b\}}\right)(k-j) \\ &= \sum_{j\in\mathbb{Z}_n}\sum_{a\in A}\sum_{b\in B} 1_{\{a\}}(j)1_{\{b\}}(k-j) \end{align}

If $k\in A+B$, then $k=a_0+b_0$ for some $a_0\in A$ and $b_0\in B$. Thus

$$ (1_A\ast 1_B)(k) = \sum_{j\in\mathbb{Z}_n}\sum_{a\in A}\sum_{b\in B} 1_{\{a\}}(j) 1_{\{b\}}(a_0+b_0-j).$$

Letting $j = a_0 = a$ and $b = b_0$, we see that the convolution is nonzero since $n<\operatorname{char}(\mathbb{F})$. Thus the support of $1_A\ast 1_B$ contains $A+B$. The question then is whether or not the support is only $A+B$. The convolution is nonzero at $k$ if $j\in A$ and $k-j\in B$ for some $j$. Thus $k\in A+B$. Again you need that $n<\operatorname{char}(\mathbb{F})$ to conclude that it can't sum to $0$.