Orphans in Forests of Linear Fractional Transformations

Sandie Han, Ariane M. Masuda, Satyanand Singh, Johann ThielThe Electronic Journal of Combinatorics 2015

TL;DR

This paper explores "orphans" in a forest of mathematical structures called Calkin-Wilf trees, which are built from positive linear fractional transformations (PLFTs). The authors provide a way to count these orphans for a given determinant and develop a method to find the orphan ancestor of any PLFT. They also extend this concept to complex numbers, showing that every positive complex number has a finite number of ancestors in related complex trees.

What Problem Does This Paper Address?

The Calkin-Wilf tree is a well-known structure that enumerates all positive rational numbers. This paper generalizes this concept to positive linear fractional transformations (PLFTs), which are functions of the form $f(z) = \frac{az+b}{cz+d}$ where $a, b, c, d$ are non-negative integers and $ad-bc \neq 0$. These PLFTs can be organized into an infinite forest of trees, where each tree is rooted by a special type of PLFT called an "orphan." The problem addressed is to understand the properties of these orphans, specifically:

  1. Counting Orphans: How many orphans exist for a given determinant $D$?
  2. Finding Ancestors: How can we determine the orphan ancestor of any given PLFT within its respective tree?
  3. Complex Extension: How does this concept of orphans and ancestors extend to complex numbers, and what are the properties of these complex orphans?

Methods

The paper employs a combination of combinatorial, number-theoretic, and algebraic techniques:

  • Combinatorial Formula: The authors derive a formula for $h(D)$, the number of orphan PLFTs with determinant $D$. This formula relates $h(D)$ to partition functions and divisor sums, specifically $h(D) = v_2(D) + 2\sigma(D) - \tau(D)$, where $v_2(D)$ is the number of partitions of $D$ into two parts, $\sigma(D)$ is the sum of divisors of $D$, and $\tau(D)$ is the number of divisors of $D$.
  • Continued Fractions: The paper extensively uses continued fraction representations of rational numbers and PLFTs. This is a key tool for understanding the structure of the Calkin-Wilf trees and the relationships between parent and child nodes. Lemma 6, for instance, shows how continued fractions encode a PLFT's location within its tree.
  • Matrix Representation: PLFTs are naturally associated with matrices in $GL_2(\mathbb{N}_0)$. The paper leverages matrix multiplication to compute descendants and analyze the structure of the trees, particularly in relation to the generators $L_1 = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ and $R_1 = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$.
  • Asymptotic Analysis: For the function $h(D)$, the paper derives asymptotic behavior, showing $h(D) \sim \frac{3}{\pi^2} D (\log D)^2$ as $D \to \infty$, and provides a formula for the summatory function $\sum_{D<x} h(D) = \frac{1}{4} x^2 \log^2 x + O(x^2 \log x)$.
  • Complex Number Analysis: The paper extends the PLFT framework to complex numbers in the first quadrant ($D_0 = \{z \in \mathbb{C} : R(z) > 0, I(z) > 0\}$). It defines complex (u,v)-orphans and characterizes them using inequalities involving the real and imaginary parts of complex numbers.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and combinatorial formulas rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Orphans as Roots: The concept of "orphans" provides a natural way to partition the entire set of PLFTs into disjoint trees, with each orphan being the unique root of its tree.
  • Determinant and Orphan Count: The number of orphans with a fixed determinant $D$ is not arbitrary but is governed by a specific combinatorial formula, linking number-theoretic properties (divisors, partitions) to the structure of PLFT trees.
  • Continued Fractions as Navigation Tools: The continued fraction representation of a PLFT or rational number acts as a map, revealing its position within its Calkin-Wilf tree and its relationship to its ancestors and descendants.
  • Complex Orphans and Geometric Constraints: Extending the concept to complex numbers reveals that (u,v)-orphans are constrained to specific regions of the complex plane, defined by inequalities related to their real and imaginary parts. This highlights a geometric interpretation of the tree structure.
  • Finite Ancestors in Complex Trees: Despite the infinite nature of the complex Calkin-Wilf trees, every complex number in the first quadrant has a finite number of ancestors, a crucial property for understanding their structure.

Key Results

  • Combinatorial Formula for $h(D)$: $h(D) = v_2(D) + 2\sigma(D) - \tau(D)$, where $h(D)$ is the number of orphan PLFTs with determinant $D$.
  • Asymptotic Behavior of $h(D)$: $h(D) \sim \frac{3}{\pi^2} D (\log D)^2$ as $D \to \infty$.
  • Summatory Function of $h(D)$: $\sum_{D<x} h(D) = \frac{1}{4} x^2 \log^2 x + O(x^2 \log x)$.
  • Characterization of Complex (u,v)-Orphans: A complex number $z = x+iy$ is a (u,v)-orphan if and only if $x \le v$ and $|2uz - 1| \ge 1$.
  • Theorem 8: Provides a detailed equivalence between the continued fraction representation of a PLFT and its decomposition into products of basic transformations, crucial for identifying orphan roots.
  • Theorem 10: Establishes a method to find the orphan root of a PLFT by maximizing certain parameters in its continued fraction representation.

Limitations and Future Work

  • Non-unique Representations: The paper notes that continued fraction representations are not always unique, which can complicate the maximization process for finding orphan roots. The paper addresses this by referring to "optimal pairs" of representations.
  • Special Cases of PLFTs: While Theorem 8 handles cases where $c, d \neq 0$, the paper briefly mentions that modifications are needed for cases where coefficients are zero.
  • Generalization of Ancestor Properties: The paper focuses on the existence of finite ancestors for complex numbers in $D_0$. Further exploration could investigate the specific structure and distribution of these ancestors.
  • Further Exploration of $h(D)$: While the asymptotic behavior of $h(D)$ is derived, deeper number-theoretic properties of this function could be a direction for future research.
  • Connection to Other Mathematical Structures: The paper hints at connections to other areas like statistical mechanics and spin chains, suggesting potential avenues for interdisciplinary research.

Summary updated

Abstract

This paper studies the set of orphans in certain Calkin-Wilf trees generated by linear fractional transformations.
BibTeX
@article{han2015orphans,
  author = {Sandie Han and Ariane M. Masuda and Satyanand Singh and Johann Thiel},
  title = {{Orphans in Forests of Linear Fractional Transformations}},
  journal = {The Electronic Journal of Combinatorics},
  year = {2015},
}

Loading related content...

Figure