smallworld

February 21, 2012

Success, to a degree.

Executable (my POV) jar is here
Executable (your POV) jar is here

  • Yellow = the circle along which the segment lies, green = the circle cutting the yellow circle at right angles.
  • Results are only correct if both ends of the line segment are inside the unit circle. If both ends are outside, sometimes the algorithm picks the path that runs through the unit circle. This means that if you are drawing lines from outside to outside, your best bet is to invert the unit circle, find the line, then invert the result.
  • Note that if the overall transform is fiddled with with the sliders, the “inside the unit circle” rule applies to the *untransformed* “inside”.
  • “drag the transform” is completely buggy.
  • Haven’t handled the case where the circle or its cutter is a straight line.
    if(segment.isLine())
      if(cutter.isPosCircle())
        return new Line2D.Double(a, b);
      else
        return null;
    else		
    if(cutter.isLine())
      return null;
    else
    if (cutter.isPosCircle())
      return Draw.arcNegative(c, a, b);
    else 
      return Draw.arcPositive(c, a, b);
    
    • However, it seems that now I have enough graphics primitives to draw a network on a conformal projection of the elliptic plane. And hyperbolic, for that matter.

      So now to the next bit.

      1. I have a set of nodes.
      2. The nodes have icons and state.
      3. Each node “participates” in two separate graph structures.
      4. Graph A is an arbitrary directed graph. Arcs have properties and end decorations.
      5. Graph B is a tree structure. Nodes can be within nodes.
      6. In terms of graph B, each node is a unit circle. The nodes “within” it are circles at some location with in it.
      7. The location of a node within a node is specified by a moebus transformation that maps the unit circle onto the location where the contained node is.
      8. This allows us to do nesting by composition of transforms.
      9. To display, a given node has the focus and is drawn as the main circle on the screen.
      10. This central circle has an outside and an inside.
      11. Either of these areas can display the “contents” of the node or the “context” of the node.
      12. The “normal” display is context outside, contents inside. Its what you would get if you did a zoom.
      13. If both the ouside and the inside display the same (context/context or content/content), then we draw the short line segments. You see both images of anything and the graph is drawn compactly.
      14. If both the ouside and the inside display the same (context/context or content/content), and a graph A arc needs to be drawn that crosses the border, then either the arc is not drawn, or the arc is drawn from the node to the border – the unit circle serves as a sort of vanishing horizon.
      15. When a graph A arc spans multiple tree steps – a choice
        1. Draw the arc relative to the current focus
        2. Draw the arc relative to the top of the tree
        3. Draw the arc relative to the higest node that contains both
        4. Draw the arc as a number of segments. I prefer this, because I think it will serve to “gather” arcs into pathways that make sense.
      16. Animate focus changes. Anything else will just not work.


      (pretend the blue crosses are closer on the outside than the inside)


smallworld

February 18, 2012

Ok! Where do the segment and it’s cutter intersect? Solving the equation is way too complicated and you wind up with a pair each of bletcherous quadratics for x and y. How to work out which two of the four combintions are the right ones? Gotta be an easier way.

And there is.

Build a mobius transformation H that moves the centre of segment to zero and the center of cutter ∞. The third point is arbitrary (perhaps make the mid point of the two center points fixed). [edit] Actually, it would be nice to have a method that builds a transformaion that moves two points to 0 and ∞ (and on that moves then to 0 and 1) with a k conjugate to the identity. can it be done? … I think so. There the right number of degrees of freedom for there to be a unique solution … but on second though, no. For two arbitrary points on a sphere, you cant move ’em to 0 and ∞ without getting bendy (in most cases). Only exception is when they are already opposite.

Since we know that the circle and its cutter are at right angles, the result will always be segment' = a circle centered on 0 and cutter' = a straight line passing through 0. From the radius of segment' and the slope of cutter', it’s easy to calculate points a' and p'. Transform them back by H-1, and we are done! As a bonus, this solution is general, having only the 2 cases where segment is a positive or a negative circle, and this affects only the sense of the arc, which we already know we have to handle.

I will have to update my code so that the transform correctly handles transforming the point at infinity, and generating the 0,1,∞ transform where one of the starting points is the point at infinity.


[update] Actually, If I move the centers of the circles to 0 and 1, then the points a and b must lie on the semicircles connecting the two and I can derive them from the radii. That means I can calculate them without having to fart around with line slopes.


Smallworld

February 16, 2012

Well, the graphics primitives are coming along. The big one is line segment.

I have defined a line segment as a circle “segment” cut by another circle “cutter” at right angles. I have two primitives – one to get an “elliptical” segment, one to get a “hyperbolic” segment. Both should work when the two points are inside the unit circle.

These depend on three methods – get a circle in elliptical space, get a circle in hyperbolic space, get a circle that cuts another at right angles.

The first two rely on finding a circle through three points. For the elliptical ones, the points are A, B, and -conj(1/a) and -conj(1/b). If A is on the boundary of the unit circle, I use the image of B as the third point. If both are on the boundary, then you can’t actually construct a unique elliptical circle, so I ignore that case.

The hyperbolic case uses conj(1/a) or conj(1/b) as the third point.

Computation of the cutting circle is as per the previous discussion. Project a,b,and the centre of the circle to 0,1,inf. transform the circle (-5,0) radius .5 by the inverse.

transforming the segment is simply a matter of transforming the circles, which we already know how to do.

To draw the shape, there are several cases.

Circle cut by circle. We find points A and B where they cross. The question is – do we draw the clockwise arc, or the counterclockwise arc? to do this, we look at the handedness of the circles. I think it will depend purely on the handedness of segment – just imagine the situation where the cutter flips: it makes no difference. This being the case, it also takes care of the circle being cut by a line.

Line cut by a circle. There are two cases, which depend on the sign of the cutter. If the cutter is positive, we draw the segment. If cutter is negative, we draw two segments from A and B to the edge of the clipping rectangle in opposite directions.

Line cut by a line. Either A or B will be non-infnite. We need to draw a segment from there to the clipping rectangle.

Hmm. So only 4 cases, really. Cool bananas. Have to find out how to get the two intersection points. Hans has a cookbook solution.


Smallworld

January 22, 2012

I rock.

I now have generalised circles drawing properly. Looks great. Weird, but makes intuitive sense when you play with the draggers. I’ve noticed this before: while you are writing the code, the lines and arcs skip around the screen in weird ways but with an underlying logic that you can sort of grasp. When you finally get it right, they move in ways that are just a little dull, by comparison. They give you an “Oh. Is that all?” feeling. The motions lock together in predictable ways.

Anyway. The next issue is drawing line segments. This is kinda crucial, because network graphs tend to be made of them.

How to model them? One way is just to keep points a and b, but that does not uniquely specify a line. Oh sure – it does if the unit circle is the elliptic plane, but my thingy is rapidly going to get too complicated for that to work well.

Ok. How about modelling it as a circle Γ, which contains the line segment, end points a and b? Well – that’s numerically unstable. I seriously dislike it – a and b will drift away from Γ. It will actually work ok, mostly, but it won’t be as nice as it could be.

So, how about two circles Γ, which contains the line segment, and Ζ, which cuts Γ at points a and b? That portion of the boundary of Γ which happens to lie inside Ζ is our line segment.

Cool. Now we are getting there. But how to choose Ζ? There’s a pencil of circles that will do the job. Well, we could just take the straight line that cuts a and b and use that. Under transformation, it will still be correct. The problem there is if Γ happens to be a straight line. Well, what about the circle where ab is a diameter? It will always be smaller than Γ. Well … except in the case where ab happens to be a diameter of Γ. This is a general problem: we need a simple way of choosing a suitable Ζ which is never identical to Γ.

The circle at right angles to Γ which intersects it at a and b fits the bill perfectly.

But how to find it? Easy as pie!

Create the moebius transform Η that maps a to (-1,0), b to (1, 0), and the center of Γ to ∞. (an if{} to handle when Γ is a straight line – easy) Our line segment ab is now the straight line from (-1,0) to (1, 0). Our Ζ’ is simply the unit circle. And so Ζ is simply the unit circle transformed by Η-1, which we already know how to do. Voila!

So, with class “LineSegment” modelled as two circles, I need some graphics primitives to return a java Shape for the arc. Transforming the segment is a matter of transforming the circles that describe it, which we can already do.

I probably need a constructor as well. In addition to a general one, and one that creates a straight line, I want one that specifically returns that line segment from a to b where a to be are inside the unit circle and the segment is a straight line in elliptical space (ie: the stereographic projection of). Shoot – while I’m at it I may as well do a constructor for the poincare projection of hyperbolic space, too.

Straight lines in the projection of elliptical space are circles that pass through the unit circle at diametrically opposite points. Straight lines in the Poincare projection of hyperbolic space are circles at right angles to the unit circle. In both cases, they are unique for a given ab with the stipulation that they don’t cross the circle (meaning that there’s a possibility of fun when a or b is on the unit circle).

Note that in hyperbolic space, a point p can be identified with 1/p. In elliptical space, p can be identified with -1/p. This means that given a segment ab, the shortest line segment joining them is not necessarily the segment contained in the unit circle. This will become important much, much later :) .


SmallWorld

January 22, 2012

So. I’m currently attempting to write the graphics primitives for smallworld. I have

The gear that translates from math coordinates to screen coordinates.
This is important, because most of the time the “circles” will be oval in user-land. You can’t just transform the geometry, because that means that the strokes and fonts get transformed as well. Happily, java has an AffineTransform class which has a method to transform a Java2D Shape object. You manage the underlying geometry on the unit circle, get the shape, transform it, and then stroke the shape as the final step. “The Gear” that does this is a method whose job it is to get the affine transform that converts a unit circle onto a given bounding box.
A Complex class
In addition to providing methods, having a complex class allows you to see what is in math land and what’s in screen land. I consistently use “Complex” for math co-ordinates, and “Point” for screen coordinates.
A matrix class
Rather than writing or using some über matrix class, I have gone minimal. The class handles 2×2 complex matrices, and that’s all. It holds the coordinates in an array of 8 doubles. The main job of the class, really, is to hold my decisions about whether the matrix is by row or by column – to keep track of which elements hold the parts of A, B,C and D.

I am assuming a single-threaded model, and so my scratch variables are all static final. This might be a mistake.

A moebus transformation class
Extends matrix, includes obvious gear.
A circle class
Extends matrix. We represent projective circles as per my bible and cookbook: Hans Schwerdtfeger’s “The Geometry of Complex Numbers”.

I have a little test app. Below the canvas are two sliders. One does a elliptic transform with fixed points at (-1,0)(1,0), and one does a rotation around (0,0). There’s a button to refers the order in which the transforms are composed. The app draws various things – point, lines and whatnot – transformed by the sliders. It correctly handles the java “Insets” and borders.

Currently I am trying to get circles drawing correctly.

The method for doing this has signature:

public Shape getShape(Shape clip)

Why do we need to pass the clip in? Because a circle may be “inside-out” when projected stereographically onto the plane. It will be inside-out if the inside of the circle covers the point at infinity. To make this happen, the “shape” returned by this method is the circle (drawn anticlockwise) and the clipping boundary (drawn clockwise). To keep any stroking from being visible, I take the clip rectangle of the canvas and add a 50-pixel fudge factor around it. If no-one is using strokewidths of 100 or more, I’m ok. Of course, this clip rectangle has to be converted into math space in order for it to be correct when its converted back again.

Now … working out if a circle is inside out or not is straightforward for circles. Circles are represented by a hermitian matrix

Γ(z) = Az(z*) + Bz + C(z*) + D

The “inside” of the circle is when Γ(z) is positive (or is it negative?), the border of the circle is at Γ(z) = 0. A circle is an inside-out circle when Re(A) < 0.

But I'm having difficulty with lines. It's not arbitrary. When a circle is smoothly transformed from a positive to a negative circle (the circle passes over the point at infinity), it's important to fill the correct side of the line. One check might be: find the value of c(0) and work it out from there, but this fails if the line passes through 0.

I'm suspecting that I'll have to do something like:

Find the line Γ' at right-angles to the line Γ which passes through 0. The construction of this line will automagically take into account the "direction" of Γ. In the matrix representation of Γ', A and D will both be zero, and C will simply be the conjugate of B. So you should be able to work out which side of circle Γ should be filled from that.

Drawing the shape is another issue. It will be something like:

Work out where the line Γ intersects the boundaries of the clipping rectangle (extended off the screen). Note that in the case of horizontal and vertical lines, this will be NaN.
Choose to use either the spots where Γ hits the vertical edges of the clip rect, or the spots where it hits the horizontal edges. Note that these may be off screen. …
No, actually that won't work well. What I really want to do is construct a triangle from the correct corner of the bounding box (which is off screen, remember) to …
No, that won't work either. Drat. My cases are:

  • Horizontal line
  • Horizontal line entirely off screen
  • Vertical line
  • Vertical line entirely off screen
  • Line passing through diagonally adjacent corners
  • Line passing through diagonally adjacent corners of the bbox
  • Line that can safely be represented as going through horizontally opposite sides of the bbox
  • Line that can safely be represented as going through horizontally opposite sides of the bbox, but owing to its vertical position it is off screen
  • Line that can safely be represented as going through vertically opposite sides of the bbox
  • Line that can safely be represented as going through vertically opposite sides of the bbox, but owing to its horizontal position it is off screen

Times 2, because the “filled” half plane may be either side of the line. Note that the “entirely off screen” lines are all the same: either a null shape is returned, or the bounding box as a shape.

Sigh. This kind of code is a drag to test, because you never know if you might have missed some weird combination that makes your screen flicker as the parameters pass over a badly-handled spot.

I do think that all cases can be done as a triangle that extends off screen, except for horizontal and vertical lines, which are easy to test for.

—-

Hang on. I have a clip rect. I have a method that will tell me if a point is “inside” the circle. All I have to do is find out if the corners of the rectangle are inside or outside, and work from there. There are 14 cases, not including cases where the line passes through a corner.


Constructing Finite Fields

February 11, 2011

Ok.

As a shortcut to get to GF(81), you can find an irreducible quartic over GF(3). Adjoin a root alpha and all elements are of the form a + b*alpha + c*alpha^2 + d*alpha^3 for a,b,c,d in GF(3).

So. To build GF(27), we find an irreducible cubic over Z(3), call its root β, and the basis vectors become β0, β1, β2.

Ok. Let’s pick x3+2x+2. For 0, 1, 2, this expression evaluates to 2, 2, 2 – no root in Z(3). Cool. We call the root β. Rearranging,β3 = β+1.

(hmm … I wonder how you factor this? The quadratic was easy: x2-2=0 factors into (x-α)(x+α) )

Well! This makes much more sense! No more “What is αβ?”. Anything bigger than ß2 reduces down, and it does so in a way that is interesting enough to be believable:

β3 = β+1
β4 = (β+1)β = β2
β5 = (β+1)β2 = β322+β+1
β6 = (β+1)(β+1) = β2+2β+1

What, I wonder, does our multiplication table look like?

001 002 010 011 012 020 021 022 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222
002 001 020 022 021 010 012 011 200 202 201 220 222 221 210 212 211 100 102 101 120 122 121 110 112 111
010 020 100 110 120 200 210 220 011 021 001 111 121 101 211 221 201 022 002 012 122 102 112 222 202 212
011 022 110 121 102 220 201 212 111 122 100 221 202 210 001 012 020 222 200 211 002 010 021 112 120 101
012 021 120 102 111 210 222 201 211 220 202 001 010 022 121 100 112 122 101 110 212 221 200 002 011 020
020 010 200 220 210 100 120 110 022 012 002 222 212 202 122 112 102 011 001 021 211 201 221 111 101 121
021 012 210 201 222 120 111 102 122 110 101 002 020 011 212 200 221 211 202 220 121 112 100 001 022 010
022 011 220 212 201 110 102 121 222 211 200 112 101 120 002 021 010 111 100 122 001 020 012 221 210 202
100 200 011 111 211 022 122 222 110 210 010 121 221 021 102 202 002 220 020 120 201 001 101 212 012 112
101 202 021 122 220 012 110 211 210 011 112 201 002 100 222 020 121 120 221 022 111 212 010 102 200 001
102 201 001 100 202 002 101 200 010 112 211 011 110 212 012 111 210 020 122 221 021 120 222 022 121 220
110 220 111 221 001 222 002 112 121 201 011 202 012 122 010 120 200 212 022 102 020 100 210 101 211 021
111 222 121 202 010 212 020 101 221 002 110 012 120 201 100 211 022 112 220 001 200 011 122 021 102 210
112 221 101 210 022 202 011 120 021 100 212 122 201 010 220 002 111 012 121 200 110 222 001 211 020 102
120 210 211 001 121 122 212 002 102 222 012 010 100 220 221 011 101 201 021 111 112 202 022 020 110 200
121 212 221 012 100 112 200 021 202 020 111 120 211 002 011 102 220 101 222 010 022 110 201 210 001 122
122 211 201 020 112 102 221 010 002 121 210 200 022 111 101 220 012 001 120 212 202 021 110 100 222 011
200 100 022 222 122 011 211 111 220 120 020 212 112 012 201 101 001 110 010 210 102 002 202 121 021 221
201 102 002 200 101 001 202 100 020 221 122 022 220 121 021 222 120 010 211 112 012 210 111 011 212 110
202 101 012 211 110 021 220 122 120 022 221 102 001 200 111 010 212 210 112 011 222 121 020 201 100 002
210 120 122 002 212 211 121 001 201 111 021 020 200 110 112 022 202 102 012 222 221 101 011 010 220 100
211 122 102 010 221 201 112 020 001 212 120 100 011 222 202 110 021 002 210 121 101 012 220 200 111 022
212 121 112 021 200 221 100 012 101 010 222 210 122 001 022 201 110 202 111 020 011 220 102 120 002 211
220 110 222 112 002 111 001 221 212 102 022 101 021 211 020 210 100 121 011 201 010 200 120 202 122 012
221 112 202 120 011 101 022 210 012 200 121 211 102 020 110 001 222 021 212 100 220 111 0
02
122 010 201
222 111 212 101 020 121 010 202 112 001 220 021 210 102 200 122 011 221 110 002 100 022 211 012 201 120

Let’s check it for at least one. According to our table, 211*101=212.

(2β2+β+1)(β2+1)
= (2β432)+(2β2+β+1)
= 2β43+3β2+β+1
≡ 2β43+β+1
= 2(β2+β)+(β+1)+β+1
= 2β2+2β+β+1+β+1
= 5β2+4β+2
≡ 2β2+1β+2

QED!


Ok. Why does it have to be an irreducible polynomial? What happens if you pick a polynomial that isn’t irreducible? I expect that what you wind up with isn’t a group.

(x+1)(x+1)(x)
(x2+2x+1)(x)
x3+2x2+x
γ3 = γ2+2γ
γ4 = γ3+2γ2

001 002 010 011 012 020 021 022 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222
002 001 020 022 021 010 012 011 200 202 201 220 222 221 210 212 211 100 102 101 120 122 121 110 112 111
010 020 100 110 120 200 210 220 021 001 011 121 101 111 221 201 211 012 022 002 112 122 102 212 222 202
011 022 110 121 102 220 201 212 121 102 110 201 212 220 011 022 000 212 220 201 022 000 011 102 110 121
012 021 120 102 111 210 222 201 221 200 212 011 020 002 101 110 122 112 121 100 202 211 220 022 001 010
020 010 200 220 210 100 120 110 012 002 022 212 202 222 112 102 122 021 011 001 221 211 201 121 111 101
021 012 210 201 222 120 111 102 112 100 121 022 010 001 202 220 211 221 212 200 101 122 110 011 002 020
022 011 220 212 201 110 102 121 212 201 220 102 121 110 022 011 000 121 110 102 011 000 022 201 220 212
100 200 021 121 221 012 112 212 120 220 020 111 211 011 102 202 002 210 010 110 201 001 101 222 022 122
101 202 001 102 200 002 100 201 220 021 122 221 022 120 222 020 121 110 211 012 111 212 010 112 210 011
102 201 011 110 212 022 121 220 020 122 221 001 100 202 012 111 210 010 112 211 021 120 222 002 101 200
110 220 121 201 011 212 022 102 111 221 001 202 012 122 020 100 210 222 002 112 010 120 200 101 211 021
111 222 101 212 020 202 010 121 211 022 100 012 120 201 110 221 002 122 200 011 220 001 112 021 102 210
112 221 111 220 002 222 001 110 011 120 202 122 201 010 200 012 121 022 101 210 100 212 021 211 020 102
120 210 221 011 101 112 202 022 102 222 012 020 110 200 211 001 121 201 021 111 122 212 002 010 100 220
121 212 201 022 110 102 220 011 202 020 111 100 221 012 001 122 210 101 222 010 002 120 211 200 021 112
122 211 211 000 122 122 211 000 002 121 210 210 002 121 121 210 002 001 120 212 212 001 120 120 212 001
200 100 012 212 112 021 221 121 210 110 010 222 122 022 201 101 001 120 020 220 102 002 202 111 011 211
201 102 022 220 121 011 212 110 010 211 112 002 200 101 021 222 120 020 221 122 012 210 111 001 202 100
202 101 002 201 100 001 200 102 110 012 211 112 011 210 111 010 212 220 122 021 222 121 020 221 120 022
210 120 112 022 202 221 101 011 201 111 021 010 220 100 122 002 212 102 012 222 211 121 001 020 200 110
211 122 122 000 211 211 122 000 001 212 120 120 001 212 212 120 001 002 210 121 121 002 210 210 121 002
212 121 102 011 220 201 110 022 101 010 222 200 112 021 002 211 120 202 111 020 001 210 122 100 012 221
220 110 212 102 022 121 011 201 222 112 002 101 021 211 010 200 120 111 001 221 020 210 100 202 122 012
221 112 222 110 001 111 002 220 022 210 101 211 102 020 100 021 212 011 202 120 200 121 012 122 01
0
201
222 111 202 121 010 101 020 212 122 011 200 021 210 102 220 112 001 211 100 022 110 002 221 012 201 120

And as you can see, some of the columns don’t have a multiplicative inverse, some cells multiply out to zero.


Still not 100% sure what this all – you know – means. I envisage these vectors as being like n speedometer wheels, each wheel having p numbers on it. Addition means advancing all the wheels by some amount each. The way that addition works means that each wheel is independent of all the others. The linear aspect of it means that 3x is the same as doing x 3 times.

The associativity rule means that to multiply something by (a+b), you can roll the wheels forward according to a, and then roll them forward according to b – these no interaction between the motions occasioned by a and b.

But we agreed earlier that multiplication must affect multiple wheels. How so? Well – multiplying two values just adds together the effect of multiplying together each pair of wheels in the two values … but each pair of wheels in the multiplication results in some combination of other wheels being rolled forward in the final sum. Moreover, the combinations have to lock together – you can’t just pick arbitrarily.

There’s a lot I still don’t “get”. Maybe … maybe I have enough to return to page 7. Or was it 6?


Constructing finite fields.

February 7, 2011

So, anyway. I was at Brett’s blog. An engineer is not a scientist, and likewise a computer programmer is not a mathematician. But we can’t help having a bit of an interest on the discipline that forms the underpinning of what we do.

So. Finite fields. My interest is in writing a program that, if you give it a prime number p and positive n, will generate the field GF(pn) ≡ GF(p)n.

Ok. A field is made up of two interlocking groups (vague memory that there is a thing called a ring?) over some set of atoms. Each group has an identity, an inverse operation etc and the two groups interlock in that one is distributive over the other. The canonical field is the rational numbers under addition and multiplication.

The finite fields GF(p)1 are simply the integers mod p, with addition and multiplication mod p as the field operators. Great! Ok, first problem: what’s the division operator? A little searching turns up the extended gcd algorithm. Brilliant, sorted.

Now then. According to Brett, higher-order finite fields can be built like so:

You find a polynomial that has no root over the field, and you treat its root as an atom in your new group. Let’s call it α. The atoms of the new group become polynomials a+bα. Where a and b are integers p. To continue, you do this again: find a β that’s the root of a polynomial that has no root in the smaller group, and the atoms of the new group become a+bα+cβ.

The addition operator over these values is simply vector addition: you add the a’s, b’s and c’s etc modulo p. The multiplication operator is not so simple – you multiply the polynomial form. Finding the multiplicative inverse … could be fun.

Ok. For a nontrivial example, let’s start with GF(3)1 Here’s the multiplication table (omitting the zero):

1 2
2 1

Awesome! Well – what’s a polynomial that doesn’t have a root in that table? By looking at the diagonal, we see that no value has a square of 2, so the root of x2 – 2 = 0 can be our new α . Re-arranging this, we see that α2 = 2$. The atoms of our new group become (a+bα).

Let’s multiply! (2+2α)(1+2α) = 2 + 6α + 4αα . Since αα = 2, this reduces to 2 + 6α + 8, which becomes 1 when we do everything mod 3.

Our multiplication table now looks like this:

1 2 α α+1 α+2 2α+1 2α+2
2 1 2α+2 2α+1 α α+2 α+1
α 2 α+2 2α+2 1 α+1 2α+1
α+1 2α+2 α+2 1 2α+1 2 α
α+2 2α+1 2α+2 1 α α+1 2
α 1 2α+1 α+1 2 2α+2 α+2
2α+1 α+2 α+1 2 2α+2 α 1
2α+2 α+1 2α+1 α 2 α+2 1

We now want to extend this, to pick a β. By inspecting the diagonal, we see that no element has a square of α+1, so our new β is the root of β2-( α+1 )= 0.

So let’s add this and build a new group!

Ah. A snag. If we simply use the same method to add it, we wind up with 81 elements, because the elements would be a+bβ where a and b are elements of the form a+bα. Obviously, to get just pn of these we have to multiply out. Now, we know what α2 is, and we know what β2 is. But what is αβ?

Well, I know that
α2 = 2
β2 = α+1
And so
(αβ)2 = 2α+2

So to work out what αβ is, I can inspect the diagonal and find if there is some value that might work as αβ. For each value x = a+bα+cβ, calculate out what happens when you square it – substituting in the correct values for α2, β2, and x itself as αβ. With a little luck, one and only one of them should evaluate to 2α+2, and that becomes our αβ.

x2 multiply out substitute
α2 = 2
β2 = α+1
substitute
αβ = x
(1)2 = 1 = 1 = 1
(2)2 = 1 = 1 = 1
(α)2 = α2 = 2 = 2
(α+1)2 = α2+2α+1 = 2α = 2α
(α+2)2 = α2+α+1 = α = α
(2α)2 = α2 = 2 = 2
(2α+1)2 = α2+α+1 = α = α
(2α+2)2 = α2+2α+1 = 2α = 2α
(β)2 = β2 = α+1 = α+1
(β+1)2 = β2+2β+1 = 2β+α+2 = 2β+α+2
(β+2)2 = β2+β+1 = β+α+2 = β+α+2
(β+α)2 = β2+2βα+α2 = 2βα+α = 2β
(β+α+1)2 = β2+2βα+2β+α2+2α+1 = 2βα+2β+1 = β+2α
(β+α+2)2 = β2+2βα+β+α2+α+1 = 2βα+β+2α+1 = α+2
(β+2α)2 = β2+βα+α2 = βα+α = β
(β+2α+1)2 = β2+βα+2β+α2+α+1 = βα+2β+2α+1 = α+2
(β+2α+2)2 = β2+βα+β+α2+2α+1 = βα+β+1 = 2β+2α
(2β)2 = β2 = α+1 = α+1
(2β+1)2 = β2+β+1 = β+α+2 = β+α+2
(2β+2)2 = β2+2β+1 = 2β+α+2 = 2β+α+2
(2β+α)2 = β2+βα+α2 = βα+α = 2β+2α
(2β+α+1)2 = β2+βα+β+α2+2α+1 = βα+β+1 = α+2
(2β+α+2)2 = β2+βα+2β+α2+α+1 = βα+2β+2α+1 = β
(2β+2α)2 = β2+2βα+α2 = 2βα+α = β+2α
(2β+2α+1)2 = β2+2βα+β+α2+α+1 = 2βα+β+2α+1 = 2β
(2β+2α+2)2 = β2+2βα+2β+α2+2α+1 = <βα+2β+1 = α+2

Barp! You fail it! None of our values work as αβ when α2-2=0 and β2-( α+1 )= 0

Ok. At this point I have to conclude that perhaps you cannot freely choose your polynomials. But … I rather got the impression that you could. Brett?