Minimum Number of Distinct Values for a Polynomial over a 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

 

[Hurkyl]

Isn't this just a straightforward counting argument?

Further hint: (how many inputs does it have?[/color])

 

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

 

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

I'll need to think more about this; it's not obvious to me.

 

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