To prove and to conjecture

A recent post on Gödel’s Lost Letter and P=NP invites readers to comment on the dilemma: should you share the stuff you are currently working on, or is the risk of someone finishing it off before you do too great?

I have only skimmed the responses, but I get the impression that the fault line runs mostly between mathematicians and computer scientists, with the mathematicians in favour of sharing. In particular, there are some very telling comments by Tim Gowers, a real pioneer in collaborative mathematics who is running a number of “polymath” projects on his blog.

Perhaps the only sour note in the career of Paul Erdős was the incident involving the “elementary” proof of the Prime Number Theorem. “Elementary” in this sense does not mean “easy”; it just requires that the proof doesn’t use the machinery of complex analysis (crucial in the first proof by Hadamard and De La Vallée Poussin in 1896). Erdős and Atle Selberg were at the IAS in Princeton (if I recall the story correctly) when Selberg was working on the proof. He told Erdős about it, and Erdős was able to fill in a gap in the proof. As he always did, Erdős immediately started telling people about it, and it was reported back to Selberg as “Erdős and somebody have an elementary proof of the Prime Number Theorem”. Selberg immediately withdrew from the collaboration and published on his own. If his intention was to stop Erdős from beating him to it, he more than succeeded; when I learned Number Theory as an undergraduate, I was told that the elementary proof was by Selberg.

Later in my career, I met Erdős (as described elsewhere on this blog). I find it very difficult to believe that he had any underhand intentions in this case. One of his best-known sayings is,

The purpose of life is to prove and to conjecture.

Now it is impossible to make a good conjecture unless you have thought very deeply about the subject concerned. So the enormous number of conjectures he made give evidence of the fact that he was prepared to share his ideas even in the earliest stages of the research. Indeed, as many people have testified, he was good at posing problems which were very well judged for their recipients, hard enough to be challenging without being daunting, and many mathematicians’ careers were kick-started by working on an Erdős problem.

Another thing I believe is that mathematics is so broad that the chance that there is someone out there with exactly the right idea to finish off your incomplete work is extremely small. When you are working on a problem, it expands to fill your whole universe, but it is still probably fairly trifling to most other mathematicians. (One of the commonest mistakes that students make, giving seminar talks for the first time, is to assume that their audience will be just as much on top of the subject as they are. It just isn’t so!)

Anyway, I am not in the league of Erdős when it comes to conjecturing (or indeed, proving!), but I have made a few conjectures which have subsequently been settled by other people. Here are some.

  • A conjecture that a random element of the symmetric group belongs to no proper transitive subgroup except the symmetric and possibly the alternating group was proved by Tomasz Łuczak and László Pyber, Comb. Probab. Comput. 2 (1993), 505-512.
  • A conjecture with Masao Kiyota on sharp characters whose values are zero and a family of algebraic conjugates was proved by Masao Kiyota and Sôhel Nozawa, J. Algebra 161 (1993), 216-229; Dean Alvis has generalised their result in Commun. Algebra 21 (1993), 535-554.
  • A conjecture that universal sum-free sets have density zero was proved by Tomasz Schoen, Combin. Probab. Comput. 8 (1999), 277-280.
  • A conjecture with Cheryl Praeger on parameters of block-transitive, point-imprimitive 3-designs has been proved by Avinoam Mann and Ngo Dac Tuan, Geom. Dedicata 88 (2001), 81-90.
  • The Cameron-Erdős conjecture has two different proofs: by Ben Green, Bull. London Math. Soc. 36 (2004), 769-778; and by Alexander Sapozhenko, Discrete Math. 308 (2008), 4361-4369. [The conjecture stated that, if f(n) denotes the number of sum-free subsets of {1,…,n}, then f(n)/2n/2 tends to a limit ce or co when n tends to infinity through even or odd values respectively, and also gave formulae for the two constants.]
  • A conjecture (really Donald Keedwell’s, refined by me) on simultaneous edge-colouring has been proved by Rong Luo, Wenan Zang, and Cun-Quan Zhang, Combinatorica 24 (2004), 641-657.
  • An old conjecture that an algebra associated with the action on finite sets of an infinite permutation group with no finite orbits is an integral domain has been proved by Maurice Pouzet, Theor. Inform. Appl. 42 (2008), 83-103.
  • A conjecture with Robert Liebler on collineation groups of projective spaces with equally many point and line orbits has been proved by John Bamberg and Tim Penttila, Commun. Algebra 36 (2008), 2503-2543.
  • A conjecture with John Sheehan that a vertex-transitive cubic graph has a large semiregular group of automorphisms has been proved by Cai Heng Li, Proc. Amer. Math. Soc. 136 (2008), 1905-1910.
  • A conjecture on the base size of primitive permutation groups has been proved by Tim Burness and various co-authors (R. M. Guralnick and J. Saxl, E. A. O’Brien and R. A. Wilson, M. W. Liebeck and A. Shalev) ina number of papers.
  • A conjecture with C. Y. Ku on the second-largest set of intersecting permutations has been proved by David Ellis.

On the other hand, here are some refuted conjectures:

  • A conjecture on the local compactness of cofinitary subgroups of the infinite symmetric group was refuted by Greg Hjorth, J. Algebra 200 (1998), 439-448.
  • A strengthening of Isbell’s conjecture: Given a prime p and a natural number d, there is a number k such that a finite p-group of permutations with d orbits, each of size at least pk, contains a fixed-point-free element. This has been disproved by Eleonora Crestani and Pablo Spiga.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics. Bookmark the permalink.

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 )

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