# The Ax-Grothendieck theorem

The Ax-Grothendieck theorem says the following: Let $$f: \mathbb{C}^n \to \mathbb{C}^n$$ be a polynomial function. If it’s injective, then it’s surjective as well.

Here’s how to prove it:

1. The statement can be formulated as a first-order statement in the language of fields
2. If a statement like that fails for $$\mathbb{C}$$, there’s a disproof in the first-order theory of algebraically closed fields of characteristic zero.
3. Such a proof is finite, so it only uses finitely many of the assumptions $$p \neq 0$$ - hence the theorem also fails in algebraically closed fields of sufficiently high characteristic.
4. Hence it fails in the algebraic closure of $$\mathbb{F}_p$$. The specific counterexample is in some finite extension of $$\mathbb{F}_p$$, which is a finite field. But clearly the theorem is true for finite fields, just by counting.

I think this is a pretty cool proof - it uses model theory in a really surprising way, and the step where you use the fact that proofs are finite is just totally bonkers.

## First-order logic and completeness

Recall that first-order logic works with statements built up out of the logical connectives $$\wedge, \vee, \neg, \Rightarrow \bot, \top, \forall, \exists, =$$. The language of fields augments these symbols with $$+, -, \cdot, 1, 0$$ (it’s really just the language of commutative rings - being a field just means that additional axioms hold).

A statement in the first-order language of fields could be something like this:

$$\forall a,b: \neg (a = 0) \Rightarrow \exists x: a\cdot x + b = 0$$

This statement says that all nonconstant linear polynomials have a solution, which is true.

We could also write down a statement like

$$\forall a, b, c, d, e: \neg (a = 0) \Rightarrow \exists x: a x^4 + bx^3 + cx^2 + dx + e = 0$$

This says that all fourth-order polynomials have a root, which is not always true, but true sometimes, like in $$\mathbb{C}$$.

Similarly, we can form a statement $$R_n$$ for all $$n \in \mathbb{N}$$, saying that all $$n$$th order polynomials have a root. Note that the conjunction of all these statements is not a first-order statement in itself - we can’t take conjuctions of infinitely many statements, and there’s no way to quantify over all polynomials in the theory of fields.

Similarly, we can form statements like $$1+1 \neq 0$$. This is also true in $$\mathbb{C}$$, but fails in fields of characteristic $$2$$. We can form statements $$C_n$$ for all $$n$$, saying that $$n \neq 0$$ - that the field does not have characteristic $$n$$.

The theory of algebraically closed fields of characteristic zero is the theory consisting of the axioms of a field augmented with the statements $$C_n$$ and $$R_n$$ for all $$n$$. A model of this theory is precisely an algebraically closed field of characteristic zero (hence the name).

Now here is a highly nontrivial fact about this theory: it is complete. This means that any statement expressible in the first-order language of fields is either provable or disprovable in it. This means that, from the perspective of first-order logic, there are really no differences between fields of this type - even though there are of course many different such fields, they have the same first-order properties.

## Ax-Grothendieck in first order

We want to phrase the Ax-Grothendieck theorem as a first-order statement. It turns out this isn’t quite possible, because we can’t quantify over “all degree $$d$$ polynomials” or “all $$n \in \mathbb{N}$$”. Therefore we instead formulate the statement $$P(n,d)$$: “Any polynomial function $$f : \mathbb{C}^n \to \mathbb{C}^n$$ of degree at most $$d$$ is surjective if it’s injective”. Then the Ax-Grothendieck statement says that $$P(n,d)$$ holds for all $$n \geq 1, d \geq 0$$.

(By the way: by “polynomial $$\mathbb{C}^n \to \mathbb{C}^n$$”, I mean a function where each coordinate is an $$n$$-variable polynomial)

How does $$P(n,d)$$ look as a first-order formula? It’s quite complicated - mostly because a degree $$d$$ polynomial like $$f$$ involves a large number of coefficients. The main point is that there is a definite number of coefficients, once $$n$$ and $$d$$ is fixed, and so we can write “for all choices of coefficients for $$f$$…” in first-order logic. For instance, if $$d = 2, n=1$$, this looks like $$\forall a_{11},a_{12},a_{21},a_{22},b_1,b_2 \dots$$ Here $$a_{12}$$ is the coefficient for $$x_1$$ in the second coordinate polynomial of $$f$$, and so on.

Now of course we can also make sense of injectivity: it’s just the statement $$f(x_1,\dots x_n) = f(x'_1, \dots x'_n) \Rightarrow x_1=x'_1 \wedge \dots \wedge x_n = x'_n$$ - where the equality on the left of the implication is shorthand for a complicated expression involving the coefficients of $$f$$.

And we can make sense of surjectivity: it just means $$\forall y_1 \dots y_n, \exists x_1, \dots x_n: f(x_1, \dots x_n) = (y_1, \dots y_n)$$

Hence we have all the ingredients to make sense of $$P(n,d)$$.

## Finishing up the proof

We now have most of the ingredients to fill out the proof above. Since Ax-grothendieck is a (family of) first-order statements, if it fails, there is a disproof in the first-order theory of algebraically closed characteristic zero fields. To be specific, if Ax-Grothendieck is false, then $$P(n,d)$$ is false for some specific $$n,d$$, and hence there is a disproof of that statement, i.e a proof of $$\neg P(n,d)$$.

Observe that such a proof is finite. Hence it can use at most finitely many of the statements $$C_n$$. Hence for $$p$$ large enough (larger than any $$n$$ where $$C_n$$ is used in the proof), Ax-Grothendieck fails for algebraically closed fields of characteristic $$p$$ - like the algebraic closure of $$\mathbb{F}_p$$. (How do we know it fails? We have a proof that it fails!) Hence there exists some polynomial function $$f: \overline{\mathbb{F}_p}^n \to \overline{\mathbb{F}_p}^n$$ which is injective and not surjective. But now we can take the algebraic extension of $$F_p$$ by all the coefficientsof $$f$$ and the coordinates of a point $$y \in \overline{\mathbb{F}_p}^n$$ which is not in the image. Call this extension $$L$$. Then $$f: L^n \to L^n$$ is a well-defined injective polynomial which is not surjective. And since $$L$$ is a finite extension of a finite field, it’s finite. But then we clearly have a contradiction: injective fuctions between finite sets of the same cardinality are bijections, just by counting.

This concludes the proof.