Wikipedia:Reference desk/Archives/Mathematics/2010 October 29

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

October 29

binomial identity

Resolved

I have been reading from the book of Concrete Mathematics and have a small doubt about a binomial identity on Pg 199. Having shown the identity ${\frac {1}{(1-z)^{n+1}}}=\sum _{k\geq 0}{\tbinom {n+k}{n}}z^{k}$, the book claims that multiplication by $z^{n}$ yields the identity ${\frac {z^{n}}{(1-z)^{n+1}}}=\sum _{k\geq 0}{\tbinom {k}{n}}z^{k}$. I am confused as to why in the latter identity the sum does not run over $k\geq n$, as I feel it should after multiplying and reindexing n+k as k. Or is this a misprint?-Shahab (talk) 03:44, 29 October 2010 (UTC)

Well, $k\geq 0$ and $k\geq n$ are both correct in this case. If $k<n$, then ${\tbinom {k}{n}}=0$. —Bkell (talk) 03:51, 29 October 2010 (UTC)

The expression can be written simply $\sum _{k}{\tbinom {k}{n}}z^{k}$ thus avoiding the problem. Bo Jacoby (talk) 07:38, 29 October 2010 (UTC).

Okay. Thanks-Shahab (talk) 09:00, 29 October 2010 (UTC)

chance to win lotto in 70 years

If Play LOTTO every day for 70 years what would be the possibility of winning 1 time? Assume lotto would play every day? —Preceding unsigned comment added by 99.16.144.232 (talk) 12:43, 29 October 2010 (UTC)

That depends on the workings of whatever thing it is you're calling "LOTTO". Algebraist 12:47, 29 October 2010 (UTC)

If you are referring to any of the standard lotteries with the odds of winning being about 1 in 50 trillion, purchasing a lottery ticket every day does not increase your odds of winning the lottery. The odds that you will receive a winning ticket as a gift or simply find a winning ticket on the ground is just as significant as the odds that you may purchase a winning ticket at some point in the future. -- kainaw™ 12:52, 29 October 2010 (UTC)

50 trillion?! That sounds off by five to six orders of magnitude. A rule of thumb that I use (primarily based on observation of US state lotteries) is that the state keeps half of the proceeds and pays out the remainder in prizes. Half of the prize money goes into the jackpot pool and the remainder is paid off each week in smaller prizes for partial matches. The jackpot prize is typically quoted as the 20-30 year total annuity payment of about twice the actual value. So a 50 million:1 lotto will often see jackpots in the order of 12.5 million (times the cost of a ticket -- typically $1 in the US), described as a 25 million annuity. A 50 trillion:1 lotto would not be popular as the public would want to see on the order of a couple of winners a year to feel as if they have a chance, and would be unlikely to participate in a game with an ever growing but never paid out jackpot. -- 119.31.126.67 (talk) 22:05, 29 October 2010 (UTC)

The lottery is called LOTTO in the UK. You pick six numbers from a total of 49, then they pick six numbers and a bonus ball from a total of 49. According to this section, the odds of winning are 13,983,815 to 1. So the probability of winning on a fixed day is

${\frac {1}{13,983,815}}\approx 7.2\times 10^{-8}.$

Ignoring leap years, then in 70 years there are 25,550 draws. The probability of winning in those 70 years is

${\frac {25,550}{13,983,815}}\approx 0.0018\sim 0.18\%.$

To get the probability up to 1 then you'd need to play about 14 million times. That would take you around 38,356 years. I think this is right, but I haven't studied probability since high school. — Fly by Night (talk) 13:45, 29 October 2010 (UTC)

That's the expected number of wins, not the probability of at least one win. Did you really think you can guarantee a lottery win by buying one ticket in enough draws? Also, there are many things in the world called "lotto", and the OP geolocates to Texas. Algebraist 13:55, 29 October 2010 (UTC)

Well why don't you enlighten us with the correct answer instead of belittling mine? — Fly by Night (talk) 14:04, 29 October 2010 (UTC)

Because I don't know what lotto we're talking about yet. Algebraist 14:07, 29 October 2010 (UTC)

Texas_Lottery#Lotto_Texas — Fly by Night (talk) 14:15, 29 October 2010 (UTC)

Anyway, if p is the probability of winning in a single draw, then the probability of winning at least once in n independent draws is 1 − (1 − p)ⁿ. Since here p is probably much smaller than 1/n, the estimate np is nearly accurate.—Emil J. 14:26, 29 October 2010 (UTC)

I guess that this is because p is so small? Assuming that 0 ≤ p ≤ 1 and that n is a positive integer, we have 1 – (1 – p)ⁿ = np if and only if p = 0. For very small p, the two are almost equal. In fact, the correct answer to the OP's question was (ignoring leap years) given by EmilJ's answer but using p = 13,983,815^–1 and n = 25,550; i.e. 1 – (1 – p)ⁿ ≈ 0.001825. If we use my incorrect school boy method then we get np ≈ 0.001827. Although, away from very small p, my school-boy answer becomes really wrong. If p = 1/2 and n = 10 then the real answer is almost 1, but my school-boy answer gives me 5; meaning I would have won every other time. That's why I didn't continue my education in probability: I'm rubbish at it! — Fly by Night (talk) 19:39, 29 October 2010 (UTC)

When your linear algorithm tells you that the expoected value is 1, then the true probability of winning (at least) once is ("almost exactly") (e-1)/e. You more or less already deduced that result. When the expected value is 5 (which actually means that the expected average number of wins is 5), then your chance of not winning even once is

${\frac {e^{5}-1}{e^{5}}}=1-e^{-5}$, more or less.

"More or less" and "almost exactly" here indicates that in practice there are rather small differences between the numbers e and $(1-n^{-1})^{n}$, when the integer n is as large as either of the ones discussed here. JoergenB (talk) 22:14, 29 October 2010 (UTC)

It wasn't really explicitly said, but you'd expect to lose money with any lottery strategy, for otherwise the organizers wouldn't make money. Of course, if you value the emotional experience of playing the lottery, you might actually come out ahead on total value by purchasing lottery tickets. (Some lotteries probably purposefully lose money--eg. a charity raffling off a car that was itself donated--but with for-profit lotteries, the above applies.) 67.158.43.41 (talk) 03:01, 30 October 2010 (UTC)

Lotto is a special tax for poor mathematicians. Bo Jacoby (talk) 19:58, 30 October 2010 (UTC).

Endomorphisms of finite cyclic groups

I want a proof relating to the kernel of endomorphisms of finite cyclic groups. --84.61.153.119 (talk) 14:42, 29 October 2010 (UTC)

Here's an easy proof: Suppose some element $c\neq 0$ maps to 0. Then $\langle c\rangle$ maps to 0. But as $G$ has prime order [this was an assumption in the statement of the proposition, which wasn't sought by the OP], $\langle c\rangle =G$, so the map is the zero map.—msh210℠ 15:58, 29 October 2010 (UTC)

See w:de:Wikipedia Diskussion:Botschaft#Odd cross-wiki behaviour by someone in Germany; sometimes includes edit-warring and disruptive page creation for more information on this person's edits. --A. B. ^{(talk • contribs)} 17:51, 2 November 2010 (UTC)

Normal subgroups of prime index

Let G be a group, N be a normal subgroup of G with index p prime, and x an element of N. What is the relation between ℂ_N(x) and ℂ_G(x)? --84.61.153.119 (talk) 17:52, 29 October 2010 (UTC)

How to prove that exactly one of the following two cases hold:

(a) ℂ_N(x) a normal subgroup of ℂ_G(x) with index p, and x^G = x^N;

(b) ℂ_N(x) = ℂ_G(x), and x^G = x₁^N ∪ … ∪ x_p^N with certain elements x₁, …, x_p of N, such that ℂ_N(x_i) = ℂ_G(x_i) ≅ ℂ_G(x) for all 1 ≤ i ≤ p? --84.61.153.119 (talk) 19:15, 29 October 2010 (UTC)

Could you give some context? Why do you need to know all of these things? What were you doing to make you arrive at needing to know such things? These seem quite isolated problems, and a little background and motivation would help the reference desk find your answer. — Fly by Night (talk) 20:03, 29 October 2010 (UTC)

For any subset S of G and any element x in G, x^S = {s^-1xs | s ∈ S}. --84.61.153.119 (talk) 07:58, 30 October 2010 (UTC)

For any group G and any element x in G, ℂ_G(x) = {g ∈ G | gx = xg}. --84.61.153.119 (talk) 14:58, 30 October 2010 (UTC)

See w:de:Wikipedia Diskussion:Botschaft#Odd cross-wiki behaviour by someone in Germany; sometimes includes edit-warring and disruptive page creation for more information on this person's edits. --A. B. ^{(talk • contribs)} 17:50, 2 November 2010 (UTC)

getting the first four of the LAST 5 digits? 1234 from 12349

Is there anything better than:

TheNumber = (x mod 10000) * 1000 + (x mod 1000) * 100 + (x mod 100) * 10 + (x mod 10)

And if there isn't, do I need the parentheses, or does order of operations take care of it? 84.153.201.148 (talk) 20:18, 29 October 2010 (UTC)

What about the floor function: floor(12349/10) = 1234? — Fly by Night (talk) 20:24, 29 October 2010 (UTC)

Thanks! Forgot about that... Actually I meant that it's a much bigger number though. So, should I write: x mod 10,000 to get the first four digits, then use floor? Like this:

floor( (x mod 10,000) / 10)

In this case is there a better, more elegant way, and do I need the parentheses? 84.153.201.148 (talk) 20:32, 29 October 2010 (UTC)

If you have a positive integer n with d digits, and you want to know the first ƒ-digits, then you need to know floor(n/10^d-ƒ). For example, n = 123,456,789 (so that d = 9) and you want to know the first five digits (so ƒ = 5) then you have floor(123456789/10^(9–5)) = floor(12345.6789) = 12345. — Fly by Night (talk) 20:43, 29 October 2010 (UTC)

Please note: I have just undone this change. Please don't change the question after people have started to answer. Just say that you asked the wrong question and rephrase what you wanted to ask. — Fly by Night (talk) 20:45, 29 October 2010 (UTC)

OP here, ip change. I already said "of the LAST five digits", so it was not a realchange. I just made it. caps just now, so I hope this doesn't irk you. Very clearly, this is what I want: the first four of the last five digits. 92.230.71.220 (talk) 21:50, 29 October 2010 (UTC)

Divide by an appropriate power of 10 and then take the floor function. That will give you an appropriate decimal digit... — Fly by Night (talk) 22:29, 29 October 2010 (UTC)

By "last" I think the OP means "least significant", in which case their mod solution seems quite good. 67.158.43.41 (talk) 02:48, 30 October 2010 (UTC)

what guarantee is there that numbers aren't very easy to factor (o(n))

what guarantee is there that large composite numbers aren't ridiculously easy to factor, just needing someone to think up and code a breakthrough algorithm that afterward anyone can use? 92.230.71.220 (talk) 22:20, 29 October 2010 (UTC)

There is no guarantee. All we know is that thousands (if not millions) of people have tried to figure out how to factor large numbers quickly. So far, nobody has figured out a way to do it quickly enough to make applications dependent on difficulty of factoring vulnerable. -- kainaw™ 03:01, 30 October 2010 (UTC)

A few more details can be found at the relevant section of the integer factorization article. Shor's algorithm shows that factorization can be done quickly on quantum computers (though these are incredibly delicate machines and progress has been slow on making large enough ones to be harmful to RSA--I hope). 67.158.43.41 (talk) 04:28, 30 October 2010 (UTC)

Some integers such as 10²⁵ or 2⁶⁴ are ridiculously easy to factor, so there is obviously no guarantee that they aren't ridiculously easy to factor. Bo Jacoby (talk) 18:09, 30 October 2010 (UTC).

Right, but there some classes of composites that are conjectured to be hard to factor, such as Blum integers (product of two distinct primes, both of which are congruent to 3 modulo 4) whose prime factors are of roughly the same size.—Emil J. 11:31, 1 November 2010 (UTC)

There are lots of algorithms for checking the non-primality of a number. For example, I can ask Maple if 10¹⁰⁰ + 1 is prime and it tells me withing a fraction of a second that it isn't prime. But when I ask it to factorize the number it just hangs. Even though the number before it, 10¹⁰⁰, could be factorized my my dog! It's already factorized. Okay, slight exaggeration; I don't have any pets. — Fly by Night (talk) 18:51, 30 October 2010 (UTC)

Conjecture

I have been reading about conjectures and proofs on Wikipedia, but I am wondering if there is any criteria for a hypothesis to be formally called a conjecture. For example, if I noted that no prime number ever identified contained both the digits 5 and 7 (which I am sure is not the case, but let's say that it is), would that be sufficient for me to claim that "no prime number contains the digits 5 and 7" was a conjecture? Is that too trivial, or poorly defined, or is there some other criteria it would fall foul of? Any clarification would be appreciated. Thanks CrispinWhittaker (talk) 23:05, 29 October 2010 (UTC)

You might like to compare and contrast the articles conjecture and hypothesis. The former says that "...a conjecture is a proposition that is unproven but appears correct and has not been disproven." while the latter says that a hypothesis is "...a proposed explanation for an observable phenomenon." For example, I might conjecture that all churches contain crosses, while you might hypothesise that all churches contain crosses because they are Christian places of worship. In short: a conjecture says that something is true, even though it cannot be proven. A hypothesis says that something is the way it is because of something or another. The problem with hypotheses is that they may be bases upon false assumptions: there may be churches without crosses. — Fly by Night (talk) 23:15, 29 October 2010 (UTC)

Ah yes, OK, so I have misused (quite badly) the term hypothesis. What I really meant, I suppose, is a proposition. So, are there any criteria that must be met for a proposition (e.g. my "no prime number has a 5 and a 7" proposition), to be formally considered (by the "mathematics community") as a conjecture? Thanks CrispinWhittaker (talk) 23:24, 29 October 2010 (UTC)

In this case, it comes down to provability. A conjecture is, as the article says, "...a proposition that is unproven but appears correct and has not been disproven." — Fly by Night (talk) 23:49, 29 October 2010 (UTC)

In mathematical writing, the word "hypothesis" is used differently from the scientific usage discussed above. Hypothesis is almost always used in the sense of Antecedent (logic). Rarely "hypothesis" is used as a synonym of "conjecture", as in Riemann hypothesis, but the terms would be regarded as interchangeable- calling the RH a hypothesis instead of a conjecture is just a convention. The term "proposition" is typically not used for conjectures, but for proved statements (like "theorem" or "lemma"), or more generally for any logical statement (as described at Proposition) whether true or false or provable or not. Staecker (talk) 12:31, 30 October 2010 (UTC)

Also, in mathematics, there is no formal criterion (and thus are no criteria) for when a statement may be called a conjecture. I think that the closest you can get is "a statement whose truth value was not known, but someone guessed probably should be true". There are some fairly clear cases, where a prominent mathematician has said or written "I conjecture that...", or words to that effect. There are other cases, which are not at all as clear. (S)he may have written something like "It would be interesting to know whether this property holds in general". In such cases, the statement "This property holds in general" sometimes are referred to as 'N.N.'s conjecture'; but this is not quite proper - and, in particular, if a case later is found where the property doesn't hold, this should most politely be referred to as "a negative answer to the question by N.N.".

In either case, the term "disproof" instead of "counterexample" or "negative answer" is unnecessary, and may be misleading, since some readers may get the impression that someone found an error in what another person has claimed to be proven. JoergenB (talk) 15:20, 30 October 2010 (UTC)

I would say that the article's definition is spot on: "...a proposition that is unproven but appears correct and has not been disproven." — Fly by Night (talk) 16:49, 30 October 2010 (UTC)

I don't like that formulation at all; it could contribute to the confusion between proof (mathematics) and proof (otherwise) which is fairly common.

Have you ever seen any of those letters from "trisectors", which universities often are plagued with, and which may start e.g. thus:

"Well, I know that the mathematicians have proved that it impossible to trisect an angle; but did they think of the following construction?"

A "proposition" in mathematics is essentially the same as a "theorem". A statement "appears correct" (i.e., appears to be a proposition), if there seems to be a proof for it; but possibly very complex, whence we have not yet checked the details. It is definitely "disproved", if we find an error in that suggested proof.

In my (less humble than usual) opinion, mathematics is not an empirical science. There is a really important difference between a "conjecture" in mathematics, and a "conjecture" in an empirical science. This is not reflected very well by the present summary in Conjecture. A quick look in the history shows that (at least for mathematics), the formulation was a good bit better six years ago:

In mathematics, a conjecture is a mathematical statement which has been proposed as a true statement, but which no one has yet been able to prove or disprove. (I should prefer "refute" to "disprove", here, but otherwise it seems fairly OK.) JoergenB (talk) 19:27, 30 October 2010 (UTC)

Your original formulation was "a statement whose truth value was not known, but someone guessed probably should be true". Your new formulation is "a mathematical statement which has been proposed as a true statement, but which no one has yet been able to prove or disprove." How do those differ from "..a proposition that is unproven but appears correct and has not been disproven"? This is exactly what your new formulation says:

• "a mathematical statement which has been proposed as a true statement" ~ "a proposition"
• "no one has yet been able to prove or disprove" ~ "unproven... has not been disproven"

— Fly by Night (talk) 19:45, 30 October 2010 (UTC)

I start to worry that this goes beyond the Reference desk issue; in which case we might continue elsewhere.

My "new" formulation is a quotation from a six year old one. I explained why I do not consider that as similar to the statement you provided (quoting our article conjecture):

• a proposition that is unproven but appears correct and has not been disproven.

As you can see, I wrote some minutes ago: A "proposition" in mathematics is essentially the same as a "theorem". Let me amplify: In modern mathematical texts, the terms proposition, theorem, lemma, and corollary are used for statements which are proved, either before or after the actual statement; either by the author(s), or by others (in an earlier article, book, or other context). There is some distinction between the usage of these terms; e.g., a corollary ordinarily follows after a statement with one of the other three labels, and its proof's main ingrediense often is a direct application of that preceeding statement.

Now, you seem to disagree. Do you disagree; and, if so, on what grounds? Do you think that my description of ordinary modern mathematical usage of the terms is wrong; or do you concede that the terms are used in that manner, but hold that using "proposition" as "proven statement of intermediate independent interest" is an abuse of the term? I can concede that we often use these four terms also for the statement themselves, in contexts where we discuss the proofs; we may start a proof with "Proof of the main theorem", or end with "Thus, the lemma is proved". However, we do not call this a theorem, proposition, lemma or corollary any longer, if the "proof" was shown to be defect. Actually, we may express this by saying something like

No, this is not a proposition; look here, that's a clear error (in the proposed proof).

Do you use these terms radically different? JoergenB (talk) 20:41, 30 October 2010 (UTC)

I'm sorry, you're straying from the point here. You said that a conjecture was "a mathematical statement which has been proposed as a true statement, but which no one has yet been able to prove or disprove." The article says that a conjecture is "...a proposition that is unproven but appears correct and has not been disproven." I say those two statements are the same. That was the only point I made, I wasn't questioning anything else. — Fly by Night (talk) 20:53, 30 October 2010 (UTC)

Well, I wrote, twice now, that in modern mathematics the term "proposition" is reserved for proven statements. Isn't that to the point? (You may well disagree factually, but I don't think you reasonably can claim that if I am right, a conjecture still could be called a proposition.) JoergenB (talk) 21:05, 30 October 2010 (UTC)

No, the word proposition is not reserved for proven statements. A proposition is simply something that is either true or false.

Now, there is a secondary meaning of proposition, usually not used stand-alone but rather in the form "Proposition 3.7" or whatever, that means "theorem that doesn't really seem worthy of the name theorem or maybe even lemma, or maybe I'm not calling it a "lemma" because it's of independent interest and not just a stepping stone". But that's not usually what proposition means except in the form "Proposition 3.7". --Trovatore (talk) 21:13, 30 October 2010 (UTC)

(e/c) I think we're having two totally different discussions here. Let's just leave it at that, shall we? — Fly by Night (talk) 21:16, 30 October 2010 (UTC)

Also note that, the fact that a proposition be a conjecture, is relative to the person who makes it. It sometimes happens that one makes a conjecture on something, ignoring that it has already been proven, or disproven. Of course a conjecture became famous when everybody would like to decide it , but nobody is able to do it for a while. --pma 21:47, 30 October 2010 (UTC)

Fly by Night, I really think this is one discussion; but with different aspects. If you agree with Trovatore, you may use "proposition" for a conjecture; if you agree with me, you can't.

When I was young, several books mentioned "Fermat's Last Theorem". This was later changed as improper; not believing that Fermat really had a correct proof for all cases, it should be called "Fermat's last conjecture".

With that, I agree that this leads too far, now and in this place. We might discuss it later at e.g. Talk:Conjecture, or at Talk:Proposition. JoergenB (talk) 22:05, 30 October 2010 (UTC)

There is really no possible argument about what proposition means. 2+2=5 is absolutely a proposition; this is indisputable. --Trovatore (talk) 23:40, 30 October 2010 (UTC)