Frames for large sets of t-designs: data and programs

This repository accompanies the paper Frames for Large Sets of t-Designs by Yeow Meng Chee. It contains every large set constructed in the paper, programs that verify them, the programs used to find them, and the program that computes the existence table in Section 7.

Contents

Path	Content
data/affine_large_sets.txt	Base blocks of the large sets of Theorems 6.5 and 6.8 (frames with trivial P)
data/shifter_large_sets.txt	Groups, shifters and base blocks of the large sets of Theorem 6.11, generated by shifters
data/rank_one_large_sets.txt	Groups, stabilisers and base blocks of 14 of the 16 large sets of Theorem 6.12 and Table 4 (frames (E1) and (E2), root cases). The other two, LS13 and LS13, are in frame_families_large_sets.txt
data/frame_families_large_sets.txt	Groups, stabilisers and base blocks of the 297 large sets of Theorem 6.16 and Table 5 (frames of families (B) to (E))
data/several_base_large_sets.txt	Groups, stabilisers and base blocks of large sets from several base designs, including those of Table 7 with frames of rank three (Theorem 6.17)
data/rank_two_large_sets.json	Generators of H, K_1, K_2 and base blocks of the 73 large sets of Theorem 6.17 realising frames of rank two (Tables 6 and 7), including the LS11
data/rank_two_search_v20.csv	Outcome of the search over frames of rank two for all 232 parameter sets with N >= 3 prime and v <= 20 (Table 6)
data/agl2_large_sets.json	Generators and base blocks of the 41 large sets realising frames with H = T x
verify/verify_affine.py	Verifier for affine_large_sets.txt
verify/verify_shifter.py	Verifier for shifter_large_sets.txt
verify/verify_several.py	Verifier for several_base_large_sets.txt, rank_one_large_sets.txt and frame_families_large_sets.txt
verify/verify_ranktwo.py	Verifier for rank_two_large_sets.json
search/	Programs used to find the large sets (search/p311 for p = 311)
table/	Program that computes the existence table in Section 7, its output, the full tables, and the list open_cases.csv of open parameter sets

Verifying the large sets

The verifiers use only the Python 3 standard library.

python3 verify/verify_affine.py data/affine_large_sets.txt
python3 verify/verify_shifter.py data/shifter_large_sets.txt
python3 verify/verify_several.py data/several_base_large_sets.txt
python3 verify/verify_several.py data/rank_one_large_sets.txt
python3 verify/verify_several.py data/frame_families_large_sets.txt
python3 verify/verify_ranktwo.py data/rank_two_large_sets.json
python3 verify/verify_ranktwo.py data/agl2_large_sets.json

Each line of output names a large set and reports whether it passed. The first two runs take a few seconds, and the third takes several minutes, mostly for the LS13. The verifiers were written separately from the search programs.

verify_affine.py checks that the base blocks lie in pairwise distinct orbits, that the orbits contain every k-subset exactly once, and that every design contains every t-subset in exactly lambda blocks. Its docstring explains why it suffices to test the t-subsets containing 0 and 1.

verify_shifter.py generates the group, expands every orbit, checks that the first design is a t-(v,k,lambda) design, and checks that its images under the powers of the shifter are pairwise disjoint and contain every k-subset.

verify_several.py closes the generators of each stabiliser K_i to a group, expands each base design as the union of the K_i-orbits of its base blocks, forms the images of the base designs under H, and checks that the N resulting sets are t-(v,k,lambda) designs that partition the k-subsets.

Data formats

affine_large_sets.txt: a header line LS group p t k lambda N, with group AGL or ASL, followed by N lines, one per design. Each line lists base blocks separated by |. A design is the union of the orbits of its base blocks under AGL(1,p) = {x -> ax + b : a != 0} or ASL(1,p) = {x -> ax + b : a a nonzero square}.

shifter_large_sets.txt: a header line LS[N](t,k,v) lambda=..., then lines G: with the generators of G, a line sigma: with the shifter, and a line blocks: with base blocks. Permutations are image lists: point i is mapped to the i-th number. The first design is the union of the G-orbits of the base blocks, and the large set consists of its images under sigma^0, ..., sigma^(N-1).

several_base_large_sets.txt: each record starts with a line LS N t k v and a comment naming the search that found it. A line H is followed by the generators of H. For each base design, a line K is followed by the generators of its stabiliser K_i (none when K_i is trivial), and a line BASE is followed by its base blocks. A record ends with END. Permutations are image lists on the points 0, ..., v-1.

Searching

The search programs need Python 3 and OR-Tools (pip install ortools), whose CP-SAT solver solves the integer programs. For example,

cd search
python3 peelbt.py AGL 3 4 23 47 59     # large sets LS[(p-3)/4](3,4,p) under AGL(1,p)
python3 peelbt.py AGL 3 5 19           # LS[4](3,5,19) under AGL(1,19)
python3 peelbt.py ASL 3 5 23           # LS[19](3,5,23) under ASL(1,23)
python3 run3.py 600 3,4,12             # large sets generated by shifters of centraliser type

km.py builds the Kramer-Mesner matrices, peel.py finds one design with integer programming, peelbt.py peels designs one at a time with backtracking, and cyc.py, cyc2.py, run3.py and run4.py search for large sets generated by shifters. The directory search/p311 contains the program that found the LS77; it peels in the same way, starting from a prescribed first design. The searches are randomised, so they generally return large sets different from those in data/.

The directory search/several contains the programs for Section 6.3. genls.py sets up and solves the system of Theorem 3.1 for given generators of H and of the stabilisers K_i, and filters.py and necessary.py test the necessary conditions of Propositions 4.1 to 4.4. scan_mix.py searches the subgroups of AGL(1,p) that contain the translations, scan_frob.py searches the groups over F_q with q a prime power and over Z_n with n composite, and qs_family.py searches large sets of 3-(p,4,2) designs under AGL(1,p). The two-stage method of lll_ls.py (driver t_lll.py) first partitions the orbits of H into the unions of Proposition 4.2 and then splits each union. It can optionally use lattice basis reduction through fpylll. The scans read the existence table from ../../table/existence_table.csv to select open parameter sets, for example

cd search/several
python3 scan_mix.py 3000 60 mix.log      # orbit cap, time limit per instance, log file
python3 qs_family.py 41 2400 6           # LS[19](3,4,41): prime, time limit, maximum number of base designs

The directory search/rank_one contains the programs for Section 6.2 (frames of rank one). twisted.py searches the frame (E2) and m1F.py the frame (E1), and m1BC.py, m1Dall.py and m1Eall.py search frames of families (B) and (C), (D) and (E). They use genls2.py for the system of Theorem 3.1 and filters.py for the necessary conditions, and read the existence table from ../../table/existence_table.csv. For example,

cd search/rank_one
python3 twisted.py 600 19,8 23,7            # time limit per instance, then p,k for LS[p](2,k,p+2)
python3 m1BC.py 2000000 300 bc.log           # cap on binomial(v,k), time limit, log file
python3 m1Eall.py 300000 120 e.log
python3 m1Dall.py 300000 120 d.log 300       # last argument: time limit per parameter set

Searching over frames of rank two

search/rank_two/phase1.py lists, for each target parameter set, the groups H of families.py and the pairs of subgroup classes (K_1, K_2) of H with [H:K_1] + [H:K_2] = N that pass the derangement and congruence conditions. search/rank_two/phase2.py applies the orbit and union filters and solves the system of Theorem 3.1 with a time limit per frame. pgrp.py computes the conjugacy classes of subgroups of a small permutation group, and summary.py produces rank_two_search_v20.csv. agl2.py and agl3.py give the groups T x| L on F_q^2 and F_3^3, used by phase1_agl2.py and phase1_agl3.py.

Existence table

cd table
python3 gen_tables.py

recomputes large_sets_table.csv, which should coincide with existence_table.csv. The base results and their sources are listed in base.py, and the recursive theorems are implemented in engine.py. existence_tables.pdf contains the full tables with the justification of every entry. open_cases.csv lists the 33547 admissible parameter sets LSN with N prime, t < k <= v/2 and v <= 100 that remain open, with columns N,t,k,v,lambda and a flag v_mod_N_lt_k_mod_N that is 1 when the shifter condition v mod N < k mod N of Corollary 5.4 holds.

Licence

The programs and data are released under the MIT License (see LICENSE). If you use the data, please cite the paper.