Proof Concerning Ratios of Minimal Denominator/Numerator

Conjecture 1:
Let A and B be real numbers such that B > A >= 1 and B-A<1. Let C be the real
interval [A,B]. Then there exists exactly one rational number in C with minimal
numerator.

Proof:
Suppose that there were at least two ratios of minimal numerator within the
interval. Then we can state that:

N/D > N/(D+1)
N/D > (N-1)/D > N/(D+1)

This violates our original assumption and we therefore conclude that the
interval C must have exactly one ratio with minimal numerator.

Conjecture 2:
There exists exactly one rational number in C with minimal denominator.

Proof:
Suppose that there were at least two ratios of minimal denominator within the
interval. Then we can state that:

(N+1)/D > N/D
(N+1)/D > (N-A)/(D-1) > N/D

N/D > A > (N+1-D)/D
N/D > A > (N+1)/D - 1

Substitute E=A+1.
(N+D)/D > E > (N+1)/D

Because N+D, N+1, N and D are all pairwise coprime with each other, and since N
> D, we know that there must be an integer solution for E which satisfies the
above inequalities. This means that a rational number with a smaller
denominator must exist within the interval C, violating our original assumption
and concluding the proof.

Conjecture 3:
The minimal ratios mentioned in the previous two conjectures (the ratio of
minimal denominator and minimal numerator) are in fact equivalent, and not
distinct.

Proof:
Suppose that the two ratios were distinct. Let us call the ratio of minimal
denominator (N+A)/D, and the ratio of minimal numerator N/(D+B). This gives us
the following inequalities:

B > 0
A > 0
(N+A)/D > N/(D+B)
(N+A)/D > N/D > N/(D+B)

This violates the conclusions of the first two conjectures, meaning that it also
violates our original assumption. Therefore the ratios are equivalent, and not
distinct.

How do you go about finding this minimal ratio? The general method is by cascading down the Stern-Brocot tree. First find the two integers X and Y, where X is greater than any element in C, and Y is smaller than any element in C, such that X-Y is a minimum. Using these two integers as "seeding pairs," travel down the Stern-Brocot tree with fractional mediants (freshman sums) until one of them lies within C. The first fraction you hit that is also a member of C is your overall minimal ratio within C.

Ryan Avella

I should apologize as I just realized that I used some of the same variable letters inconsistently. Please note that the variables A and B represent different variables in each conjecture.

In the first conjecture they represent the bounds of the interval C. In the following conjectures they are employed as arbitrary integers as necessary.

Ryan Avella

>How do you go about finding this minimal ratio? The general method is
>by cascading down the Stern-Brocot tree. First find the two integers
>X and Y, where X is greater than any element in C, and Y is smaller
>than any element in C, such that X-Y is a minimum. Using these two
>integers as "seeding pairs," travel down the Stern-Brocot tree with
>fractional mediants (freshman sums) until one of them lies within C.
>The first fraction you hit that is also a member of C is your overall
>minimal ratio within C.

Can you prove that last sentence?

-Carl

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
>
> >How do you go about finding this minimal ratio? The general method is
> >by cascading down the Stern-Brocot tree. First find the two integers
> >X and Y, where X is greater than any element in C, and Y is smaller
> >than any element in C, such that X-Y is a minimum. Using these two
> >integers as "seeding pairs," travel down the Stern-Brocot tree with
> >fractional mediants (freshman sums) until one of them lies within C.
> >The first fraction you hit that is also a member of C is your overall
> >minimal ratio within C.
>
> Can you prove that last sentence?
>
> -Carl
>

By definition, the mediant of a farey pair (X , Y) is the fraction of *minimal* numerator/denominator within the interval (X , Y). Additionally, this mediant forms farey pairs with each of the original seeding ratios, X and Y.

When you cascade down the Stern-Brocot tree, you are in essence "zooming in" on the interval in question, until one of the intermediate fractional mediants lies within the interval. This intermediate result is the simplest fraction within the interval, and is therefore the minimal ratio we originally wanted.

In the degenerate case where X and Y (above) are not farey pairs, then we know that (X+Y)/2 is the simplest ratio in the interval C. This is trivially true because if X and Y are not farey pairs, we know that X-Y=2, so there must be another integer between X and Y (refer to the original boundary conditions established in conjecture 1).

Ryan Avella

Hi Ryan,

>>> How do you go about finding this minimal ratio? The general method is
>>> by cascading down the Stern-Brocot tree. First find the two integers
>>> X and Y, where X is greater than any element in C, and Y is smaller
>>> than any element in C, such that X-Y is a minimum. Using these two
>>> integers as "seeding pairs," travel down the Stern-Brocot tree with
>>> fractional mediants (freshman sums) until one of them lies within C.
>>> The first fraction you hit that is also a member of C is your overall
>>> minimal ratio within C.
>>
>> Can you prove that last sentence?
>
>By definition, the mediant of a farey pair (X , Y) is the fraction of
>*minimal* numerator/denominator within the interval (X , Y).
>Additionally, this mediant forms farey pairs with each of the original
>seeding ratios, X and Y.
>
>When you cascade down the Stern-Brocot tree, you are in essence
>"zooming in" on the interval in question, until one of the
>intermediate fractional mediants lies within the interval. This
>intermediate result is the simplest fraction within the interval, and
>is therefore the minimal ratio we originally wanted.
>
>In the degenerate case where X and Y (above) are not farey pairs, then
>we know that (X+Y)/2 is the simplest ratio in the interval C. This is
>trivially true because if X and Y are not farey pairs, we know that
>X-Y=2, so there must be another integer between X and Y (refer to the
>original boundary conditions established in conjecture 1).

Conjecture 1 said that C = [A, B] and B-A < 1. Assuming C includes
its endpoints and X-Y must be as small as possible, X-Y can equal
either 1 or 2, correct?

In the X-Y = 2 case, I see that the mediant is the integer between
them and agree it will be the rational with minimal
numerator/denominator.

In the X-Y = 1 case, X & Y are farey neighbors. But why does the
mediant of a farey pair have minimal numerator/denominator?

Thanks,

-Carl

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> Conjecture 1 said that C = [A, B] and B-A < 1. Assuming C includes
> its endpoints and X-Y must be as small as possible, X-Y can equal
> either 1 or 2, correct?

This is indeed correct.

> In the X-Y = 1 case, X & Y are farey neighbors. But why does the
> mediant of a farey pair have minimal numerator/denominator?

The Stern-Brocot tree allows enumeration of all possible rational numbers between a farey pair A/B and C/D. Therefore, every fraction within the interval (A/B, C/D) can be represented as (A*N+C*M)/(B*N+D*M), where N and M are positive coprime integers. The simplest fraction is obtained when (N,M) = (1,1), which happens to correspond to the fractional mediant operation.

Ryan Avella

Ryan wrote:
>The Stern-Brocot tree allows enumeration of all possible rational
>numbers between a farey pair A/B and C/D. Therefore, every fraction
>within the interval (A/B, C/D) can be represented as
>(A*N+C*M)/(B*N+D*M), where N and M are positive coprime integers. The
>simplest fraction is obtained when (N,M) = (1,1), which happens to
>correspond to the fractional mediant operation.

Ok, that looks pretty good! But how do I convince myself of "every
fraction within the interval (A/B, C/D) can be represented as
(A*N+C*M)/(B*N+D*M)"?

-Carl

--- In tuning-math@yahoogroups.com, Carl Lumma <carl@...> wrote:
> Ok, that looks pretty good! But how do I convince myself of "every
> fraction within the interval (A/B, C/D) can be represented as
> (A*N+C*M)/(B*N+D*M)"?

Although a more formal proof is beyond me, I believe it involves starting with the farey pair 0/1 and 1/0. Every ratio can be generated by the expression (0*N+1*M)/(1*N+0*M) = M/N, where N and M are coprime. Then the rest probably follows from some clever inductive reasoning.

Perhaps someone else understands why this basic principle is true. I am sure either Gene, Mike or Keenan would know why.

Ryan

On Friday 07 June 2013 22:40:16 Ryan Avella wrote:
> --- In tuning-math@yahoogroups.com, Carl Lumma <carl@...>
wrote:
> > Ok, that looks pretty good! But how do I convince
> > myself of "every fraction within the interval (A/B,
> > C/D) can be represented as (A*N+C*M)/(B*N+D*M)"?
>
> Although a more formal proof is beyond me, I believe it
> involves starting with the farey pair 0/1 and 1/0.
> Every ratio can be generated by the expression
> (0*N+1*M)/(1*N+0*M) = M/N, where N and M are coprime.
> Then the rest probably follows from some clever
> inductive reasoning.

There's a proof here:

http://www.cut-the-knot.org/blue/Stern.shtml

Graham