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.