The Distance to a Squarefree Polynomial Over ${\mathbb{F}}_2[x]$

Abstract

In this paper, we examine how far a polynomial in ${\mathbb{F}}_2[x]$ can be from a squarefree polynomial. For any $\epsilon >0$, we prove that for any polynomial $f(x)\in {\mathbb{F}}_2[x]$ with degree $n$, there exists a squarefree polynomial $g(x)\in {\mathbb{F}}_2[x]$ such that $\mathrm{deg}(g)\le n$ and $L_2(f-g)<(\ln n{)}^{2\ln (2)+\epsilon }$ (where $L_2$ is a norm to be defined). As a consequence, the analogous result holds for polynomials $f(x)$ and $g(x)$ in $\mathbb{Z}[x]$.