Finding an involution with Sage

asked 2021-02-08 11:13:39 +0100

klaaa
691 ●4 ●17 ●41

updated 2021-02-08 11:14:37 +0100

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:

F is an involution, that is $F^2=id$.
F preserves the number.
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?

answered 2021-02-09 02:09:38 +0100

Max Alekseyev

6540 ●9 ●47 ●153

updated 2021-02-09 19:20:57 +0100

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 $A_1$ be the set of elements from LL1. Denote $A_2:=A\setminus A_1$, so that $A = A_1\sqcup A_2$.

Similarly, let $B$ be the set of elements from L2, and $B_1$ be the set of elements from LL2. Denote $B_2:=B\setminus B_1$, so that $B = B_1\sqcup B_2$.

For existence of $F$, it is necessary that $A_1\cap B_2=A_2\cap B_1=\emptyset$.

Let $C_1 := A_1 \cap B_1$ and $C_2 := A_2\cap B_2$. Then define $A_1^\star := A_1\setminus C_1$, $A_2^\star := A_2\setminus C_2$, $B_1^\star := B_1\setminus C_1$, $B_2^\star := B_2\setminus C_2$.

From the definition it follows that the sets $A_1^\star, A_2^\star, B_1^\star, B_2^\star, C_1, C_2$ are pairwise disjoint. Furthermore, $$A=A_1^\star \sqcup A_2^\star \sqcup C_1 \sqcup C_2,$$ $$B=B_1^\star \sqcup B_2^\star \sqcup C_1 \sqcup C_2.$$ The properties of $F$ imply that $F(A_1^\star)=B_1^\star$, $F(B_1^\star)=A_1^\star$, $F(A_2^\star)=B_2^\star$, $F(B_2^\star)=A_2^\star$, $F(C_1)=C_1$, and $F(C_2)=C_2$. ~~Other than that $F$ can be an arbitrary involution. In particular, we can take $F$ to be the identity on $C_1\cup C_2$.~~

UPDATE. Since we are given that $\left.F\right|_{A_1\cup B_1} = G$, we only need to define $F$ on $A_2\cup B_2 = A_2^\star \sqcup B_2^\star \sqcup C_2$. In particular, we can take $F$ to be the identity on $C_2$.

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

edit flag offensive delete 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 ( 2021-02-09 17:08:27 +0100 )edit

Indeed, I forgot about $G$. In fact, it simplifies things (e.g., we don't need $C_1$). 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 ( 2021-02-09 19:16:46 +0100 )edit

add a comment

Your Answer

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

Finding an involution with Sage

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Finding an involution with Sage edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Finding an involution with Sage