mm-286 > I'm looking for information about Sch.9anhage's gcd algorithm. > Does anyone here know how it works? Sch.9anhage gave at least two gcd algorithms. Which one do you mean? === Subject: Re: =?ISO-8859-1?Q?Sch=F6nhage=2C?= gcd computation > Sch.9anhage gave at least two gcd algorithms. > Which one do you mean? More than one? Ohh. I wasn't aware of that. I've read that there was one that is used for computations with very large integers in computerprograms, like maple. Do you know that one? Otherwise, anything that is potentially faster than Euclid algorithm would be nice. === Subject: =?Windows-1252?Q?Re:_Sch=F6nhage=2C_gcd_computation?= charset=Windows-1252 Gunnar schrieb > I've read that there was one that is used for computations with very large > integers in computerprograms, like maple. > Do you know that one? Otherwise, anything that is potentially faster than > Euclid algorithm would be nice. There are several methods possible. For example, take Lehmer's method D.H. Lehmer. Euclid's algorithm for large numbers. with single precision precalculations (see Knuth, TAOCP Vol. 2) to reduce the time by about 60 percent. Sch.9anhage's first algorithm is in A. Sch.9anhage. Schnelle Berechnung von Kettenbr.9fchen. Acta Informatica 1 (1971), 139-144 and the second algorithm, which is based on the idea of ÔControlled Euclidean Descent' can be found in A. Sch.9anhage, A.F.W. Grotefeld/E.Vetter Fast Algorithms, BI 1994 Regards Peter === Subject: Hard geometry problem this problem seems to be very hard for me. I'd be grateful for hints or solution, cause I've spent long hours working on it: Point O is center of circumcircle on trapezoid ABCD with bases AB and CD. Points K, L, M, N lie respectively on sides AB, BC, CD, DA. Quadrilateral KLMN is rhombus. Prove that point O lays on line KM. Thanks for your help. Michael Swift === Subject: Re: Hard geometry problem > .... > Point O is center of circumcircle on trapezoid ABCD with bases AB and > CD. Points K, L, M, N lie respectively on sides AB, BC, CD, DA. > Quadrilateral KLMN is rhombus. Prove that point O lies on line KM.... You can probably fill in the details of this outline proof. Choose the notation so that DC .b2 AB. Let the parallel to CB through N meet AB at J. (This J is used only to get result (3) below.) Then (1) triangles CLM, JNK are congruent (AAS), and (2) triangle AJN is isosceles. Hence (3) AN = CL. (Is there a shorter _Euclidean_ proof of this? I know it's easy by the sine rule.) Also (4) Angle OAN = angle OBC = angle OCB, so (5) triangles OAN, OCL are congruent (SAS). Thus (6) ON = OL. But also KN = KL and MN = ML, whence easily (7) K, M, O colline. Ken Pledger. === Subject: detecting unbalanced data using minimum representation I encountered the following problem: i have two types of events that arrived to a range, for example: [1,30]. i don't know anything about the distributions of the events, but i want to find if the two events type are balanced, which means, arriving to the same areas in the range or not. Example for the same areas: event e1- 4,5,8,19,20 event e2- 3,4,7,19. Example for unbalanced: event e1- 2,4,5,6 event e2- 13,15,16 I know that i can use histogram to accumulate the arrivals, but it's too expensive (too much space). So I'm looking for a method that allows my to detect this unbalancing but need less space to representation then the histogram. (I know that I might lose data but i can accept it). Thanks a lot, Michal === Subject: Re: An Interesting Question about Stirling's Asymptotic Expansion >>A small comment in this month's issue of _Mathematics Magazine_ >>brings to mind an interesting question about Stirling's asymptotic >>expansion of the gamma function which has been brooding in my mind >>for several months now. On page 370, merely to give an example of the >>use of Bernoulli numbers, Peter Knopf says >>... an extension of Stirling's formula allows us to compute n! to >>arbitrarily good precision: >> n! = (n/e)^n Sqrt(2 pi n) exp( sum(k=1, oo, B_(2k)/((2k-1) 2k n^(2k-1))) ) >>The questionable and interesting part is the claim of arbitrarily >>good precision. After all, the expansion does not converge, being >>merely asymptotic. > I answered too quickly and mixed up two different results. The error, > using a number of terms approximately pi n, definitely seem to be small > enough to make the error less than 1/2. Always, or just until n surpasses some rather large value? That is the unanswered question. > However, using that many terms means more computation than simply > computing n!. Yes. :-) In a private email to someone on this topic, I described the actual computation of n! precisely by this method as being numerical masochism. > I had experimented with computation of n! using Stirling's series many > years ago, and what I was recalling was that for any fixed number of > terms, the asymptotic series would soon give an absolute error greater > than 1/2 (the relative error is inversely proportional to a power of n > while n! grows much faster). The half recollection of this is what > lead me to make the statement I did. However, what I said after is > still true; you can use Stirling's expansion to any number of terms, > compute (n+k)! for a large enough integer k, then use the recursive > relation (n+k)!/(n+k) = (n+k-1)! to compute n! as precisely as needed. Sure, but I seriously doubt that that was what Peter Knopf had in mind. (BTW, I alerted him, by private email, to the existence of this thread. Do you happen to be reading this, Peter?) > However, the asymptotic series for the log of Gamma that you used is not > Stirling's series. Why do you say that? See for example Whittaker and Watson, pp. 252-3: We see therefore that the series ... is the asymptotic expansion of logGamma(z) ... This is generally known as _Stirling's series_. Or perhaps more conveniently, see , jumping down to look at (6) and the prior line. In other words, what is generally known as Stirling's series is not (1) there. > The coefficients of the former are easily described > using Bernoulli numbers; I know of no easy formula for the coefficients > of the latter. I derive a recursive formula in > http://www.whim.org/nebula/math/stirling.html > but that gives no idea of how the sizes of the coefficients behave as n > grows. Is there a non-recursive description of these coefficients that > might be used to get an idea of their size? Might (2) at the link above be of use? David Cantrell === Subject: Re: An Interesting Question about Stirling's Asymptotic Expansion In-reply-to: David W. Cantrell A small comment in this month's issue of _Mathematics Magazine_ >brings to mind an interesting question about Stirling's asymptotic >expansion of the gamma function which has been brooding in my mind >for several months now. On page 370, merely to give an example of the >use of Bernoulli numbers, Peter Knopf says ... an extension of Stirling's formula allows us to compute n! to >arbitrarily good precision: n! = (n/e)^n Sqrt(2 pi n) exp( sum(k=1, oo, B_(2k)/((2k-1) 2k n^(2k-1))) ) The questionable and interesting part is the claim of arbitrarily >good precision. After all, the expansion does not converge, being >merely asymptotic. >> I answered too quickly and mixed up two different results. The error, >> using a number of terms approximately pi n, definitely seem to be small >> enough to make the error less than 1/2. >Always, or just until n surpasses some rather large value? That is the >unanswered question. On , [17] says that asymptotically, n-1 n 2n B ~ (-1) 4 sqrt(pi n) ( ---- ) 2n pi e Plugging this into the formula you quote above, I get that the minimum term in the expansion is on the order of sqrt(2/pi)(n/e^{2pi+1})^n. n (n/e^{2pi+1})^n 1 7*10^{-4} 10 2*10^{-22} 100 5*10^{-117} 1000 9*10^{-164} which is in pretty close agreement with your values of >n error >1 -3*10^(-4) >10 -9*10^(-23) >100 2*10^(-117) >1000 -4*10^(-164) However, when n >= 1456 (e^{2pi+1}), it looks as if things might start to blow up. >> However, using that many terms means more computation than simply >> computing n!. >Yes. :-) In a private email to someone on this topic, I described the >actual computation of n! precisely by this method as being numerical >masochism. >> I had experimented with computation of n! using Stirling's series many >> years ago, and what I was recalling was that for any fixed number of >> terms, the asymptotic series would soon give an absolute error greater >> than 1/2 (the relative error is inversely proportional to a power of n >> while n! grows much faster). The half recollection of this is what >> lead me to make the statement I did. However, what I said after is >> still true; you can use Stirling's expansion to any number of terms, >> compute (n+k)! for a large enough integer k, then use the recursive >> relation (n+k)!/(n+k) = (n+k-1)! to compute n! as precisely as needed. >Sure, but I seriously doubt that that was what Peter Knopf had in mind. >(BTW, I alerted him, by private email, to the existence of this thread. >Do you happen to be reading this, Peter?) I doubt it too. >> However, the asymptotic series for the log of Gamma that you used is not >> Stirling's series. >Why do you say that? See for example Whittaker and Watson, pp. 252-3: >We see therefore that the series ... is the asymptotic expansion of >logGamma(z) ... This is generally known as _Stirling's series_. >Or perhaps more conveniently, see >, jumping down to look >at (6) and the prior line. In other words, what is generally known as >Stirling's series is not (1) there. I guess I had always thought of the non-logarithmic asymptotic expansion as Stirling, but I see that many places call the logarithmic expansion Stirling. I should refrain from saying more lest I display further ignorance (it is better to remain quiet and be thought a fool...). >> The coefficients of the former are easily described >> using Bernoulli numbers; I know of no easy formula for the coefficients >> of the latter. I derive a recursive formula in >> http://www.whim.org/nebula/math/stirling.html >> but that gives no idea of how the sizes of the coefficients behave as n >> grows. Is there a non-recursive description of these coefficients that >> might be used to get an idea of their size? >Might (2) at the link above be of use? Maybe I am being dense, but I don't see how that helps to get a handle on the size of the coefficients any more than (3) does. Which brings up the fact that (3) on wolfram.com looks almost like [7] on my page; however, they apparently differ slightly. This difference is of no consequence when you notice that most terms in each summation appears twice and if you add the coefficients of the repeated terms, they come out the same. I just happen to think that the one on my page looks a bit simpler. Rob Johnson A small comment in this month's issue of _Mathematics Magazine_ >brings to mind an interesting question about Stirling's asymptotic >expansion of the gamma function which has been brooding in my mind >for several months now. On page 370, merely to give an example of >the use of Bernoulli numbers, Peter Knopf says ... an extension of Stirling's formula allows us to compute n! to >arbitrarily good precision: > n! = (n/e)^n Sqrt(2 pi n) exp( sum(k=1, oo, B_(2k)/((2k-1) 2k n^(2k-1))) ) The questionable and interesting part is the claim of arbitrarily >good precision. After all, the expansion does not converge, being >merely asymptotic. >> The error, using a number of terms approximately pi n, definitely seem >> to be small enough to make the error less than 1/2. >Always, or just until n surpasses some rather large value? That is the >unanswered question. > On , [17] says that > asymptotically, > n-1 n 2n > B ~ (-1) 4 sqrt(pi n) ( ---- ) > 2n pi e > Plugging this into the formula you quote above, I get that the minimum > term in the expansion is on the order of sqrt(2/pi)(n/e^{2pi+1})^n. > n (n/e^{2pi+1})^n > 1 7*10^{-4} > 10 2*10^{-22} > 100 5*10^{-117} > 1000 9*10^{-164} > which is in pretty close agreement with your values of >n error >1 -3*10^(-4) >10 -9*10^(-23) >100 2*10^(-117) >1000 -4*10^(-164) > However, when n >= 1456 (e^{2pi+1}), it looks as if things might start > to blow up. I hadn't commented on this before for a couple of reasons. (1) As I noted previously in this thread, |error| starts to increase at n = 536. So I thought n = 1456 was simply wrong. I would have said (and still do say) that things _start_ to blow up, slowly, beginning at n = 536. But I see now that I must have misinterpreted what you meant by things might start to blow up. Rather, I now suppose that you meant that error has, by then, gotten sufficiently big that we can no longer get n! precisely after rounding. I now believe that is correct; see below. (2) My intuition had told me that error probably wouldn't get sufficiently big to preclude getting n! precisely after rounding until n was _much_ bigger than 1000. I was thinking of n = 10000, or more perhaps. Well, my intuition was apparently wrong in this case. I decided to try to discover, approximately, the smallest n such that the asymptotic series cannot be used to give n! precisely after rounding. It wasn't difficult (and I'm now suitably embarrassed that I hadn't done it before!) Surprise: I got n = 1456. (Well, not a surprise to you readers. But remember that I had thought n would need to be bigger than that, and so it surprised me.) And it's good now to have independent confirmation of the value which Rob obtained. BTW, I'm not claiming (and I don't suppose that Rob is either) that the smallest such n is precisely 1456. The smallest such n might be a little more or less than 1456. I am happy now to consider my Interesting Question as having been adequately answered. Thanks, Rob! Best wishes, David Cantrell === Subject: Re: An Interesting Question about Stirling's Asymptotic Expansion > I guess I had always thought of the non-logarithmic asymptotic expansion > as Stirling, but I see that many places call the logarithmic expansion > Stirling. I should refrain from saying more lest I display further > ignorance (it is better to remain quiet and be thought a fool...). Rest assured, Rob, that never, even in my wildest dreams, could I think you a fool. You always have my respect, and I value your comments. (And, after all, we are human. _Errare humanum est_.) >> The coefficients of the former are easily described >> using Bernoulli numbers; I know of no easy formula for the >> coefficients of the latter. I derive a recursive formula in > http://www.whim.org/nebula/math/stirling.html > but that gives no idea of how the sizes of the coefficients behave as >> n grows. Is there a non-recursive description of these coefficients >> that might be used to get an idea of their size? >Might (2) at the link above be of use? > Maybe I am being dense, but I don't see how that helps to get a handle > on the size of the coefficients any more than (3) does. I suspect you're right. Sorry. I didn't mean to toss out a red herring. (2) was not recursive, and I thought that there might be results (unknown to me, perhaps by Comtet) about d_3 which would make (2) useful to you... David === Subject: Re: Area of an Epitrochoid Problem Thank you very, very much. Heheh, didn't expect the thread to get quite this big. Just for the record, I think I've got everything I need now and any more debate over this subject is purely academic which I will leave to you people who are far more intelligent than I. I really appreciate all your help. 8-) ~Don > Area = 9*n^2*(2*Sqrt[15] + 13*Pi - 26*ArcCos[Sqrt[3/2]/2]) > where you can set the n at your discretion to suit the projected space > of your rotor. If you chose n=3 (that implies a=6, b=3, c=18) you get > Area = 2015.4 > Really interesting your epitrochoid. Perhaps someone in this group can > explain if the conditions under which it closes (i.e. the values of > a,b,c) are related with the prime numbers in some interesting way. > Best regards > Carlos L === Subject: Re: Area of an Epitrochoid Problem > I appreciate all your help. I especially would like to thank Lynn and > Carlos, for actually answering the question. With this we'll be able > to machine a precision rotor and housing that will be substantially > larger than the Mazda 1.3 liter Wankel. > Really interesting your epitrochoid. But, as I've mentioned before, probably irrelevant with regard to Wankel rotors. However, if my thinking is wrong, I would like to be corrected. > Perhaps someone in this group can > explain if the conditions under which it closes (i.e. the values of > a,b,c) are related with the prime numbers in some interesting way. It closes, as I indicated before, simply when a/b is rational. (Of course, if a and b are large integers, the curve will be messy. But close it will.) David === Subject: Re: Area of an Epitrochoid Problem > But, as I've mentioned before, probably irrelevant with regard to Wankel > rotors. However, if my thinking is wrong, I would like to be corrected. Hi David: It also seemed a mystery for me how could it be relevant but I've recently found the following photo of a Mazda rotor and its housing does indeed seem to have the shape of the perimeter of an epitochroid of the type mentioned by Don: http://www.revolutionrotary.com/disp1.jpg > Perhaps someone in this group can > explain if the conditions under which it closes (i.e. the values of > a,b,c) are related with the prime numbers in some interesting way. > It closes, as I indicated before, simply when a/b is rational. (Of course, > if a and b are large integers, the curve will be messy. But close it will.) Yes, I see. I missed that in your earlier post. (I have the obsession to find the secret of the primes everywhere;) > David Best regards Carlos L charlesla @ jazzfree . com === Subject: Re: Area of an Epitrochoid Problem Hi Carlos, Your important word below is seem. For example, most people who haven't studied the catenary would look at a hanging chain and say that its shape is the parabola. But of course, they'd be wrong. You can't tell what shape a curve has by mere visual inspection. (But I suppose you already knew that.) > It also seemed a mystery for me how could it be relevant but I've > recently found the following photo of a Mazda rotor and its housing > does indeed seem to have the shape of the perimeter of an > epitochroid of the type mentioned by Don: > http://www.revolutionrotary.com/disp1.jpg Thanks for that photo. Well, to my eye, the shape looks more like, say, a Cassinian oval, than a epitrochoid. But of course, I'm certainly not saying that it actually _is_ a Cassinian oval, mind you. Best regards, David === Subject: Re: Area of an Epitrochoid Problem > But, as I've mentioned before, probably irrelevant with regard to Wankel > rotors. However, if my thinking is wrong, I would like to be corrected. The epitrochoid is the shape of the housing that the rotor rotates inside. The inside of the actual motor doesn't look like it very much simply because the value c (which by pure experimentation I've realized controls the sharpness of the two points at which the curve intersects itself) is very large. You were right on the Reuleaux triangle as the shape of the rotor. There's a planetary gear system inside the rotor which allows it to move up and down as the edges traverse the inside perimeter of the housing. I'll eventually have to find the area of the rotor as well, but that'll be very easy compared to the epitrochoid. ~Don Here you go! I will be preparing the answers I have (there's a bunch I still lack) and hope to post them later tonight. In time I will collect the questions and good responses I see into a file which will be at http://www.math.niu.edu/~rusin/problems-math/ Sorry in advance about typos below. dave A1 Let n be a fixed positive integer. How many ways are there to write n as a sum off positive integers, n = a_1 + a_2 + ... + a_k, with k an arbitrary positive integer and a_1 le a_2 l3 .. a_k le a_1 + 1? For example, with n=4 there are four ways: 4, 2+2, 1+1+2, 1+1+1+1. A2 Let a1, a2, ..., a_n and b1, b2, ..., b_n be nonnegative real numbers. Show that (a1 a2 ... a_n)^{1/n} + (b1 b2 ... b_n)^{1/n} <= ( (a1+b1) (a2+b2) ... (a_n + b_n) )^{1/n} A3 Find the minimum value of | sin x + cos x + tan x + cot x + sec x + csc x | for real numbers x. A4 Suppose that a,b,c,A,B= int_0^1 |f(x)| dx. >In time I will collect >the questions and good responses I see into a file which will be at > http://www.math.niu.edu/~rusin/problems-math/ In that directory there are now two new files, putnam.03probs -- the questions (as I posted them previously, sans typos) putnam.03 -- collected answers I am happy to report that there now seem to be answers for each of the questions, some very slick and elegant, others hinting at broader contexts. (I'm always on the lookout for alternative proofs, so if your solution is distinctly different from any in the files, let me know and I can add your answers!) dave >>In time I will collect >>the questions and good responses I see into a file which will be at >> http://www.math.niu.edu/~rusin/problems-math/ >In that directory there are now two new files, > putnam.03probs -- the questions (as I posted them previously, sans typos) > putnam.03 -- collected answers It's possible that there could be readers who don't realize that they can get the second file by pointing a web browser at http://www.math.niu.edu/~rusin/problems-math/putnam.03 . >I am happy to report that there now seem to be answers for each of the >questions, some very slick and elegant, others hinting at broader contexts. >(I'm always on the lookout for alternative proofs, so if your solution >is distinctly different from any in the files, let me know and I can >add your answers!) Well this morning I was pissed I didn't have a solution to B6 - so you can imagine how I felt when you recorded my pissed-off non-solution there following an actual solution. So I thought about it. It's easy if int f = 0, which seems like it should be the hard case, for example it's trivial if f >= 0. This morning I was going to say just as a joke that you could get a solution in general by interpolating between these two cases. But it turns out that you can do exactly that. The part you want to record for posterity starts here: It's clear if f >= 0. Suppose that int f = 0. Choose a function g so that |g| = 1 and gf >= 0. Then int int |f(x) + f(y)| >= int (f(x) + f(y)) g(x) = int f(x) g(x) = int |f(x)|. You can do the general case by interpolating between these special cases: Suppose that int f > 0. Then f = g + h, where int g = 0, h >= 0, and g and h have disjoint support. Say g is supported on A and h is supported on B. Then int int |f(x) + f(y)| >= int_A int_A |f(x) + f(y)| + int_B int_B |f(x) + f(y)| = int int |g(x) + g(y)| + int int (h(x) + h(y)) >= int (|g(x)| + h(x)) = int |f(x)|. >dave ************************ Here are some answers to this year's Putnam questions. Suffering the ravages of old age, perhaps, I didn't finish as many as I usually do. Maybe the questions were a bit harder this year; certainly quite a few of them caused me to spin my wheels pursuing the wrong usual trick for too long. I have no answers here for: A2, A4 and A5 (probably not hard), and B6. My answer for A6 clearly misses some pretty idea. Hmm, maybe I just wasn't really awake for the morning session! Questions appeared in a previous post. A1 Let m be the number of summands equal to a_1 ; the other k-m (possibly zero) summands will be equal to (a_1)+1, and so the sum will be n = m a_1 + (k-m) (a_1 + 1) = k a_1 + (k-m). Since 0 <= k-m < k, this equation precisely represents the division algorithm with divisor k, that is, there is precisely one such pair ( a_1 , m ) associated to each value of k. So the number of such representations is precisely the number of possible summands, which is n. A2 No clue. The question can be interpreted as: Show that the aritmetic mean of the geometric means is no bigger than the geometric mean of the arithmetic means, which is a nice question. A3 Write x in the form x = z - 3 pi / 4. Since cos(-3 pi/4)= sin(-3 pi/4) = -1/sqrt(2), we can expand the other trig functions in terms of c = cos(z), x = sin(z) : sin(x) = -1/sqrt(2) (c + s) cos(x) = -1/sqrt(2) (c - s) and so on. The expression inside the absolute value signs is then E = -sqrt(2) c + (c+s)/(c-s) + (c-s)/(c+s) - sqrt(2) (1/(c+s) + 1/(c-s)) = -sqrt(2) c + (2)/(c^2-s^2) - sqrt(2) (2c)/(c^2-s^2) = -sqrt(2) c - (2)(sqrt(2)c - 1)/(2c^2-1) = -sqrt(2) c - (2)/(sqrt(2) c + 1) = -( x + 2/(x + 1) ) where I have set x = sqrt(2) c for brevity. This expression clearly has a (local) exteme magnitude only when 1 = 2/(x+1)^2, i.e. x=-1 +- sqrt(2) (although only x = -1 + sqrt(2) is possible as we must have x = sqrt(2) cos(z) > -sqrt(2) .) There, the value is E = -( 2 sqrt(2) -1 ) so that the minimum value of the absolute value is 2 sqrt(2) - 1 = 1.828... Remark: other rational parameterizations of the function, in one free or two constrained variables, lead to quite a bit of algebra which takes far too much time to be useful. Trust me when I make this claim... A4 No good answer. If the larger quadratic has real roots this is not hard, but otherwise I wasn't sure how to proceed past reducing the problem to the case with A=C=1,B=0. Clearly this suggests a sequence of results of the form |p(x)| <= |P(x)| for all x iff ..., ending with a condition stated independent of x, presumably refering to the discriminants of p and P and perhaps some other invariants. But I didn't spend much time on this one. A5 Did not spend any time on this one. Probably not hard. A6 The answer seems to be yes, it is possible, but right now all I have is a very inelegant answer. The partition is very naturally constructed by considering each small n in turn, but I don't see any argument which is both convincing and brief which guarantees that the process can be followed ad infinitum. Here is the sequence: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... A B B A B A A B B A A B A B B ... continuing by setting n to be in A iff n-12 is. A completely uninspired check will show that if this sequence is reversed and then shifted forward by 0, 1, ..., 11 steps, and then placed directly beneath the original sequence, then the number of times two A's align (between n=1 and n=12 inclusive) and the number of times two B's align will be equal. So for example when calculating r_A(n) and r_B(n) when n is of the form 24k+1, we will find 12k unordered pairs {s1, s2} whose sum is n, and we find that when we check whether s1 and s2 are in A or B, we simply repeat our computations k times; each time we find equal numbers of A+A pairs as B+B pairs (and of course many A+B pairs). Therefore r_A(n) = r_B(n) when n = 1 mod 24. Similar arguments hold for any n : in every set of 12 the A+A and B+B pairs are equinumerous, so we only need to consider the leftover summand nearest to n/2. If n = 24k + 2r, we will pair a number congruent to 1 with a number congruent to 2r-1 mod 12, as well as 2 and 2r-2, 3 and 2r-3, and so on (through r-1 and r+1). For each r we can conduct this experiment and find that the numbers of A+A and B+B pairs are equal. A similar experiment applies when n = 24k + 2r + 1 So the pattern seems to check out but this argument is dreadfully dull and says nothing about the obvious conjectures one is tempted to make to extend the problem. B1 No such polynomials exist. The proof here is a version of Richard Blecksmith's. We can use m x n matrices to represent polynomials of bidegree (m-1,n-1), setting M to correspond with the matrix product f(x,y) = (1, x, ..., x^{m-1}) M (1, y, ..., y^{n-1})^t . Given a set of x's and y's we can compute the matrix F of values F_{i,j} = F( x_i, y_j ) similarly as a product X M Y' . In particular, from the invertibility of Vandermonde matrices we see that the matrix M can be recovered from a few values of f . Now we simply note that if f(x,y) = a(x) c(y) then the corresponding M is simply the product of the column matrix of coefficients of a and the row matrix of coefficients of c, and is in particular of rank at most 1. Similarly f(x,y) = a(x) c(y) + b(x) d(y) corresponds to a matrix of rank 2. On the other hand, f(x,y) = 1 + x y + x^2 y^2 corresponds to the matrix diag(1,1,1,0,0,0...) of rank 3, and so cannot be represented in the given form. I had some other clever ideas for this proof but they all seemed to require an examination of many potential coefficients of small polynomials at the end; I suspect many other people will also have wasted far too much time on what is traditionally the easy problem of the afternoon! B2 Given any sequence a_1, a_2, ... we can form the succession of averages a'_1, a'_2, ... as in the problem, and then iterate to get further sequences a^(k)_1, a^(k)_2, ... . It is easily checked by induction that a^(k) _ n = (1/2^k) sum_{j=0} ^ k binomial(k,j) a_{n+j} In particular, the sequence in the problem leads to x_n = a^(n-1) _ 1 = (1/2^{n-1}) sum_{j=0}^{n-1} binomial(n-1,j) / (1+j). If we let F(t) = sum_{j=0} ^ {n-1} binomial(n-1,j) t^{j+1} / (j+1) then our x_n = 1/2^{n-1} F(1). On the other hand, F'(t) is just the expansion of sum binomial (t+1)^{n-1}, and F(0)=0, so that F(1) = int_0^1 (t+1)^{n-1} dt = (1/n) (t+1)^n | _0^1 = (2^n - 1)/n Thus x_n = (2 - 2^{1-n})/n < 2/n . B3 It suffices to show that the two integers have the same prime factorizations. If p is a prime, then its multiplicity in n! is well known (and easy to check) to be [n/p] + [n/p^2] + [n/p^3] + ... On the other hand, the multiplicity of p in lcm{1, 2, ..., k} is r iff p^r <= k <=p^{r+1}, and so the multiplicity in lcm{1, 2, ..., [n/i]} is r iff p^r <= n/i < p^{r+1} i.e. n/p^r >= i > n/p^{r+1}. The number of such integers i is [n/p^r] - [n/p^{r+1}], and therefore the i's in this range contribute r*([n/p^r] - [n/p^{r+1}]) powers of p to the product. Summing, then, over all possible values r, we get a total of sum_{r=0}^infty r ([n/p^r] - [n/p^{r+1}]) = sum_{r=0}^infty [n/p^r] ( r - (r-1) ) = sum [n/p^r] which agrees with the number from the first paragraph. B4 Let s1 = r1 + r2, s2 = r3 + r4; p1 = r1 r2, p2 = r3 r4. The relations between the roots and coefficients of f may now be written -b/a = s1 + s2 +c/a = p1 + p2 + s1 s2 -d/a = p1 s2 + p2 s1 +e/a = p1 p2 We can write the middle pair in matrix form as [ 1 1 ] [ p1 ] [ c/a - s1 s2 ] [ ] [ ] = [ ] [ s1 s2 ] [ p2 ] [ -d/a ] If s1 and s2 are different, the matrix is invertible and we can express p1 ans p2 as rational functions of a,c,d, s1, and s2=(-b/a)-s1. So clearly if s1 is rational and a,b,c,d are integers, then p1 and p2 are rational. (We don't need to know e is an integer, but it turns out to have to be rational.) B5 The area of the triangle with side lengths a,b,c is given by Heron's formula; 16 Area^2 = 2(a^2b^2 + a^2c^2 + b^2c^2) - (a^4+b^4+c^4). Once we know the values of a,b,c in terms of the distance r from P to O, it follows that we can determine the area of the triangle. (We are also supposed to check that the triangle inequalities a <= b+c etc. hold, but if say a is the largest of the three lengths, then a+b+c, a-b+c, and a+b-c are all positive, and the positivity of -a+b+c is then equivalent to the positivity of the product of these four expressions, which is precisely the formula I have noted is 16 Area^2; that is, what is supposed to be a perfect square will indeed be nonnegative iff the triangle inequalities hold.) So the question is how to determine a, b, and c from r. There is a polynomial in six variables A,B,C,D,E,F which expresses the square of the volume of a tetrahedron the squares of whose sides are A,B,C,D,E,F . Setting that polynomial equal to zero then gives a condition on the six lengths between four points which is equivalent to the points being coplanar. I never remember the formula and I spent too much time rederiving it on the exam! Here it is: 0 = (A B D + A B E + A C D + A C F + A D E + A D F + B C E + B C F + B D E + B E F + C D F + C E F ) - (A B F + A C E + B C D + D E F) - (A D^2 + D A^2 + B E^2 + E B^2 + C F^2 + F C^2 ) where A,B,C are the squares of the lengths common to a single vertex P and each of the pairs {A,D}, {B,E}, {C,F} involves all four vertices. Applying this relation to the points P,O,A,B, where the six squared-lengths are A,B,C,D,E,F = r^2,a^2,b^2,3,1,1 we get the relation 2 2 4 4 2 2 2 2 2 4 a b + a + b - 3 a - 3 b + 3 - (3 a + 3 b - 3) r + 3 r = 0 There are two analogous relations involving a,c,r and b,c,r respectively. We can also apply the relation to the points P,A,B,C, obtaining the relation 2 2 2 2 2 2 2 2 2 4 4 4 b c + a c + a b + 3 a + 3 b + 3 c - a - b - c - 9 = 0 That's three equations in four unknowns, and we can use them to solve for a,b,c in terms of r. Here's how we may do this. There are two symmetric functions in use here: S1 = a^2+b^2+c^2 and S2 = a^2b^2 + b^2c^2 + c^2a^2. We can express our symmetric expressions in terms of these: for example a^4+b^4+c^4 = S1^2-2S2 and 16 Area^2 = 4 S2 - S1^2. The last relation above states that S2 = S1^2/3 - S1 + 3, so that in effect we can express everything in terms of S1. Finally, the sum of the initial relations is also symmetric: (S2 + 2(S1^2-2S2) -6S1+9) - (6S1-9)r^2 + 9r^4 = 0. Substituting out S2 this becomes (S1^2 - 3S1) - (6 S1-9)r^2 + 9r^4 = 0. which factors, giving two possible values for S1 : S1 = 3 r^2 or S1 = 3 (r^2 + 1). The first solution is incompatible with the observed value for S1 = a^2+b^2+c^2 when r=0, and then by continuity we observe S1 must be the other value, 3(r^2+1), for all r. (It's also true for most small r that taking S1=3r^2 would lead to a negative value of a^4+b^4+c^4 !) This value of S1 then leads to S2 = 3(r^4-r^2+1). Heron's formula for the area of the triangle can also be expressed in terms of S1 and S2 as 4 S2 - S1^2 = (S1-6)^2/3 , which is now 3(r^2-2)^2. I have to say this is an awful lot of algebra; there must be a better way. Since I couldn't even remember the tetrahedron formula during the exam, I got nowhere at first; now I'm doing the calculations with Maple to make sure at least some of them are right -- obviously not permitted during the exam. B6 No clue. The result is surely also true for any measurable function, so it makes sense to prove it in that context. Then it will suffice to prove the inequality within epsilon (arbitrary); with that liberty we may replace f with a simple function, and we find that the only thing that matters is the measures of the sets on which f takes on a few values. Thus it will suffice to prove the result for increasing step functions. But I'm missing some key insight for that -- even proving this for a function f(x) = { a, if 0 < x < r ; b, if r < x < 1 } seems to lead to an inequality to be proved which involves the parameters a, b, and r , and takes some care to pin down. Two observations: It's easy to prove a similar reverse inequality: 2int |f| >= int int | f(x) + f(y) | dx dy and this one is an equality if f never changes sign. So the proposed inequality is fairly sharp. (In the example of the previous paragraph, if a=1,b=-1, and r=1/2, the inequality we have to prove is an equality.) Second, the problem may be interpreted as follows: given a random-number generator, producing reals (positive and negative) according to some distribution, the expected absolute value of the sum of two of them is at least equal to the expected absolute value of a single one. I think that makes it an interesting question. (You might also find that the previous paragraph makes more sense with this interpretation.) >Here are some answers to this year's Putnam questions. >Suffering the ravages of old age, perhaps, I didn't finish as many >as I usually do. Maybe the questions were a bit harder this year; >certainly quite a few of them caused me to spin my wheels pursuing >the wrong usual trick for too long. >I have no answers here for: A2, A4 and A5 (probably not hard), and B6. B6 pisses me off, because it looks like the sort of thing that _I_ should be able to do but I spent an hour or so spinning my wheels. Seems like it must be well-known in probability; (as I see you point out below) it just says that if X and Y are iid then E(|X+Y|) >= E(|X|). >[...] >B6 >No clue. The result is surely also true for any measurable function, so >it makes sense to prove it in that context. Then it will suffice to >prove the inequality within epsilon (arbitrary); with that liberty we >may replace f with a simple function, and we find that the only thing >that matters is the measures of the sets on which f takes on a few >values. Thus it will suffice to prove the result for increasing step >functions. But I'm missing some key insight for that -- even proving >this for a function > f(x) = { a, if 0 < x < r ; b, if r < x < 1 } >seems to lead to an inequality to be proved which involves the parameters >a, b, and r , and takes some care to pin down. >Two observations: It's easy to prove a similar reverse inequality: > 2int |f| >= int int | f(x) + f(y) | dx dy >and this one is an equality if f never changes sign. So the proposed >inequality is fairly sharp. (In the example of the previous paragraph, >if a=1,b=-1, and r=1/2, the inequality we have to prove is an equality.) >Second, the problem may be interpreted as follows: given a random-number >generator, producing reals (positive and negative) according to some >distribution, the expected absolute value of the sum of two of them >is at least equal to the expected absolute value of a single one. >I think that makes it an interesting question. (You might also find that >the previous paragraph makes more sense with this interpretation.) There's a simple proof in the case when the integral of f is 0. (What pisses me off is that it seems like this should be the hardest case - if f >= 0 it's clear, for example...) Choose a function g so that |g| = 1 and gf >= 0. Then int int |f(x) + f(y)| >= int int (f(x) + f(y)) g(x) = int f(x) g(x) = int |f| . This proof also works if int g = 0, ie if there exists a set A with |A| = 1/2, such that f >= 0 on A and f <= 0 off A. Which again seems like it should be the hard case; if f has more positive values than negative values it should be easier... ************************ Here's another proof for A2: If any b_i = 0, it's trivial, so we may assume WLOG that each b_i = 1. For 0<=k<=n, consider the nCk ways to take a product of k distinct and taking n-th roots gives (a1 a2 ... a_n)^(1/n) + 1 <= (a1+1)(a2+1)...(a_n+1), since GM_k = (a1 a2 ... a_n)^[(n-1)C(k-1)]/[nCk] = (a1 a2 ... an)^(k/n). > A2 > No clue. The question can be interpreted as: Show that the aritmetic > mean of the geometric means is no bigger than the geometric mean of > the arithmetic means, which is a nice question. Sure is a nice result, but I thought it was the easiest.. first, note that the result is trivial if a_1a_2...a_n=0. Thus, put b_1/a_1=t_1, b_2/a_2=t_2, .. Then the inequality becomes : 1+(t_1t_2...t_n)^1/n <= ((1+t_1)(1+t_2)..(1+t_n))^1/n. Raising to nth power on both sides, we need to show that : 1+sum(t_i)+sum(t_it_j) + .. + t_1t_2...t_n >= 1+C(n,1)(t_1t_2..t_n)^1/n + ... +C(n,n)t_1t_2...t_n. (RHS is the binomial expansion). Now, the (r+1)th term on the LHS is the sum of the products of t_i's taken r at a time. Each t_i occurs precisely inequality, we have (r+1)th term on LHS >= C(n,r)(t_1t_2...t_n)^(C(n-1,r-1)/C(n,r)) = C(n,r)(t_1t_2..t_n)^(r/n), which is the (r+1)th term on the RHS. > A3 > Write x in the form x = z - 3 pi / 4. Since cos(-3 pi/4)= sin(-3 pi/4) = > -1/sqrt(2), we can expand the other trig functions in terms of > c = cos(z), x = sin(z) : > sin(x) = -1/sqrt(2) (c + s) > cos(x) = -1/sqrt(2) (c - s) > and so on. The expression inside the absolute value signs is then > E = -sqrt(2) c + (c+s)/(c-s) + (c-s)/(c+s) - sqrt(2) (1/(c+s) + 1/(c-s)) > = -sqrt(2) c + (2)/(c^2-s^2) - sqrt(2) (2c)/(c^2-s^2) > = -sqrt(2) c - (2)(sqrt(2)c - 1)/(2c^2-1) > = -sqrt(2) c - (2)/(sqrt(2) c + 1) > = -( x + 2/(x + 1) ) > where I have set x = sqrt(2) c for brevity. This expression clearly > has a (local) exteme magnitude only when 1 = 2/(x+1)^2, i.e. x=-1 +- sqrt(2) > (although only x = -1 + sqrt(2) is possible as we must have > x = sqrt(2) cos(z) > -sqrt(2) .) There, the value is E = -( 2 sqrt(2) -1 ) > so that the minimum value of the absolute value is 2 sqrt(2) - 1 = 1.828... > Remark: other rational parameterizations of the function, in one free or > two constrained variables, lead to quite a bit of algebra which takes > far too much time to be useful. Trust me when I make this claim... > A4 > No good answer. If the larger quadratic has real roots this is not > hard, but otherwise I wasn't sure how to proceed past reducing the > problem to the case with A=C=1,B=0. Clearly this suggests a sequence > of results of the form |p(x)| <= |P(x)| for all x iff ..., ending > with a condition stated independent of x, presumably refering to the > discriminants of p and P and perhaps some other invariants. > But I didn't spend much time on this one. First, we may suppose that A and a are both >0. This is because if they are not, we may reverse the sign of B, C and/or b,c. Now, note first that B^2-4AC>=0 because if not, p has to vanish at the roots of P for the condition to be satisfied. Then, these become two quadratics with same roots.. so one must be a constant times other.. this case is trivial. Thus, suppose B^2-4AC>=0. If b^2-4ac<0, we are through, so assume b^2-4ac>=0. Now, |P(-B/2A)|>=|P(-b/2a)|>= |p(-b/2a)|. (The first holds because B^2-4AC>=0.) This implies that: |B^2-4AC|/|A|>=|b^2-4ac|/|a|... (I). Now, note that A>=a, because, we assumed A>0 and a>0 and if A=a implying that |b^2-4ac|/|a| >= |b^2-4ac|/|A|. This along with (I)gives the result. > A5 > Did not spend any time on this one. Probably not hard. We can prove that the numbers are equal by brute force, but it is not probably the expected way, as a bijection was asked. > A6 > The answer seems to be yes, it is possible, but right now all I have > is a very inelegant answer. The partition is very naturally constructed > by considering each small n in turn, but I don't see any argument which > is both convincing and brief which guarantees that the process can be > followed ad infinitum. > Here is the sequence: > 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... > A B B A B A A B B A A B A B B ... > continuing by setting n to be in A iff n-12 is. > A completely uninspired check will show that if this sequence is reversed > and then shifted forward by 0, 1, ..., 11 steps, and then placed directly > beneath the original sequence, then the number of times two A's align > (between n=1 and n=12 inclusive) and the number of times two B's align > will be equal. So for example when calculating r_A(n) and r_B(n) when > n is of the form 24k+1, we will find 12k unordered pairs {s1, s2} whose > sum is n, and we find that when we check whether s1 and s2 are in A or B, > we simply repeat our computations k times; each time we find equal > numbers of A+A pairs as B+B pairs (and of course many A+B pairs). > Therefore r_A(n) = r_B(n) when n = 1 mod 24. > Similar arguments hold for any n : in every set of 12 the A+A and B+B pairs > are equinumerous, so we only need to consider the leftover summand > nearest to n/2. If n = 24k + 2r, we will pair a number congruent to 1 > with a number congruent to 2r-1 mod 12, as well as 2 and 2r-2, 3 and 2r-3, > and so on (through r-1 and r+1). For each r we can conduct this experiment > and find that the numbers of A+A and B+B pairs are equal. A similar > experiment applies when n = 24k + 2r + 1 > So the pattern seems to check out but this argument is dreadfully dull and > says nothing about the obvious conjectures one is tempted to make to > extend the problem. A={0,3,5,6,9,10,12,15,... B={1,2,4,7,8,11,13,14,... You first form A with 2^k elements, B with 2^k elements, so that the elements upto 2^(k+1) are used. Next, add the elements of B+2^(k+1) to A, and initial elements of A+2^(k+1) to B. This forms 2^(k+1) elemental sets A, B. Continuing this process, it can easily be seen to give the required partition. (For eg, the 16 elemental set formed from the above A, B includes the foll in A.. 16+1, 16+2, 16+4, 16+7, 16+8, 16+11, 16+13, 16+14 and the foll in B.. 16+0, 16+3, 16+5, 16+6, 16+9, 16+10, 16+12, 16+15. The next step involves the 16 elements in A and B which are now formed. (I hope I have made myself fairly clear.. but it is right.) ------ Bhaskara Aditya Some comments: A2 This problem appeared on the 1992 Irish Mathematical Olympiad: http://www.kalva.demon.co.uk/irish/irish92.html A6 This problem appears, among other places, in A Problem Seminar by D. J. Newman. His solution uses generating functions: Let f(x) = sum_{a in A} x^a and g(x) = sum_{b in B} x^b, and assume 0 is in A. Then f(x) + g(x) = 1/(1 - x), and the given property translates as f^2(x) - f(x^2) = g^2(x) - g(x^2). He then derives that f(x) - g(x) = (1 - x)(1 - x^2)(1 - x^4)(1 - x^8)..., so we get that A is the set of numbers with an even number of 1s in the binary expansion, and B is the set of numbers with an odd number of 1s. There is also a reference in Sloane's sequence database: http://www.research.att.com/cgi-bin/access.cgi/as/njas/ sequences/eisA.cgi?An um=A000069 http://www.research.att.com/cgi-bin/access.cgi/as/njas/ sequences/eisA.cgi?An um=A001969 B5 Assume that A, B, and C are on the circle counter-clockwise. Rotate P 60 degrees clockwise around A, B, and C, to points D, E, and F, respectively. Then triangles APD, BPE, and CPF are all equilateral, with side lengths a, b, and c, respectively. Furthermore, the same rotation around A which takes P to D, also takes C to B, so triangle APC is congruent to triangle ADB, which implies that BD = PC = c. Hence, triangle BPD has side lengths a, b, and c, which proves the first part. Let K be the area of this triangle. As shown, triangle APC is congruent to triangle ADB. Similarly, triangle BPA is congruent to triangle BEC, and triangle CPB is congruent to triangle CFA. Therefore, hexagon ADBECF has twice the area of triangle ABC. But hexagon ADBECF also consists of the three congruent triangles PDB, PEC, and PFA, and three equilateral triangles PAD, PBE, and PCF. Thus, K is a function of a^2 + b^2 + c^2. Then (say, using coordinates), you can work out that a^2 + b^2 + c^2 is a function of OP. I saw essentially this problem on an olympiad last year, but I don't remember which country. N. Sato En el mensaje: de02c249.0312071813.5284bd24@posting.google.com, N. Sato dijo: > B5 > Assume that A, B, and C are on the circle counter-clockwise. Rotate P > 60 degrees clockwise around A, B, and C, to points D, E, and F, > respectively. Then triangles APD, BPE, and CPF are all equilateral, > with side lengths a, b, and c, respectively. Furthermore, the same > rotation around A which takes P to D, also takes C to B, so triangle > APC is congruent to triangle ADB, which implies that BD = PC = c. > Hence, triangle BPD has side lengths a, b, and c, which proves the > first part. Let K be the area of this triangle. > As shown, triangle APC is congruent to triangle ADB. Similarly, > triangle BPA is congruent to triangle BEC, and triangle CPB is > congruent to triangle CFA. Therefore, hexagon ADBECF has twice the > area of triangle ABC. But hexagon ADBECF also consists of the three > congruent triangles PDB, PEC, and PFA, and three equilateral triangles > PAD, PBE, and PCF. It last is obvious only if P is inner to the triangle, althougt if P is outer of triangle, but inner to the circle it is also true. If is outer the circle, the hexagon ADBECF can be autocrossing. Then, it can view that the area of the hexagon is the difference of the are of the three triangles of sides a, b an c and the triangle ABC. > Thus, K is a function of a^2 + b^2 + c^2. Then > (say, using coordinates), you can work out that a^2 + b^2 + c^2 is a > function of OP. I If OA = r and OP = k, a^2 = k^2 + r^2 - 2k*r*cos(alfa) b^2 = k^2 + r^2 - 2k*r*cos(beta) c^2 = k^2 + r^2 - 2k*r*cos(gamma) a^2 + b^2 + c^2 = 3(k^2 + r^2) - 2k*r(cos(alfa) + cos(beta) + cos(gamma)) But r(cos(alfa) + cos(beta) + cos(gamma)) is the component in the direction of OP of the sum of vectors OA, OB and OC, that is null. Then a^2 + b^2 + c^2 = 3(k^2 + r^2) and (APF) = (2(ABC) - (APD) - (BPE) - (CPF))/3 (ABC) = 3*sqrt(3)r^2/4 (APD) = sqrt(3)a^2/4, ... K = (APF) = (sqrt(3)/4)(r^2 - k^2) If P is out of the circle, K = (sqrt(3)/4)(k^2 - r^2) i.e. K = (sqrt(3)/4)|r^2 - k^2| -- Best regards, Ignacio Larrosa Ca.96estro A Coru.96a (Espa.96a) ilarrosaQUITARMAYUSCULAS@mundo-r.com > Here are some answers to this year's Putnam questions. > Suffering the ravages of old age, perhaps, I didn't finish as many > as I usually do. Maybe the questions were a bit harder this year; > certainly quite a few of them caused me to spin my wheels pursuing > the wrong usual trick for too long. > I have no answers here for: A2, A4 and A5 (probably not hard), and B6. > My answer for A6 clearly misses some pretty idea. Hmm, maybe I just > wasn't really awake for the morning session! > Questions appeared in a previous post. > A1 > Let m be the number of summands equal to a_1 ; the other k-m > (possibly zero) summands will be equal to (a_1)+1, and so the sum > will be n = m a_1 + (k-m) (a_1 + 1) = k a_1 + (k-m). Since 0 <= k-m < k, > this equation precisely represents the division algorithm with divisor k, > that is, there is precisely one such pair ( a_1 , m ) associated to > each value of k. So the number of such representations is precisely > the number of possible summands, which is n. Just want to see if the solution I used works. I basically said the following: Let n > 0 and we will show that for each length k between 1 and n inclusive, there is exactly one sequence of numbers of length k satisfying the inequalities that sums to n. To show this I just used an induction like argument. For each length k, take the k-length sequence that sums to n-1 and increment the smallest element. Now it sums to n, and it satisfies the desired inequalities. For the sequence of length n, it clearly has to be all 1's. QED. Do you think this is worth full credit? > A3 > Write x in the form x = z - 3 pi / 4. Since cos(-3 pi/4)= sin(-3 pi/4) = > -1/sqrt(2), we can expand the other trig functions in terms of > c = cos(z), x = sin(z) : > sin(x) = -1/sqrt(2) (c + s) > cos(x) = -1/sqrt(2) (c - s) > and so on. The expression inside the absolute value signs is then > E = -sqrt(2) c + (c+s)/(c-s) + (c-s)/(c+s) - sqrt(2) (1/(c+s) + 1/(c-s)) > = -sqrt(2) c + (2)/(c^2-s^2) - sqrt(2) (2c)/(c^2-s^2) > = -sqrt(2) c - (2)(sqrt(2)c - 1)/(2c^2-1) > = -sqrt(2) c - (2)/(sqrt(2) c + 1) > = -( x + 2/(x + 1) ) > where I have set x = sqrt(2) c for brevity. This expression clearly > has a (local) exteme magnitude only when 1 = 2/(x+1)^2, i.e. x=-1 +- sqrt(2) > (although only x = -1 + sqrt(2) is possible as we must have > x = sqrt(2) cos(z) > -sqrt(2) .) There, the value is E = -( 2 sqrt(2) -1 ) > so that the minimum value of the absolute value is 2 sqrt(2) - 1 = 1.828... I tried differentiating and setting the result equal to 0. I came up with sin(x)=cos(x) as one set of critical points, and cos(x) = 2sin(x)/(1-sin(x)) as another set of critical points. I ended up messing up with calculation though and then got the wrong answer. Hopefully I can get some partial credit. > B1 > I had some other clever ideas for this proof but they all seemed to require > an examination of many potential coefficients of small polynomials at the > end; I suspect many other people will also have wasted far too much time > on what is traditionally the easy problem of the afternoon! I spent a while on this one for the reason you say. I had lots of equations in many variables. I finally found two that work, although I can't remember what they were. You end up only needing 3 though. They are something like: AB + CD = 0 AE + CF = 0 AG + CH = 1 I had another clever idea by noting that xy = k, where k is a third root of unity, is a root of x^2y^2 + xy + 1. Hence if y = k/x then RHS is 0. I tried then replacing y with k/x and trying to plug into the other side, but it seemed too complicated. There might be some neat trick with this. I had another idea to show that if a(x) b(y) + c(x) d(y) can be written as a polynomial in the variable xy, then we might be able to find some conditions on a, b, c, and d. Then use those conditions to show that for this polynomial, a, b, c, and d can't exist. So that might be something else to try. > B4 > Let s1 = r1 + r2, s2 = r3 + r4; p1 = r1 r2, p2 = r3 r4. The relations > between the roots and coefficients of f may now be written > -b/a = s1 + s2 > +c/a = p1 + p2 + s1 s2 > -d/a = p1 s2 + p2 s1 > +e/a = p1 p2 > We can write the middle pair in matrix form as > [ 1 1 ] [ p1 ] [ c/a - s1 s2 ] > [ ] [ ] = [ ] > [ s1 s2 ] [ p2 ] [ -d/a ] > If s1 and s2 are different, the matrix is invertible and we can > express p1 ans p2 as rational functions of a,c,d, s1, and s2=(-b/a)-s1. > So clearly if s1 is rational and a,b,c,d are integers, then p1 and > p2 are rational. (We don't need to know e is an integer, but it > turns out to have to be rational.) This was by far the easiest problem on the exam, in my opinion. There's no trick, or anything. Just replace r1+r2 with m/n, and multiply it out. I thought I was missing something, because B4 should be pretty tough. I think this may work for A5: Take a Dyck path of size n with descents {d_1,d_2,...,d_k}. If d_k is even, prefix the path with an upstep, and append a down step to the end. The resulting path has only one descent of size 1+d_k If d_k is odd, d_k-1 is even, place an upstep at the beginning, a downstep at the end of the k-1'st descent. The resulting path has descents of size 1+d_(k-1) and d_k If d_k, d_k-1 are both odd, d_k-2 is even, place an upstep at the beginning and a downstep at the end of the k-2'nd descent, leaving a path with descents 1+d_k-2, d_(k-1), and d_k . . . If all the d_i are already odd, place a up and down step before the path we already have. To go the other direction, drop the first upstep and the first downstep which goes from height one to height zero. It turns out the number of such paths is given by the Catalan numbers, and this problem is part of an exercise in Stanley's enumerative combinatorics book asking for 2,145 bijections between 66 ways of counting the Catalan numbers. (If anyone got this problem by having done the entire exercise already, I say they deserve the points on the Putnam!) Bummer. The best I could come up with during the test was a brute force method and the same was true for another contestant as well. > A4 > No good answer. If the larger quadratic has real roots this is not > hard, but otherwise I wasn't sure how to proceed past reducing the > problem to the case with A=C=1,B=0. Clearly this suggests a sequence > of results of the form |p(x)| <= |P(x)| for all x iff ..., ending > with a condition stated independent of x, presumably refering to the > discriminants of p and P and perhaps some other invariants. > But I didn't spend much time on this one. Here are solutions to A1, A2 and A3: A1: Note that for fixed q, one has n = a1 + a1+ ...+a1 + (a1+1) + ... +(a1+1) with q-r a1's and r (a1+1)'s iff n = q*a1 + r, 0<=r<=q-1. But the division algorithm implies there's only one possibility for that, and therefore we can express n in this form in exactly n ways (one for each 1<=q<=n). A2: Let ai = xi^n, bi=yi^n. We ought to show that: (x1x2...xn + y1y2...yn)^n <= (x1^n + y1^n)(x2^n+y2^n)...(xn^n+yn^n) Note that switching (x1,x2,y1,y2) for (sqrt(x1x2),sqrt(x1x2),sqrt(y1y2),sqrt(y1y2)), the LHS does not change, while the RHS gets smaller since: sqrt(x1x2) ^n + sqrt(y1y2) ^n)^2 = (x1x2)^n + (y1y2)^n + 2sqrt( (x1x2y1y2)^n ) <= (x1x2)^n + (y1y2)^n + (x1y2)^n + (x2y1)^n = (x1^n + x2^n)(y1^n+y2^n). Now keep repeating this switching process for (x1,xk,y1,yk), k=3,4...,n. In the end, the RHS only got smaller, and therefore: LHS = final_RHS < initial_RHS 3. In terms of sin and cos one has: f(x) = |1+(senx+cosx)(1+senx * cosx)| /|senx*cosx| But (sinx+cosx)^2 = 1 + 2sinx * cosx and therefore (let u=senx+cosx): f(x) = |(u^3+u+2)/(u^2-1)| = |(u^2-u+2)/(u-1)| But u = senx+cosx = (sqrt(2))*sen(x+pi/4) yields -sqrt(2)<=u<=sqrt(2). Besides, (u^2-u+2)/(u-1) is positive for u>1 and negative for u<1, since u^2-u+2>0 always.Therefore, the minimum of |f| comes from a critical point of f. But f'(u) = 0 => u^2 - 2u - 1 = 0 => u = 1-sqrt(2). This gives |f(x)| = 2*sqrt(2) - 1 Friendly, Marcio Cohen As pointed out by Dave Russin, there is one correction to be made in my solution. It took me some time to figure out the way out, but I got it now: (the problem with my solution is that when I repeat the process for (x1,x3,y1,y3), I donÇt get 3 equals terms (for the new x2 could be different)). The first part of the solution works the same way. It shows that one can, wlog, suppose x1=x2 and y1=y2 (if not, change (x1,x2,y1,y2) for (sqrt(x1x2),sqrt(x1x2),sqrt(y1y2),sqrt(y1y2)) as in my last post). Now we use induction. For n=2 the result is easy to prove. Suppose itÇs vallid for n-1, apply it for the numbers (x1^2, x3,..,xn), (y1^2, ..., yn): (x1^2 * x2...xn + y1^2 * y2...yn)^n <= (x1^2n + y1^2n)(x2^n+y2^n)...(xn^n+yn^n) <= (x1^n+y1^n)^2 * (x2^n+y2^n)...(xn^n+yn^n). This means the inequality it true for n+1 variables with x1=x2 and y1=y2, and from this the result follows. Not an elegant solution, but .... Marcio Cohen. > A2: Let ai = xi^n, bi=yi^n. We ought to show that: > (x1x2...xn + y1y2...yn)^n <= (x1^n + y1^n)(x2^n+y2^n)...(xn^n+yn^n) > Note that switching (x1,x2,y1,y2) for > (sqrt(x1x2),sqrt(x1x2),sqrt(y1y2),sqrt(y1y2)), the LHS does not > change, while the RHS gets smaller since: > sqrt(x1x2) ^n + sqrt(y1y2) ^n)^2 = (x1x2)^n + (y1y2)^n + 2sqrt( > (x1x2y1y2)^n ) <= > (x1x2)^n + (y1y2)^n + (x1y2)^n + (x2y1)^n = (x1^n + x2^n)(y1^n+y2^n). > Now keep repeating this switching process for (x1,xk,y1,yk), > k=3,4...,n. In the end, the RHS only got smaller, and therefore: > LHS = final_RHS < initial_RHS > A4 > No good answer. If the larger quadratic has real roots this is not > hard, but otherwise I wasn't sure how to proceed past reducing the > problem to the case with A=C=1,B=0. Clearly this suggests a sequence > of results of the form |p(x)| <= |P(x)| for all x iff ..., ending > with a condition stated independent of x, presumably refering to the > discriminants of p and P and perhaps some other invariants. > But I didn't spend much time on this one. The right way to state the condition is |Ax^2 + Bxy + Cy^2| <= |ax^2 + bxy + cy^2|. It's easy if the abc form is indefinite or semidefinite. The only non-trivial cases are (i) ABC indefinite, abc definite. (ii) ABC definite, abc definite. In case (i) one can get the desired inequality by adding the inequalities (b-B)^2 - 4(a-A)(c-C) <=0 and (b+B)^2 - 4(a+A)(c+C) <=0. Case (ii) is neat! Consider the elliptical regions {(x,y): Ax^2 + Bxy + Cy^2 <= 1} and {(x,y): ax^2 + bxy + by^2 <= 1}: the former contains the latter, and their areas are pi/(AC-4B^2) and pi/(ac-4b^2). > A5 > Did not spend any time on this one. Probably not hard. Can be blasted by generating functions. Is Richard Stanley on the panel? > A6 > The answer seems to be yes, it is possible, but right now all I have > is a very inelegant answer. This is well-known. It's treated in D. J. Newman's _Analytic Number Theory_ (Springer 1998). The sets are those positive integers with an even/ an odd number of ones in base-2 representation. Most easily done with generating functions. > B5 Use complex numbers. Let the three points be 1, w and w^2 where w = exp(2pi i/3) and z be the interior point. The three lengths are |1 - z|, |w - z| and |w^2 - z|. These are the sides of a triangle: one whose side-vectors are (1-z), w(w-z) and w^2(w^2-z) as these add to 0. Now the area of a triangle in C with vertices 0, u and w is +-1/2 Im(uw). Using this with the above triangle gives area sqrt(3)(1 - |z|^2)/4. -- Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html Needless to say, I had the last laugh. Alan Partridge, _Bouncing Back_ (14 times) [A4] >The right way to state the condition is >|Ax^2 + Bxy + Cy^2| <= |ax^2 + bxy + cy^2|. [Note to readers: Robin's notation reverses the original problem's {a,b,c} and {A,B,C}] >It's easy if the abc form is indefinite or semidefinite. >The only non-trivial cases are >(i) ABC indefinite, abc definite. >(ii) ABC definite, abc definite. Both very nicely done, thank you! Your method of solution suggests that the proper generalizations would not be pairs of univariate polynomials (e.g. binary cubic forms) but rather pairs of quadratics involving more variables (e.g. ternary quadratic forms). I didn't think of that. >> A6 >> The answer seems to be yes, it is possible, but right now all I have >> is a very inelegant answer. My answer is at odds with Robin's. I checked and found I had been sloppy in considering all the cases. (I knew that wasn't the way to go!) So I retract my answer. Interestingly I did suspect the binary representations would reveal the answer but the parity pattern did not jump off the page for me. Thanks also to Paul Pollack who sent the same reference and proof as: >This is well-known. It's treated in D. J. Newman's >_Analytic Number Theory_ (Springer 1998). >The sets are those positive integers with an even/ an odd number of >ones in base-2 representation. Most easily done with generating functions. >> B5 >Use complex numbers. Let the three points be 1, w and w^2 >where w = exp(2pi i/3) and z be the interior point. [...] >Using this with the above triangle >gives area sqrt(3)(1 - |z|^2)/4. In my answer I forget that I was computing 16 Area^2, accounting for part of the difference between Robin's answer and mine. Since his answer is so much shorter I am confident his answer is right; I will try to find the source of my algebra error when I have a chance. And so, by successive approximations, we collectively find some excellent answers! dave > Here you go! I will be preparing the answers I have (there's a bunch > I still lack) and hope to post them later tonight. In time I will collect > the questions and good responses I see into a file which will be at > http://www.math.niu.edu/~rusin/problems-math/ > Sorry in advance about typos below. tweaked. > dave > A1 > Let n be a fixed positive integer. How many ways are there to write n > as a sum of positive integers, n = a_1 + a_2 + ... + a_k, with k an > arbitrary positive integer and a_1 le a_2 le .. a_k le a_1 + 1? > For example, with n=4 there are four ways: 4, 2+2, 1+1+2, 1+1+1+1. Ah, memories of Bresenham's line-drawing algorithm et al. Every solution is [_ n/a _] x F plus [^ n/a ^] x C for some a in {1..n} (and those are ßoor and cieling operators, and the perl Ôx' operator). i.e. n. The rest of the didn't jump out in a fraction of a second. Possible methods of solution appeared for some, but not the actual answers. An interesting bunch of questions. Phil -- Unpatched IE vulnerability: Timed history injection Description: cross-domain scripting, cookie/data/identity theft, command execution Reference: http://safecenter.net/liudieyu/BackMyParent2/BackMyParent2- Content.HTM Exploit: http://www.safecenter.net/liudieyu/BackMyParent2/ BackMyParent2-MyPage.HTM > Here you go! I will be preparing the answers I have (there's a bunch > I still lack) and hope to post them later tonight. In time I will collect > the questions and good responses I see into a file which will be at > http://www.math.niu.edu/~rusin/problems-math/ > Sorry in advance about typos below. > tweaked. > dave > A1 > Let n be a fixed positive integer. How many ways are there to write n > as a sum of positive integers, n = a_1 + a_2 + ... + a_k, with k an > arbitrary positive integer and a_1 le a_2 le .. a_k le a_1 + 1? > For example, with n=4 there are four ways: 4, 2+2, 1+1+2, 1+1+1+1. > Ah, memories of Bresenham's line-drawing algorithm et al. > Every solution is [_ n/a _] x F plus [^ n/a ^] x C for some a in {1..n} > (and those are ßoor and cieling operators, and the perl Ôx' operator). > i.e. n. > The rest of the didn't jump out in a fraction of a second. > Possible methods of solution appeared for some, but not the actual > answers. An interesting bunch of questions. > Phil I was surprised how easy the exam was this year. Last year I only got a 2, but this year I think I got at least a 30. B4 was practically trivial if you just sit down and start working it. B1 wasn't too hard, but it was messy (at least according to my solution). In A1, the pattern is blatantly obvious if you just work out the first 5 integers or so. Proving the pattern isn't too obvious, but it is obvious that you should use induction of some kind, so it's only a short matter of time before you figure out how to proceed. A4 was surprisingly harder than I thought. I didn't have much time left on this problem though because I spent most of the time on A3, which I think I'll get partial credit on. A6 was interesting, but I got it completely wrong after making a stupid error in the pattern. You basically just start by noting that 0 and 1 can't be in the same set, and then figure out where 2 must be, where 3 must be, etc. Eventually lots of patterns start showing up. If you demonstrate the set without proving it, I suppose that's worth a few points partial credit. But it didn't seem nearly as hard as previous years' B6 problems. Maybe I'll change my mind after I see the solution ;-) B5 was also fairly easy, although I left it blank because I was in a big hurry to leave because I had something to do after the test. On the way home it hit me that I hadn't even used the obvious fact that ABC is an equilateral triangle, which makes at least the first half very easy to prove, which should be worth 5 points. B3 is really interesting, and I am still awaiting a solution for this one. B6 is strange. >A6 >For a set S of positive integers, let r_S(n) denother the number of >ordered pairs (s_1, s_2) such that s_1 in S, s_2 in S, s_1 ne s2, >and s_1 + s_2 = n. Is it possible to partition the nonnegative >integers into two sets A and B in such a way that r_A(n) = r_B(n) >for all n ? TYPO ALERT! Another poster's response made me look again at the problem. I had looked straight at the word nonnegative and typed positive in the top line. My bad. We are to partition the NON-NEGATIVE integers into two sets A, B and count pairs of distinct NON-NEGATIVE integers both lying in A (or both lying in B). The answer is not substantially affected (nor improved, unfortunately!); the partition now begins 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... A B B A B A A B B A A B A B B A ... Sorry for the error. Peut-etre je pensais de positif a la Bourbaki. :-) dave moubinool.omarjee It was today (Saturday) but it'll probably be in this archive soon: http://www.unl.edu/amc/a-activities/a7-problems/putnam/ Larry Hammick moubinool.omarjee > It was today (Saturday) but it'll probably be in this archive soon: > http://www.unl.edu/amc/a-activities/a7-problems/putnam/ It's now Sunday and yes, they have the problems (PDF and other usual formats) but no solutions. LH === Subject: Re: Prime number series pattern test yourself in the waters of the [JSH] groups, to give Jimi Harris some competition -- and to get me the Hell out of there! > the proper way, so please I'm requesting from Dr. who are interested > in prime numbers and to contact me on my e-mail > mohammadakahil@yahoo.com --Give the Gift of Dick Cheney -- out of office! === Subject: Re: SESP = String-ESP -- Sarfatti/Hammond the human mind is like a sphinctre, it functions best when squeezing open.. > Lt.Col.Phil Corso, the man who *personally* (and, apparently, > _The Man Who Knew too Much_ by Dick, and > ... a book by Peter Dale Scott on the same subject -- but > with their ****.... and on parallel tracks......ahahahahaha....... > (just a hunch based on what Colonel Phil Corso reported) that their > metric engineering technology is at micro to nanometer scale all inside > the thin fuselage. --Give the Gift of Dick Cheney -- out of office! === Subject: Re: SESP = String-ESP -- Sarfatti/Hammond charset=iso-8859-1 > -- the human mind is like a sphinctre, > -- it functions best when squeezing open.. > Brian You appear to have made a brave attempt to show off your French by exposing your sphinctre. You are to be congratulated and encouraged to eliminate the hin-drance and add instead a forceful e when squeezing it open to obtain its best function. You then will end up with a truly remarkable insight, in that: -- ** the human mind is like a spectre ** -- Have I doctored it now professorially enough, Hutch? ahahahaha......ahahahanson PS: Please do not mistake the ** as dingle berries. > --Give the Gift of Dick Cheney -- out of office! The purpose of your political views on/via LaRouge are noted. However, your intent of presenting your notion to me for a second time now is not quite clear. AFAIC, having worked in all kinds of political circles I came to the conclusion that the active politicos across the board, domestically and globally, have one thing in common: Their aim to feed off the public trough and tell the tax payer what to do. So, needless to say political overtures do fall on deaf ears with me, barring the immediate defense needs and interests of my country. === Subject: Difficult Random variables problem (and convergence) Dear all, I am having trouble with this problem,,,maybe someone can help? it is really tough (at least I think) Suppose that the random variables X_i are independent and P(X_i = 2^k) = 2^(-k) for all k >= 1. Show that (X_1 + X_2 + ... + X_n)/(n*log(n)) converges in probability to log(2). Prove or disprove that limsup (X_1 + ... + X_n)/(n*log(n)) = infinity with probability 1. Anyone can prove this problem? Sincerely, Rob Robert Kaplan 312 Fawn Hill Lane Penn Valley, PA 19072 === Subject: Re: [Set Theory] Class of Ordinals well-ordered ? > === Subject: Re: [Set Theory] Class of Ordinals well-ordered ? >> That's true assuming well ordered ordinals. >I think it's true assuming linearly ordered ordinals. > Transitive linear sets without regularity don't inherit. Why not? > alpha ordinal when > forall beta (beta in alpha -> beta subset alpha) > forall beta, eta in alpha > (beta in eta or beta = eta or eta in beta) > without regularity > Show by that definition > beta in alpha ==> beta is ordinal. The definition I am using is that alpha is an ordinal when alpha is transitive and linearly ordered by Ôin'. By Ôlinear order' I mean that Ôin' is irreßexive, antisymmetric, transitive, and satisfies the trichotomy law. The only difference between this definition and the standard one is that I have not assumed Ôin' to be a well ordering. If alpha is an ordinal according to this definition and if beta in alpha, then I need to show that beta is transitive (I gather that's the sticking point). It's trivial to show that beta is linearly ordered by Ôin'. Let zeta in eta in beta. To show zeta in beta. First of all, transitivity tells us that both zeta and eta are in alpha. Therefore, we can apply the trichotomy law on alpha to conclude that exactly one of (a) zeta in beta, (b) zeta = beta, (c) beta in zeta holds. But both (b) and (c) violate the transitivity of alpha, and therefore option (a) is the only one possible, Q.E.D. >Defining ordinals in the standard manner does not imply regularity >in any way. You have not identified a step in the proof >of my conjecture that fails without regularity. > Transitive, well linear ordered by irreßexive Ôin' ordinals implies > regularity only for the collection of those ordinals. Of Ôthose' ordinals? What other ordinals are there? >> Another choice I think, is transitive set of transitive sets, >> linearly ordered by Ôin' deemed irreßexive. >Are you claiming this works without regularity? > Provided as I said, that trichotomy is > a in b xor a = b xor b in a > instead of > a in b or a = b or b in a Trichotomy means exactly one of those three possibilities holds, which is holds. > I better check out that ÔI think'. > The crutial point is ordinal inheritance. Well no. > It stops x in x and x in y in x but it doesn't stop x in y in z in x That's not a linear ordering. -- Dave Seaman Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling. The definition I am using is that alpha is an ordinal when alpha is >transitive and linearly ordered by Ôin'. By Ôlinear order' I mean >that Ôin' is irreßexive, antisymmetric, transitive, and satisfies >the trichotomy law. Ok, well clarified. ZF without regularity: alpha ordinal when forall beta in alpha, beta subset alpha forall beta, eta, zeta in alpha, (eta not in eta beta in eta in zeta ==> beta in zeta beta in zeta or beta = zeta or zeta in beta) So indeed, the weaken definition alpha ordinal when alpha transitive Ôlinear' set. is equivalent to the Ôregular' definition. alpha ordinal when alpha transitive Ôwell order' set. for all xi in nonnul A subset alpha, xi ordinal ==> some pi in A with for all xi in A, pi <= xi pi = /A = { xi in /alpha | for all eta in A, xi in eta } ordinal beta in pi ==> beta subset pi for all xi in A, beta in xi for all xi in A, beta subset xi beta, eta, zeta in pi ==> (eta not in eta beta in eta in zeta ==> beta in zeta beta in zeta or beta = zeta or zeta in beta) hint: some ordinal nu in A; beta, eta, zeta in nu for all xi in A, pi <= xi because for all xi in A, pi subset xi in alpha Here's a new twist for the last part: pi in A Otherwise: for all xi in A, pi < xi; pi in pi not so! -- ZF with regularity alpha ordinal when forall eta in beta in alpha, eta subset beta subset alpha alpha ordinal when forall beta in alpha, beta subset alpha forall beta, zeta in alpha, (beta in zeta or beta = zeta or zeta in beta) -- NBG class of ordinals = intersection of all sets A containing nulset and closed by successor and arbritary unions. What's the advanges of ZF over NBG, that ZF appears to be the set theory of choice while NBG seems regarded as an antique? -- NF Equivalence classes of order isomorphic sets. Even with NF |- not AxC, it hasn't been completely abandoned. What's its charm that it has a linering fan club? ---- === Subject: Re: [Set Theory] Class of Ordinals well-ordered ? > class of ordinals = intersection of all sets A containing nulset > and closed by successor and arbritary unions. If by set you mean to exclude proper classes, there is no such set A. If you mean to include proper classes, the class of ordinals according to the above definition cannot be proved to exist in NBG, since the definition is impredicative. > What's the advanges of ZF over NBG, that ZF appears to be the > set theory of choice while NBG seems regarded as an antique? There is no essential difference between ZF and NBG - classes are just a matter of convenience. === Subject: Re: Consider John Nash, math awards while clipping the excess quotes, I did notice that Johnny N. got a Memorial Nobel; thus, he could have been the first economist (sik) to get a real Nobel, instead of the Swedish Bank Prize ... *and* an Oscar. > there is no Prize in economics. rather, > there is a Swedish Bank Prize that's awarded > at the annual Nobel Prize ceremony, due to a largish endowment. > that's how you get pigs like Robert Mundell, the math and its use in the algorithms for the FCC auctions > of the airwaves, was); thus, > the scheme is going online on Dec.12, > 113 countries, mostly in the fomererly known > as the Wholly Brutish Umpire freer-trade bloc, > have ratified it -- over the 80 that were required, > whether/whenever Russia gets around to it. lies, damn lies and polls!... also not mentioned > So not only was his other mathematical work recognized by the > mathematical community, the work that would eventually lead to his > Memorial Nobel Prize in Economics was also recognized by the > mathematical community ->before<- it was awarded the Memorial Nobel. --Give the Gift of Dick Cheney -- out of office! that's really cool, except taht a PTriplet is in integers; you have to work a little of numbertheory to get them. so, is that your next step? > Consider the Pythagorean triplet: a^2 +b^2 = c^2 , where > A= arithmetic mean, G=geometric mean, H =harmonic mean of two reals p>q>0, > so that > a = A-H = ((1/2)(p-q)^2)/(p+q) > b = sqrt(H(A-H)) = ((p-q)/(p+q))G= ((p-q)/(p+q))sqrt(pq) > c = sqrt(A(A-H)) = (p-q)/2 > Thus the nice original Pythagorean triplet is rewritten: > ((A-H)^2) + (H(A-H)) = A(A-H) > This identity follows from Pappus's (Pappos) 3 rd book , where he presents > how to construct A,G and H with the aid of half circle, but not - as far as > I know - that Pythagorean triplet indentity. > The nice Pythagorean triplet results in triangle inequality sqrt(pq)>q iff > p>q, which is tha base of Fermat factorization. > Any references for A and H based Pythagorean triplets ? --Give the Gift of Dick Cheney -- out of office! > that's really cool, except taht > a PTriplet is in integers; > you have to work a little of numbertheory to get them. so, > is that your next step? Try for example 4A multiplication of each members in the basic equation. Note p and q can also be squares or their product can be square if p and q are suitable composites. > Consider the Pythagorean triplet: a^2 +b^2 = c^2 , where > A= arithmetic mean, G=geometric mean, H =harmonic mean of two reals p>q>0, > so that > a = A-H = ((1/2)(p-q)^2)/(p+q) > b = sqrt(H(A-H)) = ((p-q)/(p+q))G= ((p-q)/(p+q))sqrt(pq) > c = sqrt(A(A-H)) = (p-q)/2 > Thus the nice original Pythagorean triplet is rewritten: > ((A-H)^2) + (H(A-H)) = A(A-H) > This identity follows from Pappus's (Pappos) 3 rd book , where he presents > how to construct A,G and H with the aid of half circle, but not - as far as > I know - that Pythagorean triplet indentity. > The nice Pythagorean triplet results in triangle inequality sqrt(pq)>q iff > p>q, which is tha base of Fermat factorization. > Any references for A and H based Pythagorean triplets ? > --Give the Gift of Dick Cheney -- out of office! === Subject: Re: e^(pi*sqrt(163)) and all that (was: Re: Almost an Integer - e^?) > and is there some more conceptual > description of what a genus of > ideals (or of quadratic forms or whatever, > if that's the main special > case) is (or of the equivalence relation > on ideals for which the > genuses are the equivalence classes)? I could have included that Two strict ideal classes are said to be in the same genus if their ratio is the square of an ideal class. - Harvey Cohen, A Classical Introduction to Algebraic Numbers and Class Fields, page 145. See Chapter 14 generally for more on genus classes in quadratic number fields. John Robertson === Subject: Re: e^(pi*sqrt(163)) and all that (was: Re: Almost an Integer - e^?) | |> and is there some more conceptual |> description of what a genus of |> ideals (or of quadratic forms or whatever, |> if that's the main special |> case) is (or of the equivalence relation |> on ideals for which the |> genuses are the equivalence classes)? | |I could have included that Two strict ideal classes are said to be |in the same genus if their ratio is the square of an ideal class. - |Harvey Cohen, A Classical Introduction to Algebraic Numbers and Class |Fields, page 145. See Chapter 14 generally for more on genus classes |in quadratic number fields. thanks for the information. so apaprently the genus group is just the ideal class group tensored with z/2. also, you mentioned weak equivalence of ideals. is that just equivalence as elements of the ideal class group? -- [e-mail address jdolan@math.ucr.edu] === Subject: Re: e^(pi*sqrt(163)) and all that (was: Re: Almost an Integer - e^?) >thanks for the information. So apparently the genus group is just the >ideal class group tensored with z/2. That's beyond me. I don't know one way or the other. >also, you mentioned weak equivalence of ideals. Is that just >equivalence as elements of the ideal class group? Cohn defines strict equivalence of ideals I and J as requiring elements a and b so that I = J, and N(a/b) > 0 (where is the principal ideal generated by a). For weak equivalence, the condition N(a/b) > 0 is dropped. For example, in Q(sqrt(3)), taking beta = sqrt(3), the ideals I = <1> and J = <-1 + beta> are weakly equivalent, but not strictly equivalent, because N(-1 + beta) = -2. (Also, I and J are in different genus classes.) But yes, weak equivalence is what is normally considered to give the ideal class group. The strict class group is either equal to the (weak) class group, or has twice as many elements. John Robertson === Subject: Re: e^(pi*sqrt(163)) and all that (was: Re: Almost an Integer - e^?) |I could have included that Two strict ideal classes are said to be in the same |genus if their ratio is the square of an ideal class. - Harvey Cohen, A |Classical Introduction to Algebraic Numbers and Class Fields, page 145. |thanks for the information. So apparently the genus group is just the |ideal class group tensored with z/2. jpr2718@aol.com: |That's beyond me. I don't know one way or the other. If G is an abelian group, written additively, the tensor product of G with Z/2 is G/2G, which is not hard to show. So probably what James Dolan should have said is that the genus group is the strict ideal class group tensored with Z/2. When there are elements with negative norm, the class group tensored with Z/2 and the strict class group tensored with Z/2 will be different unless there exists an ideal whose square is a principal ideal generated by such an element. [...] |For example, in Q(sqrt(3)), taking beta = sqrt(3), the ideals I = <1> and J = |<-1 + beta> are weakly equivalent, but not strictly equivalent, because N(-1 + |beta) = -2. (Also, I and J are in different genus classes.) This example works; the ideal generated by -1+beta is maximal, so it can't be the square of any other ideal. It represents a nonzero element of the strict class group tensored with Z/2, but in the class group its 0; the class group tensored with Z/2 is the quotient of that group by the subgroup generated by -1+beta. Note incidentally that the aol newsreader takes b placed inside angle brackets < > as a hint to switch to bold text, and drops out a placed inside angle brackets entirely. For anyone not quite familiar with tensor products, here's a demonstration that for an abelian group G, G/2G is isomorphic to G tensored with Z/2. The tensor product of two abelian groups A and B (which is not hard to generalize to modules over a ring, where abelian groups are modules over Z) is an abelian group C with a bilinear function f:AxB->C with the universal property that for any other such bilinear function g:AxB->C', there exists a unique h:C->C' making g equal to the composition of f with h: g(a,b)=h(f(a,b)). Bilinearity means a->f(a,b0) is linear for each b0 in B, and b->f(a0,b) is linear for each a0 in A. The mapping from GxZ/2 to G/2G is f(g,0)=0 and f(g,1)=g+2G. That's plainly linear in the first factor, and is linear in the second factor because f(g,1+1)=0=(g+2G)+(g+2G) =f(g,1)+f(g,1), plus some trivial relationships. If we have a bilinear function h:GxZ/2->H, then h(g,0)=0 and g->h(g,1) is linear. Moreover 2g->h(2g,1)=h(g,1)+h(g,1) =h(g,1+1)=h(g,0)=0, so 2G is a subset of the kernel. Given an element g' of G/2G, let k(g')=f(g,1) where g is a representative of g'. This is well defined because if g1 and g2 are two representatives of g', then g1=g2+2g3 for some g3 in G, and f(g1)=f(g2). Then k(f(g,i))=h(g,i) for each g in G and i in Z/2. Keith Ramsay === Subject: Re: e^(pi*sqrt(163)) and all that (was: Re: Almost an Integer - e^?) |When there are elements with negative norm, the class group |tensored with Z/2 and the strict class group tensored with |Z/2 will be different unless there exists an ideal whose |square is a principal ideal generated by such an element. presumably i should try to figure this out for myself, but: do the class group and the strict class group both have galois-theoretic interpretations? that is, is there some sort of strict hilbert class field extending the hilbert class field, with galois group over the original field canonically equal to the strict class group? (actually i guess i'm hoping the answer is no, on the grounds that that would make the strict class group seem not so important and thus one less thing i'd feel obligated to learn more about.) -- [e-mail address jdolan@math.ucr.edu] === Subject: Re: e^(pi*sqrt(163)) and all that (was: Re: Almost an Integer - e^?) > |When there are elements with negative norm, the class group > |tensored with Z/2 and the strict class group tensored with > |Z/2 will be different unless there exists an ideal whose > |square is a principal ideal generated by such an element. > presumably i should try to figure this out for myself, but: do the class group and the strict class group both have galois-theoretic > interpretations? that is, is there some sort of strict hilbert class > field extending the hilbert class field, with galois group over the > original field canonically equal to the strict class group? Yes. One HCF is the maximal abelian extension unramified at all primes; the other is the maximal abelian extension unramified at all primes and unramified at the real places (i.e. the totally real part of the former when we consider imaginary quadratics fields). -- Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html Needless to say, I had the last laugh. Alan Partridge, _Bouncing Back_ (14 times) === Subject: Re: e^(pi*sqrt(163)) and all that (was: Re: Almost an Integer - e^?) ||I could have included that Two strict ideal classes are said to be ||in the same genus if their ratio is the square of an ideal class. - ||Harvey Cohen, A Classical Introduction to Algebraic Numbers and ||Class Fields, page 145. | ||thanks for the information. So apparently the genus group is just ||the ideal class group tensored with z/2. | |jpr2718@aol.com: ||That's beyond me. I don't know one way or the other. | |If G is an abelian group, written additively, the tensor |product of G with Z/2 is G/2G, which is not hard to show. |So probably what James Dolan should have said is that the |genus group is the strict ideal class group tensored with |Z/2. sorry, i accidentally overlooked that word strict there in this instance. (i've been deliberately postponing learning about its real significance, but i shouldn't have allowed it to become completely invisible.) -- [e-mail address jdolan@math.ucr.edu] === Subject: 5 spherical containers packed with unit balls Here's a post by John Braley from the yahoo group, Synergeo. Check out the pictures. John and Adrian are in a wonderful collaberation. Dick === Subject:æ 5 spherical containers packed with unit balls http://memeticdrift.net/tau/rjp/r1R12467.htm Adrian Rossiter's packer.exe using all 5 methods. The premise is that I set r=1 and R=12.467 (that's the ball radius and the container radius) to emulate the radius JBw got with packing 1157 balls in a sphere. And 1157 was the number he packed because that is the number of balls in Steve's Wroot 33. In the info below, I double JBw's and Steve's r and R to convert to r=1 rather than their r=.5. (Nor did I forget to first add .5 to each of their R radii, as they go only to outer ball center and not all the way to the surface of the sphere.) Steve's is the only one with other than R=12.467. For each: r=1. The number of balls is given, and is the item of interest. Wroot 33- 1157 (R=12.4892) xverse- 1157 ***** packer in- 1093 packer out- 960 packer up- 1073 packer inup- 1093 packer outuo- 954 The 5 packers are pictured at the url in the order of this list. I skipped my usual 4 color-coded length ranges, and only show the contact edges -- each edge = 2. One can see fairly well in's smooth outer surface and touch of emptiness in the center, while out is visibly denser in the center and jagged and sparse near the boundary. With up one can see that the top was last to fill. Are in and inup identical? I repeated outup with a light glass convex hull. It's cute, but doesn't seem to offer additional information. http://memeticdrift.net/tau/rjp/outupglass.htm I noticed a slight bug in packer.exe. The help message says: usage: packer.py...... -- obviously that's inadvertently carried over from packer.py. I was booking the packers into a suite at Hotel Swiki, when I decided to give packer.exe a try. Consequently, they are still waiting in the lobby. Bellhop, attend to these guests! -- John Braley and Adrian Rossiter Web Site: http://www.terra.es/personal/adrian_r === Subject: Independent random variables with common distribution Please help me with my problem ,,,, Consider : X_1, X_2, ... is a sequence of independent random variables with finite variances and a common distribution F such that F(0) = 0. Now consider the product Z_n = product (from k = 1 to n) of { (2(X_k)^2) / ( (X_{k-1})^2 + (X_{k-2})^2 ) } In order to analyze Z_n, I'd like to talk about 2E[(X_n)^2] and E[1/((X_{n-1})^2 + (X_{n-2})^2]. What is the relationship between these two expectation? Is one always bigger than the other? Then finally I'd like to show that Z_n converges with probability one to a random variable that is finite with probability one. Any ideas? Henrique === Subject: Re: Groups, algorithms, logic? Adjunct Assistant Professor at the University of Montana. > [.snip.] >>So I have some operators acting on pairs and on pairs of pairs. >>For example: Operator I inverts the pair. That is I(u,v)=(v,u). >>Operator P acts on pairs of pairs and carries the product. That is >>P((u,v),(w,z))=(uw,vz). >>Operator T acts also on pairs of pairs and carries on a transitivity: >>T((u,v),(v,w))=(u,w). >>Now the computer can start working with these operators: >>I(a^3,a)=(a,a^3). >>T((a^3,a),(a,a^3))=(a^3,a^3). >>P((a^3,a^3),(b^3,b))=(a^3b^3,a^3b). >>This operators are inspired by the oprations we do to generate a >>congruence. >>My question is: are there some other operators that generate new pairs >>that are not in the congruence generated. Or is it enough to >>generate >>the congruence? >You are looking for the congruence on the free semigroup on n >letters, generated by the identity a^3. >b and every b into an a (if you are looking at words in more than 2 >letters, you need all permutations of the letters). You also need to >throw in the diagonal, all elements of the form (u,u) for a word u. This is incomplete. The Ôrewriting' function needs to do more than change every a into a b and every b into an a. To make the congruence a verbal congruence (which it needs to be) you need the much more complicated family of operations, one for every pair of words u and v, that takes an identity and changes every a for u and every b for v. So from (a^3,a), you also need to be able to get ((aba)^3,aba), etc. [.rest deleted.] -- ============================================================= ========= It's not denial. I'm just very selective about what I accept as reality. --- Calvin (Calvin and Hobbes) ============================================================= ========= Arturo Magidin magidin@math.berkeley.edu === Subject: Dividing A Square Cake I have 2 major variations, at least, on this UNoriginal game to discuss. (And this is more a stategy/math-question post than a game-idea post, since it is not my game anyhow.) Let us say we have two players (named Min and Max, for example...) who want to cut a cake so as to share it, but they wish to make a game of this. Min and Max take turns cutting a square cake, Max making horizontal straight cuts and Min making vertical straight cuts, both players making n cuts apiece, where n is odd. And the cuts can be in any order in relation to each other physically. After the cuts are made (if we were to label the rows of pieces made by the cutting as 1 through (n+1), and label the columns also with 1 through (n+1)), Min gets the pieces which have the same parity (ie. mod 2 value) for the pieces' row and column coordinates, and Max gets the pieces with opposite parity for the row and column numbers. (So, for example, if n = 7, and the cuts were all made evenly spaced, the cake would correspond with a Chess board, where one player gets the black squares and the other player gets the white squares.) But the cuts need not be evenly spaced... (just either horizontal or vertical) So, what would be a good stategy for this game??? If Max moves first, for example, since Min has the same-parity pieces, she might want to match Max's moves (cutting about the same distance from the left side {where column 1 is next to} as Max did from the top {near row 1}). In this way she might increase her diagonal pieces' total volume anyway. So perhaps it would be more interesting a game to let Min move first, since she has the same-parity pieces. In the Min-first game, Max might make thicker rows when Min makes thinner columns, and vice versa. Min moving 1st seems like it might lead to some interesting play. (What if Min cuts a previously formed column in half, for example?) Another interesting variation: What if we had m >= 3 players?? If we had 3 players, say, they could alternate who cuts vertically and who cuts horizontally. Pieces would be awarded based on the sum of each piece's row and column (mod m). What would the strategy be for any of the 3 players in an m=3 game?? (Where cuts are as follows: 1H 2V 3H 1V 2H 3V 1H 2V 3H 1V 2H 3V...(repeating)) And, in a m-player game, m = 3, however, if the number of pieces must be divisible by m=3, and the players must all make the same number of cuts, then the same number of cuts cannot be made in both the vertical and horizontal directions. For, if the number of vertical cuts is vn, and the number of horizontal cuts in hn, then the total number of pieces is: q= (hn +1)(vn +1), and the total number of cuts made in the game is n = vn + hn. If m must divide both q and n, then it must divide hn *vn + 1 too. [So, if we have n/2 =hn =vn = r, then 3 must divide r^2 + 1, which it never does because of Fermat's Little theorem. And if, generally, m is an odd prime, and hn = vn = k^((m-1)/2), for some positive integer k, then we cannot have each player getting the same number of pieces and making the same number of cuts.] But the far easier proof, which works for all m >= 3, is that m must divide 2r, so it must contain primes also dividing r if m >= 3. But m is coprime with r^2 +1. So, the only m where each player gets the same number of pieces, makes the same number of cuts, and the same number of total cuts are made in each direction, is m = 2 (and m =1,0, obviously). === Subject: Re: Dividing A Square Cake > Let us say we have two players (named Min and Max, for example...) > who want to cut a cake so as to share it, but they wish to > make a game of this. Ironically, two of my fellow grad students are named Min (pronounced Ming) and Max and they were officemates at one point. I don't know if they every shared a cake though. Have a tolerable existence. Eli === Subject: Re: Dividing A Square Cake >I have 2 major variations, at least, >on this UNoriginal game to discuss. >(And this is more a stategy/math-question post >than a game-idea post, since it is not my game anyhow.) Let us say we have two players (named Min and Max, for example...) >who want to cut a cake so as to share it, but they wish to >make a game of this. >Min and Max take turns cutting a square cake, >Max making horizontal straight cuts and Min making vertical >straight cuts, both players making n cuts apiece, where n is odd. >And the cuts can be in any order in relation to each other physically. >After the cuts are made (if we were to label the rows of pieces >made by the cutting as 1 through (n+1), >and label the columns also with 1 through (n+1)), >Min gets the pieces which have the same parity (ie. mod 2 value) >for the pieces' row and column coordinates, and Max gets >the pieces with opposite parity for the row and column numbers. (So, for example, if n = 7, and the cuts were all made evenly >spaced, the cake would correspond with a Chess board, where >one player gets the black squares and the other player gets >the white squares.) >But the cuts need not be evenly spaced... >(just either horizontal or vertical) >So, what would be a good stategy for this game??? SPOILER SPACE 40 35 30 25 20 15 10 9 8 7 6 5 4 3 2 making evenly-spaced cuts for 1 through (n-1), and then for cut n, either make an evenly spaced cut (which guarantees a draw - assuming the first player's cuts make rows and the second player's cuts columns, then the second player's cuts make n+1 evenly-spaced columns, and since n+1 is even, they can be paired such that each row in each pair has an even piece and an identical odd piece) or make a cut that will give that player the most cake in the last two columns depending on how the rows are shaped. -- Don === Subject: Re: of 1 through 25 > 2! > Sequence: 1-6-7-12-11-16-21-22-18-23-24-19-14-15-10-9-4-3-2 > narayan@galaxy5.com I am sorry. For this is close...but there is at least 1 error in your sequence. :( ha scritto nel messaggio > We have the grid of 1 through 25 simply arranged unspectacularly: > 1 2 3 4 5 > 6 7 8 9 10 > 11 12 13 14 15 > 16 17 18 19 20 > 21 22 23 24 25 > Move from integer to adjacent integer by moving only > up/down/right/left (and, with one exception {see below}, diagonally), > and visiting each integer *at most* once. (Unless otherwise stated, > Ôadjacent integer' always means to the left/right/above/below.) > And, obviously, move according to the rules below, > which are to be followed, one integer (give or take) per line, > sequencially as a computer program. > What is your path and which integer do you finish upon?? > (n(k) = the value of integer upon LEAVING line-k of algorithm, ie the > value gotten at line-k by the mathematical rule.) > 1) Start at the 1. > 2) Move to an adjacent integer divisible by 3. > 3) Move to a prime. > 4) Add a prime to n(3) to get n(4), where you move to. > skip this line next time visited. (d(n(4)) = number of positive > divisors of n(4).) > 6) n(6) = n(5) + d(n(5)), move to n(6). > 7) Add 1 or 2 to n(6) to get n(7), which you move to. > 8) Move to a DIAGONALLY adjacent integer which has not yet been > visited. > 9) Move to phi(n(8)) + n(8) -1. (phi(n(8)) = number of positive > integers <= n(8) and coprime with n(8).) > 10) n(10) = n(9) + 1. > 11) n(11) = n(10) - largest prime dividing (n(10)+1). > 12) Move to ßoor(n(11)^(1/2)) +10. > 13) n(13) is coprime with 5. > 14) n(14) = n(13) - prime. > 15) Move to any unvisited composite to any unvisited composite to...as > many times as you wish, to form a chain of composites. > 16) Move to ßoor(n(15)/2). (n(15) is final composite from line-15.) > 17) Move to any yet unvisited adjacent integer. > 18) If sum of all visited integers so far is divisible by 3, then move > one integer to the left. > Which integer are you now on?? --- > Outgoing mail is certified Virus Free. > Checked by AVG anti-virus system (http://www.grisoft.com). === Subject: Overßow of linear arrival process I want to study the overßow for a linear arrival process. N sources, C link of the primary group, blocked calls go to the infinite secondary group. Suppose the current state is (i,j), i, j are number of busy cuicuits in the primary and secondary group, respectively, then the arrival rate is: (N-i-j)* lambda What I want to know is the state distribution, especially, the marginal distribution in the second group. Are there any results of this problem? Like Kosten and Brockmeyer's results of the overßow of Possion input process. > I posted something here a while back about super-palindromic > sequences, where one such sequence > (in > http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&safe=off& selm=b4be2fdf.031 0211516.78bf6f10%40posting.google.com) > had the closed-form: > a(m-1) = -(-1)^c(m), > where c(m) = > the number of e()'s where: > e(e(e(...e(m)...))) = 0, > and e(m) is a nonnegative integer such that: > 2^e(m) is the highest power of 2 dividing m. > So, the sequences {a(m)} and {c(m)} have a very interesting > palindromic structure. > I am wondering now about a generalization based somewhat on the above > c-sequence. > If m = > product{p=primes, p|m} p^e(p,m), > where e(p,m) is always a positive integer, > we can factor e(p,m) still as: > e(p,m) = product{q=primes, q|e(p,m)} q^e(q,e(p,m)). > And we can do this, in a tree-like manner (I guess), until we get a 1 > at the Ôleaves' of the tree. > A small example: > m = > 2^(2^(3^1)*3^(2^1*5^(2^1)))*5^(2^(5^(2^1))*7^1) > (Oh, forgive me, please, > if I messed the parentheses..) > But, in any case, if we were to extend (with some modifications) the > original c-sequence to involving all the primes (not just 2), we might > ask here for: > C(m) = number of primes (and 1's) in *total* factorization of m. > So, for the m above, whatever that is..., > A(m) = 17. > (Should be C(m) = 17.) > (more of my reply below) > (I bet this is not a very fast rising sequence...) > So, is there anything remotely interesting about this sequence, such > as some interesting symmetry, such as in the little-c sequence? > (I might have posted on this topic a *long* time ago, but without the > hind-sight of the little-c sequence and its super-palindromeness.) > By th way, here is the link to a post about the (little)c-sequence: > http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&safe=off& threadm=b4be2fdf. 0303281748.762fa20d%40posting.google.com&rnum=3&prev= > As for the Big-C sequence,... > First, we have the two related sequences depending on whether we want > to count the one's too or just the primes. > Second, C(m) can be generated recursively. > C(m) = sum{p|m} (1 + C(e(p,m))), > where C(0) = 0 if the 1's are not counted, and is 1 if the one's are > counted. > (And the sum is over the distinct prime divisors, p, of m.) > 3rd, if we want to sum over the terms of the sequence {a(p)}, where > each a(p) appears in the sum each time the prime p appears in the > factorization of m and in the factorization of the exponents in the > factorization of m and in the factorization of the exponents in the > exponents' factorization,... > then: > C(0) = what to add each time a 1 appears (or = 0 if the 1's are > ignored). > C(m) = sum{p|m} (a(p) + C(e(p,m))). > So, also, > sum{m=1 to n} C(m) = > sum{m=1 to n} sum{p=primes <= n/m} (a(p) + C(e(p,m)+1)) And, how many m's have a given C(m) = n, for n = fixed positive integer, and m <= some positive integer M? (where a(p) = 1 for all p) *How many m's total can be composed from b(2) 2's , b(3) 3's, b(5) 5's, ... for a given finite sequence of {b(p)}, p = primes? (this seems to be a combinatorial problem mostly.) In each Ôbranching' of the prime-factorization Ôtree', each prime occurs at most once. (But any prime can reoccur at the same level of branching, but only if it has another parent-branch.) > Leroy > Quet === Subject: Re: Annexe Canada > What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. When was Canada's last terrorist attack? Ohh ... thats right, they haven't had any because they didn't make themselves a target like you guys. No one likes Americans anymore. -TheMan- === Subject: Re: Annexe Canada > What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. > When was Canada's last terrorist attack? > Ohh ... thats right, they haven't had any because they didn't make > themselves a target like you guys. No one likes Americans anymore. > -TheMan- Good point! You -The Man-! === Subject: Re: Annexe Canada X-No-Archive: yes >When was Canada's last terrorist attack? >Ohh ... thats right, they haven't had any because they didn't make >themselves a target like you guys. No one likes Americans anymore. 1960s and 1970s - in Montreal and Quebec City. Some homegrown terrorist outfit called the FLQ. They sought independence for Quebec. Bombed a few, killed a few...even kidnapped and murdered the Minister of Immigration, Pierre Laporte. === Subject: Re: Annexe Canada >When was Canada's last terrorist attack? >Ohh ... thats right, they haven't had any because they didn't make >themselves a target like you guys. No one likes Americans anymore. > 1960s and 1970s - in Montreal and Quebec City. Some homegrown > terrorist outfit called the FLQ. They sought independence for Quebec. > Bombed a few, killed a few...even kidnapped and murdered the Minister > of Immigration, Pierre Laporte. And they were put down quickly. Problem solved. No ing around for years demolishing a country that had nothing to do with the attacks, like the USSA is doing with Iraq. === Subject: Re: Annexe Canada > What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. > It is the only way foward for Canada aka Canuckistan. > No doubt contingencies already exist for that, should the porous border > prove a threat to the security and integrity of American sovereignty > and its right to self determination. > Of course our resources would have nothing to do with it at all. > That's probably slotted for say 2010. If you annex Canada now, we'll throw in Paul Bernardo and Karla Homolka for free. _- -_ subRoutine What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. It is the only way foward for Canada aka Canuckistan. > No doubt contingencies already exist for that, should the porous border > prove a threat to the security and integrity of American sovereignty > and its right to self determination. > Of course our resources would have nothing to do with it at all. > That's probably slotted for say 2010. > If you annex Canada now, we'll throw in Paul Bernardo and Karla Homolka for > free. And Celine Dion. === Subject: Re: Annexe Canada > What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. > It is the only way foward for Canada aka Canuckistan. Please take Quebec off our hands. And if you grab Newfoundland first, then the millions of added welfare cases will bankrupt you within a month. _- -_ subRoutine What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. > It is the only way foward for Canada aka Canuckistan. > Please take Quebec off our hands. And if you grab Newfoundland first, then > the millions of added welfare cases will bankrupt you within a month. > -_ > subRoutine 0,0,1 sub-routine's logic is faulty - Newfoundland has the highest economic growth of the 10 provinces. === Subject: Re: Annexe Canada > What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. It is the only way foward for Canada aka Canuckistan. > Please take Quebec off our hands. And if you grab Newfoundland first, then > the millions of added welfare cases will bankrupt you within a month. > -_ > subRoutine 0,0,1 > sub-routine's logic is faulty - Newfoundland has the highest economic growth > of the 10 provinces. Going from 0 to 0.1 is infinite growth. === Subject: Re: Annexe Canada > What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. It is the only way foward for Canada aka Canuckistan. > Please take Quebec off our hands. And if you grab Newfoundland first, then > the millions of added welfare cases will bankrupt you within a month. > -_ > subRoutine 0,0,1 > sub-routine's logic is faulty - Newfoundland has the highest economic growth > of the 10 provinces. No man, they're all out of jobs because the Americans have destroyed the fishing industry. Stop overfishing you greedy American bastards! _- -_ subRoutine What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. It is the only way foward for Canada aka Canuckistan. Please take Quebec off our hands. And if you grab Newfoundland first, > then > the millions of added welfare cases will bankrupt you within a month. > -_ > subRoutine 0,0,1 > sub-routine's logic is faulty - Newfoundland has the highest economic > growth > of the 10 provinces. > No man, they're all out of jobs Not since Hibernia went online. >because the Americans have destroyed the > fishing industry. You're right about that. > Stop overfishing you greedy American bastards! > _- > -_ > subRoutine 0,0,1 === Subject: Re: Annexe Canada What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. It is the only way foward for Canada aka Canuckistan. Please take Quebec off our hands. And if you grab Newfoundland first, > then > the millions of added welfare cases will bankrupt you within a month. > -_ > subRoutine 0,0,1 sub-routine's logic is faulty - Newfoundland has the highest economic > growth > of the 10 provinces. > No man, they're all out of jobs > Not since Hibernia went online. The Newfs don't know how to run an operation like that. All those jobs are imported. >because the Americans have destroyed the > fishing industry. > You're right about that. I'm right about everything. And if you're looking to place real blame on someone for something, point the finger at the Finns for dragging down the Usenet bell curve. For instance, there's this really stupid Finn who hangs out in alt.ßame and got to be one of the dumbest oafs on the planet. He even shovels reindeer for a living. His shamelessly misdirected slurps of others has earned him the title for being the Best Punching Bag as Usenet's resident Village Idiot. His nonsense consists of horribly written puns, like calling a Canadian a loonie, and he's also a very well known coward and quite proud of it. I think it would be better if Russia annexed Finland because the Finns all speak Russian anyway. Yep, the Finns have one of the highest suicide rates in the world because it's always cold and depressing there. We could even use their land to dump all our toxic waste by burying it in the snow. Since they are very close to Chernobyl, no one would be able to tell them apart from the mutated freaks already there. The brain damage would go unnoticed and we would all have quite a good time laughing at them. So why bother with a country who gave us the Nokia cell phone when we have the Japanese making better ones at a cheaper price with ßashy Nintendo video games and high resolution cameras included in the package? What have they offered us lately besides an idiot like Ari Assikainen aka 03:15:38 > Stop overfishing you greedy American bastards! _- -_ subRoutine What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. > It is the only way foward for Canada aka Canuckistan. > Not even a good troll, bozo. It garnered responses... which is what a troll does. Sounds like a good troll to me. === Subject: Re: Annexe Canada > What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. > It is the only way foward for Canada aka Canuckistan. You seem to forget that the Canadians kicked our ass in two conßicts.... === Subject: Re: Annexe Canada >You seem to forget that the Canadians kicked our ass in two conßicts.... Which ones? === Subject: Re: Annexe Canada >You seem to forget that the Canadians kicked our ass in two conßicts.... > Which ones? Those who are ignorant of history are doomed to repeat it. === Subject: Re: Annexe Canada schulzsi@rz.uni-potsdam.de a .8ecrit dans le message > What with the war on terror, and Canada's puny military and corrupt > police force, the only way to insure peace and safety for that > country, is for it to be annexed by America. > It is the only way foward for Canada aka Canuckistan. --------------------------------- Well, another solution is the liberation of U.$.A by Canadians and the return of democracy to the Americans peoples. I am sure Canadians will be welcome with (french) kisses and ßowers when they will topple the Little Dictator and his gang of corporate crooks. Patriot act will be scraped; free press will be restaured, Health Care will be available to all citizens, and free election will be under supervision of neutral observers. Americans; who can be jailed if they visit Cuba, an island 90 miles of their country; will be free again to go anywhere in the world. This is real freedom. -- Anemic Combatant Ô' Make peace , you idiot ! Ô' Gerd von Rundstedt, after D-day 1944 === Subject: proof I am working on a proof dealing with finite sets and don't know how to proceed. The definition I have for finite sets is as follows. Let A be a finite set. Then for all functions f: A->A, if f is 1-1 then f is onto. Now here is the problem. Let f: A->B be a 1-1 correspondence and let A be finite. Prove that B is finite. Well, since A is a finite set, i created a function g:A->A such that g is a 1-1 correspondence. In order to prove B is a finite set according to the definition, I created a function h:B->B where h is 1-1. Then I let an element b be part of the set B. To prove it is onto, i must show that there is an element c in B such that h(c) = b. Now I am not quite sure how to do that. Since this is a homework problem, I would really appreciate if someone could just nudge me along in the right direction without giving me the answer. I'd still like to figure this out myself to learn it. Thus if you could tell me how to start it or what some key steps would be so I can deduce the rest, that would really help. Thanks. === Subject: Re: proof > I am working on a proof dealing with finite sets and don't know how to > proceed. The definition I have for finite sets is as follows. Let A be a > finite set. Then for all functions f: A->A, if f is 1-1 then f is onto. Now > here is the problem. > Let f: A->B be a 1-1 correspondence and let A be finite. Prove that B is > finite. Well, since A is a finite set, i created a function g:A->A such that > g is a 1-1 correspondence. In order to prove B is a finite set according to > the definition, I created a function h:B->B where h is 1-1. Then I let an > element b be part of the set B. To prove it is onto, i must show that there > is an element c in B such that h(c) = b. Now I am not quite sure how to do > that. Assume injection h:B -> B and bijection f:A -> B g = f^-1hf:A -> A injection, hence bijection as A finite. Thus A = g(A) = f^-1hf(A) = f^-1h(B) B = f(A) = ff^-1h(B) = h(B) Hence h surjection. > Since this is a homework problem, I would really appreciate if someone could > just nudge me along in the right direction without giving me the answer. I'd > still like to figure this out myself to learn it. Thus if you could tell me > how to start it or what some key steps would be so I can deduce the rest, > that would really help. Whoops, I showed you how. Thus instead of hint, I've given you another way of handling this stuff. Are you familar with the induced set function notation, f(A) = { f(x) | x in A } ? Have you been introducted to these common expressions? injection = 1-1 surjection = onto bijection = 1-1, onto BTW, fg = f o g function composition. === Subject: Re: proof Hey William, Thanks for all your help. What kept stumbling me was working out a valid g. Now that I see it I follow it. However, how did you come by that g, intuition or was there some set process. Other than that, thank you! > I am working on a proof dealing with finite sets and don't know how to > proceed. The definition I have for finite sets is as follows. Let A be a > finite set. Then for all functions f: A->A, if f is 1-1 then f is onto. Now > here is the problem. > Let f: A->B be a 1-1 correspondence and let A be finite. Prove that B is > finite. Well, since A is a finite set, i created a function g:A->A such that > g is a 1-1 correspondence. In order to prove B is a finite set according to > the definition, I created a function h:B->B where h is 1-1. Then I let an > element b be part of the set B. To prove it is onto, i must show that there > is an element c in B such that h(c) = b. Now I am not quite sure how to do > that. > Assume injection h:B -> B and bijection f:A -> B > g = f^-1hf:A -> A > injection, hence bijection as A finite. Thus > A = g(A) = f^-1hf(A) = f^-1h(B) > B = f(A) = ff^-1h(B) = h(B) > Hence h surjection. > Since this is a homework problem, I would really appreciate if someone could > just nudge me along in the right direction without giving me the answer. I'd > still like to figure this out myself to learn it. Thus if you could tell me > how to start it or what some key steps would be so I can deduce the rest, > that would really help. > Whoops, I showed you how. Thus instead of hint, > I've given you another way of handling this stuff. > Are you familar with the induced set function notation, > f(A) = { f(x) | x in A } ? > Have you been introducted to these common expressions? > injection = 1-1 > surjection = onto > bijection = 1-1, onto > BTW, fg = f o g function composition. === Subject: Re: proof Thanks for all your help. What kept stumbling me was working out a valid > g. Now that I see it I follow it. However, how did you come by that g, > intuition or was there some set process. Other than that, thank you! Let an evil lizard know the secrets of a civil wizard??? ;-) How do you like my Ôalgebraic' method that avoids the unpleasant task of messing around point by point? It's a jigsaw puzzle. Stumble around for long enuf and you'll get some peices to fit. > Assume injection h:B -> B and bijection f:A -> B > g = f^-1hf:A -> A > injection, hence bijection as A finite. Thus > A = g(A) = f^-1hf(A) = f^-1h(B) > B = f(A) = ff^-1h(B) = h(B) > Hence h surjection. > Whoops, I showed you how. Thus instead of hint, > I've given you another way of handling this stuff. === Subject: Re: proof X-Mimeole: Produced By Microsoft MimeOLE V6.00.2800.1165 Okay, I've been trying to do the next proof following the algebraic method. It asks: Assume A is a subset of B and that B is finite. Prove that A is finite. So following ur method I did the following: f:B->B but since A is a subset of B, f: B->B = f:BA -> BA + f:A->A due to the fact that because b is finite, f is a bijection. h:A->A Define g = f^-1h:A->A A= g(A) = f^-1h(A). A= f(A) = ff^-1h(A) = h(A). Am I allowed to do that? The only iffy part is when I say f :BA->BA as well as from A->A. I am not convinced that some element in f might not go from BA -> A. Any ideas? Thanks. > Thanks for all your help. What kept stumbling me was working out a valid > g. Now that I see it I follow it. However, how did you come by that g, > intuition or was there some set process. Other than that, thank you! > Let an evil lizard know the secrets of a civil wizard??? ;-) > How do you like my Ôalgebraic' method that avoids the unpleasant > task of messing around point by point? It's a jigsaw puzzle. > Stumble around for long enuf and you'll get some peices to fit. > Assume injection h:B -> B and bijection f:A -> B > g = f^-1hf:A -> A > injection, hence bijection as A finite. Thus > A = g(A) = f^-1hf(A) = f^-1h(B) > B = f(A) = ff^-1h(B) = h(B) > Hence h surjection. Whoops, I showed you how. Thus instead of hint, > I've given you another way of handling this stuff. === Subject: Re: proof Assume A is a subset of B and that B is finite. >Prove that A is finite. assume f:A -> A injection extend f to g:B -> B, x -> f(x) if x in A, x -> x if x in BA show g injection; thus g surjection as B finite show restriction of g to A, g|A:A -> A surjection now as f = g|A, f surjection, QED -- >f:B->B but since A is a subset of B, f:B->B = f:BA -> BA + f:A->A Weird that + stuff. >due to the fact that because b is finite, f is a bijection. No it's not. This problem seems to need some point by point work. For all you said about f:B -> B, f could be constant map. > h:A->A What's this h? Just any map from A to A? > Define g = f^-1h:A->A > A= g(A) = f^-1h(A). Why? > A= f(A) = ff^-1h(A) = h(A). Why? >Am I allowed to do that? Have you done anything? >The only iffy part is when I say f :BA->BA as well as from A->A. >I am not convinced that some element in f might not go from BA -> A. >Any ideas? Quite rambling and explain your notions as you go, we're not psychic nor do we read minds. -- exercise A finite when for injections f:A -> A, f bijection. Show that definition is equivalent to A finite when for surjections f:A -> A, f bijection. That requires showing If f:A -> A surjection and A finite, then f bijection. and If for all surjections f:A -> A, f bijection, then A finite. -- >> Assume injection h:B -> B and bijection f:A -> B >> g = f^-1hf:A -> A >> injection, hence bijection as A finite. Thus >> A = g(A) = f^-1hf(A) = f^-1h(B) >> B = f(A) = ff^-1h(B) = h(B) >> Hence h surjection. ---- === Subject: Re: proof Sorry, I took your suggestions and have refined my argument to the following: Prove: Assume A is a subset of B and B is finite. Prove A is finite. Assume A is not finite: Let f be an injection from A->A. Define h:B->B like so: h(x) = {f(x), x is an element of A {x, x is an element of BA But since f(x) is not a surjection, then h(x) is not a surjection by the definition of h(x). But this goes against the assumption that B is finite( because by the definition if B is finite then for all functions f(x):B->B, if f(x) is an injection then it is a surjection). Thus by contradiction, A must be finite. Is that any better? Sorry about the previous post, math seems weird when you're sick. Thanks. > === Subject: Re: proof >Assume A is a subset of B and that B is finite. >Prove that A is finite. > assume > f:A -> A injection > extend f to > g:B -> B, x -> f(x) if x in A, x -> x if x in BA > show g injection; thus g surjection as B finite > show restriction of g to A, g|A:A -> A surjection > now as f = g|A, f surjection, QED >f:B->B but since A is a subset of B, f:B->B = f:BA -> BA + f:A->A > Weird that + stuff. >due to the fact that because b is finite, f is a bijection. > No it's not. This problem seems to need some point by point work. > For all you said about f:B -> B, f could be constant map. > h:A->A > What's this h? Just any map from A to A? > Define g = f^-1h:A->A > A= g(A) = f^-1h(A). > Why? > A= f(A) = ff^-1h(A) = h(A). > Why? >Am I allowed to do that? > Have you done anything? >The only iffy part is when I say f :BA->BA as well as from A->A. >I am not convinced that some element in f might not go from BA -> A. >Any ideas? > Quite rambling and explain your notions as you go, > we're not psychic nor do we read minds. > -- exercise > A finite when for injections f:A -> A, f bijection. > Show that definition is equivalent to > A finite when for surjections f:A -> A, f bijection. > That requires showing > If f:A -> A surjection and A finite, then f bijection. > and > If for all surjections f:A -> A, f bijection, then A finite. >> Assume injection h:B -> B and bijection f:A -> B >> g = f^-1hf:A -> A >> injection, hence bijection as A finite. Thus >> A = g(A) = f^-1hf(A) = f^-1h(B) >> B = f(A) = ff^-1h(B) = h(B) >> Hence h surjection. > ---- === Subject: Re: proof > I've been trying to do the next proof following the algebraic method. It > asks: Assume A is a subset of B and that B is finite. Prove that A is > finite. > So following ur method I did the following: > f:B->B Start with: We show that A is finite by assuming that there is an injection f:A->A and from that, showing a contradiction. ... Dale === Subject: Re: proof > I am working on a proof dealing with finite sets and don't know how to > proceed. The definition I have for finite sets is as follows. Let A be a > finite set. Then for all functions f: A->A, if f is 1-1 then f is onto. Now > here is the problem. > Let f: A->B be a 1-1 correspondence and let A be finite. Prove that B is > finite. Well, since A is a finite set, i created a function g:A->A such that > g is a 1-1 correspondence. In order to prove B is a finite set according to > the definition, I created a function h:B->B where h is 1-1. Then I let an > element b be part of the set B. To prove it is onto, i must show that there > is an element c in B such that h(c) = b. Now I am not quite sure how to do > that. > Since this is a homework problem, I would really appreciate if someone could > just nudge me along in the right direction without giving me the answer. I'd > still like to figure this out myself to learn it. Thus if you could tell me > how to start it or what some key steps would be so I can deduce the rest, > that would really help. > Thanks. Assume that B has more objects that the finite set A. Then show that f: A->B is not onto. Then conclude that B is a finite set since it can't have more objects that A. Let me know if this helps. And THINK!!! === Subject: Re: proof X-Mimeole: Produced By Microsoft MimeOLE V6.00.2800.1165 Hm, well it helps, but I can't use it. If you take a look, we never really defined what we mean by more objects. The set is either finite or not finite. Thanks for the help though! > I am working on a proof dealing with finite sets and don't know how to > proceed. The definition I have for finite sets is as follows. Let A be a > finite set. Then for all functions f: A->A, if f is 1-1 then f is onto. > Now > here is the problem. > Let f: A->B be a 1-1 correspondence and let A be finite. Prove that B is > finite. Well, since A is a finite set, i created a function g:A->A such > that > g is a 1-1 correspondence. In order to prove B is a finite set according > to > the definition, I created a function h:B->B where h is 1-1. Then I let an > element b be part of the set B. To prove it is onto, i must show that > there > is an element c in B such that h(c) = b. Now I am not quite sure how to do > that. > Since this is a homework problem, I would really appreciate if someone > could > just nudge me along in the right direction without giving me the answer. > I'd > still like to figure this out myself to learn it. Thus if you could tell > me > how to start it or what some key steps would be so I can deduce the rest, > that would really help. > Thanks. > Assume that B has more objects that the finite set A. Then show that f: > A->B is not onto. Then conclude that B is a finite set since it can't have > more objects that A. Let me know if this helps. And THINK!!! === Subject: Re: proof > I am working on a proof dealing with finite sets and don't know how to > proceed. The definition I have for finite sets is as follows. Let A be a > finite set. Then for all functions f: A->A, if f is 1-1 then f is onto. > Now > here is the problem. > Let f: A->B be a 1-1 correspondence and let A be finite. Prove that B is > finite. Well, since A is a finite set, i created a function g:A->A such > that > g is a 1-1 correspondence. In order to prove B is a finite set according > to > the definition, I created a function h:B->B where h is 1-1. Then I let an > element b be part of the set B. To prove it is onto, i must show that > there > is an element c in B such that h(c) = b. Now I am not quite sure how to do > that. > Since this is a homework problem, I would really appreciate if someone > could > just nudge me along in the right direction without giving me the answer. > I'd > still like to figure this out myself to learn it. Thus if you could tell > me > how to start it or what some key steps would be so I can deduce the rest, > that would really help. > Thanks. > Assume that B has more objects that the finite set A. Then show that f: > A->B is not onto. Then conclude that B is a finite set since it can't have > more objects that A. Let me know if this helps. And THINK!!! The point that you are missing is that you are NOT starting from scratch, that is you don't just have set B. For example, suppose that you are told that set A is finite (has at least 10 objects)and that set B has 3 less objects than A. Now prove that set B is finite. To prove this you do not need to use your definition about, but I guess that you could. Proof: assume set A has n objects, n in naturals. Then Set B has n-3 objects which is a finite positive integer. Done. === Subject: Re: notation question > [...] > Since addition is commutative I know that I can group the emfs according to > their type: > (EL1 + EL2 +...+ELn) + (EC1 + EC2 +...+ ECm) + (ER1 + ER2 +...+ERs) = 0 > Anyway, I know how to finish the rest. I am wondering if there is a > mathematical way to say the above. In particular, how to say sum the > elements in arbitrary order, then reorganize by type. > I'd just say Ô .. collecting terms of the same type ..', or maybe > Ô .. grouping terms ..' (which is the word you used above). Ok cool. I wasn't sure if that was rigorous enough language or not. > Cheers > ------------------------------------------------------------- ------------- - > John R Ramsden (jr@adslate.com) > ------------------------------------------------------------- ------------- - Eternity is a long time, especially towards the end. > Woody Allen === Subject: Re: Mathematics software for Linux permission for an emailed response. X-Tom-Swiftie: This is illegal, I just know it, Tom said with conviction > |[...] > |I was clear on what I meant by free software I thought, but maybe > |not. I mean free by the definition used by the Free Software > |Foundation, or free as defined by the Debian Free Software > |Guidelines. I mean free as in liberty, not as in price. > | > |Maxima doesn't seem to fit the bill, unless I have misunderstood. > | > |Thomas > ``1.7. Is it free? > Yes. Maxima is distributed under the GNU General Public License, with > some export restrictions from the U.S. Department of Energy.'' I'm sorry, I was ambiguous. By doesn't seem to fit the bill, I meant that it's feature set doesn't match what I was looking for when I was looking for such a product. Macysma is indeed free software, and I'm sorry if I ever gave an incorrect impression on that score. === Subject: Re: Goedel and the direction of evolution permission for an emailed response. X-Tom-Swiftie: I'm four feet three inches tall, Tom said shortly > A law is, by definition, algorithmic. If you have not given me the > algorithm to compute future consequences, then you have not given me a > deterministic physical law. > A computer program is also by definition algorithmic. Quite incorrect. An algorithm is guaranteed to terminate. A computer program is a larger set, which might or might not terminate. I suspect a fundamental problem here is that you are simply not very well familiar with the concepts and terms you throw around. There's nothing wrong with making an impressionistic argument, but you would do better to drop the technical language if you aren't going to use it with the appropriate technical precision. > A single approach to mathematics is to focus on a single axiomization > of mathematics that is widely accepted. To me Goedel's result implies that > mathematics needs ultimately to become ever more divergent in the axioms > systems it investigates. Well, that's not what Goedel's result says. We could keep ourselves busy forever just investigating PA! > The only way to explore all the mathematics that captures > something as basic is the halting problem is with a nondeterministic > process. > Huh? What is a nondeterministic process? I know what a formal > system is. It's neither deterministic nor nondeterministic. It isn't > even a process. > A nondeterministic Turing machine can be completely simulated by a > deterministic one, so that isn't what you mean. > It is what I mean. A nondeterministic computer executes multiple or > even an infinite number of programs. I am talking about following > multiple and an ever expanding number of paths. Each path involves > alternative extensions to mathematics. 1) A nondeterministic Turing machine does not execute an infinite number of programs. 2) You said that the only way to explore such-and-such is with a nondeterministic process; if by nondeterministic process you mean a nondeterministic Turing machine, then you are incorrect. Since a deterministic Turing machine can solve any problem a nondeterministic one can, it cannot be true that some set of problems is solvable by nondeterministic machines but not deterministic ones. Therefore, nondeterministic Turing machines cannot be the only way to explore anything. > Following a single path in mathematics or biology leads to > stagnation. Mathematical stagnation is characterized by a recursive > limit ordinal that can never be reached. This is either true, but uninteresting, or it is nontrivial, but false. The trivial sense is that if you do the same thing over and over again, you get stagnation. The nontrivial, but false sense, is that exploring the consequences of a single axiom system is somehow stagnation. Because the possibilities of PA, or ZFC, are quite limitless, I don't think there will ever be any way in which we lead to stagnation. Indeed, you can arithmetize *any* formal system, and then talk about it inside ZFC, which means that you can think about *everything* as just consequences of ZFC if you want to. So indeed, adding extra axioms is, in that specific sense, entirely unnecessary to avoid stagnation. > Precisely. The greater the diversity the more likely it is that > something that has an evolutionary advantage will evolve. Sometimes this is true. Sometimes this is false. > The point I was trying to make was that for the _biological_ > evolution of complexity diversity is essential. Probably true. > Can complexity evolve in other ways that does not require diversity? Yes. The laptop I am typing in right now is an excellent example. > Certainly any > recursive process is going to run up against a Goedel limit. > Any nonrecursive process would seem to require enormous built in > complexity. Humans are able to create enormously complex designs > because of the biological diversity that led to the human > mind. Without continuing to evolve culture in a very diverse way > there will be a Goedel limit to what we can create. You are seriously and radically misunderstanding Goedel's theorem. But leave that aside: Human brains are very complicated physical machines. The laws of physics surely establish limits on what we can create, and limits which are considerably tighter than any problems of a computational limitations character. So I would suggest not worrying about the latter. Thomas === Subject: Re: Goedel and the direction of evolution > A law is, by definition, algorithmic. If you have not given me the > algorithm to compute future consequences, then you have not given me a > deterministic physical law. > A computer program is also by definition algorithmic. > Quite incorrect. An algorithm is guaranteed to terminate. A computer > program is a larger set, which might or might not terminate. A computer program is an algorithm for computing future states. The future consequences are recursively determined by the computer program. You are confusing a computer program that may or may not compute a recursive function with the laws that generate the sequence of states of the program. > It is what I mean. A nondeterministic computer executes multiple or > even an infinite number of programs. I am talking about following > multiple and an ever expanding number of paths. Each path involves > alternative extensions to mathematics. > 1) A nondeterministic Turing machine does not execute an infinite > number of programs. It certainly can. There is a simple algorithm where you do one step of the first program, 2 steps of the first two programs, three steps of the first three programs etc. > 2) You said that the only way to explore such-and-such is with a > nondeterministic process; if by nondeterministic process you mean a > nondeterministic Turing machine, then you are incorrect. Since a > deterministic Turing machine can solve any problem a nondeterministic > one can, it cannot be true that some set of problems is solvable by > nondeterministic machines but not deterministic ones. You are not paying attention to what I am saying. I will try once more. The issue is not what the Turing Machine computes. The issue is what you do with it. If you stick to a single path you are restricted to a single recursively enumerable set. If you explore all possible paths than you are not restricted in that way if the number of paths increase without limit. Specifically you can generate an arbitrarily large initial segment of every real number. > Therefore, nondeterministic Turing machines cannot be the only way to > explore anything. Following an ever expanding number paths is the only way to explore all the axioms that decide specific instances of the halting problem or any other recursively unsolvable problem. > Following a single path in mathematics or biology leads to > stagnation. Mathematical stagnation is characterized by a recursive > limit ordinal that can never be reached. > This is either true, but uninteresting, or it is nontrivial, but > false. > The trivial sense is that if you do the same thing over and over > again, you get stagnation. > The nontrivial, but false sense, is that exploring the consequences of > a single axiom system is somehow stagnation. Because the > possibilities of PA, or ZFC, are quite limitless, I don't think there > will ever be any way in which we lead to stagnation. > Indeed, you can arithmetize *any* formal system, and then talk about > it inside ZFC, which means that you can think about *everything* as > just consequences of ZFC if you want to. So indeed, adding extra > axioms is, in that specific sense, entirely unnecessary to avoid > stagnation. Again I am making a simple point. For any formal system there is a recursive ordinal that is the limit of the recursive ordinals definable within that system. You cannot get to or beyond that ordinal if you stay within that system. Every single path approach to mathematics is going to have a similar limit unless the universe has some nonrecursive processes that are part of physical law. -- Paul Budnik Mountain Math Software http://www.mtnmath.com === Subject: Re: Goedel and the direction of evolution > A Turing machine contains a state function, which does indeed map from > a present states to the next state of the machine. But that mapping > is not an *algorithm*, it's just a function. Of course its an algorithm. Any finite set of finite operations that go from one state to another state is an algorithm. A recursive realization of a function is an algrorithm. > The function in question can be computed, of course, because it is a > finite state table, and we know such functions can be computed. This > is why it is possible for one Turing machine to simulate another. > Of Turing machines, there are some which are guaranteed to terminate > on any input whatsoever. Those are called algorithmic. Other > Turing machines, which might not terminate, are not algorithmic. Of > course, for those others, there is still a state function. > But when we speak of an algorithm, we mean the whole machine, and by > definition, it must terminate, or it isn't an algorithm. > So a physical law, by definition, is algorithmic, meaning that if you > haven't given me a *terminating* Turing machine to say what will the > future look like given this current situation, then you haven't given > me a law. The sequence of states a computer program generates is algorithmic. The program or algorithm that computes future states always terminates. The recursively unsolvable problem is wether certain events or cetain outputs will ever happen. > 1) A nondeterministic Turing machine does not execute an infinite > number of programs. > It certainly can. There is a simple algorithm where you do one step of the > first program, 2 steps of the first two programs, three steps of the first > three programs > etc. > Sure; this works provided each of these is an algorithm. This does not require that the programs terminate. You will eventually execute every step of every program in a finite time even if none of the programs terminate. > 2) You said that the only way to explore such-and-such is with a > nondeterministic process; if by nondeterministic process you mean a > nondeterministic Turing machine, then you are incorrect. Since a > deterministic Turing machine can solve any problem a nondeterministic > one can, it cannot be true that some set of problems is solvable by > nondeterministic machines but not deterministic ones. > You are not paying attention to what I am saying. I will try once > more. The issue is not what the Turing Machine computes. The issue > is what you do with it. If you stick to a single path you are > restricted to a single recursively enumerable set. If you explore > all possible paths than you are not restricted in that way if the > number of paths increase without limit. Specifically you can > generate an arbitrarily large initial segment of every real number. > You are not talking about what the Turing machine computes...but then > what *are* you talking about?! I can use a Turing machine as a > doorstop, or throw it out a window, or use it as a planter for > ßowers, or compute with it. But if not the latter, what do you mean? exploring a set with a Turing machine *is* computation. I am giving up on explaining this to you. Reread the discussion and I am sure you can figure it out if you want to. > Following an ever expanding number paths is the only way to explore > all the axioms that decide specific instances of the halting problem > or any other recursively unsolvable problem. > This still does not solve the halting problem. No nondeterministic > Turing machine can solve the halting problem any more than a > deterministic one can. > Again I am making a simple point. For any formal system there is a > recursive ordinal that is the limit of the recursive ordinals > definable within that system. > Ok, for ZFC, what is the ordinal in question? If I could answer that question I would be up for the next Fields mdal in mathematics. In my youth I did try for a while. -- Paul Budnik Mountain Math Software http://www.mtnmath.com === Subject: Re: Goedel and the direction of evolution permission for an emailed response. > Again I am making a simple point. For any formal system there is a > recursive ordinal that is the limit of the recursive ordinals > definable within that system. > Ok, for ZFC, what is the ordinal in question? > If I could answer that question I would be up for the next Fields mdal in > mathematics. In > my youth I did try for a while. Ok, you didn't take my bait. I will prove to you that there is no such last ordinal. Suppose K is the last ordinal definiable within ZFC. Then consider the ordered set M = K u {K}, where: If x and y are in K, then x < y in M iff x < y in K. If x is K and y is not, then y < x in M. This suffices to define an order relation on M. It is easily checked that the relation is a well ordering since the ordering on M is. Moreover, M is a transitive set, and is indeed the ordinal K+1. So K was not the last ordinal definable within ZFC. But what do you mean by a recursive ordinal? Thomas === Subject: Re: Goedel and the direction of evolution permission for an emailed response. > A Turing machine contains a state function, which does indeed map from > a present states to the next state of the machine. But that mapping > is not an *algorithm*, it's just a function. > Of course its an algorithm. Any finite set of finite operations that go from > one state to another state is an algorithm. A recursive realization of a > function is an algrorithm. No, you miss the question entirely. There is an algorithm for going from one state of the machine to the next, but this is not the program which the program itself instantiates. The following C program is *not* algorithmic: main () {while (1) ;} because it never terminates. There is a program which can interpret this C program: it is also not algorithmic (!) because it only terminates if the C program it is given happens to be a terminating C program. There is also a program which will execute a single step of that C program's interpretation. *That* program is algorithmic, but that's irrelevant to the fact that my little C program above is not. > The sequence of states a computer program generates is algorithmic. The > program or algorithm that computes future states always terminates. The > recursively unsolvable problem is wether > certain events or cetain outputs will ever happen. There is no meaning to asking whether a sequence of states is algorithmic. The term applies to programs, not sequences of states. > Sure; this works provided each of these is an algorithm. > This does not require that the programs terminate. You will eventually > execute every step of every program in a finite time even if none of > the programs terminate. What I mean is that the result is algorithmic only if each of the programs in question is an algorithm. I am become more and more confident that you don't know what you're talking about. > You are not talking about what the Turing machine computes...but then > what *are* you talking about?! I can use a Turing machine as a > doorstop, or throw it out a window, or use it as a planter for > ßowers, or compute with it. But if not the latter, what do you mean? exploring a set with a Turing machine *is* computation. > I am giving up on explaining this to you. Reread the discussion and > I am sure you can figure it out if you want to. This is the last refuge, is it not? I have patiently attempted to understand what you are saying, but can't (and now apparently won't) make it clear. > Ok, for ZFC, what is the ordinal in question? > If I could answer that question I would be up for the next Fields > medal in mathematics. In my youth I did try for a while How about then a proof of the ordinal's existence? Thomas === Subject: Re: hard plane geometry problem > Converting to an optimization problem is not such a big deal, but your > problem might contain nonlinear equations. If you use a ready-to-use > constraint solver (e.g. Juno http://research.compaq.com/SRC/juno-2/ > which is a constraint programming language) What a fantastic program! Thanks so much for this link. --Ian === Subject: Re: Probability continuity and countable additivity > Can someone please explain the importance of the equivalence of > continuity and countable additivity in the development of prob. > theory? It would appear that some people can accept continuity but > not count. additivity, but I can't understand the controversy, given > that the 2 are mathematically equivalent. Any help appreciated. > I suspect the reason you got no replies the first time you posted > this is that nobody is aware of the controversy you mention, > and it's hard to explain the reason for something if someone > doesn't even know that it exists. I know that _I'm_ certainly > unaware of any such controversy... > The two _are_ equivalent. What controversy are you referring > to? Who is it who accepts one but not the other? > ************************ > Thanks, Dr. Ullrich. I have read (Casella/Berger text) that there is a school of statisticians led by De Finetti who do not accept the validity of countable additivity. The authors claim that finite additivity + continuity are somewhat more self-evident than countable additivity. I guess the only controversy here is between De Finetti & Co. and those who do accept countable additivity as an axiom. So I guess my question would be better phrased in 2 parts: 1.- What is DF's objection to countable additivity. 2.- Why do C/B (or others) regard one as more self-evident than the other. As always, I appreciate your help. === Subject: Re: Probability continuity and countable additivity > Can someone please explain the importance of the equivalence of >> continuity and countable additivity in the development of prob. >> theory? It would appear that some people can accept continuity but >> not count. additivity, but I can't understand the controversy, given >> that the 2 are mathematically equivalent. Any help appreciated. > I suspect the reason you got no replies the first time you posted >> this is that nobody is aware of the controversy you mention, >> and it's hard to explain the reason for something if someone >> doesn't even know that it exists. I know that _I'm_ certainly >> unaware of any such controversy... > The two _are_ equivalent. What controversy are you referring >> to? Who is it who accepts one but not the other? >> ************************ Thanks, Dr. Ullrich. I have read (Casella/Berger text) that there is >a school of statisticians led by De Finetti who do not accept the >validity of countable additivity. The authors claim that finite >additivity + continuity are somewhat more self-evident than >countable additivity. Well if in fact they accept finite additivity and continuity but not countable additivity then either they're idiots who can't follow a simple proof or they're talking about something other than standard probability theory. The second seems more likely - I have no idea what their reasons are or what their theory actually looks like, sorry. >I guess the only controversy here is between De >Finetti & Co. and those who do accept countable additivity as an >axiom. So I guess my question would be better phrased in 2 parts: >1.- What is DF's objection to countable additivity. >2.- Why do C/B (or others) regard one as more self-evident than the >other. >As always, I appreciate your help. ************************ === Subject: Re: Probability continuity and countable additivity >Thanks, Dr. Ullrich. I have read (Casella/Berger text) that there is >a school of statisticians led by De Finetti who do not accept the >validity of countable additivity. The authors claim that finite >additivity + continuity are somewhat more self-evident than >countable additivity. > Well if in fact they accept finite additivity and continuity but > not countable additivity then either they're idiots who can't follow > a simple proof or they're talking about something other than > standard probability theory. The second seems more likely - > I have no idea what their reasons are or what their theory > actually looks like, sorry. probably not worth pursuing, certainly not for a beginner like myself. === Subject: Re: Probability continuity and countable additivity > probably not worth pursuing, certainly not for a beginner like myself. Not in the sense that other responses have been directed toward, no; but there may be a theme here, for you to follow as well as anyone. Now I'm not at all certain of the following, but it seems to ring a bell. I have the feeling that deFinetti and maybe others want to *deliberately* drop countable additivity, and thus continuity as it applies directly to probability spaces, (though not necessarily as the standard approximation to the discreteness of the real world, as in applied math generally). I think they may want to do this specifically for the following context. Namely, to give a directly meaningful interpretation to such common locutions as If you pick a natural number at random, there is a one in ten chance that it ends in a zero, and the like. In regular probability, such seemingly simple and natural statements have to be approach crabwise, by considering awkward and even revolting pseudo-equivalents involving picking a number at random from 1 to N and (after calculations) letting N tend to infinity. This is not all that natural, until you have done it many times, and there are in any event competing similar approaches that are not necessarily equivalent and may be more natural in some contexts. So, one can give meaning to the statement quote-marked above in a very natural and immediate manner, AND get sensible-looking results from them, by using merely finitely additive measures (probabilities). Like I say, I don't know if deFinetti ever actually does this, but it seems like something that a philosophically differently-inclined probabilist may well want to do. ------------------------------------------------------------- --------------- -- Bill Taylor W.Taylor@math.canterbury.ac.nz ------------------------------------------------------------- --------------- -- The math is done right, but is the right math done? ------------------------------------------------------------- --------------- -- === Subject: Re: Probability continuity and countable additivity >> probably not worth pursuing, certainly not for a beginner like myself. >Not in the sense that other responses have been directed toward, no; >but there may be a theme here, for you to follow as well as anyone. >Now I'm not at all certain of the following, but it seems to ring a bell. >I have the feeling that deFinetti and maybe others want to *deliberately* >drop countable additivity, and thus continuity as it applies directly to >probability spaces, (though not necessarily as the standard approximation >to the discreteness of the real world, as in applied math generally). >I think they may want to do this specifically for the following context. >Namely, to give a directly meaningful interpretation to such common >locutions as If you pick a natural number at random, there is a one >in ten chance that it ends in a zero, and the like. In regular probability, >such seemingly simple and natural statements have to be approach crabwise, >by considering awkward and even revolting pseudo-equivalents involving >picking a number at random from 1 to N and (after calculations) letting >N tend to infinity. This is not all that natural, until you have done >it many times, and there are in any event competing similar approaches >that are not necessarily equivalent and may be more natural in some contexts. It is not at all natural, and the ones who avoid countable additivity do it generally just as badly. The problem is, there seems not to be even a reasonable way to do it. It is generally the case in trying to do statistics, that one observation puts one in a set of measure zero, and because of this, for any approximate method another can be constructed to get crazy results. >So, one can give meaning to the statement quote-marked above in a very >natural and immediate manner, AND get sensible-looking results from them, >by using merely finitely additive measures (probabilities). Unfortunately, it is not the case. One can get equivalent results which are quite different; natural approaches are what lead to paradoxes. >Like I say, I don't know if deFinetti ever actually does this, but it seems >like something that a philosophically differently-inclined probabilist may >well want to do. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 === Subject: Re: Probability continuity and countable additivity > probably not worth pursuing, certainly not for a beginner like myself. > Not in the sense that other responses have been directed toward, no; > but there may be a theme here, for you to follow as well as anyone. > Now I'm not at all certain of the following, but it seems to ring a bell. > I have the feeling that deFinetti and maybe others want to *deliberately* > drop countable additivity, and thus continuity as it applies directly to > probability spaces, (though not necessarily as the standard approximation > to the discreteness of the real world, as in applied math generally). > I think they may want to do this specifically for the following context. > Namely, to give a directly meaningful interpretation to such common > locutions as If you pick a natural number at random, there is a one > in ten chance that it ends in a zero, and the like. In regular probability, > such seemingly simple and natural statements have to be approach crabwise, > by considering awkward and even revolting pseudo-equivalents involving > picking a number at random from 1 to N and (after calculations) letting > N tend to infinity. This is not all that natural, until you have done > it many times, and there are in any event competing similar approaches > that are not necessarily equivalent and may be more natural in some contexts. > So, one can give meaning to the statement quote-marked above in a very > natural and immediate manner, AND get sensible-looking results from them, > by using merely finitely additive measures (probabilities). > Like I say, I don't know if deFinetti ever actually does this, but it seems > like something that a philosophically differently-inclined probabilist may > well want to do. > ------------------------------------------------------------- ---------------- - > Bill Taylor W.Taylor@math.canterbury.ac.nz > ------------------------------------------------------------- ---------------- - > The math is done right, but is the right math done? > ------------------------------------------------------------- ---------------- - (broadly) that deF's approach takes the intuitive meaning of probability and then derives axioms upon which the theory may be developed, trying to avoid the artificial math that goes with the traditional approach, such as the limit as n goes to infinity, etc. This strikes me as sensible insofar as probability theory seeks application to real-world events. Even though the theory based on Kolmogorov's Axioms is fascinating in itself and certainly worth studying, which approach do you think would be more fruitful in terms of applications? Again, many thanks for your help. === Subject: Re: Probability continuity and countable additivity >Thanks, Dr. Ullrich. I have read (Casella/Berger text) that there is >a school of statisticians led by De Finetti who do not accept the >validity of countable additivity. The authors claim that finite >additivity + continuity are somewhat more self-evident than >countable additivity. >Well if in fact they accept finite additivity and continuity but >>not countable additivity then either they're idiots who can't follow >>a simple proof or they're talking about something other than >>standard probability theory. The second seems more likely - >>I have no idea what their reasons are or what their theory >>actually looks like, sorry. >probably not worth pursuing, certainly not for a beginner like myself. > I suspect the original discussion relates to the foundations of probability. For De Finetti and others, the meaning or purpose of probability is to describe the degree of one's certainty about a phenomenon. Sir Harold Jeffreys presented a set of properties which such a representation should satisfy, and he showed that probability satisfies these properties (whereas statistical confidence and significance, and later fuzzy math, do not). However, the properties imply only finite additivity. Hence, De Finetti concludes that countable additivity per se is a mathematical artificiality. He is more convinced by continuity, and he is willing to accept countable additivity as a consequence thereof. I doubt very much that he is saying that he accepts continuity but not countable additivity. Rather, he refers to motivation of the axioms. All this is my rough understanding. For more on the matter, you might consult the texts of Lindley or De Finetti himself. I seem to recall hearing a talk about this at U.C. Berkeley by our own Herman Rubin some years ago. He was referring to some other work; he talked about how it seemed to him that there was no way to get countable additivity out of the set of axioms developed by some other researcher. Perhaps Herman can elucidate this here. The rest of this post, a response to Agapito's last paragraph, refers to appropriate behavior in this newsgroup, a topic still worthy of discussion. Once again, except his characteristically arrogant dismissal of people as idiots or some other insult, DCU has contributed next to nothing here. One wonders why someone should post at all if s/he admits to having no idea what the answer is. Such posts are particularly irksome since, more often, Dr. Ullrich's posting are informative and clearly reveal his expertise. Thus, I take the time to read all his posts in threads that interest me and feel cheated and annoyed by the useless, condescending ones. And there is something more serious here. Agapito, an earnest student, seems to have taken the usually expert DCU's spurious evaluation too much to heart. The topic of foundations of probability is actually quite interesting and accessible, but based on this thread, Agapito seemed ready to dismiss it. In addition to an adherence to a general civility of discourse, the teacher should consider the effect of his/her pronouncements on the student. -- Stephen J. Herschkorn herschko@rutcor.rutgers.edu === Subject: Re: Probability continuity and countable additivity >>Thanks, Dr. Ullrich. I have read (Casella/Berger text) that there is >>a school of statisticians led by De Finetti who do not accept the >>validity of countable additivity. The authors claim that finite >>additivity + continuity are somewhat more self-evident than >>countable additivity. >Well if in fact they accept finite additivity and continuity but >not countable additivity then either they're idiots who can't follow >a simple proof or they're talking about something other than >standard probability theory. The second seems more likely - >I have no idea what their reasons are or what their theory >actually looks like, sorry. >>probably not worth pursuing, certainly not for a beginner like myself. >I suspect the original discussion relates to the foundations of >probability. For De Finetti and others, the meaning or purpose of >probability is to describe the degree of one's certainty about a >phenomenon. Sir Harold Jeffreys presented a set of properties which >such a representation should satisfy, and he showed that probability >satisfies these properties (whereas statistical confidence and >significance, and later fuzzy math, do not). However, the properties >imply only finite additivity. It is difficult to come up with any reasonable properties of real world probability which will yield countable additivity. It is possible to do this with the Dutch Book approach; this states that probabilities and conditional probabilities do not allow one to bet (one can bet either way at the same odds) in such a way that one can be sure not to lose, and can win with positive probability. This CAN be modified to get countable additivity. However, the problem is usually about unknown states of nature. One can argue, and I have, that it is impossible to separate costs from prior weights; this blocks the above approach. >Hence, De Finetti concludes that countable additivity per se is a >mathematical artificiality. He is more convinced by continuity, and >he is willing to accept countable additivity as a consequence thereof. >I doubt very much that he is saying that he accepts continuity but not >countable additivity. Rather, he refers to motivation of the axioms. >All this is my rough understanding. For more on the matter, you might >consult the texts of Lindley or De Finetti himself. >I seem to recall hearing a talk about this at U.C. Berkeley by our own >Herman Rubin some years ago. He was referring to some other work; he >talked about how it seemed to him that there was no way to get countable >additivity out of the set of axioms developed by some other researcher. >Perhaps Herman can elucidate this here. It is my set of axioms, which are the weakest available to characterize self-consistent behavior. There is a major problem without countable additivity. Most of statistical inference relies on the likelihood ratio, and Bayesian behavior in the general sense needs to combine this with prior weights and loss. This can easily be done with countable additivity, but there is no good way of doing the Radon-Nikodym Theorem without countable additivity. Without countable additivity, even certain convergence does not imply convergence in measure. There have been attempts to get around this by a limit process, but it is not difficult to prove that one can adapt this limit process for a purely finitely additive measure to get anything. There is a version of the Fubini Theorem available, but it is not what is wanted. But it is Radon-Nikodym which is really what is important. The reasonable use of Bayes' Theorem is not possible without it. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 === Subject: Re: Probability continuity and countable additivity > The rest of this post, a response to Agapito's last paragraph, refers to > appropriate behavior in this newsgroup, a topic still worthy of discussion. > Once again, except his characteristically arrogant dismissal of people > as idiots or some other insult, DCU has contributed next to nothing > here. One wonders why someone should post at all if s/he admits to > having no idea what the answer is. Such posts are particularly irksome > since, more often, Dr. Ullrich's posting are informative and clearly > reveal his expertise. Thus, I take the time to read all his posts in > threads that interest me and feel cheated and annoyed by the useless, > condescending ones. > And there is something more serious here. Agapito, an earnest student, > seems to have taken the usually expert DCU's spurious evaluation too > much to heart. The topic of foundations of probability is actually > quite interesting and accessible, but based on this thread, Agapito > seemed ready to dismiss it. In addition to an adherence to a general > civility of discourse, the teacher should consider the effect of his/her > pronouncements on the student. Like your and others' postings, Dr. Ullrich's have been extremely helpful to me. I find his insistence on clarity and precision useful as well, even though they often point to my own lack thereof. It is doubtful that anyone trying to learn the subject by oneself could hope to do so as effectively without the help of people like yourself, willing to give of your time and expertise to answer and clarify questions. It is an extraordinary resource and evidence of your dedication to teach anyone willing to learn. As long as it is available, I plan to use it to the fullest extent. === Subject: Re: Probability continuity and countable additivity >>Thanks, Dr. Ullrich. I have read (Casella/Berger text) that there is >>a school of statisticians led by De Finetti who do not accept the >>validity of countable additivity. The authors claim that finite >>additivity + continuity are somewhat more self-evident than >>countable additivity. > >Well if in fact they accept finite additivity and continuity but >not countable additivity then either they're idiots who can't follow >a simple proof or they're talking about something other than >standard probability theory. The second seems more likely - >I have no idea what their reasons are or what their theory >actually looks like, sorry. >probably not worth pursuing, certainly not for a beginner like myself. >[Comments very relevant to the OP's question but irrelevant to what >I want to respond to snipped.] >The rest of this post, a response to Agapito's last paragraph, refers to >appropriate behavior in this newsgroup, a topic still worthy of discussion. >Once again, except his characteristically arrogant dismissal of people >as idiots or some other insult, DCU has contributed next to nothing >here. One wonders why someone should post at all if s/he admits to >having no idea what the answer is. To answer the second question first: I made a reply to his top post in this thread because I noticed it was the second thread he'd started with the same question - nobody had replied to the first. Regarding my arrogant dismissal of people as idiots: You seem to be missing the words if and or. I said that _if_ people are accepting continuity but not countable additivity (which seemed as unlikely to me as it does to you, but he'd said it was so and I had no direct evidence to the contrary) then they were either idiots who couldn't follow a simple proof _or_ they were talking about something other than standard probability theory. Why did I say that? For the sake of informing the OP of possible answers to his question! It _is_ true that there _are_ idiots in the universe who are unable to follow a simple proof - that _is_ a _possible_ explanation for the phenomenon he'd asked about. Then I _said_ that the second possibility seemed more likely to me! Given that I _said_ that the idea that the people he was asking about were idiots did _not_ seem to me to be the most likely explanation, your characterization of my comments as arrogant dismissal seems a little off. The main reason I said what I said was to point out the _second_ possibility, which it seemed to me perhaps the OP had not considered: that the people he was asking about were talking about something other than standard probability theory. (If he'd asked what I meant by that I would have explained that I was referring to something other than basing probability on measure theory as is usually done.) In case you missed it, read the paragraph above again: the reason I said what I said was to point out a possible answer to the OP's question that it seemed to me he might not have considered. > Such posts are particularly irksome >since, more often, Dr. Ullrich's posting are informative and clearly >reveal his expertise. Thus, I take the time to read all his posts in >threads that interest me You don't seem to have read this one very carefully - instead you saw the word idiot and ignored the rest of the paragraph. Or so it appears. >and feel cheated and annoyed by the useless, >condescending ones. Uh, that's tough. You feel cheated? You can always apply for a refund of the money you paid me. Or you can find a newsreader with a killfile. >And there is something more serious here. Agapito, an earnest student, >seems to have taken the usually expert DCU's spurious evaluation too >much to heart. The topic of foundations of probability is actually >quite interesting and accessible, but based on this thread, Agapito >seemed ready to dismiss it. In addition to an adherence to a general >civility of discourse, the teacher should consider the effect of his/her >pronouncements on the student. Nothing arrogant about that statement. ************************ === Subject: Re: Probability continuity and countable additivity > Hence, De Finetti concludes that countable additivity per se is a > mathematical artificiality. He is more convinced by continuity, and > he is willing to accept countable additivity as a consequence thereof. > I doubt very much that he is saying that he accepts continuity but not > countable additivity. Rather, he refers to motivation of the axioms. > All this is my rough understanding. For more on the matter, you might > consult the texts of Lindley or De Finetti himself. Consider also the probability theory of R.T. Cox (later developed by E.T. Jaynes). Cox based his theory on a certain set of axioms which yield the product rule p(a,b) = p(a|b) p(b) and the negation rule p(not a) = 1 - p(a). I don't know if countable addditivity could be derived in this framework -- I am pretty sure that some probability functions in this framework could have finite additivity but not countable additivity. The last book of E.T. Jaynes, Probability Theory: the Logic of Science, has now been published. Aside from the ill-tempered anti-Fisherisms, it is full of useful material. I believe R.T. Cox's books have recently come back into print. For an introduction to his theory, see: R.T. Cox (1946) Probability, Frequency, and Reasonable Expectation, Am J. Physics 14(1):1--13. Reprinted in Shafer and Pearl, eds., Readings in Uncertain Reasoning, San Mateo, CA: Morgan Kaufmann. >>Well if in fact they accept finite additivity and continuity but >>not countable additivity then either they're idiots who can't follow >>a simple proof or they're talking about something other than >>standard probability theory. The second seems more likely - >>I have no idea what their reasons are or what their theory >>actually looks like, sorry. I have to say I was pretty dismayed by this. For what it's worth, Robert Dodier -- ``Whenever I hear bagpipes I want to go home, mainly because my home doesn't have anyone playing bagpipes in it.'' -- Naich === Subject: Re: Probability continuity and countable additivity > Hence, De Finetti concludes that countable additivity per se is a > mathematical artificiality. He is more convinced by continuity, and > he is willing to accept countable additivity as a consequence thereof. > I doubt very much that he is saying that he accepts continuity but not > countable additivity. Rather, he refers to motivation of the axioms. > All this is my rough understanding. For more on the matter, you might > consult the texts of Lindley or De Finetti himself. > Consider also the probability theory of R.T. Cox (later developed > by E.T. Jaynes). Cox based his theory on a certain set of axioms > which yield the product rule p(a,b) = p(a|b) p(b) and the negation > rule p(not a) = 1 - p(a). I don't know if countable addditivity > could be derived in this framework -- I am pretty sure that some > probability functions in this framework could have finite > additivity but not countable additivity. > The last book of E.T. Jaynes, Probability Theory: the Logic of > Science, has now been published. Aside from the ill-tempered > anti-Fisherisms, it is full of useful material. I believe R.T. Cox's > books have recently come back into print. For an introduction > to his theory, see: R.T. Cox (1946) Probability, Frequency, and > Reasonable Expectation, Am J. Physics 14(1):1--13. Reprinted in > Shafer and Pearl, eds., Readings in Uncertain Reasoning, San Mateo, > CA: Morgan Kaufmann. Thanks, there's obviously more to probability theory than the standard approach. Does one, then, need to learn about all of them before making judgements about which would be more applicable in a particular situation? For a beginner like me, a harsh prospect indeed! Many thanks for your contribution. === Subject: Re: Probability continuity and countable additivity > Thanks, Dr. Ullrich. I have read (Casella/Berger text) that there is > a school of statisticians led by De Finetti who do not accept the > validity of countable additivity. The authors claim that finite > additivity + continuity are somewhat more self-evident than > countable additivity. I guess the only controversy here is between De > Finetti & Co. and those who do accept countable additivity as an > axiom. So I guess my question would be better phrased in 2 parts: > 1.- What is DF's objection to countable additivity. > 2.- Why do C/B (or others) regard one as more self-evident than the > other. OK, De Finetti. Well, in that case you reject not only countable additivity, but (as a consequence) you also reject continuity as you formulated it in your original post. As you noted, the two are equivalent (given finite additivity). -- G. A. Edgar http://www.math.ohio-state.edu/~edgar/ === Subject: Physics and batteries You have a ßashlight that holds 2 (1.5 volts) batteries. If you reverse just one battery the ßashlight will not work if you turn on the ßashlight. But do the batteries get used up if you leave the switch on. Now you have a ßashlight with 4 batteries. You have 3 batteries positioned correctly and 1 backwards. Now the ßashlight works as if there are only 2 batteries (1.5 + 1.5 + 1.5 - 1.5 = 2 x 1.5) and my question is which batteries are being used. I can't imagine the answer is 2 because then I would not understand which 2 (of the 3) would be the ones being used. Steven === Subject: Re: Physics and batteries > You have a ßashlight that holds 2 (1.5 volts) batteries. If you reverse > just one battery the ßashlight will not work if you turn on the ßashlight. > But do the batteries get used up if you leave the switch on. > Now you have a ßashlight with 4 batteries. You have 3 batteries positioned > correctly and 1 backwards. Now the ßashlight works as if there are only 2 > batteries (1.5 + 1.5 + 1.5 - 1.5 = 2 x 1.5) and my question is which > batteries are being used. I can't imagine the answer is 2 because then I > would not understand which 2 (of the 3) would be the ones being used. > Steven All 3 batteries that have current going through them in the proper direction are being used. The other one is being recharged, which it probably won't tolerate for too long, and getting warm. === Subject: Re: Physics and batteries I'm cross posting this to sci.physics.electromag because that may be a more appropriate venue > You have a ßashlight that holds 2 (1.5 volts) batteries. If you reverse > just one battery the ßashlight will not work if you turn on the > ßashlight. > But do the batteries get used up if you leave the switch on. Is this a question or a statement? I think the batteries would not run down, and this seems to be borne out by experiment with my ßashlight, but it is possible that they are not touching enough to make a circut (2 AA bateries in series) > Now you have a ßashlight with 4 batteries. You have 3 batteries > positioned > correctly and 1 backwards. Now the ßashlight works as if there are only 2 > batteries (1.5 + 1.5 + 1.5 - 1.5 = 2 x 1.5) and my question is which > batteries are being used. I can't imagine the answer is 2 because then I > would not understand which 2 (of the 3) would be the ones being used. > Steven I have never seen a ßashlight that takes 2 or 4 batteries. I think we need to know how they are wired: It can't be batteries in series, or else it wouldn't work with only 2. So it must be 4 in parallel, or 2 sets of 2 in series, and the sets are wired in parallel (I'm guessing the latter). In that case I would guess that the branch with the 2 correctly aligned batteries is doing all the work, and the other branch with the mismatched pair is doing nothing (no chemical energy in those batteries is being dissapated). --Jeff > All 3 batteries that have current going through them in the proper direction > are being used. The other one is being recharged, which it probably won't > tolerate for too long, and getting warm. === Subject: Re: Physics and batteries > I'm cross posting this to sci.physics.electromag because that may be a > more appropriate venue > You have a ßashlight that holds 2 (1.5 volts) batteries. If you reverse > just one battery the ßashlight will not work if you turn on the > ßashlight. > But do the batteries get used up if you leave the switch on. > Is this a question or a statement? I think the batteries would not run down, > and this seems to be borne out by experiment with my ßashlight, but it > is possible that they are not touching enough to make a circut (2 AA > bateries in series) If the batteries are equal, no current ßows and nothing happens. If 1 battery puts out slightly more voltage than the other, it charges the other and discharges itself until they are equal. Eventually one of the batteries self discharges and they both go dead; this may take quite a while with 2 new batteries. > Now you have a ßashlight with 4 batteries. You have 3 batteries > positioned > correctly and 1 backwards. Now the ßashlight works as if there are only 2 > batteries (1.5 + 1.5 + 1.5 - 1.5 = 2 x 1.5) and my question is which > batteries are being used. I can't imagine the answer is 2 because then I > would not understand which 2 (of the 3) would be the ones being used. > Steven > I have never seen a ßashlight that takes 2 or 4 batteries. I think we need > to know how they are wired: It can't be batteries in series, or else it > wouldn't work with only 2. So it must be 4 in parallel, or 2 sets of 2 in > series, and the sets are wired in parallel (I'm guessing the latter). Virtually all ßashlights work with the batteries in series. The biggest ßashlight I have seen takes 6 D cells. When in my teens working at the drive-in theater, the lot guy carried 2 of them; 1 shiny and working and the other with the batteries corroded in looking like a banana from it's use to quite belligerent drunks. > In that case I would guess that the branch with the 2 correctly aligned > batteries is doing all the work, and the other branch with the mismatched > pair is doing nothing (no chemical energy in those batteries is being > dissapated). > --Jeff > All 3 batteries that have current going through them in the proper direction > are being used. The other one is being recharged, which it probably won't > tolerate for too long, and getting warm. Correct. -- Jim Pennino Remove -spam-sux to reply.