Loading [MathJax]/jax/output/HTML-CSS/jax.js

First time here? Check out the FAQ!

Ask Your Question
2

Finding an involution with Sage

asked 4 years ago

klaaa gravatar image

updated 4 years ago

I have four lists L1,LL1 and L2, LL2 and a bijection G from LL1 to LL2. LL1 is a sublist of L1 and LL2 a sublist of L2. For example they look like this:

L1=[ [ [ 2, 2, 2, 1 ], 4 ], [ [ 3, 2, 2, 1 ], 3 ], [ [ 2, 3, 2, 1 ], 3 ], [ [ 3, 3, 2, 1 ], 3 ], [ [ 4, 3, 2, 1 ], 2 ] ]

LL1=[ [ [ 2, 2, 2, 1 ], 4 ], [ [ 3, 2, 2, 1 ], 3 ], [ [ 2, 3, 2, 1 ], 3 ], [ [ 4, 3, 2, 1 ], 2 ] ]

and

L2=[ [ [ 2, 2, 2, 1 ], 2 ], [ [ 3, 2, 2, 1 ], 3 ], [ [ 2, 3, 2, 1 ], 3 ], [ [ 3, 3, 2, 1 ], 3 ], [ [ 4, 3, 2, 1 ], 4 ] ]

LL2=[ [ [ 2, 2, 2, 1 ], 2 ], [ [ 3, 2, 2, 1 ], 3 ], [ [ 2, 3, 2, 1 ], 3 ], [ [ 4, 3, 2, 1 ], 4 ] ]

The bijection G looks like this:

[ [ [ [ 2, 2, 2, 1 ], 4 ], [ [ 4, 3, 2, 1 ], 4 ] ], [ [ [ 3, 2, 2, 1 ], 3 ], [ [ 2, 3, 2, 1 ], 3 ] ], [ [ [ 2, 3, 2, 1 ], 3 ], [ [ 3, 2, 2, 1 ], 3 ] ], 
[ [ [ 4, 3, 2, 1 ], 2 ], [ [ 2, 2, 2, 1 ], 2 ] ] ]

Thus an element in such a list is a tuple of the form [ [ 2, 2, 2, 1 ], 4 ] where [2,2,2,1] correponds to some algebraic object and the second entry is number. L1 and L2 will always have the same number of elements and LL1 and LL2 will have the same number of elements. The bijection G is given also as a list, where an entry such as

[ [ [ 2, 2, 2, 1 ], 4 ], [ [ 4, 3, 2, 1 ], 4 ] ]

means of course that G maps [ [ 2, 2, 2, 1 ], 4 ] to [ [ 4, 3, 2, 1 ], 4 ] .

Im searching for bijections F between L1 and L2 that satisfy the following three conditions:

  1. F is an involution, that is F2=id.

  2. F preserves the number.

  3. F restricted to LL1 maps to LL2 via the given involution G.

In the above example F is uniquely given as follows:

[ [ [ [ 2, 2, 2, 1 ], 4 ], [ [ 4, 3, 2, 1 ], 4 ] ], [ [ [ 3, 2, 2, 1 ], 3 ], [ [ 2, 3, 2, 1 ], 3 ] ], [ [ [ 2, 3, 2, 1 ], 3 ], [ [ 3, 2, 2, 1 ], 3 ] ], 
[ [ [ 4, 3, 2, 1 ], 2 ], [ [ 2, 2, 2, 1 ], 2 ] ],[ [ [ 3, 3, 2, 1 ], 3 ], [ [ 3, 3, 2, 1 ], 3 ] ] ]

Here is another example where the lists are larger:

L1=[ [ [ 2, 2, 2, 2, 1 ], 5 ], [ [ 3, 2, 2, 2, 1 ], 4 ], [ [ 2, 3, 2, 2, 1 ], 3 ], [ [ 3, 3, 2, 2, 1 ], 4 ], [ [ 4, 3, 2, 2, 1 ], 3 ], 
[ [ 2, 2, 3, 2, 1 ], 4 ], [ [ 3, 2, 3, 2, 1 ], 3 ], [ [ 2, 3, 3, 2, 1 ], 4 ], [ [ 3, 3, 3, 2, 1 ], 4 ], [ [ 4, 3, 3, 2, 1 ], 3 ], [ [ 2, 4, 3, 2, 1 ], 3 ], [ 
[ 3, 4, 3, 2, 1 ], 3 ], 
[ [ 4, 4, 3, 2, 1 ], 3 ], [ [ 5, 4, 3, 2, 1 ], 2 ] ]

LL1=[ [ [ 2, 2, 2, 2, 1 ], 5 ], [ [ 3, 2, 2, 2, 1 ], 4 ], [ [ 2, 3, 2, 2, 1 ], 3 ], [ [ 4, 3, 2, 2, 1 ], 3 ], [ [ 2, 2, 3, 2, 1 ], 4 ], 
[ [ 3, 2, 3, 2, 1 ], 3 ], [ [ 2, 4, 3, 2, 1 ], 3 ], [ [ 5, 4, 3, 2, 1 ], 2 ] ]

L2=[ [ [ 2, 2, 2, 2, 1 ], 2 ], [ [ 3, 2, 2, 2, 1 ], 3 ], [ [ 2, 3, 2, 2, 1 ], 3 ], [ [ 3, 3, 2, 2, 1 ], 3 ], [ [ 4, 3, 2, 2, 1 ], 4 ], 
[ [ 2, 2, 3, 2, 1 ], 3 ], [ [ 3, 2, 3, 2, 1 ], 3 ], [ [ 2, 3, 3, 2, 1 ], 3 ], [ [ 3, 3, 3, 2, 1 ], 3 ], [ [ 4, 3, 3, 2, 1 ], 4 ], [ [ 2, 4, 3, 2, 1 ], 4 ], [ 
[ 3, 4, 3, 2, 1 ], 4 ], 
[ [ 4, 4, 3, 2, 1 ], 4 ], [ [ 5, 4, 3, 2, 1 ], 5 ] ]

LL2=[ [ [ 2, 2, 2, 2, 1 ], 2 ], [ [ 3, 2, 2, 2, 1 ], 3 ], [ [ 2, 3, 2, 2, 1 ], 3 ], [ [ 4, 3, 2, 2, 1 ], 4 ], [ [ 2, 2, 3, 2, 1 ], 3 ], 
[ [ 3, 2, 3, 2, 1 ], 3 ], [ [ 2, 4, 3, 2, 1 ], 4 ], [ [ 5, 4, 3, 2, 1 ], 5 ] ]


G=[ [ [ [ 2, 2, 2, 2, 1 ], 5 ], [ [ 5, 4, 3, 2, 1 ], 5 ] ], [ [ [ 3, 2, 2, 2, 1 ], 4 ], [ [ 2, 4, 3, 2, 1 ], 4 ] ], [ [ [ 2, 3, 2, 2, 1 ], 3 ], [ [ 3, 2, 3, 
2, 1 ], 3 ] ], 
[ [ [ 4, 3, 2, 2, 1 ], 3 ], [ [ 2, 2, 3, 2, 1 ], 3 ] ], [ [ [ 2, 2, 3, 2, 1 ], 4 ], [ [ 4, 3, 2, 2, 1 ], 4 ] ], [ [ [ 3, 2, 3, 2, 1 ], 3 ], [ [ 2, 3, 2, 2, 1 
], 3 ] ], 
[ [ [ 2, 4, 3, 2, 1 ], 3 ], [ [ 3, 2, 2, 2, 1 ], 3 ] ], [ [ [ 5, 4, 3, 2, 1 ], 2 ], [ [ 2, 2, 2, 2, 1 ], 2 ] ] ]

There might be many F satisfying the three conditions.

Thus my question: Is there an easy method to find all such bijections F satisfying the three conditions when L1,LL1,L2,LL2 and G are given?

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
1

answered 4 years ago

Max Alekseyev gravatar image

updated 4 years ago

Since F must preserve the number, it's worth to decompose the problem into smaller subproblems, where the number is fixed. E.g., in the first example, you'd have 3 subproblems with number being 2, 3, and 4, respectively.

Let's consider such a subproblem, where the number is fixed.

Let A be a set of elements from L1, and A1 be the set of elements from LL1. Denote A2:=AA1, so that A=A1A2.

Similarly, let B be the set of elements from L2, and B1 be the set of elements from LL2. Denote B2:=BB1, so that B=B1B2.

For existence of F, it is necessary that A1B2=A2B1=.

Let C1:=A1B1 and C2:=A2B2. Then define A1:=A1C1, A2:=A2C2, B1:=B1C1, B2:=B2C2.

From the definition it follows that the sets A1,A2,B1,B2,C1,C2 are pairwise disjoint. Furthermore, A=A1A2C1C2, B=B1B2C1C2. The properties of F imply that F(A1)=B1, F(B1)=A1, F(A2)=B2, F(B2)=A2, F(C1)=C1, and F(C2)=C2. Other than that F can be an arbitrary involution. In particular, we can take F to be the identity on C1C2.

UPDATE. Since we are given that F|A1B1=G, we only need to define F on A2B2=A2B2C2. In particular, we can take F to be the identity on C2.

From this consideration, it's easy to construct a particular F.


Here us a sample code:

def construct_F_fixed_num( L1, LL1, L2, LL2, num ):
    A = { tuple(q) for q,n in L1 if n==num }
    A1 = { tuple(q) for q,n in LL1 if n==num }
    A2 = A - A1

    B = { tuple(q) for q,n in L2 if n==num }
    B1 = { tuple(q) for q,n in LL2 if n==num }
    B2 = B - B1

    assert len(A1 & B2) == 0
    assert len(A2 & B1) == 0

    #C1 = A1 & B1
    C2 = A2 & B2

    #A1s = A1 - C1
    A2s = A2 - C2

    #B1s = B1 - C1
    B2s = B2 - C2

    #assert len(A1s) == len(B1s)
    assert len(A2s) == len(B2s)

    # conversion for output
    A2l = [[list(q),num] for q in A2s]
    B2l = [[list(q),num] for q in B2s]
    C2l = [[list(q),num] for q in C2]

    return [list(t) for t in zip(C2l,C2l)] +  [list(t) for t in zip(A2l,B2l)]

def construct_F( L1, LL1, L2, LL2, G ):
    N = { n for _,n in L1+L2 }
    return sum( [construct_F_fixed_num( L1, LL1, L2, LL2, n ) for n in N], G )

Running construct_F( L1, LL1, L2, LL2, G ) on the lists from your first example returns:

[[[[2, 2, 2, 1], 4], [[4, 3, 2, 1], 4]],
 [[[3, 2, 2, 1], 3], [[2, 3, 2, 1], 3]],
 [[[2, 3, 2, 1], 3], [[3, 2, 2, 1], 3]],
 [[[4, 3, 2, 1], 2], [[2, 2, 2, 1], 2]],
 [[[3, 3, 2, 1], 3], [[3, 3, 2, 1], 3]]]

As for the number of different involutions F, it equals |A2|!ι(|C2|), where ι() is the involution number given by OEIS A000085. The factor |A2|! accounts for bijections between on A2 and B2, while ι(|C2|) accounts for involutions on C2.

Preview: (hide)
link

Comments

Thank you very much! It seems your code is not using the involution G (at least as an input). By property 3. F needs to have the property that restricted to the map LL1->LL2 it is equal to the involution G. Or do I have a thinking error? Also is there a way to obtain all F which have properties 1, 2 and 3 and count the number of such involutions? By the way, is there an easy method with sage to turn every bracket of the form ( into a bracket of the form [ in your output?

klaaa gravatar imageklaaa ( 4 years ago )

Indeed, I forgot about G. In fact, it simplifies things (e.g., we don't need C1). I've updated my answer accordingly and added a formula for the number of different F's. It now returns an answer in the requested format. In general, () and [] in Python denote tuples and lists, which are immutable and mutable objects, respectively. We cannot have lists (or any other mutable objects) as elements of sets, and so I need to convert them to tuples before forming sets, but now I covert them back to lists for output in the requested format.

P.S. Given L1, LL1, L2, LL2, G are in fact unordered objects and viewed more naturally as sets not lists (as explained in my answer). I would recommend to employ other data types, such as tuples/sets/dicts, for better representation of your data.

Max Alekseyev gravatar imageMax Alekseyev ( 4 years ago )

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 4 years ago

Seen: 315 times

Last updated: Feb 09 '21