On Keen Approximations
By Titus Piezas III
Last Feb 2005, Ed Pegg Jr, who maintains Mathpuzzle.com and writes a column, Math Games, for MAA Online (Mathematical Association of America), wrote an article on “Keen Approximations”, http://www.maa.org/editorial/mathgames/mathgames_02-14_05.html. As he pointed out himself, a polynomial related to the Heegner number 163 (namely x3-6x2+4x-2) which I mentioned in an article I wrote, “Ramanujan’s Constant (epÖ163) And Its Cousins”, led to his interest in the topic.
The general idea is to find expressions using certain functions or operations that approximate integers, or maybe certain important constants like p. For the above-mentioned polynomial equated to zero, if x is its real root, then,
epÖ163 » 6403203+744 » x24-24
with a small error of about 7.5 x 10-13.
In his article, Pegg defined the concept of keenness as,
Keenness = log10(max(CF))/complexity
where log10 is to the base 10, max(CF) is a continued fraction term (or equivalently, the error difference between the approximant and the integer). The complexity is basically the number of digits or functions used.
To quote his rules, we have,
“My rules to measure the keenness of an approximation are as follows:
As an example, the approximant with the highest keenness, at least for the moment, was the expression (in radians), sin(2017*21/5) by Michael Trott . It uses 6 digits and 1 function, so its complexity is 7. Since its error difference is 2.15 x 10-17, then,
Keenness = Log10(2.15 x 10-17)/7 = 2.381
We shall see that we can more than double this value.
In Ramanujan’s Constant (epÖ163) and Its Cousins, we discussed discriminants d with class number n, certain modular functions, and class polynomials P(x), namely the Hilbert, Weber, and Ramanujan class polynomials. We can use these, and in particular, the Weber class polynomials, to devise four systematic methods to find approximants with high keenness. However, we will have to divide our discussion for odd d, not divisible by 3, of form 8m+3 and 8m+7. (From this point, we will maintain the assumption of d as not divisible by 3.)
Let, y = x124-24, where x1 is the appropriate real root of the Weber class polynomial P(x).
Method 1.
M1 = (Log(y)/p)2; Initial complexity = 8
Method 2.
M2 = (Log(y2-552)/p)2; Initial complexity = 12
where this time, the log function is to the base e. M1 and M2 are then very good approximations to the integers d and 4d, respectively, where d is of form 8m+3.
Now where did we get 24, as well as 552 = 2(276)? Did we pluck them out of thin air? Of course not. To recall, the Weber function, w(q), had the q-series expansion,
w(q) = 1/q + 24 + 276q + 2048q2 + 11202q3 +….
so the first three terms should explain those values. The initial complexity (I) still needs to be added to the complexity of the Weber class polynomial. Since the subscript of the root x1 has already been counted in the initial complexity, then the polynomial complexity (P) will only be the number of digits used in the coefficients of the polynomial P(x), and total complexity (C), of course, will be C = I + P
Example,
Let, P(x) = x3-6x2+4x-2, for d = 163, with polynomial complexity P = 4.
And,
y = x124-24
For method 1, total complexity is C = 8+4 =12,
163 – (Log(y)/p)2 = -3.254622 x 10-32
Then,
Keenness = Log10(3.254622 x 10-32)/12 = 2.6239.
which is already higher than the highest, 2.381, in the table compiled in Keen Approximations.
For method 2, total complexity is C = 12+4 =16,
4*163 – (Log(y2-552)/p)2 = -3.861648 x 10-44
Then,
Keenness = Log10(3.861648 x 10-44)/16 = 2.9646.
Let, y = (x1Ö2)24-24, where x1 is the appropriate real root of the Weber class polynomial P(x).
Method 3.
M3 = (Log(y)/p)2; Initial complexity = 10
Method 4.
M4 = (Log(y2-552)/p)2; Initial complexity = 14
Then M3 and M4 are likewise very good approximations to the integers d and 4d, respectively, where d is of form 8m+7.
Example,
Let, P(x) = x9-99x8+38x7-89x6+42x5-65x4+37x3-22x2+5x-1, for d = 1423, with polynomial complexity P = 17.
And,
y = (x1Ö2)24-24
For method 3, total complexity is C = 10+17 = 27,
1423 – (Log(y)/p)2 = -7.683297 x 10-100
Then,
Keenness = Log10(7.683297 x 10-100)/27 = 3.6709.
For method 4, total complexity is C = 14+17 = 31,
4*1423 – (Log(y2-552)/p)2 = -7.764375 x 10-150
(M4 is the integer 4*1423 followed by 150 zeros before we see other digits.) Then,
Keenness = Log10(7.764375 x 10-150)/31 = 4.8099.
which, as was mentioned, is more than double the highest in the table!
Since the initial complexities are fixed, being the complexity measure of the common form, or the template, for these kind of approximations, then the polynomial complexity is the determining factor in the total complexity. So one objective is to find polynomials that use as few digits as possible (counting zeros), while using a d as large as possible.
As we have pointed out in “Ramanujan’s Constant…”, if we have d of form 8m+3 with class number n, then its Weber class polynomial is of degree 3n. Thus, its polynomial complexity rises quite fast. However, for d of form 8m+7 with class number n, its Weber class polynomial is only of degree n. Method 4 should be the most promising when finding approximations with high keenness.
I can see one potential problem. If we are going to come up with a list of twenty approximations with the highest keenness using the present rules, it will be swamped with class polynomials.
It might be argued that the Mi functions are asymptotic. If we define asymptotic as “approaching a given value arbitrarily closely”, then perhaps it is not, as the Mi correspond to the infinite number of integers d of form 8m+3 or 8m+7. However, perhaps d-M1 (or M3) and 4d-M2 (or M4) can be considered asymptotic. In general, the larger the d, the closer the error difference will be to zero. But, like the Pisot numbers, if we rule out class polynomials, it would be a pity, since it would rule out the class polynomial x3-6x2+4x-2, the catalyst for the article in the first place!
One solution seems to be to rule out taking the logarithm of a class polynomial root, though that is only a suggestion, and a half-hearted one at that. As a consequence, this would invalidate entry 3 and 4 in Pegg’s table, since they are analogous to the Mi functions here, though using Hilbert class polynomials. As a side note, the seemingly arbitrary value 393768 = 2*196884 found in entry 4 can be explained. To recall, the j-function associated with the Hilbert class polynomial has the q-series expansion,
j(q) = 1/q + 744 + 196884q + 21493760q2 + 864299970q3 + …
so the first three terms explains the values used in entry 3 and 4.
Obviously, this rule would also invalidate the Mi functions we have presented in this article, thus, the not-so-enthusiastic suggestion. Talk about shooting yourself in the foot! However, list-making aside, the reason why these functions were introduced nonetheless is that measuring their keenness does raise certain interesting theoretical questions. As we have pointed out, the error difference depends significantly on the magnitude of the discriminant d so in general, the larger the d, the smaller the error. However, the polynomial complexity depends in part on both d and its class number n. A large d does not always have a higher complexity than a smaller d.
We can illustrate our point by giving the complete list of fundamental d = 8m+7 (not divisible by 3) for class number not greater than 9. Fortunately, it is a short list, just 20 discriminants. The convention {c1, c2,…-1} is the coefficient list of an equation of degree n, going left-to-right, with c1 for the xn term and -1 as the constant term.
Class # 3; d = 23, 31
d23 = {1, 0, -1, -1}
d31 = {1, -1, 0, -1}
Class # 4; d = 55
d51 = {1, -2, 0, 1, -1}
Class # 5; d = 47, 79, 103, 127
d47 = {1, 0, -1, -2, -2, -1}
d79 = {1, -3, 2, -1, 1, -1}
d103 = {1, -1, -3, -3, -2, -1}
d127 = {1, -3, -1, 2, 1, -1}
Class # 6; d = 247
d247 = {1, -4, -7, -7, -6, -3, -1}
Class # 7; d = 71, 151, 223, 463, 487
d71 = {1, -2, -1, 1, 1, 1, -1, -1}
d151 = {1, -3, -1, -3, 0, -1, -1, -1}
d223 = {1, -5, 0, 1, -4, -1, 0, -1}
d463 = {1, -11, -9, -8, -7, -7, -3, -1}
d487 = {1, -13, 4, -4, 7, -4, 1, -1}
Class # 8; d = 95, 583
d95 = {1, -2, -2, 1, 2, -1, 0, 1, -1}
d583 = {1, -16, -12, 11, 12, 5, -3, -4, -1}
As one can see, class polynomials for d = 8m+7 have beautifully low polynomial complexities, at least for these low class numbers. As a specific example of the point made earlier, d95 with a class number of 8 has a complexity of 9, while d103 with class number 5 has a lower polynomial complexity of 6.
When we go into the higher class numbers, say, class number nine:
Class # 9; d = 199, 367, 823, 1087, 1423
d199 = {1, -5, 3, -3, 0, 0, -3, 0, -1, -1}
d367 = {1, -9, 3, -2, 0, 2, -6, 1, 2, -1}
d823 = {1, -29, -36, -30, -33, -30, -12, 0, -1, -1}
d1087 = {1, -51, -100, -139, -124, -100, -61, -28, -8, -1}
d1423 = {1, -99, 38, -89, 42, -65, 37, -22, 5, -1}
we find that while there are bigger discriminants d, the complexities are also increasing. So, the keenness will be pulled in two opposing directions: the error difference is getting smaller while the complexity is getting bigger. We can then ask two questions:
a) Can the keenness of the Mi functions, especially i = 3, 4, be made arbitrarily high, or is there a maximum ceiling? (Taking note that by choosing bigger d, complexity is also getting high.)
b) Can the keenness of the same Mi functions be made arbitrarily low, or is there a minimum floor? (Taking note that by choosing higher class numbers, the discriminants d are also getting bigger.)
The highest keenness I’ve found so far, 4.8099, is for d = 1423 with class number 9. Obviously, there would be higher d. For class number 10 and 11, none were bigger. For class number 12, we have d = 1807. However, its polynomial complexity was much higher so its keenness turned out to be lower. For higher class numbers up to 20, an inspection didn’t reveal any promising d, as their high complexities seemed to cancel out their low error differences, though I could be mistaken.
So, is the keenness of M4 using d = 1423, the maximum keenness for approximations of this form?
(Note: For an extensive list of Weber class polynomials for d up to 422500, the interested reader is referred to Annegret Weng’s webpage, Class Polynomials of CM-Fields, http://www.exp-math.uni-essen.de/zahlentheorie/classpol/class.html)
-- End --
© 2005
Titus Piezas III
Mar. 9, 2005
www.oocities.org/titus_piezas/ ¬ (Click here for an index of papers, articles.)
References