Skip to content

Guessing Conjectures

October 29, 2015

How well can we guess the right side of yes/no questions?


Takaaki Kajita and Arthur McDonald won the 2015 Nobel Prize in Physics for their discovery that neutrinos have mass. Although some physicists had shown as early as the 1950s that standard particle models could accommodate neutrinos with mass, there was no compelling reason for it. Moreover, the most-discussed terms for neutrino mass lack the desirable mathematical property of renormalizability. So most physicists of the last century guessed that neutrinos would be massless like photons are.

Today Ken and I wish to talk about guessing the answers to problems and conjectures in mathematics.

That neutrinos have mass came from experiments but in a way that remains in some sense “nonconstructive”—the experiments do not tell you how to measure the mass. Instead, Kajita and his team at Japan’s Super-Kamiokande neutrino detector discovered in 1998 that one of the three major types of neutrinos had different statistical frequency depending on whether they came through the earth or from overhead. McDonald’s team at the Sudbury Neutrino Observatory showed convincingly in 2001 that neutrinos were permuting themselves among the three types in transit from the sun to the earth. Together their results explained a long-mysterious huge dropoff observed by experiments that detected only the type chiefly produced in the sun. The type changes were known to be possible only if the terms for neutrino mass are present.

Of course mathematicians cannot do experiments to test conjectures—or maybe in some cases we can? But they do have a feel for how “models” of potential mathematical reality that haven’t been proved hang together. Some sides of conjectures confer more desirable mathematical properties on larger structures.

As a game for you—our readers—we will describe some problems that were solved, and invite you to guess the answers without looking up the solutions. We will give the solutions in our next post, which will have a Halloween theme. The answers won’t scare off interest in the conjectures because many matters related to them are still open. Likewise the matter of neutrinos: all we know is the sum of the three masses and the difference of the squares of two of them, and the experiments so far have not even distinguished which of two plausible mechanisms may cause the mass to arise.

The Angel Problem

The first problem is the Angel Problem, created by John Conway. Two players called the angel and the devil play on an infinite chessboard—always chess, hmmm. The angel can fly to any square that is within {k} king moves—that is, any place in the {(2k+1)\times(2k+1)} quadrant centered on her current location. The devil at each turn can put a block on any one empty square. The game is won by the devil provided the angel cannot move. Since the angel can fly over blocks but never onto them, this happens if and only when the devil takes the last unoccupied square in the angel’s current quadrant. The angel wins by surviving indefinitely.

Here is an illustration from the applet on Oddvar Kloster’s page on the problem—we’ve painted on the blue boundary for {k = 2}. The angel may move to any square within the blue quadrant except three that the devil has blocked. The picture also shows the devil blocking three squares further away in case the angel flies in that direction. The shading has to do with one side’s strategy—don’t look on his page yet for the answer.


The problem asks, Who wins the game?—and more particularly:

Is there a finite {k > 1} such that the angel wins?

For {k = 1} the angel is just a chess king and loses to a devil who plays entirely within a {32 \times 33} grid—note this is asymmetrical since the devil without loss of generality plays first. So {k} must be at least 2. A funny feature is that higher {k} effectively gives the devil more blocks per turn. The reason is that if the angel has a winning strategy, then she has one that never visits a square that was within a previous quadrant. If visiting that square is now optimal then so would have been visiting it earlier when the devil had blocked fewer squares. Thus she might as well be a Destroying Angel who bombs out every square of her quadrant other than the one she chooses at each turn. Larger {k} means more bombing of the same {\sim k^2} order as her greater mobility. Conway’s writeup shows that several natural simple strategies for the angel lose for every {k}.

The question is: Is there some {k > 1} that gives the angel eternal freedom? Or can the devil always build a clever wall starting far away that eventually encircles the angel? If you do not know the answer, which do you believe is true?

Four Others

{\bullet} Equitable Coloring.

A {k}-coloring of an {n}-vertex graph is a mapping {f: [n] \rightarrow [k]} such that for each “color” {j}, no two vertices {u,v} such that {f(u) = f(v) = j} are adjacent. The coloring is equitable provided for each {j \in [k]} the number of vertices {u} given color {j} is either {\lfloor n/k \rfloor} or {\lceil n/k \rceil}. That is, no two color classes differ in number by more than one vertex. If {k} divides {n}, so {n = rk}, then every color must be used exactly {r} times.

Rowland Brooks proved that every graph of degree {d} other than complete graphs and odd cycles has a {d}-coloring. The complete bipartite graph {K_{3,3}} has no equitable 3-coloring, though it has an equitable 2-coloring. The question is: Does every graph of degree {d} have an equitable coloring using exactly {(d+1)} colors?

{\bullet} Star Height

The star-height problem in formal language theory is the question of whether there is {k > 1} such that all regular languages have regular expressions that have at most {k}-fold nesting of Kleene stars. It was easy to show a no answer over alphabets of arbitrary size. The question is: Is there a bound on {k} if the alphabet is binary?

{\bullet} Scheinerman’s Conjecture

Edward Scheinerman conjectured in his 1984 PhD thesis that every planar graph can be represented as the intersection graph of a set of line segments in the plane. This is easy to see if you are allowed arbitrary curves in the plane, since you can replace a vertex of degree {d} by a curve that winds itself around in a {d}-pointed star. But doing it with straight line segments seems quite a challenge. We reproduce Wikipedia’s example for an 8-vertex planar graph:


The question is: Is it always possible? Note that the above example uses only lines with 4 orientations with no two segments of the same orientation touching. Such a graph can be 4-colored by making each orientation a separate color, so a yes answer using only 4 orientations implies the four-color theorem. But we are getting ahead of ourselves—is it possible at all?

{\bullet} Road Coloring Problem

Suppose we have a directed graph {G} in which every vertex has the same out-degree {d}. Let us use the same alphabet of {d} characters to label the {d} out-edges from every node. Then for every vertex {u} and string {x} of these characters, using successive characters of {x} as directions on which out-going “road” to take determines a unique path {P} of length {|x|} in the graph. If the path ends at a vertex {v} we write {P(u,x) = v}. If we get the same {v} for all {u}—even {u=v} itself—then {x = x_v} is a universal sequence of road directions to reach vertex {v}. For a particular {G} we can ask:

Can we assign {d} labels so that every {v} has a universal string {x_v}?

If {G} has no directed cycles then the answer is clearly no—you can never get to a source. If all cycles have even length then a parity argument shows no, and it works if all cycle lengths are divisible by some odd number as well. No assignment of labels will work. Are there other graphs for which no assignment will work? That is the question.

Open Problems

Without looking the answers up, can you guess them? We have stated the final italicized yes/no question in each one so that the numbers of ‘yes’ and ‘no’ answers are equitable.

[Qualified “most-discussed” before “terms” in first paragraph (see KWR comment in reply); “photons”–>”neutrinos” before “have mass” in first line of 3rd paragraph; gave fuller statement of knowledge of masses at end of intro]

12 Comments leave one →
  1. October 29, 2015 6:45 pm

    Similar to equitable coloring there are “Guessing Conjectures” for k-equitable labeling problems e.g.,

  2. October 29, 2015 9:04 pm

    I’m surprised that in your sentence “Of course mathematicians cannot do experiments to test conjectures—or maybe in some cases we can?” you didn’t link to your argument presented here: Btw, any news about this type of arguments?

  3. October 30, 2015 5:25 am

    Scheinerman’s Conjecture.

    Yes it is possible.

    An idea of a proof (draft):

  4. hul permalink
    October 30, 2015 8:59 am

    “That photons have mass came from experiments…”

  5. October 30, 2015 9:10 am

    Great analogy with conjectures in physics. Just to mention a typo

    “That photons have mass came from experiments”

    Of course you wanted to say neutrinos and not photons here (photon cannot have a mass since they travel at the speed of light)

    • October 30, 2015 3:18 pm

      Thanks, hul and “Me”. That kind of twiddle-typo can be hard to detect, and it happened right after I was wrapped up deciding whether [not] to mention gluons alongside photons as being massless.

  6. Oren Cheyette permalink
    October 30, 2015 11:41 am

    “the terms for neutrino mass lack the desirable mathematical property of renormalizability”

    This is incorrect. It’s well understood how to include a renormalizable neutrino mass term in the standard model either as a “conventional” Dirac mass or as a Majorana mass. Having worked (briefly and very long ago) on projects to measure the mass, I don’t think that most physicists thought neutrinos were massless before 1998. Generally, there’s no fundamental difficulty with having massive fermions in a renormalizable theory – QED being the prototypical example.

    The Wikipedia page on the Seesaw Mechanism has a good explanation of the restrictions imposed by the standard model’s gauge symmetry, which is required for renormalizability. Though I’m long gone from the field, I think this approach is widely believed to be the correct explanation for the tiny observed neutrino masses.

    Klinkhammer’s paper (at the link) has a conditional clause after the comma in the first sentence: he’s writing about another way to get neutrino masses with different field content.

    The analogy to non-constructive proofs is amusing but perhaps misleading. It’s true that the oscillation experiments prove the masses are non-zero without directly measuring their values, but they don’t leave them completely undetermined. Aside from showing that the values are all non-zero, they and related experiments give bounds and estimates for the differences among the squared masses. This is indirect and underdetermined, to be sure, but not the same as “it’s nonzero but we have no other information”.

    • October 30, 2015 3:48 pm

      Thanks, Oren—when one is writing from outside it is great to have help from inside. I must say, though, that the whole first page of Klinkhammer’s paper sure sounds definitive about non-renormalizability and it was referenced for that point. This Physics StackExchange item has a comment by “pho” aligning with what you say, but a more prominent and seconded comment otherwise.

      Looking further, these 2012 course notes by Yossi Nir at Weizmann seem to consider renormalizable neutrino masses and flat-out reject them saying “renormalizable {\implies m_{\nu} = 0}” on page 2. For a middle position, I’ve decided to lean on the textbook Neutrino Physics by Bellotti-Dedais-Strolin, and I read its page 9 as follows: “Our summary on neutrino masses in renormalizable extensions of the Standard Model is as follows: … … None of those possibilities looks particularly attractive, for the reasons discussed above. Let us now turn our attention to [models] admitting some non-renormalizable corrections.” Hence what I’ve done is hedged by inserting “most-discussed terms”. Let me know if you have weightier sources that should induce me to drop the point.

      The “most physicists guessed zero mass” was firstoff my own impression from the 1980s and 1990s. The Nobel Prize announcement itself said so, as I noted from this source: “For more than half a century, we used to think that neutrinos are massless,” Olga Botner, a member of the Nobel Committee for Physics, said at the announcement Tuesday morning. “The discovery of neutrino oscillations at the turn of the millennium upset our notions.” I should hope that’s different from reporters saying so… Well I wonder if this was ever included on one of the polls one reads about having been taken at physics conferences… I’ve left it as-is for now. On your last point, I did mention at the end of the intro that we know the squared differences—now I realize it’s just one squared difference and there’s a good lower bound as well as upper bound on the sum of the three masses, so I’ve edited accordingly. [I wrote the intro and fleshed out Dick’s description of the problems.]

      • Oren Cheyette permalink
        October 31, 2015 1:08 pm

        Hi Ken – I’ve sent a reply by email. I couldn’t condense my points down to suitable comment size…


      • November 3, 2015 5:41 am

        Ken and Oren, very interesting discussion. it will be great if you can share Oren’s last comments.


  1. Ghosts in Princeton | Gödel's Lost Letter and P=NP
  2. Thanks for Additivity | Gödel's Lost Letter and P=NP

Leave a Reply

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

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

Connecting to %s