Codenominator function

The codenominator is a function that extends the Fibonacci sequence to the index set of positive rational numbers, ${\displaystyle \mathbf {Q} ^{+}}$. Many known Fibonacci identities carry over to the codenominator. One can express Dyer's outer automorphism ${\displaystyle \alpha }$of the extended modular group PGL(2, Z) in terms of the codenominator. This automorphism can be viewed as an automorphism group of the trivalent tree. The real ${\displaystyle \alpha }$-covariant modular function Jimm on the real line ${\displaystyle \mathbf {R} }$is defined via the codenominator. Jimm relates the Stern-Brocot tree to the Bird tree. Jimm induces an involution of the moduli space of rank-2 pseudolattices and is related to the arithmetic of real quadratic irrationals.

The codenominator function ${\displaystyle F:\mathbf {Q} ^{+}\to \mathbf {Z} ^{+}}$is defined by the following system of functional equations:

$${\displaystyle F\left(1+{\frac {1}{x}}\right)=F(x),\quad F\left({\frac {1}{1+x}}\right)=F(x)+F\left({\frac {1}{x}}\right)\quad (x\in \mathbf {Q} ^{+})}$$

with the initial condition ${\displaystyle F(1)=1}$. The function ${\displaystyle F(1/x)\equiv F(1+x)}$is called the conumerator. (The name `codenominator' comes from the fact that the usual denominator function ${\displaystyle D:\,\mathbf {Q} ^{+}\to \mathbf {Z} ^{+}}$can be defined by the functional equations

$${\displaystyle D(1+x)=D(x),\quad D(1/(1+x))=D(x)+D(1/x),}$$

and the initial condition ${\displaystyle D(1)=1}$.)

The codenominator takes every positive integral value infinitely often.

For integer arguments, the codenominator agrees with the standard Fibonacci sequence, satisfying the recurrence:

$${\displaystyle F_{n+1}=F_{n}+F_{n-1},\quad F_{1}=F_{2}=1.}$$

The codenominator extends this sequence to positive rational arguments. Moreover, for every rational ${\displaystyle x\in \mathbf {Q} ^{+}}$, the sequence ${\displaystyle G_{n}:=F(x+n)}$is the so-called Gibonacci sequence (also called the generalized Fibonacci sequence) defined by ${\displaystyle G_{0}:=F(x)}$, ${\displaystyle G_{1}:=F(1+x)}$and the recursion ${\displaystyle G_{n+2}=G_{n}+G_{n-1}}$.

The codenominator has the following properties:

1. Fibonacci recursion: The codenominator function satisfies the Fibonacci recurrence for rational arguments:

$${\displaystyle F(x+n)=F_{n}F(x+1)+F_{n-1}F(x),\quad (n>1,\quad x\in \mathbf {Q} ^{+})}$$

2. Fibonacci invariance: For any integer ${\displaystyle n>1}$and ${\displaystyle x\in \mathbf {Q} ^{+}}$

$${\displaystyle F\left({\frac {F_{n}+F_{n+1}x}{F_{n-1}+F_{n}x}}\right)=F(x).}$$

3. Symmetry: If ${\displaystyle x\in (0,1)\cap \mathbf {Q} }$, then

$${\displaystyle F(1-x)=F(x).}$$

4. Continued fractions: For a rational number ${\displaystyle x}$expressed as a simple continued fraction ${\displaystyle [n_{0},n_{1},...,n_{k}]}$, the value of ${\displaystyle F(x)}$can be computed recursively using Fibonacci numbers as:

$${\displaystyle F[n_{0},n_{1},\ldots ,n_{k}]=F_{n_{0}}F[n_{1},\ldots ,n_{k}]+F_{n_{0}-1}F[n_{1}+1,\ldots ,n_{k}].}$$

5. Involutivity: The numerator function ${\displaystyle {\text{num}}:\mathbf {Q} ^{+}\to \mathbb {Z} ^{+}}$can be expressed in terms of the codenominator as ${\displaystyle {\text{num}}(x)=F\left({\frac {F(x)}{F(1/x)}}\right)}$, which implies

$${\displaystyle {\frac {F\left({\frac {F(x)}{F(1/x)}}\right)}{F\left({\frac {F(1/x)}{F(x)}}\right)}}=x\quad (x\in \mathbf {Q} ^{+})}$$

6. Reversion:

$${\displaystyle F[0,n_{1},\ldots ,n_{k}]=F[0,n_{k},\ldots ,n_{1}]}$$

7. Splitting: Let ${\displaystyle 0\leq l\leq r}$be integers. Then:

$${\displaystyle F[m_{0},\ldots ,m_{r}]=F[m_{0},\ldots ,m_{l}]F[m_{l+1},\ldots ,m_{r}]+F[m_{0},\ldots ,m_{s}-1]F[m_{l+1}+1,\ldots ,m_{r}],}$$

where ${\displaystyle s}$is the least index such that ${\displaystyle m_{s}=\cdots =m_{l}=1}$(if ${\displaystyle \,m_{0}=\cdots =m_{l}=1,}$then set ${\displaystyle F[m_{0},\ldots ,m_{s}-1]=0}$).

8. Periodicity: For any positive integer ${\displaystyle m}$, the codenominator ${\displaystyle F[n_{0},n_{1},\ldots ,n_{k}]}$is periodic in each partial quotient ${\displaystyle n_{k}}$modulo ${\displaystyle m}$with period divisible with ${\displaystyle \pi (m)}$, where ${\displaystyle \pi (m)}$is the Pisano period.

9. Fibonacci identities: Many known Fibonacci identities admit a codenominator version. For example, if at least two among ${\displaystyle x,y,z\in \mathbf {Q} ^{+}}$are integral, then

$${\displaystyle F({x+y})F({x+z})-F(x)F({x+y+z})=\mathrm {cds} (x)F({y})F(z),}$$

where ${\displaystyle \mathrm {cds} (x):=F(1/x)^{2}-F(1/x)F(x)-F(x)^{2}}$is the codiscriminant (also called the 'characteristic number'). This reduces to Tagiuri's identity when ${\displaystyle x,y,z\in \mathbb {Z} }$; which in turn is a generalization of the famous Catalan identity. Any Gibonacci identity can be interpreted as a codenominator identity. There is also a combinatorial interpretation of the codenominator.

The codiscriminant is a 2-periodic function.

The Jimm (ج) function is defined on positive rational arguments via

$${\displaystyle J(x):={\frac {F(1/x)}{F(x)}}\quad (x\in \mathbf {Q} ^{+})}$$This function is involutive and admits a natural extension to non-zero rationals via ${\displaystyle J(-x):=-1/J(x)}$which is also involutive.

Let ${\displaystyle x=[n_{0},n_{1},\dots ,n_{k}]>1}$be the simple continued fraction expansion of ${\displaystyle x\in \mathbf {Q} ^{+}}$. Denote by ${\displaystyle 1_{k}}$the sequence ${\displaystyle 1,1,\dots ,1}$of length ${\displaystyle k}$. Then:

${\displaystyle J(x)=[1_{n_{0}-1},2,1_{n_{1}-2},2,1_{n_{2}-2},2,\dots ,2,1_{n_{k-1}-2},2,1_{n_{k}-1}]}$

with the rules:

${\displaystyle [\dots ,n,1_{0},m,\dots ]:=[\dots ,n,m,\dots ]}$

and

${\displaystyle [\dots ,n,1_{-1},m,\dots ]:=[\dots ,n+m-1,\dots ]}$.

The function ${\displaystyle J}$admits an extension to the set of non-zero real numbers by taking limits (for positive real numbers one can use the same rules as above to compute it). This extension (denoted again ${\displaystyle J}$) is 2-1 valued on golden -or noble- numbers (i.e. the numbers in the PGL(2, Z)-orbit of the golden ratio ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$).

The extended function ${\displaystyle J}$

• sends rationals to rationals,
• sends golden numbers to rationals,
• is involutive except on the set of golden numbers,
• respects ends of continued fractions; i.e. if the continued fractions of ${\displaystyle x,y}$has the same end then so does ${\displaystyle J(x),J(y)}$,
• sends real quadratic irrationals (except golden numbers) to real quadratic irrationals (see below),
• commutes with the Galois conjugation on real quadratic irrationals (see below),
• is continuous at irrationals,
• has jumps at rationals,
• is differentiable a.e.,
• has vanishing derivative a.e.,
• sends a set of full measure to a set of null measure and vice versa

and moreover satisfies the functional equations

Involutivity

${\displaystyle J(J(x))=x}$(except on the set of golden irrationals),

Covariance with ${\displaystyle 1-x}$

${\displaystyle J(1-x)=1-J(x)}$(provided ${\displaystyle x\neq 1}$),

Covariance with ${\displaystyle 1/x}$

${\displaystyle J(1/x)=1/J(x)}$,

`Twisted' covariance with ${\displaystyle -x}$

${\displaystyle J(-x)=-1/J(x)}$.

These four functional equations in fact characterize Jimm. Additionally, Jimm satisfies

Reversion invariance

${\displaystyle J([n_{0},n_{1},\dots ,n_{k}])=[m_{0},m_{1},\dots ,m_{l}]\implies J([n_{k},\dots ,n_{1},n_{0}])=[m_{l},\dots ,m_{1},m_{0}]}$

Jumps

Let ${\displaystyle \delta :=J(x^{+})-J(x^{-})}$be the jump of ${\displaystyle J}$at ${\displaystyle x}$. Then ${\displaystyle \delta {\bigl (}[1^{m},\;n_{1},\ldots ,n_{k}]{\bigr )}\;=\;{\frac {(-1)^{\,m+n_{1}+\cdots +n_{k}}\,{\sqrt {5}}}{\mathrm {cds} \!{\bigl (}[\,0,\;n_{k},\;n_{k-1},\;\ldots ,\;n_{1},\;n_{1}-1]{\bigr )}}}.}$

The extended modular group PGL(2, Z) admits the presentation

${\displaystyle \langle U,V,K\,|\,U^{2}=V^{2}=K^{2}=(UV)^{2}=(KU)^{3}=1\rangle }$

where (viewing PGL(2, Z) as a group of Möbius transformations) ${\displaystyle U:=x\to 1/x}$, ${\displaystyle V:x\to -x}$and ${\displaystyle K:x\to 1-x}$.

The map ${\displaystyle \alpha }$of generators

${\displaystyle \alpha :U\to U,\quad V\to UV,\quad K\to K}$

defines an involutive automorphism PGL(2, Z) ${\displaystyle \to }$PGL(2, Z), called Dyer's outer automorphism. It is known that Out(PGL(2, Z))${\displaystyle \simeq \mathbf {Z} /2\mathbf {Z} }$is generated by ${\displaystyle \alpha }$. The modular group PSL(2, Z) ${\displaystyle =\langle VU,KU\rangle <}$PGL(2, Z) is not invariant under ${\displaystyle \alpha }$. However, the subgroup ${\displaystyle \Gamma =\langle KU,UVKV\rangle <}$PSL(2, Z) is ${\displaystyle \alpha }$-invariant. Conjugacy classes of subgroups of ${\displaystyle \Gamma }$is in 1-1 correspondence with bipartite trivalent graphs, and ${\displaystyle \alpha }$thus defines a duality of such graphs. This duality transforms zig-zag paths on a graph ${\displaystyle {\mathcal {G}}}$to straight paths on its ${\displaystyle \alpha }$-dual graph and vice versa.

Dyer's outer automorphism can be expressed in terms of the codenumerator, as follows: Suppose ${\displaystyle p,q,r,s\in \mathbf {Z} ^{+}}$and ${\displaystyle M={\begin{bmatrix}p&q\\r&s\end{bmatrix}}\in \mathrm {PGL} _{2}(\mathbf {Z} )}$. Then

${\displaystyle \alpha (M)={\begin{bmatrix}\mathrm {F} \left({\frac {2r+s}{2p+q}}\right)-\mathrm {F} \left({\frac {r+s}{p+q}}\right)&2\mathrm {F} \left({\frac {r+s}{p+q}}\right)-\mathrm {F} \left({\frac {2r+s}{2p+q}}\right)\\\mathrm {F} \left({\frac {2p+q}{2r+s}}\right)-\mathrm {F} \left({\frac {p+q}{r+s}}\right)&2\mathrm {F} \left({\frac {p+q}{r+s}}\right)-\mathrm {F} \left({\frac {2p+q}{2r+s}}\right)\end{bmatrix}}.}$

The covariance equations above implies that ${\displaystyle J}$is a representation of ${\displaystyle \alpha }$as a map P¹(R) ${\displaystyle \to }$P¹(R), i.e. ${\displaystyle J(Mx)=\alpha (M)J(x)}$whenever ${\displaystyle x\in \mathbf {R} }$and ${\displaystyle M\in }$PGL(2, Z). Another way of saying this is that ${\displaystyle J}$is a ${\displaystyle \alpha }$-covariant map.

In particular, ${\displaystyle J}$sends PGL(2, Z)-orbits to PGL(2, Z)-orbits, thereby inducing an involution of the moduli space of rank-2 pseudo lattices, PGL(2, Z)\ P¹(R), where P¹(R) is the projective line over the real numbers.

Given ${\displaystyle x,y\in }$P¹(R), the involution ${\displaystyle J}$sends the geodesic on the hyperbolic upper half plane ${\displaystyle {\mathcal {H}}}$through ${\displaystyle x,y}$to the geodesic through ${\displaystyle J(x),J(y)}$, thereby inducing an involution of geodesics on the modular curve PGL(2, Z)\${\displaystyle {\mathcal {H}}}$. It preserves the set of closed geodesics because ${\displaystyle J}$sends real quadratic irrationals to real quadratic irrationals (with the exception of golden numbers, see below) respecting the Galois conjugation on them.

Djokovic and Miller constructed ${\displaystyle {\text{Aut}}({\text{PGL}}_{2}(\mathbf {Z} ))}$as a group of automorphisms of the infinite trivalent tree. In this context, ${\displaystyle \alpha }$appears as an automorphism of the infinite trivalent tree. ${\displaystyle {\text{Aut}}({\text{PGL}}_{2}(\mathbf {Z} ))}$is one of the 7 groups acting with finite vertex stabilizers on the infinite trivalent tree.

Applying Jimm to each node of the Stern-Brocot tree permutes all rationals in a row and otherwise preserves each row, yielding a new tree of rationals called Bird's tree, which was first described by Bird. Reading the denominators of rationals on Bird's tree from top to bottom and following each row from left to right gives Hinze's sequence:

${\displaystyle 2,3,3,5,4,4,5,8,7,5,7,7,5,...}$(sequence 268087 in the OEIS)

The sequence of conumerators is:

${\displaystyle 1,2,1,3,3,1,2,5,4,4,5,2,1,3,3,8,7,5,7,7,...}$(sequence A162910 in the OEIS)

By involutivity, the plot of ${\displaystyle J}$is symmetric with respect to the diagonal ${\displaystyle x=y}$, and by covariance with ${\displaystyle 1-x}$, the plot is symmetric with respect to the diagonal ${\displaystyle x+y=1}$. The fact that the derivative of ${\displaystyle J}$is 0 a.e. can be observed from the plot.

The plot of Jimm hides many copies of the golden ratio ${\displaystyle \varphi }$in it. For example

More generally, for any rational ${\displaystyle q}$, the limit ${\displaystyle \lim _{x\to q+}J(x)}$is of the form ${\displaystyle y:={\frac {a\varphi +b}{c\varphi +d}}}$with ${\displaystyle a,b,c,d\in \mathbf {Z} }$and ${\displaystyle ad-bc=\pm 1}$. The limit ${\displaystyle \lim _{x\to q-}J(x)}$is its Galois conjugate ${\displaystyle {\bar {y}}:={\frac {a{\bar {\varphi }}+b}{c{\bar {\varphi }}+d}}}$. Conversely, one has ${\displaystyle J(y)=J({\bar {y}})=q}$.

Jimm sends real quadratic irrationals to real quadratic irrationals, except the golden irrationals, which it sends to rationals in a 2–1 manner. It commutes with the Galois conjugation on the set of non-golden quadratic irrationals, i.e. if ${\displaystyle J(a+{\sqrt {b}})=A+{\sqrt {B}}}$, then ${\displaystyle J(a-{\sqrt {b}})=A-{\sqrt {B}}}$, with ${\displaystyle a,b,A,B\in \mathbf {Q} }$and ${\displaystyle b,B}$positive non-squares.

For example:

${\displaystyle J\left({\frac {3+5{\sqrt {2}}}{7}}\right)={\frac {-3+2{\sqrt {95}}}{7}},\quad J({\sqrt {11}})={\frac {15+{\sqrt {901}}}{26}}.}$

The functional equations can be written in the two-variable form as:

Involutivitiy

${\displaystyle J(x)=y\iff J(y)=x}$

Covariance with ${\displaystyle 1-x}$

${\displaystyle x+y=1\iff J(x)+J(y)=1}$

Covariance with ${\displaystyle 1/x}$

${\displaystyle xy=1\iff J(x)J(y)=1}$

Covariance with ${\displaystyle -x}$

${\displaystyle x+y=0\iff J(x)J(y)=-1}$

As a consequence of these, one has: ${\displaystyle {\frac {1}{x}}+{\frac {1}{y}}=1\iff {\frac {1}{J(x)}}+{\frac {1}{J(y)}}=1.}$Therefore ${\displaystyle J}$sends the pair ${\displaystyle ({\mathcal {B}}_{x},{\mathcal {B}}_{y})}$of complementary Beatty sequences to the pair ${\displaystyle ({\mathcal {B}}_{J(x)},{\mathcal {B}}_{J(y)})}$of complementary Beatty sequences; where ${\displaystyle x,y}$are non-golden irrationals with ${\displaystyle 1/x+1/y=1}$.

If ${\displaystyle x=a+{\sqrt {b}}\quad (a,b\in \mathbf {Q} )}$is a real quadratic irrational, which is not a golden number, then as a consequence of the two-variable version of functional equations of ${\displaystyle J}$one has

1. ${\displaystyle N(x)=1\iff N(J(x))=1}$

2. ${\displaystyle Tr(x)=0\iff N(J(x))=-1}$

3. ${\displaystyle Tr(x)=1\iff Tr(J(x))=1}$

4. ${\displaystyle Tr({1}/{x})=1\iff Tr({1}/{J(x)})=1}$

where ${\displaystyle N(x):=a^{2}-b}$denotes the norm and ${\displaystyle Tr(x):=2a}$denotes the trace of ${\displaystyle x}$.

On the other hand, ${\displaystyle J}$may send two members of one real quadratic number field to members of two different real quadratic number fields; i.e. it does not respect individual class groups.

Jimm sends the Markov irrationals to 'simpler' quadratic irrationals, see table below.

Jimm conjugates the Gauss map ${\displaystyle G}$(see Gauss–Kuzmin–Wirsing operator) to the so-called Fibonacci map ${\displaystyle \Phi }$, i.e. ${\displaystyle \Phi =J\circ G\circ J}$.

The expression of Jimm in terms of continued fractions shows that, if a real number ${\displaystyle x}$obeys the Gauss-Kuzmin distribution, then the asymptotic density of 1's among the partial quotients of ${\displaystyle J(x)}$is one, i.e. ${\displaystyle J(x)}$does not obey the Gauss-Kuzmin statistics. For example

2^1/3=${\displaystyle [1,3,1,5,1,1,4,1,1,8,1,14,1,10,2,1,4,12,2,3,2,...]}$

${\displaystyle J}$(2^1/3)=${\displaystyle [2,1,3,1,1,1,4,1,1,4,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,2,3,1,1,2,1,1,1,1,1...]}$

This argument also shows that ${\displaystyle J}$sends the set of real numbers obeying the Gauss-Kuzmin statistics, which is of full measure, to a set of null measure.

It is widely believed that if ${\displaystyle x}$is an algebraic number of degree ${\displaystyle >2}$, then it obeys the Gauss-Kuzmin statistics. By the above remark, this implies that ${\displaystyle J(x)}$violates the Gauss-Kuzmin statistics. Hence, according to the same belief, ${\displaystyle J(x)}$must be transcendental. This is the basis of the conjecture that Jimm sends algebraic numbers of degree ${\displaystyle >2}$to transcendental numbers. A stronger version of the conjecture states that any two algebraically related ${\displaystyle J(x)}$, ${\displaystyle J(y)}$are in the same PGL(2, Z)-orbit, if ${\displaystyle x,y}$are both algebraic of degree ${\displaystyle >2}$.

Given a representation ${\displaystyle \rho :\mathrm {PSL} _{2}(\mathbf {Z} )\to \mathrm {PGL} _{2}(\mathbf {Z} )}$, a meromorphic function ${\displaystyle h}$on ${\displaystyle {\mathcal {H}}}$is called a ${\displaystyle \rho }$-covariant function if

${\displaystyle h(\gamma \cdot z)=\rho (\gamma )\cdot h(z)\quad {\text{for all }}z\in \mathbf {H} ,\,\gamma \in \Gamma .}$

(sometimes ${\displaystyle h}$is also called a ${\displaystyle \rho }$-equivariant function). It is known that there exists meromorphic covariant functions ${\displaystyle h}$on the upper half plane ${\displaystyle {\mathcal {H}}}$, i.e. functions satisfying ${\displaystyle h(Mz)=Mh(z)}$. The existence of meromorphic functions satisfying a version of the functional equations for ${\displaystyle J}$is also known.

Below is a table of some codenominator values ${\displaystyle 41/k}$, where 41 is an arbitrarily chosen number.

• Farey sequence