Would Evaluating a polynomial at uniformly random points outputs random values?

444 Views Asked by At

I`m wondering if we evaluate a polynomial on many points picked uniformly at random. Can we say the output values Y's are uniformly at random?

2

There are 2 best solutions below

4
On

In a comment it is specified that we are working in a finite field. Here is a simple counterexample.

Consider the field of $3$ elements, and the polynomial $p(x)=x^2$. If we evaluate at points in the field chosen at random, we get that $p(x)=0$ with probability $\frac{1}{3}$, and $p(x)=1$ with probability $\frac{2}{3}$.

7
On

A fixed polynomial over a finite field$~F$ will rarely transform uniformly chosen inputs into uniformly chosen outputs: this will happen if and only if the polynomial function $F\to F$ it defines is a bijection. This can certainly happen (every function $F\to F$ is a polynomial function, and uniquely so if one limits the degree to be less than $|F|$; moreover every polynomial of degree$~1$ defines a bijective polynomial function), but as $|F|$ increases this is a vanishing proportion of all functions, and if the sport is to permute the elements of your field, it is not clear wat advantage there is in describing that permutation by a polynomial.