A Rauzy Tree

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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: