Mathematics desk
< August 21	<< Jul \| August \| Sep >>	August 23 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 22

Kolmogorov Complexity

I am going through this assaignment: http://www.hutter1.net/ethz/assign1.pdf from this web site http://www.hutter1.net/ethz/uaiethz.htm - I am troubling by the questions involving inequalities of Kolmogorov complexities such as question KC-KC (ii) (iii) and (iv). The slides say the proof is similar to theorem 2.11 but I do not see the relation. Can you provide a help? — Preceding unsigned comment added by Bulkc (talk • contribs) 11:41, 22 August 2012 (UTC)[reply]

I think it's misleading to call the proofs similar. The only similarity is that you should build a Turing machine

T

showing that

K_{T}

is as you want, and then argue that this shows that

K

has the properties you want. For example, for (ii), make a machine that accepts extra information, but then ignores it and instead just simulates

U

.--121.73.35.181 (talk) 19:38, 22 August 2012 (UTC)[reply]

Riemann's integral from infinity to infinity

Quoting from Wikipedia's article on Bernhard Riemann's famous paper "On the Number of Primes Less Than a Given Magnitude":

The paper contains some peculiarities for modern readers, such as the use of Π(s − 1) instead of Γ(s), or writing tt instead of t². The style can also be surprising, such as writing an integral from ∞ to ∞.

What did Riemann mean when he wrote a definite integral from infinity to infinity? That interval seems nonsensical.

—SeekingAnswers (reply) 22:01, 22 August 2012 (UTC)[reply]

It's an improper integral, but it can often make perfect sense. It's very common in probability. For example, the integral of the normal density function from infinity to infinity is 1. --Tango (talk) 22:42, 22 August 2012 (UTC)[reply]

No, it isn't. The integral from negative infinity to positive infinity is 1; positive infinity to positive infinity doesn't make sense. —SeekingAnswers (reply) 22:55, 22 August 2012 (UTC)[reply]

Well, normally, though, you'd say it's the integral from minus infinity to infinity. I assume that was what Riemann meant, if indeed he did write it, just because I can't think of anything else he could mean, but it is indeed a strange way of putting it. --Trovatore (talk) 22:45, 22 August 2012 (UTC)[reply]

Wikipedia's article links to a translation, which definitely includes this. This seems to be used for a contour integral round something "passing through infinity" containing 0 and no other discontinuities - but contour integrals aren't usually written like that at all. Straightontillmorning (talk) 22:58, 22 August 2012 (UTC)[reply]

Riemann's original handwritten manuscript is here. I let you all be the judge of whether the claimed peculiarities are present in that manuscript. Hopefully you will all come to the same conclusion that I did, and therefore support my removal of the offending passage from the article. Sławomir Biały (talk) 01:32, 23 August 2012 (UTC)[reply]

Very well done Sławomir ! It seems from the manuscript as if Riemann wrote "von +∞ bis +∞" by mistake and then made the obvious correction by striking over the first "+" and writing a "−". So to me the meaning is clearly "von −∞ bis +∞", which makes sense. Bo Jacoby (talk) 07:01, 23 August 2012 (UTC).[reply]

You can add a point at infinity to the complex plane and then it is legitimate to call this an integral from infinity to infinity, as you have one unique point at infinity. The contour leaves out the singularities at 2 pi n i, but it includes 0. In modern notation we would write the integral as the limit of R to infinity of some contour that, say, starts -R and passses below the real axis to R and then returns to -R above the real axis. Count Iblis (talk) 01:39, 23 August 2012 (UTC)[reply]

See also here. If you think about it, writing t t is not that strange as the exponential notation is a shorthand for repeated multiplication, but writing t^2 for t t isn't much shorter. :) Count Iblis (talk) 01:56, 23 August 2012 (UTC)[reply]

That translation has an

\int _{\infty }^{\infty }

on page 2. However, Riemann's manuscript has something looking like

\int _{\cdot \infty }^{\infty }

there, which is clearly intended to mean

\int _{-\infty }^{\infty }

. Anyway, not worth writing about in the article. —Kusma (t·c) 07:23, 23 August 2012 (UTC)[reply]

So... what is the final verdict on what this integral is, since the answers above are conflicting? Is it a contour integral with non-modern notation as suggested by User:Straightontillmorning and User:Count Iblis? Or is it an improper integral with a typo in the lower bound as suggested by User:Sławomir Biały, User:Bo Jacoby, and User:Kusma? —SeekingAnswers (reply) 14:38, 23 August 2012 (UTC)[reply]

I'm sticking to my interpretation, because of the notations Riemann consistently uses. He never uses the modern notation for contour integrals and always formulates them as we would write an integral over an interval. In the end this is not wrong, it's just a matter of convention (our modern notation comes with some small print on how to interpret things too, without it it is just as ambiguous). He then writes that the integral is over a domain containing zero and but not the points 2 pi i n, and also how to interpret the multi-valued function. So it is clear that it is indeed a contour integral. Then if you think about how to write a contour integral using the notation for an ordinary integral over some interval, you see that you just need to specify one point that is on the contour.

It can't be an integral from minus to plus infinity because then what he wrote below it would not make any sense. There would then be no concept of "points in the interior of the integration domain". Had he wanted to write the integral entirely in terms of integrals over intervals (in our modern sense), then he would have needed to write it as the difference of two such integrals. Instead, what he does is that he explains that the integral reduces to that, but then one part from minus infinity to zero then cancels between the two integrals, while you're left with the difference between two integrals over zero to infinity, they don't cancel because each part now has a different phase factor due to the way the multi-valued function is defined. Count Iblis (talk) 16:12, 23 August 2012 (UTC)[reply]

B.t.w. Riemann cites Bo Jacobi in his paper! :) . Count Iblis (talk) 16:12, 23 August 2012 (UTC)[reply]

Carl Gustav Jacob Jacobi, actually, just so that no one coming by the Mathematical RefDesk unfamiliar with the surname gets confused. ;) —SeekingAnswers (reply) 22:49, 23 August 2012 (UTC)[reply]

LOL! Double sharp (talk) 12:57, 24 August 2012 (UTC)[reply]

Anyway, I would suggest everyone here to do the math that Riemann is doing in the paper using the standard notations instead, and see for him/herself what is going on (everything that is in the paper is accessible to second year math students). So, in the first part that we are talking about you want to derive the functional relation between Zeta(s) and Zeta(1-s) which then defines the analytic continuation of the zeta function to the entire complex plane.

Instead of looking at what Riemann with a microscope, just do the derivation yourself. E.g. you can consider the integral from infinity to zero just above the real axis, a small cricle around zero to just below the real axis and then back to infinity. Then if s is negative, you can close the contour by connecting the two ends at infinity to a big circle that then contains the poles at 2 pi i n, the integral is then given as the sum of the residues there which you can express in term of a zeta function.

This is essentailly the derivation Riemann does, his notations are just slightly different. E.g. most people today would decide to define (-x)^(s-1) by putting a branch cut along the positive real axis, while Riemann works with x^(s-1) as a multi-valued function. His contour is already closed from the start. But these are just minor issues, the math is essentailly the same. Count Iblis (talk) 16:24, 24 August 2012 (UTC)[reply]

I agree with Count Iblis that there is no misprint in that integral or in the text at that point. (I would note in passing that the integrals at the top of the page numbered "5" should be integrals with respect to dx, not ds, as you can verify by looking at the manuscript.) I don't agree that "everything that is in the paper is accessible to second year math students"! The paper is hard to understand. In this part, Riemann jumps from

$\Pi (s-1)\zeta (s)=\int \limits _{0}^{\infty }{\frac {x^{s-1}dx}{e^{x}-1}}$

to

$2\sin(\pi s)\Pi (s-1)\zeta (s)=i\int \limits _{\infty }^{\infty }{\frac {(-x)^{s-1}dx}{e^{x}-1}}$

with hardly any explanation. Basically, you need to multiply the left side of the first equation by $2\sin(\pi s)$ and the right side by the equivalent $i(e^{-\pi si}-e^{\pi si})$ , giving

$2\sin(\pi s)\Pi (s-1)\zeta (s)=i(e^{-\pi si}-e^{\pi si})\int \limits _{0}^{\infty }{\frac {x^{s-1}dx}{e^{x}-1}}$

(Note that this formula for ζ(s) will be useless for positive integer values of s because it will say that 0ζ(s)=0.) Now, we consider the function $(-x)^{s-1}$ defined for the complex plane without the non-negative reals as $e^{(s-1)\ln(-x)}$ where the logarithm is real for negative x and is analytically extended to the complex numbers. Just above the positive real line this equals $e^{(s-1)(\ln(x)-\pi i)}$ , or $-e^{-\pi si}x^{s-1}$ , and just below the positive real line it equals $-e^{\pi si}x^{s-1}$ . So we can rewrite the right-hand side of the above equation as two integrals:

$2\sin(\pi s)\Pi (s-1)\zeta (s)=i\left(\int \limits _{\infty }^{0}{\frac {(-x)^{s-1}dx}{e^{x}-1}}+\int \limits _{0}^{\infty }{\frac {(-x)^{s-1}dx}{e^{x}-1}}\right)$

where the first integral is just above the real line and the second just below. He writes this sum of two integrals as a contour integral going from +∞ to +∞ and swinging around 0, although I confess I don't understand how he can ignore the part right around zero, when the real part of s is less than 1. He goes on to say that this defines ζ(s) for all complex s (although as I said, it doesn't for positive integers), and that it shows that ζ(s) is zero for negative even integers (which I don't see -- the integral would be zero for all integers other than 1).

Another part I haven't succeeded in following is the page numbered "7" and the top of "8".

I am going to put back the sentence about the "peculiarities for modern readers" (which I put there five years ago) because I still think it's true, and helpful. For instance, it wasn't obvious to me at first that tt meant t squared!

Eric Kvaalen (talk) 13:00, 25 August 2012 (UTC)[reply]

Regardless of whether it's true, I think an observation like this needs a source if it's going to be included in the article. It's not really a big deal though. Sławomir Biały (talk) 13:12, 25 August 2012 (UTC)[reply]

I agree with User:Eric Kvaalen that the observation belongs to and is helpful in the article, but I've modified the wording of the text slightly to be clearer as to what the bounds mean. —Lowellian (reply) 17:36, 25 August 2012 (UTC)[reply]