5
$\begingroup$

Hello MathOverflow, my first question,

I apologize for the LaTeX, it works in preview but not in Safari once posted.

There are many methods out there that generate a list of unique unit fractions that sum to some rational number. One of the simplest is called the "Splitting Algorithm" which uses the identity $\frac{1}{a}=\frac{1}{a+1}+\frac{1}{a(a+1)}$. Any fraction $\frac{a}{b}$ can be represented as $\sum^a \frac{1}{b}$. The method looks at all the fractions that are duplicates, keeps one of them, and applies the identity again.

For example $\frac{2}{3}=\frac{1}{3}+\frac{1}{3}=\frac{1}{3}+\frac{1}{4}+\frac{1}{12}$

Each of the denominators can be looked at as a composition of functions $f(a)=a+1$ and $g(a)=a(a+1)$. The method works in spite of $f,g,f\circ g,g\circ f,\cdots$ are never equal. fractions like $\frac{5}{2}$. When the method is applied to fractions like this duplicates will appear although it has been proved they can be removed by subsequent applications of the method so that no remaining compositions are equal.

The Question

Can you think of any other areas where compositions of functions are used like this? I know that on its own that is too general; used in the list of sums, products, useful identities, number theory? The best case scenario would be that there are other problems like this and they can be searched for under a common name.

Edit: method produces unique unit fractions; clarified 'equal', when I wrote that I was thinking of cases like $\frac{b-1}{b}$ that may not lead to duplicates

Improve this question
$\endgroup$
1
  • $\begingroup$ References would have helped. Beeckmans, L. "The Splitting Algorithm for Egyptian Fractions." J. Number Th. 43, 173-185, 1993. and Eppstein, D. Egypt.ma Mathematica notebook. ics.uci.edu/~eppstein/numth/egypt/egypt.ma $\endgroup$
    – Will Jagy
    Commented Jun 9, 2010 at 21:06

3 Answers 3

Reset to default
6
$\begingroup$

Computing a continued fraction representation for a real number x can be seen as a repeated application of two functions. Starting with some real number x in [0,1[, apply 1/x, then x+1 the correct amount of time to come back in [0,1[, then 1/x again and so on.

The theory of fuchsian groups makes use of these codings to connect geometric properties of hyperbolic spaces to arithmetic properties of real numbers. Continued fractions representation for example is related to the geodesics on the modular surface $SL_2(R)/SL_2(Z)$.

Improve this answer
$\endgroup$
1
$\begingroup$

Another example: there are 3x3 matrices which, when applied to a vector representing a pythagorean triple, produce other pythagorean triples. I think it is even a way to produce all primitive pythagorean triples from (3,4,5).

In general, you are looking for a finite number of operations which produce through composition a number of objects, and it seems that you want no overlap, i.e. if h and k are two composition series for which h(obj)=k(obj) for some initial object obj, then h=k as composition series, or in other words they are built up the same way.

Universal algebra has some means for the study of the generation of objects through operation composition. In particular, the operations form a clone (semigroup if you look at just the operations which take one argument) which, given the uniqueness requirement above, is relatively free on the set of generators, as there will be no nontrivial equations satisfied by the compostions.

There are other areas and examples as well, but until the question becomes more specific, I will stop here.

Gerhard "Ask Me About System Design" Paseman, 2010.06.08

Improve this answer
$\endgroup$
2
  • $\begingroup$ The second paragraph is essentially what I am looking for: objects generated from compositions and no overlap. I gave the unit fraction example because I had no other way to get across what I meant. I would be interested in the other examples and areas, preferably with a number theory or combinatorics flavor but anything is welcome. $\endgroup$
    – mmm
    Commented Jun 9, 2010 at 21:18
  • $\begingroup$ To clarify my example, there are 3 matrices U, M and D, combinations of which applied to (3,4,5) generate all pythagorean triples, without overlap. I think the Roberts' calligraphic number theory book has the details. Gerhard "Ask Me About System Design" Paseman, 2010.06.10 $\endgroup$
    – Gerhard Paseman
    Commented Jun 10, 2010 at 18:25
1
$\begingroup$

I'm not sure what you mean by "$f,g,f\circ g,g\circ f,\cdots$ are never equal" - if you use this method to decompose 11/3, you'll see that $g(3)=f^9(3)$, for example.

(I think you also need to mention that the purpose of the method is to "generate a list of distinct unit fractions.)

The simplest related example that comes to mind is the study of Collatz-like functions, where in a sense the question of interest is precisely when two different compositions are equal.

Hugo

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I think he just means that no two of that list of functions are equal (as functions). In other words, that the monoid map $F[x, y] \to \hom(\mathbb{N}, \mathbb{N})$ from the free monoid on two generators to the monoid of endofunctions on $\mathbb{N}$, sending $x$ to $f$ and $y$ to $g$, is an injection. $\endgroup$
    – Todd Trimble
    Commented Jun 9, 2010 at 11:33

You must log in to answer this question.

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