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

The pdf file.
The postscript file.
Please send me a note if you download one of these files. It's always nice to know who's reading your papers.
Accepted at the 2007 International Conference on Analysis of Algorithms, June 17-22, Juan-les-pins, France.
Relevant sequences in the OEIS (Online Encyclopedia of Integer Sequences: (A128901, A128902, A128903).
Selected citations:
- Are there any?

Back to list of publications.