2
$\begingroup$

I've just started with the theory of finite fields and I am stuck in an exercise, which must be not so difficult... Can anybody, please, give me a hint what can I do for to solve it?

Given is a finite field $F_{q}$ with $q$ elements, not necesserily prime and a function $f:F_{q}\rightarrow F_{q}$.
Prove that there exists a polynomial $P\in F_{q}[x]$, such that $P(x)=f(x)$ for every $x\in F_{q}$.

I would be glad, if someone could help me. Thank you in advance!

$\endgroup$
  • $\begingroup$ If $F_q$ is a finite field, with $q$ elements, then $q$ must be prime, no? $\endgroup$ – Robert Lewis Sep 21 '13 at 21:54
  • 5
    $\begingroup$ @RobertLewis It could also be a power of a prime $\endgroup$ – Daniel Montealegre Sep 21 '13 at 21:55
  • $\begingroup$ Ah but of course! $\endgroup$ – Robert Lewis Sep 21 '13 at 21:57
  • $\begingroup$ As wisdom often comes from the mouths of babes, so drivel sometimes drips from the lips of the experienced! ;) $\endgroup$ – Robert Lewis Sep 21 '13 at 21:58
2
$\begingroup$

Whilst staring at my laptop's screen in t'shuvah for my most blasphemous comment, grace found me, fiat lux!!!:

Let $F_q = \{a_1, a_2, . . . , a_q\}$; the $a_i$ are the distinct elements of $F_q$.

Set

$p_i(x) = f(a_i) \frac{\prod_{j \ne i}(x - a_j)}{\prod_{j \ne i}(a_i - a_j)}, \tag{1}$

then

$p_i(a_i) = f(a_i), \tag{2}$

and if $i \ne j$,

$p_i(a_j) = 0. \tag{3}$

So if we set

$P(x) = \sum_i p_i(x) \tag{4}$

it is easy to see that

$P(a_i) = f(a_i) \tag{5}$

for all $a_i \in F_q$, where as I have recently learned $F_q$ is a finite field with $q = p^n$ elements for some prime $p$!

Now, correct me if I'm wrong, did I not just rediscover (something perilously close to) Lagrange interpolation?

Ah, sweet forgiveness!

Peace, Love, and chag s'meach

But above all,

Fiat Lux!!!

$\endgroup$
  • $\begingroup$ Yup, this is just Lagrange's toy, and it appears, in disguise or in all its glory, in some other answers. Yet I think your answer is nice, so חג שמח לך (let's check whether you forgto your hebrew or not) and +1 . $\endgroup$ – DonAntonio Sep 22 '13 at 3:12
  • $\begingroup$ @DonAntonio, achiy! baruch l'cha! thanks for refreshing my memory in re. Lagrange's toy, I have indeed seen it around here and MO. But I really wish I knew how to write iv'riyt in my posts, how did you do that? And thanks for the echad! $\endgroup$ – Robert Lewis Sep 22 '13 at 3:40
  • $\begingroup$ Thank you very very much!!! $\endgroup$ – Lullaby Sep 22 '13 at 9:26
  • $\begingroup$ Glad to be of assistance!, @Lullaby $\endgroup$ – Robert Lewis Sep 22 '13 at 16:04
5
$\begingroup$

Try to find a polynomial that is zero everywhere except at one point $x \in F_q$. This is possible because the field is finite. The solution is a linear combination of such polynomials.

$\endgroup$
  • $\begingroup$ This is really the key to the whole thing. Using my hint, it’s the easiest possible thing to write down such a polynomial for each $a$. Then you’re in business. $\endgroup$ – Lubin Sep 22 '13 at 0:27
3
$\begingroup$

Hint: For $\alpha \in \mathbb{F}_q$, first construct a polynomial $f_\alpha$ such that $f_\alpha(\alpha) \neq 0$ and $f_\alpha(\beta) = 0$ for all $\beta \neq \alpha$. Once this is done, you can in fact make it so $f_\alpha(\alpha) = 1$. Then the general polynomial can be made by taking a sum over the $f_\alpha$ with appropriate coefficients.

$\endgroup$
3
$\begingroup$

Hint: If you are familiar with the term, Lagrange Interpolating Polynomial solves the problem.

Otherwise, let $P(X)=a_nX^n+...+a_1x+a_0$ where we will chose $n$ later (I can chose it now, but the value will become obvious later).

Setting

$$P(a)=f(a) \forall a \in F_q $$ is a system of $q$ equations with the $n+1$ unknowns $a_0,...,a_n$. Thus if $n+1=q$ we get a square system, where the determinant can be proven to be non-zero (is actually a Vandermonde determinant). Pick the unique solution.

$\endgroup$
3
$\begingroup$

Hint: the set of nonzero elements of $\mathbb F_q$ is a group of order $q-1$. So all nonzero elements are roots of $X^{q-1}-1$. Then?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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