[r-t] Complexity of extents

[Richard Smith]

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?

I'd been thinking about this myself, and I'm coming round to 
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