Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: continued fraction

Bottom of Page

1 to 33 of 33

  1.  
    • CommentRowNumber1.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 22nd 2014

    Wrote continued fraction, emphasizing coalgebraic aspects. More links should be inserted, and some more material needs to be filled in.

    • CommentRowNumber2.
    • CommentAuthorMike Shulman
    • CommentTimeMar 22nd 2014

    Very nice! What does the constructive theory of continued fractions look like?

    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 22nd 2014

    Yeah, I don’t really know. I stuck in the thing about classical mathematics because this is the only story on continued fractions that I really know. As you can see, the theory seems to bifurcate into one for rational numbers and one for irrational numbers, and I suppose a trouble is in deciding whether some number is rational or not. Maybe Toby can say more on this?

    • CommentRowNumber4.
    • CommentAuthorMike Shulman
    • CommentTimeMar 22nd 2014

    The floor function is also not constructive, nor is deciding whether a number is zero or not.

    • CommentRowNumber5.
    • CommentAuthorTobyBartels
    • CommentTimeMar 23rd 2014

    It's not quite as crude as bifurcating into rational and irrational. For the reasons that Mike gives, we cannot constructively say that every real number has a continued fraction expansion. However, we can say more than that every rational number has one and that every irrational number has one.

    In general, a continued fraction (of the sort that we are considering here) is given by a stream of positive integers. If the stream is finite, then we have a rational number; if the stream is infinite, then we have an irrational number. A stream cannot be neither, but we can't say that it must be either.

    The characterization of the real line as a terminal coalgebra is characterizing the space of those real numbers with continued fraction expansions.

    • CommentRowNumber6.
    • CommentAuthorTobyBartels
    • CommentTimeMar 23rd 2014

    A stream that is not infinite need not be finite, but a stream that is not finite must be infinite. This means that a real number with a continued fraction expansion that is not rational must be irrational. This is an important property, because in general, a real number that is not rational need not be irrational. (Here I take the usual definition of an irrational number in constructive mathematics, that it be apart from every rational number. This is the definition that makes irrational numbers correspond precisely to infinite continued fractions.)

    • CommentRowNumber7.
    • CommentAuthorDavid_Corfield
    • CommentTimeMar 23rd 2014

    Any interest in this old post and subsequent comment?

    There’s a connection between continued fractions and rational tangles, which seems to complete to relate the reals to infinite tangles. Then there’s a representation of the behaviour of infinite multivariate weighted automaton as continued fractions.

    • CommentRowNumber8.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 23rd 2014

    Toby, would you consider adding some constructivist remarks as in #5 and #6?

    David: Yes, of course there’s interest! As far as concrete additions to the nLab go, at the very least there ought to be mention of rational tangles in the continued fraction article. And at least some of the articles you brought up could be referenced in the article. (I’d never considered, before your last comment, infinite knots such as appear in On Knots as having possible coalgebraic significance. The same would seem to apply to constructions like Alexander’s horned sphere. It’s curious to think of the Pythagorean discovery of irrational numbers as essentially an early piece of coalgebra, but there it is, and the same could be said of Alexander’s discovery I guess.)

    • CommentRowNumber9.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 23rd 2014

    I incorporated some of what David #7 was referring to into continued fraction, for example stating Conway’s theorem on rational tangles. But I don’t know whether it gets his idea across very well.

    • CommentRowNumber10.
    • CommentAuthorDavid_Corfield
    • CommentTimeMar 23rd 2014

    Thanks for that Todd. My brains are fried after a day of marking philosophy essays, so can’t think of anything very sensible. I suppose one would need to look for an unfolding operation on the collection of possibly infinite 2-tangles.

    As a reminder, if I have time, a Neighborhood of Infinity has a series of six posts on “Untangling with Continued Fractions”, 0 - 5. I think the idea is that you convert a rational tangle into a rational number, work out its continued fraction, which tells you how to untwist the tangle.

    • CommentRowNumber11.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 24th 2014

    Yes. I’ve been to at least one of Conway’s talks where he gets four volunteers, gives them two pieces of rope, and gets the audience to untangle a rational tangle by calling out a series of commands, “turn” or “twist”. It’s pretty easy if you’ve kept track of the rational number. Eventually, someone will call out “let’s twist again,” and Conway will quip, “like we did last summer?”

    • CommentRowNumber12.
    • CommentAuthorDavid_Corfield
    • CommentTimeMar 25th 2014

    So could untangling be done in a coalgebraic-unfolding way (I forget the language they use), where I don’t need to know the whole entity, or can’t know if it’s infinite, to get going?

    • CommentRowNumber13.
    • CommentAuthorTobyBartels
    • CommentTimeMar 29th 2014

    I put in some constructive commentary.

    • CommentRowNumber14.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 31st 2014

    Thank you, Toby!

    • CommentRowNumber15.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeApr 10th 2014
    • (edited Apr 10th 2014)

    I’ve been trying to better understand the correspondence between rational tangles and continued fractions, and I was wondering if someone here might be able to answer a question I’ve been stuck on. It should be possible to explain the correspondence by an interpretation of general tangles (including rational ones) in a particular tortile monoidal category, right? If so, what is the most natural place for this interpretation? TWF228 and 229 seem to get at something like this and probably have the answer to my question, but I don’t see how to extract a tortile monoidal category from that discussion.

    As an example of what I’m after, I think I do see a tortile monoidal category lurking in the proof of “the fraction through integral coloring” in the paper by Kauffman and Lambropoulou (section 5, starting p.34). They define criteria for producing a valid coloring of the arcs of a tangle by integers, so that given any coloring of a tangle with colors (nw,ne,sw,se)(nw,ne,sw,se) at the four corners, we have an identity nw+se=ne+swnw+se = ne+sw, and moreover for any rational tangle, the associated fraction ne−nwne−se\frac{ne-nw}{ne-se} is a topological invariant (equal to the Conway fraction; note this orientation of rational tangles is a quarter-turn away from the convention used in TWF22* and the nlab article).

    Well, now let’s suppose that we interpret coloring of a tangle TT as a relation T:Z×Z→Z×ZT : Z\times Z \to Z \times Z (where T(nw,ne,sw,se)T(nw,ne,sw,se) iff there is a valid coloring of TT with colors (nw,ne,sw,se)(nw,ne,sw,se) at the corners). The standard compact closed structure of RelRel gives the right definition of colorability for the 0 tangle and the ∞\infty tangle, namely 0(a,b,c,d)=[a=b]∧[c=d]0(a,b,c,d) = [a=b] \wedge [c=d] and ∞(a,b,c,d)=[a=c]∧[b=d]\infty(a,b,c,d) = [a=c] \wedge [b=d], as well as the right definition of colorability for tangle addition and rotation. But the usual symmetry in Rel is not the right notion of braiding for recovering the +1 and -1 tangles. So, let’s instead define a braiding of integer strands as follows:

    γ(a,b,c,d)=[b−a=d−c]∧[a=d]\gamma(a,b,c,d) = [b-a = d-c] \wedge [a=d]

    The inverse braiding is identical except with the clause [a=d][a=d] replaced by [b=c][b=c]. (I think it is helpful to see the associated string diagrams in Rel. For example, γ\gamma could be drawn as a multiplication (representing the functional relation Z×Z→ZZ \times Z \to Z of subtraction) followed by a comultiplication (the right adjoint of subtraction), together with an extra strand splitting off from the NW strand before the multiplication, and rejoining the SE strand after the comultiplication; γ −1\gamma^{-1} is identical, but with the extra strand running from NE to SW.) I haven’t checked all the details to verify that this gives a tortile monoidal category, but I’m pretty sure that’s right, and the resulting relations T:Z×Z→Z×ZT : Z \times Z \to Z \times Z do correspond to colorability à la Kauffman and Lambropoulou, and hence to the fraction by the above formula.

    So my questions are, 1. Does this make sense?, and 2. Is there a better choice of tortile monoidal category, such that the fraction is recovered in a more direct way?

    • CommentRowNumber16.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 10th 2014

    Noam, I haven’t read your comment carefully yet, but have you seen John’s recent comment at the Café?

    • CommentRowNumber17.
    • CommentAuthorJohn Baez
    • CommentTimeApr 10th 2014
    • (edited Apr 11th 2014)

    Hi! Todd pointed me to this thread. This relation γ:ℤ×ℤ→ℤ×ℤ\gamma : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z} given by

    γ(a,b,c,d)=[b−a=d−c]∧[a=d] \gamma (a,b,c,d) = [b-a=d-c] \wedge [a=d]

    happens to be a function, which we can write as

    γ(a,b)=(2a−b,a) \gamma (a,b) = (2a - b , a)

    I believe this is an instance of a common pattern where we have a set QQ and a function ⊳:Q×Q→Q\rhd: Q \times Q \to Q such that the function γ:Q×Q→Q×Q\gamma : Q \times Q \to Q \times Q given by

    γ(a,b)=(a⊳b,a) \gamma(a,b) = (a \rhd b, a)

    obeys the Yang-Baxter equation

    (γ×1)(1×γ)(γ×1)=(1×γ)(γ×1)(1×γ) (\gamma \times 1)(1 \times \gamma)(\gamma \times 1) = (1 \times \gamma)(\gamma \times 1)(1 \times \gamma)

    Whenever this happens, we get a way of making the category where objects are cartesian powers of QQ and morphisms are functions into a braided monoidal category where the braiding is γ\gamma. The equation

    (γ×1)(1×γ)(γ×1)=(1×γ)(γ×1)(1×γ) (\gamma \times 1)(1 \times \gamma)(\gamma \times 1) = (1 \times \gamma)(\gamma \times 1)(1 \times \gamma)

    can be translated into a nice little equation obeyed by ⊳\rhd, which is the main law governing a “rack”: it says the operation ⊳\rhd distributes over itself! (The link explains this, but you can read tons more in Alissa Crans’ thesis: check out the stuff about shelves, racks, and braided monoidal categories.)

    Note that our particular map ⊳\rhd:

    a⊳b=2a−b a \rhd b = 2a - b

    is the result of taking the reflection of ℤ\mathbb{Z} that fixes aa, and applying it to bb. The fact that this makes ℤ\mathbb{Z} into a rack thus follows from a general pattern where whenever you have a symmetric space, algebraically defined as a space where you can “reflect bb across aa” to get a⊳ba \rhd b in a way obeying some reasonable axioms, you get a rack. And since a⊳a=aa \rhd a = a in this context, our rack will be the specially nice kind called a “quandle”. In fact it seems to be a special case of the “Alexander quandle” explained here.

    Of course, to add “caps” and “cups” to our braided monoidal category and make it compact closed (probably even tortile), we need to use relations rather than functions.

    Since this math involves continued fractions, the Alexander quandle, the homomorphism from the 3-strand braid group to PSL(2,ℤ)PSL(2,\mathbb{Z}) and more, I think something nice is shaping up here. In fact, it’s so nice that a lot of it is probably known! But I suspect it all fits together much more neatly than I’ve ever seen in what I’ve read…

    • CommentRowNumber18.
    • CommentAuthorJohn Baez
    • CommentTimeApr 11th 2014
    • (edited Apr 11th 2014)

    Somehow I think it’s relevant that we get PSL 2(ℤ)PSL_2(\mathbb{Z}) by taking the 3-strand braid group B 3B_3 and modding out by its center, which is generated by the “full twist”

    (B⊗1)(1⊗B)(B⊗1)(1⊗B)(B⊗1)(1⊗B) (B \otimes 1)(1 \otimes B) (B \otimes 1)(1 \otimes B) (B \otimes 1)(1 \otimes B)

    where B⊗1B \otimes 1 and 1⊗B1 \otimes B are the two standard generators of B 3B_3. This makes me want to look at the free tortile monoidal category on one generator xx, namely the category of framed tangles, and mod it out by imposing the relation

    (B x,x⊗1)(1⊗B x,x)(B x,x⊗1)(1⊗B x,x)(B x,x⊗1)(1⊗B x,x)=1 x⊗x (B_{x,x} \otimes 1)(1 \otimes B_{x,x})(B_{x,x} \otimes 1)(1 \otimes B_{x,x}) (B_{x,x} \otimes 1)(1 \otimes B_{x,x}) = 1_{x \otimes x}

    This might be the elegant tortile monoidal category Noam is looking for.

    • CommentRowNumber19.
    • CommentAuthorDavidRoberts
    • CommentTimeApr 11th 2014

    @John #18

    This might be the elegant tortile monoidal category Noam is looking for.

    I’m guessing here that ’elegant’ is not a mathematical adjective? (compare wonderful compactification)

  20. Thank you, John (and Todd!), your comments and the links are very helpful.

    Following the Wikipedia article I landed on a paper on “Biquandles and virtual links” by Fenn, Jordan-Santana, and Kauffman (from 2004, the same year as Kauffman and Lambropoulou), and though I haven’t had time to read it very carefully, it seems to be based precisely on this connection. The γ\gamma above indeed corresponds exactly to a special case of what they call the “Alexander switch” (which is also a birack and a biquandle).

  21. I just learned that relative to a fixed modulus nn, the quandle operation a⊳b=2a−b(modn)a \rhd b = 2a - b\,(mod\,n) (or perhaps 2b−a2b-a) is known as the “dihedral quandle”, and gives rise to the classical notion of n-colorability of a knot. There is also a more general notion of coloring by an arbitrary quandle (Q,⊳)(Q,\rhd), and for a given QQ the cardinality of the set of QQ-colorings is a knot invariant. I’m interested in how this relates to knot polynomials, e.g., how does coloring by the Alexander quandle relate to the Alexander polynomial? Is it a matter of interpreting in FinVect rather than in Rel?

    • CommentRowNumber22.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeApr 18th 2014
    • (edited Apr 18th 2014)

    Here are some more half-baked thoughts about the correspondence rational tangles ↔\leftrightarrow extended rationals, just in case it sparks any ideas. K & L prove that any tangle can be brought into “standard form”, meaning that it can be constructed using only positive/negative twisting only on the right and at the bottom, starting from the tangle [0][0] or [∞][\infty]. Note that performing nn positive twists on the right (following their conventions) corresponds to the arithmetic operation q↦q+nq \mapsto q + n, while performing nn positive twists at the bottom corresponds to q↦11q+nq \mapsto \frac{1}{\frac{1}{q} + n}, so that given a tangle in standard form, it’s easy to read off the continued fraction representation (in reverse, starting from the bottom right). I’ve been trying to make sense of this in fibrational terms, based on the idea of interpreting the twisting operations as taking the pushforward/pullback of a tangle (rational) along a 2-strand braid (integer).

    To make things more focused, let’s restrict attention to non-negative rationals/tangles. Let ℕ\mathbb{N} be the monoid of natural numbers seen as a one-object category, and now define a category ℚ [0,∞)\mathbb{Q}_{[0,\infty)} whose objects are non-negative (finite) rational numbers, and where there is a morphism p→qp \to q just in case there exists a natural nn such that n+p=qn + p = q. There is an evident forgetful functor ℚ [0,∞)→ℕ\mathbb{Q}_{[0,\infty)} \to \mathbb{N}, which is also an opfibration: for any non-negative rational pp and natural number nn, the pushforward [n]p[n]p of pp along nn is defined by [n]p=n+p[n]p = n+p. Similarly, let’s define another category ℚ (0,∞]\mathbb{Q}_{(0,\infty]} whose objects are extended positive rational numbers, and where there is a morphism s→ts \to t just in case there exists a natural nn such that s=1n+1ts = \frac{1}{n + \frac{1}{t}}. Again, there is an evident forgetul functor ℚ (0,∞]→ℕ\mathbb{Q}_{(0,\infty]} \to \mathbb{N}, which is now a fibration: for any extended positive rational tt and natural number nn, the pullback [n] *t[n]^* t of tt along nn is defined as [n] *t=1n+1t[n]^*t = \frac{1}{n + \frac{1}{t}}. Note that in both categories of rationals, if p→qp \to q or s→ts \to t then p≤qp \le q and s≤ts \le t.

    Now, here are a couple of observations:

    • Taking reciprocals defines a contravariant adjunction between ℚ [0,∞)\mathbb{Q}_{[0,\infty)} and ℚ (0,∞]\mathbb{Q}_{(0,\infty]}, which sends pushforwards to pullbacks and vice versa.
    • With slight abuse of notation, we can build up the continued fraction/standard form of a rational/tangle by successive pushforward and pullback, starting from either 0 or ∞\infty. For example, 1611=1+12+15\frac{16}{11} = 1 + \frac{1}{2 + \frac{1}{5}} may be represented as [1][2] *[5]0[1][2]^*[5]0. I say “abuse of notation”, because here I am silently shifting the interpretation of the objects between the two categories of rationals, and I’m not exactly sure what justifies that formally.

  23. I have another small question about the article. Theorem 4 says that the positive extended rationals Q=(ℚ∩[1,∞])+{∞}\mathbf{Q} = (\mathbb{Q} \cap [1,\infty]) + \{\infty\} form the carrier of an initial algebra for the functor F(X)=1+X×ℕ +F(X) = 1 + X \times \mathbb{N}_+, and the proof sketched says to “invoke an algebra isomorphism (ℕ +) *→ℚ(\mathbb{N}_+)^* \to \mathbb{Q} which sends a word to the rational represented by the continued fraction [a 0,a 1,…,a n][a_0,a_1,\dots,a_n]”. But is this really an isomorphism? As the Wikipedia article says, “every rational number can be represented in precisely two different ways as a finite continued fraction”. For example, 2.25 is represented by both [2;4] and [2;3,1], although 24 and 231 are two different words in (ℕ +) *(\mathbb{N}_+)^*. Is there something that I’m missing?

    • CommentRowNumber24.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 23rd 2014

    Hm, good point Noam. Let me think on this and see if something can be salvaged.

    • CommentRowNumber25.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 23rd 2014
    • (edited Apr 23rd 2014)

    Thanks again, Noam, for bringing this (#23) to attention. Maybe let me try thinking out loud here for a moment. I’d be grateful if someone gave this a sanity check.

    Besides regular continued fractions, there’s another type of continued fraction which is worth considering every now and then. It’s where we have

    a 1−1/(a 2−1/(a 3−1/...a_1 - 1/(a_2 - 1/(a_3 - 1/...

    where the algorithm is: print the ceiling (not the floor), subtract the ceiling followed by taking the negative reciprocal; this generates a behavior stream of ceilings. We will apply this to the set of reals greater than 11 (including ∞\infty as a real). On input an integer, the output is ∞\infty (meaning the algorithm halts after printing the ceiling). Otherwise, when we subtract the ceiling we get something in the open interval (−1,0)(-1, 0) whose negative reciprocal is in (1,∞)(1, \infty); the ceiling of that output will be 22 or greater. So the behavior stream (a 1,a 2,…)(a_1, a_2, \ldots) consists of integers ≥2\geq 2. A variant of the Euclidean algorithm shows that the behavior stream of a number is finite iff the number is rational (or ∞\infty).

    For the moment, let me call this the “antiregular continued fraction”. Notice it’s more closely connected with PSL 2(ℤ)PSL_2(\mathbb{Z}) than the regular continued fraction, since after all z↦−1/zz \mapsto -1/z is a fractional linear transformation corresponding to an element of PSL 2(ℤ)PSL_2(\mathbb{Z}), whereas z↦1/zz \mapsto 1/z is not.

    Another virtue is that subtraction z↦z−nz \mapsto z - n and negative reciprocal z↦−1/zz \mapsto -1/z are both strictly increasing functions. The import is this: to see which of two antiregular continued fraction representations of real numbers is greater (as a real number), use the lexicographic order on infinite sequences. (If the stream is finite, just append a tail of ∞\infty’s to it.) Actually, this doesn’t quite work, because we have for example two antiregular continued fractions for the number 22: both (2,∞,∞,∞,…)(2, \infty, \infty, \infty, \ldots) and (3,2,2,2,…)(3, 2, 2, 2, \ldots). But: it should work for any two sequences that terminate in a tail of ∞\infty’s. Is that right?

    Let SS be the set of real numbers greater than 11 (including ∞\infty). Let FF be the endofunctor on sets defined by F(X)=1+ℕ×XF(X) = 1 + \mathbb{N} \times X. Then SS has an FF-coalgebra structure α:S→F(S)\alpha: S \to F(S) given by α(∞)=*∈1\alpha(\infty) = \ast \in 1, else α(s)=⟨ceil(s),−1/(s−ceil(s))⟩\alpha(s) = \langle ceil(s), -1/(s - ceil(s))\rangle.

    Let TT be the set of rational numbers greater than 11 (including ∞\infty). Then TT acquires an FF-coalgebra structure in a unique way if we specify that the inclusion i:T→Si: T \to S is to be a coalgebra map.

    Conjecture: the coalgebra structure T→F(T)T \to F(T) is invertible, and its inverse F(T)→TF(T) \to T realizes TT as the initial FF-algebra.

    • CommentRowNumber26.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeApr 24th 2014
    • (edited Apr 24th 2014)

    What you wrote sounds right to me, but here are some more thoughts:

    • Any finite antiregular continued fraction (a 1,…,a n)(a_1,\dots,a_n) can be read "inside-out" and reconstructed as a rational tangle, by repeatedly applying the turn and (positive) twist operations starting at the ∞\infty tangle. Formally, writing τ(z)=−1/z\tau(z) = -1/z for the negative reciprocal operation and σ(z)=1+z\sigma(z) = 1+z for successor, we have a (trivial) identity a 1−1/(a 2−1/(…−1/a n)…)=σ a 1τσ a 2⋯τσ a nτ∞a_1 - 1/(a_2 - 1/(\dots - 1/a_n)\dots) = \sigma^{a_1}\tau\sigma^{a_2}\cdots\tau\sigma^{a_n}\tau\infty. Now, we already know that starting from ∞\infty, repeatedly applying the operations τ\tau and σ\sigma will eventually enumerate all extended rational numbers, but with some double-counting (e.g., στστ∞=τ∞\sigma\tau\sigma\tau\infty = \tau\infty). The argument you gave says that restricting to block operations of the form σ aτ\sigma^a\tau for a≥2a \ge 2 suffices to enumerate all extended rationals greater than 1, without any double-counting.

    • Today I was asking about implementations of continued fractions in Coq, and pointed to the library described in this paper, which as it turns out is based on the Stern-Brocot tree 1-1 enumeration of the rationals in the interval (0,∞)(0,\infty). Then I realized that the closely-related Calkin-Wilf tree is exactly the enumeration of positive rational tangles you get by starting at the 1 tangle and generating tangles in "twist form", i.e., by repeatedly applying either right twists σ(z)=1+z\sigma(z) = 1 + z or bottom twists γ(z)=1/(1+1/z)\gamma(z) = 1/(1 + 1/z). So, this seems to give another algebraic characterization of the positive rationals: as an initial object in the category of pointed modules for the free monoid on two generators {γ,σ}\{\gamma,\sigma\}.

    • CommentRowNumber27.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 25th 2014

    Noam, thanks. Your first thought was actually what I had in mind as well. I don’t quite understand the last sentence of your second thought; aren’t σ\sigma and γ\gamma algebraically related?

    I made the necessary corrections at continued fraction (replacing what had been “theorem 1”, that was incorrect essentially by your #23, by a remark, and referring also to the work of Pavlovic-Pratt for a reasonable surrogate that replaces the false claim.

    • CommentRowNumber28.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeApr 25th 2014
    • (edited Apr 25th 2014)

    Re: your question whether σ\sigma and γ\gamma are algebraically related, since the Calkin-Wilf tree is a tree rather than a graph, the answer must be no. Actually, maybe it helps to think back on John’s original suggestion, since any sequence of right and bottom twists on a tangle can be interpreted directly as an element of the 3-strand braid group (the strand at the northwest corner of the tangle is left fixed). But under this interpretation, σ\sigma and γ\gamma do not correspond to a pair of positive or pair of negative twists (which would be subject to the relation σγσ=γσγ\sigma\gamma\sigma = \gamma\sigma\gamma), but rather to a pair of opposite-polarity twists. Indeed, letting σ −1(z)=z−1\sigma^{-1}(z) = z - 1 and γ −1(z)=1/(1/z−1)\gamma^{-1}(z) = 1/(1/z - 1), you can verify that σγ −1σ=γ −1σγ −1\sigma\gamma^{-1}\sigma = \gamma^{-1}\sigma\gamma^{-1} and σ −1γσ −1=γσ −1γ\sigma^{-1}\gamma\sigma^{-1} = \gamma\sigma^{-1}\gamma.

    I am claiming that there is an embedding of the free monoid on two generators in the 3-strand braid group. Is that a well-known fact? Actually, it seems it is: see the second-to-last bullet point here.

    Admitting that MM is the free monoid on two generators γ\gamma and σ\sigma, I believe that the right way of describing the positive rationals is as an initial object in the category of pointed MM-modules. Given any other MM-module XX with a point x∈Xx \in X, there is a unique module homomorphism ℚ +→X\mathbb{Q}^+ \to X sending 1 to xx, defined as follows: for any positive rational qq, locate qq on the Calkin-Wilf tree, and then retrace the path from 1 to qq in XX, beginning at xx and applying the actions γ\gamma and σ\sigma as appropriate.

    • CommentRowNumber29.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 25th 2014

    Oh, I see my mistake: I was considering the group generated by those elements, not the monoid.

  30. I went ahead and added some material on the Calkin-Wilf tree to the article.

    • CommentRowNumber31.
    • CommentAuthorTodd_Trimble
    • CommentTimeApr 27th 2014

    Thanks!

    • CommentRowNumber32.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeApr 29th 2014
    • (edited Apr 29th 2014)

    I think that now I can correctly formulate what I was trying to get at in #22, following the observation that the set of positive rationals may be universally characterized as a pointed module for the free monoid on two elements (MM). I’ll sketch it out here, but perhaps it would be worthwhile to write this up somewhere (perhaps in a separate article?).

    First, note that with just a bit more work we can get the extended non-negative rationals ℚ [0,∞]\mathbb{Q}_{[0,\infty]} as an MM-module with a pair of points 00 and ∞\infty, subject to the relations

    R(∞) =∞ L(0) =0 R(0) =L(∞) \begin{aligned} R(\infty) &= \infty \\ L(0) &= 0 \\ R(0) &= L(\infty) \end{aligned}

    Now, this recovers the set of extended non-negative rationals, but says nothing about the ordering. However, since there is an ordering of the rationals implicit in the Calkin-Wilf tree (namely, the Stern-Brocot tree), it’s natural to ask for a categorical formulation that reflects this.

    Well, classically, a module for a monoid MM is the same thing as a discrete opfibration (or equally well a discrete fibration) over MM seen as a one-object category. So, the idea is to drop discreteness and view the extended rationals as a special kind of functor ℚ [0,∞]→M\mathbb{Q}_{[0,\infty]} \to M. Observing that for all q∈[0,∞]q \in [0,\infty] we have q≤1+q=R(q)q \le 1 + q = R(q) and L(q)=11+1q≤qL(q) = \frac{1}{1 + \frac{1}{q}} \le q (with strict inequalities respectively when q<∞q \lt \infty and q>0q \gt 0), we place the following conditions on ℚ [0,∞]\mathbb{Q}_{[0,\infty]} and the functor ℚ [0,∞]→M\mathbb{Q}_{[0,\infty]} \to M:

    • ℚ [0,∞]\mathbb{Q}_{[0,\infty]} is equipped with a pair of objects 00 and ∞\infty, both mapped to the (unique) object ** of MM
    • every object qq lying in the fiber over ** is equipped with a pushforward along R:*→*R : * \to *, and a pullback along L:*→*L : * \to *, written R +[q]R^+[q] and L *[q]L^*[q] respectively
    • the pushforward of ∞\infty along RR is ∞\infty, the pullback of 00 along LL is 00, and the pushforward of 0 along RR is the pullback of LL along ∞\infty, i.e., we have vertical isomorphisms
    R +[∞] =∞ L *[0] =0 R +[0] =L *[∞] \begin{aligned} R^+[\infty] &= \infty \\ L^*[0] &= 0 \\ R^+[0] &= L^*[\infty] \\ \end{aligned}

    I claim that taking ℚ [0,∞]→M\mathbb{Q}_{[0,\infty]} \to M as freely generated (in an appropriate sense) with this structure is enough to recover the ordered extended non-negative rationals, i.e., that the objects of ℚ [0,∞]\mathbb{Q}_{[0,\infty]} correspond to extended non-negative rationals, and that there exists a morphism q 1→q 2q_1 \to q_2 in ℚ [0,∞]\mathbb{Q}_{[0,\infty]} if and only if q 1≤q 2q_1 \le q_2. For the first part, as before we just use the Calkin-Wilf/Stern-Brocot encoding of continued fractions, i.e., if qq has the continued fraction decomposition q=[a 0,…,a n]q = [a_0,\dots,a_n] (assume wlog nn is odd) the corresponding object is q=R +a 0L *a 1…R +a n−1L *a n[∞]q = R^{+a_0}L^{*a_1}\dots R^{+a_{n-1}}L^{*a_n}[\infty]. For the second part, we show that the properties of pullbacks/pushforwards together with the postulated equalities are enough to recover the correct rules for comparing continued fractions (as coded in the Stern-Brocot tree, this is essentially just a lexicographic comparison of the corresponding strings of LLs and RRs).

  33. no, this (#32) doesn’t actually work. Anyways, I think there are more interesting things to say about the CW tree (which I’ve learned is also related to “Raney’s binary encoding” of continued fractions), but maybe it’s better I don’t tax people’s mental resources here until I have something more concrete written up.

1 to 33 of 33

  1.