Happy new year. I'd like some help with this problem:
Let $p,d \in {[0,1]}^{n}$ so that ${||p||}_{L1} = {||d||}_{L1}=1$ i.e p,d are probability distributions over Z/nZ. '$\star$' is the operator of discrete convolution.
I am trying to prove that if $\frac{1}{2}||p-d||_{L1}=1$, then $||p\star d - p \star p||_{L1}>0$. That is, if p and d are distinguishable with probability 1, then $p\star d \neq p\star p$ (or find a counter-example)
By contradiction $p\star d = p\star p$. We remark that the followig holds: Let u,v be the discrete fourier transformations of p,d. Then $\forall j\leq n:u_{j}v_{j}=u_{j}^{2} \Longrightarrow \forall j\leq n: u_j=0 \quad or \quad u_j=v_j$.
Then: $\exists\{b_{j}\}_{j=0}^{n}\subseteq\{0,1\}^{n+1}:\forall k:p_{k}=\frac{1}{n}\sum_{j=0}^{n}(1-b_{j})v_{j}e^{\frac{2\pi i}{n}jk}$
And: $\frac{1}{2}||d_{k}-p_{k}||=\frac{1}{2n}||\sum_{j=0}^{n}b_{j}v_{j}e^{\frac{2\pi i}{n}jk}||=1$
I am not sure how to proceed from here, if it's the right direction. I have also considered using a method of additive combinatorics.
\|instead of||. $\endgroup$