1
$\begingroup$

From what I understand, we have these two isomorphisms:

  • $(TC, +)$ is isomorphic to the cyclic group $\mathbb{Z}/2^n\mathbb{Z}$.
  • $(TC, *)$ is isomorphic to the multiplicative group of polynomials.

If this is correct, can we conclude that two's complement arithmetic produces a finite field isomorphic to $GF(2^{n}$)?

If not, what algebraic structure, if any, does two's complement representation and arithmetic produce? Because there just seems to be something there.

$\endgroup$
  • $\begingroup$ I'm afraid I don't know what TC-arithmetic really is, but it sure looks like the answer is No. The finite field $GF(2^n)$ is an $n$-dimensional vector space over $\Bbb{Z}_2$. Its additive group is isomorphic to bitwise XOR of $n$-bit masks. Its multiplication is more complicated. It is a lot like polynomials with coefficients in $\Bbb{Z}_2$, but modulo a chosen irreducible polynomial. Without an irreducible polynomial you won't get a group. The arithmetic of $GF(2^n)$ most emphatically has nothing to do with arithmetic modulo $2^n$, $x+x=0$ for all $x\in GF(2^n)$ (bitwise XOR!!). $\endgroup$ – Jyrki Lahtonen Feb 22 '16 at 7:55
  • $\begingroup$ It just seems like two's complement representation and arithmetic produces some kind of algebraic structure. Intuition suggests it must be something close to a finite field. If not, I was wondering what it was then. $\endgroup$ – Leo Heinsaar Feb 22 '16 at 10:10
  • $\begingroup$ Leo, if your multiplication as polynomials means, among other things, that $0x0002\cdot 0x0002=0x0004$, $0x0002\cdot0x0004=0x0008$, $0x0003\cdot0x0003=0x0005$ et cetera, then it becomes a problem that this multiplication does not mesh at all well with modular integer addition. $\endgroup$ – Jyrki Lahtonen Feb 22 '16 at 10:17
  • $\begingroup$ Thanks Jyrki. The answer below also makes a good point that TC arithmetic can't be a field itself because it has zero divisors. I just wanted to understand in more detail how close it gets. $\endgroup$ – Leo Heinsaar Feb 22 '16 at 10:29
4
$\begingroup$

As Jyrki Lahtonen has already said, the additive group is already a problem, since for $GF(2^n)$ it is $(\mathbb{Z}/2\mathbb{Z})^n$, not $\mathbb{Z}/2^n \mathbb{Z}$.

In fact, it cannot be a field, since it has zero-divisors: $2^k \cdot 2^{n-k} = 0$.

Two's complement arithmetic is isomorphic to the quotient in your question, $\mathbb{Z}/2^n \mathbb{Z}$, but not only as groups, but as rings, that is, with multiplication too. This structure is rarely a field, through (only if $n=1$).

$\endgroup$
  • $\begingroup$ Is it not a field only because it has zero divisors, or is there something else as well? (Because if it's just zero divisors, we can forgive it and give it an honorary field title for its enormous contribution to mankind. :-) $\endgroup$ – Leo Heinsaar Feb 22 '16 at 10:24
  • 1
    $\begingroup$ @LeoHeinsaar Well, it is associative, commutative and unital. Posessing zero devisors seems to be the first obstacle to being a field, all other stuff follows from that (lacking multiplicative inverses, having proper nontrivial ideals, etc). $\endgroup$ – lisyarus Feb 22 '16 at 10:31

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.