Is there an infinite field $k$ together with a polynomial $f \in k[x]$ such that the associated map $f \colon k \to k$ is not surjective but misses only finitely many elements in $k$ (i.e. only finitely many points $y \in k$ do not lie in the image of $f$)?
For finite fields $k$, there are such polynomials $f$. If such a poynomial $f$ exists, then $k$ cannot be algebraically closed; the field $\mathbb{R}$ doesn't work either.
Since such a polynomial would have to have degree at least 2, its existence implies that the set of k-rational points of the affine line over k is thin in the sense of Serre's Topics In Galois Theory. It follows from the results presented in that book that this cannot be the case over any Hilbertian field. This includes finite extensions of Q, finite extensions of F(t) for any field F, and many other fields.
What about p-adic fields?
Here is a simple (the simplest) argument for why it does not hold over any Hilbertian fields. But first recall that $K$ is Hilbertian if for any irreducible $f(T,X)\in K[T,X]$ there is infinitely many $t\in K$ such that $f(t,X)$ is irreducible in $K[X]$.
The argument: Let $f(X)\in K[X]$ be a polynomial over a Hilbertian field. Then $f(X) - T$ is irreducible in $K[T,X]$, thus $f(X) - a$ is irreducible for infinitely many $a\in K$.
Just to have a feeling here are some Hilbertian fields:
1. number fields
2. a finitely generated transcendental extension of an arbitrary field, in particular function fields
3. the family of Hilbertian fields is closed under
3a. finite extensions
3b. abelian extensions
3c. taking a finite proper extension of an arbitrary Galois extension
3d. extensions satisfying the diamond condition (see Haran's diamond theorem)
Recently, I have shown with Hendrik Lenstra that there is no example when $k$ satisfies the following two properties:
For example, one can take $k$ to be an infinite algebraic extension of a finite field (use Hasse-Weil to see this).
I will put a proof on arXiv later, but here is a sketch:
Recently, I have shown the following theorem with Hendrik Lenstra.
Definition: A field $k$ is called large if every irreducible $k$-curve with a $k$-rational smooth point has infinitely many $k$-points.
Some examples of large fields are $\mathbb{R}$, $\mathbb{Q}_p$ ($p$ prime), $l((t))$ (where $l$ is a field), infinite algebraic extensions of finite fields. Furthermore, finite extensions of large fields are large.
Theorem: Let $k$ be a perfect large field and let $f \in k[x]$. Consider the evaluation map $f_k: k \to k$. Assume that $f_k$ is not surjective. Then the set $k \setminus f_k(k)$ is infinite (in fact, it has cardinality $|k|$).
See my arXiv article for a proof.
This isn't much, but let me sketch the argument that $\mathbb{Q}$ doesn't work. It suffices to show that given a polynomial $f$ of degree greater than $1$ which is, without loss of generality, primitive and in $\mathbb{Z}[x]$, there are infinitely many integers $k$ such that $f - k$ is irreducible.
Lemma: Suppose $f(x) \in \mathbb{Z}[x]$ is primitive and has the property that $f(0)$ is prime and greater than the sum of the absolute values of the non-constant coefficients. Then $f$ is irreducible.
Proof. The condition on the coefficients means that $f$ has no roots in the unit circle. On the other hand, since $f(0)$ is prime, every irreducible factor of $f$ has constant term $\pm 1$ except one, which will have constant term $\pm p$, and some the roots of the latter types of factor must lie in the unit circle; contradiction.
And we can find infinitely many $k$ such that $f(0) - k$ is a large prime. This proof should extend to finite extensions $K$ of $\mathbb{Q}$, since there are infinitely many primes that remain prime over the Galois closure of $K$ by Frobenius. (Although this is probably overkill.)
First, here is another reason that hasn't been supplied a reason that a field could have the property that no polynomial is co-finite. If the field is $\mathbb{R}$ and a polynomial $f(x)$ has no real roots, then $f(x)+c$ doesn't either when $c$ is a small number. That's because the map from a set of roots in $\mathbb{C}$ to the corresponding polynomial is an open map, and $\mathbb{R}$ is a closed subset. I would suppose that there are other topological fields $k$ such that the algebraic closure $\overline{k}$ (or maybe some completion of it) has this open map property. [Edit: Actually GMS and DLS have already both suggested $p$-adic continuity arguments, which is a similar point about using topology.]
Second, it seems like the answers so far take the question the wrong away around. Let $f$ be a polynomial over a field $k$, and mark a set of values $A \subset k$. Suppose that you adjoin to $k$ some root of $f(x)-b$ for every $b \in k \setminus A$. Suppose that you keep doing that with the new field $k'$, and keep going forever to obtain a partial algebraic closure $\tilde{k}$. (It will not be the full algebraic closure because all extensions are bounded by $\deg f$.) Then does any $f(x)-a$ have a root in $\tilde{k}$, with $a \in A$? If not, then you have a counterexample. If this is unavoidable, then no counterexample is possible. The field $\tilde{k}$ seems far from unique as described. However, you could make a larger field by splitting $f(x)-b$ completely rather than by adjoining just one root.
[Edit: Removed a not particularly original thought about an obstruction coming from Galois groups.]
What I was really trying to do with the second point was not to propose a new construction, which I don't have, but rather to restate the question in an interesting way. The idea, in other words, is to attack a specific polynomial form $f(x) - c$ rather than to attack a specific field. Arguably the field is negotiable, because you can keep adjoining a missing root of each $f(x) - c$ when you want $f(x)$ to take the value $c$.
A first step, suggested by the failed example $f(x) = x^n$, is to make an equivalence relation $a \sim b$ if $f(x) - a$ and $f(x) - b$ are both irreducible and adjoining one root produces isomorphic fields. If the equivalence class of $a$ is infinite, then it can't work as an avoided value.
For example, all cubic polynomials are equivalent (up to adding a constant or a linear change of variables) to $x^3$, $x^3+x$, and $x^3+px$ where $p$ is some fixed non-square. Say $p=1$ in the second case. In the field $F(x)$ with $x^3 + px + q$, any element $y = 3x^2+\alpha x+2p$ has trace 0 and minimal polynomial $y^3+(9\alpha q+\alpha^2p-3p^2)y+r$ (according to Maple). I think that there are many ways to choose $\alpha$ to make the linear coefficient a square times $p$, and thus get $z^3+pz+c$ back again after rescaling $y$ to make $z$. If this is correct, then $f(x) = x^3+px$ is eliminated from contention and thus cubic polynomials are eliminated from contention. (But note that my brief calculation for the last step assumes that the characteristic is not $2$.)
I wouldn't know how to show how any of these $f$-equivalence classes are ever finite. If that did happen, you would then want to look at whether two or more field extensions at attained values would capture a field extension at a value that you want to avoid.
Here's a strategy that I've been toying with. It seems unlikely to me that it works, but perhaps it'll inspire someone to have a better idea. Try to arrange a field $K$ whose Galois group has trivial pro-$5$ Sylow subgroup but nontrivial pro-$p$ Sylow subgroup for $p=2,3$. Let $f$ be the product of an irreducible quadratic and an irreducible cubic over $K$. Since there are no irreducible quintics over $K$, for each $a \in K$, the polynomial $f-a$ either has a root, or factors as an irreducible quadratic times an irreducible cubic. We'd be done if we can arrange for the latter to occur only finitely many times. But this seems like a stretch....
Regarding Pete question on $p$-adic fields.
I think I have an argument that should work in any non-archimedian local field. I'll work it out over $Q_p$ just for simplicity.
First we may assume that $0$ is not in the image of the polynomial $f$. By the hypothesis there is $N>0$ such that for all integer $n>N$ we have that $p^{n}$ is in the image of $f$. Let $\alpha_n \in Q_p$ such that $f(\alpha_n)=p^n$. Since $||\cdot||_p$ is non-archimedian we see that the sequence $(\alpha_n)$ is bounded. Now, let $(\alpha_{n_k})$ be a convergent subsequence of $(\alpha_n)_{n >N}$, which exists since the $\alpha_n$'s are bounded. If $\alpha$ is the limit of $(\alpha_{n_k})$ then $f(\alpha)=0$ which is a contradiction.
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.
Here is a finite-ness result for $p$-adic fields. Let $k$ be a p-adic field. One knows that there are only finitely many square classes of $k$ -- that is $k^{\times} / k^{\times 2}$ is finite (as a set). A similar situation should hold for $p^{th}$-classes of $l$-adic fields. As a concrete example, we know that for $k = \mathbb{Q}_2$, the square classes $k^\times/k^{\times 2}$ are generated by $2,-1,5$, in particular, $k^{\times} / k^{\times 2} \cong (\\mathbb{Z}/2)^{\times 3}$.
This doesn't answer the question at all, but its a finitely-generated analogue of the finite-ness result you want.
Suppose such a polynomial exists. Consider it as a morphism $f:\mathbb A^1_k \to \mathbb A^1_k$. You can compactify it as $g:\mathbb P^1_k\to \mathbb P^1_k$ by setting $g(\infty) = \infty$. This is a proper morphism. Its image is either $\mathbb P^1_k$ or a finite scheme $S$ over $k$. You have a contradiction.
Am I missing something?
