Linearised polynomial

In mathematics, a linearised polynomial (or q-polynomial) is a polynomial for which the exponents of all the constituent monomials are powers of q and the coefficients come from some extension field of the finite field of order q.

We write a typical example as $${\displaystyle L(x)=\sum _{i=0}^{n}a_{i}x^{q^{i}},}$$ where each ${\displaystyle a_{i}}$ is in ${\displaystyle F_{q^{m}}(=\operatorname {GF} (q^{m}))}$ for some fixed positive integer ${\displaystyle m}$.

This special class of polynomials is important from both a theoretical and an applications viewpoint.^[1] The highly structured nature of their roots makes these roots easy to determine.

• The map x ↦ L(x) is a linear map over any field containing F_q.
• The set of roots of L is an F_q-vector space and is closed under the q-Frobenius map.
• Conversely, if U is any F_q-linear subspace of some finite field containing F_q, then the polynomial that vanishes exactly on U is a linearised polynomial.
• The set of linearised polynomials over a given field is closed under addition and composition of polynomials.
• If L is a nonzero linearised polynomial over ${\displaystyle F_{q^{n}}}$ with all of its roots lying in the field ${\displaystyle F_{q^{s}}}$ an extension field of ${\displaystyle F_{q^{n}}}$, then each root of L has the same multiplicity, which is either 1, or a positive power of q.^[2]

In general, the product of two linearised polynomials will not be a linearized polynomial, but since the composition of two linearised polynomials results in a linearised polynomial, composition may be used as a replacement for multiplication and, for this reason, composition is often called symbolic multiplication in this setting. Notationally, if L₁(x) and L₂(x) are linearised polynomials we define $${\displaystyle L_{1}(x)\otimes L_{2}(x)=L_{1}(L_{2}(x))}$$ when this point of view is being taken.

The polynomials L(x) and $${\displaystyle l(x)=\sum _{i=0}^{n}a_{i}x^{i}}$$ are q-associates (note: the exponents "qⁱ" of L(x) have been replaced by "i" in l(x)). More specifically, l(x) is called the conventional q-associate of L(x), and L(x) is the linearised q-associate of l(x).

Linearised polynomials with coefficients in F_q have additional properties which make it possible to define symbolic division, symbolic reducibility and symbolic factorization. Two important examples of this type of linearised polynomial are the Frobenius automorphism ${\displaystyle x\mapsto x^{q}}$ and the trace function ${\textstyle \operatorname {Tr} (x)=\sum _{i=0}^{n-1}x^{q^{i}}.}$

In this special case it can be shown that, as an operation, symbolic multiplication is commutative, associative and distributes over ordinary addition.^[3] Also, in this special case, we can define the operation of symbolic division. If L(x) and L₁(x) are linearised polynomials over F_q, we say that L₁(x) symbolically divides L(x) if there exists a linearised polynomial L₂(x) over F_q for which: $${\displaystyle L(x)=L_{1}(x)\otimes L_{2}(x).}$$

If L₁(x) and L₂(x) are linearised polynomials over F_q with conventional q-associates l₁(x) and l₂(x) respectively, then L₁(x) symbolically divides L₂(x) if and only if l₁(x) divides l₂(x).^[4] Furthermore, L₁(x) divides L₂(x) in the ordinary sense in this case.^[5]

A linearised polynomial L(x) over F_q of degree > 1 is symbolically irreducible over F_q if the only symbolic decompositions $${\displaystyle L(x)=L_{1}(x)\otimes L_{2}(x),}$$ with L_i over F_q are those for which one of the factors has degree 1. Note that a symbolically irreducible polynomial is always reducible in the ordinary sense since any linearised polynomial of degree > 1 has the nontrivial factor x. A linearised polynomial L(x) over F_q is symbolically irreducible if and only if its conventional q-associate l(x) is irreducible over F_q.

Every q-polynomial L(x) over F_q of degree > 1 has a symbolic factorization into symbolically irreducible polynomials over F_q and this factorization is essentially unique (up to rearranging factors and multiplying by nonzero elements of F_q.)

For example,^[6] consider the 2-polynomial L(x) = x¹⁶ + x⁸ + x² + x over F₂ and its conventional 2-associate l(x) = x⁴ + x³ + x + 1. The factorization into irreducibles of l(x) = (x² + x + 1)(x + 1)² in F₂[x], gives the symbolic factorization $${\displaystyle L(x)=(x^{4}+x^{2}+x)\otimes (x^{2}+x)\otimes (x^{2}+x).}$$

Let L be a linearised polynomial over ${\displaystyle F_{q^{n}}}$. A polynomial of the form ${\displaystyle A(x)=L(x)-\alpha {\text{ for }}\alpha \in F_{q^{n}},}$ is an affine polynomial over ${\displaystyle F_{q^{n}}}$.

Theorem: If A is a nonzero affine polynomial over ${\displaystyle F_{q^{n}}}$ with all of its roots lying in the field ${\displaystyle F_{q^{s}}}$ an extension field of ${\displaystyle F_{q^{n}}}$, then each root of A has the same multiplicity, which is either 1, or a positive power of q.^[7]

• Lidl, Rudolf; Niederreiter, Harald (1997). Finite fields. Encyclopedia of Mathematics and Its Applications. Vol. 20 (2nd ed.). Cambridge University Press. ISBN 0-521-39231-4. Zbl 0866.11069.
• Mullen, Gary L.; Panario, Daniel (2013), Handbook of Finite Fields, Discrete Mathematics and its Applications, Boca Raton: CRC Press, ISBN 978-1-4398-7378-6