mm-3398 === Subject: Re: Corner geometry Originator: israel@math.ubc.ca (Robert Israel) |I thought about combining solids in R^3. For example an ellipsoid | and a ball are both smooth in an intuitive sense. Their union (if | they have common points) is also smooth except at the points that | belong to the boundary of both objects. I tried to think what | characterizes this smoothness - property. | | What is true is that when corner point is defined properly then | a (finite) ellipsoid does not have corner points and a (finite) | smooth torus does not have corner points. Neither has their union | corner points except at the points that belong to the boundary of | both objects. Also the set of the corner points of their union | is cornerless. | | | I tried to define corner in metric space so that the definition | would match the intuitive picture of a corner. | | It seems to me that the simplest characterization of a corner is in terms of the non-existence of unique tangent vectors in all directions. At any point of a sphere the tangent plane is 2-dimensional but at a junction of two surfaces it's 1-D and at the corner of a cube it's really 3-D. Norm === Subject: Re: Corner geometry Originator: israel@math.ubc.ca (Robert Israel) >It seems to me that the simplest characterization of a corner is in terms >of the non-existence of unique tangent vectors in all directions. At any >point of a sphere the tangent plane is 2-dimensional but at a junction of >two surfaces it's 1-D and at the corner of a cube it's really 3-D. You (and maybe the original poster) might be interested in looking at analytic varieties, usually). If you do, you might become persuaded to fine-tune your definition. For instance, if you consider the locus of all points (x,y,z) in R^3 with x^2=y^3, then there's a pretty visible corner all along the z-axis, but also at any point of the z-axis there's a good candidate for a 2-dimensional tangent *half*-plane, namely, the (+y,z)-half-plane. Lee Rudolph === Subject: Re: Corner geometry Originator: israel@math.ubc.ca (Robert Israel) | | >It seems to me that the simplest characterization of a corner is in terms | >of the non-existence of unique tangent vectors in all directions. At any | >point of a sphere the tangent plane is 2-dimensional but at a junction of | >two surfaces it's 1-D and at the corner of a cube it's really 3-D. | | You (and maybe the original poster) might be interested in looking at | analytic varieties, usually). If you do, you might become persuaded | to fine-tune your definition. For instance, if you consider the locus | of all points (x,y,z) in R^3 with x^2=y^3, then there's a pretty visible | corner all along the z-axis, but also at any point of the z-axis | there's a good candidate for a 2-dimensional tangent *half*-plane, | namely, the (+y,z)-half-plane. | | Lee Rudolph I admit to being hasty and imprecise. A better way of expressing what I had in mind is to say that at a corner the dimensionality of the tangent space changes abruptly. Norm === Subject: Re: Corner geometry Originator: israel@math.ubc.ca (Robert Israel) ... >| You (and maybe the original poster) might be interested in looking at >| analytic varieties, usually). If you do, you might become persuaded >| to fine-tune your definition. For instance, if you consider the locus >| of all points (x,y,z) in R^3 with x^2=y^3, then there's a pretty visible >| corner all along the z-axis, but also at any point of the z-axis >| there's a good candidate for a 2-dimensional tangent *half*-plane, >| namely, the (+y,z)-half-plane. ... >I admit to being hasty and imprecise. A better way of expressing what I had >in mind is to say that at a corner the dimensionality of the tangent >space changes abruptly. But that's just what *doesn't* happen in that example! The *dimensionality* is 2 everywhere. It's even easier to see in the case of plane curves (although there the wealth of *other* kinds of tangent behavior Whitney studies doesn't appear). Let C be the cuspidal cubic curve defined by x^2=y^3. Suppose you define a tangent vector to a curve at a point P to be the set of all vectors based at P that have the direction of a limit of chords PQ where Q is a point of C and the limit is taken as Q approaches P along C. Then at any point of C other than the origin, the set of all tangent vectors is a 1-dimensional vectorspace. At the origin, if you take direction in the oriented sense, then the set of all tangent vectors is a 1-dimensional half-vectorspace (i.e., a ray), but if you take direction in the unoriented sense, then the set of all tangent vectors is again a 1-dimensional vectorspace, AND that space is itself the limit of the tangent vectorspace at Q on C as Q approaches the origin--so neither the dimensionality nor the directionality of the tangent space (defined that way) changes abruptly. (What does change abruptly?) Those are two of Whitney's 5 or 6 versions of a tangent space in this case. Another, the space of vectors based at P that have the direction of a limit of chords QQ' where Q and Q' are two points of C that both approach P, is the usual tangent line away from the origin, and the entire plane at the origin, so there we *do* have an abrupt change in dimensionality. Lee Rudolph === Subject: Re: Corner geometry Originator: israel@math.ubc.ca (Robert Israel) | | ... | >| You (and maybe the original poster) might be interested in looking at | >| analytic varieties, usually). If you do, you might become persuaded | >| to fine-tune your definition. For instance, if you consider the locus | >| of all points (x,y,z) in R^3 with x^2=y^3, then there's a pretty visible | >| corner all along the z-axis, but also at any point of the z-axis | >| there's a good candidate for a 2-dimensional tangent *half*-plane, | >| namely, the (+y,z)-half-plane. | ... | >I admit to being hasty and imprecise. A better way of expressing what I had | >in mind is to say that at a corner the dimensionality of the tangent | >space changes abruptly. | | But that's just what *doesn't* happen in that example! The | *dimensionality* is 2 everywhere. It's even easier to see | in the case of plane curves (although there the wealth of | *other* kinds of tangent behavior Whitney studies doesn't | appear). Let C be the cuspidal cubic curve defined by | x^2=y^3. Suppose you define a tangent vector to a curve | at a point P to be the set of all vectors based at P that | have the direction of a limit of chords PQ where Q is a point | of C and the limit is taken as Q approaches P along C. Then | at any point of C other than the origin, the set of all tangent | vectors is a 1-dimensional vectorspace. At the origin, if you | take direction in the oriented sense, then the set of all | tangent vectors is a 1-dimensional half-vectorspace (i.e., a | ray), but if you take direction in the unoriented sense, | then the set of all tangent vectors is again a 1-dimensional | vectorspace, AND that space is itself the limit of the tangent | vectorspace at Q on C as Q approaches the origin--so neither | the dimensionality nor the directionality of the tangent space | (defined that way) changes abruptly. (What does change | abruptly?) | Using your definition of tangent vector, there are two different tangent vectors at the origin based on the +h and -h directions. Since these are not co-linear, then in some sense they define a 2-dimensional space. It's in this sense that I'm saying that the dimensionality of the tangent space changes abruptly at the cusp. An extrinsic view of the same curve at the origin is that there's a discontinuous change in the normal vector to the tangent spaces at the origin. Maybe something like this is a better characterization of corner. Norm === Subject: Re: This Week's Finds in Mathematical Physics (Week 231) Originator: baez@math-cl-n03.math.ucr.edu (John Baez) Originator: israel@math.ubc.ca (Robert Israel) >It's full of nontrivial theorems about >these, starting with Gabriel's classification of quivers into those >of finite representation type (see week230), the tame quivers >(which have a countable set of indecomposable representations), >and the wild ones. Sorry - I should have said that a tame quiver has an infinite but still manageable set of indecomposable representations. A good example is the quiver consisting of a single dot with an arrow going from that dot to itself. A representation of this quiver is just a vector space V and a linear transformation f: V -> V. Classifying the indecomposable ones of these amounts to classifying Jordan blocks (at least if the field is C). There's an uncountable but still manageable set of possibilities. (More generally, over other fields, one needs Frobenius blocks - or whatever people call the blocks that show up in rational canonical form, aka Frobenius normal form. Still manageable.) === Subject: Re: The algebraic closure of the rationals Originator: israel@math.ubc.ca (Robert Israel) tchow@lsa.umich.edu in litteris <4460ad81$0$572$b45e6eb0@senator-bedfellow.mit.edu> scripsit: >>Actually, come to think of it, I now think any two countable algebraic >>closures of Q can be shown to be isomorphic without using any form of >>the axiom of choice, the argument being something like this: number >>the elements of both fields by natural numbers (which can be done, >>since we are assuming them to be countable), take the smallest-labeled >>element of one field, say x, consider its minimal polynomial (over Q), >>take its roots in the other field, consider the smallest-labeled among >>them, say y, and map x to y; then map Q(x) to Q(y) in the only >>possible way; then take the smallest-labeled element still not >>accounted for, and so on. > Hold on a second...this seemed to make sense to me when I first read it, > but on second reading I'm not sure I understand your construction. When > you take the smallest-labeled element still not accounted for, are you > taking the smallest-labeled element in the first algebraic closure or > the second? If you're flipping back and forth between them, isn't this > an implicit use of Koenig's lemma or something? I don't think there's any reason to flip back and forth (once all elements of one field have been exhausted, the elements of the other also necessarily have been exhausted, since both are algebraic closures of Q), but, even if I did, I don't think that would require choice (e.g., Cantor's theorem that any two countable dense unbounded totally ordered sets are isomorphic doesn't require any form of the axiom of choice). (Also I seem to remember that there are several subtly different formulations of the Koenig lemma, some of which require choice and some of which don't. So I won't argue on that count, but I'm pretty sure my reasoning above works without choice - unless I'm mistaken and it doesn't work at all, I mean.) -- David A. Madore (david.madore@ens.fr, http://www.dma.ens.fr/~madore/ ) === Subject: Re: Algebraic Geometric Codes Originator: israel@math.ubc.ca (Robert Israel) > I'm working on a class project researching Algebraic Geometric codes > and cannot find any information on real time applications. I would > appreciate any help I can get. > Aarthi All Reed-Solomon and Reed-Muller codes are algebro-geometric ! At least RS codes are widely used in applications. In my mind the more generale case of AG codes are used in construction of other codes. === Subject: Non NP-complte and non NP problems Summary: Are there problems which are recurisve but not NP, or NP but not NP-complete? Keywords: recrusive, NP, NP-complete Originator: israel@math.ubc.ca (Robert Israel) Are there problems which are recurisve but not NP, and if so how extensiveley are they studied? Also, it would appear that the P=NP question is equivalent to the question as to whether or not there are problems which are NP but not P or NP-complete due to Ladner's theorem. Is this correct? -- Cody Pace Math and Computer Science Department, Drury University http://www.crystalbox.org/ === Subject: Re: Non NP-complte and non NP problems Originator: israel@math.ubc.ca (Robert Israel) > Are there problems which are recurisve but not NP, and if so how extensiveley > are they studied? Executive summary: Yes, and extensively studied, but not as much as those within NP. As is usual with questions about complexity questions, the immediate things that come to mind are not actually proven yet (or not) to have property X, but are highy suspected to be so. For example, membership in context sensitive languages is PSPACE complete, and PSPACE contains and is highly suspected to properly contain NP. To get a problem that is provably properly not in NP, you have to go way up to NEXP (nondeterministic exponential time) complete problems, like...wow....I can't think of any 'accessible' problems off the top of my head (ones that don't depend on a lot of machinery) or don't depend on the (almost trivial) descriptive logic As to extensively, the harder problems (those higher in the hierarchy) are usually not problems that people are interested (vs those lower) because there is usually in the back of everyone's head an interest in making a practical algorithm, and so once a problem is shown to be in complexity class Y, one usually wants to restrict the problem so it is accessible to an easier complexity class (or approximate it). So yes, there is a plethora of harder and harder complexity classes (driven by theory), but for practicality, the direction of interest is downward to easier classes. > Also, it would appear that the P=NP question is equivalent to > the question as to whether or not there are problems which are NP but not P or > NP-complete due to Ladner's theorem. Is this correct? Equivalent in the trivial set theory sense that if P=NP, then NP - P is empty (there are no problems that are in NP and outside of P). I think the relevant theorem of Ladner is that -if- NP-P is nonempty (there is a problem that is in NP but not P), then there is an infinite lattice of classes each with complete problems. Ladner's thm only talks about the structure of classes given that one knows that one intermediate problem already exists. Mitch === Subject: Re: Non NP-complte and non NP problems Originator: tchow@lebesgue.mit.edu.mit.edu (Timothy Chow) Originator: israel@math.ubc.ca (Robert Israel) >> Are there problems which are recurisve but not NP, and if so how >> extensiveley are they studied? [...] >To get a problem that is provably properly not in NP, you have to go >way up to NEXP (nondeterministic exponential time) complete problems, >like...wow....I can't think of any 'accessible' problems off the top of >my head (ones that don't depend on a lot of machinery) or don't depend >on the (almost trivial) descriptive logic One class of relatively natural problems that are complete for NEXP are those involving succinct representations, e.g., SUCCINCT SAT. See for example C. Papadimitriou and M. Yannakakis, A note on succinct representations of graphs, Information and Control, 71:181-185, 1986. There is a field of study known as recursion theory which studies recursive functions in general. Computational complexity theory can be thought of as a historical outgrowth of recursion theory. The recursive functions studied in recursion theory are typically far, far above the complexity level of NP. They are perhaps of more interest to logicians than to computer scientists. Occasionally, individual practical problems and algorithms show up with extremely high computational complexity. Computing the Groebner basis of an ideal in a polynomial ring comes to mind. Other examples may be found in Papadimitriou's book Computational Complexity. Sometimes these particular problems are studied in great detail because of their practical importance. Usually, though, the nontrivial facts known about these problems are specific to the problem in question and don't shed much light on general recursion theory or complexity theory. >> Also, it would appear that the P=NP question is equivalent to >> the question as to whether or not there are problems which are NP but >> not P or NP-complete due to Ladner's theorem. Is this correct? >Equivalent in the trivial set theory sense that if P=NP, then NP - P is >empty (there are no problems that are in NP and outside of P). I think >the relevant theorem of Ladner is that -if- NP-P is nonempty (there is >a problem that is in NP but not P), then there is an infinite lattice >of classes each with complete problems. Ladner's thm only talks about >the structure of classes given that one knows that one intermediate >problem already exists. Note, however, that the answer to the original question is yes, and it's not trivial. If P = NP, then certainly there are no problems in NP that are neither in P nor NP-complete. And if P != NP, then Ladner's theorem shows that there must exist problems in NP that are neither in P nor NP-complete. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences === Subject: elliptic curves Originator: israel@math.ubc.ca (Robert Israel) Can anyone give me some information on where I might find a proof (assuming one is known) that the order of the group of elliptic points on an elliptic curve of the form y^2=x^3+ax+b over the field Z_p(i), p=3 mod 4, is (p+1)^2 ? PG Brown University of NSW Australia === Subject: Re: elliptic curves Originator: israel@math.ubc.ca (Robert Israel) > Can anyone give me some information on where I might find a proof (assuming > one is known) that the order of the group of elliptic points on an elliptic > curve of the form y^2=x^3+ax+b over the field Z_p(i), p=3 mod 4, is (p+1)^2 ? To have a chance of being true, by Z_p(i) you must mean the field with p^2 elements and the curve must have complex multiplication. In fact, it is true for Y^2=X^3-DX over the field with p^2 elements, see Exercise 2.33, p185, Silverman, Advanced Topics....1994. === Subject: Re: elliptic curves Originator: israel@math.ubc.ca (Robert Israel) >Can anyone give me some information on where I might find a proof (assuming >one is known) that the order of the group of elliptic points on an elliptic >curve of the form y^2=x^3+ax+b over the field Z_p(i), p=3 mod 4, is (p+1)^2 ? >PG Brown >University of NSW >Australia If the curve has order p + 1 - tau over GF(p), where abs(tau) <= 2 *sqrt(p), then the order over GF(p^2) is (p + 1)^2 - tau^2, not (p+1)^2. You can check that (p + 1)^2 - tau^2 is a multiple of p + 1 - tau, between p^2 + 1 - 2p and p^2 + 1 + 2p. It is also divisible by p + 1 + tau, the order of the subgroup with x in GF(p) y = sqrt(quadratic nonresidue)*(element of GF(p)) This doesn't quite prove your result when tau = 0 -- conceivably the group order over GF(p^2) could be p^2 + p and satisfy the restrictions above. -- VP Cheney Burr-ed his gun as a bird flew past The nation responds burr as we await bird flu shots and fight a real cold war. pmontgom@cwi.nl Microsoft Research and CWI Home: Bellevue, WA === Subject: Re: volume of a k-parallelepiped in n-dim Originator: israel@math.ubc.ca (Robert Israel) feeling that by your saying that ... is the induced Euclidian norm squared on the k-forms you have just assumed what we want to prove, I mean the Pythagorean theorem on determinants. Why is it obvious that W_I will be the coordinates in the induced space? What also confuses me is that you are saying that the rotation is isometry and it leaves the volume invariant. But the rotation that I am sure to leave the volume invariant is in n-space not in the induced C(n,k)-space where the decomposition is done. I can see that W_I, the determinant of a kxk matrix, would be invariant under an orthogonal transformation (rotation) in a k-dim space but how does that relate to the induced C(n,k) dimensional space? === Subject: Re: volume of a k-parallelepiped in n-dim Originator: israel@math.ubc.ca (Robert Israel) > feeling that by your saying that ... is the induced Euclidian norm > squared on the k-forms you have just assumed what we want to prove, I > mean the Pythagorean theorem on determinants. Why is it obvious that > W_I will be the coordinates in the induced space? What also confuses me > is that you are saying that the rotation is isometry and it leaves the > volume invariant. But the rotation that I am sure to leave the volume > invariant is in n-space not in the induced C(n,k)-space where the > decomposition is done. I can see that W_I, the determinant of a kxk > matrix, would be invariant under an orthogonal transformation > (rotation) in a k-dim space but how does that relate to the induced > C(n,k) dimensional space? This is the idea. The space of k-forms has a basis e_I = e_{i1}^...^e_{ik} for any k-set I of {1,...,n}. Any k-form can be written in the form b=sum W_I e_I and its norm (by definition) is ||b||=sqrt(sum|W_I|^2). Furthermore, one way to compute W_I is as W_I = b^e_{I'} where I' is the complement of I (and we identify n-forms with scalars). Thus if b=a1^...^ak, then it is clear that W_I is the determinant of the kth minor as you defined it. Now, any rotation on R^n induces a natural map on the k-forms. Since the rotation is orthogonal, that is its transpose is equal to its inverse, the same is true of the induced map on the k-forms. Hence the induced map will be an isometry on the k-forms. Thus if you want to prove that Vol(a1,...,ak)=||a1^...^ak|| since both the left and right hand sides are invariant under rotations (the right under the induced rotation), wlog it is sufficient to prove this when only the first k-coordinates of a1,...,ak are non-zero. Stephen === Subject: Re: volume of a k-parallelepiped in n-dim Originator: israel@math.ubc.ca (Robert Israel) === Subject: Re: volume of a k-parallelepiped in n-dim Originator: israel@math.ubc.ca (Robert Israel) > Maybe you could do it by noting that the volume you seek is invariant > under rotations of the space. Thus wlog you may assume that only > a1,...,ak are non-zero, I meant - only the first k coordinates of a1,...,ak are non-zero. > in which case the result is obvious. You also > need that the quantity sum (W_I)^2 is invariant under rotations. > However the rotation induces an isometry on the k-forms, but what you > are computing, it seems to me, is the induced Euclidian norm squared on > the k-forms, that is, if you represent your form with respect to the > basis generated by the unit vectors, the W_I will be the coordinates. > Does that sound reasonable? > Stephen === Subject: Re: volume of a k-parallelepiped in n-dim Originator: israel@math.ubc.ca (Robert Israel) I found the description of this topic in C.H. Edwards: Advanced Calculus of Several Variables quite enlightening. He uses the Binet-Cauchy formula, so I'm not sure that you will find the approach geometric enough. Bela === Subject: Re: Banach space isomorphisms Originator: israel@math.ubc.ca (Robert Israel) I have a followup question. Viewing X as a closed subspace of X** (I believe it can be isometrically embedded), the quotient Banach space X**/X can be formed. Assuming X** and Y** are isomorphic, then the reply shows that X and Y need not be isomorphic, but are X**/X and Y**/Y isomorphic? Dan Goodman > If X and Y are Banach spaces, and X** and Y** denote their > respective > Banach double duals, and there is an isomorphism between X** and Y**, > does this imply that there is an isomorphism between X and Y? In case > this is not true in general, it might be in the particular case I am > interested in where Y is c_{0}, the space of sequence converging to > zero, and Y** is then l^{infinity}, the space of bounded sequences. > No. If S is a countable compact metric space, then Banach space C(S) > has dual isometric to l^1, so second-dual isometric to l^infinity. But > not all C(S) spaces are isomorphic. In fact, there are aleph-1 > isomorphism classes. I believe you classify them by the number of > times (possibly transfinite) you form the derived set starting with S > before you reach a finite set. (This is a countable ordinal.) There > is a topic in Banach space theory called l^1 preduals. > -- > G. A. Edgar edgar at math.ohio-state.edu === Subject: Axioms for schemes? Originator: israel@math.ubc.ca (Robert Israel) In conversation the other day, one of the other grad students claimed to have heard that Grothendieck at some point introduced a set of axioms for schemes that he considered a superior foundation than the original definition in terms of local-affineness. What exactly this means is unclear to me (the conversation was not on this subject and the comment was incidental); it would be nice if it turned out to be a sort of characterization of the category of schemes. In any case, does this sound vaguely familiar to anyone, and if so, what's the reference? -- Ryan Reich ryan.reich@gmail.com === Subject: Re: Axioms for schemes? Originator: israel@math.ubc.ca (Robert Israel) > In conversation the other day, one of the other grad students claimed > to have heard that Grothendieck at some point introduced a set of > axioms for schemes that he considered a superior foundation than the > original definition in terms of local-affineness. As I understand it, the alternative definition is as follows. It has the advantage that it can be explained to someone who doesn't know what a variety is (not that I'm suggesting you belong to this category). First you have to accept that a (commutative) ring can be viewed as a kind of space, or more precisely that Ring^op (the opposite of the category of rings) can be viewed as a category of spaces. This can be motivated by appealing to the duality between algebra and geometry that appears in many guises: study a space by studying the functions on it. Anyway, as you probably know, Ring^op is called the category of affine schemes. I mean this as a *definition* of affine scheme. The idea now is to consider spaces that can be formed by gluing together affine schemes in some nice way; these are, of course, what shall be called schemes. So a scheme will be defined as a formal gluing-together of affine schemes; put another way, the category of schemes will be obtained from the category of affine schemes by adjoining formally all nice enough formal gluings. Now, the precise way to say gluing is colimit, so we want to formally adjoin colimits to the category of affine schemes. It's a theorem that if you start with a category C then the category obtained by freely adjoining colimits is [C^op, Set], the category of contravariant functors from C to Set. (C sits inside [C^op, Set] via the Yoneda embedding.) In this case, C is the category Ring^op of affine schemes, so the category obtained by freely adjoining colimits is [Ring, Set]. Thus, a scheme is defined as a functor Ring ---> Set, satisfying conditions saying that the gluing is nice. The full details are in the book of Demazure and Gabriel, Groupes algebriques. Best wishes, Tom === Subject: Re: Axioms for schemes? Originator: israel@math.ubc.ca (Robert Israel) Hi-- TomLeinster> Thus, a scheme is defined as a functor Ring ---> Set, TomLeinster> satisfying conditions saying that the gluing is TomLeinster> nice. The full details are in the book of Demazure TomLeinster> and Gabriel, Groupes algebriques. There is an introductory account (readable, in English) of this point of view in the first section of: Representations of Algebraic Groups J. C. Jantzen Though one does not find there full details. best, gm -- __O | George McNinch _-<,_ | (_)/ (_) | === Subject: Re: Axioms for schemes? Originator: israel@math.ubc.ca (Robert Israel) > In conversation the other day, one of the other grad students claimed > to have heard that Grothendieck at some point introduced a set of > axioms for schemes that he considered a superior foundation than the > original definition in terms of local-affineness. > As I understand it, the alternative definition is as follows. It has > the advantage that it can be explained to someone who doesn't know what a > variety is (not that I'm suggesting you belong to this category). > First you have to accept that a (commutative) ring can be viewed as a kind > of space, or more precisely that Ring^op (the opposite of the category of > rings) can be viewed as a category of spaces. This can be motivated by > appealing to the duality between algebra and geometry that appears in many > guises: study a space by studying the functions on it. Anyway, as you > probably know, Ring^op is called the category of affine schemes. I mean > this as a *definition* of affine scheme. > The idea now is to consider spaces that can be formed by gluing together > affine schemes in some nice way; these are, of course, what shall be > called schemes. So a scheme will be defined as a formal gluing-together > of affine schemes; put another way, the category of schemes will be > obtained from the category of affine schemes by adjoining formally all > nice enough formal gluings. > Now, the precise way to say gluing is colimit, so we want to formally > adjoin colimits to the category of affine schemes. It's a theorem that if > you start with a category C then the category obtained by freely adjoining > colimits is [C^op, Set], the category of contravariant functors from C to > Set. (C sits inside [C^op, Set] via the Yoneda embedding.) In this case, > C is the category Ring^op of affine schemes, so the category obtained by > freely adjoining colimits is [Ring, Set]. > Thus, a scheme is defined as a functor Ring ---> Set, satisfying > conditions saying that the gluing is nice. The full details are in the > book of Demazure and Gabriel, Groupes algebriques. > Best wishes, > Tom -- Ryan Reich ryan.reich@gmail.com === Subject: Re: Axioms for schemes? Originator: israel@math.ubc.ca (Robert Israel) > In conversation the other day, one of the other grad students claimed > to have heard that Grothendieck at some point introduced a set of > axioms for schemes that he considered a superior foundation than the > original definition in terms of local-affineness. > As I understand it, the alternative definition is as follows. It has > the advantage that it can be explained to someone who doesn't know what a > variety is (not that I'm suggesting you belong to this category). > First you have to accept that a (commutative) ring can be viewed as a kind > of space, or more precisely that Ring^op (the opposite of the category of > rings) can be viewed as a category of spaces. This can be motivated by > appealing to the duality between algebra and geometry that appears in many > guises: study a space by studying the functions on it. Anyway, as you > probably know, Ring^op is called the category of affine schemes. I mean > this as a *definition* of affine scheme. > The idea now is to consider spaces that can be formed by gluing together > affine schemes in some nice way; these are, of course, what shall be > called schemes. So a scheme will be defined as a formal gluing-together > of affine schemes; put another way, the category of schemes will be > obtained from the category of affine schemes by adjoining formally all > nice enough formal gluings. > Now, the precise way to say gluing is colimit, so we want to formally > adjoin colimits to the category of affine schemes. It's a theorem that if > you start with a category C then the category obtained by freely adjoining > colimits is [C^op, Set], the category of contravariant functors from C to > Set. (C sits inside [C^op, Set] via the Yoneda embedding.) In this case, > C is the category Ring^op of affine schemes, so the category obtained by > freely adjoining colimits is [Ring, Set]. > Thus, a scheme is defined as a functor Ring ---> Set, satisfying > conditions saying that the gluing is nice. The full details are in the > book of Demazure and Gabriel, Groupes algebriques. > Best wishes, > Tom That may be around the notion of representable functor (sorry have no reference at hand, but Google may help) and IIRC Seminaire Cartan in the 60s as well (and a lot of stuff later, often related to deformation theory). -- use mail at ... instead of test3 at ... to send me a mail === Subject: Primitive Recursive Arithmetic and Computable Categories Originator: israel@math.ubc.ca (Robert Israel) Foundations of Mathematics email list. However, I thought it may also be of interest here. First, a few background comments. The primitive recursive functions are a class of computable functions from the natural numbers to the natural numbers which are total by construction. Primitive Recursive Arithmetic, or PRA, is a quantifier free formal system for discussing primitive recursive functions. One may consider it the quantifier free portion of Peano Arithmetic, the usual axiomatization of the natural numbers. While not all computable functions (Ex: Ackermann's) are primitive recursive, they form a rather 'canonical' class of 'total by construction' computable functions. Below is a short note giving an alternate but equivalent definition of of computability and the definition of five 'computable categories.' I find these constructions interesting because they are both elementary and seemingly canonical. Comments? The Note: http://www.math.utah.edu/~rbutler/PRA/PRA.pdf [I would have posted this directly in text, however text is not an appropriate medium for commutative diagrams] Here is a portion of the preliminary idea: --------------------------------------------------------- 1. A. Define a primitive to be a pair (A,~) where A is a primitive recursive predicate and ~ is a primitive recursive equivalence relation. Consider primitives as codings of countable discrete sets, with the equivalence relation determining whether two numbers represent the same combinatorial object. B. Define a function between two primitives (A,~) and (B,~) to be a primitive recursive function f: N --> N such that PRA proves If x in A then f(x) in B and If x,y in A and x~y then f(x) ~ f(y). With these statement proved, we write f: (A,~) --> (B,~), etc... Equality of functions will be as provable in PRA. [Here we use Godel coding as a method of construction rather than merely as a method of representation.] 2. Introduce computability and enumerability as follows: A. Define an primitive type A_THM to be a function pi_A : A_PROOF --> A_PROP between primitives. We write x in A_THM if PRA proves x is in the image of pi_A. The image of the function pi_A is Sigma_1, and we now define Sigma_1 sets to be sets of such form. Thinking foundationally, we may consider such primitive types as elementary protological systems. For example, we may present any recursively axiomatizable theory (such as PRA itself) in this form. Thinking geometrically, we may visualize pi_A as a projection and rename A_PROOF as A_COVER and A_PROP as A_BASE, as we do below: B. Define a function between primitive types A and B to be a function f_COVER: A_COVER --> B_COVER between their enumerating primitives such that PRA proves For x,y in A_COVER, pi_A(x) ~ pi_A(y) in A_BASE implies pi_B(f(x)) ~ pi_B(f(y)) in B_BASE This induces a effectively computable function f: A_BASE->B_BASE. We now define partial recursive functions to be those functions of such form. We now have a Brouwer-Heyting-Kolomogorov semantics of some sort, a proposition being a pair (a,A) where A = (A_COVER,pi_A,A_BASE) is a primitive type and a is an element of A_BASE. A proposition (a,A) is 'true' if PRA proves pi_A(b) = a for some explicit b in A_COVER. C. Extend the construction by allowing both the image of pi_A and the equality defined thereon to be Sigma_1 by providing explicit presentations by primitive recursive parameterization. [See linked note] Rex Butler Graduate Student Department of Mathematics University of Utah === Subject: infinite discrete isometry groups with no translations Originator: israel@math.ubc.ca (Robert Israel) Is there a known classification of the infinite discrete subgroups of isometries of R^3 which contain no translations? If not can anything interesting be said about them? Any references would be appreciated. === Subject: Re: infinite discrete isometry groups with no translations Originator: israel@math.ubc.ca (Robert Israel) An example would be any matrix in SO(3) used as a generator of a discrete group. Include inverses and the identity. Give the generator irrational entries and you'll have an infinite discrete group. [ Moderator's note: I think the original poster was looking for groups that are discrete in the usual topology on E(3). In particular, no infinite subgroup of the compact group O(3) is discrete. - ri ] === Subject: Re: infinite discrete isometry groups with no translations Originator: israel@math.ubc.ca (Robert Israel) > An example would be any matrix in SO(3) used as a generator of a > discrete group. Include inverses and the identity. Give the generator > irrational entries and you'll have an infinite discrete group. > [ Moderator's note: I think the original poster was looking for groups > that are discrete in the usual topology on E(3). In particular, no > infinite subgroup of the compact group O(3) is discrete. > - ri ] Yes, I meant in the sense used by people who study the crystallographic groups on R^3 (also sometimes called space groups). A group of isometries G acting on R^3 is discrete if the intersection of the orbit of any point with any ball is finite. I guess this is the same as saying that G is a discrete topological subgroup of E(3) (the group of all isometries of R^3) where E(3) has the natural topology. In this sense the only discrete subgroups of O(3) are finite groups as the moderator pointed out. These have been classified --as have the discrete subgroups of E(3) which contain three linearly independent translations. There are some 230 of the latter. (Geometry and Symmetry by Paul B Yale reprinted by Dover in 1988.) I'm looking for a discussion of discrete groups where every element of the group is a composition of an element of O(3,R) and a nonzero translation. It contains no nonzero translations! I think I can construct some, but I'm looking for a systematic treatment that may be out there somewhere. An example would be to take A to be a rotation by sqrt(2)*pi radians about the x axis followed by a nonzero translation along the x axis, and take B to be a rotation about the y axis by sqrt(3)*pi followed by a nonzero translation along the y axis. Then consider the group generated by A and B. I think this will be discrete and a free group on the generators A and B. Of course, the cyclic group generated by A is another example. === Subject: Irreducible Polynomials over GF(2) Originator: israel@math.ubc.ca (Robert Israel) What is known about the growth rate of the function f(n) = minimum number of nonzero terms in an irreducible polynomial of degree n over the field with 2 elements? What is the first n for which f(n)>5? === Subject: Re: Irreducible Polynomials over GF(2) Originator: israel@math.ubc.ca (Robert Israel) If there is such an n then n > 12800 according to http://magma.maths.usyd.edu.au/magma/htmlhelp/text546.htm#4808 where one finds the statement below describing the Magma command IrreducibleSparseGF2Polynomial(n) : RngIntElt -> RngUPolElt : Given an integer n in the range 4 <= n <= 12800, return the irreducible polynomial f of the form x^n + g where g has 2 non-zero terms if possible and 4 non-zero terms if not; g is the first such polynomial in lexicographical order in either case. This uses a database of sparse irreducible polynomials over GF(2) constructed by Allan Steel in 1998. PS Apparently the sequence f(n) is not in the OEIS. === Subject: factorization of positive quadratic forms Originator: israel@math.ubc.ca (Robert Israel) Supposed F(s, t, u) is a quadratic form of three real indeterminates and with (m x m) matrices as coefficients, i.e. F(s,t,u) = A s^2 + B t^2 + ... , where A, B, ... are m x m matrices. Assume further that F(s, t, u) is positive semidefinite for all s, t, and u. Are there any results that say F can be factorized in the sense that, for example, F(s, t, u) = (K s + L t + M u)^* (K s + L t + M u) , where K, L, M, are matrices. Any pointer to any results similar to Whoapao === Subject: Relation /feiner/ between Subsets of R Originator: israel@math.ubc.ca (Robert Israel) In a discussion about Dedekind cuts I happened to invent the following relation between subsets of the set R of the real numbers: Let X and Y be subsets of R. We say X is /feiner/ than Y (Def) if for all subsets A and B of Y with A < B there is an element x of X such that A <= x <= B. Two examples: The rationals Q are not /feiner/ than the reals R, but R is /feiner/ than Q. The primes P = { 2, 3, 5, 7, 11, 13, ...) are /feiner/ than the set Z = { 2, 4, 8, 16, ... } of all 2^n, n > 0. What is known about (Def)? Rainer Rosenthal r.rosenthal@web.de === Subject: A question on matroids Originator: israel@math.ubc.ca (Robert Israel) Let (X,B) be a matroid, with B the set of bases (= maximal independent sets). For each b in B let chi_B denote its characteristic function in the real vector space spanned by X. Let v_B denote the barycenter of the convex hull of {chi_b:b in B}. HOPE: If B <= B', i.e. all bases b in B are subsets of bases of B', then v_B is <= v_{B'} coordinate-wise. === Subject: Primitive Recursive Functions, References? Originator: israel@math.ubc.ca (Robert Israel) I am fairly familiar with the primitive recursive functions, but there is not much information on the topic I could find on the internet. Could someone direct me towards relevant resources? It is interesting to note that for quite some time the primitive recursive functions were thought to exhaust -all- computable functions. Ackermann's function, which uses double induction, shows this is not the case, as does a simple diagonal argument using the fact that all primitive recursive functions are total. However, any recursively enumerable set is the image of some PR function, and one could argue in the vein of the Church-Turing thesis that the PR functions form the intuitive class of 'iteration functions,' i.e. the transition functions from one state to the next in effective computation models. Being a mathematics graduate student, what is the CS view of primitive recursive functions and their role? Rex Butler === Subject: Math errors in book Secret Life of Numbers I'm a science journalist with some background in engineering mathematics. Perhaps some of you would be willing to help me with a book review of The Secret Life of Numbers by George Szpiro. The publisher, Joseph Henry, is the official publisher of the U.S. National Academy of Sciences, so the lay reader is likely to assume that the math in this book bears some relationship to reality. Have any of you read Secret Life? I found major errors in two chapters, but I'm not sufficiently competent in areas touched upon in other chapters to know whether they might also be off base. If anyone has discovered other errors, I would be delighted to cite you in the planned book review Following my analysis of the errors in the chapters Tetris is Hard, and How Can One Be Sure it's Prime? Please advise me if you see errors in these analyses. Szpiro first triggered my concern in Chapter 26, Tetris is Hard. He Toronto, proved in 1971 that all NP problems are mathematically equivalent to each other. This entirely misleads the reader about the field of decision problems, meaning those with an answer of yes or no. Every student of computer engineering learns (or ought to learn) about the class NP and its subsets. This is necessary in order to determine whether a computer program can, in practical terms, solve a given decision problem. Consider, for example, the subset NP-Complete. All NP-Complete problems are known to be easy to construct (meaning in a time bounded by a polynomial function of the size of the problem) but conjectured to be hard to solve. Furthermore, only the set NP-Complete contains problems that are (to use Szpiro's inelegant term) equivalent to each other. [For Cook's analysis of this set, see The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Symp. on Theory of Computing, Association for Computing Machinery, New York, pp. 151-158] NP-Complete problems have utility in the construction of some public key cryptography systems, and therefore are worth describing accurately. Szpiro's explanation of the set NP quickly collapses into proved that the class NP-Complete is not equal to the class P, meaning problems that are easy to solve. However, Szpiro states incorrectly that if only one NP problem can be solved in polynomial time, all NP problems can be solved in polynomial time.... Numerous scientists have wrestled with it, not least because the Clay Foundation has offered a $1 million prize for a correct solution. The problem here is that the set P is a subset of NP, and by definition, all problems in P already have been proved to be solvable in a number of steps bounded by a polynomial function of the size of the problem. For example, the spanning tree problem, meaning how to build a tree that connects a given number of points with the shortest total length of branches, has been shown to be a member of P. Therefore, it would be a world-shaking mathematical finding to prove that all NP problems are equivalent and belong to the class NP-Complete. Despite Szpiro's claim, clearly this has not been done, which means that I won't win that $1 million prize with a proof that spanning tree is solvable in polynomial time:( The second chapter that set off my alarm bells is How Can One Be Sure it's Prime? Szpiro correctly reports that Manindra Agrawal and two of his students have proven that primes can be found in polynomial time. created no small sensation among colleagues in the field because ... three mathematicians had hit on a beautiful and fundamentally new idea. For practical purposes the algorithm is, admittedly, still too time consuming. But now that the ice has been broken, experts are confident that more efficient ways of calculation are imminent. Agrawal's finding was not unexpected. Furthermore, it did not raise hopes of finding faster ways to find primes. Fast ways to find primes (but not to solve the problem of factoring a composite number down to its primes) have been known since the 1970s, and the fastest of them scale as the fourth power of the size of the numbers tested. What these techniques lacked was a proof that the amount of time required could be guaranteed to be bounded by a polynomial without introducing even a small probability of error, and while running the same algorithm every time (no random choices). In practice this didn't make a difference -- the time was fast enough, and a vanishingly small probability of error could be achieved. Experience has shown that whenever calculations turn out to be fast on a practical basis, a proof that it belongs to P is highly likely to be found. An example is the linear programming program. It was long known that in practice, it always was solved in polynomial time using the simplex method. However, it wasn't proved to belong to P until 1980 [L. G. Khachiyan, Polynomial algorithm in linear programming, U.S.S.R. Comput. Math. and Math. Phys., 20 (1980), 53--72.] Furthermore, in the case of the primes problem, in 1975 Vaugh R. Pratt proved that primes was a member of the class NP, and almost certainly solvable in polynomial time. [Every prime has a succinct 1975, pp. 214-220.] Therefore any mathematician with an interest in primes knew before Agrawals' publication that a proof was hardly unexpected. This is not meant to denigrate Agrawal's feat. It was the brilliance of his proof, not unexpectedness or practical application, that caused a sensation. The closing statement of How Do You Know it's Prime is misleading: The discovered method [Agrawal's proof] cannot be applied to breaking encryption. True, nobody could possibly use Agrawal's proof to crack RSA public key encryption, which uses the easy primes problem to create keys but the hard integer factoring problem to make cracking impossible by any known technique. Integer factoring is (somewhat informally) considered to be a member of the set NP and conjectured to be a member of the set NP-Incomplete (problems conjectured to be outside the sets of both P and NP-Complete). [Computers and Intractability: A Guide to the Theory of NP-Completeness, Michael R. Garey and David S. Johnson (W. H. Freeman and Company, New York, 23rd printing, 2002) pg. 228] According to a leading researcher in this field, Dr. Burt Kaliski, as of today, integer factoring still has not been proved to be a member of P. The issue here is that just before Szpiro states that Agrawal's proof too cumbersome to be practical because its computational time is bounded by a polynomial of too high an order. Abruptly changing the topic from the practical usage of a proof to the issue of encryption and by implication its link to a related problem Szpiro does not even mention - integer factoring - is confusing at best. If Szpiro had looked into the relationship between the primes and integer factoring problems, he would have realized that NP does not equal NP-Complete and he would have been able to fix all the errors in these two chapters.