# Boolean circular convolution

Let $\Bbb F_2$ be the finite field of order 2, and let $\Bbb F_2^n$ be the $n$-dimensional vector space over this field. Then we can equip this vector space with the convolution product to obtain the Boolean cyclic convolution algebra, where all addition is done mod 2.

If this were ordinary cyclic convolution over the reals, we could take the Fourier transform and view the algebra as isomorphic to pointwise multiplication, or a direct product of $\Bbb C$'s. However, we can't exactly take the ordinary Fourier transform given that we're working in $\Bbb F_2$, and tools like the number-theoretic transform don't work either given the low rank of the field we're working in.

However, is there some way that we can view this algebra, over $n$ dimensions, as injecting to a direct product of $n$ dimensions of some ring? In other words, is there something analogous to the Fourier transform that we can use here?

Your algebra is just the group algebra $\mathbb{F}_2[C_n]$ of the cyclic group $C_n$ over the field $\mathbb{F}_2$. This algebra can be identified with the ring $\mathbb{F}_2[x]/(x^n-1)$, where $x$ corresponds to a generator of $C_n$. If we had $\mathbb{C}$ instead of $\mathbb{F}_2$, we could factor $x^n-1$ as a product of distinct linear factors and thus by the Chinese remainder theorem get an isomorphism with $\mathbb{C}^n$, each copy of $\mathbb{C}$ being the quotient by one of the linear factors. This is exactly the Fourier transform.

Over $\mathbb{F}_2$ things are more complicated because $x^n-1$ will not factor as a product of $n$ distinct linear factors unless $n=1$. Instead, if $n=2^dm$ for $m$ odd, we have $x^n-1=(x^m-1)^{2^d}$ where $x^m-1$ splits as a product of distinct irreducible polynomials of varying degrees; these polynomials are all the possible minimal polynomials of $m$th roots of unity over $\mathbb{F}_2$. To find the degrees of these irreducible factors, note that a field $\mathbb{F}_{2^k}$ has a primitive $\ell$th root of unity iff $\ell\mid 2^k-1$, so the minimal polynomial of a primitive $\ell$th root of unity has degree equal to the least $k$ such that $\ell\mid 2^k-1$. The irreducible factors of $x^m-1$ will then have degrees ranging over all such $k$ where $\ell$ ranges over the divisors of $m$. (Note that there will typically be multiple such irreducible factors for any particular $\ell$. For instance, if $\ell=7$, then $k=3$, and there are two different minimal polynomials that a primitive $7$th root of unity can have, namely $x^3+x^2+1$ and $x^3+x+1$. In general, there are $\varphi(\ell)$ different primitive $\ell$th roots so they can have $\varphi(\ell)/k$ different minimal polynomials.)

If these irreducible factors are $p_i$, then by the Chinese remainder theorem we get an isomorphism $$\mathbb{F}_2[x]/(x^n-1)\cong\prod_i\mathbb{F}_2[x]/(p_i(x)^{2^d}).$$ Note moreover that $\mathbb{F}_2[x]/(p_i(x)^{2^d})\cong\mathbb{F}_2[u,v]/(p_i(u),v^{2^d})$ (let $u=x^{2^d}$ and $v=x-y$ where $y$ is the $2^d$th root of $u$ in the field $\mathbb{F}_2[u]/(p_i(u))$). Writing $K_i=\mathbb{F}_2[u]/(p_i(u))$ (which is a field), we thus get an isomorphism $$\mathbb{F}_2[x]/(x^n-1)\cong\prod_iK_i[v]/(v^{2^d}).$$

In particular, if $d=0$ (i.e., $n$ is odd), then this is just the product of the fields $K_i$. As above, the fields $K_i$ have the form $\mathbb{F}_{2^k}$ where $k$ is the least $k$ such that $\ell\mid 2^k-1$ for some odd divisor $\ell$ of $n$ (but each such field appears $\varphi(\ell)/k$ different times among the $K_i$). If $d>0$, then the factors in the product are the same fields but with nilpotent elements adjoined.

• Thanks for the answer. If I understand here, you're saying we have a direct product of different algebraic field extensions of $F_2$, depending on the length of the vector, right? – Mike Battaglia Jun 6 '17 at 19:49
• If $n$ is odd, yes. If $n$ is even we don't get fields. – Eric Wofsey Jun 6 '17 at 19:57
• OK. So in a big picture sense, for odd-dimensional spaces, we can view everything as injecting into a direct product of $\bar{\Bbb F_2}$'s, the algebraic completion of $\Bbb F_2$, which is basically the same as how the Fourier transform works for the reals. Is there a similar nice result for the even-dimensional case, where we can view it as a subdirect product of identical copies of some algebra over $\Bbb F_2$, but with nilpotents added? – Mike Battaglia Jun 6 '17 at 21:28
• In the even case, you could think of each factor in the direct product as a subring of $\overline{\mathbb{F}_2}[v_1,v_2,v_3,v_4,\dots]/(v_1^2,v_2^2-v_1,v_3^2-v_2,\dots)$ (send the nilpotent generator I called "$v$" to $v_d$). I don't know if this is particularly natural or useful though. – Eric Wofsey Jun 6 '17 at 21:40
• Ah, interesting! So nilpotents must have degree equal to some power of two then? – Mike Battaglia Jun 6 '17 at 21:46