Primitive lambda-roots

Nearly ten years ago, Donald Preece and I wrote the first draft of a set of notes on primitive lambda-roots. We could never decide what do do with them: they were too short for a monograph, too long (and expository) for a research paper. We discussed it but didn’t get around to doing anything with them apart from putting them on the web.

Now we can no longer discuss them, but I would like them to be read and used. So I have decided to put the current version (with some very minor changes, mainly bringing the references up to date) with my lecture notes.

Below is a slightly edited version of the preface of the notes.

The most important examples of finite commutative rings with identity are undoubtedly the rings Zn of integers mod n, for nN.

In the case where n is a prime number p, Zp is a field: its non-zero elements form a multiplicative group. This group is cyclic, of order n−1, and its generators are the primitive roots mod p.

If n is not prime, then Zn is not a field: an element x is invertible if and only if it is coprime to n, that is, gcd(n,x) = 1. The invertible elements of Zn form a group U(n), the group of units mod n; its order is φ(n), where φ is Euler’s phi-function.

If this group is cyclic, its generators are again called primitive roots. However, this is a rare event: it occurs only if n is an odd prime power, or twice an odd prime power, or 4.

To replace this, Carmichael introduced his lambda-function λ(n), the exponent of U(n), that is, the smallest number m such that every unit x satisfies xm = 1. A primitive lambda-root (or PLR) is a unit whose order is λ(n). Clearly, primitive lambda-roots exist for all n. They are the object of our study.

The role of finite fields in combinatorial constructions is well known. Our motivation is the fact that, with some ingenuity, the methods can be extended to Zn in some cases, with PLRs playing the role of primitive roots. The first chapter gives a couple of examples, the construction of terraces and difference sets.

Three other features of the text should be noted.

  1. Our aim is expository; we begin with an account of the algebra we need, and end with a short discussion of the role of the lambda-function in the RSA cryptosystem.
  2. We pose many open problems along the way. We hope that other researchers will find something to their taste here, as Thomas Müller and Jan-Christoph Schlage-Puchta have already done in one case.
  3. We have implemented many of our calculations in GAP, and a file of documented GAP code accompanies the notes, to make further exploration easy.

The notes are here. I haven’t found a way yet of publishing the GAP code in a satisfactory format; you can extract it from the notes if you are in a hurry.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, history and tagged , , , , . Bookmark the permalink.

2 Responses to Primitive lambda-roots

  1. Dima says:

    Copying GAP code from PDF, oh dear :–)… I repeat myself and say that one really ought to put such things on github or bitbucket… And then you can also put the (La)TeX sources there, with ease. At this level of sophistication learning the necessary git or hg commands take 15 minutes to learn…

    • If you keep nagging, Dima, I might do it one day … in the meantime, this is where people come; they can easily go elsewhere for the plain text (or get a preformatted html version)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.