Categories

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

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

G=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.

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)]

## By Ashani Dasgupta

Pursuing Ph.D. in Geometric Group Theory at University of Wisconsin, Milwaukee