The maximum number of some elements in the finite field.

Question

Consider the finite field $\mathbb{F}_{p^q}$ for some $p$ and $q$ where $p$ is a prime number. Suppose that $r$ in $\mathbb{F}_{p^q}$ has multiplicative order $n$. Consider the set ${\bf L}=\{0,1,r,r^2,\cdots ,r^{n-1}\}$.

Let the elements of ${\bf R}=\{a_1,a_2,,\cdots ,a_t\}$ in $\mathbb{F}_{p^q}$ for some $t$, satisfy the following condition:

For any $1\leq i,j\leq t$, $i \neq j$, we have $a_i\, a_j^{-1}$ is not an element of the set $\bf L$ and also $a_i's\not \in {\bf L}$.

Example: Suppose that $\mathbb{F}_{2^4}$ is constructed from the primitive polynomial ${\bf f}=x^4+x+1$ over $\mathbb{F}_{2}$. Let $\alpha$ be a root of $\bf f$. It is easy to check that $\alpha^5$ has multiplicative order $3$. Now consider the set ${\bf L}=\{0,1,{\alpha}^{5},{\alpha}^{10}\}$. Suppose that we want get four elements $a_i$ with $1\leq i \leq 4$ such that for any $1\leq i,j\leq 4$ we get $a_i\, a_j^{-1}$ is not an element of the set $\{0,1,{\alpha}^{5},{\alpha}^{10}\}$. By search we get: ${\bf R}=\{{\alpha}^{11},{\alpha}^{4},{\alpha}^{7},{\alpha}^{8}\}$. It can be verified that the elements of $\bf R$ satisfy the mentioned condition.

My Question: What is the maximum value for $t$ when $p$,$q$ and $r$ are fixed?

Thanks for any suggestion.

Answer 1

The keys to this question are the observations that

• $L^*=\{1,r,r^2,\ldots,r^{n-1}\}$ is a subgroup of the multiplicative group $\Bbb{F}_{p^q}^*$, and
• the condition $a_ia_j^{-1}\notin L^*$ is equivalent to the condition $$a_i\notin a_jL^*.$$ By elementary group theory $a_i\notin a_j L^*$ is equivalent to $a_iL^*\neq a_j L^*$. In other words, you want the elements $a_i,i=1,2,\ldots,t$, to come from distinct cosets of $L^*$.

The other condition $a_i\notin L$ rules out the coset $L^*=1\cdot L^*$, but doesn't affect anything else. Including $0$ into $L$ doesn't affect anything either because the presence of multiplicative inverses in the condition already excluded $0$ as an element of $\mathbf{R}$.

Anyway, the number of cosets of $L^*$ is $$ N=\frac{|\Bbb{F}_{p^q}^*|}{|L^*|}=\frac{p^q-1}n. $$

The conditions are met if and only if $\mathbf{R}$ only contains a single element from each coset of $L^*$ in $\Bbb{F}_{p^q}^*$ other than $L^*$ itself. The maximum cardinality of $\mathbf{R}$ is thus $$t=N-1=\frac{p^q-1-n}n.$$

It is also easy to describe explicit sets $\mathbf{R}$ of $N-1$ elements. If $g$ is any generator of the multiplicative group $\Bbb{F}_{p^q}^*$, IOW, a primitive element, then we can use $$ \mathbf{R}=\{g,g^2,g^3,g^4,\ldots,g^{N-1}\}. $$ Here $g^N$ is the lowest power of $g$ contained in the subgroup $L^*$.

More generally, we can use $$ \mathbf{R}=\{g^s\mid s\in S\}, $$ where $S$ consists representatives of cosets of the subgroup $H=N\Bbb{Z}_{p^q-1}$ in $\Bbb{Z}_{p^q-1}$ other than $H$ itself. In the OP's case $p^q-1=15$, $g=\alpha$, $N=5$. The set of exponents $$S=\{4,7,8,11\}$$ works because none of them is divisible by five, and they fall into distinct residue classes modulo five.