mm-366 == My apologies for not trawling the newsgroup enough to find a likely answer to this query.. it is likely here somewhere due to the high google rating oif the site in question and high amount of transfinite set discussion I have been happily reading. I seem to remember hearing a theorem that the power set of a set is always larger, even for transfinite sets.. i.e. the power set of the integers must be uncountable. Is this true? And if so, where is the error in the construction of the countable list of such power set found here: http://descmath.com/diag/power.html ? Thanks - lukas saul === Subject: : Re: power set cardinality? > My apologies for not trawling the newsgroup enough to find a likely > answer to this query.. it is likely here somewhere due to the high > google rating oif the site in question and high amount of transfinite > set discussion I have been happily reading. > I seem to remember hearing a theorem that the power set of a set is > always larger, even for transfinite sets.. What about the so-called Universal Set -- the set of everything? Is its power set larger than the Universal Set itself? How could this be? Or does the Universal Set not really exist? If so, must every set exclude at least one thing? Dan === Subject: : Re: power set cardinality? >> My apologies for not trawling the newsgroup enough to find a likely >> answer to this query.. it is likely here somewhere due to the high >> google rating oif the site in question and high amount of transfinite >> set discussion I have been happily reading. >> I seem to remember hearing a theorem that the power set of a set is >> always larger, even for transfinite sets.. > What about the so-called Universal Set -- the set of everything? Is its > power set larger than the Universal Set itself? How could this be? Or does > the Universal Set not really exist? If so, must every set exclude at least > one thing? In the versions of set theory that are in common use, there are no universal sets. There are some theories in which a universal set exists, but you have to give up some other things (such as the existence of a power set) in order to avoid contradictions. And having no universal set also means you can't have a set that excludes just one thing, or any finite number of things, or any collection of things that itself forms a set, because in those situations you would then be able to express the universal set as a union. Rather than a top-down limitation (every set must exclude something), there is a bottom-up limitation. There are only certain ways in which sets can be combined to form new sets, and a set of all sets, or a set of all sets satisfying property P is not allowed, in general. -- Dave Seaman Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling. === Subject: : Re: power set cardinality? Visiting Assistant Professor at the University of Montana. > My apologies for not trawling the newsgroup enough to find a likely > answer to this query.. it is likely here somewhere due to the high > google rating oif the site in question and high amount of transfinite > set discussion I have been happily reading. > I seem to remember hearing a theorem that the power set of a set is > always larger, even for transfinite sets.. >> What about the so-called Universal Set -- the set of everything? Is its >> power set larger than the Universal Set itself? How could this be? Or does >> the Universal Set not really exist? If so, must every set exclude at least >> one thing? >In the versions of set theory that are in common use, there are no >universal sets. There are some theories in which a universal set exists, >but you have to give up some other things (such as the existence of a >power set) in order to avoid contradictions. I thought a measurable cardinal would give you a sort of universal set in which you can take power sets. And that the axiom of universes was relatively consistent with ZFC. I guess what you would give up is the notion that it contains everything, and have to settle on it contains all of these things? == == Arturo Magidin magidin@math.berkeley.edu === Subject: : Re: power set cardinality? >>In the versions of set theory that are in common use, there are no >>universal sets. There are some theories in which a universal set exists, >>but you have to give up some other things (such as the existence of a >>power set) in order to avoid contradictions. > I thought a measurable cardinal would give you a sort of universal > set in which you can take power sets. And that the axiom of > universes was relatively consistent with ZFC. I was trying to give an example of how a universal set might exist in some theory, not provide an absolute rule. I am certainly no expert on set theory. > I guess what you would give up is the notion that it contains > everything, and have to settle on it contains all of these things? -- Dave Seaman Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling. === Subject: : Re: power set cardinality? Visiting Assistant Professor at the University of Montana. >> My apologies for not trawling the newsgroup enough to find a likely >> answer to this query.. it is likely here somewhere due to the high >> google rating oif the site in question and high amount of transfinite >> set discussion I have been happily reading. >> I seem to remember hearing a theorem that the power set of a set is >> always larger, even for transfinite sets.. >What about the so-called Universal Set -- the set of everything? Is its >power set larger than the Universal Set itself? In axiomatic set theory, there is no such set. > How could this be? Or does >the Universal Set not really exist? There is no set of all sets. > If so, must every set exclude at least >one thing? In axiomatic set theory, there are certain collections which are too big to be sets. The collection of all sets (or of all but a finite number of sets) is one of them. == == Arturo Magidin magidin@math.berkeley.edu === Subject: : Re: power set cardinality? > My apologies for not trawling the newsgroup enough to find a likely > answer to this query.. it is likely here somewhere due to the high > google rating oif the site in question and high amount of transfinite > set discussion I have been happily reading. I seem to remember hearing a theorem that the power set of a set is > always larger, even for transfinite sets.. i.e. the power set of the integers must be uncountable. Is this true? > Yes. If A is a set and P(A) is the power set of A, suppose f is a bijection between the two. Let B = {a in A : a is not an element of f(a)}. B is a subset of A, therefore B is an element of P(A), therefore since f is a bijection there exists b in A such that f(b) = B. Now we ask, is b an element of B? If it is, then by definition of B, b is not in B. If it isn't, then again by definition of B, b is in B. In other words we just proved that b is in B if and only if b is NOT in B. This is a contradiction, showing that our assumption that f is a bijection is incorrect. Since f was arbitrary, there can be no bijection from A to P(A). > And if so, where is the error in the construction of the countable > list of such power set found here: http://descmath.com/diag/power.html > One doesn't have time to debunk all the false sites on the Net. === Subject: : Re: power set cardinality? My apologies for not trawling the newsgroup enough to find a likely > answer to this query.. it is likely here somewhere due to the high > google rating oif the site in question and high amount of transfinite > set discussion I have been happily reading. I seem to remember hearing a theorem that the power set of a set is > always larger, even for transfinite sets.. i.e. the power set of the integers must be uncountable. Is this true? > Yes. If A is a set and P(A) is the power set of A, suppose f is a > bijection between the two. Let B = {a in A : a is not an element of > f(a)}. B is a subset of A, therefore B is an element of P(A), therefore > since f is a bijection there exists b in A such that f(b) = B. Now we ask, is b an element of B? If it is, then by definition of B, b > is not in B. If it isn't, then again by definition of B, b is in B. In other words we just proved that b is in B if and only if b is NOT in > B. This is a contradiction, showing that our assumption that f is a > bijection is incorrect. Since f was arbitrary, there can be no > bijection from A to P(A). > Very pretty! This seems similar to the (name forgotten) famous one: the set of all sets that don't contain themselves. Does it contain itself? Perhaps there is another assumption that could be creating your contradiction: that there exists a in A : a is not an element of f(a) .. In particular, we have {f(a_i)...} = P(A) (assuming f is a bijection). Is there an element a in A that is not in P(A)? Every element of a set is also in its power set so 'a' does not exist and B is the empty set... In a related issue, what is P({})? Is it {{}}? And if so, where is the error in the construction of the countable > list of such power set found here: http://descmath.com/diag/power.html > One doesn't have time to debunk all the false sites on the Net. Certainly true. Sorry.. === Subject: : Re: power set cardinality? My apologies for not trawling the newsgroup enough to find a likely >answer to this query.. it is likely here somewhere due to the high >google rating oif the site in question and high amount of transfinite >set discussion I have been happily reading. >I seem to remember hearing a theorem that the power set of a set is >always larger, even for transfinite sets.. >i.e. the power set of the integers must be uncountable. >Is this true? >>Yes. If A is a set and P(A) is the power set of A, suppose f is a >>bijection between the two. Let B = {a in A : a is not an element of >>f(a)}. B is a subset of A, therefore B is an element of P(A), therefore >>since f is a bijection there exists b in A such that f(b) = B. >>Now we ask, is b an element of B? If it is, then by definition of B, b >>is not in B. If it isn't, then again by definition of B, b is in B. >>In other words we just proved that b is in B if and only if b is NOT in >>B. This is a contradiction, showing that our assumption that f is a >>bijection is incorrect. Since f was arbitrary, there can be no >>bijection from A to P(A). > Very pretty! This seems similar to the (name forgotten) famous one: > the set of all sets that don't contain themselves. Does it contain > itself? This is Russell's paradox. Incidently, it's actually a (form of) a proof of Cantor's theorem that the powerset of any set is of higher cardinality than the set itself! Basicly, consider a model of set theory, i.e. a structure consisting of elements for which there is provided a relation in and in which extensionality holds, i.e. if for all x x in a if and only if x in b, then a = b. We can aks of various properties P whether or not this model contains an element a, such that the elements having the relation in to a are exactly those having the property P. Now, Russell's paradox shows that not every property can have such a corresponding element a, which means just that we can't map bijectively the powerset of the model - which consists of all possible properties of the model - into the model itself, since if we could, then a contradiction would follows by Russell's reasoning. > In a related issue, what is P({})? Is it {{}}? Yes. -- Aatu Koskensilta (aatu.koskensilta@xortec.fi) Wovon man nicht sprechen kann, daruber muss man schweigen - Ludwig Wittgenstein, Tractatus Logico-Philosophicus === Subject: : Re: power set cardinality? [Re: proof of Cantor's Theorem] > Very pretty! This seems similar to the (name forgotten) famous one: > the set of all sets that don't contain themselves. Does it contain > itself? > Perhaps there is another assumption that could be creating your > contradiction: that there exists a in A : a is not an element of f(a) There is no such assumption in the proof. The argument works even if no such a exists. > In particular, we have {f(a_i)...} = P(A) (assuming f is a bijection). > Is there an element a in A that is not in P(A)? Every element of a > set is also in its power set so 'a' does not exist and B is the empty > set... Not true. If a is a member of A, then you can conclude that {a} is a member of P(A), but not that a is a member of P(A). A member of A need not be a subset of A. > In a related issue, what is P({})? Is it {{}}? Yes. -- Dave Seaman Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling. === Subject: : Re: power set cardinality? [Re: proof of Cantor's Theorem] Very pretty! This seems similar to the (name forgotten) famous one: > the set of all sets that don't contain themselves. Does it contain > itself? Perhaps there is another assumption that could be creating your > contradiction: that there exists a in A : a is not an element of f(a) There is no such assumption in the proof. The argument works even if no > such a exists. In particular, we have {f(a_i)...} = P(A) (assuming f is a bijection). > Is there an element a in A that is not in P(A)? Every element of a > set is also in its power set so 'a' does not exist and B is the empty > set... Not true. If a is a member of A, then you can conclude that {a} is a > member of P(A), but not that a is a member of P(A). A member of A need > not be a subset of A. In a related issue, what is P({})? Is it {{}}? Yes. Whoops!! :) Please diregard my erroneous claim that the size of {{}} = size of {}. trivial bijection indeed.. (eats hat) Thanks again for the proof - luke === Subject: : Re: power set cardinality? [Re: proof of Cantor's Theorem] Very pretty! This seems similar to the (name forgotten) famous one: > the set of all sets that don't contain themselves. Does it contain > itself? Perhaps there is another assumption that could be creating your > contradiction: that there exists a in A : a is not an element of f(a) There is no such assumption in the proof. The argument works even if no > such a exists. In particular, we have {f(a_i)...} = P(A) (assuming f is a bijection). > Is there an element a in A that is not in P(A)? Every element of a > set is also in its power set so 'a' does not exist and B is the empty > set... Not true. If a is a member of A, then you can conclude that {a} is a > member of P(A), but not that a is a member of P(A). A member of A need > not be a subset of A. Thanks Dave and Fishfry for pointing out my error. In particular, that the set {a} != {{a}}. However... In a related issue, what is P({})? Is it {{}}? Yes. If so, the bijection is trivial and exists.. Why does the proof not apply? === Subject: : Re: power set cardinality? > However... > In a related issue, what is P({})? Is it {{}}? Yes. If so, the bijection is trivial and exists.. Why does the proof not > apply? Oh? {} contains no elements but {{}} contains one element, namely {}, so there is no bijection between them. === Subject: : Re: power set cardinality? Visiting Assistant Professor at the University of Montana. >> In a related issue, what is P({})? Is it {{}}? >> Yes. >If so, the bijection is trivial and exists.. Why does the proof not >apply? It does. There is no bijection. P({}) has one element (namely, the empty set), but {} has no elements. The only function from {} to {{}} is the empty function, and it is not surjective. (To think of it another way: P({}) has one element. If a bijection exist, then there must be an element of the empty set whose image is the unique element of P({}). Can you exhibit an element of the empty set with that property? In fact, can you exhibit an element of the empty set, period?) == == Arturo Magidin magidin@math.berkeley.edu === Subject: : Re: power set cardinality? >> [Re: proof of Cantor's Theorem] >> Very pretty! This seems similar to the (name forgotten) famous one: >> the set of all sets that don't contain themselves. Does it contain >> itself? >> Perhaps there is another assumption that could be creating your >> contradiction: that there exists a in A : a is not an element of f(a) >> There is no such assumption in the proof. The argument works even if no >> such a exists. >> In particular, we have {f(a_i)...} = P(A) (assuming f is a bijection). >> Is there an element a in A that is not in P(A)? Every element of a >> set is also in its power set so 'a' does not exist and B is the empty >> set... >> Not true. If a is a member of A, then you can conclude that {a} is a >> member of P(A), but not that a is a member of P(A). A member of A need >> not be a subset of A. >Thanks Dave and Fishfry for pointing out my error. In particular, >that the set {a} != {{a}}. >However... >> In a related issue, what is P({})? Is it {{}}? >> Yes. >If so, the bijection is trivial and exists.. There is no bijection between {} and {{}}. That's because {} has no elements, in particular there's no element of {} to map to the one element of {{}}. >Why does the proof not >apply? It does. ************************ David C. Ullrich === Subject: : Re: power set cardinality? My apologies for not trawling the newsgroup enough to find a likely > answer to this query.. it is likely here somewhere due to the high > google rating oif the site in question and high amount of transfinite > set discussion I have been happily reading. I seem to remember hearing a theorem that the power set of a set is > always larger, even for transfinite sets.. i.e. the power set of the integers must be uncountable. Is this true? > Yes. If A is a set and P(A) is the power set of A, suppose f is a > bijection between the two. Let B = {a in A : a is not an element of > f(a)}. B is a subset of A, therefore B is an element of P(A), therefore > since f is a bijection there exists b in A such that f(b) = B. Now we ask, is b an element of B? If it is, then by definition of B, b > is not in B. If it isn't, then again by definition of B, b is in B. In other words we just proved that b is in B if and only if b is NOT in > B. This is a contradiction, showing that our assumption that f is a > bijection is incorrect. Since f was arbitrary, there can be no > bijection from A to P(A). > Very pretty! This seems similar to the (name forgotten) famous one: > the set of all sets that don't contain themselves. Does it contain > itself? Perhaps there is another assumption that could be creating your > contradiction: that there exists a in A : a is not an element of f(a) > .. When did we make use of that assumption? We defined B as above, but for all we know B is empty. It matters not. > In particular, we have {f(a_i)...} = P(A) (assuming f is a bijection). > Is there an element a in A that is not in P(A)? Every element of a > set is also in its power set so 'a' does not exist and B is the empty > set... > I'm assuming you mean {f(a} : a in A}. You can't write a_i to enumerate A, because there's no assumption that A is countable. You can't even index A using transfinite ordinals because without assuming the axiom of choice, A might not even be well-orderable. In general it's not true that every element of a set is in its power set. For example if A = {a,b} then P(A) = { {}, {a}, {b}, {a,b} }. Note that a is not the same as {a}. > In a related issue, what is P({})? Is it {{}}? Yes. And if so, where is the error in the construction of the countable > list of such power set found here: http://descmath.com/diag/power.html > One doesn't have time to debunk all the false sites on the Net. Certainly true. Sorry.. Well a couple of others found the time. I should have said, One doesn't have time to debunk all the false sites on the Net, for suitable values of 'One.' === Subject: : Re: power set cardinality? >> And if so, where is the error in the construction of the countable >> list of such power set found here: >> http://descmath.com/diag/power.html > One doesn't have time to debunk all the false sites on the Net. Surely not, but I was able to predict where the error lay without looking at the argument. -- Dave Seaman Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling. === Subject: : Re: power set cardinality? Visiting Assistant Professor at the University of Montana. > And if so, where is the error in the construction of the countable > list of such power set found here: http://descmath.com/diag/power.html > One doesn't have time to debunk all the false sites on the Net. >Surely not, but I was able to predict where the error lay without looking >at the argument. Well, that's easy. Question is, was your prediction accurate? (-: == == Arturo Magidin magidin@math.berkeley.edu === Subject: : Re: power set cardinality? >> And if so, where is the error in the construction of the countable >> list of such power set found here: >> http://descmath.com/diag/power.html > One doesn't have time to debunk all the false sites on the Net. >>Surely not, but I was able to predict where the error lay without looking >>at the argument. > Well, that's easy. Question is, was your prediction accurate? (-: Yes, actually, it was. -- Dave Seaman Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling. === Subject: : Re: power set cardinality? >> And if so, where is the error in the construction of the countable >> list of such power set found here: >> http://descmath.com/diag/power.html > One doesn't have time to debunk all the false sites on the Net. >>Surely not, but I was able to predict where the error lay without looking >>at the argument. > Well, that's easy. Question is, was your prediction accurate? (-: >> Yes, actually, it was. >I predict that, if asked, Dave will say his guess was: the author >enumerated only the finite subsets of N. >I am not so clever. I had to look at the site and see where the error >was. In hindsight, Dave's prediction is obvious, alright. It's not a question of cleverness, you just haven't paid enough attention to the various proofs that the power set of N is countable. Enumerating just the finite subsets of N is the _standard_ proof. (Actually it's the only one I recall ever seeing. Whether or not it's the only one that exists it is in fact extremely standard.) ************************ David C. Ullrich === Subject: : Re: power set cardinality? <87ad95baqp.fsf@phiwumbda.org> linux) > It's not a question of cleverness, you just haven't paid enough > attention to the various proofs that the power set of N is > countable. I'm *sure* you're mistaken. I've paid too damn much attention to these proofs (well, perhaps not enough to make Dave's guess, but too damn much in a purely objective sense). -- Jesse Hughes LOL. How arrogant you are. Now when you realize that I DID prove Goldbach's conjecture and that I proved Fermat's Last Theorem as well, how are you going to feel then? -- === Subject: : Re: power set cardinality? >> It's not a question of cleverness, you just haven't paid enough >> attention to the various proofs that the power set of N is >> countable. >I'm *sure* you're mistaken. I've paid too damn much attention to >these proofs (well, perhaps not enough to make Dave's guess, but too >damn much in a purely objective sense). Ok, I'm mistaken. It's happened before, not that I recall exactly when... What other proof that the power set of N is countable have you seen? Just curious. ************************ David C. Ullrich === Subject: : Re: power set cardinality? <87ad95baqp.fsf@phiwumbda.org> <87r82h6lz8.fsf@phiwumbda.org> linux) > It's not a question of cleverness, you just haven't paid enough > attention to the various proofs that the power set of N is > countable. >>I'm *sure* you're mistaken. I've paid too damn much attention to >>these proofs (well, perhaps not enough to make Dave's guess, but too >>damn much in a purely objective sense). > Ok, I'm mistaken. It's happened before, not that I recall exactly > when... > What other proof that the power set of N is countable have you seen? > Just curious. Sorry, you weren't mistaken in that regard. I can't recall any other proof. I was just saying I'd seen more than enough, not fewer. -- My proof has been checked very thoroughly, both by me and others. Those others apparently decided that they would not believe the proof was correct, but cannot support that position using mathematics. But hey, they're just human beings. --JSH, prover of Fermat's Last Thm === Subject: : Re: power set cardinality? >What other proof that the power set of N is countable have you seen? >Just curious. Let I_n denote {1,2,...,n}. Clearly (as has already been discussed in some recent thread, possibly this one) the limit of I_n, as n -> oo, is N. Similarly, the limit of I_{2^n}, as n -> oo, is N. Now, the power set of any set X is 2^X, and in particular 2^{I_n} is equipollent with 2^{2^n}. As we learn in Calculus, exponentiation is continuous, so it commutes with taking limits. Therefore 2^N = 2^{limit of I_n as n -> oo} = limit of 2^{I_n} as n -> oo is equipollent to the limit of I^{2^n} as n-> oo, which is N. Howzat? Lee Rudolph === Subject: : Re: power set cardinality? >>What other proof that the power set of N is countable have you seen? >>Just curious. >Let I_n denote {1,2,...,n}. Clearly (as has already been >discussed in some recent thread, possibly this one) the limit >of I_n, as n -> oo, is N. Similarly, the limit of I_{2^n}, as >n -> oo, is N. Now, the power set of any set X is 2^X, and >in particular 2^{I_n} is equipollent with 2^{2^n}. As we >learn in Calculus, exponentiation is continuous, so it commutes >with taking limits. Therefore > 2^N = 2^{limit of I_n as n -> oo} > = limit of 2^{I_n} as n -> oo >is equipollent to the limit of I^{2^n} as n-> oo, which is N. >Howzat? That's one I'd forgotten. One might regard it as a more sophisticated version of the just-count-finite subsets, of course. >Lee Rudolph ************************ David C. Ullrich === Subject: : Re: power set cardinality? >> And if so, where is the error in the construction of the countable >> list of such power set found here: >> http://descmath.com/diag/power.html > One doesn't have time to debunk all the false sites on the Net. >>Surely not, but I was able to predict where the error lay without looking >>at the argument. >Well, that's easy. Question is, was your prediction accurate? (-: My prediction is that yes it was. >= = >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 ************************ David C. Ullrich === Subject: : Re: power set cardinality? : My apologies for not trawling the newsgroup enough to find a likely : answer to this query.. it is likely here somewhere due to the high : google rating oif the site in question and high amount of transfinite : set discussion I have been happily reading. : I seem to remember hearing a theorem that the power set of a set is : always larger, even for transfinite sets.. : i.e. the power set of the integers must be uncountable. : Is this true? : And if so, where is the error in the construction of the countable : list of such power set found here: : http://descmath.com/diag/power.html : ? : Thanks - lukas saul Your list only includes finite subsets of integers. The set of all even integers will never appear in your list. Stephen === Subject: : Re: power set cardinality? Visiting Assistant Professor at the University of Montana. >My apologies for not trawling the newsgroup enough to find a likely >answer to this query.. it is likely here somewhere due to the high >google rating oif the site in question and high amount of transfinite >set discussion I have been happily reading. >I seem to remember hearing a theorem that the power set of a set is >always larger, even for transfinite sets.. >i.e. the power set of the integers must be uncountable. >Is this true? Yes. For any set A, the cardinality of P(A) is strictly larger than the cardinality of A. This is called Cantor's Theorem, in case you want to go look for it. >And if so, where is the error in the construction of the countable >list of such power set found here: >http://descmath.com/diag/power.html >? He is enumerating the collection of all FINITE subsets of the integers. These are indeed known to be countable. In his enumeration, however, the set of all even integers never shows up, and neither does the set of all primes, etc. In a sense, these are the ones that blow up the cardinality. For any infinite set A, the set of all finite subsets of A has the same cardinality as A (assuming the Axiom of Choice, anyway). The collection of all finite subsets of the integers is countable. But the collection of all infinite subsets of the integers is uncountable. == == Arturo Magidin magidin@math.berkeley.edu === Subject: : Re: power set cardinality? My apologies for not trawling the newsgroup enough to find a likely >answer to this query.. it is likely here somewhere due to the high >google rating oif the site in question and high amount of transfinite >set discussion I have been happily reading. I seem to remember hearing a theorem that the power set of a set is >always larger, even for transfinite sets.. i.e. the power set of the integers must be uncountable. Is this true? Yes. For any set A, the cardinality of P(A) is strictly larger than > the cardinality of A. This is called Cantor's Theorem, in case you > want to go look for it. And if so, where is the error in the construction of the countable >list of such power set found here: http://descmath.com/diag/power.html ? He is enumerating the collection of all FINITE subsets of the > integers. These are indeed known to be countable. In his enumeration, > however, the set of all even integers never shows up, and neither does > the set of all primes, etc. In a sense, these are the ones that blow up the cardinality. For any > infinite set A, the set of all finite subsets of A has the same > cardinality as A (assuming the Axiom of Choice, anyway). The collection of all finite subsets of the integers is countable. But > the collection of all infinite subsets of the integers is uncountable. == > 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 Thanks to Arturo and Stephen for pointing out the missing sets from that list. It looks like that list contains the set of the first N even integers, where N is as high as I want. I suppose my error is in comparing set theory to real number theory, where that type of convergence is considered equality (definition of convergence). In other words, you probably agree that lim(n-->inf)1/n = 0 because for every eps>0 I can find an n such that 1/n is less than eps. However, you don't agree that lim (n-->inf) {even_i, even_i+1..., even_n} = {all even integers}, even though for every even integer I can find an n such that it is on the list. Am I on the right track? Thanks - luke === Subject: : Re: power set cardinality? >>My apologies for not trawling the newsgroup enough to find a likely >>answer to this query.. it is likely here somewhere due to the high >>google rating oif the site in question and high amount of transfinite >>set discussion I have been happily reading. >>I seem to remember hearing a theorem that the power set of a set is >>always larger, even for transfinite sets.. >>i.e. the power set of the integers must be uncountable. >>Is this true? >> Yes. For any set A, the cardinality of P(A) is strictly larger than >> the cardinality of A. This is called Cantor's Theorem, in case you >> want to go look for it. >>And if so, where is the error in the construction of the countable >>list of such power set found here: >>http://descmath.com/diag/power.html >>? >> He is enumerating the collection of all FINITE subsets of the >> integers. These are indeed known to be countable. In his enumeration, >> however, the set of all even integers never shows up, and neither does >> the set of all primes, etc. >> In a sense, these are the ones that blow up the cardinality. For any >> infinite set A, the set of all finite subsets of A has the same >> cardinality as A (assuming the Axiom of Choice, anyway). >> The collection of all finite subsets of the integers is countable. But >> the collection of all infinite subsets of the integers is uncountable. >> == == >> Arturo Magidin >> magidin@math.berkeley.edu >Thanks to Arturo and Stephen for pointing out the missing sets from >that list. It looks like that list contains the set of the first N >even integers, where N is as high as I want. I suppose my error is in >comparing set theory to real number theory, where that type of >convergence is considered equality (definition of convergence). >In other words, you probably agree that lim(n-->inf)1/n = 0 because >for every eps>0 I can find an n such that 1/n is less than eps. >However, you don't agree that lim (n-->inf) {even_i, even_i+1..., >even_n} = {all even integers}, even though for every even integer I >can find an n such that it is on the list. >Am I on the right track? No, you're missing something very important. It is true that (if we insert suitable definitions) then the limit as n -> infinity of the set of the first n even numbers is the set of all even numbers. What you're missing is that this is simply _irrelevant_ : the fact that the set of even numbers is a limit of sets that appear on the list does not show that the set of even numbers itself appears on the list. Just like the fact that 1/n -> 0 does not imply that the sequence 1, 1/2, 1/3, ... actually includes the number 0 at some point. It doesn't. >Thanks - luke ************************ David C. Ullrich === Subject: : Re: power set cardinality? Thanks to Arturo and Stephen for pointing out the missing sets from > that list. It looks like that list contains the set of the first N > even integers, where N is as high as I want. I suppose my error is in > comparing set theory to real number theory, where that type of > convergence is considered equality (definition of convergence). In other words, you probably agree that lim(n-->inf)1/n = 0 because > for every eps>0 I can find an n such that 1/n is less than eps. However, you don't agree that lim (n-->inf) {even_i, even_i+1..., > even_n} = {all even integers}, even though for every even integer I > can find an n such that it is on the list. Am I on the right track? Thanks - luke One can create a definition of limits of sets such that lim (n-->inf) {2, 4, ..., 2n} = {all even integers}. However this would not be relevant to the question of countability. To see this, note that there are countably many rationals, and every real number is the limit of a sequence of rationals, yet there are uncountably many real numbers. -- Stephen Montgomery-Smith stephen@math.missouri.edu http://www.math.missouri.edu/~stephen === Subject: : Re: power set cardinality? Visiting Assistant Professor at the University of Montana. >>And if so, where is the error in the construction of the countable >>list of such power set found here: >>http://descmath.com/diag/power.html >>? >> He is enumerating the collection of all FINITE subsets of the >> integers. These are indeed known to be countable. In his enumeration, >> however, the set of all even integers never shows up, and neither does >> the set of all primes, etc. >> In a sense, these are the ones that blow up the cardinality. For any >> infinite set A, the set of all finite subsets of A has the same >> cardinality as A (assuming the Axiom of Choice, anyway). >> The collection of all finite subsets of the integers is countable. But >> the collection of all infinite subsets of the integers is uncountable. >Thanks to Arturo and Stephen for pointing out the missing sets from >that list. It looks like that list contains the set of the first N >even integers, where N is as high as I want. I suppose my error is in >comparing set theory to real number theory, where that type of >convergence is considered equality (definition of convergence). Oh, dear. Don't use real number theory. Number Theory has a very precise meaning, and it is not the one you are talking about. >In other words, you probably agree that lim(n-->inf)1/n = 0 because >for every eps>0 I can find an n such that 1/n is less than eps. Because that's what the definition of convergence is for this context. >However, you don't agree that lim (n-->inf) {even_i, even_i+1..., >even_n} = {all even integers}, even though for every even integer I >can find an n such that it is on the list. I assume you mean something line the limit, as n goes to infinity, of {0, 2, 4, 6, ..., 2n} is the set {0, 2, 4, 6, ...,} of all even integers. If you interpret the notions correctly, then the answer is that it IS true: you interpret the limit as taking the ascending union of the sets. That is, let A_n = {0, 2, ..., 2n}, and then limit as n goes to infinity means the union of A_1, A_2, ... etc. But you have a similar phenomenon occurring in both cases. Even though the limit as n goes to infinity of 1/n is equal to 0, IT IS NOT THE CASE that there is an n such that 1/n=0. Likewise, even though the limit of these finite sets is an infinite set, it is not the case that at any finite step you have an infinite set. When you are ennumerating, however, you only cover the FINITE cases. You never get to the limit. That's what ennumerating means. == == Arturo Magidin magidin@math.berkeley.edu === Subject: : Re: power set cardinality? >And if so, where is the error in the construction of the countable >>list of such power set found here: >>http://descmath.com/diag/power.html >>? >> He is enumerating the collection of all FINITE subsets of the >> integers. These are indeed known to be countable. In his enumeration, >> however, the set of all even integers never shows up, and neither does >> the set of all primes, etc. >> In a sense, these are the ones that blow up the cardinality. For any >> infinite set A, the set of all finite subsets of A has the same >> cardinality as A (assuming the Axiom of Choice, anyway). >> The collection of all finite subsets of the integers is countable. But >> the collection of all infinite subsets of the integers is uncountable. Thanks to Arturo and Stephen for pointing out the missing sets from >that list. It looks like that list contains the set of the first N >even integers, where N is as high as I want. I suppose my error is in >comparing set theory to real number theory, where that type of >convergence is considered equality (definition of convergence). > Oh, dear. Don't use real number theory. Number Theory has a very > precise meaning, and it is not the one you are talking about. Sorry, mistake noted. In other words, you probably agree that lim(n-->inf)1/n = 0 because >for every eps>0 I can find an n such that 1/n is less than eps. Because that's what the definition of convergence is for this > context. >However, you don't agree that lim (n-->inf) {even_i, even_i+1..., >even_n} = {all even integers}, even though for every even integer I >can find an n such that it is on the list. I assume you mean something line the limit, as n goes to infinity, of {0, 2, 4, 6, ..., 2n} is the set {0, 2, 4, 6, ...,} of all even integers. If you interpret the notions correctly, then the answer is that it IS > true: you interpret the limit as taking the ascending union of the > sets. That is, let A_n = {0, 2, ..., 2n}, and then limit as n goes to > infinity means the union of A_1, A_2, ... etc. Thank you for correcting (and understanding) my horrendous notation :) > But you have a similar phenomenon occurring in both cases. Even though > the limit as n goes to infinity of 1/n is equal to 0, IT IS NOT THE > CASE that there is an n such that 1/n=0. > I see your point. So, the set {1/1,1/2,1/3...} does not contain the number 0, whereas the sequence 1/1,1/2,1/3 does converge to zero. > Likewise, even though the limit of these finite sets is an infinite > set, it is not the case that at any finite step you have an infinite > set. When you are ennumerating, however, you only cover the FINITE > cases. You never get to the limit. That's what ennumerating means. this helps a lot! > == > 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: : Re: Four Color Theorem Simplified Here's my revised list!! > SOME THINGS YOU NEED TO KNOW ABOUT THE FOUR COLOR THEOREM!!! DEFINITIONS: > CHI(G) is the chromatic number of graph G. > If CHI(G) <= k, then graph G is k-colorable > If CHI(G) = k, then graph G is k-chroma. A graph is planar if it contains no subgraph homeomorphic to > K5 or K3,3. Every maximal planar graph [MPG] has exactly 3n-6 edges. If every MPG is 4-colorable; then every planar graph is 4-colorable. All MPG's are generated by the intersection of two triangulations of an > n-sided polygon. Every triangulation of every convex polygon is 3-colorable. All 4-partite graphs, both planar and non-planar, are 4-colorable. Note that I have removed the statement about the reduction of 5-chroma graphs. I feel that the 'list' is now incomplete and that there are more things you need to know about the four color theorem! Amybody have any suggestions? Does anyone disagree with any of the items in the list? Bill J. === Subject: : Re: Four Color Theorem Simplified > ALL YOU NEED TO KNOW ABOUT THE FOUR COLOR THEOREM!!! DEFINITIONS: > CHI(G) is the chromatic number of graph G. > If CHI(G) <= k, then graph G is k-colorable > If CHI(G) = k, then graph G is k-chroma. A graph is planar if it contains no subgraph homeomorphic to > K5 or K3,3. Every maximal planar graph [MPG] has exactly 3n-6 edges. If every MPG is 4-colorable; then every planar graph is 4-colorable. All MPG's are generated by the intersection of two triangulations of an > n-sided polygon. Every triangulation of every convex polygon is 3-colorable. Every 5-colorable graph has a subgraph homeomorphic to the complete graph K5. All 4-partite graphs, both planar and non-planar, are 4-colorable. > How about; Every 5-chroma 'non planar' graph has a subgraph > homeomorphic (or is it 'isomorphic') to the complete graph K5.? Is > this a valid statement? > regards, Bill Despite the usage of is homeomorphic to elsewhere in math to denote an equivalence relation, it has a specialized meaning in graph theory. Graph A is homeomorphic to graph B, if by a sequence of edge deletions and coalescence of vertices, graph B can be obtained from graph A. Isomorphism of graphs is an equivalence relation, but homeomorphism in this sense is not. The statement: Every 5-chroma graph has a subgraph homeomorphic to the complete graph K5. is plausible, but I don't know how to prove it. See also my partial retraction and comment under the other branch of this thread. regards, chip === Subject: : Re: Four Color Theorem Simplified > ALL YOU NEED TO KNOW ABOUT THE FOUR COLOR THEOREM!!! > Every 5-colorable graph has a subgraph homeomorphic to the complete > graph > K5. > Your pentultimate statement is clearly wrong. regards, chip Thar's penultimate! Anyway, what is the smallest n for which it is > not true? An example, please? regards, bill > Thanks for the spelling correction, Bill. > You give no special definitions of terms, so presumably your usage is > standard for treatments of the four-color problem. > In standard parlance, four-colorable implies five-colorable, so a trivial > example (e.g. of a planar graph) may be adduced. > Even granting that you intended five-colorable in a stronger sense of > five- but not four-colorable, the statement would still be incorrect. > Here is an example which may be drawn on the surface of a torus. > Imagine three circles running parallel around the hole in a doughnut. > Subdivide one of the resulting three regions so obtained with five segments > cutting perpendicularly across that region. > The map now has 7 regions, lacks any embedded subgraph K5, and is > five-colorable but not four-colorable. > Your question about the smallest n is interesting. Obviously if there were > a map with 5 regions that was five- but not four-colorable, as a graph it > would be (isomorphic to) K5 (the complete graph on 5 vertices). Is there a > counterexample with n=6? I suspect not, but apart from an exhaustive > examination of cases, I cannot think off-hand of an approach to showing > this. > Perhaps you will have better insight. > regards, chip I must retract my last counter-example. It actually does have a subgraph homeomorphic to K5. Delete the edges between any two adjacent pairs of the five subdivided regions, thus combining each pair into a single region. The resulting graph is isomorphic to K5. Actually by saying non-planar we are already (Kuratowski's theorem) implying that the graph contains either a subgraph homeomorphic to K5 or to K3,3, and of course given the four-color theorem, any five-chroma graph would necessarily be non-planar. regards, chip === Subject: : On singular value decomposition Say the singular value decomposition of a N-by-N matrix A is, A=USV', where S=diag{s11, ... , sNN}. Take S(A), U(A) and V(A) as functions of A. Is there any stable algorithm such that S(A), U(A), V(A) are continous in A? ie. Say for every epsilon > 0, if |norm(E)| < epsilon, then there exist delta such that |norm(U(A+E)-U(A)| < delta, |norm(S(A+E)-S(A)| < delta, |norm(V(A+E)-V(A)| < delta. Bernard === Subject: : Re: On singular value decomposition > Say the singular value decomposition of a N-by-N matrix A is, A=USV', where > S=diag{s11, ... , sNN}. Take S(A), U(A) and V(A) as functions of A. Is there > any stable algorithm such that S(A), U(A), V(A) are continous in A? No. Consider the sequence: / 1/n 1/n A_n = | | if n odd 1/n 1/n / / 1/n 0 = | | if n even 0 1/n / This converges to 0, but U(A_n) toggles between: / -t -t / 0 1 | | and | | -t t / 1 0 / (for t=1/sqrt(2)) as does V(A_n). -- === Subject: : Re: On singular value decomposition >Say the singular value decomposition of a N-by-N matrix A is, A=USV', where >S=diag{s11, ... , sNN}. Take S(A), U(A) and V(A) as functions of A. Is there >any stable algorithm such that S(A), U(A), V(A) are continous in A? >ie. Say for every epsilon > 0, if |norm(E)| < epsilon, then there exist >delta such that |norm(U(A+E)-U(A)| < delta, |norm(S(A+E)-S(A)| < delta, >|norm(V(A+E)-V(A)| < delta. It can be done for S(A), as the sii can be taken to be the non-negative square roots of the characteristic values of AA'. However, it cannot be done in general for U(A) and V(A) if AA' has multiple characteristic roots. For example, it fails for A = I, as changing a_ij and a_ji to be a small non-zero number for i != j, and making no other changes, causes U(A) and V(A) to have magnitude sqrt(.5) for the elements in the i-th and j-th rows and columns. -- 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: Collatz (3x+1) as diophantine problem Can't offer constructive feedback; I'm sorry. But I find it > interesting to study. Hi Ernst - short explanation. One transformation of Collatz, starting at an odd integer x0 > and going to the next odd integer x1 can be written as > I am working your equations and so far it looks right to me. I wanted to let you know I was still chatting with you about it. Ernst === Subject: : Re: Collatz (3x+1) as diophantine problem > === Subject: : Re: Collatz (3x+1) as diophantine problem >Message-id: Can't offer constructive feedback; I'm sorry. But I find it >> interesting to study. >> Hi Ernst - >> short explanation. >> One transformation of Collatz, starting at an odd integer x0 >> and going to the next odd integer x1 can be written as > I am working your equations and so far it looks right to me. Hey Ernst, did you notice that GH's equations are the same as my Crossover Point formula? All GH has to do is multiply his equation by C to have a general formula for 3x+C. I thought something was wrong because his numerator differed from mine for the same sequence. But I studied it all weekend and finally realized that he derived his formulae by using the normal Collatz rules in going from x0 to x1 whereas I derived mine by using inverse rules going from x1 to x0. Also, his power of 2 exponents in the numerator are, for a,b,c c+b c whereas I put a,b,c into an array z[] and compute the exponents by e[0] = sum(z[]) - z[0] e[1] = e[0] - z[1] e[2] = e[1] - z[2] but in looking at this, I realized that sum(z[]) - z[0] is c+b+a - a or simply c+b which makes e[0] - z[1] c+b - b or simply c. And finally e[1] - z[2] is c - c or 0. That makes my list of exponents c+b c 0 Note that GH doesn't show 2^0 because that's simply 1. But from the programming aspect, it's better to have a rule without exceptions, so 0 exponents should always be shown for consistency. He got his the easy way, I got mine the hard way. The important thing is that we both arrived at the same place. Truth is not dependant on the pathway to it. His numbers were different because although a,b,c b,c,a c,a,b give different equations with different exponents, they are all the same loop. So GH will probably give you a more rigorous mathematical treatment, but my seat of the pants reults are still correct. > I wanted to let you know I was still chatting with you about it. Ernst -- Mensanator 2 of Clubs http://members.aol.com/mensanator666/2ofclubs/2ofclubs.htm === Subject: : Re: Collatz (3x+1) as diophantine problem X-ID: V3oWEkZbgeEe2ZS3WM5xlmIfA4PYPtQ15g8pc4QSl1+o+Eks-baasJ Hi Mensanator - my Crossover Point formula? All GH has to do is multiply his > equation by C to have a general formula for 3x+C. is that really all? I didn't look at these points yet... I thought something was wrong because his numerator differed > from mine for the same sequence. But I studied it all weekend > and finally realized that he derived his formulae by using the > normal Collatz rules in going from x0 to x1 whereas I derived > mine by using inverse rules going from x1 to x0. Yes, that was also my original approach. But I thought: all people look along this direction... and it does not really make a difference at this point. One amazing thing was, that the formula for the loop is exactly the same - viewing it in this or that direction. Note that GH doesn't show 2^0 because that's simply 1. Yes, I thought to deal only with odds. This also selects the used Collatz-numbers to these with a last index of 0 C(X;a,b,c,...,0) (in my notation) and flattens the equations > But > from the programming aspect, it's better to have a rule without > exceptions, so 0 exponents should always be shown for > consistency. Right. He got his the easy way, Well well... I had several days with excessive playing around since the grammabeautiful-start - but when it came to this simple idea... that was nearly a shame... > I got mine the hard way. And also more continuously, I must say (and appreciate). But still it needs the final argument, that the base(2/3)- digits can not be converted to a integer multiple of a repunit, if they are not all equal at start. Maybe again this comes out to be much more simple than I thought in a first try. Since the digits can only be powers of 2 (or some fixed derivate of 2/3) - and the flattening of such a digitnumber, which comprises the carry-overs from one digit to another, could be simply impossible if base and integer-property of digits are not compatible. The more general question, seen of the generating view of the collatz-transformation: can all natural numbers be created by the inverse-collatz-transformation, starting by 1, can be attacked by the same formula. The behaving of the numbers can be much instructively be studied displaying them in binary then. I think, that is then another path to arrive at the bit-pattern-subject, that you mentioned here many times. GH (Gottfried) -------------------------------------------------------------- -- Gottfried Helms Univ Kassel === Subject: : Re: Collatz (3x+1) as diophantine problem > Hi Mensanator - > my Crossover Point formula? All GH has to do is multiply his > equation by C to have a general formula for 3x+C. is that really all? I didn't look at these points yet... > You have n-1 n-2 z n-3 z+y 1 z+y+...+c z+...c+b 3 + 3 2 + 3 2 + ... + 3 2 + 2 x = --------------------------------------------------------------- z+...+c+b+a n 2 - 3 My Crossover Point formula for a 3x+C system is Z * C CO = -------- X - Y where my Z term is your entire numerator (our denominators are the same). For the standard 3x+1 system, our formulae are identical and the only way we can get an integer is if all the factors of X-Y can be cancelled by the factors of Z. When C>1, C and Z can work together (provided that C is not a power of 3, otherwise it will not cancel ANY factors in the denominator because X-Y can never have a factor of 3). Thus, systems like 3x+5 have many loops in the positive integers aside from the trivial one at C. I don't know if you saw this in another thread, so I'll repeat it here. If the Crossover Point is an integer, then there is a loop. For EVERY possible sequence, a 3x+C system exists in which that sequence is a loop. Take an extreme example ag_af ae ad ac_ab aa z y x w v u_t s r q p o n m_l k_j i h g f_e d c_b a the Crossover Point works out to be 35343985 * C -------------- 33552245 which factors to 5 * 23 * 307339 * C --------------------- 5 * 6710449 which reduces to 7068797 * C ------------- 6710449 So the system 3x+6710449 has a loop at 7068797, which is easily verified 7068797 27916840 13958420 6979210 3489605 17179264 8589632 4294816 2147408 1073704 536852 268426 134213 7113088 3556544 1778272 889136 444568 222284 111142 55571 6877162 3438581 17026192 8513096 4256548 2128274 1064137 9902860 4951430 2475715 14137594 7068797 === Subject: : Re: Collatz (3x+1) as diophantine problem X-ID: EBUZSgZrgecIcFMxpCFFawmRjo7nrSpc62MWFDv9bGg9IdyGxXOKwG ehhm, I just put two unfinished manuscripts on my server. The first, which shows a wonderful fractal tree resulting from my version of indexing the collatz-numbers http://141.51.96.22/priv/math/collatz/A_nice_fractal.htm The second a manuscript, which was the start for the current loop-attack: with some more explanations: http://141.51.96.22/priv/math/collatz/A_simplificating.htm Also a deeper view in the generation tree is this (excel-generated) image: http://141.51.96.22/priv/math/collatz/generatinglist.htm ---------------------------- Besides of giving more explanations and thoughts for discussion it's just stuff coming from stumbling on a bifurcated way... > He got his the easy way, Gottfried === Subject: : Re: Collatz (3x+1) as diophantine problem http://141.51.96.22/priv/math/collatz/A_nice_fractal.htm ---------------------------- Sorry, I'm not able to create html being readable by netscape 4 (and possibly other newsreaders) with the microsoft-version of html-generation from its word-files. Since I have written my text in this format i'm stuck now and the html-versions are partly garbage (for instance, exponents come out as indexes) So to be able to read it properly I present them as *.pdf-versions too. > http://141.51.96.22/priv/math/collatz/A_nice_fractal.pdf > http://141.51.96.22/priv/math/collatz/A_simplificating.pdf GH == === Subject: : primecounter X-ID: SAibqYZZre89a2AhnpI2yUGlQO44-yMwklKuVEH+QEUAcLaTWOXMUB should be quite fast... 4,000,000,000 in 0.25 sek. hoping i'm not too late... #define Number unsigned long #define PrimeTableSize 8192 #define NSize 8192 #define PSize 16 #define Empty 0xFFFFFFFF Number Value = 4000000000; Number Primes[PrimeTableSize]; Number Cache[NSize][PSize]; Number Kick(Number n, Number p, Number Max) { Number i, p2, NewN, Res; NewN = n / p; Res = NewN; for (i = 1; i NewN) {Res-=Max - i; break;} if ((NewNR such that g(x) = f(f(x))= x^2 - 1996. I thought of considering fixed points, specifically the fact that if f is differentiable and a is a fixed point of f, then g(a) = f(a)^2 and g(a)>=0. But this didnt work and, anyway, nothing assures that, if the function f existed, it had to be differentiable. The number 1996 appears cause this problem is from 1996, but I dont know if the conclusion can be generalized to f(f(x))= x^2 - m, m>0. Any suggestion is welcome. Artur === Subject: : Re: A help with f(f(x)=x^2 - 1996 >Hello everybody >I'm trying to show that there's no function f:R->R such that g(x) = >f(f(x))= x^2 - 1996. I thought of considering fixed points, >specifically the fact that if f is differentiable and a is a fixed >point of f, then g(a) = f(a)^2 and g(a)>=0. But this didnt work and, >anyway, nothing assures that, if the function f existed, it had to be >differentiable. >The number 1996 appears cause this problem is from 1996, but I dont >know if the conclusion can be generalized to f(f(x))= x^2 - m, m>0. You don't need differentiability, or even continuity. g(x) = x^2 - m has two fixed points, (1(+/-)sqrt(1+4m))/2, if m > -1/4. In addition, g has a single two-cycle (-1(+/-) sqrt(-3+4m))/2, if m > 3/4. Let these points be b_1 and b_2: g(b_1) = b_2 and g(b_2) = b_1. If g(x) = f(f(x)), then [b_1, f(b_1), b_2, f(b_2)] must form a four-cycle for f (and these four points must be distinct, otherwise [b_1, b_2] couldn't be a two-cycle for g). But then [f(b_1), f(b_2)] would be another two-cycle for g, and there can't be any more. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 === Subject: : Re: A help with f(f(x)=x^2 - 1996 Mr. Israel, Could you kindly suggest to me a good textbook for the study of functional equations? >Hello everybody >I'm trying to show that there's no function f:R->R such that g(x) = >f(f(x))= x^2 - 1996. I thought of considering fixed points, >specifically the fact that if f is differentiable and a is a fixed >point of f, then g(a) = f(a)^2 and g(a)>=0. But this didnt work and, >anyway, nothing assures that, if the function f existed, it had to be >differentiable. >The number 1996 appears cause this problem is from 1996, but I dont >know if the conclusion can be generalized to f(f(x))= x^2 - m, m>0. > You don't need differentiability, or even continuity. > g(x) = x^2 - m has two fixed points, (1(+/-)sqrt(1+4m))/2, if m > -1/4. > In addition, g has a single two-cycle (-1(+/-) sqrt(-3+4m))/2, if m > 3/4. > Let these points be b_1 and b_2: g(b_1) = b_2 and g(b_2) = b_1. > If g(x) = f(f(x)), then [b_1, f(b_1), b_2, f(b_2)] must form a four-cycle > for f (and these four points must be distinct, otherwise [b_1, b_2] > couldn't be a two-cycle for g). But then [f(b_1), f(b_2)] would be > another two-cycle for g, and there can't be any more. > Robert Israel israel@math.ubc.ca > Department of Mathematics http://www.math.ubc.ca/~israel > University of British Columbia > Vancouver, BC, Canada V6T 1Z2 === Subject: : looking for counterexample I'm trying to find a counterexample showing that the hypothesis |E| < infty is necessary in the following: Thm: let f_k, g_k:E->R be measurable functions finite a.e. in E subset R, with E of _finite measure_ such that f_k -> f in measure and g_k -> g in measure. Show that g_k f_k -> gf in measure. Any ideas? TIA, nojb. === Subject: : Re: looking for counterexample >I'm trying to find a counterexample showing that the hypothesis |E| < >infty is necessary in the following: >Thm: let f_k, g_k:E->R be measurable functions finite a.e. in E >subset R, with E of _finite measure_ such that f_k -> f in measure >and g_k -> g in measure. Show that g_k f_k -> gf in measure. >Any ideas? E = R, g_k(x) = f_k(x) = x + 1/k. >TIA, >nojb. ************************ David C. Ullrich === Subject: : A tight bound on Union by Rank with Path Compression Hello. I'd like to know whether the m*alpha(n) upper bound on this algorithm is tight (where alpha is the inverse of something similiar to Ackerman's function as defined in CLRS - Introduction to Algorithms). If not, what is the tight bound? Thanks in advance, Oren Becker. === Subject: : total derivative and partial derivative Hi I'm reading through some maths and they've written something like this: Given F = F(x,y,z) and y=y(x) and z=z(x) dF/dx = del/delx*F + del/dely*F*y' + del/delz*F*z' What's the rule that lets you say that? I know that you can say the following: dF = delF/delx*dx + delF/dely*dy + delF/delz*dz And I think they used the above rule to compute dF/dx. Is that right? By writing this I've answered my own question - hmmm interesting. === Subject: : Re: total derivative and partial derivative > I'm reading through some maths and they've written something like this: > Given F = F(x,y,z) and y=y(x) and z=z(x) > dF/dx = del/delx*F + del/dely*F*y' + del/delz*F*z' > What's the rule that lets you say that? I know that you can say the > following: > dF = delF/delx*dx + delF/dely*dy + delF/delz*dz Chain rule. === Subject: : Re: Any idea for a math career? Digital motion picture visual effects. It's a natural step for a mathematician to make. Much of mathematics was invented, in the first place, to render accurate images. There is scope for dynamics, rigid-body dynamics), inverse problems (photogrammetry, match-moving, inverse rendering, inverse dynamics) and image processing. You regularly use linear alagebra, multivariate calculus, optimisation, ODE and PDE solving techniques, FFTs, statistics and sampling theory, monte-carlo interation methods and I even found an application for a tiny bit of commutative algebra (which I hope to publish soon). And I'm just talking about what I do. My colleagues do a whole lot of other stuff... -- Torque === Subject: : Re: Discrete Math => K!>K^2 Proof I'm looking for a website that runs through the proof of this problem. If you can help me out, email me at shodan3510@yahoo.co m Thanks! Alainna It's not true for *all* positive integers k, since 1! = 1^2, 2! < 2^2 and 3! < 3^2. It _is_ true for k = 4, since 4! = 24 and 4^2 = 16. And ... once it's true for some value of k, then it's true for all larger values. Basically, you have that (k+1)! = (k+1) k! > (1 + (1/k))^2 k! > (k+1)^2 if k! > k^2 and k > 1. The first inequality follows from the fact that (k+1) > (1 + (1/k))^2 if k > 1 and the second from the assumption that k! > k^2. Altogether, then, this argument proves that k! > k^2 if k > 3. (Oh ... that other inequality follows from the fact that it's obviously true if k = 2 and increasing k makes the LHS of the inequality bigger while it _decreases_ the RHS ... ) === Subject: : okamoto/kashima on P vs NP unprovability fyi, this new 42 pg paper appears on superficial glance to be a very major tour-de-force result that P vs NP is in some sense difficult to prove. apparently building on some of the conjectures in razborov/rudich's natural proofs. the authors use a complex godelian type diagonalization construction. the primary author has a very distinguished record in cryptography theory. http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/o/ Okamoto:Tatsuaki .html here is kashima's (coauthors) publications which focus more on proof theory http://www.is.titech.ac.jp/~kashima/ I would like to invite all serious comment at http://groups.yahoo.com/group/theory-edge/ where I have also just extended an email invitation to the authors. posts out here to comp.theory are fine of course but note that a mailing list dialogue can be a little better/quickly synchronized among interested participants. > Resource Bounded Unprovability of Computational Lower Bounds Tatsuaki Okamoto and Ryo Kashima === Subject: : Sphere-Triangle Intersection Related Geometry Question Given the two intersection points of an intersected edge of the triangle, and information as to which edge was intersected, is there a way to procedurally generate triangles for any variant of initial triangle and sphere such that only one edge of each triangle is in contact with the sphere. The problem can be regarded as a 2D problem as it is possible to move the centre of the sphere to the plane of the triangle and calculate the new radius. An example of a solution to a similar problem would be a sphere triangle intersection with 0 edges intersected and 0 vertices intersected. / / o /____ By taking the closest point to the centre of the circle from each line three new points are generated. By finding the intersections from lines taken from each of these points to the centre of the circle the points are then moved to the surface of the sphere. 6 Triangles are then created, 3 with one vertex touching the sphere, 3 with two vertices touching the sphere. The important detail being those triangles with two vertices touching the sphere have one edge in intersected by the sphere (through the triangles vertices). === Subject: : Combinatorial/Probability Problem I am trying to evaluate the following sum: Sum from m= 5 to infinity [ m*Binomial[m-1,4] p^5 q^(m-5)] where p = 1-q = 1/36 and Binomial[a,b] is the binomial coefficient a choose b (This is the expectation value for the number of dice throws one needs to make until obtaining 5 pairs of sixes) Matematica tells me that for large m, this summation is a neat 180, but I can't see how to obtain this result analytically. TIA, Matthew T. Brenneman === Subject: : Re: Combinatorial/Probability Problem >I am trying to evaluate the following sum: >Sum from m= 5 to infinity [ m*Binomial[m-1,4] p^5 q^(m-5)] >where p = 1-q = 1/36 and Binomial[a,b] is the binomial coefficient a >choose b >Matematica tells me that for large m, this summation is a neat 180, but I >can't see how to obtain this result analytically. More generally, consider S_n = sum_{m=n}^infinity m Binomial[m-1, n-1] p^n q^(m-n). = sum_{m=n}^infinity n Binomial[m,n] p^n q^(m-n) The generating function with respect to n is g(z) = sum_{n=1}^infinity S_n z^n = sum_{n=1}^infinity sum_{m=n}^infinity n Binomial[m,n] p^n q^(m-n) z^n = sum_{m=1}^infinity sum_{n=0}^m n Binomial[m,n] q^m (zp/q)^n = sum_{m=1}^infinity q^m (1+zp/q)^(m-1) zpm/q = zp/(1-zp-q)^2 = z/(p(1-z)^2) = sum_{n=1}^infinity n z^n/p So S_n = n/p. And in particular for n=5, p=1/36 we get 180. Or a probabilistic proof: if X is the number of the trial on which the n'th success occurs, S_n is the expected value of X. Now X = X_1 + X_2 + ... + X_n, where X_1 is the number of trials until the first success, and X_i for i > 1 is the number of trials from the (i-1)th success until the ith. Each X_i has a geometric distribution with parameter p, and E[X_i] = 1/p. So E[X] = sum_{i=1}^n E[X_i] = n/p. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 === Subject: : Re: Combinatorial/Probability Problem > I am trying to evaluate the following sum: > Sum from m= 5 to infinity [ m*Binomial[m-1,4] p^5 q^(m-5)] > where p = 1-q = 1/36 and Binomial[a,b] is the binomial coefficient > a choose b > (This is the expectation value for the number of dice throws one > needs to make until obtaining 5 pairs of sixes) That's easy. There are 6*6 outcomes throwing two dice, so the probability of a pair of sixes on a single roll is 1/36. Therefore, you will need (on average) 36 rolls to get the first pair of sixes, 36 more rolls for the second pair of sixes, and so on; 5*36 = 180. > Matematica tells me that for large m, this summation is a neat 180, > but I can't see how to obtain this result analytically. Does the problem require an analytical solution? In that case, expand (1-q)^(-6) in powers of q (using the binomial theorem or whatever) and compare that with your series. Note that m*Binomial[m-1,4] = 5*Binomial[m,5]. === Subject: : Re: Jacobi Iterativ-Verfahren ? >Wer hat die sogenannte ,,Jacobi'sche >Iterativ-Verfahren , entdeckt (1845 ?) : > -der beruehmter Deutscher Mathematiker > Carl Jacob Gustav JACOBI >oder > -Boris Semionovici JACOBI , >ein Mathematiker aus Russland ? >Bitte ein Paar Literatur Hinweise. Hallo Alex, das war Carl Gustav Jacob Jacobi: C. G. Jacobi: .86ber eine neue Aufl.9asungsart der bei der Methode der kleinsten Quadrate vorkommenden linearen Gleichungen. Astronomische Nachrichten 22 (1845). Es steht auch in seinen gesammelten Werken (7 B.8ande. Berlin: R. Reimer 1881-1891) in Band 3, S. 467-478. Die Werke sind online von der Biblioth.8fque Nationale de France, Paris lesbar http://gallica.bnf.fr --> Auteur Jacobi aber momentan ist dieser Server wegen Update-Arbeiten nur teilweise in Betrieb. Hier noch einige Referenzen: http://www.numerik.uni-kiel.de/~in/PAPER/Diplom/node43.html --> Jacobi45 http://www.cs.umd.edu/TRs/authors/C_G_Jacobi.html --> CS-TR-2877, but the full paper seems to be no more available ... Gr.9fsse Hermann -- >Danke, Alex === Subject: : Re: Jacobi Iterativ-Verfahren ? Hermann Kremer schrieb in Nachricht ... Hello Alex, some additional informations. >>Wer hat die sogenannte ,,Jacobi'sche >>Iterativ-Verfahren , entdeckt (1845 ?) : >> -der beruehmter Deutscher Mathematiker >> Carl Jacob Gustav JACOBI http://www-history.mcs.st-and.ac.uk/~history/Mathematicians/ Jacobi.html Yep, he was it, see below ... >>oder >> -Boris Semionovici JACOBI , >>ein Mathematiker aus Russland ? Boris Semjonowitsch Jakobi, aka Boris Semionovich Yakobi (1801-1874), was the elder brother of Carl Gustav Jacob Jacobi; his name in German is Moritz Hermann Jacobi. In 1835 he got a chair of physics at Dorpat (now Tartu) University (Estonia), and in 1837 he moved to the Russian Academy of Sciences in St. Petersburg. http://chem.ch.huji.ac.il/~eugeniik/history/jacobi.html (at the bottom are a few links to biographies in Russian). http://hp.iitp.ru/ger/32/3284.htm http://hp.iitp.ru/ger/32/3284a.htm >>Bitte ein Paar Literatur Hinweise. C. G. Jacobi: .86ber eine neue Aufl.9asungsart der bei der Methode der kleinsten Quadrate vorkommenden linearen Gleichungen. [On a new way of solving the linear equations arising in the method of least squares]. Astronomische Nachrichten Vol. 22 (1845), Issue No. 523. It may also be found in Jacobi's Collected Works in 7 Vols. Berlin: R. Reimer 1881-1891 in Vol. 3, p. 467-478. All 7 volumes are online at the Biblioth.8fque Nationale de France in Paris: http://gallica.bnf.fr --> Recherche --> Auteur Jacobi but currently the server is partially down due to update and maintainance. Here are some more references: http://www.numerik.uni-kiel.de/~in/PAPER/Diplom/node43.html --> Jacobi45 http://www.cs.umd.edu/TRs/authors/C_G_Jacobi.html --> CS-TR-2877, but the full paper seems to be no more available ;-(( Hope that helps ... Best regards Hermann -- >>Danke, Alex === Subject: : Re: why isn't THE a quantifier? > References ACZEL, P. 1988 Non-Well-Founded Sets, CSLI, Stanford, 1988, XX?137 pp. BARWISE, J. & MOSS, L. 1996 Vicious Circles, CSLI, Stanford, 1996, X?390 > pp. > Great! How about an example or two showing how it works? [...] Do your own homework. > F. I did. I verified my recollection by pulling these documents off my bookshelf and verified that they don't contain what you maintain. What would you do if someone told you that proof of their assertion was contained in a reference which you believed does not contain such a proof? Everything you have ever posted is refuted in mathworld.com [insert your response here] Do your own homework. Cambridge, MA === Subject: : Recursive Sequence: Highest Prime Divisors If we start with two positive integers {m,n}, and let a(1) = m, a(2) = n, and we let, for k >= 3, a(k) = (highest prime dividing a(k-1)) + (highest prime dividing a(k-2)), then we get a (possibly eventually-periodic) sequence. (For example: m = 2, n = 3, leads to -> 2, 3, 5, 8, 7, 9, 10, 8, 7, 9,...) I am not at all certain, but I wonder if every {m,n} leads to a sequence that is eventually periodic. Is this so?? Obviously, if the highest primes dividing a(j) and a(j-1) are those which are the highest primes which also divide a(k) and a(k-1), respectively (for some k not = j), then the sequence is periodic. There may be something in the EIS, but the fact that {m,n} can vary makes a search not too easy, since I do not know which {m,n}-sequence is fundamental enough to be in the EIS, yet such a sequence is not trivial. Leroy Quet === Subject: : Re: Recursive Sequence: Highest Prime Divisors >If we start with two positive integers {m,n}, and let >a(1) = m, >a(2) = n, >and we let, for k >= 3, >a(k) = >(highest prime dividing a(k-1)) + >(highest prime dividing a(k-2)), >then we get a (possibly eventually-periodic) sequence. >(For example: m = 2, n = 3, leads to -2, 3, 5, 8, 7, 9, 10, 8, 7, 9,...) >I am not at all certain, but I wonder if every {m,n} leads to a >sequence that is eventually periodic. >Is this so?? >Obviously, if the highest primes dividing a(j) and a(j-1) are those >which are the highest primes which also divide a(k) and a(k-1), >respectively (for some k not = j), then the sequence is periodic. The sequence must either eventually lead to the 4-cycle [8,7,9,10] or the 1-cycle [2] or [2p] for an odd prime p. And the 1-cycle can only happen if a(1) and a(2) have the same highest prime factor. Let h(x) be the highest prime dividing x. Instead of a(n), consider the sequence p(n) = h(a(n)). Thus p(n+2) = h(p(n)+p(n+1)). We can then reconstruct (a(n)) (for n >= 2) from (p(n)) since a(n) = p(n-2) + p(n-1). For the sequence p(n) the 4-cycle is [2,7,3,5] and the 1-cycle is [p]. It seems to me that beginning with distinct primes [p(1), p(2)], by [p(5), p(6)] we reach a pair [p(i),p(i+1)] with max(p(i),p(i+1)) < max(p(1),p(2)) except in the cases [2,3], [2,5], [3,2], [3,5] and [5,2], which all lead to the 4-cycle. (I don't think I've covered all possible cases by hand, but I've done a computer search and I think this is correct) Note for example that if p(1) and p(2) are odd, p(1)+p(2) is even so p(3) <= (p(1)+p(2))/2 < max(p(1),p(2)). And then again if p(3) is odd, p(4) < max(p(2),p(3)) < max(p(1),p(2)). On the other hand, if p(3)=2 we could have p(4)= p(2)+2 (if [p(2),p(2)+2] are twin primes; this implies p(2) = 2 mod 3 unless p(2)=3), but then p(3)+p(4)=p(2)+4 is odd and divisible by 3, so 3 <= p(5) <= (p(2)+4)/3, resulting in max(p(5),p(6)) <= (2p(2)+5)/3 < max(p(1),p(2)) unless p(2) <= 5. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 === Subject: : Re: Recursive Sequence: Highest Prime Divisors >If we start with two positive integers {m,n}, and let >a(1) = m, >a(2) = n, and we let, for k >= 3, a(k) = >(highest prime dividing a(k-1)) + >(highest prime dividing a(k-2)), >then we get a (possibly eventually-periodic) sequence. (For example: m = 2, n = 3, leads to - >2, 3, 5, 8, 7, 9, 10, 8, 7, 9,...) I am not at all certain, but I wonder if every {m,n} leads to a >sequence that is eventually periodic. Is this so?? Obviously, if the highest primes dividing a(j) and a(j-1) are those >which are the highest primes which also divide a(k) and a(k-1), >respectively (for some k not = j), then the sequence is periodic. The sequence must either eventually lead to the 4-cycle > [8,7,9,10] or the 1-cycle [2] or [2p] for an odd prime p. > And the 1-cycle can only happen if a(1) and a(2) have the same > highest prime factor. ....(Robert's proof snipped) I have also unrigorously proved this myself this morning. But my proof is probably flawed someplace. I am glad to see the result confirmed. I too apparently deduced that, if m and n have both the same highest-prime-divisor, then the sequence has a period of 1, at least from the 3rd term on. Otherwise, all other {m,n} lead eventually to the period-4 sequence of {8,7,9,10} repeating. (I have seen a few others' proofs of this result. Each of these proofs varies somewhat and is interesting.) Leroy Quet === Subject: : Multiple Sum of...Divisible by... Let m and n be positive integers. Let {a(k)} be any integer sequence. Two related results, the last more general than the first: Let B_m(k/n) = --- / a(j) --- GCD(j,m)=1 1<= j <= k/n = floor(k/(nj)) --- --- / mu(j) / a(rj) --- --- j|m r=1 In linear-mode: B_m(k/n) = sum{GCD(j,m)=1, 1<=j<=k/n} a(j) = sum{j|m} mu(j) sum{r=1 to floor(k/(nj))} a(rj) (mu(j) is the Mobius fuction.) Then: m --- / m+1 k | | B_m(k/n) (-1) / k+1 / --- k=1 is a multiple of (m/(GCD(m,n)). In linear-mode: Then: sum{k=1 to m} binomial(m+1,k+1) B_m(k/n) (-1)^k is a multiple of (m/(GCD(m,n)). -- And m --- --- / m+1 --- | | k / / k+1 / / a(rj) (-1) mu(j) --- --- --- j|m k=1 GCD(r,n)=1 1<=r<=k/j is a multiple of (m/(GCD(m,n)). In linear-mode: sum{j|m} sum{k=1 to m} binomial(m+1,k+1) sum{GCD(r,n)=1,1<=r<=k/j} a(rj) (-1)^k mu(j) is a multiple of (m/(GCD(m,n)). Leroy Quet === Subject: : Re: Multiple Sum of...Divisible by... Again I suspect that this post had not propagated throughout the Usenet correctly. So I have reposted it below. Sorry if you thought I had something new to say... > Let m and n be positive integers. Let {a(k)} be any integer sequence. > Two related results, the last more general than the first: Let B_m(k/n) = --- / a(j) > --- > GCD(j,m)=1 > 1<= j <= k/n = floor(k/(nj)) > --- --- / mu(j) / a(rj) > --- --- > j|m r=1 > In linear-mode: B_m(k/n) = > sum{GCD(j,m)=1, 1<=j<=k/n} a(j) = sum{j|m} mu(j) sum{r=1 to floor(k/(nj))} a(rj) (mu(j) is the Mobius fuction.) Then: m > --- / m+1 k > | | B_m(k/n) (-1) > / k+1 / > --- > k=1 is a multiple of (m/(GCD(m,n)). In linear-mode: Then: sum{k=1 to m} binomial(m+1,k+1) B_m(k/n) (-1)^k is a multiple of (m/(GCD(m,n)). > -- And > m > --- --- / m+1 --- > | | k > / / k+1 / / a(rj) (-1) mu(j) > --- --- --- > j|m k=1 GCD(r,n)=1 > 1<=r<=k/j is a multiple of (m/(GCD(m,n)). In linear-mode: sum{j|m} sum{k=1 to m} binomial(m+1,k+1) > sum{GCD(r,n)=1,1<=r<=k/j} a(rj) > (-1)^k mu(j) is a multiple of (m/(GCD(m,n)). Leroy Quet === Subject: : only c borel subsets of R ? Anyone knows a proof showing that there are only c (continuum) borel subsets of R? nojb. === Subject: : Re: only c borel subsets of R ? Anyone knows a proof showing that there are only c (continuum) borel > subsets of R? Yes. Let B_0 be the collection of open subsets of R. Define B_alpha for ordinals alpha > 0 as follows: if alpha = beta + 1, B_alpha is the collection of countable unions of elements of B_beta and their complements. For alpha a limit ordinal. B_alpha is the union of B_beta for beta < alpha. Show that for each countable ordinal |B_alpha| = c. Then B_{omega_1} is the set of Borel subsets of R where omega_1 is the first uncountable ordinal. Thus |B_omega_1| <= aleph_1 c = c. -- Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html His mind has been corrupted by colours, sounds and shapes. The League of Gentlemen === Subject: : Re: only c borel subsets of R ? > Anyone knows a proof showing that there are only c (continuum) borel > subsets of R? Yes. Let B_0 be the collection of open subsets of R. > Define B_alpha for ordinals alpha > 0 as follows: > if alpha = beta + 1, B_alpha is the collection > of countable unions of elements of B_beta > and their complements. For alpha a limit ordinal. > B_alpha is the union of B_beta for beta < alpha. > Show that for each countable ordinal |B_alpha| = c. > Then B_{omega_1} is the set of Borel subsets of R > where omega_1 is the first uncountable ordinal. > Thus |B_omega_1| <= aleph_1 c = c. Another way shows that there are only c analytic sets (using operation A or as continuous image of N^N), and that every Borel set is analytic. -- G. A. Edgar http://www.math.ohio-state.edu/~edgar/ === Subject: : Re: Last Call For Primecounters > It's been an interesting and slightly weird contest so far, > and I'll definitely have to write a blurb on memoization > somewhere in the results. (To put it crudely, to memoize > a function, usually recursive, means to add a cache > thereto, so that a result isn't computed more than once. > The speedup can be amazing.) > Second version. Additional memoization only. Herb Savage /* Written by: Herb Savage */ /* Purpose: Computes pi(X) */ #include #include #include #include #define TRUE 1 #define FALSE 0 int prime(unsigned x) { unsigned i,t; if (x < 2) return FALSE; if (x == 2) return TRUE; if (!(x & 1)) return FALSE; i = 3; for (;;) { t = x / i; if (t < i) break; if (t * i == x) return FALSE; i += 2; } return TRUE; } unsigned nextPrimeM(unsigned x) { if (x < 2) return 2; if (!(x & 1)) x--; while (!prime(x += 2)); return x; } #define np_cache_size 10000 unsigned np_cache[np_cache_size]; unsigned nextPrime(unsigned x) { if (x < np_cache_size) { if (!np_cache[x]) np_cache[x] = nextPrimeM(x); return np_cache[x]; } return nextPrimeM(x); } unsigned pi_n(unsigned x, unsigned y); unsigned pi_nM(unsigned end, unsigned maxP) { unsigned others,p,primes; others = end - 1; if (others < 1) return 0; p = 0; primes = 0; for (;;) { p = nextPrime(p); if ((p * p > end) || (p >= maxP)) break; if (p == 2) others -= (others + 1) / 2; else if (p == 3) others -= (others + 2) / 3; else others -= pi_n(end/p,p) - (primes - 1); primes++; } return primes + others; } #define pi_cache_size 100 unsigned pi_cache[pi_cache_size][pi_cache_size]; unsigned pi_n(unsigned x, unsigned y) { if (x < pi_cache_size && y < pi_cache_size) { if (!pi_cache[x][y]) pi_cache[x][y] = pi_nM(x,y); return pi_cache[x][y]; } return pi_nM(x,y); } unsigned long long pi(unsigned long long v) { return pi_n(v,v); } int main(int argc, char *argv[]) { unsigned n; if (argc != 2) exit(1); sscanf (argv[1], %u, &n); printf (%llun, pi(n)); exit(0); } ---------------------------------end program === Subject: : Re: Last Call For Primecounters Here is mine. I know it is not the fastest but it still beats my old code. ------------------- class bit { char *bitarray; char list[8]; public: bit(unsigned long long length) { length=(length+1)/8; bitarray=new char[length]; for(unsigned long long i=0;i #include inline unsigned long long pi(unsigned long long); int main (int argc, const char * argv[]) { using namespace std; //introduces namespace std const unsigned long long n = 3900000; std::cout< It's been an interesting and slightly weird contest so far, > and I'll definitely have to write a blurb on memoization > somewhere in the results. (To put it crudely, to memoize > a function, usually recursive, means to add a cache > thereto, so that a result isn't computed more than once. > The speedup can be amazing.) > I tried to memoize a function in the following program and it speed it up by a factor of two. Here's my submission for the contest. Herb Savage /* Written by: Herb Savage */ /* Purpose: Computes pi(X) */ #include #include #include #include #define TRUE 1 #define FALSE 0 int prime(unsigned x) { unsigned i,t; if (x < 2) return FALSE; if (x == 2) return TRUE; if (!(x & 1)) return FALSE; i = 3; for (;;) { t = x / i; if (t < i) break; if (t * i == x) return FALSE; i += 2; } return TRUE; } unsigned nextPrimeM(unsigned x) { if (x < 2) return 2; if (!(x & 1)) x--; while (!prime(x += 2)); return x; } #define cache_size 10000 unsigned np_cache[cache_size]; unsigned nextPrime(unsigned x) { if (x < cache_size) { if (!np_cache[x]) np_cache[x] = nextPrimeM(x); return np_cache[x]; } return nextPrimeM(x); } unsigned pi_n(unsigned end, unsigned maxP) { unsigned others,p,primes; others = end - 1; if (others < 1) return 0; p = 0; primes = 0; for (;;) { p = nextPrime(p); if ((p * p > end) || (p >= maxP)) break; if (p == 2) others -= (others + 1) / 2; else if (p == 3) others -= (others + 2) / 3; else others -= pi_n(end/p,p) - (primes - 1); primes++; } return primes + others; } unsigned long long pi(unsigned long long v) { return pi_n(v,v); } int main(int argc, char *argv[]) { unsigned n; if (argc != 2) exit(1); sscanf (argv[1], %u, &n); printf (%llun, pi(n)); exit(0); } ----------------------------------end program === Subject: : Counterexample to FLT by modular arithmetic a,b,c,n = 5,7,13,3 and (a^n mod c + b^n mod c) mod c = 0 but a^n + b^n - c^n # 0 However, there remains the possiblity that since c.min = 2 and nc.min. The reason c.min = 2 is that 1^1 + 1^1 = 2^1 is a valid solution, and the smallest nontrivial one. So how to get from n a,b,c,n = 5,7,13,3 and > (a^n mod c + b^n mod c) mod c = 0 but > a^n + b^n - c^n # 0 > a,b,c,n = 3,4,5,2 and > a^n mod c b^n mod c (a^n mod c + b^n mod c) (n = 1,2) = > 3 4 7 > 4 1 5 and 5 mod c = 0 --Dec.2000 'WAND' Chairman Paul O'Neill, reelected to Board. Newsish? http://www.rand.org/publications/randreview/issues/rr.12.00/ http://members.tripod.com/~american_almanac === Subject: : Re: Curve Fitting? > I have a tensor whos values need to be expressed as: > I = fn(x,y,z). The function is third order on each axis. > Given a set of samples from a tensor I need to derive the co-efficents of > the polynomial that discribes the function fn. Least squares worked well for me in one dimension but how do I go about > doing it in three dimesions. or is it four? Many thanks in advance. > B. Least squares delivers reasonable results only if the set of basic functions is appropriate to the task. An example, an analog multiplier: f(x,y) = x*y + device errors The quadratic approach g(x,y) = a0 + a1*x+a2*x^2 + b1*y+b2*y^2 cannot fit f(x,y) very well. For two independent variables we can use e.g. g(x,y) = a0 + a1*x+a2*x^2 + b1*y+b2*y^2 + c1*x*y The parameter vector is (a0,a1,a2,b1,b2,c1). For more than two independent variables x,y,z its the same, but without some a-priori knowledge about the expected shape its hard to choose a good set of basic functions (ANY set of linearly independent functions, also containing sines, cosines and exponen- tial functions, if this behaviour is expected). For polynomials the mixed products are necessary. As used for the generation of look-up tables for ICC color profiles. Best regards --Gernot Hoffmann === Subject: : Re: Curve Fitting? Originator: broeker@ > I have a tensor whos values need to be expressed as: > I = fn(x,y,z). The function is third order on each axis. > Given a set of samples from a tensor I need to derive the co-efficents of > the polynomial that discribes the function fn. > Least squares worked well for me in one dimension but how do I go about > doing it in three dimesions. or is it four? It's four, and the simpler case is actually in two dimensions: one independent, one dependent variable. If you look at the least squares algorithm from a more abstract point of view, you'll note that it doesn't care at all about the number of independent variables you have --- as a matter of fact, it doesn't even pretend to know you have any input variables other than the discrete index i in the expression sum(i=0..n-1, ((measurement_i - theory_i(P)) / sigma_i)^2) with P being the vector of parameters to be fitted. If the theory is a function of not only the fittable parameters, but also some continuous variable X (which can be a vector X = (x,y,z) just as easily), you would usually rewrite that as: sum(i=0..n-1, ((y_i - theory(P; X_i)) / sigma_i)^2) The least square fitting algorithm doesn't use the values of X_i at all; it doesn't even have to know what they might be. It only cares about the parameter vector, P. -- Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de) Even if all the snow were burnt, ashes would remain. === Subject: : Re: Curve Fitting? So are you saying there is a way to use matlabs polyfit function to get the polynomials of the samples? For example if my experiment was to measure the temperatures at various locations in a 10m x 10m x 10m room. I could derive the polynomial coefficients that would describe temperature as a function of location in the room? > I have a tensor whos values need to be expressed as: > I = fn(x,y,z). The function is third order on each axis. > Given a set of samples from a tensor I need to derive the co-efficents of > the polynomial that discribes the function fn. > Least squares worked well for me in one dimension but how do I go about > doing it in three dimesions. or is it four? > It's four, and the simpler case is actually in two dimensions: one > independent, one dependent variable. > If you look at the least squares algorithm from a more abstract point > of view, you'll note that it doesn't care at all about the number of > independent variables you have --- as a matter of fact, it doesn't > even pretend to know you have any input variables other than the > discrete index i in the expression > sum(i=0..n-1, ((measurement_i - theory_i(P)) / sigma_i)^2) > with P being the vector of parameters to be fitted. If the theory is > a function of not only the fittable parameters, but also some > continuous variable X (which can be a vector X = (x,y,z) just as > easily), you would usually rewrite that as: > sum(i=0..n-1, ((y_i - theory(P; X_i)) / sigma_i)^2) > The least square fitting algorithm doesn't use the values of X_i at > all; it doesn't even have to know what they might be. It only cares > about the parameter vector, P. > -- > Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de) > Even if all the snow were burnt, ashes would remain. === Subject: : Re: Curve Fitting? > So are you saying there is a way to use matlabs polyfit function to get the > polynomials of the samples? For example if my experiment was to measure the temperatures at various > locations in a 10m x 10m x 10m room. I could derive the polynomial > coefficients that would > describe temperature as a function of location in the room? Not with polyfit, but if your model is linear in the coefficients it's not hard to write your own code. I can't quite tell from your description what the form of your model is. Here's the general linear least-squares problem: minimize E = (1/2)*sum(k=1 to N) |y_k - f(x_k, y_k, z_k)|^2 where f(x,y,z) = sum(i=1 to p) a_i * g_i(x,y,z) It doesn't care what the form of the functions g_i is. What matters is that the function f(x,y,z) depends linearly on the unknown coefficients a_i. For polynomial regression, the functions g_i are just 1, x, x^2, x^3, etc. (You need one of them to be g_i = 1 if you have a constant term). I *think* your functions are either various combinations of powers of x, y and z, like x^2 y z^3, or perhaps you only have separate terms, powers of x, powers of y, powers of z. At any rate general linear least-squares is very easy. Define a matrix V where element V(i,j) is the value of the j-th function at the i-th data point, i.e. V(i,j) = g_j(x_i, y_i, z_i). Then the least-squares solution for your a's is given by: a = Vy; where y = column vector of dependent values. - Randy === Subject: : Re: Curve Fitting? Originator: broeker@ [Note: F'up2 limited to matlab newsgroup --- this off-topic just about everywhere else]. > So are you saying there is a way to use matlabs polyfit function to get the > polynomials of the samples? I don't know MatLab or polyfit at all. They may have hidden the features of the actual least squares algorithms unter too much syntactic sugar for this to work, but in general, yes, that should be posible. All you really need is a function that maps your 3 input variables (x,y,z) to a single, discrete index i to be used in the chi^q summation I quoted, and back to (x,y,z). If, e.g., your measurements are made in a regular 11x11x11 pixels grid spanning a 10x10x10 meters cube, it's quite simple: fi(x,y,z)= x + 11*y + 11*11*z fx(i) = i MOD 11 fy(x) = (i DIV 11) MOD 11 fz(z) = i DIV (11*11) Now, if your real 3D theory function is model(parameters; x,y,z), you would fit to a transformed function fitmodel(parameters; i)=model(paremeters; fx(i), fy(i), fz(i)) OTOH if, as I suspect, polyfit restricts its model function to a simple polynomial in one variable, then this won't work, because you don't get to choose your model function freely enough. But there's bound to be other, more general implementations of the least squares fitting algorithm somewhere in the vast size of MatLab that do let you do this --- or even let you input multi-variate functions as models straightforwardly. > I could derive the polynomial coefficients that would describe > temperature as a function of location in the room? To the extend that the polynomial coefficients to describe it actually exist: yes. -- Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de) Even if all the snow were burnt, ashes would remain. === Subject: : Re: An Informal Call For Program Submissions To Compute pi(n) >(Unless, come to think of it, you allowed Mathematica >as a programming language - I believe I could write >a very short Mathematica program that would have a >pretty good shot... heh-heh.) Me, too. In Mathcad. In Mathcad: for b subset of (list) is a vector process that happens in no particular order, but as many time as there are items in the list. List can be a range, like 1, 2, ... 5; or a list of variables, any one of which can be a scalar, vector, or matrix. You don't type syntax in Mathcad, you click on it and fill in the blanks. There are only seven things you can click, and you can combine them in neat ways. The neat thing about this no particular order thing is it seems to happen all at once the way a Fourier transform of 2^n data points is broken into chunks which fit together. Like breaking down a document, copying double sided, collating the copies, and stapling, on a really good copier. Just bang bang bang. There a whole section on how to write in parallel instead of with indices. The performance benefit is many times. Yours, Doug Goncz (at aol dot com) Replikon Research Read the RIAA Clean Slate Program Affidavit and Description at http://www.riaa.org/ I will be signing an amended Affidavit soon. === Subject: : CAN you Order Reals? Is it true that there are only two closed linear orderings of R: the usual one and the mirror order? An ordering >= is closed, if the set {(x,y) | x>=y} is closed in R^2. By the way, does anybody know some references about closed (partial, linear) orderings of topological spaces? Seems that there's a lot of interesting things here. Simeon === Subject: : Re: CAN you Order Reals? > Is it true that there are only two closed linear orderings of R: the > usual one and the mirror order? An ordering >= is closed, if the set {(x,y) | x>=y} is closed in R^2. Yes. Consider the sets A={(x,y) | x>y}, B={(x,y) | x= is closed, the set B is open. But A is the mirror image of B across the diagonal, so it too is open. Therefore, A and B are two (nonempty) disjoint open sets whose union is R^2-D. But R^2-D has precisely two connected components (one on either side of the diagonal), so A and B must correspond to those components, giving the two possibilities for the ordering. -- === Subject: : Reverse number sequence function I have a the following numbers: 1,2 and 3. When input into a function F(x), the the results should be as follows: F(1) = 3; F(2) = 2; F(3) = 1; What does F look like? Is there an easy way to do this - like a formula? === Subject: : Re: Reverse number sequence function I have a the following numbers: 1,2 and 3. When input into a function > F(x), the the results should be as follows: F(1) = 3; > F(2) = 2; > F(3) = 1; What does F look like? Is there an easy way to do this - like a > formula? It depends: how nice an F would you like? F(x) = -x+4 works F(x) = -(x-2)^3+2 also works. With not too much work you could define F(x) to be a function of sin or cos functions as well. In general, there are an infinite number of ways to define F(x) to give the results listed above. -- Will Twentyman email: wtwentyman at copper dot net === Subject: : Re: Reverse number sequence function >I have a the following numbers: 1,2 and 3. When input into a function >F(x), the the results should be as follows: >F(1) = 3; >F(2) = 2; >F(3) = 1; >What does F look like? Is there an easy way to do this - like a >formula? You could use Lagrange interpolation: F(x) = 3(x-2)(x-3)/((1-2)(1-3) + 2(x-1)(x-3)/((2-1)(2-3)) + (x-1)(x-2)/((3-1)(3-2)). ************************ David C. Ullrich === Subject: : Re: Reverse number sequence function handtheman12@hotmail.com discusses and asked: >I have a the following numbers: 1,2 and 3. When input into a function >F(x), the the results should be as follows: >F(1) = 3; >F(2) = 2; >F(3) = 1; >What does F look like? Is there an easy way to do this - like a >formula? Try graphing the function based on those points. G C === Subject: : Floor-Sum let c,d positive integers. i try to simplify the following equation ( maple notation ): sum(floor((m/d),m=1..2*c); could anyone help me? christian ruether === Subject: : Re: Floor-Sum > i try to simplify the following equation ( maple notation ): > sum(floor((m/d),m=1..2*c); > sum(floor(m/d),m=1,...,2c) = K(K-1)d/2 + (2c - Kd + 1)K, where > K = floor(2c/d) ACK! I totally messed that up, disregard === Subject: : Re: Floor-Sum > i try to simplify the following equation ( maple notation ): > sum(floor((m/d),m=1..2*c); with the elegance of the solution (unlike most the sci.math problems I tackle) so I'll actually post it. sum(floor(m/d),m=1,...,2c) = K(K-1)d/2 + (2c - Kd + 1)K, where K = floor(2c/d) [Note that none of this requires we have the 2 before the c. Take that out and everything still holds (but keep the 2 that divides K(K-1)d)] Sam === Subject: : Re: Floor-Sum >let c,d positive integers. >i try to simplify the following equation ( maple notation ): >sum(floor((m/d),m=1..2*c); Let F(d,n) = sum(floor(m/d), m=1..n). Note that floor(m/d) = k for kd <= m <= kd+d-1. So F(d,qd-1) = sum_{k=1}^{q-1} kd = (q-1)qd/2 and F(d,qd-1+r) = (q-1)qd/2 + qr if 0 <= r < d, i.e. F(d,n) = q(n+1) - q(q+1)d/2 where q = floor((n+1)/d) Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 === Subject: : Re: Sets. > Has anybody ever tried formulating 'fuzzy mathematics', or other > abstract forms of mathematics? More specifically, have they ever tried > to do something like expand Zermelo-Fraenkel Set theory such that > states beyond existing and not existing can have a meaning? > (...Starblade Riven Darksquall...) Do you know the ng comp.ai.fuzzy? And the journal Fuzzy Sets and Systems? In the fuzzy set community there was, for a short time, such an initiative. They thought they could connect fuzzy logic with (the mathematical subject called) topos theory. AFAIK, the subject dried up, however, for unclear reasons. Anyway, the idea to give sets phases, or different contents at different timepoints will typically lead to some form of topos theory. In other words: you might be interested in topos theory. Cheers, Herman Jurjus === Subject: : Re: Sets. > More generally, you cannot have a set of all sets satisfying P, where P >> is some arbitrary property. In fact, this restriction covers both of >> yours. What you can have instead is the principle of bounded >> comprehension, which says that if you have a set A and a property P, then >> you can form the subset B = { x in A : P(x) }. The set A serves as an >> upper bound for the size of the new set being constructed. The other >> kind is called unbounded comprehension and is what leads to paradoxes >> such as those of Russell, Cantor, and Burali-Forti. What if we allow unbounded comprehensive sets? Your question doesn't make sense. I was using comprehension as a noun, > not an adjective. Or sets that do not > follow strict logic. That is, we allow something to exist in states > other than either existing or not existing. What would happen if we injected fuzzy logic into Zermelo Fraenkel Set > theory? We would get functions with codomain [0,1]. Not a big deal. Codomain? Well, what if we use a varity of neither-wholly-true-nor-wholly-false type logical operators? Is it possible to define a number x such that n^x is not greater than x where n is any number greater e^(1/e)? I know no numbers like that exist, but suppose we were to invent one? (...Starblade Riven Darksquall...) === Subject: : Re: Sets. >> What would happen if we injected fuzzy logic into Zermelo Fraenkel Set >> theory? >> We would get functions with codomain [0,1]. Not a big deal. > Codomain? If X is a set, then a fuzzy set would be a mapping f: X -> [0,1]. The codomain of a function is the set in which the function takes its values. The point is, no radical reformulation of set theory is necessary. Fuzzy logic can be modelled perfectly well within the existing theory. > Well, what if we use a varity of neither-wholly-true-nor-wholly-false > type logical operators? > Is it possible to define a number x such that n^x is not greater than > x where n is any number greater e^(1/e)? Since e^(1/e) > 1, I don't know where you are going with this. -- Dave Seaman Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling. === Subject: : A question on Pythagorus theorem Hi all, I was thinking about Pythagoras theorem and was baffled by this : Let us say we have a staircase. The staircase is analogous to hypotenuse of a right angled triangle formed by the wall and floor. Suppose I decrease the size of each step on the stair case. At inifinity the staircase should look flat and the length should be equal to what I get from pythagoras theorem (with the steps becoming infinitesimally small). a/2 |------ | | b/2 | | a/2 | |------ | | | | b/2 | | |------------- Let us take height of the triangle as b and base as a. Let us have two steps in staircase in such a way that each step has a height b/2 and base a/2. The total length of staircase is (a/2 + b/2 + a/2 + b/2) = a + b. Let us iterate this for n times so that n steps are created (also size of the steps decreases). We get the length as {2^n / 2^n * ( a + b )}. This becomes an non-determinate form as it has no limit at inifinity. My question is how do we arrive at the length of hypotenuse (sqrt(a^2 + b^2)) from here ? Am I making any conceptual mistake here ? thanks and regards K.Srinivasan === Subject: : Re: A question on Pythagorus theorem > Let us take height of the triangle as b and base as a. Let us have two > steps in staircase in such a way that each step has a height b/2 and > base a/2. The total length of staircase is (a/2 + b/2 + a/2 + b/2) = a > + b. Let us iterate this for n times so that n steps are created (also > size of the steps decreases). We get the length as > {2^n / 2^n * ( a + b )}. This becomes an non-determinate form > as it has no limit at inifinity. This is an indetermate form that does have a limit (as n goes to infinity). The limit is a+b. Afterall the expression is constant, equaling a+b for every n. > My question is how do we arrive at the length of hypotenuse > (sqrt(a^2 + b^2)) from here ? The total length of your saw-toothed staircase remains fixed at (a+b) at every stage. So the length of your staircase never approaches the length of the hypotenuse. > Am I making any conceptual mistake here ? As n gets very large, the distance between your steps and the hypotenuse becomes arbitrarily small. That does not mean that the total length of the steps approaches the length of the hypotenuse, as your example shows. === Subject: : Re: A question on Pythagorus theorem > Hi all, I was thinking about Pythagoras theorem and was baffled by this : Let us say we have a staircase. The staircase is analogous to > hypotenuse of a right angled triangle formed by the wall and floor. > Suppose I decrease the size of each step on the stair case. At > inifinity the staircase should look flat and the length should be > equal to what I get from pythagoras theorem (with the steps becoming > infinitesimally small). a/2 > |------ > | | b/2 > | | a/2 > | |------ > | | > | | b/2 > | | > |------------- > Let us take height of the triangle as b and base as a. Let us have two > steps in staircase in such a way that each step has a height b/2 and > base a/2. The total length of staircase is (a/2 + b/2 + a/2 + b/2) = a > + b. Let us iterate this for n times so that n steps are created (also > size of the steps decreases). We get the length as {2^n / 2^n * ( a + > b )}. This becomes an non-determinate form as it has no limit at > inifinity. 2^n/2^n = 1, so it simplifies to a+b. My question is how do we arrive at the length of hypotenuse (sqrt(a^2 > + b^2)) from here ? You don't. What you are doing is minimizing the distance from the hypotenuse you travel, but at each stage you are only *on* the hypotenuse finitely many times. Am I making any conceptual mistake here ? Yes. The hypotenuse has no vertical or horizontal components. Your staircases have *only* vertical and horizaontal components. Think of it this way, if an ant were going up your staircase, it would repeated change its facing. When it goes up the hypotenuse, it never changes facing. Therefor, no matter how similar they may appear without magnification, they are always *different* paths. -- Will Twentyman email: wtwentyman at copper dot net === Subject: : Re: A question on Pythagorus theorem >Hi all, >I was thinking about Pythagoras theorem and was baffled by this : >Let us say we have a staircase. The staircase is analogous to >hypotenuse of a right angled triangle formed by the wall and floor. >Suppose I decrease the size of each step on the stair case. At >inifinity the staircase should look flat and the length should be >equal to what I get from pythagoras theorem (with the steps becoming >infinitesimally small). > a/2 > |------ > | | b/2 > | | a/2 > | |------ > | | > | | b/2 > | | > |------------- Let us take height of the triangle as b and base as a. Let us have two >steps in staircase in such a way that each step has a height b/2 and >base a/2. The total length of staircase is (a/2 + b/2 + a/2 + b/2) = a >+ b. Let us iterate this for n times so that n steps are created (also >size of the steps decreases). We get the length as {2^n / 2^n * ( a + >b )}. This becomes an non-determinate form as it has no limit at >inifinity. Huh? That expression certainly does have a limit at infinity. >My question is how do we arrive at the length of hypotenuse (sqrt(a^2 >+ b^2)) from here ? You don't. >Am I making any conceptual mistake here ? Yes. Even though those staircase curves approach the hypotenuse the _length_ of the staircase does _not_ approach the _length_ of the hypotenuse. >thanks and regards >K.Srinivasan ************************ David C. Ullrich === Subject: : Complement of a function Hi all, Is there a way to find a complement of a function defined on integers(Both domain and range are integers)? What I mean is : Suppose you have a set of positive integers = {1,2,3,4,5....} Let us say we create a subset of even integers out of it = {2,4,6,8,....} This set of even numbers can be generated by using the function f(x) = 2x, x=1,2,3... The complement of this set is set of odd numbers and they can be generated using g(x) = 2x-1 , x=1,2,3,4,.... So I define g(x)=2x-1 to be the complement function of f(x)=2x over the set of integers. Is there a generic way to arrive at the complement function given an arbitrary integer function? (I think we can do it using Taylor series. But seems more mechanical) thanks and regards, K.Srinivasan === Subject: : Re: Complement of a function > Hi all, > Is there a way to find a complement of a function defined on > integers(Both domain and range are integers)? What I mean is : > Suppose you have a set of positive integers = {1,2,3,4,5....} > Let us say we create a subset of even integers out of it = > {2,4,6,8,....} > This set of even numbers can be generated by using the function f(x) = > 2x, x=1,2,3... > The complement of this set is set of odd numbers and they can be > generated using g(x) = 2x-1 , x=1,2,3,4,.... > So I define g(x)=2x-1 to be the complement function of f(x)=2x over > the set of integers. Is there a generic way to arrive at the complement function given > an arbitrary integer function? (I think we can do it using Taylor > series. But seems more mechanical) > thanks and regards, > K.Srinivasan As another poster has pointed out, g will not be unique in general. A more serious problem is that even if f is computable then it doesn't follow that any computable g would work. The range of a computable function from integers to integers is by definition recursively enumerable and it is a standard result that the complement of an r.e. set need not be r.e. Hope this helps -john coleman === Subject: : Re: Complement of a function > Hi all, > Is there a way to find a complement of a function defined on > integers(Both domain and range are integers)? What I mean is : > Suppose you have a set of positive integers = {1,2,3,4,5....} > Let us say we create a subset of even integers out of it = > {2,4,6,8,....} > This set of even numbers can be generated by using the function f(x) = > 2x, x=1,2,3... > The complement of this set is set of odd numbers and they can be > generated using g(x) = 2x-1 , x=1,2,3,4,.... > So I define g(x)=2x-1 to be the complement function of f(x)=2x over > the set of integers. Is there a generic way to arrive at the complement function given > an arbitrary integer function? (I think we can do it using Taylor > series. But seems more mechanical) > thanks and regards, > K.Srinivasan > As another poster has pointed out, g will not be unique in general. A > more serious problem is that even if f is computable then it doesn't > follow that any computable g would work. The range of a computable > function from integers to integers is by definition recursively > enumerable and it is a standard result that the complement of an r.e. > set need not be r.e. > Hope this helps If we restrict ourselves to functions from the positive integers into the positive integers and we take g to be an increasing function, then g is unique. If I calculated correctly, g would satisfy the equation g(f(x)-x) = f(x)-1. Of course this may not be of much use to actually compute g. _________________________________________________________ Eric J. Wingler (wingler@math.ysu.edu) Dept. of Mathematics and Statistics Youngstown State University One University Plaza Youngstown, OH 44555-0001 330-941-1817 === Subject: : Re: Complement of a function >> Is there a way to find a complement of a function defined on >> integers(Both domain and range are integers)? >> What I mean is : >> Suppose you have a set of positive integers = {1,2,3,4,5....} >> Let us say we create a subset of even integers out of it = >> {2,4,6,8,....} >> This set of even numbers can be generated by using the function f(x) = >> 2x, x=1,2,3... >> The complement of this set is set of odd numbers and they can be >> generated using g(x) = 2x-1 , x=1,2,3,4,.... >> So I define g(x)=2x-1 to be the complement function of f(x)=2x over >> the set of integers. >> Is there a generic way to arrive at the complement function given >> an arbitrary integer function? (I think we can do it using Taylor >> series. But seems more mechanical) I don't see what Taylor series could have to do with this. >> As another poster has pointed out, g will not be unique in general. A >> more serious problem is that even if f is computable then it doesn't >> follow that any computable g would work. The range of a computable >> function from integers to integers is by definition recursively >> enumerable and it is a standard result that the complement of an r.e. >> set need not be r.e. >If we restrict ourselves to functions from the positive integers into >the positive integers and we take g to be an >increasing function, then g is unique. If I calculated correctly, g >would satisfy the equation g(f(x)-x) = f(x)-1. Of This is wrong: e.g. if f(1)=1, f(2)=3, f(3)=4 then g(f(3)-3)=g(1)=2 but f(3)-1=3. >course this may not be of much use to actually compute g. I think you're also assuming f(x) is increasing. If we do that, then g is computable, e.g. g(x) = min {w >= x: f(w+1-x) > w}. (Of course, if g(x) doesn't exist, i.e. f misses fewer than x values, a search for such w would never terminate, and there is no way in general to predict this) Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 === Subject: : Re: Complement of a function > Hi all, > Is there a way to find a complement of a function defined on > integers(Both domain and range are integers)? What I mean is : > Suppose you have a set of positive integers = {1,2,3,4,5....} > Let us say we create a subset of even integers out of it = > {2,4,6,8,....} > This set of even numbers can be generated by using the function f(x) = > 2x, x=1,2,3... > The complement of this set is set of odd numbers and they can be > generated using g(x) = 2x-1 , x=1,2,3,4,.... > So I define g(x)=2x-1 to be the complement function of f(x)=2x over > the set of integers. Is there a generic way to arrive at the complement function given > an arbitrary integer function? (I think we can do it using Taylor > series. But seems more mechanical) > The complement will not, in general, be uniquely determined. For instance, if we use the whole set of integers and select the ones generated by f(n) = 2n, every function of the form g(n) = 2n - (2m + 1) is going to be a complement to f(n) for all integers m. With more complicated sets, even your generating function is not going to be uniquely determined. The problem is that you're going to begin with a set. Either you already know a generating function, or you'll be hard pressed to find one, since you'll have to know all terms of the sequence without knowing a generating function to give them to you. The best you can do, if you want a unique answer, is to give the set and its complement without speaking of functions. thanks and regards, > K.Srinivasan === Subject: : Re: Complement of a function > Hi all, > Is there a way to find a complement of a function defined on > integers(Both domain and range are integers)? What I mean is : > Suppose you have a set of positive integers = {1,2,3,4,5....} > Let us say we create a subset of even integers out of it = > {2,4,6,8,....} > This set of even numbers can be generated by using the function f(x) = > 2x, x=1,2,3... > The complement of this set is set of odd numbers and they can be > generated using g(x) = 2x-1 , x=1,2,3,4,.... > So I define g(x)=2x-1 to be the complement function of f(x)=2x over > the set of integers. Note: g(x) is *a* complement function. h(x)=2x+1 is also a complement of f(x). Finding such a function may be non-trivial. Don't know if that helps or not. -- Will Twentyman email: wtwentyman at copper dot net === Subject: : Re: Complement of a function Hi all, > Is there a way to find a complement of a function defined on > integers(Both domain and range are integers)? What I mean is : > Suppose you have a set of positive integers = {1,2,3,4,5....} > Let us say we create a subset of even integers out of it = > {2,4,6,8,....} > This set of even numbers can be generated by using the function f(x) = > 2x, x=1,2,3... > The complement of this set is set of odd numbers and they can be > generated using g(x) = 2x-1 , x=1,2,3,4,.... > So I define g(x)=2x-1 to be the complement function of f(x)=2x over > the set of integers. Note: g(x) is *a* complement function. h(x)=2x+1 is also a complement > of f(x). Finding such a function may be non-trivial. Don't know if > that helps or not. Seems to me this is more of a theory of computability issue than anything. For the given example, the OP essentially gave us a program for churning out a particular set of integers/naturals, and then gave us a program that churns out the complement of the first set. Of course there will in general be many programs to churn out the complement, if there are any at all. Among other things, if the original set (eg of evens, as per the OP) isn't recursive, then that's a good time to give up on a complement program.... Generally speaking, the notions of recursive set, recursively enumerable set, and the like seem quite relevant to the OP's question... cdj === Subject: : Re: Complement of a function >Hi all, >Is there a way to find a complement of a function defined on >integers(Both domain and range are integers)? >What I mean is : >Suppose you have a set of positive integers = {1,2,3,4,5....} >Let us say we create a subset of even integers out of it = >{2,4,6,8,....} >This set of even numbers can be generated by using the function f(x) = >2x, x=1,2,3... >The complement of this set is set of odd numbers and they can be >generated using g(x) = 2x-1 , x=1,2,3,4,.... >So I define g(x)=2x-1 to be the complement function of f(x)=2x over >the set of integers. >Is there a generic way to arrive at the complement function given >an arbitrary integer function? (I think we can do it using Taylor >series. But seems more mechanical) How do you do it using Taylor series? >thanks and regards, >K.Srinivasan ************************ David C. Ullrich === Subject: : Re: Complement of a function >Is there a way to find a complement of a function defined on >>integers(Both domain and range are integers)? >>What I mean is : >>Suppose you have a set of positive integers = {1,2,3,4,5....} >>Let us say we create a subset of even integers out of it = >>{2,4,6,8,....} >>This set of even numbers can be generated by using the function f(x) = >>2x, x=1,2,3... >>The complement of this set is set of odd numbers and they can be >>generated using g(x) = 2x-1 , x=1,2,3,4,.... >>So I define g(x)=2x-1 to be the complement function of f(x)=2x over >>the set of integers. >>Is there a generic way to arrive at the complement function given >>an arbitrary integer function? (I think we can do it using Taylor >>series. But seems more mechanical) How do you do it using Taylor series? generating functions? 1/(1-z) - f(z) the function has to be strictly increasing and the gf is really a characteristic function (all coeffs are 0 or 1) e.g. 2n <=> 1/(1-x^2), not 2/(1-x)^2 Mitch === Subject: : Re: Complement of a function Is there a way to find a complement of a function defined on >integers(Both domain and range are integers)? >What I mean is : >Suppose you have a set of positive integers = {1,2,3,4,5....} >Let us say we create a subset of even integers out of it = >{2,4,6,8,....} >This set of even numbers can be generated by using the function f(x) = >2x, x=1,2,3... >The complement of this set is set of odd numbers and they can be >generated using g(x) = 2x-1 , x=1,2,3,4,.... >So I define g(x)=2x-1 to be the complement function of f(x)=2x over >the set of integers. >Is there a generic way to arrive at the complement function given >an arbitrary integer function? (I think we can do it using Taylor >series. But seems more mechanical) >> How do you do it using Taylor series? >generating functions? 1/(1-z) - f(z) That's a way to use power series to obtain the complement of a set. It doesn't give the complement function. (Given a function f with _range_ a subset of f we want another function g with range equal to the complement of the range of f...) >the function has to be strictly increasing and the gf is really a >characteristic function (all coeffs are 0 or 1) >e.g. 2n <=> 1/(1-x^2), not 2/(1-x)^2 >Mitch ************************ David C. Ullrich === Subject: : Re: Complement of a function >Is there a way to find a complement of a function defined on >>integers(Both domain and range are integers)? >>What I mean is : >>Suppose you have a set of positive integers = {1,2,3,4,5....} >>Let us say we create a subset of even integers out of it = >>{2,4,6,8,....} >>This set of even numbers can be generated by using the function f(x) = >>2x, x=1,2,3... >>The complement of this set is set of odd numbers and they can be >>generated using g(x) = 2x-1 , x=1,2,3,4,.... >>So I define g(x)=2x-1 to be the complement function of f(x)=2x over >>the set of integers. >>Is there a generic way to arrive at the complement function given >>an arbitrary integer function? (I think we can do it using Taylor >>series. But seems more mechanical) How do you do it using Taylor series? >>generating functions? 1/(1-z) - f(z) That's a way to use power series to obtain the complement of > a set. It doesn't give the complement function. (Given a function > f with _range_ a subset of f we want another function g with > range equal to the complement of the range of f...) Hmmm... then just extract the function from this characteristic function? 2n <=> 1/(1-x^2) 1/(1-x) - 1/(1-x^2) = x/(1-x^2) <=> 2n-1 (not really a generating function coeff extraction but easy to see anyway) Yes, this last step is not particularly tractable for anything other than combinations of linear functions. (I think quadratic functions have a basis using theta functions) Do you see another way for the original problem? Mitch === Subject: : Re: Complement of a function >Is there a way to find a complement of a function defined on >>integers(Both domain and range are integers)? >>What I mean is : >>Suppose you have a set of positive integers = {1,2,3,4,5....} >>Let us say we create a subset of even integers out of it = >>{2,4,6,8,....} >>This set of even numbers can be generated by using the function f(x) = >>2x, x=1,2,3... >>The complement of this set is set of odd numbers and they can be >>generated using g(x) = 2x-1 , x=1,2,3,4,.... >>So I define g(x)=2x-1 to be the complement function of f(x)=2x over >>the set of integers. >>Is there a generic way to arrive at the complement function given >>an arbitrary integer function? (I think we can do it using Taylor >>series. But seems more mechanical) How do you do it using Taylor series? >>generating functions? 1/(1-z) - f(z) That's a way to use power series to obtain the complement of > a set. It doesn't give the complement function. (Given a function > f with _range_ a subset of f we want another function g with > range equal to the complement of the range of f...) >Hmmm... then just extract the function from this characteristic function? Extracting a function whose _values_ are the indices where the generating function has a non-zero coefficient is exactly equivalent to the original problem. >2n <=> 1/(1-x^2) > 1/(1-x) - 1/(1-x^2) > = x/(1-x^2) > <=> 2n-1 >(not really a generating function coeff extraction but easy to see anyway) >Yes, this last step is not particularly tractable for anything other >than combinations of linear functions. (I think quadratic functions have >a basis using theta functions) >Do you see another way for the original problem? No, it seems to me like the sort of problem that one should simply not expect a simple answer to. >Mitch ************************ David C. Ullrich === Subject: : Point - Curve distance I am looking for an algorithm to compute the distance between a point and a curve in 3D. My curve is a Catmull-Rom spline (curve going through all the control points). Thank you, Francois. === Subject: : Re: Point - Curve distance > I am looking for an algorithm to compute the distance between a point and a > curve in 3D. > My curve is a Catmull-Rom spline (curve going through all the control > points). > Thank you, > Francois. First, make a set of evalution points to determine which one is closer to that point. If that curve consists of N control points, I will suggest N control points and N-1 points between each control points using (U(i)+U(i+1))/2. once you find the point of the shortest distance. letting that position is i, then just do the search loop between U(i-1) ~ U(i+1) with initial condition U(i) using bisection method or any other method you prefered to find the minimal distance. Maybe there must be more fancy algorithms, I've solved that problem with this way and offered quite satisfactory result. D.K Lee === Subject: : Re: probability and/or logic puzzle > Yes, this came out of a textbook . . . > but I passed that class about 25 years ago, > so I'm not cheating on my homework. Start with a normal deck of playing cards. > Discard all but the aces and kings. Now you > have eight cards left. Your friend draws > two cards and hides them from you. He truthfully > tells you that at least one of his cards is an ace. > What is the probability that he holds two aces? He replaces the cards and you shuffle them well. > Your friend again draws two cards, and truthfully > tells you that one of them is the ace of spades. > What is the probability that he now holds two aces? > (Hint: this isn't the same answer as above!) Okay . . . I don't get it. Why isn't it the same > answer both times? Also, in case it matters, this isn't a math > book. It's a (non-mathematical) logic book. Thank you, Ted Shoemaker > shoemakerted@yahoo.com You are right, the book is wrong. This question, again illustrates the difference between being given at least one, and being told at least one. We've had this argument previously in this forum. The illustrious Dr. Ullrich has refused to acknowledge that there is an argument. Dr. Holt made a feeble attempt to understand the argument. P(A|B)=P(B|A)P(A)/P(B) Where B is defined as the event which has already happened. B is the key. Defining B. Defining the event which has definitely happened. There are two cards. Call them X and Y. X can represent Kings, and Y Aces, or vice versa. We don't need to know which is which. B is different when we are given at least one X, than when we are told that there is at least one X. Something different has definitely happened. When we are given at least one X: P(given X|XX)=P(given X|XY) When we are told at least one X: P(told X|XX)>P(told X|XY) The people who got this wrong are in good company. Marilyn had it wrong in her column and in one of her books. It was sent in by her guru, Martin Gardner, who also had it wrong in his book, Aha Gotcha! The secret is in B. What has definitely happened. Notice that to get the popular answer, the X=Ace, or X=King, must be a known, prior definition, ie, our friend must know which denominations she is looking for. In other words, to get other than the 3/7 answer, takes more information. Eldon Moritz === Subject: : NTT transform for vectors of arbitrary length in GF(2^m)? I am looking for a NTT transform that can transform vectors in GF(2^m), but the vectors should not be constrained to length 2^m -1. The vectors that I want to investigate are seldom of length (2^m) - 1, as is required with the NTT transforms I have found thus far. Does anyone know where I can find any literature on these transforms (also known as finite field Fourier transforms, if I am right)? The nice property of the transform that I have used is that the transformed vector have zero's in the coefficients corresponding to the roots of the original vector. Is this true for all the NTTs? Also, can a NTT be used to factor a polynomial? If the roots cannot be found in GF(2^m), look for roots in GF(2^h), where h > m ? Your time, effort and suggestions will be much appreciated Jaco === Subject: : Primecounter contest results I now have all the submissions for the primecounter contest. The results are in http://home.earthlink.net/~ewill3/math/primecounters/index.html and I got 32 entries (8 of them mine). Congratulations to all who participated; it was a very interesting contest. -- #191, ewill3@earthlink.net It's still legal to go .sigless. === Subject: : Re: Lisa Aileen Metz - January 13th 1980 Someone off their meds I see... === Subject: : Orthogonal Polynomials Weight Functions Given a three term recursion relation in the canonical form capable of generating orthogonal polynnomials is there any algorithm that can find the weight function or m-distribution associated with this recursion? Thanks in advance. === Subject: : Re: Orthogonal Polynomials Weight Functions > Given a three term recursion relation in the canonical form > capable of generating orthogonal polynnomials is there any > algorithm that can find the weight function or m-distribution > associated with this recursion? The fact that such a measure exists is known as Favard's theorem and the standard proof is fairly constructive. If I recall correctly, it should be possible to extract a convergent sequence for this measure out of it. -- Jane - Daria? Come on, the neighbors are starting to talk. Daria - Um... good. Soon they'll progress to cave drawings and civilization will be on its way. === Subject: : Is a polytope a projections of a hypercubes? I can represent some simple polytopes in 2 dimensions as a projections of the 3-dim. unit cube. I would like to know if this can be done in general, i.e. Can any polytope be represented as a projection of a hypercube? I've done some initial searching on this problem, but I haven't found much useful information. Are there useful textbooks / keywords that I should search for? Thanks in advance for the help, Pete Seiler === Subject: : Re: Is a polytope a projections of a hypercubes? > I can represent some simple polytopes in 2 dimensions as a projections of > the 3-dim. unit cube. I would like to know if this can be done in > general, i.e. Can any polytope be represented as a projection of a > hypercube? I've done some initial searching on this problem, but I haven't > found much useful information. Are there useful textbooks / keywords that > I should search for? Thanks in advance for the help, > Pete Seiler There is a theorem of Bessaga to the effect that every finite dimensional Banach space with a polyhedral unit ball is isometric to a subspace of c_0. I think there is a finite dimensional version which would have any finite dimensional Banach space of dimension n with polyhedral unit ball is isometric to a subspace of k(n)-dimensional l_infty. The dimension of the hypercube could get higher and higher depending on the dimension of the polytope. This isn't exactly what you are interested in because the unit balls are centrally symmetric. === Subject: : Re: Is a polytope a projections of a hypercubes? > I can represent some simple polytopes in 2 dimensions as a projections of > the 3-dim. unit cube. I would like to know if this can be done in > general, i.e. Can any polytope be represented as a projection of a > hypercube? I've done some initial searching on this problem, but I haven't > found much useful information. Are there useful textbooks / keywords that > I should search for? Thanks in advance for the help, > Pete Seiler > I don't quite understand. A regular triangle is not centrally symetric, but a projection of a hypercube is. === Subject: : Re: Is a polytope a projections of a hypercubes? 3QLpj-NoP*NzsIC,boYU]bQ]H'y<#4ga3$21: I can represent some simple polytopes in 2 dimensions as a projections of > the 3-dim. unit cube. I would like to know if this can be done in > general, i.e. Can any polytope be represented as a projection of a > hypercube? I've done some initial searching on this problem, but I haven't > found much useful information. Are there useful textbooks / keywords that > I should search for? I don't quite understand. A regular triangle is not centrally > symetric, but a projection of a hypercube is. Maybe he means perspective projection, not just parallel projection. I have a paper with some work on a related problem: perspective projections of zonotopes (which are themselves parallel projections of hypercubes...) at That paper discusses the centroid polytope C(S) where S is a set of points each associated with an interval of possible weights, and C(S) is the set of points formed by assigning a weight in its interval to each point in S and taking a weighted average; it turns out that C(S) is a perspective projection of a zonotope. When each interval is [0,1], C(S) is just the convex hull of S, so any polytope can be realized in this way. Probably it's possible to see this more directly somehow. -- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science === Subject: : Re: Is a polytope a projections of a hypercubes? Thanks for the easy counterexample. Due to the problem that I am working on, all of the examples I tried were symmetric polytopes (i.e. if x is in the polytope, then -x is in the polytope). If I restrict myself to polytopes that have this symmetry: can every such polytope be represented as the projection of a hypercube? I'm interested in what literature I should be looking at to answer this question. Thanks again for the example, Pete I can represent some simple polytopes in 2 dimensions as a projections of > the 3-dim. unit cube. I would like to know if this can be done in > general, i.e. Can any polytope be represented as a projection of a > hypercube? I've done some initial searching on this problem, but I haven't > found much useful information. Are there useful textbooks / keywords that > I should search for? Thanks in advance for the help, > Pete Seiler > I don't quite understand. A regular triangle is not centrally > symetric, but a projection of a hypercube is. === Subject: : Re: Is a polytope a projections of a hypercubes? 3QLpj-NoP*NzsIC,boYU]bQ]H'y<#4ga3$21: > Thanks for the easy counterexample. Due to the problem that I am > working on, all of the examples I tried were symmetric polytopes (i.e. if > x is in the polytope, then -x is in the polytope). If I restrict myself > to polytopes that have this symmetry: can every such polytope be > represented as the projection of a hypercube? I'm interested in what > literature I should be looking at to answer this question. The parallel projections of hypercubes are called zonotopes. They are characterized by the property that the whole polytope and each of its faces must be centrally symmetric. So a centrally symmetric polytope with non-centrally-symmetric faces, such as a regular octahedron, would be another counterexample. -- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science === Subject: : E=mc^2 I don't understand the point of the squared. Seems to me:- Since c is a constant, and the speed of light is not measured in the same units as mass or energy, c is just a 'matching' constant. and c^2 is just another matching constant So the equation (E =mc) ,without the squared, is equally as valid Is that right? Tony === Subject: : Re: E=mc^2 > I don't understand the point of the squared. Seems to me:- > Since c is a constant, and the speed of light is not measured in the > same units as mass or energy, c is just a 'matching' constant. and > c^2 is just another matching constant So the equation > (E =mc) ,without the squared, is equally as valid > Is that right? Tony No! E, m and c are not merely numbers, they are measurements, and, as measurements have appropriate units of measurement. The type of units in an equation such as E = m*c^2 must balance as well as the numerical values, i.e., if the units of E do not match the units of m*c^2, you have a major problem, and no equality. And the units of c^2 are of a different type than the units of c. === Subject: : Re: E=mc^2 > Seems to me:- > Since c is a constant, and the speed of light is not measured in the > same units as mass or energy, c is just a 'matching' constant. and > c^2 is just another matching constant So the equation > (E =mc) ,without the squared, is equally as valid > Is that right? Brain wave energy of E = m/(c^2) has been detected in some humans. === Subject: : Re: E=mc^2 >I don't understand the point of the squared. >Seems to me:- >Since c is a constant, and the speed of light is not measured in the >same units as mass or energy, c is just a 'matching' constant. and >c^2 is just another matching constant So the equation >(E =mc) ,without the squared, is equally as valid No. c is measured in meters/second, and m is measured in kilograms. Therefore, mc^2 is in units of kilograms*meters^2/seconds^2, which happens to be equal to joules, the units associated with energy. Without the squares, you don't get that. Doug === Subject: : Re: E=mc^2 > I don't understand the point of the squared. Seems to me:- > Since c is a constant, and the speed of light is not measured in the > same units as mass or energy, c is just a 'matching' constant. and > c^2 is just another matching constant So the equation > (E =mc) ,without the squared, is equally as valid > Is that right? Tony There are (I think) seven fundamental units in SI. The Joule is not one of them - it is derived from the others. One Joule is one Newton exerted over one meter. One Newton is the force required to accelerate a kilogram at one meter per second squared. Therefore the speed of light is indeed measured in the same system of units as energy and is not an arbitrary constant. Mark Atherton === Subject: : Re: E=mc^2 >I don't understand the point of the squared. The only point is that it appears to model the observed phenomena well . >Seems to me:- >Since c is a constant, and the speed of light is not measured in the >same units as mass or energy, c is just a 'matching' constant. and >c^2 is just another matching constant So the equation >(E =mc) ,without the squared, is equally as valid >Is that right? >Tony === Subject: : Re: E=mc^2 >>I don't understand the point of the squared. > The only point is that it appears to model the observed >phenomena well . That's far from the only point. Units are important. Doug === Subject: : Terminology question What do you call an equation of the fourth degree in English? Degree 2 = quadratic? Degree 3 = cubic? Degree 4 = ????????????????????????????????????????????????????????? Degree 5 = quintic? Degree 6 = sextic? hextic? Degree 7 = septic? heptic? Degree 8 = octic? And so on. I don't think degrees from 9 onwards are ever needed in undergraduate mathematics... -- /-- Joona Palaste (palaste@cc.helsinki.fi) --------------------------- | Kingpriest of The Flying Lemon Tree G++ FR FW+ M- #108 D+ ADA N+++| | http://www.helsinki.fi/~palaste W++ B OP+ | ----------------------------------------- Finland rules! ------------/ To doo bee doo bee doo. - Frank Sinatra === Subject: : Re: Terminology question > What do you call an equation of the fourth degree in English? > Degree 2 = quadratic? > Degree 3 = cubic? > Degree 4 = ????????????????????????????????????????????????????????? > Degree 5 = quintic? > Degree 6 = sextic? hextic? > Degree 7 = septic? heptic? > Degree 8 = octic? > And so on. I don't think degrees from 9 onwards are ever needed in > undergraduate mathematics... Quartic is the standard term for a fourth degree polynomial. === Subject: : Re: Terminology question Visiting Assistant Professor at the University of Montana. >What do you call an equation of the fourth degree in English? The old term is biquadratic. Some call them quartic. Many call them of degree 4. == == Arturo Magidin magidin@math.berkeley.edu === Subject: : Re: Terminology question I have always heard quartic, as Arturo said. Lurch >What do you call an equation of the fourth degree in English? > The old term is biquadratic. Some call them quartic. Many call > them of degree 4. > == > 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: : Volume Hi~ I was hoping someone could help with a math problem that I am can not seem to solve. I have a volume in spherical coordinates defined as r = F(theta,phi) where r is the radial distance, theta is the angle from the z axis (0..Pi) and phi is the angle in the xy plane (0..2*Pi). Now I think that the volume of this should be: vol = integral(integral(integral(s^2 * sin(theta) ds*dtheta*dphi, s = 0..F(theta,phi) ), theta = 0..Pi ), phi = 0..2*Pi ) But when I try and do this, in maple, for some given F (such as F=cos(theta)*cos(phi) ) I get the vol = 0. Can someone please give me the correct formula for the volume? My second problem is a little more complicated. Suppose that I have now drawn a line circumscribing my volume. The line being defined as r = F( theta(phi),phi) where theta(phi) is some combination of cosines of phi say for example theta(phi) = cos(phi) +cos(2*phi). Now since the same line is drawn for negative phi I can connect the points ( F(theta(phi),phi) , theta(phi) , phi) and ( F(theta(-phi),-phi) , theta(-phi) , -phi) with a line. This defines a surface which is dividing the volume (r = F(theta,phi)). I now wish to seek the volume of the part above this surface. How do I do this?? Any help would be greatly appreciated. Ed === Subject: : Is ...9999.9999... = 0 ? Is ...9999.9999... = 0 ? Consider the Manipulation: ...9999.9999... = ...9999.0000... + ...0000.9999... = ...9999.0 +(1.0-1.0)+ 0.9999... = ...9999.0 +1.0 -(1.0 - 0.999...)= ...00000.0 - 0.0000... = 0.0 = 0 since ...9999.0 +1.0 = ...0000.0 by carrying to the left (try it!) and 1.0 - 0.9999... = 0.0000... by borrowing to the right. Woops, I may be getting my topologies confused(*), But can anybody obtain a real contradiction(**) from assuming ...9999.9999... = 0 and the things it would clearly imply like ...3333.0 = - 0.3333... ? * It's kind of like trying to keep your feet in seperate boats, that are being pulled apart. ** Such as 0=1, but no fair dividing by zero or nothing like that. (: I hope this note isn't offensive to those trying to teach kids that 1/3 = .3333.... :) === Subject: : Re: Is ...9999.9999... = 0 ? > Is ...9999.9999... = 0 ? The expression...9999.9999... does not represent any real number, in any usual sense, since a (presumably decimal) representation of a real number must have a most significant digit, which ...9999.9999... does not have. === Subject: : Re: Is ...9999.9999... = 0 ? >(: I hope this note isn't offensive to those trying to teach kids >that 1/3 = .3333.... :) Those of us teaching kids that 1/3 = 0.3333... know the difference between that and what you just did. HTH. Doug === Subject: : Interesting Inequality *** post for FREE via your newsreader at post.newsfeed.com *** Show that a^b + b^a <= a^a + b^b for all positive real numbers a and b. -----= Posted via Newsfeed.Com, Uncensored Usenet News =----- http://www.newsfeed.com - The #1 Newsgroup Service in the World! -----== 100,000 Groups! - 19 Servers! - Unlimited Download! =----- === Subject: : Re: MS in Math or Comp Sci?? Injector-Info: news.mailgate.org; posting-host=adsl-67-119-173-68.dsl.frsn01.pacbell.net; posting-account=48257; posting-date=1063723511 X-URL: http://mygate.mailgate.org/mynews/comp/comp.theory/ 59eb4df4982c4d43fecc917e3f ea8ab8.48257%40mygate.mailgate.org CAF> I take what I said back. My statement did not convey the CAF> whole picture. Working with people who are knowledgeable CAF> in the field is definitely a good thing. That was very graciously said. Thank you. xanthian. CAF> So someone should spend 2 years of his life in grad CAF> school in order to get the advantage and luxury of CAF> reading his professor's scrap book? KPD>> More like seven years, if you hope to become a front line KPD>> constributor to the state of the art. KPD>> And yes, exactly so. When I took graph theory from KPD>> Stephen Olariu(sp?), in his office he had a 30 cm high KPD>> stack of faxes, which contained all the recent work of he KPD>> and the 18 others in the world who could understand each KPD>> others papers. Each of us floundering grad students took KPD>> a paper from that stack, read it for comprehension and KPD>> presented it to the class. KPD>> It just isn't possible to get much closer to the state of KPD>> the art than that, both because the publishing cycle is KPD>> so slow for textbooks, and because the reward for writing KPD>> a textbook in such a rarified field is so unlikely to KPD>> match the effort involved. KPD>> While self-education is possible and fruitful in some KPD>> areas, others are so intrinsically difficult that the KPD>> mentorship of a professor is a necessity of life for all KPD>> but the most hyper-intelligent students. KPD>> My abject apologies all these years later to the rest of KPD>> the class for how weak my presentation was. There is no KPD>> question my grades in graph theory were gifts, pure and KPD>> simple. -- === Subject: : Improved prime counting function A new and improved implementation of the Extended Meissel-Lehmer Algorithm for the calculation of pi (N), the number of primes <= N written in C++ can be found at my webpage at www.cbau.freeserve.co.uk This implementation comes with a test program that calculates various values of pi (N) for N from 10^3 to 10^18. All the results for pi (N) for 3 <= N <= 18 agree with the results published at www.mathword.com. All the values from the original paper by Lagarias, Miller and Odlyzko are tested and agree with the published results. The calculation times on a Macintosh running at 733 MHz, using the CodeWarrior 7 compiler, are as follows: pi (10^15) < 60 seconds pi (10^16) 4 minutes 42 seconds pi (10^17) 24 minutes 40 seconds seconds pi (10^18) 110 minutes pi (1.9*10^13) less than 1 second For comparison: Harris' best code, based on Legendre's formula, took over fifty hours to find pi (10^16); that is more than 600 times slower, and that factor grows as N grows larger. A very short overview of the mathematics involved: Let phi (N, k) be the number of integers <= N which are not divisible by any of the first primes. Let phi (N, x, k) = (-1)^j * phi (N/x, k) if x is the product of exactly j prime numbers. Then phi (N, x, k) can be calculated using the recursion formula phi (N, x, k) = phi (N, x, k-1) + phi (N, x*p(k), k-1) for k > 0, where p(k) is the k-smallest prime. Calculation of phi (N, k) for small k is quite simple, for example phi (N, 5) = 480 * floor (N / 2310) + phi (N mod 2310, 5) which can be found easily using a small table of 2310 values. If k = pi (N^(1/2)), then pi (N) = phi (N, 1, k) + (k - 1). The basic idea of the Extended Meissel-Lehmer Algorithm is as follows: We choose an integer c >= 1 such that phi (N, c) can be calculated quickly using a table-based formula. Choose an integer M, N^(1/3) <= M <= N^(1/2). Let k2 = pi (floor (N^(1/2))) or k2 = pi (ceil (N^(1/2))). Then start with pi (N) = phi (N, 1, k2) + (k2 - 1) and apply the recursion formula until either the third argument is <= c or the second argument is greater than M. If we let k3 = pi (N^(1/3)), then a careful analysis shows that pi (N) can be found by adding the following values: 1. k2 - 1 2. phi (N, x, c) for square-free integers 1 <= x <= M with no prime factor p <= p (c) 3. phi (N, x * p(k+1), k) for square-free integers x such that floor (M / p(k+1) + 1) <= x <= M, with no prime factor p <= p (k+1), for those k where c <= k < pi (M) and p (k+1) * p(k+2) <= M. 4. phi (N, x * p(k+1), k) for primes x, p(k+2) <= x <= M, for those k where c <= k < pi (M) and p (k+1) * p (k+2) > M. 5. phi (N, 1 * p(k+1), k3) + (k - k3) for those k where max (pi (M), c, k3) <= k <= k2 - 1. The calculations of values phi (N, x, k) for k > c is implemented by creating a sieve of size N / M, and about M^2 / log^2 M values need to be looked up in this sieve. That is the mathematics, the rest is just clever implementation. With a good implementation, the execution time of this algorithm grows with N^(2/3). For example, my implementation on a Macintosh takes about 4.4 * N^(2/3) processor clocks when N = 10^15. === Subject: : Vector Cross Product Is there a vector cross product defined for 7 dimensional vectors? If so, what is the definition? === Subject: : Re: Vector Cross Product > Is there a vector cross product defined for 7 dimensional vectors? > Yes, based on the purely imaginary Cayley numbers (alias octonions) > If so, what is the definition? Let e_1, ..., e_7 be the canonical basis of R^7. Then the product of e_i with e_j is given by this matrix (source: http://math.ucr.edu/home/baez/Octonions/node3.html ): e_j: e_1 e_2 e_3 e_4 e_5 e_6 e_7 e_i: e_1 0 e_4 e_7 -e_2 e_6 -e_5 -e_3 e_2 -e_4 0 e_5 e_1 -e_3 e_7 -e_6 e_3 -e_7 -e_5 0 e_6 e_2 -e_4 e_1 e_4 e_2 -e_1 -e_6 0 e_7 e_3 -e_5 e_5 -e_6 e_3 -e_2 -e_7 0 e_1 e_4 e_6 e_5 -e_7 e_4 -e_3 -e_1 0 e_2 e_7 e_3 e_6 -e_1 e_5 -e_4 -e_2 0 Extend to all of R^7 by bilinearity; that is, sum_i(r_i e_i) x sum_j(s_j e_j) = sum_ij (r_i s_j e_i x e_j) Dale. === Subject: : Re: Vector Cross Product A jumbled mess. I'll do this one last time, and if it doesn't turn out legible, I'll refer you to the web page: http://math.ucr.edu/home/baez/Octonions/node3.html : e_j: e_1 e_2 e_3 e_4 e_5 e_6 e_7 e_i: e_1 0 e_4 e_7 -e_2 e_6 -e_5 -e_3 e_2 -e_4 0 e_5 e_1 -e_3 e_7 -e_6 e_3 -e_7 -e_5 0 e_6 e_2 -e_4 e_1 e_4 e_2 -e_1 -e_6 0 e_7 e_3 -e_5 e_5 -e_6 e_3 -e_2 -e_7 0 e_1 e_4 e_6 e_5 -e_7 e_4 -e_3 -e_1 0 e_2 e_7 e_3 e_6 -e_1 e_5 -e_4 -e_2 0 Dale On second thought, perhaps this process (of mine) would have been a better candidate for alt.test or some such scratch newsgroup? === Subject: : Re: Vector Cross Product > Let's try that spacing just one more time. > Let e_1, ..., e_7 be the canonical basis of R^7. Then the product of e_i with e_j is given by this matrix (source: http://math.ucr.edu/home/baez/Octonions/node3.html ): e_j: > e_1 e_2 e_3 e_4 e_5 e_6 e_7 > e_i: > e_1 0 e_4 e_7 -e_2 e_6 -e_5 -e_3 > e_2 -e_4 0 e_5 e_1 -e_3 e_7 -e_6 > e_3 -e_7 -e_5 0 e_6 e_2 -e_4 e_1 > e_4 e_2 -e_1 -e_6 0 e_7 e_3 -e_5 > e_5 -e_6 e_3 -e_2 -e_7 0 e_1 e_4 > e_6 e_5 -e_7 e_4 -e_3 -e_1 0 e_2 > e_7 e_3 e_6 -e_1 e_5 -e_4 -e_2 0 > Extend to all of R^7 by bilinearity; that is, sum_i(r_i e_i) x sum_j(s_j e_j) = sum_ij (r_i s_j e_i x e_j) Dale. > There. All spaces, no tabs. I hope it's more legible. Dale === Subject: : Re: Vector Cross Product mattsdad2, > Is there a vector cross product defined for 7 dimensional vectors? > If so, what is the definition? Yes there is - but you need six of them at a time. The generalized n-dimensional cross-product produces a vector normal to n-1 given vectors. You may know that one way of writing the calculation for a x b in 3 dimensions is the determinant | i x_a x_b | | j y_a y_b | | k z_a z_b | where i, j and k are the unit vectors along the axes. The n-dimensional cross product of n-1 vectors is calculated analogously. Cheers, Paul === Subject: : Please assist... Mime-version: 1.0 Content-transfer-encoding: 7bit Hello Could somebody please confirm if I am on the correct path with the following? Determine if the following is a vaild, recursive defn of a function f from the set of nonnegative integers to the set of integers. If f is well defined find a formula for f(n) when n is a nonnegative integer and prove that your formula is valid. F(0) =1, F(n) = -F(n-1) for n >= 1. ANSWER F(n) = -F(1-1) = 0 As 0 is less than and not equal to 1, the definition is invalid. ! Note that every day Freemason Don Ocean libels me and calls me a pedophile (or such) on the usenet, then I will repost the stats for the following people: Daniel Bruner, Angel Cadwell, Brittanie Cecil, Carl Koopang, Jay Larson, Brian Lott, Adam Millikan, Cody Milliken, Christopher Ridsdale, Vito Rizzuto, Melissa Schultz, Erin Sorenson, Ann Wigdahl, Michael Winkler, or maybe more. === Subject: : Order of an element If the order of a is 3 mod p, show that the order of (a + 1) is 6. 3 must divide EulerPhi[p] = p - 1, so p = 3K + 1 for some K an element of the natural numbers. I need to show that (a + 1)^3 is congruent to -1 (mod p). Then, its square, (a + 1)^6 will be congruent to 1 (mod p). a^3 = (3K + 1)m + 1 for some m an element of the natural numbers. (a + 1)^3 = (3K + 1)n - 1 for some n and element of the natural numbers. a^3 + 3a^2 + 3a + 1 = (3K + 1)n - 1 a^3 + 3a^2 + 3a + 2 = (3K + 1)n a^3 - 1= (3K + 1)m Can someone help at this point? Diana === Subject: : Second Order PDE (Linear) Can anyone tell me if the equation P_xx + P_yy + A P_x + B P_y + C P = 0 has a known method of solution? (A, B, and C are functions of x and y.) I posted something a couple of months ago where I assumed that there was such a method, but I have not been able to find it. === Subject: : Continued-Fraction Root? (generalized) Let {f_n(x)} be an infinite sequence of real-> real functions (where the continued fraction is defined and converges). (f(x) is NOT necessarily a positive integer!) Then, given a real y and the sequence of {f_n}, how can we find the x('s) which are the root of this, if any x are a root and the CF converges?: y = 1 f_0(x) + --------------------- 1 f_1(x) + --------------- 1 f_2(x) + --------- f_3(x) +.... In linear-mode: y = f_0(x) + 1/(f_1(x) +1/(f_2(x) +...)) For example, for those y where a solution exists, which x give: y = 1 + 1/(x +1/(x^2 +1/(x^3 +1/(x^4 +... )))) ? Leroy Quet === Subject: : Math Cheat Sheet Thought some of you might like to have this (for undergrads I suppose). http://bit.csc.lsu.edu/~seiden/cheat.pdf