| Hosted by CoCalc | Download
Kernel: SageMath 9.7

Cayley graphs of binary bent functions of dimension 8 and degree up to 3.

from os import path
load(path.join("..", "sage-code", "boolean_dimension_cayley_graph_classifications.py"))

Import the controls module so that the time for the following operations can be shown. Enable the display of time.

import boolean_cayley_graphs.cayley_graph_controls as controls controls.timing = True

Load all of the classifications for dimension 8, degree up to 3, based on "bent_function_extended_affine_representative_polynomials.sage". Set c to be the list of these classifications, starting from 1. c[0] is None.

The reason why the classifications are loaded here rather than just computed and saved is that each of these classifications takes about 24 hours to compute on an Intel Core i5 class PC.

c = load_boolean_dimension_cayley_graph_classifications(8, dir=path.join("..", "sobj"))

Display the length of c, the list of classifications.

len(c)
11

Verify that c[0] is None.

print(c[0])
None

for k from 1 to the end of c:

  • Print k;

  • Print the algebraic normal form of the bent function corresponding to c[k];

  • Produce a report on the classification c[k];

  • Produce a matrix plot of the weight_class_matrix;

  • Produce a matrix plot of bent_cayley_graph_index_matrix, the matrix of indices of extended Cayley classes within the extended translation class;

  • Produce a matrix plot of dual_cayley_graph_index_matrix, the matrix of indices of extended Cayley classes of dual bent functions within the extended translation class.

#sage_server.MAX_OUTPUT_MESSAGES = 10000 for k in range(1, len(c)): print("") print("Classification", k) print("") print(c[k].algebraic_normal_form) c[k].report() matrix_plot(c[k].weight_class_matrix, cmap='gist_stern', colorbar=True).show() matrix_plot(c[k].bent_cayley_graph_index_matrix, cmap='gist_stern', colorbar=True).show() matrix_plot(c[k].dual_cayley_graph_index_matrix, cmap='gist_stern', colorbar=True).show()
Classification 1 x0*x1 + x2*x3 + x4*x5 + x6*x7 Algebraic normal form of Boolean function: x0*x1 + x2*x3 + x4*x5 + x6*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals are the same: There are 2 extended Cayley classes in the extended translation class.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 2 x0*x1*x2 + x0*x3 + x1*x4 + x2*x5 + x6*x7 Algebraic normal form of Boolean function: x0*x1*x2 + x0*x3 + x1*x4 + x2*x5 + x6*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals are the same: There are 4 extended Cayley classes in the extended translation class.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 3 x0*x1*x2 + x0*x6 + x1*x3*x4 + x1*x5 + x2*x3 + x4*x7 Algebraic normal form of Boolean function: x0*x1*x2 + x0*x6 + x1*x3*x4 + x1*x5 + x2*x3 + x4*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals are the same: There are 6 extended Cayley classes in the extended translation class.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 4 x0*x1*x2 + x0*x2 + x0*x4 + x1*x3*x4 + x1*x5 + x2*x3 + x6*x7 Algebraic normal form of Boolean function: x0*x1*x2 + x0*x2 + x0*x4 + x1*x3*x4 + x1*x5 + x2*x3 + x6*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals are the same: There are 6 extended Cayley classes in the extended translation class.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 5 x0*x1*x2 + x0*x6 + x1*x3*x4 + x1*x4 + x1*x5 + x2*x3*x5 + x2*x4 + x3*x7 Algebraic normal form of Boolean function: x0*x1*x2 + x0*x6 + x1*x3*x4 + x1*x4 + x1*x5 + x2*x3*x5 + x2*x4 + x3*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals are the same: There are 9 extended Cayley classes in the extended translation class.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 6 x0*x1*x2 + x0*x2 + x0*x3 + x1*x3*x4 + x1*x6 + x2*x3*x5 + x2*x4 + x5*x7 Algebraic normal form of Boolean function: x0*x1*x2 + x0*x2 + x0*x3 + x1*x3*x4 + x1*x6 + x2*x3*x5 + x2*x4 + x5*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals are the same: There are 9 extended Cayley classes in the extended translation class.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 7 x0*x1*x2 + x0*x1 + x0*x2 + x0*x3 + x1*x3*x4 + x1*x4 + x1*x5 + x2*x3*x5 + x2*x4 + x6*x7 Algebraic normal form of Boolean function: x0*x1*x2 + x0*x1 + x0*x2 + x0*x3 + x1*x3*x4 + x1*x4 + x1*x5 + x2*x3*x5 + x2*x4 + x6*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals are the same: There are 6 extended Cayley classes in the extended translation class.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 8 x0*x1*x2 + x0*x5 + x1*x3*x4 + x1*x6 + x2*x3*x5 + x2*x4 + x3*x7 Algebraic normal form of Boolean function: x0*x1*x2 + x0*x5 + x1*x3*x4 + x1*x6 + x2*x3*x5 + x2*x4 + x3*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals are the same: There are 6 extended Cayley classes in the extended translation class.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 9 x0*x1*x6 + x0*x3 + x1*x4 + x2*x3*x6 + x2*x5 + x3*x4 + x4*x5*x6 + x6*x7 Algebraic normal form of Boolean function: x0*x1*x6 + x0*x3 + x1*x4 + x2*x3*x6 + x2*x5 + x3*x4 + x4*x5*x6 + x6*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals differ in matrices of indexes: There are 8 extended Cayley classes in the extended translation class. There are 8 extended Cayley classes of dual bent functions in the extended translation class, and 8 extended Cayley classes in the union of the two.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 10 x0*x1*x2 + x0*x3*x6 + x0*x4 + x0*x5 + x1*x3*x4 + x1*x6 + x2*x3*x5 + x2*x4 + x3*x7 Algebraic normal form of Boolean function: x0*x1*x2 + x0*x3*x6 + x0*x4 + x0*x5 + x1*x3*x4 + x1*x6 + x2*x3*x5 + x2*x4 + x3*x7 Function is bent. SDP design incidence structure t-design parameters: (True, (2, 256, 120, 56)) Classification of Cayley graphs and classification of Cayley graphs of duals differ in matrices of indexes: There are 10 extended Cayley classes in the extended translation class. There are 10 extended Cayley classes of dual bent functions in the extended translation class, and 10 extended Cayley classes in the union of the two.
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook

Now produce a reclassification r by seeing which extended Cayley classes are repeated between extended translation classes.

r = BooleanDimensionCayleyGraphReclassification(c)

Each entry in reclassification_table has as row 0, the "global" index of each extended Cayley class in the extended translation class.

Row 1 contains the local index of each extended Cayley class in the extended translation class, as given by the corresponding bent functions.

Row 2 contains the size of each extended Cayley class in the extended translation class, as given by the corresponding bent functions.

Row 3 contains the local index of each extended Cayley class in the extended translation class, as given by the Walsh Hadamard dual of each of the corresponding bent functions.

Row 4 contains the size of each extended Cayley class in the extended translation class, as given by the Walsh Hadamard dual of each of the corresponding bent functions.

We see that:

  • Extended Cayley class 0 occurs in both Extended Translation class 1 (34816 Cayley graphs) and Extended Translation class 2 (6144 Cayley graphs).

  • Extended Cayley class 1 occurs in both Extended Translation class 1 (30720 Cayley graphs) and Extended Translation class 2 (2048 Cayley graphs).

  • Extended Translation class 5 and Extended Translation class 6 have the same Extended Cayley classes (16 to 24) with the same number of members of each class.

for n in range(1, len(r.reclassification_table)): print(n) print(r.reclassification_table[n])
1 [ 0 1] [ 0 1] [34816 30720] [ 0 1] [34816 30720] 2 [ 0 2 3 1] [ 0 1 2 3] [ 6144 28672 28672 2048] [ 0 1 2 3] [ 6144 28672 28672 2048] 3 [ 4 5 6 7 8 9] [ 0 1 2 3 4 5] [ 6144 2048 16384 16384 12288 12288] [ 0 1 2 3 4 5] [ 6144 2048 16384 16384 12288 12288] 4 [ 10 11 12 13 14 15] [ 0 1 2 3 4 5] [15360 9216 16384 16384 5120 3072] [ 0 1 2 3 4 5] [15360 9216 16384 16384 5120 3072] 5 [ 16 17 18 19 20 21 22 23 24] [ 0 1 2 3 4 5 6 7 8] [ 4096 6144 6144 2048 2048 6144 6144 16384 16384] [ 0 1 2 3 4 5 6 7 8] [ 4096 6144 6144 2048 2048 6144 6144 16384 16384] 6 [ 16 17 18 23 24 19 21 22 20] [ 0 1 2 3 4 5 6 7 8] [ 4096 6144 6144 16384 16384 2048 6144 6144 2048] [ 0 1 2 3 4 5 6 7 8] [ 4096 6144 6144 16384 16384 2048 6144 6144 2048] 7 [ 25 26 27 28 29 30] [ 0 1 2 3 4 5] [ 6144 21504 21504 2048 7168 7168] [ 0 1 2 3 4 5] [ 6144 21504 21504 2048 7168 7168] 8 [ 31 32 33 34 35 36] [ 0 1 2 3 4 5] [ 6144 4096 4096 2048 24576 24576] [ 0 1 2 3 4 5] [ 6144 4096 4096 2048 24576 24576] 9 [ 37 38 39 40 41 42 43 44] [ 0 1 2 3 4 5 6 7] [9216 9216 7168 7168 8192 8192 8192 8192] [ 1 0 3 2 4 5 6 7] [9216 9216 7168 7168 8192 8192 8192 8192] 10 [ 45 46 47 48 49 50 51 52 53 54] [ 0 1 2 3 4 5 6 7 8 9] [2048 2048 7168 7168 7168 7168 8192 8192 8192 8192] [ 1 0 3 2 5 4 6 7 8 9] [2048 2048 7168 7168 7168 7168 8192 8192 8192 8192]

The list r.classification_list contains the classifications in c, but with each of the matrices bent_cayley_graph_index_matrix and dual_cayley_graph_index_matrix using the indices from row 0 of reclassification_table corresponding to each index from row 1 and row 3 respectively.

rc = r.classification_list for k in range(1, len(rc)): print("") print("Classification", k) print("") matrix_plot(rc[k].weight_class_matrix, cmap='gist_stern', colorbar=True).show() matrix_plot(rc[k].bent_cayley_graph_index_matrix, cmap='gist_stern', colorbar=True).show() matrix_plot(rc[k].dual_cayley_graph_index_matrix, cmap='gist_stern', colorbar=True).show()
Classification 1
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 2
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 3
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 4
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 5
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 6
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 7
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 8
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 9
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook
Classification 10
Image in a Jupyter notebookImage in a Jupyter notebookImage in a Jupyter notebook

Test to see if the bent functions corresponding to c[5] and c[6] are general linear equivalent

bf5 = BentFunction(c[5].algebraic_normal_form) bf6 = BentFunction(c[6].algebraic_normal_form) is_gle, mapping_matrix = bf5.is_linear_equivalent(bf6, certificate=True) print(is_gle)
True
print(mapping_matrix)
[1 0 0 1 1 1 0 0] [0 0 0 1 0 0 0 0] [0 0 1 0 0 0 0 0] [0 1 1 1 0 0 0 0] [0 0 0 1 1 0 0 0] [1 0 0 0 0 0 0 0] [1 0 1 0 0 1 0 1] [0 1 1 0 0 0 1 0]