You mentioned that for finite fields, such f exist. Under the following assumption, I believe there is an infinite field with the same such that an f exists. (My field theory is very weak, so I'm not sure how obviously correct or obviously incorrect these assumptions are):

There is a sequence of finite fields $F_q$ with appropriate polynomials $f_q$ such that

i) $q_{1}< q_{2}$ implies $F_{q_{1}}$ has fewer elements than $F_{q_{2}}$ *(Edited notation a bit here)*

ii) deg$(f_{q}) \leq n\in\mathbb{N}$ (uniformly bounded)

iii) the number of points missed by $f_q$ is uniformly bounded above by $m\in\mathbb{N}$

Under these assumptions, construct an infinite field as follows:

Let F be the set of usual field axioms (expressed in first order logic).

Let $\psi$ be the first order statement "there are coefficients $a_{0}$ through $a_{n}$ and there are other points $y_{1}$ through $y_{m}$ such that for any $x$ we have $a_{n} x^{n} + ... + a_{1}x + a_{0} \neq y_{k}$ for any $k$ and for all $w$ which are not equal to $y_{1}$ through $y_{m}$ there is a $x$ such that $a_{n}x^{n} + ... + a_{0} = w$"

More colloquially, $\psi$ says "the polynomial $f(x) = a_{n}x^{n} + ... + a_{0}$ misses $y_1$ through $y_m$ but nothing else"

(One can, e.g., set $a_{n} = 0$ or $y_{1} = y_{2}$ if for a given finite field, the degree is smaller or $f_q$ misses fewer points)

Let $\phi_k$ be the first order statement "There are at least $k$ elements" (i.e., there exist $x_{1}$ through $x_{k}$ such that they are pairwise nonequal).

Finally, set $T = F \cup {\psi} \cup {\phi_{n}}$.

A model of $T$ is simply a set with interpretations for everything such that all the statements of $T$ are satisfied. In other words, a model is a field (because is satisfies F) which is infinite (because it simultaneously satisfies all of the $\phi_n$) which has a polynomial like you want (because of $\psi$).

Godel's completeness theorem says that $T$ has a model iff $T$ is consistent. The compactness theorem for first order logic says that $T$ is consistent iff every finite subset of $T$ is consistent.

Hence, by applying Godel's completeness theorem again, we need only show that every finite subset of $T$ has a model.

Choosing a finite $T_{0}\subseteq T$, we may, without loss of generality, enlarge it by including $F$ and $\psi$ because a model of $T_{0}\cup F\cup \psi$ will model $T_{0}$.

Now, since $T_{0}$ is finite, there is a largest $N$ such that $\phi_{N}$ is in $T_{0}$. Because of this, a model of $T_{0}$ is simply a finite field of at cardinality at least $N$ with a choice of function $f$ satisfying what you want (with bound on deg(f) and the number of points missed in the image). But the existence of such a field was precisely the assumption made at the top of the post.

Now, hopefully someone can shed some light as to whether or not the assumption is true.

mightwork. $\endgroup$ – Harrison Brown Nov 25 '09 at 16:103more comments