First, a simple definition. The sumset of two subsets S1 and S2 containing GF(q) elements is defined as:
S1+S2={s1+s2:s1∈S1,s2∈S2}.
I will also use the common definition: g⋅S1={g⋅s1:s1∈S1} for some g∈GF(q). Note that GF(q) arithmetic is assumed.
For example, assume that q=4 and that α is a primitive element GF(4). Then:
{0,α}+{0,α}={0+0,0+α,α+0,α+α}={0,α}.
{0,α}+{0,1,α}={0+0,0+1,0+α,α+0,α+1,α+α}={0,1,α,α2}.
α⋅{0,1,α}={0,α,α2}.
My question is as follows. Assume that the sets S1 and S2 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 p1,p2,p3,p4 such that:
I. Pr,
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