Number of non-zero entries of self-convolution Let $f(k)$ be a function on the integers with the properties  


*

*$f(k)\geq 0$ $\forall k$

*$f(k)\geq p$ for at least $t$ values of $k$


Let $g(k)=\sum_{k'} f(k')f(k-k')$ be the self-convolution of $f$.
What is the minimal number of non-zero entries of $g(k)$? Can something be said about how large they have to be at least (e.g. $\geq p^2$)?
 A: It's true that $g(x)\geq p^2$ happens at at least $t$ points. Suppose $f(k)=0$ except at the $t$ points that fall in a set $S$, and that $\forall s\in S, g(s)\geq p$.
$$g(k)=\sum_{s\in S}f(s)f(k-s)$$ holds by restricting to the terms where the $f(k)$ piece of the product is non-zero. For $g(k)$ to be non-zero, it would have to be that $\exists s$ such that $k-s\in S$. How many ways this could happen depends on the set $S$. If we have a function $h(x)$ that is a lower bound on the number of $s$ for which $x-s\in S$, then we can conclude that $g(x)\geq h(x)p^2$.
We see that there are at least $t$ values for which $h(x)>0$ by writing $S=\{s_1,s_2,\ldots, s_t\}$ where $i< j\Rightarrow s_i<s_j$. Then the $t$ numbers of the set $S'=\{x+s_t:x\in S\}$ are all numbers where $h$ is non-zero.
We can see that this is sharp at $t=1$ by taking $S=\{0\}$ and $f(0)=p$ and $f(x)=0$ for $x>0$. Then $g(0)=p^2$ and $g(x)=0$ for $x>0$.
A: From the answer of Stella Biderman I managed to find the answer I was looking for.
There are at least $2t-1$ entries of $g(k)$ s.t. $g(k)\geq p^2$.
Proof:
Let $S=\{k:f(k)\geq p\}$.
Since $g(k)=\sum_{k'}f(k')f(k-k')$ and $f(k)\geq 0$, we know that $g(k)<p^2 \Rightarrow k-k'\notin S$ $\forall k'\in S$ (otherwise there is one element of the sum which is larger than $p^2$ and thus the sum is larger than $p^2$).
Thus $g(k)<p^2 \Rightarrow k\notin S'_{k'}=\{\ell+k' :\ell\in S\}$ $\forall k'\in S$ $\Rightarrow k\notin S'= \bigcup\limits_{k'\in S} S'_{k'} = \{\ell+k':k',\ell\in S\}$
From the answer to this question, we know that $|S'|\geq 2|S|-1$.
By definition, $t\geq|S|$ which proves the statement.
