Let $p$ be a prime number, $n$ a natural number which is not divisible by $p$, and $\mathbb{K}$ is a finite field, with $char(K) = p, |K| = p^n, 1_{\mathbb{K}}$ unity element and $\widehat{0} = 0_{\mathbb{K}}.$ For every $m \in \mathbb{N}^{*}$ we note $ \widehat{m} = \underbrace{1_{\mathbb{K}} + 1_{\mathbb{K}} + \ldots + 1_{\mathbb{K}}}_{m \text{ times}} $ and define the polynomial \[ f_m = \sum_{k = 0}^{m} (-1)^{m - k} \widehat{\binom{m}{k}} X^{p^k} \in \mathbb{K}[X]. \] a) Show that roots of $f_1$ are $ \left\{ \widehat{k} | k \in \{0,1,2, \ldots , p - 1 \} \right\}$. b) Let $m \in \mathbb{N}^{*}.$ Determine the set of roots from $\mathbb{K}$ of polynomial $f_{m}.$
Problem
Source: Romania National Olympiad 2023
Tags: polynomial, field, finite fields, superior algebra
14.04.2023 06:09
What spam?
14.04.2023 06:49
They are different problems. This is all valid... Just bump it Not spam. Just problems...
14.04.2023 18:35
a) Notice that $f_1=X^p-X = X(X-\widehat{1})\dots (X-\widehat{p-1})$ by Fermat's little theorem. b) Consider the function $\varphi :\mathbb{F}_p[X]\rightarrow\mathbb{F}_p[X]$ given by $$\varphi(a_nX^n + \dots + a_1X + a_0)=a_nX^{p^n}+\dots + a_1X^p + a_0.$$Then using the Frobenius endomorphism, we see that $\varphi$ is in fact a ring homomorphism, from $(\mathbb{F}_p[X],+,\cdot)$ to $(\mathbb{F}_p[X],+,\circ)$. Indeed, $$\varphi(P)\circ\varphi(Q)=\sum_{i=0}^n a_i\left(\sum_{j=0}^m b_j X^{p^j}\right)^{p^i}=\sum_{i=0}^n a_i\sum_{j=0}^m b_j X^{p^{i+j}} =\sum_{k=0}^{m+n} \left(\sum_{i+j=k} a_i b_j\right)X^{p^k} =\varphi(P\cdot Q).$$Also $\varphi(P)+\varphi(Q)=\varphi(P+Q)$ however we won't need this. Now observe that $f_m=\varphi((X-1)^m)=\varphi((X-1)^{m-1})\circ\varphi(X-1)=f_{m-1}(X^p-X)$. We argue by induction that the set of roots in $\mathbb{K}$ of $f_m$ is exactly $\mathbb{F}_p$. Indeed, the case $m=1$ was proved above, so suppose it's true for some $m-1\geq 1$. Then if $\alpha$ is a root of $f_m$, it means that $\alpha ^p-\alpha$ is a root of $f_{m-1}$, and thus there is some $k\in\{0,1,\dots ,p-1\}$ such that $\alpha^p = \alpha +\widehat{k}$. Inductively, $$\alpha^{p^i}=(\alpha+\widehat{k})^{p^{i-1}}=\alpha^{p^{i-1}}+\widehat{k}=\dots =\alpha + i\widehat{k}.$$However, in any finite field of order $p^n$, $\alpha^{p^n}=\alpha$, and thus $n\widehat{k} = \widehat{0}$, implying that $\widehat{k}=\widehat{0}$ (since $\gcd(n,p)=1$). This means that $\alpha^p=\alpha$, i.e. $\alpha$ is a root of $f_1$, finally implying that $\alpha\in\mathbb{F}_p$, exactly what we wanted to prove.
14.04.2023 20:12
Redacted @Below I see now, thank you!
14.04.2023 21:18
You are right, however the original problem asks us to find $\mathbb{F}_{p^n}\cap \mathbb{F}_{p^p}=\mathbb{F}_{p^{\gcd(n,p)}}=\mathbb{F}_p$, so for $m=p$ the problem is somewhat simpler.
17.04.2023 06:36
Here is a possibly more motivating way to see that $f_m(x)$ is a polynomial in $x^p-x$: First, note if $f_m(x)=f_m(y)=0$, then $f_m(ax+by)=0$ for all $a,b\in \mathbb{F}_p$. Therefore, the set of roots of $f_m$ (call $R$) form a vector space. Therefore, let $S = R / \mathbb{F}_p$, then $$f_m(x) = \prod\limits_{s\in S} \prod\limits_{j=0}^{p-1} (x-s-j) = \prod\limits_{s\in S} \left((x-s)^p-(x-s)\right) = \prod\limits_{s\in S} ((x^p-x)-(s^p-s))$$ We can verify that $f_m(x)=f_{m-1}(x^p-x)$. We induct on $m$ to show that the only roots of $f_m(x)$ in $\mathbb{F}_{p^n}$ for any $p\nmid n$ is $\mathbb{F}_p$. Suppose $f_m$ has a root in $\mathbb{F}_{p^n}$, call $r$. Then by closure, $r^p-r\in \mathbb{F}_{p^n}$. By inductive hypothesis, $r^p-r\in \mathbb{F}_p$. If $r^p-r=0$ then $r\in \mathbb{F}_p$. Otherwise, I will prove that the minimal polynomial of $r$ has degree $p$, which means it must be in $\mathbb{F}_{p^p}$, and it is also in $\mathbb{F}_{p^n}$, which means it is in $\mathbb{F}_{p^p} \cap \mathbb{F}_{p^n} = \mathbb{F}_p$ (say by analyzing gcd of splitting polynomial) This boils down to the classic problem that $x^p-x-a$ is irreducible. Factor into irreducibles, say $f_1(x) f_2(x) \cdots f_k(x) = f_1(x+t) f_2(x+t) \cdots f_k(x+t)$ (where each is a nonconstant poly). Then we can see that our multiset $\{f_1(x), \cdots, f_k(x)\}$ is $\{f_1(x+t), \cdots, f_k(x+t)\}$ in some order. Thus $f_1(x)=f_{j_1}(x+1) = \cdots = f_{j_{p-1}}(x-1)$, which implies $k\ge p$ and irreducibles are linear i.e. $a=0$.
24.07.2024 03:42
Related to USA TST 2016/3. Let $\mathbb{N}$ denote the set of natural numbers, including $0$. Let $R$ be the ring consisting of the set of $\mathbb{K}$-polynomials \[ \left\{a_k x^{p^k}+a_{k-1} x^{p^{k-1}}+\cdots+a_1 x^p+a_0x\mid k\in\mathbb{N};\,a_0,\,\ldots,\,a_k\in\mathbb{K}\right\}, \]with addition $+$ and multiplication $\circ$ (function composition). It is easy to check that $R$ is a ring with additive identity $0$ and multiplicative identity $x$. It is not hard to see that $\mathbb{K}[x]$ and $R$ are isomorphic with isomorphism $\Psi\colon\mathbb{K}[x]\to R$ given by \[ a_k x^k+\cdots+a_1 x+a_0\mapsto a_k x^{p^k}+\cdots+a_1 x^p+a_0x. \]Note that $f_m=\Psi((x-1)^m)$. Claim. For $m\in\mathbb{Z}^+$, $\gcd(x^n-1,(x-1)^m)=x-1$ in $\mathbb{K}[x]$. Proof. It suffices to find the number of factors of $x-1$ in $x^n-1$. Since $p\nmid n$, it follows that $1$ is not a root of $x^{n-1}+\cdots+x+1$. Thus $x^n-1=(x-1)(x^{n-1}+\cdots+x+1)$ has one factor of $x-1$, as desired. $\square$ By Bezout's identity, there exists $A,\,B\in\mathbb{K}[x]$ for which $A(x)(x^n-1)+B(x)(x-1)^m=x-1$. Then \[ C(x)\circ(x^{p^n}-x)+D(x)\circ f_m(x)=x^p-x \]where $C:=\Psi(A)$ and $D:=\Psi(B)$. Since $C$ and $D$ have no constant terms, $0$ is a root of both of them. If $\alpha\in\mathbb{K}$ is a root of $f_m$, then $\alpha^{p^n}=\alpha$. Hence \[ \alpha^p-\alpha=C(\alpha^{p^n}-\alpha)+D(f_m(\alpha))=C(0)+D(0)=0 \]so $\alpha\in\mathbb{F}_p$. Conversely, by the binomial theorem, all elements of $\mathbb{F}_p$ are roots of $f_m$. Thus $\boxed{\mathbb{F}_p}$ is the set of roots of $f_m$ in $\mathbb{K}$. $\square$