I think this will be a bit long for a comment, so I’ll make it a post instead. I want to try to say as clearly as I can (which is not 100% clearly) what we know about a certain way of constructing a decomposition of the identity on Recall from the last post or two that what we want to do is this. Define a square in to be a set of the form where by I mean the set of all positive integers such that Let us identify sets with their characteristic functions. We are trying to find, for any constant a collection of squares and some coefficients with the following properties.
- where and is the number of points in the interval that defines or, more relevantly, the number of points in the intersection of with the main diagonal of
- Let Then for any pair of coprime positive integers we have
The second condition tells us that the off-diagonal elements of the matrix you get when you convert the decomposition into a matrix indexed by are all zero, and the first condition tells us that we have an efficient decomposition in the sense that we care about. In my previous post I showed why obtaining a collection of squares for a constant implies that the discrepancy of an arbitrary sequence is at least In this post I want to discuss some ideas for constructing such a system of squares and coefficients. I’ll look partly at ideas that don’t work, so that we can get a sense of what constraints are operating, and partly at ideas that might have a chance of working. I do not guarantee that the latter class of ideas will withstand even five minutes of serious thought: I have already found many approaches promising, only to dismiss them for almost trivial reasons. [Added later: the attempt to write up even the half promising ideas seems to have killed them off. So in the end this post consists entirely of half-baked ideas that I’m pretty sure don’t work. I hope this will lead either to some new and better ideas or to a convincing argument that the approach I am trying to use to create a decomposition cannot work.]
Using squares and fly traps.
A general idea that I have not managed to rule out is to build a decomposition out of “squares and fly traps”. I’ve already said what a square is. If you take the two squares and then their difference is the set of all points or such that It has the shape of two adjacent edges of a square. It is this kind of shape that I am calling a fly trap.
The idea then is to take a collection of fly traps with negative coefficients and a collection of squares with positive coefficients. In order for the second condition to hold, we need the following to hold: as you go along any line from the origin other than the main diagonal if you sum up the coefficients associated with the squares you visit, then the result should be cancelled out by the sum of the coefficients associated with the fly traps. In particular, if all squares have coefficients equal to 1 and all fly traps have coefficients equal to -1, then the number of times the line hits a square should be the same as the number of times it hits a fly trap. (I think of the squares as sending out “flies” that are then caught by the fly traps, which have some nasty sticky substance at their points.)
It’s not really necessary for the fly traps all to point in the same direction, and there are other small adjustments one can make, but the basic square/fly-trap idea seems to be what the computer is telling us works best in very small cases. (It is far from clear that this is a good guide to what happens in much larger cases, but it seems sensible at least to consider the possibility.)
For a nice illustration of a square/fly-trap construction, see this picture that Alec produced. Alec also has a general construction that gives us arbitrarily close to 2. Rather than repeat it here, let me give a link to the relevant comment of Alec’s (if you think of the bar as squaring the interval, it will be consistent with what I am saying in this post), and a link to a similar comment of Christian’s.
This example (or rather family of examples) uses a single fly trap of width and squares of width 2 (unlike the example in Alec’s picture, which I therefore find more interesting, despite the fact that it gives a worse constant). It is instructive to see why this gives us a bound of If the fly trap has width then it has off-diagonal points. So we need flies. Each square of width 2 contributes two flies, so we need such squares. This means that (since the fly trap needs two squares to make it) and that The ratio of these two numbers tends to 2 as tends to infinity.
It is not hard to see that if we could use squares of width 3 instead, then we would be able to get a constant arbitrarily close to 3. However, significant difficulties arise almost immediately. However again, this could be good news, because if we can find some way of getting beyond 2, we may by that stage have found a pattern that can be generalized. And I think there is some hope of pushing beyond 2, as I shall now try to explain.
One fly trap is not enough.
First, let us see why there is absolutely no hope of achieving this with just one fly trap. The argument is simple. Let be the flytrap If all the off-diagonal points in the square are caught by this fly trap, what can we say about ? One necessary condition is that both and are factors of But this implies that is at least which in turn implies that is at least Since we need almost all points in the fly trap to catch flies, we need at least distinct flies, which is more than So, roughly speaking, we need a constant fraction of the numbers of order of magnitude to be such that both and are factors of This just isn’t going to happen.
Note that if we make smaller, to give numbers near a better chance of dividing then we are forced to increase (or else the flies miss the fly trap). And that makes things even worse — we now have fewer possible flies and a bigger fly trap.
I’m sure it would be easy to state and prove something rigorous here, but for now I’d prefer to leave those thoughts as a convincing enough demonstration that a single fly trap will not do the job. But if that’s the case, what can we do? Well, the obvious next thing to try is several fly traps.
Pure randomness as a way of catching flies.
How can we make use of multiple fly traps? A first thought is that if we take the square and send out some flies, we could create two traps, one to catch flies with maximum coordinate and the other to catch flies with maximum coordinate But the trouble with this is that it seems to be far too tailored to one particular square: it is hard to believe that such a trap could catch the flies from several different squares. We would be asking for two integers and such that there are many integers such that one of and divides and the other divides
Actually, on writing that I realize that I have given no thought to it at all, so perhaps it is worth trying to show that it cannot be done (just in case, contrary to expectations, it can be done).
Since and are always coprime, there seems no point in giving and any common factors, so let’s take and to be highly smooth numbers that are coprime to each other. And let’s try to find 3-by-3 squares that send out flies that are caught by one of the fly traps or (I’m assuming that and are roughly the same size. If it is convenient to take different s then I don’t mind doing it, but I don’t expect it to help.)
If is fixed and and are large, then … I think we’re completely dead. We have fly trap points below the diagonal to get rid of and three flies below the diagonal per 3-by-3 square, so we need about squares. If is one of those squares, then for the fly at not to miss the fly traps, we need to be at least where is the rough size of and So we need pairs such that we can find an integer with and But that more or less fixes the ratio of to and anyway is bigger than
From this I am happy to conclude that we need to change our attitude and go for many fly traps. The idea would be that the reason a fly hits a fly trap is not that the fly starts out at a very carefully chosen point (roughly speaking, a “factor” of the fly trap) but that there are enough fly traps for it to be almost inevitable that the fly will hit at least one of them.
What I mean by “pure randomness” is that we use the following mechanism for ensuring that the fly at hits a trap. If then we simply make sure that there are at least traps, fairly randomly placed, or rather traps for some large constant Then the probability that the fly misses all traps is small: roughly speaking, the expected number of traps it hits is and if we can get enough independence then we can hope that all flies will hit roughly of the traps. (This model turns out to be much too crude, since the probability of a fly hitting a trap depends very much on divisibility properties of the coordinates of the fly and the trap. But let us work with it for now.)
Some back-of-envelope calculations.
Let us try to check the feasibility of this idea. An initial observation is that most fly traps are useless for our purposes. If you choose a random large integer then the fraction of integers coprime to will be around (If is the other integer, then the probability that divides both and is so the probability that they are coprime is roughly ) But if is coprime to then the point cannot catch any flies. If we have a large set of such points, then we are in trouble.
To deal with this, it seems that the only option we have is to insist that our fly traps occur at highly composite values of so that almost all other integers have quite high common factors with and therefore give rise to points that can catch many flies. It will be convenient to call and the height and width of the fly trap In that language, we want fly traps with highly composite heights. (Note that the height refers to the altitude of where the fly trap is placed, whereas the width measures the size of the trap itself. Indeed, “altitude” is probably a better word than “height” here, but I prefer an Anglo-Saxon word if there is one.)
Now let us suppose that we have 3-by-3 squares, and a reception committee of fly traps with highly composite heights between and If the widths of the fly traps are all (or perhaps all between and or something like that), then we’ll need fly traps if we want a one-to-one correspondence between flies and trap points, and a bit more than that if we want each fly to hit traps. Let us take fly traps.
Now consider a fly at say. If its chances of hitting a given trap are then we’ll also need there to be about fly traps. That is, we’ll want to be about And for that fly not to miss the traps altogether (because its angle from the main diagonal is too large), we’ll need to be at most So we’ll need to be bigger than That looks pretty problematic, because we now need a very large number of fly traps, and it will not be possible to put them all at highly smooth heights between and : there just aren’t that many highly smooth numbers.
Just to make that more conceptual, the problem we have is that there are two conflicting pressures on the flies. If they are not high enough, then the angle they make with the main diagonal is forced to be large and they therefore miss all the fly traps. But if they are too high, then they are very unlikely to hit any given fly trap, which forces the fly traps to be extremely numerous, which forces there to be several fly traps at non-smooth heights, and therefore several points in the traps that cannot catch flies.
Smooth traps and smooth squares.
Is there anything we can do to get round this problem? I think there may be. There was one questionable assumption in the discussion above, which was that the probability of a fly hitting any given fly trap was about The condition we need for this fly to hit the trap is that should divide and that should be at least Now if we choose randomly, then of course the probability that is But if we choose it as a random number with lots of small prime factors, and if also has quite a lot of small prime factors, then we hugely increase the chances that For instance, if is a random multiple of 6, and also happens to be divisible by 6, then the chances that divides are now
Let us now go back to the attempt above. Again let us suppose that we have 3-by-3 squares. Again, if we are taking fly traps with between and and if we want each fly to hit traps, then we will need about or so traps. But now let us suppose that all the traps have very smooth heights. More precisely, let us suppose that all the heights are such that all but a small proportion of integers have a fairly high common factor with Simplifying absurdly, let us suppose that this gains us an extra factor of when we think about the probability that a fly or is caught by a given fly trap: now the probability is more like rather than What does that do for us?
It means that now, if we want each fly to hit traps, we’ll need not traps (where is the height of the fly) but more like traps. We already know we need about traps, so equating the two we find that needs to be about And if we want a fly at that kind of height not to be too far from the diagonal to hit the traps, we need to be at most which tells us that should have approximate size which is rather better than the earlier estimate of (up to a constant).
But at this point we have an important question: are there enough highly smooth numbers between and ?
To answer that, we need to think about what the typical probability gain is for a given number. Suppose, for instance, that is divisible by where is some set of small integers. For what can we say that a random integer has a good chance of having a highest common factor with of at least ?
The expected number of such that is and we can expect this to be reasonably concentrated if the expectation is not too small. Writing for and assuming that is a fairly dense set of primes (something like a random set of of the first primes, say) then the expectation will be around so the value we get for assuming (not quite correctly) that the primes that divide are fairly evenly distributed, ought to be around or around (We could get there by saying that the typical size of a is fairly close to and we are choosing of these primes.)
This is fairly worrying, because in order to gain a factor we have to make the set of we are allowed to choose very much sparser. It seems as though we lose a lot more than we gain by doing this.
The “smooth squares” in the title of this section refer to the possibility that we might try to choose so that both and have quite a lot of small prime factors. But such numbers are hard to come by, so again it seems that any gain one might obtain is more than compensated for by the loss in their frequency.
Special configurations of squares and fly traps.
Can we achieve what we want by making very careful selections of our s? It’s clear that something that helps us is to have pairs of heights such that is, when written in its lowest terms, of the form or
It’s quite easy to find such that all of are of this form: just make extremely smooth and make all the differences small. Then the differences will divide and we are done. But what if we try to ensure that and are of the required form? Then we need large positive integers and such that is of the form for a positive integer That is, we need the reciprocal of to be an integer. Rearranging, we want to be an integer. It’s moderately reassuring to observe that this can be done: for instance, if and we get But how about if and are very large? Or perhaps they don’t have to be very large, just as long as we can find a set such that many of the ratios are integers.
Let’s think about this slightly further. Suppose we have such a collection of integers. Then choose with enough factors for all the numbers I mention to be integers, and for each let What we want is for to divide That is, we want to divide So we need to be an integer. (This doesn’t look very symmetric, but it is true if and only if is an integer.)
Suddenly this looks a bit easier. It looks as though we’ll be OK if we make the all fairly smooth and make their differences small. Hmm … except that that doesn’t look easy after all, since if is smooth and is small, then will not be all that smooth.
I won’t think about this for the time being, but I think it may be possible to construct, in a not quite trivial way, an arbitrarily long sequence of integers such that is always an integer.
Let’s suppose we managed that. Would it help? What we could do is this. We let be some huge factorial so that it’s divisible by whatever we need it to be divisible by. We then define the numbers as above: that is, Since whenever we have of the form for some positive integer we can find an integer such that and
Therefore, potentially at least, we could consider using the square to knock out some points in the fly traps at heights and
However, for this to have a chance of working, we want to be big, since otherwise our flies will be out wide again, which will force the traps to be big and we’ll get into all sorts of problems.
But it’s problematic either way. If we want traps of width at most some fixed then we need to be at least For that we need the integers to be of size at least (since ), and more than that unless they are close together.
But we also need the to divide so we can’t just choose the and then make huge. Rather, what we seem to want is a number that has so many factors of size somewhat bigger than that we can find interesting clusters of them such that many of the numbers are integers.
I should think a bit more about how many of these numbers actually need to be integers. Perhaps we don’t need them all to be integers — if not, then we would have a much greater chance of success.
If the fly traps have width then we have points below the diagonal that need to be hit. Each good pair leads to three flies that can do the hitting. So it looks as though needs to be bigger than
I think I must have made a mistake here, since there are basically only two chances to hit the point : we must do so either at or at So we need an extraordinary miracle to occur: it must be possible to partition (almost all of) the numbers and into pairs of consecutive integers. This does not feel possible to me.
I’m going to stop at this point. I’ll end with the obvious question: is it possible to create an example out of squares and fly traps? Part of me thinks that the square/fly-trap idea is almost forced, since we need the bigger points to avoid coprime pairs. I think also that I have not devoted enough space to discussing bigger fly traps — ones where the width is proportional to the height, say. This requires bigger squares, but it may be possible to do something. In fact, I’ll think about that (not for the first time) and if anything interesting comes out of it then I’ll extend this post.