My recent subgreedy conjecture on Egyptian fractions implies, not just that the odd greedy algorithm terminates, but also that the corresponding even greedy algorithm (in which at each step we subtract the smallest even unit fraction from the remaining value to be expanded) produces finite expansions. But there's a much simpler proof for this case:

( Cut for spoiler )

The greedy algorithm for Egyptian fractions takes as input a fraction x/y, and repeatedly expands x/y = 1/d + x'/y', where d=ceiling(y/x) is the smallest possible denominator such that 1/d is at most x/y. Once one reaches a remaining fraction x/y such that (in its simplest form) x = 1, the algorithm terminates.

Analogously, define a subgreedy expansion of x/y to be the result of repeatedly expanding either x/y = 1/d + x'/y' as above, or x/y = 1/(d+1) + x'/y', where d=ceiling(y/x) as before. Also as before, the expansion terminates as soon as the remaining fraction has a unit numerator in its simplest form.

( Examples )

Conjecture. Any fraction x/y has a finite number of subgreedy expansions. More precisely for x/y < 1 the number of expansions is O(y).

The significance of this conjecture is that the odd greedy expansion is a subgreedy expansion. It's a well-studied open problem whether the odd greedy algorithm always terminates, but its termination would follow directly from this conjecture, because if the odd greedy algorithm didn't terminate one could find infinitely many subgreedy expansions by running odd greedy for some number of steps then switching to greedy. However, the conjecture abstracts away the complications of oddness, leaving a perhaps simpler problem. In addition it allows the focus to be on the number of solutions rather than the length of an individual solution, which seems a more promising line of attack.

( Evidence )

2/7 = 1/5 + 1/(5*3) + 1/(5*3*5) + 1/(5*3*5*3) + 1/(5*3*5*3*5) + ... and
3/7 = 1/3 + 1/(3*5) + 1/(3*5*3) + 1/(3*5*3*5) + 1/(3*5*3*5*3) + ...

More generally,
2/(12n+7) = 1/(6n+5) + 1/(6n+5)(4n+3) + 1/(6n+5)(4n+3)(6n+5) + ... and
3/(12n+7) = 1/(4n+3) + 1/(4n+3)(6n+5) + 1/(4n+3)(6n+5)(4n+3) + ...

So the analogue to the odd greedy Egyptian fraction problem for Engel expansion has an immediate negative answer.

The same infinite 2/7 and 3/7 expansions also occur as the Costé prime expansion of these numbers, which is infinite for the same reasons.

For a prime p, define f(p) to be the minimum i such that all residues mod p can be expressed as sums of subsets of the values {1/1, 1/2, 1/3, ...1/i} mod p. We need only consider residues other than 0 and 1, since 0 is always the sum of the empty subset and 1 = 1/1. E.g.,

f(2) = 1, because 1 = 1/1.

f(3) = 2, because 2 = 1/2 mod 3.

f(5) = 3, because 2 = 1/3, 3 = 1/2, and 4 = 1/1 + 1/2 mod 5.

f(7) = 3, because 2 = 1/2 + 1/3, 3 = 1/1 + 1/2 + 1/3, 4 = 1/2, 5 = 1/3, and 6 = 1/1 + 1/3 mod 7.

f(11) = 4, because 2 = 1/2 + 1/3 + 1/4, 3 = 1/4, 4 = 1/3, 5 = 1/1 + 1/3, 6 = 1/2, 7 = 1/1 + 1/2, 8 = 1/1 + 1/3 + 1/4, 9 = 1/2 + 1/4, and 10 = 1/2 + 1/3 mod 11.

f(13) = 5. 2 = 1/2 + 1/5 (mod 13) and 12 = 1/1 + 1/2 + 1/3 + 1/5 (mod 13); all other residues can be expressed as sums of subsets of {1/1, 1/2, 1/3, 1/4}.

How quickly does f(p) grow with p? It must be at least log₂p else there would not be enough different subsets to cover all the residues. It seems plausible to me (e.g. using an argument in which we replace each unit fraction by a random variable) that f(p) = Θ(log p).

The relevance of this is for bounding the maximum denominator of an Egyptian fraction as a function of its denominator. For each p, some fraction x/p requires a maximum denominator of at least f(p)p in any Egyptian fraction expansion, as can be seen by considering only the terms in the expansion in which the denominator is a multiple of p. The simple lower bound for f(p) above thus leads to a lower bound of Ω(y log y) on the maximum denominator in an expansion of x/y, for infinitely many pairs x, y. On the other hand, it seems plausible (although not completely obvious due to issues with repeated fractions and overlarge expansions) that something like the prime-multiples method of my Egyptian fraction code can expand any fraction x/y using max denominator f(p)y, where p is the prime factor of y with the largest value of f(p). This approach might have some hope of improving the Tenenbaum-Yokota O(y log^2 y / log log y) upper bound on the max denominator.

The Egyptians expanded 2/101 = 1/101 + 1/202 + 1/303 + 1/606. That expansion is not the shortest (1/51 + 1/5151) but it has the smallest possible maximum denominator (606) of any expansion as a sum of distinct unit fractions. The expansion 2/n = 1/n + 1/2n + 1/3n + 1/6n works for all n; for how many other values of n does it produce the optimal result?

Answer: infinitely many, by the following theorem.

Theorem. Let D(q) denote the smallest d such that q has an Egyptian fraction with maximum denominator d, and let k be a fixed integer. Then for all but finitely many prime numbers p, D(k/p) = p D(k).

( Proof )

Testing all expressions of the form 2 - sum 1/a_i for a_i ≤ 5 shows that the only possible odd primes with 2/n expansions having denominators better than 6n are 2, 3, 5, 7, 11, 13, 17, 29, 31, 43, and 73. Here are some better expansions for these numbers:

( Read more... )

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,

5/18 => 1/18 + 1/18 + 1/18 + 1/18 + 1/18 => 1/18 + 1/9 + 1/9 => 1/18 + 1/5 + 1/45.

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

3/7 => 1/7 + 1/7 + 1/7 => 1/7 + 1/8 + 1/8 + 1/56 + 1/56 => 1/7 + 1/8 + 1/9 + 1/72 + 1/56 + 1/57 + 1/3192.

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 => 1/k + 1/2k + 1/3k + 1/6k?

3/4 => 1/4 + 1/4 + 1/4 => 1/4 + 1/8 + 1/8 + 1/12 + 1/12 + 1/24 + 1/24 = 1/4 + 1/8 + 1/12 + 1/12 + 1/16 + 1/24 + 1/24 + 1/24 + 1/48

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 => 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 ≥ 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.

Engel expansion! How did I overlook this in my previous investigations of how to generate Egyptian fractions? As I just finished including in that article, this technique was apparently known to Fibonacci, who also investigated the more well known greedy method for Egyptian fractions.

Anyway, my Egyptian fraction Python code now knows how to generate expansions of this type. If you run, e.g.,

egypt.py 7/17 engel

you will get the expansion

1/3 + 1/15 + 1/90 + 1/1530

where each denominator is a multiple of the previous one: 3, 3×5, 3×5×6, 3×5×6×17. By default it generates the standard expansion in which these multipliers 3, 5, 6, 17 are nondecreasing, but it can also generate infinitely many other expansions without this nondecreasing property, so the -a option should only be used in conjunction with -d or -l.

Just spent some time cleaning up broken links on my page about Egyptian Fractions (that is, the problem of representing rational numbers as sums of distinct unit fractions). Only had to resort to the Internet Archive once, so not too bad compared to the Augaean task that is the Geometry Junkyard. Added three new links:

• Wikipedia: Egyptian fractions. It doesn't have a lot of detail or outside references, but it's a useful basic introduction to the problem.
• Math Games: Egyptian Fractions. Ed Pegg describes the Rhind Papyrus and the 4/n problem, including a pretty density plot of the number of terms required in the shortest egyptian fraction representation of rationals with small numerators and denominators. I wish he'd add an RSS feed to this sequence of articles or his other mathpuzzle.com site, though, as I miss too many interesting updates due to checking back there too infrequently.
• Ernie Croot's papers. I'd already seen the one on binary Egyptian fractions, but there are several more there, including an interesting one showing that, for any r-coloring of the unit fractions, some color class contains a representation of one with maximum denominator at most exponential in r.

( Read more: the Gaussian Integer 4/n Problem )