Overlap Patterns

From n = 900: From n = 1800, zoomed in: From n = 2401:

An overlap pattern is a binary string that describes how a given character string overlaps shifted copies of itself.  For example, consider the string "abc". Its overlap pattern is "100".  For short, op("abc") = "100".  Here's another couple of examples: As we see, op("aba") = 101.  And op("aabaa") = "10011".      For a string s of length n, with characters indexed from 0 to n-1, the kth digit of op(s) = 1 if and only if the first n-k characters of s match its last n-k characters (in order.)  Notice that since every string matches itself, every overlap pattern starts with "1". What is an overlap pattern table? There is an OP table for every positive integer.  (We can debate whether or how to define one for n = 0.)  It consists of every possible overlap pattern of length n, arranged in increasing numeric order.  For n = 1, every string s of length 1 has op(s) = "1", so OP table n = 1 consists o...

  A zoomed-out view of a table of "representative strings".  (More colorful naming suggestions are welcome!)  There is a one-to-one correspondence between each overlap pattern table and its representative string table; each string s  lines up with its overlap pattern p .  Most overlap patterns describe multiple strings, so there are many possible representative string tables for each overlap pattern table. Some closeups:

  Overlap pattern tables n = 1 - 10, as seen at the top of any table n > 20: The first twelve overlap pattern tables, side by side: n = 11 - 16. The top of each table n contains the first floor((n-1)/2) tables. The bottom half of each table, where new patterns begin to take shape, is distinguished by its lack of complete horizontal lines (except for the base.) n = 17 - 20. The length of each table increases exponentially with n (proof forthcoming.)  As n increases, more detail can be seen.  The following are small slices of tables for various values of n: At n = 900: What emerges as n continues to grow, and is there a limit to its complexity?