Apologies for the attention-seeking title, but that really is the purpose of this post. I want to draw attention to some ideas that are buried in more comments that most people are likely to want to read, because I think there is a chance that all that stands between where we are now and a solution to EDP is a few soluble technical problems. It goes without saying that that chance is distinctly less than 100%, but I think it is high enough for it to be worth my going to some trouble to lay out as precisely as I can what the current approach is and what remains to be done. I’ll try to write it in such a way that it explains what is going on even to somebody who has not read any of the posts or comments so far. The exception to that is that I shall not repeat very basic things such as what the Erdős discrepancy problem is, what a homogeneous arithmetic progression is, etc. For that kind of information, I refer the reader to the front page of the Polymath5 wiki.
Representing the identity.
Let me now discuss an approach that doesn’t work. (If you have been keeping up with the discussion, then this will be familiar material explained in a slightly different way.) Let \(N\) be a large integer, and if \(P\) and \(Q\) are two HAPs contained in \([N]=\{1,2,\dots,N\},\) then write \(P\otimes Q\) for the \(N\times N\) matrix that is 1 at \((m,n)\) if \(m\in P\) and \(n\in Q\) and 0 otherwise. In other words, it’s the characteristic function of \(P\times Q.\) Note that if \(x\in\mathbb{R}^N,\) then \(\langle x,(P\otimes Q)(x)\rangle=(\sum_{i\in P}x_i)(\sum_{j\in Q}x_j.\) Let us write \(\sum_{i\in P}x_i\) as \(\langle x,P\rangle,\) etc.
Suppose that we could find for every pair \((P,Q)\) of HAPs contained in \([N]\) a coefficient \(\lambda_{PQ}\) in such a way that \(I_N=\sum_{P,Q}\lambda_{PQ}(P\otimes Q)\) and \(\sum_{PQ}|\lambda_{PQ}|\leq cN.\) Then for every real sequence \(x_1,\dots,x_N\) we have
\(\sum_i x_i^2=\sum_{PQ}\lambda_{PQ}\langle x,P\rangle\langle x,Q\rangle.\)
It follows by averaging that there exist \(P\) and \(Q\) such that
\(|\langle x,P\rangle \langle x,Q\rangle|\geq(cN)^{-1}\sum_ix_i^2.\)
In particular, if each \(x_i=\pm 1,\) then there must exist \(P\) and \(Q\) such that \(|\langle x,P\rangle\langle x,Q\rangle|\geq c^{-1},\) from which it follows that either \(|\langle x,P\rangle|\) or \(|\langle x,Q\rangle|\) is at least \(c^{-1/2}.\) So if we can get \(c\) to tend to zero as \(N\) tends to infinity then we are done.
Unfortunately, it is impossible to get \(c\) to tend to zero. The reason is that the above argument would imply that if \(x_i=1,-1,0\) when \(i=1,2,0\) mod 3, then for every \(C\) there exists a HAP \(P\) such that \(|\sum_{i\in P}x_i|\geq C.\) But that is not true: it can never be greater than 1.
Because of this example, we have been trying a different approach, which is to look for a more general diagonal matrix \(D\) and write that as a linear combination of matrices of the form \(P\otimes Q.\) If one generalizes the approach in this way, then it is no longer clear that it cannot work — indeed, it seems likely that it can. However, it also seems to be hard to find a suitable diagonal matrix, and hard to think how one might decompose it once it is found.
Working over the rationals instead.
The single main point of this post is to suggest a way of overcoming this last difficulty. And that is to resurrect an idea that was first raised right near the beginning of this project, which is to look at the problem for functions defined on the positive rationals rather than the positive integers. (It is a straightforward exercise to show that the two problems are equivalent. For details go to the Polymath5 wiki and look at the section on the first page with simple observations about EDP.)
The point is that the counterexamples that show that the approach cannot work for the integers all make crucial use of the fact that some numbers are more divisible by small factors than others. But over the positive rationals all numbers are equally divisible. Or to put it another way, multiplying by a positive rational is an automorphism of \(\mathbb{Q}.\) This suggests that perhaps over the rationals it would be possible to use the identity matrix.
Dealing with infinite sets.
Now a problem arises if we try to do this, which is that the rationals are infinite. So what are we supposed to say about the sum of coefficients when we decompose the identity into a linear combination \(\sum_{P,Q}\lambda_{PQ}P\otimes Q\)?
Let me answer this question in two stages. First I’ll say what happens if we decompose the identity when the ground set is \(\mathbb{N},\) which shows a way of dealing with infinite sets, and then I’ll move on to \(\mathbb{Q},\) where some additional problems arise.
Suppose, then, that the infinite identity matrix (that is, the function \(\delta_{mn}\) where \(m\) and \(n\) range over \(\mathbb{N}\)) has been expressed as a linear combination \(\sum_{P,Q}\lambda_{PQ}P\otimes Q.\) Now let \((x_n)_1^\infty\) be a \(\pm 1\) sequence. We’d like to show that it has unbounded discrepancy: that is, we’d like to show that for every \(C\) there exists a HAP \(P\) such that \(|\sum_{n\in P}x_n|>C.\)
Our problem is that \(\sum_{P,Q}|\lambda_{PQ}|\) is going to be infinite. We’d somehow like to show that it has “density” at most \(c,\) where \(c\) is an arbitrary positive constant, or perhaps show that it has density zero. One way we might do this is as follows. For each positive integer \(N,\) Let \(S_N\) be the sum of the \(|\lambda_{PQ}|\) over all \((P,Q)\) such that both \(P\) and \(Q\) have non-empty intersection with \([N].\) Then define the upper density of the coefficients to be \(\lim\sup S_N/N.\) If this is zero we can say that the coefficients have density zero. And if it is at most \(c\) then we can say that they have density at most \(c.\) (In fact, even the \(\lim \inf\) would be OK — we just want the density to be small infinitely often.)
Let’s suppose that \(S_N/N\) is at most \(c.\) Then if we truncate the sequence \((x_n)\) at \(N\), by changing all values after \(N\) to zero, we find that
\(N=\sum_{n=1}^Nx_n^2=\sum_{P,Q\in H_N}\lambda_{PQ}\langle x,P\rangle\langle x,Q\rangle,\)
where I have written \(H_N\) for the set of all HAPs that have non-empty intersection with \([N].\) Since \(\sum_{P,Q\in H_N}|\lambda_{PQ}|\leq cN,\) the same averaging argument as before gives us a HAP (either \(P\) or \(Q\) — WLOG \(P\)) such that \(|\sum_{n\in P}x_n|\geq c^{-1/2}.\)
I fully admit that this is not very infinitary, but it is simple, and I’m not sure it matters too much that it is not infinitary. I’ll just briefly mention that one can use it to express the proof of Roth’s theorem (about AP discrepancy rather than HAP discrepancy). One expresses the infinite identity matrix as the following integral:
\(I=\int_0^1 e_\alpha\otimes \overline{e_\alpha} d\alpha,\)
where \(e_\alpha(n)=e(\alpha n)=\exp(2\pi i\alpha n).\) One then expresses each function \(e_\alpha\) as a linear combination of HAPs of length \(m\) (an arbitrary positive integer) and common difference at most \(m.\) One then obtains some cancellation in the coefficients, and proves that the density of the coefficients is at most \(m^{-1/2}\) (up to a constant factor). For details of how this calculation works, see this write-up, and in particular the third section.
The importance of the restriction on the length and common difference is that the edge effects (that is, APs that intersect \([N]\) without being contained in \([N]\)) are negligible for large \(N.\) It is this feature that is slightly trickier to obtain for the rationals, to which I now turn.
Transferring to HAPs and rationals.
One useful feature of the set of APs of length \(m\) and common difference at most \(m\) is that each number greater than or equal to \(m^2\) is contained in precisely \(m^2\) such APs. A first question to ask ourselves is whether we can find a set of HAPs that covers the rationals in a similarly nice way. To start with, observe that if \(x\) is a rational, then we can easily describe every HAP of length \(m\) that contains \(x.\) Indeed, for every \(r\) between \(1\) and \(m,\) we have the HAP consisting of the first \(m\) multiples of \(x/r,\) and that is all of them (since \(x\) must be in the \(r\)th place of the HAP for some \(r,\) and that and the length determine the HAP). So we have the extremely undeep result that every \(x\) is contained in precisely \(m\) HAPs of length \(m.\) (Note, however, how untrue this is if we work in the positive integers rather than the positive rationals.)
This looks promising, but we now need an analogue of the “increasing system of neighbourhoods” that was provided for us by the sets \([N].\) (It might have been more natural to work in \(\mathbb{Z}\) and take the sets \([-N,N].\)) What is a sensible collection of finite sets with union equal to \(\mathbb{Q}\)?
One way of thinking about the sets \([N]\) is as follows. Using our system of APs, we can define a graph: we join \(x\) to \(y\) if there is an AP of length \(m\) and common difference at most \(m\) that contains both \(x\) and \(y.\) The sets \([N]\) are quite close to increasing neighbourhoods in this graph: start with the number 1 and then take all points of distance at most \(r\) from it. If we work with \(\mathbb{Z}\) rather than \(\mathbb{N},\) then this graph is a Cayley graph, and after a while the neighbourhoods grow linearly with \(r,\) which is why the boundary effects are small.
What happens if we define a similar graph using HAPs in \(\mathbb{Q}\)? Now we are joining \(x\) to \(y\) if there exists \(1\leq r\leq m\) and \(1\leq p\leq m\) such that \(px/r=y.\) That is precisely the condition that there exists a HAP of length \(m\) that contains both \(x\) and \(y.\) In other words, we take the multiplicative group of \(\mathbb{Q}\) and inside it we take the Cayley graph with generators all numbers \(p/q\) with \(1\leq p,q\leq m.\)
This feels like the right graph to take, but it has the slight drawback that it is not connected: it is impossible to get from \(x\) to \(y\) if \(x/y\) is a rational such that in its lowest terms either its numerator or denominator is divisible by a prime greater than \(m.\) The connected component of 1 in the graph is the set of all rationals \(r/s,\) where both \(r\) and \(s\) are products of primes less than or equal to \(m.\) But this is not really a problem: we’ll just work in that component of the graph.
Let’s write \(\mathbb{Q}_m\) for the component of \(\mathbb{Q}\) we are working in, and \(N(r)\) for the set of all points at distance at most \(r\) from 1 in the graph. Now we can say how it would in principle be possible to prove EDP. We would like to find a way of writing the identity (this time thought of as the function \(\delta_{rs}\) where \(r\) and \(s\) range over \(\mathbb{Q}_m\)) in the form
\(\sum_{P,Q}\lambda_{P,Q}P\otimes Q,\)
where \(P\) and \(Q\) are HAPs of length at most \(m\) that are contained in \(\mathbb{Q}_m.\) For each \(r,\) let \(H_r\) be the set of all such HAPs that have non-empty intersection with the neighbourhood \(N(r).\) Then we can define \(S(r)\) to be \(\sum_{P,Q\in H_r}|\lambda_{PQ}|,\) and we can define the upper density of the coefficients to be \(\lim\sup S(r)/|N(r)|.\)
Now let me show that if \(S(r)/|N(r)|\) is at most \(c\) for some sufficiently large \(r,\) then the HAP-discrepancy of every \(\pm 1\) function \(f\) on \(\mathbb{Q}\) is at least \(c^{-1/2}.\) This is by almost exactly the same argument that worked in \(\mathbb{N}.\) The first step is to consider the restriction of \(f\) to \(N(r).\) Then we know that
\(|N(r)|=\sum_xf(x)^2=\sum_{P,Q\in H_r}\lambda_{PQ}\langle f,P\rangle\langle f,Q\rangle.\)
Now any HAP of length at most \(m\) that intersects \(N(r-1)\) is contained in \(N(r),\) from which it follows that any HAP of length at most \(m\) that intersects \(N(r)\) but is not contained in \(N(r)\) must intersect \(N(r)\setminus N(r-1).\) Since \(\mathbb{Q}_m\) is a finitely generated Abelian group, the sets \(N(r)\) grow polynomially, which implies that the ratio \(|N(r)\setminus N(r-1)|/|N(r)|\) tends to zero with \(r.\)
I’ll now be very slightly sketchy. We are supposing that \(S(r)/|N(r)|\) is at most \(c.\) It follows that either \(S(r)\approx S(r-1)\) or \(S(r-1)/|N(r-1)|\) is noticeably smaller than \(S(r)/|N(r)|.\) In the second case we can change \(r\) to \(r-1\) and start again — we won’t be able to do this too many times so eventually we’ll reach the first case, where \(S(r)\approx S(r-1).\)
In that case we have that
\(|N(r)|\approx\sum_{P,Q\subset N(r)}\lambda_{PQ}\langle f,P\rangle\langle f,Q\rangle\)
and that
\(\sum_{P,Q\subset N(r)}|\lambda_{PQ}|\approx c|N(r)|.\)
After that, the argument really is the same as before (give or take the small approximations). [Remark: I have not checked the details of the above sketch, but I’m confident that something along these lines can be done if this doesn’t quite work. It’s slightly more difficult than in \(\mathbb{N}\) because it isn’t obvious that the intersection of a HAP with \(N(r)\) is a HAP, whereas the intersection of an AP with \(\{1,2,\dots,N\}\) is an AP.]
Characters on the rationals.
Now we must think about how to express the identity as a linear combination of HAP products with coefficients of density at most \(c,\) where \(c\) is some arbitrary positive constant. Taking our cue from the \(\mathbb{N}\) case, it would be natural to express the identity on \(\mathbb{Q}_m\) in terms of characters, and then to decompose the characters. So a preliminary task is to work out what the characters are.
This is (not surprisingly) a piece of known mathematics. I shall discuss it in a completely bare-hands way, but readers who don’t like that kind of discussion may prefer to look at the comment by BCnrd to this Mathoverflow question.
First I’ll work out what the characters on \(\mathbb{Q}\) are, and then I’ll look at \(\mathbb{Q}_m.\) Recall that a character is a function \(\chi\) from \(\mathbb{Q}\) to the unit circle in \(\mathbb{C}\) such that \(\chi(x+y)=\chi(x)\chi(y)\) for every \(x,y\in\mathbb{Q}.\) That is, it is a homomorphism from \((\mathbb{Q},+)\) to \(\mathbb{T}.\)
Suppose we know the value of \(\chi\) at a rational \(x.\) That tells us what \(\chi(nx)\) is for every integer \(n.\) However, it does not tell us what \(\chi(x/2)\) is, say. All we know is that \(\chi(x/2)^2=\chi(x),\) which gives us two possibilities for \(\chi(x/2).\) So in order to specify \(\chi,\) we need to specify its values at enough rationals that we can write every other rational as a multiple of one of them. And the choices we make at those rationals have to be compatible with each other.
A simple way of doing that is to choose the value of \(\chi\) at \(1/n!\) for every positive integer \(n,\) making sure that \(\chi(1/(n+1)!)^{n+1}=\chi(1/n!).\) That is, we choose \(\chi(1)\) to be any point in \(\mathbb{T},\) and then for each \(n\) we have \(n\) choices for \(\chi(1/n!)\) given our choices up to that point.
An equivalent way of thinking about this is that we choose a sequence of real numbers \(\alpha_1,\alpha_2,\dots\) satisfying the conditions that \(0\leq \alpha_n < n!\) and \(\alpha_{n+1}-\alpha_n\) is a multiple of \(n!.\) Then the corresponding character \(\chi\) is defined at \(x=p/q\) to be \(e(\alpha_n x)\) for any \(n\geq q.\) Note that this is well-defined, since if \(m\) and \(n\) are both at least \(q,\) then \(q|(\alpha_n-\alpha_m),\) so \(e(\alpha_np/q)=e(\alpha_mp/q).\)
Now because we chose an element of \([0,1]\) and then made a sequence of finite choices, it is easy to put a probability measure on the set of characters. We can therefore make sense of the expression
\(\mathbb{E}_\chi \chi(x)\overline{\chi(y)}=\mathbb{E}_\chi \chi(x-y)\)
and prove that it is \(\delta_{xy}.\) Let me briefly sketch this. Suppose that \(x=y.\) Then \(\chi(x-y)=\chi(0)=1\) for every \(\chi,\) so we get 1. If \(x\ne y,\) then let \(x-y=p/q\) when written in its lowest terms. If \(\alpha_1,\alpha_2,\dots\) is the (random) sequence that determines \(\chi,\) then each \(\alpha_n\) is uniformly distributed in the interval \([0,n!),\) and \(\chi(p/q)=e(\alpha_qp/q).\) But \(\alpha_q/q\) is uniformly distributed in the interval \([0,(q-1)!),\) so this expectation is zero (as \(p\ne 0\)).
We have therefore shown that
\(I=\mathbb{E}_\chi\chi\otimes\overline{\chi},\)
where \(I\) is the identity indexed by \(\mathbb{Q}.\)
What do we do if we want to modify this to work for \(\mathbb{Q}_m\)? Well, an initial complication that (I hope) turns out not to be a serious complication is that \(\mathbb{Q}_m\) is not an additive group: it contains 1 and it does not contain any prime greater than \(m.\) However, it generates a subgroup \(\Gamma_m\) of \(\mathbb{Q},\) which consists of all rationals with denominators that are products of primes less than or equal to \(m.\) When I refer to “characters on \(\mathbb{Q}_m\)” I will really mean characters on \(\Gamma_m.\)
To describe these, we no longer need a sequence of reciprocals such that every rational is a multiple of one of them: we just want to capture all rationals in \(\Gamma_m.\) But that is straightforward: instead of taking the sequence \((1/n!)\) we could take the sequence \(((1/(m!)^n)_{n=1}^\infty,\) or we could replace \(m!\) by the product of all the primes up to \(m.\) There are any number of things that we could do.
Decomposing a character into “non-local” HAPs.
The thing that seems to me to make this approach very promising is that for any character \(\chi\) on \(\mathbb{Q}\) it is possible to partition \(\mathbb{Q}\) into long HAPs on each of which \(\chi\) is approximately constant. As this result suggests, it is possible to decompose \(\chi\) in an efficient way as a linear combination of HAPs, which is very much the kind of thing we need to do in order to imitate the Roth proof.
I should warn in advance that it is not quite good enough for our purposes, because the HAPs we use are not “local” enough: they are sets of the form \(\{(a+1)x,(a+2)x,\dots,bx\}\) such that \(b-a\) is small, but we do not also know that \(a\) and \(b\) are small. Without that, each number is contained in infinitely many HAPs, so we no longer have the condition that enabled us to define the “density” of a set of coefficients. Later I shall present a different idea that does use “local” HAPs, but fails for a different reason. My gut instinct is that these difficulties are not fundamental to the approach, but whether that is mathematical intuition or wishful thinking is hard to say.
Before I go any further, here is an easy lemma.
Lemma. Let \(\chi\) be a character on \(\mathbb{Q}\) and let \(\epsilon>0.\) Then there exists \(M\) such that for every \(x\) there exists a positive integer \(n\leq M\) such that \(|\chi(x/n)-1|\leq\epsilon.\)
Proof. Without loss of generality \(x=1.\) Let \(t=\lceil 2\pi/\epsilon\rceil\) and let \(M\) be the lowest common multiple of the numbers from 1 to \(t.\) [Thanks to David Speyer for pointing out at Mathoverflow that the l.c.m. is around \(e^t,\) a non-negligible improvement over \(t!\).] Then by the usual pigeonhole argument we can find a positive integer \(s\leq t\) such that \(|\chi(s/M)-1|\leq 2\pi t^{-1}\leq\epsilon\) so we can take \(n=M/s.\)
For the next result we define a HAP to be a set of the form \(\{ax,(a+1)x,\dots,bx\}.\)
Corollary. Let \(\chi\) be a character on \(\mathbb{Q},\) let \(\epsilon>0\) and let \(m\) be a positive integer. Then we can partition \(\mathbb{Q}\) into HAPs of lengths between \(m/2\) and \(m\) on each of which \(\chi\) varies by at most \(\epsilon.\)
Proof. We begin by covering the integers. Find a positive integer \(n\) such that \(|\chi(1/n)-1|\leq \epsilon/m.\) Then on any HAP with common difference \(1/n\) and length at most \(m\) \(\chi\) varies by at most \(\epsilon.\) We can partition the multiples of \(1/n\) into HAPs of length \(m,\) and they will cover all the integers. (Indeed, they will cover all the multiples of \(1/n.\))
We now want to fill in some gaps. Let us write \(n_1=n\) and let us pick an integer \(n_2,\) a multiple of \(n_1\) and greater than \(mn_1,\) such that \(|\chi(n_2)-1|\leq\epsilon/m.\) Between any two multiples of \(1/n_1\) there are at least \(n_2/n_1\) multiples of \(1/n_2\) forming a HAP. This HAP can be partitioned into HAPs of common difference \(1/n_2\) and lengths between \(m/2\) and \(m.\) If we continue this process and make sure that every positive integer divides at least one \(n_i\) (which is easy to do), then we are done.
Now a character restricted to a HAP is just a trigonometric function. If the character varies very slowly as you progress along the HAP, then convolving it with an interval (as in the Roth argument, but now we are talking about a chunk with the same common difference as the HAP) we obtain a multiple very close to 1 of the character itself. With the help of this observation, we can actually decompose the character efficiently as a linear combination of HAPs. Since this does not obviously help us, I will leave the details as an exercise.
What can we do with local HAPs?
Let us fix a positive integer \(m\) and define a HAP to be local if it is of the form \(\{ax,(a+1)x,\dots,bx\},\) where \(1\leq a\leq b\leq m.\) (Thus, the definition of “local” depends on \(m.\)) What happens if we have a character \(\chi\) and try to decompose its restriction to \(\mathbb{Q}_m\) as a linear combination of local HAPs (of reasonable length) on each of which \(\chi\) varies very little?
The short answer is that it is easy to cover \(\mathbb{Q}_m\) with HAPs of this kind, but it doesn’t seem to be easy to partition \(\mathbb{Q}_m\) into them. In order to achieve the partition into non-local HAPs in \(\mathbb{Q},\) we helped ourselves to smaller and smaller common differences, and correspondingly larger and larger values of \(a\) and \(b.\) Another problem with that method was that what we are really searching for is a very nice and uniform way of decomposing characters, such as we had in the Roth proof. There the niceness was absolutely essential to getting enough cancellation for the proof to work, but it wasn’t essential to represent the identity — we could allow ourselves a bit extra as long as that extra was positive semidefinite.
So let’s not even try to partition \(\mathbb{Q}_m.\) Instead, we could simply take our character and use it as a guide to the coefficients that we will give to our HAPs.
The rough idea would be something like this. Given a character \(\chi\) and a HAP \(P=\{u,2u,\dots,mu\},\) we choose a coefficient \(\lambda_{\chi,u}\) in some nice way that makes it large when \(|\chi(u)-1|\) is small. It could for example be \(\max\{1-\epsilon^{-1}|\chi(u)-1|,0\}\) for some suitable \(\epsilon>0.\) And then we could use convolution to represent \(\lambda_{\chi,u}\) times the restriction of \(\chi\) to \(P\) as a linear combination of sub-HAPs of \(P\) of length smaller than \(m\) but not too much smaller, and common difference \(u.\)
We would know from the lemma above that every \(x\) would be contained in at least some HAPs with large coefficients, so the restriction of every \(x\) would in some sense be catered for. I think there would be some \(x\) that were catered for too much (the precise relationship between those \(x\) and \(\chi\) remains to be worked out, but I think this will be straightforward), but I hope that the whole decomposition can be defined in a nice enough way for the function \(\psi_\chi\) that results to be the pointwise product of the original character \(\chi\) with a “nice” non-negative real function that’s bounded away from zero. More speculatively, one can hope that the coefficients have small density and that it is possible to subtract a not too small multiple of the identity from the matrix \(\mathbb{E}_\chi \psi_\chi\otimes\overline{\psi_\chi}\) and still be left with something that’s non-negative definite.
An attempt to be more precise.
In this final section I want simply to guess at a matrix decomposition that might potentially prove EDP. As I write this sentence I do not know what the result will be, but the two most likely outcomes are that it will fail for some easily identifiable reason or that the calculations will be such that I cannot tell whether it fails or succeeds.
Actually, to make the guess just a little bit more systematic, let’s suppose that for each HAP \(P\) in the class of HAPs we are considering and for each character \(\chi\) we have a coefficient \(\lambda_{P,\chi}.\) That is, corresponding to \(\chi\) we are taking the function \(\psi_\chi=\sum_P\lambda_{P,\chi}P.\) Given two HAPs \(P\) and \(Q,\) what will the coefficient of \(P\otimes Q\) be in the decomposition \(\mathbb{E}_\chi\psi_\chi\otimes\overline{\psi_\chi}\)?
Expanding this out gives us
\(\mathbb{E}_\chi(\sum_P\lambda_{P,\chi}P)\otimes(\sum_Q\overline{\lambda_{Q,\chi}}Q).\)
If we reverse the order of expectation and summation then we see that the coefficient of \(P\otimes Q\) is \(\mathbb{E}_\chi\lambda_{P,\chi}\overline{\lambda_{Q,\chi}}.\)
Now let us think what we are trying to achieve with the HAPs \(P\) and \(Q.\) Given a HAP of the form \(\{u,2u,\dots,mu\},\) we want to use it to contribute to the representation of characters \(\chi\) for which \(|\chi(u)-1|\) is small. If \(\chi\) is such a character, then we know that the numbers \(\chi(u),\chi(2u),\dots,\chi(mu)\) vary only slowly. Therefore, if we take short subprogressions of the form \(\{au,(a+1)u,\dots,bu\},\) then on each one \(\chi\) will be roughly constant. If we fix a length \(2s+1\) (which may have to be logarithmic in \(m\) or something like that), then we can represent the restriction of \(\chi\) to \(\{u,2u,\dots,mu\}\) as a linear combination of the HAPs \(\{(a-s)u,\dots,(a+s)u\}\) of length \(2s+1,\) give or take some problems at the two ends.
Roughly speaking, the coefficient of \(\{(a-s)u,\dots,(a+s)u\}\) will be \((2s+1)^{-1}\chi(au).\) That is, if we write \(P_{u,a}\) for the HAP \(\{(a-s)u,\dots,(a+s)u\},\) then it is approximately true to say that the restriction of \(\chi\) to \(\{u,2u,\dots,mu\}\) is \((2s+1)^{-1}\sum_a\chi(au)P_{u,a}.\)
Now we want to do this only if \(\chi(u)\) is close to 1. So the coefficient of \(P_{u,a}\) in the decomposition of \(\chi\) will in general be \((2s+1)^{-1}\mu(\chi(u))\chi(au),\) where \(\mu\) is some nice function (which, if the Roth proof is anything to go by, means that it has non-negative and nicely summable Fourier coefficients) that is zero except at points that are close to 1.
What would we expect \((2s+1)^{-1}\sum_{a,u}\mu(\chi(u))\chi(au)P_{u,a}\) to be like? Is there any chance that it is close to a multiple of \(\chi\)?
Since \(\chi\) is roughly constant on \(P_{u,a}\) whenever \(\mu(\chi(u))\) is non-zero, the value of this function at \(x\) is roughly the same as it is if we take just singletons — that is, if we set \(s=0\) and define \(P_{u,a}\) to be \(\{au\}.\) So the function we get should have a value at \(x\) that is close to \(\sum_{au=x}\mu(\chi(u))\chi(x)=\chi(x)\sum_{r=1}^m\mu(\chi(x/r)).\)
In other words, we get something that has the same argument as \(\chi\) but that has big modulus at a rational \(x\) if it so happens that \(\chi(x/r)\) is close to 1 for unexpectedly many positive integers \(r\leq m.\) Now this can happen, but I would think that for nearly all \(\chi\) and \(x,\) if \(m\) is not too small, then \(\sum_{r=1}^m\mu(\chi(x/r))\) would be about its expected value of \(m\|\mu\|_1.\) So I am hoping that we will have some kind of rough proportionality statement.
Going back to the coefficient of \(P\otimes Q\) in the decomposition, let us take the two HAPs \(P_{u,a}\) and \(P_{v,b}.\) We have decided to define \(\lambda_{P_{u,a},\chi}\) to be \((2s+1)^{-1}\mu(\chi(u))\chi(au),\) so \(\mathbb{E}_\chi\lambda_{P_{u,a},\chi}\overline{\lambda_{P_{v,b},\chi}}\) is equal to
\((2s+1)^{-2}\mathbb{E}_\chi\mu(\chi(u))\mu(\chi(v))\chi(au-bv).\)
It is a significant problem that we are forced to consider the case where \(u\ne v:\) in the Roth proof, we did not have to look at products of APs with different common differences. But if we are to have any chance of decomposing \(\chi\) into “local” HAPs, then necessarily we must use completely different common differences to deal with rational numbers that are a long way apart in the graph. This is such a significant difference from the Roth proof that it may be a reason for this approach not working at all. However, it does look as though there is plenty of cancellation.
I think the expression we would be trying to bound is
\((2s+1)^{-2}\sum_{u,v\in N(r)}\sum_{a,b\leq m}|\mathbb{E}_\chi\mu(\chi(u))\mu(\chi(v))\chi(au-bv)|,\)
which is perhaps better thought of as
\((2s+1)^{-2}\sum_{u,v\in N(r)}\sum_{a,b\leq m}|\mathbb{E}_\chi\mu(\chi(u))\chi(au)\mu(\chi(v))\overline{\chi(bv)}|.\)
And our main strength would be that we would be free to choose \(\mu\) as it suited us. There would be two challenges: to obtain a good bound on the above expression, and to prove that we could subtract a reasonable-sized multiple of the identity and still be left with a positive semi-definite matrix.
I think the above counts as a calculation for which I cannot tell whether it fails or succeeds. But I hope it may be enough to provoke a few thoughts.
This entry was posted on July 18, 2010 at 10:53 pm 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.