Axioms for finite cyclic groups

Question

tl;dr: What is a minimal definition of a finite cyclic group, without resorting to the definition of a group?

Let $G$ be a finite set and $\star$ be a binary operation on $G$. My question is whether a cyclicity condition can imply some of the standard group axioms (as it implies for instance abelianity). Let us take a following cyclicity axiom:

$$\exists g\in G, \forall x\in G, \exists n\in ℤ_{>0}, x = g^n$$ where $g^n = g\star g\star\dotsb\star g$ ($n$ times). Already, this cyclicity condition assumes associativity to make sense of $g\star\dotsb\star g$. This implies that $g^{m+n} = g^m\star g^n$ for $m$, $n\inℤ_{>0}$. Note that I do not define $g^n$ for $n = 0$ or $n < 0$ that would assume identity or the existence of inverses.

Some thoughts about the other (standard) axioms:

• Closure: It seems required to me, as some kind of a converse to cyclicity (for all $n >0$, $g^n\in G$). This could be paired with cyclicity by writing something like: "a finite set $G$ is a cyclic group if $G = \{g^n:n\inℤ_{>0}\}$ for some $g\in G$."
• Identity: Since $G$ is finite, there must exist $m < n$ such that $g^m = g^n$. With only the other axioms, can we prove that there exists $k$ such that $g^k = id$ (with standard definition for identity)?
• Inverses: If we assume identity, we can give a sense to $g^0$ and prove that for all $x\in G$, there exists $0 ≤ n < k$ such that $x = g^n$. Then assuming closure, $g^{k-n}\in G$ and $g^{k-n}$ is the inverse of $x$.

My impression is that closure is required, inverses are not and I do not know for identity. But there may exist other ways to define finite cyclic groups.

Answer 1

You could take Peano's axioms and replace the axiom which states $0$ is not the successor of any natural number with its negation (number 2 below).

Your axioms then are, $G$ is a set together with a map $S:G\to G$ ('successor'), and an element $z\in G$ ('zero') such that

1. $S$ is injective
2. there is an $x\in G$ with $S(x)=z$
3. for all $H\subset G$ if $z\in H$ and for all $x\in G$ $x\in H\implies S(x)\in H$, then $H=G$

Once you have a model $(G,S,0)$ for these axioms, define the group law by:

1. for all $x\in G$, $x+z=x$
2. for all $x\in G$, $x+S(y)=S(x+y)$

which recursively defines addition.

*From the comments, it seems clear that I should explain why all models are finite cyclic groups. First note that $\{z,S(z),S^2(z),...\}$ must be all of $G$ by 3. Moreover, as 2 says that $z\in \operatorname{im}(S)$, we can conclude that $z=S^n(z)$ for some $n\in \mathbb{N}\setminus\{0\}$. Choose the least $n\in \mathbb{N}\setminus \{0\}$ such that $S^n(z)=z$. Another use of 3 implies that $\{z,S(z),S^2(z),...,S^{n-1}(z)\}$ is all of $G$, and minimality implies these are distinct.

Answer 2

You wrote

Diffie-Hellman key exchange protocol or ElGamal encryption scheme rely on finite cyclic groups. For computer science students who have no idea of what a group is, it may be an overkill to define groups in their generality. Finite cyclic groups are very simple objects in comparison.

These procedures do not rely on abstract finite cyclic groups. An implementation is going to use something based on modular arithmetic. So just make sure they know what modular arithmetic is and use that.

First make sure they understand addition and multiplication mod $m$, and especially how to check if something has a multiplicative inverse mod $m$ and how to find it (Euclid's algorithm). A unit mod $m$ is a number $a \bmod m$ with an inverse, i.e., $\gcd(a,m) = 1$.

Then say encryption uses powers of numbers in some modulus, and there's a hard theorem that when the modulus is a prime $p$ some number mod $p$ has its powers exhaust all nonzero numbers mod $p$. Those are called generators or primitive roots mod $p$, and give some examples and nonexamples (show for some composite $m$ there is no primitive root, like when $m = 8$ and $m = 15$).

I don't think you need to bring up cyclic groups at all. You don't even need to mention that adding and multiplying mod $m$ is commutative or associative, since the CS students wouldn't even question such properties at all. Don't dwell on such things that look completely obvious at the start.

After you discuss several encryption algorithms that rely on a generator, then you could introduce the concept of a commutative group and the more refine concept of a cyclic group because by that point they students will have already had experience working with such objects.

A group is a set $G$ with a binary operation $G \times G \to G$ that's associative, has an identity element, and each element has an inverse. The group is called commutative when the $xy = yx$ for all $x$ and $y$ in $G$, and say the group is called cyclic when there's some $g \in G$ such that everything in $G$ is a power of $g$. This can be illustrated right away with the units mod $m$ for various $m$. I don't think seeking minimal axioms is a good idea at all: just use a set of conditions that works in an efficient way and can be illustrated by examples the students have already seen.

Main suggestion: don't bother with the generality of cyclic groups until after you have used some actual examples, like the nonzero numbers modulo a prime. Once they see how cyclic groups work in some examples, they'll better appreciate the general terminology. Not earlier.

Answer 3

If you were to take this approach, in the context of CS / cryptography education as you mention in your comment, what I think you'd want would be something like:

A cyclic group of order $n$ is a set $A = \{a_0, a_1, a_2, \dots, a_{n-1}\}$ with a binary operator $\star: A^2 \to A$ that satisfies $a_i \star a_j = a_k \iff i + j \equiv k \pmod n$.

Of course, this is hardly an "axiomatic definition" in the sense we're used to from abstract algebra. Rather, it basically just defines a cyclic group as something isomorphic to $(\mathbb Z / n \mathbb Z)^+$, with all the consequences that entails. But for your purposes I think that's enough, and any attempt to get more "axiomatic" than that would just be a pointless exercise in abstraction for its own sake.

---

Anyway, the obvious problem with this definition is that it effectively defines the group operation in terms of the discrete logarithm — which means that, to compute $x \star y$ based on this definition of $\star$, you must first compute the discrete logarithm of both $x$ and $y$!

Of course that's a perfectly valid way to compute the group operation in situations where it's feasible — for example, if you were trying to do multiplication in the AES field by hand using pencil and paper, by far the quickest way would probably be to use a pregenerated discrete log / antilog table — but it also means that any group representation that allows doing this is useless for any cryptographic algorithms that depend on the hardness of the discrete logarithm problem.

However, if you wanted, you could probably start like this and then introduce the idea that the representation of a cyclic group can be "obfuscated" in such a way that we can still efficiently compute $\star$ while not having an efficient way to compute discrete logarithms.

At that point you could then offer some of the standard examples, like the multiplicative group modulo a prime and/or its subgroups, and show that they can in fact be proven to be cyclic groups even though the discrete logarithm may not be efficiently computable.

Indeed, on some level this is trivial: if you define $a_k \equiv g^k \pmod m$ for some $g$ coprime to $m$, and let $\star$ denote multiplication modulo $m$, then it's not hard to show that $g^n \equiv 1$ for some $n$ and that $\star$ satisfies the definition given above. Of course, determining exactly what the order $n$ is for given $m$ and $g$ can be trickier, but in many specific cases that's not too hard either, especially if you're willing to handwave past some of the deeper number-theoretic lemmas involved in the background.

---

Would this be any simpler or pedagogically better than the usual approach of starting with a definition of a group and then showing that some groups can be cyclic, even if we may not know how to efficiently compute discrete logs in them? Maybe, maybe not. But I cannot say for sure that it isn't.

One potential advantage of this method is, of course, that it would let you skip the axiomatic definition of a group, which could save a bunch of time and mental effort for students who might never need it again. Then again, being exposed to a bit of abstract algebra might be helpful to prepare the students for later dealing with e.g. finite fields. (Of course it's certainly also possible to give an introduction to finite fields in cryptography without really involving much abstract algebra either.)