<figure><img src="image_1.png" /></figure>

HAL
open science

# Hamming distance from irreducible polynomials over $F_2$

Gilbert Lee, Frank Ruskey, Aaron Williams

► To cite this version:

Gilbert Lee, Frank Ruskey, Aaron Williams. Hamming distance from irreducible polynomials over $F_2$. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.183-196, 10.46298/dmtcs.3550. hal-01184798

HAL Id: hal-01184798

https://inria.hal.science/hal-01184798

Submitted on 17 Aug 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Hamming distance from irreducible
polynomials over $\mathbb{F}_2$

Gilbert Lee† and Frank Ruskey‡ and Aaron Williams§

Dept. of Computer Science, University of Victoria, CANADA

received 26 Feb 2007, revised 8 May 2007, accepted 19 April 2007.

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 \le n \le 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.

**Keywords:** irreducible polynomials, random polynomials, Hamming distance, finite fields, binary strings, asymptotics, exhaustive enumeration

## 1 Introduction and Motivation

In this paper we are motivated by the following natural question: Under some appropriate measure how far can a polynomial be from being irreducible? We are mainly concerned with polynomials over the two element finite field and where the distance measure is the Hamming distance between polynomials of the same degree. Using recently computed exhaustive lists of irreducible polynomials up to degree 32, we compute the number of polynomials having a given Hamming distance from the set of irreducible polynomials. We conjecture that there is an absolute constant $c$ such that every polynomial is of distance at most $c$ from an irreducible polynomial. The data supports the conjecture that $c = 3$ for polynomials with non-zero constant term.

Let $\mathbb{F}_q$ denote the finite field with $q$ elements. By $\mathbb{F}_q[z]$ we denote the set of monic polynomials with coefficients in $\mathbb{F}_q$. The Hamming distance (or simply *distance*) $H(P(z), Q(z))$ between two polynomials $P(z) = \sum p_k z^k$ and $Q(z) = \sum q_k z^k$ is the number of coefficients for which $p_k \neq q_k$. Let $I_q(n, d)$ be the

<footnote>†Research supported in part by an NSERC postgraduate scholarship.</footnote>

<footnote>‡Research supported in part by an NSERC discovery grant.</footnote>

<footnote>§Research supported in part by an NSERC postgraduate scholarship.</footnote>
number of monic polynomials $P(z) \in \mathbb{F}_q[z]$ with non-zero constant term for which $d$ is the smallest value such that there is a monic degree $n$ irreducible polynomial $Q(z)$ with $d = H(P(z), Q(z))$. By $I(n, d)$ we mean $I_2(n, d)$.

A polynomial is irreducible if it cannot be factored into the product of two non-trivial polynomials. The number of monic irreducible polynomials over $\mathbb{F}_q$ is

$$ \frac{1}{n} \sum_{d|n} \mu(d) q^{n/d} \sim \frac{1}{n} q^n. \qquad (1) $$

If a polynomial is irreducible over $\mathbb{F}_q$ then the sum of its coefficients is not divisible by $q$, because otherwise 1 would be a root. In particular over $\mathbb{F}_2$, the sum of the coefficients is odd.

Conventional wisdom suggests that the coefficients of irreducible polynomials are uniformly distributed in the limit, as $n$ tends to infinity. See, for example, the final comments of (HM92). A typical result is that of (Uch55) stated below. This result was corrected by (Hay65) (and extended by (Coh72)).

**Theorem 1.1 (Uchiyama/Hayes)** The number of monic irreducible polynomials in $\mathbb{F}_q$ whose first $s$ and last $t$ $(\ge 1)$ coefficients are fixed (with non-zero constant coefficient) is, for $\frac{1}{2} \le v < 1$,

$$ \frac{q^n}{n(q-1)q^{s+t-1}} + O\left(\frac{q^{nv}}{n}\right). $$

With reference to (1), this is exactly what you would expect if the coefficients were distributed uniformly.

It is natural to investigate the distance question with sets of random polynomials to see if our experimental data support the hypothesis of uniformity. Surprisingly, we will see that this is not the case.

Two key properties of the set of irreducible polynomials over $\mathbb{F}_2$ are

* **Odd density:** In every irreducible polynomial the number of non-zero coefficients is odd. Otherwise, 1 is a root of the polynomial.

* **Reciprocal-closed:** The reciprocal of every irreducible polynomial is also irreducible. The reciprocal of a degree $n$ polynomial $p(z)$ over $\mathbb{F}_2$ is the polynomial $z^n p(1/z)$.

The central question that we are trying to answer is: with respect to the Hamming distance question, are these properties (or just one of them) sufficient to explain the observed data? We believe that the answer is no. This is surprising since the only results known to us regarding the distribution of the coefficients of irreducible polynomials suggests that they behave in the limit like random polynomials.

Here is an outline of the paper. In Section 2 we show tables of our experimental results and briefly discuss the methodology used to produce them. Our results here allow us to extend a theorem of (BH97). In Section 3 we study the distance from random sets of binary strings with the odd density property. These results show consistent bias towards the data so in Section 4 we refine the model to also have the reverse-closed property (corresponds to the polynomials being reciprocal-closed). As we shall see, the refined model turns out to have the same asymptotics as the initial model.

## 2 Results for $\mathbb{F}_2$

We used the method described in (CRS+00) to produce tables of irreducible polynomials over $\mathbb{F}_2$. To compute the distance table we do a breadth-first search of the underlying graph of polynomials. Each
polynomial of degree $n$ is represented by a bitstring of length $n-1$. For example, the polynomial

$$x^{24} + x^{23} + x^{22} + x^{21} + x^{20} + x^{16} + x^{14} + x^{12} + x^{10} + x^{8} + x^{4} + x^{3} + x^{2} + x + 1 \quad (2)$$

is represented as $1111000101010101010001111$. It is natural to use the bitstrings, interpreted as binary numbers, to index into an array that keeps track of the distance corresponding to that index. However, this would require far too much memory. We are forced to pack the information into computer words. We keep two arrays, one for polynomials of even distance, and the other for polynomials of odd distance, scanning one while updating the other.

The rightmost non-zero values in each row $1 \le n \le 17$ in Table 1 were previously computed in (BH97) (Table I., pg. 395 — but note that there is a typo, 17 should be 14), which contains the following theorem about irreducibility over the integers. If $P$ is a polynomial, the $|P|$ denotes the sum of the absolute values of the coefficients.

**Theorem 2.1** If $0 \le n \le 22$, then for every monic polynomial $P \in \mathbb{Z}[x]$ of degree $n$ there exists an irreducible monic polynomial $Q \in \mathbb{Z}[x]$ of degree $n$ such that $|P - Q| \le 4$.

Our results extend this Theorem to $0 \le n \le 32$. (To justify this claim, the main things to note are that (a) a monic polynomial that is irreducible over $\mathbb{Z}$ is also irreducible over $\mathbb{Z}_2 = \mathbb{F}_2$, and (b) if $P'$ is $P$ with coefficients reduced mod 2, and $H(P', Q') \le d$, then by adding even integers to the coefficients of $Q'$ we can arrive at a polynomial $Q$ such that $|P - Q| \le d$.)

Our calculations also show that there are polynomials at distance four from the set of primitive polynomials. There is 1 for $n = 24$ (the polynomial (2)) and 2 for $n = 32$, but no others in the range $1 \le n \le 32$.

## 3 Distance using a random set

Instead of computing the Hamming distances from the set of irreducible polynomials, what happens when we compute Hamming distances to a random set of polynomials, each having an odd number of non-zero coefficients? It will be convenient restate our results in terms of bitstrings. We identify the bitstring $b_1b_2 \cdots b_N$ with the polynomial $x^{N+1} + b_Nx^N + \cdots + b_1x + 1$.

Let us first prove a technical lemma.

**Lemma 3.1** Let

$$T(n) = \binom{2^n - p}{m} / \binom{2^n}{m}$$

where $p$ and $m$ are integers for which $p = O(n^k)$ (for some fixed $k$) and $m = o(2^n)$. Then

$$\ln T(n) = \ln \left( \left(1 - \frac{m}{2^n}\right)^p \right) + O\left(\frac{p}{2^n - m}\right) + O\left(m \left(\frac{p}{2^n - m}\right)^2\right).$$

**Proof:** By Taylor's expansion with remainder, for $z$ approaching zero,

$$\ln(1-z) = -\sum_{k=1}^{t} \frac{z^k}{k} + O(z^{t+1}), \quad (3)$$
<table><caption>Tab. 1: The values of I(n, d) for 1 ≤ n ≤ 32.</caption><thead><tr><th>n\d</th><th>0</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>1</td><td>1</td><td></td><td></td><td></td></tr><tr><td>2</td><td>1</td><td>1</td><td></td><td></td></tr><tr><td>3</td><td>2</td><td>2</td><td></td><td></td></tr><tr><td>4</td><td>3</td><td>4</td><td>1</td><td></td></tr><tr><td>5</td><td>6</td><td>8</td><td>2</td><td></td></tr><tr><td>6</td><td>9</td><td>16</td><td>7</td><td></td></tr><tr><td>7</td><td>18</td><td>32</td><td>14</td><td></td></tr><tr><td>8</td><td>30</td><td>63</td><td>34</td><td>1</td></tr><tr><td>9</td><td>56</td><td>128</td><td>72</td><td></td></tr><tr><td>10</td><td>99</td><td>255</td><td>157</td><td>1</td></tr><tr><td>11</td><td>186</td><td>510</td><td>326</td><td>2</td></tr><tr><td>12</td><td>335</td><td>1020</td><td>689</td><td>4</td></tr><tr><td>13</td><td>630</td><td>2032</td><td>1418</td><td>16</td></tr><tr><td>14</td><td>1161</td><td>4048</td><td>2935</td><td>48</td></tr><tr><td>15</td><td>2182</td><td>8109</td><td>6010</td><td>83</td></tr><tr><td>16</td><td>4080</td><td>16216</td><td>12304</td><td>168</td></tr><tr><td>17</td><td>7710</td><td>32434</td><td>25058</td><td>334</td></tr><tr><td>18</td><td>14532</td><td>64731</td><td>51004</td><td>805</td></tr><tr><td>19</td><td>27594</td><td>129597</td><td>103478</td><td>1475</td></tr><tr><td>20</td><td>52377</td><td>258718</td><td>209767</td><td>3426</td></tr><tr><td>21</td><td>99858</td><td>517424</td><td>424430</td><td>6864</td></tr><tr><td>22</td><td>190557</td><td>1034430</td><td>858019</td><td>14146</td></tr><tr><td>23</td><td>364722</td><td>2067780</td><td>1732430</td><td>29372</td></tr><tr><td>24</td><td>698870</td><td>4132038</td><td>3495434</td><td>62266</td></tr><tr><td>25</td><td>1342176</td><td>8262934</td><td>7046432</td><td>125674</td></tr><tr><td>26</td><td>2580795</td><td>16515320</td><td>14196421</td><td>261896</td></tr><tr><td>27</td><td>4971008</td><td>33021972</td><td>28583424</td><td>532460</td></tr><tr><td>28</td><td>9586395</td><td>66029987</td><td>57522469</td><td>1078877</td></tr><tr><td>29</td><td>18512790</td><td>132008983</td><td>115704938</td><td>2208745</td></tr><tr><td>30</td><td>35790267</td><td>263944002</td><td>232645189</td><td>4491454</td></tr><tr><td>31</td><td>69273666</td><td>527772375</td><td>467597246</td><td>9098537</td></tr><tr><td>32</td><td>134215680</td><td>1055126462</td><td>939526144</td><td>18615362</td></tr></tbody></table>
We only need the case of $t = 1$ in what follows. The expansion below for the Harmonic numbers is well-known (e.g., (KGP89), pg. 278).

$$H(n) = \ln n + \gamma + O(1/n). \quad (4)$$

Note that

$$T(n) = \binom{2^n - p}{m} / \binom{2^n}{m} = \prod_{i=0}^{m-1} \frac{2^n - p - i}{2^n - i} = \prod_{i=0}^{m-1} \left(1 - \frac{p}{2^n - i}\right).$$

Now take logarithms, and apply (3) and (4).

$$
\begin{align*}
\ln T(n) &= \sum_{i=0}^{m-1} \ln \left(1 - \frac{p}{2^n - i}\right) \\
&= \sum_{i=0}^{m-1} \left( \frac{-p}{2^n - i} + O\left(\left(\frac{p}{2^n - i}\right)^2\right) \right) \\
&= -p(H(2^n) - H(2^n - m)) + O\left(m \left(\frac{p}{2^n - m}\right)^2\right) \\
&= -p\left(\ln(2^n) - \ln(2^n - m) + O\left(\frac{1}{2^n}\right) + O\left(\frac{1}{2^{n-m}}\right)\right) + O\left(m \left(\frac{p}{2^{n-m}}\right)^2\right) \\
&= \ln\left(1 - \frac{m}{2^n}\right)^p + O\left(\frac{p}{2^n - m}\right) + O\left(m \left(\frac{p}{2^{n-m}}\right)^2\right)
\end{align*}
$$

□

## 3.1 Hamming distances to an odd density set

By $S(N, M)$ we denote a set of $M$ odd density bitstrings each of length $N$, chosen uniformly at random from the set of all $2^N$ odd density bitstrings of length $N$. We say that a bitstring is odd if it has odd density; otherwise, it is even. The Hamming distance $H(b, c)$ between two bitstrings $b$ and $c$ of length $N$ is the number of positions in which the corresponding bits differ. We say that two bitstrings are adjacent if their Hamming distance is one; i.e., they are adjacent in the hypercube. We extend the notation to sets $S$ of bitstrings by defining $H(b, S) = \min\{H(b, s) | s \in S\}$.

Given a set of length $N$ bitstrings $S$, the neighborhood, $N(S)$, of $S$ is the set $\{b \in \{0, 1\}^N | H(b, s) = 1 \text{ for some } s \in S\}$; in other words it is exactly the same as the open neighborhood of $S$ in the hypercube $Q_N$, in the graph theoretic sense.

**Theorem 3.2** Let $S$ be a randomly chosen set of $M$ odd bitstrings of length $N$ and let $b$ be some fixed bitstring of length $N$.

$$Pr(H(b, S) \ge 2d + 1 | b \text{ even}) = \binom{2^{N-1} - \sum_{j=0}^{d-1} \binom{N}{2j+1}}{M} / \binom{2^{N-1}}{M} \quad (5)$$
<figure><img src="image_3.png" /><figcaption>**Fig. 1:** The graph of $2^{-(N-1)}\mathcal{E}[|\mathcal{N}(S(N, M))|]$ for $M = 8, 16, 32, 64, 128, 256$. The horizontal axis shows $100M/2^{N-1}$.</figcaption></figure>

$$ Pr(H(b, S) \ge 2d \mid b \text{ odd}) = \binom{2^{N-1} - \sum_{j=0}^{d-1} \binom{N}{2j}}{M} / \binom{2^{N-1}}{M} \quad (6) $$

**Proof:** There are a total of $\binom{2^{N-1}}{M}$ ways to select $S$. Suppose that $b$ is even. By symmetry we may assume that $b$ is any even bitstring. We assume that $b$ consists solely of 0's; that is, $b = 0^N$. In order for $b$ to be distance $2d+1$ away from any string in $S$, the set $S$ can have no bitstrings of density 1, 3, ..., $2d-1$. The number of such forbidden strings is $\binom{N}{1} + \binom{N}{3} + \dots + \binom{N}{2d-1}$. The argument for $b$ odd is similar and is omitted. $\square$

**Lemma 3.3** The expected size of the set $\{b \in \{0, 1\}^N \mid H(b, S(N, M)) = d\}$ is

$$ 2^{N-1} \left( \Pr(H(b, S(N, M)) \ge d \mid b \ne d \mod 2) - \Pr(H(b, S(N, M)) \ge d+2 \mid b \ne d \mod 2) \right). $$

**Proof:** Since $S(N, M)$ is a set of odd bitstrings, $H(b, S(N, M))$ must have different parity than $b$. The number of $b \in \{0, 1\}^N$ with a given parity is $2^{N-1}$. $\square$

In this paper we use $\mathcal{E}[X]$ to denote expected value of random variable $X$. In Figure 1 we show $2^{-(N-1)}\mathcal{E}[|\mathcal{N}(S(N, M))|]$ for selected values of $N$ and varying $M$.

To make comparisons with irreducible polynomials over $\mathbb{F}_2$, we set $N = n - 1$ and $M = 2^n/n$ (from (1)).
**Theorem 3.4** Asymptotically, $\mathcal{E}[|\{b \in \{0, 1\}^N | H(b, S(N, M)) = d\}|]$ is equal to

$$ \begin{cases} 2^n/n & \text{if } d = 0 \\ 2^{n-2}(1 - e^{-4}) & \text{if } d = 1 \\ 2^{n-2} - 2^n/n & \text{if } d = 2 \\ 2^{n-2}e^{-4} & \text{if } d = 3 \\ 0 & \text{if } d \ge 4. \end{cases} $$

**Proof:** The case $d = 0$ follows from (1). We explain the $d = 1$ case below, and leave the remaining for the full paper.

We substitute $N = n - 1$ and $M = 2^n/n$ in Theorem 3.2 and Lemma 3.3 and then apply Lemma 3.1 to the binomial coefficient ratio $T(n) = (2^{n-2} - (n-1)) / (2^{n-2} / 2^n)$.

$$ \begin{aligned} \ln T(n) &= \ln \left( \left( 1 - \frac{2^n/n}{2^{n-2}} \right)^{n-1} \right) + O\left( \frac{n}{2^n} \right) + O\left( \frac{n^3}{2^{n-2}(n-4)^2} \right) \\ &= \ln \left( \left( 1 - \frac{4}{n} \right)^{n-1} \right) + O\left( \frac{n}{2^n} \right). \end{aligned} $$

Thus

$$ T(n) = \left(1 - \frac{4}{n}\right)^{n-1} e^{O(n/2^n)} \sim \frac{1}{e^4} $$

Since the expected size is $2^{n-2}(1 - T(n))$, the proof is finished. $\square$

The limiting value is achieved somewhat slowly. For example, Maple reveals that

$$ 1 - \text{Pr}(H(b, S(998, 2^{1000})/1000)) = 1) \approx 0.01816930954 $$

where the limiting value is $e^{-4} \approx 0.01831563889$. And for $n = 2000$ the approximation is 0.01827898319. Trinomial revision is a fancy name for the simple but useful identity $\binom{r}{m}\binom{m}{k} = \binom{r}{k}\binom{r-k}{m-k}$; see (KGP89), pg. 174. An application of trinomial revision to the binomial coefficient ratios in Theorem 3.2 is necessary in order to allow Maple to do the calculation.

Now the question is: How well do these results approximate the actual data? Consider the graph of Figure 2. The black horizontal line is $y = e^{-4} \approx 0.18$. The (green) dots are the scaled data values $1 - I(n, 1)/2^{n-2}$. The upper curve is $1 - \text{Pr}(H(b, S(n - 1, 2^n/n) = 1))$. The lower curve is from the next subsection. Note that the upper curve is tending to the limiting value (as proven in Theorem 3.1), but that the actual data values seem to be on a trajectory that will blast them through the horizontal line at $e^{-4}$.

Since the current model does not explain the data, perhaps we need to refine it. In the next two subsections we restrict the random strings to be reverse-closed. Given a binary string $b$, let $b^R$ represent the reversal of $b$. A set of binary strings $S$ is reverse-closed if $b^R \in S$ whenever $b \in S$.
<figure><img src="image_4.png" /><figcaption>**Fig. 2:** The black horizontal line is $y = e^{-4} \approx 0.18$. The (green) dots are the scaled data values $1 - I(n, 1)/2^{n-2}$. The upper curve is $1 - \text{Pr}(H(b, S(n-1, 2^n/n) = 1)$.</figcaption></figure>

## 3.2 Even length odd density reverse-closed sets

Let $O$ represent the binary strings of length $N$ with odd density, and let $E$ represent the binary strings of length $N$ with even density. Since $N$ is even, there is no $b \in O$ where $b = b^R$. Therefore, we can partition $O$ into $O^> \cup O^<$ where $O^>$ and $O^<$ are defined as

$$O^> := \{b \in O : b > b^R\} \text{ and } O^< := \{b \in O : b < b^R\}.$$

Let $R = R(N, M)$ be a reverse-closed set of $M$ odd density bitstrings of length $N$, chosen uniformly at random. Our objective is to calculate the expected size of $\mathcal{N}(R(N, M))$ as a function of $M$ and $N$. We will write this as $\mathcal{E}[|\mathcal{N}(R(N, M))|]$. Since $R$ is reverse-closed and $b \in O^>$ if and only if $b^R \in O^<$, each string in $R \cap O^>$ is uniquely paired with a string in $R \cap O^<$. Thus $M$ must also be even, and we proceed as if $R$ was constructed by selecting $M/2$ elements from $O^>$. Since $R \subseteq O$, we know that $\mathcal{N}(R) \subseteq E$, and we will find it useful to partition $E$ into $E^= \cup E^\ne$ where

$$E^= = \{b \in E : b = b^R\} \text{ and } E^\ne = \{b \in E : b \ne b^R\}.$$

This partition of $E$ is useful since

$$|\{c \in O^> : c \in R \implies b \in \mathcal{N}(R)\}| = \begin{cases} N/2 & \text{when } b \in E^= \\ N & \text{when } b \in E^\ne. \end{cases}$$

For example, when $N = 4$, let us consider the difference between $0000 \in E^=$ and $1010 \in E^\ne$. If $0000 \in \mathcal{N}(R)$ then one of 1000, 0100, 0010, 0001 must be in $R$, so one of 1000, 0100 must be in
$R \cap O^>$. On the other hand, if $1010 \in \mathcal{N}(R)$ then one of $0010, 1110, 1000, 1011$ must be in $R$, so one of $0100, 1110, 1000, 1101$ must be in $R \cap O^>$. The difference arises from the fact that two neighbors of $b \in E^=$ can be reverses of each other, but this cannot happen when $b \in E^\neq$. Now we are ready to compute $\mathcal{E}[|\mathcal{N}(R)|]$.

First note that $|O| = |E| = 2^{N-1}$, $|O^>| = |O^<| = 2^{N-2}$, $|E^|= 2^{N/2}$, and $|E^\neq| = 2^{N-1} - 2^{N/2}$.

**Theorem 3.5** If $N$ is even then the expected size of the set $\mathcal{N}(R(N, M))$ is

$$2^{N-1} \left( 1 - \frac{\binom{2^{N-2}-N/2}{M/2} + (2^{N/2-1}-1)\binom{2^{N-2}-N}{M/2}}{2^{N/2-1}\binom{2^{N-2}}{M/2}} \right)$$

**Proof:** We compute the probability that a bitstring $b$ is not in $\mathcal{N}(R(N, M))$, assuming that $b$ is even.

$$
\begin{align}
\mathrm{Pr}(b \notin \mathcal{N}(R)) &= \mathrm{Pr}(b \notin \mathcal{N}(S)|b \in E^=)\mathrm{Pr}(b \in E^=) + \nonumber \\
&\quad \mathrm{Pr}(b \notin \mathcal{N}(S)|b \in E^\neq)\mathrm{Pr}(b \in E^\neq) \nonumber \\
&= \frac{\binom{|O^>-N/2}{M/2}}{\binom{|O^>|}{M/2}} \frac{2^{N/2}}{2^{N-1}} + \frac{\binom{|O^>-N}{M/2}}{\binom{|O^>|}{M/2}} \frac{2^{N-1}-2^{N/2}}{2^{N-1}} \nonumber \\
&= \frac{\binom{2^{N-2}-N/2}{M/2}}{\binom{2^{N-2}}{M/2}} \frac{1}{2^{N/2-1}} + \frac{\binom{2^{N-2}-N}{M/2}}{\binom{2^{N-2}}{M/2}} \left(1 - \frac{1}{2^{N/2-1}}\right) \tag{7} \\
&= \frac{\binom{2^{N-2}-M/2}{N/2}}{\binom{2^{N-2}}{N/2}} \frac{1}{2^{N/2-1}} + \frac{\binom{2^{N-2}-M/2}{N}}{\binom{2^{N-2}}{N}} \left(1 - \frac{1}{2^{N/2-1}}\right). \tag{8}
\end{align}
$$

The last equality (8) again follows by trinomial revision and yields a final expression that is better for computation. Since

$$\begin{align*}
\mathcal{E}[|\mathcal{N}(R)|] &= |E| \cdot \mathrm{Pr}(b \in \mathcal{N}(R)) \\
&= |E| \cdot (1 - \mathrm{Pr}(b \notin \mathcal{N}(R)))
\end{align*}$$

the proof is finished.

□

**Theorem 3.6** If $N$ is even then

$$E[|\mathcal{N}(R(n-1, 2^n/n))|] \sim 2^{n-2}(1 - e^{-4}).$$

**Proof:** In Theorem 3.5 the second summand in (7) will clearly dominate asymptotically. Setting $N = n-1$ and $M = 2^n/n$, by Lemma 3.1,

$$\frac{\binom{2^{N-2}-N}{M/2}}{\binom{2^{N-2}}{M/2}} = \frac{\binom{2^{n-3}-(n-1)}{2^{n-1}/n}}{\binom{2^{n-3}}{2^{n-1}/n}} \sim \lim_{n \to \infty} \left(1 - \frac{2^{n-1}/n}{2^{n-3}}\right)^{n-1} = \lim_{n \to \infty} \left(1 - \frac{4}{n}\right)^{n-1} = e^{-4}.$$
<figure><img src="image_5.png" /></figure>

A Maple calculation for $n = 1000$ of the binomial coefficient ratio above gives $0.01824227864$ and for $n = 2000$ we get $0.01827898319$, whereas the value of $e^{-4} \approx 0.01831563889$, so again convergence is quite slow.

### 3.3 Odd length odd density reverse-closed sets

The case where $N$ is odd is more complicated because now there are odd density strings $b$ such that $b = b^R$.

Let $O$ represent the binary strings of length $N$ with odd density, and let $E$ represent the binary strings of length $N$ with even density. We can partition $O$ into $O^= \cup O^> \cup O^<$ where $O^>$ and $O^<$ were defined before and

$$O^= = \{b \in O : b = b^R\}.$$

Suppose $R = R(N, M) \subseteq O$ is chosen uniformly at random to be a reverse-closed set of $M$ binary strings of length $N$. Our objective is to calculate the expected size of $N(R)$ in terms of $M$ and $N$. We will write this as $E[|N(R(N, M))|]$. Since $R$ is reverse-closed and $b \in O^>$ if and only if $b^R \in O^<$, each string in $R \cap O^>$ is uniquely paired with a string in $R \cap O^<$, and the remaining strings in $R$ are in $R \cap O^=$. For this reason, we proceed as if $R$ was constructed by selecting $i$ elements from $O^=$ and then $(M - i)/2$ elements from $O^>$. Since $R \subseteq O$, we know that $N(R) \subseteq E$, and we will find it useful to partition $E$ into $E^0 \cup E^1 \cup E^2$ where, for $j = 0, 1, 2$, $E^j = \{b \in E : |N(\{b\}) \cap O^|= j\}$.

To illustrate these sets, let us consider one example for each set when $N = 5$. The string $01100 \in E^2$ since $N(\{b\}) \cap O^= = \{00100, 01110\}$. In general, $E^2$ contains binary strings in $E$ whose middle bit is one, and who disagree with their reverse in one of the first $(N - 1)/2$ positions. In other words, $b$ is in $E^2$ if $b[(N + 1)/2] = 1$, and $b[x] \neq b[N - x]$ has a unique solution for $0 \le x \le (N - 1)/2$. Then $N(\{b\}) \cap O^=$ contains the result of changing the $x$th or $(N - x)$th bit of $b$. The string $01010 \in E^1$ since $N(\{b\}) \cap O^= = \{01110\}$. In general, $E^1$ contains binary strings in $E$ whose middle bit is zero, and who are equal to their reverse. Then $N(\{b\}) \cap O^=$ contains the result of changing the middle bit of $b$ to one. The string $01001 \in E^0$ since $N(\{b\}) \cap O^= = \emptyset$. In general, $E^0$ contains the binary strings in $E$ that are not in $E^2$ or $E^1$.

This partition of $E$ is useful since

$$|\{c \in O^= : c \in R \implies b \in N(R)\}| = \begin{cases} 0 & \text{when } b \in E^0 \\ 1 & \text{when } b \in E^1 \\ 2 & \text{when } b \in E^2 \end{cases}$$

and

$$|\{c \in O^> : c \in R \implies b \in N(R)\}| = \begin{cases} N & \text{when } b \in E^0 \\ (N - 1)/2 & \text{when } b \in E^1 \\ N - 2 & \text{when } b \in E^2 \end{cases}$$

For example, when $N = 5$, let us consider the difference between $01100 \in E^2$, $01010 \in E^1$, and $01001 \in E^0$. If $01100 \in N(R)$ then one of $11100$, $00100$, $01000$, $01110$, $01101$ must be in $R$, so one of $00100$, $01110$ must be in $R \cap O^=$, or one of $11100$, $01000$, $10110$ must be in $R \cap O^>$. If $01010 \in N(R)$ then one of $11010$, $00010$, $01110$, $01000$, $01011$ must be in $R$, so $01110$ must be in $R \cap O^=$, or one of
11010, 01000 must be in $S \cap O^>$. Finally, if $01001 \in \mathcal{N}(R)$ then one of 11001, 00001, 01101, 01011, 01000 must be in $R$, so one of 11001, 10000, 10110, 11010, 01000 must be in $R \cap O^>$. The main thing to notice is that two neighbors of $b \in E^1$ can be reverses of each other, but this cannot happen when $b \in E^0 \cup E^2$. Now we are ready to compute $\mathcal{E}[|\mathcal{N}(R)|]$.

Note that $|O| = 2^{N-1}$ where $|O^-=| = 2^{(N-1)/2}$, and $|O^> = |O^<=| = 2^{N-2} - 2^{(N-3)/2}$. Similarly, $|E| = 2^{N-1}$, $|E^2| = (N-1)2^{(N-3)/2}$, $|E^1| = 2^{(N-1)/2}$, and $|E^0| = 2^{N-1} - (N+1)2^{(N-3)/2}$.

As before we can determine the expected size of the neighborhood by first deriving a certain probability, since

$$ \mathcal{E}[|\mathcal{N}(R(N, M))|] = |E|\Pr(b \in \mathcal{N}(R)|b \in E) \\ = |E|(1 - \Pr(b \notin \mathcal{N}(R)|b \in E)). $$

In each of the sums below, the summation is over all $i = 0, 1, \dots, M$ such that $(M - i)/2$ is an integer (i.e., such that $M$ and $i$ have the same parity).

$$ \begin{aligned} \Pr(b \notin \mathcal{N}(S)|b \in E) &= \Pr(b \notin \mathcal{N}(R)|b \in E^2)\Pr(b \in E^2|b \in E) + \\ & \quad \Pr(b \notin \mathcal{N}(R)|b \in E^1)\Pr(b \in E^1|b \in E) + \\ & \quad \Pr(b \notin \mathcal{N}(R)|b \in E^0)\Pr(b \in E^0|b \in E) \\ &= \left( \frac{\sum_i^{|O^-=|-1/2} \binom{|O^>|-(N-2)}{(M-i)/2}}{\sum_i^{|O^+=|} \binom{|O^>|}{(M-i)/2}} \right) \frac{N-1}{2^{(N+1)/2}} + \\ & \quad \left( \frac{\sum_i^{|O^+=|-1/2} \binom{|O^>|-(N-1)/2}{(M-i)/2}}{\sum_i^{|O^+=|} \binom{|O^>|}{(M-i)/2}} \right) \frac{1}{2^{(N-1)/2}} + \\ & \quad \left( \frac{\sum_i^{|O^-=|} \binom{|O^>|-N}{(M-i)/2}}{\sum_i^{|O^+=|} \binom{|O^>|}{(M-i)/2}} \right) \left( 1 - \frac{N+1}{2^{(N+1)/2}} \right) \end{aligned} \quad (9) $$

The asymptotic analysis is similar in spirit to that which was carried out before and yields the same results. These details will have to await the full paper.

# 4 Conclusion and Final Remarks

In this paper we have studied the number of polynomials at a fixed Hamming distance from any irreducible polynomial over $\mathbb{F}_2$, both experimentally, and under an idealized model that takes the irreducible polynomials to be uniformly distributed in natural ways. Perhaps surprisingly, these models do not exactly match the experimental data.

In the future, we will be computing the exact values shown in Table 1 to $n = 33, 34$ using tables that already have been computed. We may be able to extend these tables to $n = 35, 36$. We will also compute the “Hamming” distance to polynomials over other finite fields. Under our models the expected number of bitstrings at Hamming distance 4 is zero. Is there a “threshold” value of $M$ where this phenomenon first occurs?
Acknowledgements

We wish to thank the three referees for carefully reading the paper and spotting a number of typos and inconsistencies.

References

[BH97] A. Bérczes and L. Hajdu. Computational experiences on the distances of polynomials to irreducible polynomials. *Mathematics of Computation*, 66:391–398, 1997.

[Coh72] S. D. Cohen. Uniform distribution of polynomials over finite fields. *Journal of the London Mathematical Society*, 6:93–102, 1972.

[CRS+00] K. Cattell, F. Ruskey, J. Sawada, C.R. Miers, and M. Serra. Fast algorithms to generate necklaces, unlabelled necklaces and irreducible polynomials over GF(2). *J. Algorithms*, 37:267–282, 2000.

[Gou72] H. W. Gould. *Combinatorial Identities*. Morgantown Printing and Binding, Morgantown, VA., 1972.

[Hay65] D. R. Hayes. The distribution of irreducibles in GF([q, x]). *Transactions of the American Mathematical Society*, 117:101–127, 1965.

[HM92] T. Hansen and G.L. Mullen. Primitive polynomials over finite fields. *Mathematics of Computation*, 59:639–643, 1992.

[Jun93] D. Jungnickel. *Finite fields: Structure and Arithmetics*. BI-Wissenschaftsverlag, Mannheim, 1993.

[KGP89] D.E. Knuth, R.L. Graham, and O. Patashnik. *Concrete Mathematics*. Adison Wesley, second edition, 1989.

[LN94] R. Lidl and H. Niederreiter. *Introduction to finite fields and their applications*. Cambridge University Press, 1994.

[Uch55] S. Uchiyama. Sur les polynomes irréductibles dans un corps fini. ii. *Proc. Japan Acad.*, 31:267–269, 1955.