e^m 2^n

[gmalivuk]

Over in another thread, a poster ascribed some significance to (iirc) e/2^11, to which I responded,

Furthermore, you can multiply powers of e and powers of 2 together to get pretty close to infinitely many different numbers, but that doesn't mean they're terribly important. You want something close to pi? e^6/2^7 is pretty close

My question is: what is the distribution of the set A = {e^m 2^n | m, n integers}? In particular, I was wondering if it might actually be dense, so that you could get arbitrarily close to *any* given real number just by multiplying (integer) powers of e and 2 together. Unfortunately, it's been too long since I had to do any real math to know how to begin attacking this problem. Any suggestions?

[eta oin shrdlu]

Pigeonhole principle.

[gmalivuk]

How would that work? The set in question is countably infinite, and there are some dense countable subsets of R while others aren't dense. Does the pigeonhole say anything about something beyond cardinality that I'm not remembering?

[jestingrabbit]

Well, you'll never get negatives, so what you can reasonably hope for is dense in the non negative reals, and this is doable.

Consider B = { ln(a) | a in A} = {m + ln(2)*n | m and n are integers}. This is dense in the reals: you can get arbitrarily small numbers in there (by estimating ln(2) with rational numbers) and if b is in B, then so is nb for any natural n.

Because B is dense in the reals, A is dense in the non negative reals, as exp is continuous.

[eta oin shrdlu]

Well, the pigeonhole principle tells you that there must be two of the values {e^m 2^n} that get as close as you like. The other important part is that this set is closed under multiplication and division, so you can use a ratio near 1 to get close to any other desired value.

For any m, you can choose n so that e^m 2^n lies in [1,2). All of these values are different (since e is transcendental), so for any epsilon>0 you can find two of the values within epsilon, say
1 < (e^a 2^b)/(e^c 2^d) < 1+epsilon
and so there are integers m=a-c and n=b-d with
1 < e^m 2^n < 1+epsilon.

I find it a little more natural to look at the logarithms, m + n log 2; because log 2 is irrational these must densely fill, say, [0,1) and so the real line as well.

[gmalivuk]

Because B is dense in the reals, A is dense in the non negative reals, as exp is continuous.

Oh, right. I was second guessing myself thinking about how small differences in logarithm can become big differences after exp is applied. Basically, I think I was remembering this thread, and the fact that knowing {sin(n) | n in N} is dense (and thus gets arbitrarily close to 1 infinitely often) doesn't prove divergence, since there's that exponent there to magnify differences.

[benneh]

Consider B = { ln(a) | a in A} = {m + ln(2)*n | m and n are integers}. This is dense in the reals: you can get arbitrarily small numbers in there (by estimating ln(2) with rational numbers) and if b is in B, then so is nb for any natural n.

A minor quibble: You can approximate ln(2) with rationals; that is, given epsilon, you can find n, m with |m/n - ln(2)| < epsilon. You can then get |m - n*ln(2)| < n*epsilon. But n depends on epsilon; is it not conceivable that, as epsilon gets smaller, the necessary n increases too fast? I can't think of any obvious situation where this is the case, but neither can I think of any reason why it shouldn't be. Effectively, you need to ensure that you can find n, m with |m/n - ln(2)| < epsilon AND with n increasing slower than 1/epsilon, or something similar, surely?

[gmalivuk]

If x is irrational, then its irrationality measure is at least 2. This means that, for example, \(0<\left|x-\frac{p}{q}\right|<q^{-3/2}\) has infinitely many integer solutions for p and q. So the same is true for \(0<\left|qx-p\right|<q^{-1/2}\), which can be made less than any given epsilon.

[jestingrabbit]

Consider B = { ln(a) | a in A} = {m + ln(2)*n | m and n are integers}. This is dense in the reals: you can get arbitrarily small numbers in there (by estimating ln(2) with rational numbers) and if b is in B, then so is nb for any natural n.

A minor quibble: You can approximate ln(2) with rationals; that is, given epsilon, you can find n, m with |m/n - ln(2)| < epsilon. You can then get |m - n*ln(2)| < n*epsilon. But n depends on epsilon; is it not conceivable that, as epsilon gets smaller, the necessary n increases too fast? I can't think of any obvious situation where this is the case, but neither can I think of any reason why it shouldn't be. Effectively, you need to ensure that you can find n, m with |m/n - ln(2)| < epsilon AND with n increasing slower than 1/epsilon, or something similar, surely?

Yeah, true, but its not actually a problem. The simplest, most memorable (for me) result that tells you that the argument is okay is Hurwitz's Theorem.

http://en.wikipedia.org/wiki/Hurwitz%27 ... _theory%29

[eta oin shrdlu]

Yeah, true, but its not actually a problem. The simplest, most memorable (for me) result that tells you that the argument is okay is Hurwitz's Theorem.

I agree. And if the constant factor of 1/sqrt(5) is not important, you can prove a simpler inequality (Dirichlet's approximation theorem) in a few lines using the pigeonhole principle.

[gmalivuk]

The simplest, most memorable (for me) result that tells you that the argument is okay is Hurwitz's Theorem.

Oh right, I remember proving that, now. It also makes clear the sense in which the golden ratio can be said to be the irrational number "farthest" from a series of rational approximants, because any factor in that denominator greater than sqrt(5) fails to work for it.

[PM 2Ring]

Over in another thread, a poster ascribed some significance to (iirc) e/2^11, to which I responded,

Furthermore, you can multiply powers of e and powers of 2 together to get pretty close to infinitely many different numbers, but that doesn't mean they're terribly important. You want something close to pi? e^6/2^7 is pretty close

Following jestingrabbit's suggestion of estimating log(2) by rational numbers, I used continued fractions and the extended Euclidean algorithm to generate expressions of the form e^m 2^n that approximate pi. It's doable, but this is certainly not a practical method to approximate arbitrary reals as m and n rapidly grow rather large for even rough approximations, eg,
exp(191580860 - 276392755 * log(2)) ~= 3.141040999

Whereas this integer-based expression performs much better:
log(262537412640768744) / sqrt(163) ~= 3.14159265358979323846264338327972662
OTOH, that expression uses a property of the Heegner numbers, and 163 is the highest Heegner number, so there are no superior expressions of that form.


Edit
Here's an improved approximation:
exp(-3521804314145 + 5080889619000 * log(2)) ~= 3.1415924648

[eta oin shrdlu]

Following jestingrabbit's suggestion of estimating log(2) by rational numbers, I used continued fractions and the extended Euclidean algorithm to generate expressions of the form e^m 2^n that approximate pi. It's doable, but this is certainly not a practical method to approximate arbitrary reals as m and n rapidly grow rather large for even rough approximations, eg,
exp(191580860 - 276392755 * log(2)) ~= 3.141040999

Whereas this integer-based expression performs much better:
log(262537412640768744) / sqrt(163) ~= 3.14159265358979323846264338327972662
OTOH, that expression uses a property of the Heegner numbers, and 163 is the highest Heegner number, so there are no superior expressions of that form.


Edit
Here's an improved approximation:
exp(-3521804314145 + 5080889619000 * log(2)) ~= 3.1415924648

I'm not sure exactly what your algorithm is, but it's possible to do better than these examples (though not as well as the spectacular sqrt(163) result): e.g.,
exp(47247985 - 68164432 * log(2)) ~= 3.14159265[416505]
and
exp(-3203012462534 + 4620970195605*log(2)) ~= 3.141592653589[68227]
These have error roughly 1/|n|, which is about as close as we should expect to get.

(To get these, I started by finding the CFE convergents to log(2) with their errors, then subtracted these errors from the initial fit error of log(pi) at m=n=0 to get successively better approximations.)

[PM 2Ring]

I'm not sure exactly what your algorithm is, but it's possible to do better than these examples (though not as well as the spectacular sqrt(163) result): e.g.,
exp(47247985 - 68164432 * log(2)) ~= 3.14159265[416505]
and
exp(-3203012462534 + 4620970195605*log(2)) ~= 3.141592653589[68227]
These have error roughly 1/|n|, which is about as close as we should expect to get.

(To get these, I started by finding the CFE convergents to log(2) with their errors, then subtracted these errors from the initial fit error of log(pi) at m=n=0 to get successively better approximations.)

Nice work, eta oin shrdlu!

I was intentionally vague with my algorithm description, in the hope that someone would come up with a more accurate one. My algorithm is very basic: it totally ignores errors in the CFE convergents.

Let x = e^m2ⁿ
log x = m + n * log 2
Let x ~= u / v, using standard continued fraction techniques
u = v * m + v * log 2 * n
Let v * log 2 ~= p / q, once again using continued fractions
u * q = (v * q) * m + p * n

Now use the extended Euclidean algorithm to find a, b:
(v * q) * a + p * b = 1
(v * q) * a * u * q + p * b * u * q = u * q
(v * q) * (a * u * q + k * p) + p * (b * u * q - k * v * q) = u * q, for any k
Let k be the closest integer to -a * u * q / p or to b * u / v
Then m = a * u * q + k * p and n = b * u * q - k * v * q

FWIW, I was pondering how to deal with those continued fraction errors earlier today... I was also considering investigating what happens when you generate upper and lower bounding expressions and take their geometric mean.

[eta oin shrdlu]

Nice work, eta oin shrdlu!

Thanks! I don't think I've run across exactly this approximation problem before, so it was interesting to work through.

Python code to generate these approximations, spoilered for space:

Spoiler:

Code: Select all

# Find good approximations e^m 2^n to pi, i.e. integers m and n with
#   ln(pi) ~= n*ln(2) + m    [y ~= n*x +m in notation below],
# <http://forums.xkcd.com/viewtopic.php?f=17&t=83323>.
#
# Visualization: rectangular lattice with horizontal spacing 1 and vertical
# spacing ln(2); a line L with slope -1 passing through (ln(pi),0) and
# (0,ln(pi)) is the locus of points with coordinates summing to ln(pi), and
# so we want to find lattice points close to this line.
#
# We start by finding good rational approximations to ln(2) via CFE; if we
# have a/b with b*ln(2)-a=d small (< ~ 1/b), then the line through lattice
# points (0,0) and (-a,b*ln(2)) has slope nearly -1 and so is nearly
# parallel to the locus L of interest.
#
# Now we look for lattice points close to L.  If we have a point (m,n*ln(2))
# a vertical distance |t|>d/2 from L, then we can find a closer one by
# stepping by +-(-a,b*ln(2)) along the line.  We just use a greedy approach,
# translating by the first CFE convergent with error smaller than 2|t|.


# use mpmath module (arbitrary-precision floating-point math) if available;
# get this from <http://code.google.com/p/mpmath/>
try:
  from mpmath import *
  print "Using mpmath."
  # work to this many digits of precision; expect results good to
  # roughly half this many digits
  workdigits = 80
  mp.dps = workdigits
except:
  from math import *
  import sys
  try:    eps = sys.float_info.epsilon
  except: eps = 1E-16
  workdigits = -int(floor(log10(eps)))
  print "No mpmath library; working to machine precision."
  nstr = lambda x,n: "%.*f" % (n,x)
print "  Working to %d digits; expect results to ~%d digits." % (workdigits,workdigits//2)
print

# use fractions module if available (standard in Python 2.6+); otherwise use
# a homegrown version
try:
  from fractions import Fraction
except:
  from Rational import *
  Fraction = Rational


# compute up to n terms in the continued-fraction expansion for x, and
# return these terms and the corresponding convergents; each element in the
# convergent list is a 3-tuple (e,p,q) where the error e=p-x*q is O(1/q)
def CFE(x,n,eps):
  xcfe = [ ]
  pqe  = [ ]
  dx = x
  for m in range(n):
    r = int(floor(dx))
    xcfe.append(r)
    dx = 1. / (dx-r)
    if not dx: break

    if not m: continue

    rm = Fraction(0,1)
    for k in xrange(m,-1,-1):
      rm = 1 / (xcfe[k] + rm)
    qm,pm = rm.numerator,rm.denominator

    xm = float(pm)/qm  # CFE convergent value
    em = pm - x * qm   # lattice-point sum error
    dm = em / qm       # CFE convergent error
    pqe.append( (em,pm,qm) )
    print "%.10f  %+.2e  %+.2e " % (xm,em,dm),pm,qm

    if abs(dm) < eps: break

  return xcfe,pqe


# evaluate and print results for the fit e^a 2^b ~= pi
def evalfit(a,b,x,y):
  e = a + b*x - y
  yn = exp(a+b*x)
  dn = yn - pi
  en = -int(floor(log10(abs(dn))))
  print "[%2d]  pi + %+.1e = e^%-16d 2^%-16d =" % (ceil(log10(abs(b+1))),dn,a,b),nstr(yn,en+5)
  return e


# given a fit e^a 2^b ~= pi with error d = a + b*x - y, find a better one if
# we can, using the CFE tables PQ; if so return the new fit (a,b), otherwise
# return None
def nextfit(a,b,d,pqe):
  n = 0
  while n < len(pqe) and abs(pqe[n][0]) > 2*abs(d): n += 1
  if n >= len(pqe): return None
  en,pn,qn = pqe[n]
  if en == 0: return None
  k = int(round(d/en))
  a -= k * pn
  b += k * qn
  return (a,b)


x = log(2)
y = log(pi)

print "ln 2 =", x
print "ln pi=", y
print

# epsilon bound "10**(-workdigits)" only good down to floating-point min; otherwise
# use, e.g., mpf(10)**(-workdigits)
xCFE,PQE = CFE(x,5*workdigits,10**(-workdigits))

print

ab = (0,0)
while ab:
  a,b = ab
  d = evalfit(a,b,x,y)
  ab = nextfit(a,b,d,PQE)

# print
# d = evalfit(191580860,-276392755,x,y)
# d = evalfit(-3521804314145,5080889619000,x,y)


Requires version 2.6+ for the standard fractions module; install the mpmath library to work to arbitrary precision.

[PM 2Ring]

Thanks for that Python code, and for letting us know about that mpmath library; it should come in handy. I normally use bc for arbitrary precision arithmetic, but it is a bit limited compared to Python.

For those without Python, here are some of the smaller results from eta oin shrdlu's program:

Code: Select all

pi                                   ~= 3.14159265358979323846

e^6                2^-7               = 3.151787
e^-55              2^81               = 3.14219508
e^1533             2^-2210            = 3.1415960361
e^-547416          2^789756           = 3.1415939552
e^-1932523         2^2788043          = 3.141592671657
e^47247985         2^-68164432        = 3.14159265416505
e^-7794116488      2^11244533207      = 3.141592653578974
e^40633345839      2^-58621526535     = 3.1415926535883532