# Complex powers in finite fields

Is it possible to compute complex powers in finite fields? Given a $\in \mathbb{F}_p$ ($p$ prime), how can one compute $a^i$ per example?

-
I'd be interested in knowing why you would want to do this, as I can't think of any reasons myself. Have you thought of rational powers of ways of defining rational powers of finite field elements? –  Sonia Balagopalan Jan 14 '10 at 22:44
Please ignore the first instance of "of rational powers" in the previous comment. –  Sonia Balagopalan Jan 14 '10 at 22:47
@Sonia B: This is addressed in my response. –  Pete L. Clark Jan 14 '10 at 23:36
$\textbf{Hey everybody}$: please upvote Zev Chonoles' response, especially if you've already upvoted David's or mine. Reasons: 1) His response came at the same time as David's and before mine (even though all three were written independently); 2) his response -- unlike David's and mine -- was 100% correct on the first pass; and 3) he's a second-year undergraduate (unlike David and I, who are each several years post-PhD). Show some encouragement for the new generation! –  Pete L. Clark Jan 15 '10 at 0:17
Thanks Pete! Your support really means a lot to me! –  Zev Chonoles Jan 15 '10 at 2:27

I certainly don't think that for arbitrary complex numbers, you'll be able to define a notion of exponentiation (take $\pi$ for example). However, I think if you restrict to algebraic numbers, you'll have more of a chance. Here's something I cooked up for (sometimes) handling an $n$th root of unity $\omega$:

I assume we would like exponentiation to $\omega$ to be a (group) automorphism of $\mathbb{F}_q^\times\simeq\mathbb{Z}/(q-1)\mathbb{Z}$ - note that $\sigma(a)=a^\omega$ would have the property that $\sigma^n=$ id, so if there is an element of $Aut(\mathbb{F}_q^\times)$ of order $n$, then you could just define exponentiation to $\omega$ (or any of its conjugates) to be that (group) automorphism of $\mathbb{F}_q^\times$ (and set $0^\omega=0$). Note that the group of automorphisms $Aut(\mathbb{F}_q^\times)\simeq Aut(\mathbb{Z}/(q-1)\mathbb{Z})$ is simply $(\mathbb{Z}/(q-1)\mathbb{Z})^\times$, which has order $\phi(q-1)$, so if $n\nmid\phi(q-1)$, this wouldn't work.

-

There is no standard way to define this idea, and I doubt there is a useful one.

If I were trying to invent a definition, I'd say the following:

We should definitely have $(ab)^i = a^i b^i$ and $(a^i)^i=a^{-1}$. The first says that taking the $i$-th power is a homomorphism from the multiplicative group of the field to itself. Since the multiplicative group of a finite field is cyclic, the only homomorphisms from it to itself are of the form $a \mapsto a^k$ for some integer $k$.

Which integers $k$ should we accept? The second property imposes $a^{k^2} = a^{-1}$ modulo $p$. This implies that $k^2 = -1 \mod (p-1)$.

For most primes $p$, there are no solutions to $k^2 = -1 \mod (p-1)$. In the cases that there are, you could define raising to the $i$ power to means raising to the $k$ power for such a $k$. For example, when $p=11$, you could define $a^i$ to mean $a^3$, and you would get the two properties above.

I wouldn't do this though. At least in the areas of math where I work, it is considered a bad idea to define an operation on $F_p$ that doesn't extend nicely to the fields $F_{p^j}$. And there will never be a good definition of raising to the $i$ power in $F_{p^2}$. In order to get one, you'd need a solution to $k^2 = -1 \mod p^2-1$. But, for any prime other than $3$, $p^2-1$ is divisible by $3$, and $k^2+1$ is never divisible by $3$.

-
I was deliberately using elementary language above but, for those who know, the high falutin' way of saying operations on F_p should extend to F_{p^r} is that I want to work with schemes over F_p, not just with their F_p points. –  David Speyer Jan 14 '10 at 23:08
@DS: Let me return the favor (and help the readers who are trying to consolidate our two responses) by pointing out that $p = 5$ does not work: $-1$ is, famously, not a square modulo $4$. –  Pete L. Clark Jan 14 '10 at 23:29
Whoops! Let me go fix that. –  David Speyer Jan 14 '10 at 23:40

The question reminds me of a famous (and surprisingly polemical) maxim of Errett Bishop:

Do not ask whether a statement is true until you know what it means.

If $a$ is a nonzero element of $\mathbb{F}_p$, then it is not at all clear what e.g. $a^{\pi}$ ought to mean, so I can't say whether or not it is possible to compute it.

However, in some special cases, a reasonable meaning can be extracted. For instance, what properties should a map

$I: \mathbb{F}_p \rightarrow \mathbb{F}_p$

have in order to be able to reasonably assert that $I(a) = a^i$ for all $a$? Presumably we would want $I(ab) = I(a)I(b)$ and also $I(I(a)) = (a^i)^i = a^{-1}$. Thus we want $I$ to be an order four automorphism of the multiplicative group $U(p) = \mathbb{F}_p^{\times}$. Now $U(p)$ is a cyclic group of order $p-1$, so its automorphism group is isomorphic to $U(p-1)$, a not necessarily cyclic group of order $\varphi(p-1)$. So a necessary condition is that $4 \ | \ \varphi(p-1)$. The precise condition, in terms of congruences, is indeed the existence of an integer $x$ such that $x^2 \equiv -1 \pmod{p-1}$, as in David Speyer's response. So e.g. yes if $p = 11$. (Note that this works better than in the complex numbers, in which $z \mapsto z^i$ is a multi-valued function!)

Similarly, for fixed $n \geq 2$, one can certainly ask if $a^{\frac{1}{n}}$ exists for all $n$. This is the same as asking whether the multiplicative group $U(p)$ is $n$-divisible. This depends on both $n$ and $p$: e.g. no when $n = 2$ and $p$ is odd; yes when $n$ is coprime to $p-1$.

-
Wait a minute, Aut(Z/(p-1)) is not usually cyclic! For example, if p=13, then phi(12) is 4, but Aut(Z/12) is Z/2 x Z/2, not Z/4. –  David Speyer Jan 14 '10 at 23:05
@DS: You're right. How embarrassing. I'll look it over to see if there is an easy fix. –  Pete L. Clark Jan 14 '10 at 23:18
That's why I phrased it as "if there is an element of $Aut(\mathbb{F}_q^\times)$ of order $n$" instead of just "if $n\mid\phi(q−1)$" in my very similar answer :) –  Zev Chonoles Jan 14 '10 at 23:24
I find it interesting that all three of us independently gave almost exactly the same answer to a somewhat vague question. –  David Speyer Jan 14 '10 at 23:29
@DS and ZC: I upvoted both of your responses; I think that all three are pretty close. Usually MO warns me when another answer comes in while I am writing mine. If I am just finishing up formatting, I submit the response as soon as possible; otherwise I look at the other answer and decide whether to abandon ship. I probably would have done so in this case. –  Pete L. Clark Jan 14 '10 at 23:33