q q -analogs of rational numbers: from Ostrowski numeration systems to perfect matchings

Jean-Christophe Aval, Sébastien Labbé · 2025

Read q q -analogs of rational numbers: from Ostrowski numeration systems to perfect matchings by Jean-Christophe Aval, Sébastien Labbé (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-11290.txt.

Introduction

Jean-Christophe Aval and Sébastien Labbé give three counting interpretations for q-analogs of rational numbers, a deformed version of fractions introduced by Morier-Genoud and Ovsienko. In a q-analog, each integer is replaced by a polynomial in q that reduces to the integer when q is one. Earlier readings of these q-rationals covered only fractions above one, which left half the picture missing.

Their readings use a new Ostrowski numeration system, order ideals in fence posets, and perfect matchings of snake graphs, all working for every positive fraction from one shared object. Order-preserving bijections carry the proofs. A formula for a q-analog of Markoff numbers is recovered, plus a fourth reading via lattice points in a polytope.

Catalog record

CREATORJean-Christophe Aval, Sébastien Labbé
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE136 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-11290

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

q q -analogs of rational numbers: from Ostrowski numeration systems to perfect matchings Jean-Christophe Aval, Sébastien Labbé Abstract . We consider the q q -deformation of rational numbers introduced recently by Morier-Genoud and Ovsienko. We propose three enumerative interpretations of these q q -rationals: in terms of a new version of Ostrowski’s numeration system for integers, in terms of order ideals of fence posets and in terms of perfect matchings of snake graphs. Contrary to previous results which are restricted to rational numbers greater than one, our interpretations work for all positive rational numbers and are based on a single combinatorial object for defining both the numerator and denominator. The proofs rest on order-preserving bijections between posets over these objects. We recover a formula for a q q -analog of Markoff numbers. We also deduce a fourth interpretation given in terms of the integer points inside a polytope in ℝ k \mathbb{R}^{k} on both sides of a hyperplane where k k is the length of the continued fraction expansion. 2010 Mathematics Subject Classification Primary 05A15, 05A30 and 11A63; Secondary 05A19, 05C10, 06A07, 11A55, 11J06, 52A20 and 68R15 1. Introduction Fix a positive irrational number {x} with continued fraction expansion [a_{0};a_{1},a_{2},\dots] with a_{0}\geq 0 and a_{n}\geq 1 for every n\geq 1 . Let (p_{n}) and (q_{n}) be the sequence of numerators and denominators of the convergents p_{n}/q_{n} to {x} [ HW08 , Theorem 149] : (1) \displaystyle p_{i} \displaystyle=a_{i}p_{i-1}+p_{i-2}, \displaystyle\text{ with }p_{-1}=1\text{ and }p_{0}=a_{0}, \displaystyle q_{i} \displaystyle=a_{i}q_{i-1}+q_{i-2}, \displaystyle\text{ with }q_{-1}=0\text{ and }q_{0}=1. It was proved by Ostrowski a century ago [ Ost21 ] that every positive integer n can be written uniquely as n=\sum_{i=1}^{k}b_{i}q_{i} where the integer coefficients satisfy 0\leq b_{i}\leq a_{i} and if b_{i}=a_{i} then b_{i-1}=0 . See also [ Ber01 , AS03 , Arn02 , Fog02 ] or the more recent [ EFG+12 ] . To have uniqueness, different conditions can be imposed on the sequence (b_{i})_{i} , leading to different versions of the theorem. For example, two choices are called first and second multiplicative sequences in the chapter [ Arn02 ] describing the substitutive structure of Sturmian sequences. In this article, we propose a third choice leading to an alternating-sign analog of Ostrowski’s theorem using the sum of the numerator and denominator of the convergents. Our choice of sequences can be stated as follows. Let a=[a_{0};a_{1},\dots,a_{k-1}] be the even or odd-length continued fraction expansion of a positive rational number where a_{0}\geq 0 and a_{i}\geq 1 for every index i with 1\leq i<k [ HW08 , Theorem 162] . We say that a finite sequence of integers (b_{i})_{0\leq i<k} is admissible for a if it satisfies • 0\leq b_{i}\leq a_{i} for every integer i with 0\leq i<k , • if i>0 is odd and b_{i}=a_{i} , then b_{i-1}=a_{i-1} , • if i>0 is even and b_{i}=0 , then b_{i-1}=0 . We reuse the vocabulary of “admissible” sequence from [ DT89 , LL24 ] where it was used to describe another numeration system based on a single substitution. Also, let (r_{i})_{0\leq i\leq k} be the sequence defined by r_{i}=p_{i-1}+q_{i-1} for every integer i with 0\leq i\leq k where (p_{i})_{0\leq i\leq k-1} and (q_{i})_{0\leq i\leq k-1} are the numerators and denominators of the convergents defined as above from the finite continued fraction expansion a . Note that we have r_{0}=p_{-1}+q_{-1}=1 and r_{1}=p_{0}+q_{0}=a_{0}+1 . Using this choice of admissible sequences, we propose the following alternating-sign version of Ostrowski’s theorem. Note that it is distinct from the alternate Ostrowski numeration system proposed in [ Bou16 ] . Theorem A . Let k\geq 1 be an integer and a=[a_{0};a_{1},\dots,a_{k-1}] be the even or odd-length continued fraction expansion of a positive rational number. Let {\mathcal{Z}}(a)=\mathbb{Z}\,\cap\,[0,r_{k}) if k is odd or {\mathcal{Z}}(a)=\mathbb{Z}\cap[r_{k-1}-r_{k},r_{k-1}) if k is even. Every integer n\in{\mathcal{Z}}(a) can be written uniquely as n=\sum_{i=0}^{k-1}(-1)^{i}b_{i}r_{i} where (b_{i})_{0\leq i\leq k-1} is an admissible sequence for a . Given a positive rational number {x} with continued fraction expansion a=[a_{0};a_{1},\dots,a_{k-1}] , it is natural to define the set of admissible sequences for a : {\mathcal{B}}(a)=\{(b_{i})_{0\leq i\leq k-1}\mid(b_{i})_{0\leq i\leq k-1}\text{ is admissible for }a\}. Theorem A implies that n\mapsto(b_{i})_{0\leq i\leq k-1} defines a bijection \rep_{a}:{\mathcal{Z}}(a)\to{\mathcal{B}}(a) representing every integer in the interval {\mathcal{Z}}(a) as an admissible sequence for a . When a=[1;1,\dots,1] is a convergent to the golden ratio, we recover similar values as in the negaFibonacci number system proposed by Donald Knuth [ Knu09 ] in Section 7.1.3 Bitwise tricks & techniques . But, a difference is that admissible sequences allow using two consecutive Fibonacci numbers, whereas negaFibonacci numeration system forbids doing this; see Example 4.5 . We split the set {\mathcal{B}}(a) into two as the disjoint union {\mathcal{B}}(a)={\mathcal{B}}^{\bullet}(a)\cup{\mathcal{B}}^{\circ}(a) where \displaystyle{\mathcal{B}}^{\bullet}(a) \displaystyle=\{(b_{i})_{0\leq i\leq k-1}\in{\mathcal{B}}(a)\mid b_{0}=a_{0}=0<b_{1}=a_{1}\text{ or }0<b_{0}\}, \displaystyle{\mathcal{B}}^{\circ}(a) \displaystyle=\{(b_{i})_{0\leq i\leq k-1}\in{\mathcal{B}}(a)\mid b_{0}=a_{0}=0\leq b_{1}<a_{1}\text{ or }0=b_{0}<a_{0}\}. When k is even, we can show that the cardinality of the two sets are equal respectively to the numerator and denominator of the rational number represented by a , that is, \#{\mathcal{B}}^{\bullet}(a)=p_{k-1}\quad\text{ and }\quad\#{\mathcal{B}}^{\circ}(a)=q_{k-1}. This is a consequence of the following stronger result which states that the 1-norm statistics over the set of admissible sequences for a can be computed from a product of the following two matrices: L_{q}=\left(\begin{array}[]{rr}q&0\\ q&1\end{array}\right)\qquad\text{ and }\qquad R_{q}=\left(\begin{array}[]{rr}q&1\\ 0&1\end{array}\right) where q is some indeterminate. Theorem B . Let a=[a_{0};\dots,a_{2\ell-1}] be the even-length continued fraction expansion of a positive rational number. The set of admissible sequences for a satisfies \left(\begin{array}[]{r}\sum_{b\in{\mathcal{B}}^{\bullet}(a)}q^{\|b\|_{1}}\\ \sum_{b\in{\mathcal{B}}^{\circ}(a)}q^{\|b\|_{1}}\end{array}\right)=\left(\begin{smallmatrix}1&0\\ 0&q\end{smallmatrix}\right)^{-1}R_{q}^{a_{0}}L_{q}^{a_{1}}\cdots R_{q}^{a_{2\ell-2}}L_{q}^{a_{2\ell-1}}\left(\begin{smallmatrix}1\\ 0\end{smallmatrix}\right). where \|b\|_{1}=b_{0}+b_{1}+\dots+b_{2\ell-1} for every admissible sequence (b_{i})_{0\leq i<2\ell}\in{\mathcal{B}}(a) . We prove in Section 11 that the set {\mathcal{B}}(a) of admissible sequences is a convex subset in \mathbb{Z}^{2\ell} whose convex hull is a polytope and that {\mathcal{B}}^{\bullet}(a) and {\mathcal{B}}^{\circ}(a) are the two sets of integer points in the polytope on both sides of a hyperplane. A q -analog of all rational numbers was proposed in [ MGO20 ] . It is given as a ratio of two polynomials in the indeterminate q . When the rational number is larger than one, they also gave a combinatorial interpretation of the coefficients of the numerator and denominator polynomials in terms of the subsets of closures of an oriented path graph. Closures can equivalently be defined as the lower order ideals of a fence poset [ MSS21 , KOR23 ] . This is the terminology that we use in this work. We extend the definition of fence posets proposed in [ MSS21 , KOR23 ] in order to describe all of them, not only those that start with an up step. This allows to interpret simultaneously the numerator and the denominator of a q -rational number on a single fence poset. Also, this provides an enumerative interpretation of the q -analog of every positive rational number without the condition >1 assumed in [ MGO20 ] . To every positive rational number x , whose even-length continued fraction expansion is a=[a_{0};a_{1},\dots,a_{2\ell-1}] , we associate a fence poset {\mathcal{F}}({x}) containing a_{0}+a_{1}+\dots+a_{2\ell-1} elements and a_{0}+a_{1}+\dots+a_{2\ell-1}-1 covering relations; please refer to the precise definition in Section 5 . To each such fence poset {\mathcal{F}}({x}) , we denote its set of lower order ideals by {\mathcal{J}}({x}) . The set {\mathcal{J}}({x}) of lower order ideals is naturally partitioned into a disjoint union {\mathcal{J}}({x})={\mathcal{J}}^{\bullet}({x})\cup{\mathcal{J}}^{\circ}({x}) according to whether the left-most vertex of the fence poset is in the

Read the complete text