Mathematics desk
< June 8	<< May \| June \| Jul >>	June 10 >

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.

June 9

Stddev and stdevpop on TI-89 Titanium

What is the difference between these? Which should be used to calculate the standard deviation? --Tyw7 (☎ Contact me! • Contributions) Changing the world one edit at a time! 01:08, 9 June 2010 (UTC)[reply]

Both. Though my high school maths are a bit fuzzy, I recall clearly that standard deviation is calculated slightly differently in math and in science. If you are using the standard deviation for math (σx, IIRC) use stddev. If for science, use stdevpop. 76.228.192.218 (talk) 01:15, 9 June 2010 (UTC)[reply]

It's not about math versus science. The question is, do your data represent the whole population, or are they a finite sample chosen at random from an infinite population? In the former case, you divide the sum of the square deviations by the size of the population, and then take the square root — that's just the definition of the standard deviation.

In the latter case, what you care about is not the standard deviation of the sample, but the standard deviation of the population. You can't calculate what you want, because you don't have the entire population, but just a finite sample of it. However you can estimate it. An unbiased estimator for the std dev of the entire population is given by doing the same thing you would do in the first instance, except that at the step where you would divide by N, you divide by N−1 instead.

That gives you an unbiased estimator, meaning that the expected value of the estimator (maybe under the assumption of normality? I forget) is exactly the standard deviation of the infinite population. (Or is it that the expected value of its square is the variance of the population? Again, I forget.)

However it's a point of debate whether this is actually a good thing to do. If you just do the simple-minded thing and divide by N, same as always, you introduce a bias into the estimator, but you reduce the variance of the estimator.

As a practical matter, if the difference makes a difference, your sample size is too small anyway. --Trovatore (talk) 03:28, 9 June 2010 (UTC)[reply]

The expected value of its square is the variance of the population (ie, it is actually an unbiased estimator of the variance). No assumption of normality is required.

An unbiased estimator of the standard deviation is more complicated and does benefit from assumption of normality.

More details are at Standard deviation#Estimation. -- Meni Rosenfeld (talk) 07:05, 9 June 2010 (UTC)[reply]

QBF(PSPACE Complete Problem)

The Quantified Boolean Formula problem takes as input (Q1x1)(Q2X2)...(QnXn)B(X1,...Xn) and returns true if the expression is true with each Qi a quantifier. What domain do the quantifiers operate over? Is it simply {true, false};as in(All x)(Exist y)(x XOR y) is true since we have x = True and y = False, x = False and y = True, or am I missing something? 66.202.66.78 (talk) 08:38, 9 June 2010 (UTC)[reply]

Yes, the quantifier are over the set of the two truth values.—Emil J. 12:55, 9 June 2010 (UTC)[reply]

Meaning of a Conjecture Being Undecidable

I've been wondering a little lately what it means for certain conjectures to be undecidable. Suppose Goldbach's conjecture is undecidable. Now suppose that we have a computer program that when given an even number checks each pair of primes less than it and returns true iff it can be written as a sum of one of those pairs. Now, suppose we start at 2 and work upwards through the evens, halting iff a false is returned. Even if we can't prove that this computation ever halts, it seems like it should definitely halt or not halt; but, if it halts, then we know the conjecture is false, hence, it must never halt, and therefore, it must be true; obviously, something is wrong here. What have I missed?

Or does saying that Goldbach's conjecture is undecidable mean that there is some nonstandard model of arithmetic in which it is true and one in which it is false? In which case, there is no problem with our computer idea above since it would apply only to the case of the usual model for arithmetic?

Finally, my reasoning for using Goldbach's Conjecture is that we can always get to the next even number; checking the result for any given even, never throws us into a loop. Also, supposing that the notion about being true in some models and false in others is accurate, given a problem like the Riemann Hypothesis, is there anything analogus to the computer program above that can determine it in the case of a specific model? (If this is an absolute senseless combination of terms, I apologize, I'm not very aqauinted with the topic, just curious:) 66.202.66.78 (talk) 09:59, 9 June 2010 (UTC)[reply]

If you experience that the program halts, then it halts. If you do not experience that the program halts, then you do not know whether it eventually halts or not. Lacking a counterexample of the conjecture does not prove the conjecture. Any natural number is small because almost all natural numbers are bigger, so even statisticly, the vain search for a counterexample is not really an argument that the conjecture is true. A proof of a conjecture is a text explaining formally why the conjecture is necessarily true. If neither the conjecture nor its negation can be proved, then the conjecture is said to be undecidable. Bo Jacoby (talk) 11:30, 9 June 2010 (UTC).[reply]

But there are, indeed, some conjectures of the nature that, if they turn out to be undecidable, then they must be true. Of course, they can't be proven within the system, but the point is that a counterexample would be provable within the system, and if a counterexample can't be found, then the conjecture will be true. Now, whether we would be able to prove that a conjecture of that sort is independent of the axioms is a different matter, and seems dubious to me (although I really don't know), because it would partly involve proving the conjecture along the way: you would have to verify that a counterexample can never be found. --COVIZAPIBETEFOKY (talk) 11:41, 9 June 2010 (UTC)[reply]

OP Here, thank you for your replies. Allow me to clarify: I am not trying to argue that failure to find a counterexample is a proof, that is obviously false. My point was that the program halts or it doesn't, even if we don't know which. Thus, if it halts, then there is a counterexample. If it never halts, then it is true. In short, since the program halts or doesn't halt, the conjecture is true or false, even if it can't be proven. The point of my question was to ask if when people say things like Goldbach might be undecidable, would it still be true (in the sense above), or if not, why not? And what types of conjectures can such a program be developed for? (Consider the Collatz Conjecture, divergence is a counterexample that results in it never halting, thus a difference from the above, so can some undecidables have a truth value and other's not; and if they do have some form of truth, does it follow they are consistent? etc.) 67.163.183.146 (talk) 14:13, 9 June 2010 (UTC)[reply]

The thing to remember is that "undecidable" (or better for this sense of the word, "independent") is not a truth value. When you speak of a proposition being independent, you always have to mention a specific formal theory of which it's independent.

So for example it's possible (although I think few consider it very likely) that Goldbach's conjecture is independent of (let's say) ZFC; that is, that ZFC neither proves nor refutes Goldbach's conjecture. However, if that is the case, then as you note above, Goldbach's conjecture is true, because if it were false, then ZFC would be able to demonstrate that fact by demonstrating a counterexample.

This is not really a problem unless you're attached to the idea that mathematical truth is the same as provability. Once you accept that that idea is just wrong, there really isn't an issue here. --Trovatore (talk) 21:39, 9 June 2010 (UTC)[reply]

Then, isn't a proof, that ZFC neither proves nor refutes Goldbach's conjecture, a proof of Goldbachs conjecture? Bo Jacoby (talk) 07:10, 13 June 2010 (UTC).[reply]

Yes, it is. Moreover, the "neither proves" part is unnecessary: ZFC not refuting Goldbach's conjecture by itself implies Goldbach's conjecture. It therefore should not come as surprise that ZFC (if consistent) cannot prove that Goldbach's conjecture is independent of ZFC (which also follows from Gödel's incompleteness theorem), you'd need a stronger theory for that.—Emil J. 13:15, 13 June 2010 (UTC)[reply]

Program to Find Primes

I have created a program in C++ for finding prime numbers... This is a very simple program and so, I think you all can understand the gears and wheels of it... I was able to find the first 1000 primes in a little less than 1 second... Please tell me if there is a better way to find prime numbers... Just tell the way and I will program it myself... Do people find larger and larger primes only this way??

{
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int nNumberofArgs, char* pszArgs[])
{
    unsigned numberOfNumbers;
    cout << "Hey Donkey!! Type the number of prime numbers to be printed and press Enter key : ";
    cin >> numberOfNumbers;
    unsigned subjectNumber=2;
    unsigned printedNumbers=1;
    unsigned tester=1;
    unsigned hit=0;
    while (printedNumbers<=numberOfNumbers)
    {
          hit=0;
          tester=1;
          while (tester<=subjectNumber)
          {
                if (subjectNumber%tester==0)
                {
                                            hit++;
                }
                tester++;
          }
          if (hit<=2)
          {
                     cout << subjectNumber << "               " << printedNumbers << "\n";
                     printedNumbers++;
          }
          subjectNumber++;
              }
    system ("PAUSE");
}
}

harish (talk) 13:00, 9 June 2010 (UTC)[reply]

A trivial optimization is to test only divisibility by numbers up to the square root of the subject number. However, for generation of successive primes it is much more efficient to use a sieve. The classical sieve of Eratosthenes is relatively easy to implement, and fast enough (usually it should generate the numbers faster than it takes them to be converted to decimal for printing out). The sieve of Atkin is asymptotically even faster, but it is more complicated, and it is a bit tricky to implement. Primegen, which is an implementation of the Atkin sieve, can generate all primes below 1,000,000,000 in about a second on my machine (without printing, that would take much longer). Finally, people don't get to find larger and larger primes in this way, the record holders are primes of a very special form (such as Mersenne primes) for which there are much faster special-purpose primality testing algorithms available.—Emil J. 13:12, 9 June 2010 (UTC)[reply]

Also, to find a very large prime number (not record-breaking) that doesn't have a special form, you can just generate a very large number, test it for primality, and repeat until you end up with a prime. -- Meni Rosenfeld (talk) 13:29, 9 June 2010 (UTC)[reply]

[ec] There are much faster ways to find prime numbers. A few improvements you can easily make:

Test only odd numbers for primality (by setting subjectnumber=3 and subjectnumber+=2).
Test only odd factors.
Test only factors such that tester*tester <= subjectnumber.
Keep an array of primes, and test only prime factors.

However, the really efficient ways for this are sieves. Sieve of Eratosthenes is fairly simple, but Sieve of Atkin is more efficient. -- Meni Rosenfeld (talk) 13:23, 9 June 2010 (UTC)[reply]

I note that the OP also posed the same question on the Computing Reference desk.—Emil J. 13:36, 9 June 2010 (UTC)[reply]

You can also speed it up by breaking out of the while loop once you've found a factor (don't check 1 or the subject number itself, since you know they are factors, then you can just test if there is one other factor rather than having to count the factors). Once you know that 6 is divisible by 2, you don't need to know if it is also divisible by 3, 4 or 5. --Tango (talk) 20:08, 9 June 2010 (UTC)[reply]

"better" by what metric? Elegance, obfuscation, use of regular expressions for a purpose never intended?

perl -le 'print+grep{(1x$_)!~/^(11+)\1+$/}(2..1e2)'

-- 58.147.55.151 (talk) 12:04, 10 June 2010 (UTC)[reply]

trignometry

I want to ask if there is:

sin A - sin B = 2cos(A+B/2) sin(A-B/2)

is this statement true? —Preceding unsigned comment added by Shubhamgirdhar810 (talk • contribs) 17:06, 9 June 2010 (UTC)[reply]

Note that the form should be:

sin A - sin B = 2cos((A+B)/2) sin((A-B)/2)

81.147.4.160 (talk) 20:20, 9 June 2010 (UTC)[reply]

anti-transpose?

Is there a typical name for the transpose-like involution that does:

{\begin{bmatrix}a&b\\c&d\end{bmatrix}}\mapsto {\begin{bmatrix}d&b\\c&a\end{bmatrix}}

(reflecting entries across the antidiagonal)? Staecker (talk) 19:20, 9 June 2010 (UTC)[reply]

I've never heard of a name for it. I've also never seen it used, though - have you? Things typically don't get named if nobody uses them. --Tango (talk) 20:01, 9 June 2010 (UTC)[reply]

I've never seen it used before, but it's come up in something I'm working on. Briefly: I have a selfmap on the dimension 2 torus whose induced map in the fundamental group is a 2 by 2 matrix A. This matrix also gives the induced map on dimension 1 simplicial homology (which here is the same as the fundamental group). I want to know what the induced map on the dimension 1 cohomology is with respect to a Poincare dual basis. I think it's the above described involution of A. But I'm not an expert on this business- any corrections are welcome. Staecker (talk) 20:57, 9 June 2010 (UTC)[reply]

The eigenspaces of your operator are U (with eigenvalue 1) and V (with eigenvalue –1), where

U:=\left\langle \left({\begin{array}{cc}0&0\\1&0\end{array}}\right),\left({\begin{array}{cc}0&1\\0&0\end{array}}\right),\left({\begin{array}{cc}1&0\\0&1\end{array}}\right)\right\rangle \ {\mbox{and  }}\ V:=\left\langle \left({\begin{array}{cc}-1&0\\0&1\end{array}}\right)\right\rangle .

Wouldn't you just look at the dual spaces U* and V* to get the cohomolgy? •• Fly by Night (talk) 21:19, 10 June 2010 (UTC)[reply]