help with diophantine approximation.

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

help with diophantine approximation.

Okay, I need to find the two numbers a and b that maximize min(||a||||b||,2||2a||||2b||,3||3a||||3b||,...,7||7a||||7b||), where ||a|| is the distance to the nearest integer, for example, ||0.9||=0.1, ||1.3||=0.3, etc. Can you help?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: help with diophantine approximation.

Have you tried solving simpler problems, like maximizing

min ( <a><b>, 2<2a><2b> )
min ( <a><b>, 2<2a><2b>, 3<3a><3b> )
...

?

(I'm using <a> for your ||a||, since ||a||||b|| is nasty on the eyes ...)

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

Proginoskes wrote:Have you tried solving simpler problems, like maximizing

min ( <a><b>, 2<2a><2b> )
min ( <a><b>, 2<2a><2b>, 3<3a><3b> )
...

?

(I'm using <a> for your ||a||, since ||a||||b|| is nasty on the eyes ...)

I'll use your notation, it does look a lot nicer. I have maximized min( <a><b>, 2<2a><2b> ), it turns out that (for this problem) a=b=(4-sqrt(2))/7, and for maximizing min ( <a><b>, 2<2a><2b>, 3<3a><3b> ), a=2/7, b=3/7, and these values for for a and b work up to min( <a><b>, 2<2a><2b>, ... , 6<6a><6b> ), but for obvious reasons it does not work for min( <a><b>, 2<2a><2b>, ... , 7<7a><7b> ). I'm also interested in working out the maximization with more terms.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 945
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: help with diophantine approximation.

This is interesting. Numerical approximation suggests (2/9, 4/9) for the problem up to 7. This is fine for 8, too, whereas 9 gives (6/26,11/26)=(3/13,5.5/13) and that stays constant up to max=12.

We have
3-6 -> 2/7, 3/7
7-8 -> 2/9, 4/9
9-12 -> 3/13, 5.5/13 or 6/26, 11/26
13-18 -> 7/19, 8/19
19-20 -> no idea, a=0.275787 and b=0.382332 but don't trust the last digit
21-22 -> a=0.31128 and b=0.218001
23-25, 26-27, 28-30 are the following groups.

Edit: Strange typo fixed
Last edited by mfb on Sun May 20, 2012 10:52 am UTC, edited 1 time in total.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

mfb wrote:This is interesting. Numberical approximation suggests (2/9, 4/9) for the problem up to 7. This is fine for 8, too, whereas 9 gives (6/26,11/26)=(3/13,5.5/13) and that stays constant up to max=12.

We have
3-6 -> 2/7, 3/7
7-8 -> 2/9, 4/9
9-12 -> 3/13, 5.5/13 or 6/26, 11/26
13-18 -> 7/19, 8/19
19-20 -> no idea, a=0.275787 and b=0.382332 but don't trust the last digit
21-22 -> a=0.31128 and b=0.218001
23-25, 26-27, 28-30 are the following groups.

a=2/9, b=4/9 is a local maximum of the function, but it is not the correct value. The value of min( <a><b>, 2<2a><2b>, ... , 7<7a><7b> ) for those values is 8/81<0.1, but I have found (this is not optimal) a=0.265, b=0.3876 gives a value of approximately 0.1001>0.1. By the way, what is the numerical approximation you are using? I have found that a maximum of the function occurs when three of the minimized values are equal, or algebraically: m<ma><mb>=n<na><nb>=p<pa><pb>, this is satisfied by your answer, which is probably why your numerical method went to that solution.
Last edited by tomtom2357 on Fri Feb 10, 2012 11:34 am UTC, edited 1 time in total.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

jaap
Posts: 2074
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: help with diophantine approximation.

Since we can add any integer to a or b, change their sign, or swap them, we can assume w.l.o.g. that 0<=a<=b<=0.5 .

For n=3...6 I also get 2/7 and 3/7.
For n=7...14 I get 0.26797254107 and 0.4119235539. The first number seems to be 2-sqrt(3), but I don't recognise the second.
For n=15...16 I get 0.26923076923 and 0.4112903224. The first number seems to be 7/26, but again I don't recognise the second.
For n=17 I get 0.26923076923 and 0.388888888. The first number seems to be 7/26, the second 7/18.

I just used a random starting point plus hill-climbing to reach a local maximum, then repeat that 100000 times.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

jaap wrote:Since we can add any integer to a or b, change their sign, or swap them, we can assume w.l.o.g. that 0<=a<=b<=0.5 .

For n=3...6 I also get 2/7 and 3/7.
For n=7...14 I get 0.26797254107 and 0.4119235539. The first number seems to be 2-sqrt(3), but I don't recognise the second.
For n=15...16 I get 0.26923076923 and 0.4112903224. The first number seems to be 7/26, but again I don't recognise the second.
For n=17 I get 0.26923076923 and 0.388888888. The first number seems to be 7/26, the second 7/18.

I just used a random starting point plus hill-climbing to reach a local maximum, then repeat that 100000 times.

That looks like it is the right answer, I haven't found any value that beats that, but can you prove that these are the optimal values? Also, I have a method that can use your approximate values to give an exact value given that the approximation is accurate enough, can you give me some more values? The values for 7<=n<=14 are a=(115+sqrt(16881))/914, b=(4133-sqrt(16881))/9718, using your approximation and my method, and these values almost exactly match your approximation.
Last edited by tomtom2357 on Mon Feb 13, 2012 5:59 am UTC, edited 1 time in total.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

jaap
Posts: 2074
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: help with diophantine approximation.

tomtom2357 wrote:That looks like a it is the right answer, I haven't found any value that beats that, but can you prove that these are the optimal values? Also, I have a method that can use your approximate values to give an exact value given that the approximation is accurate enough, can you give me some more values? The values for 7<=n<=14 are a=(115+sqrt(16881))/914, b=(4133-sqrt(16881))/9718, using your approximation and my method, and these values almost exactly match your approximation.

a=0.26797254105689, b=0.41192355396933 is about as accurate as I can get it right now (their last digit may be one more or less). It isn't 2-sqrt(3), but it seems to me unlikely to be such a complicated expression as you gave.

Edit: No, you're entirely correct. These a and b are the solutions to 4(4a-1)(2-4b) = 5(5a-1)(5b-2) = 7(2-7a)(3-7b), which is when three of the terms in the Min() expression are equal. I think it will always be the case that at a (local) optimum at least three of the terms are equal (otherwise you can perturb a,b to get a better minimum). To prove it is optimal you would probably have to check all triplets, and for all possible nearest integers.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

jaap wrote:a=0.26797254105689, b=0.41192355396933 is about as accurate as I can get it right now (their last digit may be one more or less). It isn't 2-sqrt(3), but it seems to me unlikely to be such a complicated expression as you gave.

Edit: No, you're entirely correct. These a and b are the solutions to 4(4a-1)(2-4b) = 5(5a-1)(5b-2) = 7(2-7a)(3-7b), which is when three of the terms in the Min() expression are equal. I think it will always be the case that at a (local) optimum at least three of the terms are equal (otherwise you can perturb a,b to get a better minimum). To prove it is optimal you would probably have to check all triplets, and for all possible nearest integers.

That pretty much sums up my method, if your approximations are accurate enough, then I can see which three terms in the min expression are equal. How about we call the maximum value of min( <a><b>,2<2a><2b>,3<3a><3b>,...,n<na><nb>) f(n), and the values of a and b that accomplish this fa(n) and fb(n). I am trying to use these results to prove the littlewood conjecture, which states that lim n->infinityf(n)=0, so I need as many values of this function as you can give me. As far as I know, no one has worked on the problem from this angle before, so it might just work. Thanks for your help!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 945
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: help with diophantine approximation.

tomtom2357 wrote:a=2/9, b=4/9 is a local maximum of the function, but it is not the correct value. The value of min( <a><b>, 2<2a><2b>, ... , 7<7a><7b> ) for those values is 8/81<0.1, but I have found (this is not optimal) a=0.265, b=0.3876 gives a value of approximately 0.1001>0.1. By the way, what is the numerical approximation you are using? I have found that a maximum of the function occurs when three of the minimized values are equal, or algebraically: m<ma><mb>=n<na><nb>=p<pa><pb>, this is satisfied by your answer, which is probably why your numerical method went to that solution.

Hmm... I did not really think about the structure of the problem. It is right that the area for (a,b) can have a lot of local minima, all with
I think it will always be the case that at a (local) optimum at least three of the terms are equal (otherwise you can perturb a,b to get a better minimum).

That gives a possibility to solve the systems with O(n^4): Take all O(n^3) triplets of values within the min(...)-expression, let them be equal, solve for a,b, check if other terms are smaller (O(n)). This search method gives all local maxima. Keep the largest one.
As we always have the same structure in the equations, I think that all solutions can be written as (x+sqrt(y))/z with integer x,y,z.

Edit: Hmm... tricky thing. Assuming you have to check O(n) different cases for all, it increases to O(n^7). Not polynomial with the length of n, but that was not required, right?
Last edited by mfb on Sat Feb 11, 2012 12:09 am UTC, edited 2 times in total.

jaap
Posts: 2074
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: help with diophantine approximation.

mfb wrote:That gives a possibility to solve the systems with O(n^4): Take all O(n^3) triplets of values within the min(...)-expression, let them be equal, solve for a,b, check if other terms are smaller (O(n)). This search method gives all local maxima. Keep the largest one.

You're missing a few factors n there because you have to split up into cases depending on whether k*a or k*b are rounded up or down and to which integer.
Regardless, it would not be a polynomial algorithm, since it is usually measured w.r.t. the size of the input, i.e. the number of digits/bits in n.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

jaap wrote:
mfb wrote:That gives a possibility to solve the systems with O(n^4): Take all O(n^3) triplets of values within the min(...)-expression, let them be equal, solve for a,b, check if other terms are smaller (O(n)). This search method gives all local maxima. Keep the largest one.

You're missing a few factors n there because you have to split up into cases depending on whether k*a or k*b are rounded up or down and to which integer.
Regardless, it would not be a polynomial algorithm, since it is usually measured w.r.t. the size of the input, i.e. the number of digits/bits in n.

I think that I have a way to slightly decrease the time required. If a previous solution does not work for higher n (for example the solution for n=7 works up to n=14, but doesn't work for n=15) then the three terms in the Min expression that are equal will include n<na><nb>, this will narrow the search area down a bit.

Edit: Actually, we can do a lot better than this, just use jaap's algorithm to approximate the solutions to within 1/1000 of the correct value, and I will know exactly which terms are equal in the min expression and from there the the solution is easy.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

PM 2Ring
Posts: 3621
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: help with diophantine approximation.

Sorry, I can't offer any constructive help on this problem.

mfb wrote:As we always have the same structure in the equations, I think that all solutions can be written as (x+sqrt(y))/z with integer x,y,z.

I guess that makes sense, but are you sure about that? I tried looking up 0.41192355 on Plouffe's Inverter, but the best match it got was 0.4119235534824224 = log(32077/21247), and it's usually pretty good with simple quadratic expressions.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

PM 2Ring wrote:Sorry, I can't offer any constructive help on this problem.

mfb wrote:As we always have the same structure in the equations, I think that all solutions can be written as (x+sqrt(y))/z with integer x,y,z.

I guess that makes sense, but are you sure about that? I tried looking up 0.41192355 on Plouffe's Inverter, but the best match it got was 0.4119235534824224 = log(32077/21247), and it's usually pretty good with simple quadratic expressions.

I think that mfb is right, and Plouffe's Inverter is unlikely to come up with (4133-sqrt(16881))/9718 no matter how accurate your approximation is.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

PM 2Ring
Posts: 3621
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: help with diophantine approximation.

Fair enough.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

The reason that I think mfb is right is that the equations that set three of the terms in the min expression equal are quadratic, and so it makes sense that a and b are quadratic irrational (or rational, in the case of 3<=n<=6).
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

mfb
Posts: 945
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: help with diophantine approximation.

tomtom2357 wrote:Edit: Actually, we can do a lot better than this, just use jaap's algorithm to approximate the solutions to within 1/1000 of the correct value, and I will know exactly which terms are equal in the min expression and from there the the solution is easy.

japp's numerical search will have a similar issue, but maybe with better run-time. It has to check O(n^3) regions (?) with O(n) calculations each. With random starting values, I would expect ~O(n^4*log(n)) to find the global minimum.

>> The reason that I think mfb is right is that the equations that set three of the terms in the min expression equal are quadratic, and so it makes sense that a and b are quadratic irrational (or rational, in the case of 3<=n<=6).
That was my reasoning as well.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

Notation: Define fk(x,y)=k<kx><ky>, so that FN(x,y)=mink<=N{k<kx><ky>} is the function to be maximized.

FN(x,y)=0 if either x or y is a rational number with denominator at most N; otherwise FN(x,y)>0. So FN has at least one maximum in each of these rectangular "Farey regions", whose x and y coordinates bounded by consecutive fractions in the order-N Farey sequence. There are ~N2/3 such fractions, so there are O(N4) such regions, and so jaap's hill-climbing algorithm needs to run with at least that many initial conditions to find each local maximum.

I think it's true that each Farey region has exactly one maximum. It's true at least in the cases I've considered, but I haven't got a simple proof. It's not the case that each maximum is at the intersection of three of the individual fk. (The cases N=1 and N=2 are trivial counterexamples; more generally it looks like the maxima along the diagonal x=y are at smooth hyperbolic intersections of two of the fk.) For N>2 I haven't found any cases where the global maximum of FN is at one of these maxima, but I don't know that it can't happen.

But considering up to three of the individual fk should suffice to find all of the candidate maxima, so this gives an O(N7) algorithm to find the maximum (counting finding each candidate maximum as O(1), which is probably not quite right). It's easier to find the intersections if you subdivide along not just the order-N Farey fractions, but half of each order-N Farey fraction: this makes each fk a polynomial (of the form axy+bx+cy+d, i.e. a hyperbola).

This fairly rapidly gets unwieldy. One way to prune a lot of the O(N4) Farey regions is to find an upper bound for FN on the region. Each of the fk is bilinear, so it is bounded by its values on the four corners of the region, and
FN(x,y) <= mink<=N maxcorners(xc,yc) fk(xc,yc).
So we can start with an O(N5) search over all these regions to find the bounds, then sort by decreasing size of the bound and do the O(N3) check within the regions in this order, stopping when the current best is better than the remaining upper bounds. (At N=30 this means checking just 11 of 38781 regions, so that's a pretty good reduction. This lets you get up to N~60. Currently I only check for the maxima among three-fk intersections; for 48<N<63 I get a maximum of
(3094 (12788836+1547 sqrt(144153949)))/1099613344833
at
(x,y)=((274165-sqrt(144153949))/972018,(945304-sqrt(144153949))/2262537).
I have no idea how this pruned search scales asymptotically with N.)

As tomtom2357 noted, if you're tabulating these values over N then you can first check the maximum for FN-1; if it works then it is necessarily the maximum for FN as well. However: if not, you can't necessarily assume that fN will be a constraint in the new maximum; there could be other maxima using only earlier constraints that were not cut off by fN. (This happens at N=17; the maximum of 5/52 at (7/26,7/18) is at the intersections of f3, f5, f15.)

I can think of some other possible pruning techniques, but I haven't tried them.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

I think that Fn(x,y)=fn(x,y) or Fn(x,y)=Fn-1(x,y) (which is easy to check), which may help with the algorithms.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

tomtom2357 wrote:I think that Fn(x,y)=fn(x,y) or Fn(x,y)=Fn-1(x,y) (which is easy to check)
True...
which may help with the algorithms.
... maybe. You can avoid recalculating intersection points if you cache the previously-computed intersections (at a cost of more memory usage). Finding bounds on all of the Farey regions to allow pruning scales worse than the intersection computation (at N=49 about 85% of the time is spent in creating the ordered list of regions to search, versus actually finding the maxima in these regions), so it's not the first thing to optimize.

It is probably worthwhile to use previously-computed lists at smaller N as looser upper bounds (each region covering multiple order-N Farey regions), only subdividing the ones which pass the current thresholds. I haven't tried that yet.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

Well, how about we narrow the search are a bit: the values of a and b must be>1/(2n), I don't know if this helps or not.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

tomtom2357 wrote:Well, how about we narrow the search are a bit: the values of a and b must be>1/(2n), I don't know if this helps or not.
Well, for the exhaustive search of Farey regions (the approach described in my first post), there are O(n4) regions to be searched, and this only removes O(n2) of them, so that won't change the runtime much. The insight might be useful, though, if it can be extended to rule out enough other regions.

I've been working on a priority-queued version (described in my second post). This is definitely much faster as long as memory is available to hold the queue. It's still got a bug in it though.

What are you hoping to get from these maxima? (I know you're thinking about the Littlewood conjecture, but is there a specific question you're hoping these values will answer?)

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

eta oin shrdlu wrote:
tomtom2357 wrote:Well, how about we narrow the search are a bit: the values of a and b must be>1/(2n), I don't know if this helps or not.
Well, for the exhaustive search of Farey regions (the approach described in my first post), there are O(n4) regions to be searched, and this only removes O(n2) of them, so that won't change the runtime much. The insight might be useful, though, if it can be extended to rule out enough other regions.

I've been working on a priority-queued version (described in my second post). This is definitely much faster as long as memory is available to hold the queue. It's still got a bug in it though.

What are you hoping to get from these maxima? (I know you're thinking about the Littlewood conjecture, but is there a specific question you're hoping these values will answer?)

Well, if a can find a pattern in these numbers that proves that they approach 0, then that will prove the conjecture. It is easy to prove that 0<Fn<Fn-1, which therefore means that limn->infinityFn exists. If it is 0, then the littlewood conjecture follows, if it is not 0, then the negation of the littlewood conjecture follows. I just want to find the limit of the series.

Also, if you can find a first good guess, then that can narrow the search area down a by a lot. For example, even if jaap's first guess for n=7 is wrong, then I can say that the maximum must be>0.1, and from there 0.2<a<b<0.45, which narrows the search are down by a lot.

So my idea of an optimal algorithm would start by checking if the previous solution worked, then check the cases where a,b are integers divided by 100. Then, narrow the search area down using those values. It would then check the remaining regions for the optimal value.

Edit: Actually, a good first approximation for Fn(x,y) (for small n) is 8/(m2), where m is the first odd number after n. This works by setting x=2/m, y=4/m.

Edit 2: To prevent from double posting, I will post my idea of how to narrow the search area. First, for n=7, I will assume without loss of generalization, that 0<a<b<0.5. I know that Fn>0.1, so therefore 2<2a><2b>>0.1, but <2a><0.5 no matter what a is, so <2b>>0.1, so b<0.45. Now we also know that ab>0.1, so since b<0.45, a>2/9.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

tomtom2357 wrote:
eta oin shrdlu wrote:
tomtom2357 wrote:Well, how about we narrow the search are a bit: the values of a and b must be>1/(2n), I don't know if this helps or not.
Well, for the exhaustive search of Farey regions (the approach described in my first post), there are O(n4) regions to be searched, and this only removes O(n2) of them, so that won't change the runtime much. The insight might be useful, though, if it can be extended to rule out enough other regions.

I've been working on a priority-queued version (described in my second post). This is definitely much faster as long as memory is available to hold the queue. It's still got a bug in it though.

What are you hoping to get from these maxima? (I know you're thinking about the Littlewood conjecture, but is there a specific question you're hoping these values will answer?)

tomtom2357 wrote:Well, if a can find a pattern in these numbers that proves that they approach 0, then that will prove the conjecture. It is easy to prove that 0<Fn<Fn-1, which therefore means that limn->infinityFn exists. If it is 0, then the littlewood conjecture follows, if it is not 0, then the negation of the littlewood conjecture follows. I just want to find the limit of the series.
OK. Finding a pattern seems like it will probably be difficult.

tomtom2357 wrote:Also, if you can find a first good guess, then that can narrow the search area down a by a lot. For example, even if jaap's first guess for n=7 is wrong, then I can say that the maximum must be>0.1, and from there 0.2<a<b<0.45, which narrows the search are down by a lot.

tomtom2357 wrote:So my idea of an optimal algorithm would start by checking if the previous solution worked, then check the cases where a,b are integers divided by 100. Then, narrow the search area down using those values. It would then check the remaining regions for the optimal value.
This was the basis for the first algorithm I wrote. The problem with this is that it scales poorly with n; Fn has O(n4) local maxima, so for n=7 a 50x50 subdivision will work, but for n=20 you need more than 50x50 to see all of the local maxima. (Of course, depending on how large an n you're interested in, this may be sufficient.)

You can save computation by doing a local maximization within each of these O(n4) regions (for a roughly O(n5) algorithm); I was able to get to roughly n=50 this way.

tomtom2357 wrote:Edit: Actually, a good first approximation for Fn(x,y) (for small n) is 8/(m2), where m is the first odd number after n. This works by setting x=2/m, y=4/m.
This is not a very good approximation except for very small n; even at n=200000 the maximum is above 0.05, not 10-9.

tomtom2357 wrote:Edit 2: To prevent from double posting, I will post my idea of how to narrow the search area. First, for n=7, I will assume without loss of generalization, that 0<a<b<0.5. I know that Fn>0.1, so therefore 2<2a><2b>>0.1, but <2a><0.5 no matter what a is, so <2b>>0.1, so b<0.45. Now we also know that ab>0.1, so since b<0.45, a>2/9.
Right. You can do that for each of the k<ka><kb> functions, but as k increases you get more and more disjoint regions, so keeping track of these efficiently might not be trivial.

The approach I described in my first post was a simplification of this idea: I computed bounds for all of the order-n Farey regions and then maximized over each region (in decreasing size of bound) until finding a maximum larger than all remaining bounds. This let me get to about n=60 analytically and n=350 numerically; unfortunately there are a lot (O(n4)) of these regions, and so memory starts to become an issue.

You can save on memory by not subdividing all of the rectangles to order n; instead, just subdivide rectangles whose bounds are large enough to be possible locations of maxima--this is what I was describing in my second post, and I have it working numerically now; I haven't had time to code a fully analytic version. This does a pretty good job of reducing memory usage, and it gets (numerical) maxima up to n=100000 in about an hour.

On any given Farey region you can also usually ignore most of the fk; these are bounded by their values at the corners of the region, so if you find fa<fb everywhere on the region then you can ignore fb since fa is always a tighter constraint. This helps a lot to reduce the O(n3) number of intersections to find with a purely analytic approach (it helps numerically, too, but there you're just doing function evaluations, which are O(n), so the growth isn't so bad).

So anyway, I have what I think are the maxima of Fn up to n=100000, found approximately using numerical maximization and then found exactly using analytic approaches. (My numerical maximization routine is kind of sloppy right now and could conceivably miss a maximum, so these are not guaranteed.)

Here are the numerical values I get:

Code: Select all

n                x                        y                    F_n(x,y)3       0.42857142857142857143  0.28571428571428571429  0.122448979591836734697       0.41192355396933553342  0.26797254105688980989  0.1013092827155876258215      0.41129032258064516129  0.26923076923076923077  0.09770471464019851116617      0.38888888888888888889  0.26923076923076923077  0.09615384615384615384618      0.41096127069393081320  0.26986608525108528004  0.09572763409529911258822      0.38709677419354838710  0.26881720430107526882  0.09365244536940686784626      0.38768758439569057200  0.26441346412356091000  0.09363048576099189160534      0.38771085758397866871  0.26426503821669888769  0.09283628503166597140649      0.41250047498531451088  0.26970548608343522189  0.08824589981202177213263      0.38662941037604381527  0.26409015885919449177  0.08389644269425772014375      0.38658974759034248408  0.26409010612154114942  0.083609996016538327379106     0.42052266316465889623  0.23309613952770191772  0.082042513469911944733107     0.41318433921561916293  0.27049686684699377282  0.079657965303179234655122     0.41319277879547616864  0.27047887244054102580  0.078817091947903354571196     0.42450414802312009610  0.37191530230868703680  0.077358907019254197086285     0.36197807767768786265  0.23718600815947563265  0.074361119822964258315312     0.36197796123593608164  0.23719163571675680656  0.074356465162087371279384     0.41315549934923924308  0.27050377190776510246  0.072141955211891854199695     0.41315551994498074115  0.27050463033571461004  0.071409811306328217718973     0.41315555897072054681  0.27050473186119873817  0.0702232979334406691601268    0.41315555819145344156  0.27050509952793400636  0.0701995872051622975581353    0.43968316595550786279  0.17824998518839328044  0.0693080338353128130622777    0.42460862747118442221  0.37813036402909279967  0.0672727155673087416863641    0.42460839022295384501  0.37813036380254671437  0.0672289119831361865505231    0.42460839045928670434  0.37813039599468557161  0.0671254098428533601745551    0.39186184898804523886  0.29195611042829371811  0.0650241733376857900826316    0.39186154875742867516  0.29195614437104387433  0.0647527350146747937256477    0.39186154880125592524  0.29195613487482405949  0.06465961178614247084410690   0.44039160329412810974  0.26899500698009196694  0.06339142220557413233012398   0.42540258692288390211  0.22902594850417053235  0.06148594594496796215615959   0.42540258460455583801  0.22902594837969366770  0.06103007349446050082422045   0.42540258459909101293  0.22902594837940018156  0.06102899872612262984524840   0.41877915883832255612  0.26802396122196505959  0.05941735117957662503328046   0.41877915883835302970  0.26802396157693953880  0.05941734998712171184429863   0.38363751580916999817  0.28052541705225926613  0.05836474385648762644635020   0.38363751581041148833  0.28052541740141213341  0.05836474303227621204982677   0.41877915937794298016  0.26802394184418440662  0.05820506588813627063287022   0.46275847322715482431  0.27975230871557415907  0.05764667921863549484488839   0.46275847310678965129  0.27975230871553084455  0.057646661544032551952
Analytic values available on request.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

eta oin shrdlu wrote:Here are the numerical values I get:

Code: Select all

n                x                        y                    F_n(x,y)3       0.42857142857142857143  0.28571428571428571429  0.122448979591836734697       0.41192355396933553342  0.26797254105688980989  0.1013092827155876258215      0.41129032258064516129  0.26923076923076923077  0.09770471464019851116617      0.38888888888888888889  0.26923076923076923077  0.09615384615384615384618      0.41096127069393081320  0.26986608525108528004  0.09572763409529911258822      0.38709677419354838710  0.26881720430107526882  0.09365244536940686784626      0.38768758439569057200  0.26441346412356091000  0.09363048576099189160534      0.38771085758397866871  0.26426503821669888769  0.09283628503166597140649      0.41250047498531451088  0.26970548608343522189  0.08824589981202177213263      0.38662941037604381527  0.26409015885919449177  0.08389644269425772014375      0.38658974759034248408  0.26409010612154114942  0.083609996016538327379106     0.42052266316465889623  0.23309613952770191772  0.082042513469911944733107     0.41318433921561916293  0.27049686684699377282  0.079657965303179234655122     0.41319277879547616864  0.27047887244054102580  0.078817091947903354571196     0.42450414802312009610  0.37191530230868703680  0.077358907019254197086285     0.36197807767768786265  0.23718600815947563265  0.074361119822964258315312     0.36197796123593608164  0.23719163571675680656  0.074356465162087371279384     0.41315549934923924308  0.27050377190776510246  0.072141955211891854199695     0.41315551994498074115  0.27050463033571461004  0.071409811306328217718973     0.41315555897072054681  0.27050473186119873817  0.0702232979334406691601268    0.41315555819145344156  0.27050509952793400636  0.0701995872051622975581353    0.43968316595550786279  0.17824998518839328044  0.0693080338353128130622777    0.42460862747118442221  0.37813036402909279967  0.0672727155673087416863641    0.42460839022295384501  0.37813036380254671437  0.0672289119831361865505231    0.42460839045928670434  0.37813039599468557161  0.0671254098428533601745551    0.39186184898804523886  0.29195611042829371811  0.0650241733376857900826316    0.39186154875742867516  0.29195614437104387433  0.0647527350146747937256477    0.39186154880125592524  0.29195613487482405949  0.06465961178614247084410690   0.44039160329412810974  0.26899500698009196694  0.06339142220557413233012398   0.42540258692288390211  0.22902594850417053235  0.06148594594496796215615959   0.42540258460455583801  0.22902594837969366770  0.06103007349446050082422045   0.42540258459909101293  0.22902594837940018156  0.06102899872612262984524840   0.41877915883832255612  0.26802396122196505959  0.05941735117957662503328046   0.41877915883835302970  0.26802396157693953880  0.05941734998712171184429863   0.38363751580916999817  0.28052541705225926613  0.05836474385648762644635020   0.38363751581041148833  0.28052541740141213341  0.05836474303227621204982677   0.41877915937794298016  0.26802394184418440662  0.05820506588813627063287022   0.46275847322715482431  0.27975230871557415907  0.05764667921863549484488839   0.46275847310678965129  0.27975230871553084455  0.057646661544032551952
Analytic values available on request.

It is very interesting how the Fn for n=6477 is correct for all n up to 10690, and F35020 is accurate for all n up to 82677. I wonder why that is. Also, I looked at their asymptotic distribution, and it looks like Fn=O(ln(ln(n))/ln(n)), which helps a lot, so thanks! And yes, I would like analytic values for the table, they might shed some light on the problem.
Last edited by tomtom2357 on Thu Mar 15, 2012 3:42 am UTC, edited 1 time in total.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

tomtom2357 wrote:Also, I looked at their asymptotic distribution, and I found that the Fn=O(ln(ln(n))/ln(n)), which helps a lot, so thanks!
Please don't write things like this. From tables up to small finite values like n<=100000 you obviously can't in general say anything about the asymptotic distribution, unless you assume or already know the form of the extrapolation. Beware the law of small numbers!

Even assuming that the tables are somehow representative, n=100000 is way way way too small to make meaningful guesses about any asymptotic form with more than one nested log, since log log n grows so incredibly slowly--even n=10100 is too small.

[I'll tabulate the analytic forms for (x,y,Fn(x,y)) sometime soon, maybe later tonight.]

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

eta oin shrdlu wrote:
tomtom2357 wrote:Also, I looked at their asymptotic distribution, and I found that the Fn=O(ln(ln(n))/ln(n)), which helps a lot, so thanks!
Please don't write things like this. From tables up to small finite values like n<=100000 you obviously can't in general say anything about the asymptotic distribution, unless you assume or already know the form of the extrapolation. Beware the law of small numbers!

Even assuming that the tables are somehow representative, n=100000 is way way way too small to make meaningful guesses about any asymptotic form with more than one nested log, since log log n grows so incredibly slowly--even n=10100 is too small.

[I'll tabulate the analytic forms for (x,y,Fn(x,y)) sometime soon, maybe later tonight.]

Sorry about that, I jumped to conclusions without enough data.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

Here are the exact values for the maxima tabulated above. (Analytic maximization was done only over the Farey region found by numeric methods to contain the maximum. The numerical maximization I used is not guaranteed to find the actual maximum, so it is possible that some of these are wrong.) Because these are such long expressions I'm just attaching the values as a LaTeX file, containing two tables: one of (x,n,y) [n is in the middle to make it easier to read] and one of the maximum value (n,Fn(x,y)).

Spoilered for space:
Spoiler:

Code: Select all

\documentclass{article}\setlength{\oddsidemargin}{-1.0in}\setlength{\topmargin}{-1.5in}\setlength{\textwidth}{8.5in}\setlength{\textheight}{11in}\pagestyle{empty}\begin{document}\thispagestyle{empty}$$\begin{array}{r|c|l}\multicolumn{1}{c|}{x} &\multicolumn{1}{c|}{n} &\multicolumn{1}{c }{y} \\[0.9ex] \hline \frac{3}{7} & 3 & \frac{2}{7} \\[0.9ex] \frac{4133-\sqrt{16881}}{9718} & 7 & \frac{115+\sqrt{16881}}{914} \\[0.9ex] \frac{51}{124} & 15 & \frac{7}{26} \\[0.9ex] \frac{7}{18} & 17 & \frac{7}{26} \\[0.9ex] \frac{31975+\sqrt{760929}}{79928} & 18 & \frac{19397-\sqrt{760929}}{68644} \\[0.9ex] \frac{12}{31} & 22 & \frac{25}{93} \\[0.9ex] -\frac{3 \left(-2435+\sqrt{5209}\right)}{18284} & 26 & \frac{2197-\sqrt{5209}}{8036} \\[0.9ex] \frac{20300+\sqrt{21637}}{52738} & 34 & \frac{14231-2 \sqrt{21637}}{52738} \\[0.9ex] \frac{945304-\sqrt{144153949}}{2262537} & 49 & \frac{274165-\sqrt{144153949}}{972018} \\[0.9ex] \frac{4 \left(1334617+2 \sqrt{65417134}\right)}{13975069} & 63 & \frac{704888+\sqrt{65417134}}{2699745} \\[0.9ex] \frac{20712381+\sqrt{63365265401}}{54228302} & 75 & \frac{155861341-3 \sqrt{63365265401}}{587322901} \\[0.9ex] \frac{421828+19 \sqrt{159826}}{1021167} & 106 & \frac{214888+3 \sqrt{159826}}{927031} \\[0.9ex] \frac{190127345+\sqrt{77348825761}}{460824488} & 107 & \frac{57242037+\sqrt{77348825761}}{212646284} \\[0.9ex] \frac{234592919+7 \sqrt{16332294529}}{569921635} & 122 & \frac{43060763+\sqrt{16332294529}}{159674434} \\[0.9ex] \frac{66912147+\sqrt{48606527633}}{158143604} & 196 & \frac{9830543433-11 \sqrt{48606527633}}{26425689436} \\[0.9ex] \frac{15622183+\sqrt{4224711409}}{43337378} & 285 & \frac{15216209-2 \sqrt{4224711409}}{63604989} \\[0.9ex] \frac{376662635-\sqrt{10954117801}}{1040278728} & 312 & \frac{13625207-2 \sqrt{10954117801}}{56561367} \\[0.9ex] \frac{983119339+\sqrt{11970651961921}}{2387912550} & 384 & \frac{3430591409-\sqrt{11970651961921}}{12669440880} \\[0.9ex] \frac{2235254056+\sqrt{315919400041}}{5411560575} & 695 & \frac{525534761-\sqrt{315919400041}}{1940716110} \\[0.9ex] \frac{7699498}{18635833} & 973 & \frac{343}{1268} \\[0.9ex] \frac{6715699871663-\sqrt{493917859979133153}}{16252951087376} & 1268 & \frac{22508111674393+15 \sqrt{493917859979133153}}{83246687796968} \\[0.9ex] \frac{62408861253+50 \sqrt{19439541517}}{141956384446} & 1353 & \frac{2724500985-2 \sqrt{19439541517}}{15283154894} \\[0.9ex] \frac{1825809415351-3 \sqrt{38458037820235289}}{4298596344100} & 2777 & \frac{3 \left(27572094648957+\sqrt{38458037820235289}\right)}{218752261487620} \\[0.9ex] \frac{145644701300035-3 \sqrt{241561071717053587129}}{342899664602252} & 3641 & \frac{215764298196597+\sqrt{241561071717053587129}}{570649334429984} \\[0.9ex] \frac{36875049198707581+36 \sqrt{852711476518779865789}}{86847319250756459} & 5231 & \frac{1237301319309746+3 \sqrt{852711476518779865789}}{3272386817056619} \\[0.9ex] \frac{4324304360002559-\sqrt{22216145776643704515865}}{11034897427124604} & 5551 & \frac{2031142407752879-3 \sqrt{22216145776643704515865}}{6955481261637664} \\[0.9ex] \frac{71087114378231-\sqrt{614212562456852639358961}}{179408766838032} & 6316 & \frac{7554203403587065+\sqrt{614212562456852639358961}}{25877130063513696} \\[0.9ex] \frac{11327655515260165+\sqrt{37820545811747561859161}}{28907786500015384} & 6477 & \frac{16522287396305939+9 \sqrt{37820545811747561859161}}{56597672382728698} \\[0.9ex] \frac{263502925625271+244 \sqrt{3679093030327717}}{598371366762893} & 10690 & \frac{3923984889408443-235 \sqrt{3679093030327717}}{14587522197576932} \\[0.9ex] \frac{14561680100635951+5 \sqrt{5271558396890128893001}}{34231204923931722} & 12398 & \frac{30687552349545425-\sqrt{5271558396890128893001}}{133991278911735266} \\[0.9ex] \frac{2659023985977928845+\sqrt{598209850476441490617642601}}{6250663584422210912} & 15959 & \frac{6483611160076167449+\sqrt{598209850476441490617642601}}{28309611484092816500} \\[0.9ex] \frac{4112037471887834407+5 \sqrt{123800696836240308916742103}}{9666356655176218354} & 22045 & \frac{932414155793413035-\sqrt{123800696836240308916742103}}{4071167637619212662} \\[0.9ex] \frac{2 \left(1236866514990379738+\sqrt{1116876019890863054353909}\right)}{5907015885150327033} & 24840 & -\frac{2 \left(-51836877077037692+7 \sqrt{1116876019890863054353909}\right)}{386752580447473341} \\[0.9ex] \frac{41988868434249283549+\sqrt{20596733542645838652491385721}}{100265285565650875052} & 28046 & \frac{1012554551171409883-\sqrt{20596733542645838652491385721}}{3777315392226733517} \\[0.9ex] \frac{769695834643319699-3 \sqrt{93179521701961227473795089}}{2006234646155014984} & 29863 & \frac{5898287097830230489-\sqrt{93179521701961227473795089}}{21025821855484119224} \\[0.9ex] \frac{98526774593399473328-\sqrt{2689891855616538139601461729}}{256822439591446787993} & 35020 & \frac{31955531077528192729-\sqrt{2689891855616538139601461729}}{113912954873656933794} \\[0.9ex] \frac{3181232644560959727999-\sqrt{319054818006116643739959273598329}}{7596401853379503656764} & 82677 & \frac{3721672603272506619531-\sqrt{319054818006116643739959273598329}}{13885530955031046221888} \\[0.9ex] \frac{90996977580191309018+\sqrt{25814095688484936878515441465}}{196640674374382429671} & 87022 & \frac{69827901371330699883+\sqrt{25814095688484936878515441465}}{249606740904438144818} \\[0.9ex] \frac{56918222857575095162+3 \sqrt{1124430265710863677436610191}}{122997906603466254447} & 88839 & \frac{19692040705211582429-\sqrt{1124430265710863677436610191}}{70390865630746672134}\end{array}$$$$\begin{array}{r|l}\multicolumn{1}{c|}{n} &\multicolumn{1}{c }{F_n(x,y)} \\[0.9ex] \hline 3 & \frac{6}{49} \\[0.9ex] 7 & \frac{280 \left(-3744+35 \sqrt{16881}\right)}{2220563} \\[0.9ex] 15 & \frac{315}{3224} \\[0.9ex] 17 & \frac{5}{52} \\[0.9ex] 18 & \frac{595 \left(-77667+595 \sqrt{760929}\right)}{2743288816} \\[0.9ex] 22 & \frac{90}{961} \\[0.9ex] 26 & -\frac{720 \left(-4442+45 \sqrt{5209}\right)}{9183139} \\[0.9ex] 34 & \frac{2448}{26369} \\[0.9ex] 49 & \frac{3094 \left(12788836+1547 \sqrt{144153949}\right)}{1099613344833} \\[0.9ex] 63 & \frac{26288 \left(67255141+6572 \sqrt{65417134}\right)}{37729122657405} \\[0.9ex] 75 & \frac{318000 \left(2586041947+6360 \sqrt{63365265401}\right)}{15924761823472051} \\[0.9ex] 106 & -\frac{8170 \left(-14121137+32680 \sqrt{159826}\right)}{105183718353} \\[0.9ex] 107 & -\frac{776475 \left(-13664515517+31059 \sqrt{77348825761}\right)}{48996307474701296} \\[0.9ex] 122 & -\frac{445788 \left(-36530127787+222894 \sqrt{16332294529}\right)}{45500957246489795} \\[0.9ex] 196 & -\frac{20812 \left(-988061744663+78045 \sqrt{48606527633}\right)}{261190860349610459} \\[0.9ex] 285 & \frac{3016 \left(3506140409+4147 \sqrt{4224711409}\right)}{153137413943269} \\[0.9ex] 312 & \frac{54288 \left(1079856652+377 \sqrt{10954117801}\right)}{817216484954183} \\[0.9ex] 384 & -\frac{19703 \left(-95862771283+19703 \sqrt{11970651961921}\right)}{7563379219708761} \\[0.9ex] 695 & \frac{179588 \left(-33766073621+89794 \sqrt{315919400041}\right)}{42009211152573453} \\[0.9ex] 973 & \frac{414848280}{5907559061} \\[0.9ex] 1268 & \frac{966962535 \left(-19825777295681097+29301895 \sqrt{493917859979133153}\right)}{10570346444923292543092781} \\[0.9ex] 1353 & -\frac{12346300 \left(-3475119555463+3086575 \sqrt{19439541517}\right)}{542385352920107594681} \\[0.9ex] 2777 & -\frac{7360512 \left(-4321579836965669+124592 \sqrt{38458037820235289}\right)}{470163835747145279705021} \\[0.9ex] 3641 & -\frac{796565175 \left(-4498682729277421859+223038249 \sqrt{241561071717053587129}\right)}{12229716586346240505281420248} \\[0.9ex] 5231 & -\frac{27825258300 \left(-1441251210496423958111+25877490219 \sqrt{852711476518779865789}\right)}{284198022612882962077859582952121} \\[0.9ex] 5551 & \frac{49374169 \left(385504811186751194305+2123089267 \sqrt{22216145776643704515865}\right)}{533007099155964257409830746424} \\[0.9ex] 6316 & \frac{3240275257 \left(-185334138786967942373351+236540093761 \sqrt{614212562456852639358961}\right)}{2321291997001178442422822843136} \\[0.9ex] 6477 & -\frac{62524119681 \left(-2197039570670224707779+6947124409 \sqrt{37820545811747561859161}\right)}{818056714818869093899456449145016} \\[0.9ex]\end{array}$$$$\begin{array}{r|l}\multicolumn{1}{c|}{n} &\multicolumn{1}{c }{F_n(x,y)} \\[0.9ex] \hline 10690 & \frac{172361201670 \left(350826191909135161+7447706245 \sqrt{3679093030327717}\right)}{2182188898762037315701292596069} \\[0.9ex] 12398 & -\frac{2913919548800 \left(-354768418270277095676+4552999295 \sqrt{5271558396890128893001}\right)}{1146670731611825235585528580877013} \\[0.9ex] 15959 & \frac{468782682251 \left(-458572610246527514760766841+19220089972291 \sqrt{598209850476441490617642601}\right)}{88476928796379895127804418773556824000} \\[0.9ex] 22045 & -\frac{647553996505 \left(-210801143664947090417592762+18779065898645 \sqrt{123800696836240308916742103}\right)}{19676679194119259565571645872036799174} \\[0.9ex] 24840 & \frac{7205423750 \left(18798827538608982861593741+37900528925 \sqrt{1116876019890863054353909}\right)}{2284553636326104801324784264699127253} \\[0.9ex] 28046 & \frac{2420159455 \left(2319918556871891896597915691+32430136697 \sqrt{20596733542645838652491385721}\right)}{94683401618285494415374439419666879471} \\[0.9ex] 29863 & \frac{9185894835 \left(132028637115440341402534229+205151651315 \sqrt{93179521701961227473795089}\right)}{21091366135177781264249077878881226208} \\[0.9ex] 35020 & \frac{857350184600 \left(995569185260865278110319453+4286750923 \sqrt{2689891855616538139601461729}\right)}{14627701485861480928526276094137177567721} \\[0.9ex] 82677 & -\frac{11134926325195 \left(-15590464198293025131918806080293+857389327040015 \sqrt{319054818006116643739959273598329}\right)}{52740036540978154483011325821409601268025216} \\[0.9ex] 87022 & \frac{11483508932 \left(13611962247026136142699392583+476565620678 \sqrt{25814095688484936878515441465}\right)}{2726824325546692472799136667560811005271} \\[0.9ex] 88839 & -\frac{35876475243 \left(-773270055526263992592305206+11958825081 \sqrt{1124430265710863677436610191}\right)}{480996062032651217689961655367496026661}\end{array}$$\end{document}
The resulting DVI, or whatever, is not very readable either, but it's more readable than I'd be able to do easily with the jsMath code here.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

can't you just put it in a table like you did before?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Dopefish
Posts: 854
Joined: Sun Sep 20, 2009 5:46 am UTC
Location: The Well of Wishes

Re: help with diophantine approximation.

Glancing at the Latex code, theres fractions and squareroots everywhere. Not to mention some of the numbers get pretty huge so as to probably not fit in a nice column

You really don't want to do that with standard text (as you need a metric butt ton of parentheses to be non-ambiguous), and theres enough of it there that doing it via the LaTex support on these forums would probably kill a lot of peoples computers trying to view it.

If you're math inclined, you really ouaght to be fine compiling latex stuff into a pretty pdf (or dvi or whatever).

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

Well, how about this: I think that each number has the form (a+sqrt(b))/c, so couldn't you just make a table with the values a, b, and c?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

tomtom2357 wrote:Well, how about this: I think that each number has the form (a+sqrt(b))/c, so couldn't you just make a table with the values a, b, and c?
Sure I could. But you could too, and if you want to play with these numbers you're going to need to be able to manipulate them anyway, so it would be good practice.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

I have a new idea, you can probably find an exact formula that finds a and b, given the values i,j, and k such that i<ia><ib>=j<ja><jb>=k<ka><kb>. Now to find that formula.

Edit: Uh Oh. There is more than one fixed point for each triplet.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

MarioTrevi
Posts: 4
Joined: Tue Sep 27, 2011 5:30 pm UTC

Re: help with diophantine approximation.

eta oin shrdlu wrote:Notation: Define fk(x,y)=k<kx><ky>, so that FN(x,y)=mink<=N{k<kx><ky>} is the function to be maximized.

FN(x,y)=0 if either x or y is a rational number with denominator at most N; otherwise FN(x,y)>0. So FN has at least one maximum in each of these rectangular "Farey regions", whose x and y coordinates bounded by consecutive fractions in the order-N Farey sequence. There are ~N2/3 such fractions, so there are O(N4) such regions, and so jaap's hill-climbing algorithm needs to run with at least that many initial conditions to find each local maximum.

I think it's true that each Farey region has exactly one maximum. It's true at least in the cases I've considered, but I haven't got a simple proof. It's not the case that each maximum is at the intersection of three of the individual fk. (The cases N=1 and N=2 are trivial counterexamples; more generally it looks like the maxima along the diagonal x=y are at smooth hyperbolic intersections of two of the fk.) For N>2 I haven't found any cases where the global maximum of FN is at one of these maxima, but I don't know that it can't happen.

But considering up to three of the individual fk should suffice to find all of the candidate maxima, so this gives an O(N7) algorithm to find the maximum (counting finding each candidate maximum as O(1), which is probably not quite right). It's easier to find the intersections if you subdivide along not just the order-N Farey fractions, but half of each order-N Farey fraction: this makes each fk a polynomial (of the form axy+bx+cy+d, i.e. a hyperbola).

This fairly rapidly gets unwieldy. One way to prune a lot of the O(N4) Farey regions is to find an upper bound for FN on the region. Each of the fk is bilinear, so it is bounded by its values on the four corners of the region, and
FN(x,y) <= mink<=N maxcorners(xc,yc) fk(xc,yc).
So we can start with an O(N5) search over all these regions to find the bounds, then sort by decreasing size of the bound and do the O(N3) check within the regions in this order, stopping when the current best is better than the remaining upper bounds. (At N=30 this means checking just 11 of 38781 regions, so that's a pretty good reduction. This lets you get up to N~60. Currently I only check for the maxima among three-fk intersections; for 48<N<63 I get a maximum of
(3094 (12788836+1547 sqrt(144153949)))/1099613344833
at
(x,y)=((274165-sqrt(144153949))/972018,(945304-sqrt(144153949))/2262537).
I have no idea how this pruned search scales asymptotically with N.)

As tomtom2357 noted, if you're tabulating these values over N then you can first check the maximum for FN-1; if it works then it is necessarily the maximum for FN as well. However: if not, you can't necessarily assume that fN will be a constraint in the new maximum; there could be other maxima using only earlier constraints that were not cut off by fN. (This happens at N=17; the maximum of 5/52 at (7/26,7/18) is at the intersections of f3, f5, f15.)

I can think of some other possible pruning techniques, but I haven't tried them.

I'm unfamiliar with the syntax on the xkcd boards for mathematical notation, so I'll stick to the minimum possible.
Some time ago, I had written brute-force, simple-minded C programs to get lower bounds on the maximum
of FN for N up to 60 or so. I preferred the Monte Carlo method, with the idea of a uniform
probability distribution on [0, 1]x[0, 1]. I also used "confined search" variants, with the unit square being
substituted by a small square centered on a special point P in the unit square, and where the small square
centered at P has sides parallel to the x-axis or the y-axis. Later, I used random continued fractions
to produce the pseudo-random reals alpha and beta, favouring c.f. expansions with coefficients "usually small",
say roughly 1, 2, 3, 4, 5 or 6.

I understand your idea of the Farey regions, and I might suggest the name "Farey grid" of order N for all points
in [0, 1]x[0, 1] whose x-coordinate and/or y-coordinate can be expressed as k/n for some positive integer n
no larger than N.

I have seen that you did computations for N up to 10^4 or beyond. Given your approach using Farey regions,
I wanted to ask you if the optimimum point or points for a given N tend to fall in Farey regions that have
"above-average" area compared to all the Farey regions of order N.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

MarioTrevi wrote:I have seen that you did computations for N up to 10^4 or beyond. Given your approach using Farey regions,
I wanted to ask you if the optimimum point or points for a given N tend to fall in Farey regions that have
"above-average" area compared to all the Farey regions of order N.
I don't see any evidence of that. Below I've tabulated (the table will wrap unless your screen is pretty wide), for each N at which the maximum value changes, the numerical maximum f_max=f(x_max,y_max), the Farey fractions of order N bounding the location (x_max,y_max) of the maximum, and the values dx*N^2 and dy*N^2, where dx and dy are the widths of these two Farey regions. Since there are ~N^2/3 Farey fractions of order N, these last two values should be roughly 3 if the region is of "average" size; as far as I can tell that seems to be pretty much true, and at any rate there's not much evidence of an upward trend (as you'd expect if the region size were O(N^a) for some a<2). --Note that Farey regions vary a lot in size; there are a few large ones of size ~1/N and the smallest is 1/(N(N-1)).

Code: Select all

              f_max           x_max     y_max           x Farey region                 y Farey region          dx * N^2     dy * N^2N =      3  0.1224489796 @ (0.4285714,0.2857143) [     1/3          1/2     ] x [     0/1          1/3     ]  1.50000000 x 3.00000000N =      7  0.1013092827 @ (0.4119236,0.2679725) [     2/5          3/7     ] x [     1/4          2/7     ]  1.40000000 x 1.75000000N =     15  0.0977047146 @ (0.4112903,0.2692308) [     2/5          5/12    ] x [     4/15         3/11    ]  3.75000000 x 1.36363636N =     17  0.0961538461 @ (0.3888889,0.2692308) [     5/13         2/5     ] x [     4/15         3/11    ]  4.44615385 x 1.75151515N =     18  0.0957276341 @ (0.4109613,0.2698661) [     2/5          7/17    ] x [     4/15         3/11    ]  3.81176471 x 1.96363636N =     22  0.0936524454 @ (0.3870968,0.2688172) [     5/13         7/18    ] x [     4/15         3/11    ]  2.06837607 x 2.93333333N =     26  0.0936304857 @ (0.3876876,0.2644135) [     5/13         7/18    ] x [     5/19         4/15    ]  2.88888889 x 2.37192982N =     34  0.0928362850 @ (0.3877109,0.2642650) [    12/31         7/18    ] x [     5/19         9/34    ]  2.07168459 x 1.78947368N =     49  0.0882458998 @ (0.4125005,0.2697055) [     7/17        19/46    ] x [     7/26        10/37    ]  3.07033248 x 2.49584200N =     63  0.0838964427 @ (0.3866294,0.2640902) [    17/44        12/31    ] x [     5/19        14/53    ]  2.90982405 x 3.94141013N =     75  0.0836099960 @ (0.3865897,0.2640901) [    17/44        29/75    ] x [    19/72        14/53    ]  1.70454545 x 1.47405660N =    106  0.0820425133 @ (0.4205227,0.2330961) [    37/88         8/19    ] x [    24/103        7/30    ]  6.72009569 x 3.63624595N =    107  0.0796579651 @ (0.4131843,0.2704969) [    19/46        31/75    ] x [    10/37        23/85    ]  3.31855072 x 3.64038156N =    122  0.0788170914 @ (0.4131928,0.2704789) [    19/46        50/121   ] x [    10/37        33/122   ]  2.67409271 x 3.29729730N =    196  0.0773589070 @ (0.4245041,0.3719153) [    59/139       45/106   ] x [    45/121       61/164   ]  2.60730284 x 1.93590002N =    285  0.0743611198 @ (0.3619781,0.2371860) [    59/163       80/221   ] x [    37/156       51/215   ]  2.25480943 x 2.42173524N =    312  0.0743564651 @ (0.3619780,0.2371916) [    59/163       80/221   ] x [    37/156       51/215   ]  2.70227355 x 2.90232558N =    384  0.0721419543 @ (0.4131555,0.2705038) [    88/213      157/380   ] x [    33/122       89/329   ]  1.82179392 x 3.67372565N =    695  0.0714098097 @ (0.4131555,0.2705046) [   245/593      157/380   ] x [   188/695      155/573   ]  2.14353865 x 1.21291449N =    973  0.0702029615 @ (0.4131556,0.2705050) [   402/973      157/380   ] x [   188/695      155/573   ]  2.56052632 x 2.37731239N =   1268  0.0701966596 @ (0.4131556,0.2705051) [   402/973      157/380   ] x [   343/1268     155/573   ]  4.34852599 x 2.21291449N =   1353  0.0693080330 @ (0.4396832,0.1782500) [   277/630      390/887   ] x [    59/331      218/1223  ]  3.27590594 x 4.52211021N =   2777  0.0672727155 @ (0.4246086,0.3781304) [   949/2235     597/1406  ] x [   453/1198     619/1637  ]  2.45408110 x 3.93229655N =   3641  0.0672289053 @ (0.4246084,0.3781304) [  1301/3064     949/2235  ] x [   453/1198    1072/2835  ]  1.93586501 x 3.90329591N =   5231  0.0671254084 @ (0.4246084,0.3781304) [  1301/3064     949/2235  ] x [  1978/5231    1525/4033  ]  3.99579456 x 1.29704934N =   5551  0.0650241013 @ (0.3918618,0.2919561) [   703/1794    1589/4055  ] x [  1303/4463    1597/5470  ]  4.23573867 x 1.26220019N =   6316  0.0647527134 @ (0.3918615,0.2919561) [  2263/5775    1743/4448  ] x [  1303/4463    1597/5470  ]  1.55298577 x 1.63406764N =   6477  0.0646594523 @ (0.3918615,0.2919561) [  2263/5775    1743/4448  ] x [  1303/4463    1597/5470  ]  1.63316862 x 1.71843687N =  10690  0.0633914105 @ (0.4403916,0.2689950) [  2789/6333    2294/5209  ] x [  1448/5383    1887/7015  ]  3.46410913 x 3.02623992N =  12398  0.0614857670 @ (0.4254026,0.2290259) [  3989/9377    1400/3291  ] x [  2203/9619    1627/7104  ]  4.98094178 x 2.24941914N =  15959  0.0610296422 @ (0.4254026,0.2290259) [  6789/15959   1400/3291  ] x [  2203/9619    1627/7104  ]  4.84928593 x 3.72716374N =  22045  0.0610283558 @ (0.4254026,0.2290259) [  8189/19250   1400/3291  ] x [  3830/16723   1627/7104  ]  7.67116970 x 4.09075117N =  24840  0.0594173512 @ (0.4187792,0.2680240) [  5468/13057   8425/20118 ] x [  2725/10167   6253/23330 ]  2.34895650 x 2.60133103N =  28046  0.0594173500 @ (0.4187792,0.2680240) [  5468/13057   8425/20118 ] x [  2725/10167   6253/23330 ]  2.99442646 x 3.31615099N =  29863  0.0583647438 @ (0.3836375,0.2805254) [  4919/12822   7967/20767 ] x [  2093/7461    6642/23677 ]  3.34917109 x 5.04827674N =  35020  0.0583647430 @ (0.3836375,0.2805254) [  4919/12822  12886/33589 ] x [  2093/7461    8735/31138 ]  2.84760297 x 5.27891330N =  82677  0.0582047432 @ (0.4187792,0.2680239) [ 30297/72346  24829/59289 ] x [ 13547/50544  21038/78493 ]  1.59360532 x 1.72293496N =  87022  0.0576466783 @ (0.4627585,0.2797523) [  5281/11412  39943/86315 ] x [ 20284/72507   6415/22931 ]  7.68794173 x 4.55465189N =  88839  0.0576466595 @ (0.4627585,0.2797523) [  5281/11412  39943/86315 ] x [ 20284/72507   6415/22931 ]  8.01233843 x 4.74683780

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

I just came up with an idea for an O(1/n) lower bound on f(n). Take x=1/(n+1) and y=(3-sqrt(5))/2. I came up with y when I was looking at the one variable form of the problem, n<ny> is always at least y, and this is the best possible for the one variable problem, because it is the distance from the golden ratio to 2. Therefore i<ix><iy> is >y/(n+1) for all 1<=i<=n.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

MarioTrevi
Posts: 4
Joined: Tue Sep 27, 2011 5:30 pm UTC

Re: help with diophantine approximation.

eta oin shrdlu wrote:
MarioTrevi wrote:I have seen that you did computations for N up to 10^4 or beyond. Given your approach using Farey regions,
I wanted to ask you if the optimimum point or points for a given N tend to fall in Farey regions that have
"above-average" area compared to all the Farey regions of order N.
I don't see any evidence of that. Below I've tabulated (the table will wrap unless your screen is pretty wide), for each N at which the maximum value changes, the numerical maximum f_max=f(x_max,y_max), the Farey fractions of order N bounding the location (x_max,y_max) of the maximum, and the values dx*N^2 and dy*N^2, where dx and dy are the widths of these two Farey regions. Since there are ~N^2/3 Farey fractions of order N, these last two values should be roughly 3 if the region is of "average" size; as far as I can tell that seems to be pretty much true, and at any rate there's not much evidence of an upward trend (as you'd expect if the region size were O(N^a) for some a<2). --Note that Farey regions vary a lot in size; there are a few large ones of size ~1/N and the smallest is 1/(N(N-1)).

Code: Select all

              f_max           x_max     y_max           x Farey region                 y Farey region          dx * N^2     dy * N^2N =      3  0.1224489796 @ (0.4285714,0.2857143) [     1/3          1/2     ] x [     0/1          1/3     ]  1.50000000 x 3.00000000N =      7  0.1013092827 @ (0.4119236,0.2679725) [     2/5          3/7     ] x [     1/4          2/7     ]  1.40000000 x 1.75000000N =     15  0.0977047146 @ (0.4112903,0.2692308) [     2/5          5/12    ] x [     4/15         3/11    ]  3.75000000 x 1.36363636N =     17  0.0961538461 @ (0.3888889,0.2692308) [     5/13         2/5     ] x [     4/15         3/11    ]  4.44615385 x 1.75151515N =     18  0.0957276341 @ (0.4109613,0.2698661) [     2/5          7/17    ] x [     4/15         3/11    ]  3.81176471 x 1.96363636N =     22  0.0936524454 @ (0.3870968,0.2688172) [     5/13         7/18    ] x [     4/15         3/11    ]  2.06837607 x 2.93333333N =     26  0.0936304857 @ (0.3876876,0.2644135) [     5/13         7/18    ] x [     5/19         4/15    ]  2.88888889 x 2.37192982N =     34  0.0928362850 @ (0.3877109,0.2642650) [    12/31         7/18    ] x [     5/19         9/34    ]  2.07168459 x 1.78947368N =     49  0.0882458998 @ (0.4125005,0.2697055) [     7/17        19/46    ] x [     7/26        10/37    ]  3.07033248 x 2.49584200N =     63  0.0838964427 @ (0.3866294,0.2640902) [    17/44        12/31    ] x [     5/19        14/53    ]  2.90982405 x 3.94141013N =     75  0.0836099960 @ (0.3865897,0.2640901) [    17/44        29/75    ] x [    19/72        14/53    ]  1.70454545 x 1.47405660N =    106  0.0820425133 @ (0.4205227,0.2330961) [    37/88         8/19    ] x [    24/103        7/30    ]  6.72009569 x 3.63624595N =    107  0.0796579651 @ (0.4131843,0.2704969) [    19/46        31/75    ] x [    10/37        23/85    ]  3.31855072 x 3.64038156N =    122  0.0788170914 @ (0.4131928,0.2704789) [    19/46        50/121   ] x [    10/37        33/122   ]  2.67409271 x 3.29729730N =    196  0.0773589070 @ (0.4245041,0.3719153) [    59/139       45/106   ] x [    45/121       61/164   ]  2.60730284 x 1.93590002N =    285  0.0743611198 @ (0.3619781,0.2371860) [    59/163       80/221   ] x [    37/156       51/215   ]  2.25480943 x 2.42173524N =    312  0.0743564651 @ (0.3619780,0.2371916) [    59/163       80/221   ] x [    37/156       51/215   ]  2.70227355 x 2.90232558N =    384  0.0721419543 @ (0.4131555,0.2705038) [    88/213      157/380   ] x [    33/122       89/329   ]  1.82179392 x 3.67372565N =    695  0.0714098097 @ (0.4131555,0.2705046) [   245/593      157/380   ] x [   188/695      155/573   ]  2.14353865 x 1.21291449N =    973  0.0702029615 @ (0.4131556,0.2705050) [   402/973      157/380   ] x [   188/695      155/573   ]  2.56052632 x 2.37731239N =   1268  0.0701966596 @ (0.4131556,0.2705051) [   402/973      157/380   ] x [   343/1268     155/573   ]  4.34852599 x 2.21291449N =   1353  0.0693080330 @ (0.4396832,0.1782500) [   277/630      390/887   ] x [    59/331      218/1223  ]  3.27590594 x 4.52211021N =   2777  0.0672727155 @ (0.4246086,0.3781304) [   949/2235     597/1406  ] x [   453/1198     619/1637  ]  2.45408110 x 3.93229655N =   3641  0.0672289053 @ (0.4246084,0.3781304) [  1301/3064     949/2235  ] x [   453/1198    1072/2835  ]  1.93586501 x 3.90329591N =   5231  0.0671254084 @ (0.4246084,0.3781304) [  1301/3064     949/2235  ] x [  1978/5231    1525/4033  ]  3.99579456 x 1.29704934N =   5551  0.0650241013 @ (0.3918618,0.2919561) [   703/1794    1589/4055  ] x [  1303/4463    1597/5470  ]  4.23573867 x 1.26220019N =   6316  0.0647527134 @ (0.3918615,0.2919561) [  2263/5775    1743/4448  ] x [  1303/4463    1597/5470  ]  1.55298577 x 1.63406764N =   6477  0.0646594523 @ (0.3918615,0.2919561) [  2263/5775    1743/4448  ] x [  1303/4463    1597/5470  ]  1.63316862 x 1.71843687N =  10690  0.0633914105 @ (0.4403916,0.2689950) [  2789/6333    2294/5209  ] x [  1448/5383    1887/7015  ]  3.46410913 x 3.02623992N =  12398  0.0614857670 @ (0.4254026,0.2290259) [  3989/9377    1400/3291  ] x [  2203/9619    1627/7104  ]  4.98094178 x 2.24941914N =  15959  0.0610296422 @ (0.4254026,0.2290259) [  6789/15959   1400/3291  ] x [  2203/9619    1627/7104  ]  4.84928593 x 3.72716374N =  22045  0.0610283558 @ (0.4254026,0.2290259) [  8189/19250   1400/3291  ] x [  3830/16723   1627/7104  ]  7.67116970 x 4.09075117N =  24840  0.0594173512 @ (0.4187792,0.2680240) [  5468/13057   8425/20118 ] x [  2725/10167   6253/23330 ]  2.34895650 x 2.60133103N =  28046  0.0594173500 @ (0.4187792,0.2680240) [  5468/13057   8425/20118 ] x [  2725/10167   6253/23330 ]  2.99442646 x 3.31615099N =  29863  0.0583647438 @ (0.3836375,0.2805254) [  4919/12822   7967/20767 ] x [  2093/7461    6642/23677 ]  3.34917109 x 5.04827674N =  35020  0.0583647430 @ (0.3836375,0.2805254) [  4919/12822  12886/33589 ] x [  2093/7461    8735/31138 ]  2.84760297 x 5.27891330N =  82677  0.0582047432 @ (0.4187792,0.2680239) [ 30297/72346  24829/59289 ] x [ 13547/50544  21038/78493 ]  1.59360532 x 1.72293496N =  87022  0.0576466783 @ (0.4627585,0.2797523) [  5281/11412  39943/86315 ] x [ 20284/72507   6415/22931 ]  7.68794173 x 4.55465189N =  88839  0.0576466595 @ (0.4627585,0.2797523) [  5281/11412  39943/86315 ] x [ 20284/72507   6415/22931 ]  8.01233843 x 4.74683780

That's interesting, and a bit mysterious at the same time. Thanks.
In your table, I notice that 157/380 ~= 0.413157895 persists as y_max from N = 384 through N = 1268 .
If I'm not mistaken, your table reflects only new record lows of f_max, as N increases ...

As N increases by one over and over, we see that new Farey regions are created from old ones
in a way analogous to how a plot of land is subdivided , say by urban planners or feudal landlords.
As N increases, I believe the Farey regions can be given a rooted tree stucture, where some nodes
(vertices in graph theory terminology, I believe) split into at least two nodes, maybe even four at
depth level (N+1), "plot sub-division", Farey-region sub-division being the "cause".
From your data, I see that any Farey region with a maximum (given N) of 0.06 or less is automatically
ruled-out as a candidate for the location of (x_max, y_max) up to at least N = 22,000.
With a goal of setlling the problem up to only N=20,000 I'm wondering if keeping track of only those
Farey regions (and their later sub-divisions) where the max of f. is at least 0.06 would contribute to
a significant saving of memory with respect to O(N^4) [or whatever the growth rate is ].
This assumes that "pruning the tree" as N increases to discard Farey regions going below 0.06 in local
f_max can be done efficiently and that algorithms that are efficient enough to work with the relevant
part of the "pruned tree" exist. One feature of many programming languages, as you may well know,
is dynamic memory allocation, where new RAM memory cells are requested "on the fly" ;
the freeing of a memory cell can also be done (garbage collection in lisp). I usually
program in the C language, and there's malloc() to request memory on-the-fly ; I don't
remember much about freeing individual cells of RAM memory used in C
data structures, as it's been several years since I really used malloc() .

MarioTrevi
Posts: 4
Joined: Tue Sep 27, 2011 5:30 pm UTC

Re: help with diophantine approximation.

eta oin shrdlu wrote:
tomtom2357 wrote:
eta oin shrdlu wrote:
tomtom2357 wrote:Well, how about we narrow the search are a bit: the values of a and b must be>1/(2n), I don't know if this helps or not.
Well, for the exhaustive search of Farey regions (the approach described in my first post), there are O(n4) regions to be searched, and this only removes O(n2) of them, so that won't change the runtime much. The insight might be useful, though, if it can be extended to rule out enough other regions.

I've been working on a priority-queued version (described in my second post). This is definitely much faster as long as memory is available to hold the queue. It's still got a bug in it though.

What are you hoping to get from these maxima? (I know you're thinking about the Littlewood conjecture, but is there a specific question you're hoping these values will answer?)

tomtom2357 wrote:Well, if a can find a pattern in these numbers that proves that they approach 0, then that will prove the conjecture. It is easy to prove that 0<Fn<Fn-1, which therefore means that limn->infinityFn exists. If it is 0, then the littlewood conjecture follows, if it is not 0, then the negation of the littlewood conjecture follows. I just want to find the limit of the series.
OK. Finding a pattern seems like it will probably be difficult.

tomtom2357 wrote:Also, if you can find a first good guess, then that can narrow the search area down a by a lot. For example, even if jaap's first guess for n=7 is wrong, then I can say that the maximum must be>0.1, and from there 0.2<a<b<0.45, which narrows the search are down by a lot.

tomtom2357 wrote:So my idea of an optimal algorithm would start by checking if the previous solution worked, then check the cases where a,b are integers divided by 100. Then, narrow the search area down using those values. It would then check the remaining regions for the optimal value.
This was the basis for the first algorithm I wrote. The problem with this is that it scales poorly with n; Fn has O(n4) local maxima, so for n=7 a 50x50 subdivision will work, but for n=20 you need more than 50x50 to see all of the local maxima. (Of course, depending on how large an n you're interested in, this may be sufficient.)

You can save computation by doing a local maximization within each of these O(n4) regions (for a roughly O(n5) algorithm); I was able to get to roughly n=50 this way.

tomtom2357 wrote:Edit: Actually, a good first approximation for Fn(x,y) (for small n) is 8/(m2), where m is the first odd number after n. This works by setting x=2/m, y=4/m.
This is not a very good approximation except for very small n; even at n=200000 the maximum is above 0.05, not 10-9.

tomtom2357 wrote:Edit 2: To prevent from double posting, I will post my idea of how to narrow the search area. First, for n=7, I will assume without loss of generalization, that 0<a<b<0.5. I know that Fn>0.1, so therefore 2<2a><2b>>0.1, but <2a><0.5 no matter what a is, so <2b>>0.1, so b<0.45. Now we also know that ab>0.1, so since b<0.45, a>2/9.
Right. You can do that for each of the k<ka><kb> functions, but as k increases you get more and more disjoint regions, so keeping track of these efficiently might not be trivial.

The approach I described in my first post was a simplification of this idea: I computed bounds for all of the order-n Farey regions and then maximized over each region (in decreasing size of bound) until finding a maximum larger than all remaining bounds. This let me get to about n=60 analytically and n=350 numerically; unfortunately there are a lot (O(n4)) of these regions, and so memory starts to become an issue.

You can save on memory by not subdividing all of the rectangles to order n; instead, just subdivide rectangles whose bounds are large enough to be possible locations of maxima--this is what I was describing in my second post, and I have it working numerically now; I haven't had time to code a fully analytic version. This does a pretty good job of reducing memory usage, and it gets (numerical) maxima up to n=100000 in about an hour.

On any given Farey region you can also usually ignore most of the fk; these are bounded by their values at the corners of the region, so if you find fa<fb everywhere on the region then you can ignore fb since fa is always a tighter constraint. This helps a lot to reduce the O(n3) number of intersections to find with a purely analytic approach (it helps numerically, too, but there you're just doing function evaluations, which are O(n), so the growth isn't so bad).

So anyway, I have what I think are the maxima of Fn up to n=100000, found approximately using numerical maximization and then found exactly using analytic approaches. (My numerical maximization routine is kind of sloppy right now and could conceivably miss a maximum, so these are not guaranteed.)

Here are the numerical values I get:

Code: Select all

n                x                        y                    F_n(x,y)3       0.42857142857142857143  0.28571428571428571429  0.122448979591836734697       0.41192355396933553342  0.26797254105688980989  0.1013092827155876258215      0.41129032258064516129  0.26923076923076923077  0.09770471464019851116617      0.38888888888888888889  0.26923076923076923077  0.09615384615384615384618      0.41096127069393081320  0.26986608525108528004  0.09572763409529911258822      0.38709677419354838710  0.26881720430107526882  0.09365244536940686784626      0.38768758439569057200  0.26441346412356091000  0.09363048576099189160534      0.38771085758397866871  0.26426503821669888769  0.09283628503166597140649      0.41250047498531451088  0.26970548608343522189  0.08824589981202177213263      0.38662941037604381527  0.26409015885919449177  0.08389644269425772014375      0.38658974759034248408  0.26409010612154114942  0.083609996016538327379106     0.42052266316465889623  0.23309613952770191772  0.082042513469911944733107     0.41318433921561916293  0.27049686684699377282  0.079657965303179234655122     0.41319277879547616864  0.27047887244054102580  0.078817091947903354571196     0.42450414802312009610  0.37191530230868703680  0.077358907019254197086285     0.36197807767768786265  0.23718600815947563265  0.074361119822964258315312     0.36197796123593608164  0.23719163571675680656  0.074356465162087371279384     0.41315549934923924308  0.27050377190776510246  0.072141955211891854199695     0.41315551994498074115  0.27050463033571461004  0.071409811306328217718973     0.41315555897072054681  0.27050473186119873817  0.0702232979334406691601268    0.41315555819145344156  0.27050509952793400636  0.0701995872051622975581353    0.43968316595550786279  0.17824998518839328044  0.0693080338353128130622777    0.42460862747118442221  0.37813036402909279967  0.0672727155673087416863641    0.42460839022295384501  0.37813036380254671437  0.0672289119831361865505231    0.42460839045928670434  0.37813039599468557161  0.0671254098428533601745551    0.39186184898804523886  0.29195611042829371811  0.0650241733376857900826316    0.39186154875742867516  0.29195614437104387433  0.0647527350146747937256477    0.39186154880125592524  0.29195613487482405949  0.06465961178614247084410690   0.44039160329412810974  0.26899500698009196694  0.06339142220557413233012398   0.42540258692288390211  0.22902594850417053235  0.06148594594496796215615959   0.42540258460455583801  0.22902594837969366770  0.06103007349446050082422045   0.42540258459909101293  0.22902594837940018156  0.06102899872612262984524840   0.41877915883832255612  0.26802396122196505959  0.05941735117957662503328046   0.41877915883835302970  0.26802396157693953880  0.05941734998712171184429863   0.38363751580916999817  0.28052541705225926613  0.05836474385648762644635020   0.38363751581041148833  0.28052541740141213341  0.05836474303227621204982677   0.41877915937794298016  0.26802394184418440662  0.05820506588813627063287022   0.46275847322715482431  0.27975230871557415907  0.05764667921863549484488839   0.46275847310678965129  0.27975230871553084455  0.057646661544032551952
Analytic values available on request.

Lots of good ideas, for example:
"You can save on memory by not subdividing all of the rectangles to order n; instead, just subdivide rectangles whose bounds are large enough to be possible locations of maxima--"

So if with n = 1000, a region had a maximum of 0.065 for the k <kx> <ky> , 1<= k <= 1000, it wouln't matter and
wouldn't need sub-dividing until n reaches about 5551. Do you keep a record of the regions not currently
in need of sub-dividing? I would guess yes, because for larger n ( n ~= 5551 for a local max. of 0.065),
the region could be a contender for containing the max. of Fn for some n between 6000 and 10,000
for example.

I set n =40, and arrived at:
x = (1450 + sqrt(3091/28))/3767 ~= 0.3877108575839786687105037801982267
y = (5501/2 + sqrt(3091/7))/3767 ~= 0.735734961783301112308185686226026012

David Bernier

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: help with diophantine approximation.

MarioTrevi wrote:Lots of good ideas, for example:
"You can save on memory by not subdividing all of the rectangles to order n; instead, just subdivide rectangles whose bounds are large enough to be possible locations of maxima--"

So if with n = 1000, a region had a maximum of 0.065 for the k <kx> <ky> , 1<= k <= 1000, it wouln't matter and
wouldn't need sub-dividing until n reaches about 5551. Do you keep a record of the regions not currently
in need of sub-dividing? I would guess yes, because for larger n ( n ~= 5551 for a local max. of 0.065),
the region could be a contender for containing the max. of Fn for some n between 6000 and 10,000
for example.
Yes, the current version of my program maintains bounds on rectangular regions covering all of the lower-triangular half of [0,1/2]x[0,1/2]. It keeps track of these using a priority queue, ordered by the upper bound of the value of Fn on the region. There are two types of upper bounds: actual "exact" maxima (actually found by numerical ascent, and so subject to some errors), and upper bounds found by the bilinear bound in my post above.

When n is incremented, we start at the top of the priority queue (i.e., with the regions with largest upper bound). For each region we visit in the queue, if the region's upper bound is "exact" (for Fn-1) we first check to see if this value is still good for Fn; if so then we've found the answer. Otherwise we subdivide the region into its order-n Farey regions, find the upper bounds on each new region, and reinsert the new regions into their proper places in the queue. If one of these new regions is at the top of the queue, then we run a numerical ascent to find the actual "exact" maximum and reinsert it. Typically, if I recall correctly, not many of these regions need to be reexamined at any n.

One could use lower-bound estimates to delete the parts farther back in this queue (if you were only interested in values of n up to some Nmax), as you suggest. They could also be swapped out to disk or something. I never got to that point in my program; I think there was a numerical-precision issue that I saw first.

I set n =40, and arrived at:
x = (1450 + sqrt(3091/28))/3767 ~= 0.3877108575839786687105037801982267
y = (5501/2 + sqrt(3091/7))/3767 ~= 0.735734961783301112308185686226026012

David Bernier
Good; those values agree with the values I tabulated above (for n=34; actually <your y>=1-<my y>).

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: help with diophantine approximation.

If we made gk(x) to be k<kx><ky>, where y=(3-sqrt(5))/2, and Gn(x)=mink<=ngk(x), and g(n)=max0<=x<=1Gn(x). How does g(n) compare to f(n)? I know g(n)<=f(n), but are they related in any other way?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.