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.

24 Responses to “EDP26 — three generalizations”

gowers Says:
September 6, 2012 at 12:04 pm | Reply
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$ ?
gowers Says:
September 6, 2012 at 2:26 pm | Reply
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.
gowers Says:
September 6, 2012 at 4:41 pm | Reply
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:
  September 6, 2012 at 5:22 pm
  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.
Alec Edgington Says:
September 6, 2012 at 10:04 pm | Reply
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:
  September 7, 2012 at 7:01 am
  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:
  September 7, 2012 at 8:15 am
  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:
  September 9, 2012 at 4:06 am
  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
gowers Says:
September 7, 2012 at 10:42 am | Reply
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.
gowers Says:
September 7, 2012 at 3:27 pm | Reply
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:
  September 7, 2012 at 9:31 pm
  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.
gowers Says:
September 7, 2012 at 3:42 pm | Reply
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?
gowers Says:
September 7, 2012 at 5:08 pm | Reply
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.
gowers Says:
September 7, 2012 at 5:10 pm | Reply
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:
  September 7, 2012 at 5:54 pm
  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$ .
gowers Says:
September 7, 2012 at 6:03 pm | Reply
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.
gowers Says:
September 7, 2012 at 9:47 pm | Reply
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}$ .
gowers Says:
September 9, 2012 at 10:06 pm | Reply
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:
  September 12, 2012 at 7:10 am
  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:
  September 12, 2012 at 9:16 am
  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:
  September 12, 2012 at 12:17 pm
  Ah, good point.
- gowers Says:
  September 12, 2012 at 2:06 pm
  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 $m$ th 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.
plm Says:
September 29, 2012 at 5:19 am | Reply
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.
plm Says:
September 29, 2012 at 5:25 am | Reply
Well I phrased my comment poorly but I hope useful meaning can still be extracted from it. Anyway, thanks for the nice post.