Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Wrote continued fraction, emphasizing coalgebraic aspects. More links should be inserted, and some more material needs to be filled in.
Very nice! What does the constructive theory of continued fractions look like?
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?
The floor function is also not constructive, nor is deciding whether a number is zero or not.
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.
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.)
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.
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.)
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.
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.
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?”
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?
I put in some constructive commentary.
Thank you, Toby!
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)$ at the four corners, we have an identity $nw+se = ne+sw$, and moreover for any rational tangle, the associated fraction $\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 $T$ as a relation $T : Z\times Z \to Z \times Z$ (where $T(nw,ne,sw,se)$ iff there is a valid coloring of $T$ with colors $(nw,ne,sw,se)$ at the corners). The standard compact closed structure of $Rel$ gives the right definition of colorability for the 0 tangle and the $\infty$ tangle, namely $0(a,b,c,d) = [a=b] \wedge [c=d]$ and $\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:
$\gamma(a,b,c,d) = [b-a = d-c] \wedge [a=d]$The inverse braiding is identical except with the clause $[a=d]$ replaced by $[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 \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; $\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 \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?
Noam, I haven’t read your comment carefully yet, but have you seen John’s recent comment at the Café?
Hi! Todd pointed me to this thread. This relation $\gamma : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}$ given by
$\gamma (a,b,c,d) = [b-a=d-c] \wedge [a=d]$happens to be a function, which we can write as
$\gamma (a,b) = (2a - b , a)$I believe this is an instance of a common pattern where we have a set $Q$ and a function $\rhd: Q \times Q \to Q$ such that the function $\gamma : Q \times Q \to Q \times Q$ given by
$\gamma(a,b) = (a \rhd b, a)$obeys the Yang-Baxter equation
$(\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 $Q$ and morphisms are functions into a braided monoidal category where the braiding is $\gamma$. The equation
$(\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 \rhd b = 2a - b$is the result of taking the reflection of $\mathbb{Z}$ that fixes $a$, and applying it to $b$. 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 $b$ across $a$” to get $a \rhd b$ in a way obeying some reasonable axioms, you get a rack. And since $a \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,\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…
Somehow I think it’s relevant that we get $PSL_2(\mathbb{Z})$ by taking the 3-strand braid group $B_3$ and modding out by its center, which is generated by the “full twist”
$(B \otimes 1)(1 \otimes B) (B \otimes 1)(1 \otimes B) (B \otimes 1)(1 \otimes B)$where $B \otimes 1$ and $1 \otimes B$ are the two standard generators of $B_3$. This makes me want to look at the free tortile monoidal category on one generator $x$, namely the category of framed tangles, and mod it out by imposing the relation
$(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.
@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)
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).
I just learned that relative to a fixed modulus $n$, the quandle operation $a \rhd b = 2a - b\,(mod\,n)$ (or perhaps $2b-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,\rhd)$, and for a given $Q$ the cardinality of the set of $Q$-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?
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]$ or $[\infty]$. Note that performing $n$ positive twists on the right (following their conventions) corresponds to the arithmetic operation $q \mapsto q + n$, while performing $n$ positive twists at the bottom corresponds to $q \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 $\mathbb{Q}_{[0,\infty)}$ whose objects are non-negative (finite) rational numbers, and where there is a morphism $p \to q$ just in case there exists a natural $n$ such that $n + p = q$. There is an evident forgetful functor $\mathbb{Q}_{[0,\infty)} \to \mathbb{N}$, which is also an opfibration: for any non-negative rational $p$ and natural number $n$, the pushforward $[n]p$ of $p$ along $n$ is defined by $[n]p = n+p$. Similarly, let’s define another category $\mathbb{Q}_{(0,\infty]}$ whose objects are extended positive rational numbers, and where there is a morphism $s \to t$ just in case there exists a natural $n$ such that $s = \frac{1}{n + \frac{1}{t}}$. Again, there is an evident forgetul functor $\mathbb{Q}_{(0,\infty]} \to \mathbb{N}$, which is now a fibration: for any extended positive rational $t$ and natural number $n$, the pullback $[n]^* t$ of $t$ along $n$ is defined as $[n]^*t = \frac{1}{n + \frac{1}{t}}$. Note that in both categories of rationals, if $p \to q$ or $s \to t$ then $p \le q$ and $s \le t$.
Now, here are a couple of observations:
I have another small question about the article. Theorem 4 says that the positive extended rationals $\mathbf{Q} = (\mathbb{Q} \cap [1,\infty]) + \{\infty\}$ form the carrier of an initial algebra for the functor $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,\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?
Hm, good point Noam. Let me think on this and see if something can be salvaged.
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/...$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 $1$ (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)$ whose negative reciprocal is in $(1, \infty)$; the ceiling of that output will be $2$ or greater. So the behavior stream $(a_1, a_2, \ldots)$ consists of integers $\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(\mathbb{Z})$ than the regular continued fraction, since after all $z \mapsto -1/z$ is a fractional linear transformation corresponding to an element of $PSL_2(\mathbb{Z})$, whereas $z \mapsto 1/z$ is not.
Another virtue is that subtraction $z \mapsto z - n$ and negative reciprocal $z \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 $2$: both $(2, \infty, \infty, \infty, \ldots)$ and $(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 $S$ be the set of real numbers greater than $1$ (including $\infty$). Let $F$ be the endofunctor on sets defined by $F(X) = 1 + \mathbb{N} \times X$. Then $S$ has an $F$-coalgebra structure $\alpha: S \to F(S)$ given by $\alpha(\infty) = \ast \in 1$, else $\alpha(s) = \langle ceil(s), -1/(s - ceil(s))\rangle$.
Let $T$ be the set of rational numbers greater than $1$ (including $\infty$). Then $T$ acquires an $F$-coalgebra structure in a unique way if we specify that the inclusion $i: T \to S$ is to be a coalgebra map.
Conjecture: the coalgebra structure $T \to F(T)$ is invertible, and its inverse $F(T) \to T$ realizes $T$ as the initial $F$-algebra.
What you wrote sounds right to me, but here are some more thoughts:
Any finite antiregular continued fraction $(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 $\tau(z) = -1/z$ for the negative reciprocal operation and $\sigma(z) = 1+z$ for successor, we have a (trivial) identity $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 $\sigma^a\tau$ for $a \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,\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 $\sigma(z) = 1 + z$ or bottom twists $\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\}$.
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.
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 $\sigma^{-1}(z) = z - 1$ and $\gamma^{-1}(z) = 1/(1/z - 1)$, you can verify that $\sigma\gamma^{-1}\sigma = \gamma^{-1}\sigma\gamma^{-1}$ and $\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 $M$ 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 $M$-modules. Given any other $M$-module $X$ with a point $x \in X$, there is a unique module homomorphism $\mathbb{Q}^+ \to X$ sending 1 to $x$, defined as follows: for any positive rational $q$, locate $q$ on the Calkin-Wilf tree, and then retrace the path from 1 to $q$ in $X$, beginning at $x$ and applying the actions $\gamma$ and $\sigma$ as appropriate.
Oh, I see my mistake: I was considering the group generated by those elements, not the monoid.
I went ahead and added some material on the Calkin-Wilf tree to the article.
Thanks!
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 ($M$). 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 $\mathbb{Q}_{[0,\infty]}$ as an $M$-module with a pair of points $0$ and $\infty$, subject to the relations
$\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 $M$ is the same thing as a discrete opfibration (or equally well a discrete fibration) over $M$ seen as a one-object category. So, the idea is to drop discreteness and view the extended rationals as a special kind of functor $\mathbb{Q}_{[0,\infty]} \to M$. Observing that for all $q \in [0,\infty]$ we have $q \le 1 + q = R(q)$ and $L(q) = \frac{1}{1 + \frac{1}{q}} \le q$ (with strict inequalities respectively when $q \lt \infty$ and $q \gt 0$), we place the following conditions on $\mathbb{Q}_{[0,\infty]}$ and the functor $\mathbb{Q}_{[0,\infty]} \to M$:
I claim that taking $\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 $\mathbb{Q}_{[0,\infty]}$ correspond to extended non-negative rationals, and that there exists a morphism $q_1 \to q_2$ in $\mathbb{Q}_{[0,\infty]}$ if and only if $q_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 $q$ has the continued fraction decomposition $q = [a_0,\dots,a_n]$ (assume wlog $n$ is odd) the corresponding object is $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 $L$s and $R$s).
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