# [r-t] Complexity of extents

Richard Smith richard at ex-parrot.com
Mon Jun 24 17:32:41 UTC 2013

```Matthew Frye wrote:

> On 21 Jun 2013, at 23:25, Mark Davies <mark at snowtiger.net> wrote:
>> RAS writes,
>>
>>> The problem with that is that most general-purpose
>>> compression programs (certainly including gzip) don't
>>> understand a string occuring once forwards and a second
>>> time backwards, e.g. "abcdefghijihgfedcba".  Clearly that
>>> string has structure, but gzip doesn't spot it.
>>
>> That's a good point. Perhaps it would be sensible to
>> concatenate a reversed copy of the entire string, and
>> compress the combined entity. This ought to produce a
>> higher compression ratio for strings which have reversed
>> elements within them.
>
> But how many cases like this are you going to address?
> What about back-front symmetry? Rotational? Double?

the view that the question we should be asking is: does the
symmetry (or other structure) make it easier to get an
extent?  Palindromic symmetry certainly seems like it does,
as does an n-part structure.  Maybe glide symmetry does.
But when I try to get an extent with rotational symmetry, it
feels like I'm fighting against the symmetry rather than
utilising it.

I think we can put this feeling onto a firmer mathematical
basis if we want.  An n-part extent can be written H.M where
H = <h> is the group of order n generated from the lead
head, h, and M is the set of rows in one part. In doing
this, we're no longer encoding |H|.|M| rows, but rather
|H|+|M|.  Less information, therefore less complexity and
more structure.

The same is true for a palindromic extent.  We can write it
H.M where H = {1,e} = <e> is the group of order 2 generated
by the change, e, at the lead-end symmetry point.  And for a
palindromic n-part, we can again write it H.M where H =
<e,h> is a dihedral group of order 2n.

What of a glide-symmetric extent?  If the first half of the
extent has changes {c_1, c_2, c_3, ...}, then these produce
the rows M = {1, c_1, c_1.c_2, c_1.c_2.c_3, ...}.  If c is a
change, then its reverse is c' = τ.c.τ where τ is back
rounds, and the rows in the second half of the extent are
{m, m.τ.c_1.τ, m.τ.c_1.c_2.τ, m.τ.c_1.c_2.c_3.τ, ...} =
mτMτ, using the fact that τ^2 = 1 and where m is the row at
the mid-point of the extent.  We can therefore represent the
extent as the union of M and mτMτ, but because of the τ
post-multiplication, we cannot convert this into the form
H.M for some H.  A similar result is true of rotational
symmetry.

Why should we consider extents that can be written H.M to be
more structured than those that can be written, say, M union
mτMτ?  It might sound a bit arbitrary.  But I would argue
otherwise, as there are good techniques for generating
extents of the form H.M -- mathematically, think cosets and
transversals -- but I don't know of useful techniques for
generating extents of other forms.  Perhaps that's partly my
ignorance, but I do suspect that there's a genuine result to
be proven along these lines.

> Dealing with them piecemeal isn't really very satisfactory
> (although the possible symmetries are finite, so we
> probably could deal with them all this way).

What about properties like being right placed?

RAS
```