group-action 0.2.18
A Python package for group action.
Requires Python: >=3.10

## QUESTION
When you have to design a standard cell library, you need to choose a number of combinatorial cells.
You can simply ask a friend and start from an existing list or build your own from scratch.
But how? More specifically, how many n-input Boolean functions are there?

This latter question connects to the mathematical concept of group action that is a pivotal part of Algebra.
If you like Rubyk's cube, you should not feel too uncomfortable.

It can be reformulated in this context as follows.
What are the orbits in the action of the symmetric group $S_n$ on the set of n-input Boolean functions $X_n=B^{B^n}$?

## DESCRIPTION
The name of this package is **group_action**.

The version of this package is **0.2.18**.

It contains a library module named **library** and several applications : **orbit**, **orbit_random**, **orbits**, **conjugacy_classes**, **burnside**, **powerset**, and **symmetric_functions**.

**orbit** computes the orbit of a function specified through its number of inputs and signature generated by the natural action of Sn on Xn.

**orbit_random** computes the orbit of a random function specified through its number of inputs generated by the natural action of Sn on Xn.

**orbits** computes the orbits in the natural action of the symmetric group $S_n$ on the set of n-input Boolean functions $X_n=B^{B^n}$.

The result is basically a list of signatures that is presented in 2 formats and 2 levels of details.

Here, a **signature** is a non negative integer representing a Boolean function.

When the problem becomes too big you might consider using the following commands to get the number of orbits.

**conjugacy_classes** computes the conjugacy classes of the symmetric group $S_n$.

**burnside** computes the Burnside's formula for a given number of inputs $n$ and the number of orbits generated by the action of $S_n$ on $X_n$.

**powerset** computes the orbits generated by the natural action of the symmetric group $S_n$ on the set of n-input Boolean functions $X_n=B^{B^n}$ using the power set method.

**symmetric_functions** computes the signatures of the symmetric Boolean functions with n inputs and 1 output.

For instance, what 2-input Boolean function does 12 represent?
I use Big Endian format for binary words.
12 = 0101
This gives the following truth table
```
x0 x1 f(x0, x1)
0  0  0
1  0  1
0  1  0
1  1  1
```
and the following expression
f(x0, x1) = x0 & ~x1 | x0 & x1 = x0

Note: x1 does not figure in this expression.

So 12 represents a 1-input Boolean function.
It gives a standard cell called a **buffer**.

To move forward, is 12 the only signature representing a buffer cell?
Actually this answer is no!
If you permut x0 and x1, you get the following truth table.
```
x0 x1 f(x0, x1)
0  0  0
1  0  0
0  1  1
1  1  1
```
It corresponds to f(x0, x1) = ~x0 & x1 | x0 & x1 = x1, another instance of the buffer cell.

This is what the group action concept is all about, and behyond :-)

## HOW DOES IT WORK?

### orbits
Each permutation of $S_n$ is applied to each n-input Boolean function f of $X_n$, computing a new n-input Boolean function g.
These computations are gathered into chunks and run in parallel on a number of cores.

Each pair $\lbrace f, g \rbrace$ forms an edge of a graph that is latter analyzed.
The orbits we are looking for are the connected parts of the obtained graph.

From this analysis, one can get the number of orbits, a list of representatives, and the detailed contents of each orbit.
Boolean functions are represented by their signatures as non negative integers.

The results are printed out to the screen or stored into a json file named **data.json**.
Binary data is considered as Big Endian throughout the code.

### conjugacy_classes
Same as **orbits** but the symmetric group $S_n$ acts on itself and action looks like this : $g.x = gxg^{-1}$.

### burnside
Here the orbits are not populated like for both the previous commands, as the level of complexity grows and becomes untractable.
**burnside** command builds the formula as a string upon two facts.
1. Conjugated permutations give the same number of fixed points.
2. The action of $S_n$ on $B^n$ allows to derive the number of fixed functions for a given permutation.
Then the formula is evaluated.
Special attention to very long integers has to be payed.

### powerset
Same as orbits and burside but with ultimate performances.

### orbit
Here a single orbit is computed associated to a signature given as an input.

### orbit_random
Same as orbit but a random signature is provided.

### symmetric_functions
Compute the signatures of the symmetric functions for a given number of inputs.

## INSTALL
Run ```pip install group_action```.

### On Ubuntu
The commands named **orbit**, **orbit_random**, **orbits**, **conjugacy_classes**, **burnside**, **powerset**, and **symmetric_functions** are automatically installed under $HOME/.local/bin under Ubuntu 22.04 when you install the package.

Make sure your path is updated with $HOME/.local/bin.
Check the following [link](https://askubuntu.com/questions/1144231/home-local-bin-not-in-path-for-ubuntu-19-04) for more information. 

You are ready to go :-)

## USAGE
```
usage: orbit [-h] [--version] [--s S] [--n N] [--c C]

Computation of the orbit of a n-input, 1-output Boolean function specified via its signature as a LE integer under the
action of the symmetric group Sn via its transpositions.

options:
  -h, --help  show this help message and exit
  --version   show program's version number and exit
  --s S       Signature
  --n N       Number of inputs
  --c C       Number of cores
```

```
usage: orbit_random [-h] [--version] [--i I] [--n N] [--c C]

Iterate on computation of the orbit of a n-input, 1-output Boolean function specified via a random signature as a LE
integer under the action of the symmetric group Sn via its transpositions.

options:
  -h, --help  show this help message and exit
  --version   show program's version number and exit
  --i I       iterations
  --n N       Number of inputs
  --c C       Number of cores
```

```
orbits [-h] [--version] [--n N] [--c C] [--r] [--v] [--j]

Brut force computation of orbits of n-input 1-output Boolean functions under the action of the symmetric group Sn.

options:
  -h, --help  show this help message and exit
  --version   show program's version number and exit
  --n N       Number of inputs
  --c C       Number of cores
  --v         Output every element of each orbit
  --j         Output data.json file
```

```
usage: conjugacy_classes [-h] [--n N] [--c C] [--v] [--j]

Brut force computation of conjugacy classes of the symmetric group Sn.

options:
  -h, --help  show this help message and exit
  --version   show program's version number and exit
  --n N       Number of elements in S
  --c C       Number of cores
  --v         Output every element of each orbit
  --j         Output data.json file
```

```
usage: burnside [-h] [--n N] [--c C]

Build Burnside's formula and compute the number of orbits generated by the action of the symmetric group Sn on the set of n-input Boolean
functions B^{B^n}

options:
  -h, --help  show this help message and exit
  --version   show program's version number and exit
  --n N       Number of inputs
  --c C       Number of cores
```

```
usage: powerset [-h] [--version] [--n N] [--c C] [--v] [--j]

Computation of the orbits generated by the action of the symmetric group Sn via its transpositions on n-input Boolean functions generated by actions on power sets.

options:
  -h, --help  show this help message and exit
  --version   show program's version number and exit
  --n N       Number of inputs
  --c C       Number of cores
  --v         Output every element of each orbit
  --j         Output data.json file
```

```
usage: symmetric_functions [-h] [--version] [--n N]

Generate each symmetric n-input 1-output Boolean function.

options:
  -h, --help  show this help message and exit
  --version   show program's version number and exit
  --n N       Number of inputs
```
## EXAMPLES
After the installation, run ```orbits --n 3 --c 12``` in order to run on 12 cores and to get the number of orbits and a representative of each orbit as an integer signature for 3-input, 1-output Boolean functions.
Activate the verbose mode running ```orbits --n 3 --c 12 --v``` in order to get the orbits populated.

## TEST
```
n=0      2 orbits
n=1      4 orbits
n=2     12 orbits
n=3     80 orbits
n=4  3 984 orbits
```

## KNOWN BUGS AND LIMITATIONS
1. The group action is concrete and set up to $G=S_n$ and $X=B^{B^n}$ in this version.
2. The packaging is managed through PyPI, not yet synchronized to GitHub.
3. The length of the integer strings used to represent the signatures is limited to 8 192 characters.

## FEEDBACK
Any comment and/or improvement whether on optimization, packaging, documentation, or on any other appropriate topic is welcome :-)

## CONTACT
You can reach me by email: antoine AT sirianni DOT ai.
I'll do my best to provide you with support.

Check [ORConf 2024 presentation video](https://www.youtube.com/watch?v=cpYvwZsMajM) on Open Source Standard Cell Library Design to get to know me.

## DOCUMENTATION
Check [ORConf 2024 presentation slides](https://drive.google.com/file/d/1MqquCYTonRa8ladpjQhkc7wXzL7EGqIk/view) on Open Source Standard Cell Library Design.
Type ```pydoc -w group_action.library``` to generate the HTML documentation of the library module.