Take the 2-minute tour ×

Let $F$ be a finite field. Let $F[X]$ and $F[[X]]$ denote the ring of polynomials and power series over $F$, respectively. I'm trying to show a statement like the following:

Fix a $d > 0$. Let $g\in F[[X]]$. If there exists a set $C\subseteq F[X]$ of polynomials (with no constant term) of degree at most $k$ such that for all $c\in C$, $g(c)$ -- $g$ composed with $c$ -- is a degree $kd$ polynomial, and $|C|$ is "large" (some function of $k$, $d$, and $|F|$), then $g$ must actually be a polynomial.

I'm trying to beat the bound that one might be able to get via Schwartz-Zippel, where $|C| > kd |F|^{k-1}$ (where $kd \ll |F|$).

What bounds on $|C|$ can we get?

Thank you, Henry

share|improve this question
I should point out that you don't need $d$, as the set of degree-$k$ polynomials is finite, so $d$ is just the largest value of $\operatorname{deg} g(c) / k$. And $kd$ is better interpreted as just "the highest degree of some $g(c)$". –  Ryan Reich Jul 27 '12 at 4:36
Thanks for pointing this out Ryan. In this case, I have a specific $d$ in mind: if $g(c)$ has degree greater than $kd$, then I do not wish to consider such a $c$. The bound I'm seeking on $|C|$ may depend on $d$. I will edit the problem statement to make this clearer. –  Henry Yuen Jul 27 '12 at 4:50
The easy lower bound is $|F|^{k/2}$, coming from $g(x) = \sqrt{1+x}$. Then $g \circ c$ is a polynomial whenever $c$ is of the form $h(x)^2-1$. My guess is that this is close to optimal. –  David Speyer Jul 29 '12 at 18:45
@David: what do you mean by $g(x) = \sqrt{1 + x}$ if $F$ has characteristic $2$? –  Qiaochu Yuan Jul 30 '12 at 1:02
I don't :). In that case, $y^2=1+x$ doesn't have a root in $k[[x]]$. Probably the root of $y^2+y=x$ with $y(0)=0$ would make a good substitute. –  David Speyer Jul 30 '12 at 2:38

1 Answer 1

up vote 6 down vote accepted

I claim that, if $g(x) \in k[[x]]$ is not a polynomial, then $g \circ c$ is a polynomial for at most $|F|^{k/2}$ polynomial $c$ of degree $\leq k$. We will always use the letter $c$ to represent a polynomial with $c(x)=0$.

Case 1: $g$ is transcendental over the field $k(x)$. In this case, I claim that $g \circ c$ is a polynomial only when $c$ is $0$. Proof: Suppose that $g(c(x)) = h(x)$ for some polynomial $h$. Then there is a polynomial relation $F(c(x), h(x))=0$ for some polynomial $f$. Set $G(x) := F(x, g(x))$. By hypothesis, $G \neq 0$, but $G(c(x))=0$. The only way this can happen is if $c=0$.

Case 2: $g$ is algebraic over $k(x)$. Let $F(x,g(x))=0$ be the minimal polynomial relation between $x$ and $g$. Let $A$ be the ring $k[x,y]/F(x,y)$. At this point I really, really want to use the language of algebraic geometry. If you aren't happy with this, I'll try to convert into commutative algebra, but it will be harder to write and, in my opinion, harder to read. My goal is the following claim:

Claim: If there is any nonzero $c$ such that $g \circ c$ is polynomial, then the ring $A$ is a subring of $k[u]$ for some $u \in \mathrm{Frac}(A)$.

Example: Let $g = (1+x)^{3/2}$. Then $F(x,y) = y^2 - (1+x)^3$. Letting $u = \frac{y}{1+x}$, we have $A \subseteq k[u]$, since $x=u^2-1$ and $y=u^3$.

Proof: $\mathrm{Spec}(A)$ is an algebraic curve. Since $F$ is the minimal polynomial relation, it is irreducible. Let $X$ be the normalization of $\mathrm{Spec}(A)$.

Let $h=g \circ c$. Now, $t \mapsto (c(t), h(t))$ is a map $\mathbb{A}^1 \to \mathrm{Spec}(A)$ and, since $c$ is nonconstant, is a nonconstant map. Since $\mathbb{A}^1$ is normal, this lifts to a nonconstant map $\mathbb{A}^1 \to X$. So $X$ has genus zero, and has at most one puncture. Since $X$ is affine, it has at least one puncture. So $X \cong \mathbb{A}^1$. In other words, the normalization of $A$ is $k[u]$, so we get an embedding $A \subseteq k[u]$ for some $u \in \mathrm{Frac}(A)$. $\square$

From now on, we will assume that there is some nonzero $c$ for which $g \circ c$ is polynomial. So we may assume that there is an embedding $A \subseteq k[u]$, with $\mathrm{Frac}(A) = k(u)$, and we fix such an embedding. Let $x = a(u)$ and $g(x) = b(u)$, for some polynomials $a$ and $b$. If $a$ has degree $1$, then $u$ is a linear function of $x$ and we can write $g$ as a polynomial in $x$, contradicting your hypothesis. So $\deg a \geq 2$. I claim that there are only $|F|^{k/\deg a}$ values of $c$ for which $g \circ c$ is a polynomial. Specifically, the polynomials $c$ of the form $a(\phi(t))$, where $\phi$ is a polynomial of degree $k/\deg a$.

Why is this? Well, if $c(t) = a(\phi(t))$, then $g(c(t)) = b(\phi(t))$ and is thus a polynomial. Conversely, if we have some $c$ such that $g \circ c$ is polynomial then, as discussed above, we get a map from the normalization of $A$ to $k[t]$. Take $\phi$ to be the image of $u$.

share|improve this answer
Thanks David! This will take me a little while to parse, so i might add follow up questions in the comments. But for now I accept this! –  Henry Yuen Jul 30 '12 at 14:37

Your Answer


