#!/usr/bin/env python # coding: utf-8 # The BH equation is just one of a family of possible equations on the 2D lattice. # # It's represented as # ``` # ◾️◾️◾️ # ◾️◾️◾️ # ▫️◾️▫️ # ``` # # which tells us that the value of the center tile is determined by the values in the bottom left and bottom right. # # Of course, we can consider other formations too. This notebook investigates this. # # ### Equivilance # # The BH representation is the same as: # # ``` # ▫️◾️◾️ # ◾️◾️◾️ # ▫️◾️◾️ # ``` # # since any equation satisfying the BH representation also would satisfy this. Simiarly, # # ``` # ◾️▫️◾️ # ▫️◾️◾️ # ◾️◾️◾️ # ``` # # is the same. Let's continue: # 3x3 Matrix, with center always 0, can be "unwrapped" to the vector # ``` # [ # (1,1) # (1,2) # (1,3) # (2,1) # (2,2) # (2,3) # (3,1) # (3,2) # (3,3) # ] # ``` # # We'd like a few matrices that perform reflections and rotations (about (2,2)). Consider the vertical reflection # ``` # (1,1) <-> (1,3) => 1 <-> 3 # (2,1) <-> (2,3) => 4 <-> 6 # (3,1) <-> (3,3) => 7 <-> 9 # ``` # Or in matrix form, V # In[7]: V = np.array([[0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0]]) # The horizontal reflection is # ``` # (1,1) <-> (3,1) => 1 <-> 7 # (1,2) <-> (3,2) => 2 <-> 8 # (1,3) <-> (3,3) => 3 <-> 9 # ``` # with Matrix, H # In[8]: H = np.array([[0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0]]) # Both are the same under transpose. # # # The single rotation is the most complex: # ``` # (1,1) -> (1,2) => 1 -> 2 # (1,2) -> (1,3) => 2 -> 3 # (1,3) -> (2,3) => 3 -> 6 # (2,3) -> (3,3) => 6 -> 9 # (3,3) -> (3,2) => 9 -> 8 # (3,2) -> (3,1) => 8 -> 7 # (3,1) -> (2,1) => 7 -> 4 # (2,1) -> (1,1) => 4 -> 1 # ``` # with matrix, R: # In[9]: R = np.array([[0, 0, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1, 0, 0, 0]]) # And $R^9 = R$, => $R^8 = I$ # # With these matrices, given a boolean array A, with A[5] == 0 (|{A}| = 256), we can ask, how many unique configurations up to modifications by R, H, and V. That is, A == B iff there exists a polynomial, p, in R, H, V, s.t. p(A) = B. # # I'd like to find all unique A, up to this equivalence relation. Maybe first we count them. # # # Q: are R, H, and V abelian? # # No, but almost. There are lots of simplifications: # # # $$ V^2 = I $$ # $$ H^2 = I $$ # $$ VH = HV $$ # $$ RHR = H $$ # $$ RVR = V $$ # $$ R^4 = VH = VH $$ # $$R^{-1} = R^7$$ # # Example: given the polynomial R^2 H R V R, this can be simplified: # # $$ # R^2 H R V R = R^2 H V = R^6 # $$ # # I think the only polynomials are of the form: # # # $$ R^n$$ # $$ HR^nV $$ # $$ HR^n $$ # $$ R^nV $$ # $$ VR^nH $$ # $$ VR^n $$ # $$ R^nH $$ # # n <= 7 # # # Why? we only need to consider $R^nVR^m$ and $R^nHR^m$ in the interior, since all other forms reduce to some power of R. But # $R^nVR^m = R^{n-1}RVRR^{m-1} = R^{n-1}VR^{m-1}$, and so on, so they eliminate themselves, until R or H is at the start or end. # # # Therefore there are at max 7 * 7 = 49 unique polynomials, but likely lots of redundancy in this. Code: # In[14]: from itertools import product def matrix_pow(M, n): P = np.eye(9, dtype=int) for _ in range(n): P = P @ M return P I = np.eye(9, dtype=int) def _generate_polynomials(start, end, n): yield from ((start @ matrix_pow(R, i) @ end) for i in range(n)) def generate_polynomials(): n = 7 yield from _generate_polynomials(I, I, n) yield from _generate_polynomials(H, V, n) yield from _generate_polynomials(H, I, n) yield from _generate_polynomials(I, V, n) yield from _generate_polynomials(V, H, n) yield from _generate_polynomials(I, H, n) yield from _generate_polynomials(V, I, n) def generate_all_arrays(): for A in product([0,1], repeat=8): A = A[:4] + (0,) + A[4:] yield A def represent(A): print("▫️" if int(A[0]) else "◾️",end="") print("▫️" if int(A[1]) else "◾️",end="") print("▫️" if int(A[2]) else "◾️") print("▫️" if int(A[3]) else "◾️",end="") print("◾️", end="") print("▫️" if int(A[5]) else "◾️") print("▫️" if int(A[6]) else "◾️",end="") print("▫️" if int(A[7]) else "◾️",end="") print("▫️" if int(A[8]) else "◾️") print() def to_str(A): return "".join((str(a) for a in A)) def generate_equivilant_class(A): eqAs = set([]) for X in generate_polynomials(): A_ = X @ A eqAs.add(to_str(A_)) return list(eqAs) def generate_equivilant_classes(): array_to_bucket = {} label = 1 for A in generate_all_arrays(): if to_str(A) in array_to_bucket: continue array_to_bucket[to_str(A)] = label for A_ in generate_equivilant_class(A): array_to_bucket[to_str(A_)] = label label += 1 grouped_dict = {} # Group keys by value for key, value in array_to_bucket.items(): if value not in grouped_dict: grouped_dict[value] = [] grouped_dict[value].append(key) # Return as a list of lists yield from list(grouped_dict.values()) for i, g in enumerate(generate_equivilant_classes(), start=1): print(i) represent(g[0]) # There are 30 classes. One of them is trivial (blank). # To keep things stable, our functional equation should normalize by the number of elements being added. Ex: # # For eq.class 30, # # $$ # f(n,k) = 1/9 ( f(n-1, k-1) + f(n-1, k) + f(n-1, k+1) + ... + f(n+1, k+1) ) # $$ # In[ ]: