In this post I want to take the following attitude. Although there are several promising approaches to solving EDP, I am going to concentrate just on the representation-of-diagonals idea and pretend that that is the problem. That is, I want to pretend that the main problem we are trying to solve is not a problem about discrepancy of sequences in HAPs but the following question instead.
Problem. Is it true that for every positive constant there exists a diagonal matrix with trace at least that can be expressed as a linear combination of the form with and each and the characteristic function of a homogeneous arithmetic progression?
There are other equivalent ways of formulating this problem, but I’ll stick with this one for now. Incidentally, can be thought of as notation for the characteristic function of .
In this post I want to try to encourage a certain stepping back. Our general problem is to construct something with some rather delicate properties. We don’t really know how to go about it. In that kind of situation, what is one to do? Does one wait to be struck suddenly by a brilliant idea? Or is there a way of searching systematically? Of course, I very much hope it will be the latter, or at least nearer to the latter.
Here are a few very general (and overlapping) methods I can think of for finding delicate examples.
1. Try to find, out there in the literature already, a construction that has some delicate properties that are similar to the ones you are interested in, and then try to modify that known example.
2. Add some further properties that an example might have, in the hope that you can narrow down the search space.
3. Come up with a different problem and show that a solution to that problem has, or can be converted into something that has, the properties you want. (An example of this technique is the use of variational methods to solve differential equations.)
4. Successive approximation: make a guess, understand why your guess doesn’t work, make a guess about how to modify or replace your first guess, understand why that doesn’t work, and so on until you hit something that does work.
5. Indirect proofs of existence: prove that the constraints are mild enough that between them they do not wipe out the entire space of potential examples.
6. Recursion: instead of building what you want in one go, build it up in stages, in such a way that at the final stage you have the properties you wanted. (In Banach space theory there are examples where the building up process is infinite: you inductively define a sequence of norms and show that it converges to a limit with properties that you are looking for.)
This is unlikely to be a complete list. I would welcome further suggestions of very general example-finding strategies.
Let me briefly discuss the potential of each of the above strategies to solve our matrix problem.
1. Modifying a known example. I find this unpromising, largely because the properties we want are very closely tied to the particular nature of HAPs, and I don’t think HAPs figure much in the rest of mathematics.
2. Adding extra properties to narrow down the search. This, it seems to me, has the potential to help, though I doubt whether it will be sufficient on its own. One way we could narrow things down is to restrict the class of HAPs that we allow ourselves to use. We have already thought about this somewhat. For example, we do not know that we cannot get by just with HAPs whose common differences are either primes or powers of 2.
3. Devising another problem whose solution you can use. I think that this method could conceivably help. What is its advantage? Well, it comes in useful if you are trying to construct something and are not confident that there will be a nice formula for that thing. Another example is the use of fixed point theorems: sometimes we can cleverly devise a continuous function, show that it has a fixed point (which we cannot describe explicitly), and show that a fixed point can be translated into a solution of the original problem. For our matrix problem, we are not sure what the diagonal matrix should be, and no obvious formula jumps out of the experimental evidence. Perhaps it is something like a multiple of the stationary distribution of some random walk — since those often don’t have an obvious formula either.
4. Successive approximation. If all else fails, this, it seems to me, is the best method. Even understanding why a very bad guess is bad can make finding a good guess easier, and the more iterations one goes through of this procedure, the more deeply one understands the problem.
5. Indirect proofs of existence. This is initially tempting, but it seems to lead inexorably towards exploiting duality, and that takes us to a generalization of EDP that we have discussed in previous threads. In other words, it seems to be a backwards step. Nevertheless, it is always worth keeping this “predual” formulation in mind, as it helps us not to make guesses that are obviously wrong (such as taking the diagonal matrix to be a multiple of the identity). Another sort of indirectness is probabilistic methods: it is certainly conceivable that they could play a role.
6. I don’t find this very promising, but there is perhaps one possibility, which has already been discussed to some extent. That is to use linear and semidefinite programming techniques for improving guesses. If we do this infinitely often, we will converge to an optimal solution, which sounds great until one realizes that one has to be able to prove something about this optimal solution, and at each iteration the matrix gets harder and harder to describe.
I think we need to think very carefully about the following question. Suppose that there is no solution to the problem that can be described by a pretty formula. How in that case could we conceivably prove the existence of a decomposition with the desired properties? The only idea I have so far is 3, perhaps with a little help from the probabilistic method. (For instance, perhaps 3 would be used to come up with the diagonal matrix, and probabilistic methods for the decomposition.) But if that is genuinely the only way of going about it, then how do we come up with this other problem with a solution that magically transforms into a solution to our problem? I’m tempted to list potential sub-strategies. They might simply be a list of promising candidates for the class of “other problem”: eigenvectors, variational methods, fixed point theorems and the like. Or they might be more general advice about how to search for a proof of this kind.
I am still rather busy with other things, but perhaps we could keep the project ticking along with a high-level strategic discussion about issues such as I have raised in this post. And then when people feel ready for it, we could start getting our hands dirty again.