# Polynomial over finite field

korollar
Hello,

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

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

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

I'd appreciate any suggestions.

Greetings,
korollar

Staff Emeritus
Gold Member
Isn't this just a straightforward counting argument?

Further hint: (how many inputs does it have?)

Last edited:
korollar
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?

korollar
Ah, it's too easy. Each value can at most $$\deg f$$ times assumed by f. So $$v \geq \frac{q}{\deg f}$$.

But how can I show, that even $$v \geq \frac{q-1}{\deg f} + 1$$ is true?

evouga
Hint: Show that for $$\deg f \neq 1, q$$, $$\frac{q}{\deg f}$$ has a remainder. Then do $$\deg f = 1, q$$ as special cases.

EDIT: Also note that the inequality, as stated, isn't true: consider $$f = x^{q+1}-x$$, which has only one value, 0, yet $$1 \not\geq 1+\frac{q-1}{q+1}$$. You need a floor around your fraction.

Last edited:
korollar
Sorry, I forgot to write that I only look at polynomials of degree $$< q$$.

But I still need help.

Say $$\frac{q}{\deg f} = n \cdot \deg f + r$$ where $$r < \deg f$$. But in general $$r + \frac{\deg f -1}{\deg f} > 1$$. So I can't tell why the estimation is correct?

evouga
You're right, I was assuming you meant to include a floor on the fraction.

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

korollar
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:

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

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

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