mm-279 Subject: algebraic numbersIs the following statement true?Given an algebraic number a in C (the complex numbers), there exists aunique monic polynomial P of smallest degree with rationalcoefficients such that(1) a is a root of P(2) P contains no repea roots?It seems to me that this should be true, for if you found such apolynomial with a repea root, you could always take out that linearfactor and re-normalize by multiplying by the appropriate rationalnumber. === Subject: Re: algebraic numbers> Is the following statement true?> Given an algebraic number a in C (the complex numbers), there exists a> unique monic polynomial P of smallest degree with rational> coefficients such that> (1) a is a root of P> (2) P contains no repea roots?> It seems to me that this should be true, for if you found such a> polynomial with a repea root, you could always take out that linear> factor and re-normalize by multiplying by the appropriate rational> number. Actually, the situation is simpler: if P is monic and ofsmallest degree among polynomials having a as a root, then ithas no repea rots anyway. Why? Suppose P has repea roots. By rational operations, you candivide P by the (monic) greatest common divisor of P and itsderivative P'. The quotient will have the same roots as P, eachexactly once. ZVK(Slavek) === Subject: Intelligence and Induction for proofHere is what seems to determine a person's mathematical intelligence, somethingmore than mere mathematical learning:A typical preCalc book may have topics in the order of arithmetic sequences,geometric sequences, and then mathematical induction. The first two topicsseem quite understandable; just find patterns and use formulas for boththeoretical exercises and applied-type excersises. Then at the engagement withthe induction topic, something changes. Proving that if a k term gives anassumed result, then the k+1 term should/must also give a correct match to theformula. I am finding the process difficult, not being sure what sub-stepswill be needed in the actual proof process. I understand the basic idea:(1) the n=1 statement must be true;(2) assume the k statement is true, and prove that the k+1 statement is alsotrue.In part number (2), I am unsure how to continue. This is not for anyparticular problem, but for most possible problems. Is this something thatrequires Mathematical intelligence beyond what most of the rest of thePreCalculus textbook requires? I notice that in three different preCalculusbooks, there is only one mathematical induction section in each book. Thisseems that the induction is worth only a small emphasis for a PreCalculuscourse. Is this far off from the truth? Does math induction truely requiremore mathematical intelligence than most of the rest of PreCalculus? G C === Subject: Re: Intelligence and Induction for proofGC-> Here is what seems to determine a person's mathematical intelligence,something> more than mere mathematical learning:> A typical preCalc book may have topics in the order of arithmeticsequences,> geometric sequences, and then mathematical induction. The first twotopics> seem quite understandable; just find patterns and use formulas for both> theoretical exercises and applied-type excersises. Then at the engagementwith> the induction topic, something changes. Proving that if a k term gives an> assumed result, then the k+1 term should/must also give a correct match tothe> formula. I am finding the process difficult, not being sure whatsub-steps> will be needed in the actual proof process.> I understand the basic idea:> (1) the n=1 statement must be true;> (2) assume the k statement is true, and prove that the k+1 statement isalso> true.> In part number (2), I am unsure how to continue. This is not for any> particular problem, but for most possible problems. Is this somethingthat> requires Mathematical intelligence beyond what most of the rest of the> PreCalculus textbook requires? I notice that in three differentpreCalculus> books, there is only one mathematical induction section in each book.This> seems that the induction is worth only a small emphasis for a PreCalculus> course. Is this far off from the truth? Does math induction truelyrequire> more mathematical intelligence than most of the rest of PreCalculus?Most induction problems at the introduction do not require more intelligenceper se, but they do often demand techniques and ways of thinking about maththat you may not yet have encountered. Whereas most precalculus isdeductive, i.e. trying to simplify expressions, many induction problemsrequire backward thinking (and un-simplifying expressions).Consider the following assertion:For all integers n >= 1, 1+3^(2n-1) is divisible by 4.Testing the first case (usually called the base case), 1+3^[2(1)-1] = 1+3 = 4, which is divisible by 4Now, let's assume this is true for n = k. Thus, there is some integer msuch that 1+3^(2k-1) = 4mLet's consider the n = k+1 case: our expression is then 1+3^(2(k+1)-1) = 1+3^(2k+1) = 1+(3^2)*3^(2k-1) = 1+9*3^(2k-1)Here's the trick: we write to rewrite our expression to include 1+3^(2k-1) somewhere (because we know that expression to be divisible by4, from our n=k case). Since we have 3^(2k-1) multiplied by 9, let's add 9and subtract 9 from the total expression (you'll see why in a moment): = 1+9*3^(2k-1)+9-9Factoring a 9 out of the second and third terms, = 1+9*[1+3^(2k-1)]-9 = 9*[1+3^(2k-1)]-8Now, we know 1+3^(2k-1) = 4m; so, substituting: = 9*4m-8Writing 8 as 4*2, = 4*9m-4*2 = 4*(9m-2)But this is still our expression (albeit in disguise) for our n = k+1 case,and this is clearly divisible by 4 (m is an integer, so 9m-2 is an integer).Thus, we have both our base case true, and our recursive (or iterative)statement true as well; by induction, our claim that 1+3^(2n-1) is divisibleby 4 is true. QEDHope this helps.Travis === Subject: Re: Intelligence and Induction for proof>I understand the basic idea:>(1) the n=1 statement must be true;>(2) assume the k statement is true, and prove that the k+1 statement is also>true.>In part number (2), I am unsure how to continue. This is not for any>particular problem, but for most possible problems. Is this something that>requires Mathematical intelligence beyond what most of the rest of the>PreCalculus textbook requires? Not really, no. It's just that induction is no longer taught in Algebra I as it used to be, so it seems strange and frightening.Think of Chairman Mao: A journey of a thousand miles begins with a single step. That single step is the n=1 case. Then assume true for n=k, and prove that n=k+1 must also be true as a result says wherever I am, I can take one step forward. If you can always take a step forward, and you have a starting point, then you can reach any possible point; in other words, the statement must be true for all n.You say>This is not for any particular problem, but for most possible problems.But really the devil is in the details: One particular induction proof won;t look like another because each one depends on what you're trying to prove.here's one example: Prove that the sum of 1+2+3+...+n = n(n+1)/2.Step 1: Is it true for n=1? Yes, because 1 = 1(1+1)/2.Step 2: assume that it's true for n=k. That is, assume that 1+2+3+...+k = k(k+1)/2Now, is it true for n=k+1? Well, on the left-hand side it would be 1+2+3+...+k+(k+1), meaning that you add k+1 to the left-hand side. But you can always make a true equation by adding the same thing to both sides of an existing true equation. Since you assumed the equation was true for n=k, if you add k+1 to both sides it will still be true: 1+2+3+...+k = k(k+1)/2 1+2+3+...+k+(k+1) = k(k+1)/2 + (k+1)Now what would you have on the right-hand side if the conjecture were true for n=k+1? You'd have n(n+1)/2 but with (k+1) in place of n. In other words, you'd have (k+1)(k+2)/2. Now, can you make the right-hand side that you do have, k(k+1)/2 + (k+1), look like (k+1)(k+2)/2? Yes, you can: 1+2+3+...+k+(k+1) = k(k+1)/2 + (k+1) 1+2+3+...+k+(k+1) = k(k+1)/2 + (k+1)(2/2) 1+2+3+...+k+(k+1) = (k+1)(k/2) + (k+1)(2/2) 1+2+3+...+k+(k+1) = (k+1)[(k/2) + (2/2)] 1+2+3+...+k+(k+1) = (k+1)(k+2)/2What you have done is to prove that _if_ the conjecture is true for any particular n (call it k), _then_ it is also true for the next number n (call it k+1). But you also know that it _is_ true for n=1. Therefore it is also true for n=2. But if it's true for n=2 then it's also true for n=3. And so on, forever. You have proved that it's true for all n >= 1.-- Stan Brown, Oak Road Systems, Cortland County, New York, USA http://OakRoadSystems.comFortunately, I live in the Uni States of America, where we aregradually coming to understand that nothing we do is ever ourfault, especially if it is really stupid. --Dave Barry === Subject: Re: Strings: Need a ProofContent-transfer-encoding: 8bit> Hello everybody,> Here is my question: Suppose L is the set of all strings over the set> {a, b}, including the null string, that can be construc using the> following rules,> - if x is in L, then axb and bxa are in L> - if x is in L and y is in L, then xy is in L> Show that if x has an equal number of a's and b's, then x is in L.> I figured this would involve some proof by contradiction, but I've> found nothing of a contradiction in any of my attempts. Any hints or> clues?> Thanks in advance,> BerndOK, I'll take another stab at it.Again, I'll use induction on half string length.Since the empty string is in L, ab and ba are in L so any string oflhalf ength 1 (or 0) with the same number of a's and b's is in L.Now suppose that every string of half length less than k with the samenumber of a's as b's is in L.Let w be a string with length 2k and k a's and k b's. Wlog, assume wstarts with a. If w = abw_1 then since ab is in L and w_1 has halflength k-1 and the same number of a's as b's, by assumption, w_1 is inL and thus w is in L. Similarly, if w ends in b or in ba, w is in L.So, suppose w = aaw_1aa. Let A(n) be the number of a's in the initialsubstring of w of length n and let B(n) be the number of b's in thatinitial substring.We have A(2) = 2, B(2) = 0, A(2k-2) = k-2 and B(2k-2) = k. So, theremust be a smallest t such that A(t) <= B(t). But then A(t-1) > B(t-1).Consider the t-th entry of w. It can't be a or else A(t) = A(t-1) + 1 > B(t-1) + 1 >= B(t). So the t-th entry must be b.Thus, A(t-1) = A(t) <= B(t) = B(t-1)+1. If A(t) < B(t) then A(t-1) < B(t-1)+1 which is false.Consequently A(t) = B(t) so the initial substring of length t has asmany a's as b's and thus is in L. For the same reason, the remainingfinal substring is in L so w is in L.I suspect there is a more elegant way to do this.That completes the induction.-- Paul SperryColumbia, SC (USA)Subject: stupid question about tensors === I am currently trying to familiarize myself with tensor calculus. However Ihave come across a question to which I cannot find an answer. Namely, in thebook I am using (D.Kay Tensor Calculus p.37) it is sta that ( _ issubscript ):If T_i are the components of covariant vector T, then S_ij = T_i T_ j - T_ jT_i are the components of a skew symmetric covariant tensor S.As far as I can understand each S_i_ j should equal 0 ( T_i T_ j = T_ jT_i). But how can a tensor, having all of it's components equal to 0, beskew symmetric? Or is it a tensor at all? But it is said to be a tensor. Soshould I deduce that multiplication of tensor components is not commutative? === Subject: Re: stupid question about tensors> I am currently trying to familiarize myself with tensor calculus. HoweverI> have come across a question to which I cannot find an answer. Namely, inthe> book I am using (D.Kay Tensor Calculus p.37) it is sta that ( _ is> subscript ):> If T_i are the components of covariant vector T, then S_ij = T_i T_ j - T_j> T_i are the components of a skew symmetric covariant tensor S.> As far as I can understand each S_i_ j should equal 0 ( T_i T_ j = T_ j> T_i).Correct.> But how can a tensor, having all of it's components equal to 0, be> skew symmetric?Well, s_i_j = s_j_i = -s_j_i = 0, so it is both symmetric and skewsymmetric, no problem.> Or is it a tensor at all?Yes, it's a zero tensor, which is OK although rather dull!> But it is said to be a tensor. So> should I deduce that multiplication of tensor components is notcommutative?No, the tensor components themselves are just numbers... I don't have thebook you're reading, so I'm not sure what the author was getting at. Thingsare more interesting with two vectors T and U. Then S_ij = T_i U_j - T_jU_i is a skew symmetric tensor (rela to the vector cross product of T&U -note that the cross product of any vector with itself is also zero).Mike.(remove dead stones to reply by email) === Subject: Re: stupid question about tensorsI have the same Tensor book by D. Kay and looked up the example. I thinkthe author is merely trying to establish that given that T_i is covariantandgiven that S_ij = T_iT_j - T_jT_ishow that S_ij is covariant.This part of the question can be answered by substituting the definition forthe covariant tensor of order one on page 27 (eq 3.10) everywhere for T_iand T_j . and substituting the definition for a covariant tensor of ordertwo on page 29 (eq. 3.12)everywhere for S_ijThe skew symmetric part of the question, he says is obvious.(I hate it whenthey do that!) He means he has defined S in such a way that it equals theequavalent of AB - BA (to rid of cumbersome notation). Note if S=AB-BAit is not necessarily equal to zero. Let me give you an example.Suppose A is a counterclockwise rotation of 90 degrees in an xy plane thensuppose B is a reflection in the y axis. Draw a picture and you will see ifyou reverse the operations, they do not commute. However, S itself would beskew symmetric since it own negative transpose is the neg. transpose of(AB-BA) So you get S-S(transpose)=AB-BA-(-BA-AB) =0> I am currently trying to familiarize myself with tensor calculus.However> I> have come across a question to which I cannot find an answer. Namely, in> the> book I am using (D.Kay Tensor Calculus p.37) it is sta that ( _ is> subscript ):>>If T_i are the components of covariant vector T, then S_ij = T_i T_ j -T_> j> T_i are the components of a skew symmetric covariant tensor S.>>As far as I can understand each S_i_ j should equal 0 ( T_i T_ j = T_ j> T_i).> Correct.> But how can a tensor, having all of it's components equal to 0, be> skew symmetric?> Well, s_i_j = s_j_i = -s_j_i = 0, so it is both symmetric and skew> symmetric, no problem.> Or is it a tensor at all?> Yes, it's a zero tensor, which is OK although rather dull!> But it is said to be a tensor. So> should I deduce that multiplication of tensor components is not> commutative?> No, the tensor components themselves are just numbers... I don't have the> book you're reading, so I'm not sure what the author was getting at.Things> are more interesting with two vectors T and U. Then S_ij = T_i U_j - T_j> U_i is a skew symmetric tensor (rela to the vector cross product ofT&U -> note that the cross product of any vector with itself is also zero).> Mike.> (remove dead stones to reply by email) === Subject: Re: The mistical value of e > yes, but HOW if presen with this question, could you narrow> the limit down to e? (heck, I'm guessing it's impossible)Please don't top-post.There are many ways to see that the limit as x goes to zeroof (1+x)^(1/x) is e. But once you throw away the informationthat the base is 1+x and the exponent is 1/x, and simplytry to understand it as 1^infty, then yes, it *is* impossible.It may have fallen out of fashion, but older calculus booksused to talk about indeterminate forms; once you reducean expression to an indeterminate form, you know you've reducedit too far, and you need to go back and use some of the informationyou've thrown away, because an indeterminate form can a prioritake many values. The classic indeterminate forms are 0/0 0^0 infty/infty infty-infty 1^infty === Subject: Re: The mistical value of e> The classic indeterminate forms are> 0/0> 0^0> infty/infty> infty-infty> 1^inftyOh, I left out an important one: 0*inftyAlso, if you wind up with infty+infty, you needto check carefully to make sure the two infinitiesare signed and have the same sign. If you're usingunsigned infinity, then infty+infty is also anindeterminate form. === Subject: Re: The mistical value of e>Well, it's not that mystical, how it is achieved I understand, what I don't>understand is how the limit below could have its value:> lim(x->0) (1+x)^(1/x) = e>heck I would simplify it as follows instead:> lim(x->0) (1+0)^(infinitum) = 1>But that's wrong, or more correctly perhaps....not precise enough, but why?That's not how a limit works. 1^infinity is what we call an indeterminate form, meaning that you have to go back to the original expression and do some more work to evaluate the limit.Informally, try it this way. Make a table of x and (1+x)^(1/x). This should be easy to do with any calculator, or of course with Excel:x (1+x)^(1/x)-------- -----------1 20.1 2.593742460.01 2.7048138290.001 2.7169239320.0001 2.7181459270.00001 2.7182682370.000001 2.718280469This is not a proof, of course, but it should be enough to convince you that as x gets closer and closer to 0, (1+x)^(1/x) gets closer and closer to the particular decimal value that you know as e. And that's pretty much what a limit means: if you can get the function as close as you like to the supposed limit just by keeping x close enough to the sta value, then the supposed limit IS the limit. (We can dress that up with epsilons and deltas if you like.)-- Stan Brown, Oak Road Systems, Cortland County, New York, USA http://OakRoadSystems.comFortunately, I live in the Uni States of America, where we aregradually coming to understand that nothing we do is ever ourfault, especially if it is really stupid. --Dave Barry === Subject: Re: The mistical value of eContent-transfer-encoding: 8bit> Well, it's not that mystical, how it is achieved I understand, what I don't> understand is how the limit below could have its value:> lim(x->0) (1+x)^(1/x) = e> heck I would simplify it as follows instead:> lim(x->0) (1+0)^(infinitum) = 1> But that's wrong, or more correctly perhaps....not precise enough, but why?> If you know L'Hopital's rule, now is the time for it.Failing that, you may know lim((1 + (1/x))^x, x -> oo) = e. If so,observe lim((1+x)^(1/x), x -> 0) = lim((1 + (1/x))^x, x -> oo) = e.-- Paul SperryColumbia, SC (USA) === Subject: Re: The mistical value of e> anywho, but how would you go about simplifying that statement> lim(x->0) (1+x)^(1/x)> to obtain e. Or more correctly, is it even possible to somehow simplify> this as we do> with the limit definition of a derivative? I mean, can we do anything to> this equation> to somehow narrow it down to e Note ln[(1+x)^(1/x)] = [ln(1+x)]/x = [ln(1+x) - ln(1)]/x -> ln'(1) = 1 as x -> 0, by the definition of the derivative. Therefore (1+x)^(1/x) -> e^1 = e as x -> 0. === Subject: Re: rational arithmetic library?> I've been looking for a means to implement a numerical linear algebra> algorithm, but without the concomitant round-off error (I'm fortunate> enough that my initial matrices are of integer type). > I needed a more general library, though. I had the linear algebra> algorithm all coded up, but I simply wan to exchange the arithmetic> operators to ones which would understand & simplify both rational> numbers and integers. Check out www.linalg.org. You can download extensive C++ code therefor the exact solution of matrix problems. Rational arithmetic isusually not the best thing to use for integer matrix problems, execptperhaps that it may be required in the final steps if the answersthemselves are rational. === Subject: Re: rational arithmetic library?===> Check out www.linalg.org. You can download extensive C++ code there> for the exact solution of matrix problems. Rational arithmetic is> usually not the best thing to use for integer matrix problems, execpt> perhaps that it may be required in the final steps if the answers> themselves are rational.Why so? I need the answers to be exact, not approximate. My matrixstarts with positive & negative integers between -2 and 2. In theworst-case, I can imagine a bignum implementation chewing up a lot ofresources. But I imagine that the average case will be acceptable (Ineed accuracy, not speed).-- () === Subject: Re: rational arithmetic library?You don't say what you are doing, or how long you expectyour computation to take. There are studies that suggestdoing some exact operations can be done more efficientlyby using finite field arithmetic (perhaps several times)and sticking the pieces together with the Chinese RemainderAlgorithm. e.g. McClellan's work on exact solution of linearequations using modular arithmetic.You might also look at papers on Exact Linear Algebraby Ashoff(try google).>>Check out www.linalg.org. You can download extensive C++ code there>>for the exact solution of matrix problems. Rational arithmetic is>>usually not the best thing to use for integer matrix problems, execpt>>perhaps that it may be required in the final steps if the answers>>themselves are rational.> Why so? I need the answers to be exact, not approximate. My matrix> starts with positive & negative integers between -2 and 2. In the> worst-case, I can imagine a bignum implementation chewing up a lot of> resources. But I imagine that the average case will be acceptable (I> need accuracy, not speed). === Subject: Re: rational arithmetic library? <4pkad382oet.fsf@thar.lbl.gov> === > I took a second look at R5and I realized my confusion; I guess my> current implementation-of-choice, Guile, doesn't support 'numerator',> 'denominator', or 'rationalize'! So I tried some others:> *DrScheme: yes> *Guile: no> *Chicken: no> *Bigloo: yes> *Scheme48/Scsh: yes> *SCM: noI made a mistake: Bigloo does not support rationals:1:=> rationalize*** ERROR:bigloo:eval:Unbound variable -- rationalize#unspecified1:=> numerator*** ERROR:bigloo:eval:Unbound variable -- numerator#unspecified1:=> denominator*** ERROR:bigloo:eval:Unbound variable -- denominator#unspecified1:=> (/ 10 3)3.33333333333331:=> (/ 1111111111111111111 999999999999999999999999)*** ERROR:bigloo:/:not a number -- #l1111111111111111111#unspecified---~T === Subject: Re: rational arithmetic library?>>I took a second look at R5and I realized my confusion; I guess my>>current implementation-of-choice, Guile, doesn't support 'numerator',>>'denominator', or 'rationalize'! So I tried some others:>>*DrScheme: yes>>*Guile: no>>*Chicken: no>>*Bigloo: yes>>*Scheme48/Scsh: yes>>*SCM: no> I made a mistake: Bigloo does not support rationals:But any CL implementation does. A piece of advice: bite the bullet! Switch to CL :)Cheers--Marco === Subject: Re: Riccati challenge to Maxima THIS group, sci.math.symbolic,is presumably open to discussion of all matters rela to symbolic> computation, as the name indicates.> Unfortunately it is also open to other stuff as well :)>When I was a kid each movie feature was accompanied by a cartoon.Although you don't see Mickey Mouse, The Road Runner, Porky Pig, et al,at the movies anymore, you CAN come to sci.math.symbolic for amusement.. === Subject: Maxima vs MuPAD by support1.mathforum.org (8.11.6/8.11.6/The Math Forum, $Revision: 1.9 primary) id i1QDt7605010; by support1.mathforum.org (8.11.6/8.11.6/The Math Forum, $Revision: 1.9 primary) with ESMTP id i1QCnOi30576 by legacy.mathforum.org (8.11.6/8.11.6/The Math Forum, $Revision: 1.10 $, legacy) id i1QCnO508671 === ,I made a comparison between Maxima 5.9.0 and MuPAD 2.5.0 using M.Wester's 131 test problems; seehttp://homepage.mac.com/peso1[/index.html] . Comments are welcome -especially on problems I or Maxima or MuPAD could not solve.Pekka Sorjonen === Subject: Re: Maxima vs MuPADThis is an interesting comparison of a program (Maxima) that is22 years old and pre-dates Wester's test by many years,and MuPAD program whose authors could look at Wester's testsand fix them. Wester originally used MuPAD 1.2.1a and this testis of 2.5.0.I looked through the examples, andit seems to me that the tensor calculations in Maximarequire reading in some additional programs, but that theycould be done. (65,66).Your conclusion that MuPAD scored better seems to be basedthe performance on a number of problems all of which turn onhandling of assumptions or declarations of domains.I think there are just a bunch of bugs in Maxima (that werefixed during the subsequent 22 yeain Macsyma) that needto be repaired. On the other hand it may be that MuPAD hasdone this right from the start, and the lack of bugs isa natural consequence of the design. Do you think that is thecase, or is it just the same hodge-podge, but debugged more?I also think that adding statistical analysis programs, ornumerical matrix programs is just a matter of writing some more routine programs. Anyone doing serious statistical studies should beusing a different program, I suspect. Left out of the comparison is the speed. I would expectthat MuPAD is slower. Can you give any data on this? ForMaxima, typing showtime:all$ gives data on each command. Also left out is the fact that Maxima is (now) open-sourceand I gather that MuPAD is not, although it is sometimesfree. The quality of the documentation is a serious issue formany users. Maxima documentation is not so good, but theavailable documentation for Macsyma is substantial. And the fundamental question to meis whether MuPAD or Maxima is foundationally a better systemon which to build programs which depend on mathematical knowledge.Although you conclude that MuPAD wins, I suspect that yourconclusions would have to be revised if someone spent a monthfixing bugs in Maxima, targetting Wester's tests.My recommendation to people who ask which is better.... isto find out what they are trying to do, and if they have friendsdoing similar things with a CAS. They should use the same programas their friends, usually.Thanks for doing the tests!!> ,> I made a comparison between Maxima 5.9.0 and MuPAD 2.5.0 using M.> Wester's 131 test problems; see> http://homepage.mac.com/peso1[/index.html] . Comments are welcome -> especially on problems I or Maxima or MuPAD could not solve.> Pekka Sorjonen