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/ |
|_______________/_____\_______________________________________|