For any proper fraction n/d let f(n,d) denote the least integer k such that n/d can be expressed as a sum of distinct unit fractions with denominators less than or equal to kd. For example, we have f(31/311) = 10, because 31/311 can be expressed as a sum of distinct unit fractions with denominators no greater than 3110, but not with any smaller max denominator. I'm seeking a reference, proof, or counter-example for the conjecture that f(n,d) < 2 ln(d) + 1. The proposition would certainly be false if the +1 was omitted, because we have f(7,19) = 6, whereas 2*ln(19) equals only 5.89. On the other hand, with the +1 term the proposition is true for all d < 4831. For example, the formula correctly asserts that the fraction 43/4021 can be expressed as a sum of distinct unit fractions with greatest denominator 68357. It certainly appears that highest values of max{f(n,d)} are nearly linear as a function of log(d), and on probabilistic grounds it's easy to see that the relation should be of this form. I'd like to know if the asymptotic slope is really 2, or if something steeper is required. David Eppstein noted the following reference: H. Yokota, Denominators of Egyptian fractions, J. Num. Th. 28 (1988) 258-271 According to the abstract, this paper proves that, in my notation, f(n,d) <= (log d)^(3/2 + epsilon) where epsilon goes to zero as d goes to infinity. Yokota has published additional papers on Egyptian fractions since 1988, including one in 1990 with G. Tenebaum in which they further refined the upper bound on f(n,d). They trace their work back to a conjecture of Bleicher and Erdos in 1976 that for every epsilon > 0 there is a constant C such that f(n,d) < C log(n)^(1+epsilon) which is similar to, but less restrictive than, my conjecture that f(n,d) < 2 log(d) + 1. However, I've found a counter-example to my conjecture. The unit fraction expansion of 5/6947 with the smallest maximum denominator is 1 / 1 1 1 1 1 1 1 1 1 \ 1 1 ---- ( - + - + - + - + - + - + -- + -- + -- ) + ---- + ---- 6947 \ 2 3 4 5 7 8 13 14 19 / 3640 5187 so we have f(5,6947) = 19, whereas my conjectured upper bound is 2 log(6947) + 1 = 18.692.. If we define D(d) as max{f(n,d)|0 < n < d} then the smallest values of d for each D(d) < 20 are listed below: D(d) smallest d D(d) smallest d ----- ---------- ----- ---------- 1 2 11 271 2 3 12 419 3 5 13 521 4 11 14 751 5 13 15 1423 6 19 16 2273 7 41 17 4021 8 37 18 5659 9 89 19 6947 10 179 It's interesting to consider why it's impossible to express every simple fraction of the form n/19 (for example) as a sum of distinct unit fractions with max denominator of 5*19 or less. The reason can be explained in terms of the first five reciprocals (mod 19). These five numbers are 1/1 = 1 1/2 = 10 1/3 = 13 (mod 19) 1/4 = 5 1/5 = 4 In order to express every fraction n/19, n = 1 to 18, as a sum of unit fractions with denominators no larger than 5*19 we would need to be able to express each n from 1 to 18 as a sum (mod 19) of the above five numbers, i.e., 1, 10, 13, 5, 4, without repetition. The possible sums of these numbers (mod 19) are sums of one: 1 10 13 5 4 sums of two: 11 14 6 5 4 15 14 18 17 9 sums of three: 5 16 15 0 18 10 9 8 0 3 sums of four: 13 4 1 9 10 sums of five: 14 The numbers 2, 7, and 12 do not appear, so these are the numerators n such that the expansion of n/19 requires a denominator of at least 6*19. Obviously it's a simple matter to recursively generate the sums of the reciprocals (mod p) of the first k integers, for k=1,2,... until finding a solution. Roughly speaking, if we treat the sums of random samples, we would expect to need O(log(p)) samples to get any particular residue modulo p, so this immediately leads us to suppose that we could expand any simple fraction n/p into a sum of unit fractions with greatest denominator roughly O(p log(p)). The 1976 paper of Bleicher and Erdos concludes "with a numerical example which illustrates that the algorithms to date [for expanding fractions into sums of unit fractions minimizing the largest denominator] leave something to be desired." They note that the Fibonacci-Sylvester algorithm yields an expansion with huge denominators (although there seems to be a typo in the actual values printed in the paper). In contrast, Erdos's algorithm gives 5 1 1 1 1 1 1 1 --- = --- + --- + --- + ---- + ---- + ---- + ----- 121 48 72 180 1452 4354 8712 87120 They also noted that the continued fraction algorithm gives a shorter expansion with smaller denominators 5 1 1 1 1 1 --- = --- + ---- + ---- + ---- + ----- 121 25 1225 3477 7081 11737 Then they compare this with the algorithm described in their paper, which gives 5 1 1 1 1 1 --- = --- + --- + --- + ---- + ---- 121 30 242 363 1210 3630 They then applied "ad hoc" methods to get "a good short expansion" 5 1 1 1 1 --- = --- + --- + --- + ---- 121 42 70 330 5082 and then another expansion "which while longer has denominators considerably smaller than any of the others" 5 1 1 1 1 1 --- = --- + --- + --- + --- + ---- 121 42 70 726 770 1815 It's interesting that, at recently as 1976, people evidently weren't familiar with the simple recursive algorithm for finding the unit fraction expansion with the absolute smallest max denominator. It's easy to see that, since 121 is composite the recursive algorithm can be applied to (1/11)(5/11) to give the almost trivial expansion 5/121 = 1/33 + 1/121 + 1/363. This makes it rather surprising that 5/121 was selected by Erdos and Bleicher to exemplify a "hard" fraction, especially considering that this method was apparently used to construct the tables of unit fractions in the Akhmin Papyrus, c. 500 AD. By the way, I've done some more checking and found that the lowest order fraction n/d such that D(d)/d = 20 is 1097/14939, which expands to 1/14939 times / 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 \ ( - + - + - + - + - + - + - + - + - + -- + -- + -- + -- + -- + -- ) \ 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 / plus a remainder of 41/560 = 1/14 + 1/560. Interestingly this is back in agreement with my original conjecture that D(d)/d < 2 log(d) + 1. Another interesting point is that the only four numerators for which f(n,14939) equals 20 are 1097, 1927, 13235, and 14065. Notice that both pairs differ by 830. Evidently these are the only four numbers that can't be expressed as sums in terms of the reciprocals of the first 20 integers modulo 14393. We alluded above to a recursive method for expanding a simple fraction n/p into a sum of distinct unit fractions by forming the sums of the reciprocals of the first k integers modulo the prime denominator p. The first sum that equals the numerator n yields an expansion of the form n 1 / 1 1 1 \ u --- = --- ( --- + --- + .. + --- ) + --- p p \ x1 x2 xj / v where 0 < x1 < x2 ... < xj <= k and v is not divisible by p. I said that this method gives the expansion with the least possible max denominator, p*xj. Of course, this assumes the remainder u/v can be expanded into a sum of unit fractions with max denominator less than p*xj, which is ordinarily the case, because v can only be a product of divisors of the x's, each of which is smaller than roughly log(p). However, there are cases in which the remainder of the first solution produced by the recursive formula requires a denominator greater than p*xj in its expansion. For example, if we search recursively for an expansion of 3/2221 the first solution is occurs with k=11, namely 3 1 / 1 1 1 1 1 1 1 1 1 \ 1 ---- = ---- ( 1 + - + - + - + - + - + - + - + - + -- ) + ----- 2221 2221 \ 2 3 4 5 6 7 8 9 11 / 27720 but in this case p*xj = 24431, which is less than the remainder's denominator of 27720. What we've shown is that the greatest denoninator in an expansion of 3/2221 must be at least 24431, and need be no greater than 27720. To determine if there is an expansion with max denominator between 24431 and 27720 we must proceed to the next solution in the recursion, which occurs at k=13: 3 1 / 1 1 1 1 1 1 \ 1 ---- = ---- ( 1 + - + - + - + - + -- + -- ) + ---- 2221 2221 \ 2 5 6 7 10 13 / 2730 This shows that the next smallest possible value of p*xj is 28873, and no later expansion in the recursion sequence can have a lesser max denominator than this. Therefore, the preceeding solution is optimum. In general, this method of determining the optimum (least max denominator) expansion consists of recursively generating the solutions in increasing order of p*xj until finding one for which the remainder can be expanded with a max denominator less than p*xj. This almost always occurs on the first solution, but if it doesn't the process continues until such a remainder is found. Roughly speaking we will always find solutions with k less than O[log(p)^(1+delta)], and the recurrence involves 2^k trials, so the number of trials is very roughly on the order of p. This approach is even more efficient for finding the limiting expansion for ALL the numerators for a given denominator p, becauase this can be computed in essentially the same time required to solve for a single numerator. Of course the above algorithm applies only to expanding fractions with prime denominators. From the standpoint of determining the upper bound on max denominators this is not a serious limitation because the greatest values of (max denom in expansion)/(denom) are known to occur for prime denominators. However, it could be a limitation in carrying out the above algorithm in cases were the remainder u/v is non-trivial. Fortunately the fact that v is necessarily the product of many distinct small primes implies that it's usually quite easy to find a robust expansion of u/v simply by partitioning u into divisors of v.

Return to MathPages Main Menu