Subpolygons

A polygon $P$ is called a subpolygon of $Q$, if $\varphi(P) \subseteq Q$ for some affine unimodular transformation $\varphi$. Given a $k$-rational polygon $P$, we can find all subpolygons of $P$ using the algorithm described in section 2.3 of [2]. The main idea is to successively remove vertices of $P$ by computing Hilbert bases.

Hilbert bases

We follow [7] to compute Hilbert bases of two-dimensional cones using Hirzebruch-Jung continued fractions.

RationalPolygons.cls_cone_normal_form — Function

cls_cone_normal_form(A :: Matrix2{T}) where {T <: Integer}

Bring a two-dimensional cone into normal form in the sense of [7]. The result is a triple $(d, k, M)$, where d and k are the parameters of the cone and M is a $2x2$ integral matrix such that M * [0 d ; 1 -k] == A

Example

julia> A = Matrix2(2, 1, -3, -5)
2×2 SMatrix{2, 2, Int64, 4} with indices SOneTo(2)×SOneTo(2):
 2  -3
 1  -5

julia> cls_cone_normal_form(A)
(7, 5, [1 2; 0 1])

RationalPolygons.hirzebruch_jung — Function

hirzebruch_jung(x :: T, y :: T) where {T <: Integer}

Return the Hirzebruch-Jung continued fraction associated to x // y.

Example

See Example 10.2.4 of [7].

julia> hirzebruch_jung(7,5)
3-element Vector{Int64}:
 2
 2
 3

RationalPolygons.hilbert_basis — Function

hilbert_basis(A :: Matrix2{T}) where {T <: Integer}

Return the Hilbert basis of a two-dimensional cone spanned by the columns of A, which must be primitive.

Example

See Example 10.2.4 of [7].

julia> A = Matrix2(0,1,7,-5)
2×2 SMatrix{2, 2, Int64, 4} with indices SOneTo(2)×SOneTo(2):
 0   7
 1  -5

julia> hilbert_basis(A)
5-element Vector{SVector{2, Int64}}:
 [0, 1]
 [1, 0]
 [2, -1]
 [3, -2]
 [7, -5]

hilbert_basis(v1 :: LatticePoint{T}, v2 :: LatticePoint{T}) where {T <: Integer}

Return the hilbert basis of a two-dimensional cone spanned by given integral primitive vectors v1 and v2.

RationalPolygons.remove_vertex — Function

remove_vertex(P :: RationalPolygon{T}, i :: Int) where {T <: Integer}

Return a pair (Q, keeps_genus), where Q is the convex hull of all k-rational points of P except the i-th vertex and keeps_genus :: Bool is true if and only if Q has the same number of interior lattice points as P. If the argument primitive = true is passed, the convex hull is taken of all primitive k-rational points of P except the i-th vertex.

Example:

Compare Example 10.2.7 of [7].

julia> P = convex_hull(LatticePoint{Int}[(0,0),(7,-5),(7,1),(0,1)])
Rational polygon of rationality 1 with 4 vertices.

julia> Q,_ = remove_vertex(P,1)
(Rational polygon of rationality 1 with 4 vertices., false)

julia> vertices(Q)
4-element Vector{SVector{2, Rational{Int64}}}:
 [0, 1]
 [3, -2]
 [7, -5]
 [7, 1]

Computing subpolygons

Subpolygons can be either computed in memory or on disk using HDF5. The latter is useful for computations where the amount of polygons will grow very large (e.g. several billions), which would overload available memory. Note that even in the latter case, some polygons will have to be kept in memory in order to do equivalence checks with them later. In fact, to minimize memory usage further, we will only keep the hashes of those polygons and compare those. We use 128-bit hashes here, which makes the probability of a hash collision negligible even for several billions of polygons.

RationalPolygons.SubpolygonStorage — Type

SubpolygonStorage{T <: Integer}

An abstract supertype of storage options for computing subpolygons. There are two subtypes InMemorySubpolygonStorage and HDFSubpolygonStorage. The former keeps all subpolygons in memory, the latter delegates their storage to the disk using the HDF5 format. Both implement subpolygons_single_step.

RationalPolygons.InMemorySubpolygonStoragePreferences — Type

struct InMemorySubpolygonStoragePreferences{T <: Integer}

A struct holding preferences for InMemorySubpolygonStorage. There are the following fields:

primitive :: Bool: Whether only subpolygons with primitive vertices should be computed. The default is false.
use_affine_normal_form :: Bool: Whether to use affine_normal_form or unimodular_normal_form. The default is true, i.e. affine normal form.
only_equal_number_of_interior_lattice_points :: Bool: Whether only subpolygons having the same number of interior lattice points as the starting polygons should be computed. The default is false.
exclude_very_thin_polygons: Whether polygons that can be realized in $\mathbb{R} \times [0,1]$ should be excluded. This is only relevant for polygons with no interior lattice points. The default is false.

RationalPolygons.InMemorySubpolygonStorage — Type

mutable struct InMemorySubpolygonStorage{T <: Integer} <: SubpolygonStorage{T}

A struct holding results of a subpolygon computation. It has the following fields:

preferences :: InMemorySubpolygonStoragePreferences{T}
polygons :: Dict{T,Set{RationalPolygon{T}}}
last_completed_area :: T
total_count :: Int

RationalPolygons.HDFSubpolygonStoragePreferences — Type

struct HDFSubpolygonStoragePreferences{T <: Integer}

A struct holding preferences for HDFSubpolygonStorage. There are the following fields:

rationality :: T: The rationality of the polygons. The default is one(T).
primitive :: Bool: Whether only subpolygons with primitive vertices should be computed. The default is false.
use_affine_normal_form :: Bool: Whether to use affine_normal_form or unimodular_normal_form. The default is true, i.e. affine normal form.
only_equal_number_of_interior_lattice_points :: Bool: Whether only subpolygons having the same number of interior lattice points as the starting polygons should be computed. The default is false.
exclude_very_thin_polygons: Whether polygons that can be realized in $\mathbb{R} \times [0,1]$ should be excluded. This is only relevant for polygons with no interior lattice points. The default is false.
block_size :: Int: How many polygons should be read into memory at once during the shaving process. Defaults to 10^6.
maximum_number_of_vertices :: Int: An upper bound for the maximal number of vertices to be expected in the computation. This has to be set since every HDF5 file generated will have a dataset "numbers_of_polygons" storing the number of polygons for each number of vertices and the size of this dataset needs to be set beforehand. Defaults to 100, which should be more than enough for any feasible computation.
swmr :: Bool: Whether to use single-reader-multiple-writer mode for HDF5. Defaults to true.

RationalPolygons.HDFSubpolygonStorage — Type

mutable struct HDFSubpolygonStorage{T <: Integer} <: SubpolygonStorage{T}

A struct for managing the result of a subpolygon computation using the HDF5 file format. It has the following fields:

preferences :: HDFSubpolygonStoragePreferences{T}
file_path :: String: The file path of the HDF5 file to be created.
group_path :: String: Path to a group within the HDF5 file, if it already exists. Defaults to "/", i.e. the root group.
hash_sets :: Dict{T,Set{UInt128}}: A dictionary of hashes of polygons already encountered. This is used for comparison with new polygons to ensure the result contains each polygon exactly once. We hold these hashes in memory to avoid needing to read in polygons that have been written out in the past, which saves a lot of time.
last_completed_area :: T: The last area that has been completed. This counts down from the maximum area of the starting polygons to 1.
total_count :: Int

RationalPolygons.initialize_subpolygon_storage — Function

initialize_subpolygon_storage(st :: HDFSubpolygonStorage{T}, Ps :: Vector{<:RationalPolygon{T}}) where {T <: Integer}

Initialize a newly created HDFSubpolygonStorage with a given set of starting polygons. To restart an interrupted computation, see also restore_hdf_subpolygon_storage_status.

RationalPolygons.subpolygons_single_step — Function

subpolygons_single_step(st :: InMemorySubpolygonStorage{T}; logging :: Bool = false) where {T <: Integer}

Perform a single step of a subpolygon computation in memory.

subpolygons_single_step(st :: HDFSubpolygonStorage{T}; logging :: Bool = false) where {T <: Integer}

Perform a single step in a subpolygon computation using the HDF5 file format.

RationalPolygons.subpolygons — Function

subpolygons(st :: SubpolygonStorage{T}; logging :: Bool = false) where {T <: Integer}

Compute all subpolygons with the given storage option.

subpolygons(Ps :: Vector{<:RationalPolygon{T}}) where {T <: Integer}
subpolygons(P :: RationalPolygon{T}) where {T <: Integer}

Compute all subpolygons of a rational polygon or list of rational polygons. The computation is done in memory, for storage on disk see also HDFSubpolygonStorage. This function takes the following keyword arguments:

primitive :: Bool: Whether only subpolygons with primitive vertices should be returned. The default is false.
use_affine_normal_form :: Bool: Whether to use affine or unimodular normal form. The default is true, so affine normal form.
only_equal_number_of_interior_lattice_points :: Bool: Whether only subpolygons that share the same number of interior lattice points with the starting polygons should be returned.
exclude_very_thin_polygons: Whether polygons that can be realized in $\mathbb{R} \times [0,1]$ should be excluded. This is only relevant for polygons with no interior lattice points. The default is false.
logging :: Bool: Whether to display logging messages about the computation progress.

Example:

There are $148$ subpolygons of the square of side length three, up to affine equivalence. The maximal number of vertices of those is eight, attained by exactly one polygon.

julia> Ps = subpolygons(convex_hull(LatticePoint{Int}[(0,0),(3,0),(0,3),(3,3)]));

julia> length(Ps)
148

julia> maximum(number_of_vertices.(Ps))
8

RationalPolygons.restore_hdf_subpolygon_storage_status — Function

restore_hdf_subpolygon_storage_status(st :: HDFSubpolygonStorage{T}) where {T <: Integer}

Restore a subpolygon computation's status that was interrupted from an HDF5 file. All polygons will be read in, hashed and saved into st.hash_sets. Moreover, st.last_completed_area and st.total_count will be properly set. After calling this function, the computation can be resumed by calling subpolygons(st) again.