Given that a list of $k$ elements selected uniformly at random from some finite field $\mathbb{Z}_p$ of prime characteristic, what is the probability that this list of elements can be interpolated such that the degree of the resulting polynomial is strictly less than $k-1$? I've been noodling over this for a bit now and cannot come to a satisfactory solution.
My intuition hints to me that it's got to be proportional to both $k$ and $\log_2(p)$, or some functions of them, but I can't come to anything rigorous or satisfactory yet. Any guidance or help would be appreciated.
There are $p^k$ polynomials of degree up to $k-1$, and you can select $p^k$ different $k$-tuples of values. No two of these polynomials have the same value tuple at the $k$ positions; otherwise their difference would have $k$ roots despite them being of degree less than $k$. So the interpolation establishes a bijection between the $k$-tuples and the polynomials.
There are $p^{k-1}$ polynomials of degree up to $k-2$, and you get one of them if and only if you select its value tuple. Thus the probability for this to happen is
$$ \frac{p^{k-1}}{p^k}=\frac1p\;. $$