In polynomial quotient rings over $\mathbb{F}_2$, how to use Chinese Remainder Theorem to solve equations?

Question

Suppose I work over the polynomial quotient ring $\mathbb{F}_2[x,y]/\langle x^m+1,y^n+1\rangle$, and I want to solve for polynomials $s[x,y]$ that simultaneously solve the equations

\begin{equation} a[x,y]s[x,y]=0,\quad b[x,y]s[x,y]=0. \end{equation}

How do I use the Chinese Remainder Theorem to count the number of solutions? Without it, one thing I tried was to write $a[x,y]$ and $b[x,y]$ as sums of the irreducible cyclotomic polynomials that comprise $x^m+1$, for example $x^3+1=(1+x)(1+x+x^2)$ and $y^3+1=(1+y)(1+y+y^2)$, so we can write $y+y^2+x^3$ as $(1+y+y^2)+(1+x^3)$ over $\mathbb{F}_2$. Then it's easy to find annihilators $s[x,y]$, and use the remaining degrees of freedom that bounds your polynomial degree to count how many solutions exist. This works fine for some cases but I also noticed that in a lot of cases I underestimated the number of solutions. I feel like Chinese Remainder Theorem can be used here to have a more concrete evaluation of solutions.

Answer 1

This is not a full solution, and there are aspects I'm unhappy about in this approach. Yet, I manage to give an algorithm for giving a description of all the ideals of this ring in what I think of as the simple case, where both $m$ and $n$ are odd. The simple case does cover quite a bit of ground. An IMO apt comparison is with the theory of binary cyclic codes, where odd length is often assumed (and similarly simplifies things).

The outcome is that the ideals are direct sums of finite fields. Furthermore, the finite fields appearing as summands are quite analogous to the minimal cyclic codes. For example, they, too, can be given in terms of idempotents of your ring.

In spite of my comment, the Chinese Remainder Theorem does play a role, but the exact way it works is still not clear enough to me :-(

---

The algebra $\Bbb{F}_2[x,y]/\langle x^m+1, y^n+1\rangle$ is isomorphic to the group algebra of the direct product $G=C_m\times C_n$. It is easy to show that we have an isomorphism of groups: $$ C_m\times C_n\simeq C_{\mathrm{lcm}(m,n)}\times C_{\gcd(m,n)} $$ I will use the more canonical form on the right hand side. After all, it follows that we can (up to isomorphism) replace $n$ with $\gcd(m,n)$ and $m$ with the least common multiple. Or, equivalently, without loss of generality we can assume that $n\mid m$.

Let us first decompose $\Bbb{F}_2[y]/\langle y^n+1\rangle$. This is equivalent to classifying binary cyclic codes of length $n$, which works out nicely if and only if $y^n+1$ has no repeated factors in $\Bbb{F}_2[y]$. This is the case if and only if $2\nmid n$. Due to the fact that in this the derivative $D(y^n+1)=ny^{n-1}=y^{n-1}$ is non-zero (and obviously has no common factors with $y^n+1$).

So we have a unique factorization $$ y^n+1=\prod_{j=1}^kf_j(y),\tag{1} $$ where $f_j(y)$, $j=1,2,\ldots,k$, are all pairwise distinct irreducible polynomials in $\Bbb{F}_2[y]$. By CRT $(1)$ implies an isomorphism of rings $$ R_y:=\Bbb{F}_2[y]/\langle y^n+1\rangle\simeq\bigoplus_{j=1}^k\Bbb{F}_2[y]/\langle f_j(y)\rangle.$$ Here the quotient ring $K_j=\Bbb{F}_2[y]/\langle f_j(y)\rangle$ is actually a field of cardinality $|K_j|=2^{\deg f_j(y)}$. In other words $$ R_y\simeq \bigoplus_{j=1}^kK_j.\tag{2} $$

Let's bring in the $x$! We have natural a identification and then a decomposition $$\Bbb{F}_2[x,y]/\langle x^m+1,y^n+1\rangle= R_y[x]/\langle x^m+1\rangle\simeq\bigoplus_{j=1}^kK_j[x]/\langle x^m+1\rangle.\tag{3}$$

It's the same old business again! Assuming that $2\nmid m$, the polynomial $x^m+1$ has no repeated factors in $K_j[x]$, and hence it factors as $$ x^m+1=\prod_{i=1}^{\ell_j}g_{j,i}(x), $$ where $g_{j,i}(x)$, $i$ varying, are pairwise distinct irreducible polynomials over $K_j$. Furthermore $$ K_j[x]/\langle x^m+1\rangle\simeq\bigoplus_{i=1}^{\ell_j}L_{j,i}, $$ where the field $L_{j,i}=K_j[x]/\langle g_{j,i}(x)\rangle$.

Putting this all together we conclude that $$ \Bbb{F}_2[x,y]/\langle x^m+1,y^n+1\rangle\simeq\bigoplus_{1\le j\le k, 1\le i\le \ell_j}L_{j,i}.\tag{4} $$

---

Given the decomposition $(4)$, your question becomes easy. All the components are fields, and the sum/product in the ring has become the componentwise sum/product of entries from the fields. So, if we can figure out the isomorphic images of $a[x,y]$ and $b[x,y]$ $$ a[x,y]\mapsto (a_{j,i})_{1\le j\le k, 1\le i\le \ell_j},\qquad b[x,y]\mapsto (b_{j,i})_{1\le j\le k, 1\le i\le \ell_j}, $$ "all" we need to do is to figure out the locations $(i,j)$ of the non-zero components $a_{i,j}$ and $b_{i,j}$. After all, $$s[x,y]\mapsto (s_{j,i})_{1\le j\le k, 1\le i\le \ell_j} $$ is a solution of your system if and only if $s_{i,j}a_{i,j}=0=s_{i,j}b_{i,j}$ for all pairs $(i,j)$. In particular, the space of solutions $s[x,y]$ is the direct sum of those component fields $L_{j,i}$ such that $a_{i,j}=0=b_{i,j}$.

However, it is not exactly easy write down the decomposition isomorphism $f[x,y]\mapsto (f_{j,i})$, so I am not satisfied with this. I hope to be able to describe the idempotents $e_{j_0,i_0}[x,y]$ corresponding to the decomposition $(4)$. Those are the preimages of the tuples $(e_{j,i})$ where we have a single $1$ at a given position $(j_0,i_0)$ and zeros elsewhere. It should be possible to describe the idempotents more explicitly, but I need more time. Hopefully more to come.

Answer 2

A different approach based on two dimensional discrete Fourier transforms. Still assuming that $n\mid m$ (w.l.o.g., see the other answer) as well as $2\nmid m$ so that the group algebra $$ R=\Bbb{F}_2[x,y]/\langle x^m+1,y^n+1\rangle\simeq \Bbb{F}_2[C_m\times C_n] $$ is semi-simple.

---

Let $K$ be the smallest extension field containing a primitive root of unity $\zeta$ of order $m$. In other words, let $\ell$ be the smallest positive integer such that $m\mid 2^\ell-1$, when $K=\Bbb{F}_{2^\ell}$. Let $\xi=\zeta^{m/n}$ be a primitive root of unity of order $n$, and let $\mu_m=\langle\zeta\rangle$ and $\mu_n=\langle\xi\rangle$ be the respective groups of roots of unity.

Because the elements of $R$ are polynomials modulo $x^m+1$ and $y^n+1$, for every pair of roots pof unity $(z,w)\in\mu_m\times\mu_n$ the mapping $$ \chi_{z,w}:R\to K, f(x,y)\mapsto f(z,w) $$ is well defined.

Another key ingredient is that the coefficients of the polynomials $f(x,y)$ belong to the prime field $\Bbb{F}_2$. This will mesh nicely with the Frobenius automorphism $F:K\to K, u\mapsto u^2$ in the sense that $\chi_{z,w}$ fully determines $\chi_{z^2,w^2}$ via the relation $$ \chi_{z^2,w^2}(f)=f(z^2,w^2)=f(z,w)^2=\chi_{z,w}(f)^2. $$

In other words, we can partition the group $\mu_m\times\mu_n$ into cyclotomic cosets = the orbits of the Galois action. These are equivalence classes of the relation $$ (z,w)\sim (z',w')\Leftrightarrow z'=z^{2^j}, w'=w^{2^j}\ \text{for some $j, 0\le j<\ell$.} $$

We see that the size of the equivalence class $[(z,w)]$ is equal to the degree of the field extension $[\Bbb{F}_2(z,w):\Bbb{F}_2]$. Furthermore, $$\Bbb{F}_2(z,w)=\mathrm{Im}(\chi_{z,w}).$$

So if we fix, once and for all, a set of representatives $D\subset \mu_m\times\mu_n$ of equivalence classes, we get a mapping $$ \chi:R\to\bigoplus_{(z,w)\in D}\Bbb{F}_2(z,w) $$ by declaring $\chi(f)$ to be the $|D|$-tuple $(f(z,w))_{(z,w)\in D}$. Next I turn that direct sum of finite fields into a ring with componentwise operations. Then

• $\chi$ is a homomorphism of rings (obvious), and
• $\chi$ is bijective (the underlying DFT has an inverse), so an isomorphism of rings (equal to the Wedderburn decomposition in my other answer), and hence
• a product $as=0$, $a,s\in R$, if and only if $a(z,w)s(z,w)=0$ for all $(z,w)\in D$.

---

This (finally) gives some kind of an answer to the question. The OP specified two elements $a(x,y), b(x,y)\in R$.

• Let $J$ be the subset $$J=\{(z,w)\in D\mid a(z,w)\neq0\ \text{or}\ b(z,w)\neq0\}.$$
• We have $a(x,y)s(x,y)=0_R=b(x,y)s(x,y)$ if and only if $s(z,w)=0$ for all $(z,w)\in J$.
• The space $V(a,b)$ of solutions $s(x,y)\in R$ of $as=0=bs$ has dimension $$\dim V(a,b)=\sum_{(z,w)\notin J}[\Bbb{F}_2(z,w):\Bbb{F}_2].$$