How does trigonometry in a Galois field work?

Question

This is a follow-up to this question. I'm interested in doing trigonometry in finite fields on a computer. I do not understand precisely how trigonometric functions are supposed to work in a finite (Galois) field. I've read the Wikipedia article but I'm having trouble understanding what sorts of angles and numbers are representable in finite fields.

Here is what I do understand:

Starting with the 2D Cartesian plane with coordinates x, y, we can represent discrete angles that are multiples of $90^\circ = \frac{\pi}{2}$. These are the fourth roots of unity $x = \cos{\frac{2k\pi}{4}}$ and $y = \sin{\frac{2k\pi}{4}}$ or alternatively: $z = \cos{\frac{k\pi}{2}} + i\sin{\frac{k\pi}{2}}$, where $k$ is a positive integer less than $4$. These numbers can be represented solely with the integers. If we want to add discrete angles that are multiples of $30^\circ = \frac{2\pi}{12}$, we need a quadratic extension of the integers so that we have quadratic (algebraic) integers of the form $a + b\sqrt 3$. This allows us to represent the twelfth roots of unity as x and y coordinates. If we wish to double the number of angles to $15^\circ = \frac{2\pi}{24}$ multiples, we must extend our field again, forming a tower of quadratic extensions with numbers of the form $(a + b\sqrt 3) + (c + d\sqrt 3)\sqrt 2$. Numbers of this form allow us to represent the $24^{th}$ roots of unity.

How does this work in a finite field? Can I choose a finite field such that I can exactly represent the $n^{th}$ roots of unity in a manner analogous to the above? I'm particularly interested in constructable numbers, which feature only quadratic extensions (and multiquadratic extensions like $\sqrt{5 + \sqrt 5}$). In particular this means that $n$ is restricted to having factors of 2 and Fermat primes. I restricted myself to powers of $2$ and Fermat prime $3$ in my example above. Both $12$ and $24$ have factors of only $2$ and $3$.

- Edit -

To try to clarify what I'm struggling with. I do not see how to find or use a finite field that has been extended twice or more (e.g. angles of $\frac{\pi}{12}$ as described above), as the relationship to the complex plane in a finite field setting seems to blur as the tower of extensions grows.

This is a new subject for me, so I'd really appreciate an example or two to go along with any explanations.

Answer 1

$\def\C{\mathbb{C}} \def\F{\mathbb{F}} \def\R{\mathbb{R}} \def\Z{\mathbb{Z}} \newcommand\de{^\circ} \renewcommand\i[2]{{#1}{\rm i}{#2}} $

We have \begin{align*} \sin x=\frac{e^{ix}-e^{-ix}}{2i}\\ \cos x=\frac{e^{ix}+e^{-ix}}{2}\\ \end{align*} We may take both the domain and codomain of trigonometric functions as $\R$. We seek equivalent functions where the domain and codomain are finite and not necessarily equal.

Here I discuss cases where the codomain is a field $F$ of dimension 1 or 2, and the domain $A$ is $\Z_{n}$ where $n=|F|-1$. For example, $F=\F_p$ and $\Z_{p-1}$, or $F=\F_p[i]$ and $\Z_{p^2-1}$.

What in a field should correspond to $e^{ix}$

What goes wrong if we pick some value $u\in F$, and try using $u^x$ for $e^x$?

In any field $F$ of $n>3$ elements, not every non-zero element --- not even every element apart from 0, 1 and $-1$ --- generates the multiplicative group. For example, if $F=\Z_{73}$, the elements in $F$ corresponding to $\pm i\in\C$ (that is, those whose squares are $-1$) are 27 and 46. Where $g$ generates $F^\times$, $g^{27}$ has order only 8 and $g^{46}$ has order 36.

Thus using a field element $a\in F$ in an expression $g^a$ just because of some property of $a^2$ is unreliable.

So forget $i$ in exponents. $g\in F$ corresponds in $\C$ not to $e$ but to $e^i$. Where $a\in F$ corresponds to $x\in\C$, $e^{ix}\in \C$ corresponds in $F$ not to $g^{ai}$ but to $g^a$. (That $i$ is in $A$, and so, strictly speaking, is not $i$ but rather that element of $A$ that corresponds to $i\in\C$.)

We need $i$, so we just find an $i$ where $i^2=-1$, which entails $-1$ being a square mod $p$. $\F_2$ would not hold much interest, and trigonometry fails in fields of characteristic 2 anyway (see this MSE thread). Thus for $F$ we take a field of order $4k+1$. If $F=\F_p$, $p=4k+1$. However, $F=\F_p[i]$ can also work, provided $p=4k+3$.

Define sin and cos by \begin{align*} \sin a&=hi(g^{-a}-g^a)\\ \cos a&=h(g^a+g^{-a})\\ \end{align*} where $2h=1$ and $i^2+1=0$. (If $F=\Z_p[i]$, then that notation determines which of $-1$'s two square roots is notated $i$. If $F=\F_p$ then there are two choices for $i$, an issue I discuss later.)

$g^{-a}$ is just syntactic sugar for ${g'}^a$ or $(g^a)'$ where $'$ denotes multiplicative inverse or reciprocal. We may also interpret $g^{-a}$ as $g^{o-a}$ where $o$ is the multiplicative order of $g$.

Then the elementary trigonometric identities work, e.g. \begin{align*} \sin^2 a+\cos^2 a&=h^2[i^2(g^{-a}-g^a)^2+(g^a+g^{-a})^2]\\ &=h^2[i^2g^{-2a}-2i^2+i^2g^{2a}+g^{2a}+2+g^{-2a}]\\ &=h^2[(i^2+1)(g^{2a}+g^{-2a})-2i^2+2]\\ &=h^2[2-2i^2]\\ &=h^2[4-2(i^2+1)]\\ &=4h^2\\ &=1\\ \sin a\cos b+\cos a\sin b&=h^2i[(g^{-a}-g^a)(g^b+g^{-b})+(g^a+g^{-a})(g^{-b}-g^b)]\\ &=h^2i[2g^{-a-b}-2g^{a+b}]\\ &=hi[g^{-a-b}-g^{a+b}]\\ &=\sin(a+b)\\ \cos a\cos b-\sin a\sin b&=h^2[(g^a+g^{-a})(g^b+g^{-b})-i^2(g^{-a}-g^a)(g^{-b}-g^b)]\\ &=h^2[g^{a+b}+g^{a-b}+g^{b-a}+g^{-a-b}-i^2g^{-a-b}+i^2g^{b-a}+i^2g^{a-b}-i^2g^{a+b}]\\ &=h^2[(1-i^2)(g^{a+b}+g^{-a-b})+(1+i^2)(g^{a-b}+g^{b-a})]\\ &=h^2(1-i^2)(g^{a+b}+g^{-a-b})\\ &=h(g^{a+b}+g^{-a-b})\\ &=\cos(a+b) \end{align*} as $h(1-i^2)=h(2-(i^2+1))=2h=1$.

Thus we have such identities as: \begin{align*} \sin^2 a+\cos^2 a&=1\\ \sin(a\pm b)&=\sin a\cos b\pm\cos a\sin b\\ \sin2a&=2\sin a\cos a\\ \cos(a\pm b)&=\cos a\cos b\mp\sin a\sin b\\ \cos2a&=\cos^2a-\sin^2a=1-2\sin^2a=2\cos^2a-1\\ \end{align*}

Earlier work

The OQ cites a Wikipedia article "Trigonometry in a galois [i.e. finite] field", but unfortunately that article no longer exists. However, Wikipedia has an article on rational trigonometry, and I did locate a pertinent paper by Campello[2].

Campello and his co-authors use "GF(q)" for $\F_q$ ($q=p^r$, $p$ prime) and "G(q)" for $\F_q[i]$. They define trigonometry in the latter.

Rational trigonometry is a way of doing geometry and trigonometry in finite sets. It was developed by Norman Wildberger. Instead of distance $d$ it uses "quadrance" which corresponds to $d^2$, and instead of an angle $\theta$ it uses "spread" which corresponds to $\sin^2\theta$.

Getting sin's sign correct

A mistake which is all too easy to make is to implement $a\mapsto-\sin a$ instead of $a\mapsto\sin a$. For the sin function to be correct, it must satisfy $\sin \frac{n}4=1$ (as $\sin90\de=1$). If $F=\Z_{p}$, this can be arranged by taking $g^{n/4}$ as $i$.

If $12\mid n$, an alternative check is possible: $2 \sin \frac{n}{12}=p+1$ (as $\sin30\de=\frac12$). For example, in $Z_{11}[i]$, $\sin 10$ should be 6, not 5.

Whether the sin formula yields $\sin a$ or $-\sin a$ depends on the generator $g$ and (unless $F$ is defined by explicitly adjoining $i$) the choice of square root of $-1$ for $i$. Where $a=\frac{n}4$, $g$ is right if $g^a=i$ and wrong when $g^a=-i=i'=\overline{i}$.

Write $\i{x}{y}$ for $x+yi$. Now $(\overline{g})^a=\overline{g^a}$ so where two generators are each other's conjugates, one is right and one is wrong. $\overline{\i{x}{y}}=\i{x}{(p-y)}$. And $(g')^a=(g^a)'$, so the same is true if they are each other's reciprocals.

Some examples.

For $F=\Z_{73}$, $g=5, i=27$ and $g=11, i=46$.

For $F=Z_{11}[i]$, $\frac{n}4=\frac{p^2-1}4=30$, $\i{4}{1}, \i{5}{4}, \i{3}{9}=\overline{\i{3}{2}}, \i{7}{10}=(\i{3}{2})', \i{5}{9}=\overline{\i{5}{2}}, \i{7}{6}=(\i{5}{2})'$.

[2]: Campello de Souza, R.M. et al. Trigonometry in a Finite field and a New Hartley Transform. ISIT 16-21 August 1998, p.293.