The title of this post is meant to serve various purposes. First and foremost, it is a cheap trick designed to attract attention. Secondly, and relatedly, it is a nod to the amusing events of the last week or so. [Added later: they were from the last week or so when I wrote that sentence.] But there is a third reason that slightly excuses the first two, which is that the current state of play with the EDP project has a very P\(\ne\)NP-ish feel to it. Indeed, that has been the case for a while: we are trying to find a clever decomposition of a diagonal matrix, which is a difficult search problem, even though we can be fairly confident that if somebody came up with a good candidate for a decomposition, then checking that it worked would be straightforward. And just in case that is not true, let’s make it trivially true by saying that we are searching for a decomposition that can easily be checked to work. If it can easily be checked to work, then it can easily be checked that it can easily be checked to work (the algorithm being to try to check it and see whether you succeed). But now I want to air a suggestion that reduces the search problem to another one that has similar properties but may be easier.
A brief word also on why I am posting again on EDP despite the fact that we are nowhere near 100 comments on the previous post. The main reason is that, now that the rate of commenting has slowed to a trickle, it is far from clear that the same rules should apply. I think the 100-comment rule was a good sufficient condition for a new post, but now I think I want to add a couple more: if there is something to say and quite a long time has elapsed since the previous post, or if there is something to say that takes a while to explain and is not a direct continuation of the current discussion, then it seems a good idea to have a new post. And both these conditions apply.
[Added later: this is a rather strange post written over a few weeks during which my thoughts on the problem were constantly changing. So everything that I say, particularly early on, should be taken with a pinch of salt as I may contradict it later. One approach to reading the post might be to skim it, read the very end a bit more carefully, and then refer back to the earlier parts if you want to know where various ideas came from.]
A simple question about functions on \(\mathbb{N}\).
Let me cut to the chase and ask a question that I find quite nice and that can be understood completely independently of all the discussion of EDP so far. I will then try to motivate the question and sketch a proof that a positive answer to this question would imply EDP.
The question, in isolation, is this. Does there exist, for every constant \(c>0,\) a sequence \((a_n)\) with the following properties?
1. \(\sum_na_n=1.\)
2. \(\sum_na_{rn}=0\) for every \(r\geq 2.\)
3. \(|a_1|+\sum_{n=1}^\infty|a_{n+1}-a_n|\leq c.\)
Without the third condition, the answer is easily seen to be yes, since one can take \(a_1=1\) and all the other \(a_n\) to be zero.
After writing that question, I had to stop for a day or so, during which I realized that the answer was a trivial no. Indeed, if \(\sum_na_n=1\) and \(\sum_na_{2n}=0,\) then \(\sum_na_{2n-1}=1,\) so
\(\sum_n|a_{n+1}-a_n|\geq\sum_n|a_{2n}-a_{2n-1}|\geq 1,\)
which rules out condition 3.
How could I have asked such a dull question? Well, the question may be dull but I think there remains some interest in the motivation for it, especially as it leads to a related question that may be harder to answer but have equal potential to be useful. If you want to cut to the new chase, then skip to the bottom of this post, where I shall ask a different question that again involves finding a function that satisfies various conditions (though this time the function is of two variables).
Where the question came from.
But if you would prefer some motivation, then here is how the first question arose. We would like to find a decomposition of the identity on the rationals. (By this I mean the matrix \(\delta_{rs},\) where \(r\) and \(s\) range over \(\mathbb{Q}.\)) We want this decomposition to take the form \(\sum_i\lambda_iP_i\otimes Q_i,\) where each \(P_i\) and each \(Q_i\) is the characteristic function of a HAP, and the sum of the \(|\lambda_i|\) is small. (What precisely this smallness condition is I’ll discuss later.)
Now let me consider briefly a very general question related to the facetious title of this post: how is that mathematicians often manage to solve difficult problems with an NP flavour? That is, how is it that when they are faced with searching for an X that does Y, and most Xs clearly don’t do Y, they nevertheless often succeed in finding an X that does do Y. Obviously the answer is not a brute-force search, but what other kinds of searches are there?
One very useful method indeed is to narrow down the search space. If I am looking for an X that does Y, then one line of attack is to look for an X that does Y and Z. If I am lucky, there will exist Xs that do both Y and Z, and the extra condition Z will narrow down the search space enough to make it feasible to search.
One of the best kinds of properties Z to add is symmetry properties, since if we insist that X is symmetric in certain ways then we have fewer independent parameters. For example, if we want to find a solution to a PDE, then it may be that by imposing an appropriate symmetry condition one can actually ensure that there is a unique solution, and finding something that is unique is often easier than finding something that is far from unique (because somehow your moves are more forced).
Let us write \(P_{d,m}\) for the characteristic function of the HAP \(\{d,2d,\dots,md\}.\) Then we are looking for a decomposition as a linear combination of functions of the form \((x,y)\mapsto P_{d,m}(x)P_{d',m'}(y),\) which we have been writing as \(P_{d,m}\otimes P_{d',m'}.\) What symmetry conditions can we impose?
An obvious one to start with is that we could insist that \(d=d'\) and \(m=m'.\) That is, we could attempt to find a decomposition of the form \(\sum_{d,m}\lambda_{d,m}P_{d,m}\otimes P_{d,m}.\) (Note that \(d\) ranges over the rationals and \(m\) over the positive integers.) Actually, I think that’s more of a simplicity condition than a symmetry condition, but the same cannot be said of the next condition, which is to insist that \(\lambda_{d,m}\) should be independent of \(d.\) This tells us that the decomposition “looks the same everywhere” and takes the form \(\sum_{d,m}\lambda_mP_{d,m}\otimes P_{d,m}.\)
Now what is the smallness property we need of the coefficients \(\lambda_m\)? I won’t fully justify this here, because I have already discussed how to deal with the fact that the rationals form an infinite set. Let me simply say that if the \(m\) for which \(\lambda_m\ne 0\) are bounded, then we are done if \(\sum_m|\lambda_m|\) can be made arbitrarily small. (Roughly speaking, we are interested in the ratio of the average diagonal entry to the average \(\sum_m|\lambda_{m,d}|\) per \(d.\) Since the average diagonal entry of the identity is 1 and \(\lambda_{m,d}\) depends only on \(m,\) we are interested in \(\sum_m\lambda_m.\))
Let \(f_m\) be the function \(\sum_dP_{d,m}\otimes P_{d,m}.\) Then we would like to express the identity as a linear combination of the \(f_m\) with coefficients with a small absolute sum. A good start might be to calculate \(f_m(x,y).\) It is the number of \(d\in\mathbb{Q}\) such that \(x=rd\) and \(y=sd\) for some positive integers \(1\leq r,s \leq m.\) If \(a\) and \(b\) are minimal integers such that \(ax=by,\) then the only \(d\) that “divide” \(x\) and \(y\) are numbers of the form \(z/t,\) where \(x=bz\) and \(y=az.\) We then get \(r=bt\) and \(s=at,\) so we need \(t\) to be at most \(m/b\) and also at most \(m/a.\) But the maximum of \(a\) and \(b\) is \(d(x,y),\) so we need \(t\) to be at most \(m/d(x,y).\) Since any positive integer satisfying this condition works, we ind that \(f_m(x,y)=\lfloor m/d(x,y)\rfloor.\)
One nice thing to observe about this is that it depends only on \(d(x,y)\) and not on \(x\) and \(y\) themselves. This turns our question into a one-dimensional one (but unfortunately it is the question above that has a boring answer).
But let’s see why that is. We are now in a position where we want to write the identity as a linear combination of the functions \(f_m.\) But now we know that if we write \(g_m(n)=\lfloor m/n\rfloor,\) what we are trying to do is write the function \((1,0,0,0,\dots)\) as a linear combination of the \(g_m\) (since we want \(\sum_m\lambda_mf_m(x,y)=1\) if \(d(x,y)=1\) and 0 otherwise.
How are we to deal with the functions \(g_m,\) given that they have unpleasant integer parts involved? There turns out to be a nice answer to this: look at the differences \(g_m-g_{m-1}.\) We see that \(g_m(n)-g_{m-1}(n)=1\) if \(m\) is a multiple of \(n\) and 0 otherwise. Now \(\sum_m\lambda_mg_m(n)=\sum_ma(m)(g_m(n)-g_{m+1}(n)),\) where \(a(m)=\lambda_1+\dots+\lambda_m.\) So the condition \(\sum_m|\lambda_m|\leq c\) translates to the condition \(\sum_m|a_m-a_{m-1}|\leq c\) (interpreting \(a_0\) to be 0). And \(\sum_ma(m)(g_m(n)-g_{m-1}(n)=\sum_ra(rn),\) which we want to be 1 when \(n=1\) and 0 otherwise, which is where conditions 1 and 2 come from.
If we could get conditions 1-3 then I’m pretty sure we’d have a solution to EDP. But we can’t, so where does that leave us? In particular, are we forced to give up the very appealing idea of having a decomposition that is “the same everywhere”?
Rectangular products.
Actually no. It shows that we cannot combine the following two features of a decomposition: being the same everywhere, and using only “square” products — that is, products of the form \(P\otimes P\) rather than more general “rectangular” products of the form \(P_1\otimes P_2.\) What happens if we allow ourselves a bit of extra generality? We would like to do this in a minimal way, so for the time being let us assume that \(P_1\) and \(P_2\) have the same common difference.
At first it may seem as though we gain nothing, because there is a sort of polarization identity operating. Observe first that if we decompose \(I\) as a sum of matrices \(A_i,\) then we can replace each \(A_i\) by its symmetrized form \((A_i+A_i^T)/2\) and we will have a decomposition of \(I\) into symmetric parts. So without loss of generality we can assume that the coefficient of \(P\otimes Q\) in any decomposition is the same as the coefficient of \(Q\otimes P.\) If \(P\) is longer than \(Q,\) then we can now use the fact that
\(P\otimes Q+Q\otimes P=P\otimes P-Q\otimes Q-(P\setminus Q)\otimes(P\setminus Q)\)
to replace the rectangular products by a comparably small combination of square products. However, there is an important difference, which is that we are now allowing ourselves (square) products of HAPs of the form \(\{rd,(r+1)d,\dots,sd\}.\) Perhaps surprisingly, this gives us a large amount of extra flexibility.
To demonstrate this, I need to go through calculations similar to the ones above, but slightly more complicated (though with a “magic” simplification later that makes things nice again). First, it turns out to be convenient to define \(P_{d,r,s}\) to be the characteristic function of the HAP \(\{rd,(r+1)d,\dots,(s-1)d\}.\) (One indication of this is that it has length \(s-r,\) or to be more accurate \((s-r)\vee 0,\) a piece of pedantry that turns out to be unexpectedly important later.) Now let us define \(g_{r,s}(x,y)\) to be \(\sum_dP_{d,r,s}(x)P_{d,r,s}(y).\) We can calculate \(g_{r,s}(x,y)\) in a similar way to the way we calculated \(f_m(x,y)\) earlier. Let \((a,b)\) be minimal such that \(ax=by,\) and let \(z\) be the largest rational that divides both \(x\) and \(y,\) which tells us once again that \(x=bz\) and \(y=az.\) For \(d\) to contribute to the sum, we again need \(d\) to be of the form \(z/t\) for some positive integer \(t,\) but now we need \(at\) and \(bt\) to lie in the interval \([r,s).\) Without loss of generality \(a\leq b.\) Then our requirements are that \(at\geq r\) and \(bt<s.\) Since \(t\) is an integer, this is equivalent to requiring that \(t\geq \lceil r/a\rceil\) and \(t<\lceil s/b\rceil.\)
The number of \(t\) that satisfy this is obviously \((\lceil r/a \rceil - \lceil s/b\rceil)\vee 0.\) Again, the max with zero is extremely important to us, and not just because it makes the expression correct. So now we have our formula:
\(g_{r,s}(x,y)=(\lceil r/a\rceil - \lceil s/b\rceil)\vee 0.\)
As in the previous one-dimensional case, we have ugly integer parts to contend with, not to mention the max with zero. But once again we can simplify matters by looking at telescoping sums and the “derivative” of our function, except that this time we want two-dimensional analogues. What we shall do is this (I think it is fairly obviously the natural thing to do so I won’t try to justify it in detail). Define a function \(h_{r,s}\) by
\(h_{r,s}=g_{r+1,s+1}-g_{r+1,s}-g_{r,s+1}+g_{r,s}.\)
We would now like to express an infinite linear combination \(\sum_{r<s}\mu_{r,s}g_{r,s}\) as a linear combination of the \(h_{r,s}.\) (Note that \(g_{r,s}\) is identically zero if \(r\geq s.\) Hence the range of summation.) Since we don’t actually know what the \(\mu_{r,s}\) are, let us just imagine that we have some coefficients \(\lambda_{r,s}\) that satisfy
\(\mu_{r,s}=\lambda_{r,s}-\lambda_{r,s-1}-\lambda_{r-1,s}+\lambda_{r-1,s-1}.\)
Then
\(\sum_{r<s}\lambda_{r,s}h_{r,s}=\sum_{r<s}\lambda_{r,s}(g_{r+1,s+1}-g_{r+1,s}-g_{r,s+1}+g_{r,s})\)
\(=\sum_{r<s}(\lambda_{r,s}-\lambda_{r,s-1}-\lambda_{r-1,s}+\lambda_{r-1,s-1})g_{r,s}=\sum_{r<s}\mu_{r,s}g_{r,s}.\)
But \(\sum_{r,s}\lambda_{r,s}h_{r,s}(x,y)\) turns out to be something we can understand very well, because the functions \(h_{r,s}\) are unexpectedly simple. Recall that
\(g_{r,s}(x,y)=(\lceil r/a\rceil - \lceil s/b\rceil)\vee 0,\)
where \(a\) and \(b\) are minimal such that \(ax=by.\) So in principle we can calculate \(h_{r,s}(x,y).\) This looks unpleasant until we make a couple of simple observations. First of all, note that \(g_{r,s}\) is constant on rectangles of sidelengths \(a\) and \(b.\) (Here I am taking \(a\) and \(b\) fixed and varying \(r\) and \(s.\)) More precisely, there is a tiling of \(\mathbb{N}^2\) into such rectangles, and \(g_{r,s}\) is constant on each of these rectangles. As you go horizontally from one rectangle to another to its right, \(g_{r,s}\) increases by 1, and as you go vertically upwards it decreases by 1. If you put all these facts together, you find that \(h_{r,s}(x,y)=-1\) on all multiples of \((a,b)\) and is zero everywhere else.
What does this tell us about the coefficients \(\lambda_{r,s}\)? Well, we want \(\sum_{r<s}\lambda_{r,s}h_{r,s}(x,y)\) to be 1 if \(x=y\) and \(0\) otherwise. It follows that whenever \(a\) and \(b\) are coprime, with \(a\leq b,\) then we want \(\sum_u\lambda_{au,bu}\) to be 1 if \(a=b\) and \(0\) otherwise. This is very similar to our one-dimensional criterion, but with the huge difference that the sets along which we are summing the function \(\lambda_{r,s}\) are disjoint. (They are lines through the origin, or rather intersections of those lines with \(\mathbb{N}^2.\))
We also have a smallness criterion. Recall that in the one-dimensional case we needed \(\sum_n|a_n-a_{n-1}|\) to be arbitrarily small (interpreting \(a_0\) as 0). Here we need the very similar property that
\(\sum_{r<s}|\lambda_{r,s}-\lambda_{r,s-1}-\lambda_{r-1,s}+\lambda_{r-1,s-1}|\)
is arbitrarily small. Let me briefly remark that there is nothing to stop us defining \(\lambda_{r,s}\) however we like for values of \((r,s)\) with \(r\geq s,\) and it will be convenient to exploit this.
So there is a rather simple looking question: can we find a function \(\lambda:\mathbb{N}^2\rightarrow\mathbb{R}\) such that the “\(\ell_1\)-norm of the mixed partial derivatives” is arbitrarily small, the sum along the diagonal is 1, and the sum over all other lines of positive rational gradient is 0?
Somehow this question doesn’t feel as though it should be that hard, since the constraints don’t seem to interact all that much. So it would be natural to think that either there is a simple reason for no such \(\lambda\) existing, just as there was in the one-dimensional case, or there is a fairly simple construction of such an example.
Solving the two-dimensional question.
If there is a construction, how might one expect it to work? There are two reasonable possibilities: either one writes something quite clever straight down (perhaps involving trigonometric functions somehow to get the sums to be zero along the lines of gradient not equal to 1), or one goes for a just-do-it proof. My feeling (with the benefit of some hindsight) is that there are few enough constraints for a just-do-it approach to be appropriate, and in any case attempting a just-do-it proof can hardly fail to increase one’s understanding of the task, whether or not the attempt succeeds.
I should interrupt what I’m writing to say that I’m almost certain that a just-do-it approach works. By that I mean that I’m sitting here about to write down what I think is a correct proof, but that proof has been sitting in my head for the last day or so and has not been written down. And I’m pretty sure that my arguments that this would solve EDP can be tightened up and turned into a rigorous proof too, though that will need to be checked very carefully. So right now I don’t see why we don’t have a complete proof of EDP.
I should also at this point make a general remark about Polymath. I’ve been spending quite a lot of time thinking about the problem on my own, which is contrary to the spirit of Polymath and therefore demands an apology — but also an explanation. The explanation is that I have been trying to write this post for a long time — I started it nearly a week ago — but my efforts have been interrupted by plane journeys and ICM activities, including blogging the ICM. However, plane journeys, long waits for opening ceremonies, lonely moments in my hotel room, etc., are very conducive to mathematical thought, and since most of the argument I am writing here is rather simple (it was just a question of finding the right idea to get it started), I have found that the length of what I need to put in the post has been increasing faster than the length of the post itself. And one other mitigating factor is that there has been very little reaction to my recent comments on the previous post, where I first set out some of this approach (see in particular the two most recent comments), so I feel more entitled to go it alone for a while than I would have if the project had been roaring ahead at the sort of speed it was going at earlier in the year. Needless to say, the proof, if it turns out to work, is still very much a joint effort — this most recent argument depends crucially on the insights that have emerged from the more active discussion phase — and will be another paper of D. H. J. Polymath.
I must repeat that this post is being written over the course of many days. Several hours have passed since I finished the last paragraph, and during them I thought a bit harder about the step I was most worried about, which was dealing with the fact that the rationals are infinite and that at some point one must do some kind of truncation. I now think that that step will be more problematic than I had thought, and it seems to me to be about 50-50 whether it will be possible to get it to work. Having said that, I feel as though something non-trivial has emerged from the argument I shall complete in a moment, and I will be quite surprised (not to mention disappointed) if it leads nowhere. What I’m really saying is that I have an argument that does exactly what seems to be needed, except that the sums involved are a bit too formal. Now it could be that establishing convergence in some appropriate sense is where the real difficulty of the problem lies. In that case, this approach will be much less useful than I thought. But I am hoping that it is more of a technical problem. No time to think about it right now as I am going to a performance of A Disappearing Number, a play about which I shall undoubtedly have more to write later.
WELL OVER A WEEK LATER
The first thing to say is that EDP definitely isn’t yet solved. I’ve also reformulated the problem again, in a way that I find clearer. I could give a long description of how the new perspective evolved from the one above, but I think instead I’ll just sketch what happened.
Solving the two-dimensional question, continued
The first thing to observe is that if we take the characteristic function of a rectangle, then the sum of the \(|\lambda_{r,s}-\lambda_{r,s+1}-\lambda_{r+1,s}+\lambda_{r+1,s+1}|\) is 4, since the only contributions come from the four corners.
Therefore, all we have to do is this. We shall build up an infinite matrix as a linear combination of rectangles — that is, functions of the form \(P\otimes Q,\) where \(P\) and \(Q\) are arithmetic progressions with common difference 1. We start by choosing a large integer \(k.\) We then put entries \(k^{-1}\) at every point \((x,y)\in \{1,2,\dots,k\}^2.\) That ensures that the sum along the main diagonal is 1, provided that we do not do anything else to that diagonal. However, it also causes the sums along several other lines to be non-zero, so there is work to do. Note that the sum of coefficients so far is \(k^{-1}\) since there is just one rectangle and its coefficient is \(k^{-1}.\)
To do the rest of the work, let us enumerate all rationals greater than 1 as \(q_1,q_2,\dots\) and deal with each gradient in turn. What “deal with” means is that we shall add in some very small multiple of a rectangle in such a way that the sum along the line of the gradient we are dealing with is now zero, and will agree that from then on we will not change any entry in that line. Can we do this? Well, let’s suppose that we are dealing with the gradient \(q_i.\) So far, the sum of the entries of the matrix along the line of gradient \(q_i\) is \(t,\) say. So we must find a rectangle that contains many integer points along the line of gradient \(q_i\). And we also need it not to intersect any line of gradient \(q_j\) with \(j<i.\) But if we go far enough up the line with gradient \(q_i,\) we will find ourselves at a very great distance from the lines we are trying to avoid, so we can find a very large rectangle that is disjoint from those lines and contains many integer points of the form \((x,q_ix).\) If it contains \(h\) such points, then we make the coefficient of that rectangle equal to \(-h^{-1}t.\) Since we can get \(h\) to be as big as we like, we can get this coefficient to be as small as we like. So we have “dealt with” the gradient \(q_i,\) and the problem is solved.
Why doesn’t that solve EDP?
Let me start by saying why I thought it might solve EDP. I thought that if the sum of coefficients associated with each \(d\) was arbitrarily small, then that would be saying that in a certain sense the average weight of the coefficients was arbitrarily small. Since the average size of the diagonal entries is 1, this ought somehow to give us what we want.
To understand why this doesn’t work, and probably can’t be made to work, I find it helpful to reformulate the problem again. To do so, let us think about the operators \(\sum_dP_{d,r,s}\otimes P_{d,r,s}\) once again. (These first came in fairly near the beginning of the section entitled “Rectangular products.”) In particular, let us think what one of these operators does to the function \(\delta_x\) that is 1 at \(x\) and 0 everywhere else.
In fact, let us be slightly more general, as it will be useful to us later. What is the value of \((P_{d,r,s}\otimes P_{d,u,v})(\delta_x)\) at \(y?\) For it to be non-zero we need \(x\in\{du,\dots,d(v-1)\}\) and \(y\in\{dr,\dots,d(s-1)\},\) and then it is 1. So if we sum over all \(d,\) then we get the number of \(d\) with that property. Now each \(d\) with that property is of the form \(x/w\) for some \(w\in\{u,\dots,v-1\},\) so when we sum over \(d\) we are counting the number of ways of writing \(y\) as \(tx/w\) for some \(w\in\{u,\dots,v-1\}\) and some \(t\in\{r,\dots,(s-1)\}.\)
That is, if we define \(g_{r,s,u,v}(z)\) to be the number of ways of writing \(z\) as \(t/w\) with \(r\leq t<s\) and \(u\leq w<v,\) then \((P_{d,r,s}\otimes P_{d,u,v})(\delta_x)(y)=g_{r,s,u,v}(y/x).\) That is another way of saying that \((P_{d,r,s}\otimes P_{d,u,v})(\delta_x)=g_{r,s,u,v}*\delta_x,\) where \(*\) is a multiplicative convolution.
If you don’t like following calculations but want to know what the moral of all that is, then here you are. Let us define the multiplicative convolution of two functions \(f\) and \(g\) to be the function \(h\) given by the formula
\(h(x)=\sum_{yz=x}f(y)g(z).\)
Then the operator \(\sum_d P_{d,r,s}\otimes P_{d,u,v}\) takes a function \(f\) to the multiplicative convolution of \(f\) with the function \(g_{r,s,u,v},\) which is itself the multiplicative convolution of the characteristic functions of the sets \(\{r,r+1,\dots,s-1\}\) and \(\{u^{-1},(u+1)^{-1},\dots,(v-1)^{-1}\}.\) (That is, as I’ve already said, \(g_{r,s,u,v}(z)\) is the number of ways of writing \(z\) as a fraction with numerator in \(\{r,r+1,\dots,s-1\}\) and denominator in \(\{u,u+1,\dots,v-1\}.\))
Now we’re trying to express the identity as a small linear combination of these convolution operators, so we can turn the problem into a one-dimensional problem: to write the function \(\delta_1\) (which is the identity for the multiplicative convolution) as a small linear combination of functions \(g_{r,s,u,v}.\)
I am about 99% sure that if we could do that with a finite linear combination then we would have a proof of EDP. I used to think that “whatever works for finite should also work for infinite but with absolutely summable coefficients,” but it seems that this is wrong because even if the coefficients can be made very small, the functions themselves may be getting quite large in the norms we care about, so the convergence may be much too weak.
That does indeed seem to be the case here. If you convert the just-do-it argument above into an argument to express \(\delta_1\) in terms of the functions \(g_{r,s,u,v},\) then you get pointwise (absolute) convergence, but that is not strong enough.
Let me just elaborate on the remark that this problem can be solved directly by means of a just-do-it argument. I won’t give the full argument, but I’ll just point out that for each rational \(q=a/b\) you have the option of doing the following. You choose a very large integer \(m\) and a very much larger integer \(n.\) You then set \(P=\{an,an+1,an+2\dots,a(n+m-1)\}\) and \(Q=\{bn,bn+1,\dots,b(n+m-1)\}.\) Since \(n\) is much larger than \(m,\) \(r/s\) is very close to \(a/b\) for every \(r\in P\) and \(s\in Q.\) Moreover, the number of pairs \((r,s)\in P\times Q\) such that \(r/s=a/b\) is \(m\) (assuming that \(a\) and \(b\) are coprime, that is). So if we want to get rid of a value \(\alpha\) at the point \(q,\) then we can subtract the function \(\alpha m^{-1}P*Q^{-1},\) which has a small coefficient and is supported on only a very small neighbourhood of \(q.\)
What is not so good about it is that the \(\ell_1\) norm of \(m^{-1}P*Q^{-1}\) is roughly \(abm,\) which is not small at all.
Thinking slightly further about this, I see that what I said above about pointwise convergence was a bit too pessimistic: for example, we can easily organize for the convergence to be uniform. And indeed, if we think of \(m^{-1}P*Q^{-1}\) as being, in its broad shape, roughly like a set of size close … actually, what is it like?
Rational numbers sort of repel each other, so if we’ve devised \(P\) and \(Q\) such that all points in \(PQ^{-1}\) are close to \(a/b,\) then all points that are not actually equal to \(a/b\) will tend to have rather large denominators, and therefore not to occur very frequently. So let’s hazard a guess that for the purposes of thinking about \(\ell_p\) norms, we can think of \(P*Q^{-1}\) as having a spike at \(a/b\) where the value is \(m\) and \(abm^2\) other values that are all around 1. That would mean that the pth power of the \(\ell_p\) norm was around \(m^p+abm^2.\) Thinking of \(a\) and \(b\) as constants, it looks as though we might expect some kind of good behaviour to kick in when \(p\) passes 2. Remembering that we’re actually interested in \(m^{-1}\) times the \(\ell_p\) norm, we get something like \(1+m^{2/p-1}.\) But if the value \(\alpha\) we were trying to get rid of was small, we can multiply that by a small factor \(\alpha.\) Ah, but the problem is that there are an awful lot of those \(\alpha\)s to worry about, and they add up in an \(\ell_1\)-ish way.
What that boils down to is that this kind of greedy keep-away-from-everything-else approach doesn’t give us any kind of useful convergence, which we need if we are to get the averaging argument to work. I realize that I haven’t been too clear about what kind of convergence would work, but there is one kind that is definitely OK, and that is if we have a finite linear combination. So let me now ask a completely precise question.
A sufficient (I’m almost sure) condition for EDP
Let \(P\) and \(Q\) be subsets of \(\mathbb{N}.\) We define \(P*Q^{-1}\) to be the function whose value at \(x\) is the number of ways of writing \(x\) as \(r/s\) with \(r\in P\) and \(s\in Q.\) I claim that EDP follows if for every \(c>0\) there exists a way of writing the function \(\delta_1\) (which is defined on \(\mathbb{Q}\) and takes the value 1 at 1 and 0 everywhere else) as a finite linear combination \(\sum_i\lambda_iP_i*Q_i^{-1}\) where the \(P_i\) and \(Q_i\) are intervals of positive integers and \(\sum_i|\lambda_i|\leq c.\)
Summary.
In this post I have been looking at the representation-of-diagonals approach over the rationals with the extra symmetry constraint that the HAP products are all of the form \(P_{d,r,s}\otimes P_{d,u,v},\) where \(P_{d,r,s}=\{dr,d(r+1),\dots,d(s-1)\}\) and that the coefficient of \(P_{d,r,s}\otimes P_{d,u,v},\) is independent of \(d.\) This symmetry condition forces the diagonal map we are trying to represent to be the identity. (As I write this it occurs to me that we might be able to take an arbitrary efficient representation of a diagonal matrix and average it over all multiples in order to obtain an efficient representation of the identity. So perhaps this “new” approach is equivalent to the old one — which would be quite encouraging as it would increase the chances that the new one can be made to work.)
Thinking through what this means, we find that we can reformulate the problem and obtain the question asked in the previous section.
Where next for EDP?
To finish, I’d like to ask if anyone has views about how they would like the EDP project to proceed. We are in uncharted waters at the moment: we have a project that started with a burst of activity — in fact it was sustained enough to count as more than just a burst — but now it has slowed right down and I’m not sure it will ever regain anything like its earlier intensity. And yet I myself am still enthusiastic about it, and perhaps I’m not alone in that.
My question is what should happen if it turns out that there are only two or three people, or even just one, who feel like working on the problem. In that case, there are various options. We could simply continue to post comments on this blog and not worry if there are very few participants or if the rate of posting is small. Or we could move the project to a different phase, more like a normal collaboration, with longer periods of private thought, but from time to time write comments or posts to make sure that any important developments are kept public (so that, in particular, anyone who wanted to join in would be free to do so). Or we could turn the project into a completely conventional collaboration, always with the understanding that the author of the eventual paper would be D. H. J. Polymath. And that’s not quite the most conventional it could go. The final possibility would be to close the project altogether, write a paper summarizing all the partial results, and then “free up” the problem for anyone who wants to think about it privately — if they used any of Polymath’s ideas they could simply refer to the paper that contained those ideas.
I think I favour keeping the project going as a Polymath project but with longer periods of private thought, but I don’t favour this strongly enough that I couldn’t be persuaded to change my mind if others feel differently. If that is the way we go, then my final question is, are there people out there who would like to be part of a small group of reasonably dedicated participants, or am I on my own now?
This entry was posted on September 3, 2010 at 11:12 am and is filed under polymath5. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.