CoCalc -- boolean_linear_code

Path: Boolean-Cayley-graphs / boolean_cayley_graphs / boolean_linear_code_graph.py
Views: ¹⁹²⁰⁴
1
r"""
2
Boolean linear code graphs
3
==========================
4

5
The ``boolean_linear_code_graph`` module defines the functions:
6

7
 * ``boolean_linear_code_graph``,
8
   which returns the graph corresponding to the linear code of a bent Boolean function; and
9
 * ``strongly_regular_from_code_gens``,
10
   which returns the strongly regular graph corresponding to a list of generators
11
   of projective two-weight codes.
12

13
AUTHORS:
14

15
- Paul Leopardi (2016-08-21): initial version
16

17
"""
18

19
#*****************************************************************************
20
#       Copyright (C) 2016-2017 Paul Leopardi [email protected]
21
#
22
#  Distributed under the terms of the GNU General Public License (GPL)
23
#  as published by the Free Software Foundation; either version 2 of
24
#  the License, or (at your option) any later version.
25
#                  http://www.gnu.org/licenses/
26
#*****************************************************************************
27

28
from sage.graphs.strongly_regular_db import strongly_regular_from_two_weight_code
29

30
from boolean_cayley_graphs.boolean_linear_code import boolean_linear_code
31
from boolean_cayley_graphs.boolean_linear_code import linear_code_from_code_gens
32

33

34
def boolean_linear_code_graph(dim, f):
35
    r"""
36
    Return the graph corresponding to the linear code of a bent Boolean function.
37

38
    INPUT:
39

40
    - ``dim`` -- positive integer. The assumed dimension of function ``f``.
41
    - ``f`` -- a Python function that takes a positive integer and returns 0 or 1.
42
      This is assumed to represent a bent Boolean function on :math:`\mathbb{F}_2^{dim}`
43
      via lexicographical ordering.
44

45
    OUTPUT:
46

47
    An object of class ``Graph``, representing the graph corresponding to
48
    the linear code of the bent Boolean function represented by ``f``.
49

50
    .. WARNING::
51

52
        This function raises a ``ValueError`` if ``f`` is not bent.
53

54
    REFERENCES:
55

56
    .. [Car2010]_
57

58
    .. [DD2015]_ Corollary 10.
59

60
    EXAMPLES:
61

62
    Where bf is a bent function.
63

64
    ::
65

66
        sage: from sage.crypto.boolean_function import BooleanFunction
67
        sage: bf = BooleanFunction([0,1,0,0,0,1,0,0,0,1,0,0,1,0,1,1])
68
        sage: bf.is_bent()
69
        True
70
        sage: dim = bf.nvariables()
71
        sage: from boolean_cayley_graphs.boolean_linear_code_graph import boolean_linear_code_graph
72
        sage: bg = boolean_linear_code_graph(dim, bf)
73
        sage: bg.is_strongly_regular()
74
        True
75

76
    Where f is not a bent function.
77

78
    ::
79

80
        sage: from sage.crypto.boolean_function import BooleanFunction
81
        sage: f = BooleanFunction([0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,1])
82
        sage: f.is_bent()
83
        False
84
        sage: from boolean_cayley_graphs.boolean_linear_code_graph import boolean_linear_code_graph
85
        sage: dim = f.nvariables()
86
        sage: g = boolean_linear_code_graph(dim, f)
87
        Traceback (most recent call last):
88
            ...
89
        ValueError: too many values to unpack (expected 2)
90

91
    """
92
    L = boolean_linear_code(dim, f)
93
    return strongly_regular_from_two_weight_code(L)
94

95

96
def strongly_regular_from_code_gens(gens):
97
    r"""
98
    Return the strongly regular graph corresponding to a list of generators.
99

100
    INPUT:
101

102
    - ``gens`` -- list. A list of strings of 0,1 characters.
103
      This is assumed to represent the generators of a
104
      projective two-weight linear code which yields a strongly regular graph.
105

106
    OUTPUT:
107

108
    An object of class ``Graph``, representing the graph corresponding to
109
    the generators represented by ``gens``.
110

111
    .. WARNING::
112

113
        This function raises a ``ValueError`` if ``gens`` is not a list of
114
        generators of a projective two-weight linear code which yields a
115
        strongly regular graph.
116

117
    EXAMPLES:
118

119
    ::
120

121
        Where ``gens`` is a list of generators for a code yielding a
122
        strongly regular graph.
123

124
        sage: from boolean_cayley_graphs.boolean_linear_code_graph import strongly_regular_from_code_gens
125
        sage: gens = [
126
        ....: "100001",
127
        ....: "010100",
128
        ....: "001100",
129
        ....: "000011"]
130
        sage: g = strongly_regular_from_code_gens(gens)
131
        sage: g.is_strongly_regular()
132
        True
133

134
    ::
135

136
        Where ``nongens`` is a list of generators for a code that does *not*
137
        yield a strongly regular graph.
138

139
        sage: nongens = [
140
        ....: "10001",
141
        ....: "01000",
142
        ....: "00100",
143
        ....: "00011"]
144
        sage: nong = strongly_regular_from_code_gens(nongens)
145
        Traceback (most recent call last):
146
            ...
147
        ValueError: too many values to unpack (expected 2)
148

149
    """
150
    L = linear_code_from_code_gens(gens)
151
    return strongly_regular_from_two_weight_code(L)
152

153