Linearised polynomial: Difference between revisions

Revision as of 17:01, 20 April 2014

Latest revision as of 19:04, 10 November 2023

(8 intermediate revisions by 7 users not shown)

Line 1:

In [[mathematics]], a '''linearised polynomial''' (or ''q''- polynomial) is a [[polynomial]] for which the exponents of all the constituent [[monomial]]s are [[power (mathematics)|powers]] of ''q'' and the coefficients[[coefficient]]s come from some [[extension field]] of the [[finite field]] of order ''q''.

We write a typical example as

:<math> ldisplay="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}, \text{ where each } <math>a_i \text{</math> is in } <math>F_{q^m} (\text= \operatorname{ = GF} GF(q^m)) \text{</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.

:<math>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. </math>

This special class of polynomials is important from both a theoretical and an applications viewpoint.<ref>{{harvnb|Lidl|Niederreiter|1983|loc=pg.107 (first edition)}}</ref> The highly structured nature of their 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.

* The set of linearised polynomials over a given field is closed under addition and [[function composition|composition]] of polynomials.

* If ''L'' is a nonzero linearised polynomial over <math>F_{q^n}</math> with all of its roots lying in the field <math>F_{q^s}</math> an extension field of <math>F_{q^n}</math>, then each root of ''L'' has the same multiplicity, which is either 1, or a positive power of ''q''.<ref>{{harvnb|Mullen|Panario|2013|loc=p. 23 (2.1.106)}}</ref>

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

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

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 factorizatonfactorization. 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 [[Reduciblereducible expressionpolynomial|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==

Line 55 ⟶ 48:

==References==

* {{cite book | zbl=0866.11069 | last1=Lidl | first1=Rudolf | last2=Niederreiter | first2=Harald | author2-link=Harald Niederreiter | title=Finite fields | edition=2nd | series=Encyclopedia of Mathematics and Its Applications | volume=20 | publisher=[[Cambridge University Press]] | year=1997 | isbn=0-521-39231-4 | url-access=registration | url=https://archive.org/details/finitefields0000lidl_a8r3 }}

* {{citation|first1=Gary L.|last1=Mullen|first2=Daniel|last2=Panario|title=Handbook of Finite Fields|year=2013|publisher=CRC Press|place=Boca Raton|series=Discrete Mathematics and its Applications|isbn=978-1-4398-7378-6}}