
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 ∙ shareread it

Factorization of Cfinite Sequences
We discuss how to decide whether a given Cfinite sequence can be written nontrivially as a product of two other Cfinite sequences.
01/12/2016 ∙ by Manuel Kauers, et al. ∙ 0 ∙ shareread it

ReductionBased 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 ∙ shareread it

Dfinite Numbers
Dfinite functions and Precursive 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 Dfinite functions and Precursive sequences. It consists of the limits of convergent Precursive sequences. Typically, this class contains many wellknown mathematical constants in addition to the algebraic numbers. Our definition of the class of Dfinite 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 Dfinite numbers over the Gaussian rational field are essentially the same as the values of Dfinite functions at nonsingular algebraic number arguments. This result makes it easier to recognize certain numbers as Dfinite.
11/17/2016 ∙ by Hui Huang, et al. ∙ 0 ∙ shareread 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 QRes with the symmetry rule and obtain separations to powerful QBF calculi.
04/04/2018 ∙ by Manuel Kauers, et al. ∙ 0 ∙ shareread it

Hypergeometric Expressions for Generating Functions of Walks with Small Steps in the Quarter Plane
We study nearestneighbors walks on the twodimensional square lattice, that is, models of walks on Z^2 defined by a fixed step set that is a subset of the nonzero 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. BousquetMélou and Mishna [Contemp. Math., pp. 139, Amer. Math. Soc., 2010] identified 19 models of walks that possess a Dfinite 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. 201215, 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 ∙ shareread 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 ∙ shareread it

ReductionBased Creative Telescoping for Fuchsian Dfinite 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 Dfinite functions and develop a reductionbased creative telescoping algorithm for this class of functions, thereby generalizing our recent reductionbased algorithm for algebraic functions, presented at ISSAC 2016.
11/22/2016 ∙ by Shaoshi Chen, et al. ∙ 0 ∙ shareread it

Bounds for Substituting Algebraic Functions into Dfinite Functions
It is well known that the composition of a Dfinite function with an algebraic function is again Dfinite. 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 orderdegree curve which is much more accurate than the orderdegree curve obtained from the usual linear algebra reasoning.
01/26/2017 ∙ by Manuel Kauers, et al. ∙ 0 ∙ shareread it

Apparent Singularities of Dfinite Systems
We generalize the notions of singularities and ordinary points from linear ordinary differential equations to Dfinite systems. Ordinary points of a Dfinite 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 Dfinite system at apparent singularities.
05/02/2017 ∙ by Shaoshi Chen, et al. ∙ 0 ∙ shareread 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 ∙ shareread it