Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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
5  
$\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
1  
Thanks Pete! Your support really means a lot to me! –  Zev Chonoles Jan 15 '10 at 2:27
show 2 more comments

3 Answers

up vote 15 down vote accepted

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.

share|improve this answer
add comment

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$.

share|improve this answer
2  
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
1  
@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
add comment

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$.

share|improve this answer
2  
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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