What is "rich structure", actually? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-22T05:29:57Z http://mathoverflow.net/feeds/question/16003 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16003/what-is-rich-structure-actually What is "rich structure", actually? Hans Stricker 2010-02-22T00:16:19Z 2010-02-22T11:19:36Z <p>An ubiquitous claim in mathematics is that such-and-such mathematical entity has a <em>rich structure</em> or <em>more structure</em> than another one. Most oftenly the entity <em>is</em> a structure - a set explicitly equipped with a structure, i.e. a graph, a group, etc. - but often enough it's just a set <em>not</em> explicitly equipped with a structure. </p> <p>Examples:</p> <ol> <li><p>Ash/Gross in <em>Fearless Symmetry</em> claim that the solution <em>set</em> [sic!] of a polynomial equation has "<strong>more structure</strong>" than just its cardinality (p.66).</p></li> <li><p>They state on the other hand that the absolute Galois group $G_{\mathbb Q}$ "has a <strong>rich structure</strong> - much of it still unknown" (p. 87).</p></li> </ol> <p>Two questions arise (for the beginner):</p> <blockquote> <p><strong>Question #1</strong>: If one considers the structure-richness of a genuine structure - as a set equipped with a structure (as in Example #2) -, what is a possible quantitative measure for <strong>richness</strong>? </p> </blockquote> <p>The only answer that comes to my mind is something like the diversity of non-isomorphic (induced?) sub-structures. Is this formalizable?</p> <blockquote> <p><strong>Question #2</strong>: If only a set is mentioned - not explicitly equipped with a structure (as in Example #1) -, what sense does it make to talk of the richness of its structure? </p> </blockquote> <p>I guess I have to <strong>presume</strong> a structure imposed on the set, and go back to Question #1. But often enough the structure to impose isn't obvious from the context (like in Example #1). Is this only because this is a book for the general audience? My impression is, that it's fairly often "left to the reader" to literally guess, which structure has to be imposed (to be a rich one).</p> http://mathoverflow.net/questions/16003/what-is-rich-structure-actually/16005#16005 Answer by lhf for What is "rich structure", actually? lhf 2010-02-22T00:24:59Z 2010-02-22T00:24:59Z <p>At least in the examples you mentioned, richness can be interpreted as the structure of the group of symmetries associated to the object (sub-object graph and permutation group in the examples).</p> http://mathoverflow.net/questions/16003/what-is-rich-structure-actually/16012#16012 Answer by Gerhard Paseman for What is "rich structure", actually? Gerhard Paseman 2010-02-22T01:46:55Z 2010-02-22T01:46:55Z <p>It sounds like richness shares with beauty: the beholder's eye determines what is rich. While I will not attempt to give a quantitative answer, I think the following points can be considered.</p> <ol> <li><p>The object may have many properties that are desired for study or application. An example of this is a set system {{1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}} on seven points. It has a lot of symmetry but the structure as a system is not apparent until you give it an interpretation: finite projective plane, complement of a D-optimal design, arrangement of statistical tests. Richness of application may be meant even though richness of structure was stated.</p></li> <li><p>The richness may come from using the structure to build more things. The two-element lattice generates the variety of all distributive lattices, and its equational theory is the same as the equational theory of any larger distributive lattice in the same language. So in a proper context the richness may stem from how the structure will be used in creating other structures or in determining properties of related structures.</p></li> </ol> <p>Granted these are not literal interpretations, but I think they are in mind when someone makes a statement about richness of structure.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.02.21</p> http://mathoverflow.net/questions/16003/what-is-rich-structure-actually/16016#16016 Answer by Charles Siegel for What is "rich structure", actually? Charles Siegel 2010-02-22T02:38:17Z 2010-02-22T03:22:39Z <p>I would interpret things like "has richer structure than just X" to mean that there's more there that you get for free, in some sense. For instance, in your example, the set of solutions to a system of polynomial equations at first seems to just have a cardinality, which is the only thing you can say automatically about a set. However, in this case, it's not just any set, by virtue of being solutions to some polynomial equations over a ring, it has a structure of a scheme (variety if the ring is a field and the equations are nice) where, without making any choices at all, we can make it into something more than just a set. In some cases (elliptic curves) the structure is yet richer, and is in fact also a group in a natural way.</p> <p>At the least, things like this are how I generally hear the phrase used. But generally it's used informally to say that something is more interesting than a random object that looks like it at first glance, or that an object is very interesting (richness of structure of the absolute Galois group) and in nontrivial ways.</p> http://mathoverflow.net/questions/16003/what-is-rich-structure-actually/16020#16020 Answer by Douglas Zare for What is "rich structure", actually? Douglas Zare 2010-02-22T02:51:59Z 2010-02-22T02:51:59Z <p>I'm answering with a stub that I hope others will fill out. Please feel free to edit this. </p> <p>The rich structure on "the solution set of a polynomial" can mean the nice properties of the function which assigns to a polynomial its multiset of roots rather than a value of that function. It can mean that we have a permutation representation of the absolute Galois group on the roots. </p> <p>The rich structure on the absolute Galois group may describe the actions on many objects, the lattice of (normal) subgroups, and that it carries a topology as a profinite group. Perhaps to say an object has a rich structure in this sense, there should be natural morphisms to many interesting objects, and we can recognize it as an image of a forgetful functor. </p> http://mathoverflow.net/questions/16003/what-is-rich-structure-actually/16036#16036 Answer by Emerton for What is "rich structure", actually? Emerton 2010-02-22T06:20:56Z 2010-02-22T06:20:56Z <p>If one's intent is to understand the comments in Fearless Symmetry, then an investigation of the actual subject at hand (Galois theory and, more particularly, algebraic number theory) will be more revealing than an enquiry into generalities about the concepts of structure and richness.</p> <p>In this direction:</p> <p>Regarding Example 1/Question 2: Literally, the structure on the set of solutions is that it is a set equipped with an action of the Galois group (as was already noted by several people). </p> <p>Regarding Example 2/Question 1: There has <a href="http://mathoverflow.net/questions/2791" rel="nofollow">already been</a> an MO question about what number theorists mean when they speak of understanding the group $G_{\mathbb Q}$, which is relevant to this question too. In any event, in the quoted example, as in many similar statements in the literature, "structure of $G_{\mathbb Q}$" is a short-hand for a number of problems related to the study of $G_{\mathbb Q}$, first and foremost being the study of the representations of $G_{\mathbb Q}$ and their relationships to (i) automorphic forms and (ii) motives.</p> <p>Note that $G_{\mathbb Q}$ itself has to be thought of not just as a group, but as a group equipped with conjugacy classes of embeddings $G_K \hookrightarrow G_{\mathbb Q}$ for each completion $K$ of $\mathbb Q$ (so $K$ is $\mathbb R$ or $\mathbb Q_p$ for some prime $p$), whose images topologically generated $G_{\mathbb Q}$ (by Cebotarev density) in an extremely overdetermined way. </p> <p>The theory of representations of $G_{\mathbb Q_p}$ itself has a deep theory, involving $p$-adic Hodge theory among other tools, and this should be thought of as being included in the "rich structure" being alluded to.</p> <p>In summary: I think that such assertions are typically short-hand allusions to a deep and important (in the eyes of those making the assertion, at least) set of problems, techniques, and theorems related to the object at hand; that is the certainly the case in this instance. At least in the case of Example 2, they do not admit a superficial description in terms of some formal notion of "rich structure". </p> http://mathoverflow.net/questions/16003/what-is-rich-structure-actually/16040#16040 Answer by David Corfield for What is "rich structure", actually? David Corfield 2010-02-22T08:50:39Z 2010-02-22T08:50:39Z <p>A good case to look at would be Michiel Hazewinkel's 'star example' of a rich structure <strong>Symm</strong>, the ring of symmetric functions in a countably infinite number of indeterminates.</p> <blockquote> <p><strong>Symm</strong>, the Hopf algebra of the symmetric functions is a truly amazing and rich object. It turns up everywhere and carries more extra structure than one would believe possible. For instance it turns up as the homology of the classifying space <strong>BU</strong> and also as the cohomology of that space, illustrating its self-duality. It turns up as the direct sum of the representation spaces of the symmetric group and as the ring of rational representations of the infinite general linear group. This time it is Schur duality that is involved. It is the free $\lambda$-ring on one generator. It has a nondegenerate inner product which makes it self-dual and the associated orthonormal basis of the Schur symmetric functions is such that coproduct and product are positive with respect to these basis functions...<strong>Symm</strong> is also the representing ring of the functor of the big Witt vectors and the covariant bialgebra of the formal group of the big Witt vectors (another manifestation of its auto-duality)... </p> <p>As the free $\lambda$-ring on one generator it of course carries a $\lambda$-ring structure. In addition it carries ring endomorphisms which define a functorial $\lambda$-ring structure on the rings $W(A) = CRing(Symm, A)$ for all unital commutative rings $A$. A sort of higher $\lambda$-ring structure. Being self dual there are also co-$\lambda$-ring structures and higher co-$\lambda$-ring structures (whatever those may be).</p> <p>Of course, <strong>Symm</strong> carries still more structure: it has a second multiplication and a second comultiplication (dual to each other) that make it a coring object in the category of algebras and, dually, (almost) a ring object in the category of coalgebras.</p> <p>The functor represented by <strong>Symm</strong>, i.e. the big Witt vector functor, has a comonad structure and the associated coalgebras are precisely the $\lambda$-rings.</p> <p>All this by no means exhausts the manifestations of and structures carried by <strong>Symm</strong>. It seems unlikely that there is any object in mathematics richer and/or more beautiful than this one, and many more uniqueness theorems are needed. (<a href="http://arxiv.org/abs/0804.3888" rel="nofollow">Witt vectors. Part 1</a>: 7)</p> </blockquote> http://mathoverflow.net/questions/16003/what-is-rich-structure-actually/16042#16042 Answer by kakaz for What is "rich structure", actually? kakaz 2010-02-22T10:08:38Z 2010-02-22T10:08:38Z <p>In my opinion the richness of the structure is related to endomorphisms of such set. It i s note necessary the group of symmetry but definitely it has something in common to possible relations within elements of such set. Even if You cannot have symmetry within set, it may have rich structure, for example even if there is no inverse elements or identity, there may be many interesting properties. </p> <p><hr /></p> <p>Remarks: </p> <p>If You agree with above, it probably we may go further and try to define the measure for this "richness". For example You may try to construct some functors from given class of endomorphisms over structure to some predefined and known categories for example. Maybe there is possible to find something analogous to class of homotopy etc. in such construction? Probably it would be very interesting thing to define "richness invariants" which would be some constructions staying at some level whilst between similarly rich structures. </p> <p>Note that it is not that the number ( cardinality) of such endomorphism decide about richness, but rather its "strangeness". For example class of endomorphisms of general function between two complex planes is much bigger that class of conformal mapping of complex planes, but the last class is definitely more interesting than first one. The last one is too big so not very interesting...</p> http://mathoverflow.net/questions/16003/what-is-rich-structure-actually/16044#16044 Answer by Neel Krishnaswami for What is "rich structure", actually? Neel Krishnaswami 2010-02-22T11:19:36Z 2010-02-22T11:19:36Z <p>Regarding question 1: </p> <p>Formalizing the idea of richness of structure is very difficult. This is not because the question is inherently impossible to answer, but because many of the relevant questions are open problems in logic which do not yet have satisfactory explanations. As just one example, we don't have entirely satisfactory explanations of what the complexity of a proof is, which seems necessary to make the idea of rich structure a fruitful one. </p> <p>Concretely, let's restrict our attention to set equipped with structure, and then further restrict our attention to purely algebraic structures on a set -- that is, we posit that our set has a collection of operations whose equations are universally quantified equalities on the operations. Now, notice that for any such algebraic structure, the one-element set provides a trivial model. </p> <p>Of course, it's utterly absurd to say that the one-element set has rich structure because it's a model of all algebraic theories. The reason it's absurd to say such a thing, is because it's a model of all algebraic theories for trivial reasons -- in other words, there's a trivial, generic, proof that the one-element set satisfies all those equalities (namely, all functions into a one-element set are equal, by the extensionality of equality of functions). </p> <p>In order to rule out these boring counterexamples, we need a concept of the complexity of proofs, so that we have some formal way of saying that an equation is satisfied for an interesting reason. For example, we may wish to say that the natural numbers have nontrivial commutative monoid structure $(\mathbb{N}, 0, +)$, because the proofs of the associativity and commutativity of addition are not trivial (though of course they are very easy -- which is itself another idea that calls for formalization!). </p> <p>However, even the equality theory of proofs is very difficult, let alone being able to measure their relative complexities. The basic technology here is Gentzen's sequent calculus, and the basic question here is how to deal with lemmas (i.e., the "cuts" of his cut-elimination theorem). Namely, if we take a proof, and factor it into a series of lemmas, is it still the same proof? If we answer the question with a "yes", then we have a theory of proof which says we should compare the normal forms of proofs -- but it's easy to show that even in the propositional case, the presence of lemmas can make proofs doubly-exponentially smaller. It seems extremely weird to say that such a dramatic change makes no difference! If we answer the question with a "no", then some trivial rearrangements can cause us to declare two proofs not the same, which is also strange. </p> <p>One way of squaring this circle is to suggest that perhaps we should look at the <em>complexity</em> of proof-normalization, and equate two proofs when it only takes a small amount of work to go to a common normal form. However, this suggestion has the problem that we don't know how to do this. Perhaps the closest we can presently come to this is with Jean-Yves Girard's Geometry of Interaction, which gives a fixed point semantics to proof normalization, which can be used to get numerical estimates of the complexity of normalizing individual proofs. However, this is very much current research, and many basic questions about GoI remain open. </p>