question related to Littlewood's conjecture in diophantine approximation
David Bernier
distance from x to the integer nearest to x.
For example, || 4/3 || = 4/3 - 1 = 1/3.
|| 107.5 || = 108 - 107.5 = 0.5 = 1/2.
|| 22.99 || = 23 - 22.99 = 0.01 = 1/100.
Let alpha and beta be real numbers in the interval [0, 1].
Littlewood conjectured that, for all alpha, beta in [0, 1],
lim inf_{n-> infinity} ( n ||n alpha|| || n beta|| ) = 0.
MathWorld has an article on "Badly approximable"
irrational numbers:
< http://mathworld.wolfram.com/BadlyApproximable.html >.
The relevance of badly approximable numbers is that,
if alpha is irrational and not badly approximable,
then
lim inf_{q -> oo} q | q alpha - nint(q alpha)| = 0. (***)
"nint", which is used at MathWorld, denotes the nearest
integer function.
Clearly, | q alpha - nint(q alpha) | = || q alpha ||.
So (***) can be re-written as:
lim inf_{n-> oo} n || n alpha || = 0
(for irrational alpha that are not badly approximable).
If we rewrite Littlewood's conjecture:
lim inf_{n-> infinity} ( n ||n alpha|| || n beta|| ) = 0.
[ any alpha, beta in [0, 1] ],
then the following cases are true:
(a) when alpha is rational
(b) when alpha is irrational and not "badly approximable"
(c) when beta is rational
(d) when beta is irrational and not "badly approximable".
The cases that remain are the hardest to deal with:
when alpha and beta are both irrational and both
badly approximable by rational numbers as defined at
MathWorld:
< http://mathworld.wolfram.com/BadlyApproximable.html >.
I've been doing computer experiments to test for how many
consecutive values of 'n' starting at n=1 one can keep
the numbers n ||n alpha|| || n beta|| >= C, for some positive
C such as 0.001 or more. Here, alpha and beta are chosen
pseudo-randomly in [0, 1] and C>0 is fixed.
In mathematical notation,
Find N as large as possible such that, for some alpha, beta in [0, 1],
n || n alpha|| || n beta || >= C, for all integers n with 1<= n <= N.
Note: C is a given constant.
For C = 0.09, N >= 49. For C = 0.08, N >= 107.
For C = 0.07, N >= 489, using
alpha = 0.76280657416324324784 and beta = 0.63802788485904796638.
If C, alpha and beta are fixed, then Littlewood's Conjecture
implies the existence of a positive integer M_{alpha, beta} such that:
M_{alpha,beta} ||M_{alpha,beta} alpha|| ||M_{alpha, beta} beta|| < C.
I've been wondering about uniform bounds M, independent
of alpha and beta:
Let C >0 be a fixed positive real number. If we assume
Littlewood's Conjecture, does there exist a positive
integer M such that, for all alpha, beta in [0, 1],
min_{1<= n <= M} n || n alpha|| || n beta || < C ?
The idea is that even though Littlewood's Conjecture might be true,
by varying alpha and beta, one might get arbitrarily
long sequences: { n || n alpha|| || n beta || }_{n = 1 ... N},
all of whose elements are greater than 1/(10^100), for example.
[The C = 1/(10^100) case ].
In any case, it certainly appears that it's not too hard with
a computer to find N which grow rapidly as C decreases, as
above:
For C = 0.09, N >= 49. For C = 0.08, N >= 107.
For C = 0.07, N >= 489.
Also,
alpha = 0.29343792080787903904, beta = 0.94866752977247887323 then
for N = 7,000,000 ,
n || n alpha|| || n beta || > 0.015 for 1<= n <= N.
Thus, C ~= 0.01 or less leads to very long sequences
and takes a substantial amount of time to find/check.
Values of C around 0.07 seem more reasonable for
experimentation for now.
David Bernier
David Bernier
Maybe one can use the sequential compactness of [0, 1]x[0, 1]
together with the fact that the functions
min_N: [0,1]x[0,1] -> R defined by
min_N(alpha, beta) = min_{ 1<= n <= N} n || n alpha|| || n beta ||,
are continuous from [0, 1]^2 to R
[for N a positive integer], to show that Littlewood's Conjecture
implies that for any C>0, there is an M not depending
on alpha and beta such that:
min_{ 1<= n <= M} n || n alpha|| || n beta || < C .
Perhaps someone can comment on whether this might work.
Virgil
David Bernier <davi...@videotron.ca> wrote:
> "nint", which is used at MathWorld, denotes the nearest
> integer function.
How does it deal with the half-integers?
David Bernier
Right. I didn't think about that. I posted a link to MathWorld
because it has an article on "Badly Approximable" irrational
numbers.
So suppose n >= 0 is an integer, and the question is
how nint(n + 1/2) is defined (nearest integer to
n + 1/2). Both n and n+1 are at a distance 1/2 from
n + 1/2. So
| nint(n+1/2) - (n+1/2)| = 1/2 , and this is true
regardless of whether nint(n+1/2) is defined as
n or as n+1.
MathWorld has this to say about nint:
"Since this definition is ambiguous for half-integers, the additional
rule that half-integers are always rounded to even numbers is usually
added in order [...]"
Cf.:
< http://mathworld.wolfram.com/NearestIntegerFunction.html > .
Wikipedia has an article on this open conjecture:
< http://en.wikipedia.org/wiki/Littlewood_conjecture > .
Also, Timothy Gowers has posted quite a lot on his Web Blog here
(with comments):
<
http://gowers.wordpress.com/2009/11/17/problems-related-to-littlewoods-conjecture-2/
>
Alec Edgington, ( December 2, 2009) posted
two related graphics:
< http://www.obtext.com/littlewood/t1000_02.png >
He writes on Gowers's Blog:
"Edit: the second plot is of
min_{ n>= 1 : n || nx || || ny || < epsilon}"
where epsilon = 0.02 and x, y range over [0, 1]x[0, 1].
Also, from December 2, Edgington explains:
" [...] on a logarithmic scale where high values correspond to bright
pixels: ".
So when a "very large" n is needed in order that
n || nx || || ny || < 0.02, the point (x,y) will be
"very bright".
Here are my latest computations for C = 0.06:
n alpha beta
833 0.17280915302268556690 0.55942500902033840164
1024 0.69821934733652751083 0.44042962285186438142
1239 0.78298859594376504442 0.62873273699707146652
1653 0.23472148069703919507 0.56442619442208041955
2792 0.60923809495822096589 0.72958364822618209712
For each line, one should have:
k || k alpha || || k beta || >= 0.06 for 1<= k <= n , but
(n+1) || (n+1) alpha || || (n+1) beta || < 0.06 .
David Bernier
David Bernier
There is a paper by Pollington and Velani in Acta Math., vol. 185 (2000),
pp. 287-306 which shows that the Littlewood Conjecture holds
for a "large" subset of [0, 1] x [0,1] , in terms of Hausdorff
dimension, and also which gives a rate of decrease of
n || n alpha|| || n beta|| which holds for
infinitely many n.
Specifically, they are only concerned with "Badly approximable"
irrationals and their Theorem 1 is as follows:
Theorem (Pollington/Velani):
Let alpha in [0, 1] be a Badly Approximable irrational number.
Then there exists a set of badly approximable irrational
numbers G(alpha), which depends on alpha, and such that:
(a) G(alpha) has Hausdorff dimension 1.
(b) For any beta in G(alpha), it is the case that:
q || q alpha || || q beta || <= 1/log(q)
for infinitely many positive integers q.
---
It's interesting to have a rate of decrease of 1/log(q).
From what I've read, the set of q such that
q || q alpha || || q beta || <= 1/log(q) is
of course infinite, but could potentially
be very sparse. So returning to C = 0.06,
for alpha and beta as in the Theorem of Pollington
and Velani,
1/log(q) < 0.06 if q > 18,000,000 (for example).
But even if a positive integer q satisfies
1/log(q) < 0.06, this in no way guarantees that
q || q alpha || || q beta || <= 1/log(q).
For all we know, the q satisfying
q || q alpha || || q beta || <= 1/log(q) < 0.06
could form a sparse set.
So this doesn't seem to illuminate the question of
how large N can possibly be if
n || n alpha || || n beta || >= 0.06 for all integers n
such that 1<= n <= N, and where one is free to choose
alpha and beta to get N as large as possible ...
David Bernier
David Bernier
There was a bug in my C program, unfortunately, so that in fact
k || k alpha || || k beta || >= 0.06 for 1<= k < n , but
n || n alpha || || n beta || < 0.06 .
I checked this independently with PARI-gp for the line
with "n = 2792".
Let g(k) = k || k alpha|| || k beta || , for fixed alpha, beta in [0, 1].
I continued the search for N as large as possible for which
g(k) >= 0.06 for all k such that 1 <=k<= N by choosing
alpha and beta pseudo-randomly.
For alpha = 0.56052015125412777644 and beta = 0.7340125156311948479
I find with PARI-gp with precision set to 100 digits
that for N = 9913, the minimum of g(k) for 1<=k <= N is
attained for k = 537, where g(k) ~= 0.060041 .
In PARI-gp:
Initially, I set z = 2.0 .
? for(k=1,9913,if(g(k)<z,z=g(k))) // PARI-gp expression entered
Now, z = 0.060041259748985071537148714594443964172 .
David Bernier
David Bernier
> David Bernier wrote:
[...]
>> Here are my latest computations for C = 0.06:
>>
>> n alpha beta
>> 833 0.17280915302268556690 0.55942500902033840164
>> 1024 0.69821934733652751083 0.44042962285186438142
>> 1239 0.78298859594376504442 0.62873273699707146652
>> 1653 0.23472148069703919507 0.56442619442208041955
>> 2792 0.60923809495822096589 0.72958364822618209712
>>
>> For each line, one should have:
>>
>> k || k alpha || || k beta || >= 0.06 for 1<= k <= n , but
>>
>> (n+1) || (n+1) alpha || || (n+1) beta || < 0.06 .
>
> There was a bug in my C program, unfortunately, so that in fact
>
> k || k alpha || || k beta || >= 0.06 for 1<= k < n , but
> n || n alpha || || n beta || < 0.06 .
>
> I checked this independently with PARI-gp for the line
> with "n = 2792".
>
> Let g(k) = k || k alpha|| || k beta || , for fixed alpha, beta in [0, 1].
>
> I continued the search for N as large as possible for which
> g(k) >= 0.06 for all k such that 1 <=k<= N by choosing
> alpha and beta pseudo-randomly.
>
> For alpha = 0.56052015125412777644 and beta = 0.7340125156311948479
Using Contfrac from a WIMS server,
( http://wims.auto.u-psud.fr/wims/wims.cgi )
the number alpha = 0.56052015125412777644 has 19 out of
its first 20 non-zero continued fraction terms equal to 1, 2 or 3
and just one term equal to 4.
This suggests that "good" alpha and beta have a
"distribution" of terms unlike that of random
irrationals, and maybe this could give
better computer search methods.
David Bernier
I've changed from C = 0.06 to C = 0.05 . The question is still to
find an integer N as large as possible for which
k || kx || || ky|| >= C, for all integers k such that 1<= k <= N.
For C = 0.05, I find that N = 110,103 is possible using
x = 0.7377661109835727137 and
y = 0.38309233482355924035 .
In a sense, k = 110104 is a hurdle when trying to go further,
while keeping (x, y) in a small neighborhood of
(0.7377661109835727137, 0.38309233482355924035). (***)
By making a very tiny adjustment to x and y as above,
k || kx || || ky|| remains near its value of about 0.0200542
for k = 110,104 . A slightly too large "adjustment" to x and y
might fix k || kx || || ky|| , for k = 110,104 but then up till now,
D(k', x, y) := k' || k'x || || k'y|| < 0.05 .
The new algorithm I use chooses terms for continued fractions using a
probability law close
to
P( 1) = 1/2
P(2) = 1/4
P(3) = 1/8
P(4) = 31/256
P(5) = 1/256 .
I haven't computed the terms in the c.f. expansion of x and y as in
(***) above.
So maybe there are patterns in the c.f. terms that could be
exploited to find large N for C = 0.05 and below ...
David Bernier
=========== PARI-gp said: ===================
? z = 2.0
%13 =
2.0000000000000000000000000000000000000000000000000000000000000000000000000000000
? for(k=1,110103,if(g(k)<z,z=g(k)))
? z
%14 =
0.050474248124740145729189816450245165000000000000000000000000000000000000000000000
? x
%15 =
0.73776611098357271370000000000000000000000000000000000000000000000000000000000000
? y
%16 =
0.38309233482355924035000000000000000000000000000000000000000000000000000000000000
David Bernier
for one or more values of k'<110104, which depend
on the re-assignments of x and y in the program:
x = x_old + delta_x
y = y_old + delta_y
with delta_x and delta_y pseudo-random floating point numbers
in an interval [- epsilon, epsilon] ,
where epsilon ~= 1/(10^4) tends to produce relatively short
sequences D(1, x, y) , ... D(M, x, y) with all values at least C = 0.05,
and epsilon ~= 1/(10^8) tending to leave D(110104, x, y) < 0.05 .
David Bernier
For C = 0.05, I got as far as N = 193,545
using x = 0.29521731066981802448 and y = 0.73023885423838781654.
The C program finds min_{1<=k<=193545} k ||kx|| ||ky|| > 0.05.
For C=0.04, I got as far as N = 258,301 where the C program
finds min_{1<=k<=258301} k ||kx|| ||ky|| ~= 0.042877,
for x = 0.41083263641842546660, y = 0.26210552951303559645.
I expect larger N are possible for C=0.04.
Littlewood conjectured that
liminf_{k-> oo} k ||kx|| ||ky|| = 0 for any x, y in [0,1].
Through advanced work in ergodic theory, it's been shown
that the set of points (x,y) for which
liminf_{k-> oo} k ||kx|| ||ky|| > 0 is either empty
or has Hausdorff dimension zero [ Annals of Mathematics,
Einsiedler, Katok and Lindenstrauss]:
< http://annals.princeton.edu/annals/2006/164-2/p04.xhtml >
I've been wondering for what kind of function f(k)
defined on [0, oo) or at least [a, oo), some
positive a, one could find x, y in [0, 1] such that
liminf_{k-> oo} kf(k) ||kx|| ||ky|| > 0 ?
For example, if we let f(k) = log(k) for k>1,
do there exist x, y in [0, 1] with
liminf_{k-> oo} k log(k) ||kx|| ||ky|| > 0 ?
Earlier, I mentioned a Theorem of Pollington and Velani:
Theorem :
Let alpha in [0, 1] be a Badly Approximable irrational number.
Then there exists a set of badly approximable irrational
numbers G(alpha), which depends on alpha, and such that:
(a) G(alpha) has Hausdorff dimension 1.
(b) For any beta in G(alpha), it is the case that:
q || q alpha || || q beta || <= 1/log(q)
for infinitely many positive integers q.
---
That would mean:
log(q) q || q alpha || || q beta || <= 1 for
infinitely many q, so
lim_inf {q->oo} log(q) q || q alpha || || q beta || <= 1,
so I think that still leaves open the possibility that
for some x, y in [0, 1],
liminf_{k-> oo} k log(k) ||kx|| ||ky|| > 0 ...
David Bernier