Codenominator function

Codenominator function and the involution Jimm

The codenominator is a function that extends the Fibonacci sequence to the index set of positive rational numbers, $\mathbf {Q} ^{+}$. Many known Fibonacci identities carry over to the codenominator. One can express Dyer's outer automorphism $\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 $\alpha$-covariant modular function Jimm on the real line $\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.

Definition of the codenominator

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

 $$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 $F(1)=1$. The function $F(1/x)\equiv F(1+x)$ is called the conumerator. (The name `codenominator' comes from the fact that the usual denominator function $D:\,\mathbf {Q} ^{+}\to \mathbf {Z} ^{+}$ can be defined by the functional equations

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

and the initial condition $D(1)=1$.)

The codenominator takes every positive integral value infinitely often.

Connection with the Fibonacci sequence

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

$$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 $x\in \mathbf {Q} ^{+}$, the sequence $G_{n}:=F(x+n)$ is the so-called Gibonacci sequence (also called the generalized Fibonacci sequence) defined by $G_{0}:=F(x)$, $G_{1}:=F(1+x)$ and the recursion $G_{n+2}=G_{n}+G_{n-1}$.

	Examples ($n$ is a positive integer)
1	$F(n)=F_{n}$
2	$F(1/2)=2$, more generally $F(1/n)=F(n+1)=F_{n+1}$.
3	$F(n+1/2)=L_{n}=F_{n+1}+F_{n-1}$ is the Lucas sequence OEIS: A000204.
4	$F(n+1/3)=2F_{n+1}+F_{n-1}$ is the sequence OEIS: A001060.
5	$F(n+1/4)=3F_{n+1}+F_{n-1}$ is the sequence OEIS: A022121.
6	$F(n+1/5)=5F_{n+1}+F_{n-1}$ is the sequence OEIS: A022138.
7	$F(n+1/n)=2F_{n}^{2}+(-1)^{n}$ is the sequence OEIS: A061646.
8	$F(23/31)=107$, $F(31/23)=47$.
9	$F(19/41)=2^{4}\times 7$, $F(41/19)=3^{4}$.
10	$F({\frac {F_{n}}{F_{n+1}}})=n,\quad F({\frac {F_{n+1}}{F_{n}}})=1$.

Properties of the codenominator

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

$$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 $n>1$ and $x\in \mathbf {Q} ^{+}$

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

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

 $$F(1-x)=F(x).$$

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

  $$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 ${\text{num}}:\mathbf {Q} ^{+}\to \mathbb {Z} ^{+}$ can be expressed in terms of the codenominator as ${\text{num}}(x)=F\left({\frac {F(x)}{F(1/x)}}\right)$, which implies

  $${\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:

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

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

    $$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 $s$ is the least index such that $m_{s}=\cdots =m_{l}=1$ (if $\,m_{0}=\cdots =m_{l}=1,$ then set $F[m_{0},\ldots ,m_{s}-1]=0$).

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

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

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

where $\mathrm {cds} (x):=F(1/x)^{2}-F(1/x)F(x)-F(x)^{2}$ is the codiscriminant (called 'characteristic number' in ). This reduces to Tagiuri's identity when $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.

Involution Jimm

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

 $$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 $J(-x):=-1/J(x)$ which is also involutive.

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

 $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:

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

and

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

The function $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 $J$) is 2-1 valued on golden -or noble- numbers (i.e. the numbers in the PGL(2, Z)-orbit of the golden ratio $\varphi ={\frac {1+{\sqrt {5}}}{2}}$).

The extended function $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 $x,y$ has the same end then so does $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

  $J(J(x))=x$ (except on the set of golden irrationals),

Covariance with $1-x$

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

Covariance with $1/x$

  $J(1/x)=1/J(x)$,

`Twisted' covariance with $-x$

  $J(-x)=-1/J(x)$.

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

Reversion invariance

  $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 $\delta :=J(x^{+})-J(x^{-})$ be the jump of $J$ at $x$. Then $\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 )}}}.$

Dyer's outer automorphism and Jimm

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

 $\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) $U:=x\to 1/x$, $V:x\to -x$ and $K:x\to 1-x$.

The map $\alpha$ of generators

 $\alpha :U\to U,\quad V\to UV,\quad K\to K$ 

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

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

 $\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 $J$ is a representation of $\alpha$ as a map P¹(R) $\to$ P¹(R), i.e. $J(Mx)=\alpha (M)J(x)$ whenever $x\in \mathbf {R}$ and $M\in$PGL(2, Z). Another way of saying this is that $J$ is a $\alpha$-covariant map.

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

Jimm as a tree automorphism

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

Jimm and the Stern-Brocot 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

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

The sequence of conumerators is

 $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)

Properties of the plot of Jimm and the golden ratio

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

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

1	$\lim _{x\to +\infty }J(x)=\varphi$,	$J(\varphi )=+\infty$
2	$\lim _{x\to -\infty }J(x)={\bar {\varphi }}$,	$J({\bar {\varphi }})=-\infty$
3	$\lim _{x\to 0^{+}}J(x)=\varphi ^{-1}$,	$J(\varphi ^{-1})=0$
4	$\lim _{x\to 0^{-}}J(x)={\bar {\varphi }}^{-1}$,	$J({\bar {\varphi }}^{-1})=0$
5	$\lim _{x\to 1^{+}}J(x)=1+\varphi$,	$J(1+\varphi )=1$
6	$\lim _{x\to 1^{-}}J(x)=1+{\bar {\varphi }},$	$J(1+{\bar {\varphi }})=1$

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

Jimm on real quadratic irrational numbers

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 $J(a+{\sqrt {b}})=A+{\sqrt {B}}$, then $J(a-{\sqrt {b}})=A-{\sqrt {B}}$, with $a,b,A,B\in \mathbf {Q}$ and $b,B$ positive non-squares.

For example

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

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

Involutivitiy

$J(x)=y\iff J(y)=x$

Covariance with $1-x$

$x+y=1\iff J(x)+J(y)=1$

Covariance with $1/x$

$xy=1\iff J(x)J(y)=1$

Covariance with $-x$

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

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

If $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 $J$ one has

1. $N(x)=1\iff N(J(x))=1$

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

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

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

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

On the other hand, $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 on Markov irrationals

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

Markov number	Markov irrational $x$	$J(x)$
1	$(1+{\sqrt {5}})/2$	$\infty$
2	$1+{\sqrt {2}}$	${\sqrt {2}}$
5	$(9+{\sqrt {221}})/10$	${\sqrt {6}}-1$
13	$(23+{\sqrt {1517}})/26$	${\sqrt {12}}-2$
29	$(53+{\sqrt {7565}})/58$	${\sqrt {35/6}}-1$
34	$(15+5{\sqrt {26}})/17$	${\sqrt {20}}-3$
89	$(157+{\sqrt {71285}})/178$	${\sqrt {30}}-4$
169	$(309+{\sqrt {257045}})/338$	${\sqrt {204/35}}-1$
194	$(86+{\sqrt {21170}})/97$	${\sqrt {119/10}}-2$
233	$(411+{\sqrt {488597}})/466$	${\sqrt {42}}-5$
433	$(791+{\sqrt {1687397}})/866$	$(12{\sqrt {143}}-60)/59$
610	$(269+{\sqrt {209306}})/305$	${\sqrt {56}}-6$
985	$(1801+{\sqrt {8732021}})/1970$	${\sqrt {1189/204}}-1$
1325	$(2339+{\sqrt {15800621}})/2650$	$(3{\sqrt {434}}-42)/14$
1597	$(2817+{\sqrt {22953677}})/3194$	${\sqrt {72}}-7$
2897	$(5137+{\sqrt {75533477}})/5794$	${\sqrt {12958}}/33-2$
4181	$(7375+{\sqrt {157326845}})/8362$	${\sqrt {90}}-8$
5741	$(10497+5{\sqrt {11865269}})/11482$	$3{\sqrt {915530}}/1189-1$
6466	$(2953+5{\sqrt {940706}})/3233$	$(7{\sqrt {10295}}-297)/292$
7561	$(13407+{\sqrt {514518485}})/15122$	$(4{\sqrt {14430}}-279)/139$
9077	$(16013+{\sqrt {741527357}})/18154$	$7{\sqrt {22}}/6-4$
10946	$(19308+4{\sqrt {67395890}})/21892$	${\sqrt {110}}-9$
14701	$(26879+{\sqrt {1945074605}})/29402$	$(70{\sqrt {4899}}-2030)/2029$
28657	$(50549+{\sqrt {7391012837}})/57314$	${\sqrt {132}}-10$
33461	$(61181+{\sqrt {10076746685}})/66922$	$(13{\sqrt {184030}}/2310-1)$
37666	$(17202+5{\sqrt {31921370}})/18833$	$(8{\sqrt {1081730}}-3479)/3421$
43261	$(76711+{\sqrt {16843627085}})/86522$	$13{\sqrt {345}}/70-2$

Jimm and dynamics

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

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

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

$J$(2^1/3)=$[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 $J$ sends the set of real numbers obeying the Gauss-Kuzmin statistics, which is of full measure, to a set of null measure.

Jimm on higher algebraic numbers

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

Functional equations and equivariant modular forms

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

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

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

Some codenumerator values

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

$k$	$F(41/k)$	$k$	$F(41/k)$	$k$	$F(41/k)$	$k$	$F(41/k)$
1	$59369\times 2789$	11	$17$	21	$3\times 5\times 11\times 41$	31	$199$
2	$7\times 2161$	12	$2^{3}\times 3$	22	$31$	32	$17$
3	$5\times 7\times 19$	13	$5\times 13$	23	$2\times 3$	33	$131$
4	$5\times 67$	14	$3\times 281$	24	$2^{2}\times 3$	34	$2\times 3\times 11$
5	$11\times 19$	15	$23$	25	$2^{2}$	35	$2^{6}$
6	$3\times 5\times 7$	16	$19$	26	$7$	36	$3\times 43$
7	$103$	17	$29$	27	$233$	37	$3^{2}\times 23$
8	$3^{2}\times 23$	18	$17$	28	$47$	38	$3\times 137$
9	$31$	19	$3^{4}$	29	$17$	39	$9349$
10	$7^{3}$	20	$89\times 199$	30	$13$	40	$3\times 5\times 7\times 11\times 41\times 2161$

See also

• Fibonacci sequence
• Continued fraction
• Modular form
• Farey sequence
• Pisano period
• Golden number
• Quadratic irrational