math.AG

15 posts

arXiv:2311.10515v5 Announce Type: replace-cross Abstract: Cylindrical algebraic decomposition is a classical construction in real algebraic geometry. Although there are many algorithms to compute a cylindrical algebraic decomposition, their practical performance is still very limited. In this paper, we revisit this problem from a more geometric perspective, where the construction of cylindrical algebraic decomposition is related to the study of morphisms between real varieties. It is showed that the geometric fiber cardinality (geometric property) decides the existence of semi-algebraic continuous sections (semi-algebraic property). As a result, all equations can be systematically exploited in the projection phase, leading to a new simple algorithm whose efficiency is demonstrated by experimental results.

Rizeng Chen3/31/2025

arXiv:2503.22650v1 Announce Type: cross Abstract: Free tensors are tensors which, after a change of bases, have free support: any two distinct elements of its support differ in at least two coordinates. They play a distinguished role in the theory of bilinear complexity, in particular in Strassen's duality theory for asymptotic rank. Within the context of quantum information theory, where tensors are interpreted as multiparticle quantum states, freeness corresponds to a type of multiparticle Schmidt decomposition. In particular, if a state is free in a given basis, the reduced density matrices are diagonal. Although generic tensors in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$ are non-free for $n \geq 4$ by parameter counting, no explicit non-free tensors were known until now. We solve this hay in a haystack problem by constructing explicit tensors that are non-free for every $n \geq 3$. In particular, this establishes that non-free tensors exist in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$, where they are not generic. To establish non-freeness, we use results from geometric invariant theory and the theory of moment polytopes. In particular, we show that if a tensor $T$ is free, then there is a tensor $S$ in the GL-orbit closure of $T$, whose support is free and whose moment map image is the minimum-norm point of the moment polytope of $T$. This implies a reduction for checking non-freeness from arbitrary basis changes of $T$ to unitary basis changes of $S$. The unitary equivariance of the moment map can then be combined with the fact that tensors with free support have diagonal moment map image, in order to further restrict the set of relevant basis changes.

Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam3/31/2025

arXiv:2503.22653v1 Announce Type: new Abstract: Pasque et al. showed that using a tropical symmetric metric as an activation function in the last layer can improve the robustness of convolutional neural networks (CNNs) against state-of-the-art attacks, including the Carlini-Wagner attack. This improvement occurs when the attacks are not specifically adapted to the non-differentiability of the tropical layer. Moreover, they showed that the decision boundary of a tropical CNN is defined by tropical bisectors. In this paper, we explore the combinatorics of tropical bisectors and analyze how the tropical embedding layer enhances robustness against Carlini-Wagner attacks. We prove an upper bound on the number of linear segments the decision boundary of a tropical CNN can have. We then propose a refined version of the Carlini-Wagner attack, specifically tailored for the tropical architecture. Computational experiments with MNIST and LeNet5 showcase our attacks improved success rate.

Gillian Grindstaff, Julia Lindberg, Daniela Schkoda, Miruna-Stefana Sorea, Ruriko Yoshida3/31/2025

arXiv:2503.22633v1 Announce Type: new Abstract: Moment polytopes of tensors, the study of which is deeply rooted in invariant theory, representation theory and symplectic geometry, have found relevance in numerous places, from quantum information (entanglement polytopes) and algebraic complexity theory (GCT program and the complexity of matrix multiplication) to optimization (scaling algorithms). Towards an open problem in algebraic complexity theory, we prove separations between the moment polytopes of matrix multiplication tensors and unit tensors. As a consequence, we find that matrix multiplication moment polytopes are not maximal, i.e. are strictly contained in the corresponding Kronecker polytope. As another consequence, we obtain a no-go result for a natural operational characterization of moment polytope inclusion in terms of asymptotic restriction. We generalize the separation and non-maximality to moment polytopes of iterated matrix multiplication tensors. Our result implies that tensor networks where multipartite entanglement structures beyond two-party entanglement are allowed can go beyond projected entangled-pair states (PEPS) in terms of expressivity. Our proof characterizes membership of uniform points in moment polytopes of tensors, and establishes a connection to polynomial multiplication tensors via the minrank of matrix subspaces. As a result of independent interest, we extend these techniques to obtain a new proof of the optimal border subrank bound for matrix multiplication.

Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam3/31/2025

arXiv:2206.04837v4 Announce Type: replace-cross Abstract: Let $\mathcal{H}_{n,d} := \mathbb{R}[x_1$,$\ldots$, $x_n]_d$ be the set of all the homogeneous polynomials of degree $d$, and let $\mathcal{H}_{n,d}^s := \mathcal{H}_{n,d}^{\mathfrak{S}_n}$ be the subset of all the symmetric polynomials. For a semialgebraic subset of $A \subset \mathbb{R}^n$ and a vector subspace $\mathcal{H} \subset \mathcal{H}_{n,d}$, we define a PSD cone $\mathcal{P}(A$, $\mathcal{H})$ by $\mathcal{P}(A$, $\mathcal{H}) := \big\{f \in \mathcal{H}$ $\big|$ $f(a) \geq 0$ ($\forall a \in A$)$\big\}$. In this article, we study a family of extremal symmetric polynomials of $\mathcal{P}_{3,6} := \mathcal{P}(\mathbb{R}^3$, $\mathcal{H}_{3,6})$ and that of $\mathcal{P}_{4,4} := \mathcal{P}(\mathbb{R}^4$, $\mathcal{H}_{4,4})$. We also determine all the extremal polynomials of $\mathcal{P}_{3,5}^{s+} := \mathcal{P}(\mathbb{R}_+^3$, $\mathcal{H}_{3,5}^s)$ where $\mathbb{R}_+ := \big\{ x \in \mathbb{R}$, $x \geq 0 \big\}$. Some of them provide extremal polynomials of $\mathcal{P}_{3,10}$.

Tetsuya Ando3/14/2025

arXiv:2501.06217v1 Announce Type: cross Abstract: Kinematics of rigid bodies can be analyzed in many different ways. The advantage of using Euler parameters is that the resulting equations are polynomials and hence computational algebra, in particular Gr\"obner bases, can be used to study them. The disadvantage of the Gr\"obner basis methods is that the computational complexity grows quite fast in the worst case in the number of variables and the degree of polynomials. In the present article we show how to simplify computations when the mechanism contains revolute joints. The idea is based on the fact that the ideal representing the constraints of the revolute joint is not prime. Choosing the appropriate prime component reduces significantly the computational cost. We illustrate the method by applying it to the well known Bennett's and Bricard's mechanisms, but it can be applied to any mechanism which has revolute joints.

Jukka Tuomela1/14/2025

arXiv:2306.07886v4 Announce Type: replace-cross Abstract: We consider the nonconvex optimization problem associated with the decomposition of a real symmetric tensor into a sum of rank one terms. Use is made of the rich symmetry structure to construct infinite families of critical points represented by Puiseux series in the problem dimension, and so obtain precise analytic estimates on the value of the objective function and the Hessian spectrum. The results allow an analytic characterization of various obstructions to using local optimization methods, revealing in particular a complex array of saddles and minima differing by their symmetry, structure and analytic properties. A~desirable phenomenon, occurring for all critical points considered, concerns the number of negative Hessian eigenvalues increasing with the value of the objective function. Our approach makes use of Newton polyhedra as well as results from real algebraic geometry, notably the Curve Selection Lemma, to determine the extremal character of degenerate critical points, establishing in particular the existence of infinite families of third-order saddles which can significantly slow down the optimization process.

Yossi Arjevani, Gal Vinograd1/14/2025

arXiv:2501.03792v1 Announce Type: new Abstract: In this paper, we present a numerical method for rigorously finding the monodromy of linear differential equations. Beginning at a base point where certain particular solutions are explicitly given by series expansions, we first compute the value of fundamental system of solutions using interval arithmetic to rigorously control truncation and rounding errors. The solutions are then analytically continued along a prescribed contour encircling the singular points of the differential equation via a rigorous integrator. From these computations, the monodromy matrices are derived, generating the monodromy group of the differential equation. This method establishes a mathematically rigorous framework for addressing the monodromy problem in differential equations. For a notable example, we apply our computer-assisted proof method to resolve the monodromy problem for a Picard--Fuchs differential equation associated with a family of K3 toric hypersurfaces.

Toshimasa Ishige, Akitoshi Takayasu1/8/2025

arXiv:2101.03482v3 Announce Type: replace-cross Abstract: We define a new type of ideal basis called the proper basis that improves both Gr\"obner basis and Buchberger's algorithm. Let $x_1$ be the least variable of a monomial ordering in a polynomial ring $K[x_1,\dotsc,x_n]$ over a field $K$. The Gr\"obner basis of a zero-dimensional polynomial ideal contains a univariate polynomial in $x_1$. The proper basis is defined and computed in the variables $\tilde{\bm{x}}:=(x_2,\dotsc,x_n)$ with $x_1$ serving as a parameter in the algebra $K[x_1][\tilde{\bm{x}}]$. Its algorithm is more efficient than not only Buchberger's algorithm whose elimination of $\tilde{\bm{x}}$ unnecessarily involves the least variable $x_1$ but also M\"oller's algorithm due to its polynomial division mechanism. This is corroborated by a series of benchmark testings herein. The proper basis is in a modular form and neater than Gr\"obner basis and hence reduces its coefficient swell problem. It is expected that all the state of the art algorithms improving Buchberger's algorithm over the last decades can be further improved if we apply them to the proper basis.

Sheng-Ming Ma1/6/2025

arXiv:2408.14915v2 Announce Type: replace Abstract: How can Transformers model and learn enumerative geometry? What is a robust procedure for using Transformers in abductive knowledge discovery within a mathematician-machine collaboration? In this work, we introduce a Transformer-based approach to computational enumerative geometry, specifically targeting the computation of $\psi$-class intersection numbers on the moduli space of curves. By reformulating the problem as a continuous optimization task, we compute intersection numbers across a wide value range from $10^{-45}$ to $10^{45}$. To capture the recursive nature inherent in these intersection numbers, we propose the Dynamic Range Activator (DRA), a new activation function that enhances the Transformer's ability to model recursive patterns and handle severe heteroscedasticity. Given precision requirements for computing the intersections, we quantify the uncertainty of the predictions using Conformal Prediction with a dynamic sliding window adaptive to the partitions of equivalent number of marked points. To the best of our knowledge, there has been no prior work on modeling recursive functions with such a high-variance and factorial growth. Beyond simply computing intersection numbers, we explore the enumerative "world-model" of Transformers. Our interpretability analysis reveals that the network is implicitly modeling the Virasoro constraints in a purely data-driven manner. Moreover, through abductive hypothesis testing, probing, and causal inference, we uncover evidence of an emergent internal representation of the the large-genus asymptotic of $\psi$-class intersection numbers. These findings suggest that the network internalizes the parameters of the asymptotic closed-form and the polynomiality phenomenon of $\psi$-class intersection numbers in a non-linear manner.

Baran Hashemi, Roderic G. Corominas, Alessandro Giacchetto1/6/2025

arXiv:2501.00563v1 Announce Type: cross Abstract: We present a new Python package called "motives", a symbolic manipulation package based on SymPy capable of handling and simplifying motivic expressions in the Grothendieck ring of Chow motives and other types of $\lambda$-rings. The package is able to manipulate and compare arbitrary expressions in $\lambda$-rings and, in particular, it contains explicit tools for manipulating motives of several types of commonly used moduli schemes and moduli stacks of decorated bundles on curves. We have applied this new tool to advance in the verification of Mozgovoy's conjectural formula for the motive of the moduli space of twisted Higgs bundles, proving that it holds in rank 2 and 3 for any curve of genus up to 18 and any twisting bundle of small degree.

Daniel Sanchez, David Alfaya, Jaime Pizarroso1/3/2025

arXiv:2501.00657v1 Announce Type: new Abstract: Relative pose (position and orientation) estimation is an essential component of many robotics applications. Fiducial markers, such as the AprilTag visual fiducial system, yield a relative pose measurement from a single marker detection and provide a powerful tool for pose estimation. In this paper, we perform a Lie algebraic nonlinear observability analysis on a nonlinear dual quaternion system that is composed of a relative pose measurement model and a relative motion model. We prove that many common dual quaternion expressions yield Jacobian matrices with advantageous block structures and rank properties that are beneficial for analysis. We show that using a dual quaternion representation yields an observability matrix with a simple block triangular structure and satisfies the necessary full rank condition.

Nicholas B. Andrews, Kristi A. Morgansen1/3/2025

arXiv:2412.17952v1 Announce Type: cross Abstract: Similarly to the global case, the local structure of a holomorphic subvariety at a given point is described by its local irreducible decomposition. Following the paradigm of numerical algebraic geometry, an algebraic subvariety at a point is represented by a numerical local irreducible decomposition comprised of a local witness set for each local irreducible component. The key requirement for obtaining a numerical local irreducible decomposition is to compute the local monodromy action of a generic linear projection at the given point, which is always well-defined on any small enough neighborhood. We characterize some of the behavior of local monodromy action of linear projection maps under analytic continuation, allowing computations to be performed beyond a local neighborhood. With this characterization, we present an algorithm to compute the local monodromy action and corresponding numerical local irreducible decomposition for algebraic varieties. The results are illustrated using several examples facilitated by an implementation in an open source software package.

Parker B. Edwards, Jonathan D. Hauenstein12/25/2024

arXiv:2412.17099v1 Announce Type: cross Abstract: A finite group with an integral representation has two induced canonical actions, one on polynomials and one on Laurent polynomials. Knowledge about the invariants is in either case applied in many computations by means of symmetry reduction techniques, for example in algebraic systems solving or optimization. In this article, we realize the two actions as the additive action on the symmetric algebra and the multiplicative action on the group algebra of a lattice with Weyl group symmetry. By constructing explicit equivariant isomorphisms, we draw algorithmic relations between the two, which allow the transfer and preservation of representation- and invariant-theoretic properties. Our focus lies on the multiplicative coinvariant space, which is identified with the regular representation and harmonic polynomials.

Sebastian Debus, Tobias Metzlaff12/24/2024

arXiv:2403.17250v3 Announce Type: replace-cross Abstract: We use machine learning to study the moduli space of genus two curves, specifically focusing on detecting whether a genus two curve has $(n, n)$-split Jacobian. Based on such techniques, we observe that there are very few rational moduli points with small weighted moduli height and $(n, n)$-split Jacobian for $n=2, 3, 5$. We computational prove that there are only 34 genus two curves (resp. 44 curves) with (2,2)-split Jacobians (resp. (3,3)-split Jacobians) and weighted moduli height $\leq 3$. We discuss different machine learning models for such applications and demonstrate the ability to detect splitting with high accuracy using only the Igusa invariants of the curve. This shows that artificial neural networks and machine learning techniques can be highly reliable for arithmetic questions in the moduli space of genus two curves and may have potential applications in isogeny-based cryptography.

Elira Shaska, Tony Shaska12/24/2024