Source author record

Mark van Hoeij

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Symbolic Computation math.NT math.AG hep-th math.CO Computational Complexity Discrete Mathematics math.CA math.CV

Catalog footprint

Research overview

18works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Desingularization and p-Curvature of Recurrence Operators

Linear recurrence operators in characteristic $p$ are classified by their $p$ -curvature. For a recurrence operator $L$ , denote by $χ(L)$ the characteristic polynomial of its $p$ -curvature. We can obtain information about the factorization of $L$ by factoring $χ(L)$ . The main theorem of this paper gives an unexpected relation between $χ(L)$ and the true singularities of $L$ . An application is to speed up a fast algorithm for computing $χ(L)$ by desingularizing $L$ first. Another contribution of this paper is faster desingularization.

preprint2020arXiv

A Divisor Formula and a Bound on the $\mathbb{Q}$ -gonality of the Modular Curve $X_1(N)$

We give a formula for divisors of modular units on $X_1(N)$ and use it to prove that the $\mathbb{Q}$ -gonality of the modular curve $X_1(N)$ is bounded above by $\left[\frac{11N^2}{840}\right]$ , where $[\bullet]$ denotes the nearest integer.

preprint2020arXiv

A Family of Denominator Bounds for First Order Linear Recurrence Systems

For linear recurrence systems, the problem of finding rational solutions is reduced to the problem of computing polynomial solutions by computing a content bound or a denominator bound. There are several bounds in the literature. The sharpest bound leads to polynomial solutions of lower degrees, but this advantage need not compensate for the time spent on computing that bound. To strike the best balance between sharpness of the bound versus CPU time spent obtaining it, we will give a family of bounds. The $J$ 'th member of this family is similar to (Abramov, Barkatou, 1998) when $J=1$ , similar to (van Hoeij, 1998) when $J$ is large, and novel for intermediate values of $J$ , which give the best balance between sharpness and CPU time. The setting for our content bounds are systems $τ(Y) = MY$ where $τ$ is an automorphism of a UFD, and $M$ is an invertible matrix with entries in its field of fractions. This setting includes the shift case, the $q$ -shift case, the multi-basic case and others. We give two versions, a global version, and a version that bounds each entry separately.

preprint2016arXiv

A Modular Algorithm for Computing Polynomial GCDs over Number Fields presented with Multiple Extensions

We consider the problem of computing the monic gcd of two polynomials over a number field L = Q(alpha_1,...,alpha_n). Langemyr and McCallum have already shown how Brown's modular GCD algorithm for polynomials over Q can be modified to work for Q(alpha) and subsequently, Langemyr extended the algorithm to L[x]. Encarnacion also showed how to use rational number to make the algorithm for Q(alpha) output sensitive, that is, the number of primes used depends on the size of the integers in the gcd and not on bounds based on the input polynomials. Our first contribution is an extension of Encarnacion's modular GCD algorithm to the case n>1, which, like Encarnacion's algorithm, is is output sensitive. Our second contribution is a proof that it is not necessary to test if p divides the discriminant. This simplifies the algorithm; it is correct without this test. Our third contribution is a modification to the algorithm to treat the case of reducible extensions. Such cases arise when solving systems of polynomial equations. Our fourth contribution is an implementation of the modular GCD algorithm in Maple and in Magma. Both implementations use a recursive dense polynomial data structure for representing polynomials over number fields with multiple field extensions. Our fifth contribution is a primitive fraction-free algorithm. This is the best non-modular approach. We present timing comparisons of the Maple and Magma implementations demonstrating various optimizations and comparing them with the monic Euclidan algorithm and our primitive fraction-free algorithm.

preprint2016arXiv

Computing Hypergeometric Solutions of Second Order Linear Differential Equations using Quotients of Formal Solutions and Integral Bases

We present two algorithms for computing hypergeometric solutions of second order linear differential operators with rational function coefficients. Our first algorithm searches for solutions of the form $\exp(\int r \, dx)\cdot{_{2}F_1}(a_1,a_2;b_1;f)$ where $r,f \in \overline{\mathbb{Q}(x)}$ , and $a_1,a_2,b_1 \in \mathbb{Q}$ . It uses modular reduction and Hensel lifting. Our second algorithm tries to find solutions in the form $\exp(\int r \, dx)\cdot \left( r_0 \cdot{_{2}F_1}(a_1,a_2;b_1;f) + r_1 \cdot{_{2}F_1}'(a_1,a_2;b_1;f) \right)$ where $r_0, r_1 \in \overline{\mathbb{Q}(x)}$ , as follows: It tries to transform the input equation to another equation with solutions of the first type, and then uses the first algorithm.

preprint2016arXiv

Hypergeometric Expressions for Generating Functions of Walks with Small Steps in the Quarter Plane

We study nearest-neighbors walks on the two-dimensional square lattice, that is, models of walks on $\mathbb{Z}^2$ defined by a fixed step set that is a subset of the non-zero vectors with coordinates 0, 1 or $-1$ . We concern ourselves with the enumeration of such walks starting at the origin and constrained to remain in the quarter plane $\mathbb{N}^2$ , counted by their length and by the position of their ending point. Bousquet-Mélou and Mishna [Contemp. Math., pp. 1--39, Amer. Math. Soc., 2010] identified 19 models of walks that possess a D-finite generating function; linear differential equations have then been guessed in these cases by Bostan and Kauers [FPSAC 2009, Discrete Math. Theor. Comput. Sci. Proc., pp. 201--215, 2009]. We give here the first proof that these equations are indeed satisfied by the corresponding generating functions. As a first corollary, we prove that all these 19 generating functions can be expressed in terms of Gauss' hypergeometric functions that are intimately related to elliptic integrals. As a second corollary, we show that all the 19 generating functions are transcendental, and that among their $19 \times 4$ combinatorially meaningful specializations only four are algebraic functions.

preprint2016arXiv

Reduction-Based Creative Telescoping for Fuchsian D-finite Functions

Continuing a series of articles in the past few years on creative telescoping using reductions, we adapt Trager's Hermite reduction for algebraic functions to fuchsian D-finite functions and develop a reduction-based creative telescoping algorithm for this class of functions, thereby generalizing our recent reduction-based algorithm for algebraic functions, presented at ISSAC 2016.

preprint2015arXiv

Groebner basis in Boolean rings is not polynomial-space

We give an example where the number of elements of a Groebner basis in a Boolean ring is not polynomially bounded in terms of the bitsize and degrees of the input.

preprint2014arXiv

Belyi functions for hyperbolic hypergeometric-to-Heun transformations

A complete classification of Belyi functions for transforming certain hypergeometric equations to Heun equations is given. The considered hypergeometric equations have the local exponent differences 1/k,1/l,1/m that satisfy k,l,m in N and the hyperbolic condition 1/k+1/l+1/m<1. There are 366 Galois orbits of Belyi functions giving the considered (non-parametric) hypergeometric-to-Heun pull-back transformations. Their maximal degree is 60, which is well beyond reach of standard computational methods. To obtain these Belyi functions, we developed two efficient algorithms that exploit the implied pull-back transformations.

preprint2014arXiv

Computing Galois representations and equations for modular curves $X_H(\ell)$

We construct plane models of the modular curve $X_H(\ell)$ , and use their explicit equations to compute Galois representations associated to modular forms for values of $\ell$ that are significantly higher than in prior works.

preprint2014arXiv

Low Degree Places on the Modular Curve X1(N)

This short note gives questions and examples of points on X1(N) defined over number fields whose degrees are lower than the gonality.

preprint2013arXiv

Algorithms and differential relations for Belyi functions

A tool package for computing genus 0 Belyi functions is presented, including simplification routines, computation of moduli fields, decompositions, dessins d'enfant. The main algorithm for computing the Belyi functions themselves is based on implied transformations of the hypergeometric differential equation to Fuchsian equations, preferably with few singular points. This gives interesting differential relations between polynomial components of a Belyi function.

preprint2013arXiv

Computing Puiseux Expansions at Cusps of the Modular Curve X0(N)

The goal in this preprint is to give an efficient algorithm to compute Puiseux expansions at cusps of X0(N). It is based on a relation with a hypergeometric function that holds for any N.

preprint2012arXiv

On Hirzebruch invariants of elliptic fibrations

We compute all Hirzebruch invariants $χ_q$ for $D_5$ , $E_6$ , $E_7$ and $E_8$ elliptic fibrations of every dimension. A single generating series $χ(t,y)$ is produced for each family of fibrations such that the coefficient of $t^{k}y^{q}$ encodes $χ_q$ over a base of dimension $k$ , solely in terms of invariants of the base of the fibration.

preprint2012arXiv

On stringy invariants of GUT vacua

We investigate aspects of certain stringy invariants of singular elliptic fibrations which arise in engineering Grand Unified Theories in F-theory. In particular, we exploit the small resolutions of the total space of these fibrations provided recently in the physics literature to compute `stringy characteristic classes', and find that numerical invariants obtained by integrating such characteristic classes are predetermined by the topology of the base of the elliptic fibration. Moreover, we derive a simple (dimension independent) formula for pushing forward powers of the exceptional divisor of a blowup, which one may use to reduce any integral (in the sense of Chow cohomology) on a small resolution of a singular elliptic fibration to an integral on the base. We conclude with a speculatory note on the cohomology of small resolutions of GUT vacua, where we conjecture that certain simple formulas for their Hodge numbers may be given solely in terms of the first Chern class and Hodge numbers of the base.}

preprint2011arXiv

Explicit formula for the generating series of diagonal 3D rook paths

Let $a_n$ denote the number of ways in which a chess rook can move from a corner cell to the opposite corner cell of an $n \times n \times n$ three-dimensional chessboard, assuming that the piece moves closer to the goal cell at each step. We describe the computer-driven \emph{discovery and proof} of the fact that the generating series $G(x)= \sum_{n \geq 0} a_n x^n$ admits the following explicit expression in terms of a Gaussian hypergeometric function: \[ G(x) = 1 + 6 \cdot \int_0^x \frac{\,\pFq21{1/3}{2/3}{2} {\frac{27 w(2-3w)}{(1-4w)^3}}}{(1-4w)(1-64w)} \, dw.\]

preprint2010arXiv

Gradual sub-lattice reduction and a new complexity for factoring polynomials

We present a lattice algorithm specifically designed for some classical applications of lattice reduction. The applications are for lattice bases with a generalized knapsack-type structure, where the target vectors are boundably short. For such applications, the complexity of the algorithm improves traditional lattice reduction by replacing some dependence on the bit-length of the input vectors by some dependence on the bound for the output vectors. If the bit-length of the target vectors is unrelated to the bit-length of the input, then our algorithm is only linear in the bit-length of the input entries, which is an improvement over the quadratic complexity floating-point LLL algorithms. To illustrate the usefulness of this algorithm we show that a direct application to factoring univariate polynomials over the integers leads to the first complexity bound improvement since 1984. A second application is algebraic number reconstruction, where a new complexity bound is obtained as well.

preprint2010arXiv

Isomorphisms of Algebraic Number Fields

Let $\mathbb{Q}(α)$ and $\mathbb{Q}(β)$ be algebraic number fields. We describe a new method to find (if they exist) all isomorphisms, $\mathbb{Q}(β) \rightarrow \mathbb{Q}(α)$ . The algorithm is particularly efficient if the number of isomorphisms is one.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Mark van Hoeij

Research overview

Is this your work?

18 publications

Desingularization and p-Curvature of Recurrence Operators

A Divisor Formula and a Bound on the $\mathbb{Q}$ -gonality of the Modular Curve $X_1(N)$

A Family of Denominator Bounds for First Order Linear Recurrence Systems

A Modular Algorithm for Computing Polynomial GCDs over Number Fields presented with Multiple Extensions

Computing Hypergeometric Solutions of Second Order Linear Differential Equations using Quotients of Formal Solutions and Integral Bases

Hypergeometric Expressions for Generating Functions of Walks with Small Steps in the Quarter Plane

Reduction-Based Creative Telescoping for Fuchsian D-finite Functions

Groebner basis in Boolean rings is not polynomial-space

Belyi functions for hyperbolic hypergeometric-to-Heun transformations

Computing Galois representations and equations for modular curves $X_H(\ell)$

Low Degree Places on the Modular Curve X1(N)

Algorithms and differential relations for Belyi functions

Computing Puiseux Expansions at Cusps of the Modular Curve X0(N)

On Hirzebruch invariants of elliptic fibrations

On stringy invariants of GUT vacua

Explicit formula for the generating series of diagonal 3D rook paths

Gradual sub-lattice reduction and a new complexity for factoring polynomials

Isomorphisms of Algebraic Number Fields

See the researcher in context

Building this map preview

Mark van Hoeij

Research overview

Is this your work?

18 publications

Desingularization and p-Curvature of Recurrence Operators

A Divisor Formula and a Bound on the Q\mathbb{Q}Q-gonality of the Modular Curve X1(N)X_1(N)X1​(N)

A Family of Denominator Bounds for First Order Linear Recurrence Systems

A Modular Algorithm for Computing Polynomial GCDs over Number Fields presented with Multiple Extensions

Computing Hypergeometric Solutions of Second Order Linear Differential Equations using Quotients of Formal Solutions and Integral Bases

Hypergeometric Expressions for Generating Functions of Walks with Small Steps in the Quarter Plane

Reduction-Based Creative Telescoping for Fuchsian D-finite Functions

Groebner basis in Boolean rings is not polynomial-space

Belyi functions for hyperbolic hypergeometric-to-Heun transformations

Computing Galois representations and equations for modular curves XH(ℓ)X_H(\ell)XH​(ℓ)

Low Degree Places on the Modular Curve X1(N)

Algorithms and differential relations for Belyi functions

Computing Puiseux Expansions at Cusps of the Modular Curve X0(N)

On Hirzebruch invariants of elliptic fibrations

On stringy invariants of GUT vacua

Explicit formula for the generating series of diagonal 3D rook paths

Gradual sub-lattice reduction and a new complexity for factoring polynomials

Isomorphisms of Algebraic Number Fields

See the researcher in context

Building this map preview

A Divisor Formula and a Bound on the $\mathbb{Q}$ -gonality of the Modular Curve $X_1(N)$

Computing Galois representations and equations for modular curves $X_H(\ell)$