VizualBusiness: EDP26 — three generalizations

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.

DIGITAL JUICE

VizualBusiness

Sunday, September 9, 2012

EDP26 — three generalizations

No comments:

Post a Comment

Digital Juice for Primary Education

About Me

Translate

Total Pageviews