Adjacent fractions
Definition
Let \(a_1, a_2, b_1, b_2\) be positive integers and let us consider two fractions \(\frac{a_1}{b_1} < \frac{a_2}{b_2}\). It is said that \(\frac{a_1}{b_1}\) and \(\frac{a_2}{b_2}\) are adjacent if
\[ \frac{a_2}{b_2 + 1} < \frac{a_1}{b_1}, \text{ and } b_1 = 1 \text{ or } \frac{a_2}{b_2} < \frac{a_1}{b_1-1}. \]
It can be proven that if a sequence \(\frac{a_1}{b_1} < \frac{a_2}{b_2} < \cdots < \frac{a_p}{b_p}\) is a Bézout sequence and \(\frac{a_1}{b_1}, \frac{a_p}{b_p}\) are adjacent fractions, then \(\{a_1, \ldots, a_p\}\) is a minimal system of generators of \(S = \langle a_1, \ldots, a_p \rangle\).
Examples
\(\circ\) Let \(a_1 = 7, a_2 = 15, b_1 = 3, b_2 = 4\) and the fractions \(\frac{a_1}{b_1} = \frac{7}{3}, \frac{a_2}{b_2} = \frac{15}{4}\). We have,
\[ \frac{a_2}{b_2 + 1} = \frac{15}{5} = 3 > \frac{7}{3} = \frac{a_1}{b_1}. \]
Then, \(\frac{7}{3}\) and \(\frac{15}{4}\) are not adjacent fractions.
\(\circ\) Let \(a_1 = 2, a_2 = 2, b_1 = 7, b_2 = 9\) and the fractions \(\frac{a_1}{b_1} = \frac{2}{7}, \frac{a_2}{b_2} = \frac{2}{9}\). We have,
\[ \frac{a_2}{b_2 + 1} = \frac{2}{10} < \frac{2}{7} = \frac{a_1}{b_1} \text{ and } \frac{a_2}{b_2} = \frac{2}{9} < \frac{2}{7-1} = \frac{a_1}{b_1 - 1}. \]
Therefore, \(\frac{2}{7}\) and \(\frac{2}{9}\) are adjacent fractions.
Examples with GAP
Nowadays, there are no functions in package NumericalSgps related to adjacent fractions. However, given two rationals \(x = a_1/b_1, y = a_2/b_2\) where \(a_1, a_2, b_1, b_2\) are positive integers, the following function returns true if \(\frac{a_1}{b_1}, \frac{a_2}{b_2}\) are adjacent fractions and false otherwise.
gap> AdjacentFractions := function(x, y)
> local a_1, a_2, b_1, b_2;
> if not IsRat(x) then
> Error("First argument must be a positive rational number");
> fi;
> if NumeratorRat(x) < 0 then
> Error("First argument must be a positive rational number");
> fi;
> if not IsRat(y) then
> Error("Second argument must be a positive rational number");
> fi;
> if NumeratorRat(y) < 0 then
> Error("Second argument must be a positive rational number");
> fi;
> if x >= y then
> return false;
> fi;
> a_1 := NumeratorRat(x); b_1 := DenominatorRat(x);
> a_2 := NumeratorRat(y); b_2 := DenominatorRat(y);
> if a_1*(b_2 + 1) - a_2*b_1 > 0 then
> if b_1 = 1 then
> return true;
> fi;
> if a_1*b_2 - a_2*(b_1 - 1) > 0 then
> return true;
> fi;
> fi;
> end;
function( x, y ) ... end\(\diamond\) Let \(\frac{3}{1} < \frac{7}{2}\). Since \(\frac{7}{3} < 3\) and \(b_1 = 1\), they are adjacent fractions. If we use the function defined above,
gap> AdjacentFractions(3/1 7/2);
trueReferences
https://gap-packages.github.io/ numericalsgps.