## 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?

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

henriette
Member

Posts: 362
Joined: 30 Oct 2007

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

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!

Marshall
Honored Member

Posts: 7916
Joined: 17 Oct 2006

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

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

henriette
Member

Posts: 362
Joined: 30 Oct 2007

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

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?

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?

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

henriette
Member

Posts: 362
Joined: 30 Oct 2007

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

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

henriette
Member

Posts: 362
Joined: 30 Oct 2007

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

Unlabelled Necklaces (6,6) Concatenation

Dear,

Unlabelled Necklaces are beads rotation and color permutation invariant n-color n-beads necklaces.
The image shows the only possible way to concatenate the 43 Unlabelled Necklaces 6-6 from 000000 to 012345 (necklaces are the 6 beads columns)
0: green, 1 : blue, 2: red, 3: yellow, 4: Black, 5: purple
Within the sequence a representant of each class of necklaces appears exactly once. The sequence is [000000-upper line of the image-52013]
colors can be chosen differently but the resulting sequence of the UN would be the same.

Question : because of the uniqueness of the solution, may it make sense to test such sorting as a description of energy levels in Boltzman like model?

Ps : The 43 UN 66 (lexicographic order)
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 0 1 2
0 0 0 1 0 1
0 0 0 1 0 2
0 0 0 1 1 1
0 0 0 1 1 2
0 0 0 1 2 1
0 0 0 1 2 2
0 0 0 1 2 3
0 0 1 0 0 1
0 0 1 0 0 2
0 0 1 0 1 1
0 0 1 0 1 2
0 0 1 0 2 1
0 0 1 0 2 2
0 0 1 0 2 3
0 0 1 1 0 2
0 0 1 1 2 2
0 0 1 1 2 3
0 0 1 2 0 1
0 0 1 2 0 2
0 0 1 2 0 3
0 0 1 2 1 2
0 0 1 2 1 3
0 0 1 2 2 1
0 0 1 2 2 3
0 0 1 2 3 1
0 0 1 2 3 2
0 0 1 2 3 4
0 1 0 1 0 1
0 1 0 1 0 2
0 1 0 1 2 3
0 1 0 2 0 3
0 1 0 2 1 2
0 1 0 2 1 3
0 1 0 2 3 2
0 1 0 2 3 4
0 1 2 0 1 2
0 1 2 0 1 3
0 1 2 0 3 4
0 1 2 3 4 5

henriette
Member

Posts: 362
Joined: 30 Oct 2007

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

Ah! Now I see ... way beyond my mathematical know how. I don't understand half the terminology.

Does this kind of thing relate :

I am completely ignorant here, but keen to learn if you've the time to talk me through the problem.

Resident Member

Posts: 5009
Joined: 14 Mar 2012

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

What an interesting thread. We don't get much chit-chat around here about p-adic representations.

OP, your link http://theory.cs.uvic.ca/inf/neck/NecklaceInfo.html did not work for me. Site could not be reached.
someguy1
Member

Posts: 638
Joined: 08 Nov 2013

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

Is there is systematic way of solving the n bead n color problem? If so I am not seeing one. It looks to me like you just have to count them. As I try to solve this for increasing n I am seeing little in the way patterns. Therefore, I am suspecting there is no group structure in general. Though I suppose it is possible that for a given n there might be, but if there is I don't see how you could determine this analytically. I am wondering if this is a problem for computer... to exhaustively test for different possible group structures for a given n. Do you know if group structures have been found in the cases of n=1,2,3,4,5,6,7?

Also do you know the counts for other n, just to check my work...
n=2 gives 2 necklaces
n=3 gives 3 necklaces
n=4 gives 6 necklaces
n=5 gives 13 necklaces

Just counting them as I have been doing, it seems very easy to miss one or even count one too many (by missing an equivalence).

mitchellmckain
Member

Posts: 930
Joined: 27 Oct 2016

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

You can break the problem down by number of colors in the necklace (call it c). Then for c=1 and c=n you always get a count of only one necklace. For c=2 you get 1,1,3,3,7,8 for n=2,3,4,5,6,7 respectively... It is looking to me like any formula you make for even just c=2 has to be continually adjusted for higher n. It does not look promising for a general formula or general way of determining a group structure.

mitchellmckain
Member

Posts: 930
Joined: 27 Oct 2016

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

Dear all,

Thank you for the answers. Writing compact sequences of partial words over an alphabet is a topics in combinatorics. Alas, though many sets of partial words have been analyzed yet (including necklaces, k-set of n-set, permutations of a single word, etc.), no theorem is available yet to deal with the unlabelled necklaces. A little team of well-tempered students and a combinatorist give me some help since a couple of months...

Let's consider a field UN(M,t) of unlabelled necklaces, where M is the location and t is over [0,1]. UN(M,t) is derived from a single image I(M,lambda). (time t varies with model of exposure time)
Bouding conditions :
UN(M,0) = 000000 (t=0 is the black image)
UN(M,1)= 012345 (t=1, fully colored image)

In this context, the following two crazy questions arise.

-1 Modeling UN(M,t) in order to analyse the image (of the environment) in terms of physical parameters. Let's say something like the diffusion model d2(F)/dM2= alpha. dF/dt
Does it make a sense when F is a pattern UN?

-2 I note only two kinds of physical models : those where the set of the measurements need to be sorted (like with the Boltzman levels of energy) and those who require a law group (so that a partial derivative can make sense, like with the diffusion model)

Is there any chance that the uniqueness of the solution of concatenation of the patterns (see image above) yields a sorting of interest in term of analog energy levels for a Boltzman model ?

henriette
Member

Posts: 362
Joined: 30 Oct 2007

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

Hmmm...

It seems you may have something like a systematic approach with this thing you call lexicographic order.
It looks like counting in base n while throwing out those which are equivalent by either rotation or color permutation.
Perhaps you even have some systematic way of determining the next element by some set of rules -- such as only being able to use digits when you have a next lower digit in a higher place (i.e. to the left). But perhaps you still have to eliminate based on your restriction to invariance with regards to rotation and color permutation and this order just makes it a little bit easier.

I only ask because your latest approach (restricted to n=6) seems to take this all for granted and there is no representation of the rotation and color permutation invariance.

P.S. For others trying to follow along... in henriette's new approach the bounding condition with t=0 and t=1 correspond to c=1 and c=n cases I mentioned earlier.

mitchellmckain
Member

Posts: 930
Joined: 27 Oct 2016

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

I thought to see if lexicographic order helped with my counting for n=2,3,4,5 and I see that I did get some wrong
n=2
00
01
n=3
000
001
012
n=4
0000
0001
0011
0012
0101
0102
0123
so the count for this one is 7 not 6.
n=5
00000
00001
00011
00012
00101
00102
00112
00121
00123
01001
01002
01012
01023
01234
so the count for this one is 14 rather than 13, which also reveals I miscounted for c=2 in the case of n=5 in my other post above -- should be 4 not 3.

I had a lot of difficulty with this for n=5, but the reason was probably just getting used to the different way of counting. But the lexicographic order does seem to reveal some patterns which help to reveal some of the equivalences which are easy to miss. For example, you can't have two of the same digit together unless you have two of a lower digit together to the left -- otherwise color permutation just takes you to a lower number which you would already have covered. Another rule would be you cannot have a digit unless you have the next lower digit to the left and you cannot have more of a digit than you have of some lower digit. I am certainly not saying these rules are enough, but they do help.

I am still not entirely confident with my counting so a confirmation would be nice.

mitchellmckain
Member

Posts: 930
Joined: 27 Oct 2016

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

You know....

If you are looking for a mathematical connection between this problem and another area of mathematics...

What this reminds me of most is topology. Looking for differences under a set of equivalences.

mitchellmckain
Member

Posts: 930
Joined: 27 Oct 2016

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

mitchellmckain » February 24th, 2018, 2:54 pm wrote:n=5
00000
00001
00011
00012
00101
00102
00112
00121
00123
01001
01002
01012
01023
01234
so the count for this one is 14 rather than 13, which also reveals I miscounted for c=2 in the case of n=5 in my other post above -- should be 4 not 3.

More mistakes found

01001 is equivalent to 00101 by rotation.
Ah! and that means
01002 is equivalent to 00102 by color permutation and rotation.

So the count I get for n=5 is 12 and the count for c=2 in the case of n=5 is 3 as I said originally.

mitchellmckain
Member

Posts: 930
Joined: 27 Oct 2016

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

Ah and I think I missed one
01021
I haven't found a permutation and rotation to show equivalence to any of the previous numbers. It was by thinking of this as a topology problem which helped me catch this one.

This brings the count back to 13, and thus I have the answers I first got with my own method (broken down by c, the number of colors in a necklace) and thus all my troubles have been with trying to use lexicographic order to solve the problem. I suppose this lexicographic order is a natural way for writing a computer algorithm for solving the problem despite the trouble I was having with it. If you wonder at my difficulty consider that the n=5 problem requires sifting through 3125 (5 to the fifth power) numbers and eliminating those which are equivalent, though a lot are eliminated rather quickly.

mitchellmckain
Member

Posts: 930
Joined: 27 Oct 2016

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

How about a more complete set of rules for counting in lexicographic order so that you eliminate the vast majority of numbers quickly.

1) All start with zero because you can always put a zero in this position by color permutation and rotation, and the result is obviously a lower number, which you should already have checked.
2) Never end in zero because a rotation will put this zero in the start (far left) position and this always give you a lower number.
3) Don't use a digit unless you have the next lower digit somewhere to the left. This is because you can easily get to this by color permutation to make it a lower number which you already considered.
4) Don't use more of a digit than you have already have of some lower digit. This is because you can invariably get a lower number by color permutation and rotation if you do this.
5) Don't put two or more of the same digit together unless you have the same number of a lower digit together to the left. Same reasoning applies for this.

After applying these rules to eliminate most of them you still have to check each one which is left to see if it is equivalent to others by rotation or color permutation. And perhaps those with more experience in this counting can add more rules to speed up the process.

mitchellmckain
Member

Posts: 930
Joined: 27 Oct 2016