BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mark van Hoeij

Mark van Hoeij appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Symbolic Computationmath.NTmath.AGhep-thmath.COComputational ComplexityDiscrete Mathematicsmath.CAmath.CV

Catalog footprint

What is connected

18works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

18 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.}

0 citations0 reviewsNo code linkedOpen access
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.\]

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access