Can we restrict the average multiplicative order of a number?

84 Views Asked by At

We are given a size of a number system, $s$, which is the number of components in the system. For example, the quaternions have $s=4$ components.

Now, in general, we will be interested in multiplications. We are allowed to define interactions between components as any type of multiplication. For example, we could define $i = jk$ or $i=-jk$ or even $i=8jk$.

We also take the components modulo a prime $n$. So the full system is a set of $s$ components of a number, all taken modulo a natural, $n$.

Can we design a system of $s$ components that has an average multiplicative order of $n$ or $n^2$?

1

There are 1 best solutions below

0
On

Let $K$ be a number system of size $s$, with all components taken modulo a prime $p$. Then $|K|=p^s$, so in particular $K$ is finite. If $K$ contains no zero-divisors other than $0$, then $K$ is a finite domain. By Wedderburn's theorem, $K$ is a finite field of order $p^s$. It is a basic fact on fields that every field of order $p^s$ is isomorphic to $\Bbb{F}_{p^s}$. The units of $\Bbb{F}_{p^s}$ form a cyclic group of order $p^s-1$, which contains precisely $\varphi(d)$ elements of order $d$ for every divisor $d\mid p^s-1$, where $\varphi$ denotes Euler's totient function. The average multiplicative order of the nonzero elements of $K$ is therefore $$\frac{1}{p^s-1}\sum_{d\mid p^s-1}d\varphi(d).$$ If the average number is a positive power of $p$, then $$\sum_{d\mid p^s-1}d\varphi(d)=(p^s-1)p^k.$$ This sum on the left hand side is odd because $d\varphi(d)$ is odd iff $d=1$, but the right hand side is even unless $s=0$, or $p=2$ and $k=0$. We conclude that no number system as described exists.

Note that if $k=0$ then the average order of the nonzero elements is $1$, which means the only nonzero element is $1$, and so $K\cong\Bbb{F}_2$ and $s=1$.