Saturday 19 October 2019

galois theory - Distribution of the sumset of two GF($q$) subsets

First, a simple definition. The sumset of two subsets $\mathcal{S}_1$ and $\mathcal{S}_2$ containing $GF(q)$ elements is defined as:



$$\mathcal{S}_1 + \mathcal{S}_2 = \left\{ s_1 + s_2:s_1 \in \mathcal{S}_1,s_2 \in \mathcal{S}_2 \right\}.$$



I will also use the common definition: $g \cdot \mathcal{S}_1 = \left\{ g \cdot s_1:s_1 \in \mathcal{S}_1 \right\}$ for some $g \in GF(q)$. Note that $GF(q)$ arithmetic is assumed.



For example, assume that $q=4$ and that $\alpha$ is a primitive element GF($4$). Then:





  1. $$\{ 0,\alpha \} + \{ 0,\alpha \} = \{ 0 + 0,0 + \alpha ,\alpha + 0,\alpha + \alpha \} = \{ 0,\alpha \}.$$


  2. $$\{ 0,\alpha \} + \{ 0,1,\alpha \} = \{ 0 + 0,0 + 1,0 + \alpha ,\alpha + 0,\alpha + 1,\alpha + \alpha \} = \{ 0,1,\alpha,\alpha ^2 \}.$$


  3. $$\alpha \cdot \{ 0,1,\alpha \} = \{ 0,\alpha,\alpha ^2 \}.$$




My question is as follows. Assume that the sets $\mathcal{S}_1$ and $\mathcal{S}_2$ are iid random variables containing the symbol $0$. The additional elements of each set are drawn at random (without repetition), such that each $GF(q)$ subset (containing $0$) of a given size is equiprobable. For example, if $q=4$ then there exist probabilities $p_1,p_2,p_3,p_4$ such that:



I. $\Pr ( S_1 = \{ 0 \} ) = p_1$,




II. $\Pr \left( {{S_1} = \left\{ {0,1} \right\}} \right) = \Pr \left( {{S_1} = \left\{ {0,\alpha } \right\}} \right) = \Pr \left( {{S_1} = \left\{ {0,{\alpha ^2}} \right\}} \right) = {p_2},$



III. $\Pr \left( {{S_1} = \left\{ {0,1,\alpha } \right\}} \right) = \Pr \left( {{S_1} = \left\{ {0,1,{\alpha ^2}} \right\}} \right) = \Pr \left( {{S_1} = \left\{ {0,\alpha ,{\alpha ^2}} \right\}} \right) = {p_3},$



IV. $\Pr \left( {{S_1} = \left\{ {0,1,\alpha ,{\alpha ^2}} \right\}} \right) = {p_4}.$



In addition, $h_1$ and $h_2$ are iid random variables, distributed uniformly over the set $\left\{ {1,\alpha ,{\alpha ^2},...,{\alpha ^{q - 2}}} \right\}$ (i.e., $h_1$ and $h_2$ can be any non-zero element of GF($q$) with probability $1/(q-1)$). Denote: $\mathcal{S}_{\rm out} = {h_1} \cdot {\mathcal{S}_1} + {h_2} \cdot {\mathcal{S}_2}.$



I want to prove that $\mathcal{S}_{\rm out}$ is also distributed such that each GF($q$) subset of a given size containing $0$ is equiprobable. (As a special case, it means that I-IV above hold for $\mathcal{S}_{\rm out}$ with some $p_1', p_2',p_3',p_4'$).




What I tried:



So far I observed that $\mathcal{S}_{\rm out}$ sets that differ by a multiplicative factor are equiprobable, as $g \cdot {\mathcal{S}_{\rm out}} = g \cdot {h_1} \cdot {\mathcal{S}_1} + g \cdot {h_2} \cdot {\mathcal{S}_2}$ (for some $g \in$ GF($q$)) has the same distribution as $\mathcal{S}_{\rm out}$, since $g \cdot h_1, g \cdot h_2$ remain uniformly distributed. In fact, this is independent of the distribution of $\mathcal{S}_1$ and $\mathcal{S}_2$. However, I couldn't come up with an idea how to extend this relation to sets of the same size that do not differ by a multiplicative factor. In such cases one needs to show that all element-wise translations of $\mathcal{S}_{\rm out}$ of a given size has the same probability.

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...