help with diophantine approximation.
Moderators: gmalivuk, Moderators General, Prelates

 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(ab,22a2b,33a3b,...,77a7b), 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 ab is nasty on the eyes ...)
min ( <a><b>, 2<2a><2b> )
min ( <a><b>, 2<2a><2b>, 3<3a><3b> )
...
?
(I'm using <a> for your a, since ab is nasty on the eyes ...)

 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 ab 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=(4sqrt(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.
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
36 > 2/7, 3/7
78 > 2/9, 4/9
912 > 3/13, 5.5/13 or 6/26, 11/26
1318 > 7/19, 8/19
1920 > no idea, a=0.275787 and b=0.382332 but don't trust the last digit
2122 > a=0.31128 and b=0.218001
2325, 2627, 2830 are the following groups.
Edit: Strange typo fixed
We have
36 > 2/7, 3/7
78 > 2/9, 4/9
912 > 3/13, 5.5/13 or 6/26, 11/26
1318 > 7/19, 8/19
1920 > no idea, a=0.275787 and b=0.382332 but don't trust the last digit
2122 > a=0.31128 and b=0.218001
2325, 2627, 2830 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.

 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
36 > 2/7, 3/7
78 > 2/9, 4/9
912 > 3/13, 5.5/13 or 6/26, 11/26
1318 > 7/19, 8/19
1920 > no idea, a=0.275787 and b=0.382332 but don't trust the last digit
2122 > a=0.31128 and b=0.218001
2325, 2627, 2830 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.
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 2sqrt(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 hillclimbing to reach a local maximum, then repeat that 100000 times.
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 2sqrt(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 hillclimbing to reach a local maximum, then repeat that 100000 times.

 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 2sqrt(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 hillclimbing 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=(4133sqrt(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.
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=(4133sqrt(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 2sqrt(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(4a1)(24b) = 5(5a1)(5b2) = 7(27a)(37b), 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.

 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 2sqrt(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(4a1)(24b) = 5(5a1)(5b2) = 7(27a)(37b), 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>infinity}f(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.
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.
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.

 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.
Re: help with diophantine approximation.
Sorry, I can't offer any constructive help on this problem.
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.
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.

 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 (4133sqrt(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.
Re: help with diophantine approximation.
Fair enough.

 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.
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 runtime. 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: 442
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: help with diophantine approximation.
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 orderN Farey sequence. There are ~N^{2}/3 such fractions, so there are O(N^{4}) such regions, and so jaap's hillclimbing 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^{7}) 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 orderN Farey fractions, but half of each orderN 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^{4}) 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^{5}) search over all these regions to find the bounds, then sort by decreasing size of the bound and do the O(N^{3}) 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 threef_{k} intersections; for 48<N<63 I get a maximum of
(3094 (12788836+1547 sqrt(144153949)))/1099613344833
at
(x,y)=((274165sqrt(144153949))/972018,(945304sqrt(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_{N1}; 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_{3}, f_{5}, f_{15}.)
I can think of some other possible pruning techniques, but I haven't tried them.
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 orderN Farey sequence. There are ~N^{2}/3 such fractions, so there are O(N^{4}) such regions, and so jaap's hillclimbing 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^{7}) 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 orderN Farey fractions, but half of each orderN 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^{4}) 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^{5}) search over all these regions to find the bounds, then sort by decreasing size of the bound and do the O(N^{3}) 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 threef_{k} intersections; for 48<N<63 I get a maximum of
(3094 (12788836+1547 sqrt(144153949)))/1099613344833
at
(x,y)=((274165sqrt(144153949))/972018,(945304sqrt(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_{N1}; 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_{3}, f_{5}, f_{15}.)
I can think of some other possible pruning techniques, but I haven't tried them.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: help with diophantine approximation.
I think that F_{n}(x,y)=f_{n}(x,y) or F_{n}(x,y)=F_{n1}(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: 442
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: help with diophantine approximation.
True...tomtom2357 wrote:I think that F_{n}(x,y)=f_{n}(x,y) or F_{n}(x,y)=F_{n1}(x,y) (which is easy to check)
... maybe. You can avoid recalculating intersection points if you cache the previouslycomputed 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.which may help with the algorithms.
It is probably worthwhile to use previouslycomputed lists at smaller N as looser upper bounds (each region covering multiple orderN Farey regions), only subdividing the ones which pass the current thresholds. I haven't tried that yet.

 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: 442
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: help with diophantine approximation.
Well, for the exhaustive search of Farey regions (the approach described in my first post), there are O(n^{4}) regions to be searched, and this only removes O(n^{2}) 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.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.
I've been working on a priorityqueued 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?)

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: help with diophantine approximation.
eta oin shrdlu wrote:Well, for the exhaustive search of Farey regions (the approach described in my first post), there are O(n^{4}) regions to be searched, and this only removes O(n^{2}) 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.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.
I've been working on a priorityqueued 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_{n1}, which therefore means that lim_{n>infinity}F_{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^{2}), 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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 eta oin shrdlu
 Posts: 442
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: help with diophantine approximation.
tomtom2357 wrote:eta oin shrdlu wrote:Well, for the exhaustive search of Farey regions (the approach described in my first post), there are O(n^{4}) regions to be searched, and this only removes O(n^{2}) 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.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.
I've been working on a priorityqueued 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?)
OK. Finding a pattern seems like it will probably be difficult.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<F_{n}<F_{n1}, which therefore means that lim_{n>infinity}F_{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.
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.
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^{4}) 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.)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.
You can save computation by doing a local maximization within each of these O(n^{4}) regions (for a roughly O(n^{5}) algorithm); I was able to get to roughly n=50 this way.
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: Actually, a good first approximation for F_{n}(x,y) (for small n) is 8/(m^{2}), where m is the first odd number after n. This works by setting x=2/m, y=4/m.
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.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 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.
The approach I described in my first post was a simplification of this idea: I computed bounds for all of the ordern 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^{4})) 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 maximathis 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^{3}) 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

 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:Analytic values available on request.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
It is very interesting how the F_{n} for n=6477 is correct for all n up to 10690, and F_{35020} 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.
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: 442
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: help with diophantine approximation.
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!tomtom2357 wrote: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!
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 slowlyeven n=10^{100} is too small.
[I'll tabulate the analytic forms for (x,y,F_{n}(x,y)) sometime soon, maybe later tonight.]

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: help with diophantine approximation.
eta oin shrdlu wrote: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!tomtom2357 wrote: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!
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 slowlyeven n=10^{100} 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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 eta oin shrdlu
 Posts: 442
 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,F_{n}(x,y)).
Spoilered for space: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.
Spoilered for space:
Spoiler:

 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.
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 nonambiguous), 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).
You really don't want to do that with standard text (as you need a metric butt ton of parentheses to be nonambiguous), 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).

 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: 442
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: help with diophantine approximation.
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 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?

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

 Posts: 4
 Joined: Tue Sep 27, 2011 5:30 pm UTC
Re: help with diophantine approximation.
eta oin shrdlu wrote: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 orderN Farey sequence. There are ~N^{2}/3 such fractions, so there are O(N^{4}) such regions, and so jaap's hillclimbing 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^{7}) 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 orderN Farey fractions, but half of each orderN 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^{4}) 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^{5}) search over all these regions to find the bounds, then sort by decreasing size of the bound and do the O(N^{3}) 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 threef_{k} intersections; for 48<N<63 I get a maximum of
(3094 (12788836+1547 sqrt(144153949)))/1099613344833
at
(x,y)=((274165sqrt(144153949))/972018,(945304sqrt(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_{N1}; 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_{3}, f_{5}, f_{15}.)
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 bruteforce, simpleminded 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 xaxis or the yaxis. Later, I used random continued fractions
to produce the pseudorandom 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 xcoordinate and/or ycoordinate 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
"aboveaverage" area compared to all the Farey regions of order N.
 eta oin shrdlu
 Posts: 442
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: help with diophantine approximation.
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(N1)).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
"aboveaverage" area compared to all the Farey regions of order N.
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

 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=(3sqrt(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.

 Posts: 4
 Joined: Tue Sep 27, 2011 5:30 pm UTC
Re: help with diophantine approximation.
eta oin shrdlu wrote: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(N1)).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
"aboveaverage" area compared to all the Farey regions of order N.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 subdivision", Fareyregion subdivision being the "cause".
From your data, I see that any Farey region with a maximum (given N) of 0.06 or less is automatically
ruledout 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 subdivisions) 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 onthefly ; 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() .

 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:Well, for the exhaustive search of Farey regions (the approach described in my first post), there are O(n^{4}) regions to be searched, and this only removes O(n^{2}) 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.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.
I've been working on a priorityqueued 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?)OK. Finding a pattern seems like it will probably be difficult.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<F_{n}<F_{n1}, which therefore means that lim_{n>infinity}F_{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.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.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^{4}) 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.)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.
You can save computation by doing a local maximization within each of these O(n^{4}) regions (for a roughly O(n^{5}) algorithm); I was able to get to roughly n=50 this way.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: Actually, a good first approximation for F_{n}(x,y) (for small n) is 8/(m^{2}), where m is the first odd number after n. This works by setting x=2/m, y=4/m.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.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 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.
The approach I described in my first post was a simplification of this idea: I computed bounds for all of the ordern 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^{4})) 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 maximathis 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^{3}) 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:Analytic values available on request.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
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 subdividing until n reaches about 5551. Do you keep a record of the regions not currently
in need of subdividing? 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
 Posts: 442
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: help with diophantine approximation.
Yes, the current version of my program maintains bounds on rectangular regions covering all of the lowertriangular 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.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 subdividing until n reaches about 5551. Do you keep a record of the regions not currently
in need of subdividing? 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.
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_{n1}) 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 ordern 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 lowerbound 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 numericalprecision issue that I saw first.
Good; those values agree with the values I tabulated above (for n=34; actually <your y>=1<my y>).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

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: help with diophantine approximation.
If we made g_{k}(x) to be k<kx><ky>, where y=(3sqrt(5))/2, and G_{n}(x)=min_{k<=n}g_{k}(x), and g(n)=max_{0<=x<=1}G_{n}(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.
Who is online
Users browsing this forum: No registered users and 1 guest