Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Polynomial over finite field

  1. May 27, 2008 #1

    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.

  2. jcsd
  3. May 27, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Isn't this just a straightforward counting argument?

    Further hint: (how many inputs does it have?)
    Last edited: May 27, 2008
  4. May 29, 2008 #3
    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?
  5. May 29, 2008 #4
    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?
  6. May 30, 2008 #5
    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: May 30, 2008
  7. Jun 1, 2008 #6
    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?
  8. Jun 1, 2008 #7
    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.
  9. Jun 2, 2008 #8
    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.
  10. Jun 2, 2008 #9
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook