##
Hamming distance from irreducible polynomials over GF(2)

*Gilbert Lee*,
Department of Computer Science,
University of Victoria, Canada.

*Frank Ruskey*,
Department of Computer Science,
University of Victoria, Canada.

*Aaron Williams*,
Department of Computer Science,
University of Victoria, Canada.

### Abstract:

We study the Hamming distance from
polynomials to classes of polynomials that share certain
properties of irreducible polynomials.
The results give insight into whether or not irreducible
polynomials can be effectively modeled by these more general
classes of polynomials.
For example, we prove that the number of degree *n* polynomials
of Hamming distance one from a randomly chosen set of
2^{n}/*n*
odd density polynomials is asymptotically
(1-*e*^{-4}) 2^{n-1}, and this appears
to be inconsistent with the numbers for irreducible polynomials.
We also conjecture that there is a constant *c* such that every
polynomial has Hamming distance at most *c* from an irreducible
polynomial.
Using exhaustive lists of irreducible polynomials over
GF(2) for degrees 1 __<__ *n* __<__ 32,
we count the number of polynomials with a given Hamming distance
to some irreducible polynomial of the same degree.
Our work is based on this "empirical" study.

Back to list of publications.