Polynomial over finite field

  • Thread starter korollar
  • Start date
  • #1
5
0

Main Question or Discussion Point

Hello,

I've got a quite simple question, but I don't get it:

Say we've got a finite field [tex]\mathbb{F}_q[/tex] and a polynomial [tex]f \in \mathbb{F}_q[X][/tex]. Let [tex]v[/tex] denote the number of distinct values of [tex]f[/tex].

Then, i hope, it should be possible to proof, that [tex]\deg f \geq 1 \Rightarrow v \geq \frac{q}{\deg f}[/tex].

I'd appreciate any suggestions.

Greetings,
korollar
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
Isn't this just a straightforward counting argument?

Further hint: (how many inputs does it have?)
 
Last edited:
  • #3
5
0
Sorry, I just don't see it.

I have q inputs. I can try out some polynomials and fields of small degree. But doesn't it demand number theoretical arguments do show this estimation?
 
  • #4
5
0
Ah, it's too easy. Each value can at most [tex]\deg f[/tex] times assumed by f. So [tex]v \geq \frac{q}{\deg f}[/tex].

But how can I show, that even [tex]v \geq \frac{q-1}{\deg f} + 1[/tex] is true?
 
  • #5
10
0
Hint: Show that for [tex]\deg f \neq 1, q[/tex], [tex]\frac{q}{\deg f}[/tex] has a remainder. Then do [tex]\deg f = 1, q[/tex] as special cases.

EDIT: Also note that the inequality, as stated, isn't true: consider [tex]f = x^{q+1}-x[/tex], which has only one value, 0, yet [tex]1 \not\geq 1+\frac{q-1}{q+1}[/tex]. You need a floor around your fraction.
 
Last edited:
  • #6
5
0
Sorry, I forgot to write that I only look at polynomials of degree [tex]< q[/tex].

But I still need help.

Say [tex]\frac{q}{\deg f} = n \cdot \deg f + r[/tex] where [tex]r < \deg f[/tex]. But in general [tex]r + \frac{\deg f -1}{\deg f} > 1[/tex]. So I can't tell why the estimation is correct?
 
  • #7
10
0
You're right, I was assuming you meant to include a floor on the fraction.

I'll need to think more about this; it's not obvious to me.
 
  • #8
10
0
Wan et al's "Value Sets over Finite Fields" give this result as their Corollary 2.4; their paper may be worth a look.

If there's a simple counting argument, I don't see it.
 
  • #9
5
0
I'd love to have a look at them. You don't accidentally have it at hand?

However - I found this inequation in a paper of Gomez-Calderon, where the notation is the following:

[tex]\left[ \frac{q-1}{d} \right] + 1 \leq |V_f|[/tex] (d: degree of f, V_f: value set of f)

And it says: [tex][x][/tex] denotes the greatest integer [tex]\leq x[/tex] - which makes it trivial.

In my source there were no brackets. I assume the notation above is the correct one.
 

Related Threads for: Polynomial over finite field

Replies
15
Views
13K
Replies
5
Views
2K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
1
Views
3K
Replies
2
Views
2K
  • Last Post
Replies
1
Views
6K
Replies
1
Views
2K
Top