Problems related to Littlewood's conjecture

This is the third in a series of posts in which I discuss problems that could perhaps form Polymath projects. Again, I am elaborating on a brief discussion that appeared in an earlier post on possible future projects. [Not for the first time in my experience, WordPress’s dates have gone funny and this was posted not on the 17th as it says above but on the 20th.]

An obvious objection to the Littlewood conjecture as a Polymath project is that it is notoriously hard. On its own that might not necessarily be a convincing argument, since part of the point of Polymath is to attempt to succeed where individual mathematicians have failed. However, a second objection is that the best results in the direction of the Littlewood conjecture, due to Einsiedler, Katok and Lindenstrauss, use methods that are far from elementary (and far from understood by me). I envisage this project as an elementary one, at least to begin with, so does that make it completely unrealistic? I shall try to argue in this post that there is plenty that could potentially be done by elementary methods, even if attempting to prove the conjecture itself is probably too ambitious.

Another advantage of tackling the conjecture by elementary means is that if we find ourselves forced to reintroduce the non-elementary methods that have led to the very interesting results of Einsiedler, Katok and Lindenstrauss, we will have a deeper understanding of those methods than if we had just passively learnt about them. I myself prefer to rediscover things than to learn them: it isn’t always practical, but it’s easier if you half bear in mind that they are there and have a vague idea about them.

Still on the topic of elementary versus non-elementary, one of the factors that contributed to the success of the DHJ project was that there was a non-elementary way of looking at the problem that we were trying to solve by elementary means. That meant that those participants who knew their ergodic theory could look at proposed proof strategies and make useful comments about whether they were likely to succeed. I think of it as like trying to find one’s way out of a jungle. The non-elementary methods give you something like a satellite picture of your surroundings, which enables you to plan your route instead of wandering around in the dense vegetation with no idea where you are. But there are things that the satellite picture won’t show, such as narrow but useful paths. So sometimes the person with the satellite picture knows that the person without it is wasting time, but sometimes there are important ideas that the person with the satellite picture will not spot. With a collaboration, one can of course have the best of both worlds.

For those who are interested, there is a very nice survey article by Akshay Venkatesh about the work of Einsiedler, Katok and Lindenstrauss, which explains how dynamics comes into the problem.

Before we discuss Littlewood’s conjecture, let us look at an easier question. Suppose that is a real number. To what extent can the multiples of stay away from integers? To make this question precise, let us write for the distance from to the nearest integer. Then we would like to examine the sequence .

Before thinking about the right question to ask, let us quickly prove a simple and very well-known theorem. (Unless my history is letting me down, which is possible, it is due to Dirichlet.)

Theorem 1. For every real number and every positive integer there exists a positive integer such that .

Proof. Let be chosen uniformly at random from the interval . Then the expected number of numbers in the sequence that lie in the interval mod 1 is . Therefore, there must exist and such that both and lie in the interval mod 1, from which it follows that . QED

Note (i) that Dirichlet used the pigeonhole principle rather than an averaging argument and (ii) that we could, if we had been bothered, have obtained a bound of from the above argument. (This illustrates the point, which is often handy, that even if partitioning a set into subsets of a certain form is hard — not that it is here — finding subsets of that form such that every element of is in the same number of may well be easy. In that case, something very similar to the pigeonhole principle works. I should expand this parenthetical remark into a Tricki article.)

What this argument shows is that sometimes must be small. Since it clearly won’t stay small (at least if ), this suggests that we should be interested in the sequence . And the obvious question then is: how fast must (or how slowly can) tend to as tends to infinity?

The argument above shows that , and this is asymptotically best possible, because it is not hard to show that if has a continued fraction with bounded quotients then for some positive constant (that depends on the upper bound of those terms). In particular, if is a quadratic irrational, then is at least for every positive integer .

This suggests that the slowest possible rate at which can tend to zero is achieved when is the golden ratio, and that is indeed the case. So this problem is completely understood: basically, the continued fraction expansion of tells you exactly how behaves.

Littlewood’s conjecture is about what at first seems to be an innocent generalization of the above result. Instead of looking at one real number , let us look at two, and . In broad terms, our goal is to understand to what extent it is possible for both and to be reasonably large. The precise question that Littlewood asked is (equivalent to) the following.

Problem 2. Let and be real numbers, and for each define to be . Must tend to zero faster than ?

By “faster”, I mean at a rate . Littlewood conjectured that the answer was yes. A more usual way of formulating the conjecture is as the statement that , which is obviously equivalent to a positive answer to Problem 2.

Since , it is trivial that tends to zero at least as fast as , and the only way that it could fail to tend to zero faster than that is if magically stays away from an integer whenever threatens to get close, and vice versa.

One question that it is reasonable to ask is the following: why, when we are considering the question of whether can remain far from a pair of integers, do we multiply together and ? Is that really a natural thing to do? I shall come back to this question, but for now let me remark (slightly cryptically) that this formulation leads to symmetries that are critical to the work that has been done on it.

A more general question.

Theorem 1 leads to the following nice construction of a set of points in such that if and are distinct elements of , then . (Note that this is best possible, since just must sometimes be at most .) One takes to be , where is reduced mod 1 and is a number with bounded quotients in its continued-fraction expansion (or, if you prefer, is something concrete like ).

Why does this work? Well,

by our choice of .

This shows that we can use a quadratic irrational, or any “counterexample to the one-dimensional analogue of the Littlewood conjecture”, to produce a set of points with the desired property. Let us define the “distance” between two points and to be , noting that this is very definitely not a metric. Then what we have produced is points in the unit square such that any two have distance at least from each other.

Can we do this in three dimensions? This time, we define the “distance” between and to be . Let me ask this question as a serious problem.

Problem 3. Is there a constant such that for every it is possible to find points in such that the distance between any two of them (as defined above) is at least ?

The reason for asking this question is the following simple observation.

Observation 4. If there is a counterexample to Littlewood’s conjecture, then the answer to Problem 3 is yes.

Proof. We generalize the two-dimensional construction in the obvious way, by defining to be . Again, and are reduced mod 1, and is a pair of real numbers such that is bounded below by a positive constant . Checking that this works is straightforward. QED

What is the point of asking this question? Well, one reason is that it is clearly very closely related to Littlewood’s conjecture, but it is far more general. Therefore, if such a set of points does exist, then it should be easier to find it than to find a counterexample to Littlewood’s conjecture, whereas if it doesn’t exist, then proving that it doesn’t exist might also be easier (because now it would be a purely combinatorial problem rather than a number-theoretic one).

Unfortunately, there are objections to the above arguments. It seems to be very hard to find a set of well-separated points in three dimensions (I’ll discuss what one can do in a moment), and part of the reason is that there are pairs of points to worry about. So it is tempting to introduce dependences, by which I mean to come up with a construction such that if one pair of points is separated it causes many other pairs to be separated as well. But that thought leads one inexorably to the idea that the best approach could be to start by finding a counterexample to the Littlewood conjecture … (This is an issue that I have discussed before on this blog. Sometimes combinatorial generalizations seem to be no easier to tackle than the problems they generalize.)

If finding an example of a collection of well-separated points turns out not to be easier to think about than finding a counterexample to Littlewood’s conjecture, what about trying to prove that such a collection cannot exist? Formally speaking, it is of course harder, but if such a collection cannot exist, then it could be that to prove it one is forced to think about the problem in the correct, more general way. I’m not sure how I feel about this. I have no decent idea about how to go about proving that a well-separated collection doesn’t exist, and if I attempt to do so there is always a little imaginary voice saying to me, “If you managed to prove this, then you’d have shown the highly non-trivial (indeed, not known) number-theoretic fact that .” Do I believe that such a fact might conceivably be provable by much more general combinatorial techniques? It seems like a long shot, but I can’t think of a good reason for its being impossible.

Incidentally, it is easy to find points that are separated by . There are two (ultimately not all that different) ways of doing this. One is just to choose any old maximal separated set of points. The set of points at distance at most from any given point has volume at most or thereabouts, so if is then this is about , so you can fit points in before there is any chance of the set being maximal. The other way of doing it is to choose the points randomly until the expected number of pairs that are too close exceeds half the number of points. You then throw away one point from each pair. This uses exactly the same volume calculation (since the volume of points close to is the probability that gets too close to ) and gives essentially the same bound.

But the weakness with those arguments is that they don’t exploit the fact that the “distance” is not in fact a metric and the “ball” around a point is far from convex. The greedy approach takes no account of the fact that the balls around the points could overlap considerably — all the more so if you try to choose the points in order to make this happen. However, I know of no better argument. (Of course, in the two-dimensional case I have just given a better argument, but that doesn’t help us.)

A variant of Problem 3.

One of the difficulties in thinking about Problem 3 is that we do not have a big supply of examples in the two-dimensional case. However, there is another construction that doesn’t quite work, but “morally” does work, which goes as follows. For convenience, let and take all points of the form such that both and have binary expansions that terminate after exactly digits (if necessary, one should add zeros to achieve this) and the digit sequence for is the reverse of the digit sequence for . For example, if then one of the points is in binary.

Why should this work? Well, for two distinct points to have coordinates that are very close, they will have to differ in some late digit, which means that their coordinates will have to differ in an early digit. More precisely, if the coordinates first differ in the digit, then the coordinates differ at or before the th digit, so the product of the differences should be at least .

So why doesn’t it work? Unfortunately, that argument makes the elementary blunder of assuming that if two numbers differ in an early digit, then they must be far apart. But the example of and shows that that is false. And if we take the numbers and then we have two numbers such that both they and their reversals are close.

I mentioned this to Nets Katz once, and he came up with the suggestion of changing the metric to a dyadic one. That is, we define the distance between two numbers in to be if they first differ in the th digit. With this definition, which is in some ways more natural than the “real” metric on , the digit-reversal construction works.

That may feel a bit like cheating, but if that’s the way you feel, then have a go at the next question, and also read on to the end of the next section.

Problem 5. Is it possible to find points in such that if and are any two of them then ?

Of course, one wants to do this for all and an absolute constant .

I have a hazy memory that Nets Katz and I managed to find such a set when we discussed this problem, but I’m not quite sure whether that memory is correct. In any case, I don’t have an example at my fingertips right now and it could be a good place to start. (It could be that what I am remembering is something else, namely a way of modifying the digit-reversal construction so that it works for the usual metric. Added later: I now think that that is indeed what I was remembering, since I have reconstructed the modification. See below.) Note that the dyadic distance between any two numbers is at least half the actual distance, so if one could prove that no dyadic-separated set existed, one would have proved Littlewood’s conjecture. (Added later still: I have now found a dyadic-separated set. See the sixth comment below. I don’t remember it from before, but neither am I certain that it is new. Added later still: on further reflection, it does feel faintly familiar. Nets, if you ever read this, does the example ring any bells with you?)

While I am at it, here is a general question.

Problem 6. Does the Littlewood conjecture, or indeed any of the related problems discussed here, become easy if the dimension is sufficiently high?

For example, if are real numbers, is it known that ? I think it may be but I have not found it by Googling. Problem 6 is potentially important in the context of the dyadic problem: if the answer to Problem 5 turns out to be yes (as I vaguely remember), then we do not have a proof of Littlewood’s conjecture. But it could be that the answer to a sufficiently high-dimensional analogue of Problem 5 is no, in which case one would have a combinatorial proof of a high-dimensional version of Littlewood’s conjecture.

Are the two constructions related?

We now have two ways of producing well-separated subsets of (one of them by changing the metric): using a quadratic irrational, and the digit-reversal idea. However, these two methods may be less different than they at first appear. To see this, let us consider what happens if we try to produce an example using the golden ratio, except that to keep the discussion finite we shall use a good approximation to it of the form , where and are consecutive Fibonacci numbers. In fact, let us go further and take . What’s more, let us make our points live in the grid rather than in . Thus, we shall take the set of all multiples of mod 13. These are ,. Note how beautifully these points behave themselves: when one of them is close to (mod 13) then the other one stays away.

How can we connect this with digit-reversal? Obviously we do not want to take base-ten representations. The natural base if we are thinking about Fibonacci numbers is … to write numbers as sums of Fibonacci numbers. To make the representation unique, we forbid the use of consecutive Fibonacci numbers (it is an easy exercise to check that this gives a unique representation). An easy algorithm for working out the representation is to keep subtracting the largest Fibonacci number that is less than what you have: for instance, 12=8+4=8+3+1 and there is our representation. There is a small issue that needs to be sorted out: the number 1 occurs twice, so are 1 and 2 consecutive Fibonacci numbers? I shall use the algorithm just described, so I shall never need the first 1. Thus, I regard 1 and 2 as consecutive.

Let us write our numbers as we would in base 10: with the largest term at the left. If we do that, and if we put zeros at the beginnings of numbers, then the points above work out to be .

The first thing to say is that we are clearly not reversing the digits here. And yet, if one looks more closely, then one starts to see patterns emerging: there seems to be a mixture of digit-reversal and moving “blocks” of numbers around. To see what I mean here, look at what happens if we take the multiples of 8 and reverse their Fibonacci digits. The resulting sequence is this: 1,3,4,10,8,9,11,12,7,5,6,2. Let us throw in 0 at the beginning of the sequence and imaginine it arranged in a cycle. Now we can partition this cycle into two chunks, one of length 5 and one of length 8. These chunks are (7,5,6,2,0,1,3,4) and (10,8,9,11,12). The first chunk naturally splits up as (7,5,6) and (2,0,1,3,4), which again consists of permutations of intervals of Fibonacci lengths. And the second does too: it splits up as (10,8,9) and (11,12). And we can keep doing this. For example, (7,5,6,2,0,1,3,4) splits up into (7,5,6) and (2,0,1,3,4), and so on.

It should be fairly easy to describe exactly what is going on here and prove that it always happens, but I have not got round to doing so. What I would like to see is this. First, there should be a simple algorithm that tells you how to unscramble the sequence of digit-reversed numbers by iterating the following process — take a sequence of numbers of Fibonacci length, divide it into two subintervals of Fibonacci length and possibly swap them round (but not always, so one would need to know when, and also when the longer interval comes first) — until you get down to singletons. The second thing should be a direct combinatorial proof that if you do this process in reverse, then you will get a sequence of numbers such that nearby terms in the sequence have reversals that are far away.

Note that it was obvious in advance that we would not get digit-reversal, because the Fibonacci base is subject to the same problem that the binary base was: it is possible for two numbers to be close and for their digit-reversals to be close. But this is interesting, as it suggests that if we understand what is going on combinatorially in the above patterns, then we might be able to come up with a flexible construction that uses digit reversal but cleverly modifies it to get round the nought-point-one-recurring difficulty. More generally, it suggests that thinking about the dyadic problem could give useful insights into the original problem.

Added later: after editing the above (to add the description of the interesting pattern that appears when you multiply by 8 and reverse the Fibonacci digits), I realized that it is indeed possible to mimic what is going on there and deal with the nought-point-one-recurring difficulty. This gives rise to a construction that is probably what Nets Katz and I came up with when we discussed the problem (about eight years ago), though it is certainly not how we came up with it.

What I want to do is construct a sequence of pairs of points such that both and live in and have binary digits. I also want to be at least whenever Digit reversal doesn’t work, but what about a combination of digit reversal and “sometimes exchanging clumps”? The most obvious idea would be to organize the into a binary tree, and then go down the levels of this tree, alternately not swapping and swapping. That is, I let for every . The first level of the tree is the partition into two intervals according to the first digit of . So I do that partition and then don’t swap the intervals. At the second level, I do swap the intervals, so now I have four intervals in the following order: numbers that start 01, numbers that start 00, numbers that start 11, numbers that start 10. I continue this process.

The resulting order will be what you get if you take each number, change every other binary digit, and then put the numbers in increasing order. Let be the map that changes every other binary digit of a number and let be the map that reverses the digits. Then the set of points I want to take is the set of all such that is of the form .

Why does this work? Well, if and first differ in the th binary place, then and differ in the th place and are identical after that. Therefore, The only way that this can fail to help is if and are much closer than . Now if is greater than , then this means that the th digit of must be a 1 and several subsequent digits are 0, while the th digit of is a 0 and several subsequent digits are 1. But then and have alternating 0s and 1s after the th digit, and in different places. If the lengths of these strings of alternating digits are around , then it is not hard to see that and must differ by at least basically because they now differ in the th place and are not followed by strings of 0s and 1s after they first differ.

Conclusion: digit reversal and shifting intervals can combine to give a second example of a well-separated subset of with respect to the Euclidean metric (in each coordinate) rather than the dyadic metric. The rough reason this works is that the digit-reversal almost works, but fails because of the nought-point-one-recurring problem, while takes numbers that are “close when they shouldn’t be” and pulls them apart. (Of course, then has to bring together numbers that used to be far apart, but this turns out not to matter because the images of those numbers under turn out to be sufficiently far apart to compensate for it.)

More variants.

Returning to Littlewood’s conjecture itself, there is a substantial weakening of it that I still do not know how to answer, though I think it has a good chance of being known and would be interested to hear from anyone if they do know the answer, though in an ideal world I would prefer to come up with an answer for myself (where “for myself” really means “by thinking about it in collaboration with other Polymath participants”). (Added later: I have now found a paper that makes it clear that the question I am about to ask is indeed a known result. I will give the reference at the end of this section.) As I have already mentioned, one of the difficulties of Littlewood’s conjecture is that the function is not a metric. This is why the usual techniques for solving packing problems (up to a constant) fail for Problem 3. However, suppose we know that the ratio of to is roughly to . Then is roughly , which is roughly , which equals

Let and for each between and let us write . Then it is not hard to check that .

Therefore, if were a counterexample to Littlewood’s conjecture and , it would have to be the case that for every between and the numbers were bounded below by some . In particular, this would need to be the case when , which would say that the numbers were bounded below. This motivates the following weak version of Littlewood’s conjecture.

Problem 7. Do there exist real numbers and such that ?

Here is what this problem is asking geometrically. For each the points (mod 1) with form a subset of of size . A trivial volume argument shows that there must be two of these points within a distance of . Problem 7 asks whether there is some pair such that this trivial upper bound is correct up to a constant for every . Thus, there is not much room to play around, but neither is there in the one-dimensional case and yet numerous examples exist. Here is a somewhat vaguer problem.

Problem 8. If the answer to Problem 7 is yes, then is there some general procedure, analogous to picking a continued fraction with bounded exponents, that yields a large family of examples?

One might think that if the answer to Problem 7 is yes, then the answer to Problem 8 is almost certainly yes as well. But it does not seem to be all that easy to generalize continued fractions in the appropriate way. (Of course, many people have tried to produce higher-dimensional generalizations of continued fractions, and it is possible that out there is just what would be needed.)

Another indication that the Littlewood conjecture is hard is that it is not known even in very concrete cases such as and , as I have already mentioned. This means that a positive solution to the conjecture would have serious number-theoretic content. However, it might be worth thinking about whether a concrete pair of numbers like this could work for Problem 7. (Added later: this too seems to have been done.)

Here is another problem, which I think of as a “dual” version of Littlewood’s conjecture. I will try to justify this name in a moment. (Added later: it turns out that dual problems such as the ones I am about to mention have been considered in the literature as well, and they are dual in a much more direct, though closely related, sense than the one that I talk about.)

Problem 9. Do there exist real numbers and such that ?

The lim inf there is over all pairs of non-negative integers and of which at least one is positive. Again, if an example exists then it is best possible, since out of all the numbers with there must be two, and , that differ by at most . The difference between this and Littlewood’s conjecture is that we are taking a two-dimensional collection of points in rather than a one-dimensional collection of points in .

This problem also has a weak version.

Problem 10. Do there exist real numbers and such that ?

What is “dual” about these problems? I’ll give an informal argument here: yet another aspect of this project would be the question of whether the argument can be turned into a formal argument for equivalences, or at least one-way implications, between these problems and some of the earlier ones.

Let us begin with the weak versions. Problem 7 asks for and such that one of and is always at least whenever is a positive integer less than $m$. Let us simplify things a bit by taking to be a prime number and trying to find and mod such that at least one of and lies outside the interval whenever .

Now for any given there are two sets of interest here. One is the set of such that , and the other is the set of such that . We would like the intersection of these two sets, which are equal to and , to be the trivial one, namely . If that happens, then we cannot find in with and in the interval .

Here is where I will get very informal. Heuristically speaking, the Fourier transform of a set such as behaves like an arithmetic progression of common difference and length . (There are all sorts of tricks for making this heuristic better, such as convolving the set with itself so that it has non-negative Fourier coefficients. I won’t worry about such issues here,) Now the intersection of two sets corresponds to the pointwise product of their characteristic functions, and that transforms to the convolution of their Fourier transforms. And the size of the intersection is given by the square of the norm of this convolution. If we ensure that the Fourier transform is real and positive, then the norm of the convolution will not depend on and . Therefore, in order to make the norm as small as possible, we want the convolution to be as “spread out” as possible, which happens if there are as few linear relations amongst and with coefficients less than as possible. This suggests that we should look for and such that all the numbers with are as distinct as possible. And now we are getting close to Problem 10. I haven’t checked, but I think a slightly more complicated argument establishes a similar connection between Problems 2 and 9.

It’s quite possible that the answers to some of these questions are known, or at least that the questions would seem easy to experts in the area.

Added later: as I mentioned above, this is indeed the case. See for example this paper of Pollington and Vellani, which shows that the set of all pairs such that and are badly approximable and for every , where , has Hausdorff dimension 2. (Their result is in fact more general than this.) Davenport proved in the early 1950s that the answer to Problem 7 is yes, and that there are uncountably many examples.

The paper where I found a mention of a dual problem is “Simultaneous Diophantine approximation” by Davenport, published in the Proceedings of the LMS, December 1952, pages 406-416.

Could one make a serious attempt to find a counterexample?

Let me return yet again to the question of whether elementary methods are appropriate for the Littlewood problem. As I have shown above, there are several problems that seem to be very closely related to it but that are in one way or another easier, and I don’t see any good reason for ruling out elementary approaches to those. That is particularly true of Problem 5 (the dyadic variant of the separated-points problem).

However, another reason I think that one should not rule out the use of elementary methods is that it is possible that Littlewood’s conjecture is false. I want in this section to outline a few thoughts about how one might go about disproving it.

The first thing to say is that if the conjecture is false, it is not false by very much. The headline result of Einsiedler, Katok and Lindenstrauss is that the set of counterexamples to the conjecture has Hausdorff dimension zero, and this result has a strong bearing on what kind of methods stand a chance of yielding a counterexample.

In order to elaborate on this remark, let me discuss a “combinatorial” way in which one might end up with a good real number if you want to be positive. We have already seen that any with bounded convergents in its continued fraction expansion will do: what I am about to discuss is a way of seeing that without explicitly thinking about continued fractions.

The idea is to start with an attempt and to make a series of adjustments to it. So let’s start with a truly stupid choice of , namely . Instantly we are in trouble, because is not large. So let us make it as large as we can by taking . Now that sorts out but we quickly run into trouble again, since So let us adjust again, by moving until becomes as large as possible. There are two minimal ways of doing that: we could take or . Let’s try increasing at every stage, so we take to be . Now we run into problems only at , when we get So let us adjust by taking such that which gives us

We are running into difficulties, because it appears that if we continue with this algorithm. But at this point we might pause to observe that if is an integer, we do not need to increase to make as far from an integer as possible: all that really matters is that it should be further from an integer than In retrospect, it makes sense if our successive adjustments are as small as possible, so that we don’t mess up the progress we have made previously.

With this thought in mind, let us try again. We take . Since is very small, we had better take to be as far from an integer as possible, so let us once again take to be But now, when we come to deal with the problem that is an integer, let us increase it from to instead of to . In other words, let us take to be . Our next problem comes with , so let us change that from to , which gives us .

Unfortunately, we are in trouble again, because works out to be So let us think slightly harder about what we have to do in order to ensure that we do not get into trouble. We are trying to build a sequence that converges to a limit in such a way that for every . This we can achieve if we ensure that for every , and this we can achieve if we make sure that and that .

Here is another approach. Let us again start with and . To define , we shall use the following principle: we look for the “worst place” and the “second worst place” and share the badness equally between them. Here the “worst place” is where the disaster occurs that and the “second worst place” is where . So we increase to , so that both and are equal to .

The next disaster occurs when we notice that . The second worst place could be taken to be either or . There is something to be said for alternately increasing and decreasing our , since that will make the total change smaller than if we always increase, so let us focus on . To share out the badness equally, we would like to decrease slightly so that . That tells us to take

Probably you can guess by now what happens: we keep going like this and we end up producing the fractions and in the limit we get the golden ratio.

But the method of making successive adjustments is much more general and flexible than this — we just happened to do things so efficiently that we got the best result. I confess that I haven’t quite nailed this explanation, but ultimately it should be possible to devise a successive-adjustment procedure that could in principle give any real for which the continued-fraction expansion has bounded quotients, and thereby present the continued-fraction solution as the outcome of a just-do-it proof.

Unfortunately, the main point I now want to make is that it is highly unlikely that any such approach could give rise (except perhaps very indirectly) to a counterexample to the Littlewood conjecture. The idea would be to start with a pair of real numbers and make successive adjustments to it each time some multiple misbehaved. If you try this, you will soon find yourself running into difficulties, but the result of Einsiedler, Katok and Lindenstrauss tells you in advance to expect this, or at least I think it does.

My heuristic reasoning here is as follows: if you can use a reasonably flexible successive-adjustment argument, then you will tend to get a set that is somewhat Cantor-like: you start with an interval of possibilities, then from it you remove some subintervals, and from what remains you remove further subintervals, and so on. These kinds of ideas show that the Hausdorff dimension of the set of reals with bounded partial quotients is not small: I haven’t yet found a good reference and I don’t know what the precise results are. But turning this on its head, one would expect that for Littlewood’s conjecture, if any successive-adjustment technique worked, it would have to be incredibly non-robust and work almost miraculously: perhaps as one removed subintervals one would sometimes remove whole branches of the tree and it would be far from obvious that by the end of the process there would be any tree left.

It is thoughts such as these that make me interested in Problem 7 (the weak version of Littlewood’s conjecture). For this problem, has to avoid a box of radius , and therefore area . This feels much more like what you have to do when you are trying to find such that avoids an interval of length , so it is tempting to try a successive-adjustment strategy. (Added later: This is indeed the type of argument that Pollington and Vellani use. At one point they use a very clever idea of Davenport.)

My belief is that such a pair exists, but finding one using a successive-adjustment strategy seems not to be wholly straightforward, because there is not an obvious direction in which to take the adjustment. (What is clear is that this direction must vary enough to stop the set of multiples becoming “approximately one-dimensional”, but I don’t see how to do this systematically.) Anyhow, I very much like this problem, because it seems to be of intermediate difficulty, and if one did manage to find a good supply of examples, and perhaps even understand the Hausdorff dimension of the set of examples, then one might be able to understand how that set behaved when you intersect it with copies of that set that you obtain by stretching it in one direction and shrinking it in the other (which is supposed to help you avoid other rectangles of the same area and thereby attempt to give a counterexample to Littlewood’s conjecture). Perhaps the set is sufficiently non-symmetric under transformations of the kind that images of it under such transformations are “independent” in some way and therefore have a non-empty, but very small, intersection.

(Added later: Given what I now know about results in the area, the goal here would have to be different. It would be to understand the set of examples well enough to be able to show that it has non-empty intersections with various transformations of itself. This, it seems, is a known hard problem: see Conjecture 1 of the paper of Pollington and Vellani.)

Computer-generated pictures.

I’m a hopeless programmer. If I weren’t, then I would have done the following very simple computer experiment, and I would love it if someone else could do it. It would be to generate a picture as follows. Choose a fairly large prime and take a square of pixels. Choose also a small constant such as and an integer that’s much larger than 1 and (probably) quite a bit smaller than . (It would be interesting to do this with different constants.) Think of the square as . Now make the pixel black if there exists a positive integer such that mod lies in the box I would very much like to see what the resulting set looks like. In particular, I would like to know whether it is obvious from looking at it that the horizontal and vertical distance scales are the same. (One would have to look at just a small chunk of it since it would be symmetrical in and .) And I’d also like to know whether it has a Cantor-ish feel to it. If anyone is ready to spend the half hour it would need a competent programmer to generate a few pictures like this I would be extremely grateful to have my curiosity satisfied. This wouldn’t have to wait for an official project to start — it could be an interesting preliminary.

Needless to say, one could also generate images of sets related to Littlewood’s conjecture itself, rather than the weak version. One would simply colour a pixel black if . It would be interesting to try this for various values of , and (especially) . In particular, I am interested to know what the residual set looks like, and whether it gets smaller very quickly (as the dimension-zero result suggests that it should).

As well as generating pictures, one could try to test the conjecture in a crude experimental way, by searching for pairs of numbers such that does not get small (or at least does not get small unless is large. Indeed, we could define to be the largest possible value of . One can get good estimates of if is not too large by simply trying all pairs such that the decimal expansion terminates after digits for some manageable . Of course, if is small for some smallish , then the same will be true for all pairs in some neighbourhood of , so there may be good ways of speeding up this brute-force approach. (At the very least, one could eliminate all pairs that fail when , then all pairs that fail when , and so on, so that one would search through fewer pairs when one had got further with the search.)

Conclusion.

One of the things I like about this project is that there is quite a long list of subproblems of graded difficulty: it seems likely that at least something interesting could be proved, and the aim would be simply to get as far as we can. Even doing a few simple computer investigations would be quite interesting (though if it turns out that tends to zero slowly with , then this might well not show up clearly in the data). The dyadic version of the packing problem looks to me as though it could have a reasonably easy solution, at least if a good packing exists. The “weak Littlewood problem” ought to be substantially easier than the main problem — I think there should be a reasonably large set of counterexamples — but hard enough to be interesting (unless the answer is already known, which is certainly possible). Likewise, the higher-dimensional problem should be easier to prove, this time with a positive answer (but again the answer may be known). And perhaps the “dual versions” are sufficiently different that they too have a chance of being of the right level of difficulty. (Added later: the fact that the weak version is indeed known changes my assessment of this project somewhat. I would be interested to understand the proof of that as well as possible, but given that it is known, the place to focus on first might be the dyadic packing problem in three dimensions.)

For the sake of commenters, here is a set of abbreviations that might be useful.

LP (Littlewood problem). PP (packing problem — the one where you want a large well-separated set with the distance that isn’t really a distance). DPP (dyadic packing problem). WLP (weak version of Littlewood problem). HDLP (high-dimensional Littlewood problem). HDDPP, HDWLP (obvious meanings). DLP (dual Littlewood problem). WDLP (weak dual Littlewood problem).

About these ads