On Monday, 24 October 2016 01:45:10 UTC+11, David Joyner wrote:
>
>
> I haven't looked at your code but are you comparing the SRG associated
> to the Boolean bent function and the graph associated to the incidence
> matrix of that graph?
>
>
I don't understand your precise meaning here, so I will spell out exactly
what I have done.
Briefly, if f is a Boolean bent function f: Z_2^{dim} -> Z_2, with f(0)=0,
then, if Z_2^{dim} is given lexicographical ordering from 0 to 2^{dim}-1,
define the matrix M[i,j]=f(i \xor j).
The matrix M is the *adjacency* matrix of the Cayley graph of f, and is
simple because f(0) != 1. The following function takes the equivalent f : Z
-> Z_2 and produces the Cayley graph for a given dim.
def boolean_cayley_graph(dim, f):
v = 2 ** dim
result = Graph(v)
result.add_edges([(i,j) for i in xsrange(v) for j in xsrange(i) if f(i
^ j)])
return result
This is the graph that I am using for G1 in test_isomorphism.sage
A Boolean bent function can also generate a projective, two-weight linear
code. Again, we take lexicographic ordering of Z_2^{dim} and produce a
matrix M, but here the number of columns is the weight of f, i.e. the size
of the support of f,
the number of rows is 2^{dim}, and each entry M[x,j] = <x, {support}_j>
where support is a list corresponding to the support of f. This matrix M
generates the linear code. In fact, the elements of the code are the rows
of M.
def linear_code(self):
dim = self.nvariables()
v = 2 ** dim
f = self.extended_translate()
support = [y
for y in xsrange(n)
if f(y)==1]
M = matrix(GF(2), [[inner(x, y)
for y in support]
for x in xsrange(v)])
return LinearCode(M)
There is Sage function strongly_regular_from_two_
weight_code(), described at
http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/strongly_regular_db.html
"A strongly regular graph can be built from a two-weight projective code
with weights w1,w2 (assuming w1 < w2) by adding an edge between any two
codewords whose difference has weight w1."
The graph G2 that I am using in test_isomorphism.sage is thus
strongly_regular_from_two_weight_code(f.linear_code()).
The bent function f can have one of two weights. If m=dim/2, the weight of
f is either 2^{2m-1} - 2^{m-1} (weight class 0) or 2^{2m-1}+2^{m-1} (weight
class 1).
In all cases where m<4, it turns out that if f has weight class 0 then
f.cayley_graph() is isomorphic to f.strongly_regular_graph(), and if f has
weight class 0 then f.cayley_graph() is isomorphic to
f.strongly_regular_graph().complement().
For m=4, these isomorphisms are true for the bent functions in the extended
affine equivalence class of the bent function corresponding to each of the
first 8 polynomials listed below. For polynomials 9 and 10, there are
exceptions,
according to the canonical label algorithms as implemented in Sage.
def bent_function_extended_affine_representative_polynomials_dimension_8():
r"""
The Boolean polynomials p8[i] for from 1 to 10 are the representatives
of
the extended affine equivalence classes of bent functions in 8
variables,
with degree up to 3, as listed at 7.3 of Tokareva 2015,
with citation [167] to Hou 1998.
"""
R8.<x1,x2,x3,x4,x5,x6,x7,x8> = BooleanPolynomialRing(8)
p8 = [None]*11
p8[1] = x1*x2 + x3*x4 + x5*x6 + x7*x8
p8[2] = x1*x2*x3 + x1*x4 + x2*x5 + x3*x6 + x7*x8
p8[3] = x1*x2*x3 + x2*x4*x5 + x3*x4 + x2*x6 + x1*x7 + x5*x8
p8[4] = x1*x2*x3 + x2*x4*x5 + x1*x3 + x1*x5 + x2*x6 + x3*x4 + x7*x8
p8[5] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x3*x5 + x2*x6 + x2*x5 + x1*x7
+ x4*x8
p8[6] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x3*x5 + x1*x3 + x1*x4 + x2*x7
+ x6*x8
p8[7] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x3*x5 + x2*x6 + x2*x5 + x1*x2
+ x1*x3 + x1*x4 + x7*x8
p8[8] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x3*x5 + x1*x6 + x2*x7 + x4*x8
p8[9] = x1*x2*x7 + x3*x4*x7 + x5*x6*x7 + x1*x4 + x3*x6 + x2*x5 + x4*x5
+ x7*x8
p8[10] = x1*x2*x3 + x2*x4*x5 + x3*x4*x6 + x1*x4*x7 + x3*x5 + x2*x7 +
x1*x5 + x1*x6 + x4*x8
return p8
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
