Most wanted reproducible results in computational algebra

Question

I am interested in suggestions for major computational results obtained with the help of mathematical software but not easily verifiable using computers.

"Most wanted" could refer, for example, to the following:

• results which are highly cited/reused in other publications/computations
• computational proofs of fundamental results
• counterexamples to central conjectures in a field
• checking correctness of various mathematical databases
• producing open source implementations of computations previously performed using another open or closed source software, or when the old code is not available at all
• landmark computations that one could be interested to reproduce (in the same way like a chemistry reaction from a textbook could be reproduced by mixing baking soda and vinegar in your kitchen).

If the publication just says "this result was produced using the system X", it may be a long way to reproduce it. It may include a reference to exact version of the system, a link to the extra code to download, but again it may happen that that version has to be installed in some particular way to satisfy certain dependencies, the extra code is not well documented so it is unclear how to run it, some other special knowledge or non-trivial computational resources are needed, etc.

On the other side, having these results easier reproducible could be crucial for science. Hypothetically, one could e.g. download a virtual machine and re-run the whole experiment, or use the newest version of the system to check whether the experiment still runs with the same outcome.

I hope that making such a list of suggested experiments to reproduce will be useful to those interested in checking them twice ;-). For example, one could submit their findings to a journal like ReScience which "targets computational research and encourages the explicit replication of already published research, promoting new and open-source implementations in order to ensure that the original research is reproducible".

Remark: suggestions on computational verification of previously obtained theoretical results and pointers to existing reproducible experiments are also welcome.

Answer 1

I am not sure if the result is "most wanted", but we disproved a well-known conjecture of John Milnor, that every connected solvable Lie group admits a left-invariant affine structure, by a very hard computation concerning a refinement of Ado's theorem for Lie algebras. We proved the following result, yielding a counterexample to Milnor's conjecture:

Theorem: There exist nilpotent Lie algebras of dimension $10$ and nilpotency class $9$ over a field of characteristic zero which do not admit any faithful linear representation of dimension $11$.

Reference: Affine structures on nilmanifolds, $1996$. See there for references and the proof of Yves Benoist for dimension $11$. The computations have been done with "Reduce", which is open source. Willem de Graaf (also an expert in GAP) and other experts in computational algebra have confirmed that these computations are very hard; recently the computations have been re-used to show that not every solvable $p$-group admits a left-brace structure - see here. This gives again a counterexample ( to a well-known conjecture about brace structures), but this time about faithful Lie algebra representations over characteristic $p>0$.

Answer 2

I believe that enumeration of finite groups of a given order is definitely among most wanted reproducible experiments. Here "enumeration" means providing complete and non-redundant list of groups, "complete" means that no groups are missing in this list, and "non-redundant" means that groups from this list are non-isomorphic pairwise. Guaranteeing these properties is crucial for results that rely on checking all groups of a given order, or that refer to a particular group by its "catalogue number".

The most complete collection of groups of certain orders is available in the GAP system via several interconnected packages:

• Hans Ulrich Besche and Bettina Eick: GrpConst - Constructing the Groups of a Given Order, Version 2.5 (2015), http://www.icm.tu-bs.de/~beick/so.html

• Hans Ulrich Besche, Bettina Eick and Eamonn O'Brien: The Small Groups Library, http://www.icm.tu-bs.de/ag_algebra/software/small/

• Bettina Eick and Michael Vaughan-Lee: SglPPow - Database of groups of prime-power order for some prime-powers, Version 1.1 (2014), http://www.icm.tu-bs.de/~beick/soft/sglppow/

• Heiko Dietrich: Cubefree - Constructing the Groups of a Given Cubefree Order, Version 1.15 (2015), http://users.monash.edu.au/~heikod/cubefree.html

Altogether, this provides some precomputed collections of groups for some orders as well as functions to construct all groups of a given order for some infinite series. None of this packages is actually a mere database which only stores certain groups, since even predominantly database-providing packages also implement algorithms for generic constructions of groups of order $p^n$ for some $p$ and $n$, and for groups of square-free orders. These packages are closely interconnected: for example, while GrpConst was used to construct some groups from the SmallGroups library, it also uses the SmallGroups library to enumerate groups of some other orders.

It is very important to have such results as much cross-checked and reproducible as possible: even if the database part of the libraries remains unchanged, that does not guarantee that any other changes in GAP and/or this packages will not break the code. Of course, a lot of cross-checks had been done, and this functionality is considered to be very reliable:

• The group numbers in the SmallGroups library are to a large extent cross-checked, being computed using different approaches and also compared with theoretical results, where available (see [Hans Ulrich Besche, Bettina Eick and Eamonn O'Brien. A MILLENNIUM PROJECT: CONSTRUCTING SMALL GROUPS. Int. J. Algebra Comput. 12, 623 (2002), http://dx.doi.org/10.1142/S0218196702001115], in particular 4.1. Reliability of the data).

• The Cubefree package was cross-checked against the SmallGroups Library and IRREDSOL package as described at http://www.gap-system.org/Manuals/pkg/cubefree/htm/CHAP002.htm#SECT005.

• The GAP standard test suite, which is run nightly and is a part of the release preparation workflow, includes tests of ConstructAllGroups from the GrpConst package.

But modern tools permit us to do even more, and in particular improve situation for orders where precomputed collections of all groups are not available. Recently I have initiated a "Group numbers reproducibility project" (which was inspired by some questions under the 'groups-enumeration' tag here - see in particular this one). This project uses crowdsourcing approach to assemble a database of numbers of isomorphism types of finite groups. In other words, it fills in the table of the values of the function $gnu(n)$, returning the number of isomorphism types of finite groups of order n (so "gnu" stands for the "Group NUmber"). It puts together data from several sources, including values calculated at runtime using the packages listed above and numbers published by the AG Algebra und Diskrete Mathematik group of TU Braunschweig at http://www.icm.tu-bs.de/ag_algebra/software/small/number.html. Furthermore, it accepts reports on new values, not available in any of the above mentioned sources and on recomputation of previously known values. The data are added to the database only after they are replicated by the maintainer. The project also uses two other designations for the submissions: "reproduced", when the same result was obtained using another implementation, and "agrees with theory", when it corresponds to the theoretically proved result.

In the current version of the database, the value of $gnu(n)$ is available from the computer algebra system level (from GAP locally or remotely, and from any other SCSCP client remotely). Using the version control history, one could also access provenance information (runtime, versions of the software, etc). This could be useful to the researchers interested in producing the list of all groups locally, since they can check if someone else had already attempted to do this and how much time did they wait. Since the beginning of the project, almost 200 new entries has been submitted, replicated and added to the database, which now provides the most complete available table of known values of $gnu(n)$.

Further details could be found in the README.md file at https://github.com/olexandr-konovalov/gnu. See also my presentation "Computational Algebra meets Open Science: Group Numbers Reproducibility Project".