Wikipedia:Reference desk/Archives/Mathematics/2009 December 22

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

December 22

Desperately Seeking a Faster Algorithm

Pari/GP is remakably slow at determining whether a polynomial is irreducible. Now, it may be that the problem is just generally hard, but I find it difficult to believe that the following program to generate the smallest coefficients to build a sequence of irreducible polynomials cannot be made faster. It involves small positive coefficients, and I would think that there is at least a better way than simply using PARI/GP's polisirreducible function for the sizes of coefficients involved. Here is the program as it now stands (and a good many of the terms it output are at oeis:A171810):

x=1:for(d=1,4000,c=1;x=x+v^d;while(polisirreducible(x)-1,c+=1;x=x+v^d;next());print1(c" "))

If anybody knows of or can think up an algorithm for determining irreducibility (over Z) for the special case of small positive coefficients, it will make the terms of the sequence given more open to study. As things stand, certain things about the coefficients are more mysterious than they might be with access to hundreds of thousands rather than merely thousands of terms. Much appreciation for any worthwhile answer.Julzes (talk) 03:16, 22 December 2009 (UTC)

I'm not an expert in the field, but you're already using a computer algebra program and the people who write them generally know what they are doing. Not that the one you're using is perfect, you might want to try some other ones to see if they work any better, but I think anything you're going to learn here will already be incorporated into most programs with a good reputation.--RDBury (talk) 06:32, 22 December 2009 (UTC)

Well, I do appreciate that point of view, and generally I'd also guess the polisirreducible function is about as good as possible, but I was wondering whether there might be something a little more tuned to small coefficients (mostly 1s, regular 2s, few 3s, one 4 and that's it). A function like polisirreducible is going to be set up for the most general case, and is unlikely to be close to optimal for polynomials that are so strongly biased toward small positive coefficients.Julzes (talk) 08:19, 22 December 2009 (UTC)

I just came back to share an intriguing result of a different, related, problem. Starting with constant coefficient 1, the problem is to create a sequence of polynomials that are relatively prime to each other using the smallest positive coefficient. While acting in no particularly orderly way up to the 89th degree, beginning there up to at least the 1000th the coefficients are all 1s at degrees not congruent to 3 modulo 5, and are 2s there. I'm not looking for, and I don't expect, an explanation.Julzes (talk) 09:41, 25 December 2009 (UTC)

Summation of finite differences

I am trying to do a definite sum from a to b, viz.:
sum [ (n+j)! / n! ]
I had thought to sum it by parts, i.e.:
sum [v * delta(u) ] = [ u*v {with appropriate limits for a and b} ] - sum [ u * delta(v) ]
where v is [ (n+j) ! / n! ] and delta(u) is ( 1 ).
Using information from previous posts:
delta [ (n+j) ! / n! ] = [ j * (n+j)! / (n+1)! ] = [ j / (n+1) ] * [ (n+j)! / n! ]
Summing delta(u) leads to ( n ), or to [ (n+1) - 1 ].
[Being a definite sum, it seems there should be no constant of summation to make it ( n+1 ).]
The sum(delta(u)) combines with delta(v) to give
sum { [ j * (n+j) ! / n! ] - [ ( j / (n+1) ) * (n+j)! / n! ] }
The first part { sum [ j * (n+j)! / n! ] } fits in nicely with the original sum [ (n+j)! / n! ].
But what to do with the second part { sum [ ( -j / (n+1) ) * ( (n+j)! / n! ) ] };
there remains a sum whose summand is equal to the original summand times -j/(n+1).
Keep integrating by parts and wind up with an answer involving an infinite series?
Or perhaps trying to do the original summation differently?ImJustAsking (talk) 14:11, 22 December 2009 (UTC)

Are you talking about $\sum _{n=a}^{b}{\frac {(n+j)!}{n!}}$ or $\sum _{j=a}^{b}{\frac {(n+j)!}{n!}}$ ? Bo Jacoby (talk) 00:53, 23 December 2009 (UTC).

Sorry about the ambiguity: n goes from a to b, and j is a constant.ImJustAsking (talk) 19:21, 23 December 2009 (UTC)

So write it as j! times a sum of binomial coefficients, and the sum is just the difference of two binomial coefficients. --pma (talk) 22:03, 23 December 2009 (UTC)

Can I do the following:
Because delta[ (n+j)! / n! ] = j * (n+j)! / (n+1)!
therefore sum{ delta[ (n+j)! / n! ] } = sum { j * (n+j)! / (n+1)! }
where “sum” goes from a to b,
so that by exchanging sides sum{ j * (n+j)! / (n+1)! } = sum{ delta[ (n+j)! / n! ] }
and cancelling “sum” and “delta”, one gets sum{ j * (n+j)! / (n+1)! } = [ (n+j)! / n! ]
Question: may I assume that the quantity on the right side is to be evaluated at a and b+1?
Of course this does not answer my original question, but it would show a way for solving it.ImJustAsking (talk) 23:54, 23 December 2009 (UTC)

Stationary Points in Higher Dimensions

To identify a stationary point of a function of more than one variable, more specifically f(x,y), do you simply have to identify the points at which every one of its partial derivatives is zero? Also, how do you go about classifying the stationary points as maxima, minima and saddle points? Thanks 92.0.129.48 (talk) 18:58, 22 December 2009 (UTC)

Yes, a stationary point is one in which f is differentiable and all partial derivatives are 0.

The first step of classification uses the signs of the eigenvalues of the Hessian matrix. In the case of two variables, this reduces to denoting $A=f_{xx}(x,y)$, $B=f_{xy}(x,y)$, $C=f_{yy}(x,y)$ and looking at $A$ and $AC-B^{2}$. If either is 0, higher order derivatives are required. If $AC-B^{2}<0$, it is a saddle point. If $AC-B^{2}>0$, then it is a local minimum if $A>0$ and a local maximum if $A<0$. -- Meni Rosenfeld (talk) 20:28, 22 December 2009 (UTC)

In case of nondegenerate critical points the classification is quite simple even in several variables, and it is given by the Morse lemma. Check also Sylvester's law of inertia. --pma (talk) 00:00, 23 December 2009 (UTC)

Symbol for 'such that'

Hi all,

I was just wondering if there's any symbol (in terms of $\forall ,\exists ,\in$ etc.) which is typically used to mean "Such that" (there exists A such that B, for example) in mathematics? I'm aware of the vertical bar |, and occasionally the colon, but sometimes these can be unclear in the context: are there any others?

Many thanks, 86.26.6.36 (talk) 22:29, 22 December 2009 (UTC)

Table of mathematical symbols only lists the colon. -- kainaw™ 22:40, 22 December 2009 (UTC)

I usually just use "s.t.". When defining a set as {A such that B} you can use a vertical bar or colon, but I wouldn't use them in any other context - too confusing. --Tango (talk) 22:42, 22 December 2009 (UTC)

I've seen $\ni$ used to mean "such that". Also a period is often used immediately after a $\exists$ to mean "such that". So the existence of ${\sqrt {2}}$ could be written $\exists x\ni x^{2}=2$ or $\exists x.(x^{2}=2)$. Of course english words are usually preferable to any of those. Staecker (talk) 22:49, 22 December 2009 (UTC)

You don't need any symbol, after the existential quantifier, to mean such that. Usually you just put either the formula that follows the quantifier, or the quantifier (plus variable) itself, in round brackets.

The $\ni$ symbol could be useful to translate other instances of such that, such as "given x such that φ(x) holds", in which you have no explicit quantifier symbol. In my experience, however, it sees fairly limited use. --Trovatore (talk) 22:58, 22 December 2009 (UTC)

Oh, it also occurs to me: The reason you don't use the symbol in existential statements is that such that doesn't actually mean anything in existential statements. "There exists x such that φ(x) holds" is just $\exists x\phi (x)$.

It does mean something, on the other hand, in universal statements, like "For every x such that φ(x) holds, τ(x) also holds". That statement translates as $\forall x(\phi (x)\implies \tau (x))$, but could also be written $(\forall x\ni \phi (x))\tau (x)$.

But again, could be written that way; usually isn't. --Trovatore (talk) 23:10, 22 December 2009 (UTC)

Great, thankyou :) 86.26.6.36 (talk) 23:27, 22 December 2009 (UTC)

Beware that you can't expect that a random reader (even assumed mathematically literate) will understand $\ni$ used with this meaning if it's not explicitly explained in the surrounding text (and then what would be the point?). For example, I managed to earn a Ph.D. in a fairly logic-heavy area of computer science without ever seeing $\ni$ used to mean anything but "contains as an element". –Henning Makholm (talk) 13:33, 23 December 2009 (UTC)

I've never seen that symbol used for "contains as an element". I've seen $\in$ used for that purpose, though.--COVIZAPIBETEFOKY (talk) 13:48, 23 December 2009 (UTC)

But $\in$ means "contained as an element". -- Meni Rosenfeld (talk) 13:56, 23 December 2009 (UTC)

... thus Harry $\in$ {Harry, Sally} and {Harry, Sally} $\ni$ Harry. Gandalf61 (talk) 14:07, 23 December 2009 (UTC)

Shot myself in the foot, there, didn't I? Whoops... --COVIZAPIBETEFOKY (talk) 14:33, 23 December 2009 (UTC)

I think that usage of $\ni$ is even more obscure than the "such that" meaning. The element almost exclusively goes on the left and the set of which it's an element on the right; there's almost never a reason to reverse them. --Trovatore (talk) 19:29, 23 December 2009 (UTC)

I wouldn't do it in a formal paper, but I often see good reason to use it this way. How about, "Let $x\in \mathbb {R}$ and consider an open set $U\ni x$" is sometimes nicer than "... and consider an open set $U$ with $x\in U$". Staecker (talk) 20:21, 23 December 2009 (UTC)

That's true; good example. --Trovatore (talk) 21:30, 23 December 2009 (UTC)

I've seen once $\ni ^{\prime }$ for "such that". I find it really ugly. --pma (talk) 15:35, 24 December 2009 (UTC)

Cartoon books about mathematics

Are there any cartoon or other fun books that teach mathematics? In particular at a level equalivalent to what we would call GCE "A" level in England (and Wales)? 92.24.76.99 (talk) 22:59, 22 December 2009 (UTC)

Don't know bupkus about A levels. But sure, things like Prof. E McSquared's Calculus Primer: Expanded Intergalactic Version (ISBN 0971462402) are out there. Do a search for "cartoon calculus", for example. --jpgordon^{::==( o )} 23:57, 22 December 2009 (UTC)

I'd say Murderous Maths but that only runs to about GCSE level (despite what our article may say about age range), and in particular is missing subjects solely taught at A level, such as calculus. - Jarry1250 ^{[Humorous? Discuss.]} 17:30, 24 December 2009 (UTC)