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

Michael Drmota

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

ResearcherUnclaimed source record
math.COmath.NTmath.PRData Structures and AlgorithmsDiscrete MathematicsInformation Theorymath.ITSymbolic Computation

Catalog footprint

What is connected

16works
8topics
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

16 published item(s)

preprint2022arXiv

Primes as sums of Fibonacci numbers

The purpose of this paper is to discuss the relationship between prime numbers and sums of Fibonacci numbers. One of our main results says that for every sufficiently large integer $k$ there exists a prime number that can be represented as the sum of $k$ different and non-consecutive Fibonacci numbers. This property is closely related to, and based on, a prime number theorem for certain morphic sequences. The proof of such a prime number theorem, combined with a corresponding local result, is the central contribution of this paper, from which we derive the result stated in the beginning. Problems of this type have been discussed intensively in the context of the base-$q$ expansion. The Gelfond problems (1968/1969), and the Sarnak conjecture, were the driving forces of this development. Mauduit and Rivat resolved the question on the sum of digits of prime numbers (2010) and the sum of digits of squares (2009), thus leaving open only part of the third Gelfond problem. Later the second author (2017) proved Sarnak's conjecture for all automatic sequences, which are based on the q-ary expansion of integers, and which generalize the sum-of-digits function in base $q$ considerably. In order to obtain corresponding results for Fibonacci numbers, we have to extend Mauduit and Rivat's method considerably. In fact, we are departing significantly from this method, proving the statement that $\exp(2πi \vartheta\mathsf z(n))$ has \emph{level of distribution} $1$ (here $\mathsf z(n)$ is the number of Fibonacci numbers needed to write $n$ as their sum). This latter result forms an essential part of our treatment of the occurring sums of type $\textrm I$ and $\textrm{II}$ and uses Gowers norms related to $\mathsf z(n)$ as a central technical tool. The appearance of Gowers norms in our method is intimately tied to the iterated application of a new generalization of van der Corput's inequality.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Sequential Universal Modeling for Non-Binary Sequences with Constrained Distributions

Sequential probability assignment and universal compression go hand in hand. We propose sequential probability assignment for non-binary (and large alphabet) sequences with empirical distributions whose parameters are known to be bounded within a limited interval. Sequential probability assignment algorithms are essential in many applications that require fast and accurate estimation of the maximizing sequence probability. These applications include learning, regression, channel estimation and decoding, prediction, and universal compression. On the other hand, constrained distributions introduce interesting theoretical twists that must be overcome in order to present efficient sequential algorithms. Here, we focus on universal compression for memoryless sources, and present precise analysis for the maximal minimax and the average minimax for constrained distributions. We show that our sequential algorithm based on modified Krichevsky-Trofimov (KT) estimator is asymptotically optimal up to $O(1)$ for both maximal and average redundancies. This paper follows and addresses the challenge presented in \cite{stw08} that suggested "results for the binary case lay the foundation to studying larger alphabets".

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Effective Erdős-Wintner theorems for digital expansions

In 1972 Delange observed in analogy of the classical Erd\H os-Wintner theorem that $q$-additive functions $f(n)$ has a distribution function if and only if the two series $\sum f(d q^j)$, $\sum f(d q^j)^2$ converge. The purpose of this paper is to provide quantitative versions of this theorem as well as generalizations to other kinds of digital expansions. In addition to the $q$-ary and Cantor case we focus on the Zeckendorf expansion that is based on the Fibonacci sequence, where we provide a sufficient and necessary condition for the existence of a distribution function, namely that the two series $\sum f(F_j)$, $\sum f(F_j)^2$ converge (previously only a sufficient condition was known).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Universal singular exponents in catalytic variable equations

Catalytic equations appear in several combinatorial applications, most notably in the numeration of lattice path and in the enumeration of planar maps. The main purpose of this paper is to show that the asymptotic estimate for the coefficients of the solutions of (so-called) positive catalytic equations has a universal asymptotic behavior. In particular, this provides a rationale why the number of maps of size $n$ in various planar map classes grows asymptotically like $c\cdot n^{-5/2} γ^n$, for suitable positive constants $c$ and $γ$. Essentially we have to distinguish between linear catalytic equations (where the subexponential growth is $n^{-3/2}$) and non-linear catalytic equations (where we have $n^{-5/2}$ as in planar maps). Furthermore we provide a quite general central limit theorem for parameters that can be encoded by catalytic functional equations, even when they are not positive.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Limit Laws of Planar Maps with Prescribed Vertex Degrees

We prove a general multi-dimensional central limit theorem for the expected number of vertices of a given degree in the family of planar maps whose vertex degrees are restricted to an arbitrary (finite or infinite) set of positive integers $D$. Our results rely on a classical bijection with mobiles (objects exhibiting a tree structure), combined with refined analytic tools to deal with the systems of equations on infinite variables that arise. We also discuss possible extensions to maps of higher genus and to weighted maps.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Asymmetric Rényi Problem and PATRICIA Tries

In 1960, Rényi asked for the number of random queries necessary to recover a hidden bijective labeling of n distinct objects. In each query one selects a random subset of labels and asks, what is the set of objects that have these labels? We consider here an asymmetric version of the problem in which in every query an object is chosen with probability p > 1/2 and we ignore "inconclusive" queries. We study the number of queries needed to recover the labeling in its entirety (the height), to recover at least one single element (the fillup level), and to recover a randomly chosen element (the typical depth). This problem exhibits several remarkable behaviors: the depth D_n converges in probability but not almost surely and while it satisfies the central limit theorem its local limit theorem doesn't hold; the height H_n and the fillup level F_n exhibit phase transitions with respect to p in the second term. To obtain these results, we take a unified approach via the analysis of the external profile, defined at level k as the number of elements recovered by the kth query. We first establish new precise asymptotic results for the average and variance, and a central limit law, for the external profile in the regime where it grows polynomially with n. We then extend the external profile results to the boundaries of the central region, leading to the solution of our problem for the height and fillup level. As a bonus, our analysis implies novel results for analogous parameters of random PATRICIA tries.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Graph limits of random graphs from a subset of connected $k$-trees

For any set $Ω$ of non-negative integers such that $\{0,1\}\subseteq Ω$ and $\{0,1\}\ne Ω$, we consider a random $Ω$-$k$-tree ${\sf G}_{n,k}$ that is uniformly selected from all connected $k$-trees of $(n+k)$ vertices where the number of $(k+1)$-cliques that contain any fixed $k$-clique belongs to $Ω$. We prove that ${\sf G}_{n,k}$, scaled by $(kH_{k}σ_Ω)/(2\sqrt{n})$ where $H_{k}$ is the $k$-th Harmonic number and $σ_Ω>0$, converges to the Continuum Random Tree $\mathcal{T}_{\sf e}$. Furthermore, we prove the local convergence of the rooted random $Ω$-$k$-tree ${\sf G}_{n,k}^{\circ}$ to an infinite but locally finite random $Ω$-$k$-tree ${\sf G}_{\infty,k}$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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) \geq 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)\cdots(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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Vertex Degrees in Planar Maps

We prove a general multi-dimensional central limit theorem for the expected number of vertices of a given degree in the family of planar maps whose vertex degrees are restricted to an arbitrary (finite or infinite) set of positive integers D. Our results rely on a classical bijection with mobiles (objects exhibiting a tree structure), combined with refined analytic tools to deal with the systems of equations on infinite variables that arise. We also discuss some possible extension to maps of higher genus.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Gaussian limit process for optimal FIND algorithms

We consider versions of the FIND algorithm where the pivot element used is the median of a subset chosen uniformly at random from the data. For the median selection we assume that subsamples of size asymptotic to $c \cdot n^α$ are chosen, where $0<α\le \frac{1}{2}$, $c>0$ and $n$ is the size of the data set to be split. We consider the complexity of FIND as a process in the rank to be selected and measured by the number of key comparisons required. After normalization we show weak convergence of the complexity to a centered Gaussian process as $n\to\infty$, which depends on $α$. The proof relies on a contraction argument for probability distributions on c{à}dl{à}g functions. We also identify the covariance function of the Gaussian limit process and discuss path and tail properties.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Disproof of a conjecture by Rademacher on partial fractions

In his book Topics in Analytic Number Theory, Rademacher considered the generating function of partitions into at most $N$ parts, and conjectured certain limits for the coefficients of its partial fraction decomposition. We carry out an asymptotic analysis that disproves this conjecture, thus confirming recent observations of Sills and Zeilberger (Journal of Difference Equations and Applications 19, 2013), who gave strong numerical evidence against the conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Shape of Unlabeled Rooted Random Trees

We consider the number of nodes in the levels of unlabelled rooted random trees and show that the stochastic process given by the properly scaled level sizes weakly converges to the local time of a standard Brownian excursion. Furthermore we compute the average and the distribution of the height of such trees. These results extend existing results for conditioned Galton-Watson trees and forests to the case of unlabelled rooted trees and show that they behave in this respect essentially like a conditioned Galton-Watson process.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

The Distribution of Patterns in Random Trees

Let $T\_n$ denote the set of unrooted labeled trees of size $n$ and let $T\_n$ be a particular (finite, unlabeled) tree. Assuming that every tree of $T\_n$ is equally likely, it is shown that the limiting distribution as $n$ goes to infinity of the number of occurrences of $M$ as an induced subtree is asymptotically normal with mean value and variance asymptotically equivalent to $μn$ and $σ^2n$, respectively, where the constants $μ>0$ and $σ\ge 0$ are computable.

0 citations0 reviewsNo code linkedOpen access