MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## What is “rich structure”, actually? [closed]

An ubiquitous claim in mathematics is that such-and-such mathematical entity has a rich structure or more structure than another one. Most oftenly the entity is a structure - a set explicitly equipped with a structure, i.e. a graph, a group, etc. - but often enough it's just a set not explicitly equipped with a structure.

Examples:

1. Ash/Gross in Fearless Symmetry claim that the solution set [sic!] of a polynomial equation has "more structure" than just its cardinality (p.66).

2. They state on the other hand that the absolute Galois group $G_{\mathbb Q}$ "has a rich structure - much of it still unknown" (p. 87).

Two questions arise (for the beginner):

Question #1: 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 richness?

The only answer that comes to my mind is something like the diversity of non-isomorphic (induced?) sub-structures. Is this formalizable?

Question #2: 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?

I guess I have to presume 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).

-
I think this is way too philosophical and discussion-y to work on MO. I don't think it's a question that "has an answer" (i.e. it's really bait for a discussion). I'd vote to close it as "not a real question", but I don't want to close unilaterally. If it acquires two or three other votes to close, then I'll vote to close too. – Anton Geraschenko Feb 22 2010 at 0:35
Why is there a rush to label questions as ones which might lead to a discussion? If someone gives a concrete example of what is meant when someone says "rich structure," is that so horrible? – Douglas Zare Feb 22 2010 at 0:56
It's not my question, but I'd like to see the answers, not to have this closed out of a bizarre fear that someone might try to discuss something instead of answering the question. I'm aware of the limitations of MO. – Douglas Zare Feb 22 2010 at 1:04
@Douglas: while what you're saying sounds reasonable, I disagree with it. If you want to discuss it further, let's do it on meta, where this topic has already received a lot of attention. Here is another one of my posts that elaborates on why we should close questions at all: meta.mathoverflow.net/discussion/130/2/…. Please also have a look at this thread: meta.mathoverflow.net/discussion/155/…. – Anton Geraschenko Feb 22 2010 at 1:19
It seems to me that the most honest answer is that "richness of structure" is used only informally by mathematicians: like a deep theorem or an elegant proof, it involves an aesthetic judgment on the part of the speaker. You could try to create some quantitative measure of richness of structures, in which e.g., richness is non-increasing under forgetful functors, but this is not what people mean when they use the term. Thus I agree with Anton G. that the question is not a good one for MO: it is not possible to decide whether a given answer is correct. – Pete L. Clark Feb 22 2010 at 4:21

## closed as subjective and argumentative by Reid Barton, Pete L. Clark, S. Carnahan♦, Qiaochu Yuan, Scott Morrison♦Feb 23 2010 at 6:07

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).

-
 Then the question goes for the richness-of-structure of the group of symmetries. – Hans Stricker Feb 22 2010 at 0:27 No, I think the claim is "more structure = smaller automorphism group" (which seems pretty reasonable, at least in these cases). – Reid Barton Feb 22 2010 at 1:14 So it's just a matter of the size of the automorphism group? But cannot two groups of the same size have different complexities? – Hans Stricker Feb 22 2010 at 8:40 Clearly it's the partial ordering by inclusion, not the size, that's relevant here. – Scott Morrison♦ Feb 23 2010 at 6:09

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.

1. 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.

2. 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.

Granted these are not literal interpretations, but I think they are in mind when someone makes a statement about richness of structure.

-

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.

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.

-

I'm answering with a stub that I hope others will fill out. Please feel free to edit this.

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.

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.

-

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.

In this direction:

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).

Regarding Example 2/Question 1: There has already been 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.

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.

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.

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".

-

A good case to look at would be Michiel Hazewinkel's 'star example' of a rich structure Symm, the ring of symmetric functions in a countably infinite number of indeterminates.

Symm, 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 BU 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...Symm 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)...

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).

Of course, Symm 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.

The functor represented by Symm, i.e. the big Witt vector functor, has a comonad structure and the associated coalgebras are precisely the $\lambda$-rings.

All this by no means exhausts the manifestations of and structures carried by Symm. 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. (Witt vectors. Part 1: 7)

-
 Sounds promising, I will try to get into it. I also found very interesting your post on Mathematical robustness at the n-Category Café: golem.ph.utexas.edu/category/2008/11/… – Hans Stricker Feb 22 2010 at 10:02 I think maybe arxiv.org/abs/0810.5691 might be a more interesting reference. I would really like to thank you though for pointing out the Witt Vector article, I have been trying to get into them. – Sean Tilson Mar 3 2010 at 20:09

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.

Remarks:

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.

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...

-

Regarding question 1:

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.

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.

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).

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!).

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.

One way of squaring this circle is to suggest that perhaps we should look at the complexity 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.

-
 Very interesting note. As regards to complexity of proofs: I check that in Mizar proof assistant, the longest proofs are usually assigned to not-very-interesting or most-known theorems. Of course it s not so simple to check just size of certain proof to say something about general complexity, but in other way it is interesting to see it on certain example. – kakaz Feb 22 2010 at 11:51