From: ksbrown@seanet.com (Kevin Brown) Newsgroups: sci.math Subject: Re: Conjecture On Unit Fraction Expansions Date: Thu, 19 Sep 1996 05:47:34 GMT ksbrown@seanet.com (Kevin Brown) writes: > 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...I'm seeking a reference, > proof, or counter-example for the conjecture that f(n,d) < 2log(d)+1. eppstein@wormwood.ICS.UCI.EDU (David Eppstein) wrote: > The best result in this direction that I know of is > H. Yokota, Denominators of Egyptian fractions, > J. Num. Th. 28 (1988) 258-271 > According to the abstract...it proves that, in your notation, > f(n,d) <= (log d)^(3/2 + epsilon), > where epsilon goes to zero as d goes to infinity. Thanks for the reference. 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):0The 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." ... > >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 > > 5 1 / 1 1 1 1 1 1 1 \ 1 1 > --- = --- ( - + - + - + - + - + - + - ) + --- + --- > 121 121 \ 1 2 3 4 5 7 8 / 84 120 > David Eppstein has pointed out that since 121 is composite the above expansion of 5/121 isn't optimum, because 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 even more surprising that 5/121 was selected by Erdos and Bleicher to exemplify a "hard" fraction. 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. ============================================================================== From: ksbrown@seanet.com (Kevin Brown) Newsgroups: sci.math Subject: Re: Conjecture On Unit Fraction Expansions Date: Sat, 21 Sep 1996 04:37:26 GMT In a recent article I described a recursive method of 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 numerator p. The first sum that equals the denominator 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). eppstein@wormwood.ICS.UCI.EDU (David Eppstein) wrote: > I am not convinced however that this idea necessarily always gives > the expansion with the minimum denominator... It gives some multiples > of 1/p together with a remaining term in which no factors of p appear. > But how do we know that remaining term has a good expansion? You're right, 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 you 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. _____________________________________________________________ | /*\ | | MathPages / \ http://www.seanet.com/~ksbrown/ | |_______________/_____\_______________________________________|