Linear Map = Function of degree P-1

Click For Summary
For every function f: Fp -> Fp, where p is prime, there exists a polynomial Q of degree at most p-1 such that f(x) = Q(x) for all x in Fp. The discussion raises questions about the applicability of polynomial interpolation in finite fields, with some participants expressing confusion about the concept of interpolation in this context. It is noted that polynomial interpolation can work over any field, but the finite nature of Fp complicates the idea of finding values between given values. Participants clarify that while a polynomial of degree p-1 has p coefficients, the connection to the function f remains unclear for some. The conversation emphasizes the need for a deeper understanding of polynomial behavior in finite fields.
brru25
Messages
29
Reaction score
0
If p is prime, prove that for every function f: Fp -> Fp there exists a polynomial Q (depending on f) of degree at most p-1 such that f(x) = Q(x) for each x in Fp.
 
Physics news on Phys.org
Would polynomial interpolation work here?
 
I don't see how you could interpolate. There are only p possible values in F_p. I notice you titled this "Linear Map= Function of degree P-1". Do you understand that there is nothing said here about f being linear?
 
Yea I assumed by accident it was linear. Yea I understand that there are only p values in Fp but I don't know how to make the connection to a polynomial. I mean I know a polynomial of degree p-1 has p coefficients but for some reason I can't connect the dots.
 
brru25 said:
Would polynomial interpolation work here?
Have you tried it? What happened?


HallsofIvy said:
I don't see how you could interpolate.
Polynomial interpolation works over any field... or is there something else you see that I don't?
 
Hurkyl said:
Polynomial interpolation works over any field... or is there something else you see that I don't?
Well, I think of "interpolation" as finding values between given values. And since this is a finite field, there is nothing "between" values.
 

Similar threads

  • · Replies 24 ·
Replies
24
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
988
  • · Replies 13 ·
Replies
13
Views
2K
Replies
9
Views
2K
Replies
1
Views
2K
Replies
5
Views
1K
Replies
15
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 5 ·
Replies
5
Views
2K