# Order rational numbers by 'complexity'?

I don’t know if I’m inventing the wheel, but I devised a quick way to order the “complexity” of rational numbers because it made sense in a specific context I was working on. It seems like it makes sense, but at the same time, maybe I’m doing something very wrong, or it’s a well-known procedure that I ignore. I’d be glad if anyone wants to take a look, comment, or even point me to another way to do this. I’m sure many did something similar before, but I just don’t know.

The code calculates a rational number’s “complexity” (for the lack of a better word) or “simplicity” to sort a list of rationals. It is calculated based on the number of terms (continued fractions), the average coefficient size, and whether the continued fraction representation of the number has a repeating pattern or not (two numbers and a boolean). I use those three measures to compare and generate an ordering type for rationals.

1 Like

There are sets of rational numbers that are ranked identically by this scheme. For example 7/3 has continued fraction [2; 3] and 7/2 has continued fraction [3; 2]. They have the same number of terms, average coefficient, and neither has a repetition. As a result, this ranking doesn’t qualify as a total order. I think the correct term here would be “weak order.” I don’t know whether meeting the strict definition of an order is a concern for you, but I thought it’s worth mentioning.

The concept of assigning a “score” to a rational number is common in the microtonal community for scoring the complexity of a JI ratio. These are known as height functions: Height - Xenharmonic Wiki They’re not total orders either, since multiple rationals may have the same height.

To get a bit cheeky, the rational numbers already have a total order, it’s just the ordinary less-than-or-equal operator, which fits all the criteria of a total order. A true discrete ranking would entail a bijection between the rational numbers and the positive integers. There’s many ways to do this (eg place all possible x/y on a 2D grid and spiral around, skipping over any fractions not in lowest terms), but I’m also not sure what the application is here to be honest.

2 Likes

Reading the link, I think you mean strict total order, right? Yes, I thought that people in the JI community would have done something equivalent, but I didn’t know where to look. The practical application includes rhythmic stuff.

1 Like

Your relation is missing the antisymmetric property (3/2 R 2/3, 3/2 R 2/3 are both true, but 2/3 != 3/2), so it doesn’t define a strict or non-strict total order on rationals, only on these int-rational-bool triples.

1 Like

Yes, but isn’t it the nature of continued fraction representation, since it’s not always possible to exactly reconstruct the original number? I did some tests and it seems not possible. It seems it can be helpful in a loose way, since the quality itself it is measuring is difficult to define.

Maybe it can be improved if it considers another aspect of the rational number to compare.

1 Like

It’s possible to define total orders over the rationals, including total orders isomorphic to the ordering of the natural numbers, but it all depends on what you want to accomplish. If the goals here are artistic, then I’d suggest starting with something like the Benedetti height H(n/d) = nd, and only add complication if there’s a specific reason to do so.

1 Like

Thank you. I will check it out. I just don’t understand why my short snippet would add complication comparing to another method.

1 Like

Yea, I think Benedetti Height can be very good option for many things. (although the implementation was a bit complicatedf too )

1 Like

It’s not complicated at all. Benedetti height is just the numerator times the denominator of the ratio.

1 Like

Neither was the other code. I was just kidding, nathan

(it appears complicated because I read the link you mentioned, and also implemented the “Monzo” and the vector form. that’s is)

Thank you for mentioning it, you were helpful. Thanks

1 Like

I did not know about the Benedetti height, but it seems to be similar to a positive definite cosine similarity applied to natural numbers a,b which could be the numerator and denominator of a rational number:

k(a,b) := gcd(a,b)^2/(a*b)

Since it is a positive definite kernel, it means that you can do Cholesky decomposition on a Gram matrix if you wanted to measure the similarities between two numbers a,b : 0 < k(a,b) <= 1, where 1 means identical, and near 0 means very different.
I should mention that I have used this to define the simplicity of a ratio and so to measure consonance in two pitches in Western music:

So basically it is a mapping from pitches to a vector space, where we associate to each pitch in music a vector in such a way, that two pitches which sound consonant when played together are more similar ( have a larger inner product k(a,b) then two pitches with a lower inner product which should sound more dissonant.)

Here is a piece for piano which has been done with the method described above:

2 Likes

The k function is identical to the reciprocal of the Benedetti height because in H(n/d) it’s assumed that gcd(n,d) = 1. The Benedetti height is maybe a little too simple for its own good as a “consonance” model, for example 4/1 is considered less consonant than 3/1, but it looks like you’re doing octave reduction so it’s not a problem in your case.

I confess I don’t really see the relationship with inner product spaces, as I don’t see how this satisfies the definition of an inner product, as it isn’t linear in either argument. Is the underlying vector space the sequence of exponents in the prime factorization or something? Even if so, I can’t see how k can work as an inner product.

1 Like

Thanks for your explanation. I noticed that it is the inverse of the Benedetti height in this case.
The function k(a,b) = gcd(a,b)^2/(ab) is positive definite over the natural numbers, which means, that if you consider the Gram matrix G_n = (k(i,j))_{1 <= i,j <= n} of pairwise k(i,j), it will be positive definite and this means one can do the Cholesky decomposition on this matrix to get the feature vector phi(i) for each natural number \$i\$: You might want to look here ( nt.number theory - A geometric proof that there are infinitely many primes? - MathOverflow ) for a direct definition of the feature vector phi, which does not use the Cholesky decomposition : < phi(a) , phi(b) > = k(a,b) = gcd(a,b)^2 / (ab).

1 Like

You might be interested in Euler’s Gradus Suavitatus function, which attempts to score consonance of rational numbers. (See for example Gradus Suavitatis, Music and Mathematics)

4 Likes