Linearised polynomial: Difference between revisions

Revision as of 19:16, 29 May 2022

Latest revision as of 19:04, 10 November 2023

(One intermediate revision by one other user not shown)

Line 2:

We write a typical example as

:<math display="block">L(x) = \sum_{i=0}^n a_i x^{q^i},</math>

:<math>L(x) = \sum_{i=0}^n a_i x^{q^i},</math>

where each <math>a_i</math> is in <math>F_{q^m} (= \operatorname{GF}(q^m))</math> for some fixed positive [[integer]] <math>m</math>.

This special class of polynomials is important from both a theoretical and an applications viewpoint.<ref>{{harvnb|Lidl|Niederreiter|19831997|loc=pg.107 (first edition)}}</ref> The highly structured nature of their [[root of a function|roots]] makes these roots easy to determine.

==Properties==

* The map {{math|''x'' ↦ ''L''(''x'')}} is a [[linear map]] over any [[field (mathematics)|field]] containing '''F'''_''q''.

* The [[set (mathematics)|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.

Line 17 ⟶ 15:

==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 <math display="block">L_1(x) \otimes L_2(x) = L_1(L_2(x))</math> when this point of view is being taken.

when this point of view is being taken.

==Associated polynomials==

The polynomials {{math|''L''(''x'')}} and <math display="block">l(x) = \sum_{i=0}^n a_i x^i </math> are ''q-associates'' (note: the exponents "''q''^''i''" 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'').

The polynomials ''L''(''x'') and

:<math>l(x) = \sum_{i=0}^n a_i x^i \ </math>

are ''q-associates'' (note: the exponents "''q''^''i''" 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 <math>x \mapsto x^q</math> and the trace function <math display="inline">\operatorname{Tr}(x) = \sum_{i=0}^{n-1} x^{q^i}.</math>

In this special case it can be shown that, as an [[Operation (mathematics)|operation]], symbolic multiplication is [[Commutative property|commutative]], [[associative]] and [[Distributive property|distributes]] over ordinary addition.<ref>{{harvnb|Lidl|Niederreiter|19831997|loc=pg. 115 (first edition)}}</ref> 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: <math display="block">L(x) = L_1(x) \otimes L_2(x).</math>

:<math>L(x) = L_1(x) \otimes L_2(x).</math>

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'').<ref>{{harvnb|Lidl|Niederreiter|19831997|loc=pg. 115 (first edition) Corollary 3.60}}</ref> Furthermore,

''L''₁(''x'') divides ''L''₂(''x'') in the ordinary sense in this case.<ref>{{harvnb|Lidl|NeiderreiterNiederreiter|19831997|loc=pg. 116 (first edition) Theorem 3.62}}</ref>

A linearised polynomial ''L''(''x'') over '''F'''_''q'' of [[degree of a polynomial|degree]] > 1 is ''symbolically irreducible'' over '''F'''_''q'' if the only symbolic decompositions

::<math display="block">L(x) = L_1(x) \otimes L_2(x),</math>

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 polynomial|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,<ref>{{harvnb|Lidl|NeiderreiterNiederreiter|19831997|loc=pg. 117 (first edition) Example 3.64}}</ref> 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

::<math display="block">L(x) = (x^4 + x^2 + x) \otimes (x^2 + x) \otimes (x^2 + x).</math>

==Affine polynomials==