Limits with better properties

From Polymath1Wiki

Jump to: navigation, search

Click here to return to the main Polymath5 page

Contents

From an integer sequence to a function defined on the rationals

Let (xn) be an infinite \pm 1 sequence of discrepancy at most C. Using this sequence, we can define a "rational sequence" (y_a)_{a\in\mathbb{Q}} in one or other of the following three ways (which look different but the first two are essentially the same).

Method 1

For each positive rational number a and each positive integer n, let fn(a) = xn!a if n!a is an integer and let it be undefined (or arbitrarily defined) otherwise. Pick a subsequence of the functions fn that converges pointwise and define ya to be the limit of the values of fn(a) along this subsequence.

Method 2

Define the functions fn as above, but this time define ya to be the limit of fn(a) along a non-principal ultrafilter U. It is simple to check that the result will again be a pointwise limit of a subsequence of the functions fn.

Method 3

This time, define fn(a) to be xna and again let ya be the limit of fn(a) along a non-principal ultrafilter U. As it stands, this does not work, since it is not clear that the set of n such that fn(a) is an integer belongs to U. However, the set of all infinite HAPs forms a filter F, so we can insist that U extends F, and then the construction works. A more interesting way of achieving this is to take U to be an idempotent ultrafilter. It is straightforward to check that idempotent ultrafilters contain all infinite HAPs (which already suggests that they might conceivably have a role to play in the problem), but the property of being idempotent is much stronger than that. It would be interesting to think about whether this third method yields a rational function with some useful extra properties.

Properties of the resulting function

Let us begin by proving that every sequence of the form y_a,y_{2a},y_{3a},\dots (which we shall call an HAP-subsequence) has discrepancy at most C.

This is trivial. Let g_1,g_2,g_3,\dots be a subsequence of the fn such that fn(a) converges to ya for every rational number a. Let m be any positive integer. Then there exists some n such that gn(ka) = yka for every k between 1 and m. We may also pick n large enough so that n!a is an integer. If we do so, then the numbers n!a, 2n!a,...,mn!a form an HAP, which implies that the partial sum g_n(a)+\dots+g_n(ma) has absolute value at most C, since it equals the sum x_d+\dots+x_{md}, where d=n!a.

Thus, this construction gives us a way of passing from an example that works over the integers to an example that works over the rationals. However, it does more than that, as the following argument shows. Let us suppose that the r-sequence and the s-sequence of (xn) are equal: that is, xrn = xsn for every positive integer n. What does this tell us about the function ya? Obviously, it implies immediately that yra = ysa for every rational number a. From that we deduce that ya = ysa / r for every rational number a (applying the previous result to a/r) and also that ya = yar / s. In other words, once we have passed to the rational limit, we find that the function is invariant under dilation by r/s, which implies that it is also invariant under dilation by s/r.

Further investigation

Improved properties in the limit

If we know only that two HAP-subsequences of the sequence (xn) are approximately equal, then it is still possible that we might be able to choose the pointwise limit carefully so as to ensure that in the limit we have exact invariance. It would be very interesting to reach a clear understanding of when this is possible and when it isn't. (If the two sequences differ everywhere on some further HAP-subsequence, for example, then it probably isn't possible. But then we might not be inclined to say that the two sequences are approximately equal.)

Here is a simple result along these lines, but it is almost certainly far from the strongest one could prove. For simplicity I'll discuss just one special case. Let us say that a sequence (xn) is eventually T2-invariant if for every m the sequence x_m,x_{2m},x_{4m},\dots converges. Then in the limit we get a function that is exactly T2-invariant. (What is nice about this is that the time it takes for the sequence x_m,x_{2m},x_{4m},\dots to stabilize is allowed to depend on m.)

Having written that, I no longer find it obvious. However, one can create some limit with this property: just take the limit along an ultrafilter of x_a,x_{2a},x_{4a},\dots. This will be defined on all dyadic rationals, and one can then use one of Methods 1-3 to obtain an example defined on all rationals. It's possible that taking iterated limits along different sequences of powers could be useful, therefore (or perhaps an idempotent ultrafilter would do everything at once -- this should be checked). Let us therefore add a new method.

Method 4

Similar to Methods 1 and 2, but this time we define a p-limit to be a limit obtained when you define fn(a) to be x_{p^na}. If you start with an integer sequence and then take a 2-limit, followed by a 3-limit of the resulting function (which is defined on the dyadic rationals) then a 5-limit of that (which is defined on all rationals with denominator of the form 2r3s) and so on, and finally take a pointwise limit of a subsequence of the functions that you obtain at each stage of this process, then you will have a function defined on all rationals, and some of the "errors" in the original sequence will have been swept away. In particular, eventual Td-invariance will have been turned into exact Td-invariance.

Dichotomies

Suppose, as we may, that we have a rational example (ya) with discrepancy at most C. That instantly gives us a whole host of other examples, since for every rational b the function yba is an example, and any pointwise limit of a subsequence of these further examples (which is the same as an element of the closure of the set of those examples in the product topology) is again an example. We have already seen that we can get improved properties in the limit. What happens if we try to force the limit to take certain values in certain places by choosing an appropriate sequence of dilations?

To get some handle on this question, let us look at a couple of simple examples. Suppose, for instance, that I want to find an example (za) such that z1 = z2. If I can find any r such that yr = y2r then I am done, since I can simply set za = yra. So if I cannot find an example with z1 = z2 then I know that ya = − y2a for every a, which is a very strong multiplicativity property.

This is not particularly interesting, because the property z1 = z2 will rapidly be lost if one dilates the function za and passes to limits. So let us try to do something more infinitary.

Suppose that I want to pass to an example that is multiplicative. I can do this if for every finite multiset A of rationals there exists some rational r such that yryrab = yrayrb for every a,b in A. The reason is that if I have such an r for a given set A and I set za = yar / yr, then zab = zazb for every a,b in A. Taking an increasing sequence of sets A whose union is all of \mathbb{Q} and passing to the limit of the corresponding z-sequences, we obtain an example that is multiplicative everywhere.

This is basically just a simple compactness argument that says either there is a multiplicative example or there is some finite set A such that for every r we find a "failure of A-multiplicativity at r". For example, if A is the multiset {2,2,3}, then it tells us that there is no r such that both the equalities y_ry_{4r}=y_{2r}^2 and yry6r = y2ry3r hold.

This is quite a strong non-multiplicativity property. It would be interesting to investigate experimentally whether insisting on non-multiplicativity of this kind forces the discrepancy to become large.

Limiting behaviour of some concrete sequences or classes of sequences

As well as beginning with a hypothetical counterexample to the Erdős discrepancy problem, one can begin with concrete sequences and see what happens. For example, if you start with the Liouville sequence, then the only two HAP-subsequences are the sequence itself and minus the sequence. More generally, if a sequence is weakly multiplicative, then there will be only finitely many HAP-subsequences, so any pointwise limit of them is automatically one of these subsequences (and similar remarks apply to any rational extension).

It might be interesting to see what happens to the Morse sequence. It is T2-invariant, so the interest would come with dilations by odd factors. Can one characterize all functions on the rationals that are pointwise limits of sequences of the form Tkx, where x is the Morse sequence? I think it is done here

If x is a random sequence, then I'm pretty sure that every sequence is a pointwise limit of dilations of x. This, interestingly, would give an infinitary proof that random sequences have unbounded discrepancy. (When you unpack it, however, the argument is less interesting: it is essentially using the fact that a random sequence will have arbitrarily long strings of 1s, which trivially rules out bounded discrepancy.)

Possible definitions of essential sameness

We could place various equivalence relations on sequences. One particularly generous one would be to say that two sequences x and y are equivalent if you can find pointwise limits of dilations of x and y that were equal. A more restricted one would be as above, but to insist that the same sequence of dilations is chosen for each. A yet more restricted one would be to insist that all pointwise limits of dilations (perhaps with the added property that every positive integer is eventually a factor of all the amounts by which you are dilating) are the same.

Using an idempotent ultrafilter

What happens if we follow Method 3 above? It is in a sense strictly stronger than Method 2, but do we gain anything as a result?

Retrieved from "http://michaelnielsen.org/polymath1/index.php?title=Limits_with_better_properties"
Personal tools