1
$\begingroup$

Suppose we have a fraction $\frac{A}{B}$ and want to find a (possibly different) way $\frac{a}{b}$ of writing the same fraction, where $a$ and $b$ are as small as possible.

In primary school we learn a very simple algorithm for doing this: look for some common divisor $d$ of $A$ and $B$, replace $A$ and $B$ with $A':= A/d$ and $B':= B/d$. Now obviously $A'/B'= A/B$ and $A' \leq A, B' \leq B$ so we made progress! Finding a new common divisor $d'$ of $A'$ and $B'$ we can repeat the process and we keep repeating until no common divisor can be found anymore.

Now that we are all older and wiser it is time to ask the question:

Why does this work?

How do we know that we do not get trapped in some 'local minimum' where we do have an expression $a/b$ for our fraction where $a$ and $b$ have no common divisors (except for 1) but there are still some $a' < a$ and $b' < b$ out there with $a/b = a'/b'$?!?

Probably your first reflex is 'Doesn't this follow from Unique Factorisation?' and the answer is 'yes it does'. (I'll provide a proof at the end of this post for completeness.)

Even something much more interesting is true: it is equivalent to unique factorization! We can deduce the Fundamental Theorem of Arithmetic from the fact that this greedy approach works. (Again I'll give the argument at the end of this post.)

Since the FT of A is highly non-trivial this gives an incentive to find a proof that the algorithm does indeed find the simplest form of any fraction that does not rely on unique factorization but instead only uses properties of fractions, and indeed such a proof can be found (I'll provide one at the end of this post).

Now with 2 proofs in my pocket, it seems a bit silly to come here and ask for a third, but yet here I am.

What I am really asking you is:

Is there a matroid or greedoid structure on pairs of numbers that explains the success of the greedy algorithm for simplifying fractions?

You read sometimes that matroids and later greedoids were invented to explain when greedy algorithms work, and I want to see how they do that in this very particular case.

An answer might either reveal an underlying structure in one of the two proofs below that I didn't spot or provide an entirely new third proof. Both would make me really happy.

EDIT: It was pointed out in the comment that this is not a greedy algorithm (which at least locally tries to make the best choice) but an even more stupid algorithm that doesn't even locally care about the choices it makes.

Of course this makes it even more remarkable that it arrives at the correct answer without getting trapped in a local minimum, but it makes it less likely that matroids are what is behind this. I feel that I understand the number theory side of 'why this works' well enough (see below) but I want to understand it more from an 'algorithm perspective'.

So my question should be generalized to this:

Can this example of a stupid 'do whatever you want'-algorithm that by a Brussels sprouts-like magic always arrives at the right answer be placed in a more general context/theory of similar stupid-but-succesful algorithms?


Appendix: proofs of the claims above.

We want to give two proofs of

Theorem A: The algorithm works

and show that in turn it implies the Fundamental Theorem of Arithmetic.

However we will first translate Theorem A into a more readable form.

All we know a priori is that if the algorithm stops at some expression $a/b$ then $a$ and $b$ are co-prime. The goal is to find the smallest $a$ and $b$ such that $a/b = A/B$. Thus the claim 'the algorithm works' translates to

Theorem B: If $a$ and $b$ are coprime and $a/b = A/B$ then $a$ and $b$ are the smallest numbers for which $a/b$ equals $A/B$.

Now an immediate consequence of theorem B is:

Theorem C: The set of expressions $a/b$ such that $a$ and $b$ are coprime and $a/b = A/B$ consist of a single, unique element.

However, Theorem C also implies Theorem B because the smallest numbers $a$ and $b$ such that $a/b = A/B$ must be coprime since otherwise the greedy algorithm would yield a smaller pair. So theorems A, B and C are equivalent.

Now the algorithm yields some room for choices. An immediate weakening of Theorem A ('no matter what we choose, the algorithm will always find the smallest $a$ and $b$ if we run it to the end') is the claim 'at least some of the choices of divisors we can make in the algorithm will yield the smallest $a$ and $b$'. This latter claim is equivalent to:

Theorem D: Let $a$, $b$ be the smallest numbers such that $A/B = a/b$. Then there is some $D$ such that $aD = A$ and $bD = B$.

Combining theorems B and D then yields:

Theorem E: Let $A, B$ be numbers and $a, b$ be coprime numbers such that $A/B = a/b$. Then $a|A$ and $b|B$.

So Theorem E follows from the equivalent theorems A, B and C. But Theorem E also implies Theorem C! After all, let $a, b$ be coprime numbers such that $a/b = A/B$ and suppose that $a', b'$ are also coprime numbers such that $A/B = a'/b'$. Then $a/b = a'/b'$ and applying Theorem $E$ with $a', b'$ in the role of $A$ and $B$ yields $a|a'$ and $b|b'$. However, applying Theorem E with $a$ and $b$ in the role of $A$ and $B$ and $a'$ and $b'$ in the role of $a$ and $b$ we find that $a'|a$ and $b'|b$, so that $a = a'$ and $b = b'$.

We conclude that all five theorems A, B, C, D, E are equivalent.

Due to the uniqueness appearing in Theorem C, and to stress the relationship to Unique Factorization that we will now get to, Bill Dubuque (elsewhere on MSE) calls these equivalent theorems 'unique fractionization'. A brilliant name if you ask me.

The Fundamental Theorem of Arithmatic is equivalent to

Euclid's lemma: if a prime $p$ divides a product $xy$ then $p|x$ or $p|y$.

The proof of this equivalence is easy to google. I just state it here to justify working with Euclid's Lemma instead of the FTofA.

Euclid's Lemma implies Theorem E

Proof: let $a, b, A, B$ be as in that theorem. The equation $a/b = A/B$ implies $aB = bA$. Let $p$ be any prime factor of $a$ so it divides the left hand side. It then divides the righthand side, and hence by Euclid's lemma $p|b$ or $p|A$. But since $a$ and $b$ are coprime, $p$ cannot divide $b$ and hence we have $p|A$. Since this holds for every prime divisor of $a$ it follows that $a|A$. (This last step only requires that $a$ has some factorization into primes, not even that it is unique.) Similarly we can show $b|B$.

Theorem E implies Euclid's lemma

Proof: let $p, x, y$ be as in Euclid's lemma. In particular this means that there is a number $z$ such that $pz = xy$. We can rewrite this as $p/x = y/z$. There are two possibilities: $p$ and $x$ have a common divisor greater than 1 or they don't. If they do this common divisor must be $p$, since $p$ is the only divisor of $p$ greater than 1. This means that $p|x$. If they don't we can apply Theorem E with $p$ in the role of $a$ and $y$ in the role of $A$ to conclude $p|y$.

Now in order to give a proof of unique fractionization that does not depend on the Fundamental Theorem of Arithmetic we begin with a lesser known lemma of Euclid:

Euclid's Other Lemma: Let $\frac{A}{B} = \frac{P}{Q}$ with $A \neq P$ and (hence) $B \neq Q$. Then $\frac{A + P}{B + Q}$ and $\frac{A - P}{B - Q}$ are also equal to this same fraction.

I like the lemma because it goes against our reflexes. We are inclined to say: 'No this is wrong! You can preserve equality by multiplying or dividing but not with adding of subtracting!' or 'No this is wrong! You can't combine two fraction into one by this method, it yields unpredictable and nonsensical results'

But actually, in this context it is right. If, like Euclid, you think about $A/B$ as the ratio between two lengths rather than as a fraction, then you can more or less 'see' it geometrically. But here is a 'modern' proof:

From $A/B = P/Q$ we get $AQ = BP$ so that $AB + AQ = AB + BP$ or equivalently $A(B+Q) = (A + P)B$ which yields $A/B = (A+P)/(B+Q)$.

Proof of Theorem D that does not use Euclid's lemma Let $A, B, a, b$ be as in that theorem. Let $D$ be the largest number such that $A - Da \geq 0$. We assume that $A - Da > 0$ and arrive at a contradiction. Indeed applying Euclid's Other Lemma $D$ times we find that $(A - a)/(B-b), (A-2a)/(B - 2b), \ldots, (A - Da)/(B - Db)$ are all equal to $A/B$. Now by definition of $D$, we have $A - Da < a$ but by definition of $a$ the fact that $(A - Da)/(B - Db) = A/B$ implies $A - Da \geq a$. This is our contradiction. It follows that $A - Da = 0$ or equivalently that $A = Da$ as we wanted to show. From $Ab = aB$ we then get $Dab = aB$ and hence $Db = B$ as well.

$\endgroup$
8
  • 1
    $\begingroup$ What precisely is your question? These well-known results are already proved here in may places, e.g. see here and here and here and their links. $\endgroup$ Commented Oct 10, 2023 at 22:51
  • $\begingroup$ .... OP said: "What I am really asking you is: Is there a matroid or greedoid structure on pairs of numbers that explains the success of the greedy algorithm for simplifying fractions?" $\endgroup$
    – dmh
    Commented Oct 10, 2023 at 22:57
  • 1
    $\begingroup$ A typical greedy algorithm relies on the greediness of the choice at each step, but in the algorithm you're describing, you can choose any common divisor at each step. So I doubt the abstractions built for establishing correctness of greedy algorithms will do the desired work here. $\endgroup$
    – Karl
    Commented Oct 10, 2023 at 23:18
  • 1
    $\begingroup$ If what you really seek is further intuition on why any sequence of cancellations always terminates with the same reduced fraction then this can be clarified from a more general perspective using ideas from rewrite rule theory (via the diamond (confluent) property). If you think this would be of interest then let me know and I will post an answer from that perspective. $\endgroup$ Commented Oct 11, 2023 at 6:19
  • 1
    $\begingroup$ Ok, I'll try to find some time to compose an answer (hopefully within the next couple days) $\endgroup$ Commented Oct 13, 2023 at 20:32

1 Answer 1

1
$\begingroup$

This is not a greedy algorithm. We are not at any step selecting a locally optimal choice in any sense. In fact any sequence of choices gets us to the same result.

This is easy to explain with no reference to a structure as complicated as a matroid or a greedoid: there is a poset of simplifications of the fraction $\frac{A}{B}$ and it has a unique minimal element, namely the fraction $\frac{a}{b}$ in lowest terms, where $\gcd(a, b) = 1$. Since this poset is finite, any sequence of steps down in the poset hits this unique minimal element after a finite number of steps. All we need for this is Theorem E, together with the observation that a positive integer can only be divided by a proper divisor a finite number of times.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .