Return to Question

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector space.

$$M_{p^k}^{(d)}:=\max_{\{\beta_1,\cdots,\beta_k\}\text{ is a basis of } \mathbb{F}_{p^k}}\Big\{\dim\langle\beta_1^d, \cdots, \beta_k^d \rangle\Big\}$$

For fixed $p^k$ and $d$, is there any known results on exact value or bounds of this quantity? I am both interested in the general case and the special case of $d=2$. Any idea or comment will be very helpful. The following are some very basic facts that I have observed, but I could not go further.

• When $d$ is a power of $p$, it holds that $M_{p^k}^{(d)}=k$, regarding a normal basis and Frobenius map.
• $M_{p^k}^{(d)}\ge \lfloor \frac{k-1}{d} \rfloor + 1$, regarding first $(\lfloor \frac{k-1}{d} \rfloor + 1)$ elements of a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$.

A conjecture:

If $\gcd (d,p^k-1)=1$, then $M_{p^k}^{(d)}=k$. (from the discussion with Donggeon Yhee)

Some experimental results:

A primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$ usually gives the optimal basis.

$p=2$ case:

• $M_{2^k}^{(3)}=k$ for $k\le 100$, except $M_{2^2}^{(3)}=1$
• $M_{2^k}^{(5)}=k$ for $k\le 100$, except $M_{2^4}^{(5)}=2$
• $M_{2^k}^{(6)}=k$ for $k\le 100$, except $M_{2^2}^{(6)}=1$
• $M_{2^k}^{(7)}=k$ for $k\le 100$, except $M_{2^3}^{(7)}=1$
• $M_{2^k}^{(9)}=k$ for $k\le 100$, except $M_{2^2}^{(9)}=1$ and $M_{2^6}^{(9)}\ge 3$
• $M_{2^k}^{(10)}=k$ for $k\le 100$, except $M_{2^4}^{(10)}=2$
• $M_{2^k}^{(25)}=k$ for $k\le 100$, except $M_{2^4}^{(25)}=2$
• $M_{2^k}^{(27)}=k$ for $k\le 100$, except $M_{2^2}^{(27)}=1$ and $M_{2^6}^{(27)}\ge 3$

$p=3$ case:

• $M_{3^k}^{(2)}=k$ for $k\le 100$
• $M_{3^k}^{(4)}=k$ for $k\le 100$, except $M_{3^2}^{(4)} = 1$
• $M_{3^k}^{(5)}=k$ for $k\le 100$
• $M_{3^k}^{(6)}=k$ for $k\le 100$

$p=5$ case:

• $M_{5^k}^{(2)}=k$ for $k\le 100$
• $M_{5^k}^{(3)}=k$ for $k\le 100$
• $M_{5^k}^{(4)}=k$ for $k\le 100$
• $M_{5^k}^{(6)}=k$ for $k\le 100$, except $M_{5^2}^{(6)} = 1$

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector space.

$$M_{p^k}^{(d)}:=\max_{\{\beta_1,\cdots,\beta_k\}\text{ is a basis of } \mathbb{F}_{p^k}}\Big\{\dim\langle\beta_1^d, \cdots, \beta_k^d \rangle\Big\}$$

For fixed $p^k$ and $d$, is there any known results on exact value or bounds of this quantity? I am both interested in the general case and the special case of $d=2$. Any idea or comment will be very helpful. The following are some very basic facts that I have observed, but I could not go further.

• When $d$ is a power of $p$, it holds that $M_{p^k}^{(d)}=k$, regarding a normal basis and Frobenius map.
• $M_{p^k}^{(d)}\ge \lfloor \frac{k-1}{d} \rfloor + 1$, regarding first $(\lfloor \frac{k-1}{d} \rfloor + 1)$ elements of a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$.
• If $\gcd (d,p^k-1)=1$, then $M_{p^k}^{(d)}=k$, regarding a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$. Indeed, $\beta^d$ is a primitive element, and $\{1, \beta^d, \beta^{2d}, \cdots, \beta^{(k-1)d}\}$ is again a basis. (from the discussion with Donggeon Yhee)

Some experimental results:

A primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$ usually gives the optimal basis.

$p=2$ case:

• $M_{2^k}^{(3)}=k$ for $k\le 100$, except $M_{2^2}^{(3)}=1$
• $M_{2^k}^{(5)}=k$ for $k\le 100$, except $M_{2^4}^{(5)}=2$
• $M_{2^k}^{(6)}=k$ for $k\le 100$, except $M_{2^2}^{(6)}=1$
• $M_{2^k}^{(7)}=k$ for $k\le 100$, except $M_{2^3}^{(7)}=1$
• $M_{2^k}^{(9)}=k$ for $k\le 100$, except $M_{2^2}^{(9)}=1$ and $M_{2^6}^{(9)}\ge 3$
• $M_{2^k}^{(10)}=k$ for $k\le 100$, except $M_{2^4}^{(10)}=2$
• $M_{2^k}^{(25)}=k$ for $k\le 100$, except $M_{2^4}^{(25)}=2$
• $M_{2^k}^{(27)}=k$ for $k\le 100$, except $M_{2^2}^{(27)}=1$ and $M_{2^6}^{(27)}\ge 3$

$p=3$ case:

• $M_{3^k}^{(2)}=k$ for $k\le 100$
• $M_{3^k}^{(4)}=k$ for $k\le 100$, except $M_{3^2}^{(4)} = 1$
• $M_{3^k}^{(5)}=k$ for $k\le 100$
• $M_{3^k}^{(6)}=k$ for $k\le 100$

$p=5$ case:

• $M_{5^k}^{(2)}=k$ for $k\le 100$
• $M_{5^k}^{(3)}=k$ for $k\le 100$
• $M_{5^k}^{(4)}=k$ for $k\le 100$
• $M_{5^k}^{(6)}=k$ for $k\le 100$, except $M_{5^2}^{(6)} = 1$

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector space.

$$M_{p^k}^{(d)}:=\max_{\{\beta_1,\cdots,\beta_k\}\text{ is a basis of } \mathbb{F}_{p^k}}\Big\{\dim\langle\beta_1^d, \cdots, \beta_k^d \rangle\Big\}$$

For fixed $p^k$ and $d$, is there any known results on exact value or bounds of this quantity? I am both interested in the general case and the special case of $d=2$. Any idea or comment will be very helpful. The following are some very basic facts that I have observed, but I could not go further.

• When $d$ is a power of $p$, it holds that $M_{p^k}^{(d)}=k$, regarding a normal basis and Frobenius map.
• $M_{p^k}^{(d)}\ge \lfloor \frac{k-1}{d} \rfloor + 1$, regarding first $(\lfloor \frac{k-1}{d} \rfloor + 1)$ elements of a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$.

A conjecture:

If $\gcd (d,p^k-1)=1$, then $M_{p^k}^{(d)}=k$. (from the discussion with Donggeon Yhee)

Some experimental results:

$p=2$ case: a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$ usually gives the optimal basis.

• $M_{2^k}^{(3)}=k$ for $k\le 100$, except $M_{2^2}^{(3)}=1$
• $M_{2^k}^{(5)}=k$ for $k\le 100$, except $M_{2^4}^{(5)}=2$
• $M_{2^k}^{(6)}=k$ for $k\le 100$, except $M_{2^2}^{(6)}=1$
• $M_{2^k}^{(7)}=k$ for $k\le 100$, except $M_{2^3}^{(7)}=1$
• $M_{2^k}^{(9)}=k$ for $k\le 100$, except $M_{2^2}^{(9)}=1$ and $M_{2^6}^{(9)}\ge 3$
• $M_{2^k}^{(10)}=k$ for $k\le 100$, except $M_{2^4}^{(10)}=2$
• $M_{2^k}^{(25)}=k$ for $k\le 100$, except $M_{2^4}^{(25)}=2$
• $M_{2^k}^{(27)}=k$ for $k\le 100$, except $M_{2^2}^{(27)}=1$ and $M_{2^6}^{(27)}\ge 3$

$p=3$ case: a primitive element basis rarely gives the optimal basis.

• $M_{3^k}^{(2)}=k$ for $k\le 12$, except $M_{3^{10}}^{(2)} \ge 9$ and $M_{3^{12}}^{(2)} \ge 9$
• $M_{3^k}^{(4)}=k$ for $k\le 12$, except $M_{3^2}^{(4)} = 1$ and $M_{3^{12}}^{(4)} \ge 9$
• $M_{3^k}^{(5)}=k$ for $k\le 7$, except $M_{3^7}^{(5)} \ge 6$
• $M_{3^k}^{(6)}=k$ for $k\le 6$, except $M_{3^6}^{(6)} \ge 5$

$p=5$ case: a primitive element basis rarely gives the optimal basis.

• $M_{5^k}^{(2)}=k$ for $k\le 7$, except $M_{5^7}^{(2)} \ge 5$
• $M_{5^k}^{(3)}=k$ for $k\le 6$, except $M_{5^6}^{(3)} \ge 5$
• $M_{5^k}^{(4)}=k$ for $k\le 5$, except $M_{5^5}^{(4)} \ge 4$
• $M_{5^k}^{(6)}=k$ for $k\le 6$, except $M_{5^2}^{(6)} = 1$ and $M_{5^6}^{(6)} \ge 5$

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector space.

$$M_{p^k}^{(d)}:=\max_{\{\beta_1,\cdots,\beta_k\}\text{ is a basis of } \mathbb{F}_{p^k}}\Big\{\dim\langle\beta_1^d, \cdots, \beta_k^d \rangle\Big\}$$

For fixed $p^k$ and $d$, is there any known results on exact value or bounds of this quantity? I am both interested in the general case and the special case of $d=2$. Any idea or comment will be very helpful. The following are some very basic facts that I have observed, but I could not go further.

• When $d$ is a power of $p$, it holds that $M_{p^k}^{(d)}=k$, regarding a normal basis and Frobenius map.
• $M_{p^k}^{(d)}\ge \lfloor \frac{k-1}{d} \rfloor + 1$, regarding first $(\lfloor \frac{k-1}{d} \rfloor + 1)$ elements of a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$.

A conjecture:

If $\gcd (d,p^k-1)=1$, then $M_{p^k}^{(d)}=k$. (from the discussion with Donggeon Yhee)

Some experimental results:

A primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$ usually gives the optimal basis.

$p=2$ case:

• $M_{2^k}^{(3)}=k$ for $k\le 100$, except $M_{2^2}^{(3)}=1$
• $M_{2^k}^{(5)}=k$ for $k\le 100$, except $M_{2^4}^{(5)}=2$
• $M_{2^k}^{(6)}=k$ for $k\le 100$, except $M_{2^2}^{(6)}=1$
• $M_{2^k}^{(7)}=k$ for $k\le 100$, except $M_{2^3}^{(7)}=1$
• $M_{2^k}^{(9)}=k$ for $k\le 100$, except $M_{2^2}^{(9)}=1$ and $M_{2^6}^{(9)}\ge 3$
• $M_{2^k}^{(10)}=k$ for $k\le 100$, except $M_{2^4}^{(10)}=2$
• $M_{2^k}^{(25)}=k$ for $k\le 100$, except $M_{2^4}^{(25)}=2$
• $M_{2^k}^{(27)}=k$ for $k\le 100$, except $M_{2^2}^{(27)}=1$ and $M_{2^6}^{(27)}\ge 3$

$p=3$ case:

• $M_{3^k}^{(2)}=k$ for $k\le 100$
• $M_{3^k}^{(4)}=k$ for $k\le 100$, except $M_{3^2}^{(4)} = 1$
• $M_{3^k}^{(5)}=k$ for $k\le 100$
• $M_{3^k}^{(6)}=k$ for $k\le 100$

$p=5$ case:

• $M_{5^k}^{(2)}=k$ for $k\le 100$
• $M_{5^k}^{(3)}=k$ for $k\le 100$
• $M_{5^k}^{(4)}=k$ for $k\le 100$
• $M_{5^k}^{(6)}=k$ for $k\le 100$, except $M_{5^2}^{(6)} = 1$

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector space.

$$M_{p^k}^{(d)}:=\max_{\{\beta_1,\cdots,\beta_k\}\text{ is a basis of } \mathbb{F}_{p^k}}\Big\{\dim\langle\beta_1^d, \cdots, \beta_k^d \rangle\Big\}$$

For fixed $p^k$ and $d$, is there any known results on exact value or bounds of this quantity? I am both interested in the general case and the special case of $d=2$. Any idea or comment will be very helpful. The following are some very basic facts that I have observed, but I could not go further.

• When $d$ is a power of $p$, it holds that $M_{p^k}^{(d)}=k$, regarding a normal basis and Frobenius map.
• $M_{p^k}^{(d)}\ge \lfloor \frac{k-1}{d} \rfloor + 1$, regarding first $(\lfloor \frac{k-1}{d} \rfloor + 1)$ elements of a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$.

Some experimental results:

$p=2$ case: a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$ usually gives the optimal basis.

• $M_{2^k}^{(3)}=k$ for $k\le 100$, except $M_{2^2}^{(3)}=1$
• $M_{2^k}^{(5)}=k$ for $k\le 100$, except $M_{2^4}^{(5)}=2$
• $M_{2^k}^{(6)}=k$ for $k\le 100$, except $M_{2^2}^{(6)}=1$
• $M_{2^k}^{(7)}=k$ for $k\le 100$, except $M_{2^3}^{(7)}=1$
• $M_{2^k}^{(9)}=k$ for $k\le 100$, except $M_{2^2}^{(9)}=1$ and $M_{2^6}^{(9)}\ge 3$
• $M_{2^k}^{(10)}=k$ for $k\le 100$, except $M_{2^4}^{(10)}=2$
• $M_{2^k}^{(25)}=k$ for $k\le 100$, except $M_{2^4}^{(25)}=2$
• $M_{2^k}^{(27)}=k$ for $k\le 100$, except $M_{2^2}^{(27)}=1$ and $M_{2^6}^{(27)}\ge 3$

$p=3$ case: a primitive element basis rarely gives the optimal basis.

• $M_{3^k}^{(2)}=k$ for $k\le 12$, except $M_{3^{10}}^{(2)} \ge 9$ and $M_{3^{12}}^{(2)} \ge 9$
• $M_{3^k}^{(4)}=k$ for $k\le 12$, except $M_{3^2}^{(4)} = 1$ and $M_{3^{12}}^{(4)} \ge 9$
• $M_{3^k}^{(5)}=k$ for $k\le 7$, except $M_{3^7}^{(5)} \ge 6$
• $M_{3^k}^{(6)}=k$ for $k\le 6$, except $M_{3^6}^{(6)} \ge 5$

$p=5$ case: a primitive element basis rarely gives the optimal basis.

• $M_{5^k}^{(2)}=k$ for $k\le 7$, except $M_{5^7}^{(2)} \ge 5$
• $M_{5^k}^{(3)}=k$ for $k\le 6$, except $M_{5^6}^{(3)} \ge 5$
• $M_{5^k}^{(4)}=k$ for $k\le 5$, except $M_{5^5}^{(4)} \ge 4$
• $M_{5^k}^{(6)}=k$ for $k\le 6$, except $M_{5^2}^{(6)} = 1$ and $M_{5^6}^{(6)} \ge 5$

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector space.

$$M_{p^k}^{(d)}:=\max_{\{\beta_1,\cdots,\beta_k\}\text{ is a basis of } \mathbb{F}_{p^k}}\Big\{\dim\langle\beta_1^d, \cdots, \beta_k^d \rangle\Big\}$$

For fixed $p^k$ and $d$, is there any known results on exact value or bounds of this quantity? I am both interested in the general case and the special case of $d=2$. Any idea or comment will be very helpful. The following are some very basic facts that I have observed, but I could not go further.

• When $d$ is a power of $p$, it holds that $M_{p^k}^{(d)}=k$, regarding a normal basis and Frobenius map.
• $M_{p^k}^{(d)}\ge \lfloor \frac{k-1}{d} \rfloor + 1$, regarding first $(\lfloor \frac{k-1}{d} \rfloor + 1)$ elements of a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$.

A conjecture:

If $\gcd (d,p^k-1)=1$, then $M_{p^k}^{(d)}=k$. (from the discussion with Donggeon Yhee)

Some experimental results:

$p=2$ case: a primitive element basis of the form $\{1, \beta, \beta^2, \cdots, \beta^{k-1}\}$ usually gives the optimal basis.

• $M_{2^k}^{(3)}=k$ for $k\le 100$, except $M_{2^2}^{(3)}=1$
• $M_{2^k}^{(5)}=k$ for $k\le 100$, except $M_{2^4}^{(5)}=2$
• $M_{2^k}^{(6)}=k$ for $k\le 100$, except $M_{2^2}^{(6)}=1$
• $M_{2^k}^{(7)}=k$ for $k\le 100$, except $M_{2^3}^{(7)}=1$
• $M_{2^k}^{(9)}=k$ for $k\le 100$, except $M_{2^2}^{(9)}=1$ and $M_{2^6}^{(9)}\ge 3$
• $M_{2^k}^{(10)}=k$ for $k\le 100$, except $M_{2^4}^{(10)}=2$
• $M_{2^k}^{(25)}=k$ for $k\le 100$, except $M_{2^4}^{(25)}=2$
• $M_{2^k}^{(27)}=k$ for $k\le 100$, except $M_{2^2}^{(27)}=1$ and $M_{2^6}^{(27)}\ge 3$

$p=3$ case: a primitive element basis rarely gives the optimal basis.

• $M_{3^k}^{(2)}=k$ for $k\le 12$, except $M_{3^{10}}^{(2)} \ge 9$ and $M_{3^{12}}^{(2)} \ge 9$
• $M_{3^k}^{(4)}=k$ for $k\le 12$, except $M_{3^2}^{(4)} = 1$ and $M_{3^{12}}^{(4)} \ge 9$
• $M_{3^k}^{(5)}=k$ for $k\le 7$, except $M_{3^7}^{(5)} \ge 6$
• $M_{3^k}^{(6)}=k$ for $k\le 6$, except $M_{3^6}^{(6)} \ge 5$

$p=5$ case: a primitive element basis rarely gives the optimal basis.

• $M_{5^k}^{(2)}=k$ for $k\le 7$, except $M_{5^7}^{(2)} \ge 5$
• $M_{5^k}^{(3)}=k$ for $k\le 6$, except $M_{5^6}^{(3)} \ge 5$
• $M_{5^k}^{(4)}=k$ for $k\le 5$, except $M_{5^5}^{(4)} \ge 4$
• $M_{5^k}^{(6)}=k$ for $k\le 6$, except $M_{5^2}^{(6)} = 1$ and $M_{5^6}^{(6)} \ge 5$