PeriodsAfter a brief introduction to the combinatorics on words, which builds on some of the same ground that was discussed in a prior note, I will look at a remarkable theorem due to the mathematicians Herbert Wilf and Nathan Jacob Fine...
Mathematics is sometimes described as the science of studying patterns. Some mathematical patterns seem a bit hidden at first: 1, 1+3, 1+3+5, 1+3+5+7,.... The "rule" here seems clear enough; look at the sequence of adding the first n odd numbers. But there is a surprise! After the additions are carried out we see: 1, 4, 9, 16, .... The sum of the first n odd integers seems to be n times n, or n2. And since the alternately shaded white and black "hooks" in the diagram below (the case of n = 8) have an odd number of cells 1, 3, 5, etc. that fit together to form a square:
Patterns of repeats
In a prior column I looked at some topics in the combinatorics of words. Combinatorics on words studies properties and patterns present in strings of symbols like:
Periodic graphs (Courtesy of Wikipedia)
Border or frieze patterns (Courtesy of Wikipedia)
Herbert Wilf (Photo courtesy of Wikipedia)
Nathan Jacob Fine (1916-1994) (Photo Courtesy of Wikipedia)
Nathan Jacob Fine (1916-1994) spent his career at Pennsylvania State University but got his doctorate degree from Antoni Zygmund at the University of Pennsylvania in 1946. As an aside, the mathematics building at Princeton University is called Fine Hall, and mathematicians may be tempted to think it is named for Nathan Fine. In fact, Fine Hall is named for Henry Burchard Fine (1858-1928) a dean at Princeton who did much to make Princeton a center for research in mathematics.
Combinatorics on words
The area of mathematics known as combinatorics on words has exploded in recent years with a large volume of new results. There have been many attempts to summarize and understand what has been done in the past but they are scattered throughout different parts of the mathematical literature. As is often true in rapidly emerging fields there are often concepts that are defined slightly differently (using different terms for the same idea) or the same term is used to mean not exactly the same thing. Happily, there is a growing consensus about how to organize these ideas so that one can see what the field is accomplishing. However, for better or worse, there is a fair amount of "technical" vocabulary. Here I will try to "conversationally" define the important terms that encompass the ideas involved but will, wherever possible, work using examples, rather than giving a very formal approach.
w = aabaabaabaa (*)
Although we have yet to offer a formal definition, these two don't seem to line up very well, with only occasional matches between the two strings.
Given two strings X and Y, even if they are not the same length, one can try to see how they are "related." Below are two strings X and Y of different lengths from the DNA alphabet, A,C, G, and T. We can construct a binary string which gives information about how the two strings "match." This can be done by lining up the strings starting at the left (left-adjusted). We record if Y matches X in all of the positions they overlap in by recording a 1 for such an overlap match and a 0 for no such match. Then we shift the string Y one position to the right and check for a match in all overlapping positions in the shifted position. We can repeat this process over and over until we exhaust the "columns" of X. Shown below is this process carried out for two particular strings X nd Y.
Period patterns for words
Some issues of the period of a string involve the idea of a greatest common divisor of two integers. Remember that here we are looking at strings that might use digits as their alphabet. However, every string has a length which is a number and for the notion of a period we are concerned in part with the issue of lengths of strings and of substrings of a given string.
w = aabaaabaa
w = aabaaabaa
Theorem (Nathan Fine and Herbert Wilf):
Borders and periods
The phenomenon that there may be subwords of a word that are both prefixes and suffixes leads to what for me was an unexpected phenomenon, namely the idea captured using the term "border." A border of a word is a subword which is both a prefix and a suffix of the word. It came as a surprise to me that the concept of a border is related to the issue of a period. If a subword u of a string is a prefix and a suffix, and if we shift the string with prefix u to the start of where u appears as a suffix, all of the letters will line up. Thus, such a shift by the length of u will be a period of our string.
Given a string x, let border(x) denote the longest border of x that is not the whole word itself. We see that |x| - border(x) is the amount we must shift x to the right for the start of x to be located at the start of the suffix copy of the border. (Look at the diagram above.) If we compute the "border function" of border(x) we can locate another period of x. We can do this over and over again until we get all of the periods of x.
Photos of Leonidas Guibas and Andrew Odlyzko (Courtesy of Wikipedia and Professor Odlyzko)
Allouche, J-P. and J. Shallit, The ubiquitous prouhet-thue-morse sequence, in Sequences and their applications, pp. 1-16. Springer, London, 1999.
The AMS encourages your comments, and hopes you will join the discussions. We review comments before they're posted, and those that are offensive, abusive, off-topic or promoting a commercial product, person or website will not be posted. Expressing disagreement is fine, but mutual respect is required.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance
Comments: Email Webmaster