Wikipedia:Reference desk/Archives/Mathematics/2010 March 16

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.

March 16

Sum of i?

Look at Kullback-leibler divergence and the first formula in the definition defines a sum from i. Not from i to something, just from i. Is that a typo? If not, what is it the sum of? Is it assumed that P(i) is a set of values? -- kainaw™ 01:32, 16 March 2010 (UTC)

The notation $\Sigma _{i}$ means "sum over all values of i ". Of course the meaning of all is context-dependent. --Trovatore (talk) 01:37, 16 March 2010 (UTC)

In this case it's over all real numbers i for which $P(i)>0$. There are countably many such is. Note that the distribution is assumed to be discrete, so $\Sigma _{i}P(i)=1$. It can probably be shown that the sum converges absolutely. -- Meni Rosenfeld (talk) 08:14, 16 March 2010 (UTC)

I don't see anything that says i has to range over real numbers. i could be taken from the set {red,green,blue}, and then you'd have the perfectly sensible expression $P(red)\log {\frac {P(red)}{Q(red)}}+P(green)\log {\frac {P(green)}{Q(green)}}+P(blue)\log {\frac {P(blue)}{Q(blue)}}$. --Trovatore (talk) 18:42, 16 March 2010 (UTC)

Indeed. While it should be made more explicit, I think it is clear that i ranges over the sample space of the random variables in question. There is no restriction on what that sample space can be, other than that it must be countable in order for a discrete distribution to exist on it. --Tango (talk) 18:47, 16 March 2010 (UTC)

four dimensional space.

If S^3= { (x,y,z) : x^2+y^2+z^2+w^2=1} and S^2= { (x,y,z) : x^2+y^2+z^2} and h: S^3→S^2, where S^3 is circle in four dimensional space and S^2 is circle in three dimensional space. Then check for h(a,b,c,d) ε S^2. Find h^(-1)(0,0,1). —Preceding unsigned comment added by 147.174.75.241 (talk) 01:48, 16 March 2010 (UTC)

You need to be more specific about what the function h is. You've given its domain and codomain, but not the actual definition. Staecker (talk) 11:12, 16 March 2010 (UTC)

Our original poster is not asking a question; he's doing stenography. If he'd bother to read and understand what he wrote, he'd realize it doesn't make sense because he left something out. Michael Hardy (talk) 02:07, 17 March 2010 (UTC)

Was 2 always prime?

Is it true that the number 2 was not always considered prime? If so, when was this and what were the arguments against its primality? Thanks.Antheafor (talk) 11:17, 16 March 2010 (UTC)

From the article Prime number: Until the 19th century, most mathematicians considered the number 1 a prime. You might be thinking of this fact instead of the number 2 ??? 195.35.160.133 (talk) 11:44, 16 March 2010 (UTC) Martin.

I agree, the OP is probably thinking of the dispute over whether 1 should be considered prime (these days it isn't, simply because it makes the definition more useful - that's how definitions are decided in maths). As far as I know, 2 has always been considered prime and I can't think of any reason for it to be excluded. --Tango (talk) 11:51, 16 March 2010 (UTC)

There are some cases in which considering 1 to be a prime would be more useful: For a typical example, just think about the common version of Goldbach conjecture: every even number greater than 2 is a sum of two primes. The restriction "greater than 2" spoils the aesthetics of the conjecture; However, if we considered 1 to be a prime then we would get the original conjecture (being slightly different from the better-known conjecture), which is much simpler to formulate: every even number is a sum of two primes. Note that even the original conjecture hasn't been resolved yet. HOOTmag (talk) 12:10, 16 March 2010 (UTC)

Wouldn't that change the content? Is it known that if p is a prime greater than 2 then (p+1) is the sum of two primes (neither of which is equal to 1)? If not, it seems like including 1 would change the meaning of the conjecture. — Carl (CBM · talk) 12:20, 16 March 2010 (UTC)

Yes, that would really change the content, but I have already made a distinction between what I've called "the original conjecture" and what I've called "the better-known conjecture" (see above what I wrote in parentheses). Note that Goldbach used originally what I called "the original conjecture", which really considers 1 to be a prime. The better-known conjecture, which does not consider 1 to be a prime, is due to Euler, rather than Goldbach. For more details, see Goldbach conjecture. HOOTmag (talk) 13:23, 16 March 2010 (UTC)

Let's also report the "little Goldbach conjecture": every even prime is a sum of two odd numbers. --78.13.143.108 (talk) 15:03, 20 March 2010 (UTC)

Notice that considering 1 to be a prime does not change the content of your conjecture... HOOTmag (talk) 18:06, 22 March 2010 (UTC)

If 1 is prime there is no more unique factorization. I'm amazed that the idea that 1 is prime persisted til the 19th century. 66.127.52.47 (talk) 12:50, 16 March 2010 (UTC)

It takes some development of abstract algebra to realize that unique factorization is a useful property.—Emil J. 13:15, 16 March 2010 (UTC)

According to our article, Fundamental theorem of arithmetic, the first complete and correct proof of the theorem was in Disquisitiones Arithmeticae, which was published in 1801. So, unique factorisation wasn't even properly proven until the 19th century. --Tango (talk) 13:36, 16 March 2010 (UTC)

You still have unique factorization; it's just more awkward to state. You have to keep talking about "primes other than 1" or some such. There are several things that seem more natural if 1 is included in the primes; I recall a list on some Usenet group, but I don't remember them right now. --Trovatore (talk) 02:01, 17 March 2010 (UTC)

Everybody knows 2 is the odd prime, being the only prime that is even. Gabbe (talk) 15:00, 16 March 2010 (UTC)

Not so long ago I heard a formidable mathematician object to calling 2 a prime number on the grounds that so many theorems have a hypothesis that p is an odd prime (for example, recall from undergraduate algebra that the quadratic formula works in the field of integers mod p if p is an odd prime). Michael Hardy (talk) 00:57, 17 March 2010 (UTC)

Yes, lots of quadratic things require you to exclude p=2, but don't the equivalent cubic things require you to exclude p=3, etc.? We just work with quadratics more often, but the principles are the same. --Tango (talk) 01:49, 17 March 2010 (UTC)

A theorem in finite group theory due to Thompson asserts that in order to prove that a finite group has a normal p-complement (for p an odd prime), it suffices to check that the normalizers of just two p-subgroups each possess a normal p-complement (out of interest, the subgroups are the center of a Sylow p-subgroup of G, and the Thompson subgroup of this Sylow p-subgroup). A theorem due to Frobenius asserts that a finite group G has a normal p-complement if and only if the normalizer of every non-identity p-subgroup of G has a normal p-complement; the result due to Thompson is clearly very strong in comparision to Frobenius's result. However, the strengthening is valid only for odd primes (one particular application of Thompson's result is that a non-identity p-group cannot be a maximal subgroup of a finite simple group if p>2; another instance of how "2" differs from other primes). Results of this nature are dispersed across the field of finite group theory, and perhaps add furthur evidence supporting the idea that 2 "should not be a prime". PST 13:44, 17 March 2010 (UTC)

Request for input at our Entertainment desk

This question might benefit from your thoughts, O oracles of problem-solving! ---Sluzzelin talk 13:42, 16 March 2010 (UTC)

First of all note that there is a difference between (1) a soduko puzzle, (2) a soduko puzzle with an unique solution, and (3) a designed soduko puzzle. It's also not quite defined what you mean by having to guess, most steps of solving soduko puzzles are based on guessing, ie. we know that the 1 goes in this slot because if it does not there is no point it can go into. So it's more of a question of degree of guessing, how much will you have to "solve" the puzzle past your guess to resolve the question, and how many steps you will have to backtrack, that is how many seperate points will you have to guess on. That said, (1) will frequently require guessing because, since more than one solution is possible there will be no way to exclude a solution. (3) will, if the design is good, be solvable with a degree of guessing that most will consider as not guessing. This leaves (2) as the interesting case. Unless I am completely mistaken soduku is NP-complete, so the answer is that most believe that any method of solving will be at least as much work as guessing and backtracking, but it's possible that effective algorithms exists which will solve things faster. This is known as the P=NP problem, and is considered one of the great unsolved problems of computing today. Taemyr (talk) 12:33, 17 March 2010 (UTC) I have seen no proof of sudoku NP-hardness and could be completely wrong when I claim it's hard. Taemyr (talk) 12:37, 17 March 2010 (UTC)

Sudoku is ASP-complete under parsimonious poly-time reductions[1], which means the following: for every NP-problem of the form $\exists y\,P(x,y)$ with P poly-time and |y| implicitly bounded by a polynomial in |x|, there exists a poly-time function f whose outputs are partially filled Sudoku grids (m×m for some m polynomial in |x|) such that for every x the number of y satisfying P(x,y) equals the number of solutions of f(x). Thus in this (very strong) sense, Sudoku is indeed NP-complete.

However, if you strictly take the task of solving Sudoku in the usual sense, the situation is different. First, it is not even a decision problem, but a search problem: you are not looking for any yes-no answer, you are looking for a solution of the grid (i.e., given a Sudoku puzzle with a unique solution, find the solution). Now, this search problem is mutually poly-time Turing reducible with the following promise problem: given a Sudoku puzzle with at most one solution, decide whether it has a solution. By the completeness result above, this is a complete problem for promise-UP (the class of promise problems of the form $\exists y\,P(x,y)$ with |y| polynomially bounded in |x| and with the promise that there is at most one y which satisfies P(x,y)). This is similar to NP-completeness, but it is not quite the same. There is a randomized poly-time reduction of NP to UP, hence you can consider Sudoku solving to be "NP-complete" by randomized poly-time Turing reductions.

Of course, all the above relies on using variable-sized grids. If you stick to the usual 9×9 grid, it becomes a finite problem, hence it is trivial from the viewpoint of computational complexity (it is solvable in constant time).—Emil J. 14:11, 17 March 2010 (UTC)

I find no link to ASP-complete, and a quick Google search finds nothing on the first page that explains it. What is it? Michael Hardy (talk) 18:41, 17 March 2010 (UTC)

.....oh, maybe your explanation answers that. Should we have a Wikipedia article on that concept? Michael Hardy (talk) 18:43, 17 March 2010 (UTC)

My explanation actually only explained what parsimonious is (as that's what's relevant here), see the original paper for definition of ASP-reductions and the general framework (basically, the reduction also has to provide a poly-time bijection between the two solution sets). I put the link there so that people can click on it instead of searching on Google. Should we have an article? I don't know; it does not seem to be a widely used concept. Parsimonious reduction may be a better candidate for an article, or at least for a definition included in sharp-P.—Emil J. 19:01, 17 March 2010 (UTC)

The Complexity Zoo doesn't have an ASP-completeness entry either, so it sounds pretty obscure. 66.127.52.47 (talk) 19:54, 17 March 2010 (UTC)

Inner Product Spaces

I asked almost this before, but I wasn't quite clear enough. I know the assumption would be enough to show that cauchy sequences converge, but:

In an inner product space, does ZF prove that if all absolutely convergent series converge then all cauchy nets/filters converge? (I know nets and filters are equivalent.) JumpDiscont (talk) 21:18, 16 March 2010 (UTC)

Actually your previous version here did seem clear enough (at least, not less that the new one). Since in the new version of your question Cauchy filters replace Cauchy sequences, I guess you want to know what is used to show the equivalence. Let me recall to you:

• A normed space is complete as a metric space (all Cauchy sequence converge) if and only if all absolutely convergent series converge; the equivalence just uses natural induction.

Therefore I guess you are asking whether for inner product spaces sequential completeness is equivalent to filter completeness, and whether AC is needed for the proof. Is this what you want? Recall that

• If a metric space (more geerally, a uniform space) is filter-complete, it is obviously sequentially complete.
• Conversely, (Cantor argument) any Cauchy filter-base ${\mathcal {B}}$ in a complete metric space (M,d) does converge; however, for this you do use a choice (for any $n\in \mathbb {N}$ you pick a $B_{n}\in {\mathcal {B}}$ and a point $x_{n}\in B_{n}$. It follows that $(x_{n})$ is a Cauchy sequence, thus convergent, and that ${\mathcal {B}}$ converges to the same limit).

I guess one can't avoid using AC or some weaker form of it, even in the case of Hilbert spaces. --pma 00:43, 17 March 2010 (UTC)

"Therefore I guess you are asking whether for inner product spaces sequential completeness is equivalent to filter completeness, and whether AC is needed for the proof." Exactly.

I think choice would not be needed for separable spaces (use the obvious embedding into the space's filter-completion, take the first member of the countable dense subset less than 1/n from the limit), although I'm wondering if the full thing is any weaker than CC, even if it was weakened to a normed space.

For example does ZF+"All sequentially complete normed vector spaces are filter-complete" prove Countable Choice?

JumpDiscont (talk) 02:07, 17 March 2010 (UTC)

X/Y

Consider a random variable X with mean µ1 and standard deviation σ1. Consider a random variable Y with mean µ2 and standard deviation σ1. What is X/Y? I know it has a cauchy distribution--203.22.23.9 (talk) 22:08, 16 March 2010 (UTC)

If X is a random variable and Y is a random variable then X/Y is also a random variable (as long as Y is not zero). Gabbe (talk) 00:16, 17 March 2010 (UTC)

See Ratio_distribution#Gaussian_ratio_distribution, if X & Y are known to be normally distributed. --173.49.81.5 (talk) 00:34, 17 March 2010 (UTC)

You can't conclude it's Cauchy-distributed without assuming more than what you've said. Often that additional assumption is simply that X and Y are independent, although some weaker assumptions will get you the same conclusion. Michael Hardy (talk) 00:58, 17 March 2010 (UTC)

.... geeeeeeeeez..... I just realized the question didn't say anything about normality or anything like that. So you can't say it's Cauchy-distributed. Michael Hardy (talk) 02:11, 17 March 2010 (UTC)