Geodesic
Hamming distance from irreducible polynomials over $\mathbb {F}_2$
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

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 $\lfloor 2^n/n \rfloor$ odd density polynomials, each of degree $n$ and each with non-zero constant term, is asymptotically $(1-e^{-4}) 2^{n-2}$, 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 $\mathbb{F}_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. 
@article{DMTCS_2007_special_253_a32,
     author = {Lee, Gilbert and Ruskey, Frank and Williams, Aaron},
     title = {Hamming distance from irreducible polynomials over $\mathbb {F}_2$},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3550},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3550/}
}
TY  - JOUR
AU  - Lee, Gilbert
AU  - Ruskey, Frank
AU  - Williams, Aaron
TI  - Hamming distance from irreducible polynomials over $\mathbb {F}_2$
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3550/
DO  - 10.46298/dmtcs.3550
LA  - en
ID  - DMTCS_2007_special_253_a32
ER  - 
%0 Journal Article
%A Lee, Gilbert
%A Ruskey, Frank
%A Williams, Aaron
%T Hamming distance from irreducible polynomials over $\mathbb {F}_2$
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3550/
%R 10.46298/dmtcs.3550
%G en
%F DMTCS_2007_special_253_a32
Lee, Gilbert; Ruskey, Frank; Williams, Aaron. Hamming distance from irreducible polynomials over $\mathbb {F}_2$. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3550. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3550/

Cité par Sources :