Opened 8 years ago

Closed 7 years ago

#13726 closed enhancement (fixed)

The semimonomial group

Reported by: tfeulner Owned by: joyner
Priority: major Milestone: sage-5.13
Component: group theory Keywords: (semi-)monomial group, semilinear action, isometry group
Cc: ppurka Merged in: sage-5.13.beta1
Authors: Thomas Feulner Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

A semimonomial group over a ring R of length n is equal to the semidirect product of the monomial group and the group of ring automorphisms. The multiplication of two elements (\phi, \pi, \alpha)(\psi, \sigma, \beta) with

  • \phi, \psi \in {R^*}^n
  • \pi, \sigma \in S_n
  • \alpha, \beta \in Aut(R)

is defined by:

(\phi, \pi, \alpha)(\psi, \sigma, \beta) := (\phi * \psi^{\pi, \alpha}, \pi * \sigma, \alpha * \beta)

with

\psi^{\pi, \alpha} := (\alpha(\psi_{\pi(0} ) ), \ldots, \alpha(\psi_{\pi(n-1} ) ) )

and an elementwisely defined multiplication of vectors.

This group plays an important role in coding theory since it is the group of all semilinear isometries (relative to the Hamming/Lee?/homogenous metric) of the ambient space.


apply only: trac_13726-semimonomial_group_vb.patch

Attachments (4)

semimonomial_group.patch (28.2 KB) - added by tfeulner 8 years ago.
trac_13726-semimonomial_group.patch (29.7 KB) - added by tfeulner 8 years ago.
trac_13726-semimonomial_group.2.patch (30.3 KB) - added by tfeulner 7 years ago.
new class names
trac_13726-semimonomial_group_vb.patch (30.4 KB) - added by vbraun 7 years ago.
Rediffed patch

Download all attachments as: .zip

Change History (23)

Changed 8 years ago by tfeulner

comment:1 Changed 8 years ago by tfeulner

  • Description modified (diff)

comment:2 Changed 8 years ago by tfeulner

  • Description modified (diff)
  • Status changed from new to needs_review

Patchbot: apply trac_13726-semimonomial_group.patch

Last edited 8 years ago by tfeulner (previous) (diff)

comment:3 Changed 8 years ago by tfeulner

  • Description modified (diff)

Changed 8 years ago by tfeulner

comment:4 Changed 8 years ago by tfeulner

Made some changes which were necessary for #13771. In particular, I changed the definition of the multiplication.

comment:5 Changed 8 years ago by tfeulner

Apply trac_13726-semimonomial_group.patch

comment:6 Changed 8 years ago by ppurka

Hmm... I can only suggest minor cosmetic changes. Someone else needs to look at the math behind what you implemented.

comment:7 Changed 7 years ago by tfeulner

  • Description modified (diff)

Updated patch

Patchbot: apply trac_13726-semimonomial_group.2.patch

Last edited 7 years ago by tfeulner (previous) (diff)

comment:8 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:9 follow-up: Changed 7 years ago by vbraun

  • Your _element_class method doesn't do anything non-trivial, its simpler to use
    class SemimonomialGroup(...):
        Element = SemimonomialGroupElement
    
    instead.
  • Your parent overrides __call__, thats a big no-no in our parent/element framework. By default, calling the parent will end up using SeminmonomialGroupElement.__init__. If you need to normalize arguments, you should implement a SemimonomialGroup._element_constructor_ method. See e.g. Simon King's talk at http://wiki.sagemath.org/days53/schedule for details. (This should be better documented in the developer manual, I know).
  • Also run the testsuite for elements, e.g. TestSuite(S.an_element()).run()
  • It would be nice to have exceptions in py3-compatible syntax (this should also go into the developer manual) and lower-case:
      raise Exception, 'This is a boo-boo'   # bad
      raise Exception('this is a boo-boo')   # good
    
  • Is SemimonomialGroup really used in the literature? A quick googling doesn't find any other references. Its a bit confusing since you are not talking about a generalization of monomial groups. The latter is already quite general, e.g. every supersolvable group. Perhaps AutomorphismGroupOfLinearCode would be a more fitting description? Or is there another characterization? I realize that thats a handful, but it could be made available as LinearCode.AutomorphismGroup, say.
  • Storing the translation in a list is tricky as the user might inadvertently change it
      sage: g = my_group.gen(0)
      sage: v = g.get_v()
      ... 
      sage: v[0] = 1   # changes g!
    
    To hold immutable data, its better to use tuples. Alternatively, use Sage vectors and set them immutable:
      sage: v = vector(GF(3), [0, 1, 2])
      sage: v.set_immutable()
      sage: v[0] = 1
      ...
      ValueError: vector is immutable; please change a copy instead (use copy())
    
Last edited 7 years ago by vbraun (previous) (diff)

comment:10 in reply to: ↑ 9 Changed 7 years ago by tfeulner

Replying to vbraun:

I made all the changes you suggested except for renaming the group.

  • Is SemimonomialGroup really used in the literature? A quick googling doesn't find any other references. Its a bit confusing since you are not talking about a generalization of monomial groups. The latter is already quite general, e.g. every supersolvable group. Perhaps AutomorphismGroupOfLinearCode would be a more fitting description? Or is there another characterization? I realize that thats a handful, but it could be made available as LinearCode.AutomorphismGroup, say.

There are a few other references, for example T. Honold and I. Landjev: Linear codes over finite chain rings. But mostly, people do either restrict themselves to linear isometries, which leads to the action of the monomial group or they don't express the equivalence relation with the help of a group action (semilinearly equivalent codes).

I do not understand the rest of your comment. This group is a generalization of the monomial group, since you just add the group of field automorphisms, similar to the construction of the general semilinear group. I think AutomorphismGroupOfLinearCode would be confusing, since the elements of this group need not to define an automorphism of a linear code. The automorphism group of a linear code is a subgroup of the semimonomial group.

Another characterization would be the group of semilinear Hamming isometries.

comment:11 follow-up: Changed 7 years ago by vbraun

Here is what I'm confused about. A monomial group is one where all characters are induced from linear characters. Although I haven't checked, it seems very plausible that the group of monomial transformations is a monomial group. But I don't think the converse is true. E.g. S_3 is a monomial group

sage: SymmetricGroup(3).is_monomial()
True

but doesn't seem to be the group of monomial automorphisms of a vector space (Is this true?).

comment:12 in reply to: ↑ 11 ; follow-up: Changed 7 years ago by tfeulner

Replying to vbraun:

Here is what I'm confused about. A monomial group is one where all characters are induced from linear characters. Although I haven't checked, it seems very plausible that the group of monomial transformations is a monomial group.

I did not find any answer to your question. But the wreath product G \wr S_n is known as the complete monomial group. So, do you think I should call my group CompleteSemimonomialGroup or SemimonomialTransformationGroup to emphasize the difference?

But I don't think the converse is true. E.g. S_3 is a monomial group

sage: SymmetricGroup(3).is_monomial()
True

but doesn't seem to be the group of monomial automorphisms of a vector space (Is this true?).

The symmetric group S_n is the group of monomial automorphisms of the n-dimensional binary vector space.

comment:13 in reply to: ↑ 12 Changed 7 years ago by vbraun

Replying to tfeulner:

I did not find any answer to your question. But the wreath product G \wr S_n is known as the complete monomial group. So, do you think I should call my group CompleteSemimonomialGroup or SemimonomialTransformationGroup to emphasize the difference?

I think either name would be fine. SemimonomialTransformationGroup sounds clearer to me since it makes it clear that we are talking about groups acting in a certain way. Though if people in your field always talk about complete monomial groups then the former might be better, I don't know. Take your pick ;-)

The symmetric group S_n is the group of monomial automorphisms of the n-dimensional binary vector space.

Oh, good point. I was somehow assuming that there is at least one non-trivial unit.

comment:14 follow-up: Changed 7 years ago by vbraun

Small nitpicks:

  • In general it is better to use lazy import to improve the Sage startup time:
    lazy_import('sage.groups.semimonomial_group.semimonomial_group',
                'SemimonomialGroup')
    
    in sage/groups/all.py. Then the actual import is deferred until you use it.
  • incidentally, the change to sage/groups/all.py doesn't apply cleanly on sage-5.13.beta0 and needs to be rediffed anyways.
  • Add also semimonomial_group_element to the developer manual.

The code looks great, thank you for your hard work!

comment:15 in reply to: ↑ 14 ; follow-up: Changed 7 years ago by tfeulner

Unfortunately, people do not use group actions in coding theory... I also prefer semimonomial transformation group and semimonomial transformation for the elements. So, I changed the class names to these names.

Replying to vbraun:

Small nitpicks:

  • In general it is better to use lazy import to improve the Sage startup time:
    lazy_import('sage.groups.semimonomial_group.semimonomial_group',
                'SemimonomialGroup')
    
    in sage/groups/all.py. Then the actual import is deferred until you use it.

Done.

  • incidentally, the change to sage/groups/all.py doesn't apply cleanly on sage-5.13.beta0 and needs to be rediffed anyways.

Is this my job, too?

  • Add also semimonomial_group_element to the developer manual.

Done.

The code looks great, thank you for your hard work!

Thanks for all your help, Volker!

Changed 7 years ago by tfeulner

new class names

comment:16 in reply to: ↑ 15 Changed 7 years ago by vbraun

Replying to tfeulner:

  • incidentally, the change to sage/groups/all.py doesn't apply cleanly on sage-5.13.beta0 and needs to be rediffed anyways.

Is this my job, too?

Afraid so... depending on how complicated it is, the author should be the most qualified to do this. Though it its pretty trivial here.

comment:17 Changed 7 years ago by vbraun

  • Description modified (diff)
  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

Changed 7 years ago by vbraun

Rediffed patch

comment:18 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:19 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.13.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.