1 Introduction
The arithmetic-geometric mean (AGM) sequence is a sequence of ordered pairs where the first element of the pair is the arithmetic mean of the previous pair, and the second element of the pair is the geometric mean of the previous pair. The AGM over positive real numbers was first considered by Lagrange in 1785 and by Gauss a few years later.
Definition 1.1. Let
$a, b$
be positive real numbers. The sequence
$$ \begin{align*}\text{AGM}_{\mathbb{R}}(a,b)=((a_n,b_n))_{n=0}^\infty\end{align*} $$
is defined as follows. Let
$a_0 = a$
,
$b_0 = b$
and for
$n>0$
, set
$$ \begin{align*} a_n = \frac{a_{n-1}+b_{n-1}}{2}, \quad b_n&=\sqrt{a_{n-1}b_{n-1}}. \end{align*} $$
The AGM sequences have numerous applications, such as the rapid computation of the digits of
$\pi$
and the computation of elliptic integrals and inverse tangent functions, and can also be considered over the complex numbers (see [Reference Borwein and Borwein3, Reference Cox5]). They can also be used for studying elliptic curves and for computing bases for the period lattices and elliptic logarithms of points (see [Reference Cremona and Thongjunthug6, Reference Thongjunthug10]) and for computing the Serre--Tate lifts (see [Reference Carls4]).
As is clear from Definition 1.1,
$(a_n)_{n\in \mathbb {N}}$
and
$(b_n)_{n\in \mathbb {N}}$
have the same limit. The difficulty of defining the AGM sequences over other fields, for example, finite fields, is in specifying the root, which might not be defined or might involve choices.
Griffin et al. [Reference Griffin, Ono, Saikia and Tsai7] introduced AGM sequences over the finite field
$\mathbb {F}_q$
with q elements such that
$q \equiv 3 \pmod 4$
. However, it was not clear if we could define an infinite sequence over every finite field of odd characteristic. We extend the definition to finite fields with q elements such that
$q \geq 29$
and
$q \equiv 5 \pmod 8$
.
This paper is based on the bachelor thesis [Reference Bátorová1] of the first author, cosupervised by the second author. Very recently, Kayath et al., published a preprint [Reference Kayath, Lane, Neifeld, Ni and Xue8] in which they generalise results from [Reference Griffin, Ono, Saikia and Tsai7] and define and explain AGM sequences over all finite fields of odd characteristic. To do so, they used elliptic curves. In contrast, our approach for
$q\equiv 5\pmod {8}$
is based on elementary number theory.
1.1 Main results
We define the AGM sequences over
$\mathbb {F}_q$
where
$q\equiv 5\pmod {8}$
in Definition 4.8 and fully describe the corresponding graphs in Theorem 4.7. Some sketches of such graphs can be seen in Figures 2 and 3. A key property of the AGM sequences over finite fields is that a nontrivial connected component of the graph, having at least one edge, always contains a cycle (see Theorem 4.2). We prove that for all
$q\geq 29$
, there is at least one cycle in the corresponding graph (see Theorem 4.9), and
$q\geq 29$
is the best possible bound. In addition, we prove slightly more generally that there is at least one connected component, all of whose vertices are squares (that is, both components of the vertex are squares) (see Definition 2.8 and Corollary 4.15).
We also slightly improve and generalise the results from [Reference Griffin, Ono, Saikia and Tsai7] in Theorems 2.7 and 2.9. More precisely, we analyse components of the corresponding graphs and give a slightly better divisibility conclusion than in [Reference Griffin, Ono, Saikia and Tsai7, Theorem 1(4)].
1.2 Structure of the paper
We introduce the AGM sequences over finite fields and their corresponding graphs in Section 2. We always use Definition 2.4 for the corresponding graph of the AGM sequence. We mostly follow [Reference Griffin, Ono, Saikia and Tsai7], but we include our improved results there. We summarise the results from [Reference Griffin, Ono, Saikia and Tsai7] in Section 3.
Section 4 contains our results. In Section 5, we explain the strategy used to switch from
$q\equiv 3\pmod {4}$
to
$q\equiv 5\pmod {8}$
and why this strategy does not work for
$q\equiv 1\pmod {8}$
. We finish this paper with a challenge for interested readers to try to discover an elementary solution to extend the AGM sequences to
$q\equiv 1\pmod {8}$
.
2 The AGM as a directed graph over finite fields
Throughout the paper, q is an odd prime power and
$\mathbb {F}_q$
the field with exactly q elements. We briefly recall some well-known properties of
$\mathbb {F}_q$
.
Definition 2.1. Let
$x \in \mathbb {F}_q^\times $
. We call x a quadratic residue if there exists
$y \in \mathbb {F}_q$
such that
$y^2 = x$
. If there is no such y, x is a quadratic nonresidue. We will also call quadratic residues squares and nonresidues nonsquares.
Definition 2.2. Define the homorphism
$\phi _q \colon \mathbb {F}_q^\times \to \{\pm 1\}$
by
$$ \begin{align*} \phi_q(a) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue,}\\ -1 & \text{if } a \text{ is a quadratic nonresidue}. \end{cases} \end{align*} $$
We use some standard notions from graph theory, which can be found, for example, in [Reference Bondy and Murty2, Chs. 1, 10]. We just recall one definition.
Definition 2.3. Let
$u,v$
be vertices in a directed graph. Then we will call u a parent of v if there is an edge
$u \rightarrow v$
. We will call u a child of v if there is an edge
$v \rightarrow u$
.
We now define a directed graph which represents the AGM sequences over
$\mathbb {F}_q$
.
Definition 2.4. Define a directed graph
$\mathcal {J}_{\mathbb {F}_q}=(V,E)$
as follows: the set of vertices is
$V = \{(a,b) \in {\mathbb {F}_q^\times }^2 \mid \phi _q(ab)=1, a \neq \pm b\}$
and
$(a,b) \rightarrow (c,d)$
is an edge if and only if
$$ \begin{align*} c = \frac{a+b}{2} \quad\text{and}\quad d^2 =ab. \end{align*} $$
The following lemma is mostly contained in the proof of [Reference Griffin, Ono, Saikia and Tsai7, Theorem 1(3)] and can be easily deduced from it. We emphasise that it does not depend on q modulo 4.
Lemma 2.5. Let
$(a,b)$
be a vertex of
$\mathcal {J}_{\mathbb {F}_q}$
. Then,
$(a,b)$
has a parent if and only if
$\phi _q(a^2-b^2)=1$
. Furthermore, if
$(a,b)$
has a parent, there are exactly two parents, namely,
$(a + S, a - S)$
and
$(a-S,a+S)$
, where
$S^2 = a^2-b^2$
.
There is a group of natural automorphisms of
$\mathcal {J}_{\mathbb {F}_q}$
, as proven in [Reference Griffin, Ono, Saikia and Tsai7, Theorem 1(4)].
Lemma 2.6. Every
$\alpha \in \mathbb {F}_q^\times $
induces a distinct graph automorphism
$\varphi _\alpha \colon \mathcal {J}_{\mathbb {F}_q} \to \mathcal {J}_{\mathbb {F}_q}$
given by
$\varphi _\alpha (a,b)=(\alpha a,\alpha b)$
. Furthermore,
$G=\{\varphi _\alpha \mid \alpha \in \mathbb {F}_q^\times \} \simeq \mathbb {F}_q^\times $
as a group.
We look at the components of
$\mathcal {J}_{\mathbb {F}_q}$
. Let
$N_n$
denote the number of components of
$\mathcal {J}_{\mathbb {F}_q}$
with n vertices. Then, [Reference Griffin, Ono, Saikia and Tsai7, Theorem 1(4)] states that
$(q-1) \mid nN_n$
. However, we can prove a slightly better result. Namely, for any positive integer n, denote by
$M_n$
the number of oriented cycles of length n. When
$q\equiv 3\pmod {4}$
, [Reference Griffin, Ono, Saikia and Tsai7, Theorem 1(3,4)] implies that, in this situation,
$nM_n = \frac{1}{2} nN_n$
.
Theorem 2.7. For any positive integer n, we have
$(q-1) \mid nM_n$
.
Proof. The group G from Lemma 2.6 acts on
$\mathcal {J}_{\mathbb {F}_q}$
. Every orbit of a vertex has size
$q-1$
as
$(\alpha a,\alpha b)\neq (\beta a,\beta b)$
for
$\alpha \neq \beta $
and
$(a,b)\in V$
. A vertex from a cycle is mapped under
$\varphi _\alpha $
to a vertex from a cycle of the same size. This implies that
$q-1$
divides the number of all vertices which are in the cycles of the same length, so
$q-1 \mid nM_n$
.
We can make one more observation which has not been mentioned in [Reference Griffin, Ono, Saikia and Tsai7].
Definition 2.8. We call the vertex
$(a,b)\in V$
a square vertex if a and b are both squares. The other vertices in V are called nonsquare vertices.
Theorem 2.9.
-
• If an edge in the component connects two square vertices, then all the vertices in the component are square vertices.
-
• If an edge in the component connects two nonsquare vertices, then all the vertices in the component are nonsquare vertices.
-
• If an edge in the component connects a square vertex and a nonsquare vertex, then in the component, the square and nonsquare vertices alternate, so there is no edge in this component connecting two square or two nonsquare vertices.
Proof. The theorem will be completed after the next lemma.
Lemma 2.10. Consider the path
$(a,b) \rightarrow (c,d) \rightarrow (e,f)$
. Then,
$(a,b)$
is a square vertex if and only if
$(e,f)$
is a square vertex.
Proof. Suppose
$(a,b)$
is a square vertex, so
$a = A^2$
and
$b = B^2$
. Then,
$$ \begin{align*} c = \frac{A^2+B^2}{2}, \quad d^2 = A^2B^2, \end{align*} $$
which means that
$d =\pm AB$
, implying
$$ \begin{align*}e = \frac{c+d}{2}= \bigg(\frac{A\pm B}{2}\bigg)^2. \end{align*} $$
Then, by Definition 2.4, f is a square.
Now, assume that
$(a,b)$
is a nonsquare vertex. Let
$\alpha \in \mathbb {F}_q^\times $
be a nonsquare and consider the graph automorphism
$\varphi _\alpha ((a,b))=(\alpha a,\alpha b)$
. Then,
$$ \begin{align*} (a,b) \rightarrow (c,d) \rightarrow (e,f) \quad \mapsto \quad \varphi_\alpha((a,b)) \rightarrow \varphi_\alpha((c,d)) \rightarrow \varphi_\alpha((e,f)). \end{align*} $$
Since
$\phi _q(\alpha a) = (-1)(-1) = 1$
,
$\varphi _\alpha ((a,b))$
is a square vertex. We have already proved that
$\varphi _\alpha ((e,f))$
is a square vertex and as
$\varphi _\alpha ((e,f)) = (\alpha e, \alpha f)$
, we have
$\phi _q(e) = -1$
, which completes the proof of the lemma.
Hence, if we have a path between two vertices that are both squares or nonsquares, then all vertices are of the same type; otherwise, they will alternate.
Corollary 2.11. Let n be an odd positive integer. Then,
$M_n$
is even.
3 The AGM over
$\mathbb {F}_q$
, where
${q \equiv 3}$
(mod 4)
We now recall the results from [Reference Griffin, Ono, Saikia and Tsai7], which served as an inspiration for our work. In this section, we assume
$q \equiv 3 \pmod 4$
. Then,
$-1$
is a quadratic nonresidue in
$\mathbb {F}_q$
, so the proof of the following lemma is clear.
Lemma 3.1. Let
$\varepsilon \in \{\pm 1\}$
,
$x \in \mathbb {F}_q^\times $
. If
$\phi _q(x) = 1$
, then there is a unique
$y \in \mathbb {F}_q^\times $
such that
$y^2 = x$
and
$\phi _q(y) = \varepsilon $
. We will denote
$\sqrt [{\leftroot {8}\uproot {-10}\scriptstyle \varepsilon }]{x} = y$
.
Definition 3.2. Let
$a,b \in \mathbb {F}_q^\times $
such that
$\phi _q(ab)=1$
and
$a \neq \pm b$
. We define a sequence AGM
$_{\mathbb {F}_q}(a,b) = ((a_n,b_n))_{n=0}^\infty $
such that
$a_0 = a$
,
$b_0 = b$
and
$$ \begin{align*} a_n = \frac{a_{n-1}+b_{n-1}}{2}; \quad \varepsilon = \phi_q(a_n), \quad b_n = \sqrt[{\leftroot{8}\uproot{-10}\scriptstyle \varepsilon}]{a_{n-1}b_{n-1}}. \end{align*} $$
Example 3.3. Let
$q=3$
. We have
$\mathbb {F}_q^\times = \{1,-1\}$
so there is no
$(a,b)$
such that
$a\neq \pm b$
.
For
$q\geq 7$
, we observe that AGM
$_{\mathbb {F}_q}(\cdot ,\cdot )$
is an infinite sequence
$(a_n,b_n)_{n\in \mathbb {N}} \in {\mathbb {F}_q^\times }^2$
, such that
$a_n b_n(a_n^2-b_n^2)\neq 0$
.
Example 3.4. Consider
$q=11$
. Then,
$$ \begin{align*} \text{AGM}_{\mathbb{F}_{11}}(9,1)= (&\overline{(9, 1), (5, 3), (4, 9), (1, 5), (3, 4)})\\ \text{AGM}_{\mathbb{F}_{11}}(1,9) = (&(1,9),\overline{(5, 3), (4, 9), (1, 5), (3, 4), (9, 1)}), \end{align*} $$
where the line above a sequence means it is a repeating period. The graph
$\mathcal {J}_{\mathbb {F}_{11}}$
consists of three connected components shown in Figure 1.
Components of
$\mathcal {J}_{\mathbb {F}_{11}}$
.
Now, let us have a look at the graph of
$\mathcal {J}_{\mathbb {F}_q}$
. We will see that the components have a special shape, which is not a coincidence, as it is proven in [Reference Griffin, Ono, Saikia and Tsai7, Theorem 1].
Theorem 3.5.
-
(1)
$\mathcal {J}_{\mathbb {F}_q}$
has
$(q-1)(q-3)/2$
vertices. -
(2) Every component of
$\mathcal {J}_{\mathbb {F}_q}$
consists of one directed cycle and a directed path of length 1 to every vertex of that cycle. There are no other cycles (even undirected).
When we draw the component of
$\mathcal {J}_{\mathbb {F}_q}$
in the plane, it looks like a bell head with tentacles. Hence, the components of
$\mathcal {J}_{\mathbb {F}_q}$
are playfully called jellyfish and the graph
$\mathcal {J}_{\mathbb {F}_q}$
is a jellyfish swarm in [Reference Griffin, Ono, Saikia and Tsai7].
4 The AGM over
$\mathbb {F}_q$
, where
$q\equiv 5$
(mod 8)
This section contains our results, which are independent of those in [Reference Kayath, Lane, Neifeld, Ni and Xue8], even though, not surprisingly, there are overlaps, especially with [Reference Kayath, Lane, Neifeld, Ni and Xue8, Section 4]. In this section,
$q \equiv 5 \pmod 8$
. Then,
$-1$
is a square in
$\mathbb {F}_q$
, but 2 and i, such that
$i^2=-1$
, are nonsquares.
Lemma 4.1. Let
$(a,b)$
be a vertex of
$\mathcal {J}_{\mathbb {F}_q}$
. Then,
$(a,b)$
has either
$2$
or
$0$
children.
Proof. Suppose
$(a,b)$
has a child
$(A,B)$
, so
$\phi _q(AB) = 1$
. The equation
$x^2=ab$
has exactly two solutions, B and
$-B$
. Then,
$\phi _q(A \cdot (-B))=1$
, so
$(A,-B)$
is the other child.
Recall that
$(a,b)$
has either
$2$
or
$0$
parents from Lemma 2.5.
Theorem 4.2. Let E be the set of edges of
$\mathcal {J}_{\mathbb {F}_q}$
. If
$E \neq \emptyset $
, then there is a cycle in
$\mathcal {J}_{\mathbb {F}_q}$
.
Proof. Consider the edge
$(a,b) \rightarrow (A,B)$
in
$\mathcal {J}_{\mathbb {F}_q}$
. The other child of
$(a,b)$
is
$(A,-B)$
. Consider the pairs
$(c,d)$
and
$(e,f)$
(which do not have to be vertices of
$\mathcal {J}_{\mathbb {F}_q}$
) such that
$$ \begin{align*} c = \frac{A+B}{2}, \quad d^2 = AB; \quad e = \frac{A-B}{2}, \quad f^2 = -AB. \end{align*} $$
Then,
$d = \pm if$
, where
$i \in \mathbb {F}_q$
is such that
$i^2=-1$
, and we compute
$$ \begin{align*}\phi_q(cdef) = \phi_q(ce) \phi_q(\pm if^2) = \phi_q \bigg( \bigg(\frac{a-b}{4}\bigg)^2 \bigg) \cdot \phi_q(\pm 1)\phi_q(i)\phi_q(f^2) = -1.\end{align*} $$
As
$cdef$
is a quadratic nonresidue, exactly one of
$cd$
and
$ef$
is a quadratic residue, so exactly one of
$(c,d)$
,
$(e,f)$
is a vertex. So, we can make the path longer and continue analogously for either
$(A,B)$
or
$(A,-B)$
, but not both. As we can continue in this way at every step and the number of vertices is finite, there must be a cycle in
$\mathcal {J}_{\mathbb {F}_q}$
.
Corollary 4.3. Let
$C \subseteq V$
be the set of vertices in a cycle. Then, every
$c\in C$
has exactly two children; one is a part of the cycle and the other does not have any children.
Proof. Suppose
$c_1 \in C$
has exactly two children,
$c_2$
and
$d_2$
. Suppose
$c_2\in C$
, so it has exactly two children,
$c_3$
and
$c_3'$
. From the proof of Theorem 4.2,
$d_2$
cannot have any children.
Theorem 4.4. Let C be the cycle in
$\mathcal {J}_{\mathbb {F}_q}$
. Then there are more than two vertices in C.
Proof. Suppose that there are edges
$(a,b) \rightarrow (c,d)$
and
$(c,d) \rightarrow (a,b)$
in
$\mathcal {J}_{\mathbb {F}_q}$
. Then,
$$ \begin{align*} c = \frac{a+b}{2} \quad \text{and} \quad a= \frac{c+d}{2} \quad \text{imply} \quad a+c = b+d.\end{align*} $$
Also,
$d^2=ab$
and
$b^2=cd$
imply
$ac = bd$
.
By Vieta’s formulae,
$(x-a)(x-c) = (x-b)(x-d)\in \mathbb {F}_q[x]$
, so
$\{a,c\}=\{b,d\}$
.
From Definition 2.4, we have
$a\neq b$
. Suppose
$a=d$
and
$b = c$
. Then, there is an edge
$(a,b) \rightarrow (b,a)$
which gives
$b = {(a+b)}/{2}$
, and thus
$b = a$
, which is a contradiction.
Theorem 4.5. Consider the path
$(a,b) \rightarrow (c,d) \rightarrow (e,f)$
in
$\mathcal {J}_{\mathbb {F}_q}$
. Then, there is another path
$(g,h) \rightarrow (d,c) \rightarrow (e,f)$
and exactly one of the vertices
$(a,b),(g,h)$
has parents.
Proof. By Lemma 2.5,
$\phi _q(c^2-d^2)=1$
, so
$\phi _q(d^2-c^2)=1$
. Then, by Lemma 2.5, there exist parents
$(g,h)$
of
$(d,c)$
. Also, by Lemma 2.5, we know that there are
$x,y\in \mathbb {F}_q^\times $
such that
$a= c-x$
,
$b = c+x$
and
$x^2= c^2-d^2$
, and
$g= d-y$
,
$h = d+y$
and
$y^2 = d^2 - c^2$
. Then,
$y=\pm ix$
and we compute
$$ \begin{align*} \phi_q((a^2-b^2)(g^2-h^2)) &= \phi_q(((c-x)^2-(c+x)^2)((d-y)^2-(d+y)^2))\\ &=\phi_q(16\cdot cx \cdot dy) = \phi_q(16) \phi_q(cd) \phi_q(xy) = \phi_q(xy)= -1. \end{align*} $$
Thus, either
$(a^2-b^2)$
or
$(g^2-h^2)$
is a quadratic residue. By Lemma 2.5, either
$(a,b)$
or
$(g,h)$
has parents, and the other does not.
Corollary 4.6. Let
$C \subseteq V$
be the set of vertices in a cycle. Then, every
$c\in C$
has exactly 2 parents; one is part of the cycle C and the other is not part of any cycle.
Proof. Suppose
$c \in C$
and recall by Theorem 4.4 that the length of a cycle is at least
$3$
, so we can consider the path
$c_1 \rightarrow c_2 \rightarrow c$
of vertices from the cycle. As c has another parent
${c_2}'$
, by Theorem 4.5, we know there is another path
${c_1}' \rightarrow {c_2}' \rightarrow c$
, and hence exactly one of the vertices
$c_1$
and
$c_1'$
has parents by Theorem 4.5. As
$c_1 \in C$
, it has parents, and hence
$c_1'$
does not have parents.
When we join all the previous claims about
$\mathcal {J}_{\mathbb {F}_q}$
together, we obtain the following theorem. It is useful to look at Figure 2 for the proof of Theorem 4.7.
Theorem 4.7. Every component of
$\mathcal {J}_{\mathbb {F}_q}$
is made either of a single vertex or of the cycle
$c_1 \rightarrow c_2 \rightarrow \cdots \rightarrow c_n$
, vertices
$u_i$
such that
$c_i \rightarrow u_{i+1}$
, vertices
$v_i$
such that
$v_i \rightarrow c_i$
,
$v_i \rightarrow u_i$
, vertices
$w_i$
such that
$w_i \rightarrow v_i$
,
$w_{n+i} \rightarrow v_i$
and vertices
$x_i$
such that
$w_i \rightarrow x_i$
,
$w_{n+i} \rightarrow x_i$
. These are all the edges and vertices of a nontrivial component of
$\mathcal {J}_{\mathbb {F}_q}$
.
A general nontrivial component of
$\mathcal {J}_{\mathbb {F}_q}$
such that
$q \equiv 5 \pmod 8$
.
Proof. Assume there is a cycle C of length n (otherwise, by Theorem 4.2, only vertices are the components). Consider the path
$c_n=(a_n,b_n)\rightarrow c_1=(a_1,b_1)\rightarrow c_2=(a_2,b_2)$
. By Corollary 4.3,
$c_1$
has two children, one is
$c_2=(a_2,b_2)$
in the cycle, and the other one is
$u_2=(a_2,-b_2)$
, which is not in the cycle and has no children. We also know that there is another parent of
$c_2$
and
$u_2$
, which is
$v_2=(b_1,a_1)$
. Since
$c_1=(a_1,b_1)$
has parents because
$c_1\in C$
, this implies that
$\phi _q(a_1^2-b_1^2)=1$
and so
$\phi _q(b_1^2-a_1^2)=1$
; thus
$v_2=(b_1,a_1)$
also has parents by Lemma 2.5. Let these parents be
$w_2=(e_1,f_1)$
and
$w_{2+n}=(f_1,e_1)$
. They have another child
$x_2=(b_1,-a_1)$
. Since
$v_2$
has children, we know that
$x_2$
has no children. Now, we apply Theorem 4.5 to the paths
$c_n\rightarrow c_1\rightarrow c_2$
and
$w_2\rightarrow v_2\rightarrow c_2$
(or
$w_{n+2}\rightarrow v_2\rightarrow c_2$
) to conclude that
$w_2$
and
$w_{n+2}$
have no parents because
$c_n\in C$
, so it has parents. This completes the proof and explains the components containing a cycle in a bit more detail.
Definition 4.8. Let
$q \equiv 5 \pmod 8$
and
$(a,b) \in {\mathbb {F}_q^\times }^2$
such that
$ab(a^2-b^2)\neq 0$
,
$\phi _q(ab) = 1$
, and there exist
$c,d \in \mathbb {F}_q^\times $
such that
$cd(c^2-d^2)\neq 0$
and
$$ \begin{align*} c = \frac{a+b}{2}, \quad d^2 =ab, \quad \phi_q(cd) = 1. \end{align*} $$
Let C be the component of
$\mathcal {J}_{\mathbb {F}_q}$
, which contains the vertex
$(a,b)$
, and suppose it contains a cycle of the length n. Then, using the notation from Theorem 4.7, without loss of generality, we may assume
$(a,b) \in \{c_1, v_1, w_1\}$
. We define an infinite arithmetic-geometric mean sequence as follows:
$$ \begin{align*}\mathrm{AGM_{\mathbb{F}_q}}(a,b) = \begin{cases} (\overline{c_1, c_2, \ldots, c_n}) & \text{if } (a,b) = c_1,\\ (v_1,\overline{c_1, c_2, \ldots, c_n}) & \text{if } (a,b) = v_1,\\ (w_1, v_1,\overline{c_1, c_2, \ldots, c_n}) & \text{if } (a,b) = w_1. \end{cases} \end{align*} $$
Recall that we denote the repeating period by a line over elements of the sequence.
Theorem 4.9. If
$q\geq 29$
and
$q \equiv 5 \pmod 8$
, there is at least one nontrivial component.
Proof. We prove that there is a vertex
$(a,b)$
in
$\mathcal {J}_{\mathbb {F}_q}$
which has parents, that is, with
$\phi _q(a^2-b^2)=1$
by Lemma 2.5. Let g be a generator of the group
$\mathbb {F}_q^\times $
. As
$q\geq 29$
, we have
$g^2, g^4, g^6 \notin \{1,-1\}$
, so we can consider vertices
$(g^2,1)$
,
$(g^4,1)$
,
$(g^6,1)$
. If any of
$$ \begin{align*} (g^2)^2-1^2=g^4-1, \quad (g^4)^2-1^2 = g^8-1, \quad (g^6)^2-1^2 = g^{12}-1 \end{align*} $$
is a square, then we find a vertex with its parents. If not, then
$$ \begin{align*} -1 &= \phi_q(g^8-1) = \phi_q((g^4-1)(g^4+1)) = - \phi(g^4+1), \quad\text{therefore, } \phi(g^4+1)=1;\\ -1 &= \phi_q(g^{12}-1) = - \phi_q(g^8+g^4+1), \quad\text{therefore, } \phi_q(g^8+g^4+1)=1. \end{align*} $$
So, there are
$a,b\in \mathbb {F}_q^{\times }$
such that
$a^2 = g^4+1 \neq 0$
and
$b^2 = g^8+g^4+1 \neq 0$
. Then,
$$ \begin{align*}a^4-b^2 = g^8+2g^4+1-(g^8+g^4+1) = g^4,\quad\text{so } a^4-g^4 = b^2.\end{align*} $$
We have
$\phi _q(a^2g^2) = 1$
and
$a^2g^2(a^4-g^4)\neq 0$
, so
$(a^2,g^2)$
is a vertex of
$\mathcal {J}_{\mathbb {F}_q}$
which has parents.
We note that [Reference Kayath, Lane, Neifeld, Ni and Xue8, Theorem 3(1)] is much stronger than this result for sufficiently large q, but we have the best possible bound for q such that there is at least one nontrivial component in
$\mathcal {J}_{\mathbb {F}_q}$
because for smaller q, there are no nontrivial components. Further, we can be more precise than in Theorem 4.9, and show that there is a nontrivial component consisting only of square vertices (see Corollary 4.15).
Theorem 4.10. There are
$\tfrac 12(q-1)(q-5)$
vertices in
$\mathcal {J}_{\mathbb {F}_q}$
.
Proof. There are
$\tfrac 12(q-1)$
squares which we can pair with
$\tfrac 12(q-1)-2=\tfrac 12(q-5)$
squares (to avoid pairs
$(a,\pm a)$
) and the same for nonsquares, so in total, there are
$\tfrac 12(q-1)(q-5)$
vertices.
Example 4.11. From Theorem 4.10, for
$q=5$
, there are no vertices.
Example 4.12. Let
$q = 13$
. The vertices which contain
$1$
as the first coordinate are
$(1,3)$
,
$(1,4)$
,
$(1,9)$
and
$(1,10)$
, but none of them is part of an edge. Using symmetry and automorphisms
$\varphi _\alpha $
, we conclude that there are no edges in this graph.
Example 4.13. The smallest q with nontrivial graph components is
$q=29$
. There is one cycle of length
$28$
and four cycles of length
$7$
(see Figure 3).
Theorem 4.14 (Main theorem in [Reference Small9]).
Let k be a positive integer and
$q>1$
be a prime power. Let
$\delta = \gcd (q-1,k)$
. Assume
$q>(\delta -1)^4$
. Then, every element of
$\mathbb {F}_q$
is a sum of two kth powers.
Corollary 4.15. If
$q \equiv 5 \pmod 8$
,
$q\geq 29$
, there is a nontrivial component in
$\mathcal {J}_{\mathbb {F}_q}$
consisting only of square vertices.
Components of
$\mathcal {J}_{\mathbb {F}_{29}}$
.
Proof. Let
$q>3^4$
and
$a\in \mathbb {F}_q^{\times }$
be a nonsquare. Since
$4 = (q-1,4)$
, by Theorem 4.14, there are
$x,y\in \mathbb {F}_q$
such that
$x^4+y^4=2a^2$
. Then,
$xy\neq 0$
as
$a\neq 0$
and
$\phi _q(2)=-1$
. If
$x=\pm y$
, then
$x^4+y^4=2x^4=2a^2$
, so
$a=x^2$
or
$a=(ix)^2$
, which is a contradiction. So, we obtain an edge
$(x^4,y^4) \rightarrow (a^2,x^2y^2)$
. Both of the vertices are squares; hence, their component consists of square vertices by Theorem 2.9. For
$q < 81$
, we check the statement by computer. For example, consider the components that contain cycles which contain
$(9,6)$
for
$q=29$
;
$(27,4)$
for
$q=37$
;
$(25,7)$
for
$q=53$
;
$(1,9)$
for
$q=61$
.
5 Challenge for
$q\equiv 1$
(mod 8)
It might be tempting to try to generalise our approach to
$q\equiv 1\pmod {8}$
.
For
$q\equiv 3\pmod {4}$
, the key idea is to use the fact that
$-1$
is not a square in
$\mathbb {F}_q$
to give a natural choice from
$(a_1,b_1)\rightarrow (a_2,\pm b_2)$
for the next term in the sequence. This is indeed used in the definition of the AGM over such
$\mathbb {F}_q$
in [Reference Griffin, Ono, Saikia and Tsai7].
In this paper, we look at
$q\equiv 5\pmod {8}$
; then
$-1$
is a square in
$\mathbb {F}_q$
but
$i\in \mathbb {F}_q$
such that
$i^2=-1$
is not, which is our key idea. We consider two potential steps,
$(a_1,b_1)\rightarrow (a_2,\pm b_2)\rightarrow (*,i^k b_3)$
, where
$0\leq k\leq 3$
. Due to Lemma 2.10, it is not important what the first coordinate is, but it is important that all potential values of the second coordinate differ by multiplication by
$i^k$
. We use that fact and
$\phi _q(i)=-1$
to show that the sequence can continue in a natural way.
Finally, let
$q\equiv 1\pmod {8}$
. Then, there is an eighth root of unity in
$\mathbb {F}_q$
, call it
$\zeta _8$
. To make use of it, we need to consider three potential steps. However, the problem is that all potential values of the second coordinate do not differ by multiplication by
$\zeta _8^k$
, and hence our approach does not work.
In the preprint [Reference Kayath, Lane, Neifeld, Ni and Xue8], Kayath et al. explain how to approach
$q\equiv 1\pmod {8}$
in a clever way using elliptic curves. They achieve exciting results which extend [Reference Griffin, Ono, Saikia and Tsai7, Theorem 5] about the number of components of the graphs corresponding to AGM sequences in the cases where
$q\equiv 5\pmod {8}$
and
$q\equiv 1\pmod {8}$
(see [Reference Kayath, Lane, Neifeld, Ni and Xue8, Theorem 3]). We leave a challenge for interested readers.
Question 5.1. Is there an elementary way to prove that for sufficiently large
$q\equiv 1\pmod {8}$
, there is always a nontrivial component of the graph corresponding to the AGM sequence over
$\mathbb {F}_q$
?
Acknowledgements
We warmly thank Vítězslav Kala for many valuable comments and suggestions throughout this work. We also thank Steffen Müller, Lazar Radičević, Magdaléna Tinková, Jaap Top and Pavlo Yatsyna for helpful discussions. We thank the anonymous referee for several useful comments that improved the paper.
