The Balanced Centrifuge Problem

Next week I start a new position as Associate Dean for Faculty Development in the Georgia Tech College of Sciences.  One of the things I’m looking forward to is getting to know more faculty outside the School of Mathematics and learning about their research. My knowledge of biology, in particular, is rather woeful, but I love reading about the latest developments in Quanta Magazine and elsewhere.

The other day I took my 14-year-old daughter, who is hoping to study genetics, to visit the lab of a Georgia Tech colleague in the School of Biology.  During the visit we discussed how expensive it can be not just to purchase but also to maintain certain kinds of lab equipment, for example centrifuges.  This reminded me about a blog post I’ve been meaning to write for a long time now…

Back in 2011-12, I spent a year as a faculty member at UC Berkeley and I became friends with some biologists there.  One weekend afternoon I was chatting with a cancer researcher named Iswar Hariharan at a barbecue, and when he heard that I was a number theorist he told me about a problem he had been thinking about on and off for more than 15 years.   The problem concerns balancing centrifuges.

A crash course on centrifuges

A centrifuge, as you probably know, is a laboratory device used to separate fluids based on density.  The separation is achieved through centrifugal force by spinning a collection of test tubes at high speeds.  As Iswar explained to me, it’s very important to balance a centrifuge before operating it; running a centrifuge with an unbalanced load can permanently damage it.  A centrifuge is called balanced if the center of mass of the collection of test tubes coincides with the center of mass of the centrifuge itself.  For example, here is balanced configuration of 8 test tubes in a 20-hole centrifuge:

20-hole-centrifuge

There are also configurations of test tubes which are balanced, but less obviously so, such as this one with 13 test tubes and 24 holes:

balanced-centrifuge

If you spend a lot of time balancing centrifuges and have a mathematically curious mind, the following question might naturally arise:

Problem: For which pairs (n,k) with 1 ≤ k ≤ n can you find a way to balance k identical test tubes in an n-hole centrifuge?

This is precisely the question which Iswar started to think about, and in 1998 he arrived at a conjectural answer.  Before I tell you Iswar’s conjecture (which he described to me at the barbecue), let’s think about a few special cases to get a feeling for the problem.

Some special cases

If n=3 then you can only balance the centrifuge if k=3, and if n=4 you can balance for k=2 and k=4.

If n=6, then it’s easy to see that you cannot balance the centrifuge if k=1 or 5 but you can if k=2,3,4, or 6:

6-hole-centrifuge

If n=5 or 7, on the other hand, you can only balance the centrifuge if k=n.

It seems that the answer might have something to do with whether or not n is prime… Let’s look at some more examples.

If n=8, then you can balance the centrifuge if and only if k is even.

If n=9, you can balance for k=3,6, or 9.

If n=10, you can balance for k= 2,4,5,6,8 or 10.  Notice, for example, that if you wanted to balance the centrifuge with k=7, you could try to start with a balanced set of 5 test tubes (occupying every other slot) and then add two more in opposite holes, but there’s a problem: one out of each pair of opposite holes is already occupied!  We will call this the overlap problem.  It is in some sense the key subtlety in this problem.

If n=11, you can balance if and only if k=11.

If n=12, you can balance the centrifuge as long as k is not 1 or 11.

For a larger example: if n=21, you can balance if and only if k=3,6,7,9,12,14,15,18, or 21. For another illustration of the overlap problem, consider what happens when k=10.  You could try to take a balanced configuration of 7 test tubes (spaced every 3) and then add 3 more in the shape of an equilateral triangle, but you will find that it doesn’t work because of that damned overlap problem.

If you stare long enough at this data, and at similar data for other values of n, you might come up with the same guess which Iswar made.  I’ll give you a chance to stop and think about it before the spoiler which follows…

Iswar’s conjecture

Conjecture: You can balance k identical test tubes, 1 ≤ k ≤ n, in an n-hole centrifuge if and only if both k and n-k can be expressed as a sum of prime divisors of n.

For example, when n=21 and k=6 we have 6=3+3 and 21-6=15=3+3+3+3+3, and indeed the pair (21,6) can be balanced.  But when k=10, although 10=3+7 there is no way to express n-k=11 as a combination of 3’s and 7’s.  And the pair (21,10) cannot be balanced.

The conjecture predicts, for example, that if 6 divides n then every pair (n,k) with 2 \leq k \leq n-2 can be balanced (and when n \geq 5 this happens only if 6 divides n).  This is presumably why the number of chambers in most commercial centrifuges is a multiple of 6.

A solution to the problem

When I left the barbecue, I started thinking about Iswar’s conjecture and it occurred to me that a natural way to phrase the question mathematically was in terms of n^{\rm th} roots of unity.  In this language, the conjecture becomes:

Conjecture (alternate form): For any integers n ≥ 2 and 1 ≤ k ≤ n, one may find k distinct n^{\rm th} roots of unity whose sum is 0 if and only if both k and n − k are expressible as linear combinations of prime factors of n with nonnegative coefficients.

I worked out some special cases of the conjecture from this perspective; for example, if n=p is prime then the conjecture says that only k=n should be balanced, and this follows from the fact that the p^{\rm th} cyclotomic polynomial is irreducible.  But I couldn’t see how to deal with the general case.  However, I knew there were some papers in the literature about linear relations between roots of unity (for example, Mann’s theorem), so I decided to do a Google search.  And lo and behold, I found that Iswar’s conjecture had been proved in 2010 in this paper by Gary Sivek! I don’t think I would have found this reference if I hadn’t first translated the question into a problem about linear relations between roots of unity.

Sivek’s proof of the “if” direction is short and elementary.  For the “only if” direction, he uses a theorem of Lam and Leung, who proved the analogous result but where the k roots of unity are not assumed to be distinct.  The proof of Lam and Leung is based on a careful study of the kernel of the natural homomorphism (sending z to \zeta_n) from the group ring {\mathbb Z}[G], where G=\langle z \rangle is a cyclic group of order n, to the cyclotomic ring {\mathbb Z}[\zeta_n].

Denoument

I emailed Iswar telling him that the conjecture he had made back in 1998 was in fact correct, and he replied:

I am both happy and sad to get this email. On the one hand I am happy that I “guessed” the solution correctly (15 years ago). I am sad that I never acquired the mathematical skills to prove it myself!
It is funny how our minds get stuck on some problems over multiple decades.
Thanks for taking our conversation seriously.

Although it’s ultimately just a stimulating curiosity, and nothing which is going to cure cancer, I still think of this episode as a nice illustration of the intellectual cross-fertilization that can take place when scientists from different disciplines get together, whether at a research conference or a barbecue.  I hope that I’m able to encourage and foster such interdisciplinary friendships in my new role in the College of Sciences.  We’re off to a great start in 2018 in this regard with the new Southeast Center for Mathematics and Biology headquartered at Georgia Tech.

Concluding remarks

(1) Sivek, who it seems received his Ph.D. in mathematics from Berkeley in 2010, begins his paper by saying that his motivation came from the balanced centrifuge problem.  I would conjecture that the problem came to him indirectly through Iswar, but I don’t know for sure.

(2) It would be interesting to know for which k there is a unique way (up to rotational symmetry) to balance the pair (n,k).  Or more generally, exactly r ways (for some fixed positive integer r).

(3) There is in fact a relationship between this problem and something I’ve been thinking about recently in my own research.  I’m currently interested in “matroids over partial hyperstructures” such as partial fields and, more generally, tracts.  (This post is not the place to explain such things, but see this guest blog post which I wrote for the Matroid Union for details.)  If n is an even positive integer, the balanced centrifuge problem is equivalent to deciding for which k there is a k-term relation in the nullset N_G of the tract associated to the partial field (\mu_n, {\mathbb C}), where \mu_n is the group of n^{\rm th} roots of unity in {\mathbb C}.

 

7 thoughts on “The Balanced Centrifuge Problem

  1. There are fun higher dimensional analogues.
    There is a sequence of polyhedra which begin with a dodecahedron and whose limiting shape is an icosahedron and these can be projected to a sphere.
    there’s the 120-cell, again to be projected on the three sphere, as well as the other polychora in R4.
    there’s the polytope associated with E8, again to be projected onto a sphere.

    There are hyperboloids crossed by rulings which are Lorenz invariant.

    there’s the Klein quartic. eek?

    symmetry with respect to more complicated discrete subgroups of SO(n,R) feels like it might have a representation theoretic flavor

    Reply
  2. This is totally awesome! Please come back to my lab every week.

    Would you care to expand this problem to include hanging baskets? The scenario here would be to find the balanced solutions for (b,n,k) where b is the number of baskets with n holes each.

    Reply
  3. They should build centrifuges in characteristic 2. Then, for example, there would be solutions for n=7 and k=3,4. But, seriously, one can consider the problem in characteristic p>0 as well. Is the answer known there?

    Reply

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s