Archive for January, 2010

Homogeneous Drift

January 16, 2010

(This post is part of Polymath5; see Gowers’ weblog to understand what I’m talking about.)

The following trees represent ways to assign primes in a completely multiplicative sequence. If a leaf is labeled {N,k}, it means that the corresponding assignment has \sum_{i=N-k+1}^N x_i with absolute value “drift”.

drift = 2

drift = 3

drift = 4

drift = 5

A Rauzy Tree

January 9, 2010

One way to visualize an infinite word is by making a Rauzy graph. The vertices are the words of a given length, and you connect aw to wb for any word w and not necessarily distinct letters a,b.

In the Erdos Homogeneous Discrepancy problem, we are interested not in subwords, but in the pattern of pluses and minuses that are along HAPs. This image is the tree of patterns that we see in a particular 1124-term sequence that has shockingly small discrepancy. Each vertex label includes the number of HAPs that begin with that particular pattern. Here’s the same tree for the subsequences x_i RauzyTreeStub1124, x_{2i} RauzyTreeStub1124d2, x_{3i} RauzyTreeStub1124d3, x_{4i} RauzyTreeStub1124d4, x_{6i} RauzyTreeStub1124d6, and x_{8i} RauzyTreeStub1124d8. A word of caution: the subsequences are shorter than the original, and so the tree represents less data. The fact that the tree appears cleaner could be illusory.