Skip to main content
MathOverflow

Return to Question

deleted 75 characters in body
Source Link
Henry Yuen
Henry Yuen
  • 2k
  • 15
  • 23

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 (it's not clear to me that one can even get a Schwartz-Zippel-type bound), where $|C| > kd |F|^{2k-1}$$|C| > kd |F|^{k-1}$ (where $kd \ll |F|$).

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

Thank you, Henry

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 (it's not clear to me that one can even get a Schwartz-Zippel-type bound), where $|C| > kd |F|^{2k-1}$ (where $kd \ll |F|$).

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

Thank you, Henry

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

clarification in problem statement.
Source Link
Henry Yuen
Henry Yuen
  • 2k
  • 15
  • 23

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" (for some fixedsome function of $k$, $d$), and $|C|$ is "large"$|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 (it's not clear to me that one can even get a Schwartz-Zippel-type bound), where $|C| > kd |F|^{2k-1}$ (where $kd \ll |F|$).

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

Thank you, Henry

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:

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 (for some fixed $d$), and $|C|$ is "large", then $g$ must actually be a polynomial.

I'm trying to beat the bound that one might be able to get via Schwartz-Zippel (it's not clear to me that one can even get a Schwartz-Zippel-type bound), where $|C| > kd |F|^{2k-1}$ (where $kd \ll |F|$).

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

Thank you, Henry

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 (it's not clear to me that one can even get a Schwartz-Zippel-type bound), where $|C| > kd |F|^{2k-1}$ (where $kd \ll |F|$).

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

Thank you, Henry

Source Link
Henry Yuen
Henry Yuen
  • 2k
  • 15
  • 23

Can formal power series become polynomial often, when composed with polynomials?

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:

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 (for some fixed $d$), and $|C|$ is "large", then $g$ must actually be a polynomial.

I'm trying to beat the bound that one might be able to get via Schwartz-Zippel (it's not clear to me that one can even get a Schwartz-Zippel-type bound), where $|C| > kd |F|^{2k-1}$ (where $kd \ll |F|$).

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

Thank you, Henry