A Group Structure for a Finite Set of Necklaces?

Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.

A Group Structure for a Finite Set of Necklaces?

Postby henriette on June 26th, 2012, 7:34 am 

Dear,

Let's consider the finite set of the necklaces with 8 pearls and possibly up to 8 colors.
They are unlabeled necklaces, invariant by permutation of the pearls'colors and by rotation.
There are 544 different necklaces. The necklaces Nj are sorted by their minimum equivalent values in (0,8^8)

    N0 : (00000000)=(11111111)=(...)=(77777777) : the only necklace with 1 color
    N1 : (00000001)=(10000000) rotation=(66666664) color permutation
    N2 : (00000011)
    N3 : (00000012)
    N4 : (00000101)
    ...
    ...
    N543 : (01234567) = the only necklace with 8 different colors

Question : Can a group structure by associated to this set?

I am in need to give a meaning to Ni+Nj and to the inverse of a given Ni.
The bibliography is quite difficult : The p-adic representation and the Witt vector theory seem to be good candidate for doing so...
(maybe 7-adic here, because the first pearl of each collar is known (0) and because all the necklace but the latest have a maximum of 7 colors).

Any experience or suggestion for further reading?
thank
User avatar
henriette
Member
 
Posts: 357
Joined: 30 Oct 2007


Re: A Group Structure for a Finite Set of Necklaces?

Postby Marshall on June 26th, 2012, 10:03 pm 

That seems like a sophisticated problem. You are far along on it, it looks like.

I can't offer any help. I am simply impressed. Have you studied the cases N=2 and N=3?

Does a symmetry group arise in either of those cases?

For clarification, is the necklace considered to be linear or circular.

Linear would look like O-O-O-O-O-O-O-O

Circular would loop around, so the rotation subgroup would make many configurations equivalent.

I suppose you mean circular since you mentioned rotations.

In that case, in the second line (N1) you probably meant to write

O-O-O-O-O-O-O-1 = (...) = 1-O-O-O-O-O-O-O rotation
=(...)=(66666664) color permutation

If you omit the =(...)= then it looks like you just swapped ends.

Henriette do you happen to know the definition of the *semi-direct product*.

I can't remember how the semidirect product of two groups is constructed, or what this accomplishes. I learned of it long long ago and have completely forgotten.

I envy you if your brain is still young enough to do this problem.
But I do not envy your being confronted by it. It is very hard. One could sweat over this problem. I think.
Good luck with it!
User avatar
Marshall
Honored Member
 
Posts: 7916
Joined: 17 Oct 2006


Re: A Group Structure for a Finite Set of Necklaces?

Postby henriette on June 27th, 2012, 11:40 am 

Dear,
Thank you for the answer. This question arises when I consider to make a quantum graph (1) approximation of images of natural scenes. In this model, the nodes of the regular graph are not the pixels but the 8 pixels long circular unlabeled necklaces around each of them.
There are some papers devoted to the generation of necklaces, but it is not a big deal to generate the basis of the unlabeled necklaces with 8 pearls and up to 8 colors (2).

I studied Semidirect_product a long time ago, and thank to your comment I will have a glance to http://en.wikipedia.org/wiki/Semidirect_product

(1) Sven Gnutzmann and Uzy Smilansky, Quantum Graphs: Applications to Quantum Chaos and Universal Spectral Statistics, Advances in Physics, 55 (5-6), 527-625, 2006.

(2) Kevin Cattell, Frank Ruskey, Joe Sawada, Micaela Serra, C.Robert Miers, Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2), Journal of Algorithms, Volume 37, Issue 2, November 2000, Pages 267-282
User avatar
henriette
Member
 
Posts: 357
Joined: 30 Oct 2007


Re: A Group Structure for a Finite Set of Necklaces?

Postby Percarus on July 1st, 2012, 4:58 am 

Sorry, my maths is really rusty, it was stated that there are:

There are 544 different necklaces.


But 8 factorial (8!) is 40,320. I forget how to derive mathematically the number of combinations - can someone PM me the calculation reasoning as simple as possible? In a lotto scenario with six numbers ranging from 1-60 the calculation would be, 60x59x58x57x56x55, correct?
User avatar
Percarus
Banned User
 
Posts: 787
Joined: 16 Dec 2008
Location: Perth - Australia
Blog: View Blog (4)


Re: A Group Structure for a Finite Set of Necklaces?

Postby henriette on July 20th, 2012, 11:58 pm 

Dear,
Unlabelled necklaces are invariant by rotation of the beads and by color permutation, this is why there are only 544 unlabelled necklaces with 8 beads and up to 8 colors.
The number of primal necklaces (closed to that of unlabelled necklace) have been derived from inversion of the classical Mobius function : http://en.wikipedia.org/wiki/Necklace_polynomial

Metropolis and Rota and Christian Lenart discuss the point
N. Metropolis and C.-C. Rota, Witt vectors and the Algebra of Necklaces, Adv. in Math. 50
(1983), 95–125
Cristian Lenart, Formal Group-Theoretic Generalizations of the Necklace Algebra, Including a q-Deformation, Journal of Algebra DOI:10.1006/jabr.1997.7203
User avatar
henriette
Member
 
Posts: 357
Joined: 30 Oct 2007


Re: A Group Structure for a Finite Set of Necklaces?

Postby henriette on March 10th, 2016, 4:06 am 

Dear,


First, I managed to sort properly the unlabeled necklaces on a torus (UN, 6 beads, 6 colors, there are 43 such necklaces) http://theory.cs.uvic.ca/inf/neck/NecklaceInfo.html) .

000000
000001
.......11
.......12
..........
012345



The post includes a question about graph and Hamiltonian cycles. Alas, it 's not yet a standard graph, because some vertexes of the considered graph must be erased while propagating within the graph. This is because the nominal nodes include all the representatives of given classes (i.e. the 6 rotations of each Unlabelled Necklace) while the cyclic path of interest must includes a single representative of each class. (the graph is defined of the set of the 43x6 (rotation) necklaces (vertex) and edges connect the 43x6 necklaces that only differ by the bead at position 0)

I foresee to defend that the proposed classifying of the necklaces follows the most basic possible rule that defines the torus : only one beads changes from a necklace to its neighbor on the torus and this bead is always at the same place.
The rule is the following, you start from a given necklace UN(0) and a given rotation of UN(0), the next necklace on the torus is UN(i+1)=rotate(Un,1 bead clockwise) + change bead(0)

A physical model is derived from the density of state of the UN in images of natural scenes.
This torus offers the possibility to define a law group (i.e. the law group on the nth roots of 1) on the set of the unlabelled necklaces and it opens a way to rule a physical model on shapes, a basis of shapes are the UN. The necklace 000000, that only have a single neighbor (i.e. 000001), can not be included into the torus, has been extracted from the list ; it is used to define a zero for a complex plane in the UN space while the torus is the equivalent of the unit circle in the complex plane.

Billions of pathes have been tested yet and a single hamiltonian path on the UN has been carried out. The combinatorics to define a torus is not tractable and because the graph is changing during path exploration, there is no way yet to use the standard algorithms that help to find hamiltonian cycles.

The question is the following : is there a bibliography on graphes where vertexes may change during propagation of a path? I found nothing about this topics on graduate and post-graduate courses and I lost my brain on Reutenauer's papers (who on Earth was that so genius guy?), Hopf algebra and alike. I envisioned that the proposed graph may be extended to a standard graph (with stated vertex/nodes) ...

Thank you
User avatar
henriette
Member
 
Posts: 357
Joined: 30 Oct 2007



Return to Mathematics

Who is online

Users browsing this forum: No registered users and 4 guests