Enzymind Labs

 

Minimal arrays containing all sub-array combinations of symbols

 

For n symbols in m groups, what are the smallest arrays that contain all combinations of adjacent elements?

This is a symbolic combinatorics question, somewhat similar to the necklace problem. I know very little about this topic, and have not attempted to formalize the problem in standard mathematical language. The obsevations and algorithms below were derived from tinkering and intuition.

This problem came up when designing motifs for aperiodic tesselations, for example Thue-Morse patterns. In a 1-D 2-symbol Thue-Morse sequence all pairs of symbols occur ( aa, ab, ba, bb ) but no triplets (of symbols or sets of sequential symbols). Extended to 2-D and more symbols, aperiodic sequences can have sub-arrays (adjacent sets) of symbols that occur infrequently. [To Do: 4-symbol cyclic system example.] It would be nice to be able to draw all possible neighborhoods (sets of adjacent motifs)  with no repetitions.

It is convenient to consider the symbols as sequential integers starting at 0 because the possible pairs can be enumerated as all possible integers with a base of the number of symbols (e.g. binary numbers represent a 2-symbol system).

 

1-D 2-symbol, every pair

There are four unique pairs of two symbols. Using {0,1} as symbols they correspond to the binary (base 2) numbers between 0 and 3:
A bit of trial and error yields a string with all adjacent pairs and no duplications: The mirror and complements of this string also are solutions:

Note that the first symbol is the same as the last for each solution, so the same sets of pairs ocurrs in the four term rings:
and in any cyclic permutations of the rings. Allowing for a 3-D rotation of the ring, these 2-D enantiomers are identical, and the minimal solution is unique.

1-D 2-symbol, every triplet

There are eight unique triplets of two symbols. Using {0,1} as symbols they correspond to the binary (base 2) numbers between 0 and 7:

A solution can be found by starting with [ 0 0 0 1 1 1 ] and iteratively add a symbol to the right with these conditions:
(a) Choose the symbol that will form a triple that is not yet in the string
(b) If both symbols can be added to result in a new triplet, use the one that will most closely balance the number of each symbol.
(c) If the number of symbols is balanced, add 0.

Here's the sequence of adding to the string, with the appropropriate conditions: Condition (c) is not used here, but will be for longer sub-strings below. As in all solutions, mirror and complements of this string also are solutions.
Similar to the "every pair" solution, the first two symbols are the same as the last, so the same sets of triplets ocurrs in the eight term ring:
and in any cyclic permutations. This is a unique minimal solution.

1-D 2-symbol, every quadruplet

Using the algorithm described in "every triplet":


The sixteen term ring is:
Is this is a unique minimal solution, up to cyclic permutations and mirroring? This is a bit more difficult to prove, but tractable by brute force (an exhaustive search).

1-D 2-symbol, every quintuplet

Using the same procedures as for the "every triplet" string:

The 32-term ring is:
Is this is a unique minimal solution, up to cyclic permutations and mirroring? This is even more difficult to prove, but still tractable by brute force.

2-D 2-symbol, every 2x2

There are sixteen possible 2x2 sub-arrays with two symbols. Using {0, 1} as symbols they correspond to the binary (base 2) numbers between 0 and 15:


I gave up on using a toroidal (wrap-around) array solution, because it is ugly (there must be many duplicates). A 5x5 array seems natural because it has exactly 16 2x2 sub-arrays. But it has 25 elements so must include an unequal number of the two symbols -- it didn't seem possible since the set of 2x2's is equivalent with a swap of symbols so there must be an equal number of symbols.


13-0's and 12-1's, but the central elements (with more 1's) appear in more sub-arrays that the side elements (with more 0's).

All rows, but only 3 of 5 columns, are 1-D 2-symbol solutions. The first and last column are the same, so it could be a 5x4 cylinder

L_system_tiling( 'test', 1, 2, 1, 0,'zig_zag_eel_motif_5.png', '2x2_2s_a.png', 0, 1 );


Of course it works with a swap of the symbols, or with rotations/mirrors of the matrix too. I'd be willing to bet that is is unique -- there are only so many 5x5 arrays and I tried just about every one that contained [ 0 0; 0 0 ] and [ 1 1; 1 1 ].

2-D 2-symbol, Thue-Morse 2x2s

Corners tilings

[To Do: These [will be] examples of a combinatorial system with a second neighborhood constraint.



The pattern is formed from these rotations and inversions of a single "corner motif"::


The left half of the pattern is this arrangement::



This pattern has a nice set of symmetries and anti-symmetries [ To Do: Describe in B/W matrix.]. But it doesn't include the fifth set [ To Do: Show ].
Is there an square, or nearly square matrix of motifs that contains all 2x2 patterns in an arrangement where the white and black (a's and b's) have the same relationship?

References

P. Ligeti and P. Sziklai
Department of Computer Science, Eotvos University, Budapest, Pazmany P.s.1c, H1117 Budapest, Hungary

Discrete Mathematics
Volume 305, Issues 1-3, 6 December 2005, Pages 372-378