13
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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)$". $\endgroup$
    – Ryan Reich
    Jul 27, 2012 at 4:36
  • $\begingroup$ 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. $\endgroup$
    – Henry Yuen
    Jul 27, 2012 at 4:50
  • 4
    $\begingroup$ 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. $\endgroup$ Jul 29, 2012 at 18:45
  • $\begingroup$ @David: what do you mean by $g(x) = \sqrt{1 + x}$ if $F$ has characteristic $2$? $\endgroup$ Jul 30, 2012 at 1:02
  • $\begingroup$ 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. $\endgroup$ Jul 30, 2012 at 2:38

1 Answer 1

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – Henry Yuen
    Jul 30, 2012 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.