Invariable generation of alternating groups

Copyright © 2022 Robert M. Guralnick, John Shareshian, and Russ Woodroofe

This code is in support of our paper On invariable generation of alternating groups (arXiv:2201.12371).

The basic idea is that if n is preceded by a prime number r (at most n-3), and p^a is a prime-power divisor of n so that r + p^a > n, then A_n is generated by any r cycle together with any element of order p^a having a certain cycle structure. We use fast C code to check which n in a range of integers satisfies this condition.

Certain (rare) smooth numbers do not satisfy the condition, and for these we use slower GAP code to verify more complicated number-theoretic conditions which yield similar generation condition. For details, please see the paper.

Instructions for use

1. Run make to build. (Requirements: primesieve library)
2. Edit batchjob to match the number of simultaneous jobs and the size and number of ranges to examine. By default, it outputs to files of the form out-num.g in your home directory.
3. Run ./batchjob. Alternatively, time ./batchjob.
4. Run gap.
5. Read("invgen_pub.g"); in gap.
6. InvgenCheckPhaseTwoFromFilesInDirectory("~/"); in gap.

This is research software, and may require tweaking for your specific circumstances. It has been tested on macOS and Ubuntu Linux.

Inventory

The project consists of the following main files.

invgen_sievelp.c

This C program generates a list of integers n where the prime preceding n-2 and the largest prime-power divisor of n sum to at most n. Thus, it generates a list of numbers that are smooth, relative to the prime gap that they lie in.

The resulting command-line tool takes two arguments, which specify the first and last numbers in a range of positive integers.

The output is a GAP readable file, which sets variable invgen_oversmooth_range to the range of integers considered, and variable invgen_oversmooth to a list of entries of the form [n, p^a], where n is a smooth number and p^a is the largest prime-power divisor of n.

batchjob

This bash script runs a configurable number of parallel instances of invgen_sievelp, covering some given range. It should be edited before a computation. The variable INVGEN_CHUNKSIZE holds the size of each range, INVGEN_STOPSTEP holds the largest multiple of the chunk size to compute out to, and INVGEN_NUMJOBS holds the maximum number of simutaneous jobs to run.

The script is relatively unsophisticated, and waits for all current jobs to complete before beginning new ones.

invgen_pub.g

This family of GAP functions has several functions. The most important function is:

InvgenCheckPhaseTwoFromFilesInDirectory

Given a directory, this function looks for files matching the wildcard out-\*.g or out-\*.g.gz, which it expects to be output from invgen_sievelp. It checks that the alternating group at each n given is generated by any two elements having certain cycles structures (where one such element has prime order, the other prime-power order).

Also of note: InvgenCheckInRange is slower GAP code to check the same condition as in invgen_sievelp, together with the "Phase 2" check. Several other functions work together to implement a segmented sieve of Eratosthenes.