Classification of boolean functions within an extended translation class

The boolean_function_extended_translate_classification module defines:

  • the BooleanFunctionExtendedTranslateClassification class; which represents the classification of the general linear classes within the extended translation class of a boolean function; and

  • the BooleanFunctionExtendedTranslateClassPart class, which represents part of an extended translate classification.

AUTHORS:

  • Paul Leopardi (2023-01-26): initial version

EXAMPLES:

The classification of the boolean function defined by the polynomial x2 + x1*x2.

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: from boolean_cayley_graphs.boolean_function_extended_translate_classification import (
....:     BooleanFunctionExtendedTranslateClassification as BooleanFunctionETC)
sage: R2.<x1,x2> = BooleanPolynomialRing(2)
sage: p = x2+x1*x2
sage: f = BooleanFunctionImproved(p)
sage: c = BooleanFunctionETC.from_function(f)
sage: dict(sorted(c.__dict__.items()))
{'algebraic_normal_form': x0*x1 + x1,
 'boolean_function_index_matrix': [0 2 1 3]
 [1 3 0 2]
 [2 0 3 1]
 [3 1 2 0],
 'boolean_function_list': [Boolean function with 2 variables,
  Boolean function with 2 variables,
  Boolean function with 2 variables,
  Boolean function with 2 variables],
 'general_linear_class_index_matrix': [0 0 1 0]
 [1 0 0 0]
 [0 0 0 1]
 [0 1 0 0],
 'general_linear_class_list': [Boolean function with 2 variables,
  Boolean function with 2 variables]}

REFERENCES:

The extended translation equivalence class and the general linear equivalence class of a boolean function are defined by Leopardi [Leo2017].

class boolean_cayley_graphs.boolean_function_extended_translate_classification.BooleanFunctionExtendedTranslateClassPart(*args, **kwargs)[source]

Bases: sage.structure.sage_object.SageObject, boolean_cayley_graphs.saveable.Saveable

Partial classification of the general linear classes within the extended translation equivalence class of a boolean function.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: from boolean_cayley_graphs.boolean_function_extended_translate_classification import (
....:     BooleanFunctionExtendedTranslateClassPart as BooleanFunctionETCPart)
sage: R2.<x1,x2> = BooleanPolynomialRing(2)
sage: p = x1+x2+x1*x2
sage: f = BooleanFunctionImproved(p)
sage: c1 = BooleanFunctionETCPart.from_function(f, c_stop=1)
sage: print(c1)
BooleanFunctionExtendedTranslateClassPart.from_function(BooleanFunctionImproved(x0*x1 + x0 + x1, c_start=0, c_stop=1))
sage: latex(c1)
\text{\texttt{BooleanFunctionExtendedTranslateClassPart.from{\char`\_}function(BooleanFunctionImproved(x0*x1{ }+{ }x0{ }+{ }x1,{ }c{\char`\_}start=0,{ }c{\char`\_}stop=1))}}
classmethod from_function(boolf, c_start=0, c_stop=None, limited_memory=False)[source]

Constructor from the BooleanFunction boolf.

INPUT:

  • boolf – an object of class BooleanFunction.

  • c_start – integer (default: 0). The smallest value of c to use for extended translates.

  • c_stop – integer (default: None). One more than largest value of c to use for extended translates. None means use all remaining values.

  • limited_memory – boolean (default: False). A flag indicating whether the classification might be too large to fit into memory.

OUTPUT:

An object of class BooleanFunctionExtendedTranslateClassPart, initialized as follows.

  • algebraic_normal_form is set to boolf.algebraic_normal_form(),

  • boolean_function_index_matrix – a Matrix` of integers, which are indices into ``boolean_function_list representing the distinct boolean functions.

  • boolean_function_list – a list of boolean functions.

  • general_linear_class_index_matrix – a Matrix` of integers, which are indices into ``general_linear_class_list representing the general linear equivalence classes.

  • general_linear_class_list – a list of matrices representing the general linear equivalence classes.

  • c_start is set to smallest value of c used for extended translates.

Each entry boolean_function_index_matrix[c-c_start,b] corresponds to the boolean function \(x \mapsto \mathtt{boolf}(x+b) + \langle c, x \rangle + \mathtt{boolf}(b)\). This enumerates all of the extended translates of boolf having c from c_start to but not including c_stop.

EXAMPLES:

A partial classification of the boolean function defined by the polynomial \(x_1 + x_2 + x_1 x_2\).

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: from boolean_cayley_graphs.boolean_function_extended_translate_classification import (
....:     BooleanFunctionExtendedTranslateClassPart as BooleanFunctionETCPart)
sage: R2.<x1,x2> = BooleanPolynomialRing(2)
sage: p = x1+x2+x1*x2
sage: f = BooleanFunctionImproved(p)
sage: c1 = BooleanFunctionETCPart.from_function(f,c_start=2,c_stop=4)
sage: dict(sorted(c1.__dict__.items()))
{'algebraic_normal_form': x0*x1 + x0 + x1,
 'boolean_function_index_matrix': [0 2 1 3]
 [1 3 0 2],
 'boolean_function_list': [Boolean function with 2 variables,
  Boolean function with 2 variables,
  Boolean function with 2 variables,
  Boolean function with 2 variables],
 'c_start': 2,
 'general_linear_class_index_matrix': [0 1 0 0]
 [0 0 0 1],
 'general_linear_class_list': [Boolean function with 2 variables,
  Boolean function with 2 variables]}
class boolean_cayley_graphs.boolean_function_extended_translate_classification.BooleanFunctionExtendedTranslateClassification(*args, **kwargs)[source]

Bases: boolean_cayley_graphs.boolean_function_extended_translate_classification.BooleanFunctionExtendedTranslateClassPart

Classification of the Cayley graphs within the extended translation equivalence class of a boolean function.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: from boolean_cayley_graphs.boolean_function_extended_translate_classification import (
....:     BooleanFunctionExtendedTranslateClassification as BooleanFunctionETC)
sage: R2.<x1,x2> = BooleanPolynomialRing(2)
sage: p = x1+x2+x1*x2
sage: f = BooleanFunctionImproved(p)
sage: c1 = BooleanFunctionETC.from_function(f)
sage: print(c1)
BooleanFunctionExtendedTranslateClassification.from_function(BooleanFunctionImproved(x0*x1 + x0 + x1))
sage: latex(c1)
\text{\texttt{BooleanFunctionExtendedTranslateClassification.from{\char`\_}function(BooleanFunctionImproved(x0*x1{ }+{ }x0{ }+{ }x1))}}
bent_function_csv_suffix = '_bent_function.csv'
cg_class_list_csv_suffix = '_cg_class_list.csv'
classmethod from_function(boolf, list_dual_graphs=True, limited_memory=False)[source]

Constructor from the BooleanFunctionImproved boolf.

INPUT:

  • boolf – an object of class BooleanFunctionImproved.

  • list_dual_graphs – boolean. a flag indicating whether to list dual graphs.

  • limited_memory – boolean. A flag indicating whether the classification might be too large to fit into memory. Default is False.

OUTPUT:

An object of class BooleanFunctionExtendedTranslateClassification, initialized as follows.

  • algebraic_normal_form is set to boolf.algebraic_normal_form(),

  • boolean_function_index_matrix – a Matrix` of integers, which are indices into ``boolean_function_list representing the distinct boolean functions.

  • boolean_function_list – a list of boolean functions.

  • general_linear_class_index_matrix – a Matrix` of integers, which are indices into ``general_linear_class_list representing the general linear equivalence classes.

  • general_linear_class_list – a list of matrices representing the general linear equivalence classes.

Each entry boolean_function_index_matrix[c,b] corresponds to the Cayley graph of the boolean function \(x \mapsto \mathtt{boolf}(x+b) + \langle c, x \rangle + \mathtt{boolf}(b)\). This enumerates all of the extended translates of boolf.

EXAMPLES:

The classification of the boolean function defined by the polynomial \(x_1 + x_2 + x_1 x_2\).

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: from boolean_cayley_graphs.boolean_function_extended_translate_classification import (
....:     BooleanFunctionExtendedTranslateClassification as BooleanFunctionETC)
sage: R2.<x1,x2> = BooleanPolynomialRing(2)
sage: p = x1+x2+x1*x2
sage: f = BooleanFunctionImproved(p)
sage: c3 = BooleanFunctionETC.from_function(f)
sage: dict(sorted(c3.__dict__.items()))
{'algebraic_normal_form': x0*x1 + x0 + x1,
 'boolean_function_index_matrix': [0 2 1 3]
 [1 3 0 2]
 [2 0 3 1]
 [3 1 2 0],
 'boolean_function_list': [Boolean function with 2 variables,
  Boolean function with 2 variables,
  Boolean function with 2 variables,
  Boolean function with 2 variables],
 'general_linear_class_index_matrix': [0 1 1 1]
 [1 1 0 1]
 [1 0 1 1]
 [1 1 1 0],
 'general_linear_class_list': [Boolean function with 2 variables,
  Boolean function with 2 variables]}

TESTS:

The classification of the boolean function defined by the polynomial \(x_1 + x_2 + x_1 x_2\), but with list_dual_graphs=False.

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: from boolean_cayley_graphs.boolean_function_extended_translate_classification import (
....:     BooleanFunctionExtendedTranslateClassification as BooleanFunctionETC)
sage: R2.<x1,x2> = BooleanPolynomialRing(2)
sage: p = x1+x2+x1*x2
sage: f = BooleanFunctionImproved(p)
sage: c4 = BooleanFunctionETC.from_function(f,list_dual_graphs=False)
sage: dict(sorted(c4.__dict__.items()))
{'algebraic_normal_form': x0*x1 + x0 + x1,
 'boolean_function_index_matrix': [0 2 1 3]
 [1 3 0 2]
 [2 0 3 1]
 [3 1 2 0],
 'boolean_function_list': [Boolean function with 2 variables,
  Boolean function with 2 variables,
  Boolean function with 2 variables,
  Boolean function with 2 variables],
 'general_linear_class_index_matrix': [0 1 1 1]
 [1 1 0 1]
 [1 0 1 1]
 [1 1 1 0],
 'general_linear_class_list': [Boolean function with 2 variables,
  Boolean function with 2 variables]}
matrices_csv_suffix = '_matrices.csv'