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

October 19

Quick query on field extension K-homomorphisms and isomorphisms

Hi all,

I'm looking at K-homomorphisms: L->L in the field extension L/K (i.e. homomorphisms: L->L which are the identity on the subfield K), and trying to show when they must be isomorphisms. I've shown that for any algebraic field it must be isomorphic, and in general any k-homomorphism must be injective no matter whether or not the field is algebraic (looking at the kernel of the homomorphism which is an ideal). However, I'm trying to find an example of a non-bijective K-homomorphism on a transcendental field, and I've come up with the following, which is not even injective so it must be wrong.

Look at K[X], and take the map F:K[X]->K[X], F(p(X))=p(1).

Then F(p(X)q(X))=p(1)q(1)=F(p(X))F(q(X)), F(p+q)=F(p)+F(q) and F(k)=k for any constant k, so F(1)=1 in particular and F is a K-homom. However, first question: F is clearly not injective (F(x-1)=0=F(0)), but what's gone wrong? I can see how it's really a map F:K[X]->K in a sense, but K is a subset of K[X] so presumably that's fine (or else there's no such thing as a map K->K which is not surjective). Which part of my argument is fallacious?

And my second question is (assuming it is my example rather than my logic which is wrong!) could anyone suggest such a non-bijective K-homom. which would work, over a non-algebraic field extension?

Thankyou very very much, just brief answers will suffice, I don't want to take up too much of your time! Spalton232 (talk) 00:08, 19 October 2010 (UTC)

K[X] is not a field. Your F doesn't extend to the field K(X), since F(X-1)=0, so there's nothing F(1/(X-1)) can be. The map from K(X) to K(X) given by F(X)=X² should be a non-surjective homomorphism. Algebraist 00:12, 19 October 2010 (UTC)

More complex number trigonometry

1. Simplify ${\frac {1+\cos 2x-i\sin 2x}{1-\cos 2x+i\sin 2x}}$

2. Show that ${\frac {1-\cos x+i\sin x}{1+\cos x+i\sin x}}=ie^{-ix}\tan {\frac {x}{2}}$

For the first one I have multiplied the numerator and denominator by a wide array of assorted rubbish (including the complex conjugate of 1-cos2x+isin2x), but I have no way of knowing if it's the simplest form. I wouldn't have a clue how to do the second one. --MrMahn (talk) 04:08, 19 October 2010 (UTC)

For the first one, "wide array of assorted rubbish" does not sound very systematic. I would notice that $1-\cos x+i\sin x=1-z$ for $z=e^{i2x}$. An narrow array of systematic rubbish to try would then be $1+z$, $1-z$, $1+{\bar {z}}$, and $1-{\bar {z}}$. One of these should end up with something you can express with a single term. –Henning Makholm (talk) 06:35, 19 October 2010 (UTC)

If everything else fails, the algorithm I proposed in response to your previous question should work for the second one, if you set $y=x/2$ and unfold the exponential using Euler's formula. Or (easier in practice) set $z=e^{ix/2}$ and rewrite the two sides as ${\frac {1-z^{-2}}{1+z^{2}}}=iz^{-2}{\frac {(z-z^{-1})/2i}{(z+z^{-1})/2}}$ after which only algebra is left. –Henning Makholm (talk) 06:21, 19 October 2010 (UTC)

(After ec)

1. Try this way:
   
   ${\frac {1+\cos 2x-i\sin 2x}{1-\cos 2x+i\sin 2x}}={\frac {1+\cos ^{2}x-\sin ^{2}x-2i\sin x\cos x}{1-\cos ^{2}x+\sin ^{2}x+2i\sin x\cos x}}$
   
   $={\frac {2\cos ^{2}x-2i\sin x\cos x}{2\sin ^{2}x+2i\sin x\cos x}}={\frac {\cos x(\cos x-i\sin x)}{\sin x(\sin x+i\cos x)}}$
2. Did you try to substitute $f(x)=f\left(2{\frac {x}{2}}\right)$ for sine and cosine of x? For the right-hand side use the Euler's formula.

HTH. --CiaPan (talk) 06:24, 19 October 2010 (UTC)

related to the question above

This is related to my question about refuting a famous open conjecture. Should the proof be titled "A disproof of" ___ conjecture or "A proof that" __ conjecture "is false"?

How should that be capitalized in the title? (title case or just initial capital only). 92.229.12.100 (talk) 11:40, 19 October 2010 (UTC)

I would go with the first option, shorter titles are more catchy. As for capitalization, it does not really matter. If you are going to publish it, the journal will impose their house style anyway.—Emil J. 12:24, 19 October 2010 (UTC)

Actually, in the second title the "A proof that" part is redundant. You can call it just "__ conjecture is false".—Emil J. 12:33, 19 October 2010 (UTC)

So would you use "The ___ is false" or "Disproof of ____" / "A disproof of _____" ? 92.229.12.100 (talk) 14:03, 19 October 2010 (UTC)

Here's some examples of titles people have used in such circumstances: A counterexample to Borsuk's conjecture (Borsuk's conjecture), Two complexes which are homeomorphic but combinatorially distinct (Hauptvermutung), Disproof of the Mertens conjecture (Mertens conjecture), On Hamiltonian circuits (Tait's conjecture), and A disproof of a conjecture of Pólya (Pólya conjecture). Algebraist 14:54, 19 October 2010 (UTC)

Personnally (perhaps because I'm a little older?), I dislike both alternatives. "A counterexample to" in my ears is much better. One reason is, that a conjecture wasn't stated as a theorem. When you write "A disproof", in my (older) ears it sounds a bit like "Well, this guy thought that (s)he had more or less proved that statement; but I'm going to show that (s)he was wrong". A properly stated conjecture is nothing like a loosely `claimed fact'. The person(s) putting it are not proven to have made any kind of mistake, if the conjectured statement is proved to be false.

If you provide a counterexample to a "famous open conjecture", and your example is a correct counterexample, and correctly motivated, then your own fame is ascertained anyhow. The professionals will go for the mathematical content, not for the title; and in fact a title which does not overstate the result probably is the better.

Actually, there are even more understated formulations, which sometimes are better, like "A negative answer to a question by...". It does happen that a mathematician thinks (s)he did not make a conjecture, just pose an open question; and in such cases may be a bit irritated even over a title like "A counterexample to a conjecture by...". (I'm not even trying to imagine the reaction to a title like "A disproof of..." in such a situation.) You probably should check the original formulation of the problem, before you decide of the title.

If the statement first was stated as a theorem, but later the proof was found insufficient, then "A disproof..." could be appropriate, I think. JoergenB (talk) 18:41, 19 October 2010 (UTC)

Rectification

What is the origin of the term Rectification? What is the connection between the original sense of the term (action of setting right) and the action of cutting of corners of a polyhedron? --İnfoCan (talk) 20:12, 19 October 2010 (UTC)

The original sense of the term is not setting right, but setting straight (it is derived from Latin rectus). This is where another geometric term, rectification of curves, comes from. I don't quite understand how (or whether) this is related to cutting polyhedrons.—Emil J. 14:43, 20 October 2010 (UTC)

The link he gave, Rectification (geometry), explains quite clearly how the word applies to cutting polyhedrons. Use of the word is quite old, like most solid geometry. I don't think it's likely we can discover exactly who first used it this way. But it makes sense to think that it is derived from the use in rectification of curves; the diagram for a rectified curve suggests cutting off. 68.36.117.147 (talk) 01:43, 22 October 2010 (UTC)

I see no such explanation in the article. Can you point to it more precisely? –Henning Makholm (talk) 02:41, 22 October 2010 (UTC)

how does arXiv work, or help with peer review?

Hi,

The arXiv article says "the arXiv is not peer-reviewed", so how does putting an article on arXiv before publication help / how do you use arXiv for peer review? If I put a paper up, will I just get emails from people who happen to be interested, and is that what it is good for? Or, should I myself email people who might be interested, linking my arXiv paper, and hopefully they will give me valuable feedback? Or, how is arXiv supposed to be uesd?

Basically what I'm saying is that I'm kind of fuzzy about the difference between me->arXiv->Journal versus me->Journal... thanks! 92.230.234.134 (talk) 20:29, 19 October 2010 (UTC)

It doesn't help with peer review. It won't help to get your paper published. It's just a big electronic library for people to put their papers in order to aid the dissemination of knowledge. More people will get to read your paper and that will make you work known to a wider base. Hopefully that will increase possible collaborations and citations. Both of which are good for a long and successful academic career. — Fly by Night (talk) 20:44, 19 October 2010 (UTC)

Some journals have integrated arXiv to their submission system. E.g. if you want to submit a new paper to one of the Physical Review journals, all you have to do is give your arXiv preprint number. Putting a paper on the arXiv may get feedback from other authors who will advertise their papers to you (asking for you to cite their paper). It helps making your paper more visible and will lead to your paper being cited a lot more. That in turn will help you getting your next paper published, because a Referee will, of course, check if the sort of research you are doing is of interest. Having published a few papers with zero citations doesn't help here. Count Iblis (talk) 03:51, 20 October 2010 (UTC)

Two reasons to post on the arxiv: 1) peer review can take a looong time, but if you post something on the arxiv it appears the next (working) day, 2) in contrast to most journals, the arxiv is accessible freely to all. (Virtually) no quality control is applied to arxiv postings - lots of stuff on there is wrong/cranky, but it's a great way to get your work out there. Tinfoilcat (talk) 18:43, 20 October 2010 (UTC)

October 20

floor( exponential random variable ) = geometric distribution

How can I prove that if one takes the floor function of an exponential random variable it yields a geometric distribution? I've read in many places that it is really true, but I cannot find a proof, no matter how much I search. Thanks. --Belchman (talk) 20:51, 20 October 2010 (UTC)

Interpret the variable as time (in, say, minutes): since the distribution is memoryless, after a minute has passed, the chances of the event occurring in the second minute are the same as it had at the start of happening in the first minute. That the distribution of floors is geometric with the parameter equal to that minute's probability follows immediately. --Tardis (talk) 21:40, 20 October 2010 (UTC)

You can also use the direct approach: Let $X\sim \exp(\lambda ),Y=\lfloor X\rfloor \;\!$. Then

$\mathrm {Pr} (Y=k)=\mathrm {Pr} (k\leq X<k+1)=\int _{k}^{k+1}\lambda e^{-\lambda x}\ dx=e^{-k\lambda }(1-e^{-\lambda }).$

If you take $p=1-e^{-\lambda }$ then this is $(1-p)^{k}p$ which is a geometric distribution. -- Meni Rosenfeld (talk) 09:13, 21 October 2010 (UTC)

Thank you. Brilliant answers. --Belchman (talk) 18:47, 21 October 2010 (UTC)

October 21

Formula for converting solid volume to liquid volume

This may sound like a strange question but this has bugged me for a long time

is there a mathematical formula for predicting the change change in volume of substance after it changes states.

for example if i was to take a 5'x5' block of ice and melt it how would i estimate the volume of liquid water i would have?

thanks in advance —Preceding unsigned comment added by 209.167.165.2 (talk) 03:00, 21 October 2010 (UTC)

This is really more of a chemistry/physics question, but the ideal gas law is a good approximation to allow you to predict gas volume given the number of particles (equivalently, initial/solid mass or weight), atmospheric pressure, and gas temperature. There are of course more refined approximations if you're really interested, but it doesn't seem like that's what you're after. There are probably similar formulas for other states; I purposefully forgot the chem I learned :). 67.158.43.41 (talk) 05:11, 21 October 2010 (UTC)

Water is different from most other substances in that it expands when it freezes; a block of ice is approximately 10% larger, by volume, than the water it froze from (see Properties of water#Density of water and ice, in which this is explained in terms of density). So your 5′ × 5′ × 5′ block of ice (I assume you meant to have three dimensions there), which has a volume of 125 cubic feet, would melt into about 114 cubic feet of water. (Keep in mind that the volume of liquid water expands a bit as it heats up, too.) These calculations are specific to water, though—other substances behave differently. Most substances shrink when they freeze. —Bkell (talk) 05:31, 21 October 2010 (UTC)

Is Coefficient of thermal expansion relevant, or does that only apply when there's no change of state? Rojomoke (talk) 11:18, 21 October 2010 (UTC)

The thermal expansion coefficient assumes that the state is the same. It would not make sense to have one for state changes, since the phase change takes place without any change in temperature. –Henning Makholm (talk) 14:32, 21 October 2010 (UTC)

Bachmuth representation

I'm currently reading a paper of Chein ([1]), and he states that if F is the free group on three generators (a,b,c), and $\Phi =F/F''$ is the free metabelian group on three generators, then we can regard a,b and c as generators of $\Phi$, and we have a mapping sending

$a\mapsto {\begin{pmatrix}s_{1}&t_{1}\\0&1\end{pmatrix}},b\mapsto {\begin{pmatrix}s_{2}&t_{2}\\0&1\end{pmatrix}},c\mapsto {\begin{pmatrix}s_{3}&t_{3}\\0&1\end{pmatrix}},$

which induces a representation of $\Phi$ (where the $s_{i},t_{i}$ are commuting indeterminates in some ring R). Perhaps I'm being dense, but I don't see how this gives a homomorphism. I'm assuming there's something I'm not understanding about multiplication in $\Phi$. The problem I'm having is with the (1,2) entry of the image of, say, ab, which is $t_{1}t_{2}$, but in the product of the images of a and b, the (1,2) entry is $s_{1}t_{2}+t_{1}$.

Chein says that Magnus has proved this, but Magnus' paper is in German, and I've not managed to find an English translation. I've checked other sources, and they all agree that this map is a representation, but I just can't see it. Any help would be great, thanks, Icthyos (talk) 11:54, 21 October 2010 (UTC)

The multiplication reminds me of a semi-direct product. Not sure if it's just a coincidence, or not. — Fly by Night (talk) 12:12, 21 October 2010 (UTC)

No coincidence. If R is a ring, then the matrix group ${\begin{pmatrix}R^{\times }&R\\0&1\end{pmatrix}}$ is isomorphic to the semidirect product $(R,+)\rtimes (R^{\times },\cdot )$, where $R^{\times }$ acts on R by multiplication.—Emil J. 15:04, 21 October 2010 (UTC)

What makes you believe that the (1,2) entry in the image of ab is $t_{1}t_{2}$?—Emil J. 13:18, 21 October 2010 (UTC)

(e/c) Anyway: any function from {a,b,c} to any group G extends to a unique homomorphism f from F to G (that's the definition of a free group). In order to get a homomorphism from Φ to G, you need f to factor through the quotient map F → Φ, which happens if and only if Ker(f) includes F'', so one would need to check that. Alternatively, since Φ is the free metabelian group, it would suffice to check that G (or just the range of f as a subgroup of G) is metabelian. I can't tell how difficult is this to establish in your case, in fact, I don't even understand the description of the mapping. (What is an "indeterminate in a ring"? And when you write that "$s_{i},t_{i}$ are commuting", do you only mean that s_i commutes with t_i for every i=1,2,3, or that any pair of elements of {s₁,t₁,s₂,t₂,s₃,t₃} commutes?)—Emil J. 13:37, 21 October 2010 (UTC)

Oh, I see what you mean about the (1,2) entry, I don't know what I was thinking. Your statement about the unique extension of the homomorphism was one of the first things I learned about free groups, it should've been obvious. I agree that the map is not defined in a clear way. Another source I have (Lyndon & Schupp's "Combinatorial Group Theory", Chapter 1.4) defines the $s_{i}$ and $t_{i}$ as being 'independent invertible elements' in a commutative ring, R, which isn't really much better. Thanks for pointing out my mistake; I shall attempt to soldier on! Icthyos (talk) 14:12, 21 October 2010 (UTC)

I had a look on Chein's paper, and the description there is easier to understand: the elements are apparently taken in the rational function field $\mathbb {Q} (s_{1},s_{2},s_{3},t_{1},t_{2},t_{3})$ (or rather, its subring $\mathbb {Z} [s_{1},s_{2},s_{3},t_{1},t_{2},t_{3},s_{1}^{-1},s_{2}^{-1},s_{3}^{-1}]$). The only important point is that the ring is commutative (and the s_i are invertible). The mapping goes into the group G of matrices of the form $\left({\begin{smallmatrix}x&y\\0&1\end{smallmatrix}}\right)$, where x,y are elements of the ring, and x is invertible. Then the existence of the homomorphism is clear, since G is metabelian: when the matrices are multiplied, the (1,1) entry of the result is just the product of the individual (1,1) entries, which are taken in a commutative ring, hence G' only contains matrices of the form $\left({\begin{smallmatrix}1&y\\0&1\end{smallmatrix}}\right)$. The group of such matrices is commutative (they are multiplied by adding the y's), hence G'' is trivial.—Emil J. 14:32, 21 October 2010 (UTC)

Could you please provide the reference to Magnus'es paper? JoergenB (talk) 13:25, 21 October 2010 (UTC)

The reference to Magnus is [2], and Chein says Magnus proves that the above is a representation in Theorem 6.

He actually says that he proved it to be a faithful representation. I gather that the faithfulness is the hard part.—Emil J. 14:38, 21 October 2010 (UTC)

Actually, I found the Mathematische Annalen 111... and there Magnus is discussing a (superficially) quite different representation (working with finite upper left hand corners of certain upper triangular infinite matrices, seemingly). This could be slightly confusing.

I do not understand your discussions about in which rings to find the representations. In the definition on page 606, Chein just talks about commuting indeterminates (i. e., elements like the variables x and y in a polynomial expression such as $5x^{2}+3xy^{2}-y^{5}$), without complicating matters by embedding them in a ring of high enough transcendence degree; right? JoergenB (talk) 15:07, 21 October 2010 (UTC)

When one just refers to something as commuting indeterminates in a context asking for a ring, it is understood that one takes the ring of polynomials in said indeterminates (or simply the free commutative ring in these indeterminates, i.e., polynomials over Z). I'm not embedding anything anywhere, I'm using directly that polynomial ring (more or less: in this particular case, one obviously needs the s_i to have inverses, so plain $\mathbb {Z} [s_{1},s_{2},s_{3},t_{1},t_{2},t_{3}]$ is not enough). He actually explicitly refers to "$\mathbf {Z} (s_{1}^{\pm 1},s_{2}^{\pm 1},s_{3}^{\pm 1})$" on the next page.—Emil J. 15:26, 21 October 2010 (UTC)

Good; I agree with that. Ichtyos, did you essentially mean the same thing with

"which induces a representation of $\Phi$ (where the $s_{i},t_{i}$ are commuting indeterminates in some ring R)"? JoergenB (talk) 19:36, 21 October 2010 (UTC)

Yes; I was essentially just quoting Chein, but that's what I took him to mean.Icthyos (talk) 11:19, 22 October 2010 (UTC)

Thanks for the discussion, both of you! Icthyos (talk) 11:19, 22 October 2010 (UTC)

What is Mathematica doing?

So, I am putting an improper integral on a quiz, $\int _{-1}^{8}x^{-1/3}\,dx$, and I plugged it in to Mathematica to make sure I didn't make any mistakes. The answer Mathematica gave me was $6-{\frac {3}{2}}(-1)^{2/3}$, which is what I got. But, I then simplified $(-1)^{2/3}=1$, whereas finding the numerical form of this in Mathematica apparently picks a complex cube root of unity here. So, I tried plotting the function from -8 to -2 and Mathematica shows nothing at all, Plot[x^(-1/3), {x, -8, -2}]. Wolfram Alpha shows two graphs, one labeled real part and one labeled imaginary part. What's the deal? StatisticsMan (talk) 16:52, 21 October 2010 (UTC)

Just a guess, but it's probably doing the principal value. Basically, you can define a cube root function that behaves well except for when z is on the negative real axis. The value of the function on the axis depends on how you define it, but it would have to be one of the complex values. You might try breaking up the interval and using something like $-(-x)^{-1/3}$ where x is negative.--RDBury (talk) 17:41, 21 October 2010 (UTC)

(ec) Well, if you want $x\mapsto x^{-1/3}$ to make sense for nonzero complex numbers (you may not care, but how would Methematica know that?), and get the real branches for both positive and negative $x$, you need cuts in both the upper and the lower half-plane. It seems reasonable for Mathematica to always always use the same single cut (say, infinitesimally below the negative real axis) for all non-integral powers. That's the best you can do for almost all exponents anyway. If you want $(-1)^{y}=-1$ whenever $-1$ is a possible value, then $y\mapsto (-1)^{y}$ would need to be discontinuous on the entire real line. –Henning Makholm (talk) 18:08, 21 October 2010 (UTC)

The problem is that x^–1/3 is multivalued. Mathematica is using one of the complex roots as a solution. You should be able to tell it to work over the reals, or to assume that x is a real variable. — Fly by Night (talk) 17:49, 21 October 2010 (UTC)

The IEEE floating point standard treats the problem by having a special function rootn(x,n) where n has to be an integer. If you put in pow(-1,1/3) it would give an error. Dmcq (talk) 22:32, 21 October 2010 (UTC)

I put that equation into my TI-89 Titanium calculator and, after freezing up my calculator for about a minute or two, and saying "questionable accuracy," (to 4 floating points) it gave me 4.5. I am not a "math expert," so I couldn't begin to tell you if that's correct or not.

---WikiHelper46

what do we know about large primes?

we know they are odd. What other properties do they have? (other than the obvious one!) —Preceding unsigned comment added by 85.181.49.255 (talk) 17:31, 21 October 2010 (UTC)

All of the cool properties of division/multiplication. If you reverse the digits, it will not be divisible by 9. If you add the digits up (recursively until there is only 1 number left), it will not be 9. See divisibility rule for more. -- kainaw™ 17:55, 21 October 2010 (UTC)

(What kind of "property" are you looking for? Something like Fermat's little theorem? Or deterministic primality tests? Number theory is full of things that have been proved to be true specifically for primes. They are too numerous to list. –Henning Makholm (talk) 17:58, 21 October 2010 (UTC)

For a large prime, it is true that no positive integer other than 1 and itself divides it. That's a cool property shared by all large primes. Also, no large, odd prime is divisible by 3, 5, 7, 11, or 13 (saying they are odd is just saying they are not divisible by 2). StatisticsMan (talk) 18:08, 21 October 2010 (UTC)

For that matter, there are no large even primes that are divisible by 3, 5, 7, 11, or 13 either (I have a wonderful proof of this, which unfortunately is WP:OR). –Henning Makholm (talk) 18:12, 21 October 2010 (UTC)

No large prime is divisible by any positive integer other than 1 and itself; not just 3, 5, 7, 11, or 13. If it were then it wouldn't be prime! — Fly by Night (talk) 13:42, 22 October 2010 (UTC)

Well, the fact that only 1 and itself divides is what I meant above with "other than the obvious one". What I'm really interested is what Makholm has said "Number theory is full of things that have been proved to be true specifically for primes. They are too numerous to list." Surely he could have listed like 10 of them!! I am really interested in things that are going to be true for large primes, but not for every large number, other than the fact that they have two factors... 85.181.49.255 (talk) 18:49, 21 October 2010 (UTC)

So things like Fermat's little theorem, Wilson's theorem, Goldbach's conjecture, the prime number theorem, or the fact that the order of every finite field is a power of a prime? You can find more in Category:Prime numbers. —Bkell (talk) 19:08, 21 October 2010 (UTC)

OK, let us list 10 random prime properites:

1. Fermat's little theorem.
2. Wilson's theorem.
3. Euclid's lemma
4. Primes are the only nonzero numbers that can be the characteristic of a field.
5. Primes are the only numbers such that two finite groups with this many elements are necessarily isomorphic.
6. The Sylow theorems
7. Eisenstein's criterion
8. Only if p is a prime will the p-adic numbers be a field (rather than a ring).
9. Quadratic reciprocity
10. Touchard's congruence

–Henning Makholm (talk) 02:35, 22 October 2010 (UTC)

The Finite group article gives infinitely many counterexamples to #5: Every group of order pq is cyclic when q < p are primes with p-1 not divisible by q. Matthew Auger (talk) 11:07, 22 October 2010 (UTC)

Ooops! –Henning Makholm (talk) 14:58, 22 October 2010 (UTC)

They are hard to factor, which is the basis of RSA encryption. They get rarer and rarer as a consequence of the prime number theorem. 67.158.43.41 (talk) 22:23, 21 October 2010 (UTC)

Actually primes are very easy to factor. If you give me a large prime I'll factor it for you immediately, even without a computer. :-) —Bkell (talk) 22:39, 21 October 2010 (UTC)

I bow down to you. I'm not worthy. :) --Kinu ^t/_c 22:42, 21 October 2010 (UTC)

Haha, whoops. I of course meant numbers "near" them are hard to factor, ex. pq for large primes p and q., Interestingly, though, primality testing is "easy" inasmuch as it can be done in polynomial time in the number of digits in the input using the AKS primality test. That is, you can test whether or not a given large number is prime "quickly". 67.158.43.41 (talk) 00:19, 22 October 2010 (UTC)

Bertrand's postulate is an interesting property, there's another prime below 2p. 22:38, 21 October 2010 (UTC)

The primes contain arbitrarily long arithmetic progressions, which usually occur for very large primes; see the Green–Tao theorem. —Anonymous Dissident^Talk 22:48, 21 October 2010 (UTC)

According to http://primes.utm.edu/largest.html, some large primes are Mersenne primes.

—Wavelength (talk) 01:04, 22 October 2010 (UTC)

Depends on your definition of 'large'. There may be no 'large' Mersenne primes if they are finite in number. Dmcq (talk) 10:01, 22 October 2010 (UTC)

All primes are small, because most primes are bigger. Bo Jacoby (talk) 12:25, 22 October 2010 (UTC).

If you take all the prime numbers, square them, take the reciprocal of the numbers, take one minus these numbers, and then multiply all the numbers, you get exactly 6/pi^2:

$\prod _{p}\left(1-{\frac {1}{p^{2}}}\right)={\frac {6}{\pi ^{2}}}$

Count Iblis (talk) 15:01, 22 October 2010 (UTC)

The OP's question may have been better than I though at first. I understand it to ask for properties of each prime individually, that is, something you can do with a singe large number that happens to be prime. Most of what people suggest here are interesting properties of the set of all prime numbers in general. I really had to reach to fill out the 10 properties I quote above without including properties that are trivial rephrasings of each other (and one of them even turned out erroneous, stupid me). It seems to be hard to get very far when you cannot even use the fundamental theorem of arithmetic (which is a collective property of all the primes, rather than a property of each prime individually). –Henning Makholm (talk) 15:18, 22 October 2010 (UTC)

If the OP's question was really, what is the practical use of knowing that some medium-large number (with, say, hundreds of digits) is prime, then the best answer may be to point to the use of prime numbers in various public-key cryptography schemes. The most significant mathematical underpinnings of these seem to be variations on Fermat's little theorem, the theory of finite fields, and in particular the assumed difficulty of computing discrete logarithms. –Henning Makholm (talk) 15:33, 22 October 2010 (UTC)

October 22

Polynomial degree vs order

Reading both Wikipedia and Wolfram I see that order and degree can be used interchangeably. But I was fairly certain that when I researched the same thing about 5 years ago the definitions were slightly different. In the next paragraph I do not state a fact, I am simply stating my previous (most likely erroneous) understanding.

I remember the "degree" being defined as the exponent of the highest order term, so a parabola would be 2nd degree. The order (and this is where I'm confused) was defined as the number of variables in the particular class of polynomial, so a general parabola would be 3rd order. A general 2nd degree polynomial of the form a*x^2 + b (no linear term), would be 2nd order.

Was it once defined like this or must I have been getting bad information?

196.211.175.2 (talk) 09:56, 22 October 2010 (UTC) Eon

The words degree and order are used interchangeably, according to degree of a polynomial. Bo Jacoby (talk) 12:37, 22 October 2010 (UTC).

I don't recall seeing the definition of order you described. But it's very possible that this definition is common in a particular place or you've seen it used by a particular author. -- Meni Rosenfeld (talk) 13:58, 22 October 2010 (UTC)

I've always used the word "degree" for things like the exponent in x³, and said that the degree of a polynomial is the exponent of the highest-degree (not highest-order) term. "Order", on the other hand, I use for differential operators; thus one can speak of a second-order differential equation. I think that's the way I was taugth to use those terms in school. But I know that in some eras the word "order" has been used the way I use the word "degree", and that some people are not fastidious. Michael Hardy (talk) 18:43, 22 October 2010 (UTC)

typesetting a long stream of numbers in Latex?

How do I typeset 114813069527425452423283320117768198402231770208869520047764273682576626139237031385665948631650626991844596463898746277344711896086305533142593135616665318539129989145312280000688779148240044871428926990063486244781615463646388363947317026040466353970904996558162398808944629605623311649536164221970332681344168908984458505602379484807914058900934776500429002716706625830522008132236281291761267883317206598995396418127021779858404042159853183251540889433902091920554957783589672039160081957216630582755380425583726015528348786419432054508915275783882625175435528800822842770817965453762184851149029376 so that it wraps and stuff? It just goes off the edge of the page now, so that only one line is visible... 84.153.179.167 (talk) 13:52, 22 October 2010 (UTC)

Insert \allowbreak in places where you want to allow it to break. You'd probably also need to mark the paragraph with \raggedright, as there will be no stretchable spaces on the lines.—Emil J. 14:14, 22 October 2010 (UTC)

If you want to allow a line break after every digit, and if you need to do this repeatedly, here's a macro:

\def\longnumber#1{\raggedright$\dolongnumber#1\stop}
\def\dolongnumber#1{\ifx\stop#1$\else#1\allowbreak\expandafter\dolongnumber\fi}

\longnumber{1148130695274254524232833201177...965453762184851149029376}

—Emil J. 14:28, 22 October 2010 (UTC)

Now I wonder: does anyone have a clue why the syntax highlighter coloured the first occurrence of "#1" black, the second one pink, and the other three blue?—Emil J. 15:19, 22 October 2010 (UTC)

I think it is confused by the (apparently) unpaired dollar signs. The anomaly changes somewhat if I replace them with \begin{math} and \end{math}, and goes away if I remove them completely. –Henning Makholm (talk) 15:40, 22 October 2010 (UTC)

I see. Thank you.—Emil J. 16:40, 22 October 2010 (UTC)

With hindsight, the \raggedright was a bad idea, as it spill over to subsequent paragraphs, and cannot be easily confined. Here is a better implementation:

\def\longnumber#1{$\dolongnumber#1\stop}
\def\dolongnumber#1{\ifx#1\stop$\else#1\allowbreak\hskip0pt plus.5pt\expandafter\dolongnumber\fi}

\longnumber{1148130695274254524232833201177...965453762184851149029376}

It inserts a slightly stretchable space after every digit to allow proper justification. Here's the same kind of thing with a bit of syntactic trickery:

\def\longnumber{\def\relax##1{##1\allowbreak\hskip0pt plus.5pt\relax}\relax}

$\longnumber1148130695274254524232833201177...965453762184851149029376$

—Emil J. 13:55, 25 October 2010 (UTC)

Redefining \relax is very much asking for trouble, even though it happens to work safely in the intended use case. It won't work with LaTeXy \begin{math}/\end{math}, nor for a primitive $$display$$. –Henning Makholm (talk) 15:38, 25 October 2010 (UTC)

That's why I called it a trickery, it's basically for fun, and it's designed to work only in the exact way I used above (a sequence of digits between single dollars). If that's a problem, use the previous solution (which however also relies on some assumptions on the token sequence in its argument, it won't process correctly stuff like \longnumber{123\bar{4}567}). If I were serious about it I'd also define a skip register for that "0pt plus .5pt".—Emil J. 15:57, 25 October 2010 (UTC)

if you had to brute-force a number but could be told some of the digits

If you had to brute-force a number but could be told some of the digits, would you rather have the n most significant or the n least significant digits - or wouldn't it make a difference? —Preceding unsigned comment added by 93.186.23.239 (talk) 14:07, 22 October 2010 (UTC)

If you do not know (or suspect) anything else about the number, it makes no difference. If you do, it depends on the other expected properties of the number.—Emil J. 14:37, 22 October 2010 (UTC)

all right, you're trying to factor a large composite number into its exactly two large random primes, and I'm telling you about the n most or least significant digits of the larger of them. Is the only reason you would prefer the former that the last digit is odd, so you already have slightly more information about it? Or would you have any other reason to prefer one over the other? Thank you.

You also know that it is coprime with 5 (if the digits are decimal digits). This is already a good reason (just oddness of primes essentially halves your search space if given the most significant digits), but I would also prefer the most significant digits because then the brute force requires me to sieve primes out of an interval, which is somewhat easier then to sieve them from the set of numbers with given ending (however, this is only relevant if you are really going to find the factors by brute force; if you are using a more sophisticated factoring algorithm, it may have quite different preferences as to which extra information on the factors is more useful, and it may well happen that it cannot use either of them).—Emil J. 15:37, 22 October 2010 (UTC)

I am struggling to see how you can say anything useful about the factorisation of the number if you are only told some of its digits and that it is a semiprime. For example, if you know the number is 1231x, it could be 13 x 947 = 12311, or 7 x 1759 = 12313 or 109 x 113 = 12317 or 97 x 127 = 12319. Gandalf61 (talk) 16:04, 22 October 2010 (UTC)

No, that wouldn't be an example of the kind the OP is describing. An example may be that you need to factor 12317 and know that one of the factors is 11x. –Henning Makholm (talk) 16:19, 22 October 2010 (UTC)

Yes (OP here, my IP has changed though) . If you were trying to factor 5725797461 would you rather know that the larger of them begins 75... or ends ...679 -- you only get to learn one of these things. Extrapolating, would you rather learn the first or the last hundred digits of a 1000-digit prime factor of an even larger composite number you were trying to factor into its exactly two large prime factors? 84.153.222.131 (talk) 18:03, 22 October 2010 (UTC)

Quotients

Resolved

I'm looking for a command in either Maple or Maxima to compute the quotient of a polynomial ring by a gradient ideal. I can do some simple examples by hand, but I don't know a general method. For example, let ƒ(x,y) = x² + y^k where k is a positive integer. I have

${\mathcal {A}}=\mathbb {R} [x,y]/\left\langle f_{x},f_{y}\right\rangle =\mathbb {R} [x,y]/\langle x,y^{k-1}\rangle \cong \mathbb {R} \langle 1,y,y^{2},\ldots ,y^{k-2}\rangle .$

Provided that the gradient vector field has an algebraically isolated zero at x = y = 0 the result will be a finite dimensional real vector space. Algebraically isolated zero means that the zero is isolated when x and y are considered as complex variables, and not just real. For example, can anyone calculate the vector space (called the local algebra) when ƒ(x,y) = x³ + xy^k?

${\mathcal {A}}=\mathbb {R} [x,y]/\left\langle f_{x},f_{y}\right\rangle =\mathbb {R} [x,y]/\langle 3x^{2}+y^{k},xy\rangle \cong \ldots \ ?$

More importantly, does anyone know a command in either Maple or Maxima to compute the quotient? — Fly by Night (talk) 15:10, 22 October 2010 (UTC)

I know what an ideal is, and I know what a gradient is, but what is a "gradient ideal"? Neither article so much as mentions the other word. –Henning Makholm (talk) 15:46, 22 October 2010 (UTC)

The thing in the denominator of my quotients above. For a function ƒ : Rⁿ → R the gradient ideal of ƒ is given by

$I_{f}:=\left\langle {\frac {\partial f}{\partial x_{1}}},\ldots ,{\frac {\partial f}{\partial x_{n}}}\right\rangle .$

It should really be thought of as an ideal in the ring of analytic function germs, but you can get away with thinking of R[x,y] instead. It's quite a common term. Google Scholar returns about 140 hits. — Fly by Night (talk) 15:54, 22 October 2010 (UTC)

It confused me that it looked as if "gradient ideal" was linked to something that ought to explain that particualar construction. Also, I'm not used to the angle bracket notation here; the texts I grew up with used round parentheses for "the ideal generated by such-and-such". –Henning Makholm (talk) 16:09, 22 October 2010 (UTC)

Ah, I see. Looking around on Google seems to show a mixture of rounded and angled brackets for the gradient ideal. Maybe it's not common in traditional ring theory, but the gradient ideal is an application of ring theory to another subject. So you'd have non-ring-theorists using rings and ideals. Maybe that would explain the non-familiar notation. — Fly by Night (talk) 17:59, 22 October 2010 (UTC)

In your example $\mathbb {R} [x,y]/\langle 3x^{2}+y^{k},xy\rangle$: When you quotient out (xy), all mixed terms drop out, so you have, R(1,x,y,x²,y²,x³,y³,...) left. Now quotient out (3x²+y^k). Then you can rewrite y^(k+1) as -3x²y which drops out because xy=0. Similarly, x³=x(-1/3)y^k=0. Then you're left with R(1,x,x²,y,y²,...,y^k), but x² is (-1/3)y^k, so your final space is R(1,x,y,y²,...,y^k).

This is hardly an example of a general method, of course. And the multiplicative structure of the quotient ring is lost when you write it simply as a vector space, but I suppose that is what you want? –Henning Makholm (talk) 16:09, 22 October 2010 (UTC)

It's a method to calculate the index at a singular point of a gradient vector field. You work out the quotient and then make a multiplication table of the spanning elements. You fill it in, modulo the gradient ideal. Then you find a linear map that takes the class of the determinant of the Hessian of ƒ to 1. The simplest one would send [det(Hess_ƒ)] to 1 and every other class to 0. This maps changes the k-by-k multiplication table into a k-by-k matrix. The signature of which is the index of the singular point of the gradient vector field. See here if your interested. (N.B. They use round brackets for ideals in this article.) — Fly by Night (talk) 18:12, 22 October 2010 (UTC)

You might want to try the SINGULAR CAS. I believe that it specialise in this sort of calculation.--Salix (talk): 19:44, 22 October 2010 (UTC)

I've just looked at the website, and it looks perfect. Thanks a lot Salix. I shall download it now. — Fly by Night (talk) 20:04, 22 October 2010 (UTC)

Scenario: Traveling to Pandora as seen in James Cameron's movie Avatar

I've been trying to figure out how long it would take to get to the fictional moon Pandora from Earth in the movie Avatar—at a specific faster-than-light speed—, but the unit conversions have been tedious. My problem is based on a few assumptions and definitions. I've laid them out as follows:

• Assumptions & Considerations:
  • Assume that fast than light travel is possible.
  • Either assume that time dilation does not occur or is not a concern.
  • Either assume that I'm not killed by the speed or that it is not a concern.
  • Assume their is no need for acceleration/deceleration time.
• Definitions:
  • The distance from Earth to Pandora is 4.37 light years.
  • One year is 31,557,600 seconds.
  • The speed of light is 186,282.397 miles per second.
• Givens:
  • The speed I'm traveling at is 5 trillion miles per nanosecond.
• Problems:
  • I would like the speed converted to miles per second—no rounding please.
  • I would like to know how long it would take me to get their—no rounding please.
  • I would like a real world comparison as to how quick that time is (example, 0.25 seconds is the blink of an eye).

--Melab±1 ☎ 19:02, 22 October 2010 (UTC)

Google is neat for unit conversions: 4.37 light years / 5e12 miles/ns, assuming short-scale trillions. –Henning Makholm (talk) 19:16, 22 October 2010 (UTC)

Thank you, but I need all three of my problems answered and I also do not know if Google's unit conversions use the definitions I have defined. --Melab±1 ☎ 19:48, 22 October 2010 (UTC)

Well, OK. 5 trillion is usually 5x10¹², and this occurs 10⁹ times per second, giving an exact speed of 5x10²¹ miles per second. At your definition, a light year is 5.87862537 x 10¹² miles (for a standardised definition, see light year). That makes a total distance of 2.56895929 × 10¹³ to a level of accuracy that's only true if Pandora was exactly 4.37 light years away. Divide the latter by the former, and you get 5.13791857 nanoseconds. That's less than the time it takes light to cover two metres, to give an example. That really short period of time is quite hard to quantify in everyday terms. Hope I've done this right, - Jarry1250 ^{[Who? Discuss.]} 20:23, 22 October 2010 (UTC)

I agree with the above calculations. Mine are... 5 trillion miles per nanosecond = 5*10^12 miles / (10^-9 sec) = 5*10^21 miles / sec = 5,000,000,000,000,000,000,000 miles / sec. 4.37 light years * 31,557,600 seconds / year * 186,282.397 miles / second = 5,878,625,371,567.2 miles * 4.37 = 25,689,592,873,748.664 miles. Distance = rate * time, so time = distance / rate (using the nonrelativistic approximation you seem to want). Here, travel time is 25,689,592,873,748.664 miles / (5*10^21 miles / sec) = 0.0000000051379185747497328 sec = 5.1379185747497328 nanoseconds. For scaling, about 5.14 nanoseconds in a second is the same ratio as about 2.5 minutes in a millenium. It should be noted that you're asking us to use wayyyyy too many significant figures in these calculations, and the speed is incredibly high. 67.158.43.41 (talk) 05:00, 23 October 2010 (UTC)

But faster than light travel isn't possible. Traveling exactly at the speed of light isn't possible either, unless you have zero mass or infinite energy: your mass increases with respect to your speed, so the faster you go the more energy you need to go faster. Close to the speed of light you would need almost infinite amounts of energy to accelerate your almost infinite mass. See this section of the Special Relativity article. Some theories hypothesise about anti-particles with negative mass travelling faster than the speed of light. Why don't you just assume the speed to be s, and the distance to by d? — Fly by Night (talk) 10:01, 23 October 2010 (UTC)

Generalization of ordinals

In ZFC, ordinals are equivalence classes of sets, since every set can be well-ordered in ZFC. In ZF+~AC, there are sets that cannot be well-ordered. Is there any way to organize these sets into equivalence classes that provide some notion of size similar to the ordinals? 99.237.180.170 (talk) 19:07, 22 October 2010 (UTC)

I'd quibble with the way you put it. There's no such thing as "sets in ZFC" or "sets in ZF+~AC"; there are only sets, and AC is either true of them, or it is not.

That said, yes, you can certainly get objects corresponding to cardinality, working in ZF alone. What you do is take equivalence classes up to the existence of a bijection. Unfortunately these are proper classes, so you use the Scott trick to cut them down to sets. --Trovatore (talk) 19:13, 22 October 2010 (UTC)

I think your terminology quibble is more Platonic than the mainstream mathematical culture makes it fashionable to be. But in that case, if you accept that the ZF axioms are true, then both of ZFC and ZF¬C will be consistent and thus have models. And the elements of such a model's universe are usually known as "sets" in that model, even though you may prefer to reserve the word for something more metaphysical. –Henning Makholm (talk) 19:31, 22 October 2010 (UTC)

Well, those objects are sets in the sense of the model, not in the sense of the theory. It's a critical distinction. --Trovatore (talk) 21:08, 22 October 2010 (UTC)

Like Henning Makholm, I stand by my original use of the word "sets." I don't see what you mean by "sets in the sense of the theory." To me, sets are objects described by the axioms of a set theory. I did consider using cardinality as you suggested, but I was hoping for something more specific. Maybe something with another axiom added to ZF¬C might work better for my purposes. Any more suggestions? 76.67.74.196 (talk) 22:04, 22 October 2010 (UTC)

The correct phrasing is ZFC proves that every set can be wellordered, not every set can be wellordered in ZFC. --Trovatore (talk) 23:17, 22 October 2010 (UTC)

I suspect what you mean is the correct phrasing is

"{Every set can be well-ordered} in ZFC

rather than

"Every set can be {well-ordered in ZFC}.

(The latter being meaningless.) Michael Hardy (talk) 16:57, 23 October 2010 (UTC)

No, I really don't. The mathematical standard is to talk like a Platonist whether you actually are one or not. This saves an immense amount of grief when it comes to things like expositions of the incompleteness theorems.

It's far cleaner in such cases to use the standard language, where a flat assertion of a statement is the same as the claim that the statement is true (disquotational truth) rather than provable. Then you can always make some sort of disclaimer afterwards about what interpretation you really have in mind. --Trovatore (talk) 17:49, 23 October 2010 (UTC)

This discussion is getting pretty far off topic. Returning to the original answer, doesn't the definition of the cardinal numbers depend on the ordinal numbers through cardinals like $\beth _{\omega }$, $\beth _{\omega +1}$, and $\beth _{2\omega }$? How can you name cardinals without the axiom of choice? Are the cardinals defined as equivalence classes, but they cannot be enumerated without the AC? 74.14.109.58 (talk) 20:01, 23 October 2010 (UTC)

No, without the AC there is no systematic enumeration of the cardinals; you cannot even always compare two cardinals to see whether one is larger than the other (the AC is equivalent to trichotomy between cardinals). Without AC there is no better general way of naming a cardinal than to exhibit a set (or many sets) of the cardinality you want to speak of. –Henning Makholm (talk) 20:12, 23 October 2010 (UTC)

A useful proxy in some contexts for such cardinalities is the notion of Borel reducibility of equivalence relations. If equivalence relation E is reducible to equivalence relation F, then the quotient space by E has cardinality less than or equal to the quotient space by F. See Borel equivalence relation for a bare start. An article I had ambitious plans for at one time but never got around to really developing. --Trovatore (talk) 20:17, 23 October 2010 (UTC)

Shoelace formula

Why does the shoelace formula work? --75.33.217.61 (talk) 19:59, 22 October 2010 (UTC)

Our article Shoelace formula explains (um, no it doesn't, but one easily sees that it is the case) how the formula can be expressed as a sum of cross products where each can be seen to be ±2 times the area of the triangle formed by the origin and two successive vertices.

The easiest case to convince onself of is when the polygon is convex and that the origin lies inside it. Draw lines from each vertex to the origin; this cuts it into a number of triangles that each corresponds to a cross product in the formula, and all of the cross products have the same sign.

For general polygons, the easiest approach may be to cut the polygon into triangles, and then show by induction on the number of triangles that the formula works and that the sum of the cross products is positive if the vertices are taken in clockwise (or is it anticlockwise? Never mind, one of them will turn out to work) order around the polygon. The base case for a single triangle is just a matter of calculation (the area of triangle ABC is ${\frac {|(B-A)\times (C-A)|}{2}}$, and the numerator can be rewritten using the distributive and anticommutative laws for the cross product, to give just the terms in the shoelace formula). In the induction case, add one triangle that shares one or two edges with the polygon you already have; the cross products corresponding to the shared edges will cancel each other out. –Henning Makholm (talk) 20:20, 22 October 2010 (UTC)

Reducing Transformation Arrays

Hi all, I'm looking for a way to reduce N 'transformation arrays' to a single transformation array without running through each individual transformation. Here's an example:

Given the alphabet, alpha = "abcd" and the transformation array, t1 = [4, 3, 2, 1]:

f(alpha, t1) = "dcba"

given t2 = [4, 2, 3, 1]

f(f(alpha, t1), t2) = "acbd"

So the first transformation we did was [4, 3, 2, 1] and the second was [4, 2, 3, 1] and the result was [1, 3, 2, 4]

I'm looking for a function, let's call it g(t1, ..., tN) to compute this. For instance:

g([4, 3, 2, 1], [4, 2, 3, 1]) = [1, 3, 2, 4]

Ideally I'd like for g(t1, ..., tN) to have a time complexity of O(n). If I actually do each of the transformations I can achieve O(n*m) where m is the length of the alphabet; thus, a time complexity of this, or worse, won't really help.

I'm not entirely sure if such a function can (does?) exist, but any ideas would be much appreciated!

Thanks!

24.147.249.232 (talk) 20:59, 22 October 2010 (UTC)

You cannot do better than O(nm); otherwise you don't have time to read all of the inputs!

(By the way, what you're referring to as a "transformation" is commonly known as a permutation) –Henning Makholm (talk) 21:06, 22 October 2010 (UTC)

Oh. Good point! I suppose a better question would be what's the optimal way to compute g(...)? I was hoping for a method where I could apply simple operations to each element, but that seems unlikely. The best method I've come up with, thus far, is (apologies for the poor pseudocode formatting!):

for(i in 0..m)

for(j in 0..n)

ndeck[j] = deck[permutations[i][j]]

deck = ndeck

Which is okay, but could be a lot faster if the last copy step didn't need to occur. Thus, perhaps my original question should have asked whether it's possible to do that innermost step in-place.

24.147.249.232 (talk) 22:16, 22 October 2010 (UTC)

Is this really the critical part of your entire program? Remember, premature optimization is the root of all evil. If it is critical, I would suggest unrolling the outer loop twice and shifting back and forth between two arrays:

for(i in 0,2,4,...,m-1)

for(j in 0..n)

decka[j] = deckb[permutations[i][j]]

for(j in 0..n)

deckb[j] = decka[permutations[i+1][j]]

Alternatively, you might also try to trace each element backwards through the permutations:

for(j in 0..n)

k = j

for(i in m..0)

k = permutations[i][k]

outj] = k

which seems to faster under an unit cost model, but is likely to have horrible cache locality. –Henning Makholm (talk) 23:00, 22 October 2010 (UTC)

Does the last copy step need to occur? It obviously depends on what goes on to be done with it and how modularised your code as a whole is, but if you've got space in memory for both deck and ndeck, can't you just carry on using ndeck once you're on the other side of the loop?

Thinking about it from another direction, would some recursion help? If you had a function to work out the end product of applying two re-orderings sequentially (even on a dummy "initial order" which you could then sub in your real data for at the end), you could just keep piling in pairs: t1 and t2, t3 and t4 ... up to tN-1, tN. Then you do it again to (the result from doing t1t2) and (the result from doing t3 and t4), etc. until you finally end up at the eventual answer. Obviously this is easiest to work for N a power of 2, but it's not difficult for some other N. Then again, that's probably only any practical use in speeding things up if you've got access to a parallel architecture where you can do all the initial pairs in parallel and then gradually bring them together. (So you use N/2 processes in your first go round, then N/4, then N/8 etc.) I'm rusty on all this, but it feels like it ought to be possible. --81.153.109.200 (talk) 10:36, 23 October 2010 (UTC)

GMAT scoring system

This page seems as good as any for my question, so here goes: On the math portion of the GMAT[3] I scored 50/95th percentile. Had I answered the last question correctly (it was not very hard; I had made my choice and was ready to press Next), was it probable that I might've raised my score? Thanks. 67.243.7.240 (talk) 21:31, 22 October 2010 (UTC)

I presume that by "50/95" you mean a score of 50 at the 95th percentile. You can see in the link you provided how an extra mark would increase the percentile score, assuming that you get one mark per correct answer. 92.24.178.5 (talk) 11:03, 23 October 2010 (UTC)

I don't know that one gets "one mark per correct answer"; thus my question hoping someone knows. 67.243.7.240 (talk) 23:48, 24 October 2010 (UTC)

Logic - deduction of axioms

Is it possible to deduce $\neg \neg p\Rightarrow p\,\forall \,p$ from $p\Rightarrow (q\Rightarrow p)\,\forall \,p,\,q$ and $(p\Rightarrow (q\Rightarrow r))\Rightarrow ((p\Rightarrow q)\Rightarrow (p\Rightarrow r))\,\forall \,p,\,q,\,r$? I'm studying on a logic theory course and I've been asked whether it is possible to deduce the third axiom we use from the first two? I strongly believe it isn't because otherwise we wouldn't need to take it as an axiom, but I'm not sure how to go about showing it. I know of most of the basic theorems by now (deduction, completeness etc), but I can't see any obvious way to get there. Could anyone please suggest anything? Thankyou, 62.3.246.201 (talk) 23:20, 22 October 2010 (UTC)

A typical way to prove that one axiom does not follow from the others, would be to exhibit a non-standard interpretation of the connectives that makes the two latter axioms (K and S, among friends) into tautologies but the first one into a non-tautology (while tautologies are still closed under whatever inference rules you have, such as modus ponens). This should be particularly easy because the two axioms you assume do not mention ¬ at all, so the only thing you need from an alternative truth table for ¬ is that it makes $\neg \neg p\rightarrow p$ into a non-tautology. –Henning Makholm (talk) 23:39, 22 October 2010 (UTC)

I'm sorry, I don't quite follow - what do you mean by 'exhibit a non-standard interpretation of the connectives'? Thankyou for the help :) 131.111.16.20 (talk) 11:53, 23 October 2010 (UTC)

Okay, let's take it more slowly then. A general method to show that some wff A cannot be proved from B, C, D is to define some set S of "special" well-formed formulas such that

1. B, C, D are all in S
2. A is not in S
3. For each rule of inference (such as modus ponens, which I suspect is actually the only one you have at the moment), if the rule allows you to infer a wff from wffs in S, then the wff you infer is also in S.

Then it's quite easy to show that no formal proof can ever contain a wff outside S, and in particular there's no formal proof that concludes A. (This ought to remind you of how soundness of the proof system was shown, where S was taken to be "all logically valid wffs").

I assume that by this point you have seen truth tables for ¬ and → and learned how to use them to determine whether a given formula is a tautology. My suggestion is then to invent your own crazy truth tables for the symbols, and then let S be all of those wffs that would have been "tautologies" under your crazy truth tables. –Henning Makholm (talk) 15:11, 23 October 2010 (UTC)

The axioms describe properties of the logical symbols $\neg$ and $\Rightarrow$. If you can find an interpretation that is true under two of the axioms, but not under a third, you have shown that the third does not follow from the other two. Try e.g. a three-valued logic. --Stephan Schulz (talk) 12:06, 23 October 2010 (UTC)

So just to be clear, there's no way to do this without going outside the realms of the 2-valued (just true/false) logic? I only ask because I'm being asked this question having been taught nothing but 2-valued logic on the course so far with no mention of other possibilities - basically we have covered basic propositional logic such as valuations, truth-tables (with only the values 0/1), the deduction, completeness, soundness, adequacy, Moor existence lemma, compactness and predictability theorems, the 3 axioms above and the deduction rule modus ponens. (I don't know how many of these things are course-specific and how many are widely known by these names so sorry if any of those sound unfamiliar!) I would usually happily read ahead on these things and I don't mean to sound glib or anything like that, it's just we've only been lectured on this material from scratch for the past 2 weeks (though I need to get my head around this for work due in just a week!), so I presume there must be some way to prove this using just 2-value logic - if that's what you meant Henning then please say, it's quite possible I misunderstood! Thankyou both for your patience, and if you can direct me to something I can read up on this via, rather than having to explain every step to a complete beginner (must be quite tiresome for you!) then I'd be very happy to do so, I'm just concerned I'm missing an easier way of doing this. Perhaps our lecturer expects us to deduce higher-valued logic for ourselves, it just seems a bit unlikely... Thanks again! 131.111.185.68 (talk) 21:01, 23 October 2010 (UTC)

The solution I have in mind does indeed stay within two values. It is a fairly standard technique, but by no means the only way to reach the goal, so there may or may not be hints in your text that point in another direction. (With the hints I've given so far, there are only 63 possible truth-table combinations to try out, most of which can be eliminated quickly, and all of which will yield to brute force. So you're not lost, though you might end up bored out of your skull unless you can think of a smarter way to home in on the right one).

The trouble with pointing to "something you can read up on" is that it is hard to know what will work for you better than the text you're already studying. Also it wouldn't do to simply point you to a complete solution; that way you would miss the learning experience of figuring it out yourself. (Except that it probably wouldn't work for exactly the same definitions your text is using. There are many slightly different ways to do formal logic, and they are all easily seen to be fairly unimportant variations of the same thing once you understand them in the first place. But until you get that basic understanding, it is best not to confuse oneself too much with alternative sources).

You syllabus so far sounds fairly standard, though the names "Moor existence lemma" and "predictability theorem" do not register with me. –Henning Makholm (talk) 22:01, 23 October 2010 (UTC)

Okay, I think I grasp the concept now - the 'not' and 'implies' symbols are literally just that - symbols. We can assign whatever meaning to them we want (we could say not(p) is always equal to 1, no matter what p, or not(p) has the same value as p, say): the reason I was finding it so hard was that I was retaining the meaning I'm used to for them, i.e. 0 implies 1 is true, 1 implies 0 is false, etc, rather than seeing we can define the values of p implies q, and not(p), to be whatever we want, and we just want to find a definition for which our 2 axioms and modus ponens are always tautologies (true no matter what values p,q,r take) and for which not(not(p)) implies p is -not- always true. So then, could we take implies under its normal meaning (always one except for 1 does not imply 0), given that we know this should make our 2 axioms and MP true (they do not involve the 'not' symbol so our definition of it is irrelevant with regards to these axioms), and take 'not' as not(p)=0 for p=0 or 1? So then not(not(1))=not(0)=0 which does not imply 1=p? 131.111.185.68 (talk) 01:41, 24 October 2010 (UTC)

Almost there, except 0→1 is 1. But 1→0 is 0. Nudge, wink. –Henning Makholm (talk) 02:28, 24 October 2010 (UTC)

Oh well, you can surely fix that one last mixup, so I'll pretend you that you've solved the problem, and feel free to point you to intuitionistic logic which explores what happens if one refuses to accept ¬¬p→p as an axiom. It turns out to be not quite as crazy as one would think at first; you may find it interesting. (Or it may make your head asplode, in which case don't sweat it. It usually takes several tries getting used to). –Henning Makholm (talk) 02:33, 24 October 2010 (UTC)

Ahh gotcha, so setting not(p)=1 and p=0, we get not(not(1))=1 which does not imply 0=p :) Thankyou so much for being so patient with me, I definitely owe you one! I will have a look at intuitionist logic the next time I'm feeling brave, all this is a bit of a brain-melter to say the least. Thanks again! Out of interest, where do the 'K' and 'S' ("among friends...") come from? Is there a list of standard axioms somewhere, each assigned a letter for conciseness or something like that? 131.111.185.68 (talk) 10:41, 24 October 2010 (UTC)

Hmm, after I've checked various sources, it may actually only be a small select circle of friends who call them that. I shouldn't have introduced them here. The reasoning I allude to is described in Combinatory logic#Logic, but has some fairly heavy prerequisites. If your brain is melting, you probably don't want to go there. –Henning Makholm (talk) 13:21, 24 October 2010 (UTC)

A simpler way to phrase the argument in this particular case would be: "Suppose we had a proof of ¬¬p→p. Then we would replace every subformula ¬φ anywhere in the proof with q, where q is any propositional variable that differs from p. Since none of the rules we use treat ¬φ specially, this substitution still leaves a valid proof. But that proof would conclude q→p which is manifestly not a tautology, so the assumed proof of ¬¬p→p cannot exist."

This may be what your teacher had envisioned. However, I couldn't find any hint for that version that wouldn't give it all away, and the method isn't as general. –Henning Makholm (talk) 13:44, 24 October 2010 (UTC)

October 23

the four-color theorem doesn't seem right to me

I can always come very close to producing a counter-example. What is the probability that the four-color theorem really is wrong, as it seems to me? If there is a simple, intuitive proof, maybe you could tell me it? 84.153.222.131 (talk) 15:40, 23 October 2010 (UTC)

Have your read our Four color theorem article? Basically, there is no known proof that is small enough to be checked by hand, but several independent computer-assisted proofs and at least one computer-verified formal proof have been constructed, and it is pretty implausible that they are all flawed.

I cannot imagine any meaningful sense in which one could assign a definite "probability" (other than 0 or 1) to the theorem being untrue. –Henning Makholm (talk) 16:00, 23 October 2010 (UTC)

See Bayesian inference for a paradigm in which assigning such probabilities makes sense. Robinh (talk) 16:10, 23 October 2010 (UTC)

I said "I cannot imagine any meaningful sense in which...". Pulling numbers out of one's ass and pretending that they have anything to do with the subject under discussion does not count. –Henning Makholm (talk) 16:53, 23 October 2010 (UTC)

Bayesian probability doesn't pretend to describe the subject under discussion, but rather our state of knowledge about the subject under discussion. This is of crucial importance in epistemology and decision theory. An example for someone making a decision based on his credence for the correctness of a proof is this. -- Meni Rosenfeld (talk) 07:29, 24 October 2010 (UTC)

I thought one pulled a prior out of thin air, not a posterior out of one's ass. Robinh (talk) 18:42, 24 October 2010 (UTC)

There is a relatively simple proof of the weaker Five color theorem. It does take several big steps to fully understand, though. If you want to give it a shot, here's a list of things you can look at:

1. Understand the translation of the map coloring problem into that of coloring graphs. This is explained in this section of the Four color theorem article. If you aren't already familiar with graph theory, you might want to play with those a little; a famous theorem that might help you get acquainted with graphs is the condition under which an Eulerian path exists (though that is not crucial to understanding the proof of the five color theorem).
2. Study the Euler characteristic for planar graphs. If a graph is planar, then we can count not only edges and vertices, but regions enclosed by the edges as well. It turns out that these three quantities satisfy a nice rule, V-E+F=2. The proof of this fact is outlined in that article.
3. Figure out why the Euler characteristic implies E ≤ 3V − 6 (assuming the planar graph has at least 3 edges). This can be algebraically derived from knowing that every edge touches at most two regions and every region touches at least 3 edges.
4. From this fact, prove that every planar graph must have some vertex of degree 5 or less.
5. If you are sufficiently well versed in proof by induction, a proof that every planar graph can be colored with 6 colors should follow naturally, knowing that last fact. Turning this into a proof that every planar graph can be colored with 5 colors requires a clever trick, which is explained in the article on the five color theorem. Why can't the same trick be used to prove the Four color theorem?

HTH. --COVIZAPIBETEFOKY (talk) 16:29, 23 October 2010 (UTC)

Help me impress my friend?

Hey I'm trying to pretend I know something about calculus to impress my friend. Technically that's why I want the answer to this question, it's not (my) homework.

So..

1/⅔ × sqrt(X) × constant = 3/2 X

What is the value of constant?? It's from a first year calculus course, I've already taken it, but I don't know where to start on this question. —Preceding unsigned comment added by 174.89.36.96 (talk) 16:07, 23 October 2010 (UTC)

This is not calculus. It is algebra. You need to isolate the X on the right. Multiply both sides by 2/3 and you'll have a very simple formula. However, the "constant" is not a constant. -- kainaw™ 16:28, 23 October 2010 (UTC)

(e/c) This isn't calculus, it's algebra. There is no differentiation or integration involved. Looking at your problem you have

${\frac {1}{2/3}}\times {\sqrt {x}}\times k={\frac {1}{2}}(3k{\sqrt {x}}).$

You claim that this is equal to 3x/2, i.e.

${\frac {1}{2}}(3k{\sqrt {x}})={\frac {3}{2}}x\iff k{\sqrt {x}}=x\iff k={\sqrt {x}}.$

But this doesn't really make sense. You see, x is usally though of as a variable. That means you would solve the equation for x and not k. (k was a constant after all, and was fixed.) A more likely solution would be

${\frac {1}{2}}(3k{\sqrt {x}})={\frac {3}{2}}x\iff x=0,k^{2}\ .$

If there's something you forget to mention then let us know. It will change the problem and hence change the answer. — Fly by Night (talk) 16:30, 23 October 2010 (UTC)

Ok thanks a lot guys, I asked if there are more details, but that seems to be the whole question. For now I guess this is resolved, I was hoping I was missing some advanced calculus technique that would let me find a genuine constant.

Hopefully she's impressed —Preceding unsigned comment added by 69.165.137.230 (talk) 17:08, 23 October 2010 (UTC)

If she knows calculus, she will quickly spot your naive error: your assumption that "any complicated math is calculus." Once you are outed thusly, she will see through your charade and will probably be unimpressed by you (and will likely consider your stunt a poor indicator of character). To avoid this eventuality, you should educate yourself first by reading our articles on algebra and calculus, (and your textbooks) and work out as many practice problems as you can. Girls (or guys) who would be impressed by pseudo-calculus are of dubious quality. You should stick to actually knowing things; this will impress everybody, including those girls who actually know calculus. Nimur (talk) 18:03, 23 October 2010 (UTC)

Quite the opposite! If she knows calculus, and realizes he's only pretending to, she is far more likely to find him a hot boy-toy, ie physically lust for him, than otherwise. In fact, if he were a Fields-metal level genius, it would only hurt his chances... 84.153.221.42 (talk) 18:44, 23 October 2010 (UTC)

I beg to differ! Nimur (talk) 18:46, 23 October 2010 (UTC)

Sir, may I ask you, kindly to leave the inquiring gentleman's delusions intact? If indeed his friend can tell calculus from pseudocalculus, it would be discourteous to deny her this opportunity to form an accurate assessment of his moral character. –Henning Makholm (talk) 18:55, 23 October 2010 (UTC)

The idea that one might be able to use pseudo-calculus as an effective dating tool implies such a fundamental misunderstanding of dating interactions and the psychology of women that I don't see any real possibility that anything we say will un-delude this guy. Just give him a Darwin Award for trying, because if he keeps it up it's extremely unlikely he will ever reproduce. --Ludwigs2 19:06, 23 October 2010 (UTC)

Unless he becomes a sexual predator. 67.243.7.240 (talk) 23:53, 24 October 2010 (UTC)

Don't worry she doesn't know too much calculus. —Preceding unsigned comment added by 99.224.233.138 (talk) 19:21, 23 October 2010 (UTC)

See [4] for a joke about assuming a waitress doesn't know calculus. I think the whole business is a bad idea. Dmcq (talk) 22:07, 23 October 2010 (UTC)

secure hash

how to securely hash any two numbers each over 100 digits long into a number between 1 - 10 with equal distribution/probability. The easier the hash is to explain/follow, the better. this is not homework. thank you! 84.153.221.42 (talk) 18:41, 23 October 2010 (UTC)

How about modulo ten? There is no way to avoid hash collision with your scenario, so why try? Nimur (talk) 18:44, 23 October 2010 (UTC)

What do you mean? How do you combine the numbers? Anyway both my numbers are odd (they're large primes), so if you're adding them, you would only ever get 2,4,6,8, or 0 and never any of the other numbers. Do you have a better suggestion, that would use more of the digits of both numbers? (and 'depend' on both of them) 84.153.221.42 (talk) 18:55, 23 October 2010 (UTC)

(ec) Just add all the digits modulo ten. If you want something "more secure", you'll need to specify which kind of security property you're thinking about (since quite clearly the usual characteristics of a cryptographic hash functions are unachievable with an output that small). –Henning Makholm (talk) 19:02, 23 October 2010 (UTC)

(Is what you're looking for perhaps not a hash but a message authentication code? –Henning Makholm (talk) 19:05, 23 October 2010 (UTC)

Yes, I am looking for a message authentication code, but that article says it is sometimes called a keyed (cryptographic) hash function. This is the sense in which I used the word "hash". 84.153.221.42 (talk) 20:08, 23 October 2010 (UTC)

From a security standpoint, the recommendation would be something tried and true, such as HMAC-SHA1, and then use mod 10 (or whatever) to cut `it down to the size you want. If you insist on simpler calculations (always at the risk of accidentally introducing cryptographic weaknesses), you'll need to be much more explicit about which threats you want to secure against. –Henning Makholm (talk) 20:28, 23 October 2010 (UTC)

Well, I don't really want to secure against anything so much as make sure that there is an equal distribution.... 84.153.221.42 (talk) 20:38, 23 October 2010 (UTC)

To be clear, you want a hash function mapping into {1, ..., 10} which has a roughly uniform distribution for input primes in the ~100's of digits? How about... just take the first two (i.e. most significant) nonzero decimal digits mod 10? I'd be surprised if the distribution was much different from uniform. Of course you should try it out with a thousand or so test cases to see. (I'm guessing you just want something decent, not perfect, and an attacker isn't in the picture. If these assumptions are incorrect, please clarify the question.) 67.158.43.41 (talk) 04:44, 24 October 2010 (UTC)

I'm not sure what you mean by "securely" here. It's not possible to achieve any of the usual security properties of a cryptographic hash function if the function can only take 10 distinct values; in particular, even if the hash was a random oracle, it would only take on average 10 queries to find a preimage for any output. —Ilmari Karonen (talk) 19:01, 23 October 2010 (UTC)

By the way, is modulo 10 equally distributed?

rand() % x in c is not equally distributed, as it slightly favors smaller numbers over larger ones. Would it be equally distributed 1-10 when applied to the sum of the digits of two primes? 84.153.221.42 (talk) 20:09, 23 October 2010 (UTC)

This isn't answering your question, but a more important reason that rand()%x might not be uniformly distributed in C is that the pseudorandom number generator used in many C libraries does not produce uniformly distributed least-significant bits. —Bkell (talk) 06:18, 24 October 2010 (UTC)

also followup

is your recommendation the same if we need a number 1-10, 1-100, 1-500. 1-1000, or 1-5000? (assuming we're looking at primes several hundred digits long.) 84.153.221.42 (talk) 20:11, 23 October 2010 (UTC)

terminology

Resolved

add two things. The resulting sum...
multiply two things. The resulting product...
take modulo 5. The resulting _____?

what is the missing word? 84.153.221.42 (talk) 20:36, 23 October 2010 (UTC)

Remainder or residue. –Henning Makholm (talk) 20:42, 23 October 2010 (UTC)

Thanks!

can you find an n-digit prime?

I know for binary digits, you can -- encryption uses, for example, 512-bit primes. Can I ask you to find an exactly 100-digit prime (or 500, etc), expressed in decimal? 84.153.221.42 (talk) 22:20, 23 October 2010 (UTC)

Yes, you can ask. Whether anyone will bother to actually do it for you is another matter. If you google for prime number generator, you will find websites and free software that purport to do things like this for you. –Henning Makholm (talk) 22:32, 23 October 2010 (UTC)

There always exist primes with any desired number of digits. The known bounds on the prime-counting function imply that for any $n>e^{\ln 2+10}\approx 44053$ there is at least one prime between n and 2n, and this property also holds for smaller n (by inspection of tables of primes). –Henning Makholm (talk) 23:06, 23 October 2010 (UTC)

Also see Bertrand's postulate. --Sam^Talk 05:15, 24 October 2010 (UTC)

Ah, that's slicker than the pedestrian argument I used. Thanks. –Henning Makholm (talk) 13:24, 24 October 2010 (UTC)

The following 500 decimal digits number is almost certainly a prime:

9871615190774109714631411860249057511981491262347298846971208567428248575453148043285875030217607786541394670874
1765030099536818318173353655505066711178433481944388749902895601864112760848063528268606416757060899302271352925
5864263819518034812848659084214983995663078865233769085509471793209927625145995901711340039317987632029515022435
2487509247090084455951957030991069493698109678946205440148128949032618192971706584082407007804900529851119894058
1723948298045506883722180286057686368471530972548567

-- Meni Rosenfeld (talk) 07:04, 24 October 2010 (UTC)

Encryption software just tests randomly chosen numbers of the appropriate size for primality, and that can just as well be done with decimal digits. But even not knowing that, it follows from the fact that you can find primes for any number of binary digits that you can find them for any number of decimal digits. For example, 2³²⁹ through 2³³² all have 100 decimal digits, so if you can find a prime of 329 to 331 binary digits then you've found a prime of 100 decimal digits. -- BenRG (talk) 07:13, 24 October 2010 (UTC)

October 24

Differentiate a function

How would I compute ${\frac {d}{dx}}(x!)$, assuming that non-integer values of n! exist and can be computed using the gamma function/Stirling's approximation. 24.92.78.167 (talk) 02:56, 24 October 2010 (UTC)

Technically, non-integer values of n! do not exist, by definition. If we were to use n! as a shorthand for $\Gamma (n+1)$, which is equal for integer values of n, then, according to the page on the gamma function,

${\frac {d}{dx}}(x!)={\frac {d}{dx}}\Gamma (x+1)=x!\cdot \left(-\gamma +\sum _{k=1}^{x}{\frac {1}{k}}\right),$

where $\gamma$ is the Euler–Mascheroni constant. According to Stirling's approximation,

$x!\sim {\sqrt {2\pi x}}\left({\frac {x}{e}}\right)^{x}.$

${\frac {d}{dx}}({\sqrt {2\pi x}}\left({\frac {x}{e}}\right)^{x})={\sqrt {\frac {\pi }{2}}}e^{-x}x^{x-1/2}(2x\log(x)+1)$

Since Stirling's approximation is different then the gamma function and they are not even equal at integer values, it is no surprise that this is a very different formula. 76.67.73.90 (talk) 03:31, 24 October 2010 (UTC)

The formulas aren't that different. ${\sqrt {\frac {\pi }{2}}}e^{-x}x^{x-1/2}(2x\log(x)+1)={\sqrt {2\pi x}}e^{-x}x^{x}(\log x+1/2x)\approx x!(\log x+1/2x)$. It is well known that $-\gamma +\sum _{k=1}^{x}{\frac {1}{k}}\approx \log x$ and slightly less well known that it is $\approx \log x+1/2x$. -- Meni Rosenfeld (talk) 06:55, 24 October 2010 (UTC)

"76.67.73.90", you wrote:

${\frac {d}{dx}}(x!)={\frac {d}{dx}}\Gamma (x+1)=x!\cdot \left(-\gamma +\sum _{k=1}^{m}{\frac {1}{k}}\right),$

Can you explain what you mean by m? What is m? Michael Hardy (talk) 04:43, 24 October 2010 (UTC)

Looking at the linked page on the Gamma function, they meant x instead of m. It should be noted x is an integer in that formula (...since otherwise x! isn't defined). 67.158.43.41 (talk) 04:50, 24 October 2010 (UTC)

Finite subgroups of the multiplication group of the unit quaternions

I want a list of all finite subgroups of the multiplication group of the unit quaternions. --84.61.153.119 (talk) 08:30, 24 October 2010 (UTC)

You really should do your own homework. At least show some effort. If you don't know what a quaternion is, you may find the page quaternion group helpful. Jkasd 08:50, 24 October 2010 (UTC)

Also the list of small groups may be useful. --JohnBlackburne^words_deeds 11:37, 24 October 2010 (UTC)

I want a list of all finite subgroups of the group O(4). --84.61.153.119 (talk) 14:37, 24 October 2010 (UTC)

Does the position of the median change if a plot is distorted like this?

Let's say I have a large number of values, creating a one dimensional plot, and I figure out what the median is and in what places on the graph it occurs. Then I want to change the values so that the highest and lowest values remain the same, while the current median value is changed, and all values in-between are "scaled" to allow this to happen. If I calculate the median again, will I always find it in the same places on the graph as before? I think it should be but I lack the knowledge to verify this. Thanks. (Sorry, I can't express this in any other way than with words, but I can try to rephrase it if it's hard to understand) Obiha (talk) 11:12, 24 October 2010 (UTC)

The median for a finite number of discrete values is simply the middle value: more precisely if there are an odd number of values, n say, it's the (n + 1)⁄2 value, if there are an even number it's midway between the n⁄2 and n⁄2 + 1 values. To change the median you need to change just these values, but keeping them at their positions which may mean moving other values too. E.g. if the values are

1  5  9 13 17 21 25 29 33

the median is 17, the 5th element. To change the median to 21 you could change the numbers like so

1  6 11 16 21 23 25 28 31

The first and last numbers are unchanged but everything else has changed.--JohnBlackburne^words_deeds 11:47, 24 October 2010 (UTC)

What the OP asked is: He has an unsorted sequence of values, say

1 4 3 9 4 5 4

He finds their median 4, and then notes that it appears is position 2, 5 and 7. Then he applies a transformation which changes the median - I don't know if he means specifically a linear scaling, but for now assume that the transformed values are:

1 6 4 9 6 7 6

What he wants to know is - if he takes these new values, find their median and note where it appears, will he also get 2, 5 and 7? -- Meni Rosenfeld (talk) 12:04, 24 October 2010 (UTC)

[ec] Yes, if either there are an odd number of values or the middle two values are equal (otherwise it could depend on your definition of median, and your method for finding it). Let $x_{1},\ldots ,x_{n}$ be the values, f be the transformation you apply to each, $y_{i}=f(x_{i})$ be the transformed values, and ${\tilde {x}},{\tilde {y}}$ be the medians of x and y. A median is characterized by the fact that at most half the values are less than it and at most half the values are greater than it. So if f merely satisfies $a>{\tilde {x}}\Rightarrow f(a)>f({\tilde {x}})$ and $a<{\tilde {x}}\Rightarrow f(a)<f({\tilde {x}})$, it will follow that $f({\tilde {x}})$ is the median of y. From these conditions it will also follow that $a={\tilde {x}}\iff f(a)=f({\tilde {x}})$ which means that $x_{i}={\tilde {x}}\iff y_{i}={\tilde {y}}$, so the median will appear in the same places for both sets. -- Meni Rosenfeld (talk) 11:59, 24 October 2010 (UTC)

Venn Diagram Word Problems

I recently undertook a logic and problem solving course at a local community college as part of an IT diploma. We just commenced Venn diagrams and I seem to be having a lot of difficulty with them. Can anyone recommend a resource or site which contains questions on which to practice? I have used this site so far http://www.math.tamu.edu/~kahlig/venn/venn.html and I am looking for more?24.89.210.71 (talk) 12:16, 24 October 2010 (UTC)

Problem

Sir i have on problem plz solove it.

If:

  7-3=124
  6+3=279
  5-2=63
  11+2=2613

then 15-3=? —Preceding unsigned comment added by Apsirkeel (talk • contribs) 12:58, 24 October 2010 (UTC)

I'll give you a hint:

7-3=12|4
6+3=27|9
5-2=6|3
11+2=26|13
15-3=??|??

-- Meni Rosenfeld (talk) 13:11, 24 October 2010 (UTC)

Choosing a pineapple at a supermarket

The pineapples, for example, at a supermarket are all the same price but vary in quality according to a Gaussian distribution. If I choose three pineapples at random from the pile, and then select the best of those three, what is the probability that the selected pineapple is within the top ten percent of quality of the whole pile?

How many pineapples do I need to compare to have at least a 50% chance of being in the top x percent of quality? Not a homework question, but a practical problem. Thanks 92.15.31.47 (talk) 16:57, 24 October 2010 (UTC)

ditto for wives, guys. how many past candidates should you first reject in order to have a sample base, and afterward pick the first one better than all of these? Assume that although normally distributed, the "value" is hidden to you, and you have no absolute way to compare candidates, but instead can only do a comparison function on candidates you have already rejected? You don't want to waste your time, so we're looking at the least number to have some high confidence (as with the number above) 84.153.247.182 (talk) 17:48, 24 October 2010 (UTC)

See Secretary problem. —Bkell (talk) 18:13, 24 October 2010 (UTC)

The answer to the first is straightforward, and the distribution doesn't matter. The chance of picking 1 that's in the top 10% is 0.1. The chance it's not is 0.9. If you pick three the chance all three are not in the top 10% is 0.9³ = 0.729. The probability at least one is in the top 10%, so that the best is in the top 10%, is therefore 0.271.

If you want to choose n so there's at least a 50% chance that the best of those is in the top 10% then you need n = 7, as 0.9⁷ = 0.478, so there's about a 52% change one of the seven will be in the top 10%.--JohnBlackburne^words_deeds 18:17, 24 October 2010 (UTC)

Nit-picking, but would the fact that you are not replacing the chosen pinapple make any difference? 92.28.246.6 (talk) 20:12, 24 October 2010 (UTC)

Yes, if the qualities are not independently, identically distributed (we may discard this difficulty here, I guess) Pallida  Mors 20:21, 24 October 2010 (UTC)

The questioner stated "top 10% of quality", not "top 10% of the population of pineapples." So, if quality goes from 0 to 99, he wants a quality of 90-99. If the distribution is skewed towards 99, more than 10% of the population will have the top 10% of quality. -- kainaw™ 23:00, 24 October 2010 (UTC)

"top x percent of quality". I normally read that as the corresponding percentile. However, your point can be answered, considering the nth order statistic distribution, computing $1-F^{n}\left(x*\right)$, the probability that the highest of the n pineapples extracted has a quality as good as the threshold x* [again, considering the iid assumption]. (Forgotten sign of Pallida  Mors 00:04, 25 October 2010 (UTC))

A relevant article is order statistic. Pallida  Mors 19:53, 24 October 2010 (UTC)

This is not the same as the secretary problem, or the wives problem suggested by 84.153.., since with the pineapples you can choose any of the pineapples you have previously inspected. Its more like a quality control (poor article) or Sampling (statistics) problem. 92.28.246.6 (talk) 20:03, 24 October 2010 (UTC)

Nitpicking: If the whole pile is N pineapples, and K of them are within the top ten percent of quality of the whole pile, and you buy n pineapples, then the probability that k of these are in the top ten percent of quality is

${\frac {{\binom {K}{k}}{\binom {N-K}{n-k}}}{\binom {N}{n}}}$

See hypergeometric distribution. Bo Jacoby (talk) 22:14, 24 October 2010 (UTC).

October 25

Roulette

Forgive my weakness in math. If I had $100 and I played roulette with the intent of walking away with as much money as possible, would I be better off placing all $100 on red/black and having it out in one spin, or incrementally wagering on red/black, say $5 at a time 20 times (so that the total wager is the same)? With a 1-to-1 payout, the possible results for my first option are $200 or $0. For the second, it'd be $105/$95, then $110/$100/$100/$90, and continue branching for 18 more levels. My gut says the most likely outcome would be something like $45 at the end, but I'm not sure how to do the calculations save for the brute force approach. The Masked Booby (talk) 02:12, 25 October 2010 (UTC)

You have to specify your goals more carefully. What do you mean by "as much money as possible"? Literally speaking, you could be saying that you want the maximum probability of breaking the house, even though that chance is going to be vanishingly small. Is that what you mean? That's probably not too hard to figure out, once we know how much money the house has, and which kind of roulette we're talking about (is there 0 and 00, or just 0)?. --Trovatore (talk) 02:55, 25 October 2010 (UTC)

Ah, never mind; I didn't read carefully enough. I didn't realize you were asking only about two discrete alternatives. --Trovatore (talk) 06:43, 25 October 2010 (UTC)

The House has some (small) advantage, since not every number is red or black. The expected value on a $1 bet is a $0.053 loss, in American roulette. Either strategy has an expected loss of 100*$0.053 = $5.30. The variance of the first strategy is much higher than the second strategy--you either win big or lose big, instead of winning small and losing small. The second strategy basically follows the multinomial distribution with p1=16/38, p2=16/38, p3=2/38. 67.158.43.41 (talk) 03:21, 25 October 2010 (UTC)

Make that the binomial distribution with p=16/38. The above is also correct, though if you bet "black" all the time, for winning total purposes, "red" and "neither black nor red" are the same outcome, so p2 and p3 can be combined into the implicit loss fraction of the binomial distribution. 67.158.43.41 (talk) 04:20, 25 October 2010 (UTC)

If there's no house advantage, then the distribution of the number of wins with 20 plays is distributed binomially with $n=20,\ p=0.5$, which can be seen here. With house advantage it's $p=8/19$ which can be seen here.

Of course, since the house does have an advantage, if you want to maximize your expected money, the correct answer is not to play. -- Meni Rosenfeld (talk) 07:33, 25 October 2010 (UTC)

Mentally generating random numbers

Suppose I am playing a game like poker, and my strategy includes bluffing with a certain (fixed) probability each hand. Of course, humans are notoriously bad at generating "random" numbers themselves. The bluff (poker) article mentions using the colors of my hidden cards or the second hand on my watch as randomizing devices, but suppose I want to use some kind of pseudorandom number generator. Nearly all of the results about PRNGs are for computers that can easily remember and manipulate large numbers, which humans cannot do. Are there results for "human-implementable" PRNGs that use numbers with no more than, say, four decimal digits and computations that can easily be performed mentally? —Bkell (talk) 14:14, 25 October 2010 (UTC)

My initial thought was to do something like this:

• Choose prime numbers p, q.
• Choose m and n, small generators of the multiplicative groups modulo p and q, respectively (this will be easier if m and n are equal, more so if they are equal to 2)
• Choose thresholds $1\leq t<p,\ 1\leq u<q$ so that ${\frac {tu}{(p-1)(q-1)}}$ is equal to the probability of bluffing.
• Choose seeds $1\leq a_{0}<p,\ 1\leq b_{0}<q$.
• At each iteration, take $a_{i+1}\equiv ma_{i}{\pmod {p}},\,b_{i+1}\equiv nb_{i}{\pmod {q}}$. Bluff if $a_{i}\leq t,b_{i}\leq u$.

However, testing this gave a sequence with longer runs than random. Maybe some modification of this can give better results.

Another approach is to generate a sequence in advance and memorize it using some mnemonic. -- Meni Rosenfeld (talk) 15:19, 25 October 2010 (UTC)

I would just remember a long string of numbers. Or you could use some other more easily remembered pattern. E.g. if you've foolishly remembered π to 50 decimal places, or know the phone numbers of all your friends. You can extend the use of these by looking at them more than one way. For example you could alternate between bluffing if a digit is odd and bluffing when a digit is 5 or more. It even need not be numbers. A text, which might be easier to remember, could do the same job, though you need to be smarter at generating random numbers from it as the frequency and distribution of letters in most texts is far from random (or if it is random the text isn't easy to remember).--JohnBlackburne^words_deeds 15:29, 25 October 2010 (UTC)

complete the sequence

5+3+2 = 151012
9+2+4 = 183662
8+6+3 = 482466
5+4+5 = 202504
 Then
7+2+5 = ?  —Preceding unsigned comment added by 119.154.134.131 (talk) 17:42, 25 October 2010 (UTC)