Cyclic Symmetry of the Scaled Simplex

This notebook was written by Nathan Williams.  It implements large portions of the paper “Cyclic Symmetry of the Scaled Simplex” by Hugh Thomas and Nathan Williams (http://arxiv.org/abs/1207.5240).

Introduction

Definition.  Let Cylic Symmetry of the Scaled Simplex_1.gif consist of the Cylic Symmetry of the Scaled Simplex_2.gif alcoves contained in the m-fold dilation of the fundamental alcove of the type Cylic Symmetry of the Scaled Simplex_3.gif affine hyperplane arrangement.

Example. The 16 alcoves of Cylic Symmetry of the Scaled Simplex_4.gif are those alcoves contained within the thick black lines.

Cylic Symmetry of the Scaled Simplex_5.gif

As the fundamental alcove has a cyclic symmetry of order (k+1), so does Cylic Symmetry of the Scaled Simplex_6.gif. Let Cylic Symmetry of the Scaled Simplex_7.gif be the set of words of length (k+1) on Z/mZ with sum (m-1)  (mod  m), with the order (k+1) cyclic action given by rotation. As the orbit structure of Cylic Symmetry of the Scaled Simplex_8.gif is easily understood, we determine the orbit structure of Cylic Symmetry of the Scaled Simplex_9.gif with the following theorem.

Theorem. There is an equivariant bijection from Cylic Symmetry of the Scaled Simplex_10.gif under its cyclic action to Cylic Symmetry of the Scaled Simplex_11.gif under rotation.  

Example. Each alcove of Cylic Symmetry of the Scaled Simplex_12.gif is labeled with its corresponding word in Cylic Symmetry of the Scaled Simplex_13.gif.  There are 5 orbits of size 3 and a single orbit (the alcove in the center) of size 1.

Cylic Symmetry of the Scaled Simplex_14.gif

Cylic Symmetry of the Scaled Simplex_15.gif: a poset of words x of length k on Z/mZ

We first convert Cylic Symmetry of the Scaled Simplex_16.gif to a purely combinatorial object.

Definition. Let Cylic Symmetry of the Scaled Simplex_17.gif be the poset of words x of length k on Z/mZ with the partial order induced by the following covering relations:
    1) For a<m-1, ya=(a+1)y, where y is a string of length k-1 on the alphabet Z/mZ.
    2) For b<a, yabz=ybaz, where y and z are two strings on the alphabet Z/mZ, with the total length of the two strings being (k-1).

Example. The posets Cylic Symmetry of the Scaled Simplex_18.gif, Cylic Symmetry of the Scaled Simplex_19.gif

In[1683]:=

Cylic Symmetry of the Scaled Simplex_20.gif

Out[1683]=

Cylic Symmetry of the Scaled Simplex_21.gif Cylic Symmetry of the Scaled Simplex_22.gif Cylic Symmetry of the Scaled Simplex_23.gif Cylic Symmetry of the Scaled Simplex_24.gif Cylic Symmetry of the Scaled Simplex_25.gif

Theorem. There is a poset isomorphism between Cylic Symmetry of the Scaled Simplex_26.gif and Cylic Symmetry of the Scaled Simplex_27.gif. The geometric symmetry of the underlying graph is realized by the cyclic action φ.  

Proof (sketch). Alcoves of Cylic Symmetry of the Scaled Simplex_28.gif are naturally labeled by increasing affine permutations.  The action of the affine symmetric group on Cylic Symmetry of the Scaled Simplex_29.gif is mirrored on (k+1)-cores, which allows us to pass from Cylic Symmetry of the Scaled Simplex_30.gif to (k+1)-cores.  The abacus diagram of the resulting (k+1)-core is necessarily flush, which allows us to just record the number of runners in each column.  For more detail on this bijection, see the paper or the presentation at http://www.math.umn.edu/~will3089/docs/SimplexPresentation/simplex.htm.

Example. The posets Cylic Symmetry of the Scaled Simplex_31.gif, Cylic Symmetry of the Scaled Simplex_32.gif

Cylic Symmetry of the Scaled Simplex_33.gif

Theorem. The graph of Cylic Symmetry of the Scaled Simplex_34.gif has (k+1)-fold cyclic symmetry, realized by an explicit action φ.  

Proof (sketch). We will define a cyclic action φ  of order (k+1) that is a graph isomorphism.  Given a word Cylic Symmetry of the Scaled Simplex_35.gif, form the extended word of length (k+1)m

                                Cylic Symmetry of the Scaled Simplex_36.gif

That is, for any 1≤i≤(k+1), the entries in positions i,(k+1)+i,2(k+1)+i,…(m-1)(k+1)+i are cyclically decreasing by 1. Let Cylic Symmetry of the Scaled Simplex_37.gif be defined by cyclically rotating Cylic Symmetry of the Scaled Simplex_38.gif left so that its leftmost 0 appears as its rightmost character. This induces an action φ on Cylic Symmetry of the Scaled Simplex_39.gif by restricting the resulting word to its first k letters.  Observe that φ is a cyclic action of order (k+1), since there are (k+1) zeros in Cylic Symmetry of the Scaled Simplex_40.gif.  It is now a tedious check to show that φ takes edges to edges. Note that φ is not a poset isomorphism: it reverses the orientation of some edges.  

Example. The graphs of Cylic Symmetry of the Scaled Simplex_41.gif, Cylic Symmetry of the Scaled Simplex_42.gif

In[1684]:=

Cylic Symmetry of the Scaled Simplex_43.gif

Out[1684]=

Cylic Symmetry of the Scaled Simplex_44.gif Cylic Symmetry of the Scaled Simplex_45.gif Cylic Symmetry of the Scaled Simplex_46.gif Cylic Symmetry of the Scaled Simplex_47.gif

Cylic Symmetry of the Scaled Simplex_48.gif: Words of length (k+1) that sum to (m-1)

Definition. Let Cylic Symmetry of the Scaled Simplex_49.gif be the set of words on Z/mZ of length (k+1) with sum equal to (m-1)  (mod  m).

We let Cylic Symmetry of the Scaled Simplex_50.gif act by left rotation, sending Cylic Symmetry of the Scaled Simplex_51.gif to Cylic Symmetry of the Scaled Simplex_52.gif.

Theorem. There is an equivariant bijection w from Cylic Symmetry of the Scaled Simplex_53.gif under φ to Cylic Symmetry of the Scaled Simplex_54.gif under left rotation.

Proof (sketch). Take the first letter of each word from an orbit of Cylic Symmetry of the Scaled Simplex_55.gif under φ, and concatenate these letters into a single word, cyclically repeated to make the resulting word of length (k+1). (This trick is called a bijaction.)  By construction, φ maps to left rotation. A description of the (much more complicated) inverse Cylic Symmetry of the Scaled Simplex_56.gif is in the paper.  

Cylic Symmetry of the Scaled Simplex_57.gif is the set of all words of length 2 on {0,1,2}.

Cylic Symmetry of the Scaled Simplex_58.gif

Cylic Symmetry of the Scaled Simplex_59.gif

Cylic Symmetry of the Scaled Simplex_60.gif toCylic Symmetry of the Scaled Simplex_61.gif--the set of all words of length 3 on {0,1,2} that sum to 2 mod 3.

Cylic Symmetry of the Scaled Simplex_62.gif

Cylic Symmetry of the Scaled Simplex_63.gif

Cylic Symmetry of the Scaled Simplex_64.gif

It turns out that finding Cylic Symmetry of the Scaled Simplex_65.gif is equivalent to the following problem.

Dendrodistinctivity

Definition. Let Cylic Symmetry of the Scaled Simplex_66.gif be the set of all words of length (k+1) on Z/mZ.

Definition. Let Cylic Symmetry of the Scaled Simplex_67.gif and let Cylic Symmetry of the Scaled Simplex_68.gif be an (m-1)-tuple with entries in {0,1,2,…,k+1}. Define a partitioned word
Cylic Symmetry of the Scaled Simplex_69.gif
to be a partition of w into m connected blocks, where b specifies where the dividers are placed. We denote the set of all partitioned words on Z/mZ with w of length k+1 by Cylic Symmetry of the Scaled Simplex_70.gif.

Definition. Define an infinite complete m-ary tree Cylic Symmetry of the Scaled Simplex_71.gif by
    1) The 0th rank consists of the empty word φ, partitioned as Cylic Symmetry of the Scaled Simplex_72.gif.
    2) The children of a partitioned word (w,b) are the m words obtained by prepending -i  (mod  m) to Cylic Symmetry of the Scaled Simplex_73.gif.

Cylic Symmetry of the Scaled Simplex_74.gif.

Cylic Symmetry of the Scaled Simplex_75.gif

Cylic Symmetry of the Scaled Simplex_76.gif

Theorem [Dendrodistinctivity].
    Let Cylic Symmetry of the Scaled Simplex_77.gif be the infinite complete m-ary tree obtained from Cylic Symmetry of the Scaled Simplex_78.gif by replacing each partitioned word (w,b) with its underlying word w. Then each word of length k+1 on Z/mZ appears exactly once.   

Cylic Symmetry of the Scaled Simplex_79.gif.

Cylic Symmetry of the Scaled Simplex_80.gif

Cylic Symmetry of the Scaled Simplex_81.gif

The proof is technical (see sections 8 and 9 of the paper): it first constructs a partition that is an approximation to the desired partition.

Cylic Symmetry of the Scaled Simplex_82.gif

Cylic Symmetry of the Scaled Simplex_83.gif

This approximation is then adjusted to the desired partition.

Cylic Symmetry of the Scaled Simplex_84.gif

Cylic Symmetry of the Scaled Simplex_85.gif

Code

Cylic Symmetry of the Scaled Simplex_86.gif

In[1679]:=

Cylic Symmetry of the Scaled Simplex_87.gif

Cylic Symmetry of the Scaled Simplex_88.gif: Words of length (k+1) that sum to (m-1)

In[1661]:=

Cylic Symmetry of the Scaled Simplex_89.gif

Dendrodistinctivity

In[1664]:=

Cylic Symmetry of the Scaled Simplex_90.gif

Spikey Created with Wolfram Mathematica 8.0