This is a mathematical post rather than a Tricki post, but the title comes from the fact that the issue I want to discuss has arisen because I have made a statement in a Tricki article and can’t quite justify it to my satisfaction.
The article in question is about a useful piece of advice, which is that if one is having trouble proving a theorem, it can help a lot to try to prove rigorously that one’s approach cannot work. Sometimes one realizes as a result that it can work, but sometimes this exercise helps one to discover a feature of the problem that one has been wrongly overlooking. I have a few examples written up, but one of them is giving me second thoughts.
The example in question is this. Let be a subset of for some prime . Define a gap in of length to be a set of integers mod that contains no elements of . A nice (and well-known) question one can ask is the following. Let be of size at least . How small can one make the largest gap if one dilates ? That is, if we write for the size of the largest gap in a set , what is the largest possible value of over all sets of size at least ? (Here stands for the set .)
If you take a random set of size , then with high probability the largest gap in any dilate of will have size at most , where depends on only. After a bit of experimenting, it becomes natural to conjecture that this is the best possible bound. But is it?
This looks like a combinatorial question until one observes the following. Let be a prime of the form and let be the set of all non-zero quadratic residues mod . Then every dilate of is either the set of all non-zero quadratic residues or the set of all non-zero quadratic non-residues. Suppose it is the case that all of are quadratic residues mod . Then, since is a quadratic non-residue, all of are quadratic non-residues. Therefore, every dilate of has a gap of length . So the conjecture above will be false if there are infinitely many primes congruent to mod such that the first numbers are quadratic residues for some that tends to infinity faster than .
Suddenly we have a number-theoretic question to solve, and it turns out to be a well-known unsolved problem. Nobody has even ruled out that there is some such that for infinitely many primes all the numbers from to are quadratic residues mod . Even with the help of the Generalized Riemann Hypothesis this has been improved to rather than .
I want to claim that this example demonstrates that the original problem is “not really” a combinatorial problem. But to do that, I have to argue against someone whose reaction to it is, “Ah, this shows that an apparently number-theoretic problem is in fact a combinatorial one.” This is hard, because there are some very nice examples of number-theoretic statements that have been hugely generalized and then solved combinatorially. So what is it about this problem that makes it appear that purely combinatorial arguments are doomed to fail?
One relevant factor is that many combinatorial tools apply to large systems of sets. Initially, it looked as though the set of dilates of was a large set system, but the example of quadratic residues shows that it can in fact be very small. This fact does seem to lie behind the general feeling (or at least, I think it is a general feeling) that the problem cannot be solved combinatorially, but I would like a more general answer to the following question. Suppose you are trying to prove a theorem of the form “For every , .” Then suppose you come across a particular example of an for which you cannot prove . When is it clear that you will not be able to tackle the general theorem without first having a thorough understanding of why it is true for ?
Clearly the answer is not “always”. For example, might just be an example that is sufficiently complicated not to have any special features. It may then be slightly easier (for notational reasons, say) to think about , but thinking about isn’t interestingly different from thinking about the general case in such situations. One relevant feature of the example I have just discussed is that the appropriate tools for tackling the question about quadratic residues seem to be number-theoretic, which makes the special case different from the general case. Another sign of that is that one can easily imagine a solution to the question about quadratic residues not helping all that much to solve the general problem. But why isn’t that an argument for aiming at the general problem and ignoring the particular one?
Another feeling I have about this question, but can’t do proper justice to, relates to the discussion in the previous post. If the conjecture is true, then you can’t find a prime such that the first integers are quadratic residues for a very large . However, we can create something like a “probably inconsistent model” in which such a prime does exist, and then for any combinatorial argument about a general set , we can interpret it as referring to our fictitious that consists of quadratic residues modulo our strange prime . And in some sense our combinatorial arguments “never realize” that the model is inconsistent. Are there any reverse mathematicians out there who can make sense of this? Is it conceivable that there is some weak axiom system that is sufficient for combinatorial arguments, in which one might possibly not be able to prove that such a prime cannot exist?