Orthogons and orthobraces

One of these days soon I will get back to writing about primality tests, but for now I am having fun getting sidetracked on orthogons!

In a previous post I gave rules for when two orthogons will be considered the same:

Two orthogons are the same if one is the mirror image of the other.
Two orthogons are the same if one can be turned into the other just by changing the length of some of the edges.

I just realized that I forgot a rule!

Two orthogons are the same if one is a rotation of the other.

You might not have even noticed this omission, because it would be strange not to have this rule: usually we think of two polygons as being the same if one is just a rotation of the other. And if rotating an orthogon were to result in a distinct orthogon, then there would be way too many distinct orthogons (uncountably infinitely many, in fact).

So, for example, these four orthogons are all the same:

Of course this notion of sameness should also be reflexive (any orthogon is the same as itself) and transitive (if A is the same as B and B is the same as C, then A is the same as C), so that it is an equivalence relation.

Now, in my previous post I finished the proof showing that orthogons are in 1-1 correspondence with sequences of X’s and V’s, containing exactly 4 more X’s than V’s, when the sequences are also considered the same up to rotation and reversal. Sequences considered the same up to rotation and reversal are sometimes called bracelets. They are very similar to the necklaces we saw in a recent proof of Fermat’s Little Theorem; the only difference is that two sequences which are the reverse of each other are considered distinct as necklaces, but the same as bracelets. Let’s call bracelets of X’s and V’s, with exactly four more X’s than V’s, orthobraces. (Not to be confused with orthodontics, which are also called braces, but are definitely not the same when rotated.)

So we have reduced the problem of listing all the orthogons with a given number of vertices to two subproblems:

List all orthobraces of a given length.
Turn each orthobrace into a drawing of an orthogon.

I want to start by talking about the first subproblem. To get a sense for why listing bracelets is an interesting problem, here are some questions you can ponder:

Start by considering normal sequences (so, e.g., XXXXXV, VXXXXX, and XXXVXX are all different sequences). How many sequences are there with four X’s and no Vs? How many with five X’s and one V? Six X’s and two V’s? In general, how many sequences are there with $n+4$ X’s and $n$ V’s?
Try listing small orthobraces. How many do you get for each number of V’s? You can try to come up with a formula if you really want, but this actually turns out to be quite difficult; I suggest just trying to systematically list orthobraces and see how many you get. For example, there is only one orthobrace when $v = 0$ , namely XXXX. There is also only one, XXXXXV, for $v = 1$ . This is the only one since any sequence with five X’s and one V is just a rotation of this one. (The particular sequence we pick to represent the orthobrace doesn’t matter.)
Compare how many bracelets there are of each size with how many sequences there are. What seems to be the general trend?
An obvious algorithm for listing all bracelets of a given size is to list all the sequences (this is very easy), and throw away any sequences which are equivalent to one we’ve already generated when considered as bracelets (i.e. up to rotation and reversal). Based on your observations above, how feasible is this method?

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

4 Responses to Orthogons and orthobraces

Gesh says:

February 25, 2018 at 4:27 pm

Haven’t thought much about the latest questions yet.
Question 1 is clearly the usual stars-and-bars question (with solution $\left(2n+4\choose n\right)$ ). As for question 3, a quick back-of-the-envelope estimate – assuming that a generic string differs from all its shifts and reflections (which is true for something like $1-n2^{-n/2}$ strings) – gives that the amount of strings corresponding to a given orthobrace is linear in the length of the orthobrace, thus making the amount of orthobraces grow about as $O(2^n/n)$ . This, in turn, suggests that the problem you’re alluding to in question 4 is that we we need to canonicize an exponentially-growing set by a linearly-growing relation, which would take exponential time. Hence the need for a canonical-by-construction generating function.

One thing that does stand out to me is that the identifications you made (orthobraces are considered identical up to cyclic permutations and reversals (which corresponds to mirroring the orthogon)) correspond to quotienting the set of strings over $\Sigma=\{X,V\}$ by the action of the infinite dihedral group.

In more detail, let $\Sigma^n$ the set of all strings of length $n$ over $\Sigma$ , and $\Sigma^*=\bigcup_n\Sigma^n$ .
Then $D_n=\langle r,s\mid r^n=s^2=1, rsr^{-1}=s\rangle$ acts on $\Sigma^n$ by sending $r$ to a one-symbol shift (in an arbitrary direction) and $s$ to reversal.

To extend these actions to an action on $\Sigma^*$ , we first view $D_n$ as $D_n=\mathbb{Z}/n\mathbb{Z}\rtimes\mathbb{Z}/2\mathbb{Z}$ , which clearly extends to an action by $D_m$ for all $n\mid m$ by the natural map $\mathbb{Z}/m\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z}$ . This procedure extends to $D_\infty=\mathbb{Z}\rtimes\mathbb{Z}/2\mathbb{Z}$ , giving an action of $D_\infty$ on $\Sigma^n$ for all $n$ .
Taking the union of these actions, we obtain an action on $\Sigma^*$ .

Quotienting $\Sigma^*$ by this action, we obtain the braces,
with the orthobraces being just those braces arising from $\Sigma^*\supseteq\mathcal{V}=\{\sigma\mid\#_X(\sigma)=\#_V(\sigma)+4\}$ under the action.

This gives a way to improve the estimate of the growth rate from above, by use of Burnside’s theorem. Clearly it suffices to estimate the growth rate at prime lengths (used to keep the strings fixed by $r^k$ manageable$).
Noting that $sr^k$ fixes concatenations of palindromes of lengths $k,n-k$ – of which there are $2^{(k+n-k)/2}=2^{n/2}$ and that $r^k$ fixes strings that are repetitions of strings of length $k$ for $k\mid n$ , we have that the amount of braces – which equals the average amount of points fixed by an action of $D_n$ – is $(n2^{n/2}+2)/2n=O(2^n/n)$ – the same estimate, but with better constants.

P.S. Sorry for the more rambly nature of this comment, I didn’t take the time to properly digest my thoughts here.
- Brent says:
  
  March 2, 2018 at 10:29 am
  
  Great analysis! I think you are spot on.
Pingback: Listing orthobraces | The Math Less Traveled
Pingback: Efficiently listing orthobraces | The Math Less Traveled