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}},{\text{ where each }}a_{i}{\text{ is in }}F_{q^{m}}({\text{ = }}GF(q^{m})){\text{ for some fixed positive integer }}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.

Properties

• 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]

Symbolic multiplication

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.

Associated polynomials

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

q-polynomials over F_q

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 ${\displaystyle \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).}$

Affine polynomials

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]

Notes

1. Lidl & Niederreiter 1983, pg.107 (first edition) harvnb error: no target: CITEREFLidlNiederreiter1983 (help)
2. Mullen & Panario 2013, p. 23 (2.1.106)
3. Lidl & Niederreiter 1983, pg. 115 (first edition) harvnb error: no target: CITEREFLidlNiederreiter1983 (help)
4. Lidl & Niederreiter 1983, pg. 115 (first edition) Corollary 3.60 harvnb error: no target: CITEREFLidlNiederreiter1983 (help)
5. Lidl & Neiderreiter 1983, pg. 116 (first edition) Theorem 3.62 harvnb error: no target: CITEREFLidlNeiderreiter1983 (help)
6. Lidl & Neiderreiter 1983, pg. 117 (first edition) Example 3.64 harvnb error: no target: CITEREFLidlNeiderreiter1983 (help)
7. Mullen & Panario 2013, p. 23 (2.1.109)

References

• Lidl, Rudolf; Niederreiter, Harald (1997). Finite fields. Encyclopedia of Mathematics and Its Applications. 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