Monday, August 26, 2013

What are Galois Games?


How are math concepts named?

  1. After the people who was involved with it. Examples: The Cook-Levin Theorem, Goldbach Conjecture, Ehrenfeucht-Fraisse games,
    Banach-Tarski Paradox.
  2. A descriptive name:
    Examples: Chromatic Number; Girth of a graph (length of shortest cycle). This resembles the definition of Girth in English though I have only heard the word used in mathematics;
    Duplicator-Spoiler games.
  3. A name that conjures up a nice image. Examples: Dining Philosophers problem;
    The Monty Hall Paradox (though future historians will think he was a great Probabilist).
  4. Name may have very little connection to the concept. Example: The Pell equation.
I saw an article whose title was Greedy Galois Games. I wondered what this game could be.
  1. Do the players alternate picking polynomials and if the composition is solvable by radicals then (say) Player I wins.
  2. Did Galois invent some game?
The first game I thought of might be interesting; however, the paper was not about that. Nor was it about some game Galois invented. So---what is a Galois game? Aside from being a mathematician what else is known about Galois:
He died in a duel!
In the article Greedy Galois Games they study a DUEL between two BAD DUELISTS. The idea is that if both have prob of hitting p (and p is small) and they want to make it fair, first Alice shoots, then Bob shoots the min number of times so that the prob of Bob winning exceeds Alice's, then Alice shoots a number of times so that her prob of winning exceeds Bob's, etc. The paper ends up involving the Thue-Morse sequence. They are NOT using the name Galois the way we use Banach in Banach-Tarski Paradox, nor the way we use Monty Hall in The Monty-Hall Paradox. The fact that Galois was a mathematician has nothing to do with the naming,  The authors are using  Galois because he is a  famous duel-loser. They could have used Alexander Hamilton (who lost a Duel to Aaron Burr) and then called them Greedy Hamiltonian Games, in which case I would assume that the game involved
Hamiltonian cycles or Quaternions.

12 comments:

  1. You've never heard anyone use the usual sense of the word girth?

    ReplyDelete
  2. Alexander Hamilton

    ReplyDelete
  3. I fixed Hamilton. If Alexander Hamilton (or any Hamilton) did devise a game, would it be called a Hamilton game or a Hamiltonian game. I left it at Hamiltonian, but I don't know.

    Girth- correct, I have never heard anyone use it in what is supposed to be the usual sense. Could be the people I hang out with.

    ReplyDelete
  4. Here is at least one non-mathematical usage of the word "girth": http://diablo.wikia.com/wiki/Trang-Oul's_Girth.
    And here are some more: http://bnc.bl.uk/saraWeb.php?qy=girth

    ReplyDelete
  5. "The fact that Galois was a mathematician has nothing to do with the naming, except that the authors may be more aware of Galois as a famous duel-loser"

    truly hilarious! :)

    ReplyDelete
    Replies
    1. I know both the authors, and they are both first-rate. The fact that they chose a fanciful name highlighting one aspect of Galois' life certainly does not imply that they are unaware of his mathematical contributions.

      Delete
    2. Ah- I did not mean to imply the authors did not know that Galois made math contributions and have edited it so that it now does not imply that.

      I APPLAUD authors for their use of the term `Galois games' that both surprised and interested me- enough so that I read their article.

      Delete
  6. In the hopes that this will save someone from confusion: I believe girth is the length of the *shortest* cycle in a graph.

    Incidentally, the first time I learned the word girth was in a computer science class, but it wasn't about graphs. We had to write a function to compute the length and girth of a parcel to calculate shipping (or something like that).

    ReplyDelete
  7. I've always been partial to the Byzantine General's Problem.

    This is a perfect instance where you should use a fictional or historic incident. My vote would be Eugene Onegin.

    ReplyDelete
  8. From Allyn Jackson's "Comme Appelé du Néant —
    As If Summoned from the Void: The Life of Alexandre Grothendieck (Part 2)" (Notices of the AMS, 2004)

    ------------------
    Grothendieck had a flair for choosing striking, evocative names for new concepts; indeed, he saw the act of naming mathematical objects as an integral part of their discovery, as a way to grasp them even before they have been entirely understood. One such term is étale, which in French is used to describe the sea at slack tide, that is, when the tide is neither going in nor out.
    ------------------

    An early, celebrated usage of étale (that perhaps Grothendieck had in mind) is found in Victor Hugo's Toilers of the Sea (1883):

    ------------------
    La mer était étale, mais le reflux commençait à se faire sentir; le moment était excellent pour partir.

    It was slack water, but the tide was beginning to make itself felt, the moment was favorable for setting out.
    ------------------

    Colin McLarty's "The Rising Sea: Grothendieck on simplicity and generality" (2003) provides many further meditations upon mathematical naming as a creative process.

    ReplyDelete
    Replies
    1. William Burke's samizdat math-methods textbook Div, Grad, Curl are dead includes a meditation upon nomenclature:

      -------------------------
      Mathematician: When do you guys (scientists and engineers) treat dual spaces in linear algebra?

      Scientist: We don't.

      Mathematician: What! How can that be?
      -------------------------

      The point is that students who lack even a name for "dual" spaces are not cognizant of their lack.

      Such lacks have impeded the progress of entire STEM disciplines for decades and even centuries. Consider (e.g.) Saunders Mac Lane's lament:

      -------------------------
      "It has taken me over fifty years to understand the derivation of Hamilton's equations ... The point of this cautionary tale is the difficulty in getting to the bottom of it all.
      -------------------------

      Nowadays pioneers like Gromov, Gelfand, and Grothendieck (to cite only the "G"s!) are helping us to more natural namings, and thus more natural appreciations, and thus more natural extensions, across a vast span of 20th century STEM enterprises. To paraphrase (and extend) one of Feynman's meditations:

      -------------------------
      We are very lucky to live in an world whose elements we are still naming naturally. The age in which we live is the one in which we are creating a natural description of the laws of nature, and that day will never come again.
      -------------------------

      Delete