Jason (jcreed) wrote,
Jason
jcreed

Which non-prime finite fields are subfields of the complex numbers modulo a lattice? (I say non-prime just because all the prime fields are already trivially subfields of the reals modulo a single number) Is it just GF(4)? The picture I have in my head of a fundamental domain of the lattice is
    0---1---0
   / \ / \ /
  x---y---x
 / \ / \ /
0---1---0 (0=2)


Where x is a primitive 6th root of unity, so like the sum of any two of {x,y,1} is the third, and xy = 1, and..., you know, it behaves like how GF(4) behaves.

And also I can represent GF(7) differently from "the integers modulo 7" as living in a lattice with a fundamental domain like so:
   0
    \ / \      
    -5---6---0
      \ / \ /
     --3---4--
      / \ / \
     0---1---2-
          \ / \
               0

(the things I'm labelling 1 and 2 are really the complex numbers 1 and 2. The things labelled 3, 4, 5, 6 are the Eisenstein integers they spatially appear to be, and correspond to the evident elements of GF(7))

Similarly GF(5) can be made to look like
    0
    |   |
  --3---4---0
    |   |
0---1---2-- 
    |   |
        0

(with again 1 and 2 really being 1 and 2, and 3 ∈ GF(5) being 1 + i and 4 ∈ GF(5) being 2 + i)

Dunno if that is particularly meaningful.

---

Thoughts during lunch:

You can't do GF(pk) for any k ≥ 3 because there's not enough places for zeroes. Any x in the field has to have px = 0 mod the lattice, but there's only p2 distinct places in the fundamental domain on the lattice that have that property. So GF(8) is right out.

But at least GF(9) = GF(3)[x]/(x2 - x - 1) seems to be doable: writing y for -x = 2x just to make my ascii art fit better, I can do
 0 --- 1 --- 2 --- 0
 |     |     |     |
 |     |     |     |
y+2 -- y -- y+1 - y+2 
 |     |     |     |
 |     |     |     |
x+1 - x-1 -- x -- x+1
 |     |     |     |
 |     |     |     |
 0 --- 1 --- 2 --- 0

such that x=2+i is a generator mod the lattice {3,3i}, for the powers of x go like 1,x,x2,...,x7,x8 =
1, x, x+1, 2x+1, 2, 2x, 2x+2, x+2, 1

That's pretty weird, then. Can I do all fields GF(p2) like this? Can I make any sense of GF(pk) for any k ≥ 3 over some other base field? Obviously the quaternions aren't commutative, but maybe multiplication on some subset of it would end up commutative modulo a well-chosen lattice?

---

Hmm the only ones I can find now are
1 + 2i generates GF(9) mod {3,3i}.
1 + 2i generates GF(49) mod {7,7i}
1 + 4i generates GF(121) mod {11,11i}
1 + 2i generates GF(529) mod {23,23i}
so I guess squares of 3-mod-4 primes are more well-behaved?

---

Well at least for all primes up to 571 that are 3 mod 4, it seems like the p-by-p square of {a+bi|0 ≤ a, b < p}, modulo the lattice generated by {p,pi}, is isomorphic to GF(p2). (There's nothing special about 571, it's just the last prime in a list of primes I copy-pasted from somewhere)


#!/usr/bin/perl

sub testGenerator {
  my ($p, $zr, $zi) = @_;

  my ($x, $y) = (1, 0);
  my (%seen) = ();

  for ($t = 0; $t < $p * $p; $t++) {
    my $a = ($x * $zr - $y * $zi) % $p;
    my $b = ($y * $zr + $x * $zi) % $p;
    $x = $a;
    $y = $b;

    last if $seen{"$x,$y"};
    $seen{"$x,$y"} = 1;
  }
  return $t;
}

for (my $p = 3; $p < 1000; $p++) {
  for (my $x = 0; $x < 15; $x++) {
    if (testGenerator($p, 1, $x) == $p * $p - 1) {
      print "$p gen by 1 + ${x}i\n";
      last;
    }
  }
}



Oh! and it seems like GF(p2) for p = 2 mod 3 can be embedded in a nice p-by-p parallelogram in the Eisenstein integers.. So GF(169) is the first one I'm really uncertain about, since 13 is the smallest prime that's not 2 mod 3 or 3 mod 4.

---

There aren't any solutions of 0 = a2 + b2 mod p when p is a prime 3 mod 4 and 0 < a,b < p, are there? Then defining the inverse of a + bi in the usual way as a/(a2 + b2) + i * b/(a2 + b2) (where the divisions by a2 + b2 are taken in the field GF(p)) will always be well-defined.
Tags: finite fields, math
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 16 comments