3
$\begingroup$

I'm trying to figure out the number of solutions to a particular system of equations. The variables here are $A_1,A_2,A_3,B_1,B_2,B_3,C_1,C_2,C_3$, all in $\mathbb{F}_2$, constraint to

(a) $B_1^2 = A_1 C_1$,

(b) $A_1 C_2 + A_2 C_1 = 0$, and

(c) $A_1 C_3 + A_3 C_1 = 0$.

This problem actually relates to something I'm doing in algebraic geometry right now--I just suck at counting, so forgive me if they I have been approaching this isn't optimal. Here's what I've got so far:

$B_2, B_3$ are free, so that is 4 options.

I split the problem into two main cases, case 1 being when $B_1 = 1$ and when $B_1 = 0$.

Case $B_1 = 1$: Then $A_1 = C_1 = 1$ by (a). By (b), we must then have $A_2 + C_2 = 0$, and since we are in $\mathbb{F}_2$, this means that $A_2 = C_2$, so we have 2 options here. Likewise we must have $A_3 = C_3$ by (c), giving us 2 more options, independent from what we did in (b). So for this case, we have

(4 [from $B_2, B_3$]) $\times$ (2 [from $A_2, C_2$]) $\times$ (2 [from $A_3, C_3$]) = 16.

So it is just the case when $B_1^2 = 0$ that I am having difficulty with, as this implies either $A_1 = 0$ or $C_1 = 0$ (or both), splitting the problem into many sub-cases whhich might intersect.

$\endgroup$
1
  • $\begingroup$ Of course you might as well replace $B_1^2$ with $B_1$ throughout, in $\mathbb F_2$. $\endgroup$ May 15, 2013 at 23:44

1 Answer 1

0
$\begingroup$

I don't think the $B_1=0$ subcases are that bad. If $A_1=C_1=0$, then $A_2,A_3,C_2,C_3$ can be whatever they want. If $A_1=0$ but $C_1=1$, then $A_2=A_3=0$ but $C_2,C_3$ can be whatever. The case $C_1=0$ but $A_1=1$ is similar.

(If you really just care about this one specific problem, you can check all $2^9=512$ options by brute force!)

$\endgroup$
1
  • $\begingroup$ I wrote a Python program to do this by brute force and found 128 solutions. Hope this is correct. $\endgroup$
    – Chris
    May 15, 2013 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.