Limits with better properties

Click here to return to the main Polymath5 page

From an integer sequence to a function defined on the rationals

Let [math]\displaystyle{ (x_n) }[/math] be an infinite [math]\displaystyle{ \pm 1 }[/math] sequence of discrepancy at most C. Using this sequence, we can define a "rational sequence" [math]\displaystyle{ (y_a)_{a\in\mathbb{Q}} }[/math] 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 [math]\displaystyle{ f_n(a)=x_{n!a} }[/math] if n!a is an integer and let it be undefined (or arbitrarily defined) otherwise. Pick a subsequence of the functions [math]\displaystyle{ f_n }[/math] that converges pointwise and define [math]\displaystyle{ y_a }[/math] to be the limit of the values of [math]\displaystyle{ f_n(a) }[/math] along this subsequence.

Method 2

Define the functions [math]\displaystyle{ f_n }[/math] as above, but this time define [math]\displaystyle{ y_a }[/math] to be the limit of [math]\displaystyle{ f_n(a) }[/math] 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 [math]\displaystyle{ f_n }[/math].

Method 3

This time, define [math]\displaystyle{ f_n(a) }[/math] to be [math]\displaystyle{ x_{na} }[/math] and again let [math]\displaystyle{ y_a }[/math] be the limit of [math]\displaystyle{ f_n(a) }[/math] 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 [math]\displaystyle{ f_n(a) }[/math] 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 [math]\displaystyle{ y_a,y_{2a},y_{3a},\dots }[/math] (which we shall call an HAP-subsequence) has discrepancy at most C.

This is trivial. Let [math]\displaystyle{ g_1,g_2,g_3,\dots }[/math] be a subsequence of the [math]\displaystyle{ f_n }[/math] such that [math]\displaystyle{ f_n(a) }[/math] converges to [math]\displaystyle{ y_a }[/math] for every rational number a. Let m be any positive integer. Then there exists some n such that [math]\displaystyle{ g_n(ka)=y_{ka} }[/math] 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 [math]\displaystyle{ g_n(a)+\dots+g_n(ma) }[/math] has absolute value at most C, since it equals the sum [math]\displaystyle{ x_d+\dots+x_{md} }[/math], 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 [math]\displaystyle{ (x_n) }[/math] are equal: that is, [math]\displaystyle{ x_{rn}=x_{sn} }[/math] for every positive integer n. What does this tell us about the function [math]\displaystyle{ y_a }[/math]? Obviously, it implies immediately that [math]\displaystyle{ y_{ra}=y_{sa} }[/math] for every rational number a. From that we deduce that [math]\displaystyle{ y_a=y_{sa/r} }[/math] for every rational number a (applying the previous result to a/r) and also that [math]\displaystyle{ y_a=y_{ar/s} }[/math]. 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 [math]\displaystyle{ (x_n) }[/math] 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 [math]\displaystyle{ (x_n) }[/math] is eventually [math]\displaystyle{ T_2 }[/math]-invariant if for every m the sequence [math]\displaystyle{ x_m,x_{2m},x_{4m},\dots }[/math] converges. Then in the limit we get a function that is exactly [math]\displaystyle{ T_2 }[/math]-invariant. (What is nice about this is that the time it takes for the sequence [math]\displaystyle{ x_m,x_{2m},x_{4m},\dots }[/math] 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 [math]\displaystyle{ x_a,x_{2a},x_{4a},\dots }[/math]. 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 [math]\displaystyle{ f_n(a) }[/math] to be [math]\displaystyle{ x_{p^na} }[/math]. 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 [math]\displaystyle{ 2^r3^s }[/math]) 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 [math]\displaystyle{ T_d }[/math]-invariance will have been turned into exact [math]\displaystyle{ T_d }[/math]-invariance.

Dichotomies

Suppose, as we may, that we have a rational example [math]\displaystyle{ (y_a) }[/math] with discrepancy at most C. That instantly gives us a whole host of other examples, since for every rational b the function [math]\displaystyle{ y_{ba} }[/math] 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 [math]\displaystyle{ (z_a) }[/math] such that [math]\displaystyle{ z_1=z_2 }[/math]. If I can find any r such that [math]\displaystyle{ y_r=y_{2r} }[/math] then I am done, since I can simply set [math]\displaystyle{ z_a=y_{ra} }[/math]. So if I cannot find an example with [math]\displaystyle{ z_1=z_2 }[/math] then I know that [math]\displaystyle{ y_a=-y_{2a} }[/math] for every a, which is a very strong multiplicativity property.

This is not particularly interesting, because the property [math]\displaystyle{ z_1=z_2 }[/math] will rapidly be lost if one dilates the function [math]\displaystyle{ z_a }[/math] 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 [math]\displaystyle{ y_ry_{rab}=y_{ra}y_{rb} }[/math] for every a,b in A. The reason is that if I have such an r for a given set A and I set [math]\displaystyle{ z_a=y_{ar}/y_r }[/math], then [math]\displaystyle{ z_{ab}=z_az_b }[/math] for every a,b in A. Taking an increasing sequence of sets A whose union is all of [math]\displaystyle{ \mathbb{Q} }[/math] 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 [math]\displaystyle{ y_ry_{4r}=y_{2r}^2 }[/math] and [math]\displaystyle{ y_ry_{6r}=y_{2r}y_{3r} }[/math] 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 [math]\displaystyle{ T_2 }[/math]-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 [math]\displaystyle{ T_kx }[/math], 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?