Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Yashpreet Kaur, Varadharaj R. Srinivasan We extend the theorem of Liouville on integration in finite terms to include dilogarithmic integrals, logarithmic integrals and error functions along with transcendental elementary functions. We also generalise a result of Baddoura on integration in finite terms with dilogarithmic integrals.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Péter Kutas We propose an algorithm for finding zero divisors in quaternion algebras over quadratic number fields, or equivalently, solving homogeneous quadratic equations in three variables over Q(d) where d is a square-free integer. The algorithm is randomized and runs in polynomial time if one is allowed to call oracles for factoring integers.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Ana Romero, Julio Rubio, Francis Sergeraert In this paper, we present a new module for the Kenzo system which makes it possible to compute the effective homotopy of the total space of a fibration, using the well-known long exact sequence of homotopy of a fibration defined by Jean-Pierre Serre. The programs are written in Common Lisp and require the implementation of new classes and functions corresponding to the definitions of setoid group (SG) and effective setoid group (ESG). Moreover, we have included a new module for working with finitely generated abelian groups, choosing the representation of a free presentation by means of a matrix in canonical form. These tools are then used to implement the long exact homotopy sequence of a fibration. We illustrate with examples some applications of our results.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Konrad Schrempf We describe a simple approach to factorize non-commutative polynomials, that is, elements in free associative algebras (over a commutative field), into atoms (irreducible elements) based on (a special form of) their minimal linear representations. To be more specific, a correspondence between factorizations of an element and upper right blocks of zeros in the system matrix (of its representation) is established. The problem is then reduced to solving a system of polynomial equations (with at most quadratic terms) with commuting unknowns to compute appropriate transformation matrices (if possible).
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Cristina Bertone, Francesca Cioffi, Davide Franco A classical approach to investigate a closed projective scheme W consists of considering a general hyperplane section of W, which inherits many properties of W. The inverse problem that consists in finding a scheme W starting from a possible hyperplane section Y is called a lifting problem, and every such scheme W is called a lifting of Y. Investigations in this topic can produce methods to obtain schemes with specific properties. For example, any smooth point for Y is smooth also for W.We characterize all the liftings of Y with a given Hilbert polynomial by a parameter scheme that is obtained by gluing suitable affine open subschemes in a Hilbert scheme and is described through the functor it represents. We use constructive methods from Gröbner and marked bases theories. Furthermore, by classical tools we obtain an analogous result for equidimensional liftings. Examples of explicit computations are provided.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Antonio Jiménez-Pastor, Veronika Pillwein Differentiably finite (D-finite) formal power series form a large class of useful functions for which a variety of symbolic algorithms exists. Among these methods are several closure properties that can be carried out automatically. We introduce a natural extension of these functions to a larger class of computable objects for which we prove closure properties. These are again algorithmic. This extension can be iterated constructively preserving the closure properties.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Pilar Benito, Daniel de-la-Concepción, Jorge Roldán-López, Iciar Sesma Taking into account the theoretical results and guidelines given in this work, we introduce a computational method to construct any 2-step nilpotent quadratic algebra of d generators. Along the work we show that the key of the classification of this class of metric algebras relies on certain families of skewsymmetric matrices. Computational examples for d≤8 will be given.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Jürgen Herzog, Ayesha Asloob Qureshi, Maryam Mohammadi Saem By using Gröbner bases we determine in an explicit way the depth of the fiber cone and its relation ideal for classes of monomial ideals in two variables. These classes include concave and convex ideals as well as symmetric ideals.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Angel Blasco, Sonia Pérez-Díaz Let P(t)∈P2(K(t)) be a rational projective parametrization of a plane curve C. In this paper, we introduce the notion of limit point, PL, of P(t), and some remarkable properties of PL are obtained. In particular, if the singularities of C are P1,…,Pn and PL (all of them ordinary) and their respective multiplicities are m1,…,mn and mL, we show that T(s)=∏i=1nHPi(s)mi−1HPL(s)mL−1, where T(s) is the univariate resultant of two polynomials obtained from P(t), and HP1(s),…,HPn(s),HPL(s) are the fibre functions of the singularities. The fibre function of a point P is a polynomial HP(s) whose roots are the fibre of P. Thus, a complete classification of the singularities of a given plane curve, via the factorization of a resultant, is obtained.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Wayne Eberly Initial findings in a study of the automatic selection of algorithms for matrix computations are reported. These include the presentation and analysis of algorithms for the detection and certification of matrix properties allowing the reliable use of a variety of special-purpose algorithms for sparse and structured matrix computations.
Abstract: Publication date: September–October 2019Source: Journal of Symbolic Computation, Volume 94Author(s): Moulay A. Barkatou, Suzy S. Maddah In this article, we discuss formal invariants of singularly-perturbed linear differential systems in neighborhood of turning points and give algorithms which allow their computation. The algorithms proposed are implemented in the computer algebra system Maple.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Sara Kališnik, Davorin Lešnik The growth of tropical geometry has generated significant interest in the tropical semiring in the past decade. However, there are other semirings in tropical algebra that provide more information, such as the symmetrized (max,+), Izhakian's extended and Izhakian–Rowen's supertropical semirings. In this paper we identify in which of these upper-bound semirings we can express symmetric polynomials in terms of elementary ones. We show that in the case of idempotent semirings we can do this precisely when the Frobenius property is satisfied, that in the case of supertropical semirings this is always possible, and that in non-trivial symmetrized semirings this is never possible. Our results allow us to determine the tropical algebra semirings where an analogue of the Fundamental Theorem of Symmetric Polynomials holds and to what extent.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Melanie Gerling The computation of the chromatic polynomial of a graph, which was introduced by Birkhoff (1912), is an NP-complete problem. Consequently, this is also valid for the bivariate generalization of the chromatic polynomial by Dohmen et al. (2003). A recursion formula, which was presented by Averbouch et al. (2008), has exponential complexity. Hence, the aim of the current article is to find efficient algorithms or formulas for the calculation of the bivariate chromatic polynomial for special types of graphs. The following results will be presented:We found efficient formulas for complete graphs, from which the edges of stars with pairwise different vertices are deleted, for complete partite graphs and for special split graphs.Furthermore, in a section about separators, we show that the special case of separating complete subgraphs, which is very simple in the univariate case, requires rather complex methods in the bivariate case.Finally, we establish a connection between the bivariate chromatic polynomial and the matching polynomial for complete graphs from which the edges of stars with pairwise different vertices are removed, as well as for bi-cliques.Some algorithms are implemented in Mathematica, and examples are presented.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Jonas Szutkoski, Mark van Hoeij For a finite separable field extension K/k, all subfields can be obtained by intersecting so-called principal subfields of K/k. In this work we present a way to quickly compute these intersections. If the number of subfields is high, then this leads to faster run times and an improved complexity.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): W.R. Unger We describe an algorithm for computing Schur indices of irreducible characters of a finite group G, based on computations within G and its subgroups and with their character tables. The algorithm has been implemented within Magma and examples of its use are given. We also compare the output of the algorithm on groups associated with sporadic simple groups with the results of W. Feit. The differences are considered.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Shaoshi Chen, Christoph Koutschan In 1992, Wilf and Zeilberger conjectured that a hypergeometric term in several discrete and continuous variables is holonomic if and only if it is proper. Strictly speaking the conjecture does not hold, but it is true when reformulated properly: Payne proved a piecewise interpretation in 1997, and independently, Abramov and Petkovšek in 2002 proved a conjugate interpretation. Both results address the pure discrete case of the conjecture. In this paper we extend their work to hypergeometric terms in several discrete and continuous variables and prove the conjugate interpretation of the Wilf–Zeilberger conjecture in this mixed setting.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Luca Amata, Marilena Crupi Consider a polynomial ring in a finite number of variables over a field of characteristic 0. We implement in CoCoA some algorithms in order to easy compute graded ideals of this ring with given extremal Betti numbers (positions as well as values). More precisely, we develop a package for determining the conditions under which, given two positive integers n,r, 1≤r≤n−1, there exists a graded ideal of a polynomial ring in n variables with r extremal Betti numbers in the given position. An algorithm to check whether an r-tuple of positive integers represents the admissible values of the r extremal Betti numbers is also described. An example in order to show how the package works is also presented.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): J.I. García-García, D. Marín-Aragón, M.A. Moreno-Frías We study the lattice of divisor-closed submonoids of finitely generated cancellative commutative monoids. In case the monoid is an affine semigroup, we give a geometrical characterization of such submonoids in terms of its cone. Finally, we use our results to give an algorithm for computing Δ⁎(H), the set of minimal distances of H.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Abbas Nasrollah Nejad, Ashkan Nikseresht, Ali Akbar Yazdan Pour, Rashid Zaare-Nahandi A tame ideal is an ideal I⊂k[x1,…,xn] such that the blowup of the affine space Akn along I is regular. In this paper, we give a combinatorial characterization of tame squarefree monomial ideals. More precisely, we show that a square free monomial ideal is tame if and only if the corresponding clutter is a complete d-partite d-uniform clutter. Equivalently, a squarefree monomial ideal is tame, if and only if the facets of its Stanley–Reisner complex have mutually disjoint complements. Also, we characterize all monomial ideals generated in degree at most 2 which are tame. Finally, we prove that tame squarefree ideals are of fiber type.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Juan Du, Ron Goldman, Xuhui Wang Complex rational curves have been used to represent circular splines as well as many classical curves including epicycloids, cardioids, Joukowski profiles, and the lemniscate of Bernoulli. Complex rational curves are known to have low degree (typically half the degree of the corresponding rational planar curve), circular precision, invariance with respect to Möbius transformations, special implicit forms, an easy detection procedure, and a fast algorithm for computing their μ-bases. But only certain very special rational planar curves are also complex rational curves. To construct a wider collection of curves with similar appealing properties, we generalize complex rational curves to hyperbolic and parabolic rational curves by invoking the hyperbolic and parabolic numbers. We show that the special properties of complex rational curves extend to these hyperbolic and parabolic rational curves. We also provide examples to flesh out the theory.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): François Boulier, François Lemaire, Adrien Poteaux, Marc Moreno Maza This paper provides new equivalence theorems for regular chains and regular differential chains, which are generalizations of Ritt's characteristic sets. These theorems focus on regularity properties of elements of residue class rings defined by these chains, which are revealed by resultant computations. New corollaries to these theorems have quite simple formulations.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Qing-Hu Hou, Zuo-Ru Zhang Let L be the operator given by L{an}n≥0={an+12−anan+2}n≥0. A sequence {an}n≥0 is called asymptotically r-log-convex if Lk{an}n≥N are non-negative sequences for 1≤k≤r and a certain integer N. Based on asymptotic analysis, we present a method for proving the asymptotic r-log-convexity of a sequence. As an application, we consider the problem of proving the asymptotic r-log-convexity of P-recursive sequences. We find that most P-recursive sequences are asymptotically r-log-convex for any non-negative integer r once they are asymptotically log-convex. Moreover, we show how to find an explicit integer N such that they are r-log-convex for n≥N.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Andreas-Stephan Elsenhans, Jürgen Klüners A polynomial time algorithm to find generators of the lattice of all subfields of a given number field was given in van Hoeij et al. (2013).This article reports on a massive speedup of this algorithm. This is primary achieved by our new concept of Galois-generating subfields. In general this is a very small set of subfields that determine all other subfields in a group-theoretic way. We compute them by targeted calls to the method from van Hoeij et al. (2013). For an early termination of these calls, we give a list of criteria that imply that further calls will not result in additional subfields.Finally, we explain how we use subfields to get a good starting group for the computation of Galois groups.
Abstract: Publication date: July–August 2019Source: Journal of Symbolic Computation, Volume 93Author(s): Victor Magron, Mohab Safey El Din, Markus Schweighofer It is well-known that every non-negative univariate real polynomial can be written as the sum of two polynomial squares with real coefficients. When one allows a (non-negatively) weighted sum of finitely many squares instead of a sum of two squares, then one can choose all coefficients in the representation to lie in the field generated by the coefficients of the polynomial. In particular, this allows for an effective treatment of polynomials with rational coefficients.In this article, we describe, analyze and compare, from both the theoretical and practical points of view, two algorithms computing such a weighted sum of squares decomposition for univariate polynomials with rational coefficients.The first algorithm, due to the third author, relies on real root isolation, quadratic approximations of positive polynomials and square-free decomposition, but its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm. They are exponential in the degree of the input univariate polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using quantifier elimination and root isolation bounds.The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies on complex root isolation and square-free decomposition, and was introduced for certifying positiveness of polynomials in the context of computer arithmetic. Again, its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm, which are polynomial in the degree of the input polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using Vieta's formula and root isolation bounds.Finally, we report on our implementations of both algorithms and compare them in practice on several application benchmarks. While the second algorithm is, as expected from the complexity result, more efficient on most of examples, we exhibit families of non-negative polynomials for which the first algorithm is better.
Abstract: Publication date: Available online 15 March 2019Source: Journal of Symbolic ComputationAuthor(s): Feng Guo, Tiến-Sơn Phạm In this paper, we consider the problem of identifying the type (local minimizer, maximizer or saddle point) of a given isolated real critical point c, which is degenerate, of a multivariate polynomial function f. To this end, we introduce the definition of faithful radius of c by means of the curve of tangency of f. We show that the type of c can be determined by the global extrema of f over the Euclidean ball centered at c with a faithful radius. We propose algorithms to compute faithful radius of c and determine its type.
Abstract: Publication date: Available online 15 March 2019Source: Journal of Symbolic ComputationAuthor(s): Bertrand Nguefack, Emmanuel Pola This work's primary objective is to investigate an effective Buchberger-Zacharias-Weispfenning theory of bimodules over skew polynomial extensions of a coefficient ring satisfying the appropriate notion of coherence. The original contribution of our approach establishes the subbilateral coherence together with the effective computation of subbilateral Gröbner bases for a sufficiently large class of skew polynomial extensions, over term-ordered monoids, of subbilateral Noetherian coherent coefficient rings. The strategy to produce finite bilateral Gröbner bases from subbilateral ones generalizes Kandri-Rody and Weispfenning completion from left Gröbner bases to bilateral ones over a subclass of solvable polynomial rings, as well as Weispfenning completion from Weispfenning restricted modules to bilateral ones over the bivariate Weispfenning extensions of skew fields. It equally results that the class of rings that are both left Noetherian and left coherent (or resp., right Noetherian and right coherent) is closed under iterative skew polynomial extension with bijective conjugation maps.
Abstract: Publication date: Available online 8 March 2019Source: Journal of Symbolic ComputationAuthor(s): Tommi Junttila, Matti Karppa, Petteri Kaski, Jukka Kohonen This paper presents a technique for symmetry reduction that adaptively assigns a prefix of variables in a system of constraints so that the generated prefix-assignments are pairwise nonisomorphic under the action of the symmetry group of the system. The technique is based on McKay's canonical extension framework (McKay, 1998). Among key features of the technique are (i) adaptability—the prefix sequence can be user-prescribed and truncated for compatibility with the group of symmetries; (ii) parallelizability—prefix-assignments can be processed in parallel independently of each other; (iii) versatility—the method is applicable whenever the group of symmetries can be concisely represented as the automorphism group of a vertex-colored graph; and (iv) implementability—the method can be implemented relying on a canonical labeling map for vertex-colored graphs as the only nontrivial subroutine. To demonstrate the practical applicability of our technique, we have prepared an experimental open-source implementation of the technique and carry out a set of experiments that demonstrate ability to reduce symmetry on hard instances. Furthermore, we demonstrate that the implementation effectively parallelizes to compute clusters with multiple nodes via a message-passing interface.
Abstract: Publication date: Available online 6 March 2019Source: Journal of Symbolic ComputationAuthor(s): Laura Menini, Corrado Possieri, Antonio Tornambè In this paper, a symbolic, algorithmic procedure to compute an immersion that recasts a polynomial system into a linear one up to an output injection is proposed. Such a technique is based on computing, through algebraic geometry methods, the set of all the embeddings of the system and on matching the coefficients of these polynomials with the ones of the embeddings of a linear system up to an output injection. The given algorithm is then relaxed to compute an immersion that recasts a polynomial system into a form that is linear up to a finite order and an output injection and to compute an approximation of the immersion.
Abstract: Publication date: Available online 1 March 2019Source: Journal of Symbolic ComputationAuthor(s): Yoav Len, Hannah Markwig We study lifts of tropical bitangents to the tropicalization of a given complex algebraic curve together with their lifting multiplicities. Using this characterization, we show that generically all the seven bitangents of a smooth tropical plane quartic lift in sets of four to algebraic bitangents. We do this constructively, i.e. we give solutions for the initial terms of the coefficients of the bitangent lines. This is a step towards a tropical proof that a general smooth quartic admits 28 bitangent lines. The methods are also appropriate to count real bitangents; however the conditions to determine whether a tropical bitangent has real lifts are not purely combinatorial.
Abstract: Publication date: Available online 28 February 2019Source: Journal of Symbolic ComputationAuthor(s): Takafumi Shibuta, Shinichi Tajima In this paper, we present an algorithm for computing the minimal reductions of m-primary ideals of Cohen–Macaulay local rings. Using this algorithm, we are able to compute the Hilbert–Samuel multiplicities and solve the membership problem for the integral closure of m-primary ideals.
Abstract: Publication date: Available online 25 February 2019Source: Journal of Symbolic ComputationAuthor(s): Christina Boura, Eirini Chavli, Maria Chlouveraki, Konstantinos Karvounis We prove the BMM symmetrising trace conjecture for the exceptional irreducible complex reflection groups G4,G5,G6,G7,G8 using a combination of algorithms programmed in different languages (C++, SAGE, GAP3, Mathematica). Our proof depends on the choice of a suitable basis for the generic Hecke algebra associated with each group.
Abstract: Publication date: Available online 25 February 2019Source: Journal of Symbolic ComputationAuthor(s): Marie-Françoise Roy, Aviva Szpirglas Sylvester doubles sums, introduced first by Sylvester (see Sylvester, 1840, Sylvester, 1853), are symmetric expressions of the roots of two polynomials P and Q. Sylvester's definition of double sums makes no sense if P and Q have multiple roots, since the definition involves denominators that vanish when there are multiple roots. The aims of this paper are to give a new definition for Sylvester double sums making sense if P and Q have multiple roots, which coincides with the definition by Sylvester in the case of simple roots, to prove the fundamental property of Sylvester double sums, i.e. that Sylvester double sums indexed by (k,ℓ) are equal up to a constant if they share the same value for k+ℓ, and to prove the relationship between double sums and subresultants, i.e. that they are equal up to a constant. In the simple root case, proofs of these properties are already known (see Lascoux and Pragacz, 2002, d'Andrea et al., 2007, Roy and Szpirglas, 2011). The more general proofs given here are using generalized Vandermonde determinants and a new symmetric multivariate Hermite interpolation as well as an induction on the length of the remainder sequence of P and Q.
Abstract: Publication date: Available online 25 February 2019Source: Journal of Symbolic ComputationAuthor(s): Zeyu Guo We introduce a family of combinatorial objects called P-schemes, where P is a collection of subgroups of a finite group G. A P-scheme is a collection of partitions of right coset spaces H\G, indexed by H∈P, that satisfies a list of axioms. These objects generalize the classical notion of association schemes as well as m-schemes (Ivanyos et al., 2009).We apply the theory of P-schemes to deterministic polynomial factoring over finite fields: suppose f˜(X)∈Z[X] and a prime number p are given, such that f(X):=f˜(X)modp factorizes into n=deg(f˜) distinct linear factors over the finite field Fp. We show that, assuming the generalized Riemann hypothesis (GRH), f(X) can be completely factorized in deterministic polynomial time if the Galois group G of f˜(X) is an almost simple primitive permutation group on the set of roots of f˜(X), and the socle of G is a subgroup of Sym(k) for k up to 2O(logn). This is the first deterministic polynomial-time factoring algorithm for primitive Galois groups of superpolynomial order.We prove our result by developing a generic factoring algorithm and analyzing it using P-schemes. We also show that the main results achieved by known GRH-based deterministic polynomial factoring algorithms can be derived from our generic algorithm in a uniform way.Finally, we investigate the schemes conjecture in Ivanyos et al. (2009), and formulate analogous conjectures associated with various families of permutation groups. We show that these conjectures form a hierarchy of relaxations of the original schemes conjecture, and their positive resolutions would imply deterministic polynomial-time factoring algorithms for various families of Galois groups under GRH.
Abstract: Publication date: Available online 25 February 2019Source: Journal of Symbolic ComputationAuthor(s): Xiaoning Zeng, Shuijing Xiao In this paper, we present an algorithm for determining the limits of real rational functions in two variables, based on Sturm's familiar theorem and the general Sturm–Tarski theorem for counting certain roots of univariate polynomials in a real closed field. Let R[x,y] be the ring of polynomials with real coefficients in two variables x, y, and let u(x,y), v(x,y)∈R[x,y] be two non-zero polynomials such that u(a,b)=v(a,b)=0 for a, b∈R. The purpose of this paper is to decide the existence of lim(x,y)→(a,b)u(x,y)v(x,y) and compute the limit if it exists. Our algorithm needs no assumption on the denominators and does not involve the computation of Puiseux series.
Abstract: Publication date: Available online 22 February 2019Source: Journal of Symbolic ComputationAuthor(s): Tung Le, Kay Magaard, Alessandro Paolini We parametrize the set of irreducible characters of the Sylow p-subgroups of the Chevalley groups D6(q) and E6(q), for an arbitrary power q of any prime p. In particular, we establish that the parametrization is uniform for p≥3 in type D6 and for p≥5 in type E6, while the prime 2 in type D6 and the primes 2, 3 in type E6 yield character degrees of the form qm/pi which force a departure from the generic situations. Also for the first time in our analysis we see a family of irreducible characters of a classical group of degree qm/pi where i>1 which occurs in type D6.
Abstract: Publication date: Available online 21 February 2019Source: Journal of Symbolic ComputationAuthor(s): Leo Margolis The Prime Graph Question for integral group rings asks if it is true that if the normalized unit group of the integral group ring of a finite group G contains an element of order pq, for some primes p and q, also G contains an element of that order. We answer this question for the three Conway sporadic simple groups after reducing it to a combinatorial question about Young tableaux and Littlewood-Richardson coefficients. This finishes work of V. Bovdi, A. Konovalov and S. Linton.
Abstract: Publication date: Available online 21 February 2019Source: Journal of Symbolic ComputationAuthor(s): Yongbin Li, Qiuju Fu, Renbin Deng In this paper, an injection from the partition lattice Πn to a zero-dimensional affine algebra over the finite field F2 is constructed. We study some interesting properties of the injection and present two direct sum decompositions of the zero-dimensional affine algebra. Based upon these, some properties of Πn are revealed in an algebraic manner, for instance, the rank-generating function and characteristic polynomial of Πn can be derived using the symbolic method.
Abstract: Publication date: Available online 21 February 2019Source: Journal of Symbolic ComputationAuthor(s): Rida T. Farouki A unique feature of polynomial Pythagorean–hodograph (PH) curves is the ability to interpolate G1 Hermite data (end points and tangents) with a specified total arc length. Since their construction involves the solution of a set of non–linear equations with coefficients dependent on the specified data, the existence of such interpolants in all instances is non–obvious. A comprehensive analysis of the existence of solutions in the case of spatial PH quintics with end derivatives of equal magnitude is presented, establishing that a two–parameter family of interpolants exists for any prescribed end points, end tangents, and total arc length. The two free parameters may be exploited to optimize a suitable shape measure of the interpolants, such as the elastic bending energy.
Abstract: Publication date: Available online 21 February 2019Source: Journal of Symbolic ComputationAuthor(s): Enzo Aljovin, Hossein Movasati, Roberto Villaflor Loyola We describe an algorithm which verifies whether linear algebraic cycles of the Fermat variety generate the lattice of Hodge cycles. A computer implementation of this confirms the integral Hodge conjecture for quartic and quintic Fermat fourfolds. Our algorithm is based on computation of the list of elementary divisors of both the lattice of linear algebraic cycles, and the lattice of Hodge cycles written in terms of vanishing cycles, and observing that these two lists are the same.
Abstract: Publication date: Available online 21 February 2019Source: Journal of Symbolic ComputationAuthor(s): Michela Ceria, Teo Mora, Margherita Roggero Polynomial reduction is one of the main tools in computational algebra with innumerable applications in many areas, both pure and applied. Since many years both the theory and an efficient design of the related algorithm have been solidly established. This paper presents a definition of the generic concept of polynomial reduction structure, studies its features and highlights the aspects needed in order to grant and to efficiently test the main properties (Noetherianity, confluence, ideal membership). The most significant aspect of this analysis is a negative reappraisal of the role of the notion of term ordering which is usually considered a central and crucial tool in the theory. In fact, as it was already established in the computer science context in relation with termination of algorithms, most of the properties can be obtained simply considering a well founded order, while the classical requirement that it be preserved by multiplication is irrelevant. The last part of the paper shows how the polynomial basis concepts present in literature are interpreted in our language and their properties are consequences of the general results established in the first part of the paper.
Abstract: Publication date: Available online 21 February 2019Source: Journal of Symbolic ComputationAuthor(s): Shaoshi Chen, Manuel Kauers, Ziming Li, Yi Zhang We generalize the notions of ordinary points and singularities from linear ordinary differential equations to D-finite systems. Ordinary points and apparent singularities of a D-finite system are characterized in terms of its formal power series solutions. We also show that apparent singularities can be removed like in the univariate case by adding suitable additional solutions to the system at hand. Several algorithms are presented for removing and detecting apparent singularities. In addition, an algorithm is given for computing formal power series solutions of a D-finite system at apparent singularities.
Abstract: Publication date: Available online 20 February 2019Source: Journal of Symbolic ComputationAuthor(s): Pascal Koiran We give a separation bound for the complex roots of a trinomial f∈Z[X]. The logarithm of the inverse of our separation bound is polynomial in the size of the sparse encoding of f; in particular, it is polynomial in log(degf). It is known that no such bound is possible for 4-nomials (polynomials with 4 monomials). For trinomials, the classical results (which are based on the degree of f rather than the number of monomials) give separation bounds that are exponentially worse.As an algorithmic application, we show that the number of real roots of a trinomial f can be computed in time polynomial in the size of the sparse encoding of f. The same problem is open for 4-nomials.
Abstract: Publication date: Available online 20 February 2019Source: Journal of Symbolic ComputationAuthor(s): Yairon Cid-Ruiz In this paper, we study how the degrees of the elements in a minimal μ-basis of a parametrized surface behave. For an arbitrary rational surface parametrization P(s,t)=(a1(s,t),a2(s,t),a3(s,t),a4(s,t))∈F[s,t]4 over an infinite field F, we show the existence of a μ-basis with polynomials bounded in degree by O(d33), where d=max(deg(a1),deg(a2),deg(a3),deg(a4)). Under additional assumptions we can obtain tighter bounds.
Abstract: Publication date: Available online 3 January 2019Source: Journal of Symbolic ComputationAuthor(s): Pedro Quaresma, Vanda Santos, Pierluigi Graziani, Nuno Baeta In the current Information Society the organisation of the information is key to ensure the information safekeeping and retrieval. It is of utmost importance that each and every user can find the information he/she is looking for, presented in such a way that best fit his/her needs. Geometry is no exception, the servers of geometric information should be easily and successfully searchable. By classifying the information contained in the servers of geometric information accordingly to several taxonomies, it will be possible to begin applying filters to the users' queries, adjusting them to the perceived user's needs. Having that in mind, the introduction of an adaptive filtering mechanisms into servers of geometric information is considered.Different taxonomies for different goals are presented. For educational purposes, a classification like Common Core Standards should be considered, but other considerations like the complexity of the construction, the provability, by a geometry automatic theorem prover, of a given conjecture and the readability of the resulting proof, should be taken into account. For research in automated deduction purposes, other issues must be considered, e.g. efficiency and applicability of the available automated provers.To validate the usefulness of these taxonomies it will be used, as a case study, their application to a server of geometric information. In particular, Thousands of Geometric problems for geometric Theorem Provers will be considered. TGTP is a Web-based repository of geometric problems being developed to support the testing and evaluation of geometric automated theorem proving systems. Using this system it will be analysed how the taxonomies could help to tailor the search for information adapted to each and every geometer.
Abstract: Publication date: Available online 3 January 2019Source: Journal of Symbolic ComputationAuthor(s): Zoltán Kovács, Tomás Recio, M. Pilar Vélez We illustrate an on-going work on the crossroad of mechanical linkages, dynamic geometry and automated reasoning. In particular, we exemplify how some automated reasoning tools (ART) based on symbolic computation and recently implemented in GeoGebra, can be used for linkage exploration. For instance, when considering linkages for generating specific algebraic curves, such as Peaucellier's construction of a straight line, we will show how these ART can help towards the verification (automatic proving) of the correctness of the linkage construction, as well as for finding (automatic discovery) a suitable modification on a given linkage for achieving a desired movement.
Abstract: Publication date: Available online 3 January 2019Source: Journal of Symbolic ComputationAuthor(s): Michael Strobel We will present the benefits of using methods of non-standard analysis in dynamic projective geometry. One major application will be the desingularization of geometric constructions.
Abstract: Publication date: Available online 2 January 2019Source: Journal of Symbolic ComputationAuthor(s): Thierry Dana-Picard Learning mathematics in a technology rich environment enables to revive classical topics which have been removed from the curriculum a long time ago. Theoretical issues and their applications can be studied within an experimental process, using automated proofs. We present a technology based study of isoptic curves of an astroid, which is a non smooth and non convex curve. We take advantage of both algebraic symbolic features, such as resultants and Gröbner bases packages implemented in a Computer Algebra System (CAS), together with a Dynamical Geometry System (DGS). The usage of algebraic methods is made possible by the translation of the trigonometric parametrization into rational expressions, and then into polynomial equations. The dynamics provided by the DGS enable the discovery of special features of the isoptics, in particular the fact that the isoptic has singular points and, according to the viewing angle, the isoptic may be inscribed in the astroid or not.
Abstract: Publication date: Available online 2 January 2019Source: Journal of Symbolic ComputationAuthor(s): Francisco Botana, Zoltán Kovács, Tomas Recio
Abstract: Publication date: Available online 2 January 2019Source: Journal of Symbolic ComputationAuthor(s): Milica Selaković, Vesna Marinković, Predrag Janičić Dynamic Geometry Software (DGS) is present for more than three decades: it found its way to classrooms worldwide and it is now an irreplaceable component of mathematical education. From the very beginning and still, DGS tools are built around one central scenario: the user chooses several (free) points and, using them, constructs some other points and other geometric objects. Then, the user can move (“drag”) a chosen free point and explore how the constructed points and other constructed objects change. In this paper we describe one new DGS scenario: the user can move the constructed points and explore how the free points and the constructed objects change accordingly. This scenario uses a solver for geometry construction problems. We implemented this DGS feature within our prototype tool Touch&Drag, developed for touch-based devices. The presented feature can be implemented in other DGS tools, too.
Abstract: Publication date: Available online 8 October 2018Source: Journal of Symbolic ComputationAuthor(s): Ralf Hemmecke, Silviu Radu We describe an algorithm that, given a positive integer N, computes a Gröbner basis of the ideal of polynomial relations among Dedekind η-functions of level N, i.e., among the elements of {η(δ1τ),…,η(δnτ)} where 1=δ1
Abstract: Publication date: Available online 2 October 2018Source: Journal of Symbolic ComputationAuthor(s): Evelyne Hubert Assuming the variety of a polynomial set is invariant under a group action, we construct a set of invariants that define the same variety. Our construction can be seen as a generalization of the previously known construction for finite groups. The result though has to be understood outside an invariant variety which is independent of the polynomial set considered. We introduce the symmetrizations of a polynomial that are polynomials in a generating set of rational invariants. The generating set of rational invariants and the symmetrizations are constructed w.r.t. a section to the orbits of the group action.
Abstract: Publication date: Available online 26 September 2018Source: Journal of Symbolic ComputationAuthor(s): John J. Cannon, Derek F. Holt, William R. Unger We determine the minimal degree permutation representations of all finite groups with trivial soluble radical, and describe applications to structural computations in large finite matrix groups that use the output of the CompositionTree algorithm. We also describe how this output can be used to help find an effective base and strong generating set for such groups. We have implemented the resulting algorithms in Magma, and we report on their performance.
Abstract: Publication date: Available online 10 September 2018Source: Journal of Symbolic ComputationAuthor(s): Belén García, Jaume Llibre, Antón Lombardero, Jesús S. Pérez del Río Quasi-homogeneous systems, and in particular those 3-dimensional, are currently a thriving line of research. But a method for obtaining all fields of this class is not yet available. The weight vectors of a quasi-homogeneous system are grouped into families. We found the maximal spatial quasi-homogeneous systems with the property of having only one family with minimum weight vector. This minimum vector is unique to the system, thus acting as identification code. We develop an algorithm that provides all normal forms of maximal 3-dimensional quasi-homogeneous systems for a given degree. All other 3-dimensional quasi-homogeneous systems can be trivially deduced from these maximal systems. We also list all the systems of this type of degree 2 using the algorithm. With this algorithm we make available to the researchers all 3-dimensional quasi-homogeneous systems.
Hybrid journal (It can contain Open Access articles)
[3203 journals]
