Moderators: gmalivuk, Prelates, Moderators General
Proginoskes wrote:Have you tried solving simpler problems, like maximizing
min ( <a><b>, 2<2a><2b> )
min ( <a><b>, 2<2a><2b>, 3<3a><3b> )
...
?
(I'm using <a> for your ||a||, since ||a||||b|| is nasty on the eyes ...)
mfb wrote:This is interesting. Numberical approximation suggests (2/9, 4/9) for the problem up to 7. This is fine for 8, too, whereas 9 gives (6/26,11/26)=(3/13,5.5/13) and that stays constant up to max=12.
We have
3-6 -> 2/7, 3/7
7-8 -> 2/9, 4/9
9-12 -> 3/13, 5.5/13 or 6/26, 11/26
13-18 -> 7/19, 8/19
19-20 -> no idea, a=0.275787 and b=0.382332 but don't trust the last digit
21-22 -> a=0.31128 and b=0.218001
23-25, 26-27, 28-30 are the following groups.
jaap wrote:Since we can add any integer to a or b, change their sign, or swap them, we can assume w.l.o.g. that 0<=a<=b<=0.5 .
For n=3...6 I also get 2/7 and 3/7.
For n=7...14 I get 0.26797254107 and 0.4119235539. The first number seems to be 2-sqrt(3), but I don't recognise the second.
For n=15...16 I get 0.26923076923 and 0.4112903224. The first number seems to be 7/26, but again I don't recognise the second.
For n=17 I get 0.26923076923 and 0.388888888. The first number seems to be 7/26, the second 7/18.
I just used a random starting point plus hill-climbing to reach a local maximum, then repeat that 100000 times.
tomtom2357 wrote:That looks like a it is the right answer, I haven't found any value that beats that, but can you prove that these are the optimal values? Also, I have a method that can use your approximate values to give an exact value given that the approximation is accurate enough, can you give me some more values? The values for 7<=n<=14 are a=(115+sqrt(16881))/914, b=(4133-sqrt(16881))/9718, using your approximation and my method, and these values almost exactly match your approximation.
jaap wrote:a=0.26797254105689, b=0.41192355396933 is about as accurate as I can get it right now (their last digit may be one more or less). It isn't 2-sqrt(3), but it seems to me unlikely to be such a complicated expression as you gave.
Edit: No, you're entirely correct. These a and b are the solutions to 4(4a-1)(2-4b) = 5(5a-1)(5b-2) = 7(2-7a)(3-7b), which is when three of the terms in the Min() expression are equal. I think it will always be the case that at a (local) optimum at least three of the terms are equal (otherwise you can perturb a,b to get a better minimum). To prove it is optimal you would probably have to check all triplets, and for all possible nearest integers.
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.
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).
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.
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.
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.
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.
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.
True...tomtom2357 wrote: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)
... 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.which may help with the algorithms.
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.
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 priority-queued version (described in my second post). This is definitely much faster as long as memory is available to hold the queue. It's still got a bug in it though.
What are you hoping to get from these maxima? (I know you're thinking about the Littlewood conjecture, but is there a specific question you're hoping these values will answer?)
tomtom2357 wrote: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 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?)
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_{n-1}, 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.
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.
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
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
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!
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 slowly--even n=10^{100} is too small.
[I'll tabulate the analytic forms for (x,y,F_{n}(x,y)) sometime soon, maybe later tonight.]
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?
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 order-N Farey sequence. There are ~N^{2}/3 such fractions, so there are O(N^{4}) 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^{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 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^{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 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_{3}, f_{5}, f_{15}.)
I can think of some other possible pruning techniques, but I haven't tried them.
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)).MarioTrevi wrote:I have seen that you did computations for N up to 10^4 or beyond. Given your approach using Farey regions,
I wanted to ask you if the optimimum point or points for a given N tend to fall in Farey regions that have
"above-average" area compared to all the Farey regions of order N.
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
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(N-1)).MarioTrevi wrote:I have seen that you did computations for N up to 10^4 or beyond. Given your approach using Farey regions,
I wanted to ask you if the optimimum point or points for a given N tend to fall in Farey regions that have
"above-average" area compared to all the Farey regions of order N.
- 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
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 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?)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_{n-1}, 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 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^{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 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^{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
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.MarioTrevi wrote:Lots of good ideas, for example:
"You can save on memory by not subdividing all of the rectangles to order n; instead, just subdivide rectangles whose bounds are large enough to be possible locations of maxima--"
So if with n = 1000, a region had a maximum of 0.065 for the k <kx> <ky> , 1<= k <= 1000, it wouln't matter and
wouldn't need sub-dividing until n reaches about 5551. Do you keep a record of the regions not currently
in need of sub-dividing? I would guess yes, because for larger n ( n ~= 5551 for a local max. of 0.065),
the region could be a contender for containing the max. of F_{n} for some n between 6000 and 10,000
for example.
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
Users browsing this forum: >-) and 7 guests