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

July 11

Simple Probability

Suppose that there have been 20 no-hitters in baseball history. What is the probability that there's been at least one on each day of the week?

The case for 7 no-hitters is simple enough, but I'm having trouble extending this to 8+ days. Help would be greatly appreciated. 74.15.137.192 (talk) 00:33, 11 July 2010 (UTC)

I only have time for this quick answer: I wonder if Schroedinger's method would help with this one? Michael Hardy (talk) 02:16, 11 July 2010 (UTC)

Isn't this what Stirling numbers of the second kind are for? $(S(20,11)*7!)/(7^{20})$should do it. —Preceding unsigned comment added by 203.97.79.114 (talk) 04:52, 11 July 2010 (UTC)

Shouldn't it be S(20,7)*7!/7^20? (There are seven days of the week, right?) 74.15.137.192 (talk) 09:22, 11 July 2010 (UTC)

This is the Coupon collector's problem. Robinh (talk) 19:27, 14 July 2010 (UTC)

ordinals

I'm interested mostly in countable ordinals in this question, in fact computable ones, I think. Is there a concept of a limit ordinal that represents a fixed point of the (informally) biggest operation seen so far? By that I mean ω is such an ordinal, and maybe 2ω and ω^ω are as well (not sure about further iterations of exponentiating), and the next thing after that is ε₀, but something like ω³+ω²·2+ω·3 would not be, even though it's a limit ordinal. The next thing after ε₀ would be ε₁ or maybe Γ₀. I don't mean a singular ordinal since there's only one of those for each cardinal. Am I making any sense? Maybe what I'm looking for is the places where various reasonable ordinal notations run out of gas. Thanks. 71.141.88.179 (talk) 01:16, 11 July 2010 (UTC)

The question does not make much sense without specifying rigorously which operations you take into consideration. It's fairly trivial to cook up an artificial ordinal notation system which "runs out of gas" at ω³ + ω²·2 + ω·3.—Emil J. 13:13, 12 July 2010 (UTC)

Thanks, I'm just asking if there is a way to formalize the usual informal way of explaining ordinals. You know, you've got 1,2,3...ω,ω+1,...,ω·2,...ω·3...ω²...ω³...ω^ω...ω^ωω...ε₀...

For each place that "..." appears in the above, what comes next? Obviously I've missed some intermediate ones, but the idea is that at each stage we've iterated some newly concocted ordinal operation and found a fixed point for it, as opposed to just finding the nearest limit ordinal by iterating the successor operation. Maybe each one corresponds to the order type of some natural combinatorial structure? 71.141.88.179 (talk) 19:28, 12 July 2010 (UTC)

Simplifying Radical Expressions

Hello. How would you simplify ${\sqrt {11+6{\sqrt {2}}}}$ to $3+{\sqrt {2}}$? If you let ${\sqrt {11+6{\sqrt {2}}}}=a+b$, how can you identify 11 as a sum of squares, $a^{2}+b^{2}$ and not anything else? Thanks in advance. --Mayfare (talk) 03:18, 11 July 2010 (UTC)

You can check the identity by letting $a={\sqrt {11+6{\sqrt {2}}}},b=3+{\sqrt {2}}$, computing a² and b², and checking whether they are equal. $11=3^{2}+({\sqrt {2}})^{2}$, a perfectly good sum of two squares in the extension field $\mathbf {Q} [{\sqrt {2}}]$.

71.141.88.179 (talk) 03:29, 11 July 2010 (UTC)

See Nested radical for the conditions where this can be done for nested square roots. Dmcq (talk) 11:25, 11 July 2010 (UTC)

In general, to find ${\sqrt {p+q{\sqrt {2}}}}$ where p and q are rational you proceed as follows:

${\sqrt {p+q{\sqrt {2}}}}=r+s{\sqrt {2}}$

$\Rightarrow p+q{\sqrt {2}}=r^{2}+2rs{\sqrt {2}}+2s^{2}$

$\Rightarrow p=r^{2}+2s^{2}{\text{ ; }}q=2rs$

$\Rightarrow 2r^{4}-2pr^{2}+q^{2}=0$

$\Rightarrow r^{2}={\frac {p\pm {\sqrt {p^{2}-2q^{2}}}}{2}}{\text{ ; }}s^{2}={\frac {p\mp {\sqrt {p^{2}-2q^{2}}}}{4}}$

The identification of coefficients in line 2 not only requies p and q to be rational, but also r² and s² must also be rational, and so ${\sqrt {p^{2}-2q^{2}}}$ must be rational too. Gandalf61 (talk) 17:26, 11 July 2010 (UTC)

Why does ${\sqrt {a^{2}-b^{2}c}}$ have to be an integer if some nested radical, ${\sqrt {a+b{\sqrt {c}}\ }}$, can be denested into a sum of surds? Thanks again in advance. --Mayfare (talk) 20:35, 12 July 2010 (UTC)

Angle

• Hi, How is the angle=arc/radius?Max Viwe | Wanna chat with me? 04:49, 11 July 2010 (UTC)

Radian should get you started on this. -- Meni Rosenfeld (talk) 05:22, 11 July 2010 (UTC)

Automorphism group of a Hilbert space

What is the largest subgroup of the diffeomorphism group of a 2n-1 sphere that is holomorphic when the sphere is taken to be the unit sphere of an n-dimensional complex space? 74.14.108.160 (talk) 06:58, 11 July 2010 (UTC)

What exactly are you looking for here? It doesn't make sense to say that a subgroup of maps that are also holomorphic? Do you mean a subgroup of holomorphic maps? Are you considering the diffeomorphism group of the sphere (as an abstract manifold) or the subgroup of the diffeomorphism group of the ambient space which preserves the sphere (as a submanifold of the ambient space)? •• Fly by Night (talk) 19:47, 14 July 2010 (UTC)

Yes, I meant to say the subgroup whose members are holomorphic maps rather than calling the subgroup itself holomorphic. The sphere was meant to be an abstract manifold and was only embedded in the complex space in order to give diffeomorphisms of the sphere a holomorphicity criterion. 76.67.74.129 (talk) 07:54, 16 July 2010 (UTC)

Mathematical induction

The article we have on mathematical induction seems to imply that assumption is an integral part of the process. This doesn't appear right to me. Statements made about an arbitrary k during the inductive step are only allowable because the existence of at least one suitable k is proven in the basis step. No speculation or assumption is done. Now, to the right person, there is no difference between "Let k be an integer for which the statement holds..." and "Assume the statement holds for some k..."; but to another reader, it's the difference between speculation and logical argument. The prevalence of the word assume in textbooks, at least over here, is part of the difficulty people seem to have with the legitimacy of induction. Am I being too picky or misunderstanding things, or is this something that should be looked at? Thanks for the help. —Anonymous Dissident^Talk 13:33, 11 July 2010 (UTC)

I always used to say "suppose it is true for some k" ... I also explained (once, not every time) that use of a logical contrapositive makes the argument clear and finite (rather than infinite induction). Dbfirs 22:00, 11 July 2010 (UTC)

The article explains the concept in several different ways so I think most readers will understand at least one version. My experience teaching this is that it's something of a pons asinorum in that there are always going to be a few people who have a very difficult time getting it. Keep in mind though that Wikipedia isn't intended to teach the subject from scratch, so a completely foolproof explanation isn't the goal.--RDBury (talk) 23:13, 11 July 2010 (UTC)

It's always a bit hard to find the right wording to explain this point when teaching induction, but once you see it it's not a difficult concept at all. The issue is that, yes, you make an assumption, but only temporarily. In logical jargon the assumption is discharged before the end of the proof, and doesn't count as an assumption for the proof as a whole.

To prove $\forall nP(n)$, you have to prove two things: First, you have to prove $P(0)\,\!$; how you do that doesn't concern us here. More to the point, you need to prove $\forall k\left(P(k)\implies P(k+1)\right)$.

How do you do that? Well, how do you prove $A\implies B$ in general? You assume $A\,\!$ and conclude $B\,\!$. The assumption of $A\,\!$ is truly an assumption, but only for the length of time that you're in the little subproof of $B\,\!$. Once you're done with that, $A\implies B$ has been proved and the assumption is discharged (that is, it's no longer an assumption).

Exactly the same deal for the assumption of $P(k)\,\!$ when proving $P(k+1)\,\!$.

(Aside to Dbfirs: I don't think saying "suppose" rather than "assume" helps at all; they're synonyms.) --Trovatore (talk) 22:46, 11 July 2010 (UTC)

Not if you say "suppose we can find a value of k for which the statement is true". It conveys a different impression of the argument, avoiding the (unfounded) suspicion that we are assuming what we set out to prove. Dbfirs 07:26, 12 July 2010 (UTC)

Hmm, possibly. But they still have to deal with the proof-within-a-proof thing, and specifically that the proof-within-a-proof may have different assumptions than the whole proof, one way or another.

I think this is the same issue people have with proof by contradiction — there's a mental leap involved in "assuming" something that, come to find out, is not actually true. You see it over and over again in objections to, say, Cantor's diagonal argument; people will say "Cantor assumes you can list the real numbers! But you can't!", and not notice that that's actually the thing being proved. --Trovatore (talk) 07:46, 12 July 2010 (UTC)

"Suppose" and "Assume" are basically synonyms, so I don't see any real improvement. --Tango (talk) 09:24, 12 July 2010 (UTC)

This is exactly what the OP is talking about- to the uninitiated, these two words are not synonyms. In common language, "suppose" is somewhat of a hypothetical assertion of something which may or may not be true (this is the meaning mathematicians want), while "assume" means something is asserted without proof as being true in some wider or objective context (this is basically never what mathematicians mean). People beginning to read serious mathematics need to be taught that "assume" means "suppose", and it's natural for them to get confused otherwise. Staecker (talk) 11:58, 12 July 2010 (UTC)

Mathematical inductions consists of two steps: step 1: P(0), step 2: P(n)==>P(n+1). one of these is called the induction. A common misunderstanding is to call part 2 the induction. Logically it is part 1 which is the induction step. Induction is concluding from special cases. Bo Jacoby (talk) 07:44, 12 July 2010 (UTC).

I would say that the "induction" is putting the two steps together to reach a conclusion. Dbfirs 19:19, 12 July 2010 (UTC)

The word 'induction' is much older than the idea of 'mathematical induction'. So 'mathematical induction' got its name for a reason. That reason being that is contains an element of good oldfashioned philosophical induction. That element being P(0). Bo Jacoby (talk) 21:26, 12 July 2010 (UTC).

I'm skeptical of the claim that the name "induction" was applied because the method was thought of as philosophical induction from a single example. --Trovatore (talk) 23:40, 12 July 2010 (UTC)

Why else call it induction, if not because it contains an element of induction? (Although a single example is theoretically sufficient, in practice you also try P(1) and P(2) and P(3) to give a hint about the truth of the assertion before you work on the P(n)==>P(n+1) argument). Bo Jacoby (talk) 04:47, 13 July 2010 (UTC).

I too am skeptical of this. Do you have any evidence beyond your own inability to think of another explanation? Algebraist 09:33, 13 July 2010 (UTC)

Induction is concluding a general statement from observed special cases (and more generally, any form of reasoning that usually works but is not strictly guaranteed to be correct), but not from a single special case. One would check P(0), P(1), P(2), P(3), etc., and after reaching a sufficiently (depending on the application and desired level of confidence) high number and getting sufficiently bored, one would conclude that P(n) for every n by induction. Mathematical induction, which is indeed named after this "philosophical" induction (it does not actually have much to do with philosophy, it's the usual way of inferring general rules in natural sciences like physics), does the same in a sense, except that it involves a property (a proof of P(n) → P(n + 1)) which enables to generate an argument for all these special cases P(0), P(1), P(2), etc. uniformly (by chaining instances of the implication), and leads to the desired conclusion in a mathematically rigorous way. Claiming that the P(0) step is the induction is nonsense. As for calling P(n) → P(n + 1) the "induction step", this does not quite correspond to the origin of the term "induction" as described above, but that's irrelevant. In mathematics it is established terminology, with obvious etymology (it is the main step in what is called "(mathematical) induction", so we can as well call it the "induction step"), and there is nothing wrong with it.—Emil J. 13:21, 13 July 2010 (UTC)

Maybe it's language-dependent, but in Hebrew the two parts are often called "induction base" and "induction step" (בסיס האינדוקציה, צעד האינדוקציה), and I took the etymology to be: Both parts together constitute (mathematical) induction; the first is where we start, and the second is what allows us to step from each number to the next. -- Meni Rosenfeld (talk) 15:02, 13 July 2010 (UTC)

Gabriel's Horn

In Gabriel's Horn are the diagrams wrong? The text says x>=1 yet the diagrams seem to do x>0. -- SGBailey (talk) 14:16, 11 July 2010 (UTC)

Well the diagram does do some other shape than 1/x between 0 and 1, but it would be better to have a diagram that starts at x=1. I'd like one that showed the opening a bit so it looked more horn like rather than 2d. I'm surprised there's no reference to the problem of painting it. You only need a finite amount to fill the inside but would need an infinite amount to paint the outside. Dmcq (talk) 16:10, 11 July 2010 (UTC)

The outside may have infinite area, but a finite amount of paint of zero thickness would be required to cover it - just get two of them vertically. fill one with paint, fit the other inside then lift it out.→86.132.163.37 (talk) 15:46, 13 July 2010 (UTC)

July 12

order of growth

To show that log x grows more slowly then x^c (c > O) is it sufficient to show that log x/x^c goes to 0? How does that mathematically imply that log x is less then x^c for sufficiently large x. Thanks-Shahab (talk) 06:38, 12 July 2010 (UTC)

I can answer the second part. If $\lim _{x\rightarrow \infty }{\frac {\log x}{x^{c}}}=0$, then for every $\epsilon >0$ there exists $N\in \mathbb {R}$ such that for all $x>N$, $\left|{\frac {\log x}{x^{c}}}\right|<\epsilon$. Choosing $\epsilon =1$ gives us that for large enough $x$ (larger than a finite positive real number $N$), ${\frac {\log x}{x^{c}}}<1$, which implies that $\log x<x^{c}$ (since $x^{c}>0$ whenever $x$ is positive). RJaguar3 | u | t 06:44, 12 July 2010 (UTC)

Thanks for answering both parts.-Shahab (talk) 06:50, 12 July 2010 (UTC)

Calculus/Derivatives

Find the equations of both lines that are tangent to the curve y=1+x^2 and are parallel to the line 12x-y=1

—Preceding unsigned comment added by KRmiwaD93 (talk • contribs) 07:38, 12 July 2010 (UTC) I need some help finding the equation. Could I have an explanation please? Thanks.

What have you tried so far? 71.141.88.179 (talk) 08:08, 12 July 2010 (UTC)

The question didn't actually ask for both lines did it? Are you sure it didn't say the line that is both tangent to.. and parallel to ...? Dmcq (talk)

That's the way I read it. —Anonymous Dissident^Talk 08:45, 12 July 2010 (UTC)

If the line has to be parallel to $12x-y=1$ then it must have the same gradient. You then need to find out at which value of x the curve $y=1+x^{2}$ has that gradient. Readro (talk) 09:17, 12 July 2010 (UTC)

Well one can't have 'both lines' as no two points on the quadratic have the same tangent direction whereas a straight line only has the one tangent direction. Dmcq (talk) 11:32, 12 July 2010 (UTC)

In general, there is only one tangent to a given parabola that is parallel to a given line. The exception is that there are no tangents parallel to the axis of the parabola.--RDBury (talk) 13:36, 12 July 2010 (UTC)

Rewrite the linear part as $y=12x-1$, and then you mentioned derivatives in the title, what does differentiating with respect to x give and what use is that? Dmcq (talk) 14:33, 12 July 2010 (UTC)

Trig question

Resolved

I'm having a bit of trouble trying to solve the following identity verification:

[ (sec - tan)^2 + 1 ] divided by [(sec)(csc) - (tan)(csc)] entire fraction set equal to 2tan

I have gotten as far as converting the denominator in terms of sine and cosine, but I'm a bit stuck from there. Any help is appreciated! Thanks, WordyGirl90 12:07, 12 July 2010 (UTC)

If you express the numerator in terms of cos and sin too it works out pretty simply - don't forget a famous identity involving the squares of cos and sin. AndrewWTaylor (talk) 12:57, 12 July 2010 (UTC)

If you divide said famous identity by the square of cos x then you get another identity in terms of tan and sec, which you can use if you fancy cancelling some terms first before converting to sin and cos. Readro (talk) 13:06, 12 July 2010 (UTC)

Thanks guys. A classmate solved it basically through factoring. I ended up using his method. Thanks anyway! WordyGirl90 19:58, 12 July 2010 (UTC)

integers solutions

Resolved

Hello. I have the following equation in three variables: 3x + 4y = 7z. I want to find out solutions to it which satisfy the following criteria: one they are all positive integers, secondly, they are all distinct, thirdly x,y,z are all less then 30. The only ways I know are to set it up as an integer programming problem, and use a software which I have, or to write a computer program which uses brute force. I want to then find out solutions for 2x + 5y = 7z, and in general I want to find out a way to solve ax + by = (a+b)z. What would be the appropriate way? Thanks-Shahab (talk) 14:25, 12 July 2010 (UTC)

$x\equiv y{\pmod {7}}$. For the general case, $x\equiv y{\pmod {a+b}}$. Gandalf61 (talk) 14:40, 12 July 2010 (UTC)

...assuming (without loss of generality) that a and b are coprime.—Emil J. 14:47, 12 July 2010 (UTC)

To write it more explicitly, integer solutions of the equation are exactly triples of the form (x, x + k(a + b), x + kb), where x and k are integers.—Emil J. 14:51, 12 July 2010 (UTC)

Gandalf61 how do I solve $x\equiv y{\pmod {7}}$ and from where did you get it. Thanks to you both for responding so fast.--Shahab (talk) 15:18, 12 July 2010 (UTC)

$x\equiv y{\pmod {7}}$ just means that x and y leave the same remainder when you divide them by 7 - see modular arithmetic. For a parametric solution, just pick two integers x and k and use Emil J.'s solution (x, x + 7k, x + 4k). Geometrically, these solutions all line on the plane spanned by the vectors (1,1,1) and (0,7,4). Gandalf61 (talk) 15:46, 12 July 2010 (UTC)

No, no...I mean how did you deduce that x,y such that $x\equiv y{\pmod {7}}$ give the solutions.-Shahab (talk) 16:37, 12 July 2010 (UTC)

On the one hand, if 3x + 4y = 7z, then 7 | 3x + 4y, hence also 7 | 4(y − x). As 7 and 4 are coprime, this implies 7 | y − x, i.e., $x\equiv y{\pmod {7}}$. On the other hand, if this conguence holds, then z = (3x + 4y)/7 = x + 4(y − x)/7 is an integer, and solves 3x + 4y = 7z.—Emil J. 16:43, 12 July 2010 (UTC)

Thanks, its all clear now-Shahab (talk) 16:51, 12 July 2010 (UTC)

July 13

the value of 0/0

i have a doubt for long days. what is the value for 0/0??? upto my knowledge i have guessed that this will have three values as shown below....could you please give me the right answer????

case (i):

 0/0=0

reason: zero divided by any number is equal to zero.

case(ii):

 0/0=1

reason: any number divided by the same number is equal to zero.

case(iii):

 0/0=infinite

reason: any number divided by zero is equal to infinite.

i have asked this question to many teachers. all said that the answer is infinite.....but they can't explain why we shouldnot consider the remaining cases.....please explain me —Preceding unsigned comment added by 122.183.208.130 (talk) 14:35, 13 July 2010 (UTC)

Division by zero is undefined. So, it does not have a value. You can argue that it is any value you like. So, in a sense, division by zero produces EVERY answer possible. -- kainaw™ 14:37, 13 July 2010 (UTC)

You mean division of zero by zero, I suppose. It does not make sense to make the value of x/0 a finite real number for nonzero x.—Emil J. 14:44, 13 July 2010 (UTC)

See indeterminate form. --Tango (talk) 14:40, 13 July 2010 (UTC)

In computing dividing one floating point 0 by another will give a special value called Not a Number, which basically is saying it is indeterminate. In reasoning about values in automatic proofs it is liable to be set to Bottom type which is yet another way of saying the same thing - but then again one might mean any value rather than no value. In some circumstances a value can be defined for it for instance x/x is indeterminate when x'=0 but it has a limit value of 1 at that point.You might as well ask how many angels can dance on the head of a pin? Dmcq (talk) 14:58, 13 July 2010 (UTC)

If someone with computer graphing skills can upload a graph showing together the three equations 0/x = y, x/x = y, and x/0 = y, then we might see where they lead for 0/0 = y.—Wavelength (talk) 15:11, 13 July 2010 (UTC)

There is nothing to graph here. For $x\neq 0$ we have $0/x=0,\ x/x=1$, and in the real projective line $x/0=\infty$. You also have $(2x)/x=2$ and $x/(7x)=1/7$. All of these approach the indeterminate form 0/0, and because of this, there is no natural definition for it. -- Meni Rosenfeld (talk) 15:23, 13 July 2010 (UTC)

Division by zero is also relevant. -- Meni Rosenfeld (talk) 15:24, 13 July 2010 (UTC)

Your teacher, even allowing them to be a bit sloppy, isn't right to say "infinite". More often the answer is something like "unknown". Imagine that you're trying to calculate the speed of an object (which is travelling at a steady speed) using the equation speed = distance / time. If you check how far its travelled after 2 seconds and find it has travelled half a metre, then its speed is 0.5 / 2 = 0.25 metres per second. If you had checked after just half a second you would find it had travelled an eighth of a metre, so its speed is still 0.125 / 0.5 = 0.25 metres per second. If you check how far it has travelled after zero seconds i.e. after no time at all, then you would find it hasn't travelled at all, so your calculation would look like 0/0. But this is what you would get no matter how fast or slow the object was travelling, so really "the object travels 0 metres in 0 seconds" gives no information. (What your teacher was thinking of was x/0 for any x other than 0 e.g. if an object travelled 2 metres in 0 seconds then it must have been going infinitely fast.) Quietbritishjim (talk) 00:36, 14 July 2010 (UTC)

A (slightly) more rigorous way of looking at it is to look at the graph. The page inverse function shows how to get from an equation like y=(something involving x) to x=(something involving y): by flipping about the diagonal line shown on that graph. In our case we want to go from y = 0 x to x = y / 0. But y = 0 x is a horizontal line, so x = y / 0 becomes a vertical line. This backs up the idea that if you try to take 0 / 0 you have any (or all) values, whereas y / 0 for any other y doesn't make sense (or is infinite, if you allow that). Quietbritishjim (talk) 00:43, 14 July 2010 (UTC)

The fraction a/b is 'the' solution to the equation bx=a. If b≠0 then this equation uniquely determines x, (because (b≠0 and bx=a and by=a) → (b≠0 and bx−by=a−a) → (b≠0 and b(x−y)=0) → (x−y=0) → (x=y)). If a=b=0 then the equation bx=a is 0x=0 which is true independent of the value of x, and so the equation does not define x, and so 0/0 is undefined. If a≠0 and b=0, then the equation bx=a is 0=a, which is false independent of the value of x. Bo Jacoby (talk) 03:20, 14 July 2010 (UTC).

time to break out truth

In case the above isn't convincing to you, let's break out actual reality - you know, truth. So, what is 0 - it is the absence of a single one or fraction of whatever you're counting, but not negative - you don't owe any either. For example, 0 apples is the complete absence of a single Apple. Now, I am about to do strictly integer division - no fractions. Let's say you drive to my house, pick up 2 apples, drive home, put them in your basket at home, and repeat until you can't make your next drive, since there aren't enough apples left. How many times can you make that drive (physically - we are talking about reality here, not math). You can physically do that half as many times (INTEGER DIVISION) as I have apples. If I have 8 Apples, you can drive to my house, pick up two, drive home, and repeat, 4 times (8/2 = 4). After the fourth time, you can't do that again, there not being enough apples at my house to make the trip. So, that is how many times you can do it. Now what if instead of coming to my house and picking up 2 apples, you come to my house and pick up 0 apples, drive home, and repeat. After how many trips will you have to stop, there not being enough apples at my house for you to make your next trip? There is no answer to "after how many do you stop" because you do not stop. It's not that you stop after infinite times - you do not stop; the division is not exhaustive: you can always do one more. So, if the normal definition of integer division would be subtracting the divisor one time until you can't do that any more* (because you run out of the dividend), then you will never meet that definition: you will never "run out" of the dividend when you're taking 0 from it. So, there is no solution to how many times you are going to be able to do that, if the process is never finished. This is like asking: if every time you say something, your wife says something, and every time your wife says something, you say something, then if you are the first to speak, how many times will the last person to speak have spoken? There is no "last person to speak" by that definition, so it is a meaningless question, it fails to refer. Asking what 5/0 is, is the same as asking what the value of the last prime is. There is no last prime, and there is no end result to the division. Saying 5/0 is "infinite" is just as wrong as saying the "last prime" is "infinite". The last prime is not infinite, since there is none.84.153.208.32 (talk) 10:13, 14 July 2010 (UTC)

• obviously this is the normal definition. When I ask you how many times you can remove 2 apples from 8, your answer isn't "Oh, you have a lot of choices. You can do it 0 times, 1 time, 2 times, 3 times, or 4 times - these are the physically possible alternatives facing you when you are looking at 8 apples and are to remove 2 a certain number of times, these are the possibilities of how many times you can do that.". Yes, "linguistically" the question "how many times can you remove 2 apples from 8" has the answer "0, 1, 2, 3 or 4", but that's not how we understand it. We understand "how many times until you can't do it again." That's the definition, and by that definition when you divide by 0 you do not get "any answer you want", any more than when you divide 8 by 2 you get "any answer you want, from the choices 0, 1, 2, 3, or 4" -- the definition is to do it until you can't do it one more time, and since there is no such point in the calculation, there is no answer when dividing by 0. It's like me telling you how to calculate Mango's number: you start with 2, then keep doubling (2, 4, 8, 16, 32) until you get to a negative number: that's Mango's number. What is the value of Mango's number? (Obviuosly it is not "infinite", or "any number you want", or architecture-dependent). No, there is no Mango's number. It's the same if we say Mango's number is defined as "4/0": there is no value, the definition does not admit of a point at which you can say, "Okay, now I have Mango's number", just as you can't reach a point where you can say "Okay, now I have the largest prime." You can't say "Okay, now I have the value of 4/0".

You are correct in saying that there is no answer in the real numbers, but many mathematicians and also many non-mathematicians are happy with R, the Extended real number line, where the answer to x/0 is plus or minus infinity for non-zero x. Dbfirs 08:25, 16 July 2010 (UTC)

The extended real number line is not suitable for division by zero. For this you need the real projective line, where 1/0 is unsigned infinity. -- Meni Rosenfeld (talk) 09:07, 16 July 2010 (UTC)

Another way round is used in IEEE floating point where they have Signed zero. So you either have plus infinity equal to minus infinity or you have plus zero being different from minus zero, take your pick ;-) Dmcq (talk) 11:47, 16 July 2010 (UTC)

I considered linking to the real projective line article, but most people are happier with plus infinity being distinct from minus infinity. Dbfirs 17:06, 17 July 2010 (UTC)

July 14

Free stuff

What's the free ring over an abelian group? Is it this: given an abelian group A, take the free ring generated by A then quotient it by the ideal generated by all the i(a)+i(b)-i(a!b), where i is insertion of generators and ! is the addition in A?

Also I was reading about Freyd's adjoint functor theorem. If you run through the whole proof it seems to be somewhat constructive. My book (MacLane's 2nd edition) on page 125 proves the forgetful functor from compact hausdorff spaces to SET has a left adjoint using adjoint functor theorem; he finds a small solution set explicitly then applies the theorem. Did this suggest how to construct an explicit stone cech compactification? Similarly for Grp. Does the adjoint functor theorem suggest ways to construct free objects explicitly? Because free groups are so much more complicated than free abelian groups (you could put the abelian relation on the free group but why do that when you can use set of all cofinally 0 function from X to the integers) I wonder how they managed to get free groups in the first place. Money is tight (talk) 04:17, 14 July 2010 (UTC)

Regarding the first question, I don't specifically know that terminology, but I think it would be the group ring of Z over A. Using your phrasing I guess that would be the free ring generated by A modded out by the ideal generated by all the i(a)*i(b) - i(a!b). Rckrone (talk) 06:11, 14 July 2010 (UTC)

I think what you described is the tensor algebra over A with A considered as a Z-module. (Can anyone confirm if that is correct?) Rckrone (talk) 06:26, 14 July 2010 (UTC)

Sorry for the confusion I was in a rush. What I wanted was the left adjoint to the forgetful Rng->Ab, sending each ring to its underlying addition abelian group. I've never heard of this construction before. Also my 2nd question is more clearly stated as: How do people explicitly construct free objects for the first time? Is it raw ingenuity or is there some algorithm in doing so? Money is tight (talk) 09:20, 14 July 2010 (UTC)

For algebraic categories like the examples you mentioned there is a uniform "algorithm". If U and V are varieties such that the signature σ of U includes the signature τ of V and V includes all reducts of algebras from U, then the forgetful functor U → V has a left adjoint F: V → U defined as follows: F(A) is the quotient of the free U-algebra (which can itself be constructed as the quotient of an absolutely free σ-algebra, e.g. the term algebra, over the congruence generated by the defining identities of U) in generators A over the congruence ~ generated by the atomic diagram of A (i.e., f(a₁,...,a_k) ~ a for each k-ary operation f ∈ τ and each a₁,...,a_k,a ∈ A such that a = f^A(a₁,...,a_k)). (Incidentally, the coverage of universal algebra on Wikipedia is extremely poor.)—Emil J. 12:57, 14 July 2010 (UTC)

Oh, and the answer to your first question is yes, your construction is in fact a special case of the general construction above (more precisely, the general construction would also put i(−a) + i(a) into the ideal, but that's easily seen to be redundant).—Emil J. 13:22, 14 July 2010 (UTC)

Thanks! I've never had any exposure to universal algebra so I don't exactly know what you mean. I had a look at the online pdf version "A course in universal algebra" page 73, and I think this is how: Say we want the free group over a set X (with signiture multiplication binary inverse unary and 1 constant). Take the term algebra T(X), which is like the free magma except it's got terms with inverse and 1. Next take the intersection E of all congruences on T(X) such that the quotient is actually a group (since T(X) is the "absolutely free algebra" you described, it has no relations on it, not even associativity), and intersection of congrugence is a congruence. The quotient under E is a group too, the free group on X.

I really have no idea what's going on lol. I'll take a proper look some other time.

Another question: this "uniform algorithm" is not the standard way to construct free groups. Is it because this construction is so much more difficult to use practically than the standard construction using equivalence class of words? The free abelian group can be constructed from the free group by using further identifications, but why do that when we can use all confinally 0 functions to the integers. So sure, this algorithm proves every forgeful functor on some type of algebras has a left adjoint, but it might as well just be a pure existence because of the insane complexity in its construction. Money is tight (talk) 05:19, 15 July 2010 (UTC)

The congruence E can also be described "from below": t E s iff there exist n ≥ 0 and terms t₀ = t, t₁, ..., t_n = s such that for each i < n, t_i = u_i(v_i) and t_i+1 = u_i(w_i) for some terms u_i, v_i, w_i, where either v_i ≈ w_i or w_i ≈ v_i is an instance of one of the defining identities of groups (for example, we may have v_i = 1 and w_i = r⁻¹·r for some term r). The standard group-specific construction is actually equivalent to this: another description of E is that t E s iff (the flattened forms of) t and s are equivalent as words. In this way it gives more information, as it provides an explicit description of representants of the equivalence classes. This is useful for various group-theoretic considerations, but I don't think it is any easier than the general construction if you just need to prove that the free group is a free group. Of course, in the case of abelian groups the explicit description of free objects is so simple that it beats any generic construction.—Emil J. 12:28, 15 July 2010 (UTC)

Polish notation

What's the point of Polish notation? Not only is it harder to read, it's more difficult to work with algebraicly. For example, compare the normal version ab+cd to its Polish notation equivalent, + * a b * c d. --138.110.206.101 (talk) 16:45, 14 July 2010 (UTC)

It removes ambiguity. How do you KNOW that ab+cd=(ab)+(cd) and not ab+cd=a(b+c)d? You are using an assumption that multiplication precedes addition. Polish notation never requires assumptions or parenthesis. -- kainaw™ 16:59, 14 July 2010 (UTC)

It isn't really an assumption is it, when everyone is using previously agreed-upon rules? There isn't really any ambiguity to ab+cd is there? mislih 20:07, 14 July 2010 (UTC)

It's very easy to evaluate without ever rereading any of the input (which is helpful if the input is large). You just note each operation as you come to it and then evaluate it with the next one or two values (depending on the operator). One or both of those might itself be the result of an operator, so you proceed recursively. In your example you would say "Add... multiply a and b..." (at which point you have the two things + and ab to remember; you need not remember a and b separately or that you multiplied them) "...multiply c and d" (at which point you obtain cd and then immediately the overall result). In practice, RPN is used for this purpose because then only numbers (and never operators) have to be temporarily remembered (and the stack that remembers them can often then be smaller). --Tardis (talk) 18:59, 14 July 2010 (UTC)

So Polish or reverse Polish would be better for determining the value of a given expression, but isn't it worse for algebraic manipulation? --138.110.206.101 (talk) 19:01, 14 July 2010 (UTC)

Not really. You are just assuming it would be because you aren't used to seeing it. If you only learned Polish notation, you would look at all the precedence rules and parenthesis used in inline notation and think it was a confusing mess. -- kainaw™ 19:04, 14 July 2010 (UTC)

How would you, for example, solve x 2 ^ x 1 + 2 ^ + x - 1 - 0 = without converting to regular notation? It's a lot harder. --138.110.206.101 (talk) 19:09, 14 July 2010 (UTC)

You don't include = in the notation. Keep it as two separate expressions, one being x 2 ^ x 1 + 2 ^ + x - 1 - and the other being just 0. Anything you do to one you do to the other. ie: To get rid of "1 -", you use "1 +" and get x 2 ^ x 1 + 2 ^ + x - and 0 1 +. Since there are no parenthesis or order of operations, we had no issues with deciding what we could and could not do. The next thing to work on is the trailing x -. But, it is apparent that you will hit a point at which you want to have one side simply 0 and the other side will contain a squared x. You will have to simplify. How do you simplify? You memorize patterns. You've probably memorized them as inline patterns, but you could have memorized them as Polish notation patterns just as well. -- kainaw™ 19:25, 14 July 2010 (UTC)

English is like the standard arithmetic expressions if you consider verbs as operators. Latin is reverse polish as in Jim the ball hit and Irish is polish with the equivalent of hit jim the ball. I gues sin them polish or reverse polish might appear a bit more natural. Dmcq (talk) 20:54, 14 July 2010 (UTC)

In Hebrew, all three are correct. And the subject doesn't even have to precede the object, giving a total of 6 variations! (Though I'm unsure of the "Hit the ball Jim" variant). -- Meni Rosenfeld (talk) 09:50, 15 July 2010 (UTC)

Verb Object Subject doesn't seem to be all that common, and Object Verb Subject even less so - it says Klingon uses that order because it is so strange sounding :) Dmcq (talk) 11:15, 15 July 2010 (UTC)

To avoid potential misunderstanding, all six variations are possible in Polish as well, though the default word order is SVO as in English. Polish notation has nothing to do with Polish language, it's named after members of the Polish logical school who invented it.—Emil J. 11:41, 15 July 2010 (UTC)

Rubik's cube group

How many conjugacy classes has the Rubik's cube group? --84.61.131.18 (talk) 20:05, 14 July 2010 (UTC)

How large is the largest order of any element in the Rubik's cube group? --84.61.131.18 (talk) 20:41, 14 July 2010 (UTC)

We have some info on the group in Rubik's cube group. The answer to your questions is not there, but some of the stuff may be useful. I suppose it shouldn't be hard to compute conjugacy classes and maximal orders using some computer algebra system.—Emil J. 15:38, 15 July 2010 (UTC)

Off the top of my head there are elements of order 8.3.5.7=840. A complete listing of conjugacy classes would be rather lengthy, I'm guessing there are at least a thousand. Conjugacy class of Wreath products of the symmetric groups are fairly easy to work with so a computer algebra system may not be necessary.--RDBury (talk) 16:50, 15 July 2010 (UTC)

According to the Magma computer algebra system there are 81120 conjugacy classes and the largest element order is 1260. The group has elements of the following orders: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 30, 33, 35, 36, 40, 42, 44, 45, 48, 55, 56, 60, 63, 66, 70, 72, 77, 80, 84, 90, 99, 105, 110, 112, 120, 126, 132, 140, 144, 154, 165, 168, 180, 198, 210, 231, 240, 252, 280, 315, 330, 336, 360, 420, 462, 495, 504, 630, 720, 840, 990, 1260. Most orders are made up of many classes of several sizes. Ignoring class sizes, and just sorting by order, one gets the following table:

Order table

Order	NrClasses	NrElems
1	1	1
2	74	170911549183
3	119	33894540622394
4	439	4346957030144256
5	5	133528172514624
6	7542	140621059298755526
7	3	153245517148800
8	316	294998638981939200
9	219	55333752398428896
10	136	34178553690432192
11	1	44590694400
12	20899	2330232827455554048
14	54	23298374383021440
15	190	14385471333209856
16	35	150731886270873600
18	4739	1371824848124089632
20	315	151839445189791744
21	66	39337151559333120
22	5	927085127270400
24	7590	3293932519796244480
28	114	97419760907673600
30	5155	1373347158867028224
33	23	15874019662233600
35	7	65526218912563200
36	8703	3768152294808760320
40	130	835897246403788800
42	1428	737199776831097600
44	4	100120377950208000
45	144	197329441659727104
48	739	911497647410380800
55	1	4854321355161600
56	47	671205306846412800
60	7371	4199961633799421952
63	57	264371433705308160
66	103	404051175250329600
70	37	210461722916290560
72	3289	1981453794190295040
77	2	187238109413376000
80	7	13349383726694400
84	1664	1697725818678067200
90	2177	1764876446897050368
99	27	104367909135974400
105	70	232824419423354880
110	1	4854321355161600
112	5	128726200221696000
120	1776	1947044011463147520
126	679	854783686296207360
132	36	637129677864960000
140	28	223125413717606400
144	330	714192029378150400
154	2	187238109413376000
165	12	213590139627110400
168	274	1050269239266508800
180	2015	2320395168471367680
198	55	759701292082790400
210	388	1053174509332070400
231	4	374476218826752000
240	84	407156203664179200
252	468	689877080447385600
280	6	68653973451571200
315	35	99309879652515840
330	12	213590139627110400
336	10	257452400443392000
360	460	571019888909352960
420	182	961155628321996800
462	4	374476218826752000
495	4	174755568785817600
504	70	238381852262400000
630	87	395380140162416640
720	10	120144453540249600
840	24	240288907080499200
990	4	174755568785817600
1260	8	51490480088678400

By hand calculations of the orders/sizes of all conjugacy classes are likely much too difficult due to the length, but David Joyner's Adventures in Group Theory (chapter 11, I believe) works out the elements of order 2 in quite some detail by hand. I believe Joyner also includes the by hand calculation of the maximum order, though it might be in one of his other books. JackSchmidt (talk) 17:25, 15 July 2010 (UTC)

How many sporadic subgroups has the Rubik's cube group? --84.61.131.18 (talk) 21:53, 15 July 2010 (UTC)

Which sporadic groups can be subgroups of the Rubik's cube group? --84.61.131.18 (talk) 16:24, 16 July 2010 (UTC)

M11 and M12 are subgroups of A12, which is a subgroup of the cube group. Every simple subgroup is isomorphic to a section of some simple composition factor, in other words, is contained as a section of A12 (or A8, but A8 ≤ A12, so this adds nothing new). The only sporadic simple groups contained in the cube group are M11 and M12. JackSchmidt (talk) 02:19, 17 July 2010 (UTC)

Are there any sporadic groups which have the Rubik's cube group as a subgroup? --84.61.131.18 (talk) 16:24, 16 July 2010 (UTC)

No. The only possibility not ruled out by Lagrange's theorem is the monster group, but the cube group is not contained in any of the monster's maximal subgroups, again by Lagrange's theorem. JackSchmidt (talk) 02:19, 17 July 2010 (UTC)

Help with a definite integral

I am trying to solve this integral,

$f(x)={\frac {1}{2\pi }}\int _{0}^{2\pi }d\theta \,e^{ix\theta }\,\theta \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,x\in \mathbb {Z} \!$

which, I believe, has the solution

$f(x)={\begin{cases}\pi ,&{\mbox{if }}x=0\\{\frac {1}{ix}},&{\mbox{if }}x\neq 0\end{cases}}\!$ .

However I am having a hard time getting this answer. Using integration by parts, I get

${\begin{aligned}f(x)&={\frac {\theta e^{ix\theta }}{2\pi \,i\,x}}{\Bigg |}_{\theta =0}^{\theta =2\pi }-{\frac {1}{2\pi }}\int _{0}^{2\pi }d\theta \,{\frac {e^{ix\theta }}{ix}}\\&={\frac {1}{ix}}\left(1-{\frac {1}{2\pi }}\int _{0}^{2\pi }d\theta \,e^{ix\theta }\right)\\&={\frac {1}{ix}}\left(1-\delta _{x,0}\right)\end{aligned}}$ .

This gives the correct answer when x is any integer other than zero, but is infinite when $x=0$. I could get the correct result for $x=0$ just by plugging that in at the beginning. Is there something wrong with my derivation above? Is there a more elegant way to arrive at the correct answer? Thanks mislih 20:03, 14 July 2010 (UTC)

$\forall x\;{\frac {de^{ix\theta }}{d\theta }}=ixe^{ix\theta }$, but $\int e^{ix\theta }\,{\text{d}}\theta \not \equiv {\frac {e^{ix\theta }}{ix}}+C$ because of the $x=0$ possibility, in which case you have $\int {\text{d}}\theta =\theta +C$, of course. If you write $\int e^{ix\theta }\,{\text{d}}\theta ={\frac {e^{ix\theta }-1}{ix}}+C$ (which is just using a different C), then the limit works out properly, so you might try that as an intuitive approach, but it's still technically undefined. So when you do integration by parts you have to split off the $x=0$ case just as if you were dividing by x on both sides of an equation. Then of course you're allowed to assume $x\neq 0$ later in the other branch, so you would avoid bringing in the Kronecker delta. --Tardis (talk) 23:36, 14 July 2010 (UTC)

Thanks for clearing that up. mislih 21:14, 15 July 2010 (UTC)

Denesting Radicals

Hello. Why does ${\sqrt {a^{2}-b^{2}c}}$ have to be an integer if some nested radical, ${\sqrt {a+b{\sqrt {c}}\ }}$, can be denested into a sum of surds, ${\sqrt {d}}+{\sqrt {e}}$? If I rewrite ${\sqrt {a^{2}-b^{2}c}}$ in terms of $d$ and $e$, I get $d-e$. Thanks in advance. --Mayfare (talk) 22:17, 14 July 2010 (UTC)

If

${\sqrt {a+b{\sqrt {c}}}}={\sqrt {d}}+{\sqrt {e}},\,$

then squaring both sides yields

$a+b{\sqrt {c}}=d+e+2{\sqrt {de}}.\,$

Now if a, b, d, e are rational and √c is not, then we have

$a=d+e{\text{ and }}b{\sqrt {c}}=2{\sqrt {de}}.\,$

Therefore

$a-b{\sqrt {c}}=d+e-2{\sqrt {de}}=({\sqrt {d}}-{\sqrt {e}})^{2}\,$

and if everything in site is nonnegative, we can then say

${\sqrt {a-b{\sqrt {c}}}}={\sqrt {d}}-{\sqrt {e}}.\,$

Finally we have these two products:

${\begin{aligned}{\sqrt {a+b{\sqrt {c}}}}{\sqrt {a-b{\sqrt {c}}}}={\sqrt {a^{2}-b^{2}c}}\\[12pt]({\sqrt {d}}+{\sqrt {e}})({\sqrt {d}}-{\sqrt {e}})=d-e\end{aligned}}$

Therefore

${\sqrt {a^{2}-b^{2}c}}=d-e.\,$

So if d − e is an integer then we're done. Michael Hardy (talk) 23:50, 14 July 2010 (UTC)

July 15

Testing the bias on a coin

If a coin is flipped a number of times, and the results are n heads and m tails, what is the probability that the next flip will be heads?115.178.29.142 (talk) 03:22, 15 July 2010 (UTC)

There's no way to know. But the maximum likelihood estimate is n/(n+m). 67.119.12.184 (talk) 05:11, 15 July 2010 (UTC)

Assuming of course that you have no other information regarding the fairness of the coin, the probability that the next flip will be heads is P=(n+1)/(n+m+2). This formula also applies when n=m=0, unlike the approximate estimate P≈n/(n+m). Bo Jacoby (talk) 09:33, 15 July 2010 (UTC).

If you were pretty certain there should be little or no bias either way then (n+10)/(n+m+20) might be better. You can see it depends on your prior probability. Dmcq (talk) 09:48, 15 July 2010 (UTC)

Dmcq's result assumes that the coin has been flipped n+m+18 times given n+9 heads and m+9 tails. The prior probability can not be chosen freely. No information about the fairness of the coin means that the prior probability of heads, (H|), is 1/2, and the prior probability of tails, (T|), is also 1/2. The wanted conditional probability of heads, giving the facts, F, (that there were already n heads and m tails), is computed by Bayes' formula together with the formula for the hypergeometric distribution

$(H|F)={\frac {(F|H)(H|)}{(F|H)(H|)+(F|T)(T|)}}$ $={\frac {{\frac {{\binom {n+1}{n}}{\binom {m}{m}}}{\binom {n+m+1}{n+m}}}{\frac {1}{2}}}{{\frac {{\binom {n+1}{n}}{\binom {m}{m}}}{\binom {n+m+1}{n+m}}}{\frac {1}{2}}+{\frac {{\binom {n}{n}}{\binom {m+1}{m}}}{\binom {n+m+1}{n+m}}}{\frac {1}{2}}}}$ $={\frac {n+1}{n+m+2}}$

Bo Jacoby (talk) 11:11, 15 July 2010 (UTC).

That is a pretty good prior if you'd never come across a coin before but most people recognize that coins are usually pretty unbiased. Now supposed we tossed the coin once and it came up heads. That would give the chance of the coming coming up heads as 2/3. That means if I bet 100 quatloos on tails and the other person 200 on heads then we should break even over a number of throws - in three goes on average I'd lose twice and they'd lose once. Now would you really be willing to bid against me if I put 150 quatloos on tails to your 200 on heads? Dmcq (talk) 12:00, 15 July 2010 (UTC)

Indeed. Bo is assuming we have no information about the fairness of the coin, but that's not the case. We know it's a coin, which means it is very likely to be very close to fair. --Tango (talk) 12:42, 15 July 2010 (UTC)

If you already know that the coin is fair, then don't test it, just tell the OP that the probability is 1/2 because you know that it is a fair coin. But the OP is not sure, and that's why he tests it. If you have noticed (or have been told) that coins are usually pretty unbiased, it must be because coins have been flipped before, and then the values of n and m are high. It doesn't need to have been the same coin every time. Now the OP clearly assumes that "a coin is flipped a number of times, and the results are n heads and m tails", so we are justified in assuming that n and m are the correct counts. Or perhaps the OP is using the word coin figuratively meaning some device providing random values called heads and tails. In any case (n+1)/(n+m+2) is the correct formula for the probability that the next flip show head. Bo Jacoby (talk) 14:46, 15 July 2010 (UTC).

Previous coin tosses aren't the only kind of evidence you could have. You could have the word of the person that gave it to you that is isn't a fixed coin, for example. Or simply the knowledge that most coins in existence are fair. Knowing that a different coin was tossed and got certain results isn't the same as knowing that the coin in your hand was tossed and get certain results. --Tango (talk) 14:53, 15 July 2010 (UTC)

I feel this is rapidly heading towards at least one side of at least one sheep seems black territory. :) Dmcq (talk) 15:33, 15 July 2010 (UTC)

That's nonsense. There is no dichotomy between "know for certain the coin is fair" and "have no idea what a coin is, and hence use a maximum-entropy prior". If you know that 99% of coins are fair, then when given a random coin (which you have no reason to suspect was chosen based on its fairness or lack thereof), you'll say there's 99% that this coin is fair. If you then toss it 3 times and it's all heads, you'll still have a high credence to it being fair (the exact amount depends on the continuous prior distribution for the bias of biased coins), and thus your credence for the next toss being heads will be close to 50%. As more evidence is collected where this coin lands heads more then it should, your posterior will shift towards the coin having the bias implied by the Heads:Tails ratio.

Even if past coin tosses is the only knowledge of coins you have (as opposed to, say, proficiency in metallurgy and rigid body mechanics), you can't compress this knowledge to 2 numbers m and n. If you sample 2 coins and toss each many times, then "one coin always lands heads, one always tails" is very different, wrt your conclusions about the bias of coins, from "each coin lands a roughly equal number of heads or tails". Your probability distribution for the bias of coins can take any form depending on what observations you have made. -- Meni Rosenfeld (talk) 15:51, 15 July 2010 (UTC)

The arcsin for numbers >1

How do you find the arcsin for numbers greater than 1 (which I believe is a complex value) —Preceding unsigned comment added by 115.178.29.142 (talk) 04:44, 15 July 2010 (UTC)

By the way, I know the real part is pi/2 . but what is the imaginary part?115.178.29.142 (talk) 05:15, 15 July 2010 (UTC)

Sin(z) is defined in terms of the exponential function exp(z) as sin(z)=(exp(iz)-exp(-iz))/2i, and exp(z) is in turn defined in terms of a power series (see article Exponential_function). So when you want to find arcsin of x, you solve for z in x=(exp(iz)-exp(-iz))/2i Money is tight (talk) 05:24, 15 July 2010 (UTC)

Which will give you the expression in Inverse trigonometric functions#Logarithmic forms.—Emil J. 11:51, 15 July 2010 (UTC)

$\arcsin(x)={\frac {\pi }{2}}\pm i\,\operatorname {arccosh} (x){\text{ for }}x>1$ Gandalf61 (talk) 13:00, 15 July 2010 (UTC)

Comparing two averages

If you are comparing two samples from completely separate populations, you can use a two sample t-test. Is there anyway to compare a population's mean to a subset's mean? For instance, you look at 2000 students with an average weight of 150 pounds. Then you choose 50 of those students and get their average weight. Is there anyway to check that their average weight is not significantly different from the population's average of 150 pounds? Like: an average of 149 might not be significant, but an average of 220 is significant. Remember, you don't have the average and standard deviation of the whole population without those students.

Basically you're trying to show that the group of students you chose as a whole is not significantly heavier than the other students at the school. 160.10.98.106 (talk) 15:21, 15 July 2010 (UTC)

The whole population without those students is (2000×150−50×220) / (2000−50) = 148.2 pounds per student. Your problem is treated by analysis of variance. Bo Jacoby (talk) 09:46, 17 July 2010 (UTC).

It depends how you know the population's average. If you've measured the entire population then there's no uncertainty in its mean, so to test the null hypothesis that the weights of the 50 students could be a random sample from the population then you can use a one-sample t-test with the population mean as the specified value μ₀, and you'd gain precision by using the population standard deviation if you know it rather than the sample standard deviation. If on the other hand you found the population mean from a random sample of the population then you have a two sample t-test provided none of that sample were also members of your subset of 50 students. If they were, it's going to get a bit trickier—simplest to exclude those students from one group or the other, e.g. from the larger group. Qwfp (talk) 11:14, 17 July 2010 (UTC)

Theoretical computer science

Suppose F is a boolean function with n variables, and I want to determine whether there exists an assignment of true or false to those variables such that F is true. With a nondeterministic Turing machine, this can clearly be solved in time n, so this is in NP. However, a deterministic Turing machine requires time 2ⁿ to check all 2ⁿ possible assignments of variables, so this is not in P. Therefore, P!=NP. What's the problem with this proof? --138.110.206.101 (talk) 16:25, 15 July 2010 (UTC)

You're assuming there's no better method for a deterministic Turing machine to use than straightforward brute force search. You're also taking "polynomial-time" to mean polynomial in the number of variables, while I think the only sensible meaning for it here is polynomial in the length of the proposition. Algebraist 16:31, 15 July 2010 (UTC)

[ec] The problem is that you have assumed that brute-forcing all possibilities is the most efficient algorithm to solve this. To prove that a problem is not in P you have to show that each and every algorithm that solves it is superpolynomial, not that one particular algorithm is superpolynomial. -- Meni Rosenfeld (talk) 16:33, 15 July 2010 (UTC)

Are there any polynomial-time deterministic algorithms for determining whether a boolean equation has a solution? --138.110.206.101 (talk) 16:40, 15 July 2010 (UTC)

We don't know. That's exactly what the P =? NP problem asks for. However, there are SAT solvers which do better than the brute force assignment search (they achieve time complexity $2^{\epsilon n}$ for some $0<\epsilon <1$), which should at least persuade you that the problem is nontrivial.—Emil J. 16:43, 15 July 2010 (UTC)

This is a very common mistake for those beginning to study P/NP. You are not using a standard nondeterministic Turing machine. You are using an infinite-length nondeterministic Turing machine. What if the maximum number of values that your machine can store is m. You have n values to check. If m>n, no problem. If m<n, you have a problem. You cannot do this in simply polynomial time. A basic rule: If your "polynomial" time solution begins with "get a tape long enough to store all the values" or "get enough memory to store all the variables" or "get a rope long enough to stretch around all the posts", it is not a polynomial solution. -- kainaw™ 17:24, 15 July 2010 (UTC)

What on earth are you talking about? The standard Turing machine, as used in the definition of NP, has (at least potentially) an infinite tape. It can get away with a polynomially bounded tape as it is a poly-time machine here, but it certainly cannot be bounded by a constant. That would be equivalent to a nondeterministic finite automaton, which can only recognize regular languages, a tiny subset of P (let alone NP). The OP's NP algorithm is correct, and it is in fact a textbook example (SAT being among the most popular NP-complete problems).—Emil J. 18:04, 15 July 2010 (UTC)

I was attempting to use language to make it understood to the questioner. When you say "infinite tape" and you know what you are talking about, those just learning about P/NP hear "the tape starts out with an infinite amount of data already written on it and all I have to do is read it quickly from one end to the other". I have argued for many years that the language used in describing P/NP leads to more confusion than anything else. -- kainaw™ 18:07, 15 July 2010 (UTC)

Whereas telling the OP that he or she made a mistake when they actually did not (in this part of the argument, that is) is supposed to reduce confusion, right?—Emil J. 18:15, 15 July 2010 (UTC)

I figured he was confused enough already because he most likely intended to describe a 3-SAT but didn't. A 2-SAT (or 1-SAT, which is what he described) has a simple solution. 3-SAT is where the trouble starts. Further, it appeared that he was going towards the standard "I can't believe I solved the 3-SAT problem" solution of: 1. Get enough memory to store every 3-variable set in the 3-SAT. 2. Calculate the possibility of each of those being true. 3. Solve those solutions as a 1-SAT. Step 1 is where it immediately gets thrown out of P. -- kainaw™ 21:54, 15 July 2010 (UTC)

But the OP was not trying to prove that SAT (or 3-SAT, though I don't see anything in their post which would indicate that they intend such a restriction) is in P. On the contrary, they were trying to prove that it is not in P (whereas it is in NP, that's what the part about nondeterministic TM does).—Emil J. 10:27, 16 July 2010 (UTC)

Implicit function theoem

My text book writes "...note that the cain rule applied to F(x,g(x)) = 0 gives

$\mathbf {D_{x}} F(\mathbf {x} ,g(\mathbf {x} ))=[{\frac {\partial F}{\partial x}}(\mathbf {x} ,g(\mathbf {x} ))][\mathbf {D} g(\mathbf {x} )]$

which is equivalent to

${\frac {\partial g}{\partial x_{i}}}=-{\frac {\frac {\partial F}{\partial x_{i}}}{\frac {\partial F}{\partial z}}}.$

I was wondering the first equation can be arrived at. Oh, and F:ℝⁿ⁺¹ → ℝ. PS Do you have to bold the D everytime you write the derivative matrix? Because it's hard to bold on paper...74.15.137.192 (talk) 19:31, 15 July 2010 (UTC)

Riddle (of my own)

I apologize if you think it's to easy. Additionaly, user:EmilJ is hereby asked not to respond, unless no response has been given by Sunday morning. If even EmilJ won't respond by Monday morning, then I'll provide the solution. The riddle goes as follows:

By "arithmetical" mapping - we shall hereby mean: a mapping expressible in the arithmetical language: (+,×,0,1), i.e. a function for which there exists a formula $\varphi (x,y)$ comprising of logical symbols as well as the symbols: +,×,0,1, so that for every a in the domain there is a unique b in the codomain such that $\varphi (a,b)$.

Now, one has to find a field F (+,× being its corresponding addition and multiplication, 0,1 being its units respectively), with respect to which the relation: " there is an arithmetical mapping from S to T " - is not transitive, i.e. one has to find three sub-sets of F, let's call them A,B,C, such that there's an arithmetical mapping from A to B, and there's an arithmetical mapping from B to C, but there's no arithmetical mapping from A to C.

HOOTmag (talk) 21:20, 15 July 2010 (UTC)

I'll bow out too then with EmilJ and ponder deeply on "How much wood could a woodchuck chuck if a woodchuck could chuck wood?" Dmcq (talk) 23:33, 15 July 2010 (UTC)

If you think my riddle is too easy, you may Email me. Thanks.HOOTmag (talk) 23:48, 15 July 2010 (UTC)

Well, I was supposed not to respond to this question, but let me just say that I don't understand the description. What do you mean by "expressible in the arithmetical language"? I would read it as "definable by a first-order formula in the structure (F,+,×,0,1)", but then the riddle would have no solution, because the composition $g\circ f$ of two definable surjections is a surjection definable by $\exists u\,(f(x)=u\land g(u)=y)$. You thus may want to clarify the statement of the problem.—Emil J. 10:39, 16 July 2010 (UTC)

Yes: by "expressible in the arithmetical language" I really mean just as you've interpreted it.

No: although there are surjections f and g expressible in the arithmetical language, the surjection $g\circ f$ may be not expressible in the arithmetical language. This is my riddle, and it does have a solution.

To make things even more provocative, I've replaced "surjection" by "mapping", as you can see now in the current version of my riddle.

Good luck. HOOTmag (talk) 14:49, 16 July 2010 (UTC)

You contradict yourself. What I wrote above is a (standard) proof that the composition of two definable functions is definable, so you obviously cannot mean it as I've interpreted it. You have to explain your terminology, otherwise your "riddle" is just gobbledygook.—Emil J. 15:07, 16 July 2010 (UTC)

No, I don't.

Yes, what you wrote above is really a (standard) proof that the composition of two [arithmetically] definable functions is [arithmetically] definable.

However, the composition of two [arithmetically] definable functions is unnecessarilly an [arithmetically] definable function.

No, my riddle is not gobbledygook.

Good luck. HOOTmag (talk) 15:27, 16 July 2010 (UTC)

Then your terminology must be even more puzzling than I expected. The composition of two functions is always a function, by definition. What you write makes no sense.—Emil J. 15:31, 16 July 2010 (UTC)

No, my terminology is just like yours.

Yes, The composition of two functions is always a function, and the composition of two [arithmetically] definable functions is [arithmetically] definable.

However, the composition of two [arithmetically] definable functions is unnecessarilly an [arithmetically] definable function.

No, what I wrote does make sense.

Good luck. HOOTmag (talk) 15:38, 16 July 2010 (UTC)

Let me try it in a different way. Here's the standard terminology:

• a function f: A → B is, depending on whom you ask, either a relation R ⊆ A × B such that for every a in A there exists a unique b in B such that a R b, or the triple (R, A, B) where R is as above,
• the composition of functions f: A → B and g: B → C is the function $g\circ f\colon A\to C$ such that $(g\circ f)(a)=g(f(a))$ (sometimes f and g are written in the opposite order),
• a function f: A → B, where A and B are subsets of the domain of a structure M, is definable in M, if there exists a first-order formula $\varphi (x,y)$ in the language of M such that for every a and b in M, $M\vDash \varphi (a,b)$ iff a is in A and f(a) = b.

Tell us which of these your terminology disagrees with. In particular, you seem to make a distinction between a definable function and a function which is definable, but these two are synonyms in the standard terminology.—Emil J. 15:49, 16 July 2010 (UTC)

Your third terminology of "definability in M" has nothing to do with my riddle.

To put things clearer: A,B being sub-sets of the field F, the expression "arithmetical mapping" f: A → B should be interpreted here as follows: there exists a formula $\varphi (x,y)$ comprising of logical symbols as well as the symbols: +,×,0,1 (which are interpreted as the addition the multiplication and the units of both operations of F respectively), so that for every a in A and for every b in B, $\varphi (a,b)$ iff f(a) = b. I'll be back on sunday morning. HOOTmag (talk) 16:15, 16 July 2010 (UTC)

Aha, so you don't want the function itself to be arithmetically definable, but that there exists an arithmetically definable relation whose intersection with A × B is (the graph of) the function. Then the problem becomes sensible.—Emil J. 16:29, 16 July 2010 (UTC)

so others don't have to read through all this, you should move this part of the conersatino to the talk page (to preserve it) and just change the original phrasing so it is clear as finally realized by EmilJ. 92.229.14.255 (talk) 21:26, 16 July 2010 (UTC)

Let F = GF(4) = {0, 1, a, a + 1}, and put A = {0}, B = {a}, C = {a, a + 1}, f(0) = a, g(a) = a. Then f: A → B and g: B → C are arithmetical mappings in HOOTmag's sense (f by the true formula, g by x = y), but no mapping from A to C is arithmetical, because it is not invariant under the Frobenius automorphism (which swaps a and a + 1). Pretty much the same thing can be done with any field which carries any nonidentical automorphism.—Emil J. 12:00, 18 July 2010 (UTC)

Excellent. Now try to solve the same riddle but with my original "surjection" (and also with "bijection") instead of "mapping". (By "arithmetical surjection", I mean: an "arithmetical mapping" - which is also a surjection. By "arithmetical bijection" from A to B, I mean: an "arithmetical mapping" from A to B - which is also an "arithmetical mapping" from B to A). HOOTmag (talk 12:00, 18 July 2010 (UTC)}}

I'm also not sure in what way f is arithmetical. As clever as using an ifexpr statement is, it doesn't really work since it's visible when editing... --Tango (talk) 20:26, 17 July 2010 (UTC)}}

It's arithmetical since the formula uses no symbols other than the logical ones and the arithmetical ones. HOOTmag (talk 12:00, 18 July 2010 (UTC)}}

But how can you write it without using the symbol a? I thought we were only allowed addition, multiplication and identities. --Tango (talk) 22:53, 17 July 2010 (UTC)}}

f is expressed (e.g.) by the formula: "0=0" (or by any true formula, as EmilJ indicated). You should remember that B= {a}, so the only object in B satisfying the formula "0=0" is a. If you still have any doubt, look again at the very definition of "arithmetical mapping", above. HOOTmag (talk 12:00, 18 July 2010 (UTC)}}

I've boldly removed the time delays because they were getting ridiculous and Emil J.'s answer wasn't correct anyway (not being a surjection). Ah, I see. That kind of trick will only work if A and B are singleton sets, though, which will make it difficult to use it with surjections (if there is a surjection from B to C, and B is a singleton set, then C must be too, which means any mapping from A to C is trivially arithmetical by the same trick). --Tango (talk) 23:45, 17 July 2010 (UTC)

I've boldly put back the time delays, because EmilJ who decided to use them didn't allow you to remove them. and Emil J.'s answer was correct (because the current version of my riddle is not about surjections but rather about mappings). If you want to remove the time delays from your posts, you can do that, but please don't touch Emilj's posts and my posts :). My riddle has a solution even for surjections. For more details, read my response to EmilJ's last response, and wait for EmilJ's response, or wait untill Monday morning when I give the full answer if EmilJ hasn't responded by then. HOOTmag (talk 12:00, 18 July 2010 (UTC)

I've removed them again. Please do not put them back without a consensus on the talk page. Hiding answers to questions goes against the intentions of the reference desk, which is to answer people's questions. This isn't a competition page. --Tango (talk) 00:42, 18 July 2010 (UTC)

July 16

Fixed Point

Studying some old analysis exams, I came across the following problem and it has resisted all efforts by everyone I know (including myself) so I appeal here. Here is the problem verbatim.

"The continuous map $F(x,y)=(f_{1}(x,y),f_{2}(x,y))$ from $\mathbb {R} ^{2}$ to $\mathbb {R} ^{2}$ satisfies

a) $|f_{i}(x_{2},y_{2})-f_{i}(x_{1},y_{1})|<{\frac {1}{2}}(|x_{2}-x_{1}|+|y_{2}-y_{1}|)$ for $i=1,2$

b) F maps the set $\Omega =(0,1)\times (0,1)$ into itself.

Show that F has a unique fixed point in $\mathbb {R} ^{2}$".

Ok, several issues with this question. The only fixed point theorem we are supposed to know is the contraction mapping theorem so I am guessing that the only way to do this problem is to show that F is a strict contraction (with the contraction constant being strictly less than one) on the unit square. Condition a) doesn't give us a contraction because the two metrics being used on the opposite sides of the inequality are different (left is using the 2-norm and the right is using the 1-norm). I have shown that F continuous implies that it maps the closed unit square to itself but I can't get a strict contraction for any of the metrics I can think of. The contraction constant always comes out to one which is useless. In fact I proved that $d_{p}(F(y),F(x))<d_{p}(y,x)$ for any of the p-metrics (include the max-metric). I think that as long as I find one metric (for which R^2 is complete) for which F is a contraction, its good because the actual fixed point doesn't depend on the metric. Any help?-Looking for Wisdom and Insight! (talk) 02:46, 16 July 2010 (UTC)

left is using the 2-norm. Really? There is no square or square root involved. Condition a) is the two inequalities

$|f_{1}(x_{2},y_{2})-f_{1}(x_{1},y_{1})|<{\frac {1}{2}}(|x_{2}-x_{1}|+|y_{2}-y_{1}|)$

$|f_{2}(x_{2},y_{2})-f_{2}(x_{1},y_{1})|<{\frac {1}{2}}(|x_{2}-x_{1}|+|y_{2}-y_{1}|)$

when added together you get

$|f_{1}(x_{2},y_{2})-f_{1}(x_{1},y_{1})|+|f_{2}(x_{2},y_{2})-f_{2}(x_{1},y_{1})|<|x_{2}-x_{1}|+|y_{2}-y_{1}|\,$

or

${\frac {|f_{1}(x_{2},y_{2})-f_{1}(x_{1},y_{1})|+|f_{2}(x_{2},y_{2})-f_{2}(x_{1},y_{1})|}{|x_{2}-x_{1}|+|y_{2}-y_{1}|}}<1$

which looks like a contraction. PS. The notation in the problem is confusing. Indexes 1 and 2 refer sometimes to different points and sometimes to different coordinates of the same point. $f(x,y)=(f_{x}(x,y),f_{y}(x,y))$ is better. Bo Jacoby (talk) 07:41, 16 July 2010 (UTC).

Yes true but this is still $||F(y)-F(x)||_{1}<||y-x||_{1}$ and the constant of contraction is still one (which I already knew). The thing is that it needs to be a number strictly less than one. Contraction constant being one doesn't say anything. There may be a fixed point (like the identity map which has many fixed points) or there may be no fixed points. The constant needs to be less than one for the existence and uniqueness of a fixed point. I already know that any of the standard p-norms (include the infinity norm) give us one. I even tried more exotic things like $d(x,y)={\frac {d_{2}(x,y)}{1+d_{2}(x,y)}}$ and I still get the contraction constant as 1. Is there a metric which would work? How would we go about finding it? Or are we going about this completely the wrong way and the approach is completely different? I was also thinking, this problem of having the contraction constant c=1 happens because of the diagonal y=x so maybe if I could take the diagonal, take a little band around it (width=epsilon) and remove it from the closed unit square. Then I would have a c<1 and then maybe take a limit as epsilon goes to zero or something. Would that work?-Looking for Wisdom and Insight! (talk) 07:58, 16 July 2010 (UTC)

(Edit Conflict) You are also right about the notation being confusing. Its basically, pick two points $x=(x_{1},y_{1}),y=(x_{2},y_{2})$ in $\mathbb {R} ^{2}$. And F has the two scalar components f1 and f2. I agree this is not the best choice but that's what it said.-Looking for Wisdom and Insight! (talk) 07:58, 16 July 2010 (UTC)

A square with side a is mapped into a square with side a/2? No, sorry. Bo Jacoby (talk) 08:07, 16 July 2010 (UTC).

There's a wee bit of a problem in that if you're talking about the open square there isn't any fixed point - it could all tend to one corner. If you're talking about a closed square then the contraction factor doesn't have to be less than 1, it just needs to always be less than 1 for any pair of points you look at but could have a limit of 1. A map like that sending everything to a diagonal line that then goes towards a corner is

$f_{1}(x,y)=f_{2}(x,y)=(x+y)/(1+x+y)$

The important thing for a closed square is that it is compact. Dmcq (talk) 09:59, 16 July 2010 (UTC)

Stupid me! Just substitute zeroes in all coordinates and obtain the relation 0<0 which is false. No mapping satisfy the required conditions, and so every mapping that does satisfy the condition has a fixed point. Bo Jacoby (talk) 13:30, 16 July 2010 (UTC).

Ah but is it a unique fixed point :) You're quite right, the theorem for the compact case is where the inequality holds whenever the two points are different. Dmcq (talk) 13:39, 16 July 2010 (UTC)

I don't see the need for any separate "compact case". In the original case, f: R² → R² maps Ω to itself and is continuous, therefore it also maps ${\overline {\Omega }}$ to itself. Thus by your argument it has a fixed point in ${\overline {\Omega }}$ and a fortiori in R². Uniqueness is straightforward.—Emil J. 14:05, 16 July 2010 (UTC)

Oh I see what you're talking about, it is a fixed point of the map of the whole plane, I was just thinking of the open square. Um, yes I should have read it better, thanks. Dmcq (talk) 15:51, 16 July 2010 (UTC)

Wait, maybe its just me being stupid but what's the verdict here? How do we know that there is a fixed point and how do we know that its unique? Maybe its irrelevant but can we say anything about where (or what) the fixed point would be? Is it in omega? Is it in omega closure (like the origin)? The only thing I can understand from this is that if I pick two points in omega, then their images will be closer in L1 norm. But we don't even know specifically how close.-Looking for Wisdom and Insight! (talk) 23:25, 16 July 2010 (UTC)

Yep there's always a unique fixed point. I was using the Brouwer fixed point theorem rather than the Banach fixed point theorem on the closure of the unit square. As EmilJ pointed out the closure of an open area will always transform to within the closure of the transformed open area. Plus you can't have two fixed points if the distance after the mapping is always smaller. Dmcq (talk) 00:02, 17 July 2010 (UTC)

The theorem that a distance-reducing map on a compact metric space has a fixed point is much easier than Brouwer (just consider a point x minimizing the continuous function x↦d(x,f(x))). Algebraist 09:11, 17 July 2010 (UTC)

Yes that's better, compact sets map to compact sets, or even invoke the extreme value theorem from analysis but topology is easier here. I was trying to work in the poster's contraction mapping theorem and I didn't manage anyway. Looking at Banach fixed point theorem I see it mentions this bit about a compact set and not needing the contraction to have a definite factor less than 1. I don't see how to fit in the poster's bit about having just done the contraction mapping theorem,it sounds like it should be relevant but just doesn't seem to be, or is the bit about compact sets a part of the contraction mapping theorem? Dmcq (talk) 10:35, 17 July 2010 (UTC)

No, the verdict is that the problem is a joke. Condition a) is a contradiction because for point 1 equal to point 2 condition a) says that 0<0, which is simply not the case. You do not need any fixed point theorems at all. There exist no mapping satisfying condition a). The set of mappings satisfying condition a) is the empty set = { } = Ø. What can be said about the elements of the empty set? The answer is that anything can be said about the elements of the empty set, because the empty set has got no elements. So all the mappings satisfying condition a), ( there are none ), have got unique fix points, Q.E.D. Bo Jacoby (talk) 04:01, 17 July 2010 (UTC).

That's true but I'm reading it as meaning the inequality refers to any two distinct points as I said above. It's not a joke, its just a missing condition. Dmcq (talk) 09:06, 17 July 2010 (UTC)

The original problem may be modified in several ways to make more sense. The sign '<' may be replaced by '≤' to avoid the contradiction 0<0. Then the identity map, having plenty of fixed points, is a possibility. Then the constants 1/2 could be lowered a little to, say, 499/1000. Then the Banach theorem applies and there is a unique fixed point. But the problem as written assumes a contradictory condition. Bo Jacoby (talk) 11:20, 17 July 2010 (UTC).

If a person looks around a house and says "I looked and there was nobody there" we don't go around saying "Ha ha you're trying to trick us, you were there so it couldn't have been empty". Let's just assume a bit of good faith and a straightforward problem and not jump at things like that. Dmcq (talk) 12:58, 17 July 2010 (UTC)

An old analysis exam need no good faith for its interpretation. The purpose is to check that the student can read and think. Bo Jacoby (talk) 18:50, 17 July 2010 (UTC).

Linear independence over complex numbers of modular forms of different weights

Hello, I am trying to show that n nonzero modular forms of n distinct integer weights are linearly independent over the complex numbers. I thought induction might work and the base case is easy as it is just the case n = 1. But, I can also prove it for n = 2 directly:

Assume $f_{1}(z),f_{2}(z)$ are nonzero modular forms of distinct integer weights $k_{1},k_{2}$. Assume also that there exist $a_{1},a_{2}\in \mathbb {C}$, not both zero such that $a_{1}f_{1}+a_{2}f_{2}=0$. WLOG, assume $a_{1}\neq 0$. Then, I can solve for $f_{1}(z)=-{\frac {a_{2}}{a_{1}}}f_{2}(z)$. Since these are both modular forms, they are invariant under the stroke operator for any $\gamma ={\begin{bmatrix}a&b\\c&d\end{bmatrix}}\in SL_{2}(\mathbb {Z} )$ for their respective weights. Thus,

$(cz+d)^{-k_{1}}f_{1}(\gamma z)=-{\frac {a_{2}}{a_{1}}}(cz+d)^{-k_{2}}f_{2}(\gamma z)$

which gives

$f_{1}(\gamma z)=-{\frac {a_{2}}{a_{1}}}(cz+d)^{k_{1}-k_{2}}f_{2}(\gamma z)$

which gives

$-{\frac {a_{2}}{a_{1}}}f_{2}(\gamma z)=-{\frac {a_{2}}{a_{1}}}(cz+d)^{k_{1}-k_{2}}f_{2}(\gamma z)$

so that

$(cz+d)^{k_{1}-k_{2}}=1$.

Now, since $\gamma \in SL_{2}(\mathbb {Z} )$ can be anything and this exact equation must hold for all such matrices, the only conclusion is $k_{1}=k_{2}$, a contradiction. Thus, they are linearly independent.

I tried extending this same argument to the general case of n but I am not sure where to go. Any suggestions? Thanks StatisticsMan (talk) 13:26, 16 July 2010 (UTC)

Just to be clear, when I tried it with n, hoping to use the induction hypothesis that n-1 are linearly independent, I got

$\sum _{i=2}^{n}a_{i}f_{i}(\gamma z)=\sum _{i=2}^{n}a_{i}(cz+d)^{k_{1}-k_{i}}f_{i}(\gamma z)$

and this does not seem to have any great way to cancel. I put everything on one side to get

$\sum _{i=2}^{n}a_{i}f_{i}(\gamma z)[1-(cz+d)^{k_{1}-k_{i}}]=0$

which is almost a linear combination of n-1 of them, well it is, but it's in complex variables instead of complex numbers. StatisticsMan (talk) 13:57, 16 July 2010 (UTC)

Millennium Prize Problems

Would you get the prize money for disproving one of the conjectures or proving it independent? --138.110.206.101 (talk) 16:12, 16 July 2010 (UTC)

The rules say

In the case of the P versus NP problem and the Navier-Stokes problem, the SAB will consider the award of the Millennium Prize for deciding the question in either direction. In the case of the other problems if a counterexample is proposed, the SAB will consider this counterexample after publication and the same two-year waiting period as for a proposed solution will apply. If, in the opinion of the SAB, the counterexample effectively resolves the problem then the SAB may recommend the award of the Prize. If the counterexample shows that the original problem survives after reformulation or elimination of some special case, then the SAB may recommend that a small prize be awarded to the author. The money for this prize will not be taken from the Millennium Prize Problem fund, but from other CMI funds.

Independence proofs aren't mentioned as far as I can see. Algebraist 16:16, 16 July 2010 (UTC)

July 17

Half pennies on credit cards

Can half pennies be saved on British credit cards? --84.61.131.18 (talk) 13:54, 17 July 2010 (UTC)

Half pennies are no longer legal tender. The miscellaneous reference desk is probably better for this sort of thing. Dmcq (talk) 14:29, 17 July 2010 (UTC)

British banks have never dealt in decimal half pennies (except in pairs), even when they were legal tender. Some credit cards are generous and round up to the nearest penny. Dbfirs 16:59, 17 July 2010 (UTC)

Greedy tricolorability

The section called "How to color a knot" in the Tricolorability article seems to imply that a greedy, nonbacktracking algorithm will always succeed in properly tricoloring a knot if the knot is indeed tricolorable. But surely this is not the case—in the fourth step of the "example of a tricolorable knot", if the lower right strand is selected and colored blue (rather than the L-shaped strand on the left) then it is impossible to properly complete the tricoloring. Right? —Bkell (talk) 14:17, 17 July 2010 (UTC)

In the example given, each step is forced except for the initial color choices. So it's not so much greedy as take the only choice available at each step. The article doesn't do into it but I assume there are more complex knots where you have multiple choices available at an intermediate step, and have to use some sort of backtracking. The section is a bit WP:HOWTO for my taste but it seems correct mathematically.--RDBury (talk) 14:34, 17 July 2010 (UTC)

The colors for the top right weren't forced, they could be swapped round. Notice the 'and color it with another color' in box 3. The only available different color for that lower right strand is red. Dmcq (talk) 14:36, 17 July 2010 (UTC)

Sure, the colors are forced if the strands are chosen in the order given. But if I choose to color the lower right strand third rather than fourth, and I choose to color it blue, then I arrive at a conflict that cannot be resolved without backtracking (because I cannot then color the L-shaped strand on the left). —Bkell (talk) 15:26, 17 July 2010 (UTC)

Anyway, my point is that I think the section is subtly flawed. It (imprecisely) describes an algorithm for coloring the strands—a greedy, nonbacktracking algorithm—and implicitly makes the claim that if this algorithm gets stuck then the knot is not tricolorable. I think this claim is false. —Bkell (talk) 15:29, 17 July 2010 (UTC)

Ah, okay, I see what you're saying, RDBury. In these examples the strands are chosen in an order that is carefully prepared so that there is only one possible color in each step, thus making backtracking unnecessary. (That's an important point that is omitted in the "how-to".) However, even this is not exactly the case: the "rules" of tricolorability described in the preceding section allow all of the strands incident upon a crossing to be given the same color, so, for example, the second strand colored in each of these examples could have been red. —Bkell (talk) 15:38, 17 July 2010 (UTC)

If you followed their rules you could have chosen different colors for the top right but the only choice for the bottom right was red. The color chosen according to the rule is another color. It can't be the same color as the other side unless the string over was the same color too. Dmcq (talk) 15:42, 17 July 2010 (UTC)

Yes, I know. I'm talking about the point in time when you have just colored the first strand red and you are pondering what color to use for the second strand. You have two choices here: either color the second strand red, so that it matches the first strand, or green (say), so that it doesn't match. Either is a priori allowable by the rules of tricolorability, even though the description of the algorithm says that a different color must be chosen. —Bkell (talk) 15:45, 17 July 2010 (UTC)

In other words, the entire lower left corner of the first example could properly be colored red. Or the entire upper right corner. (But not both, because the rules require at least two colors be used.) —Bkell (talk) 15:47, 17 July 2010 (UTC)

If your comment was a reply to what I wrote at 15:26, then let me try to explain it again. First operation is the same as the example: coloring the upper left strand red. Second operation is also the same as the example: coloring the J-shaped strand green. Third operation is different from the example: we are going to color the lower right strand now, not the lower left strand. This seems to be a legal choice to make. We choose to color this strand blue. This also seems to be a legal choice to make. It does not conflict with the coloring of the lower left L-shaped strand, because we haven't colored the lower left L-shaped strand yet. However, if we now choose to color the lower left L-shaped strand as our fourth operation, we arrive at a conflict and must backtrack. —Bkell (talk) 15:52, 17 July 2010 (UTC)

I see, instead of following the string across choose a string that was crossed over. That certainly gives problems. It might be the statement of the algorithm is incomplete, but anyway I had a quick look on the web and I couldn't see any reference to an algorithm to three color a knot if it is possible, so on a quick guess I'd have to agree it was made up, or in wiki speech original research. Lets just see if anyone else comes up with a citation within a day since there are nice diagrams, and otherwise just remove that stuff entirely and note its removal and date in the talk page. Dmcq (talk) 16:32, 17 July 2010 (UTC)

Interest calculations

My credit card company has just sent me an offer of zero percent interest for one year, and no transfer fee. I am not at all in debt apart from an interest-only mortgage. How should I calculate the amount of money that I can obtain from the credit card to pay off part of my mortgage? The two conditions are i) there must be zero money outstanding on the credit card when the interest-free year ends, and ii) the combined payments on the credit card and the interest-only mortgage must be no more than they are now. The credit card small-print says I should pay at least 2.25% of the outstanding balance off each month, or £5, whichever is greater. Thanks 92.29.117.202 (talk) 15:54, 17 July 2010 (UTC)

Without thinking about the particulars my first impulse would be to borrow as much as possible and stick 73% into bonds for 11 months and pay back the 2.25% with the remainder. Then walk away with the interest when paying the bank back. I doubt they'd lend you enough to pay any decent part of the mortgage back but you might be able to buy yourself a nice dinner. Dmcq (talk) 16:57, 17 July 2010 (UTC)

The interest rate on the mortgage would be greater than that on bonds. 92.29.117.202 (talk) 18:59, 17 July 2010 (UTC)

ACT practice test question

This is an extremely elementary geometry question, I'm just asking because there is a surprising amount of disagreement over it. I was taking an ACT practice test, and there is a question, which I've copyied below:

The rectangles ABCD and EFGH shown below are similar. Using the given information, what is the length of side EH, to the nearest tenth of an inch? (Rectangle drawing summary follows: ABCD: AD labelled 3 inches, CD labelled 8 inches, others unlabelled; EFGH: GH labelled 2 inches; AB and CD appear to be the longer sides of ABCD; EH and FG appear to be the longer sides of EFGH) Attempt at ASCII art rendering follows

                       E _______F
   A_____________ B     |       |         
   |             |    ? |       |
 3 |             |      |       |
   |_____________|      |_______|
  D       8      C     H   2 in  G

The answer choices are: A. 0.8
B. 1.3
C. 5.3
D. 7
E. 8

I saw that EH and FG was longer than GH and EF, but the instructions in the ACT said that Figures are not necessarily drawn to scale, so I disregarded this. I reasoned that since ABCD~EFGH then EH and AD must be proportional, as must be GH and CD. Setting up the proportion EH/3=2/8 I got EH=.75 which rounds up to .8 and thus picked A. However in the answers section they claim the correct answer is C. The explanation they provided makes no sense to me. They said that 3/8=2/EH therefore 3(EH)=16 and EH=5.3. Is this a mistake in the book? I thought corresponding segments in similar figures have to be proportional, ie A corresponds to E, B to F, C to G, D to H. Thanks for any help. Sorry about the TLDR. 76.229.159.199 (talk) 17:25, 17 July 2010 (UTC)

Apparently they want you to decide that EFGH is a rotated and scaled version of ABCD (thus still similar). The idea that they're not to scale is meant to prevent you from measuring EH and GH directly on the paper with a ruler to get the length; it seems it is not meant to prevent you from noticing which sides are longer. --Tardis (talk) 17:37, 17 July 2010 (UTC)

I don't get it. If you pick GH is the long side then EH = 0.75 whereas if you pick GH to be the short side then EH = 5.33. Both are included (rounded) in the choices so what was the clue to treat GH as the short side? hydnjo (talk) 19:47, 17 July 2010 (UTC)

Algorithm to combine trees?

Is there an algorithm to combine two similar trees please? The trees would be broadly similar, except some of the nodes (and their sub-nodes) would be missing in one of the trees, and there would be extra nodes (and their sub-nodes) in one of the trees. The trees start from the same root.

If it makes thing clearer then the two trees-to-be-merged could be TreeA: Food>breakfast,lunch. breakfast>boiledegg,toast,marmalade. lunch>pasta,apple.

TreeB: Food>breakfast,lunch, dinner. breakfast>toast,kipper,marmalade. lunch>sandwich,fruit. fruit>apple,orange,banana. dinner>lentils,rice,strawberries.

TreeCombined: Food>breakfast,lunch,dinner. breakfast>boiledegg,toast,marmalade,kipper. lunch>pasta,apple,sandwich,fruit. fruit>apple,orange,banana. dinner>lentils,rice,strawberries.

Thanks 92.29.117.202 (talk) 18:26, 17 July 2010 (UTC)

The Computing reference desk is probably better for this sort of thing. Dmcq (talk) 18:46, 17 July 2010 (UTC)

By the way I believe this would be called a merge of the trees and you have named nodes. Dmcq (talk) 18:52, 17 July 2010 (UTC)

Mathematical game

Player B chooses a positive integer 1 < n < 20. Then, player A writes down any n consecutive positive integers. Starting with A, players alternate crossing off numbers until there are two left. If the two numbers are relatively prime, A wins; otherwise, B wins. Can one player guarantee victory? --138.110.206.102 (talk) 21:17, 17 July 2010 (UTC)