An Egyptian fraction is a sum of distinct unit fractions, but it's easy to convert sums of non-distinct fractions into Egyptian fractions, by repeatedly finding pairs of equal fractions \( 1/k + 1/k \) and replacing them either by \( 2/k \) (if \( k \) is even) or \( 2/(k+1) + 2/k(k+1) \) as I described here. For example,

\[ \begin{align} \frac{5}{18} &\Rightarrow \frac{1}{18} + \frac{1}{18} + \frac{1}{18} + \frac{1}{18} + \frac{1}{18} \\ &\Rightarrow \frac{1}{18} + \frac{1}{9} + \frac{1}{9} \\ &\Rightarrow \frac{1}{18} + \frac{1}{5} + \frac{1}{45}. \\ \end{align} \]

It also works to replace \( 1/k + 1/k \) by \( 1/k + 1/(k+1) + 1/k(k+1) \), as Graham and Jewett proved:

\[ \begin{align} \frac{3}{7} &\Rightarrow \frac{1}{7} + \frac{1}{7} + \frac{1}{7} \\ &\Rightarrow \frac{1}{7} + \frac{1}{8} + \frac{1}{8} + \frac{1}{56} + \frac{1}{56} \\ &\Rightarrow \frac{1}{7} + \frac{1}{8} + \frac{1}{9} + \frac{1}{72} + \frac{1}{56} + \frac{1}{57} + \frac{1}{3192}. \\ \end{align} \]

Both of these methods produce fractions that may have significantly larger denominators than the starting one, because the replacement formulas involve quadratic polynomials. But maybe that quadratic blowup is unnecessary? What if we try a much simpler replacement: \( 1/k + 1/k \Rightarrow 1/k + 1/2k + 1/3k + 1/6k \)?

\[ \begin{align} \frac{3}{4} &\Rightarrow \frac{1}{4} + \frac{1}{4} + \frac{1}{4} \\ &\Rightarrow \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{12} + \frac{1}{12} + \frac{1}{24} + \frac{1}{24} \\ &\Rightarrow \frac{1}{4} + \frac{1}{8} + \frac{1}{12} + \frac{1}{12} + \frac{1}{16} + \frac{1}{24} + \frac{1}{24} + \frac{1}{24} + \frac{1}{48} \\ \end{align} \]

and now we have a problem: the three copies of \( 1/4 \) led to three copies of \( 1/24 \), which will lead to three copies of \( 1/144 \), which...won't ever terminate.

Can we fix this by a more complicated replacement rule? What about, say, \( 1/k + 1/k \Rightarrow 1/2k + 1/3k + 1/7k + 1/42k \)? No such expansion rule, in which all the denominators of the expansion are linear in the duplicated input denominator, can work! For, in a rule with \( s \) terms in the expansion, starting with \( a \) copies of the same fraction and expanding one of these copies once, one copy twice, etc., results in an expansion with \( \ge s^{a-1} \) terms, all of which belong to a set of \( O(a^s) \) different multiples of the starting denominator. So for any sufficiently large \( a \), we can find after these forced expansions a larger denominator \( d \) with at least \( a \) copies of the fraction \( 1/d \), setting off the same kind of infinite loop we saw for the \( 1/2 + 1/3 + 1/6 \) expansion.




Comments:

1minusqsquared:
2006-12-02T02:59:04Z

Neat.

But you can do better than quadratic and still not be linear, right? What about some expansion rule that, (on average 'cause we're dealing with integers), makes the denominator \( n\log(n) \) or \( n^{3/2} \) or any number of other things?

11011110:
2006-12-02T06:12:34Z

There are methods that will expand \( a/b \) to something with denominators that are subquadratic in \( b \), but I don't know how to express them in terms of this sort of simple expansion rule.