3
$\begingroup$

Let $p$ be an odd prime and let $k\mid q$ for some positive integer numbers $k$ and $q$. Suppose that $r \in \mathbb{F}_{p^q}$ has multiplicative order $p^k-1$.

For each $1\leq u \leq p^k-3$, the subfield $\mathbb{F}_p(r) \cong \mathbb{F}_{p^k}$ of $\mathbb{F}_{p^q}$ contains $r^u + r^{u-1} + \cdots + r+1 \not=0$. Hence there exists a positive integer number $m_u$ such that the following equation holds. $$ r^{m_u}+r^u+r^{u-1}+\cdots+r+1=0 $$

Is there a systematic method to get the value of $\sum_{u=1}^{p^k-3}m_u$?

$\endgroup$
4
  • 1
    $\begingroup$ I made some minor edits. I assume that you want $m_u \in \{1,\ldots, p^{k}-2\}$, so that it is uniquely defined? $\endgroup$ Jan 23, 2019 at 3:24
  • 3
    $\begingroup$ In that case, this is equivalent to finding the unique missing element of $\{1, \dots, p^k - 2\}$ in the list. That is the element $x$ such that $r^x (r + 1) = 1$, or equivalently, $p^k - 1 - \text{ind}_r(r + 1)$, where $\text{ind}$ denotes the index. $\endgroup$
    – user44191
    Jan 23, 2019 at 6:52
  • $\begingroup$ @MarkWildon Your assumption is correct. I appreciate for edition of question. $\endgroup$
    – user0410
    Jan 23, 2019 at 6:59
  • 1
    $\begingroup$ Anyway, @user44191 had the same idea. $\endgroup$ Feb 4, 2019 at 5:57

1 Answer 1

4
$\begingroup$

The bad news is that the sum depends on the choice of $r$. We can do the following, reducing the problem to that of finding the discrete logarithm of $r-1$ (base $r$, of course).

Consider the sum $$ 1+r+r^2+\cdots+r^u=\frac{r^{u+1}-1}{r-1}. $$ The exponent $u+1$ in the numerator takes all the values in the range $2\le u+1\le p^k-2$. Consequently $r^{u+1}$ ranges over the $p^k$ elements of the field $K=\Bbb{F}_{p^k}$ with the three exceptions $r^{u+1}\notin\{0,1,r\}$.

This means that $$ r^{m(u)}=-\frac{r^{u+1}-1}{r-1} $$ ranges over the set $K\setminus\{0,-1,1/(r-1)\}.$

Therefore the exponent $m(u)$ otherwise takes all the possible values of the logarithm, $\{0,1,2,\ldots,p^k-2\}$, but omits $$\log_r(-1)=(p^k-1)/2\quad\text{and}\quad\log_r(1/(r-1))=p^k-1-\log_r(r-1).$$

Given all this, your sum equals $$ \begin{aligned} \sum_{u=1}^{p^k-3}m(u)&=\sum_{\ell=0}^{p^k-2}\ell-\frac{p^k-1}2-(p^k-1-\log_r(r-1))\\ &=\frac12(p^k-1)(p^k-2)-\frac{3(p^k-1)}2+\log_r(r-1)\\ &=\frac12(p^k-1)(p^k-5)+\log_r(r-1). \end{aligned} $$

But this is all we can say. We don't have a formula for the discrete logarithm $\log_r(r-1)$. The discrete logarithm problem is difficult in general, and in most cases the answer depends on the choice of $r$.

$\endgroup$
1
  • $\begingroup$ This assumes that $p>2$. When $p=2$ we have $-1=1$, meaning that $\log_r(-1)=0$ in that case. $\endgroup$ Feb 4, 2019 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.