help with diophantine approximation.

[tomtom2357]

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?

[Proginoskes]

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]

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.

[mfb]

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

[tomtom2357]

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.

[jaap]

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]

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.

[jaap]

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]

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 f_a(n) and f_b(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!

[mfb]

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?

[jaap]

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]

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.

[PM 2Ring]

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

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]

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

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.

[PM 2Ring]

Fair enough.

[tomtom2357]

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).

[mfb]

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]

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

F_N(x,y)=0 if either x or y is a rational number with denominator at most N; otherwise F_N(x,y)>0. So F_N 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 ~N²/3 such fractions, so there are O(N⁴) 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 f_k. (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 f_k.) For N>2 I haven't found any cases where the global maximum of F_N is at one of these maxima, but I don't know that it can't happen.

But considering up to three of the individual f_k should suffice to find all of the candidate maxima, so this gives an O(N⁷) 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 f_k 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(N⁴) Farey regions is to find an upper bound for F_N on the region. Each of the f_k is bilinear, so it is bounded by its values on the four corners of the region, and
F_N(x,y) <= min_k<=N max_{corners(xc,yc)} f_k(xc,yc).
So we can start with an O(N⁵) search over all these regions to find the bounds, then sort by decreasing size of the bound and do the O(N³) 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-f_k 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 F_N-1; if it works then it is necessarily the maximum for F_N as well. However: if not, you can't necessarily assume that f_N will be a constraint in the new maximum; there could be other maxima using only earlier constraints that were not cut off by f_N. (This happens at N=17; the maximum of 5/52 at (7/26,7/18) is at the intersections of f₃, f₅, f₁₅.)

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

[tomtom2357]

I think that F_n(x,y)=f_n(x,y) or F_n(x,y)=F_n-1(x,y) (which is easy to check), which may help with the algorithms.

[eta oin shrdlu]

I think that F_n(x,y)=f_n(x,y) or F_n(x,y)=F_n-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]

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.

[eta oin shrdlu]

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(n⁴) regions to be searched, and this only removes O(n²) 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]

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(n⁴) regions to be searched, and this only removes O(n²) 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<F_n<F_n-1, which therefore means that lim_n->infinityF_n 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 F_n(x,y) (for small n) is 8/(m²), 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 F_n>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.

[eta oin shrdlu]

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(n⁴) regions to be searched, and this only removes O(n²) 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<F_n<F_n-1, which therefore means that lim_n->infinityF_n 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.

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.

This was the basis for the first algorithm I wrote. The problem with this is that it scales poorly with n; F_n has O(n⁴) 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(n⁴) regions (for a roughly O(n⁵) algorithm); I was able to get to roughly n=50 this way.

Edit: Actually, a good first approximation for F_n(x,y) (for small n) is 8/(m²), 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.

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 F_n>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(n⁴)) 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 f_k; these are bounded by their values at the corners of the region, so if you find f_a<f_b everywhere on the region then you can ignore f_b since f_a is always a tighter constraint. This helps a lot to reduce the O(n³) 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 F_n 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.12244897959183673469
7       0.41192355396933553342  0.26797254105688980989  0.10130928271558762582
15      0.41129032258064516129  0.26923076923076923077  0.097704714640198511166
17      0.38888888888888888889  0.26923076923076923077  0.096153846153846153846
18      0.41096127069393081320  0.26986608525108528004  0.095727634095299112588
22      0.38709677419354838710  0.26881720430107526882  0.093652445369406867846
26      0.38768758439569057200  0.26441346412356091000  0.093630485760991891605
34      0.38771085758397866871  0.26426503821669888769  0.092836285031665971406
49      0.41250047498531451088  0.26970548608343522189  0.088245899812021772132
63      0.38662941037604381527  0.26409015885919449177  0.083896442694257720143
75      0.38658974759034248408  0.26409010612154114942  0.083609996016538327379
106     0.42052266316465889623  0.23309613952770191772  0.082042513469911944733
107     0.41318433921561916293  0.27049686684699377282  0.079657965303179234655
122     0.41319277879547616864  0.27047887244054102580  0.078817091947903354571
196     0.42450414802312009610  0.37191530230868703680  0.077358907019254197086
285     0.36197807767768786265  0.23718600815947563265  0.074361119822964258315
312     0.36197796123593608164  0.23719163571675680656  0.074356465162087371279
384     0.41315549934923924308  0.27050377190776510246  0.072141955211891854199
695     0.41315551994498074115  0.27050463033571461004  0.071409811306328217718
973     0.41315555897072054681  0.27050473186119873817  0.070223297933440669160
1268    0.41315555819145344156  0.27050509952793400636  0.070199587205162297558
1353    0.43968316595550786279  0.17824998518839328044  0.069308033835312813062
2777    0.42460862747118442221  0.37813036402909279967  0.067272715567308741686
3641    0.42460839022295384501  0.37813036380254671437  0.067228911983136186550
5231    0.42460839045928670434  0.37813039599468557161  0.067125409842853360174
5551    0.39186184898804523886  0.29195611042829371811  0.065024173337685790082
6316    0.39186154875742867516  0.29195614437104387433  0.064752735014674793725
6477    0.39186154880125592524  0.29195613487482405949  0.064659611786142470844
10690   0.44039160329412810974  0.26899500698009196694  0.063391422205574132330
12398   0.42540258692288390211  0.22902594850417053235  0.061485945944967962156
15959   0.42540258460455583801  0.22902594837969366770  0.061030073494460500824
22045   0.42540258459909101293  0.22902594837940018156  0.061028998726122629845
24840   0.41877915883832255612  0.26802396122196505959  0.059417351179576625033
28046   0.41877915883835302970  0.26802396157693953880  0.059417349987121711844
29863   0.38363751580916999817  0.28052541705225926613  0.058364743856487626446
35020   0.38363751581041148833  0.28052541740141213341  0.058364743032276212049
82677   0.41877915937794298016  0.26802394184418440662  0.058205065888136270632
87022   0.46275847322715482431  0.27975230871557415907  0.057646679218635494844
88839   0.46275847310678965129  0.27975230871553084455  0.057646661544032551952

Analytic values available on request.

[tomtom2357]

Here are the numerical values I get:

Code: Select all

n                x                        y                    F_n(x,y)
3       0.42857142857142857143  0.28571428571428571429  0.12244897959183673469
7       0.41192355396933553342  0.26797254105688980989  0.10130928271558762582
15      0.41129032258064516129  0.26923076923076923077  0.097704714640198511166
17      0.38888888888888888889  0.26923076923076923077  0.096153846153846153846
18      0.41096127069393081320  0.26986608525108528004  0.095727634095299112588
22      0.38709677419354838710  0.26881720430107526882  0.093652445369406867846
26      0.38768758439569057200  0.26441346412356091000  0.093630485760991891605
34      0.38771085758397866871  0.26426503821669888769  0.092836285031665971406
49      0.41250047498531451088  0.26970548608343522189  0.088245899812021772132
63      0.38662941037604381527  0.26409015885919449177  0.083896442694257720143
75      0.38658974759034248408  0.26409010612154114942  0.083609996016538327379
106     0.42052266316465889623  0.23309613952770191772  0.082042513469911944733
107     0.41318433921561916293  0.27049686684699377282  0.079657965303179234655
122     0.41319277879547616864  0.27047887244054102580  0.078817091947903354571
196     0.42450414802312009610  0.37191530230868703680  0.077358907019254197086
285     0.36197807767768786265  0.23718600815947563265  0.074361119822964258315
312     0.36197796123593608164  0.23719163571675680656  0.074356465162087371279
384     0.41315549934923924308  0.27050377190776510246  0.072141955211891854199
695     0.41315551994498074115  0.27050463033571461004  0.071409811306328217718
973     0.41315555897072054681  0.27050473186119873817  0.070223297933440669160
1268    0.41315555819145344156  0.27050509952793400636  0.070199587205162297558
1353    0.43968316595550786279  0.17824998518839328044  0.069308033835312813062
2777    0.42460862747118442221  0.37813036402909279967  0.067272715567308741686
3641    0.42460839022295384501  0.37813036380254671437  0.067228911983136186550
5231    0.42460839045928670434  0.37813039599468557161  0.067125409842853360174
5551    0.39186184898804523886  0.29195611042829371811  0.065024173337685790082
6316    0.39186154875742867516  0.29195614437104387433  0.064752735014674793725
6477    0.39186154880125592524  0.29195613487482405949  0.064659611786142470844
10690   0.44039160329412810974  0.26899500698009196694  0.063391422205574132330
12398   0.42540258692288390211  0.22902594850417053235  0.061485945944967962156
15959   0.42540258460455583801  0.22902594837969366770  0.061030073494460500824
22045   0.42540258459909101293  0.22902594837940018156  0.061028998726122629845
24840   0.41877915883832255612  0.26802396122196505959  0.059417351179576625033
28046   0.41877915883835302970  0.26802396157693953880  0.059417349987121711844
29863   0.38363751580916999817  0.28052541705225926613  0.058364743856487626446
35020   0.38363751581041148833  0.28052541740141213341  0.058364743032276212049
82677   0.41877915937794298016  0.26802394184418440662  0.058205065888136270632
87022   0.46275847322715482431  0.27975230871557415907  0.057646679218635494844
88839   0.46275847310678965129  0.27975230871553084455  0.057646661544032551952

Analytic values available on request.

It is very interesting how the F_n for n=6477 is correct for all n up to 10690, and F₃₅₀₂₀ is accurate for all n up to 82677. I wonder why that is. Also, I looked at their asymptotic distribution, and it looks like F_n=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.

[eta oin shrdlu]

Also, I looked at their asymptotic distribution, and I found that the F_n=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=10¹⁰⁰ is too small.

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

[tomtom2357]

Also, I looked at their asymptotic distribution, and I found that the F_n=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=10¹⁰⁰ is too small.

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

Sorry about that, I jumped to conclusions without enough data.

[eta oin shrdlu]

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,F_n(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]

can't you just put it in a table like you did before?

[Dopefish]

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]

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?

[eta oin shrdlu]

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]

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.

[MarioTrevi]

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

F_N(x,y)=0 if either x or y is a rational number with denominator at most N; otherwise F_N(x,y)>0. So F_N 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 ~N²/3 such fractions, so there are O(N⁴) 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 f_k. (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 f_k.) For N>2 I haven't found any cases where the global maximum of F_N is at one of these maxima, but I don't know that it can't happen.

But considering up to three of the individual f_k should suffice to find all of the candidate maxima, so this gives an O(N⁷) 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 f_k 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(N⁴) Farey regions is to find an upper bound for F_N on the region. Each of the f_k is bilinear, so it is bounded by its values on the four corners of the region, and
F_N(x,y) <= min_k<=N max_{corners(xc,yc)} f_k(xc,yc).
So we can start with an O(N⁵) search over all these regions to find the bounds, then sort by decreasing size of the bound and do the O(N³) 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-f_k 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 F_N-1; if it works then it is necessarily the maximum for F_N as well. However: if not, you can't necessarily assume that f_N will be a constraint in the new maximum; there could be other maxima using only earlier constraints that were not cut off by f_N. (This happens at N=17; the maximum of 5/52 at (7/26,7/18) is at the intersections of f₃, f₅, f₁₅.)

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 F_N 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]

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

[tomtom2357]

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.

[MarioTrevi]

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

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(n⁴) regions to be searched, and this only removes O(n²) 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<F_n<F_n-1, which therefore means that lim_n->infinityF_n 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.

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.

This was the basis for the first algorithm I wrote. The problem with this is that it scales poorly with n; F_n has O(n⁴) 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(n⁴) regions (for a roughly O(n⁵) algorithm); I was able to get to roughly n=50 this way.

Edit: Actually, a good first approximation for F_n(x,y) (for small n) is 8/(m²), 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.

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 F_n>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(n⁴)) 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 f_k; these are bounded by their values at the corners of the region, so if you find f_a<f_b everywhere on the region then you can ignore f_b since f_a is always a tighter constraint. This helps a lot to reduce the O(n³) 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 F_n 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.12244897959183673469
7       0.41192355396933553342  0.26797254105688980989  0.10130928271558762582
15      0.41129032258064516129  0.26923076923076923077  0.097704714640198511166
17      0.38888888888888888889  0.26923076923076923077  0.096153846153846153846
18      0.41096127069393081320  0.26986608525108528004  0.095727634095299112588
22      0.38709677419354838710  0.26881720430107526882  0.093652445369406867846
26      0.38768758439569057200  0.26441346412356091000  0.093630485760991891605
34      0.38771085758397866871  0.26426503821669888769  0.092836285031665971406
49      0.41250047498531451088  0.26970548608343522189  0.088245899812021772132
63      0.38662941037604381527  0.26409015885919449177  0.083896442694257720143
75      0.38658974759034248408  0.26409010612154114942  0.083609996016538327379
106     0.42052266316465889623  0.23309613952770191772  0.082042513469911944733
107     0.41318433921561916293  0.27049686684699377282  0.079657965303179234655
122     0.41319277879547616864  0.27047887244054102580  0.078817091947903354571
196     0.42450414802312009610  0.37191530230868703680  0.077358907019254197086
285     0.36197807767768786265  0.23718600815947563265  0.074361119822964258315
312     0.36197796123593608164  0.23719163571675680656  0.074356465162087371279
384     0.41315549934923924308  0.27050377190776510246  0.072141955211891854199
695     0.41315551994498074115  0.27050463033571461004  0.071409811306328217718
973     0.41315555897072054681  0.27050473186119873817  0.070223297933440669160
1268    0.41315555819145344156  0.27050509952793400636  0.070199587205162297558
1353    0.43968316595550786279  0.17824998518839328044  0.069308033835312813062
2777    0.42460862747118442221  0.37813036402909279967  0.067272715567308741686
3641    0.42460839022295384501  0.37813036380254671437  0.067228911983136186550
5231    0.42460839045928670434  0.37813039599468557161  0.067125409842853360174
5551    0.39186184898804523886  0.29195611042829371811  0.065024173337685790082
6316    0.39186154875742867516  0.29195614437104387433  0.064752735014674793725
6477    0.39186154880125592524  0.29195613487482405949  0.064659611786142470844
10690   0.44039160329412810974  0.26899500698009196694  0.063391422205574132330
12398   0.42540258692288390211  0.22902594850417053235  0.061485945944967962156
15959   0.42540258460455583801  0.22902594837969366770  0.061030073494460500824
22045   0.42540258459909101293  0.22902594837940018156  0.061028998726122629845
24840   0.41877915883832255612  0.26802396122196505959  0.059417351179576625033
28046   0.41877915883835302970  0.26802396157693953880  0.059417349987121711844
29863   0.38363751580916999817  0.28052541705225926613  0.058364743856487626446
35020   0.38363751581041148833  0.28052541740141213341  0.058364743032276212049
82677   0.41877915937794298016  0.26802394184418440662  0.058205065888136270632
87022   0.46275847322715482431  0.27975230871557415907  0.057646679218635494844
88839   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 F_n 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]

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 F_n 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 F_n 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 F_n-1) we first check to see if this value is still good for F_n; 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]

If we made g_k(x) to be k<kx><ky>, where y=(3-sqrt(5))/2, and G_n(x)=min_k<=ng_k(x), and g(n)=max_0<=x<=1G_n(x). How does g(n) compare to f(n)? I know g(n)<=f(n), but are they related in any other way?