A SAGE experiment on Nested Approximate Subgroups

(this is a continuing write-up mostly for personal records)

Spoiler

Before you read on, here is what I have found curious so far (this section is constantly changing):

  • A little computation reveals that though group action conjugation preserves most elements of a subgroups in majority of cases, there exists some subgroups of S_4 which are ill mannered.
  • Ill -Mannered Subgroups when conjugated with non members, have exactly 33% of the elements common with the conjugated set
    • example: [(), (1,3), (1,3,4), (3,4), (1,4,3), (1,4)] is an ill mannered subgroup.

Section 0

This concerns a computational experiment (in SAGE platform) inspired by an article by Terence Tao on Nested Approximate Subgroup. 

To learn more about SAGE please visit this link.

Pre-requisites

  • A preliminary knowledge on group theory (ref: Topics in Algebra by Herstein)
  • Basics of mathematical programming (it is useful to have an exposure to Python or C).
  • Tao’s article

Section 1

Conjugation and Preservation

The basic question is very simple. Suppose A is a subgroup of a group B (both finite). Say the index of A in B i.e. [B:A] = K. Hence we will get K disjoint cosets of A that partitions B.

Suppose s_1 A, s_2 A ,... , s_k A be the K cosets. Let S = {s_1 , ... , s_k } Then we may write B = SA.

What happens if an arbitrary element s acts (via conjugation) on subgroup A. That is if A = \{ a_1 , a_2 , ... , a_n \} and A^s = sAs^{-1} = \{ s a_1 s^{-1} , s a_2 s^{-1} , ... , s a_n a^{-1} \}  then how different is  A and A^s ?

If A is normal in B then ofcourse A = A^s  (by definition of normal subgroup)

However if A is not normal then? Turns out that the group action ‘approximately’ preserves A (I am deliberately using of some Terence Tao’s remarks here).

Here we take a pause and create the first set of computation. We examine S_4 that is 24 elements, compute it’s subgroups and identify normal subgroups. Next we focus on the non normal subgroups and make elements of S_4 We  conjugation on them. Finally we will compare how different the conjugated sets are from actual subgroups.

We use this little program to:

1. Compute all subgroups of S_4
2. Compute their conjugated cosets (with each element of the main group)
3. Compute intersection of the coset with the corresponding subgroup.
4. Find the ratio of length of this intersection with the length of the subgroup

Program

Screen Shot 2015-06-06 at 10.31.16 PMG=SymmetricGroup(4)
G1=G.list()
mag=[]
sub=[]
sub.append(G1)
for k in range(0,23):
for r in range (0,23):
if (k<r): H=G.subgroup([G[k], G[r]]) H1=H.list() z=set(H1) length=[] for x in range(0,len(sub)): y=set(sub[x]) m = y.symmetric_difference(z) n= list(set(m)) t = len(n) length.append(t) lengthmin = min(length) if(lengthmin>0):
sub.append(H1)
print “The subgroup H is”
print H1
print “\n”
coset=[]
for p in G1:
b=p
d=p**(-1)
for a in H1:
e=(b*a)*d
coset.append(e)
print “The coset %s H %s is” %(b,d)
print coset
print “\n”
intcoset = list(set(H1) & set(coset))
num = float(float(len(intcoset))/float(len(H1)))
print num
mag.append(num)
coset = []
print len(sub)
print mag

Result:

[1.0, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.25, 1.0, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.5, 1.0, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 0.25, 1.0, 1.0, 1.0, 0.25, 0.25, 1.0, 1.0, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 1.0, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 1.0, 0.5, 0.5, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 1.0, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 1.0, 1.0, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 1.0, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.5, 1.0, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 1.0, 0.5, 0.5, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.25, 1.0, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 0.25, 1.0, 1.0, 1.0, 0.25, 0.25]

Remark:

The value ‘1.0’ says the conjugated set is exactly same as corresponding subgroup. 0.25 indicates that one fourth of the values of the coset match the original subgroup.

As far as S_4 is concerned, a glance at the values reveal [A : A \cap A^s ] \ge 3 for large majority of values.

Notice apart from the trivial subgroup consisting of identity element, we have considered all remaining 29 subgroups (including the three other normal subgroups). For each of those 29 subgroups we have computed 24 conjugated subgroups, with respect to each of the 24 elements of S_4 . Thus we found 29 \times 24 = 696 conjugated subgroups.

Next we found the intersection set of each of 24 conjugations with corresponding subgroups, and found the ratio of order of intersection with order of subgroup.

Among the 696 values thus found, maximum value is obviously 1 (when, conjugated subgroup is same as original subgroup). Since A_4, V_4 , S_4 are normal in $S_4$, they will generate 72 one. Among remaining 624 values, it turns out that 240 values are less than or equal to 0.33.

So for about 60% of the cases (of non -normal subgroups), A and A^s have exactly half or all the elements in common.

One may be interested in those subgroups which are different that is whose conjugations have less than 33% element in common. Question is are those 0.33 or 0.25 values distributed all over the values generated? Actually not. They come in chunks. Then definitely there are some subgroups for which the values falls below 33%

Section 2

The Ill mannered Conjugates

So are there some subgroups whose cojugate subgroups are ill mannered? Turns out that for S_4 there are. We revised the code found in our program to find out how each subgroup is behaving. Here is the revised code.

Screen Shot 2015-06-07 at 5.56.14 PM

Screen Shot 2015-06-07 at 5.56.42 PM

The result is interesting:

  • Some subgroups ill-mannered. That is they have either at most 33% common or they are exactly equal with ALL their conjugated subgroups.
  • Ill mannered Subgroups are also consistent in their behavior. They have exactly two behaviors
    • Exactly 33% common with their conjugated subgroup (mostly this)
    • Or 100% common (only with elements belonging to this subgroup)

Examples of Ill Mannered Subgroups of S_4

[(), (1,3,4), (1,4,3)]

[(), (1,3,4), (1,4,3)]

[(), (1,4,2), (1,2,4)]

[(), (1,3,2), (1,2,3)]

[(), (1,2), (1,4,2), (2,4), (1,2,4), (1,4)]

[(), (1,2), (1,3,2), (1,3), (1,2,3), (2,3)]

[(), (1,3), (1,3,4), (3,4), (1,4,3), (1,4)]

[(), (3,4), (2,3,4), (2,4,3), (2,4), (2,3)]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s