A class of finitary codes

It is shown that for any two Bernoulli schemes with a finite number of states and unequal entropies, there exists a finitary homomorphism from the scheme with larger entropy to the one with smaller entropy.     

Perfect simulation with exponential tails on the running time

Monte Carlo algorithms typically need to generate random variates from a probability distribution described by an unnormalized density or probability mass function. Perfect simulation algorithms generate random variates exactly from these distributions, but have a running time T that is itself an unbounded random variable. This article shows that commonly used protocols for creating perfect simulation algorithms, such as Coupling From the Past can be used in such a fashion that the running time is unlikely to be very much larger than the expected running time. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Universal hashing and authentication codes

In this paper, we study the application of universal hashing to the construction of unconditionally secure authentication codes without secrecy. This idea is most useful when the number of authenticators is exponentially small compared to the number of possible source states (plaintext messages). We formally define some new classes of hash functions and then prove some new bounds and give some general constructions for these classes of hash functions. Then we discuss the implications to authentication codes.A preliminary version of this paper was presented at CRYPTO '91 and appeared in Lecture Notes in Computer Science, vol. 576, pp. 74–85, Springer-Verlag, 1992.     

An exponential inequality for suprema of empirical processes with heavy tails on the left

In this Note, we provide exponential inequalities for suprema of empirical processes with heavy tails on the left. Our approach is based on a martingale decomposition, associated with comparison inequalities over a cone of convex functions originally introduced by Pinelis. Furthermore, the constants in our inequalities are explicit.     

Superlarge deviation probabilities for sums of independent lattice random variables with exponential decreasing tails

In the note we study large and superlarge deviation probabilities of sum of i.i.d. lattice random variables, whose distribution function has an exponentially decreasing tail at infinity.     

Weight of duals of BCH codes and exponential sums

We consider a binary BCH code C_m of length 2^m–1. If m is odd, we improve the bound on the distance of the dual of C_m previously given by Carlitz–Uchiyama, Serre and Moreno–Moreno.     

Exponential and double exponential tails for maximum of two-dimensional discrete Gaussian free field

We study the tail behavior for the maximum of discrete Gaussian free field on a 2D box with Dirichlet boundary condition after centering by its expectation. We show that it exhibits an exponential decay for the right tail and a double exponential decay for the left tail. In particular, our result implies that the variance of the maximum is of order 1, improving an $o(\log n)$ bound by Chatterjee (Chaos, concentration, and multiple valleys, 2008) and confirming a folklore conjecture. An important ingredient for our proof is a result of Bramson and Zeitouni (Commun. Pure Appl. Math, 2010), who proved the tightness of the centered maximum together with an evaluation of the expectation up to an additive constant.     

Groups with finitary classes of conjugate elements

A class of conjugate elements of a group is called finitary if the conjugation action of the group induces a group of finitary permutations of this class. A group with finitary classes of conjugate elements will be called a ΦC-group. Some characterizations of ΦC-groups in the class of all groups have been obtained. It is also shown for every ΦC-group that either it is an FC-group, i.e., a group with finite classes of conjugate elements, or its structure is close to the structure of a totally imprimitive group of finitary permutations.     

A finitary Tits' alternative

It is shown that for any family of finite groups of uniformly bounded rank, either (i) a subdirect product of these groups contains a non-cyclic free group, or (ii) there exists a single word w which is a law in each group, and moreover, if N is the length of the word, and r the maximal rank of each finite group, then each group is nilpotent-of-bounded class-by-abelian-by-bounded-index, with the bounds being functions of N and r alone. Additionally, various corollaries are derived from this result.     

Constructing finitary isomorphisms with finite expected coding times

This paper is motivated by the question of whether the invariants β, Δ,cΔ completely characterize isomorphism of Markov chains by finitary isomorphisms that have finite expected coding times (fect). We construct a finitary isomorphism with fect under an additional condition. Whether coincidence of β, Δ,cΔ implies the required condition remains open.     

Bound for mixed exponential sums associated to binary good cyclic codes

In this paper, we give an improved bound for mixed exponential sums associated to good cyclic codes.     

Complex finitary simple Lie algebras

An algebra is called finitary if it consists of finite-rank transformations of a vector space. We classify finitary simple Lie algebras over an algebraically closed field of zero characteristic. It is shown that any such algebra is isomorphic to one of the following¶ (1) a special transvection algebra \frak t(V,P)\frak t(V,\mit\Pi );¶ (2) a finitary orthogonal algebra \frak fso (V,q)\frak {fso} (V,q); ¶ (3) a finitary symplectic algebra \frak fsp (V,s)\frak {fsp} (V,s).¶Here V is an infinite dimensional K-space; q (respectively, s) is a symmetric (respectively, skew-symmetric) nondegenerate bilinear form on V; and P\Pi is a subspace of the dual V^* whose annihilator in V is trivial: 0={v ? V | Pv=0}0=\{{v}\in V\mid \Pi {v}=0\}.     

On geometric and finitary sketches

A survey of results on categories which can be sketched by a finitary sketch (i.e., a sketch with finite limit and finite colimit specifications) or by a geometric sketch (i.e., a sketch with finite limit specifications and arbitrary colimit specifications) is presented. Transitive-hull theories are introduced which precisely characterize finitarily sketchable categories.Financial support of the Grant Agency of the Czech Republic under the grant No 201/93/0950 is gratefully acknowledged.