Simultaneous Novelty from First-Appearance Times in the Calkin-Wilf Enumeration

Abstract

We study the first-appearance map $\pi :{\mathbb{N}}_{\ge 2}\to {\mathbb{N}}_0$ that assigns to each denominator $d$ the earliest breadth-first index at which a reduced fraction of denominator $d$ occurs in the Calkin-Wilf enumeration of ${\mathbb{Q}}_{>0}$. In parallel, we consider the elementary denominator-first array $D=(U(2)\mid U(3)\mid U(4)\mid \cdots )$ with rows $U(a)=(1/a,2/a,\dots ,(a-1)/a)$ and row-starts $i_0(a)=\frac{(a-2)(a-1)}{2}$. We say level $a$ locks if $\pi (a)=i_0(a)$. Our main theorem is purely combinatorial: for every $n\ge 2$ there exists $i\in \{0,\dots ,n-2\}$ such that the first appearances of denominators $n-i$ and $n+i$ align symmetrically around $i_0(n)$, i.e.\ $\pi (n\pm i)=i_0(n)\pm i$. We prove this pairing (or simultaneous novelty) theorem via a local-coherence analysis of $\pi$ around a level and a discrete intermediate-value argument. An equivalent group-theoretic restatement uses the free monoid $⟨L,R⟩\subset S{L}_2(\mathbb{Z})$ underlying the Calkin-Wilf and Stern-Brocot trees.

4 pages