BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Daniel Krenn appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
In this paper we consider a number of natural decision problems involving k-regular sequences. Specifically, they arise from - lower and upper bounds on growth rate; in particular boundedness, - images, - regularity (recognizability by a deterministic finite automaton) of preimages, and - factors, such as squares and palindromes of such sequences. We show that the decision problems are undecidable.
In this note the precise minimum number of key comparisons any dual-pivot quickselect algorithm (without sampling) needs on average is determined. The result is in the form of exact as well as asymptotic formulæ of this number of a comparison-optimal algorithm. It turns out that the main terms of these asymptotic expansions coincide with the main terms of the corresponding analysis of the classical quickselect, but still---as this was shown for Yaroslavskiy quickselect---more comparisons are needed in the dual-pivot variant. The results are obtained by solving a second order differential equation for the generating function obtained from a recursive approach.
We present an average case analysis of two variants of dual-pivot quicksort, one with a non-algorithmic comparison-optimal partitioning strategy, the other with a closely related algorithmic strategy. For both we calculate the expected number of comparisons exactly as well as asymptotically, in particular, we provide exact expressions for the linear, logarithmic, and constant terms. An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proven.
This article deals with redundant digit expansions with an imaginary quadratic algebraic integer with trace $\pm 1$ as base and a minimal norm representatives digit set. For $w\geq 2$ it is shown that the width-$w$ non-adjacent form is not an optimal expansion, meaning that it does not minimize the (Hamming-)weight among all possible expansions with the same digit set. One main part of the proof uses tools from Diophantine analysis, namely the theory of linear forms in logarithms and the Baker--Davenport reduction method.
For fixed $t\ge 2$, we consider the class of representations of $1$ as sum of unit fractions whose denominators are powers of $t$ or equivalently the class of canonical compact $t$-ary Huffman codes or equivalently rooted $t$-ary plane "canonical" trees. We study the probabilistic behaviour of the height (limit distribution is shown to be normal), the number of distinct summands (normal distribution), the path length (normal distribution), the width (main term of the expectation and concentration property) and the number of leaves at maximum distance from the root (discrete distribution).
In a multi-base representation of an integer (in contrast to, for example, the binary or decimal representation) the base (or radix) is replaced by products of powers of single bases. The resulting numeral system has desirable properties for fast arithmetic. It is usually redundant, which means that each integer can have multiple different digit expansions, so the natural question for the number of representations arises. In this paper, we provide a general asymptotic formula for the number of such multi-base representations of a positive integer $n$. Moreover, we prove central limit theorems for the sum of digits, the Hamming weight (number of non-zero digits, which is a measure of efficiency) and the occurrences of a fixed digits in a random representation.
For a fixed integer base $b\geq2$, we consider the number of compositions of $1$ into a given number of powers of $b$ and, related, the maximum number of representations a positive integer can have as an ordered sum of powers of $b$. We study the asymptotic growth of those numbers and give precise asymptotic formulae for them, thereby improving on earlier results of Molteni. Our approach uses generating functions, which we obtain from infinite transfer matrices. With the same techniques the distribution of the largest denominator and the number of distinct parts are investigated.
We analyse the number of occurrences of a fixed non-zero digit in the width-w non-adjacent forms of all elements of a lattice in some region (e.g. a ball). Our result is an asymptotic formula, where its main term coincides with the full block length analysis. In its second order term a periodic fluctuation is exhibited. The proof follows Delange's method. This result in a general lattice set-up is then used for numeral systems with an algebraic integer as base. Those come from efficient scalar multiplication methods (Frobenius-and-add methods) in hyperelliptic curves cryptography, and our result is needed for analysing the running time of such algorithms.
We describe the Sylow $p$-groups of the group of polynomial permutations of the integers mod $p^n$.
We consider digital expansions to the base of $τ$, where $τ$ is an algebraic integer. For a $w \geq 2$, the set of admissible digits consists of 0 and one representative of every residue class modulo $τ^w$ which is not divisible by $τ$. The resulting redundancy is avoided by imposing the width $w$-NAF condition, i.e., in an expansion every block of $w$ consecutive digits contains at most one non-zero digit. Such constructs can be efficiently used in elliptic curve cryptography in conjunction with Koblitz curves. The present work deals with analysing the number of occurrences of a fixed non-zero digit. In the general setting, we study all $w$-NAFs of given length of the expansion. We give an explicit expression for the expectation and the variance of the occurrence of such a digit in all expansions. Further a central limit theorem is proved. In the case of an imaginary quadratic $τ$ and the digit set of minimal norm representatives, the analysis is much more refined: We give an asymptotic formula for the number of occurrence of a digit in the $w$-NAFs of all elements of $\Z[τ]$ in some region (e.g. a disc). The main term coincides with the full block length analysis, but a periodic fluctuation in the second order term is also exhibited. The proof follows Delange's method. We also show that in the case of imaginary quadratic $τ$ and $w \geq 2$, the digit set of minimal norm representatives leads to $w$-NAFs for \emph{all} elements of $\Z[τ]$. Additionally some properties of the fundamental domain are stated.
We consider digital expansions in lattices with endomorphisms acting as base. We focus on the $w$-non-adjacent form ($w$-NAF), where each block of $w$ consecutive digits contains at most one non-zero digit. We prove that for sufficiently large $w$ and an expanding endomorphism, there is a suitable digit set such that each lattice element has an expansion as a $w$-NAF. If the eigenvalues of the endomorphism are large enough and $w$ is sufficiently large, then the $w$-NAF is shown to minimise the weight among all possible expansions of the same lattice element using the same digit system.
Let $\ord$ be the maximal order of a number field. Belcher showed in the 1970s that every algebraic integer in $\ord$ is the sum of pairwise distinct units, if the unit equation $u+v=2$ has a non-trivial solution $u,v\in\ord^*$. We generalize this result and give applications to signed double-base digit expansions.
Efficient scalar multiplication in Abelian groups (which is an important operation in public key cryptography) can be performed using digital expansions. Apart from rational integer bases (double-and-add algorithm), imaginary quadratic integer bases are of interest for elliptic curve cryptography, because the Frobenius endomorphism fulfils a quadratic equation. One strategy for improving the efficiency is to increase the digit set (at the prize of additional precomputations). A common choice is the width\nbd-$w$ non-adjacent form (\wNAF): each block of $w$ consecutive digits contains at most one non-zero digit. Heuristically, this ensures a low weight, i.e.\ number of non-zero digits, which translates in few costly curve operations. This paper investigates the following question: Is the \wNAF{}-expansion optimal, where optimality means minimising the weight over all possible expansions with the same digit set? The main characterisation of optimality of \wNAF{}s can be formulated in the following more general setting: We consider an Abelian group together with an endomorphism (e.g., multiplication by a base element in a ring) and a finite digit set. We show that each group element has an optimal \wNAF{}-expansion if and only if this is the case for each sum of two expansions of weight 1. This leads both to an algorithmic criterion and to generic answers for various cases. Imaginary quadratic integers of trace at least 3 (in absolute value) have optimal \wNAF{}s for $w\ge 4$. The same holds for the special case of base $(\pm 3\pm\sqrt{-3})/2$ and $w\ge 2$, which corresponds to Koblitz curves in characteristic three. In the case of $τ=\pm1\pm i$, optimality depends on the parity of $w$. Computational results for small trace are given.