/
ShortVectors.jl
161 lines (133 loc) · 4.65 KB
/
ShortVectors.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
@doc raw"""
short_vectors(L::ZZLat, [lb = 0], ub, [elem_type = ZZRingElem]; check::Bool = true)
-> Vector{Tuple{Vector{elem_type}, QQFieldElem}}
Return all tuples `(v, n)` such that $n = |v G v^t|$ satisfies `lb <= n <= ub`,
where `G` is the Gram matrix of `L` and `v` is non-zero.
Note that the vectors are computed up to sign (so only one of `v` and `-v`
appears).
It is assumed and checked that `L` is definite.
See also [`short_vectors_iterator`](@ref) for an iterator version.
"""
short_vectors
@doc raw"""
short_vectors_iterator(L::ZZLat, [lb = 0], ub,
[elem_type = ZZRingElem]; check::Bool = true)
-> Tuple{Vector{elem_type}, QQFieldElem} (iterator)
Return an iterator for all tuples `(v, n)` such that $n = |v G v^t|$ satisfies
`lb <= n <= ub`, where `G` is the Gram matrix of `L` and `v` is non-zero.
Note that the vectors are computed up to sign (so only one of `v` and `-v`
appears).
It is assumed and checked that `L` is definite.
See also [`short_vectors`](@ref).
"""
short_vectors_iterator
function short_vectors(L::ZZLat, ub, elem_type::Type{S} = ZZRingElem; check::Bool = true) where {S}
if check
@req ub >= 0 "The upper bound must be non-negative"
@req is_definite(L) "Lattice must be definite"
end
if rank(L) == 0
return Tuple{Vector{S}, QQFieldElem}[]
end
_G = gram_matrix(L)
if _G[1, 1] < 0
_G = -_G
end
return _short_vectors_gram(Vector, _G, ub, S)
end
function short_vectors_iterator(L::ZZLat, ub, elem_type::Type{S} = ZZRingElem; check::Bool = true) where {S}
if check
@req ub >= 0 "The upper bound must be non-negative"
@req is_definite(L) "Lattice must be definite"
end
_G = gram_matrix(L)
if rank(L) != 0 && _G[1, 1] < 0
_G = -_G
end
return _short_vectors_gram(LatEnumCtx, _G, ub, S)
end
function short_vectors(L::ZZLat, lb, ub, elem_type::Type{S} = ZZRingElem; check=true) where {S}
if check
@req lb >= 0 "The lower bound must be non-negative"
@req ub >= 0 "The upper bound must be non-negative"
@req is_definite(L) "Lattice must be definite"
end
if rank(L) == 0
return Tuple{Vector{S}, QQFieldElem}[]
end
_G = gram_matrix(L)
if _G[1, 1] < 0
_G = -_G
end
return _short_vectors_gram(Vector, _G, lb, ub, S)
end
function short_vectors_iterator(L::ZZLat, lb, ub, elem_type::Type{S} = ZZRingElem; check=true) where {S}
if check
@req lb >= 0 "The lower bound must be non-negative"
@req ub >= 0 "The upper bound must be non-negative"
@req is_definite(L) "Lattice must be definite"
end
_G = gram_matrix(L)
if rank(L) != 0 && _G[1, 1] < 0
_G = -_G
end
return _short_vectors_gram(LatEnumCtx, _G, lb, ub, S)
end
################################################################################
#
# Shortest vectors
#
################################################################################
@doc raw"""
shortest_vectors(L::ZZLat, [elem_type = ZZRingElem]; check::Bool = true)
-> QQFieldElem, Vector{elem_type}, QQFieldElem}
Return the list of shortest non-zero vectors in absolute value. Note that the
vectors are computed up to sign (so only one of `v` and `-v` appears).
It is assumed and checked that `L` is definite.
See also [`minimum`](@ref).
"""
shortest_vectors(L::ZZLat, ::ZZRingElem)
function shortest_vectors(L::ZZLat, elem_type::Type{S} = ZZRingElem; check::Bool = true) where {S}
if check
@req rank(L) > 0 "Lattice must have positive rank"
@req is_definite(L) "Lattice must be definite"
end
_G = gram_matrix(L)
if _G[1, 1] < 0
_G = -_G
end
min, V = _shortest_vectors_gram(_G)
L.minimum = min
return V
end
################################################################################
#
# Minimum
#
################################################################################
@doc raw"""
minimum(L::ZZLat) -> QQFieldElem
Return the minimum absolute squared length among the non-zero vectors in `L`.
"""
function minimum(L::ZZLat)
@req rank(L) > 0 "Lattice must have positive rank"
if !isdefined(L, :minimum)
shortest_vectors(L)
end
return L.minimum
end
################################################################################
#
# Kissing number
#
################################################################################
@doc raw"""
kissing_number(L::ZZLat) -> Int
Return the Kissing number of the sphere packing defined by `L`.
This is the number of non-overlapping spheres touching any
other given sphere.
"""
function kissing_number(L::ZZLat)
@req rank(L) > 0 "Lattice must have positive rank"
return 2 * length(shortest_vectors(L))
end