Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

June 10

Functional powers

Beginning with the usual definition of f⁻¹ for a function f and

$f^{n}:=\underbrace {f\circ f\circ \dots \circ f} _{n}$

led me to the idea of functional roots (i.e. if g² = f, then g = f^1/2) and then to rational powers of functions (i.e. f^a/b = (f^1/b)^a). From here, I had several questions:

1. How could you extend the definition to real or complex powers of functions? Is it even possible, given the duplicity of things like f^1/2 (i.e. if f(x) = g(x) = x and h(x) = 1/x, then g(g(x)) = h(h(x)) = f(x), so g and h are both "f^1/2" for the right domain)? If it is possible, you could consider taking functions to the power of other functions, which is an interesting concept (to me, anyway).
2. How do you go about graphing or finding formulaic approximations for functions like rin = sin^1/2 (see here)? How was it determined that as n goes to infinity, sin^1/n goes to the sawtooth function?
3. Do these notions have any particular application?

Thanks in advance for taking the time with these loaded and naïve questions. —Anonymous Dissident^Talk 12:44, 10 June 2011 (UTC)

Your questions will take you into the area of functional equations. One complication you will encounter is that the functional square root of a function is usually far from unique - for example, the function

$y(x)=x$

has functional square roots

$y_{(1/2)}={\frac {x+a}{ax-1}}$

for any real (or complex) number a. Gandalf61 (talk) 14:13, 10 June 2011 (UTC)

The set of all "square roots" of the identity function on an arbitrary set $X$ is in natural one-to-one correspondence with the set of all partitions of $X$ into sets of size 1 or 2. --COVIZAPIBETEFOKY (talk) 15:00, 10 June 2011 (UTC)

You can define a generator of a function as follows. If:

$f(x)=\lim _{n\to \infty }\left[x+{\frac {g(x)}{n}}\right]^{\circ n}$

then we can consider g(x) to be a generator of f(x). Count Iblis (talk) 15:44, 10 June 2011 (UTC)

I get a one-to-one correspondence between the complement of a projective algebraic variety in the complex projective plane and the Möbius transformations that are functional square roots of g(z) = z. Let [a : b : c] be in CP², with a² − bc ≠ 0, and define

$f(z):={\frac {az+b}{cz-a}}\,.$

we see that ƒ has the property that (ƒ ∘ ƒ)(z) = z. — Fly by Night (talk) 11:32, 11 June 2011 (UTC)

If you're just interested in constructing the functional square root, then the method of Kneser (referenced in our article) seems to be worth studying. This paper constructs a functional square root of the exponential function, and the method seems like one could work it out without a great deal of specialized knowledge. If you're interested in looking at the whole semigroup (if there is one—which seems to me a little unlikely) of functional roots $\sin ^{\alpha }$, then some basic papers on this subject appear to be Erdos and Jabotinsky (1960) [1] and Szekeres (1958) "Regular iteration of real and complex functions", Volume 100, Numbers 3-4, 203-258, DOI: 10.1007/BF02559539. It seems to be a theorem that there is no way to define non-integer iterates of the exponential function so that the semigroup property holds (maybe along with analyticity in the iteration parameter, it's not clear to me what the rules are). The following paper also seems to be worth looking at: Levy, (1928) "Fonctions à croissance régulière et itération d'ordre fractionnaire", Annali di Matematica Pura ed Applicata Volume 5, Number 1, 269-298, DOI: 10.1007/BF02415428. I haven't found any (reliable) papers that specifically address the sine function. There's this, which I find a little dubious. Sławomir Biały (talk) 13:55, 12 June 2011 (UTC)

June 11

Proof of Inequality

How to prove the following inequality?

If $p>0$ is a real number, then there exists a constant $C_{p}$ dependent only on $p$ such that for all real numbers $x,y\geq 0$, we have the inequality:

$x^{p}+y^{p}\leq C_{p}(x+y)^{p}$

This isn't homework. I was reading a proof in a paper and I think this inequality is used and I'm wondering how to prove it. Can anyone enlighten me? — Preceding unsigned comment added by 49.2.4.186 (talk) 08:47, 11 June 2011 (UTC)

As stated, it isn't true. For $p=1/2$, $y=1$, there's no $C_{p}$ that works for all $x$.--203.97.79.114 (talk) 12:32, 11 June 2011 (UTC)

Sorry, ignore that. I just had a really dumb moment.--203.97.79.114 (talk) 12:43, 11 June 2011 (UTC)

Okay, trying again. First, if $p\geq 1$, then $C_{p}=1$ will suffice: the inequality clearly holds for $x=0$, and the derivative of the right (with respect to $x$) is always at least as much as the derivative of the left.

If $p<1$, then $C_{p}=2$ will suffice. Let's assume by symmetry that $x\geq y$. If $x=y$, then the inequality becomes $2x^{p}\leq 2\cdot 2^{p}x^{p}$, and since $p>0$, this holds. Now we again take the derivatives with respect to $x$. The left gets us $px^{p-1}$, while the right gives $2p(x+y)^{p-1}\geq 2p(2x)^{p-1}>px^{p-1}$.--203.97.79.114 (talk) 12:55, 11 June 2011 (UTC)

Excellent. Thanks! It didn't occur to me to differentiate. But do you think that this can be proven without differentiation. This is just out of curiosity since I understand your proof and am content with it but would like to know whether there is a nice trick that solves it. — Preceding unsigned comment added by 49.2.4.186 (talk) 02:04, 12 June 2011 (UTC)

I think perhaps an easier approach is to divide both sides by $y^{p}$, which converts the expressions to functions of a single variable equal to $x/y$. Looie496 (talk) 16:44, 11 June 2011 (UTC)

Alternative Proof

Does anyone know of a way to evaluate the following:

$\lim _{n\to \infty }\left(\sum _{k=1}^{n}{\frac {1}{k^{2}}}\right)$

that does not involve Fourier series? — Fly by Night (talk) 21:48, 11 June 2011 (UTC)

By evaluating the double integral $\int _{0}^{1}\int _{0}^{1}{\frac {dx\,dy}{1-xy}}$. Sławomir Biały (talk) 22:33, 11 June 2011 (UTC)

Sławomir, how does that double integral relate to the sum? I don't see how the dilog function relates to the sum in question in a simple, non-convoluted way. Could you show the steps for getting from the sum I gave to that double integral please? — Fly by Night (talk) 00:56, 12 June 2011 (UTC)

Expand the integrand as a geometric series and integrate it term-by-term. That gives your series. The integral itself can be evaluated by rotating the coordinate system through an angle of $\pi /4$, which transforms the integrand into something of the form $(1-x^{2}/2+y^{2}/2)^{-1}$. The resulting integral can be dealt with by elementary means. Sławomir Biały (talk) 02:00, 12 June 2011 (UTC)

Here is a link. Sławomir Biały (talk) 02:28, 12 June 2011 (UTC)

There is another elementary proof at our article Basel problem (along with Euler's proof, mentioned below, and a proof using Fourier series). Sławomir Biały (talk) 02:47, 12 June 2011 (UTC)

Excellent. How very cunning. Thanks for that. — Fly by Night (talk) 14:27, 12 June 2011 (UTC)

There's a description of Euler's proof here. AndrewWTaylor (talk) 23:25, 11 June 2011 (UTC)

Thanks. I'll take a look in the morning. The non-LaTeX font makes it hard to read at this time of night. — Fly by Night (talk) 00:56, 12 June 2011 (UTC)

See question 8 here: http://www.boardofstudies.nsw.edu.au/hsc_exams/hsc2010exams/pdf_doc/2010-hsc-exam-mathematics-extension-2.pdf . (I don't really know anything about Fourier series, but the proof which the student is led through doesn't explicitly mention them; judge for yourself whether they are "involved" implicitly.) —Anonymous Dissident^Talk 23:27, 11 June 2011 (UTC)

Thanks a lot for taking the time to find that link. It looks to me that Question 8 is basically asking people to compute the integrals involved in calculating the Fourier series. — Fly by Night (talk) 00:56, 12 June 2011 (UTC)

What the hell? Have you heard of Parseval's identity you guys? — Preceding unsigned comment added by 49.2.4.186 (talk) 02:08, 12 June 2011 (UTC)

The OP wants a proof that does not involve Fourier series. Sławomir Biały (talk) 02:23, 12 June 2011 (UTC)

Quite! — Fly by Night (talk) 14:27, 12 June 2011 (UTC)

Sure but I'm just wondering whether FBN (= "Fly by Night" are you an owl?) here knows Parseval's identity. Because he "claims" the integrals being computed in Question 8 are "basically those involved in calculating the Fourier series". I looked at that and it sure as hell doesn't look like that to me dudes. Maybe FBN needs to brush up on his theory of integration. BTW, see my PDF http://empslocal.ex.ac.uk/people/staff/rjchapma/etc/zeta2.pdf for some cool methods on how to sum this series. — Preceding unsigned comment added by 49.2.4.186 (talk) 00:58, 13 June 2011 (UTC)

Ask yourself this: If I didn't know that Fourier series could be used to evaluate the sum, and ergo know of Parseval's identity, then why would I ask for a proof that doesn't involve Fourier series? As for Question 8, I looked at that at 3 o'clock in the morning. The question involves terms of the form A_n and B_n, while integrating x² multiplied by a trigonometric terms. Sound familiar? Thanks for the offer, but you can keep your "cool methods". According to the Exeter website, Robin Chapman lives and works in Exeter, but your IP is from Sydney, Australia^[2]. Are you sure it's your PDF? — Fly by Night (talk) 14:34, 13 June 2011 (UTC)

I think it's a valid point that the Question 8 argument is elementary in a way that an argument using properties of Fourier series is not. I'm not sure how one motivates this approach, though. Sławomir Biały (talk) 14:45, 13 June 2011 (UTC)

I agree. I just didn't read it properly, saw all the A_n's, B_n's, and trigonometric and thought it was Fourier series. — Fly by Night (talk) 17:00, 13 June 2011 (UTC)

I'll tell you Parseval's identity. It's more conceptual to think of L^2 the space of measurable square-integrable functions on [-pi,pi] as a complex inner product space (Hilbert space). The idea is that the space has an orthonormal basis (general orthornormal basis can be found by wavelets) such as {e^{-in}} for n an integer. And if f is a function in L^2 you can take its inner product against each of these functions and get "components" of f. The point is, as you'd expect in any Hilbert space, the components are the only relevant data when it comes to taking inner products. So you can find the inner product (an integral) of two functions just by knowing their Fourier coefficients. Pretty cool math dude? So basically I advise you to find the Fourier coefficients of the function "x" on [-pi,pi] and take the inner product of this function with itself and apply Parseval. The PROOF of Parseval is probably well beyond the scope of your education; you'll see it when you get to university. It involves proving the completeness of the trigonometric system (in the L^2 case) which can be done nicely with convolution but I'll save the details to your lecturers at first year undergrad. uni. — Preceding unsigned comment added by 49.2.4.186 (talk) 09:31, 14 June 2011 (UTC)

Thanks, but you seem to miss the point of my question. I was interested in alternative proofs that did not involve Fourier series and, therefore, did not involve Parseval's identity. I'm fully aware of Parseval's identity; I first learnt it as a second year undergraduate in 2002. It's the only way I know of summing the sum I gave; that's why I titled the section Alternative Proof and went on to ask for a proof without Fourier series. I know you're new around here, so I recommend that you read WP:CIVIL before you make any more posts. Thanks for taking the time, but there's really no need to write lengthy posts about topics the OP has explicitly said they are not interested in. Thanks again. — Fly by Night (talk) 12:17, 14 June 2011 (UTC)

P.S. Don't forget to sign your posts with four tildes, like this: ~~~~. — Fly by Night (talk) 12:18, 14 June 2011 (UTC)

Your civility is unwarranted, Fly by Night. --72.179.51.84 (talk) 15:31, 14 June 2011 (UTC)

Here's a nice computation (sketch). Recall that $(1+z/n)^{n}\to e^{z}$ for complex $z$. Define polynomials $p_{n}(x):={\frac {1}{2i}}{\Big (}(1+ix/n)^{n}-(1-ix/n)^{n}{\Big )},$ and note that $p_{n}(x)\to \sin x.$ Factorize $p_{n}(x)$ in linear factors. Keep track of the first coefficients of $p_{n}$ in terms of their roots, and equate the limits (this way you can also compute in elementary way $\zeta (4),$ $\zeta (6)$ etc.) Also, by the theorem of dominated convergence for products, the factorizations converge to an infinite product, so you also find the Euler product for $\sin x$. --pma 19:27, 13 June 2011 (UTC)

Nice, thanks pma. — Fly by Night (talk) 12:24, 14 June 2011 (UTC)

June 12

Normal Deviation

The Menstrul Cycle of female is on an average, of 28 days and has standard deviation of 2 days A)in what % of women will the cycle differ by more than 3 days from mean ? B)mark out symmetrically around the mean the range in which 80% women will lie — Preceding unsigned comment added by 49.200.54.220 (talk) 16:40, 12 June 2011 (UTC)

This is obviously a homework question. We don't do people's homework for them here. Could you show us what you have done so far and then we will help you to understand what you need to do next. As it says at the beginning of this page: "If your question is homework, show that you have attempted an answer first, and we will try to help you past the stuck point. If you don't show an effort, you probably won't get help. The reference desk will not do your homework for you. — Fly by Night (talk) 17:49, 12 June 2011 (UTC)

I'll just point out that from a fully technical position, the question is underspecified. The answer depends *highly* on which probability distribution you use. Average and standard deviation are really only enough to fully specify a distribution if you're assuming a normal distribution (and some other, simple distributions). While it's possible that the length of the menstrual cycle is normally distributed (Central Limit Theorem and all that), as the problem is stated we can't be sure if the assumption is completely valid. -- 174.31.219.218 (talk) 19:14, 12 June 2011 (UTC)

Well, the fact that the OP entitled this section Normal Deviation is a bit of a clue, perhaps. Looie496 (talk) 23:18, 12 June 2011 (UTC)

The distribution can't be normal because that would imply the possibility of a negative time. The question also seems to assume (wrongly, as far as I know) that the cycle time is constant for any particular woman. AndrewWTaylor (talk) 19:36, 13 June 2011 (UTC)

A negative value would be 14 standard deviations away from the mean. I think we can safely ignore that problem. Few things are actually normally distributed, but a great many things are well approximately by the normal distribution within about 3 sd of the mean, which is what makes it such a useful distribution. --Tango (talk) 23:23, 13 June 2011 (UTC)

Newton's Second Law

"The second law states that the net force on a particle is equal to the time rate of change of its linear momentum p in an inertial reference frame:

$\mathbf {F} ={\frac {\mathrm {d} \mathbf {p} }{\mathrm {d} t}}={\frac {\mathrm {d} (m\mathbf {v} )}{\mathrm {d} t}},$

where, since the law is valid only for constant-mass systems the mass can be taken outside the differentiation operator by the constant factor rule in differentiation. Thus,

$\mathbf {F} =m\,{\frac {\mathrm {d} \mathbf {v} }{\mathrm {d} t}}=m\mathbf {a}$"

This is an extra from your article on Newton's laws of motion, specifically the section on the second law. I don't understand why it says that the law is valid only for constant mass systems, not least of all because on Isaac Newton, in the section entitled 'Laws of Motion', the second law is written as ${\vec {F}}={\frac {\mathrm {d} {\vec {p}}}{\mathrm {\mathrm {d} } t}}\,=\,{\frac {\mathrm {d} }{\mathrm {d} t}}(m{\vec {v}})\,=\,{\vec {v}}\,{\frac {\mathrm {d} m}{\mathrm {d} t}}+m\,{\frac {\mathrm {d} {\vec {v}}}{\mathrm {d} t}}\,.$, the form that I am familiar with.

I'm partly asking what the subtlety is that demands we treat the mass as constant in the first case, assuming it's not a mistake, and partly suggesting that someone who knows what they're doing clarifies the issue. I have studied mathematics and physics at university and if I am left confused by this then the layman will have no idea what's going on. Thanks. meromorphic [talk to me] 16:44, 12 June 2011 (UTC)

Can I just say, as a the layman of your words, I can follow the first version with mass constant, but would have more trouble with the rule if the rule is equally true in changing-mass systems. (I do understand the product rule, but still.) I couldn't say which is more familiar to people with physics or mathematics degrees, but I'm certainly more aware of f=ma than one adapted for use on changing-mass systems. I don't know which Newton used, but if the second is more "true", then it may still be preferable to keep the first and say "if mass is constant" rather than "since mass has to be constant", at least introductory-wise. Grandiose (me, talk, contribs) 16:52, 12 June 2011 (UTC)

The problem with ${\vec {F}}=\,{\vec {v}}\,{\frac {\mathrm {d} m}{\mathrm {d} t}}+m\,{\frac {\mathrm {d} {\vec {v}}}{\mathrm {d} t}}$ is that if the mass of an object is changing it must be picking up or expelling mass (or energy) from outside. The mass that's entering or leaving has momentum of its own, and the formula doesn't tell us how to accurately deal with that. For example if I have a moving object and a piece breaks off, but the original object and the piece both keep moving off at the same velocity, then I end up with a non-zero ${\vec {v}}\,{\frac {\mathrm {d} m}{\mathrm {d} t}}$, but can we really say there's a force acting on the object? Rckrone (talk) 18:24, 12 June 2011 (UTC)

I think the term for non-constant mass comes in when you take relativity into account. You can apply all the force you want but the velocity will always be less than c. So when you get close to c what the force does mostly is increase mass, which is where the dm/dt comes in. But this is the math helpdesk, we don't normally deal with soft science like physics.--RDBury (talk) 22:53, 12 June 2011 (UTC)

No response yet from physicists who might object to calling their science "soft"? Dbfirs 07:51, 17 June 2011 (UTC)

See here:

Hilbert said "Physics is too hard for physicists", implying that the necessary mathematics was generally beyond them; the Courant-Hilbert book made it easier for them.

Count Iblis (talk) 02:10, 18 June 2011 (UTC)

While you can do relativity using relativistic mass (and I often do when trying to give people an intuitive feels for how it works), it isn't the normal way of formulating it mathematically. You can see a derivation of the more common relativistic equivalent of F=ma here: Special_relativity#Force. --Tango (talk) 23:30, 13 June 2011 (UTC)

June 13

Ogden's lemma examples

Our article on Ogden's lemma (and many other pages I've found on the web) use the example {aⁱb^jc^kd^l : i = 0 or j = k = l} but this language can be proven non-context-free using the pumping lemma and closure of CFLs under intersection by regular languages (take ab^*c^*d^*). Are there examples of languages which can be proven to be non-CFLs with Ogden's lemma, but not with the pumping lemma and closure of CFLs under regular intersection and gsm mappings? --146.141.1.96 (talk) 10:51, 13 June 2011 (UTC)

nilpotent cone of a Lie algebra

The article nilpotent cone claims that "The nilpotent cone...is invariant under the adjoint action of ${\mathfrak {g}}$ on itself." Take the example of ${\mathfrak {g}}={\mathfrak {sl}}_{2}=\langle E,F,H\rangle$ as in the article, so the nilcone N is spanned by E and F. Then $\operatorname {ad} (E)(F)=H$ which is not in the nilcone, so N is not ad-invariant. Have I misunderstood something, or is the article wrong? Tinfoilcat (talk) 11:15, 13 June 2011 (UTC)

If g is a Lie algebra and x is an element of g, then the adjoint action ad_x : g → g is defined by ad_x(y) = [x,y] for all y in g. To prove that the nilpotent cone, say N, is invariant under the adjoint action you just need to show that for all x and y in N, the Lie bracket [x,y] is again in N. — Fly by Night (talk) 14:47, 13 June 2011 (UTC)

FbN, I know what the adjoint map is and what it means to be ad-invariant (it's not quite what you say - ad-invariant means a Lie ideal, not a Lie subalgebra). The example I gave in my post seems to show that the nilcone is not ad-invariant since $[E,F]=H$ which is not in the nilcone, whereas E and F are. Tinfoilcat (talk) 14:54, 13 June 2011 (UTC)

I don't recall mentioning subalgebras or ideas. I'm sorry I wasn't able to help. — Fly by Night (talk) 15:50, 13 June 2011 (UTC)

FbN, I was very bitey above. Sorry. When you say "for all x and y in N, the Lie bracket [x,y] is again in N " that's equivalent to it being a subalgebra. Being an ideal (= being ad-invariant) is that for n in N, x in the Lie algebra, $[x,n]\in N$ - a little stronger. Tinfoilcat (talk) 15:59, 13 June 2011 (UTC)

No problem. Proving it's a subalgebra means that it's automatically an ideal too, by definition (because of the way the nilpotent cone is defined in the first place). Or at least I think so… — Fly by Night (talk) 16:06, 13 June 2011 (UTC)

The statement is wrong. The nilpotent cone is invariant under the action on Int(g) on g (interior auromorphisms). Sławomir Biały (talk) 15:53, 13 June 2011 (UTC)

Thanks. I'll fix the page (if you haven't got there first). Tinfoilcat (talk) 15:59, 13 June 2011 (UTC)

Normalizing Associated Legendre Polynomials to get Spherical Harmonics

Hi all. I've been working on this problem for like weeks, and I can't seem to figure it out. I'm trying to normalize Associated Legendre polynomials to turn them into Spherical harmonics. The integral comes out to:

$\int _{-1}^{1}P_{\ell _{1}}^{m}(x)P_{\ell _{2}}^{m}(x)dx={\frac {1}{A^{2}}}$

where $A$ is the normalization constant. $A$ can be found in Spherical harmonics#Orthogonality and normalization. I know that it involves integrating by parts $\ell +m$ times, and that the boundary terms vanish in each case, but I'm not sure why they vanish. Can anyone point me to a (very detailed) discussion of how to actually do the integral, or maybe a better way than by parts? Thanks!--Dudemanfellabra (talk) 23:32, 13 June 2011 (UTC)

Hi, I had a quick look in Boas - 'Mathematical Methods in the Physical Sciences'. She has a problem (prob 10.10 in second edition) about the normalisation, first some results:

a) $P_{l}^{m}(x)={\frac {1}{2^{l}l!}}(1-x^{2})^{m/2}{\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}$

This comes from substituting in Rodriques' formula (see Legendre_polynomials) for the Legendre polynomials. Next Boas says derive

b) $P_{l}^{m}(x)=(-1)^{m}{\frac {(l+m)!}{(l-m)!}}{\frac {(1-x^{2})^{-m/2}}{2^{l}l!}}{\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}$

Multiply these two results together (this forms your normalisation integrand) then integrate by parts repeatedly until both l+m and l-m derivatives are just l derivatives. Then use

$\int _{-1}^{1}[P_{l}(x)]^{2}dx={\frac {2}{2l+1}}$ - I assume because you end up having an integrand that looks like two Legendre polynomials multiplied together.

Now, the derivation of result (b) is a task in itself. Apparently one can show that

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}={\frac {(l-m)!}{(l+m)!}}(x^{2}-1)^{m}{\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}$

by starting with $(x^{2}-1)^{l}=(x-1)^{l}(x+1)^{l}$ and finding derivatives using Leibniz' rule. Good luck, I'd find a copy of Boas and work from that if I was you. Christopherlumb (talk) 19:55, 14 June 2011 (UTC)

I found a copy of Boas, but unfortunately the method for part b) is not given. After applying Leibniz' rule, I get

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}=\sum _{i=0}^{l-m}{\binom {l-m}{i}}{\frac {d^{l-m-i}}{dx^{l-m-i}}}(x+1)^{l}{\frac {d^{i}}{dx^{i}}}(x-1)^{l}$

I have no idea where to go from here...--Dudemanfellabra (talk) 23:13, 14 June 2011 (UTC)

I'm really struggling myself, I think you have to get expressions for the $l+m$th and $l-m$th derivatives and compare them term-by-term, so

${\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}=\sum _{i=0}^{l+m}{\binom {l+m}{i}}{\frac {d^{l+m-i}}{dx^{l+m-i}}}(x+1)^{l}{\frac {d^{i}}{dx^{i}}}(x-1)^{l}$

we note that the derivatives on the right-hand side are just acting on $(x\pm 1)^{l}$ so that any derivative higher than $l$ differentiates to zero. This means the sum gets truncated: we must have $i\leq l$ (else the d/dx^i goes to zero) and $i\geq m$ (else the d/dx^(l+m-i) will go to zero). So:

${\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}=\sum _{i=m}^{l}{\binom {l+m}{i}}{\frac {d^{l+m-i}}{dx^{l+m-i}}}(x+1)^{l}{\frac {d^{i}}{dx^{i}}}(x-1)^{l}$

now we have no-more terms in this sum than for the $l-m$ sum, next evaluate the derivatives:

${\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}=\sum _{i=m}^{l}{\binom {l+m}{i}}l(l-1)\ldots (1-l-m+i){\frac {(x+1)^{l}}{(x+1)^{l+m-i}}}$

$\times l(l-1)\ldots (1-i){\frac {(x-1)^{l}}{(x-1)^{i}}}$

I've written the derivatives as fractions where you'd normally just write $(x^{2}-1)^{l-i}$. Next job is to make this look like the l-m derivative:

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}=\sum _{j=0}^{l-m}{\binom {l-m}{j}}{\frac {d^{l-m-j}}{dx^{l-m-j}}}(x+1)^{l}{\frac {d^{j}}{dx^{j}}}(x-1)^{l}$

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}=\sum _{j=0}^{l-m}{\binom {l-m}{j}}l(l-1)\ldots (1-l+m+j){\frac {(x+1)^{l}}{(x+1)^{l-m-j}}}$

$\times l(l-1)\ldots (1-j){\frac {(x-1)^{l}}{(x-1)^{j}}}$

Let $j=k-m$ then our sum runs from $k=m$ to $k=l$:

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}=\sum _{k=m}^{l}{\binom {l-m}{k-m}}l(l-1)\ldots (1-l+k){\frac {(x+1)^{l}}{(x+1)^{l-k}}}$

$\times l(l-1)\ldots (1-k+m){\frac {(x-1)^{l}}{(x-1)^{k-m}}}$

Pull a factor of (x^2-1)^m out the front:

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}=(x^{2}-1)^{m}\sum _{k=m}^{l}{\binom {l-m}{k-m}}l(l-1)\ldots (1-l+k){\frac {(x+1)^{l}}{(x+1)^{l+m-k}}}$

$\times l(l-1)\ldots (1-k+m){\frac {(x-1)^{l}}{(x-1)^{k}}}$

It's looking very similar to the l+m version above, I haven't the energy to go through to check the factorials all work out but I think this is on the right track 213.249.173.33 (talk) 21:09, 15 June 2011 (UTC)

AH! THANK YOU THANK YOU THANK YOU THANK YOU! Haha I had figured out what the (l+m-i)th and (l-m-i)th derivatives were (btw, the factorials in your above derivation are a little off. I'll show the correct one below.), but I didn't think about shifting the index of one of the sums so that they can be compared properly. By shifting that index and using falling factorials for the derivatives, I was able to show the correct relationship. I'll show it below and continue to work on the rest of the problem. Thanks for all your help!

Derivation showing alternative way to write Plm(x)

${\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}=\sum _{i=0}^{l+m}{\binom {l+m}{i}}{\frac {d^{l+m-i}}{dx^{l+m-i}}}(x+1)^{l}{\frac {d^{i}}{dx^{i}}}(x-1)^{l}$

$(x\pm 1)^{l}$ has only l non-vanishing derivatives, so $i\geq m,i\leq l$. Therefore, the sum can be written from i=m to l. Using falling factorial notation for the derivatives and expanding the binomial coefficients in factorial form yields

${\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}=\sum _{i=m}^{l}{\frac {(l+m)!}{i!(l+m-i)!}}{\frac {l!}{(i-m)!}}(x+1)^{i-m}{\frac {l!}{(l-i)!}}(x-1)^{l-i}$

Doing the Leibniz formula for the l-m derivative yields

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}=\sum _{j=0}^{l-m}{\binom {l-m}{j}}{\frac {d^{l-m-j}}{dx^{l-m-j}}}(x+1)^{l}{\frac {d^{j}}{dx^{j}}}(x-1)^{l}$

Again, expanding the coefficients and using falling factorials,

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}=\sum _{j=0}^{l-m}{\frac {(l-m)!}{j!(l-m-j)!}}{\frac {l!}{(m+j)!}}(x+1)^{m+j}{\frac {l!}{(l-j)!}}(x-1)^{l-j}$

Let $k=m+j\Rightarrow k\in [m,l]$ Plugging in:

${\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}=\sum _{k=m}^{l}{\frac {(l-m)!}{(k-m)!(l-k)!}}{\frac {l!}{k!}}(x+1)^{k}{\frac {l!}{(l-k+m)!}}(x-1)^{l-k+m}$

Now that the two sums have the same indices (i and k are just dummy variables, so we may as well say they're the same thing; let's choose i), we can divide the two sums to find the ratio of the l+m and l-m derivatives. That is,

${\frac {{\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}}{{\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}}}=\sum _{i=m}^{l}{\frac {(l+m)!}{i!(l+m-i)!}}{\frac {l!}{(i-m)!}}{\frac {l!}{(l-i)!}}{\frac {(i-m)!(l-i)!}{(l-m)!}}{\frac {i!}{l!}}{\frac {(l-i+m)!}{l!}}(x+1)^{-m}(x-1)^{-m}$

which, after cancelling and observing that all i's disappear so the sum can be dropped, yields:

${\frac {{\frac {d^{l+m}}{dx^{l+m}}}(x^{2}-1)^{l}}{{\frac {d^{l-m}}{dx^{l-m}}}(x^{2}-1)^{l}}}={\frac {(l+m)!}{(l-m)!}}(x^{2}-1)^{-m}$

This gives the relationship desired in part b) of Christopherlumb's comment above (with the exception of the $(-1)^{m}$ factor... I'm hoping that doesn't matter though haha). I'll now attempt to work through the integral using this identity. Again, thanks for all the help!--Dudemanfellabra (talk) 23:34, 15 June 2011 (UTC)

June 14

Software

WHAT IS THE COMPUTER SOFTWER? — Preceding unsigned comment added by 117.197.165.191 (talk) 05:38, 14 June 2011 (UTC)

Try asking at The Computing Helpdesk. Perhaps a little more detail about your question would help. ―JuPitEer (talk) 06:50, 14 June 2011 (UTC)

Or read our article on computer software. Gandalf61 (talk) 09:20, 14 June 2011 (UTC)

I think the OP might be wondering how Wikipedia works. I don't know if Wikipedia has a software per se. But, as JuPitEer said: the computer reference desk would be a better place to ask. Maybe try the Wikipedia article too. — Fly by Night (talk) 14:28, 14 June 2011 (UTC)

The software that runs wikipedia is MediaWiki. Staecker (talk) 23:27, 15 June 2011 (UTC)

Evaluating the matrix exponential of a tridiagonal matrix

I am working on a classification problem based on Bayesian inference, where I observe the discrete state of an object at non-equidistant points in time (the evidence). My objective is to keep updated probabilities that the object belongs to different classes C_k, k=1,...m using Bayes' theorem. The evolution of the state can be modelled as a continuous-time Markov process. The states can be ordered such that the state only jumps to a neighboring state. The rates at which the jumps occur are a characteristic of the object class, and I have collected data from objects with known classes and based on this I have good estimates of the class specific rate matrices R_k. The rate matrices are tridiagonal since the state jumps are restricted to nearest neighbours.

The number of states n are in the range 5-20 and the number of classes m is less than 10. For the Bayseian inference update I need to evaluate the state-transition probability conditioned the class hypothesis C_k

$P(s_{j}|s_{i},\Delta t_{i,j},C_{k})=\left[\exp(\mathbf {R} _{k}\Delta t_{i,j})\right]_{i,j}$

where

$s_{j}$

Posterior state at time $t_{j}$

$s_{i}$

Prior state at time $t_{j}$

$\Delta t_{i,j}$

Time difference $t_{j}-t_{i}$

In my problem I need to evaluate the matrix exponential

$\exp(\mathbf {R} _{k}\Delta t_{i,j})$

regularly for each of the m object classes but with different update intervals. One way to do that is to diagonalize the rate matrices as

$\mathbf {R} _{k}=\mathbf {P} _{k}^{-1}{\boldsymbol {\Lambda }}_{k}\mathbf {P} _{k}$

where ${\boldsymbol {\Lambda }}$ is a diagonal matrix containing the eigenvalues (eigenrates) as then

$\exp(\mathbf {R} _{k}\Delta t_{i,j})=\mathbf {P} _{k}^{-1}\exp({\boldsymbol {\Lambda }}\Delta t_{i,j})\mathbf {P} _{k}$

which makes recalculating the matrix exponential for different update times easier, as calculating P and its inverse only needs to be done once per object class, so what I basically need to do is to make n scalar exponential calculations and then make the matrix product, which scales as ${\mathcal {O}}(n^{2})$. From the eigenrates, I also know the characteristic times in the system and I may even precalculate the matrix exponentials for some logarithmically distrubuted update times and simply pick the closest match in update time.

However, I am concerned about the numerical stability in the diagonalization. The largest eigenvalue should always be zero (corresponding to the steady state solution), but this is susceptible to roundoff error. (Until now I has postcorrected the eigenvalue setting the highest one to zero) For the remaining eigenvalues the ratio between min and max can be assumed to be smaller than 1000. I read in the matrix exponential article that doing this right is far from trivial.

Can I use the fact that my rate matrices are tridiagonal to make a more robust or elegant computation of the matrix exponentials?

--Slaunger (talk) 09:06, 14 June 2011 (UTC)

Try the formula $e^{M}=\lim _{n\rightarrow \infty }\left(1+2^{-n}M\right)^{2^{n}}$ to reduce the matrix exponential to n squarings of the matrix $1+2^{-n}M$, and not using the fact that M is tridiagonal. Bo Jacoby (talk) 15:56, 14 June 2011 (UTC).

Thank you for your response. Ok, I think I understand, but if I digonalize once, I only have to do three matrix multiplications for each different $\Delta t_{i,j}$, whereas using the approach you suggest I need make n multiplications, where n depends on how fast the expression converge, assuming I understand correctly? I realize it will converge very fast though... Obviously n should be selected such that that $2^{-n}{\boldsymbol {M}}\ll \mathbf {I}$, and this is mathematically correct, but will it be more numerically stableerrors than the diagonalization approach? What I am concerned about is the numerical stability and reliability of the diagonalization approach. It is mentioned in Matrix exponential#Computing the matrix exponential that

Finding reliable and accurate methods to compute the matrix exponential is difficult, and this is still a topic of considerable current research in mathematics and numerical analysis.

In mathematical libraries, also the Padé approximant is often used as a robust way to do the matrix exponential for general matrices (except if it is ill-conditioned), but it seems like overkill for my case where the rate matrices are constant and I only multiply it with a scalar prior to taking the exponential.

In the Octave documentation for expm I noticed a reference to Moller and Van Loan, Nineteen Dubious Ways to Compute the Exponential of a Matrix, SIAM Review, 1978, which seems very interesting in this context. Unfortunately I do not have access to that paper, but the abstract seems very interesting:

And I was thinking that maybe there was a nifty, reliable and elegant method for calculating the matrix exponential if the matrix was tridiagonal and multiplied by some scalar - at least I seem to recall that solving the eigenvalue problem for a tridiagonal matrix is much easier than for a general diagonalizable matrix. --Slaunger (talk) 19:12, 14 June 2011 (UTC)

Even when a scalar exponential e^M is approximated by (1+2⁻ⁿM)²ⁿ , n should be chosen with care. If n is too small, then the approximation has insufficient precision, and if n is too big, then round-off errors make 1 + 2⁻ⁿM equal to 1. Floating-point numbers have fixed precision, and not everything can be done. Bo Jacoby (talk) 08:49, 15 June 2011 (UTC).

Yes, that is why the question is not so simple. It is more about the most efficient and reliable algorithm than about the maths (although you need some linear algebra maths to arrive at the best algorithm). Maybe the Computer or science help desk is better place for my question? I was in doubt if numerical methods/algorithms are in scope of this help desk, when I asked the question, but decided to try here as the question was pretty mathematically oriented... In my problem i need to do these caclulation in real time for many objects on a computational platform with rather limited resources, so I need to understand how to find the best processing compromise. --Slaunger (talk) 10:11, 15 June 2011 (UTC)

As far as I'm concerned, asking at the math desk is fine. I think at the computing desk they're more used to answering questions about programming languages and systems administration than numerical algorithms. --Trovatore (talk) 10:30, 15 June 2011 (UTC)

In order to find the most efficient and reliable algorithm you need to test some algorithms. Have you tried my method before you think that something else is better? Bo Jacoby (talk) 15:51, 15 June 2011 (UTC).

A valid point. I have tried experimenting with the Padé approximant implementation in scipy, which seem to converge very fast for the examples I have tried. I have implemented the diagonalization approach in Python, which also seem to work and which is efficient as the number of computations is fixed once the rate matrices have been diagonalized. I have not tried your approach yet, but my fealing is that it is not as stable as the Padé approximant. However, I need to go to a production language like C to properly profile the different options, and this takes a considerable effort. I think I will try to get hold on the reference I mentioned earlier, where I have noticed there is also a 25 years later updated review article, and study what others have done instead of spending a lot of time of reinventing the wheel. Tak for din tid! --Slaunger (talk) 19:40, 15 June 2011 (UTC)

The 25 years later reference is also publicly available at http://www.cs.cornell.edu/cv/researchpdf/19ways+.pdf. I am reading it with interest - a lot of goodies there.... --Slaunger (talk) 07:45, 16 June 2011 (UTC)

To compute the formula $\left(I+2^{-n}M\right)^{2^{n}}$ to good numerical precision, start with $2^{-n}M$ rather than $I+2^{-n}M$ and use $(I+X)^{2}=I+(2X+X^{2})$ to perform the squaring without adding in the $I$. At some point, unless $M$ is very small, the intermediate value being stored gets large and then the $I$ can be added in and ordinary squaring can be used for the remaining steps. McKay (talk) 04:32, 16 June 2011 (UTC)

After having studied the review article, it appears to me that series expansion and multiplicative methods as suggested here will not be stable as $\Delta t_{i,j}\rightarrow \infty$ for my rate matrix problem. In my case the highest eigenvalue is always exactly zero, whereas all others are negative real numbers, which implies that

$\lim _{\Delta t_{i,j}\rightarrow \infty }\exp(\mathbf {R} _{k}\Delta t_{i,j})\rightarrow \mathbf {S} _{k})$,

where $\mathbf {S} _{k}$ is the steady-state state-transition probability matrix containing n identical column vectors. Any column vector in will $\mathbf {S} _{k}$ represent the steady-state (or a priori) probability distribution between the states. As the time difference grows, the elements of the matrix to exponentiate also grows, and so will be number of multiplications and roundoff errors. In the specific case, where the I have this eigenvalue property of the rate matrices, a matrix decomposition method seems to be a good path. However, the decomposition does not necessarily have to be an eigenvalue decomposition (although that is very easy for a tridiagonal matrix). If the condition of the matrix P_k containing the eigenvectors is too high (if it is nearly defective), one should be careful. I also learned that other decomposition methods such QR decomposition into an orthogonal and a triangular matrix can be a useful alternative to eigenvlaue decomposition, as calculating the matrix exponential of a triangular matrix should be fairly simple (have not studied the details).

Another observation is that the decomposition method require of the order ${\mathcal {O}}(n^{3})$ computations to make the decomposition but only ${\mathcal {O}}(n^{2})$ for each calculations for each subsequent $\Delta t_{i,j}$. --Slaunger (talk) 09:48, 16 June 2011 (UTC)

McKay's trick above is a clever one. The review article is scholarly and inconclusive. High floating point precision was not available in 1978. If you know that no eigenvalue has a positive real part, then use e^Mt=(e^−Mt)⁻¹ Bo Jacoby (talk) 12:31, 16 June 2011 (UTC).

It is the updated 25 years after article from 2003 I have been reading, albeit it still contains quite some old stuff reminescent of 1978 single precision computing possibilities. I agree it is not very conclusive, the bottom-line is that all methods has it pros and cons, although the pro/con balance differs from method to method and to some extend depend especially on how well-behaved the matrix you want to exponentiate is.

Thanks for the inversion trick. But does the inversion trick help when the largest eigenvalue in the rate matrix is identical zero? The rate matrices fulfill the condition that the sum of elements in each column is zero, the diagonals are negative and the offdiagonals are positive. Does a sign reversal on all elements really make it easier to exponentiate, and is the matrix inversion needed afterwards not a ${\mathcal {O}}(n^{3})$ process, or am I missing something? --Slaunger (talk) 12:54, 16 June 2011 (UTC)

The series expansion of e⁻⁵ is unstable, due to round-off errors, while (e⁵)⁻¹ is stable. e⁰ is the easier case. Yes, matrix inversion is n³, so don't do it if anything else works. The squaring method is stable, I think. The tridiagonal property is apparently not helpful. Good luck on the project! Bo Jacoby (talk) 16:34, 16 June 2011 (UTC).

Dimension and Cardinality

Let M be a smooth, real, n−dimensional manifold. I'd like to know the dimension and cardinality of C^∞(M,R), i.e. the space of smooth functions from M to R. I believe that the dimension is at least ℵ₁, and maybe even ℵ₂. I have no idea what the cardinality might be; although that isn't of paramount importance. Can anyone confirm, or deny, that the dimension is at least ℵ₁, and maybe even ℵ₂? If someone could supply a reference then that'd be great. — Fly by Night (talk) 15:45, 14 June 2011 (UTC)

I may be being stupid, but isn't M a disjoint union of as many open balls as you like a perfectly good smooth n-dimensional manifold which has as many such functions as you like? Or is there an implicit connectedness assumption somewhere in that? 128.232.241.211 (talk) 16:23, 14 June 2011 (UTC)

You're not being stupid at all, in fact you raise an interesting point. I guess you're right. I should have mentioned that it's connected. Although I'm not sure that it matters. You'd get a Cartesian product of the form

$C^{\infty }(M_{1}\sqcup \ldots \sqcup M_{k},\mathbb {R} )=C^{\infty }(M_{1},\mathbb {R} )\times \cdots \times C^{\infty }(M_{k},\mathbb {R} )\,.$

I'm not sure that that would change the dimension. The because k⋅ℵ₁ = ℵ₁. Or at least I think so… — Fly by Night (talk) 16:42, 14 June 2011 (UTC)

I think (part of) 128's point was that k need not be finite. AndrewWTaylor (talk) 17:04, 14 June 2011 (UTC)

I was just thinking of a nice hypersurface like we use in differential geometry all the time. — Fly by Night (talk) 17:37, 14 June 2011 (UTC)

Okay, so that's at least σ-compact, which still gets you separable (unless I was wrong about compact manifold => separable). --Trovatore (talk) 18:22, 14 June 2011 (UTC)

For an abstract topological space, compact does not imply separable; for example the so-called Lexicographic order topology on the unit square. It's compact and connected, but it's not separable. As for a manifold, I'm not sure. It's usual to assume connectedness and paracompactness (that makes it a metrizable space). — Fly by Night (talk) 18:47, 14 June 2011 (UTC)

It's actually pretty trivial; I just didn't see it right away. Given a compact manifold, each point has an open neighborhood that's homeomorphic to Rⁿ, so that neighborhood has a countable dense subset. By compactness, finitely many such neighborhoods cover the whole manifold. --Trovatore (talk) 19:04, 14 June 2011 (UTC)

Good work. It's easy when you know how… — Fly by Night (talk) 19:53, 14 June 2011 (UTC)

OK, first of all, I kind of suspect that you're using $\aleph _{1}$ and $\aleph _{2}$ to mean $2^{\aleph _{0}}$ and $2^{2^{\aleph _{0}}}$ respectively, is that true? That's a bad habit, unfortunately one encouraged by a lot of popularizations. The GCH is not some harmless little notational thing but rather a strong combinatorial assertion. You can write instead $\beth _{1}$ and $\beth _{2}$, although these are somewhat less universally recognized and suffer from the problem that $\beth$ and $\gimel$ look awfully similar.

Are we assuming M is compact? Then the cardinality of C^∞(M,R) is $2^{\aleph _{0}}$. The lower bound should be pretty trivial; for the upper bound, note that M is separable (I think that follows from "compact manifold"), and pick a countable dense subset; then any continuous function from M to R is determined by its values on that subset. If you drop "compact" then you can find non-separable (topological) manifolds like the long line and things get a little more complicated, but if I recall correctly there's no way to make the long line into a smooth manifold. But again that's more complicated.

For the dimension, what sort of dimension are you interested in? Topological dimension? Dimension as a real vector space? --Trovatore (talk) 16:40, 14 June 2011 (UTC)

Ermm, errr. I wasn't assuming M to be compact; I didn't think that it would have mattered. But it obviously does. I'm thinking of it as a ring, with point-wise addition and multiplication as the operations. So (I guess) that the vector space dimension would be of more useful for me. You obviously know your stuff, so go easy. Try not the fry my mind. — Fly by Night (talk) 16:59, 14 June 2011 (UTC)

Assuming M to be connected and paracompact, $C^{\infty }(M)$, equipped with the topology of uniform convergence of all derivatives on compact subsets, is a separable Frechet space. That's probably more useful to know than the linear dimension (which is $2^{\aleph _{0}}$.) Sławomir Biały (talk) 17:55, 14 June 2011 (UTC)

Is there an example of a connected infinitely differentiable manifold that's not separable? Did I remember correctly that there's no infinitely differentiable structure on the long line? --Trovatore (talk) 18:24, 14 June 2011 (UTC)

I think the Lexicographic order topology on the unit square gives a topology on a manifold (with boundary) that is compact and connected, but which is not separable. I'm not sure if that's what you were asking. — Fly by Night (talk) 18:53, 14 June 2011 (UTC)

There is a smooth structure on the long line (according to our article long line). The lexicographic order topology is not a manifold with boundary. No neighborhood of a point (x,1) for 0<x<1 is homeomorphic to an interval. Sławomir Biały (talk) 19:21, 14 June 2011 (UTC)

Also, every connected paracompact manifold is separable. (Paracompactness and local compactness implies that each component is sigma compact, hence Lindeloef, hence separable.) Sławomir Biały (talk) 19:46, 14 June 2011 (UTC)

Okay, that makes sense. Would it just be a (topological) manifold then? — Fly by Night (talk) 19:55, 14 June 2011 (UTC)

It's not any sort of manifold. Sławomir Biały (talk) 19:57, 14 June 2011 (UTC)

The article on topological manifold says that each point in the space must have a neighbourhood homeomorphic to an open subset of Rⁿ. But to define a homeomorphism you need to know the topology in both the source and the target. What must the topology be on Rⁿ to be able to talk about a homeomorphism? The unit square with the lexicographic order topology is compact, connected and Hausdorff. — Fly by Night (talk) 21:20, 14 June 2011 (UTC)

It's with the usual Euclidean topology. Sławomir Biały (talk) 23:57, 14 June 2011 (UTC)

Back to the Question

My question has blossomed into a very interesting topological discussion. But could we bring it back to the question at hand. What are the main conclusions? It seems that the space of smooth functions on a manifold M to R is a Fréchet space. Does that tell us anything about the dimension? Have we decided that the dimension is 2^ℵ₀ (which may or may not be the same as ℵ₁)? — Fly by Night (talk) 21:23, 14 June 2011 (UTC)

Any infinite-dimensional separable Frechet space has dimension as a linear space equal to the continuum. However it might be more natural to think of the dimension as countable, since there is a dense sunspace whose linear dimension is countable. This is in much the same way that the space $\ell ^{2}$ has continuum dimension as a linear space, but its "Hilbert dimension" is countable. Sławomir Biały (talk) 23:57, 14 June 2011 (UTC)

June 15

What's the probability of getting twenty heads in a row if you flip a coin one million times?

Here's my reasoning: the twenty in a row could happen in the first twenty tosses, or between the second toss and the twenty first toss, and so on. So there are 10^6 - 19 ways to get twenty heads in a row. So the probability would be (10^6 - 19)/2^20 ~ 95%. Is this right? Incidentally, this isn't a homework question, just something that came up in a conversation. 65.92.5.252 (talk) 01:12, 15 June 2011 (UTC)

No, there are many more than $10^{6}-19$ ways to get twenty heads in a row. To see this, consider how many ways there are to have the first twenty tosses come up heads: the remaining $10^{6}-20$ tosses can come up in $2^{10^{6}-20}$ different ways! (Of course, some of these possibilities also include other runs of twenty heads in a row, besides the first twenty, so you'll need to correct for that overcounting; see Inclusion–exclusion principle.) Your denominator isn't right either—there are $2^{10^{6}}$ possible outcomes for the $10^{6}$ coin tosses, which is vastly larger than $2^{20}$. —Bkell (talk) 01:25, 15 June 2011 (UTC)

Alright...so how would you do it? 65.92.5.252 (talk) 01:55, 15 June 2011 (UTC)

This is actually a hard problem. The solution to it is described on this page from Wolfram Mathworld -- it involves some pretty advanced concepts. Looie496 (talk) 02:25, 15 June 2011 (UTC)

Well, as you say there are $10^{6}-19$ possible places for a run of 20. If we treat each of these possibilities as independent (they aren't, but let's pretend), you get $1-(1-.5^{20})^{10^{6}-19}\approx 61.5\%$. Of course, as mentioned, they aren't independent: having tosses 1 to 20 all come up heads increases the odds that tosses 2 to 21 all come up heads. So outcomes with multiple runs of 20 should be over-represented compared to what you would expect if they were all independent. Since the expected total number of runs of 20 is the same, independent or not, this means that the actual answer to your question should be less than 61.5%.--Antendren (talk) 02:31, 15 June 2011 (UTC)

Thanks. 65.92.5.252 (talk) 15:59, 15 June 2011 (UTC)

The average number of rows of twenty heads if you flip a coin twenty times, is 2⁻²⁰.

The average number of rows of twenty heads if you flip a coin a million times, is 999981 · 2⁻²⁰ = 0.954.

The probability that the number is equal to k, is P_k = e^−0.954 0.954^k / k! = 0.385 · 0.954^k / k!

    0     1     2      3      4       5
0.385 0.367 0.175 0.0557 0.0133 0.00254

The probability of not getting twenty heads in a row if you flip a coin one million times, is P₀ = 0.385.

The probability of getting twenty heads in a row once or more, if you flip a coin one million times, is 1−P₀ = 0.615. Bo Jacoby (talk) 12:56, 15 June 2011 (UTC).

Cool, thanks. 65.92.5.252 (talk) 15:59, 15 June 2011 (UTC)

Um, wrong. The events are not independent (for example, 1-20 all being heads is not independent of 10-30 all being heads), so the calculation is not valid. There simply is no easy answer to this question; the calculation is genuinely hard. Looie496 (talk) 18:40, 15 June 2011 (UTC)

See our article Perfectionism (psychology). The proper way to criticize a calculation is to improve it. Bo Jacoby (talk) 19:26, 15 June 2011 (UTC).

Well, I already said above that the solution is explained on this page. Looie496 (talk) 21:08, 15 June 2011 (UTC)

Yes, and what is your improved calculation? Bo Jacoby (talk) 06:46, 16 June 2011 (UTC).

(1 000 000 - 19) * 0.5^20 = 95.37..% Cuddlyable3 (talk) 08:59, 16 June 2011 (UTC)

No that's nowehere near the nswer. A fairly reasonable estimate is got by looking for the chance of not having any so the chance of having one at least would be about 1 - (1 - 1/2^20)^1000000 i.e. about 1-1/e or 1-0.37 or about 0.63 that's a very rough estimate and doesn't deal with the problem of overlap of intervals at all. Dmcq (talk) 11:14, 16 June 2011 (UTC)

90!

Greetings, learned amigops (: I took a recreational maths test once that had a question, what are the last two nonzero digits of 90!, in order from the left? (that is, if 90! were equal to 121, they would be 21) I did not get to this question, but looking back, how would I have solved it? WA gives a solution (12) but even simple calculators were not allowed, let alone alpha. I suppose I could have written 90!'s prime factorization out, crossed out 2 and 5 in pairs, and then multipled all the remaining numbers mod 10, but is there a faster and less tedious way to do this? (remembering that all I had at my disposal were literally a pen and paper). Cheers. 72.128.95.0 (talk) 03:36, 15 June 2011 (UTC)

De Polignac's formula may or may not be helpful-Shahab (talk) 05:53, 15 June 2011 (UTC)

Since we are only interest in the two LS digits that are non-zero, we can reduce the calculations to products of 2 digit numbers. Implement the following algorithm:

      t = 1
      FOR i = 2 TO 90
         t = t * i
         IF (t MOD 10) = 0 THEN t = t / 10
         DO WHILE (t MOD 10) = 0 : t = t / 10 : LOOP
         t = t MOD 100
      NEXT

which though tedious is doable by hand and gives the answer 52 (not 12). Is this right? -- SGBailey (talk) 11:37, 15 June 2011 (UTC)

That algorithm fails at i=25, 50, 75. You need to repeat t=t/10 while (t mod 10) = 0 still holds. Algebraist 12:25, 15 June 2011 (UTC)

Algorithm repaired a la Algebraist and this gives 12. -- SGBailey (talk) 13:01, 15 June 2011 (UTC)

From an IPython shell using scipy I get

In [1]: factorial(90, exact=1)
Out[1]: 14857159644817614973095227336208257378855699612846887669422168637049
85393094065876545992131370884059645617234469978112000000000000000000000L

So, it is 12. --Slaunger (talk) 12:01, 15 June 2011 (UTC)

I gather you wanted a way to do it by hand without a program. In that case, I would have noticed that there are a lot more powers of 2 than 5 in 90! and hence even after removing all the trailing zeros, the number will still be divisible by 4. Hence, we only need to work out the result mod 25. I would then write out every number with those divisible by 5 having their factors of 5 removed and then write this list out again taken mod 25. Then I would cancel out those which are multiplicative inverses (so 2 and 13 would cancel each other out, 3 and 17, etc (This might take a while to work out but can be done) and finally from what is left it should be easy enough to calculate the product by hand mod 25. Then multiply by 4 and you're done. --AMorris (talk)●(contribs) 14:24, 15 June 2011 (UTC)

Don't multiply by 4 at the end. Just see which of the 25n+k is divisible by 4 where k is the result modulo 25. ANd by the way you can remove powers of 20 when calculating modulo 25. Dmcq (talk) 00:11, 16 June 2011 (UTC)

Just had another think of this and if I weas doing it by hand I wouldn't split into prime factors as suggested above. Instead I'd work base 25 as mentioned before and use Gauss's generalization of Wilson's theorem, the product of the numbers below 25 prime to 25 is -1 modulo 25. Applied three times up to 75 this can remove a whole pile of numbers quickly and then just remove powers of 5 and a corresponding number of powers of 2 from the remainder and multiply what remains modulo 25 - tht might be n appropriate time to split into factors. Dmcq (talk) 08:52, 16 June 2011 (UTC)

Riemann integral of a circle

Is there a way to finish this sum of rectangles? For a semicircle of radius r cut into n slices, the area of the kth slice is: ${\frac {r}{n}}2{\sqrt {r^{2}-\left({\frac {kr}{n}}\right)^{2}}}={\frac {2r^{2}}{n}}{\sqrt {1-{\frac {k^{2}}{n^{2}}}}}$

The sum of all of them is: $\sum _{k=1}^{n}{\frac {2r^{2}}{n}}{\sqrt {1-{\frac {k^{2}}{n^{2}}}}}={\frac {2r^{2}}{n}}\sum _{k=1}^{n}{\sqrt {1-{\frac {k^{2}}{n^{2}}}}}$

And extending to infinity: $\lim _{n\to \infty }{\frac {2r^{2}}{n}}\sum _{k=1}^{n}{\sqrt {1-{\frac {k^{2}}{n^{2}}}}}=2r^{2}\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=1}^{n}{\sqrt {1-{\frac {k^{2}}{n^{2}}}}}$

Somehow this has to equal ${\frac {\pi r^{2}}{2}}$, which means $\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=1}^{n}{\sqrt {1-{\frac {k^{2}}{n^{2}}}}}={\frac {\pi }{4}}$ Is it possible to show that this is true? This isn't for homework, just curiosity. I've been able to do this with a parabola, cone, sphere, just about everything but a circle, so it seems weird to me that it's so difficult. KyuubiSeal (talk) 03:53, 15 June 2011 (UTC)

I haven't taken a look at the math, but there's an easier way to show that the area of a circle is πr^2: http://en.wikipedia.org/wiki/Area_of_a_disk#Onion_proof. 65.92.5.252 (talk) 03:58, 15 June 2011 (UTC)

Yeah, plus there's the 'chop into sectors and rearrange into almost-parallelogram' method. Also, the integral of the circumference is area? That looks like it works for spheres too. Weird... — Preceding unsigned comment added by KyuubiSeal (talk • contribs) 04:09, 15 June 2011 (UTC)

[wrong answer removed] Ignore me, I confused your sum for an integral ... in my defence it was about midnight when I posted that. 72.128.95.0 (talk) 15:11, 15 June 2011 (UTC)

Well, if you divided a circle like an onion, each segment would have a width dr. The area between r and r + dr is approximately (circumference at that point) * (width) = 2πrdr. Then, you can just integrate. (To the experts: please don't smite me for ignoring rigor). 65.92.5.252 (talk) 04:16, 15 June 2011 (UTC)

Maybe this has something to do with the Basel problem? That does create a pi from a sum, but I don't know how I would apply it. Or if it's even relevant. — Preceding unsigned comment added by KyuubiSeal (talk • contribs) 17:12, 15 June 2011 (UTC)

This site has the same sum. I agree that it would be nice to know if you can show it sums to $\pi /4$ using another technique. To me the series looks quite elegant, and clearly isn't difficult to derive, so I'm surprised it doesn't seem to be on the long list of Pi formulas at mathworld. Perhaps it is somehow trivially equivalent to some other series? 81.98.38.48 (talk) 21:13, 15 June 2011 (UTC)

This is the Riemann sum for

$\int _{0}^{1}2r^{2}{\sqrt {1-x^{2}}}dx$

which is not an easy integral to evaluate. I know of the methods which involve integration by substitution of $x=\sec(t)$ or $x=\sin(t)$ or x = sech(t) with use of hyperbolic or trigonometric identities.(Igny (talk) 02:20, 16 June 2011 (UTC))

It should be possible to compare ${\frac {2}{n}}\sum _{k=1}^{n}{\sqrt {1-{\frac {k^{2}}{n^{2}}}}}$ to a polygonal approximation of the arc length of the part of the unit circle in the first quadrant, and so prove that in the limit this Riemann sum tends to the arc length. (I think this only involves elementary inequalities.) Then, using the geometric definition of π as half the circumference of the unit circle, this should then show

$\lim _{n\to \infty }{\frac {2}{n}}\sum _{k=1}^{n}{\sqrt {1-{\frac {k^{2}}{n^{2}}}}}={\frac {\pi }{2}}$

which can then be used to evaluate the aforementioned limit. I've not really tried to write out the details of this, though. Sławomir Biały (talk) 14:14, 16 June 2011 (UTC)

Highest number

Suppose there are N balls in a bin, each distinctly labeled with a number from 1 to N. I draw D balls from the bin, and note the highest numbered ball I get, which I call S. Is there a way to calculate the probability distribution of S? I wouldn't mind a general answer, but in the problem I'm dealing with, D<<N. 65.92.5.252 (talk) 17:07, 15 June 2011 (UTC)

There are ${\binom {S-1}{D-1}}$ different ways that a highest number S can arise. So the distribution is

$p_{S}={\frac {\binom {S-1}{D-1}}{\binom {N}{D}}}.$

--Sławomir Biały (talk) 18:49, 15 June 2011 (UTC)

Sorry, do you mind explaining how you got ${\binom {S-1}{D-1}}$? 65.92.5.252 (talk) 20:12, 15 June 2011 (UTC)

For a fixed S, the remaining balls are drawn from the set {1,...,S-1}. Sławomir Biały (talk) 20:53, 15 June 2011 (UTC)

Cotcha, thanks. 65.92.5.252 (talk) 09:39, 16 June 2011 (UTC)

If Visible Light Represented by People/Person, what's the Ratio

Just a thought, if the ELECTROMAGNETIC SPECTRUM was represented by population/people, how many people would see the Light? --i am the kwisatz haderach (talk) 17:41, 15 June 2011 (UTC)

I think it would just be (highest wavelength of visible - lowest of visible) / (highest of spectrum - lowest of spectrum), then multiply by earths population. KyuubiSeal (talk) 18:19, 15 June 2011 (UTC)

The Universe on an eps on Nebulas, says Visible light is represented by only 1 inch on an electromagnetic scale of over 2000 miles. According to this show, I would take 63,630 inches/1 Mile x 2000 to get my 126.72 Million inches. With 1/126,720,000, w/worlds pop at 6.92 Bil, I take 6.92 Billion and divide by 126.72 Million to get about 55 People seeing the Light. --i am the kwisatz haderach (talk) 20:48, 15 June 2011 (UTC)

June 16

Geometry problem

Hello all, it's me from yesterday. This is the other question that I did not answer (pretty good, considering this was a 25 question test). Unlike the 90! one, I tried on this one but did not get it and so refrained from answering (guessing is penalized). It goes, Let R be a square region and n>3 an integer. A point P inside R is called n-ray partitional if there are n rays emanating from P divding R into n triangles of equal area (for example, there is one 4-ray partitional point at the center of the square). How many points are 100-ray partitional but not 60-ray partitional? I didn't even know where to begin on this one- can someone point me right? Thanks. 72.128.95.0 (talk) 00:48, 16 June 2011 (UTC)

Suppose wlog that R is the unit square. Orient R so that the sides are parallel to the coordinate axes and the lower left hand point is at the origin. Call the point (x,y). The rays from the point to the vertices of the square divide the square into four triangles of areas $x/2,y/2,(1-x)/2,(1-y)/2$. Now, (x,y) is a (2n)-ray point if and only if $x/2=a/2n$ and $y/2=b/2n$ for some integers $0\leq a,b\leq n$ (since these two triangles need to be divisible into equal pieces of area $1/2n$). Sławomir Biały (talk) 02:38, 16 June 2011 (UTC)

Angle bisectors of a triangle

prove that the angle bisectors of a triangle is concurrent. — Preceding unsigned comment added by Qwshubham (talk • contribs) 07:55, 16 June 2011 (UTC)

You need to put in a title otherwise it looks like it follows from the previous discussion. Have you had a look at triangle? Dmcq (talk) 08:42, 16 June 2011 (UTC)

Spot the error?

$0$
$=0+0+0+0+...$
$=(1-1)+(1-1)+(1-1)+(1-1)+...$
$=1-1+1-1+1-1+1-1+...$
$=1+(-1+1)+(-1+1)+(-1+1)+...$
$=1+0+0+0+...$
$=1$
Widener (talk) 13:29, 16 June 2011 (UTC)

The third and fourth equals signs are not justified. Indeed, the series $\sum (-1)^{n}$ is divergent. What this fallacious argument illustrates is that the summation of infinite series is not associative: one can't "insert and remove parentheses" into series in general. There is a discussion of this in Tom Apostol's textbook "Mathematical analysis", for instance. Sławomir Biały (talk) 13:47, 16 June 2011 (UTC)

See Grandi's series. Gandalf61 (talk) 13:52, 16 June 2011 (UTC)

…or the Eilenberg–Mazur swindle. — Fly by Night (talk) 14:58, 16 June 2011 (UTC)