Manuel Kauers

is this you? claim profile


Professor for algebra at the Johannes Kepler University

  • On a Conjecture of Cusick Concerning the Sum of Digits of n and n + t

    For a nonnegative integer t, let c_t be the asymptotic density of natural numbers n for which s(n + t) ≥ s(n), where s(n) denotes the sum of digits of n in base 2. We prove that c_t > 1/2 for t in a set of asymptotic density 1, thus giving a partial solution to a conjecture of T. W. Cusick stating that c_t > 1/2 for all t. Interestingly, this problem has several equivalent formulations, for example that the polynomial X(X + 1)...(X + t - 1) has less than 2^t zeros modulo 2^t+1. The proof of the main result is based on Chebyshev's inequality and the asymptotic analysis of a trivariate rational function, using methods from analytic combinatorics.

    09/29/2015 ∙ by Michael Drmota, et al. ∙ 0 share

    read it

  • Factorization of C-finite Sequences

    We discuss how to decide whether a given C-finite sequence can be written nontrivially as a product of two other C-finite sequences.

    01/12/2016 ∙ by Manuel Kauers, et al. ∙ 0 share

    read it

  • Reduction-Based Creative Telescoping for Algebraic Functions

    Continuing a series of articles in the past few years on creative telescoping using reductions, we develop a new algorithm to construct minimal telescopers for algebraic functions. This algorithm is based on Trager's Hermite reduction and on polynomial reduction, which was originally designed for hyperexponential functions and extended to the algebraic case in this paper.

    02/01/2016 ∙ by Shaoshi Chen, et al. ∙ 0 share

    read it

  • D-finite Numbers

    D-finite functions and P-recursive sequences are defined in terms of linear differential and recurrence equations with polynomial coefficients. In this paper, we introduce a class of numbers closely related to D-finite functions and P-recursive sequences. It consists of the limits of convergent P-recursive sequences. Typically, this class contains many well-known mathematical constants in addition to the algebraic numbers. Our definition of the class of D-finite numbers depends on two subrings of the field of complex numbers. We investigate how difference choices of these two subrings affect the class. Moreover, we show that D-finite numbers over the Gaussian rational field are essentially the same as the values of D-finite functions at non-singular algebraic number arguments. This result makes it easier to recognize certain numbers as D-finite.

    11/17/2016 ∙ by Hui Huang, et al. ∙ 0 share

    read it

  • Short Proofs for Some Symmetric Quantified Boolean Formulas

    We exploit symmetries to give short proofs for two prominent formula families of QBF proof complexity. On the one hand, we employ symmetry breakers. On the other hand, we enrich the (relatively weak) QBF resolution calculus Q-Res with the symmetry rule and obtain separations to powerful QBF calculi.

    04/04/2018 ∙ by Manuel Kauers, et al. ∙ 0 share

    read it

  • 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 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 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 × 4 combinatorially meaningful specializations only four are algebraic functions.

    06/09/2016 ∙ by Alin Bostan, et al. ∙ 0 share

    read it

  • Some Open Problems related to Creative Telescoping

    Creative telescoping is the method of choice for obtaining information about definite sums or integrals. It has been intensively studied since the early 1990s, and can now be considered as a classical technique in computer algebra. At the same time, it is still subject of ongoing research. In this paper, we present a selection of open problems in this context. We would be curious to hear about any substantial progress on any of these problems.

    09/13/2016 ∙ by Shaoshi Chen, et al. ∙ 0 share

    read it

  • 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.

    11/22/2016 ∙ by Shaoshi Chen, et al. ∙ 0 share

    read it

  • Bounds for Substituting Algebraic Functions into D-finite Functions

    It is well known that the composition of a D-finite function with an algebraic function is again D-finite. We give the first estimates for the orders and the degrees of annihilating operators for the compositions. We find that the analysis of removable singularities leads to an order-degree curve which is much more accurate than the order-degree curve obtained from the usual linear algebra reasoning.

    01/26/2017 ∙ by Manuel Kauers, et al. ∙ 0 share

    read it

  • Apparent Singularities of D-finite Systems

    We generalize the notions of singularities and ordinary points from linear ordinary differential equations to D-finite systems. Ordinary points 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.

    05/02/2017 ∙ by Shaoshi Chen, et al. ∙ 0 share

    read it

  • On the maximal minimal cube lengths in distinct DNF tautologies

    Inspired by a recent article by Anthony Zaleski and Doron Zeilberger, we investigate the question of determining the largest k for which there exists boolean formulas in disjunctive normal form (DNF) with n variables, none of whose conjunctions are `parallel', and such that all of them have at least k literals. Using a SAT solver, we answer some of the questions they left open. We also determine the corresponding numbers for DNFs obeying certain symmetries.

    02/09/2019 ∙ by Manuel Kauers, et al. ∙ 0 share

    read it