In 1984, Deligne proved that for any prime number $p$, the reduction modulo $p$ of the diagonal of a multivariate algebraic power series with integer coefficients is algebraic over the field of rational functions with coefficients in $\mathbb F_p$. Moreover, he conjectured that the algebraic degrees $d_p$ of these functions should grow at most polynomially in $p$. In this article, we provide a new and elementary proof of Deligne's theorem, which yields the first general polynomial bound on $d_p$ with an explicit and reasonable degree.
In this work, we introduce a novel variant of the multivariate quadratic problem, which is at the core of one of the most promising post-quantum alternatives: multivariate cryptography. In this variant, the solution of a given multivariate quadratic system must also be regular, i.e. if it is split into multiple blocks of consecutive entries with the same fixed length, then each block has only one nonzero entry. We prove the NP-completeness of this variant and show similarities and differences with other computational problems used in cryptography. Then we analyze its hardness by reviewing the most common solvers for polynomial systems over finite fields, derive asymptotic formulas for the corresponding complexities and compare the different approaches.
This paper continues the studies of symbolic integration by focusing on the stability problems on D-finite functions. We introduce the notion of stability index in order to investigate the order growth of the differential operators satisfied by iterated integrals of D-finite functions and determine bounds and exact formula for stability indices of several special classes of differential operators. With the basic properties of stability index, we completely solve the stability problem on general hyperexponential functions.
An open source symbolic tool for vector fields analysis 'SymFields' is developed in Python. The SymFields module is constructed upon Python symbolic module sympy, which could only conduct scaler field analysis. With SymFields module, you can conduct vector analysis for general curvilinear coordinates regardless whether it is orthogonal or not. In SymFields, the differential operators based on metric tensor are normalized to real physical values, which means your can use real physical value of the vector fields as inputs. This could greatly free the physicists from the tedious calculation under complicated coordinates.
The resultant of two univariate polynomials is an invariant of great importance in commutative algebra and vastly used in computer algebra systems. Here we present an algorithm to compute it over Artinian principal rings with a modified version of the Euclidean algorithm. Using the same strategy, we show how the reduced resultant and a pair of Bézout coefficient can be computed. Particular attention is devoted to the special case of $\mathbf{Z}/n\mathbf{Z}$, where we perform a detailed analysis of the asymptotic cost of the algorithm. Finally, we illustrate how the algorithms can be exploited to improve ideal arithmetic in number fields and polynomial arithmetic over $p$-adic fields.
Recently, it has been shown constructively how a finite set of hypergeometric products, multibasic hypergeometric products or their mixed versions can be modeled properly in the setting of formal difference rings. Here special emphasis is put on robust constructions: whenever further products have to be considered, one can reuse --up to some mild modifications-- the already existing difference ring. In this article we relax this robustness criteria and seek for another form of optimality. We will elaborate a general framework to represent a finite set of products in a formal difference ring where the number of transcendental product generators is minimal. As a bonus we are able to describe explicitly all relations among the given input products.
We study the termination problem for probabilistic term rewrite systems. We prove that the interpretation method is sound and complete for a strengthening of positive almost sure termination, when abstract reduction systems and term rewrite systems are considered. Two instances of the interpretation method - polynomial and matrix interpretations - are analyzed and shown to capture interesting and nontrivial examples when automated. We capture probabilistic computation in a novel way by way of multidistribution reduction sequences, this way accounting for both the nondeterminism in the choice of the redex and the probabilism intrinsic in firing each rule.
To synthesize Maxwell optics systems, the mathematical apparatus of tensor and vector analysis is generally employed. This mathematical apparatus implies executing a great number of simple stereotyped operations, which are adequately supported by computer algebra systems. In this paper, we distinguish between two stages of working with a mathematical model: model development and model usage. Each of these stages implies its own computer algebra system. As a model problem, we consider the problem of geometrization of Maxwell's equations. Two computer algebra systems---Cadabra and FORM---are selected for use at different stages of investigation.
In the 1930s Tarski showed that real quantifier elimination was possible, and in 1975 Collins gave a remotely practicable method, albeit with doubly-exponential complexity, which was later shown to be inherent. We discuss some of the recent major advances in Collins method: such as an alternative approach based on passing via the complexes, and advances which come closer to "solving the question asked" rather than "solving all problems to do with these polynomials".
P. -V Koseleff, D Pecker, Fabrice Rouillier
et al.
A Chebyshev curve $\mathcal{C}(a,b,c,φ)$ has a parametrization of the form$ x(t)=T\_a(t)$; \ $y(t)=T\_b(t)$; $z(t)= T\_c(t + φ)$, where $a,b,c$are integers, $T\_n(t)$ is the Chebyshev polynomialof degree $n$ and $φ\in \mathbb{R}$. When $\mathcal{C}(a,b,c,φ)$ is nonsingular,it defines a polynomial knot. We determine all possible knot diagrams when $φ$ varies. Let $a,b,c$ be integers, $a$ is odd, $(a,b)=1$, we show that one can list all possible knots $\mathcal{C}(a,b,c,φ)$ in$\tilde{\mathcal{O}}(n^2)$ bit operations, with $n=abc$.
A period of a rational integral is the result of integrating, with respect to one or several variables, a rational function over a closed path. This work focuses particularly on periods depending on a parameter: in this case the period under consideration satisfies a linear differential equation, the Picard-Fuchs equation. I give a reduction algorithm that extends the Griffiths-Dwork reduction and apply it to the computation of Picard-Fuchs equations. The resulting algorithm is elementary and has been successfully applied to problems that were previously out of reach.
Efficient matrix determinant calculations have been studied since the 19th century. Computers expand the range of determinants that are practically calculable to include matrices with symbolic entries. However, the fastest determinant algorithms for numerical matrices are often not the fastest for symbolic matrices with many variables. We compare the performance of two algorithms, fraction-free Gaussian elimination and minor expansion, on symbolic matrices with many variables. We show that, under a simplified theoretical model, minor expansion is faster in most situations. We then propose optimizations for minor expansion and demonstrate their effectiveness with empirical data.
We show that the number of digits in the integers of a creative telescoping relation of expected minimal order for a bivariate proper hypergeometric term has essentially cubic growth with the problem size. For telescopers of higher order but lower degree we obtain a quintic bound. Experiments suggest that these bounds are tight. As applications of our results, we give an improved bound on the maximal possible integer root of the leading coefficient of a telescoper, and the first discussion of the bit complexity of creative telescoping.
The developable surface is an important surface in computer aided design, geometric modeling and industrial manufactory. It is often given in the stan- dard parametric form, but it can also be in the implicit form which is commonly used in algebraic geometry. Not all algebraic developable surfaces have rational parametrizations. In this paper, we focus on the rational developable surfaces. For a given algebraic surface, we first determine whether it is developable by geometric inspection, and we give a rational proper parametrization for the af- firmative case. For a rational parametric surface, we can also determine the developability and give a proper reparametrization for the developable surface.
The extended Lüroth's Theorem says that if the transcendence degree of $\KK(\mathsf{f}_1,\dots,\mathsf{f}_m)/\KK$ is 1 then there exists $f \in \KK(\underline{X})$ such that $\KK(\mathsf{f}_1,\dots,\mathsf{f}_m)$ is equal to $\KK(f)$. In this paper we show how to compute $f$ with a probabilistic algorithm. We also describe a probabilistic and a deterministic algorithm for the decomposition of multivariate rational functions. The probabilistic algorithms proposed in this paper are softly optimal when $n$ is fixed and $d$ tends to infinity. We also give an indecomposability test based on gcd computations and Newton's polytope. In the last section, we show that we get a polynomial time algorithm, with a minor modification in the exponential time decomposition algorithm proposed by Gutierez-Rubio-Sevilla in 2001.
We consider the problem of isolating the real roots of a square-free polynomial with integer coefficients using (variants of) the continued fraction algorithm (CF). We introduce a novel way to compute a lower bound on the positive real roots of univariate polynomials. This allows us to derive a worst case bound of $\sOB(d^6 + d^4τ^2 + d^3τ^2)$ for isolating the real roots of a polynomial with integer coefficients using the classic variant \cite{Akritas:implementation} of CF, where $d$ is the degree of the polynomial and $τ$ the maximum bitsize of its coefficients. This improves the previous bound of Sharma \cite{sharma-tcs-2008} by a factor of $d^3$ and matches the bound derived by Mehlhorn and Ray \cite{mr-jsc-2009} for another variant of CF; it also matches the worst case bound of the subdivision-based solvers.
We present a new proof of Stembridge's theorem about the enumeration of totally symmetric plane partitions using the methodology suggested in the recent Koutschan-Kauers-Zeilberger semi-rigorous proof of the Andrews-Robbins q-TSPP conjecture. Our proof makes heavy use of computer algebra and is completely automatic. We describe new methods that make the computations feasible in the first place. The tantalizing aspect of this work is that the same methods can be applied to prove the q-TSPP conjecture (that is a q-analogue of Stembridge's theorem and open for more than 25 years); the only hurdle here is still the computational complexity.
Existing algorithms for isolating real solutions of zero-dimensional polynomial systems do not compute the multiplicities of the solutions. In this paper, we define in a natural way the multiplicity of solutions of zero-dimensional triangular polynomial systems and prove that our definition is equivalent to the classical definition of local (intersection) multiplicity. Then we present an effective and complete algorithm for isolating real solutions with multiplicities of zero-dimensional triangular polynomial systems using our definition. The algorithm is based on interval arithmetic and square-free factorization of polynomials with real algebraic coefficients. The computational results on some examples from the literature are presented.
Alin Bostan, Muhammad Chowdhury, Joris van der Hoeven
et al.
We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li, Moreno Maza and Schost, we propose an algorithm that relies on homotopy and fast evaluation-interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given to notably addition of algebraic numbers in small characteristic.