[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?
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
More information about the ringing-theory
mailing list