How to interpret "multiplication" in this representation of $GF(2)$?

70 Views Asked by At

Most students' first encounter with the concept of "isomorphism" -- probably long before they learn the word -- comes from recognizing that the rules for adding odd and even numbers have the same structure as the rules for multiplying positive and negative numbers: that is, we have

$$\textrm{Even} + \textrm{Even} = \textrm{Even}$$ $$\textrm{Even} + \textrm{Odd} = \textrm{Odd}$$ $$\textrm{Odd} + \textrm{Odd} = \textrm{Even}$$

and also

$$\textrm{Positive} \times \textrm{Positive} = \textrm{Positive}$$ $$\textrm{Positive} \times \textrm{Negative} = \textrm{Negative}$$ $$\textrm{Negative} \times \textrm{Negative} = \textrm{Positive}$$

These two sets of rules are structurally "the same", in the sense that if you replace "Even" with "Positive", "Odd" with "Negative", and "+" with "$\times$", the first set of rules becomes identical with the second set of rules.

More formally, we define this "sameness" as an isomorphism, and we say that the two groups $$\langle \{\textrm{Even}, \textrm{Odd} \}, + \rangle$$ and $$\langle \{\textrm{Positive}, \textrm{Negative} \}, \times \rangle$$

are isomorphic — and in fact, both are isomorphic to the group $\mathbb Z/(2)$. We have the following correspondences:

Evens and Odds Positives and Negatives $\mathbb Z_2$
Even $\Longleftrightarrow$ Positive $\Longleftrightarrow$ 0
Odd $\Longleftrightarrow$ Negative $\Longleftrightarrow$ 1
$+$ $\Longleftrightarrow$ $\times$ $\Longleftrightarrow$ $+$ (modulo 2)

But $\mathbb Z/(2)$ is not only a group; it is also a field. That is to say, there is a multiplication operation in $\mathbb Z/(2)$, which corresponds to multiplication in $\{ \textrm{Even}, \textrm{Odd} \}$, and which can be expressed by the following rules:

$$\textrm{Even} \times \textrm{Even} = \textrm{Even}$$ $$\textrm{Even} \times \textrm{Odd} = \textrm{Even}$$ $$\textrm{Odd} \times \textrm{Odd} = \textrm{Odd}$$

My question is: What, if anything, is the "natural" interpretation of this operation in the context of positive and negative numbers? That is, is there some operation (say $\boxdot$) on integers that obeys the rules

$$\textrm{Positive} \boxdot \textrm{Positive} = \textrm{Positive}$$ $$\textrm{Positive} \boxdot \textrm{Negative} = \textrm{Positive}$$ $$\textrm{Negative} \boxdot \textrm{Negative} = \textrm{Negative}$$

so that we could fill in the middle cell of the bottom row of the following table?

Evens and Odds Positives and Negatives $\mathbb Z_2$
Even $\Longleftrightarrow$ Positive $\Longleftrightarrow$ 0
Odd $\Longleftrightarrow$ Negative $\Longleftrightarrow$ 1
$+$ $\Longleftrightarrow$ $\times$ $\Longleftrightarrow$ $+$ (modulo 2)
$\times$ $\Longleftrightarrow$ ???? $\Longleftrightarrow$ $\times$ (modulo 2)
1

There are 1 best solutions below

5
On BEST ANSWER

Gerry Myerson has hit the nail on the head. Not only will $\max$ work, but there is a whole field of study which does exactly this - called “max-plus algebra” or “tropical algebra” in honour of its inventor Imre Simon, who lived and worked in Brazil.

The thing is a semiring rather than a ring because “max” has no inverse. It has applications in operational research and when looking at travel across networks. There is a moderately interesting Wikipedia article but a wider search of the Web produces better and more instructive results.