numbers – MathematRec

Sum ideas (part 4)

22 June 201919 June 2019 by Rich Holmes, posted in Numbers

So how do you sum — or, if you prefer, associate a value with — $1+1+1+...$ ?

One way is zeta function regularization. For this we start with the sum

$\displaystyle S(s) = \sum_{k=1}^{\infty}k^{-s}$ .

For example, $S(2) = 1+1/4+1/9+1/16+...$ . This series converges to the limit $\pi^2/6$ . In fact $S(s)$ converges for any complex $s$ where the real part $\Re(s) > 1$ .

For $s=1$ , $S(1) = 1+1/2+1/3+1/4...$ and this diverges. If you approach $s=1$ along the real axis you find $S(s)$ increases without limit. Off the real axis, things are a little different. At $s=1+i$ , for example, the sum fails to converge, but as you approach t $s=1+i$ from the right, $S(s)$ approaches $0.58215 + 0.92684i$ . Similar behavior is found elsewhere on the $\Re(s) = 1$ line, other than $s=1$ .

That suggests there might be a way to construct a function that is equal to $S(s)$ for $\Re(s)>1$ but which has well defined values elsewhere, except $s=1$ . And indeed there is: analytic continuation.

Imagine I give you the following function: $f(x) = x$ for real $x \in [0,1]$ . Outside that interval $f(x)$ is undefined. But you obviously could define another function $g(x) = x$ which is defined on the whole real number line and has the property that $g(x) = f(x)$ in the range where $f(x)$ is defined. Obviously $g(x)$ is continuous, and is differentiable everywhere.

On the other hand, you could instead define $g(x)$ as being quadratics grafted onto the line from $(0,0)$ to $(1,1)$ :

$g(x) = x^2+x \quad x < 0$
$= x \quad 0 \le x \le 1$
$= x^2-x+1 \quad x > 1$

which has the same properties. Or you could use cubics, or quartics, or, well, anything provided it has the right value and derivative at $0$ and $1$ . There’s an infinite number of ways to continue $f(x)$ to the entire real line.

In the complex plane you can do something similar. I give you a function $f(z)$ defined for $z$ within some region of the complex plane. $f(z)$ is analytic, that is, it has a complex derivative everywhere it’s defined. Then you can give me an analytic function $g(z)$ defined everywhere in the complex plane and equal to $f(z)$ everywhere $f(z)$ is defined. (I’m being sloppy and informal here; there could be poles where neither function is defined, for example.)

Here’s the thing, though: Unlike $g(x)$ on the real line, $g(z)$ is unique. There is exactly one analytic function that continues my analytic function to the entire complex plane.

So, getting back to our sum (which is analytic), we can define an analytic function $\zeta(s) = S(s)$ for $\Re(s) > 1$ , whose behavior for $\Re(s) \le 1$ is given by analytic continuation. One can show

$\displaystyle \zeta(s) = \frac{1}{\Gamma(s)}\int_0^\infty \frac{x^{s-1}}{e^x-1} dx$

where $\Gamma(s) = \int_0^\infty x^{s-1}e^{-x} dx$ is the usual gamma function. $\zeta(s)$ has a pole at $s=1$ but is well defined everywhere else. $\zeta(s)$ is known as the Riemann zeta function.

Now, we know $\zeta(s)$ is the value of $\sum_{k=1}^{\infty}k^{-s}$ wherever that sum converges. Zeta regularization just assigns the value of $\zeta(s)$ to that sum where it does not converge as well. For instance, when $s=0$ , we have $1+1+1+1+... = \zeta(0)$ , and $\zeta(0) = -1/2$ .

The somewhat notorious sum of the positive integers, $1+2+3+4+...$ , is $S(-1)$ , to which is assigned the value $\zeta(-1) = -1/12$ . If you want to start an argument on the Internet, claiming that $1+2+3+4+... = -1/12$ is a good way to do it. Of course that claim glosses over a lot.

It turns out the negative even integers are (“trivial”) zeros of the zeta function, so $\sum_{k=1}^{\infty}k^{2n} = 0$ by this summation method. Generally, for integer exponents,

$\displaystyle \sum_{k=1}^{\infty}k^{n} = \zeta(-n) = (-1)^n \frac{B_{n+1}}{n+1}$ ,

where $B_n$ is the nth Bernoulli number,

$\displaystyle B_n = \sum_{k=0}^n\sum_{v=0}^k (-1)^v\binom{k}{v}\frac{v^m}{k+1}$ .

$\displaystyle \sum_{k=1}^{\infty}k^{1} = -\frac{1}{12}$
$\displaystyle \sum_{k=1}^{\infty}k^{3} = \frac{1}{120}$
$\displaystyle \sum_{k=1}^{\infty}k^{5} = -\frac{1}{252}$
$\displaystyle \sum_{k=1}^{\infty}k^{7} = \frac{1}{240}$
$\displaystyle \sum_{k=1}^{\infty}k^{9} = -\frac{1}{132}$
$\displaystyle \sum_{k=1}^{\infty}k^{11} = \frac{691}{32760}$

and on from there.

Sum ideas (part 3)

20 June 201919 June 2019 by Rich Holmes, posted in Numbers

Another summation method is Abel summation. The idea is, if we have

$\displaystyle S = \sum_{k=0}^{\infty} a_k$

then we can define

$\displaystyle f(r) = \sum_{k=0}^{\infty} a_kr^{k}$

for $r \in [0, 1)$ . Then if $\lim_{r\to 1^-} f(r)$ exists and is finite, that limit is the Abel sum of $S$ .

As a simple example, apply this to Grandi’s series, $1 - 1 + 1 - 1 ...$ . Here $f(r) = 1 - r + r^2 - r^3 ... = 1/(1+r)$ for $|r|<1$ . The limit as $r\to 1$ is $1/2$ , the same result as we obtained using Cesàro summation. In fact it can be shown that Abel summation is stronger than Cesàro summation, i.e., for series that can be Cesàro summed, Abel summation give the same result, but there are additional series which can be Abel summed but not Cesàro summed. Of course Cesàro summation is consistent with ordinary summation for convergent series, and therefore so is Abel summation: that is, Abel summation is regular.

Here’s another example. Consider

$\displaystyle 1-2+3-4+... = \sum_{k=0}^{\infty} (-1)^k(k+1)$ .

Not only does this series not converge, but the partial sum averages don’t converge either, so it is not Cesàro summable. But it is Abel summable. We make this sum into a function

$\displaystyle f(r) = \sum_{k=0}^{\infty} (-1)^k(k+1)r^k = r^0-2r^1+3r^2-4r^5...$

But now notice: $r^0 = -d(-r)^1/dr$ , $-2r^1 = -d(-r)^2/dr$ , $3r^2 = -d(-r)^3/dr$ , and so on:

$\displaystyle f(r) = -\frac{d}{dr}\sum_{k=0}^{\infty} (-r)^k$

and, again, for $|r|<1$ ,

$\displaystyle f(r) = -\frac{d}{dr}\frac{1}{1+r} = \frac{1}{(1+r)^2}.$

Now the Abel sum is $\lim_{r\to1^-} f(r) = 1/4$ .

A couple more properties (besides regularity) a summation method might have are linearity and stability. For the following let $\mathbf {A}(r)$ denote the result of applying summation method $\mathbf {A}$ to series $r$ . By linearity is meant: if $\mathbf {A}(\sum a_n) = s$ and $\mathbf {A}(\sum b_n) = t$ then $\mathbf {A}(\sum ka_n+b_n) = ks+t$ . By stability is meant: if $\mathbf {A}(a_0+a_1+a_2+...) = s$ then $\mathbf {A}(a_1+a_2+...) = s-a_0$ , and conversely. Cesàro summation and Abel summation both are linear and stable. So is classical summation, for that matter.

You can prove that for any linear and stable summation method $\mathbf{A}$ , the sum of the Grandi series $\mathbf{A}(g)$ is $1/2$ , if that sum exists:

$\mathbf{A}(g) = \mathbf{A}(1-1+1-1+1...) = 1 + \mathbf{A}(-1+1-1+1...)$ (by stability)
$= 1 - \mathbf{A}(1-1+1-1...)$ (by linearity)
$= 1 - \mathbf{A}(g)$ and so
$\mathbf{A}(g) = 1/2$ .

That “if that sum exists” provision is important. For instance, classical summation of the Grandi series is undefined, not $1/2$ , even though classical summation is linear and stable. You can come up with similar proofs about linear and stable sums of other series, that they must always have some particular value if they have a value at all. Showing that they do indeed have a value is another matter!

Conversely, you can prove some series do not have values for any summation method that is linear and/or stable. For example, suppose $\mathbf{A}$ is stable and $\mathbf{A}(\sum_{k=0}^\infty 1)$ has value $a$ . Then

$a = \mathbf{A}(1+1+1+1+1...) = 1 + \mathbf{A}(1+1+1+1...)$ (by stability)
$a = 1 + a$ ,

an impossibility. So $\sum_{k=0}^\infty 1$ cannot be summed by any stable summation method. There are unstable methods, however, that can sum that series.

Sum ideas (part 2)

19 June 201919 June 2019 by Rich Holmes, posted in Numbers

So, what about divergent series?

A divergent series has no limit, so we can’t assign that as a value. Conventionally we just say it has no value, its value is undefined. But in fact some divergent series can be associated with a definite quantity by means other than the limit of the sequence of partial sums. For some purposes, it can be useful to regard that quantity as the value, or a value, of the series.

There are lots of ways to associate a value with a divergent series; lots of summation methods, as they are called. It’s unfortunate terminology, in that it suggests they’re methods for finding the unfindable sum of the infinite number of numbers. But it’s the terminology we’re stuck with.

Summation methods are kind of like technical standards: the great thing about them is there’s so many to choose from. Generally a given summation method can be used with some series, but not with others. Some methods are stronger than others, in the sense that the one can be applied to any series the other can, with the same result, but it can also be applied to some series the other can’t handle.

Perhaps the simplest summation method applicable to a divergent series is Cesàro summation. In its simplest form, this is just finding the limit not of the partial sums of a series, but the average of the partial sums. For example, Grandi’s series is

$1 - 1 + 1 - 1 + 1 - 1 + ...$ .

The first partial sum is $1$ , the second is $1-1=0$ , the third is $1-1+1=1$ , the fourth is $1-1+1-1=0$ , and so on — they alternate between $1$ and $0$ . They don’t converge. But the average of the first one partial sum is $1$ , the average of the first two is $1/2$ , the average of the first three is $2/3$ , the average of the first four is $1/2$ , and so on, forming the sequence

$\displaystyle 1, \frac{1}{2}, \frac{2}{3}, \frac{1}{2}, \frac{3}{5}, \frac{1}{2}, \frac{4}{7}, \frac{1}{2}...$

and that sequence does converge, to $1/2$ . This value is the Cesàro summation of Grandi’s series.

Now, we know if we add together a finite number of integers, we get an integer, and it seems crazy to think you could sit down and add an infinite number of integers and get a fraction. Then again, it’s crazy to think you could sit down and add an infinite number of integers. And that’s not what we’re doing. But we know the partial sums alternate between $0$ and $1$ , so the value halfway between, $1/2$ , in some sense does characterize the behavior of the infinite series.

A reasonable question to ask is, what’s the Cesàro summation of a convergent series? It doesn’t take too much thinking to realize intuitively that if a series converges, then the average of the partial sums also should converge and to the same value. For instance, the partial sums of

$S = \displaystyle \sum_{k=0}^{\infty} \frac{1}{k!}$

converge to $e$ , and so do the averages of the partial sums. Granted, the partial sums converge much faster: after just 12 terms the partial sum is $1.718281828...$ while after 10000 terms the average of the partial sums is still $1.717281831...$ . But it’s getting there. A summation method that gives the conventional limit when applied to a convergent series is called regular. Cesàro summation is regular, and clearly that’s a nice attribute to have: it means Cesàro summation is consistent with ordinary summation, but is stronger in the sense that it also gives results for some series which have no classical value.

But does it make sense to say

$\displaystyle 1 - 1 + 1 - 1 + 1 - 1 + ... = \frac{1}{2}$ ?

It’s an unconventional and probably misleading use of the equal sign, but if it’s understood you’re talking about a value assigned using a summation method, specifically Cesàro summation, you maybe can get away with it. But you can also make the sense more explicit. Hardy again:

We shall make systematic use of the following notations. If we define the sum of $\Sigma a_n$ , in some new sense, say the ‘Pickwickian’ sense, as $s$ , we shall say that $\Sigma a_n$ is summable (P), call $s$ the P sum of $\Sigma a_n$ , and write

$\Sigma a_n = s$ (P).

We shall also say that $s$ is the P limit of the partial sum $s_n$ , and write

$s_n \to s$ (P).

Sum ideas (part 1)

19 June 201919 June 2019 by Rich Holmes, posted in Numbers

[I]t is broadly true to say that mathematicians before Cauchy asked not “How shall we define 1 – 1 + 1 – …?” but “What is 1 – 1 + 1 – …?”, and that this habit of mind led them into unnecessary perplexities and controversies which were often really verbal.
— G. H. Hardy, Divergent Series

What is the value of an infinite series?

I mean, what does “value” mean here?

With a finite series, you can (in principle) just add all the numbers together. You take the result and call that the value of the series. The value of $1+2+3+4+5$ is $15$ . No problem. But you can’t do that with an infinite series. You’d never complete the process — and so you can’t get its result.

You learn about infinite series in school, and what you learn is that some series converge to a limit. That is, if you have the infinite series

$S = \displaystyle \sum_{k=0}^{\infty} a_k$

it converges if, loosely speaking, the sequence of partial sums

$S_n = \displaystyle \sum_{k=0}^{n} a_k$

approaches some value $s$ arbitrarily closely as $n$ gets larger; that value is called the limit and we can write

$\displaystyle \lim_{n\to\infty} \sum_{k=0}^{n} a_k = s$ .

And then there’s a bit of a leap as we regard $s$ as not just the limit of the partial sums, but as the value of the infinite series:

$\displaystyle \sum_{k=0}^{\infty} a_k = s$

But not all series have limits, and if the limit doesn’t exist, then we regard the value of the infinite series as undefined.

That all can be learned in an intuitive way, though it can be made much more formal, and on the surface it makes sense. But there’s a sort of swindle going on here. You’re thinking of the “value” of the series as “what you would get if you added up all the infinite number of numbers”… but you can’t add them all up, so how can you assert what you would get if you did?

Here’s a demonstration of why that way of thinking about it is deceptive: the Riemann series theorem. Consider the series

$\displaystyle 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - ...$

You can show this converges to the limit $\ln 2$ . But you can take the same series and rearrange the terms like this:

$\displaystyle \left (1 - \frac{1}{2} - \frac{1}{4}\right ) + \left (\frac{1}{3} - \frac{1}{6} - \frac{1}{8}\right ) + \left (\frac{1}{5} - \frac{1}{10} - \frac{1}{12}\right )...$

and that converges to $\frac{1}{2}\ln 2$ . You’re adding up “the same” numbers in the second series as in the first, and addition is commutative, so you should get the same answer if you could add up all the numbers in the series (which you can’t)… but the limits are different! In fact, Riemann proved that any conditionally convergent series (one that has a limit, but the sum of the absolute values of the terms does not) can be rearranged to give you any limit, including $\infty$ or $-\infty$ , or no limit at all. It seems the “value” of a conditionally convergent series is a property not just of the numbers being summed, but the order they’re being summed in, and that’s not at all true of the value of a finite sum. Really the limit is a number that can be unambiguously associated with an infinite series, and we can define it as that series’s value, but “value” here means something different than in the case of a finite series where it’s just what you get if you add all the terms together. In fact, what the value means is just what it is: the limit of the sequence of the finite sums.

That being said, what about a divergent series?

Stay tuned.

Ramp primes

23 April 201923 April 2019 by Rich Holmes, posted in Numbers

I have no idea who’s gotten to this before me, nothing turns up in Google…

Define the zeroth ramp number R(0) to be 123456789. Then define the nth ramp number R(n) to be R(n-1) with a 1 prepended and a 9 appended: R(1) = 11234567899, R(2) = 1112345678999, and so on.

Likewise, the antiramp numbers R'(n) are R'(0) = 987654321, R'(1) = 99876543211, R'(2) = 9998765432111, and so on.

Then R(17), R(19), and R'(38) are (if the Python primefac library is to be believed) primes. And they are the only ramp/antiramp primes for a good long time. I checked up through R(1000) and R'(1000)… and just when it seemed there were no more, R'(926) turns out to be prime:

9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999876543211111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Thanoseses

19 April 201919 April 2019 by Rich Holmes, posted in Numbers

I saw this tweet:

and my first thought was, “Let’s see, so if each destroys half of all life…”

Or am I getting my pop culture mixed up? Well. Suppose we did have a line of, say, 63 Thanoses. Thani? Thanoxen? Something. One by one they snap their fingers and each time, half of all life is destroyed. You end up with $1/2^{63}$ of all life surviving. About 1.1E-19. Good luck surviving that.

But wait, that’s wrong. The first Thanos snaps and half of all life is destroyed… including half of all Thanoses. Of the 62 who haven’t snapped yet, now there are only 31 of them. After two snaps there are 15 who haven’t snapped. After three there are 7, after four there are 3, after five there is 1. That one snaps and we’re done. The surviving fraction is $1/2^{6} \approx 1.6\%$ . Your odds still aren’t good but they’re enormously better.

6 is $\log_2(63+1)$ ; the surviving fraction is $1/2^{\log_2(64)} = 1/64$ , or $1/2^{\log_2(n+1)} = 1/(n+1)$ for $n$ initial Thanoses.

Well, but not exactly. Presumably this is a random, probabilistic thing. On average half of all Thanoses die on each snap, but there’s some probability they all survive, and some probability they all die. If they all die on the first snap, $1/2$ of us survive; if they all survive every snap, $1/2^n$ of us die. The former is a lot more likely than the latter, though.

I wrote a little Python script and got this distribution of survival fractions with 64 initial Thanoses: [edited after bug fix]

Fraction	Number of times
1/4 or more	0
1/8	671
1/16	54,214
1/32	343,104
1/64	430,491
1/128	152,643
1/256	18,035
1/512	832
1/1024	10

So, good news, in the worst case there still are several million people alive. Just probably not you.

Limited persistence (part 3)

31 March 2019 by Rich Holmes, posted in Numbers

By the way:

I talked about how, instead of checking in base 10 every number up to, say, 10⁴⁰, you can check only numbers with no 0 or 1 digits, that do not have both a 5 and an even digit, with digits in increasing order, and that’s a vastly smaller number to check.

Similarly for other bases, but think about base 3. The only digits you have are 0, 1, and 2, so the only numbers that do not have 0 or 1 digits are all 2s: 2₃, 22₃, 222₃, 2222₃, …

There are 343,585,013,821,340,887,357,640,753,177,080,848,468,071,681,334 numbers that have 100 digits in base 3. Out of those only one needs to be checked (if you’ve already checked the 99 other numbers consisting of fewer 2s). Which is one heck of a speedup.

In base 4, any number with more than one digit equal to 2 has maximum persistence 2, so there are only two numbers per decade worth checking (23₄, 33₄, 233₄, 333₄, 2333₄, 3333₄, …)

So if we want to check numbers up to 100 digits, there are 100 base 3 numbers and 200 base 4 numbers. For base 5, there are 176,850 numbers. 181,900 in base 6, benefiting from the factors of 6, but 96,560,645 in base 7! Still a lot less than 7¹⁰⁰, but things are slowing down pretty hard.

Like this:

Like this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Like this: