Minimizing the Denominators of Unit Fraction Expansions
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
Сайт управляется системой
uCoz