Minimum Number of Distinct Values for a Polynomial over a Finite Field

Click For Summary

Discussion Overview

The discussion revolves around the minimum number of distinct values that a polynomial can take over a finite field \(\mathbb{F}_q\). Participants explore theoretical aspects of polynomials, particularly focusing on the relationship between the degree of the polynomial and the number of distinct outputs it can produce.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant proposes that for a polynomial \(f\) of degree \(\deg f \geq 1\), the number of distinct values \(v\) should satisfy \(v \geq \frac{q}{\deg f}\).
  • Another participant suggests that this could be shown through a counting argument, questioning how many inputs the polynomial has.
  • A different participant expresses uncertainty, indicating that they believe number theoretical arguments may be necessary to establish the estimation.
  • One participant asserts that each value can be assumed at most \(\deg f\) times, reinforcing the initial claim about \(v\) being greater than or equal to \(\frac{q}{\deg f}\).
  • Another participant questions the validity of the inequality, providing a counterexample with the polynomial \(f = x^{q+1}-x\), which has only one value, 0.
  • A participant mentions the need to consider polynomials of degree less than \(q\) and expresses confusion regarding the correctness of the estimation involving remainders.
  • One participant acknowledges the need for a floor function in the fraction to accurately represent the relationship.
  • A reference to Wan et al.'s work is made, suggesting that it contains relevant results on the topic.
  • Another participant cites a paper by Gomez-Calderon, which presents an inequality involving the greatest integer function, indicating that this notation may clarify the earlier confusion.

Areas of Agreement / Disagreement

Participants exhibit a mix of agreement and disagreement regarding the validity of the proposed inequalities and the methods to prove them. There is no consensus on the correct approach or the necessity of additional theoretical arguments.

Contextual Notes

Participants note limitations in their understanding, particularly regarding the assumptions needed for the inequalities and the implications of the degree of the polynomial. The discussion also reflects uncertainty about the correct notation and definitions used in the context of the problem.

korollar
Messages
5
Reaction score
0
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
 
Physics news on Phys.org
Isn't this just a straightforward counting argument?

Further hint: (how many inputs does it have?[/color])
 
Last edited:
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?
 
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?
 
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:
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?
 
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.
 
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.
 
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.
 

Similar threads

Undergrad Finite fields, irreducible polynomial and minimal polynomial theorem
  • · Replies 6 ·
Replies
6
Views
3K
Simple Induction Induction proof of Polynomial Division Theorem
  • · Replies 10 ·
Replies
10
Views
3K
Challenge Math Challenge - August 2021
  • · Replies 46 ·
2
Replies
46
Views
8K
Undergrad Need clarification on a theorem about field extensions/isomorphisms
  • · Replies 14 ·
Replies
14
Views
3K
Graduate Is Every Diagonalizable Endomorphism Defined by a Simple Polynomial?
  • · Replies 12 ·
Replies
12
Views
3K
Graduate Proving the Primality of a Polynomial over Finite Fields
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Irreducible Polynomials over Finite Fields
  • · Replies 5 ·
Replies
5
Views
3K
MHB Automorphisms of Field Extensions .... Lovett, Example 11.1.8 .... ....
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Automorphisms of Field Extensions .... Lovett, Example 11.1.8
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Is There an Algebraic Closure for Every Field?
  • · Replies 1 ·
Replies
1
Views
2K