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?
2026-03-25 16:13:30.1774455210
On
Would Evaluating a polynomial at uniformly random points outputs random values?
444 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
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.
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}$.