# Can a non-surjective polynomial map from an infinite field to itself miss only finitely many points?

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.

-
Correct me if I'm wrong, but can't you even say that if you have an embedding of an algebraically closed field into $k$, no such polynomial exists? –  Harrison Brown Nov 25 '09 at 15:45
Why? I'm thinking of some kind of inverse limit of extensions of function fields over algebraic closure of finite field might occidentally work. –  Dror Speiser Nov 25 '09 at 16:07
Why? Because I was being stupid and misread the question :D. I don't really see why that construction has any better chance than any other, but I concede it might work. –  Harrison Brown Nov 25 '09 at 16:10
I am deeply impressed with the strong interest MOers show in the problem. So far we have 10 answers, 57 comments, 28 upvotes, and 11 favorites. We have no final answer but I guess I have to accept an answer because the bounty is going to end. I'll choose to accept the answer with the highest number of upvotes, albeit that answer was given before the bounty was released. Accepting the answer doesn't mean that I want to discourage people from further thinking about the problem. I just don't want to waste the bounty. The case of Hilbertian fields seems to be the current state of knowledge. –  Philipp Lampe Dec 4 '09 at 10:39

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.

-
Doesn't seem like p-adic fields stand much of a chance, since if y isn't in the image of f, neither can be anything sufficiently close to y. –  D. Savitt Nov 25 '09 at 20:38

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)

-
What family is "3. the family" referring to? –  Greg Martin Nov 14 '13 at 20:20
The family of Hilbertian fields –  Lior Bary-Soroker Nov 15 '13 at 8:41

Recently, I have shown with Hendrik Lenstra that there is no example when $k$ satisfies the following two properties:

1. the absolute Galois group of $k$ is procyclic and $k$ is perfect;
2. every geometrically irreducible normal projective curve over $k$ has infinitely many $k$-points.

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:

1. Consider $L=k(x) \supseteq K=k(f(x))$, a finite extension of function fields over $k$ (or for the geometers, a map from $\mathbb{P}_k^1 \to \mathbb{P}_k^1$) and it is a matter of counting how many $k$-points lie above a $k$-point of $K$ in $L$.
2. Use Galois theory to study the extension $L/K$. Suppose $M/K$ is finite Galois with group $G$ such that $X=\mathrm{Hom}_K(L,M)$ is not empty. Then to every rational point $P$ of $K$ we can associate a Frobenius element $(P,M) \in G$ (using 1).
3. An unramified point $P$ has no rational points above it iff $X^{(P,M)} = \emptyset$ (there is a statement for the ramified case as well). Suppose that this is the case for $P$. Hence it is enough to show that there are infinitely many rational points $Q$ of $K$ with $(Q,M)=(P,M)$.
4. Give a version of the Chebotarev density theorem for such fields $k$: There is a geometrically irreducible function field over $k$ such that its rational points `correspond' to the rational points $Q$ of $K$ with $(Q,M)=(P,M)$.
5. From assumption 2 and step 4 it follows that there are infinitely many points with the specific Frobenius element from step 3. Hence the result follows.
-
Actually, with some changes I can prove the statement for a field $k$ with 1. $k$ is perfect 2. every geometrically irreducible normal projective curve over k has infinitely many k-points. The proof uses the statement that the exact sequence with the decomposition group and the inertia group splits. –  Michiel Kosters Jan 21 at 14:57
Koenigsmann proves this result in a more general setting. Namely he proves that if $K$ is ample, then the image of an irreducible separable polynomial of degree at most $2$ is NOT cofinite. See the argument in arXiv:1106.1310 after Conjecture 6.1. –  Lior Bary-Soroker Feb 4 at 11:38
I forgot to say that a field $K$ is called ample if for every smooth geometrically connected curve $C$ over $K$, the set of rational points $C(K)$ is either empty or infinite. This property is clearly satisfied for your fields, and also for other fields like complete fields, etc. –  Lior Bary-Soroker Feb 4 at 11:39

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.)

-
Or, the (order-based) argument for R works also for Q, isn't it ? –  Guillaume Aubrun Nov 26 '09 at 8:00
I'm not sure what you mean by the order-based argument. The argument for R I'm thinking of is that f(R) is connected, but this fails horribly for Q. –  Qiaochu Yuan Nov 27 '09 at 21:31

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.

-
I have the feeling that your $\tilde k$ is Hilbertain, if $k$ is (and $A$ is sufficiently large). Here is the rough uncompleted idea: choose a partition of $A$ into two subsets say $A_1$ and $A_2$. Let $M_i$ be the compositum of all splitting fields of $f(X)-a$, $a\in A_i$. I think that if $A$ is sufficiently large, and $A_1$ and $A_2$ are chosen wisely, we could get that $\tilde k$ is not contained in neither $M_1$ nor $M_2$. But clearly it is contained in $M_1M_2$. Thus by Haran's diamond theorem (see link in my post) $\tilde k$ is Hilbertian. –  Lior Bary-Soroker Nov 30 '09 at 14:12
By construction, $f(x)-c$ has a root cofinitely in $\tilde{k}$. So are you telling me that $f(X)-T$ is reducible?? –  Greg Kuperberg Nov 30 '09 at 14:20
1) From comments below you'll see you are not the first or even second to propose trying to build such a construction. 2) Other answers certainly do address this reason for a polynomial not working over the reals. 3) Restating the problem is not an answer. –  Dror Speiser Nov 30 '09 at 14:49
Greg, how did you understand from what I wrote that $f(X) - T$ is reducible? Clearly it is irreducible. What I'm saying is that your $\tilde k$ is Hilbertian, i.e., there exists $a\in \tilde k$ such that $f(X) - a$ is irreducible. –  Lior Bary-Soroker Nov 30 '09 at 15:06
(1) My main point is that what everyone else (including me at first) meant merely as a construction is more properly understood as a tangible restatement of the problem. (2) My first point is about topology, with R meant only as an example; but I see that GMS made a similar p-adic argument and I apologize that I missed it. (3) If a popular construction is promoted to an equivalent problem statement, then hopefully that is a useful remark. I would hope that we have room for those if no one solves the problem? –  Greg Kuperberg Nov 30 '09 at 15:10
show 1 more comment

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.

-
Since non-archimedian local fields are just finite extensions, this is quite elementary, and the argument doesn't work for infinite extensions, which are the only interesting cases. –  Dror Speiser Nov 27 '09 at 10:59
when you say "non-archimedian local fields are just finite extensions" I don't quite follow what you mean. Finite extensions of what? I hope you are not thinking finite extensions of a fixed field. Now $Q_p$ and $F_p((T))$ both are local fields and they can't be extensions of a common field. Now, my point is that for any complete field with a compact unit ball -e.g R, Q_p F_p((T))- the argument described above works. I'd like to understand what is what you mean by extensions –  Guillermo Mantilla Nov 27 '09 at 21:19
Since the field needs to have f^(-n)(a) for all a, it seems elementary that Q_p and F_p((T)) can't work, as well as any finite extension of either. R has other trivial reasons. The argument does not work for the field Q_p adjoined with all roots of p: even though the absolute value of nth-root(p) converges to 1, there is no convergent subsequence. I'm not sure how to treat infinite extensions, is there a way to get the argument back working? (or does it actually work still and I don't see it?) –  Dror Speiser Nov 28 '09 at 23:38
The proof for R, Q_p and F_p((T)) and any local field(what you call finite extensions) is basically the same...the unit ball is compact...for infinite extensions of them there is no way to make the argument work as your example shows(balls are not sequentially compact). Taking about your example, do you have a proof that work with it? I was thinking in working out the field K=Q_p^{unr}. I think f(x)=x^p misses only countable points on K, but it might be a dead end. –  Guillermo Mantilla Nov 29 '09 at 22:19
f(x)=x^p misses everything whose valuation is not a multiple of p. –  S. Carnahan Nov 30 '09 at 3:21
show 2 more comments

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.

-
Is Fp a finite field as well? Then no, there does not exist an infinite sequence of finite fields Fq of same characteristic such that Fq is smaller in cardinality than Fp. So T itself is finite, and the field constructed will not be infinite. –  Dror Speiser Nov 30 '09 at 4:56
No, (i) just means that there is an infinite sequence of primes. The argument is correct, I think -- in fact, I had thought of something very similar myself a few days ago. If (ii) and (iii) hold, then you get an infinite "pseudofinite" field K and a polynomial P such that K \setminus P(K) is finite and nonempty. The trouble is that it is not at all clear that a sequence (p,f_p) exists satisfying (ii) and (iii) above. It seems doubtful to me, in fact. –  Pete L. Clark Nov 30 '09 at 5:27
It's an interesting approach. But I don't see why such a sequence exsists either. –  Philipp Lampe Nov 30 '09 at 5:46
@Pete: There does not exist such a sequence. A non-surjective polynomial of degree n over a finite field of q elements has image smaller than q-(q-1)/n. If you bound n and m, then for all but a finite number of finite fields, the bound is smaller than q-m. This was proved by D. Wan in "A p-adic lifting lemma and its applications to permutation polynomials". I found this immediately in the second result of the google search "size of polynomial finite fields". –  Dror Speiser Nov 30 '09 at 15:20
Wan's result is very impressive: I didn't know about it (although the record reflects that I was inclined in that direction, for whatever little that's worth). So Wan's argument uses the key "model-theoretic fact" that a polynomial over a finite field is injective iff it is surjective. (This is a tongue-in-cheek allusion to the standard model-theoretic proof that injective polynomial maps from C^n to C^n are surjective.) Altogether this is turning out to be quite a fascinating question... –  Pete L. Clark Dec 1 '09 at 4:12
show 6 more comments

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.

-
Does this generalize at all to maps $f_k \colon V(k) \rightarrow W(k)$, where $V,W$ are $k$-varieties (or $k$-schemes) and where $f_k$ is induced by a morphism $f \colon V \rightarrow W$? (And what if $f$ is a rational map?) –  René 21 hours ago

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.

-
A similar result does hold for $p$th powers in $\ell$-adic fields (hint: use exp and log to analyse a neighbourhood of $1$ in $k^\times$ and relate it to a neighbourhood of $0$ in $k$) but it doesn't answer the question somehow, because it's not the size of the quotient that is the obstruction, it's the size of the cosets, all of which are infinite if $k$ is. –  Kevin Buzzard Nov 30 '09 at 19:27
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.