Re: Sparse Irreducible Polynomials mod 2

Thanks, but those papers (and several others linked to them by
reference in various directions) don't answer my question at all,
because they are either about polynomials over fields of much larger
characteristic than 2, or they are about finding particular examples of
sparse irreducible polynomials for certain nice degrees, while I am
interested in how sparse a polynomial must exist even for the WORST
degree.

The numerical finding of Allan Steel, that there is always a polynomial
of at most 5 nonzero terms which is irreducible mod 2 for degrees up to
12800, is very striking and suggestive, but I have not found even a
conjecture on the growth rate of the number of terms in the sparsest
irreducible polynomial of degree n (though many have expressed a wish
that it is O(log(n)).

For the application I have in mind, it would suffice to have, for each
odd prime power q, an explicit sparse irreducible polynomial over GF(2)
whose degree is divisible by q, but even that seems out of reach (the
special cases that have been written about apply to powers of 3 and 5
but not powers of 7, for example). But the general question "is there
any n for which all irreducible polynomials over GF(2) of degree n have
more than 5 nonzero terms?" seems not to have been raised in any papers
I have seen.

-- Joe Shipman




Gerry Myerson wrote:

You may find something useful in various papers by Shuhong Gao
and some co-suthors, e.g.,

Gao, S., Howell, J., Panario, D. (1999). Irreducible polynomials of
given forms. In Mullin, R., Mullen, G., editors, Finite fields: theory,
applications and algorithms, volume 225, pages 43--54. Contemporary
Mathematics, Amer. Math. Soc.

MR1661992 (99m:11141) Gao, Shuhong; Panario, Daniel Tests and
constructions of irreducible polynomials over finite fields.
Foundations of computational mathematics (Rio de Janeiro, 1997),
346--361, Springer, Berlin, 1997.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)

.

Relevant Pages

  • Re: Finite fields from aperiodic necklaces
    ... uses aperiodic necklaces instead of irreducible polynomials. ... The case of the so called minimal normal basis (those ...
    (sci.math)
  • Re: Finite fields from aperiodic necklaces
    ... explicit mapping between the sets irreducible polynomials ... shifting the coefficients, the elements of the subfield GF, ... those necklaces that have m/n as a period. ... For polynomials we have this sort of formula ...
    (sci.math)
  • Re: irredicuble polynomials
    ... > Prove that for every prime power q, one has that for all n there exists and ... > where I-the number of irredicuble polynomials of degree k(we are working ... is the number of monic polynomials of degree n, ... irreducible polynomials, right? ...
    (sci.math)
  • Re: Text on LFSR
    ... >>various cycles when the polynomial is not primitive. ... I begin with a known multiple of the period ... modulo each of the irreducible polynomials which product ...
    (sci.crypt)
  • Re: Solving overdetermined equations
    ... >outlined in two of my papers, which can be found on my website: ... Call the sphere center coordinates. ... the direction vector plus the lines known point, ... polynomials as below, with four extra magnitude variables that, in ...
    (sci.math.symbolic)
Quantcast