The 11th Conference of the Fachgruppe Computeralgebra will take place from June 2 to 4, 2025 at the Max Planck Institute for Mathematics in the Sciences in Leipzig.
Main Speakers:
Clemens Hofstadler
Thomas Kahle
Marta Panizzut
Lorenz Panny
Milena Wrobel
Theme talk: Christiane Görgen
Young talent award: On the final day, a prize of €500 will be awarded for the best young talent presentation. The cash prize is accompanied by an invitation to give a main talk at the next conference.
Travel allowance: The Fachgruppe Computeralgebra Section can provide a limited amount of funds as a travel allowance. Please submit applications for travel grants with an explanatory cover letter, a reference person and a list of the required funds.
We present an effective algorithm to decide if a homogeneous prime ideal can be made toric by a linear automorphism of the ambient space. If this is the case, the algorithm computes such a transformation explicitly. We benchmark the algorithm on Gaussian graphical models on five vertices and Gaussian conditional independence models of undirected graphs up to six vertices. We find that these are either toric from the start or cannot be made toric by linear coordinate changes. This is joint work with Julian Vill.
In diesem Vortrag führen wir die XOR-OR-AND-Normalform (XNF) für logische Formeln ein und präsentieren einen ersten Algorithmus zur Lösung jener. Die XNF verallgemeinert die wohlbekannte konjunktive Normalform, indem sie Literale durch XORs von Literalen, so genannte Linerale, ersetzt. Wir präsentieren Methoden zur Konvertierung Boolescher Polynomsysteme zu Formeln in 2-XNF, also Formeln in XNF, bei denen jede Klausel maximal zwei Linerale enthält. Experimente mit dem Verschlüsselungssystem ASCON-128 zeigen, dass Verschlüsselungssysteme mit vielen XOR-Operationen durch die XNF effizienter dargestellt werden können als mit herkömmlichen Konvertierungsmethoden. Anschließend präsentieren wir 2-Xornado, unseren neuen Graph-basierten SAT-Solver zur Lösung von Formeln in 2-XNF. Wir vergleichen 2-Xornado mit herkömmlichen SAT-Solvern mit XOR-Unterstützung und algebraischen Solvern für Boolesche Polynome anhand von Beispielen aus der Kryptoanalyse.
Max-linear Bayesian networks (MLBN) are statistical models described by weighted directed acyclic graphs (weighted DAG). At the same time, we can associate to this weighted DAG an alcoved polyhedron, a polyhedron whose facet normals correspond to the type $A_n$ root system. This alcoved polyhedron also describes the feasible set of an optimal transport problem on the same weighted DAG. The combinatorics of this optimal transport problem are encoded by the Gröbner fan. We use this fact to enumerate the combinatorial types of alcoved polyhedra associated to MLBN
Eulerian trails have connected automata theory, as well as formal languages, for a decade now. This paper extends to explain a new discovery based on (un)tested ideas or techniques with application in programming languages. Converting graphs to words and finding their respective automata models that accept a particular set of words as their language is one of the challenging tasks; henceforth, finding the time complexity of the algorithms. In this paper, hole-free Eulerian words are the main sets of words.
In a discrete graphical model, an underlying graph encodes conditional independences among a set of discrete random variables that label the vertices of the graph. Mixtures of these models allow us to incorporate the assumption that the population is split into subpopulations, each of which may follow a different distribution in the graphical model. From the perspective of algebraic statistics, a discrete graphical model is the real positive piece of a toric variety and the mixture model is part of one of its secant variety. In this talk, we use discrete geometry to investigate the dimensions of the second mixtures of decomposable discrete graphical models. We show that when the underlying graph is not a "clique star", the mixture model has the maximal dimension. This in turn allows us to prove results on the local identifiability of the parameters.
We prove that the transitive permutation group 17T7, isomorphic to a split extension of C2 by PSL2(F16), is a Galois group over the rationals. The group arises from the field of definition of the 2-torsion on an abelian fourfold with real multiplication defined over a real quadratic field. We find such fourfolds using Hilbert modular forms. Finally, building upon work of Dembélé, we show how to conjecturally reconstruct a period matrix for an abelian variety attached to a Hilbert modular form; we then use this to exhibit an explicit degree 17 polynomial with Galois group 17T7.
In the talk, we will give a general overview of the topic and the methods involved, and then more details of our construction.
This is joint work with Raymond van Bommel, Edgar Costa, Noam D. Elkies, Sam Schiavone, and John Voight.
In this talk we will recall the definition of Khovanskii (or Sagbi) bases and compare their properties with Gröbner bases. Inspired by several applications of Gröbner bases in solving zero-dimensional polynomial systems, we present analogous applications in computer algebra using Khovanskii bases. These include an eigenvalue-based algorithm to solve equations on unirational varieties parameterized by a Khovanskii basis, as well as the implementation of a Khovanskii-based homotopy in Julia to compute linear sections of such varieties. We conclude by discussing the Mukai lifting problem for self-dual points in P^6 , which we solve by exploiting the Khovanskii-homotopy algorithm to compute linear sections on the Grassmannian Gr(2,6). The results presented are based on joint works with V. Borovik, L. Kayser, M. Panizzut and S. Telen
Let G be a finite group and let k be a large enough field of characteristic p dividing |G|. In this talk, we present one possible way to explicitly calculate matrix representations of the projective indecomposable kG-modules (for groups of moderate order) using the open source computer algebra system GAP. Moreover, we comment on some applications thereof.
We introduce a detection algorithm for SAGBI basis in polynomial rings, analogous to a Gröbner basis detection algorithm previously proposed by Gritzmann and Sturmfels. We also present two accompanying software packages named SagbiGbDetection for Macaulay2 and Julia. Both packages allow the user to find one or more term orders for which a set of input polynomials form either Gröbner basis for the ideal they generate or a SAGBI basis for the subalgebra. Additionally, we investigate the computational complexity of homogeneous SAGBI detection and apply our implementation to several novel examples.
The computational complexity of polynomial ideals and Gröbner bases has been studied since the 1980’s.
In recent years the related notions of polynomial subalgebras and SAGBI bases have gained more and more attention in computational algebra, with a view towards effective algorithms.
In this talk we investigate the computational complexity of the membership problem for subalgebras and give degree bounds.
We also present a conjectural structure theory for their (often infinitely generated) initial algebras.
We highlight the parallels and differences compared to the "ideal world" and also look at important classes of polynomials such as homogeneous and monomial algebras.
Based on joint work with Bernhard Reinke.
Khovanskii bases extend the theory of Groebner bases of ideals in polynomial ring to general algebras. Recently they have been used to introduce exciting new methods for solving polynomial systems. We present a new eigenvalue method for solving structured polynomial equations, generilizing esatblished algorithms for toric varieties. We assume that the equations are defined on a projective algebraic variety which admits a rational parameterization by a Khovanskii basis. The talk is based on joint work with Barbara Betti and Simon Telen.
We study systems of real polynomial equations associated with certain triangulations of convex polytopes and investigate their number of real solutions. Our main focus is set on pairs of plane algebraic curves which form a so-called Wronski system. We present the computational difficulties arising in the analysis of such Wronski pairs. Joint work with Michael Joswig and Rafael Mohr.
In this talk, we'll introduce a new method for computing the kernel of a polynomial map which is homogeneous with respect to a multigrading. We first demonstrate how to quickly compute a matrix of maximal rank for which the map has a positive multigrading. Then in each graded component we compute the minimal generators of the kernel in that multidegree with linear algebra. We have implemented our techniques in Macaulay2 and show that our implementation can compute many generators of low degree in examples where Gröbner basis techniques have failed. This includes several examples coming from phylogenetics where even a complete list of quadrics and cubics were unknown. When the multigrading refines total degree, our algorithm is embarrassingly parallel. This is joint work with Joseph Cummings.
Computing the algebraic shift of a uniform hypergraph or a simplicial complex is resource intensive. We discuss improvements to the general algorithm for computations over the exterior algebra that lead to the definition of partial algebraic shifting. Further, we provide a sufficient condition for a partial algebraic shift to preserve the Betti numbers in terms of the weak order. This talk is based on joint work with Michael Joswig and Fabian Lenzen.
The expected signature of a family of paths need not be a signature of a path itself. Motivated by this, we consider the notion of a Lie group barycenter introduced by Buser and Karcher to propose a barycenter on signature tensors. We investigate affine algebraic varieties arising from barycenters of several families of samples in paths space, and use path learning techniques (Pfeffer, Seigal, Sturmfels) to recover the underlying path associated to the Lie group barycenter. We provide an implementation in the computer algebra system OSCAR. This is joint work with Carlos Amendola.
The signature of a path is a non-commutative power series whose coefficients are given by certain iterated integrals over the path components. This series almost uniquely characterizes the path up to translation and reparametrization. Projections of these series to their homogeneous components yield the so-called signature tensors.
Our package PathSignatures simplifies the study of these interesting objects in Macaulay2 for piecewise polynomial paths. It allows for the creation and manipulation of paths and the straight-forward computation of the associated signature tensors.
This is joint work with Carlos Améndola, Oriol Reig and Angelo El Saliby.
We will give an insight into the computer agebra system OSCAR and how to use it. After a brief introduction to and background of the system, we will look into some easy-to-grasp real-life examples.
OSCAR is being developed as part of the SFB-TRR 195 "Symbolic Tools in Mathematics and their Application". It is a general-purpose computer algebra system written in julia that builds on the four cornerstones GAP, polymake, Singular, and Antic (Hecke, Nemo) and has capabilities for dealing with problems in number theory, group and representation theory, tropical and polyhedral geometry, algebraic geometry, commutative algebra, non-commutative algebra, and many more areas of computer algebra.
In recent years the study of certain semi-algebraic sets known as "positive geometries" gained increasing attention due to its relevance in the sciences. Originally this concept was defined by physicists, but these sets also admit a beautiful structure when considering them from a mathematical viewpoint. The easiest class of examples consists of convex polytopes. The theory of positive geometries allows us to associate a polynomial known as the adjoint to each convex polytope. This polytope had several appearances in the study of polytopes in the past: Some examples include volumes of polar bodies and generalized barycentric coordinates of polytopes. In my talk I plan to present several different methods of computing the adjoint of a polytope from the perspective of positive geometry. These methods range from combinatorial formulas including triangulations to geometric interpolation problems.
Non-commutative Gröbner bases of two-sided ideals are not necessarily finite. In my talk I'll give a closed-form description of a finite and reduced Gröbner base for the two-sided ideal used in the construction of Wang's quantum symmetric group. This further extends the computational toolset for research on quantum symmetric groups, quantum automorphism groups of graphs, matroids and other combinatorial structures. For the construction of the Gröbner bases, we relied on the OSCAR system, with large parts of the proof implemented as computations within OSCAR.
This talk is based on joint work with Leonard Schmitz.
Systems of homogeneous linear PDEs can be represented as left ideals in the Weyl algebra. Using Gröbner basis techniques, these systems can be systematically encoded by connection matrices. In fundamental particle physics and theoretical cosmology, when investigating scattering amplitudes and cosmological correlators, they turn up as systems of differential equations in matrix form. We explain the implementation of our package ConnectionMatrices in Macaulay2 and showcase a few examples from physics.
This talk is based on joint work with: Paul Görlach, Anna-Laura Sattelberger, Mahrud Sayrafi, Hendrik Schroeder, Nicolas Weiss, and Francesca Zaffalon
We use software to study matroid realizations and initial degenerations of Grassmannians. In particular, we use OSCAR to study properties of matroid strata in rank 3 Grassmannians, classifying (3,n) pairs such that all strata are smooth and isolating concrete examples of matroids whose strata are singular. We then use this information, and matroid subdivisions of hypersimplices, to study initial degenerations of Grassmannians. For the (3,8)-Grassmannian, we show all initial degenerations are smooth, using OSCAR to classify all symmetry classes of matroid subdivisions of the (3,8) hypersimplex corresponding to cones in the tropical Grassmannian. Using examples of singular matroid strata, we construct singular initial degenerations of the associated Grassmannian. The content of this talk covers some material from my PhD thesis, and is the result of joint work with Daniel Corey.
Resultants are useful for applications in robotics and control theory, but often they become extensive multivariate polynomials. Therefore, it is useful to represent them implicitly as determinants of matrices. Gelfand, Kapranov and Zelevinsky associated resultants with a Koszul complex of sheaves. They consider the spectral sequence of the double complex arising from the sheaf cohomologies and specified resultants via determinants of the corresponding Weyman complexes. This complex depend on an additional line bundle. It can be chosen in a way that all higher sheaf cohomologies vanish, but the resulting complex often contains several terms. Thus, to calculate its determinant, a fraction of multivariate polynomials must be evaluated. To avoid this, we consider as Dickenstein and Emiris line bundles which yield Weyman complexes with only two terms. For this, higher sheaf cohomologies must also be taken into account. Here, we determine their higher differentials.
Elementary vectors - support-minimal vectors in a subspace - play a central role in areas such as linear inequality systems, linear and oriented matroids, the sparse basis problem, reaction network theory, and optimization.
We present a new algorithm for the enumeration of elementary vectors, avoiding scalar multiples. Its correctness is ensured via the Grassmann–Plücker identity. Our method computes elementary vectors over arbitrary integral domains using maximal minors, making it applicable to algebraic numbers, field extensions, and matrices with parameters.
We demonstrate our approach with examples and discuss one application to the solvability of linear inequality systems. Our implementation is available as part of our SageMath package.
We explain the concept of dependency equilibria in game theory, which generalize the well-known concept of Nash equilibria and allow for better results via assumptions of dependencies. They can be described nicely by an algebraic variety, the so-called Spohn variety. The new "GameTheory" package for Macaulay2 (currently still in development) can be used to compute this Spohn variety for a given game and also to intersect it with a conditional independence model.
For 2x2 games, the Spohn variety generically takes the form of an elliptic curve that is the intersection of two quadrics in P^3. We examine the reduction of Spohn curves to plane curves, analyzing conditions under which they are reducible via computations in Macaulay2. We then prove that the real points are dense on the Spohn curve in all cases, which is relevant since we are of course interested in real probabilities.
Research-data management is a hot topic across the sciences but what has it got to do with mathematics? I will report on a best-practice example: the process of taking an early 2000's mathematical library, the Small Phylogenetic Trees, and transforming it into a FAIR repository for data from algebraic phylogenetics. In doing so, modern web technology and expertise from data stewards is applied to preserve valuable mathematical results and ensure their reproducibility for the foreseeable future. Details can the found in this article https://arxiv.org/abs/2501.10823
Algebraic techniques, such as Gröbner bases, have a long and successful history in automatic geometric theorem proving. Recently, these methods have found a new and promising area of application in the context of proving operator statements. Operator statements are first-order formulas involving identities of matrices or, more generally, linear operators. These statements appear in various branches of mathematics, such as linear algebra, geometry, and functional analysis, as well as in related disciplines like signal processing or quantum physics.
In this talk, we present how the correctness of a first-order operator statement can be translated into an algebraic statement about noncommutative polynomials, which can be verified automatically using computer algebra. More precisely, this translation gives rise to a semi-decision procedure that allows to prove any true operator statement based on a single algebraic computation. Moreover, we discuss how this algebraic framework can be leveraged to compute shortest proofs of operator statements. For false operator statements, we address how to certify their invalidity by constructing explicit counterexamples. While this is an undecidable problem in general, we present a heuristic method that has shown promising results so far.
We give a short introduction into the theory of Cox rings and investigate their explicit structure for varieties with torus action. Building up on this description, we show how Cox rings can be used to classify (singular) Fano varieties using methods from computer algebra.
Participants
Marcus Aichmayr
Universität Kassel
Bernhard Andraschko
Universität Passau
George Balla
MPI MiS Leipzig
Barbara Betti
Max Planck Institute MiS
Martin Bies
RPTU Kaiserslautern-Landau
Bernhard Boehmler
Leibniz University Hannover
Viktoriia Borovik
MPI MiS
Alessio Borzi
MPI MiS Leipzig
Kilian Bruns
Carl von Ossietzky Universität Oldenburg
Veronica Calvo
MPI MiS
Laura Casabella
MPI MiS Leipzig
Jane Ivy Coons
MPI-CBG
Michael Cuntz
Leibniz Universität Hannover
Joris Dannemann
Carl von Ossietzky Universität Oldenburg
Antony Della Vecchia
TU Berlin
Kamillo Ferry
TU Berlin
Mirja Fitzner
Carl von Ossietzky Universität Oldenburg
Heß Florian
Universität Oldenburg
Anne Frühbis-Krüger
Carl von Ossietzky Universität Oldenburg
Alheydis Geiger
Max Planck Institute for Mathematics in the Sciences
Christiane Görgen
Uni Leipzig
Lars Göttgens
RWTH Aachen University
Friedemann Groh
ISG Industrielle Steuerungstechnik GmbH
Clemens Hofstadler
Johannes Kepler Universität Linz
Benjamin Hollering
Technical University of Munich
Max Horn
Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau
Michael Joswig
TU Berlin
Thomas Kahle
Otto-von-Guericke Universität Magdeburg
Leonie Kayser
MPI MiS
Timo Keller
Universität Würzburg
Joris Koefler
MPI MIS
Sven Logemann
C.v.O. Universität Oldenburg
Felix Lotter
MPI MiS Leipzig
Dante Luber
Paderborn Universität
Fabian Mäurer
RPTU Kaiserslautern
Konstantin Meiwald
Universität Oldenburg
Elke Neuhaus
MPI MiS
Marta Panizzut
The Arctic University of Norway
Meenakshi Paramasivan
University of Leipzig
Niharika Paul
MIS MPG Leipzig
Dmitrii Pavlov
TU Dresden
Georg Regensburger
University of Kassel
Fabian Reimers
Technische Universität München
Eva Reinert
University of Oldenburg
Marcel Salmon
Carl von Ossietzky Universität Oldenburg
Anna-Laura Sattelberger
MPI-MiS Leipzig
Leonard Schmitz
TU Berlin
Luca Sodomaco
MPI MiS
Wilken Steiner
University Siegen
Laurin Teubert
University of Passau
Angelica Torres
MPI MiS
Marcel Wack
Tu Berlin
Julian Weigert
MPI MiS/University Leipzig
Milena Wrobel
University of Oldenburg
Francesca Zaffalon
MPI MIS, Leipzig
Organizers
Anne Frühbis-Krüger
Carl von Ossietzky Universität Oldenburg
Alheydis Geiger
Max Planck Institute for Mathematics in the Sciences
Max Horn
Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau
Administrative Contact
Saskia Gutzschebauch
Max Planck Institute for Mathematics in the Sciences
Contact via Mail
Mirke Olschewski
Max Planck Institute for Mathematics in the Sciences
Contact via Mail
