Voronoi summation formulae and multiplicative functions on permutations

We prove a Tauberian theorem for the Voronoi summation method of divergent series with an estimate of the remainder term. The results on the Voronoi summability are then applied to analyze the mean values of multiplicative functions on random permutations.     

Additive multiplicative increasing functions on nonnegative square matrices and multidigraphs

It is known that if f is a multiplicative increasing function on , then either f(n)=0 for all or f(n)=n for some 0. It is very natural to ask if there are similar results in other algebraic systems. In this paper, we first study the multiplicative increasing functions over nonnegative square matrices with respect to tensor product and then restrict our result to multidigraphs and loopless multidigraphs.     

Additive and multiplicative Sidon sets

Acta Mathematica Hungarica - We give a construction of a set $$A \subset \mathbb N$$ such that any subset $${A' \subset A}$$ with $$|A'| \gg |A|^{2/3}$$ is neither an additive nor...     

Additive and multiplicative Sidon sets

Summary Inspired by a paper of Sárk?zy [4] we study sets of integers and sets of residues with the property that all sums and all products are distinct.     

Spherically symmetric random permutations

We consider random permutations which are spherically symmetric with respect to a metric on the symmetric group S_n and are consistent as n varies. The extreme infinitely spherically symmetric permutation‐valued processes are identified for the Hamming, Kendall‐tau and Cayley metrics. The proofs in all three cases are based on a unified approach through stochastic monotonicity.     

Extending simulation uses of antithetic variables: partially monotone functions, random permutations, and random subsets

We show how to effectively use antithetic variables to evaluate the expected value of (a) functions of independent random variables, when the functions are monotonic in only some of their variables, (b) Schur functions of random permutations, and (c) monotone functions of random subsets.     

Alternating permutations and symmetric functions

We use the theory of symmetric functions to enumerate various classes of alternating permutations w of {1,2,…,n}. These classes include the following: (1) both w and w⁻¹ are alternating, (2) w has certain special shapes, such as (m−1,m−2,…,1), under the RSK algorithm, (3) w has a specified cycle type, and (4) w has a specified number of fixed points. We also enumerate alternating permutations of a multiset. Most of our formulas are umbral expressions where after expanding the expression in powers of a variable E, Ek is interpreted as the Euler number Ek. As a small corollary, we obtain a combinatorial interpretation of the coefficients of an asymptotic expansion appearing in Ramanujan's “Lost” Notebook.     

Efficient sampling of random permutations

We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external memory. In contrast to previously known work for parallel setups, our method is able to fulfill the three criteria of uniformity, work-optimality and balance among the processors simultaneously. To guarantee the uniformity we investigate the matrix of communication requests between the processors. We show that its distribution is a generalization of the multivariate hypergeometric distribution and we give algorithms to sample it efficiently in the two settings.     

Integrals over Grassmannians and random permutations

Testing the independence of two Gaussian populations involves the distribution of the sample canonical correlation coefficients, given that the actual correlation is zero. The “Laplace transform” (as a function of x) of this distribution is not only an integral over the Grassmannian of p-dimensional planes in real, complex or quaternion n-space , but is also related to a generalized hypergeometric function. Such integrals are solutions of Painlevé-like equations; in the complex case, they are solutions to genuine Painlevé equations. These integrals over have remarkable expansions in x, related to random words of length ? formed with an alphabet of p letters 1,…,p. The coefficients of these expansions are given by the probability that a word (i) contains a subsequence of letters p,p−1,…,1 in that order and (ii) that the maximal length of the disjoint union of p−1 increasing subsequences of the word is ?k, where k refers to the power of x. Note that, if each letter appears in the word, then the maximal length of the disjoint union of p increasing subsequences of the word is automatically =? and is thus trivial.     

Increasing permutations of random processes

The paper is concerned with an application of limit theorems to the study of increasing permutations of stable random processes. By the increasing permutation of a function is meant the nondecreasing function with the same distribution. The trajectories of a random process may be approximated by step-functions, and then the continuity of the increasing permutation operator permits one to apply the Skorokhod invariance principle to obtain the distribution of the random process. The distribution function and the expected value of the increasing permutation of a stable random process are given explicitly. Also the univariate distributions of the increasing permutation of the Cauchy process are obtained. In various normed spaces the images of the unit balls with respect to the operator of increasing permutation are described. A separate section is devoted to the increasing permutations of higher-dimensional processes. Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 216, 1994, pp. 62–75. Translated by A. Sudakov.     

Simple permutations and algebraic generating functions

A simple permutation is one that never maps a nontrivial contiguous set of indices contiguously. Given a set of permutations that is closed under taking subpermutations and contains only finitely many simple permutations, we provide a framework for enumerating subsets that are restricted by properties belonging to a finite “query-complete set.” Such properties include being even, being an alternating permutation, and avoiding a given generalised (blocked or barred) pattern. We show that the generating functions for these subsets are always algebraic, thereby generalising recent results of Albert and Atkinson. We also apply these techniques to the enumeration of involutions and cyclic closures.     

The shape of random pattern-avoiding permutations

We initiate the study of limit shapes for random permutations avoiding a given pattern. Specifically, for patterns of length 3, we obtain delicate results on the asymptotics of distributions of positions of numbers in the permutations. We view the permutations as 0–1 matrices to describe the resulting asymptotics geometrically. We then apply our results to obtain a number of results on distributions of permutation statistics.     

The cyclic structure of random permutations

Letα _r denote the number of cycles of length r in a random permutation, taking its values with equal probability from among the set S_n of all permutations of length n. In this paper we study the limiting behavior of linear combinations of random permutationsα ₁, ...,α _r having the form $$\zeta _{n, r} = c_{r1^{a_1 } } + ... + c_{rr} a_r $$ in the case when n, r→∞. We shall show that the class of limit distributions forξ _n,r as n, r→∞ and r In r/h→0 coincides with the class of unbounded divisible distributions. For the random variables η_n, r=α ₁+2α ₂+... rα _r, equal to the number of elements in the permutation contained in cycles of length not exceeding r, we find' limit distributions of the form r In r/n→0 and r=γ ⁿ, 0<γ<1.     

On random permutations of finite groups

Given a finite abelian group G,  consider a uniformly random permutation of the set of all elements of G. Compute the difference of each pair of consecutive elements along the permutation. What is the number of occurrences of \(h\in G\setminus \{0\}\) in this sequence of differences? How do these numbers of occurrences behave for several group elements simultaneously? Can we get similar results for non-abelian G? How do the answers change if differences are replaced by sums? In this paper, we answer these questions. Moreover, we formulate analogous results in a general combinatorial setting.

     

On multiplicative functions on consecutive integers

Let f and g be multiplicative functions of modulus 1. Assume that \( {\lim_{x \to \infty }}\frac{1}{x}\left| {\sum\nolimits_{n \leqslant x} {f(n)} } \right| = A > 0 \) and \( {\lim_{x \to \infty }}\frac{1}{x}\left| {\sum\nolimits_{n \leqslant x} {g(n)} } \right| = 0 \). We prove that, under these conditions,

$ \mathop {\lim }\limits_{x \to \infty } \frac{1}{x}\sum\limits_{n \leqslant x} {f(n)g(n + 1) = 0.}$

Concerning the Liouville function λ, we find an upper estimate for \( \frac{1}{x}\left| {\sum\limits_{n \leqslant x} {\lambda (n)\lambda (n + 1)} } \right| \) under the unproved hypothesis that L(s, χ) have Siegel zeros for an infinite sequence of L-functions.

     

A theorem on totally multiplicative functions

In this paper we resolve in the affirmative a conjecture of Emma Lehmer that there are exactly two totally multiplicative functions F taking on values ±1, with F(2)=+1, for which there are no positive integers a,a+2, a+3 with F(a)=F(a+2)=F(a+3)=+1.Research supported by Natural Sciences and Engineering Research Council Canada Grant #A-7233     

Additive and multiplicative tolerance in multiobjective linear programming

We consider a multiobjective linear program. We propose a procedure for computing an additive and multiplicative (percentage) tolerance in which all the objective function coefficients may simultaneously and independently vary while preserving the efficiency of a given solution. For a nondegenerate basic solution, the procedure runs in polynomial time.