Suppose that I have a polynomial vector, i.e. a polynomial $$\vec{p}(z) = \sum_{k} \vec{v}_k z^k$$
where $z$ lies in the complex unit circle.
My conjecture is that $span_k(\vec{v}_k) = span_z(\vec{p}(z))$.
One direction is clear, as $p(z)$ is a linear combination of the $\vec{v}_k$, but I'm not sure the converse holds. My intuition is that the claim is true because the $z^k$ with different choices of $z$ are linearly independent, but I'm not sure how to formalize this intuition.
This is true, and in fact if $\deg p = n$ it suffices to pick any $n$ distinct values of $z$, say $z_0, \dots z_{n-1}$. Your intuition is exactly correct; the desired statement is equivalent to the claim that the matrix with entries $z_j^k, 0 \le j, k < n$ is invertible. This is the Vandermonde matrix and there are several ways to prove it is invertible, for example by calculating its determinant, or by an argument involving Lagrange interpolation.
A particularly nice choice is to choose $z_j = e^{ \frac{2 \pi i j}{n} }$ to be the $n^{th}$ roots of unity. In this case the Vandermonde matrix is the discrete Fourier transform matrix (or, depending on your conventions, the inverse), and its inverse is given by the inverse discrete Fourier transform. There are some specialized proofs that the DFT is invertible, for example by explicitly writing down its inverse and explicitly calculating that it inverts the DFT, or using facts about the representation theory of finite groups.
So, if you want to write down a statement that does not depend on $\deg p$ and is valid for polynomials of arbitrarily large degree, it suffices to take $z$ to run over the roots of unity (or any other countable set of distinct elements of the unit circle).
