Solving some affine equations over finite fields (Q1994968): Difference between revisions

Fix a prime \(p\) and a finite field \(\mathbb{F}_{p^n}\) of characteristic \(p\). Let \(k\) and \(\ell\) be positive integers with \(\ell\) dividing \(k\). Define \[ T_\ell^k(X) := \sum_{i = 0}^{k/\ell-1} X^{p^{\ell i}} \ \text{and} \ S_\ell^k(x) := \sum_{i = 0}^{k/\ell-1} (-1)^i X^{p^{\ell i}}. \] These polynomials are visibly related to one another. In this paper, the authors find all solutions in \(\mathbb{F}_{p^n}\) to affine equations of the form \(T^k_\ell(X) = a\) and \(S_\ell^k(X) = a\), where \(a \in \mathbb{F}_{p^n}\). Their argument is entirely elementary, and proceeds as follows. Recall that the \(p\)-power map \(x \mapsto x^p\) is linear over \(\mathbb{F}_{p^n}\). Then as \(T_\ell^k\) and \(S_\ell^k\) are both linear combinations of compositions of the \(p\)-power map with itself, they are also linear maps over \(\mathbb{F}_{p^n}\). Thus we are in essence attempting to solve a nonhomogeneous linear algebra problem. We may find all solutions to our equations by first finding the kernels of the maps \(x \mapsto T^k_\ell(x)\) and \(x \mapsto S_\ell^k(x)\), and then finding particular solutions to the equations \(T_\ell^k(X) = a\) and \(S_\ell^k(X) = a\). Elementary computations yield identities like \(T_\ell \circ S^{2 \ell}_\ell = S^{2k}_k\) (see Lemma 1.1), and we may leverage these interrelationships to express the kernel of \(T_\ell^k\) using \(S_\ell^k\), and vice versa. Now, for any \(a \in \mathbb{F}_{p^n}\) fixed, we may check whether the equations \(T^k_\ell(X) = a\) and \(S_\ell^k(X) = a\) have solutions by checking if \(a\) is a root of an explicitly given polynomial, which depends on our choice of parameters for the affine equation (for instance, the polynomial depends on whether \(k / \ell\) is even or odd). If our affine equation has a solution, we can compute that solution in terms of a nontrivial solution to an equation like \(T_d^n(X) = 1\), where \(d = \gcd(n,k)\) The readers are advised that in Lemma 1.1, the condition \(\ell | m\) should be \(m | \ell\) both times it occurs.