April 12, 2007

Structure and Pseudorandomness

Posted by David Corfield

Terence Tao has written three delightful posts, starting here, detailing his views delivered at the Simons’ lectures at MIT on the relationship between structure and pseudorandomness in mathematics. We read

Structured objects are best studied using the tools of algebra and geometry.

Pseudorandom objects are best studied using the tools of analysis and probability.

In order to study hybrid objects, one needs a large variety of tools: one needs tools such as algebra and geometry to understand the structured component, one needs tools such as analysis and probability to understand the pseudorandom component, and one needs tools such as decompositions, algorithms, and evolution equations to separate the structure from the pseudorandomness.

From this position, what do we make of ($n$-)category theory? Is it merely an attempt to deepen our grasp on what is structural in mathematics, and as such it helps us with the whole to the extent that it throws into clearer relief what is pseudorandom?

Just as Tao illustrates hybridness by way of the prime numbers, would it be profitable to view examples of ($n$-)categories as hybrid?

Posted at April 12, 2007 3:40 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1238

Re: Structure and Pseudorandomness

These days I’m spending a lot of time hybridizing $n$-category theory and gauge theory, to get higher gauge theory. To do this hybridization, it’s nice to ‘internalize’ concepts. For example, a (strict) Lie 2-group is a kind of hybrid of a Lie group and a category. Using internalization, we can define it as ‘a category internal to the category of Lie groups’. There are a lot more examples in section 2.1 here. There are also some important subtleties not mentioned here!

Anyway, ‘internalization’ and ‘enrichment’ are two basic methods of forming hybrid concepts in $n$-category theory.

Posted by: John Baez on April 12, 2007 9:51 PM | Permalink | Reply to this

Re: Structure and Pseudorandomness

Wouldn’t this be more an example of a blending of algebraic structures, i.e., a movement towards yet richer algebraic structure? Tao seems to be interested in what escapes structural description.

Chris Hillman discusses something relevant in the last section (from p. 10) of What is Information? He gives a series of lessons, from

Lesson 1. The existence of “mathematical structure” in an object may mean that it can be specified more compactly than would otherwise be the case.

to

Lesson 8. The existence of symmetries in a subset $A \subset X$ usually means that we can describe $A$ much more efficiently than would otherwise be the case, by naming the group of symmetries and then describing how to pick out $A$ from among the other subsets invariant under the group.

Posted by: David Corfield on April 13, 2007 11:21 AM | Permalink | Reply to this

Re: Structure and Pseudorandomness

Okay — I didn’t notice you were asking specifically about hybrids of ‘structured objects’ and ‘pseudorandom objects’.

That’s not the kind of hybridization I want to think about right now. I’m having too much trouble understanding structured objects to want to throw pseudorandomness into the mix. But, as you note in your example of homotopy groups of spheres, it may sneak in uninvited! So, I’m glad someone is thinking about this stuff.

Posted by: John Baez on April 13, 2007 6:15 PM | Permalink | Reply to this

Re: Structure and Pseudorandomness

Linking the presence of structure in an object to the compactness of its specification, as Hillman does points us to the work in learning theory on ‘Minimum Description Length’.

Peter Grünwald, whom I shall meet next month in Amsterdam at the FotFS VI conference, has an excellent 80 page tutorial on Minimum Description Length. Note that on page 6 he compares three binary strings which, as indicator functions of subsets of $\mathbb{N}$, would correspond to: an arithmetic progression, a random subset of density 1/2, and, a random subset of a lower density.

Now, Tao’s illustrations of structure, pseudorandom, hybrid are: an arithmetic progression, a random subset of density 1/2, and, the primes.

Grünwald is illustrating the idea of ‘Learning as Data Compression’. There’s an interesting circle of ideas here.

Posted by: David Corfield on April 13, 2007 11:40 AM | Permalink | Reply to this

Re: Structure and Pseudorandomness

Another tangential comment: you mention “what is pseudorandom” although I think there’s two levels here. Firstly there’s structures which are pseudorandom and those which we currently “probe” by pseudorandom/ensemble methods, and for which we don’t know where on the spectrum of pseudorandomness they lie. Eg, Shannon’s noisy channel coding theorem is proved in an ensemble-based way, but how much is that “a particular proof strategy” and how much is “pseudorandomness” an unavoidable part of coding. (Clearly creating an output stream full of “non-degenerate” correlations between elements of the input stream is a key, but is the pinacle of this pseudorandom or an intricate structure that appears random when you don’t look at it right? There’s also something I remember reading – but not where – that maybe most mathematical objects are pseudorandom but there’s a reverse “law of large numbers” that the problems humans can actually think about have so few “degrees of freedom” that they can’t not have structure.) There are numerous examples in computer science, particularly involving graph theory, where an object O of type T satisfying property P is desired and the overwhelming proportion of objects in T satisfy P yet all the imagined deterministic techniques for constructing such an object don’t work (presumably because they’re too simplistic to capture the desired property) and yet random generation is an easy, effective generation strategy.

The relevance to your point about learning is that you can clearly represent “this is a pseudorandom integer sequence s.t. its density is 1/2” much more compactly than an instance “0,8,9,…”, but how can you determine that this property is all that matters about the sequence, rather than say that it has density 1/2 and that it defines the topology of a multi-holed manifold that’s relevant because…? (This is clearly a non-sense example.) Of course, for finite learning examples you can perform cross-validation and argue that you want to learn what you can support from the data, but clearly as more general mathematical question is a better answer is desired.

Posted by: dave tweed on April 13, 2007 10:40 PM | Permalink | Reply to this

Golomb comment; Re: Structure and Pseudorandomness

Solomon W. Golomb told me, circa 1972, that what’s strange about Coding Theory, in the Shannon Communications Theory context, is that one finds exact results with probability theory and analysis, and approximate results with Finite Fields and Galois Theory. So that’s a weird hybrid of structured and pseudorandom.

Speculation on consciousness in this may be found in Minimumum Description Length theories, in Doug Hofstadter’s Strange Loops, and in Greg Chaitin. I suspect that both the objects of consciousness and the probes of consciousness are hybrid, and correlated.

Posted by: Jonathan Vos Post on April 15, 2007 7:14 AM | Permalink | Reply to this

Re: Structure and Pseudorandomness

Those are hybrid concepts that John mentioned, but not in the sense that (I think) Terry Tao was talking about.

They’re just hybrids between a structured thing and another structured thing.

On the other hand, I think it’s likely that, sooner or later, people are going to start moving into topology with ideas of pseudorandomness.

Analytic methods have been great for studying the long-term behaviour of the primes. The long-term behaviour of, say, stable homotopy groups of spheres looks like something which could be studied analytically.

I’ve no idea how on earth to do it though. :-)

Posted by: James Cranch on April 13, 2007 11:58 AM | Permalink | Reply to this

Re: Structure and Pseudorandomness

Is there anything known about the pseudorandomness of these stable homotopy groups, or the unstable ones? Something like what remains after pieces of structure are removed, as with the ‘renormalization’ of the odd primes when mapped to (p - 1)/2, see p. 22 of The Dichotomy between structure and randomness.

Posted by: David Corfield on April 13, 2007 3:23 PM | Permalink | Reply to this

Re: Structure and Pseudorandomness

I’ve never heard any results about pseudorandomness of homotopy groups of spheres. But, pseudorandomness is related to computational complexity. So, this is interesting:

• David Anick, The computation of rational homotopy groups is #P-hard, in Computers in Geometry and Topology, ed. Martin Tangora, Lecture Notes in Pure and Applied Mathematics, vol. 114, Decker, New York, 1989.

And also this, which I just bumped into:

Posted by: John Baez on April 14, 2007 9:36 PM | Permalink | Reply to this

Re: Structure and Pseudorandomness

No, I don’t think anything is known which could be interpreted as saying that the stable homotopy groups of spheres have pseudorandom properties.

The philosophy is that, if you try to find certain sorts of patterns in the stable homotopy groups of spheres, and fail, then it could of course be because you’re stupid and lazy, but after a while you have to consider the alternative possibility that they have no such patterns.

I don’t even think the correct language exists to phrase such statements yet.

Posted by: James Cranch on April 15, 2007 11:17 PM | Permalink | Reply to this
Read the post The Two Cultures of Mathematics
Weblog: The n-Category Café
Excerpt: Part of what intrigues me about reading Terence Tao's blog is that he displays there a different aesthetic to the one largely admired here. The best effort to capture this difference is, I believe, Timothy Gowers' essay The Two...
Tracked: April 17, 2007 10:16 AM

Post a New Comment