Carries, shuffling, and cocycles

Last week we were treated to a lovely lecture by Persi Diaconis. As he so often does, he started with an elementary question: how many carries do you expect if you add n numbers in base b? From there he reached de Rham cohomology and Szemerédi’s Regularity Lemma.

I want to explain here the message of the first part of the talk, and then take a slightly sideways look at the second part.

Carries

Suppose that you are adding n numbers in base b. They are big numbers, so we just examine what happens at a given stage of the process. So rather than worry about what it means for the numbers to be random, we just assume that each digit is chosen randomly from the set {0,1,…b−1}.

The carry at each stage can be any of the numbers 0,1,…n−1. And it depends on the random digits we are looking at and the carry from the stage before. So we have a Markov chain, a random process where the only dependence of what happens this time on the past is what happened last time. Thus, the process is completely specified by a n×n matrix P, whose (i,j) entry is the probability that the carry this time is j given that it was i last time. The entries of P depend only on b.

A formula for the matrix was calculated by John Holte in a paper in the American Mathematical Monthly in 1997, entitled “Carries, combinatorics and an amazing matrix”. He gives many properties of the matrix as well. A striking thing about the matrix is that its entries involve Eulerian numbers, which are connected with permutation statistics. On seeing this, Persi Diaconis and Jason Fulman immediately thought, “Shuffling!”

Shuffles

There is a standard model of the riffle shuffle, which is a good approximation of the way ordinary people actually shuffle cards. Given a pack of n cards, you first cut the pack into two parts of sizes c and nc, where c is chosen according to a symmetric binomial distribution (with probability 1/2). That is, the probability of cutting c cards into the first part is equal to the probability that a uniform random subset of the cards has size c, even though the first part is not a random subset. (So the size of the first part is close to n/2, with standard deviation proportional to the square root of n.) Then you drop cards one at a time from the two parts, the probability of dropping a card from a given part being proportional to its current size. (So if at some stage the parts have a and b cards, the probability of the next card coming from the first part is a/(a+b).)

Of course, one shuffle does not produce a very plausible random permutation, since the resulting permutation is the union of two increasing subsequences. How many shuffles are needed? The remarkable result of Bayer and Diaconis is that, for a pack of 52 cards, seven shuffles are necessary and sufficient. In general, the “variation distance” of the shuffled pack from the uniform distribution remains very close to 1 until a well-specified point, when it leaves 1 superexponentially fast, and then tends exponentially to 0 (roughly halving with any new shuffle).

The description can be extended to a riffle shuffle with b parts: in the first stage, use the multinomial distribution to choose the size of the parts; at the second, proceed exactly as before.

A descent in a permutation is just a place where the value is greater than its right-hand neighbour. So the permutation 236514 has two descents, in the third and fourth positions. The number of descents of a permutation of {1,2,…n} can be 0,1,…n−1, and the Eulerian numbers give the numbers of permutations with given numbers of descents.

Diaconis and Fulman proved the following remarkable result:

The numbers of descents in the permutations obtained by successive riffle shuffles (with b piles) of a pack of n cards follows a Markov chain, whose transition matrix is identical to the matrix describing the numbers of carries when n random numbers in base b are added.

It is not at all obvious that the number of descents after a shuffle depends on the order before the shuffle only through its number of descents. I don’t know a neat way to see this, though I suspect that Persi does.

The paper by Diaconis and Fulman is also in the American Mathematical Monthly, in 2009.

Cocycles

Nice stuff, but Persi said more in his talk, and it is this I want to turn to now. Let us return for a moment to the case where we are only adding two numbers in base b. The numbers being added are elements of the group Z of integers. The units digits tell us which coset of the subgroup bZ they belong to. If Z were the direct product of bZ with Z/bZ, then we could add the units digits independently of the rest, and no carries would be needed. So carrying reflects the non-splitting of this group extension. Indeed, the carry is a function from Z/bZ×Z/bZ to bZ (except that we have normalised by dividing through by b), and indeed it is precisely a 2-cocycle.

If homological algebra and algebraic topology is a closed book to you, bear with me. If I explained everything here, this post would be far too long; but the picture is this. A cocycle is just a “fudge factor” to allow for the fact that, in a group extension, we cannot in general do the group operation in the normal subgroup and the factor group independently. We are allowed to change coset representatives, which has the effect of changing the cocycle by a coboundary. The set of cocycles differing from one another by coboundaries is a cohomology class.

So it would be nice if we could reduce the number of pairs of arguments where the cocycle is non-zero (or maybe, for other applications, the number of values taken by the cocycle). In general, the first question is:

Given a cohomology class, what is the smallest number of non-zero values of a cocycle in the class?

For integer addition, changing the cocycle in a class corresponds to using a different set of digits. For the usual choice 0,1,…b−1, about half the pairs of digits will result in carrying 1. The optimal solution is to use balanced digits, which roughly halves the number of non-zero carries. For b=10, this means using the digits −4,−3,…0,1,…5.

Seidel minimality

Unexpectedly and remarkably, a similar problem comes up in quite a different context.

First some Euclidian geometry. Choose n points in general position in the plane. There are n(n−1)(n−2)/6 triangles that can be formed using these points as vertices. Boros and Füredi showed that there is a constant c2 such that there exists a point contained in at least a proportion c2 of these triangles. (In fact, the best possible value is c2 = 2/9). Bárány showed that a similar result holds for d-dimensional space, but the exact value of the constant cd is not known for d ≥ 3.

Gromov gave a combinatorial argument for finding a lower bound for cd. It depends on solving a “minimum weight of a cocycle” problem in all dimensions up to d, but the nature of the bound means that an improvement to any of these values will give an improved bound for cd. Lukáš Mach talked about this at the Magdeburg conference I went to a couple of years ago.

The case that has received the most attention is d = 2, which can be interpreted in graph-theoretic terms. Let me briefly repeat something from a recent post. Given a graph G on vertex set X, the operation of Seidel switching G with respect to a subset A of X involves changing all edges between A and its complement into non-edges, and all non-edges into edges, while leaving edges within or outside A unaltered. This generates an equivalence relation on graphs on vertex set X, whose equivalence classes are called switching classes.

A graph G is called Seidel-minimal if it has the minimum number of edges in its switching class; equivalently, if for any cut, the number of non-edges crossing the cut is at least as great as the number of edges crossing the cut.

Let T be the set of triples of vertices carrying an odd number of edges of G. Then T is unaltered by switching, and so is an invariant of the switching class. Indeed, a set of triples comes from a switching class in this way if and only if it has the property that any four points contain an even number of triples in the set.

Now Gromov’s function φ2(x) is defined to as follows: consider all switching classes whose associated set of triples has density at least x (among all triples); find the edge densities of the Seidel-minimal graphs in these switching classes and take the smallest; now take the limit inferior as the number of vertices goes to infinity.

This definition takes a bit of swallowing, but better lower bounds for this function would improve the lower bounds for the cd in every dimension. This can be found in a paper of Král’, Mach and Sereni on the arXiv (number 1108.0297).

It is also not clear what this has to do with cocycles. For this, I would need to give the algebraic topology formulation rather than the homological algebra formulation, and this post is already far too long. Roughly, a graph can be regarded as a binary function of two variables, which is our cocycle; switching is adding a coboundary; so Seidel-minimality is an instance of the minimum-weight cocycle in a cohomology class.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s