Condition for the number of distinct solutions over GF($q$)

78 Views Asked by At

Assume that we have $p$ sets $\left\{ {{m_i}} \right\}_{i = 1}^p$ with given cardinalities $\left\{ {{K_i}} \right\}_{i = 1}^p$, $1 \le {K_i} \le q$, where $q$ is a power of $2$. What I'm trying to do is to find a condition for the content of the sets, such that the sums (using GF($q$) arithmetic) of combinations of elements from the sets gives $n=1,2,...,q$ unique elements of GF($q$).

For example, assume that we have $2$ sets, both with cardinality $2$:

$${m_1} = \left\{ {{x_1},{x_2}} \right\},{m_2} = \left\{ {{x_3},{x_4}} \right\}$$

with $x_i$ taken from GF($q$). We have the following sums:

$${x_1} + {x_3},{x_1} + {x_4},{x_2} + {x_3},{x_2} + {x_4}$$

(in general we have $\prod\limits_{i = 1}^p {{K_i}} $ such sums). Is there a condition that guarantees that the number of distinct sums equals $n=1,2,...,q$? (it is clear that we have at least ${\max _i}{K_i}$ distinct sums). An approximate condition would also be helpful.

(this question is similar to one posted at csthoery, but now with focusing on the mathematical structure of GF($q$).

Edit:

  • If it helps, it can be assumed that $0 \in m_i$ for all $i$.

  • In the meantime, I noted that if $m_i$ are subgroups of the group formed by the elements of gf($q$) (with '+') ($K_i$ therefore must be a divisor of $q$), then for each pair $m_i,m_j$ we have:

$$\left| {{m_i}+{m_j}} \right| = \frac{{\left| {{m_i}} \right|\left| {{m_j}} \right|}}{{\left| {{m_i} \cap {m_j}} \right|}}$$

where:

$${m_i} + {m_j} = \left\{ {a + b:a \in {m_i},b \in {m_j}} \right\}$$

I should also add that given sets $\left\{ {{m_i}} \right\}_{i = 1}^p$ (with elements taken from gf($q$)) with given cardinalities $K_i$, I'm able to calculate the probability that the size of their intersection equals $n=1,2,...,q$.