Daily Papers

Communication-avoiding Krylov methods require solving small dense Gram systems at each outer iteration. We present a low-synchronization approach based on Forward Gauss--Seidel (FGS), which exploits the structure of Gram matrices arising from Chebyshev polynomial bases. We show that a single FGS sweep is mathematically equivalent to Modified Gram--Schmidt (MGS) orthogonalization in the A-norm and provide corresponding backward error bounds. For weak scaling on AMD MI-series GPUs, we demonstrate that 20--30 FGS iterations preserve scalability up to 64 GPUs with problem sizes exceeding 700 million unknowns. We further extend this approach to Algebraic MultiGrid (AMG) coarse-grid solves, removing the need to assemble or factor dense coarse operators

Recent advancements in Spectral Graph Convolutional Networks (SpecGCNs) have led to state-of-the-art performance in various graph representation learning tasks. To exploit the potential of SpecGCNs, we analyze corresponding graph filters via polynomial interpolation, the cornerstone of graph signal processing. Different polynomial bases, such as Bernstein, Chebyshev, and monomial basis, have various convergence rates that will affect the error in polynomial interpolation. Although adopting Chebyshev basis for interpolation can minimize maximum error, the performance of ChebNet is still weaker than GPR-GNN and BernNet. We point out it is caused by the Gibbs phenomenon, which occurs when the graph frequency response function approximates the target function. It reduces the approximation ability of a truncated polynomial interpolation. In order to mitigate the Gibbs phenomenon, we propose to add the Gibbs damping factor with each term of Chebyshev polynomials on ChebNet. As a result, our lightweight approach leads to a significant performance boost. Afterwards, we reorganize ChebNet via decoupling feature propagation and transformation. We name this variant as ChebGibbsNet. Our experiments indicate that ChebGibbsNet is superior to other advanced SpecGCNs, such as GPR-GNN and BernNet, in both homogeneous graphs and heterogeneous graphs.

In this paper, we propose a novel top-down instance segmentation framework based on explicit shape encoding, named ESE-Seg. It largely reduces the computational consumption of the instance segmentation by explicitly decoding the multiple object shapes with tensor operations, thus performs the instance segmentation at almost the same speed as the object detection. ESE-Seg is based on a novel shape signature Inner-center Radius (IR), Chebyshev polynomial fitting and the strong modern object detectors. ESE-Seg with YOLOv3 outperforms the Mask R-CNN on Pascal VOC 2012 at mAP^r@0.5 while 7 times faster.

Shampoo is one of the leading approximate second-order optimizers: a variant of it has won the MLCommons AlgoPerf competition, and it has been shown to produce models with lower activation outliers that are easier to compress. Yet, applying Shampoo currently comes at the cost of significant computational slowdown, due to its expensive internal operations. In this paper, we take a significant step to address this shortcoming by proposing \method (for Distributed Accelerated SHampoo), a faster implementation of Distributed Shampoo based on two main new techniques: First, we show that preconditioner blocks can be stacked into 3D tensors to significantly improve GPU utilization; second, we introduce the Newton-DB iteration and the Chebyshev polynomial approximations as novel and faster approaches for computing the inverse matrix roots required by Shampoo. Along with these algorithmic contributions, we provide a first in-depth analysis of how matrix scaling critically affects Shampoo convergence. On the practical side, our GPU-aware implementation achieves up to 4.83times faster optimizer steps compared to the well-optimized Distributed Shampoo, while Newton-DB attains the lowest validation perplexity per iteration among all tested methods. Our code is available at https://github.com/IST-DASLab/DASH.

In this paper, we introduce a mesh-free two-level hybrid Tucker tensor format for approximation of multivariate functions, which combines the product Chebyshev interpolation with the ALS-based Tucker decomposition of the tensor of Chebyshev coefficients. It allows to avoid the expenses of the rank-structured approximation of function-related tensors defined on large spacial grids, while benefiting from the Tucker decomposition of the rather small core tensor of Chebyshev coefficients. This leads to nearly optimal Tucker rank parameters which are close to the results for well established Tucker-ALS algorithm applied to the large grid-based tensors. These rank parameters inherited from the Tucker-ALS decomposition of the coefficient tensor can be much less than the polynomial degrees of the initial Chebyshev interpolant via function independent basis set. Furthermore, the tensor product Chebyshev polynomials discretized on a tensor grid leads to a low-rank two-level orthogonal algebraic Tucker tensor that approximates the initial function with controllable accuracy. It is shown that our techniques could be gainfully applied to the long-range part of the electrostatic potential of multi-particle systems approximated in the range-separated tensor format. Error and complexity estimates of the proposed methods are presented. We demonstrate the efficiency of the suggested method numerically on examples of the long-range components of multi-particle interaction potentials generated by 3D Newton kernel for large bio-molecule systems and lattice-type compounds.

The original Grover's algorithm suffers from the souffle problem, which means that the success probability of quantum search decreases dramatically if the iteration time is too small or too large from the right time. To overcome the souffle problem, the fixed-point quantum search with an optimal number of queries was proposed [Phys. Rev. Lett. 113, 210501 (2014)], which always finds a marked state with a high probability when a lower bound of the proportion of marked states is given. The fixed-point quantum search relies on a key lemma regarding the explicit formula of recursive quasi-Chebyshev polynomials, but its proof is not given explicitly. In this work, we give a detailed proof of this lemma, thus providing a sound foundation for the correctness of the fixed-point quantum search. This lemma may be of independent interest as well, since it expands the mathematical form of the recursive relation of Chebyshev polynomials of the first kind, and it also constitutes a key component in overcoming the souffle problem of quantum walk-based search algorithms, for example, robust quantum walk search on complete bipartite graphs [Phys. Rev. A 106, 052207 (2022)]. Hopefully, more applications of the lemma will be found in the future.

Previously, methods for learning marginally stable linear dynamical systems either required the transition matrix to be symmetric or incurred regret bounds that scale polynomially with the system's hidden dimension. In this work, we introduce a novel method that overcomes this trade-off, achieving dimension-free regret despite the presence of asymmetric matrices and marginal stability. Our method combines spectral filtering with linear predictors and employs Chebyshev polynomials in the complex plane to construct a novel spectral filtering basis. This construction guarantees sublinear regret in an online learning framework, without relying on any statistical or generative assumptions. Specifically, we prove that as long as the transition matrix has eigenvalues with complex component bounded by 1/poly log T, then our method achieves regret O(T^{9/10}) when compared to the best linear dynamical predictor in hindsight.

The problem of computing optimal orthogonal approximation to a given matrix has attracted growing interest in machine learning. Notable applications include the recent Muon optimizer or Riemannian optimization on the Stiefel manifold. Among existing approaches, the Newton-Schulz iteration has emerged as a particularly effective solution, as it relies solely on matrix multiplications and thus achieves high computational efficiency on GPU hardware. Despite its efficiency, the method has inherent limitations - its coefficients are fixed and thus not optimized for a given matrix. In this paper we address this issue by proposing a Chebyshev-optimized version of Newton-Schulz (CANS). Based on the Chebyshev's alternance theorem, we theoretically derive optimal coefficients for the 3-rd order Newton-Schulz iteration and apply a Remez algorithm to compute optimal higher-degree polynomials. We leverage these polynomials to construct controlled approximate orthogonalization schemes, which is of interest in deep learning applications. Practically, we demonstrate the method's effectiveness in two key applications: orthogonalization in the Muon optimizer, and providing an efficient retraction alternative for Riemannian optimization on the Stiefel manifold.

We present a formalization of Gröbner basis theory in Lean 4, built on top of Mathlib's infrastructure for multivariate polynomials and monomial orders. Our development covers the core foundations of Gröbner basis theory, including polynomial division with remainder, Buchberger's criterion, and the existence and uniqueness of reduced Gröbner bases. We develop the theory uniformly for polynomial rings indexed by arbitrary types, enabling the treatment of Gröbner bases in rings with infinitely many variables. Furthermore, we connect the finite and infinite settings by showing that infinite-variable reduced Gröbner bases can be characterized via reduced Gröbner bases on finite-variable subrings through monomial-order embeddings and filter-based limit constructions.

Polynomial filters, a kind of Graph Neural Networks, typically use a predetermined polynomial basis and learn the coefficients from the training data. It has been observed that the effectiveness of the model is highly dependent on the property of the polynomial basis. Consequently, two natural and fundamental questions arise: Can we learn a suitable polynomial basis from the training data? Can we determine the optimal polynomial basis for a given graph and node features? In this paper, we propose two spectral GNN models that provide positive answers to the questions posed above. First, inspired by Favard's Theorem, we propose the FavardGNN model, which learns a polynomial basis from the space of all possible orthonormal bases. Second, we examine the supposedly unsolvable definition of optimal polynomial basis from Wang & Zhang (2022) and propose a simple model, OptBasisGNN, which computes the optimal basis for a given graph structure and graph signal. Extensive experiments are conducted to demonstrate the effectiveness of our proposed models.

In this paper we revisit the classical problem of polynomial interpolation, with a slight twist; namely, polynomial evaluations are available up to a group action of the unit circle on the complex plane. It turns out that this new setting allows for a phaseless recovery of a polynomial in a polynomial time.

Which functions can be used as activations in deep neural networks? This article explores families of functions based on orthonormal bases, including the Hermite polynomial basis and the Fourier trigonometric basis, as well as a basis resulting from the tropicalization of a polynomial basis. Our study shows that, through simple variance-preserving initialization and without additional clamping mechanisms, these activations can successfully be used to train deep models, such as GPT-2 for next-token prediction on OpenWebText and ConvNeXt for image classification on ImageNet. Our work addresses the issue of exploding and vanishing activations and gradients, particularly prevalent with polynomial activations, and opens the door for improving the efficiency of large-scale learning tasks. Furthermore, our approach provides insight into the structure of neural networks, revealing that networks with polynomial activations can be interpreted as multivariate polynomial mappings. Finally, using Hermite interpolation, we show that our activations can closely approximate classical ones in pre-trained models by matching both the function and its derivative, making them especially useful for fine-tuning tasks. These activations are available in the torchortho library, which can be accessed via: https://github.com/K-H-Ismail/torchortho.

The concept class of low-degree polynomial threshold functions (PTFs) plays a fundamental role in machine learning. In this paper, we study PAC learning of K-sparse degree-d PTFs on R^n, where any such concept depends only on K out of n attributes of the input. Our main contribution is a new algorithm that runs in time ({nd}/{epsilon})^{O(d)} and under the Gaussian marginal distribution, PAC learns the class up to error rate epsilon with O(K^{4d}{epsilon^{2d}} cdot log^{5d} n) samples even when an eta leq O(epsilon^d) fraction of them are corrupted by the nasty noise of Bshouty et al. (2002), possibly the strongest corruption model. Prior to this work, attribute-efficient robust algorithms are established only for the special case of sparse homogeneous halfspaces. Our key ingredients are: 1) a structural result that translates the attribute sparsity to a sparsity pattern of the Chow vector under the basis of Hermite polynomials, and 2) a novel attribute-efficient robust Chow vector estimation algorithm which uses exclusively a restricted Frobenius norm to either certify a good approximation or to validate a sparsity-induced degree-2d polynomial as a filter to detect corrupted samples.

We study the problem of learning hierarchical polynomials over the standard Gaussian distribution with three-layer neural networks. We specifically consider target functions of the form h = g circ p where p : R^d rightarrow R is a degree k polynomial and g: R rightarrow R is a degree q polynomial. This function class generalizes the single-index model, which corresponds to k=1, and is a natural class of functions possessing an underlying hierarchical structure. Our main result shows that for a large subclass of degree k polynomials p, a three-layer neural network trained via layerwise gradient descent on the square loss learns the target h up to vanishing test error in mathcal{O}(d^k) samples and polynomial time. This is a strict improvement over kernel methods, which require widetilde Theta(d^{kq}) samples, as well as existing guarantees for two-layer networks, which require the target function to be low-rank. Our result also generalizes prior works on three-layer neural networks, which were restricted to the case of p being a quadratic. When p is indeed a quadratic, we achieve the information-theoretically optimal sample complexity mathcal{O}(d^2), which is an improvement over prior work~nichani2023provable requiring a sample size of widetildeTheta(d^4). Our proof proceeds by showing that during the initial stage of training the network performs feature learning to recover the feature p with mathcal{O}(d^k) samples. This work demonstrates the ability of three-layer neural networks to learn complex features and as a result, learn a broad class of hierarchical functions.

We study the H-chromatic symmetric functions X_G^H (introduced in (arXiv:2011.06063) as a generalization of the chromatic symmetric function (CSF) X_G), which track homomorphisms from the graph G to the graph H. We focus first on the case of self-chromatic symmetric functions (self-CSFs) X_G^G, making some progress toward a conjecture from (arXiv:2011.06063) that the self-CSF, like the normal CSF, is always different for different trees. In particular, we show that the self-CSF distinguishes trees from non-trees with just one exception, we check using Sage that it distinguishes all trees on up to 12 vertices, and we show that it determines the number of legs of a spider and the degree sequence of a caterpillar given its spine length. We also show that the self-CSF detects the number of connected components of a forest, again with just one exception. Then we prove some results about the power sum expansions for H-CSFs when H is a complete bipartite graph, in particular proving that the conjecture from (arXiv:2011.06063) about p-monotonicity of ω(X_G^H) for H a star holds as long as H is sufficiently large compared to G. We also show that the self-CSFs of complete multipartite graphs form a basis for the ring Λ of symmetric functions, and we give some construction of bases for the vector space Λ^n of degree n symmetric functions using H-CSFs X_G^H where H is a fixed graph that is not a complete graph, answering a question from (arXiv:2011.06063) about whether such bases exist. However, we show that there generally do not exist such bases with G fixed, even with loops, answering another question from (arXiv:2011.06063). We also define the H-chromatic polynomial as an analogue of the chromatic polynomial, and ask when it is the same for different graphs.

We study the relation between equal-weight circle quadrature, Gauss--Chebyshev quadrature, and planar Minkowski reconstruction. The regular N-point grid is an mathbb S^1-design of strength N-1; a half-step rotation of the 2M-point grid projects to the classical M-point Gauss--Chebyshev rule. A common family of quadrature-error functionals gives exact identities for integration error, mixed-area error, and support-function error. For Nge3, the centered Minkowski polygon P_N with perimeter 2π has the exact Hausdorff distance from the unit disk B^2 \[ d_H(P_N,B^2)=1-\fracπ{N}\cot\fracπ{N} =π^2{3N^2}+O(N^{-4}). \] With Steiner centering, we obtain d_H(K_μ,K_ν)leπW_1(μ,ν) for balanced, nondegenerate probability measures, where W_1 uses geodesic distance. Its exponent is sharp even for smooth positive densities near the uniform measure. The identity W_1(ν_N,σ)=π/(2N) yields a general O(N^{-1}) bound for the regular grid. The sharper O(N^{-2}) rate follows from the sparse discrepancy spectrum and the inverse multiplier (1-k^2)^{-1}. Finally, a perturbation estimate gives sufficient conditions for preserving the quadratic rate and its leading constant.

We study two-step recurrences with positive step sizes and nonnegative momentum coefficients whose terminal residual is the Chebyshev minimax polynomial on a prescribed spectral interval [μ,L]. These recurrences have the same terminal error on a fixed quadratic, but their first-order responses to stepwise Hessian perturbations can differ. We prove that the sine-Jacobi recurrence of Part I is asymptotically optimal for this response norm within a factor of 1.000004, uniformly over 0<μ<L. Every terminal-exact recurrence satisfies A_Nge(2c_{cert}-o(1))N^{3/2}ε_N^star/(L-μ) with c_{cert}>1.14268353624, whereas the sine-Jacobi recurrence attains the constant 2c_{sin} with c_{sin}<1.14269218. The proof reduces the gain to the diagonal energy of a Jacobi Green matrix. A centering lift represents this matrix by an exponential kernel; packing its diagonal into a density on the line preserves the energy and controls the change in the Birman-Schwinger spectrum. A calibrated identity gives a lower bound using the ground parameter and one Fredholm determinant. Two further determinants and a trace observation improve the bound through a pointwise inequality on an explicit compact state region. One rational certificate verifies this inequality by interval arithmetic. A second certificate constructs a density satisfying the selected observations and both normalizations with energy below the sine value. Finally, no C^1 function of finitely many observations of the specified kinds gives a locally sharp lower bound at the sine density.

Recently the author presented a new approach to solving the coefficient problems for various classes of holomorphic functions f(z) = sumlimits_0^infty c_n z^n, not necessarily univalent. This approach is based on lifting the given polynomial coefficient functionals J(f) = J(c_{m_1}, dots, c_{m_s}), 2 < c_{m_1} < dots < c_{m_s} < infty, onto the Bers fiber space over universal Teichmuller space and applying the analytic and geometric features of Teichm\"{u}ller spaces, especially the Bers isomorphism theorem for Teichmuller spaces of punctured Riemann surfaces. In this paper, we extend this approach to more general classes of functions. In particular, this provides a strengthening of de Branges' theorem solving the Bieberbach conjecture.

The full shadow of a complex polynomial P of degree dge2 is the closure of all zeros of (P^n)^{(m)}, nge1, 0le m<dn. We prove that it consists of a compact connected limiting core containing all roots and critical points of P, together with isolated transient zeros, each occurring at only finitely many powers. The core is the Hausdorff limit of the zero sets pooled over all derivative orders as ntoinfty and the support of their limiting normalized root-counting measure. For m/ntoαin(0,d), we establish weak convergence of normalized root-counting measures and Hausdorff convergence of zero sets to the limiting supports, both stable under coefficient perturbations. We exhibit quartics with infinitely many transients. A bounded operator constructed from polynomial differentiators realizes the full shadow, core, and transients as its spectrum, Fredholm essential spectrum, and discrete spectrum, respectively.

In this work, we focus on a fractional differential equation in Riesz form discretized by a polynomial B-spline collocation method. For an arbitrary polynomial degree p, we show that the resulting coefficient matrices possess a Toeplitz-like structure. We investigate their spectral properties via their symbol and we prove that, like for second order differential problems, also in this case the given matrices are ill-conditioned both in the low and high frequencies for large p. More precisely, in the fractional scenario the symbol has a single zero at 0 of order α, with α the fractional derivative order that ranges from 1 to 2, and it presents an exponential decay to zero at π for increasing p that becomes faster as α approaches 1. This translates in a mitigated conditioning in the low frequencies and in a deterioration in the high frequencies when compared to second order problems. Furthermore, the derivation of the symbol reveals another similarity of our problem with a classical diffusion problem. Since the entries of the coefficient matrices are defined as evaluations of fractional derivatives of the B-spline basis at the collocation points, we are able to express the central entries of the coefficient matrix as inner products of two fractional derivatives of cardinal B-splines. Finally, we perform a numerical study of the approximation behavior of polynomial B-spline collocation. This study suggests that, in line with non-fractional diffusion problems, the approximation order for smooth solutions in the fractional case is p+2-α for even p, and p+1-α for odd p.

To model high-risk traffic densities a cellular automaton model is constructed, exhibiting Ising model-like properties. The attraction-repulsion forces between vehicles are evaluated as coupling, and the coupling function p(1-p)=g/8, where p is the initial distribution of cells with state 1, and g is the Moore neighbor count, which has roots cos^2(π/8) and sin^2(π/8) for g=1. This is achieved without the use of any trigonometric functions in the code. From the roots, the tangent polynomial tan^2(x) + tan(x) emerges. Kramers-Wannier duality is recovered and it is conjectured that the 1/2 difference between the roots serves as a fixed point for a projection mechanism from the 2-dimensional Ising model onto a 1-dimensional Ising chain through the Gudermannian function. The sigmoid evaluated at the proposed fixed point is substituted into the derivative of the logistic coupling function, σ(1/2)(1-σ(1/2)), yielding a numerical approximation to the three-dimensional Ising inverse critical coupling. Finally, the results are linked to risk densities in traffic and vehicle types, accounting for the amplification of fatal accidents.

We characterize when a banded totally positive matrix admits a positive bidiagonal factorization. In finite dimension such a factorization always exists. For semi-infinite matrices of arbitrary finite bandwidth, existence is equivalent to convergence of a finite family of positive series determined by the Metelmann factors. Their reciprocals are the limiting values of scalar Jacobi continued fractions. We also prove that every bounded banded totally positive matrix can be approximated in operator norm by matrices admitting positive bidiagonal factorizations, through perturbations confined to a fixed initial block. For banded Toeplitz matrices, the negative roots of the polynomial symbol give a global factorization with bounded factors. Ordered partitions of these roots determine explicit mixed-type multiple orthogonal polynomials. Applying the existing spectral Favard theorem, we compute their matrix of positive measures: its support is one interval, and the measure is purely absolutely continuous with an algebraic density of rank one. These formulas also give transition and first-return laws for the associated killed random walks.

Convolution is a broadly useful operation with applications including signal processing, machine learning, probability, optics, polynomial multiplication, and efficient parsing. Usually, however, this operation is understood and implemented in more specialized forms, hiding commonalities and limiting usefulness. This paper formulates convolution in the common algebraic framework of semirings and semimodules and populates that framework with various representation types. One of those types is the grand abstract template and itself generalizes to the free semimodule monad. Other representations serve varied uses and performance trade-offs, with implementations calculated from simple and regular specifications. Of particular interest is Brzozowski's method for regular expression matching. Uncovering the method's essence frees it from syntactic manipulations, while generalizing from boolean to weighted membership (such as multisets and probability distributions) and from sets to n-ary relations. The classic trie data structure then provides an elegant and efficient alternative to syntax. Pleasantly, polynomial arithmetic requires no additional implementation effort, works correctly with a variety of representations, and handles multivariate polynomials and power series with ease. Image convolution also falls out as a special case.

In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root with a prescribed multiplicity structure. More precisely, given a polynomial system f =(f_1, ldots, f_N)in C[x_1, ldots, x_n]^N, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of f such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so called inverse system that describes the multiplicity structure at the root. We use $alpha$-theory test to certify the quadratic convergence, and togive bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria.

For the polynomial f(z) in Q[z], we consider the Zsigmondy set Z(f,0) associated to the numerators of the sequence {f^n(0)}_{n geq 0}. In this paper, we provide an upper bound on the largest element of Z(f, 0). As an application, we show that the largest element of the set Z(f,0) is bounded above by 6 when f(z) = z^d + z^e +c in Q[z], with d>e geq 2 and |c|>2. Furthermore, when f(z) =z^d+c in Q[z] with |f(0)| > 2^{d{d-1}} and d >2, we also deduce a result of Krieger [Int. Math. Res. Not. IMRN, 23 (2013), pp. 5498-5525] as a consequence of our main result.

Many real-world machine learning problems involve inherently hierarchical data, yet traditional approaches rely on Euclidean metrics that fail to capture the discrete, branching nature of hierarchical relationships. We present a theoretical foundation for machine learning in p-adic metric spaces, which naturally respect hierarchical structure. Our main result proves that an n-dimensional plane minimizing the p-adic sum of distances to points in a dataset must pass through at least n + 1 of those points -- a striking contrast to Euclidean regression that highlights how p-adic metrics better align with the discrete nature of hierarchical data. As a corollary, a polynomial of degree n constructed to minimise the p-adic sum of residuals will pass through at least n + 1 points. As a further corollary, a polynomial of degree n approximating a higher degree polynomial at a finite number of points will yield a difference polynomial that has distinct rational roots. We demonstrate the practical significance of this result through two applications in natural language processing: analyzing hierarchical taxonomies and modeling grammatical morphology. These results suggest that p-adic metrics may be fundamental to properly handling hierarchical data structures in machine learning. In hierarchical data, interpolation between points often makes less sense than selecting actual observed points as representatives.

This is the third paper of the CayleyPy project applying artificial intelligence to problems in group theory. We announce the first public release of CayleyPy, an open source Python library for computations with Cayley and Schreier graphs. Compared with systems such as GAP and Sage, CayleyPy handles much larger graphs and performs several orders of magnitude faster. Using CayleyPy we obtained about 200 new conjectures on Cayley and Schreier graphs, focused on diameters and growth. For many Cayley graphs of symmetric groups Sn we observe quasi polynomial diameter formulas: a small set of quadratic or linear polynomials indexed by n mod s. We conjecture that this is a general phenomenon, giving efficient diameter computation despite the problem being NP hard. We propose a refinement of the Babai type conjecture on diameters of Sn: n^2/2 + 4n upper bounds in the undirected case, compared to previous O(n^2) bounds. We also provide explicit generator families, related to involutions in a square with whiskers pattern, conjectured to maximize the diameter; search confirms this for all n up to 15. We further conjecture an answer to a question posed by V M Glushkov in 1968 on directed Cayley graphs generated by a cyclic shift and a transposition. For nilpotent groups we conjecture an improvement of J S Ellenberg's results on upper unitriangular matrices over Z/pZ, showing linear dependence of diameter on p. Moreover. Some conjectures are LLM friendly, naturally stated as sorting problems verifiable by algorithms or Python code. To benchmark path finding we created more than 10 Kaggle datasets. CayleyPy works with arbitrary permutation or matrix groups and includes over 100 predefined generators. Our growth computation code outperforms GAP and Sage up to 1000 times in speed and size.

Linear structural equation models are multivariate statistical models encoded by mixed graphs. In particular, the set of covariance matrices for distributions belonging to a linear structural equation model for a fixed mixed graph G=(V, D,B) is parameterized by a rational function with parameters for each vertex and edge in G. This rational parametrization naturally allows for the study of these models from an algebraic and combinatorial point of view. Indeed, this point of view has led to a collection of results in the literature, mainly focusing on questions related to identifiability and determining relationships between covariances (i.e., finding polynomials in the Gaussian vanishing ideal). So far, a large proportion of these results has focused on the case when D, the directed part of the mixed graph G, is acyclic. This is due to the fact that in the acyclic case, the parametrization becomes polynomial and there is a description of the entries of the covariance matrices in terms of a finite sum. We move beyond the acyclic case and give a closed form expression for the entries of the covariance matrices in terms of the one-connections in a graph obtained from D through some small operations. This closed form expression then allows us to show that if G is simple, then the parametrization map is generically finite-to-one. Finally, having a closed form expression for the covariance matrices allows for the development of an algorithm for systematically exploring possible polynomials in the Gaussian vanishing ideal.

We identify the free half shuffle algebra of Schützenberger (1958) with an algebra of real-valued functionals on paths, where the half shuffle emulates integration of a functional against another. We then provide two, to our knowledge, new identities in arity 3 involving its commutator (area), and show that these are sufficient to recover the Zinbiel and Tortkara identities of Dzhumadil'daev (2007). We use these identities to prove that any element of the free half shuffle algebra can be expressed as a polynomial over iterated areas. Moreover, we consider minimal sets of iterated integrals defined through the recursive application of the half shuffle on Hall trees. Leveraging the duality between this set of Hall integrals and classical Hall bases of the free Lie algebra, we prove using combinatorial arguments that any element of the free half shuffle algebra can be written uniquely as a polynomial over Hall integrals. We interpret this result as a structure theorem for streamed information, loosely analogous to the unique prime factorisation of integers, allowing to split any real valued function on streamed data into two parts: a first that extracts and packages the streamed information into recursively defined atomic objects (Hall integrals), and a second that evaluates a polynomial function in these objects without further reference to the original stream. The question of whether a similar result holds if Hall integrals are replaced by Hall areas is left as an open conjecture. Finally, we construct a canonical, but to our knowledge, new decomposition of the free half shuffle algebra as shuffle power series in the greatest letter of the original alphabet with coefficients in a sub-algebra freely generated by a new alphabet with an infinite number of letters. We use this construction to provide a second proof of our structure theorem.

This paper gives an explicit isomorphic mapping from the 240 real R^{8} roots of the E_8 Gosset 4_{21} 8-polytope to two golden ratio scaled copies of the 120 root H_4 600-cell quaternion 4-polytope using a traceless 8times8 rotation matrix U with palindromic characteristic polynomial coefficients and a unitary form e^{i\mathbb{U}}. It also shows the inverse map from a single H_4 600-cell to E_8 using a 4Dhookrightarrow8D chiral leftleftrightarrowright mapping function, φ scaling, and U^{-1}. This approach shows that there are actually four copies of each 600-cell living within E_8 in the form of chiral H_{4L}oplusφH_{4L}oplusH_{4R}oplusφH_{4R} roots. In addition, it demonstrates a quaternion Weyl orbit construction of H_4-based 4-polytopes that provides an explicit mapping between E_8 and four copies of the tri-rectified Coxeter-Dynkin diagram of H_4, namely the 120-cell of order 600. Taking advantage of this property promises to open the door to as yet unexplored E_8-based Grand Unified Theories or GUTs.

We give explicit low-rank bilinear non-commutative schemes for multiplying structured n times n matrices with 2 leq n leq 5, which serve as building blocks for recursive algorithms with improved multiplicative factors in asymptotic complexity. Our schemes are discovered over F_2 or F_3 and lifted to Z or Q. Using a flip graph search over tensor decompositions, we derive schemes for general, upper-triangular, lower-triangular, symmetric, and skew-symmetric inputs, as well as products of a structured matrix with its transpose. In particular, we obtain 4 times 4 rank-34 schemes: (i) multiplying a general matrix by its transpose using 10 recursive calls, improving the factor from 26/41 (0.634) to 8/13 (0.615); and (ii) multiplying an upper-triangular matrix by a general matrix using 12 recursive calls, improving the factor from 8/13 (0.615) to 22/37 (0.595). Additionally, using F_3 flip graphs, we discover schemes over Q that fundamentally require the inverse of 2, including a 2 times 2 symmetric-symmetric multiplication of rank 5 and a 3 times 3 skew-symmetric-general multiplication of rank 14 (improving upon AlphaTensor's 15).

We give a finite cover argument for nonnegativity of the ordinary monomial coefficients of every stretched Littlewood-Richardson polynomial with partition lengths at most seven and outer size at most thirty. Explicit reductions leave 358,952 residual triples. The computational part consists of exact finite enumeration, local reduction checks and rational Ehrhart polynomial computations. Its three named dependencies are stated precisely below, separately from the mathematical implication they establish.

For a graph G with n vertices and m edges, Lin et al. Lin define the atom--bond sum-connectivity (ABS) matrix of G such that the (i,j)^{th} entry is \[ 1 - \frac{2{d_i + d_j}} \] if vertex v_i is adjacent to the vertex v_j, and 0 otherwise. In this article, we determine the characteristic polynomial of the ABS matrix for certain specific classes of graphs. Furthermore, we compute the ABS eigenvalues and the ABS energy for these classes.

Gross, Mansour, and Tucker introduced the partial-duality polynomial of a ribbon graph [Distributions, European J. Combin. 86, 1--20, 2020], the generating function enumerating partial duals by the Euler genus. Chmutov and Vignes-Tourneret wondered if this polynomial and its conjectured properties would hold for general delta-matroids, which are combinatorial abstractions of ribbon graphs. Yan and Jin contributed to this inquiry by identifying a subset of delta-matroids-specifically, even normal binary ones-whose twist polynomials are characterized by a singular term. Building upon this foundation, the current paper expands the scope of the investigation to encompass even non-binary delta-matroids, revealing that none of them have width-changing twists.

Let G be a graph with adjacency matrix A(G) and degree matrix D(G), and let L_μ(G):=A(G)-μD(G). Two graphs G_1 and G_2 are called degree-similar if there exists an invertible matrix M such that M^{-1} A(G_1) M =A(G_2) and M^{-1} D(G_1) M =D(G_2). In this paper, we address three problems concerning degree-similar graphs proposed by Godsil and Sun. First, we present a new characterization of degree-similar graphs using degree partition, from which we derive methods and examples for constructing cospectral graphs and degree-similar graphs. Second, we construct infinite pairs of non-degree-similar trees G_1 and G_2 such that tI- L_μ(G_1) and tI-L_μ(G_2) have the same Smith normal form over Q(μ)[t], which provides a negative answer to a problem posed by Godsil and Sun. Third, we establish several invariants of degree-similar graphs and obtain results on unicyclic graphs that are degree-similar determined. Lastly we prove that for a strongly regular graph G and any two edges e and f of G, G backslash e and G backslash f have identical μ-polynomial, i.e., det(tI-L_μ(G backslash e))=det(tI-L_μ(G backslash f)), which enables the construction of pairs of non-isomorphic graphs with same μ-polynomial, where G backslash e denotes the graph obtained from G by deleting the edge e.

For w in the symmetric group, we provide an exact formula for the smallest positive power q^{h(w)} appearing in the Kazhdan-Lusztig polynomial P_{e,w}(q). We also provide a tight upper bound on h(w) in simply-laced types, resolving a conjecture of Billey-Postnikov from 2002.

Reverse derivative categories (RDCs) have recently been shown to be a suitable semantic framework for studying machine learning algorithms. Whereas emphasis has been put on training methodologies, less attention has been devoted to particular model classes: the concrete categories whose morphisms represent machine learning models. In this paper we study presentations by generators and equations of classes of RDCs. In particular, we propose polynomial circuits as a suitable machine learning model. We give an axiomatisation for these circuits and prove a functional completeness result. Finally, we discuss the use of polynomial circuits over specific semirings to perform machine learning with discrete values.

Polynomial neural networks (PNNs) have been recently shown to be particularly effective at image generation and face recognition, where high-frequency information is critical. Previous studies have revealed that neural networks demonstrate a spectral bias towards low-frequency functions, which yields faster learning of low-frequency components during training. Inspired by such studies, we conduct a spectral analysis of the Neural Tangent Kernel (NTK) of PNNs. We find that the Pi-Net family, i.e., a recently proposed parametrization of PNNs, speeds up the learning of the higher frequencies. We verify the theoretical bias through extensive experiments. We expect our analysis to provide novel insights into designing architectures and learning frameworks by incorporating multiplicative interactions via polynomials.

New geometric methods for fast evaluation of derivatives of polynomial and rational B\'{e}zier curves are proposed. They apply an algorithm for evaluating polynomial or rational B\'{e}zier curves, which was recently given by the authors. Numerical tests show that the new approach is more efficient than the methods which use the famous de Casteljau algorithm. The algorithms work well even for high-order derivatives of rational B\'{e}zier curves of high degrees.

Let f(T) be a monic polynomial of degree d with coefficients in a finite field F_q. Extending earlier results in the literature, but now allowing (q,2d)>1, we give a criterion for f to satisfy the following property: for all but d^2-d-1 values of s in F_q, the probability that f(T)+sT+b is irreducible over F_q (as binF_q is chosen uniformly at random) is 1/d+O(q^{-1/2}).

This paper studies the problem of recovering cameras from a set of fundamental matrices. A set of fundamental matrices is said to be compatible if a set of cameras exists for which they are the fundamental matrices. We focus on the complete graph, where fundamental matrices for each pair of cameras are given. Previous work has established necessary and sufficient conditions for compatibility as rank and eigenvalue conditions on the n-view fundamental matrix obtained by concatenating the individual fundamental matrices. In this work, we show that the eigenvalue condition is redundant. We provide explicit homogeneous polynomials that describe necessary and sufficient conditions for compatibility in terms of the fundamental matrices and their epipoles. In this direction, we find that quadruple-wise compatibility is enough to ensure global compatibility for any number of cameras. We demonstrate that for four cameras, compatibility is generically described by triple-wise conditions and one additional equation involving all fundamental matrices.

We introduce a simple algorithm that efficiently computes tensor products of Pauli matrices. This is done by tailoring the calculations to this specific case, which allows to avoid unnecessary calculations. The strength of this strategy is benchmarked against state-of-the-art techniques, showing a remarkable acceleration. As a side product, we provide an optimized method for one key calculus in quantum simulations: the Pauli basis decomposition of Hamiltonians.

Sparse autoencoders are a standard tool for uncovering interpretable latent representations in neural networks. Yet, their interpretation depends on the inputs, making their isolated study incomplete. Polynomials offer a solution; they serve as algebraic primitives that can be analysed without reference to input and can describe structures ranging from linear concepts to complicated manifolds. This work uses bilinear autoencoders to efficiently decompose representations into quadratic polynomials. We discuss improvements that induce importance ordering, clustering, and activation sparsity. This is an initial step toward nonlinear yet analysable latents through their algebraic properties.

We introduce a Monte Carlo approach for estimating isolated polynomial zeros through their contour integral representations. For a simple zero enclosed by an isolating contour, we show that the zero can be expressed exactly as the expectation of a complex-valued random variable obtained by uniformly sampling the contour. This yields an unbiased estimator without perturbing the polynomial coefficients. We establish its variance and derive finite sample probabilistic error bounds based on concentration inequalities, with the bounds explicitly reflecting the geometry of the contour and its separation from the zeros. The framework also provides a stochastic formulation of contour based root counting and root isolation. Numerical results illustrate the estimator's behavior under varying polynomial degrees, and we further provide comparisons to existing methods.

We present an end-to-end reconfigurable algorithmic pipeline for solving a famous problem in knot theory using a noisy digital quantum computer, namely computing the value of the Jones polynomial at the fifth root of unity within additive error for any input link, i.e. a closed braid. This problem is DQC1-complete for Markov-closed braids and BQP-complete for Plat-closed braids, and we accommodate both versions of the problem. Even though it is widely believed that DQC1 is strictly contained in BQP, and so is 'less quantum', the resource requirements of classical algorithms for the DQC1 version are at least as high as for the BQP version, and so we potentially gain 'more advantage' by focusing on Markov-closed braids in our exposition. We demonstrate our quantum algorithm on Quantinuum's H2-2 quantum computer and show the effect of problem-tailored error-mitigation techniques. Further, leveraging that the Jones polynomial is a link invariant, we construct an efficiently verifiable benchmark to characterise the effect of noise present in a given quantum processor. In parallel, we implement and benchmark the state-of-the-art tensor-network-based classical algorithms for computing the Jones polynomial. The practical tools provided in this work allow for precise resource estimation to identify near-term quantum advantage for a meaningful quantum-native problem in knot theory.

We introduce Exhaustive Symbolic Integration (ESI), a method that enumerates all symbolic functions up to a given complexity k within a specified operator basis and determines which admit closed-form antiderivatives within the same class. This allows us to compute the "integrability fraction" ρ(k) (the fraction of functions whose derivatives lie within the same class), which we do for five operator bases including combinations of rational functions, powers, exponentials, logarithms and trigonometric functions. We find that ρ(k) declines at high complexity and that the operator basis has a dramatic effect -- in particular, adding the logarithm boosts ρ(k) by a factor of sim3 and produces or exacerbates a clear peak at k=6. We also deploy ESI as a novel integration algorithm, identifying three integrals that resist SymPy, Mathematica, RUBI, FriCAS, Maxima and Giac under all tested strategies. When an antiderivative can be found by multiple methods, ESI often returns the simplest form. These results reveal that the landscape of symbolic integrability is shaped primarily by the choice of operators, and that exhaustive enumeration can systematically discover integrable forms -- including novel ones -- that elude computer albegra systems.

Let f: {0,1}^n to {0, 1} be a boolean function, and let f_land (x, y) = f(x land y) denote the AND-function of f, where x land y denotes bit-wise AND. We study the deterministic communication complexity of f_land and show that, up to a log n factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f_land. This comes within a log n factor of establishing the log-rank conjecturefor AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on f such as monotonicity or low F_2-degree. Our techniques can also be used to prove (within a log n factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f_land is polynomially-related to the AND-decision tree complexity of f. The results rely on a new structural result regarding boolean functions f:{0, 1}^n to {0, 1} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials f:{0,1}^n to R with a larger range.

We study Krasner quotient hyperfields arising from finite fields, F_q/G_r, where G_rle F_q^times has index r. Building on the structure theorem of Baker--Jin, we determine the characteristic and C-characteristic of all sufficiently large such quotients: they depend only on the parity of r and, when r is even, on the residue class of q modulo 2r. In particular, the two Baker--Jin stable classes for even r are separated by characteristic 2 versus 3, while the C-characteristic is always 1. We complement this structural result with a computational laboratory: sharp Weil thresholds for Baker--Jin large-q isomorphism, empirical minimal stabilization bounds N_r^{emp}, complete finite-field quotient atlases for hyperfield orders nle 7, and comparisons with the enumerations of Ameri--Eyvazi--Hošková-Mayerová (orders le 6) and Massouros--Massouros (order 7). Among other findings, exactly 15 isomorphism types of order 7 arise as finite-field quotients, out of 277 hyperfields of that order -- a concrete data point toward the Baker--Jin rarity conjecture for quotients. All algorithms and tables are available in an open-source package suitable for independent verification and arXiv ancillary material.

This work investigates the number of limit cycles bifurcating from the periodic orbits of a linear center when it is perturbed by piecewise holomorphic systems with three zones separated by two external circles. We analyze how different geometric configurations of these zones influence the number of limit cycles. Moreover, we show the existence of at least sixteen limit cycles in fourth-degree piecewise polynomial holomorphic systems under certain configurations.

Generating functions, which are widely used in combinatorics and probability theory, encode function values into the coefficients of a polynomial. In this paper, we explore their use as a tractable probabilistic model, and propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are strictly more expressive efficient than many existing tractable probabilistic models, including determinantal point processes (DPPs), probabilistic circuits (PCs) such as sum-product networks, and tractable graphical models. We contend that PGCs are not just a theoretical framework that unifies vastly different existing models, but also show great potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks. We also highlight PGCs' connection to the theory of strongly Rayleigh distributions.

For any integer d geq 2 and prime power q, we construct unexpectedly large induced matchings in the point-line incidence graph of F_{q}^{d} by leveraging a new connection with the Furstenberg-Sárközy problem from arithmetic combinatorics. In particular, we significantly improve the previously well-known baselines when q is prime, showing that F_{q}^{2} contains matchings of size q^{1.233} and F_{q}^{d} contains matchings of size q^{d-o_{d}(1)}. These results and their proofs have several applications. First, we also obtain new constructions for finite field Nikodym sets in dimension d geq 2, improving recent results of Tao by polynomial factors. For example, when q is prime, we show the existence of Nikodym sets in F_q^d of size q^d - q^{d - o_d(1)}. Second, we construct a new minimal blocking set in PG(2,q), solving a longstanding problem in finite geometry. Third, we obtain new constructions for the minimal distance problem (in R^{2} and also in higher dimensions), improving a recent result of Logunov-Zakharov. We also obtain analogous results for general finite fields with large characteristics. In particular, in one of our constructions we introduce a new special set of points inside the norm hypersurface in F_{q}^{d}, which directly generalizes the classical Hermitian unital and which may be of independent interest for applications.

Given a remarkable representation of the generalized Pauli operators of two-qubits in terms of the points of the generalized quadrangle of order two, W(2), it is shown that specific subsets of these operators can also be associated with the points and lines of the four-dimensional projective space over the Galois field with two elements - the so-called Veldkamp space of W(2). An intriguing novelty is the recognition of (uni- and tri-centric) triads and specific pentads of the Pauli operators in addition to the "classical" subsets answering to geometric hyperplanes of W(2).

We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g. the computational basis). Our approach is based upon the intuition that noise exponentially damps non-local correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by only keeping track of the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasi-polynomial time, so long as the distribution anti-concentrates. A number of practical implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: for constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.

The second part of Hilbert's 16th problem is one of the most fundamental open problems in the qualitative theory of ordinary differential equations and dynamical systems. A central unresolved question is whether the Hilbert number H(d) is finite for arbitrary polynomial degree d. (A very recent manuscript from OpenAI asserts the finiteness of H(d); see the remark at the end of this paper.) In the absence of a general upper bound theory, most existing work constructs explicit perturbed polynomial systems to obtain improved lower bounds for H(d), while rigorous upper bound estimates remain largely unavailable. This paper focuses on improving the quantitative lower bound for polynomial systems through a systematic Hierarchical Melnikov Realization framework. We construct perturbed dynamics based on an anisotropic Chebyshev Hamiltonian, where hierarchically selected perturbation coefficients generate simple zeros of the first-order Melnikov function simultaneously across multiple disjoint period annuli. Two distinct 3-adic filtrations supply the necessary logarithmic correction factors, and a Borel--Gauss analysis establishes the required local rank condition under sufficiently strong anisotropy. As the main result of this work, we prove that H(d)=Ωbigl(d^2ln^2 dbigr), which improves the previously known lower bound by a factor of ln d. The full construction of limit cycles and the resulting dynamical bounds are formally certified using Lean 4 formal verification.

Despite the great promise of the physics-informed neural networks (PINNs) in solving forward and inverse problems, several technical challenges are present as roadblocks for more complex and realistic applications. First, most existing PINNs are based on point-wise formulation with fully-connected networks to learn continuous functions, which suffer from poor scalability and hard boundary enforcement. Second, the infinite search space over-complicates the non-convex optimization for network training. Third, although the convolutional neural network (CNN)-based discrete learning can significantly improve training efficiency, CNNs struggle to handle irregular geometries with unstructured meshes. To properly address these challenges, we present a novel discrete PINN framework based on graph convolutional network (GCN) and variational structure of PDE to solve forward and inverse partial differential equations (PDEs) in a unified manner. The use of a piecewise polynomial basis can reduce the dimension of search space and facilitate training and convergence. Without the need of tuning penalty parameters in classic PINNs, the proposed method can strictly impose boundary conditions and assimilate sparse data in both forward and inverse settings. The flexibility of GCNs is leveraged for irregular geometries with unstructured meshes. The effectiveness and merit of the proposed method are demonstrated over a variety of forward and inverse computational mechanics problems governed by both linear and nonlinear PDEs.

Quantum computation is an emerging technology with important potential for solving certain problems pivotal in various scientific and engineering disciplines. This paper introduces an efficient quantum protocol for the explicit construction of the block-encoding for an important class of Hamiltonians. Using the Schrodingerisation technique -- which converts non-conservative PDEs into conservative ones -- this particular class of Hamiltonians is shown to be sufficient for simulating any linear partial differential equations that have coefficients which are polynomial functions. The class of Hamiltonians consist of discretisations of polynomial products and sums of position and momentum operators. This construction is explicit and leverages minimal one- and two-qubit operations. The explicit construction of this block-encoding forms a fundamental building block for constructing the unitary evolution operator for this Hamiltonian. The proposed algorithm exhibits polynomial scaling with respect to the spatial partitioning size, suggesting an exponential speedup over classical finite-difference methods. This work provides an important foundation for building explicit and efficient quantum circuits for solving partial differential equations.

A complete study of an operad NC M of noncrossing configurations of chords introduced in previous work of the author is performed. This operad is defined on the linear span of all noncrossing M-cliques. These are noncrossing configurations of chords with arcs labeled by a unitary magma M. The magmatic product of M intervenes for the computation of the operadic composition of M-cliques. We show that this operad is binary, quadratic, and Koszul by considering techniques coming from rewrite systems on trees. We also compute a presentation for its Koszul dual. Finally, we explain how NC M allows one to obtain alternative constructions of already known operads like operads of formal fractions and the operad of bicolored noncrossing configurations.

In this paper, we study the ideas of composition and decomposition in the context of vector spaces, graphs and matroids. For vector spaces V_{AB}, treated as collection of row vectors, with specified column set Auplus B, we define V_{SP}lrarv V_{PQ}, Scap Q= emptyset, to be the collection of all vectors (f_S,f_Q) such that (f_S,f_P)in V_{SP}, (f_P,f_Q)in V_{PQ}. An analogous operation G_{SP}lrarg G_{PQ}equivd G_{PQ} can be defined in relation to graphs G_{SP}, G_{PQ}, on edge sets Suplus P, Puplus Q, respectively in terms of an overlapping subgraph G_P which gets deleted in the right side graph (see for instance the notion of k-sum oxley). For matroids we define the `linking' M_{SP}lrarm M_{PQ} equivd (M_{SP}vee M_{PQ})times (Suplus Q), denoting the contraction operation by 'times'. In each case, we examine how to minimize the size of the `overlap' set P, without affecting the right side entity. In the case of vector spaces, there is a polynomial time algorithm for achieving the minimum, which we present. Similar ideas work for graphs and for matroids under appropriate conditions. Next we consider the problem of decomposition. Here, in the case of vector spaces, the problem is to decompose V_{SQ} as V_{SP}lrarv V_{PQ}, with minimum size P. We give a polynomial time algorithm for this purpose. In the case of graphs and matroids we give a solution to this problem under certain restrictions.

This paper makes a formal connection between two families of widely used matrix factorization algorithms in numerical linear algebra. One family consists of the Jacobi eigenvalue algorithm and its variants for computing the Hermitian eigendecomposition and singular value decomposition. The other consists of Gaussian elimination and the Gram-Schmidt procedure with various pivoting rules for computing the Cholesky decomposition and QR decomposition respectively. Both families are cast as special cases of a more general class of factorization algorithms. We provide a randomized pivoting rule that applies to this general class (which differs substantially from the usual pivoting rules for Gaussian elimination / Gram-Schmidt) which results in the same linear rate of convergence for each algorithm, irrespective of which factorization it computes. A second important consequence of this randomized pivoting rule is a provable, effective bound on the numerical stability of the Jacobi eigenvalue algorithm, which addresses a longstanding open problem of Demmel and Veseli\'c `92.

We study first-order methods with preconditioning for solving structured nonlinear convex optimization problems. We propose a new family of preconditioners generated by symmetric polynomials. They provide first-order optimization methods with a provable improvement of the condition number, cutting the gaps between highest eigenvalues, without explicit knowledge of the actual spectrum. We give a stochastic interpretation of this preconditioning in terms of coordinate volume sampling and compare it with other classical approaches, including the Chebyshev polynomials. We show how to incorporate a polynomial preconditioning into the Gradient and Fast Gradient Methods and establish the corresponding global complexity bounds. Finally, we propose a simple adaptive search procedure that automatically chooses the best possible polynomial preconditioning for the Gradient Method, minimizing the objective along a low-dimensional Krylov subspace. Numerical experiments confirm the efficiency of our preconditioning strategies for solving various machine learning problems.

The paper ``Tropical Geometry of Deep Neural Networks'' by L. Zhang et al. introduces an equivalence between integer-valued neural networks (IVNN) with ReLU_{t} and tropical rational functions, which come with a map to polytopes. Here, IVNN refers to a network with integer weights but real biases, and ReLU_{t} is defined as ReLU_{t}(x)=max(x,t) for tinRcup{-infty}. For every poset with n points, there exists a corresponding order polytope, i.e., a convex polytope in the unit cube [0,1]^n whose coordinates obey the inequalities of the poset. We study neural networks whose associated polytope is an order polytope. We then explain how posets with four points induce neural networks that can be interpreted as 2times 2 convolutional filters. These poset filters can be added to any neural network, not only IVNN. Similarly to maxout, poset pooling filters update the weights of the neural network during backpropagation with more precision than average pooling, max pooling, or mixed pooling, without the need to train extra parameters. We report experiments that support our statements. We also define the structure of algebra over the operad of posets on poset neural networks and tropical polynomials. This formalism allows us to study the composition of poset neural network arquitectures and the effect on their corresponding Newton polytopes, via the introduction of the generalization of two operations on polytopes: the Minkowski sum and the convex envelope.

Daniel McNulty et.al (2024 J. Phys. A: Math. Theor. submitted) voiced suspicions to the Lemma 11(v) Part 6 in Chen and Yu (2017 J. Phys. A: Math. Theor. 50 475304) and three theorems derived in later publications (Liang et al 2019 Quantum Inf. Process. 18 352; Liang et al 2019 Linear Multilinear Algebra 69 2908-25; Chen et al 2021 Quantum Inf. Process. 20 353). For these suspicions, we reprove that any complex Hadamard matrix of order-six whose number of real elements more than 22 does not belong to a set of four mutually unbiased bases. We show that the number of complex Hadamard submatrices of order-two of any H2-reducible matrix is not 10,...,16,18. We also put forward some possible directions for further development.

We show how the Schur-Weyl duality that exists between the partition algebra and the symmetric group results in a stronger theoretical foundation for characterising all of the possible permutation equivariant neural networks whose layers are some tensor power of the permutation representation M_n of the symmetric group S_n. In doing so, we unify two separate bodies of literature, and we correct some of the major results that are now widely quoted by the machine learning community. In particular, we find a basis of matrices for the learnable, linear, permutation equivariant layer functions between such tensor power spaces in the standard basis of M_n by using an elegant graphical representation of a basis of set partitions for the partition algebra and its related vector spaces. Also, we show how we can calculate the number of weights that must appear in these layer functions by looking at certain paths through the McKay quiver for M_n. Finally, we describe how our approach generalises to the construction of neural networks that are equivariant to local symmetries.

This article concerns the computational complexity of a fundamental problem in number theory: counting points on curves and surfaces over finite fields. There is no subexponential-time algorithm known and it is unclear if it can be NP-hard. Given a curve, we present the first efficient Arthur-Merlin protocol to certify its point-count, its Jacobian group structure, and its Hasse-Weil zeta function. We extend this result to a smooth projective surface to certify the factor P_{1}(T), corresponding to the first Betti number, of the zeta function; by using the counting oracle. We give the first algorithm to compute P_{1}(T) that is poly(log q)-time if the degree D of the input surface is fixed; and in quantum poly(Dlog q)-time in general. Our technique in the curve case, is to sample hash functions using the Weil and Riemann-Roch bounds, to certify the group order of its Jacobian. For higher dimension varieties, we first reduce to the case of a surface, which is fibred as a Lefschetz pencil of hyperplane sections over P^{1}. The formalism of vanishing cycles, and the inherent big monodromy, enable us to prove an effective version of Deligne's `theoreme du pgcd' using the hard-Lefschetz theorem and an equidistribution result due to Katz. These reduce our investigations to that of computing the zeta function of a curve, defined over a finite field extension F_{Q}/F_{q} of poly-bounded degree. This explicitization of the theory yields the first nontrivial upper bounds on the computational complexity.

In this article, we continue the development of the Riemann-Hilbert formalism for studying the asymptotics of Toeplitz+Hankel determinants with non-identical symbols, which we initiated in GI. In GI, we showed that the Riemann-Hilbert problem we formulated admits the Deift-Zhou nonlinear steepest descent analysis, but with a special restriction on the winding numbers of the associated symbols. In particular, the most natural case, namely zero winding numbers, is not allowed. A principal goal of this paper is to develop a framework that extends the asymptotic analysis of Toeplitz+Hankel determinants to a broader range of winding-number configurations. As an application, we consider the case in which the winding numbers of the Szego-type Toeplitz and Hankel symbols are zero and one, respectively, and compute the asymptotics of the norms of the corresponding system of orthogonal polynomials.

We provide a full characterisation of all of the possible group equivariant neural networks whose layers are some tensor power of R^{n} for three symmetry groups that are missing from the machine learning literature: O(n), the orthogonal group; SO(n), the special orthogonal group; and Sp(n), the symplectic group. In particular, we find a spanning set of matrices for the learnable, linear, equivariant layer functions between such tensor power spaces in the standard basis of R^{n} when the group is O(n) or SO(n), and in the symplectic basis of R^{n} when the group is Sp(n).

Given two homogeneous spaces of the form G_1/K and G_2/K, where G_1 and G_2 are compact simple Lie groups, we study the existence problem for G_1xG_2-invariant Einstein metrics on the homogeneous space M=G_1xG_2/K. For the large subclass C of spaces having three pairwise inequivalent isotropy irreducible summands (12 infinite families and 70 sporadic examples), we obtain that existence is equivalent to the existence of a real root for certain quartic polynomial depending on the dimensions and two Killing constants, which allows a full classification and the possibility to weigh the existence and non-existence pieces of C.

Graph Neural Networks (GNN) are inherently limited in their expressive power. Recent seminal works (Xu et al., 2019; Morris et al., 2019b) introduced the Weisfeiler-Lehman (WL) hierarchy as a measure of expressive power. Although this hierarchy has propelled significant advances in GNN analysis and architecture developments, it suffers from several significant limitations. These include a complex definition that lacks direct guidance for model improvement and a WL hierarchy that is too coarse to study current GNNs. This paper introduces an alternative expressive power hierarchy based on the ability of GNNs to calculate equivariant polynomials of a certain degree. As a first step, we provide a full characterization of all equivariant graph polynomials by introducing a concrete basis, significantly generalizing previous results. Each basis element corresponds to a specific multi-graph, and its computation over some graph data input corresponds to a tensor contraction problem. Second, we propose algorithmic tools for evaluating the expressiveness of GNNs using tensor contraction sequences, and calculate the expressive power of popular GNNs. Finally, we enhance the expressivity of common GNN architectures by adding polynomial features or additional operations / aggregations inspired by our theory. These enhanced GNNs demonstrate state-of-the-art results in experiments across multiple graph learning benchmarks.

Automated proving of polynomial inequalities is a fundamental challenge in automated mathematical reasoning, where rich algebraic structure and a rapidly growing certificate search space hinder scalability. Purely symbolic approaches provide strong guarantees but often scale poorly as the number of variables or the degree increases, due to expensive algebraic manipulations and rapidly growing intermediate expressions. In parallel, LLM-guided methods have made notable progress, particularly on competition-style inequalities with a small number of variables. To address the remaining scalability challenges, we propose NSPI, a neuro-symbolic framework that combines the complementary strengths of LLMs and symbolic computation for polynomial-inequality proving. Concretely, an LLM proposes a conjecture in the form of an approximate polynomial Sum-Of-Squares (SOS) decomposition; we refine it via symbolic computation to obtain an exact polynomial SOS representation, which directly proves the target inequality, and we further certify the proof in Lean, yielding an end-to-end pipeline from heuristic discovery to machine-checked proof. Experiments on challenging benchmarks involving polynomials with up to 10 variables demonstrate the effectiveness and scalability of the proposed method.

Large Language Models (LLMs) have achieved human-level proficiency across diverse tasks, but their ability to perform rigorous mathematical problem solving remains an open challenge. In this work, we investigate a fundamental yet computationally intractable problem: determining whether a given multivariate polynomial is nonnegative. This problem, closely related to Hilbert's Seventeenth Problem, plays a crucial role in global polynomial optimization and has applications in various fields. First, we introduce SoS-1K, a meticulously curated dataset of approximately 1,000 polynomials, along with expert-designed reasoning instructions based on five progressively challenging criteria. Evaluating multiple state-of-the-art LLMs, we find that without structured guidance, all models perform only slightly above the random guess baseline 50%. However, high-quality reasoning instructions significantly improve accuracy, boosting performance up to 81%. Furthermore, our 7B model, SoS-7B, fine-tuned on SoS-1K for just 4 hours, outperforms the 671B DeepSeek-V3 and GPT-4o-mini in accuracy while only requiring 1.8% and 5% of the computation time needed for letters, respectively. Our findings highlight the potential of LLMs to push the boundaries of mathematical reasoning and tackle NP-hard problems.

Tool calling allows large language models (LLMs) to invoke external computation during problem solving, a useful capability in various fields including AI for mathematics. We study this setting through weighted sum-of-squares (SOS) decomposition, a machine-checkable route to proving polynomial nonnegativity and hence polynomial inequalities. A candidate decomposition can be checked exactly, but finding one requires choosing among non-unique regroupings and coordinating multiple symbolic transformations. We develop an agent that combines algebraic task training, symbolic tools, and verifier-grounded optimization for this task. Rather than training only on the composite SOS task, we construct 1.35 million synthetic examples covering eight supporting polynomial tasks together with weighted-SOS decomposition. We first apply supervised fine-tuning (SFT) to direct algebra problems and simulated symbolic traces, and then use Group Relative Policy Optimization (GRPO) with task-specific symbolic rewards. The SFT corpus contains no native tool-calling messages; at evaluation, the agent uses native SymPy calls for expansion, collection, reordering, and factorization. Every final SOS answer is checked by exact expansion and coefficient comparison. On held-out, same-generator synthetic problems, the full SFT+GRPO+tools system is the strongest of four evaluated configurations, reaching 78.96% verified success on weighted SOS, compared with 44.73% for the base model with the same tools, and 91.75% macro accuracy across nine polynomial tasks. Within this controlled setting, our work provides a case study of combining domain-specific skill training, executable tools, and verifier feedback, and may inform the design of tool-calling agents in other domains with exactly checkable outputs.

Phenomenological modeling of variable stars allows determination of a set of the parameters, which are needed for classification in the "General Catalogue of Variable Stars" and similar catalogs. We apply a recent method NAV ("New Algol Variable") to eclipsing binary stars of different types. Although all periodic functions may be represented as Fourier series with an infinite number of coefficients, this is impossible for a finite number of the observations. Thus one may use a restricted Fourier series, i.e. a trigonometric polynomial (TP) of order s either for fitting the light curve, or to make a periodogram analysis. However, the number of parameters needed drastically increases with decreasing width of minimum. In the NAV algorithm, the special shape of minimum is used, so the number of parameters is limited to 10 (if the period and initial epoch are fixed) or 12 (not fixed). We illustrate the NAV method by application to a recently discovered Algol-type eclipsing variable 2MASS J11080308-6145589 (in the field of previously known variable star RS Car) and compare results to that obtained using the TP fits. For this system, the statistically optimal number of parameters is 44, but the fit is still worse than that of the NAV fit. Application to the system GSC 3692-00624 argues that the NAV fit is better than the TP one even for the case of EW-type stars with much wider eclipses. Model parameters are listed.

Classical simulation of quantum physics is a central approach to investigating physical phenomena. Quantum computers enhance computational capabilities beyond those of classical resources, but it remains unclear to what extent existing limited quantum computers can contribute to this enhancement. In this work, we explore a new hybrid, efficient quantum-classical representation of quantum states, the multiple-basis representation. This representation consists of a linear combination of states that are sparse in some given and different bases, specified by quantum circuits. Such representation is particularly appealing when considering depth-limited quantum circuits within reach of current hardware. We analyze the expressivity of multiple-basis representation states depending on the classical simulability of their quantum circuits. In particular, we show that multiple-basis representation states include, but are not restricted to, both matrix-product states and stabilizer states. Furthermore, we find cases in which this representation can be used, namely approximation of ground states, simulation of deeper computations by specifying bases with shallow circuits, and a tomographical protocol to describe states as multiple-basis representations. We envision this work to open the path of simultaneous use of several hardware-friendly bases, a natural description of hybrid computational methods accessible for near-term hardware.

Ongoing efforts that span over decades show a rise of AI methods for accelerating scientific discovery, yet accelerating discovery in mathematics remains a persistent challenge for AI. Specifically, AI methods were not effective in creation of formulas for mathematical constants because each such formula must be correct for infinite digits of precision, with "near-true" formulas providing no insight toward the correct ones. Consequently, formula discovery lacks a clear distance metric needed to guide automated discovery in this realm. In this work, we propose a systematic methodology for categorization, characterization, and pattern identification of such formulas. The key to our methodology is introducing metrics based on the convergence dynamics of the formulas, rather than on the numerical value of the formula. These metrics enable the first automated clustering of mathematical formulas. We demonstrate this methodology on Polynomial Continued Fraction formulas, which are ubiquitous in their intrinsic connections to mathematical constants, and generalize many mathematical functions and structures. We test our methodology on a set of 1,768,900 such formulas, identifying many known formulas for mathematical constants, and discover previously unknown formulas for pi, ln(2), Gauss', and Lemniscate's constants. The uncovered patterns enable a direct generalization of individual formulas to infinite families, unveiling rich mathematical structures. This success paves the way towards a generative model that creates formulas fulfilling specified mathematical properties, accelerating the rate of discovery of useful formulas.

This paper presents a new state-of-the-art algorithm for exact 3times3 matrix multiplication over general non-commutative rings, achieving a rank-23 scheme with only 58 scalar additions. This improves the previous best additive complexity of 60 additions without a change of basis. The result was discovered through an automated search combining ternary-restricted flip-graph exploration with greedy intersection reduction for common subexpression elimination. The resulting scheme uses only coefficients from {-1, 0, 1}, ensuring both efficiency and portability across arbitrary fields. The total scalar operation count is reduced from 83 to 81.

Artificial Intelligence and Machine learning have been widely used in various fields of mathematical computing, physical modeling, computational science, communication science, and stochastic analysis. Approaches based on Deep Artificial Neural Networks (DANN) are very popular in our days. Depending on the learning task, the exact form of DANNs is determined via their multi-layer architecture, activation functions and the so-called loss function. However, for a majority of deep learning approaches based on DANNs, the kernel structure of neural signal processing remains the same, where the node response is encoded as a linear superposition of neural activity, while the non-linearity is triggered by the activation functions. In the current paper, we suggest to analyze the neural signal processing in DANNs from the point of view of homogeneous chaos theory as known from polynomial chaos expansion (PCE). From the PCE perspective, the (linear) response on each node of a DANN could be seen as a 1^{st} degree multi-variate polynomial of single neurons from the previous layer, i.e. linear weighted sum of monomials. From this point of view, the conventional DANN structure relies implicitly (but erroneously) on a Gaussian distribution of neural signals. Additionally, this view revels that by design DANNs do not necessarily fulfill any orthogonality or orthonormality condition for a majority of data-driven applications. Therefore, the prevailing handling of neural signals in DANNs could lead to redundant representation as any neural signal could contain some partial information from other neural signals. To tackle that challenge, we suggest to employ the data-driven generalization of PCE theory known as arbitrary polynomial chaos (aPC) to construct a corresponding multi-variate orthonormal representations on each node of a DANN to obtain Deep arbitrary polynomial chaos neural networks.

We show how to obtain improved active learning methods in the agnostic (adversarial noise) setting by combining marginal leverage score sampling with non-independent sampling strategies that promote spatial coverage. In particular, we propose an easily implemented method based on the pivotal sampling algorithm, which we test on problems motivated by learning-based methods for parametric PDEs and uncertainty quantification. In comparison to independent sampling, our method reduces the number of samples needed to reach a given target accuracy by up to 50%. We support our findings with two theoretical results. First, we show that any non-independent leverage score sampling method that obeys a weak one-sided ell_{infty} independence condition (which includes pivotal sampling) can actively learn d dimensional linear functions with O(dlog d) samples, matching independent sampling. This result extends recent work on matrix Chernoff bounds under ell_{infty} independence, and may be of interest for analyzing other sampling strategies beyond pivotal sampling. Second, we show that, for the important case of polynomial regression, our pivotal method obtains an improved bound of O(d) samples.

We provide a full characterisation of all of the possible alternating group (A_n) equivariant neural networks whose layers are some tensor power of R^{n}. In particular, we find a basis of matrices for the learnable, linear, A_n-equivariant layer functions between such tensor power spaces in the standard basis of R^{n}. We also describe how our approach generalises to the construction of neural networks that are equivariant to local symmetries.

We completely classify the atomic summands in a graph product (M,varphi) = *_{v in G} (M_v,varphi_v) of von Neumann algebras with faithful normal states. Each type I factor summand (N,psi) is a tensor product of type I factor summands (N_v,psi_v) in the individual algebras. The existence of such a summand and its weight in the direct sum can be determined from the (N_v,psi_v)'s using explicit polynomials associated to the graph.

In this paper, we present a general framework for the derivation of interesting finite combinatorial sums starting with certain classes of polynomial identities. The sums that can be derived involve products of binomial coefficients and also harmonic numbers and squared harmonic numbers. We apply the framework to discuss combinatorial sums associated with some prominent polynomial identities from the recent past.

We present the design of a flexible quantum-chemical method development framework, which supports employing any type of basis function. This design has been implemented in the light-weight program package molsturm, yielding a basis-function-independent self-consistent field scheme. Versatile interfaces, making use of open standards like python, mediate the integration of molsturm with existing third-party packages. In this way both rapid extension of the present set of methods for electronic structure calculations as well as adding new basis function types can be readily achieved. This makes molsturm well-suitable for testing novel approaches for discretising the electronic wave function and allows comparing them to existing methods using the same software stack. This is illustrated by two examples, an implementation of coupled-cluster doubles as well as a gradient-free geometry optimisation, where in both cases, an arbitrary basis functions could be used. molsturm is open-source and can be obtained from https://molsturm.org.

Let 1 le k le n, and let v_1,ldots,v_k be integral vectors in Z^n. We consider the wedge map α_{n,k} : (Z^n)^k /SL_k(Z) rightarrow wedge^k(Z^n), (v_1,ldots,v_k) rightarrow v_1 wedge cdots wedge v_k . In his Disquisitiones, Gauss proved that α_{n,2} is injective when restricted to a primitive system of vectors when defining his composition law for binary quadratic forms. He also gave an algorithm for inverting α_{3,2} in a different context on the representation of integers by ternary quadratic forms. We give here an explicit algorithm for inverting α_{n,2}, and observe via Bhargava's composition law for Z^2 otimes Z^2 otimes Z^2 cube that inverting α_{4,2} is the main algorithmic step in Gauss's composition law for binary quadratic forms. This places Gauss's composition as a special case of the geometric problem of inverting a wedge map which may be of independent interests. We also show that a given symmetric positive definite matrix A induces a natural metric on the integral Grassmannian G_{n,k}(Z) so that the map X rightarrow X^TAX becomes norm preserving.

Short-recurrence Krylov methods that are equivalent in exact arithmetic often diverge in floating-point arithmetic. To illustrate this, we provide an exactly representable two-cycle for steepest descent with a recursively updated residual. A complementary convergence theorem gives a sufficient condition under which the stored residual decreases geometrically. We then show that a second positive definite family yields different outcomes for a Hestenes--Stiefel Conjugate Gradient (CG) implementation and a direct Lanczos--Galerkin approach. CG finds the exact solution after four updates, whereas the two-step projected system becomes inconsistent. Under stated perturbation and transfer hypotheses, a common spectral enclosure gives comparable convergence bounds. For a dense, left-to-right evaluation order, we prove a sufficient precision bound for a prescribed backward error within n updates for an ntimes n matrix, together with a computable stopping test and specified exponent-range assumptions. We use polynomial estimates and numerical experiments to examine the trade-off between working precision and the number of CG iterations needed to achieve a prescribed backward error. We also compare results on inexact matrix-vector products and preconditioning with the frameworks of Paige and Greenbaum. For block Lanczos, we analyze Householder orthogonalization and singular-value truncation as the block size changes. Under componentwise and normwise error bounds, the computed coefficients satisfy a controlled local recurrence and an exact block Lanczos relation for a nearby symmetric problem in a larger space. A block form of Paige's identity bounds the overlap with a Ritz vector along its residual coordinate direction. An inter-block recurrence describes the evolution of overlap, and a Gram-matrix argument gives a count of additional nearby Ritz values.

This thesis is divided into three parts. The first part deals with cylindric plane partitions. The second with lambda-determinants and the third with commutators in semi-circular systems. For more detailed abstract please see inside. Cylindric plane partitions may be thought of as a natural generalization of reverse plane partitions. A generating series for the enumeration of cylindric plane partitions was recently given by Borodin. The first result of section one is a new bijective proof of Borodin's identity which makes use of Fomin's growth diagram framework for generalized RSK correspondences. The second result is a (q,t)-analog of Borodin's identity which extends previous work by Okada in the reverse plane partition case. The third result is an explicit combinatorial interpretation of the Macdonald weight occurring in the (q,t)-analog using the non-intersecting lattice path model for cylindric plane partitions. Alternating sign matrices were discovered by Robbins and Rumsey whilst studying λ-determinants. In the second part of this thesis we prove a multi-parameter generalization of the λ-determinant, generalizing a recent result by di Francesco. Like the original λ-determinant, our formula exhibits the Laurent phenomenon. Semicircular systems were first introduced by Voiculescu as a part of his study of von Neumann algebras. In the third part of this thesis we study certain commutator subalgebras of the semicircular system. We find a projection matrix with an interesting self-similar structure. Making use of our projection formula we given an alternative, elementary proof that the semicircular system is a factor.

We construct explicit algebraic finite Gabor windows that are simultaneously full spark and phase retrievable, with quantitative control of the self-ambiguity function. In every cyclic dimension, a constant--Chu window has an exactly computable ambiguity minimum of order N^{-3/2}; for Nge25, a two-site Chu repair has margin comparable to dN^{-3/2} for every divisor dlesqrt N. A quantitative algebraic regularization, based on the high-degree specialization principle used in explicit full-spark Gabor constructions, imposes full spark while retaining a fixed proportion of a seed's ambiguity margin. These ingredients give explicit simultaneous constructions in every cyclic dimension and a factor-sensitive improvement when N has a divisor near sqrt N. Further consequences include exact Chinese-remainder tensorization, optimal-order squarefree families, near-SIC prime regularization, lifted stability, and a finite cyclic Schrödinger construction.

Under the conditional framework breaking the longstanding O(n log n) integer multiplication barrier (originating from OpenAI Preprint #109), the asymptotic time complexity exponent T(n) = O(n (log n)^{1-κ}) is governed by bounding the second moment E[X^2] < 1 of recursive branching processes over trilinear tensor carrier graphs. In this work, we present a constructive combinatorial optimization over the alternating carrier bipartite matching graphs of the Schönhage trilinear tensor decomposition at dimensions h=23 and h=25. Through an alternating augmenting path search, we uncover a non-trivial cluster-unlocking cascade that eliminates 185 carrier roles (95 roles in h=23 and 90 roles in h=25), reducing the global physical wire width by 377,890 wires from the reviewed baseline W = 177,284,805 down to W = 176,906,915. Evaluated over the exact 10^{-14} rational grid, this wire reduction certifies an improved second-moment coefficient AB = 5,164,059 / 125,000,000,000 and establishes the sharpened conditional exponent κ= 826,215,307 / 20,000,000,000,000 \approx 4.131076535 \times 10^{-5}, strictly surpassing the preceding record on this architecture (κ\approx 4.123864 \times 10^{-5}). All 47 polynomial constraints and 7 rational security margins are audited in exact Q-arithmetic with zero floating-point error, and the fundamental wire reduction identity is formally verified in the Lean 4 interactive theorem prover without unproven axioms.

Matrix multiplication optimization remains a fundamental challenge in computational mathematics. This work introduces a novel approach that discovers matrix multiplication schemes in the ternary field (Z_T), where coefficients are restricted to {-1, 0, 1} to minimize naive additive complexity. The core of the method is a GPU-accelerated meta flip graph algorithm that maintains ternary safety through specialized arithmetic operations and sign symmetry breaking. Key results include new best ranks for the formats 4 times 5 times 12, 5 times 6 times 10, and 6 times 7 times 9, the independent discovery of 32 schemes in Z_T that match known optimal ranks (including 8 previously known only with rational coefficients), and 30 rank improvements in the binary field. The analysis of 164 known schemes shows that 92 can be implemented in Z_T, while 72 could not be found in the ternary field with current methods, defining the current boundaries of this approach. All software, results, and discovered schemes are provided as open-source.

Kolmogorov-Arnold Networks (KANs) place learnable B-spline activations on network edges rather than fixed activations on nodes. The standard Cox-de Boor recursion evaluates these activations through k sequential passes for degree-k splines, consuming over 90% of forward-pass time. InKAN replaces this recursion with the truncated power form, a classical result from approximation theory that expresses each uniform cubic B-spline as five (x)_+^3 terms at shifted knot positions. The resulting expression computes exact B-spline basis values: the same mathematical function as the Cox-de Boor recursion, evaluated without sequential passes. This paper documents three contributions: (1) an implementation structured for torch . compile fusion, eliminating recursion, span lookup, and scatter-gather operations; (2) a bounded-coordinate evaluation that clamps the normalized input to [0, k{+}1], preventing the growth of cancellation error at large off-support coordinates; and (3) an open-source package (pip install inkan). In the tested configurations, InKAN has 2.8--3.5times lower forward-pass latency than the Cox-de Boor recursion. Partition-of-unity errors remain below 10^{-5} for grid sizes up to 200.

Given the damping factor α and precision tolerance ε, andersen2006local introduced Approximate Personalized PageRank (APPR), the de facto local method for approximating the PPR vector, with runtime bounded by Θ(1/(αε)) independent of the graph size. Recently, fountoulakis2022open asked whether faster local algorithms could be developed using O(1/(sqrtαε)) operations. By noticing that APPR is a local variant of Gauss-Seidel, this paper explores the question of whether standard iterative solvers can be effectively localized. We propose to use the locally evolving set process, a novel framework to characterize the algorithm locality, and demonstrate that many standard solvers can be effectively localized. Let operatorname{vol}{ (S_t)} and overlineγ_{t} be the running average of volume and the residual ratio of active nodes textstyle S_{t} during the process. We show operatorname{vol}{ (S_t)}/overlineγ_{t} leq 1/ε and prove APPR admits a new runtime bound O(operatorname{vol}(S_t)/(αoverlineγ_{t})) mirroring the actual performance. Furthermore, when the geometric mean of residual reduction is Θ(sqrtα), then there exists c in (0,2) such that the local Chebyshev method has runtime O(operatorname{vol}(S_{t})/(sqrtα(2-c))) without the monotonicity assumption. Numerical results confirm the efficiency of this novel framework and show up to a hundredfold speedup over corresponding standard solvers on real-world graphs.

We study the matrix models pi:C(S_N^+)to M_N(C(X)) which are flat, in the sense that the standard generators of C(S_N^+) are mapped to rank 1 projections. Our first result is a generalization of the Pauli matrix construction at N=4, using finite groups and 2-cocycles. Our second result is the construction of a universal representation of C(S_N^+), inspired from the Sinkhorn algorithm, that we conjecture to be inner faithful.

The analysis of the spectral features of a Toeplitz matrix-sequence left{T_{n}(f)right}_{ninmathbb N}, generated by a symbol fin L^1([-π,π]), real-valued almost everywhere (a.e.), has been provided in great detail in the last century, as well as the study of the conditioning, when f is nonnegative a.e. Here we consider a novel type of problem arising in the numerical approximation of distributed-order fractional differential equations (FDEs), where the matrices under consideration take the form \[ T_{n}=c_0T_{n}(f_0)+c_{1} h^h T_{n}(f_{1})+c_{2} h^{2h} T_{n}(f_{2})+\cdots+c_{n-1} h^{(n-1)h}T_{n}(f_{n-1}), \] c_0,c_{1},ldots, c_{n-1} in [c_*,c^*], c^*ge c_*>0, independent of n, h=1{n}, f_jsim g_j, g_j=|θ|^{2-jh}, j=0,ldots,n-1. Since the resulting generating function depends on n, the standard theory cannot be applied and the analysis has to be performed using new ideas. Few selected numerical experiments are presented, also in connection with matrices that come from distributed-order FDE problems, and the adherence with the theoretical analysis is discussed together with open questions and future investigations.

The total variation (TV)-seminorm is considered for piecewise polynomial, globally discontinuous (DG) and continuous (CG) finite element functions on simplicial meshes. A novel, discrete variant (DTV) based on a nodal quadrature formula is defined. DTV has favorable properties, compared to the original TV-seminorm for finite element functions. These include a convenient dual representation in terms of the supremum over the space of Raviart--Thomas finite element functions, subject to a set of simple constraints. It can therefore be shown that a variety of algorithms for classical image reconstruction problems, including TV-L^2 and TV-L^1, can be implemented in low and higher-order finite element spaces with the same efficiency as their counterparts originally developed for images on Cartesian grids.

We present an elementary, self-contained proof of Grothendieck's inequality that unifies the real and complex cases and yields both the Krivine and Haagerup bounds, the current best-known explicit bounds for the real and complex Grothendieck constants respectively. This article is intended to be pedagogical, combining and streamlining known ideas of Lindenstrauss--Pe{\l}czy\'nski, Krivine, and Haagerup into a proof that need only univariate calculus, basic complex variables, and a modicum of linear algebra as prerequisites.

Despite the success of neural networks (NNs), there is still a concern among many over their "black box" nature. Why do they work? Here we present a simple analytic argument that NNs are in fact essentially polynomial regression models. This view will have various implications for NNs, e.g. providing an explanation for why convergence problems arise in NNs, and it gives rough guidance on avoiding overfitting. In addition, we use this phenomenon to predict and confirm a multicollinearity property of NNs not previously reported in the literature. Most importantly, given this loose correspondence, one may choose to routinely use polynomial models instead of NNs, thus avoiding some major problems of the latter, such as having to set many tuning parameters and dealing with convergence issues. We present a number of empirical results; in each case, the accuracy of the polynomial approach matches or exceeds that of NN approaches. A many-featured, open-source software package, polyreg, is available.

The kernel of a binary code containing the zero word partitions the binary coordinates into blocks, two coordinates lying in the same block when every kernel word takes the same value in both, and the kernel-block rank profile is the multiset of the dimensions of its linear span punctured on those blocks. For the family H^{t_1,t_2,t_3} of Z_2Z_4Z_8-linear Hadamard codes, this invariant is known explicitly and gives a complete classification of the family. In this paper, we compute it for the Z_2Z_4-linear and Z_{2^s}-linear Hadamard families with which those codes are compared, and we prove that it is constant for every nonlinear Z_2Z_4-linear Hadamard code and for every nonlinear Z_{2^s}-linear Hadamard code bar H^{a_1,dots,a_s} with sgeq2. The second statement is obtained without any rank formula, by exhibiting coordinate permutations that preserve the code and act transitively on its kernel blocks, which makes the argument uniform in s. We also prove a descent theorem: if bar H^{a_1,dots,a_s} is nonlinear and a_1geq2, then the code punctured on one kernel block is the Z_{2^{s-1}}-linear Hadamard code bar H^{a_1,dots,a_{s-1}}. Consequently, the constant local rank equals rank(bar H^{a_1,dots,a_{s-1}}) and is at least t-κ+2, where 2^t is the length and κ the kernel dimension. These results separate every nonlinear Z_2Z_4Z_8-linear Hadamard code from every Z_4-linear, Z_2Z_4-linear and Z_{2^s}-linear Hadamard code of the same length, except for the single infinite family H^{1,1,t-4} and bar H^{2,0,t-5} with tgeq5. The members of this infinite family agree in the rank, kernel dimension and the kernel-block rank profile, but a two-block refinement separates them.

Two geometric spaces are in the same topological class if they are related by certain geometric deformations. We propose machine learning methods that automate learning of topological invariance and apply it in the context of knot theory, where two knots are equivalent if they are related by ambient space isotopy. Specifically, given only the knot and no information about its topological invariants, we employ contrastive and generative machine learning techniques to map different representatives of the same knot class to the same point in an embedding vector space. An auto-regressive decoder Transformer network can then generate new representatives from the same knot class. We also describe a student-teacher setup that we use to interpret which known knot invariants are learned by the neural networks to compute the embeddings, and observe a strong correlation with the Goeritz matrix in all setups that we tested. We also develop an approach to resolving the Jones Unknot Conjecture by exploring the vicinity of the embedding space of the Jones polynomial near the locus where the unknots cluster, which we use to generate braid words with simple Jones polynomials.

Motivated by W. P. Thurston, we ask: What is the shape of a meromorphic function on a simply connected Riemann surface Ω_z? We consider Speiser functions, i.e. meromorphic functions on a simply connected Riemann surface, that have a finite number q at least 2 of singular (critical or asymptotic) values. As a first result, we make precise the correspondence between: Speiser functions w(z), Speiser Riemann surfaces R_w(z), Speiser q-tessellation, and analytic Speiser graphs of index q. As the second main result, we characterize tessellations with alternating colors (equivalently abstract pre-Speiser graphs) that are realized by Speiser functions on Ω_z. The characterization is in terms of the q-regular extension problem of bipartite planar graphs. As third main results, the Speiser Riemann surface R_w(z) can be constructed by isometric glueing of a finite number of types of sheets, where each sheet is a maximal domain of single-valuedness of the inverse of w(z). Furthermore, a unique decomposition of R_w(z) into maximal logarithmic towers and a soul is provided. Using vector fields we recognize that logarithmic towers come in two flavors: exponential or h-tangent blocks, directly related to the exponential or the hyperbolic tangent functions on the upper half plane. The surface R_w(z) of a finite Speiser function is characterized by surgery of a rational block and a finite number of exponential or h-tangent blocks.

Developing equivariant neural networks for the E(3) group plays an important role in modeling 3D data across real-world applications. Enforcing this equivariance primarily involves the tensor products of irreducible representations (irreps). However, the computational complexity of such operations increases significantly as higher-order tensors are used. In this work, we propose a systematic approach to substantially accelerate the computation of the tensor products of irreps. We mathematically connect the commonly used Clebsch-Gordan coefficients to the Gaunt coefficients, which are integrals of products of three spherical harmonics. Through Gaunt coefficients, the tensor product of irreps becomes equivalent to the multiplication between spherical functions represented by spherical harmonics. This perspective further allows us to change the basis for the equivariant operations from spherical harmonics to a 2D Fourier basis. Consequently, the multiplication between spherical functions represented by a 2D Fourier basis can be efficiently computed via the convolution theorem and Fast Fourier Transforms. This transformation reduces the complexity of full tensor products of irreps from O(L^6) to O(L^3), where L is the max degree of irreps. Leveraging this approach, we introduce the Gaunt Tensor Product, which serves as a new method to construct efficient equivariant operations across different model architectures. Our experiments on the Open Catalyst Project and 3BPA datasets demonstrate both the increased efficiency and improved performance of our approach.

Neural networks are famously nonlinear. However, linearity is defined relative to a pair of vector spaces, f:XtoY. Is it possible to identify a pair of non-standard vector spaces for which a conventionally nonlinear function is, in fact, linear? This paper introduces a method that makes such vector spaces explicit by construction. We find that if we sandwich a linear operator A between two invertible neural networks, f(x)=g_y^{-1}(A g_x(x)), then the corresponding vector spaces X and Y are induced by newly defined addition and scaling actions derived from g_x and g_y. We term this kind of architecture a Linearizer. This framework makes the entire arsenal of linear algebra, including SVD, pseudo-inverse, orthogonal projection and more, applicable to nonlinear mappings. Furthermore, we show that the composition of two Linearizers that share a neural network is also a Linearizer. We leverage this property and demonstrate that training diffusion models using our architecture makes the hundreds of sampling steps collapse into a single step. We further utilize our framework to enforce idempotency (i.e. f(f(x))=f(x)) on networks leading to a globally projective generative model and to demonstrate modular style transfer.

The solution of Shareshian-Wachs conjecture by Brosnan-Chow and Guay-Paquet tied the graded chromatic symmetric functions on indifference graphs (or unit interval graphs) and the cohomology of regular semisimple Hessenberg varieties with the dot action. A similar result holds between unicellular LLT polynomials and twins of regular semisimple Hessenberg varieties. A recent result by Abreu-Nigro enabled us to prove these results by showing the modular law for the geometrical objects, and this is indeed done by Precup-Sommers and Kiem-Lee. In this paper, we give elementary and simpler proofs to the modular law through GKM theory.

This paper is devoted to the classification and studying properties of complex unital 3-dimensional structurable algebras. We provide a complete list of non-isomorphic classes, identifying five algebras for type (2, 1) and two algebras for type (1, 2). For each obtained algebra, we describe the derivation algebra, the automorphism group, the lattice of subalgebras and ideals, and functional identities of degree 2. Furthermore, we investigate the Allison-Kantor construction for the classified algebras. We determine the structure of the resulting Z-graded Lie algebras, providing their dimensions and Levi decompositions.

We construct Feynman rules for Lindblad master equations in the operator language of quantum optics: a fixed algebra of elementary operator moves and closed-form propagators for perturbation theory about an exactly solvable, in most cases Gaussian, generator. The expansion separates into a kinematic part (the shift algebra on the Wick-ordered eigenoperators O_{mn}=:(c^dagger)^m c^n:, from which the vertex table for a specified interaction is assembled) and a dynamical part that enters only through the resolvent of the unperturbed generator, diagonal and additive for any stable, diagonalizable Gaussian L_0, including thermal and squeezed reservoirs and correlated decay, and equally available for a two-level emitter, driven or undriven. In the driven Kerr cavity the loop expansion is the semiclassical expansion and the series is asymptotic. In a strongly driven two-level atom, dressed lines replace a series of finite radius by one accurate deep into saturation, one line per Mollow component. For Kerr rings and chains the cost is polynomial in the number of sites at fixed perturbative order. On a three-site ring the diagrams recover the non-Gaussian part of the three-photon correlation that the Gaussian cumulant closure lacks; carried to tenth order they give the smallest g^{(3)} error of the methods compared for Uleq0.25κ at a cost below that of a fourth-order closure, and third- and fourth-order closures are more accurate at moderate coupling. The same rules, extended to the counting-field-tilted generator, give the photon-counting cumulants of a disordered eight-site chain beyond direct diagonalization; quantum-jump trajectories at three couplings agree with them to within 1.6 standard errors, within one at the strongest coupling, where they place the third cumulant six standard errors above the Gaussian value.

Let r_n be the infimum of \[ \lVert P'-P'(0)P\rVert_{H^2}{\lVert P\rVert_{H^2}} \] over all degree-n polynomials P satisfying P(0)=1 whose zeros lie in the closed unit disk. We prove the quantitative residual bound \[ r_n\geq \exp\!\bigl(-(1+o(1))\sqrt n\log n\bigr) \qquad(n\to\infty). \] As an application, we answer Erdős Problem 973 on exterior power sums in the negative, in a form quantitatively stronger than the answer first obtained by Luo, Yang, and Zhu.

The asymptotic safety conjecture is examined for quantum gravity in four dimensions. Using the renormalisation group, we find evidence for an interacting UV fixed point for polynomial actions up to the 34th power in the Ricci scalar. The extrapolation to infinite polynomial order is given, and the self-consistency of the fixed point is established using a bootstrap test. All details of our analysis are provided. We also clarify further aspects such as stability, convergence, the role of boundary conditions, and a partial degeneracy of eigenvalues. Within this setting we find strong support for the conjecture.

The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its L_1-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most Γ, Klivans et al. (2008) show that degree d = O(Γ^2 / varepsilon^4) suffices to achieve an varepsilon-approximation. This leads to the best-known bounds on the complexity of learning a variety of concept classes. In this note, we improve their analysis by showing that degree d = tilde O (Γ^2 / varepsilon^2) is enough. In light of lower bounds due to Diakonikolas et al. (2021), this yields (near) optimal bounds on the complexity of agnostically learning polynomial threshold functions in the statistical query model. Our proof relies on a direct analogue of a construction of Feldman et al. (2020), who considered L_1-approximation on the Boolean hypercube.

Quantum algorithms offer significant speedups over their classical counterparts for a variety of problems. The strongest arguments for this advantage are borne by algorithms for quantum search, quantum phase estimation, and Hamiltonian simulation, which appear as subroutines for large families of composite quantum algorithms. A number of these quantum algorithms were recently tied together by a novel technique known as the quantum singular value transformation (QSVT), which enables one to perform a polynomial transformation of the singular values of a linear operator embedded in a unitary matrix. In the seminal GSLW'19 paper on QSVT [Gily\'en, Su, Low, and Wiebe, ACM STOC 2019], many algorithms are encompassed, including amplitude amplification, methods for the quantum linear systems problem, and quantum simulation. Here, we provide a pedagogical tutorial through these developments, first illustrating how quantum signal processing may be generalized to the quantum eigenvalue transform, from which QSVT naturally emerges. Paralleling GSLW'19, we then employ QSVT to construct intuitive quantum algorithms for search, phase estimation, and Hamiltonian simulation, and also showcase algorithms for the eigenvalue threshold problem and matrix inversion. This overview illustrates how QSVT is a single framework comprising the three major quantum algorithms, thus suggesting a grand unification of quantum algorithms.

Strategies for the generation of periodic discrete structures with identical two-point correlation are developed. Starting from a pair of root structures, which are not related by translation, phase inversion or axis reflections, child structures of arbitrary resolution (i.e., pixel or voxel numbers) and number of phases (i.e., material phases/species) can be generated by means of trivial embedding based phase extension, application of kernels and/or phase coalescence, such that the generated structures inherit the two-point-correlation equivalence. Proofs of the inheritance property are provided by means of the Discrete Fourier Transform theory. A Python 3 implementation of the results is offered by the authors through the Github repository https://github.com/DataAnalyticsEngineering/EQ2PC in order to make the provided results reproducible and useful for all interested readers. Examples for the generation of structures are demonstrated, together with applications in the homogenization theory of periodic media.

This paper presents the first numerical realization of Suzuki's Weil-Quadratic-Form operator, a candidate for the Hilbert--Pólya program linking spectral positivity to the Riemann Hypothesis (RH). Suzuki's 2026 construction was purely theoretical; here, the operator is instantiated via P1 finite-element discretization and Richardson extrapolation. Key results include: (R1) In the prime-free regime, the spectrum follows a closed Archimedean law A_k(a) = log(1/a) + log(k-2) + B_0 + O(a), with B_0 = log q - 2log 2, confirmed to 30-digit precision. (R2) A Mellin double-pole argument proves the head coefficient B(ν) and shows B_0 depends only on the conductor q, independent of the Archimedean parameter. (R2b) The degree d of an L-function appears directly as the logarithmic slope of the spectrum. (R3) Total spectral intensity follows the prime number theorem, S(a) sim (2a)^3/6. (R4) Nontrivial zeros are not eigenvalues but occur in the explicit-formula error term of the prime symbol. (R5) The best-match line σ^*(a) descends toward the critical line. (R6) Weil's positivity criterion is realized in operator form: bounded residual growth corresponds to all zeros on the line, while an injected off-line zero causes exponential blow-up. (R7) The lowest eigenvalue λ_1(a) is strictly positive, decays superexponentially, and passes smoothly through the first prime threshold. (R8) The characteristic function W(a,0;z) is computed for the first time, with all zeros confirmed real. (R9) Indirect traces of GUE statistics appear in the moment structure, even where direct detection is blocked. The authors emphasize that this work does not prove RH. All results are Archimedean and universal, with significance lying in the faithful numerical realization of classical identities rather than new arithmetic.

We study orbits in a family of Markoff-like surfaces with extra off-diagonal terms over prime fields F_p. It is shown that, for a typical surface of this form, every non-trivial orbit has size divisible by p. This extends a theorem of W.Y. Chen from the Markoff surface itself to others in this family. The proof closely follows and elaborates on a recent argument of D.E. Martin. We expect that there is just one orbit generically. For some special parameters, we prove that there are at least two or four orbits. Cayley's cubic surface plays a role in parametrising the exceptional cases and dictating the number of solutions mod p.

We begin the study of list-decodable linear regression using batches. In this setting only an alpha in (0,1] fraction of the batches are genuine. Each genuine batch contains ge n i.i.d. samples from a common unknown distribution and the remaining batches may contain arbitrary or even adversarial samples. We derive a polynomial time algorithm that for any nge tilde Omega(1/alpha) returns a list of size mathcal O(1/alpha^2) such that one of the items in the list is close to the true regression parameter. The algorithm requires only mathcal{O}(d/alpha^2) genuine batches and works under fairly general assumptions on the distribution. The results demonstrate the utility of batch structure, which allows for the first polynomial time algorithm for list-decodable regression, which may be impossible for the non-batch setting, as suggested by a recent SQ lower bound diakonikolas2021statistical for the non-batch setting.

This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. This family of methods arises in many machine learning tasks and is used to obtain approximate solutions of a linear system Atheta = b for which A and b can only be accessed through random estimates {({bf A}_n, {bf b}_n): n in N^*}. Our analysis is based on new results regarding moments and high probability bounds for products of matrices which are shown to be tight. We derive high probability bounds on the performance of LSA under weaker conditions on the sequence {({bf A}_n, {bf b}_n): n in N^*} than previous works. However, in contrast, we establish polynomial concentration bounds with order depending on the stepsize. We show that our conclusions cannot be improved without additional assumptions on the sequence of random matrices {{bf A}_n: n in N^*}, and in particular that no Gaussian or exponential high probability bounds can hold. Finally, we pay a particular attention to establishing bounds with sharp order with respect to the number of iterations and the stepsize and whose leading terms contain the covariance matrices appearing in the central limit theorems.

We study the realizability of simplicial complexes with a given pair of integer sequences, representing the node degree distribution and the facet size distribution, respectively. While the s-uniform variant of the problem is NP-complete when s geq 3, we identify two populations of input sequences, most of which can be solved in polynomial time using a recursive algorithm that we contribute. Combining with a sampler for the simplicial configuration model [J.-G. Young et al., Phys. Rev. E 96, 032312 (2017)], we facilitate the efficient sampling of simplicial ensembles from arbitrary degree and size distributions. We find that, contrary to expectations based on dyadic networks, increasing the nodes' degrees reduces the number of loops in simplicial complexes. Our work unveils a fundamental constraint on the degree-size sequences and sheds light on further analysis of higher-order phenomena based on local structures.

The tensor rank of a bilinear map is the least number of multiplications any bilinear algorithm needs to compute it; for the multiplication of an algebra it measures how cheaply the algebra can be multiplied at all. For the even-dimensional real normed division algebras it is 3 for the complex numbers and 8 for the quaternions, both classical, while for the octonions O only a range was known: at least 15 (Fiduccia and Zalcstein, 1977) and at most 30 (Cariow and Cariowa). We prove $18 le R_{R}(T_{O}) le 25. The lower bound peels the eight slices of T_{O} down to two and bounds the rank of the surviving pencil through the octonion norm. Nothing in it is special to dimension 8: the same steps give R_{R}(T_A) \ge 5{2}n - 2 for every real normed division algebra A of even dimension n, sharp for C and H and the best bound we know for O. The upper bound is a separate construction, an explicit rank-25 decomposition certified by a Krawczyk argument, in exact rational arithmetic, to sit within 10^{-6} of an exact one. The same two arguments pin down the rank of a smaller three-slice quaternion tensor τ, giving R_{R}(τ) = 7$. The Lean 4 kernel checks the lower bounds and the Krawczyk existence principle; the accompanying scripts check the certificate's finitely many exact-rational inequalities.

For any graph G having n vertices and its automorphism group Aut(G), we provide a full characterisation of all of the possible Aut(G)-equivariant neural networks whose layers are some tensor power of R^{n}. In particular, we find a spanning set of matrices for the learnable, linear, Aut(G)-equivariant layer functions between such tensor power spaces in the standard basis of R^{n}.

This paper presents several notable properties of the matrix U shown to be related to the isomorphism between H_4 and E_8. The most significant of these properties is that U.U is to rank 8 matrices what the golden ratio is to numbers. That is to say, the difference between it and its inverse is the identity element, albeit with a twist. Specifically, U.U- (U.U)^{-1} is the reverse identity matrix or standard involutory permutation matrix of rank 8. It has the same palindromic characteristic polynomial coefficients as the normalized 3-qubit Hadamard matrix with 8-bit binary basis states, which is known to be isomorphic to E8 through its (8,4) Hamming code.

We present Neural Spectral Methods, a technique to solve parametric Partial Differential Equations (PDEs), grounded in classical spectral methods. Our method uses orthogonal bases to learn PDE solutions as mappings between spectral coefficients. In contrast to current machine learning approaches which enforce PDE constraints by minimizing the numerical quadrature of the residuals in the spatiotemporal domain, we leverage Parseval's identity and introduce a new training strategy through a spectral loss. Our spectral loss enables more efficient differentiation through the neural network, and substantially reduces training complexity. At inference time, the computational cost of our method remains constant, regardless of the spatiotemporal resolution of the domain. Our experimental results demonstrate that our method significantly outperforms previous machine learning approaches in terms of speed and accuracy by one to two orders of magnitude on multiple different problems. When compared to numerical solvers of the same accuracy, our method demonstrates a 10times increase in performance speed.

Local heights are arithmetic invariants used in the quadratic Chabauty method for determining the rational points on curves. We present an algorithm to compute these local heights for hyperelliptic curves at odd primes ellneq p. This algorithm significantly broadens the applicability of quadratic Chabauty to curves which were previously inaccessible due to the presence of non-trivial local heights. We provide numerous examples, including the first quadratic Chabauty computation for a curve having two primes with non-trivial local heights.

Quantum kernels are among the most promising methods in quantum machine learning, providing a natural way to embed data into high-dimensional Hilbert spaces via quantum circuits and capturing non-linear relationships in data. Their learning behaviour is governed by the function class they represent, which is formally characterized by the structure of the associated Reproducing Kernel Hilbert Space (RKHS). However, a theoretical characterization of this function class, and of how it depends on the choice of feature map and its hyperparameters, is still lacking. In this work, we focus on the Instantaneous Quantum Polynomial (IQP) feature map and derive a Fourier representation of the associated RKHS generators as finite sums of trigonometric functions evaluated on polynomially transformed input variables, with a finite set of accessible frequencies determined by the circuit construction and scaled by the bandwidth hyperparameter. This representation identifies three bandwidth regimes with qualitatively distinct expressive properties from localised, through multimodal, to periodic. Numerical experiments on synthetic datasets with controlled periodic and multimodal structure, across data dimensions and feature-map configurations, reproduce the three regimes in both supervised classification and unsupervised anomaly detection, benchmarked against a classical Gaussian kernel. These results make the relationship between expressivity and data structure explicit for IQP kernels: expressive power translates into a practical benefit only when the accessible frequencies match with the structure of the data, which provides a criterion for selecting the bandwidth when the periodic or multimodal structure of data is known.

We develop a bottom-up framework to reconstruct the asymptotic spectrum of light towers in four-dimensional N=1 effective field theories directly from their Kähler potential. Our construction uses the Integral Scaling Relation, which relates the mass scales of towers becoming light at infinite distance to the tensions of EFT strings, together with the Emergent String Conjecture applied recursively upon decompactification. These conditions organize the tower scaling vectors into a lattice generated by the EFT-string vectors and select the globally consistent tower polytopes. When applied to Kähler potentials arising from string compactifications, our algorithm precisely reproduces the known arrangements of towers and duality frames. We then classify the admissible polytopes for asymptotic Kähler potentials Ksim-log P(s), with P(s) a homogeneous polynomial of degree at most seven, and show that certain apparently consistent Kähler potentials are incompatible with the assumed quantum-gravity constraints. For general polynomials, additional restrictions arise from gluing the tower arrangements across different growth sectors. Remarkably, every tower polytope allowed by our reconstruction can be obtained as a concrete slice of the polytope associated with M-theory on a Joyce G_2-manifold. This provides evidence for a form of string universality in which EFT strings act as the fundamental building blocks of the UV tower structure in the EFT perturbative regimes.

We prove a persistence theorem for attracting weakly normally hyperbolic invariant tori under small time-periodic perturbations. The theorem extends recent continuation results for weakly normally hyperbolic limit cycles to invariant tori of arbitrary dimension, providing a general analytical framework for their detection. As an application, we establish an averaging principle showing that attracting normally hyperbolic invariant d-tori of the averaged system give rise to attracting normally hyperbolic invariant (d+1)-tori of the original non-autonomous system. We further introduce a polynomiality-preserving construction that simultaneously lifts the dimensions of the phase space and the attracting normally hyperbolic invariant tori, yielding recursive lower bounds for the maximal number of codimension-1 normally hyperbolic invariant tori of polynomial vector fields of a given degree, thereby extending the counting aspect of Hilbert's sixteenth problem to higher-dimensional invariant tori. In particular, we prove that this number grows at least polynomially with the degree and becomes unbounded for invariant tori of higher codimension.