User gowers - MathOverflow

Answer by gowers for Are there any good websites for hosting discussions of mathematical papers?

2013-06-19T08:43:21Z

Time to mention the Selected Papers Network: https://selectedpapers.net

Are there very strongly pseudorandom permutations?

2013-06-18T14:14:56Z

A pseudorandom permutation can be defined formally as a function $\phi$ from $\{0,1\}^k\times\{0,1\}^n$ to $\{0,1\}^n$ such that for every $x\in\{0,1\}^k$ the function $\phi_x:y\mapsto\phi(x,y)$ is a bijection. The difficulty of distinguishing between a random permutation of the form $\phi_x$ and a purely random permutation of $\{0,1\}^n$ is defined roughly as follows. The function $\phi$ has hardness at least m if for every algorithm $A$ that takes at most $m$ steps in the worst case and has access to an oracle that tells it values $\pi(y)$ of a given permutation $\pi$ whenever it wants to know them (taking, say, one step to do so), the probability that $A$ outputs 1 when $\pi$ is a random $\phi_x$ differs from the probability that $A$ outputs 1 when $\pi$ is a fully random permutation by at most $m^{-1}$.

A celebrated result of Luby and Rackoff shows that pseudorandom permutations of superpolynomial hardness exist if pseudorandom functions of superpolynomial hardness exist. I won't bother here to explain what a pseudorandom function is, since this question is aimed at people who already know. What I would like to know is whether under suitable assumptions there are pseudorandom permutations of hardness $2^{Cn}$ for arbitrarily large $C$. I don't mind if $k$ is bigger than $n$. It might at first seem a silly question, since one can look at every single value that $\pi$ takes. But that's fine by me. For this question, the oracle is no longer needed, since one can just think of the function as a gigantic table of values. Even given those values, it doesn't seem easy to distinguish between a pseudorandom permutation and a random one.

This question is motivated by thoughts connected with Razborov and Rudich's famous Natural Proofs paper, where they consider a pseudorandom function of very large hardness. It may be that if you take such a function and apply the Luby-Rackoff construction to it, then you get a very hard pseudorandom permutation, but from the accounts I've found online I've been unable to see easily whether that is the case.

Are there any very hard unknots?

2011-01-27T09:35:29Z

Some years ago I took a long piece of string, tied it into a loop, and tried to twist it up into a tangle that I would find hard to untangle. No matter what I did, I could never cause the later me any difficulty. Ever since, I have wondered whether there is some reasonably simple algorithm for detecting the unknot. I should be more precise about what I mean by "reasonably simple": I mean that at every stage of the untangling, it would be clear that you were making the knot simpler.

I am provoked to ask this question by reading a closely related one: http://mathoverflow.net/questions/4918/can-you-fool-snappea . That question led me to a paper by Kaufmann and Lambropoulou, which appears to address exactly my question: http://www.math.uic.edu/~kauffman/IntellUnKnot.pdf , since they define a diagram of the unknot to be hard if you cannot unknot it with Reidemeister moves without making it more complicated. For the precise definition, see page 3, Definition 1.

A good way to understand why their paper does not address my question (by the way, when I say "my" question, I am not claiming priority -- it's clear that many people have thought about this basic question, undoubtedly including Kaufmann and Lambropoulou themselves) is to look at their figure 2, an example of an unknot that is hard in their sense. But it just ain't hard if you think of it as a three-dimensional object, since the bit of string round the back can be pulled round until it no longer crosses the rest of the knot. The fact that you are looking at the knot from one particular direction, and the string as it is pulled round happens to go behind a complicated part of the tangle is completely uninteresting from a 3D perspective.

So here's a first attempt at formulating what I'm actually asking: is there a generalization of the notion of Reidemeister moves that allows you to pull a piece of string past a whole chunk of knot, provided only that that chunk is all on one side, so to speak, with the property that with these generalized Reidemeister moves there is an unknotting algorithm that reduces the complexity at every stage? I'm fully expecting the answer to be no, so what I'm really asking for is a more convincing unknot than the ones provided by Kaufmann and Lambropoulou. (There's another one on the Wikipedia knot theory page, which is also easily unknotted if you allow slightly more general moves.)

I wondered about the beautiful Figure 5 in the Kaufmann-Lambropoulou paper, but then saw that one could reduce the complexity as follows. (This will be quite hard to say in words.) In that diagram there are two roughly parallel strands in the middle going from bottom left to top right. If you move the top one of these strands over the bottom one, you can reduce the number of crossings. So if this knot were given to me as a physical object, I would have no trouble in unknotting it.

With a bit of effort, I might be able to define what I mean by a generalized Reidemeister move, but I'm worried that then my response to an example might be, "Oh, but it's clear that with that example we can reduce the number of crossings by a move of the following slightly more general type," so that the example would merely be showing that my definition was defective. So instead I prefer to keep the question a little bit vaguer: is there a known unknot diagram for which it is truly the case that to disentangle it you have to make it much more complicated? A real test of success would be if one could be presented with it as a 3D object and it would be impossible to unknot it without considerable ingenuity. (It would make a great puzzle ...)

I should stress that this question is all about combinatorial algorithms: if a knot is hard to simplify but easily recognised as the unknot by Snappea, it counts as hard in my book.

Update. Very many thanks for the extremely high-quality answers and comments below: what an advertisement for Mathoverflow. By following the link provided by Agol, I arrived at Haken's "Gordian knot," which seems to be a pretty convincing counterexample to any simple proposition to the effect that a smallish class of generalized moves can undo a knot monotonically with respect to some polynomially bounded parameter. Let me see if I can insert it:

I have stared at this unknot diagram for some time, and eventually I think I understood the technique used to produce it. It is clear that Haken started by taking a loop, pulling it until it formed something close to two parallel strands, twisting those strands several times, and then threading the ends in and out of the resulting twists. The thing that is slightly mysterious is that both ends are "locked". It is easy to see how to lock up one end, but less easy to see how to do both. In the end I think I worked out a way of doing that: basically, you lock one end first, then having done so you sort of ignore the structure of that end and do the same thing to the other end with a twisted bunch of string rather than a nice tidy end of string. I don't know how much sense that makes, but anyway I tried it. The result was disappointing at first, as the tangle I created was quite easy to simplify. But towards the end, to my pleasure, it became more difficult, and as a result I have a rather small unknot diagram that looks pretty knotted. There is a simplifying move if one looks hard enough for it, but the move is very "global" in character -- that is, it involves moving several strands at once -- which suggests that searching for it algorithmically could be quite hard. I'd love to put a picture of it up here: if anyone has any suggestions about how I could do this I would be very grateful.

Basic results with three or more hypotheses

2010-10-22T08:19:04Z

Consider the following statement of the Arzela-Ascoli theorem.

Theorem. Let K be a compact topological space and let S be a subset of C(K). Then S is relatively compact if and only if S is uniformly bounded and equicontinuous.

There are various hypotheses needed here, but they divide up naturally into two classes: some, such as the compactness of K, are setting the scene, whereas others, such as the equicontinuity of S, are the "real" hypotheses that we assume. This is reflected in the way we state the theorem, putting the scene-setting assumptions in a sentence that begins "Let" so that the meat of the theorem can appear uncluttered in a second sentence that begins "Then".

What interests me is that nearly always when we do this we seem to have either one or two hypotheses. For example, a compact Hausdorff space is normal, or a metric space is compact if and only if it is complete and totally bounded. In this question I am asking for good exceptions to this rule. A truly good exception would be a statement of an undergraduate-level theorem that sets the scene and then talks about an object X, concluding, in the main sentence, that if X is A, B and C, then X is D, where A, B and C are adjectives or short adjectival phrases. (Thus, a technical lemma that needs five complicated conditions in order to hold does not count as a good exception.) It doesn't have to be from general topology -- it's just that there seem to be a lot of adjectives floating around in that area. At the time of writing, I don't have a single good example, though I fully expect them to exist.

Note that this is really a question about mathematical language, and in particular what prompts us to make definitions. After all, if we have a theorem that X is A, B and C implies that X is D, we can always define an X to be E if it is A and B, in which case we will have split the statement up into two parts, one saying that A and B imply E (a definition) and the other that E and C imply D (a theorem). It seems to me that we have a tendency to do this kind of thing because we like two-hypothesis statements.

I'm not going to use the big-list tag though, because I secretly hope that the result will be only a rather small list.

Edit: Some of the examples below are excellent. But I think I don't really want to count examples where we say something about a function between two different objects, where it is obviously quite natural to want information about the function and both objects. (For example, the statement that a continuous bijection from a compact topological space to a Hausdorff topological space is a homeomorphism needs at least three hypotheses for this reason.) Also, the distinction between scene setting and genuine meaty hypotheses is essential (even if slightly vague) if this question is to make any sense at all.

I would of course be happy with an example where we have a function between two objects, we regard all properties about the objects as scene setting, and we claim that three conditions about the function imply a fourth.

Proofs that require fundamentally new ways of thinking

2010-12-09T15:08:32Z

I do not know exactly how to characterize the class of proofs that interests me, so let me give some examples and say why I would be interested in more. Perhaps what the examples have in common is that a powerful and unexpected technique is introduced that comes to seem very natural once you are used to it.

Example 1. Euler's proof that there are infinitely many primes.

If you haven't seen anything like it before, the idea that you could use analysis to prove that there are infinitely many primes is completely unexpected. Once you've seen how it works, that's a different matter, and you are ready to contemplate trying to do all sorts of other things by developing the method.

Example 2. The use of complex analysis to establish the prime number theorem.

Even when you've seen Euler's argument, it still takes a leap to look at the complex numbers. (I'm not saying it can't be made to seem natural: with the help of Fourier analysis it can. Nevertheless, it is a good example of the introduction of a whole new way of thinking about certain questions.)

Example 3. Variational methods.

You can pick your favourite problem here: one good one is determining the shape of a heavy chain in equilibrium.

Example 4. Erdős's lower bound for Ramsey numbers.

One of the very first results (Shannon's bound for the size of a separated subset of the discrete cube being another very early one) in probabilistic combinatorics.

Example 5. Roth's proof that a dense set of integers contains an arithmetic progression of length 3.

Historically this was by no means the first use of Fourier analysis in number theory. But it was the first application of Fourier analysis to number theory that I personally properly understood, and that completely changed my outlook on mathematics. So I count it as an example (because there exists a plausible fictional history of mathematics where it was the first use of Fourier analysis in number theory).

Example 6. Use of homotopy/homology to prove fixed-point theorems.

Once again, if you mount a direct attack on, say, the Brouwer fixed point theorem, you probably won't invent homology or homotopy (though you might do if you then spent a long time reflecting on your proof).

The reason these proofs interest me is that they are the kinds of arguments where it is tempting to say that human intelligence was necessary for them to have been discovered. It would probably be possible in principle, if technically difficult, to teach a computer how to apply standard techniques, the familiar argument goes, but it takes a human to invent those techniques in the first place.

Now I don't buy that argument. I think that it is possible in principle, though technically difficult, for a computer to come up with radically new techniques. Indeed, I think I can give reasonably good Just So Stories for some of the examples above. So I'm looking for more examples. The best examples would be ones where a technique just seems to spring from nowhere -- ones where you're tempted to say, "A computer could never have come up with that."

Edit: I agree with the first two comments below, and was slightly worried about that when I posted the question. Let me have a go at it though. The difficulty with, say, proving Fermat's last theorem was of course partly that a new insight was needed. But that wasn't the only difficulty at all. Indeed, in that case a succession of new insights was needed, and not just that but a knowledge of all the different already existing ingredients that had to be put together. So I suppose what I'm after is problems where essentially the only difficulty is the need for the clever and unexpected idea. I.e., I'm looking for problems that are very good challenge problems for working out how a computer might do mathematics. In particular, I want the main difficulty to be fundamental (coming up with a new idea) and not technical (having to know a lot, having to do difficult but not radically new calculations, etc.). Also, it's not quite fair to say that the solution of an arbitrary hard problem fits the bill. For example, my impression (which could be wrong, but that doesn't affect the general point I'm making) is that the recent breakthrough by Nets Katz and Larry Guth in which they solved the Erdős distinct distances problem was a very clever realization that techniques that were already out there could be combined to solve the problem. One could imagine a computer finding the proof by being patient enough to look at lots of different combinations of techniques until it found one that worked. Now their realization itself was amazing and probably opens up new possibilities, but there is a sense in which their breakthrough was not a good example of what I am asking for.

While I'm at it, here's another attempt to make the question more precise. Many many new proofs are variants of old proofs. These variants are often hard to come by, but at least one starts out with the feeling that there is something out there that's worth searching for. So that doesn't really constitute an entirely new way of thinking. (An example close to my heart: the Polymath proof of the density Hales-Jewett theorem was a bit like that. It was a new and surprising argument, but one could see exactly how it was found since it was modelled on a proof of a related theorem. So that is a counterexample to Kevin's assertion that any solution of a hard problem fits the bill.) I am looking for proofs that seem to come out of nowhere and seem not to be modelled on anything.

Further edit. I'm not so keen on random massive breakthroughs. So perhaps I should narrow it down further -- to proofs that are easy to understand and remember once seen, but seemingly hard to come up with in the first place.

Examples of common false beliefs in mathematics.

2010-05-04T21:02:58Z

The first thing to say is that this is not the same as the question about interesting mathematical mistakes. I am interested about the type of false beliefs that many intelligent people have while they are learning mathematics, but quickly abandon when their mistake is pointed out -- and also in why they have these beliefs. So in a sense I am interested in commonplace mathematical mistakes.

Let me give a couple of examples to show the kind of thing I mean. When teaching complex analysis, I often come across people who do not realize that they have four incompatible beliefs in their heads simultaneously. These are

(i) a bounded entire function is constant; (ii) sin(z) is a bounded function; (iii) sin(z) is defined and analytic everywhere on C; (iv) sin(z) is not a constant function.

Obviously, it is (ii) that is false. I think probably many people visualize the extension of sin(z) to the complex plane as a doubly periodic function, until someone points out that that is complete nonsense.

A second example is the statement that an open dense subset U of R must be the whole of R. The "proof" of this statement is that every point x is arbitrarily close to a point u in U, so when you put a small neighbourhood about u it must contain x.

Since I'm asking for a good list of examples, and since it's more like a psychological question than a mathematical one, I think I'd better make it community wiki. The properties I'd most like from examples are that they are from reasonably advanced mathematics (so I'm less interested in very elementary false statements like $(x+y)^2=x^2+y^2$, even if they are widely believed) and that the reasons they are found plausible are quite varied.

What can be proved about the Ramanujan conjecture using elementary means?

2013-03-29T08:53:11Z

The Ramanujan conjecture states that the coefficients $\tau(n)$ in the identity

$$q\prod_{m=1}^\infty(1-q^m)^{24}=\sum_{n=1}^\infty\tau(n)q^n$$

satisfy the inequality $|\tau(n)|\leq d(n)n^{11/2}$, where $d(n)$ is the number of divisors of $n$. A positive answer to the conjecture followed (non-trivially) from Deligne's proof of the Riemann hypothesis for varieties over finite fields, conjectured by Weil.

One can interpret the coefficient $\tau(n)$ combinatorially as follows. Let $(a_n)$ be the sequence $1,1,1,\dots,1,2,2,2,\dots,2,3,3,3,\dots,3,4,\dots$, where each number occurs 24 times. Let $\rho(n)$ be the number of ways of writing $n-1$ as a sum $x_1+\dots+x_r$ of $r$ terms of the sequence for some even number $r$, and let $\sigma(n)$ be the number of ways of writing $n-1$ as a sum $x_1+\dots+x_s$ of $s$ terms of the sequence for some odd number $s$. Then $\tau(n)=\rho(n)-\sigma(n)$. It is easy to check that both $\rho(n)$ and $\sigma(n)$ grow very fast -- at least at a rate $\exp(c\sqrt{n})$ (and I'm almost sure that that is the correct order of magnitude, but haven't carefully checked so don't want to claim it as a fact). So Deligne's result tells us that there is a huge amount of cancellation: the number of representations as an even sum is almost exactly half the total number of representations.

Of course, it tells us something considerably more precise than that, and it seems clear that elementary methods are unlikely to be sufficient for this more precise result. But what if we just ask for a proof that $\tau(n)$ grows at most polynomially? Is that easy to show? If it is, then a much more general result ought to be true. For example, suppose we take an arbitrary non-decreasing sequence $a=(a_1,a_2,a_3,\dots)$ of positive integers such that $cr\leq a_r\leq Cr$ for every $r$. Define $\rho_a(n)$ to be the number of ways of writing $n$ as a sum of an even number of terms of this sequence and $\sigma_a(n)$ as the number of ways of writing $n$ as a sum of an odd number of terms. Must $\tau_a(n)=\rho_a(n)-\sigma_a(n)$ grow at most polynomially? If so, then what can be said about the degree of this polynomial in terms of $c$ and $C$?

Note that we have the identity

$$\prod_{r=1}^\infty(1-q^{a_r})=\sum_n\tau_a(n)q^n\ .$$

(A small remark is that we don't quite recover Ramanujan's $\tau$ function when the sequence takes each positive integer 24 times, because in this combinatorial context there is no motivation for taking the initial $q$ and shifting everything by 1.)

However, in this more general problem, we don't obtain a modular form when we substitute $q=e^{2\pi iz}$. As far as I can see, this rules out not just Deligne's proof methods but also earlier methods such as those of Rankin that gave weaker bounds. However, I don't know my way around this literature: is a result like the one suggested known? Is it even true?

Edit: As Garth Payne points out, it isn't true if all the $a_r$ are odd, since then the parity of the number of terms you need to pick depends on the parity of $n$. So for my question to make sense I need to add some extra condition. I don't really care what that condition is, but one possibility is to take $C$ to be less than 1, but to modify the growth condition to $cn-u\leq a_n\leq Cn+u$ for some $c>0$, $C<1$ and $u$. Or we could insist that each $a_r$ occurs in the sequence an even number of times. Basically, any condition that rules out this kind of example would leave a question that would interest me.

Further edit: Maybe better than those two conditions is just to assume that the density of terms of the sequence that are even is bounded below the whole time.

Can infinity shorten proofs a lot?

2009-11-16T23:37:08Z

I've just been asked for a good example of a situation in maths where using infinity can greatly shorten an argument. The person who wants the example wants it as part of a presentation to the general public. The best I could think of was Goodstein sequences: if you take a particular instance of Goodstein's theorem, then the shortest proof in Peano arithmetic will be absurdly long unless the instance is very very small, but using ordinals one has a lovely short proof.

My question is this: does anyone have a more down-to-earth example? It doesn't have to be one where you can rigorously prove that using infinity hugely shortens the shortest proof. Just something where using infinity is very convenient even though the problem itself is finite. (This is related to the question asked earlier about whether finite mathematics needs the axiom of infinity, but it is not quite the same.)

A quick meta-question to add: when I finally got round to registering for this site, I lost the hard-earned reputation I had gained as a non-registered user. I am now disgraced, so to speak. Is that just my tough luck?

Difficult examples for Frankl's union-closed conjecture

2010-11-26T11:04:10Z

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there must be an element that belongs to at least half the sets.

I know that pretty well any naive approach one takes to this conjecture is known to fail. By "naive approach" I suppose I mean something like an observation that it would follow from such-and-such a stronger conjecture -- it seems that all sensible stronger conjectures one thinks of are false. A very simple example of a stronger conjecture would be that if you pick a random element then on average it will belong to at least half the sets. That is completely false: take the family that consists of the empty set, {1}, and {1,2,3,4,5,6,7,8,9,10}, for example. One can try to "correct" this strengthening by devices such as insisting that for any two elements there is a set that contains one and not the other (which WLOG is the case), but such corrections don't get one very far.

What I am asking for is examples, either small ones or ones that are constructed theoretically, of union-closed families that defeat more sophisticated strengthenings of the original conjecture. I'm fairly sure they are out there but I am not an expert on this problem so I don't know them myself.

Apologies in advance if this resembles an existing question (which it feels as thought it easily might). But I've looked and not found anything.

A combination of two well-known complexity problems

2012-09-05T22:52:17Z

Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other doesn't. Can you tell in polynomial time which situation you are in? Obviously you can if graph isomorphism is easy or if finding Hamilton cycles is easy, so let's assume that they are both hard.

There may be a trivial answer, but it seems to me that the question is not obviously as hard as graph isomorphism, since if you can always solve it, it isn't clear that you can modify the algorithm to tell whether an arbitrary pair of graphs is isomorphic. If there isn't a trivial answer, then my guess is that the question is more or less as hard as resolving the P versus NP problem or the graph isomorphism problem, but maybe it isn't, since you're allowed to assume answers to those problems. Anyhow, the question has just occurred to me and I haven't yet found a reason not to like it, so here it is.

What was Gödel's real achievement?

2010-04-03T08:39:26Z

When I first heard of the existence of Gödel's theorem, I was amazed not just at the theorem but at the fact that the question could be made precise enough to answer: how on earth, even in principle, could one show that it was impossible to prove something in a given system? That doesn't bother me now, and that is not my question.

It seems to me that Gödel's theorem is a combination of at least three amazing achievements, namely these.

Formalizing the notions of proof, model, etc. so that the question could be considered rigorously.
Daring to think that there might be true but unprovable statements in Peano arithmetic.
Thinking of the idea of Gödel numbering and getting the proof to work.

One might think that 3 constitutes two separate achievements, but I think that actually getting the proof to work, though pretty good going, is somehow a technicality once you have had the idea that in principle a proof along those lines might be possible. (I'm not saying I could have done it, but Gödel would have been deeply immersed in these ideas.)

My guess is that pretty well all the credit for 2 and 3 goes to Gödel (except that the idea of diagonal proofs was not invented by him). My question is how much he contributed to 1 as well. Had it occurred to anyone else that it might be possible to think about such questions rigorously, or did an entirely new way of thinking appear pretty well out of nowhere? Popular accounts suggest the latter, but common sense would suggest the former, at least to some extent.

Answer by gowers for Believing the Conjectures

2012-10-25T22:16:45Z

I initially wrote this as a comment, but it got too long and it sort of contains an example, so here goes. Reflection seems false in a number of contexts, since there are many properties that can't be satisfied in any canonical way. For example, there isn't a small or simple basis for the reals over the rationals.

But maybe more in the spirit of the question than constructions that require the axiom of choice are a number of strange Banach-space counterexamples that are built using tools such as a sufficiently fast-growing sequence, a concave function that tends to infinity more slowly than any power, an injection from finite sets of rationals to the positive integers, etc., where the properties you need can be achieved reasonably simply, but not canonically, and the combination of the various elements is best viewed not as a single example but as a technique for building examples, where the precise details of the implementation clearly don't matter.

I'm making a slightly stronger point than may immediately be apparent, which is that for some of these strange Banach-space properties (a famous example being the property of not containing $c_0$ or any $\ell_p$ space, which was first shown to be possible by Tsirelson), not only is there considerable flexibility in how you build counterexamples, but it appears that this flexibility is in some sense "necessary". One way of making that assertion semi-precise is to say that there don't seem to be additional (sensible) properties you can insist on that cause the flexibility to go away.

I'm not saying that Reflection is definitely false for this kind of property, but it does seem to be, and I see no reason to suppose that it would be true.

Answer by gowers for Is every distance-regular graph vertex-transitive?

2012-09-07T11:27:13Z

Here's a quasi-proof that the answer is no. Wikipedia says that Moore graphs are examples of distance regular graphs. It also says "It is not known whether a Moore graph with girth 5 and degree 57 exists, but Higman proved that it cannot be vertex-transitive, unlike the known ones." Or were you asking the question in the hope of a cheap answer to this open problem?

A geometric Ramsey problem

2011-01-02T15:54:57Z

The following problem seems like one to which the answer could well be known: if so, I'd be interested to have a reference.

How large does n have to be such that among any n points in the plane you can find either m points that are collinear or m points such that no three are collinear? The fact that n is finite follows from Ramsey's theorem: colour triples of points according to whether they are collinear.

However, as with many geometric colourings, far better bounds hold than what one can obtain from the abstract Ramsey theorem. Here are what seem to me to be the trivial bounds. In one direction, an m-by-m grid of points does not contain more than m in a line, but if you choose 2m+1 of the points then you must have three that are collinear. So you need at least $cm^2$ points. (It's not quite obvious that you can choose linearly many points in this grid with no three in a line, but an old idea of Erdős does the trick: assume that m is prime and choose all points (x,y) such that $y\equiv x^2$ mod m. It is not hard to check that this set does not contain three points that are in a line even in the mod-m sense, so certainly not in the integer sense. If m isn't prime, then discard a few points until it is.)

In the other direction, you can just greedily pick points such that no three are collinear. If you reach r points and then cannot extend your set, then all subsequent points lie in one of the $\binom r2$ lines defined by the points so far. Therefore, there must be $cn/r^2$ points in a line, by the pigeonhole principle. It follows that it is enough if $n=cm^3$.

My question is, is one of these two bounds known to be correct (up to $n^{o(1)}$), and if so which? It feels quite close to known incidence results: another possibility is that a simple adaptation of a known argument would answer the question. The one thing that suggests that it might be hard is the fact that it takes a slight effort to find that set of points in the grid with no three in a line.

Has mathoverflow yet led to mathematical breakthroughs?

2010-01-15T11:28:03Z

Some people ask questions here out of simple curiosity. But some ask them because they are working on a research project, come up with a question they need to know the answer to, and think that the answer is probably known. In the past, one had to search for the right person to tell you the answer or trawl through lots of books and articles, often not knowing quite where to look. Mathoverflow ought to be a far more efficient way of doing it.

So my question here (asked out of simple curiosity) is whether there are some good examples of people using mathoverflow in an essential way to solve a research problem. The best example would be a story such as this: you struggled to solve a problem, you identified a statement that you thought would be helpful, you asked about it on mathoverflow, you got an answer, and the answer was just what you needed to complete your research project.

Demonstrating that rigour is important

2010-09-03T13:08:22Z

Any pure mathematician will from time to time discuss, or think about, the question of why we care about proofs, or to put the question in a more precise form, why we seem to be so much happier with statements that have proofs than we are with statements that lack proofs but for which the evidence is so overwhelming that it is not reasonable to doubt them.

That is not the question I am asking here, though it is definitely relevant. What I am looking for is good examples where the difference between being pretty well certain that a result is true and actually having a proof turned out to be very important, and why. I am looking for reasons that go beyond replacing 99% certainty with 100% certainty. The reason I'm asking the question is that it occurred to me that I don't have a good stock of examples myself.

The best outcome I can think of for this question, though whether it will actually happen is another matter, is that in a few months' time if somebody suggests that proofs aren't all that important one can refer them to this page for lots of convincing examples that show that they are.

Added after 13 answers: Interestingly, the focus so far has been almost entirely on the "You can't be sure if you don't have a proof" justification of proofs. But what if a physicist were to say, "OK I can't be 100% sure, and, yes, we sometimes get it wrong. But by and large our arguments get the right answer and that's good enough for me." To counter that, we would want to use one of the other reasons, such as the "Having a proof gives more insight into the problem" justification. It would be great to see some good examples of that. (There are one or two below, but it would be good to see more.)

Further addition: It occurs to me that my question as phrased is open to misinterpretation, so I would like to have another go at asking it. I think almost all people here would agree that proofs are important: they provide a level of certainty that we value, they often (but not always) tell us not just that a theorem is true but why it is true, they often lead us towards generalizations and related results that we would not have otherwise discovered, and so on and so forth. Now imagine a situation in which somebody says, "I can't understand why you pure mathematicians are so hung up on rigour. Surely if a statement is obviously true, that's good enough." One way of countering such an argument would be to give justifications such as the ones that I've just briefly sketched. But those are a bit abstract and will not be convincing if you can't back them up with some examples. So I'm looking for some good examples.

What I hadn't spotted was that an example of a statement that was widely believed to be true but turned out to be false is, indirectly, an example of the importance of proof, and so a legitimate answer to the question as I phrased it. But I was, and am, more interested in good examples of cases where a proof of a statement that was widely believed to be true and was true gave us much more than just a certificate of truth. There are a few below. The more the merrier.

Finding lots of discrete vectors in fairly general position

2012-04-30T21:57:04Z

How many vectors can there be in $\mathbb{F}_2^{2n}$ such that no $n$ of them form a linearly dependent set? The bounds I have so far are embarrassingly far apart, though that probably means I should have thought about the question for longer before posting it.

To get an upper bound, observe that you can partition $\mathbb{F}_2^{2n}$ into $2^{n+2}$ translates of an $(n-2)$-dimensional subspace. If you choose more than $(n-1)2^{n+2}$ vectors, then $n$ of them must lie in one of those translates, and therefore in an $(n-1)$-dimensional subspace. So you definitely can't choose more than $Cn2^n$ vectors with the required property.

In the other direction, if you choose $M$ vectors randomly, then the probability that some fixed set of $n$ of them lives in an $(n-1)$-dimensional subspace is at most $n2^{-n}$ (since one of them must lie in the linear span of the others). So the expected number of problematic sets of size $n$ is at most $\binom Mn n2^{-n}$. If this is at most $M/2$, then we can get rid of a vector from each problematic set and we end up with no such sets. But for $n\binom Mn$ to be less than $2^n$ we basically need $M$ to be proportional to $n$, so this gives a lower bound of something like $2n$, which is pathetic as we could have just taken $2n$ linearly independent vectors.

I end up with a similarly pathetic bound if I try to pick vectors one by one, always avoiding the subspaces that the previous vectors require me to avoid.

I think I'm slightly more convinced by the lower bound, pathetic as it is. My rough reason is that the difficulty I run into feels pretty robust, and also that the result I prove in the upper bound is much stronger than it needs to be (since the subspace I obtain is essentially a translate of some fixed subspace). But basically I can't at the time of writing see even roughly what the bound should be.

Answer by gowers for Family of subsets such that there are at most two sets containing two given elements

2012-03-30T10:21:56Z

I think I may have an answer. Let $p$ be a prime (for simplicity). Let $r=p^3$ and let $T_1,\dots,T_r$ be all possible graphs of quadratic functions defined on the integers mod $p$. These graphs live in a set of size $n=p^2$, so $r=n^{3/2}$. Note that no two quadratic functions agree in more than two places, so $|T_i\cap T_j|\leq 2$ for every $i\ne j$.

Now for each $k,l\leq p$ let $S_{kl}=\{i:(k,l)\in T_i\}$. If $q_i$ is the quadratic function corresponding to $T_i$, then $S_{kl}=\{i:q_i(k)=l\}$. Then $|S_{kl}|=p^2=n$ and there are $n$ of these sets. Each $S_{kl}$ is a subset of $\{1,2,\dots,r\}$ so lives inside a set of size $n^{3/2}$. And finally, the number of $S_{kl}$ that contain $i$ and $j$ is the number of pairs $(k,l)$ such that $q_i(k)=l$ and $q_j(k)=l$. But two distinct quadratic functions can agree in at most two places (since their difference has at most two roots).

Thus, it seems to me that the $n^{3/2}$ bound is the correct one and not $\Omega(n^2)$.

Why does the Riemann zeta function have non-trivial zeros?

2010-02-01T10:16:29Z

This is a very basic question of course, and exposes my serious ignorance of analytic number theory, but what I am looking for is a good intuitive explanation rather than a formal proof (though a sufficiently short formal proof could count as an intuitive explanation). So, for instance, a proof that estimated a contour integral and thereby showed that the number of zeros inside the contour was greater than zero would not count as a reason. A brief glance at Wikipedia suggests that the Hadamard product formula could give a proof: if there are no non-trivial zeros then you get a suspiciously nice formula for ζ(s) itself. But that would feel to me like formal magic. A better bet would probably be Riemann's explicit formula, but that seems to require one to know something about the distribution of primes. Perhaps a combination of the explicit formula and the functional equation would do the trick, but that again leaves me feeling as though something magic has happened. Perhaps magic is needed.

A very closely related question is this. Does the existence of non-trivial zeros on the critical strip imply anything about the distribution of prime numbers? I know that it implies that the partial sums of the Möbius and Liouville functions cannot grow too slowly, and it's really this that I want to understand.

Best known constant for parallel sorting

2012-03-25T15:23:15Z

I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because it takes time $C\log n$ for a fairly large constant $C$, and so in practice it is better to go for an algorithm that takes time, say, $2(\log n)^2$. I have read that reducing this constant is still an interesting open problem, and wondered if there was a good place to find out what the status of this problem is.

The answer may depend on exactly what is required of the algorithm, so let me ask a precise question, though I may be interested in answers to slightly different but related questions. Let's suppose you have $n=2m$ objects to sort, and you want to minimize the number of rounds. In each round you can partition the $n$ objects into $m$ pairs and compare each pair, and in between rounds you can do whatever computations you want. [See below -- I've changed my mind about that last point.] The number of rounds you need is of the form $C\log n$, but what is known about the constant $C$?

If I understand correctly, the question I've just asked isn't the usual one, since usually one requires more. The idea is that you start with the objects lined up from left to right in an arbitrary order, and then at each round you choose some way of partitioning the objects into pairs, but in between rounds the only thing you can do is switch the objects in each pair if the larger one is to the left of the smaller. Also, the comparisons you do in each round are, I think, independent of the results of previous rounds. This is called a sorting network.

One other way in which one can vary the question is according to whether you allow randomized algorithms. The case that interests me most is the one where randomness is allowed and so is any amount of computation between rounds. Actually, I now realize that that's a bit too generous, since it means that we can check every single ordering and see whether it is consistent with the comparisons we have made. So I'd better change what I'm asking. First, what is known about the constant $C$ in the best sorting network, with randomness allowed? Secondly, is the best known constant smaller if you allow "reasonable" additional computations to take place between rounds?

Generalizing a problem to make it easier

2010-09-26T08:09:31Z

One of the many articles on the Tricki that was planned but has never been written was about making it easier to solve a problem by generalizing it (which initially seems paradoxical because if you generalize something then you are trying to prove a stronger statement). I know that I've run into this phenomenon many times, and sometimes it has been extremely striking just how much simpler the generalized problem is. But now that I try to remember any of those examples I find that I can't. It has recently occurred to me that MO could be an ideal help to the Tricki: if you want to write a Tricki article but lack a supply of good examples, then you can ask for them on MO.

I want to see whether this works by actually doing it, and this article is one that I'd particularly like to write. So if you have a good example up your sleeve (ideally, "good" means both that it illustrates the phenomenon well and that it is reasonably easy for others to understand) and are happy to share it, then I'd be grateful to hear it. I will then base an article on those examples, and I will also put a link from that article to this MO page so that if you think of a superb example then you will get the credit for it there as well as here.

Incidentally, here is the page on this idea as it is so far. It is divided into subpages, which may help you to think of examples.

Added later: In the light of Jonas's comment below (I looked, but not hard enough), perhaps the appropriate thing to do if you come up with a good example is to add it as an answer to the earlier question rather than this one. But I'd also like to leave this question here because I'm interested in the general idea of some kind of symbiosis between the Tricki and MO (even if it's mainly the Tricki benefiting from MO rather than the other way round).

Economical hard word problem

2011-12-27T17:54:00Z

Can anyone give me an example of a very simple word problem, where by "simple" I mean that it has very few generators and relations, that is nevertheless insoluble. To make the question easier, I am prepared to allow "relation schemas" (an example might be that the fifth power of any word is equal to the identity, say), and I'm happy -- in fact, very happy -- to weaken "insoluble" to "insoluble in polynomial time" (in the length of the word). Also, I'm happy to work in a semigroup rather than a group. To make clearer what would count as a good example, let me give the reason behind it. I would like to find a collection of strings (the strings that are equal to the identity in the semigroup) such that recognising membership is difficult, but such that the space of strings in the collection is "interesting to explore", in the sense that one can develop methods for showing quite non-trivially that certain strings belong to the collection, and then build on those methods to get even less trivial examples and so on.

My motivation for that is to have a nice toy model of mathematics itself. So I'd like to be able to develop from the original replacement rules further particularly useful replacement rules that would be like lemmas, and that kind of thing. But I really would like the initial set of generators and relations to be very simple. Does this ring a bell with anyone?

Edit. Many examples of groups with insoluble word problems use sets of integers for which membership is not decidable and encode their membership problems as word problems for suitably constructed groups. I wouldn't consider such examples good ones, because they are simple relative to a set that may be quite complex. I want absolutely simple examples. If that seems like rather a strong demand, remember that I am allowing a considerable weakening of the insolubility condition.

Answer by gowers for How to write popular mathematics well?

2011-12-28T15:02:19Z

One piece of negative advice, to avoid a common fault in popular maths books: work out carefully what your audience is and write for that audience. I call that negative advice because it's really the contrapositive that concerns me: don't, for example, carefully explain how to add complex numbers and then a few pages later refer without explanation to a manifold as having trivial homology. (That sounds too obvious to be worth saying. Unfortunately, it isn't.)

Answer by gowers for Casual tours around proofs

2011-11-10T10:37:09Z

Timothy Chow's article on forcing (called A Beginner's Guide to Forcing) is one of the best of this general type.

http://www-math.mit.edu/~tchow/forcing.pdf

What could be some potentially useful mathematical databases?

2011-06-21T22:05:43Z

This is a soft question but it's not meant as a big-list question. I have recently been asked whether I want to provide feedback at the pre-beta stage on a forthcoming website that will provide a platform for data sharing, and rather than giving just my personal opinion I'd rather consult other mathematicians first. I was going to write a blog post but then I thought that Mathoverflow was a more suitable place since I have a question and I'm looking for answers of a certain type rather than general comments. The website seems to be aimed mostly at scientists who want to share raw data, so at first I thought it probably wouldn't be much use to mathematicians since our data is (or are if you prefer) mostly highly interlinked -- the connections are often more interesting than what they connect.

But on further reflection, it seems to me that a good data sharing site could be a valuable resource, even if it doesn't do absolutely everything any mathematician would ever want. For instance, Sloane's database is fantastically useful. A rather different sort of database that is also useful is Scott Aaronson's Complexity Zoo. So useful databases exist already. Is this an aspect of mathematical life that could be greatly expanded given the right platform? And if so, what should the platform be like?

I don't know anything about the design of the site, but if I'm going to comment intelligently on what features it would need to have to be useful to mathematicians, I'd like to be armed with some examples of the kind of data sharing we might actually go in for. Here are a few ideas off the top of my head.

Diophantine equations: one could have a list of what is known about various different ones.
Mathematical problems: listed in some nice categorized way, each problem accompanied by a description, complete with reading list, of what you really ought to know before thinking about the problem. (As an example, if you are thinking about the P versus NP problem, then you really ought to know about the Razborov/Rudich natural proofs paper.)
Key examples in various different areas and subareas of mathematics.
Sometimes you have a whole lot of related mathematical properties with a complicated pattern of implications between them. Under such circumstances, it could be nice to have this information presented in a nice graphical way (something I think this site may be able to do well -- they seem to be keen on visualization) with links to proofs of the implications or counterexamples that demonstrate when the implications do not hold. (The example I'm thinking of while writing this is different forms of the approximation property for Banach spaces, but there are presumably several others.)
List of special functions and the facts about each one that are the main facts one uses to prove things about them.
List of integrals that can be evaluated, with descriptions of how they can be evaluated.
List of important irrational numbers with their decimal expansions to vast numbers of places. (I'm not sure why this would be useful but it might be amusing.)

These are supposed to be examples where people could usefully pool the background knowledge that they pick up while doing research. I'm not particularly pleased with them: they should be thought of as a challenge to come up with better ones, which almost certainly exist. If you've ever thought, "Wouldn't it be nice if there's somewhere where I could look up X," then X would make a great answer. I think the most interesting answers would be research-level answers (unlike some of the suggestions above).

If there were a site with a lot of databases, it would make a great place to browse: it would be much easier to find useful data there than if it was scattered all round the internet.

One constraint on answers: there should be something about a suggested database that makes it unsuitable for Wikipedia, since otherwise putting it on Wikipedia would appear to be more sensible.

How much universality is there for contact processes?

2011-10-14T09:52:27Z

A couple of weeks ago I had to pick my daughter up from her nursery because of suspected chicken pox. It turned out to be a false alarm, but while I was waiting at the doctor's surgery to establish that, it occurred to me to wonder how it was known that the gestation period before spots appear is five days, and that somebody with the disease is infectious for up to nine days after getting it. Presumably the answer is boring: that there are enough situations where you can pinpoint when infection must have taken place to make it possible to determine the gestation and infection periods fairly accurately.

But suppose that were not the case, and instead you wanted to deduce the infection period from the global behaviour of the spread of the disease. A rough version of my question is whether this is possible.

Here's a more precise version (but this is just one model and I don't mind answers that apply to different but similar models). Let's define a contact process as follows. At any one time, each point in $\mathbb{Z}^2$ is either diseased or healthy. If you get the disease at time $t$, then there is some probability distribution $\mu$ on $[t,\infty]$ for your four immediate neighbours: their probability of catching the disease from you during the time interval $[a,b]$ is $\mu([a,b])$. I'm thinking of $\mu({\infty})$ as the probability that your neighbour doesn't catch the disease from you. And let's say that if two of your neighbours are infected, then your chances of catching the disease from one of them is independent of your chances of catching it from the other. Finally, let's assume that $\mu$ is the same for everybody (apart from the translation by $t$ to take account of when a point becomes infected).

A simple example of a distribution $\mu$ would be half the uniform distribution on $[t,t+1]$ plus half a point mass at $\infty$. That would represent the situation where if you get the disease at time $t$ then your neighbour's chance of getting the disease from you is 1/2 and if your neighbour does get the disease from you then the time of infection is uniformly distributed over $[t,t+1]$.

With this set-up, my question is this: how much can you tell about the probability distribution $\mu$ from the global spread of the disease? That's still not a completely precise question, and I think I may lack the expertise to make it completely precise, but it's the usual picture that applies to models of this kind, where you look at everything from a great distance so that you can't see the small-scale structure (so, for example, I can't just empirically test lots of pairs of neighbours to build up a picture of the probability distribution).

A different way of asking the question, which explains the title, is this. It is a well-known and fascinating phenomenon that many probabilistic models like this have global behaviour that is very insensitive to the details of their local behaviour. So I would expect, for example, that all compactly supported probability distributions for which $\mu(\infty)$ is the same would have similar global behaviour: perhaps the only parameter that mattered would be the expected time to become infected, or something like that, which would govern how quickly the disease spread. (It's not obvious to me that that is the right parameter, by the way.) But perhaps I'm wrong about this. It might, for instance, be that if the time of infection is sharply concentrated in two places, then the disease spreads in two "waves", one faster and one slower. And if that's the case, then perhaps you can work out virtually the entire distribution from the global behaviour.

I'm asking this question out of idle curiosity and nothing more. I'd just be interested to know what is known (or at least believed to be true).

Answer by gowers for Famous mathematicians with background in arts/humanities/law etc

2011-09-28T20:03:13Z

My colleague Tadashi Tokieda studied classics at university and switched to maths after being inspired by a book on the subject. I can't remember the exact details, but they are remarkable, as is he.

More on Lebesgue non-measurability

2011-08-03T11:02:45Z

I have just read the following question about measurable and non-measurable sets. Does there exist a measurable subset of $\mathbb{R}^2$ all of whose projections are non-measurable? As with many such questions, there is an easy solution based on the general principle that measure-zero sets in the plane can be very nasty: you can just take your favourite non-measurable set in $\mathbb{R}$ and think of it as a subset of $\mathbb{R}^2.$

Just for fun, here is a meta-question: is there a way of somehow ruling out any use of this principle and thereby obtaining a more challenging question? One idea that fails miserably is to insist that the subset of $\mathbb{R}^2$ has positive measure. That fails because all you have to do is take the union of a nasty measure-zero set with a token nice set of positive measure that doesn't cause any of the projections to become measurable. And that is easy.

Here is a different idea, which comes with a warning that I've only just thought of it so the question has a very good chance of not being interesting. Let X be a measurable subset of the plane. Does there necessarily exist a measure-zero subset Y of X and a projection $\pi$ such that $\pi(X\setminus Y)$ is measurable? In case asking for Y to be a subset of X is too much of a restriction, an alternative question would be for Y to be an arbitrary set of measure zero and consider $\pi(X\Delta Y).$

Answer by gowers for Lebesgue non measurability in the plane

2011-08-03T14:47:08Z

This is an answer to Gerald Edgar's question (a) (see comment just after main question). To produce a set such that all but two projections are non-measurable, take a subset X of [0,1] that's not measurable in any interval and put a copy of X into the segment from (0,0) to (1,0) and a copy of the complement of X into the segment from (1,0) to (1,1). If we project to the Y axis we get two points, so it's measurable. If we project to the X axis, we get the interval [0,1], so it's measurable. If we project in any other direction, then the images of the two segments are intervals of positive length that do not share their endpoints, so by the local non-measurability of X the resulting projection is non-measurable. My guess is that similar tricks can be used to do other things but I haven't thought about this.

Edit: I also have a very silly answer to Gerald Edgar's question (b), which is that the existence of such an example is consistent with ZF. It is known that there can be non-measurable sets of cardinality less than the continuum (of course, this means that CH fails). Let $K$ be such a set and let $X=K\times\mathbb{R}$. Now let $Y$ be the union of uncountably many rotations of $K$, but not continuum many. Finally, let $Z$ be the complement of $Y$ in the plane. If one of the rotates of $K$ is through an angle of $\theta$, then the projection of $Z$ on to the line $L_\theta$ that makes an angle of $\theta$ with the x-axis misses all points in $K$ (or rather the obvious copy of $K$ along that line). It also contains each point not in $K$, since if P is such a point, then we have removed fewer than continuum many points from the line perpendicular to $L_\theta$ that goes through P. Therefore, this projection is just a copy of the complement of $K$ and so non-measurable. If $L$ is any line that is not perpendicular to one of the $L_\theta$ for which $\theta$ is one of the angles we chose, then again we have removed fewer than continuum many points from $L$. Therefore, if we project onto $L_\phi$ for some $\phi$ that is not one of our chosen angles, then we obtain the whole of $L_\phi$, which is of course measurable. So we have uncountably many measurable projections and uncountably many non-measurable ones.

I don't know what happens if we ask for continuum many measurable projections and continuum many non-measurable projections ...

Homogeneous arithmetic progressions in difference sets

2010-09-09T21:26:25Z

I have a nasty feeling that I ought to be able to answer this question, but I've got other things to think about right now and I'm interested in the answer just so that I can reply to a mathematical email I've received. (If anyone gives me substantial help I will of course acknowledge it when I reply.)

This isn't precisely what was asked in the email, but it's closely related and would enable me to give a good answer. A result of Bourgain shows that if you take two dense subsets A and B of {1,2,...,n} then A+B must contain an arithmetic progression of length $\exp(c(\log n)^{1/3})$ or thereabouts. In particular this is true of A-A (since it contains arithmetic progressions of the same length as A-(n+1-A)). But what bounds can one get in the A-A case if one insists that the progression should be homogeneous? That is, suppose that A is a subset of {1,2,...,n} of density δ. How large an m can we guarantee to find such that there exists d such that all of -dm, -(d-1)m, ... , dm are elements of A-A?

By Szemerédi's theorem applied to A, m at least tends to infinity with n and can be taken to be n logged a few times. But can we do a lot better than this? Another small observation is that if we apply Bourgain's theorem to A-A, we can obtain a quite long homogeneous arithmetic progression in A+A-A-A.

It's been a little while since I looked at either Bourgain's proof or a subsequent improvement by Green to $\exp(c\sqrt{\log n})$, so I can't instantly say whether their arguments would give one a homogeneous progression in the case that B=-A. Based on my hazy memory, it feels as though it could go either way.

Although I think it is unlikely, there's just a small chance that this is an interesting question to which the answer is not known (or an easy consequence of known results or techniques).

Comment by gowers

2013-06-19T08:45:47Z

I now think it may be possible to do something by composing polynomially many Feistel permutations.

Comment by gowers

2013-06-19T06:55:38Z

Yes. I was vague about it, but the precise requirement I would like is that $k$ should be at most a polynomial function of $n$ (or perhaps a very slightly superpolynomial function).

Comment by gowers

2013-06-18T17:57:51Z

Good point -- thanks for the tip.

Comment by gowers

2013-06-18T17:00:25Z

I have now found a source that seems to suggest that the Luby-Rackoff construction won't give hardness greater than $2^n$. So it looks as though a different idea would be needed. But maybe there are some different ideas out there.

Comment by gowers

2013-06-18T16:47:42Z

I would also suggest Googling "random regular graph" to get an idea of how far regular graphs are from having anything that one might call a standard structure.

Comment by gowers

2013-06-18T14:20:51Z

That's obviously false and there are many counterexamples. The discrete cube, for example, or any finite Cayley graph.

Comment by gowers

2013-06-13T12:18:29Z

I drew the "quotient" knot and the picture has been sitting on my desk for about a month. At first it looked hard to simplify, but then I saw that one could make a "hole" in the middle and take a chunk of knot and pass it up through the hole and back down again. This kind of global untwisting would, I think, have to be part of any unknotting procedure of the kind I fantasize about. At some point I might make the knot out of string and see whether I can indeed untie it fairly straightforwardly starting with that move.

Comment by gowers

2013-05-09T14:49:32Z

Thank you for this example. It's quite interesting as it is in some sense a "product" of smaller knots. I tried replacing the bundles of strands (most of the time four strands) by a single strand and obtained a picture of a knot that I can't instantly see to be the unknot, though I did find a local way of reducing the number of crossings. If this "quotient" knot is not the unknot, then it's a very interesting example.

Comment by gowers

2013-03-29T18:34:35Z

I don't mind complex analysis, but I'm wondering whether a "non-structural" proof is possible. Without saying precisely what I mean by that, I would say that modular forms are on the wrong side of the boundary.

Comment by gowers

2013-03-29T16:45:38Z

Ah, I see the point now. OK, I'll go back and add a condition.

Comment by gowers

2013-03-29T16:43:23Z

I'm taking $1-q^{a_r}$, and not $1+(-q)^{a_r}$.

Comment by gowers

2012-10-26T13:02:15Z

Going back to your hypothetical Tsirelson story, I still don't see what Maximize adds to it. Why not just say that if you've tried hard to prove a conjecture, it becomes more reasonable to doubt it, regardless of what that conjecture looks like? (This doesn't apply to all conjectures: for example, our failure to prove the twin prime conjecture doesn't suggest that it might be false, since there are good heuristic reasons to expect both that it is true and that it is hard to prove.)

Comment by gowers

2012-10-26T12:59:11Z

This discussion, which I find very interesting by the way, leaves me with the feeling that I don't understand very well what the rules of thumb are really saying and what their purpose is. I agree about Banach space theory: in some ways it is a very structureless subject, because any old bunch of functionals can be used to define a norm (as long as you've got enough of them that you don't have just a seminorm), but from time to time it springs surprises -- the almost negligible constraints nevertheless interestingly restrict what you can do.

Comment by gowers

2012-10-26T08:42:20Z

The general point I'm making here is that in this context it's the mathematics that tells us to what extent Maximize is an appropriate principle, rather than the principle that is guiding our mathematical expectations.

Comment by gowers

2012-10-26T08:41:24Z

Is Tsirelson's space an example of the success of Maximize? Again, I have my doubts. Before his example, it was reasonable to try to prove that every space did contain $c_0$ or $\ell_p$ -- all known spaces did, sometimes for quite non-trivial reasons. I would contend that it was only after (i) a failure, despite considerable efforts, to prove positive theorems and (ii) Tsirelson's example that it became reasonable to believe quite strongly that if you can't easily prove something about a general Banach space, then it is probably false. And there have been counterexamples to that principle ...