Re: Status of Waring-problem
From: Gottfried Helms (helms_at_uni-kassel.de)
Date: 08/31/04
- Next message: Jesse F. Hughes: "Re: JSH: Math proofs"
- Previous message: William Elliot: "Re: Explaining the foundations of math"
- Next in thread: Gottfried Helms: "Re: Status of Waring-problem"
- Maybe reply: Gottfried Helms: "Re: Status of Waring-problem"
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 31 Aug 2004 12:07:32 +0200
David -
... that was again a helpful short-course in approximation
theory. I recognized, I have mailed an unfounded remark to
eric roosendaal's pages concerning high values for that
log(3)/log(2) approximation: my method was essentially
a continued-fraction-method in disguise.
Am 26.08.04 03:27 schrieb David Moews:
> |Could (1) be related to bounds to the entries [a0,a1,a2,...]
> |of the continued fraction of some construct from
> | powerceil2(3^N)/3^N or log(3/2)?
>
> Yes, it is. First, let me say that there are m and n for which the
> inequalities in (1') both hold; the smallest example is
>
> m=20816638400272738047368492381060294533896172097625924359292341264797752249989287849839400689106668686909215,
> n=13133836536070216578107364133782187951468730053797860331128520665822294009505732797871598129236098353038886 (2)
>
> for which 2^m/3^n is about 1 + 5.256*10^(-109), while 1/(128n) is about
> 5.948*10^(-109).
>
Thanks for that example, after I extended my float-point-precision
I found some more examples, and also could recognize, that this
approximation could not determined by a constant value like 128.
> The connection to continued fractions is as follows. Taking logarithms,
> we can rewrite (1') as
>
> 0 < m log 2 - n log 3 <= log(1 + 1/(128n)),
>
> which implies, using the inequality log (1+x) <= x, that
>
> 0 < m log 2 - n log 3 <= 1/(128n),
>
> or, dividing by n log 2,
>
> 0 < m/n - log 3/log 2 <= 1/(128 n^2 log 2).
>
> Now it is a theorem that if x > 0 is irrational and | x - m/n | < 1/(2 n^2),
> then m/n must be some convergent, pk/qk say, of the continued fraction of x.
> If it is, let m/n = pk/qk (using the notation of my last post.) Then
>
> 1/((ak+2) qk^2) <= | x - pk/qk | <= 1/(ak qk^2)
>
> where ak is the first partial quotient of the continued fraction omitted
> from pk/qk. We therefore get a good approximation to x when x's continued
> fraction is truncated just before a large partial quotient; the example
> (2) comes from truncating the continued fraction for log 3/log 2 just
> before a partial quotient 100.
>
> For a `random' real number x, the Gauss-Kuzmin law states that a partial
> quotient q should occur with frequency log (1 + 1/(q (q+2))) / log 2
> in the continued fraction of x, and this is approximately what we observe
> in the first 10000 partial quotients of log 3/log 2. So, you should
> expect arbitrarily large partial quotients to occur in the continued
> fraction expansion of log 3/log 2.
Yes; what I was interested in, was some ratio like that of Gauss, which
binds the elements of the continued-fraction with some function of
N.
And it seems, that I still have difficulties to understand things right.
so I'll review my considerations.
I've received a mail of someone who applied that technique to my original
problem. In that mail he said:
> This is an absolutely astounding degree of approximation -- exponentially good. In
> general the best you can expect is on the order of 1/L^2, and IIRC for the number
> pi it has been proved that you can't do better than 1/L^8 or something. In
(original posting below)
The Guss-argument is a statistical one; from this we only expect
frequencies, but not a first possible occurence. For problems like
the given I'd expect some connection to the index n...
My question arose from approximation of powerceil2(3^N)/3^N.
I stated that as a iterative problem of approximation by a
infinite product, say
4/3 > 1 4*4/3/3 > 1 4*4*2/3*3*3 >1 ...
Let's write A for 4/3 and B for 2/3 . Then this written as a string
(always checked to get the best approximation to 1 from above) gives
AABABAABAB....
On each step the approximation cannot arbitrarily good, but is
bounded by the initial discrepancy {A} and the length of the re-
petitions used.
Now we find, that in that string we have two types of substrings
C = AAB and D = AB
so a compressed string is
CD CDD CD CDD
or something else.
Again the minimal possible discrepancy is clearly bounded by the
length of the patterns; it cannot, say, at the second step be
smaller than 3^-12.
But on certain steps of recursion of this compressions, we may
have
H= FFFFFFG and I=FFFFFG
so the approximation at the beginning of the pattern H and at the
end of H must be much smaller (and better than at the beginning
and ends of I, since the length of I is one element shorter)
Meanwhile I understood, that this arguing is nothing else than
just reproducing the convergents of the continued fraction, and
the lengthes represent its coefficients.
If some combinations of H and I say, HHHHHHHHHHHHHHHHHI are
very long, then that means we have a very good approximation.
But the lengthes cannot occur *arbitrarily* early and the problem
of marking bounds for the cf-coefficients depending on
its index n is just to find bounds for the first occurence
of these maximal lengthes in relation to n.
That's a problem, where I'm turning in circles...
I tried the following idea:
define a function, which gives a somehow "inverse" to the
initial string in the following manner:
A = 4/3 = (3+1)/3 B = 2/3 = (3-1)/3
a = (3-x)/3 b = (3+x)/3
F(n) = AABABA... substring from 1..n
G(n,x) = aababa... substring from 1..n
then
F(n)*G(n,1) = (8/9)^n
and the product is monotonely decreasing with n, so its
approximation-ratio is known.
Also G(n,1) is decreasing with n, but has a similar approximation
pattern as F(n) (since it is derived from that).
If we change x to 3/4 in G(n,x), then this seems to be a somehow
limiting value, which makes the monotonic decreasing product
to a monotonic, but stepwise decreasing product. If x would be smaller,
then the decreasing of the product loses its monotony and gets
this erratic manner.
I'm trying to find out, whether this product can be used as
a limiting factor for the best possible approximation on step
n in whatever way...
Regards -
Gottfried Helms
---------------------------------------------------------------
>From ... -
-------------------------------------
Just to emphasize Robert Israel's comment: Another formuation is
1 - {L*log(3/2)/log(2)} <= log((3^L - 1)/(2^L - 1))/log(2) - L*log(3/2)/log(2)
where {x} is the fractional part of x, i.e. x - [x], where [x] is the integer floor
of x. Equality holds for L = 1 as has been noted. For larger L, the above may be
recast as
1 - {L*log(3/2)/log(2) <= (log(1 - (1/3^L)) - log(1 - 1/2^L))/log(2)
Using natural logs (ln(x) = log(x) /log(e)) and making obvious estimates, we obtain
1 - {L*log(3/2)/log(2) <= B, where
B = 1/2^L *1/ln(2) approximately. Then
{L*log(3/2)/log(2)} >= 1 - B
If we take N = [L*log(3/2)/log(2)] (integer floor) we have
-B <= L*log(3/2)/log(2) - N - 1 < 0
-B/L < log(3/2)/log(2) - ((N+1))/L < 0
so
|(N+1)/L - log(3/2)/log(2)| < 1/L * 1/2^L * 1/ln(2),
approximately.
This is an absolutely astounding degree of approximation -- exponentially good. In
general the best you can expect is on the order of 1/L^2, and IIRC for the number
pi it has been proved that you can't do better than 1/L^8 or something. In
general, the best we can do with rational approximations is the convergents in the
simple continued fraction expansion. In general, if M/L is a convergent to the
irrational number x and L' is the denominator of the next convergent (taking x
irrational makes sure there IS a next convergent) , then
1/(2*L*L') < |M/L - x| < 1/(L*L')
In the case at hand we must have (assuming L is large enough, which here probably
means at least 2)
1/(2*L*L') < 1/L *1/2^L * 1/ln(2)
approximately
L' > ln(2) * 2^(L -1)
approximately.
Using the usual recursion formulas for consecutive convergents, this implies
(assuming L is large enough) an astronomically large partial quotient in the simple
continued fraction for
log(3/2)/log(2).
I can't rule this out offhand, but even a modest limitation on how well this number
can be approximated by rationals would polish it off.
=============================================================
-
- Next message: Jesse F. Hughes: "Re: JSH: Math proofs"
- Previous message: William Elliot: "Re: Explaining the foundations of math"
- Next in thread: Gottfried Helms: "Re: Status of Waring-problem"
- Maybe reply: Gottfried Helms: "Re: Status of Waring-problem"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
