This submit will give an in depth instance of working in a discipline with 9 parts. That is necessary as a result of finite fields are usually not usually handled concretely aside from the case of prime order.

In my first submit on Costas arrays I discussed in a footnote that Lempel’s algorithm works extra usually over any finite discipline, however I caught to integers modulo primes to make issues less complicated.

On this submit we’ll create a 7 × 7 Costas array by working in a discipline with 9 parts. Alongside the way in which we’ll clarify in nice element how finite discipline arithmetic works, utilizing the sector with 9 parts for instance.

## Prime powers are completely different

The order of a finite discipline might be any energy of a major. That’s, a finite discipline can have *q* parts if (and provided that) *q* = *p ^{ok}* for some prime

*p*and optimistic integer

*ok*.

If *q* is a major, then any discipline with *q* parts is isomorphic to the integers mod *q*. Addition and multiplication are outlined simply as within the integers, besides you at all times take the rest by *q* after you add or multiply.

But when *q* is a major *energy*, issues are completely different. So whereas multiplication in a discipline of seven parts is just multiplication mod 7, multiplication in a discipline of 9 parts is **not** multiplication mod 9.

## Defining addition and multiplication

The sector with 9 parts might be outlined as polynomials of the shape *ax* + *b* the place *a* and *b* are integers mod 3, i.e. *a* and *b* can tackle the values 0, 1, or 2.

You may outline addition on this little discipline the identical manner you at all times outline polynomial addition, with the understanding that the coefficients are added mod 3. So, for instance,

(2*x* + 1) + (*x* + 0) = 1

as a result of the main coefficient is 2 + 1, which reduces to 0 mod 3.

Multiplication can be outlined as polynomial multiplication, with coefficient arithmetic being carried out mod 3, with another step: after multiplying the polynomials, you divide by an irreducible quadratic polynomial and maintain the rest.

Typically, if *q* = *p ^{ok}* for some prime

*p*and optimistic integer

*ok*, we outline parts of our discipline to be polynomials of diploma

*ok*– 1. When multiplying, we take the rest after dividing by a set irreducible polynomial of diploma

*ok*. In our instance,

*ok*= 2, so we’ve got first diploma polynomials, and we take the rest after dividing by a second diploma polynomial.

### Irreducible polynomials

The definition of multiplication brings up a number of questions.

- What’s an irreducible polynomial?
- Can I at all times discover one?
- How can I discover one?
- Which one ought to I decide?

An irreducible polynomial is one that can not be factored within the given context. Right here we wish a polynomial of diploma 2, with coefficient in integers mod 3, that can not be factored because the product of two linear polynomials with coefficients in integers mod 3.

There are many irreducible polynomials. In our case, we’ve got 36 to select from. (This submit explains a method for counting what number of irreducible polynomials there are of a given order over a given finite discipline.)

There are algorithms for locating irreducible polynomials, however that is past the scope of this submit. Right here’s one we are going to use:

*x*² + *x* + 2.

You would confirm by brute pressure that this polynomial can’t be factored into

(*ax* + *b*)(*cx* + *d*)

the place *a* and c are non-zero. There are 2 × 3 × 2 × 3 potentialities for *a*, *b*, *c*, and *d*, and you would confirm that none of them work.

### The distinction selection makes

We mentioned there are 36 irreducible polynomials we may select. What in regards to the different 35 we didn’t select? All of them result in the identical discipline, the place by “similar” we imply *isomorphic*. They generate completely different *representations* of the sector, however there’s a direct correspondence (an isomorphism) between any two representations.

In a single sense that is nothing to fret about, and in one other sense it’s. You’re not going to create one thing basically completely different by selecting a unique irreducible polynomial. When you and I decide completely different polynomials, we are going to agree on all of the algebraic properties of our fields, however we may disagree on what the product of two explicit polynomials is, like two folks utilizing two completely different models of measure. This may be a difficulty when doing finite discipline arithmetic with software program: two software program packages may give completely different outcomes for a given product.

## Primitive parts

A component *g* in in group *G* is primitive if each aspect of *G* is a few energy of *g*. For instance, 3 is a primitive aspect of the integers mod 7 as a result of if we take successive powers of three mod 7 we get

3, 2, 6, 4, 5, 1

and that’s all of the non-zero parts of the integers mod 7. Alternatively, 2 is *not* a primitive aspect mod 7 as a result of its powers are 2, 4, and 1. There’s no technique to increase 2 to any energy mod 8 and get 3, 5, or 6 out.

We want a primitive aspect of our finite discipline so as to perform Lempel’s algorithm. It seems we will use *x* as our primitive aspect. That’s, each non-zero aspect of our discipline is an influence of *x*. There are different primitive parts we may have chosen[1].

That assertion could sound fallacious. How, for instance, can an influence of *x* equal 2x + 1? We have now to keep in mind that we’re multiplying polynomials as described above, not as polynomials over actual numbers.

After we multiply *x* by *x*, we get *x*² in fact, however then we’ve got to divide by our selection of irreducible polynomial, which we mentioned above can be *x*² + *x* + 2.

If we divide *x*² by *x*² + *x* + 2 as we’d in a highschool algebra class, we get a quotient of 1 with a the rest of –*x* – 2. After we cut back the coefficients mod 3, we get 2*x* + 1. So in our world,

*x*² = 2*x* + 1.

OK, that takes some getting used to, however now what’s *x*³? Properly, it’s *x* instances *x*² in fact, however what’s that? As earlier than we’ll first fake we’re doing highschool algebra, then we’ll regulate. So *x* instances 2*x* + 1 equals 2*x*² + *x*. After we divide by our irreducible polynomial, we get

2*x*² + *x* = 2(*x*² + *x* + 2) + 2*x* + 2

so the rest is 2*x* + 2. Due to this fact in our context,

*x*³ = 2*x* + 2.

## Powers of *x*

Lempel’s algorithm says to fill within the (*i*, *j*) sq. of our matrix if and provided that

*a*^{i} + *a*^{j} = 1

the place *a* is a generator of our discipline. In our case *a* is just the polynomial *x*. Right here *i* and *j* run from 1 by 7 (i.e. as much as *q* – 2, and for us *q* = 9.)

We don’t want a full multiplication desk; we solely want powers of *x*. Right here they’re:

*x*- 2
*x*+ 1 - 2
*x*+ 2 - 2
- 2
*x* *x*+ 2*x*+ 1- 1

By the way, we may use this as a form of desk of logarithms. To multiply any two parts, scan the checklist to search out out what energy of *x* every aspect is. Then add the exponents, and see what aspect that corresponds to.

## Filling within the Costas array

For every row *i*, we compute *x*^{i} after which discover which worth of *j* satisfies

*x*^{j} = 1 – *x*^{i}.

So right here we go.

When *i* = 1, 1 – *x*^{i} = 1 – *x* = 2*x* + 1, and so *j* = 2.

When *i* = 2, 1 – *x*^{i} = 1 – *x*² = 1 – (2*x* + 1) = *x*, and so *j* = 1.

When *i* = 3, 1 – *x*^{i} = 1 – (2*x*+ 2) = *x* + 2, so *j* = 6.

When *i* = 4, 1 – *x*^{i} = 1 – 2 = 2, so *j* = 4.

When *i* = 5, 1 – *x*^{i} = 1 – 2*x* = *x* + 1, so *j* = 7.

We will work out the remainder by symmetry. As famous within the earlier submit, the pairs (*i*, *j*) are symmetric. So since (3, 6) is stuffed in, so is (6, 3). And since (5, 7) is stuffed in, so is (7, 5). We may have additionally found out the case of *i* = 2 by symmetry.

## Visualizations

Right here we visualize the Costas array we’ve discovered as within the earlier submit. The road segments between stuffed in cells are all distinctive, so we draw cell positions and the connecting strains.

Right here we translate all of the strains to the origin to point out that they’re distinct.

No two strains are the identical, however some strains have the identical slope with completely different lengths. To make it doable to see these, I added a small quantity of randomness to the factors earlier than plotting them.

***

[1] The variety of primitive polynomials of diploma *n* in a discipline with *q* parts is φ(*q*^{n} – 1)/*n* the place φ is Euler’s totient perform. In our instance, *n* = 1 and *q* = 9, so there are φ(8) = 4 primitive polynomials to select from. What are they?

Each non-zero aspect of our discipline is an influence of *x*, so a primitive polynomial *y* should itself be an influence of *x*, say *y* = *x*^{ok}. If *y*^{j} = *x*, then we should have *x*^{jk} = *x*. The multiplicative group of our discipline has 8 parts, so *jk* should be congruent to 1 mod 8. This implies *ok* should be 1, 3, 5, or 7. So our turbines are *x*, *x*^{3} = 2*x* + 2 = *x* + 2, *x*^{5} = 2*x*, and *x*^{7} = *x* + 1.