EDP26 — three generalizations

This short post is designed as a possible way in to EDP for anyone who might be interested in participating but daunted by the idea of reading large amounts of material. One of the natural strategies for proving EDP is to try to formulate and prove stronger statements. At first that sounds paradoxical: isn’t it even harder to prove a stronger statement? But the answer to that question is often no. To give a slightly silly example, suppose you were asked to prove that for every c>0 there exists N such that for every n\geq N if n is odd and has at least c\log n prime factors (counted with multiplicity), then 2^{\phi(n)}\equiv 1 mod n, where \phi is Euler’s totient function. You could make the problem easier by proving Euler’s theorem, that a^{\phi(n)}\equiv 1 mod n for every n and every a that is coprime to n. You wouldn’t have as many hypotheses to use, but that’s good, since they can’t be used. Perhaps a better and more relevant example is when you generalize the class of numbers you are working with so as to allow a wider set of methods. For instance, suppose you want to prove that the largest possible product of three positive integers that add to 300 is at most 10^6. If you replace positive integers by positive reals, then you suddenly have available methods that you didn’t have before — for example, you could use compactness plus a lemma that says that if any two numbers are not equal then you can increase the product by replacing both of them by their average. (I’m not saying that’s the easiest proof — just that it’s a proof that you can’t do without first generalizing the statement.)

In this post I want to mention three strengthenings of EDP. One of them I find interesting but not promising as a way of proving EDP, for reasons that I will explain. The other two look to me also very interesting and much more promising. All of them have been mentioned already, but the point of this post is to collect them in one convenient place.

Restricting the allowable common differences.

I know of no \pm 1-sequence that has bounded discrepancy on all HAPs with common difference either a prime or a power of 2. The sequence 1,1,-1,-1,1,1,-1,-1,\dots has bounded discrepancy on all HAPs of prime common difference, but if you allow powers of 2 as well, then no periodic construction can work, since if the period m is 2^ka for some odd integer a, then a HAP of common difference 2^k will have a bias of at least 1 in each interval of length m, for parity reasons, and this bias will gradually accumulate.

One can defeat powers of 2 by using the Morse sequence 1,-1,-1,1,-1,1,1,-1,-1,1,1,-1,1,-1,-1,1,-1,\dots (if you haven’t seen it, then it’s a nice exercise to see how it is generated), but that has unbounded discrepancy on HAPs of odd prime length. (I can’t remember exactly why.)

Why do I not think that this potential strengthening of EDP is likely to be useful for attacking the problem? Well, one promising feature of EDP is that it seems to generalize to sequences taking other kinds of values, such as complex numbers of modulus 1 or even unit vectors in an arbitrary Hilbert space. However, something that I’ve only just noticed (though others may have spotted it ages ago) is that if one restricts to, say, prime-power common differences, then even the complex version of the problem becomes false. A very simple counterexample is the sequence \omega,\omega^2,\omega^3,\dots, where \omega=\exp(\pi i/3) (that is, a primitive sixth root of 1). Then the sum along any HAP with common difference d that isn’t a multiple of 6 will be a sum of a GP with common ratio \exp(d\pi i/3)\ne 1, and will therefore be (uniformly) bounded. In particular, this is true of HAPs with prime-power common difference.

This simple example also shows that a certain real generalization of EDP is false when you restrict the common differences in this way: you cannot prove unbounded discrepancy for sequences that take values in the set \{-2,-1,1,2\}. The counterexample is simply twice the real part of the example above: the sequence 1,-1,-2,-1,1,2 repeated over and over again. So if (and I think it’s a big if) EDP is true for HAPs with common differences that are either primes or powers of 2, then any proof must make pretty strong use of the fact that the sequence is a \pm 1-valued sequence. This rules out a lot of promising techniques, so it appears to make the problem harder rather than easier.

A discrepancy question about matrices.

In my earlier post I mentioned what I called the non-symmetric vector-valued EDP. I have subsequently realized (though perhaps a better word is “remembered” since I must have been sort of aware of this at some point) that it is equivalent to another discrepancy statement that I now find more appealing. The statement is the following.

Conjecture. Let f be a function from \mathbb{N}^2 to \mathbb{R} and suppose that f(n,n)=1 for every n\in\mathbb{N}. Then for every real number C there exist HAPs P and Q such that |\sum_{m\in P,n\in Q}f(m,n)|\geq C.

If we take a function g:\mathbb{N}\to\{-1,1\} and define f(m,n)=g(m)g(n), then for every C the above conjecture, if true, gives us HAPs P and Q such that |\sum_{m\in P}g(m)||\sum_{n\in Q}g(n)|\geq C, which proves that the discrepancy of g is at least C^{1/2}. So the above conjecture implies EDP. But the class of functions of the form g(m)g(n) with g:\mathbb{N}\to\{-1,1\} is a very small subset of the class of all functions f that take the value 1 along the diagonal, so this conjecture is very much stronger than EDP.

It is also equivalent to the statement that for every c>0 there exists a diagonal matrix D of trace at least 1 that can be written as a linear combination \sum_i\lambda_iu_i\otimes v_i, where for each i u_i and v_i are characteristic functions of HAPs P_i and Q_i and \sum_i|\lambda_i|\leq c. (This is the statement that I discussed at length in my previous post.) In one direction this is easy: if a decomposition of that kind exists, then \sum_nf(n,n)D(n,n) equals the trace of D and is therefore greater than 1, but it also equals \sum_i\lambda_i|\sum_{(m,n)\in P_i\times Q_i}f(m,n)|, which is at most c\max_i|\sum_{(m,n)\in P_i\times Q_i}f(m,n)|. It follows that there is some i such that |\sum_{(m,n)\in P_i\times Q_i}f(m,n)|\geq c^{-1}.

In the other direction, if no such decomposition of a diagonal matrix exists, then the Hahn-Banach theorem gives us a linear functional that separates the class of diagonal matrices with trace at least 1 from the class of linear combinations of HAP products defined above. It is easy to check that this functional must be a diagonal matrix (f(m,n)) with a constant diagonal such that the value along the diagonal is at least 1 and such that |\sum_{(m,n)\in P\times Q}f(m,n)|\leq c^{-1} for any two HAPs P and Q.

The conjecture is so much stronger than EDP that I think it would be a mistake just to assume that it is true. My guess is that it is true, but I would be very interested if there was a counterexample (even if, like the complex sequence above, it is disappointingly simple — in fact, if there is a counterexample, then it seems quite likely that it will be fairly simple). And if there isn’t a counterexample, then the fact that it is so much stronger a conjecture than EDP does this time make me think that the result might be easier to prove than EDP itself.

Until very recently, I had been mainly interested in the dual version of the question (that is, the question about decomposing diagonal matrices), but now it seems to me that the matrix discrepancy question is worth thinking about directly. It is a clean question, and it has the big advantage over the original EDP question that it does not restrict values to the set \{1,-1\}, so a number of methods can be used that cannot be used directly for EDP. For instance, linear programming can be used to get experimental results: Sasha Nikolov may be going to look into this.

Given any matrix f, one can find vectors v_m and w_n such that f(m,n)=\langle v_m,w_n\rangle, so this matrix question is actually trivially equivalent to the non-symmetric vector-valued question I had formulated earlier. But expressing it in terms of vectors makes it harder to think about rather than easier, and that is what had previously put me off thinking about the question directly.

There is one class of matrices that is particularly worth mentioning I think. If EDP is true but this matrix question is false, then the best candidates for counterexamples to the matrix problem are probably matrices of high rank, and an obvious class of matrices that tend to have high rank is matrices that are constant on diagonals (that is, Toeplitz matrices).

Suppose, then, that our matrix f(m,n) is defined to be g(m-n) for some function g:\mathbb{Z}\to\mathbb{R} such that g(0)=1. Then \sum_{m\in P,n\in Q}f(m,n)=\sum_xg(x)P*(-Q)(x), where by P*(-Q)(x) I mean the number of ways of writing x as y-z with y\in P and z\in Q. So we have a class of functions that I’ll call HAP convolutions, and we’d like to show that if g:\mathbb{Z}\to\mathbb{R} is any function with g(0)=1 and C is any constant, then there exists a HAP convolution \phi such that \langle g,\phi\rangle\geq C. This is true if and only if there is an efficient way of writing the function that is 1 at 0 and 0 everywhere else as a linear combination of HAP convolutions. This is another question that could be investigated using linear programming, and perhaps since it concerns functions of just one variable we could get more extensive results than we could for the general matrix problem.

The modular conjecture.

In his most recent guest post, Gil Kalai reformulates EDP as a question about sums mod p. EDP is trivially equivalent to the following assertion.

Conjecture. For every p there exists n such that for every \pm 1 sequence \epsilon of length n and every r there exists a HAP P\subset\{1,2\dots,n\} such that \sum_{x\in P}\epsilon(x)\equiv r mod p.

At first that doesn’t look like a very interesting reformulation since it is too obviously equivalent to EDP. But what makes it interesting is that it has a very natural generalization that doesn’t have any obvious counterexamples.

Stronger Conjecture. For every p there exists n such that for every sequence s of length n of non-zero numbers mod p and every r there exists a HAP P\subset\{1,2\dots,n\} such that \sum_{x\in P}s(x)\equiv r mod p.

In other words, we replace the condition that the sequence takes values \pm 1 by the much weaker condition that it is never zero. Gil calls this the modular conjecture. (He also presented it in a comment on a much earlier EDP post.)

As Gil points out in his post, one can write down a polynomial that is identically zero (mod p) if and only if the modular conjecture is true for n. It is tempting to try to prove that it is zero by analysing its coefficients. More generally, this approach to the problem appears to open the door to a number of algebraic methods.

If you want to prove EDP this way, you have to solve the conjecture for some non-zero r. (Since p is prime, if you can show it for one then you’ve shown it for all.) However, the problem with r=0 is interesting in its own right, and in particular it seems to be interestingly different from the problem with non-zero r. At the time of writing, I don’t see any way of modifying the EDP examples to obtain exponentially long sequences mod p that avoid zero sums — it seems to me that the upper bound on the length could be significantly smaller. That would be interesting, as it would place constraints on what a proof could look like for non-zero r.

A fourth strengthening.

This isn’t really meant as part of the body of the post, but more of an afterthought. A strengthening of EDP that has been considered since very early on in the project is where you replace a \pm 1 sequence by a sequence of unit vectors in a Hilbert space. To be precise, one looks at the following statement.

Conjecture. Let v_1,v_2,\dots be a sequence of unit vectors in a Hilbert space and let C be a real number. Then there exists a HAP P such that \|\sum_{n\in P}v_n\|\geq C.

There is something slightly curious about this conjecture, which is that it is very hard to see how having infinitely many dimensions to play with could help one find a counterexample. In some sense, if you use too many dimensions, then it ought to be the case that there will be a HAP P such that the vectors v_n with n\in P are pointing in lots of different directions and therefore not cancelling. That makes me wonder whether one can prove that if there is a counterexample to the above conjecture, then there must be a counterexample for some finite-dimensional Hilbert space. Or if that is too much to ask, perhaps there might have to be a counterexample where all the v_i live in some compact set. I think it would be very interesting to think about whether the vague intuition I have just expressed can be made precise. As it stands, it is of course not even close to a proper argument. (I should stress one aspect of what I am saying. If there is any vector sequence (v_n) of bounded discrepancy, then one can arbitrarily modify v_p for each prime p and the sequence will still have bounded discrepancy. So I’m not suggesting that every bounded-discrepancy sequence lives, or almost lives, in finite dimensions, but that it can be used to construct one that does.)

As I write that, another question occurs to me. For this one I don’t even have a vague intuitive argument. Let’s suppose that we can find a counterexample f to the matrix discrepancy question earlier. Suppose also that f(m,n) takes the form \langle v_m,w_n\rangle for some (not necessarily unit) vectors v_m and w_n in a Hilbert space. Must there be an example where the v_m and w_n lie in a finite-dimensional Hilbert space, or at least in a compact subset of a Hilbert space?

A combined generalization.

A second afterthought is that the matrix question has a modular version that might be of some interest. Let p be a prime and let f be a function from \mathbb{N}^2 to \mathbb{Z}_p with f(n,n)=1 for every n. Must the sums of f on products P\times Q take all possible values mod p? What if we merely ask for f to take non-zero values on the diagonal?

If the strong modular conjecture is false, then we can turn a counterexample (x_n) into a diagonal matrix in the obvious way and we get a counterexample to the second question. Indeed, suppose that f(n,n)=x_n for every n and f(m,n)=0 when m\ne n. Then \sum_{m\in P,n\in Q}f(m,n)=\sum_{n\in P\cap Q}x_n, which avoids some value, since P\cap Q is a HAP. But with matrices there are many more ways of trying to avoid particular values, so the strong modular matrix conjecture looks like a much stronger statement. Again there are two cases — avoiding 0 and avoiding a non-zero value — of which only the second obviously implies EDP.

About these ads

24 Responses to “EDP26 — three generalizations”

  1. gowers Says:

    I have an suggestion for how one might attempt to get a handle on the matrix question in either its real or its mod-p form in the special case where we insist that the HAPs have the same common difference. Let’s imagine trying to build a counterexample: that is, an N\times N matrix (with N arbitrarily large) such that the sum over any product P\times Q of HAPs P and Q of the same common difference has absolute value at most C (or avoids t mod p). We might attempt to do this by finding an ordering a_1,\dots,a_N of the numbers from 1 to N such that every number in that ordering precedes all its factors. We could then attempt to define the matrix by choosing its values at points (x,y) with highest common factor a_1, then points with highest common factor a_2, and so on.

    If we pursued such a strategy, then what would we have to do when we got to a_k? We could decide that we would worry only about sums over P\times Q where the common differences of P and Q were both a_k. If we did this, we wouldn’t mess up any of our earlier work, since we would be choosing values at points (x,y) that were not both multiples of any predecessor of a_k (since all factors of a_k appear after a_k in the ordering).

    So far so good, but the problem is that the number of points where we get to choose values is smaller than the number of HAP products that we are trying to deal with. For example, when we get to a_N, which equals 1, we have chosen the values of the matrix for all non-coprime pairs (x,y). That leaves us approximately 6N^2/\pi^2 values to choose, since that is roughly the number of coprime pairs, but the number of sums we need to worry about is N^2, since that is the number of products of HAPs of common difference 1.

    However, in the mod-p version, it’s not clear that we can’t deal with several HAPs at once. For example, if I have numbers a_1,\dots,a_m and want to choose x such that none of a_1x,\dots,a_mx is congruent to r mod p, I can do it easily if m<p.

    So here is a question that could be helpful. Suppose you have defined a function f:\{1,2,\dots,N\}^2\to\mathbb{Z}_p on all pairs (x,y) that have a non-trivial common factor. Can you choose the values of f at coprime pairs in such a way that the sum of f over any set of the form \{1,2,\dots,m\}\times\{1,2,\dots,n\} is not equal to r?

  2. gowers Says:

    Let me try to answer the question at the end of the previous comment in a trivial way. I don’t expect to succeed, but would like to know what goes wrong.

    I think it will be easier if I ask a more abstract question. Suppose I’ve got sets A_1,\dots,A_m\subset\{1,2,\dots,n\} (where m and n are not the same as the m and n above) and numbers t_1,\dots,t_m and I want to find a sequence x_1,\dots,x_n of numbers mod p such that \sum_{i\in A_j}x_i is never congruent to t_j mod p. Is there a simple sufficient condition that allows me to choose such a sequence? I’m hoping for something a bit like Hall’s condition for finding a perfect matching, but unlike with that problem I think it is unrealistic to ask for a simple sufficient condition that is also necessary.

    A very simple sufficient condition is this: that for each i the number of sets A_j with maximum element i is at most p-1. If that is the case, then let’s suppose we have chosen x_1,\dots,x_r in such a way that the conclusion we want is true for all sets A_j that are contained in \{1,2,\dots,r\}. There are at most p-1 sets of maximum element r+1, so we can choose x_{r+1} so as to ensure that none of the sums over those p-1 sets takes a value we don’t want it to. (Proof: for each set, there is one bad value of x_{r+1}, so at most p-1 bad values in all.)

    That condition can be generalized in a trivial way: it is enough for it to hold for some total ordering of the ground set.

    So now let’s ask whether we can find a permutation that does the job when the ground set is the set of all coprime pairs (x,y)\in\{1,2,\dots,N\}^2 and the sets are intersections of this set with sets of the form I_{m,n}=\{1,2,\dots,m\}\times\{1,2,\dots,n\}. We would like to find a total ordering (x_1,y_1),(x_2,y_2),\dots such that for each r the number of sets I_{m,n} that contain (x_r,y_r) and no further (x_s,y_s) is at most p-1. Is this possible?

    The answer would be trivially no if the number of coprime pairs were less than p^{-1}N^2, but that is not the case, and becomes less and less the case as p gets bigger. However, there are little problematic places, such as rows where one of the coordinates has lots of small prime factors, which leads to long strings of points that are not coprime pairs. I don’t yet see whether that kind of problem makes the answer obviously no, or whether it might be possible to get round it in a clever way.

  3. gowers Says:

    So far that isn’t particularly reminiscent of Hall’s theorem. But what if we ask for conditions under which we can be sure that an appropriate ordering of the ground set exists? If there were a neat characterization, then it might conceivably look a bit like Hall’s condition.

    One small remark is that if all the sets in the set system have size 2, then we are looking for an ordering of the vertices of a graph such that each vertex is joined to at most p-1 earlier vertices. That is a well-known condition: such a graph is said to be (p-1)-degenerate. So we are looking at a certain hypergraph generalization of degeneracy.

    Another small remark is that without the coprimeness condition the problem is easy: just take any ordering of \{1,2,\dots,N\}^2 that extends the partial order where (x,y)<(z,w) if and only if x<z and y<w. Then the only I_{m,n} that has (x,y) as its last element in this ordering is I_{x,y}. So that system is 1-degenerate.

    Suppose we totally order just the coprime pairs in a way that extends the coordinate-domination order. That alone doesn’t work, since if, for example, a segment of our order is (m!,m!+2),(m!,m!+3),\dots,(m!,m!+m), and if all those points are bigger than all points (u,v) such that u<m! and v\leq m, then the point (m!,m!+1) is the maximal coprime pair belonging to all the intervals I_{m!,m!+j} with 2\leq j\leq m. So if m>p, then the condition is violated.

    More generally, suppose we have an m\times m square of points (x,y) such that none of them is a coprime pair. Is there any hope of finding an ordering that works?

    The answer is not obviously no. Suppose, for instance, that we take the complement of the set of all points in the square \{(x,y):u\leq x<u+m,v\leq y<v+m\} and try to order this complement in such a way that the degeneracy condition holds.

    Hmm … I’ve changed my mind. I think the answer is obviously no. Suppose that the maximal pair in our ordering that belongs to the set I_{u+m,v+m} is the pair (a,b). Then it is the maximal pair in any set I_{x,y} such that a\leq x\leq u+m and b\leq y\leq v+m. Since (a,b) does not belong to the square above, there are at least m such sets I_{x,y}.

    • gowers Says:

      OK, the failure above is good news, because it shows that there isn’t a trivial just-do-it counterexample to the strong modular matrix EDP. Before I discuss what that teaches us, let me briefly remark that the simple argument just given points to an obvious necessary condition for an ordering to exist: it must be the case that every set A\in\mathcal{A} at least contains a point that is in at most p-1 of the other sets in \mathcal{A} that are subsets of A. If that fails, then trivially there is no ordering of the points such that the maximal element of A is the maximal element of at most p-1 other sets in \mathcal{A}.

      But that’s not particularly relevant, because an ordering of that kind does not exist. So if we are determined to find a counterexample, then either we have to worry about big rectangles of points that do not contain any coprime pairs, or we have to ensure somehow that the values we have already chosen in those rectangles make choosing the coprime pairs easier than it would normally be, or we have to give up on the idea of dealing with HAPs with common difference d before we deal with HAPs with common difference a factor of d. None of these options seems very palatable. In short, finding a counterexample looks hard.

  4. Alec Edgington Says:

    A trivial observation about the ‘stronger’ modular conjecture for r=0: to find an exponentially long sequence modulo p that avoids zero sums along HAPs it would be natural to look for a multiplicative function whose partial sums avoided zero.

    • Alec Edgington Says:

      If I’ve understood the comments that Gil linked to from earlier posts, it seems that, at least for p=5, avoiding zero is easier than avoiding a non-zero value. (One can have sequences at least as long as 155 in the former case, but no longer than 83 in the latter.)

    • gowers Says:

      One reason I thought that avoiding zero might be harder than avoiding a non-zero value is that finding a multiplicative sequence of that kind seems quite hard. The techniques we have used up to now tend to rely heavily on the fact that a sum of small numbers is small. But if you want to avoid zero, then you can’t use that. You can use the fact that a big number plus a small number is big, but then you have to have a bigger supply of big numbers than it seems possible to get. I’m therefore quite surprised by what you say about p=5, but perhaps it is the law of small numbers striking.

    • Jason Conti Says:

      I was going to add that it may not necessarily be easier to avoid 0 than 1, since with zero we have more symbols to work with: {1, 2, 3, 4} for 0 mod 5 but only {2, 3, 4} for 1 mod 5. But I tried avoiding 0 with only {2, 3, 4} and I actually get an example of length 149 (which I think is maximal):

      2, 2, 2, 2, 3, 2, 3; 2, 3, 3, 2, 2, 3, 3; 2, 2, 3, 3, 2, 3, 3
      2, 2, 2, 3, 3, 2, 3; 2, 2, 3, 2, 3, 3, 2; 3, 3, 2, 2, 3, 2, 3
      3, 2, 3, 2, 3, 2, 4; 3, 3, 3, 2, 2, 2, 3; 3, 2, 3, 2, 3, 3, 2
      2, 3, 3, 2, 3, 2, 2; 3, 3, 2, 3, 2, 2, 3; 2, 2, 3, 3, 4, 3, 3
      2, 3, 2, 2, 3, 3, 2; 2, 3, 3, 2, 2, 4, 2; 2, 3, 2, 3, 2, 3, 3
      2, 2, 2, 4, 2, 2, 3; 4, 3, 3, 2, 3, 3, 2; 2, 3, 3, 2, 3, 2, 2
      3, 2, 3, 3, 2, 3, 4; 2, 3, 3, 2, 2, 4, 2; 2, 3, 2, 3, 3, 2, 2
      3, 2

  5. gowers Says:

    It occurs to me that I haven’t completely killed off the simple approach I was trying to use to obtain a counterexample to the strong modular matrix conjecture in the case of HAPs with the same common difference. I’ve shown that the simple approach fails if you insist on choosing the value at (a,b) before you choose the value at (c,d) if the highest common factor of c and d strictly divides the highest common factor of a and b. But what if you don’t insist on that? The question then becomes the following. Let \mathcal{A} be the set of all products P\times Q, where P and Q are HAPs and subsets of \{1,2,\dots,N\}. Does there exist an ordering of $\{1,2,\dots,N\}^2$ minus the diagonal such that with respect to that ordering each point (x,y) is the maximal element of at most p-1 sets in \mathcal{A}?

    Let me try to rephrase that question as a question about a certain bipartite graph, because I think it will have a dual formulation. The bipartite graph has two sets of vertices: points in \{1,2,\dots,N\}^2 and sets in \mathcal{A}, with an edge joining a point to a set whenever the point is an element of the set.

    In the abstract, we have a bipartite graph with vertex sets X and Y, and we would like to find an ordering of X such that each x\in X is the maximal neighbour of at most s=p-1 vertices in Y.

    Here is a sufficient condition for such an ordering to exist. Suppose we have an ordering of the vertices not of X but of Y. We could order the vertices of X by saying that x_1<x_2 if the minimal y\in Y that is joined to x_1 is smaller than the minimal y\in Y that is joined to x_2. In other words, we go through the vertices of Y in order and write down any neighbours that we have not yet written down. (In cases where several new neighbours appear at once, we choose the order arbitrarily.)

    Under this ordering, how many elements of Y have maximum neighbour x? Well, let’s write the elements of Y in order as y_1,\dots,y_n. Then x will first appear as a new neighbour of some y_i. It will need to be the largest new neighbour. And then we will need the neighbours of y_{i+1},\dots,y_{j-1} all to be vertices of X that have already appeared as neighbours of earlier points in Y. And finally y_j will have a neighbour that has not yet appeared. Under those and only those circumstances, x will be the maximal neighbour of j-i vertices of Y.

    So if we want to avoid that, then we need to find an ordering of the vertices of Y such that as we write down their neighbours, there is never a string of more than s vertices in Y without a new neighbour appearing.

    Going back to our specific bipartite graph, that tells us that we would like to find an ordering of the HAP products P\times Q such that if we look at the union of the first k products, there is never a string of s of these unions without a new element appearing.

    Can that be done? It is crucial that the common differences should be the same, or there will be too many HAP products and the answer is trivially no. But if the common differences have to be the same, then the number of HAP products is roughly N^2+(N/2)^2+(N/3)^2+\dots and is therefore at most CN^2 for some absolute constant C. So the existence of such an ordering is not ruled out on trivial grounds. So far I have established that if such an ordering exists, then it will sometimes be necessary for a HAP with common difference a to come earlier than a HAP with common difference b even when b is a non-trivial multiple of a. That’s worrying — in general, it seems much better to put smaller sets earlier in the ordering — but it doesn’t by itself rule out the existence of the ordering, especially as the problematic places (that is, large rectangles full of points that all have coordinates with non-trivial common factors) appear to be quite rare, and the rectangles are small compared with how far out they are from the origin.

    Here is the kind of thing that we might try to do. Suppose R is one of these troublesome rectangles. What worries us is that when we come to HAP products with small common differences (I’m thinking about common differences of 1 as I write this) and maximal points (that is, top right-hand corners) in R, we may find that we have already chosen lots of other HAP products with maximal points in R, so new points will not easily appear. To counter this, we could simply identify the HAP products with top right-hand corners in factor-rich rectangles and label them “troublesome”. Then we could do a preliminary ordering of the non-troublesome HAP products and insert the troublesome ones in at various points, in such a way that each troublesome product appears only after all its points have already appeared (so it won’t mess up anything that has gone on earlier, but also won’t have a new element) and also in such a way that the troublesome products are reasonably spread out, so that the longest interval of sets that don’t contribute a new point is not much longer after the insertions than it was before.

  6. gowers Says:

    I’ve just noticed that my argument that the ordering of coprime pairs doesn’t exist was wrong. So I’m going to go back to that question, but think about it in its dual formulation. That is, I’d like to find an ordering of the rectangles I_{m,n}=\{1,2,\dots,m\}\times\{1,2,\dots,n\} such that when you take partial unions you add at least one new point that’s a coprime pair for every s new rectangles that you include in the union.

    Let’s suppose that we’ve chosen an initial segment of the ordering, and let’s suppose that we’ve done it in such a way that if a\leq c and b\leq d then I_{a,b} is not chosen after I_{c,d}. Then the union will be a down-set (that is, a set of points such that if (c,d) belongs to the set and a\leq c and b\leq d, then (a,b) belongs to the set) and the next rectangle we pick must be a minimal element of its complement.

    One way we could choose our ordering would result from time to time in the union itself being a rectangle. If we did that, then we would have very little choice about which points to pick next, since the complement would have only two minimal elements. But if we’re a bit smarter, we can aim for something more like a triangle — say, the set of all (x,y) such that x+y\leq r — in which case, the complement will have lots of minimal elements.

    Here’s another example of a tricky situation that could arise. Suppose that we decide to fill up diagonal by diagonal. Things will go OK for a while, but at some point we will try to fill up a diagonal such as x+y=m! for some large m. If x+y=m! then x and y are coprime if and only if x has no prime factor less than or equal to m. But the proportion of x that satisfy this condition tends to 0 as m tends to infinity, so there will be some diagonals that contain very few coprime pairs. And we can also have several consecutive diagonals with very few coprime pairs: what it takes is several consecutive numbers each of which has many small prime factors. This happens, by the Chinese remainder theorem and the fact that the sum of the reciprocals of the primes diverges. We just have to pick several disjoint sets of primes all of which have large sums of reciprocals and then pick an integer m such that m is a multiple of all the primes in the first set, m+1 is a multiple of all the primes in the second set, and so on.

    But m has to be very large for us to be able to do this, and there is absolutely no obligation to fill up diagonal by diagonal. If you think of the boundary of the down-set you have filled up so far as a kind of curve that is gradually moving away from the origin, then you can make sure that when a dangerous set of diagonal comes along, the curve doesn’t cross them in too parallel a way.

    Of course, there are plenty of other constraints of a similar kind, and the difficulty is trying to work out how to satisfy all of them at the same time. It’s a tough one because we can’t hope to use some nice description of the set of coprime pairs: I don’t see any alternative to identifying a property that this set has that is sufficient for the expanding curve to be able to pick up points in the set on a regular basis.

    This comment is getting a bit long, so I’ll move to a new one.

    • gowers Says:

      I’m not sure what got into my head there — the argument I said was wrong was right. So quite a bit of what I’ve written in response to its supposed wrongness is not all that relevant to anything.

  7. gowers Says:

    Again it feels helpful to think about an abstract version of the problem. Because of the constraint I’m putting on the ordering, (m,n) is always the unique new element of the union contributed by the set I_{m,n}. So what I’m looking for is a total ordering of \{1,2,\dots,N\}^2 that extends the obvious partial ordering and has the property that any consecutive s points in the total ordering (where s is independent of N) include a coprime pair. In the abstract, I can ask for conditions that allow me to extend a partial ordering to a total ordering in such a way that any s consecutive elements in the total ordering contain an element from some prescribed set. Is there a nice sufficient condition for this?

  8. gowers Says:

    To answer that last question, it seems a good idea to try to find some trivial necessary conditions for such a total ordering to exist. If the partial order doesn’t make any comparisons at all, then a necessary and sufficient condition is obviously that the prescribed set has size at least N/s (give or take integer parts). If the partial order is non-trivial, then we’ll need some kind of relationship between the set and the partial order. But what?

    Since I’m looking for a necessary condition, I should try to think of a fairly general situation where it is not possible to find a total ordering with the desired property. One situation would be if you can find points x<y such that at least m points are obliged to lie between x and y, and fewer than m/s points that are allowed to lie between x and y belong to the prescribed set.

    This is a rather strong-seeming condition. A point z is obliged to lie between x and y if x<z<y, whereas a point w is allowed to lie between x and y if neither w\leq x nor w\geq y hold. Typically there will be many more points of the second kind than the first.

    Thus, this observation gives rise to only a very weak necessary condition for the ordering to exist, which makes it rather unlikely to be sufficient — though of course there are some beautiful combinatorial theorems where apparently weak necessary conditions do turn out to be sufficient.

  9. gowers Says:

    A trivial sufficient condition is that there is a partition of the poset X into antichains X_1,\dots,X_k such that if i<j then no point in X_i is greater than any point in X_j and such that at least |X_i|/s points in X_i belong to the prescribed set. That is perhaps the natural generalization of the comment about the trival poset.

    • gowers Says:

      I also wanted to try to find an algorithm that would fail only under certain circumstances that one could hope didn’t happen. Let A be the prescribed set. The rough idea would be as follows. We pick the total ordering x_1<x_2<\dots element by element. For each k let Y_k be the complement of \{x_1,\dots,x_k\}. Then we try to pick the points x_1,x_2,\dots in such a way that |Y_k\cap A|/|Y_k| stays as large as possible.

      It’s not obvious that that is the right quantity to preserve. The reason I go for it is that I think of the process as “saving points of A for when the going gets tough”. If you find yourself approaching a region where lots of points don’t belong to A, you want to have a number of points of A waiting to be chosen, so that you can intersperse them amongst the points not in A as you continue to choose your sequence.

      If you have chosen a point of A recently (by which I mean more recently than s steps ago) and have a choice between picking a point in A and picking a point not in A, could there ever be a disadvantage in picking the point not in A? I don’t see how there could, but I haven’t quite seen a formal argument for that. If there is no disadvantage, then we can assume that the algorithm has a kind of reverse-greedy property: you pick points of A only if either that’s all you’ve got in front of you or if not doing so leads to a sequence of s consecutive points not in A.

  10. gowers Says:

    I think I may have made a mistake earlier. Suppose I have a total ordering of the HAP products in such a way that a new element appears at least every s steps? If I order the elements according to when they first appear in one of the HAP products, is it really true that each element can be a maximum of at most s of the HAP products?

    Unfortunately, it doesn’t follow at all. I need to think about this.

  11. gowers Says:

    Let me go back to the abstract question about bipartite graphs. Suppose you have a bipartite graph with vertex sets X and Y and a total ordering on X such that for every x\in X there are at most s vertices y\in Y such that x is the maximal neighbour of y. I’d like to characterize this condition in a more Y-focused way. That is, I’d like conditions on the neighbourhoods of the vertices in Y that are necessary and sufficient for such an ordering to exist.

    A sufficient condition is that Y can be partitioned into sets Y_1,\dots,Y_m of size at most s such that no neighbourhood of any vertex in Y_i is contained in the union of the neighbourhoods of the vertices in Y_1\cup\dots\cup Y_{i-1}. If such a partition exists, then let X_i be the set of vertices that are neighbours of a vertex in Y_i but not of any vertex in Y_j for any j<i. If we order the vertices in X in such a way that if j<i then every vertex in X_j precedes every vertex in X_i, then a vertex in X_i can only be a maximal neighbour of y if y\in Y_i. (Proof: it isn’t a neighbour at all if y\in Y_j for some j<i, and if j>i then by assumption y has a neighbour that is not joined to any of Y_1,\dots,Y_i, so it is greater than all vertices in X_i in the ordering.) Since the Y_i have size at most s, we are done.

    This condition is also trivially necessary, since if an ordering x_1,\dots,x_n satisfies the original condition, then we can define Y_i to be the set of all y\in Y with maximal element x_i and the sets Y_i satisfy this condition.

    In the case of HAP products, we want to partition the set \Sigma of all such products into sets \Sigma_1,\dots,\Sigma_m of size at most s in such a way that no P\times Q in \Sigma_i is contained in the union of all the sets in \Sigma_1\cup\dots\cup\Sigma_{i-1}.

  12. gowers Says:

    I feel like returning to EDP itself, and the diagonal decomposition approach where one is allowed to use products of HAPs that may have different common differences (since that would prove EDP and it’s not clear that the result is even true if you insist on the same common difference).

    In general, it seems that the reason it is difficult to come up with a counterexample to EDP is that eventually you start facing too many constraints all at once. That happens because some numbers are contained in lots of HAPs. It occurs to me that the reason we have trouble proving anything is that we are trying to find decompositions in a place where they don’t exist, and what we should be doing is looking at some long interval in which every number has lots of small factors. Exactly what that means is not quite clear, and one might perhaps loosen it to almost all numbers having lots of small factors, but let me try to give a clearer idea.

    An observation we made a long time ago was that instead of looking at HAPs we could instead look at shifted HAPs. The way it would work is that if n is a prime power p^k then we choose an integer a_n and let A_n be the residue class of all integers congruent to a_n mod n, making sure that A_p\supset A_{p^2}\supset. Then for general n=p_1^{r_1}\dots p_k^{r_k} we let A_n be the intersection of the sets A_{p_i^{r_i}}. The reason we can do this is that if we manage to prove a large discrepancy for these shifted HAPs, then we can use the Chinese remainder theorem to find an integer N such that N+m is divisible by n if and only if m\in A_n. In other words, “near N the HAPs look like shifted HAPs”.

    It occurs to me now that if we do this then we may find it easier to find a decomposition, because we won’t be near the incredibly unusual number 0, which is a multiple of everything. If we shift all HAPs randomly (subject to the constraints), then a typical number will belong to A_n for lots of small n. The sort of reason this might be useful is that if we take lots of products A_n\times A_m, then we can hope to cover the pairs (x,y) much more evenly than if we use HAPs and have to say things like that if x is a prime then it is contained in only two HAPs.

    • Alec Edgington Says:

      Thinking in terms of these shifted HAPs seems to be easier if we restrict ourselves to HAPs with square-free common difference, since then we just need to choose an arbitrary residue class modulo p for each p. I don’t remember if we ever thought much about this strengthening of EDP — it isn’t quite the same as Gil’s ‘square-free EDP’, where the sequence is set to zero at non-square-free numbers — or if we rejected it as false?

    • gowers Says:

      The sequence 1,1,-1,-1,1,1,-1,-1,… is a counterexample for square-free EDP, so unfortunately we can’t make that simplification.

    • Alec Edgington Says:

      Ah, good point.

    • gowers Says:

      I should add that it’s a point that I too missed recently (or had perhaps forgotten about) and that Gil put me right on. For the complex version of the EDP you can’t prove anything unless every m divides the common difference of one of your HAPs, since if m doesn’t then you can rotate through the mth roots of unity. In the real case, you can’t use a periodic example if for every k you have HAPs with common difference 2^k, so it’s less clear what happens, but since the promising approaches (apart from the modular conjecture) would yield the complex case as well, it looks difficult to prove anything without a pretty rich set of HAPs.

  13. plm Says:

    Actually Tim, I find your example quite deep. It is not at all obvious that what makes competition or school problems difficult is sometimes the same as what makes research problems difficult: misleading hints or context.

    Because in the case of problems there is the psychological aspect of “game against the problem poser” (e.g. is he trying to trap students?).

    So your example is thought-provoking.

    Thanks.

  14. plm Says:

    Well I phrased my comment poorly but I hope useful meaning can still be extracted from it. Anyway, thanks for the nice post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,558 other followers

%d bloggers like this: