text:
# Molecular dynamics study of melting of a bcc metal-vanadium I : mechanical melting

## 1  Introduction

Over the years, several theories explaining the mechanism of melting have been proposed.  This research has by now evolved to a state where a clear distinction exists between two possible scenarios for the melting transition: a first scenario of homogeneous, or mechanical melting resulting from lattice instability  and/or a spontaneous generation of thermal defects, and a second scenario of heterogeneous, or thermodynamic melting which begins at extrinsic defects such as a free surface or an internal interface (grain boundaries, voids, etc). Throughout this paper we will use the term mechanical melting to describe the former case, which we consider here. In particular, we take the view proposed by Born that at the melting point a ’rigidity catastrophe’ is caused by the vanishing of one of the elastic shear moduli, $`C_{44}`$, or $`C^{}=(C_{11}C_{12})/2`$. In other words, the crystal melts once it loses its ability to resist shear. This condition determines the mechanical melting temperature, $`T_s`$, of a perfectly homogeneous bulk crystal and was confirmed in extensive studies of fcc metals.

Tallon pointed out that a mechanical instability arises when the solid expands up to a critical specific volume which is close to that of the liquid phase (melt). In the study by Wang et al. of the mechanical melting transition of an fcc solid under external stress, it was found that volume expansion is the underlying cause of lattice instability. Kanigel et al.  confirmed this scenario in a simulation of fcc copper in the presence of point defects. They showed that the critical volume at which a crystal of copper melts is independent of the path through phase space by which it is reached, whether by heating of the perfect crystal or by adding point defects to expand the solid at a constant temperature .

Solids can undergo mechanical melting only if they have no extended defects , a situation which is conveniently realized in three-dimensional computer simulations by means of periodic boundary conditions which eliminate the surface. Simulations of atomic dynamics for solids with an fcc  or diamond  structures show, among other things, the onset of a shear instability of the solid at a temperature $`T_s`$, which can exceed the thermodynamic melting temperature $`T_m`$ by some 20%, depending on the details of the potential.

Given the considerable degree of understanding of the melting process of fcc crystals, it is of substantial interest to see if the scenario of mechanical melting also applies to solids having a different lattice structure. We therefore decided to study mechanical melting of a bcc metal, vanadium, by means of computer simulations. We present details of the calculations in Sec. II. In Sec. III we describe the results of the simulation of some physical properties of a vanadium with and without point defects. In Sec. IV we present molecular dynamics simulation results for mechanical melting in the presence of point defects. Finally, in Sec. IV, we discuss the implication of our results for the question of the microscopic mechanism of melting.

## 2  Simulation details

We model the bulk melting transition of vanadium using the molecular dynamics simulation  technique. The choice of vanadium has no special significance as we are only interested in the generic features of metallic solids with a bcc lattice symmetry. While various many-body potentials for fcc metals  have been developed and thoroughly tested in numerous simulations, the situation with such potentials for bcc metals is not as good. This can be explained by the more complicated nature of the bcc metals in comparison with fcc ones which manifests itself in the wide range of elastic constants (and even in the negative values of the Cauchy condition $`C_{12}C_{44}<0`$ for some bcc metals). The packing density of atoms in a bcc lattice is smaller than in a fcc lattice (there are 8 nearest-neighbors in a bcc lattice and 12 nearest-neighbors in a fcc). However, the second nearest-neighbor distance in the bcc structure is larger than the first nearest-neighbor distance by only about 15%. Therefore, the interaction between the second order and the first order nearest-neighbors in bcc metals is not negligible, even with screening.

In addition, band structure effects are crucial for bcc metals. A simple approximation which assumes that the electron density can be considered as a superposition of atomic orbitals is successful for fcc metals, but less appropriate for bcc metals. Therefore, for metals with the bcc structure electron density is chosen to be an adjustable function, rather than a superposition of atomic orbitals. Furthermore, angle dependent interactions could be very important in bcc solids.

For our simulations, we chose the many-body interaction potential developed by Finnis and Sinclair  (FS), and modified by Rebonato et al.  FS proposed a way to incorporate the delocalized physical nature of the metallic bonding and the essential band character of bcc metals in a simple model. The FS potential involves two short ranged potentials, a cohesive one and a repulsive one. The cohesive potential is summed over neighbors and the square root of the result describes the bonding energy. The cohesive energy is therefore proportional to $`\sqrt{z}`$, where $`z`$ is the atomic coordination number. The square root form is used assuming that the band energy is the sum of occupied one-electron levels, and according to the tight-binding model the cohesive energy is proportional to the hopping integrals between the d-orbitals. The repulsive potential is summed in the usual way to describe the repulsive core-core interactions.

Our molecular dynamics (MD) simulations with the FS potential were performed using the Parinello-Rahman  method and the Nose-Hoover thermostat. This ensemble is identified as an isothermal-isotensional ensemble (NtT),  which allows simulation of fluctuations in the shape and volume of the sample (here, $`N`$ is the number of atoms, $`T`$ the temperature, $`V`$ the volume and $`t`$ is the sample tension). The shape and volume thus obtained were used for calculation of the shear modulus in a canonical (NVT) ensemble. The shear elastic moduli were calculated using the fluctuations of the stress tensor.

The samples used for the simulations contained 2000 atoms, initially arranged as a perfect bcc crystal of size 10x10x20 unit cells. Periodic boundary conditions were applied in all three directions. Point defects were introduced either by the insertion of extra atoms between the lattice sites (self-interstitials) or by the removal of atoms from the lattice (vacancies). Newton’s equations of motion were solved using a predictor-corrector algorithm.  Throughout this study, interactive visualization with the AViz program  was implemented.

## 3  Validation of the potential and order parameter

To learn about the capatibility of the potential, we examined some physical properties of a perfect crystal. First, we calculated the thermal expansion at zero external pressure. We found the thermal expansion coefficient at low temperatures to be $`\alpha _c=(18\pm 6)\times 10^6K^1`$, in reasonable agreement with the experimental value measured at room temperature $`\alpha _{\mathrm{exp}}=8.6\times 10^6K^1`$. Next, the thermodynamic melting temperature for our potential was calculated, using the method of Lutshko et al. , to be $`T_m=2220\pm 10`$ K. This value is close to the experimental value $`T_m=2183`$ K, despite the fact that the FS potential was constructed by fitting its parameters to room temperature values of various physical properties of vanadium (lattice constant, cohesion energy, shear elastic moduli, vacancy formation energy, etc).

In order to test the algorithm we calculated the shear moduli as a function of temperature. The shear elastic coefficients decrease with temperature as shown in Fig. 1.

The accuracy of the simulations was estimated by monitoring the convergence of the shear elastic moduli calculated along symmetrically equivalent directions. We found the difference to be approximately 10%.

Following the validation that our potential can indeed reproduce the physical properties of a perfect crystal with acceptable accuracy, point defects were introduced. These point defects are distributed homogeneously throughout the bulk of the solid. Only one type of point defects, e.g. vacancies or self-interstitials were used in each run to avoid their mutual annihilation.

The configurations of atoms in the vicinity of a point defect inside the bulk at low temperatures was investigated by means of the simulated tempering method.  The most energetically favored configuration of an interstitial was found to be the $`<011>`$ dumb-bell split - interstitial (See Fig. 2) with a formation energy of $`E_f=4.18\pm 0.02eV`$. This formation energy is in agreement with that of previous simulations .

To investigate the temperature dependence of the crystalline order, we define the structure order parameter $`\eta `$:

$$\eta =\frac{1}{N^2}\left|\underset{i=1}{\overset{N}{}}\mathrm{cos}(\stackrel{}{k}\stackrel{}{r}_i)\right|^2+\frac{1}{N^2}\left|\underset{i=1}{\overset{N}{}}\mathrm{sin}(\stackrel{}{k}\stackrel{}{r}_i)\right|^2$$
(1)
where $`\stackrel{}{k}=\{0,0,2\pi /a\}`$ is a vector of the reciprocal lattice, $`\stackrel{}{r}_i`$ is the position of atom $`i`$, $`N`$ is the number of the atoms in the sample, and the angular brackets stands for ensemble average. For an ideal-crystal lattice at zero temperature, $`\eta `$ equals unity, while in the liquid state, $`\eta `$ fluctuates near zero.

We calculated $`\delta \eta /\delta C`$, the change of the order parameter upon the introduction of point defects. Here, $`C`$ is the concentration of point defects, given in % of the number of atoms. Fig. 3 shows the result of this calculation for small $`C`$ ,and at different temperatures. The introduction of self \- interstitials results in noticeable decrease of the structure order parameter (from $`\eta 0.6`$ to $`\eta 0.4`$), while the influence of vacancies is relatively weaker. With increasing temperature, the order parameter becomes increasingly sensitive to the introduction of point defects, as evidenced by the increase of the absolute value of $`|\delta \eta /\delta C|`$ with temperature. We believe that this increased sensitivity results from the increase of the amplitude of thermal vibration of the atoms in the immediate vicinity of the point defect.

Introduction of self - interstitials increases the volume of the sample (See Fig. 4) while vacancies decrease the volume, as shown in Fig. 5. The specific volume of point defects at various temperatures was estimated using the linear dependence of the volume on the number of defects, apparent in Figs. 4 and 5. The volume of the sample at a small number of vacancies can thus be written as

$$V=(NN_{va})v+N_{va}v_{va}$$
(2)
here, $`N`$ is the number of atoms in the sample, $`N_{va}`$ is the number of vacancies, $`v`$ is the volume per atom in a perfect crystal of vanadium and $`v_{va}`$ is the volume per vacancy. A similar relation for self-interstitials can be written as

$$V=Nv+N_{si}v_{si}$$
(3)
where, $`N_{si}`$ is the number of self-interstitials and $`v_{si}`$ is the volume per interstitial. It is interesting to point out that the linear dependence appears to hold even at temperatures close to $`T_s`$. This may indicate that the concept of a point defect remains meaningful even under these conditions. The specific volume of a point defect (in atomic volume units) is shown as a function of temperature in Fig. 6. It is seen that at temperatures above 2000K these specific volumes change rapidly. To a large degree, this increase can be accounted for by the rapid decrease of the elastic coefficients of the crystal in this temperature range.

## 4  The bulk melting transition

The prime goal of our simulations is the investigation of the role of point defects in mechanical melting. In the simulations of mechanical melting of fcc metals  it was established that the key parameter controlling melting is the volume of the crystal. When the Born criterion is applied to a superheated crystal lattice it establishes the existence of a critical volume above which the crystal becomes mechanically unstable and therefore undergoes a phase transformation to the liquid state or some other crystal structure. The critical volume is coupled with a maximum superheating temperature, $`T_s`$. Simulations with fcc metals showed that this critical volume, $`v_s`$, can be attained by expansion caused either by heating the crystal, or by doping it with point defects at a constant temperature which expand the crystal, or by pure mechanical dilatation at zero temperature. In this sense the mechanical melting process appears to be universal, i.e. it is determined only by the sample expansion up to the critical volume.

In order to verify whether the same scenario holds in the case of a bcc metal we carried out simulations using samples with various concentrations of self-interstitials or alternatively, vacancies.

The initial temperature of each sample was chosen far below the melting point of a perfect sample, $`T0.7T_s`$. As the samples were heated by gradually increasing the temperature, at some point we observed an abrupt decrease of the structure order parameter (see Fig. 7), together with a simultaneous increase of the total energy and volume (see Fig. 8). This event determines the mechanical melting temperature. The melting temperature of a sample without point defects is found to be $`T_s=2500\pm 20`$ K. Since MD simulations are plagued by statistical fluctuations in the temperature and volume, in practice it is very difficult to reach the maximum superheating temperature, $`T_s`$. Therefore, the accuracy in the determination of $`T_s`$ in this way is about $`1\%`$.

The same temperature, $`T_s=2500\pm 12`$ K, was also found from a least-squares fit to the temperature dependence of $`C^{}`$ as shown in Fig. 1 It is the temperature where $`C^{}`$ goes to zero. This indicates that as is the case for fcc metals, homogeneous melting of the bcc metal results from a shear elastic instability. This particular value of $`T_s`$ applies to a crystal of vanadium containing no defects, and is about $`280K`$ higher than the thermodynamic melting point $`T_m=2220\pm 15`$ K obtained for our model using the method proposed by J. F. Luthsko et al.

Once point defects are introduced, it is found that $`T_s`$ becomes a function of their concentration. Results of simulations performed at different temperatures and defect concentrations are summarized in our phase diagram (See Fig. 9). The fact that point defects lower the melting temperature has been confirmed experimentally ( $`\gamma `$-irradiation lowers the melting point of pure metals by an amount proportional to the dose, and thus to the number of generated point defects. \[Gorecki, 9\]) The lowering of $`T_s`$ can be explained as follows: Introduction of self - interstitials leads to a significant local distortion of the bcc lattice, and expands the volume of the solid, see Fig. 10. Therefore, a solid containing self - interstitials reaches its critical volume already at a lower temperature ( the melting temperature is lower). In contrast, the effect of vacancies is rather minor, at least if their concentration is small enough. The same effect of lowering of the bulk melting temperature induced by interstitials was obtained by A. Kanigel et al.  for copper (fcc lattice). However, at higher concentrations of point defects the decrease of $`T_s`$ can not be explained simply by volume expansion. This is especially notable in the case of vacancies which decrease the volume, but at high enough concentrations also lower the melting temperature (See Fig. 9). We refer here to the region in Fig. 9 where the concentration of point defects approaches 1%. These values are unrealistically large in comparison with the typical laboratory values $`0.001\%`$. At these high concentrations, the concept of a single point defect is unclear and one should perhaps consider clusters, or extended defects. According to Jin et al.  extended defects can act as nucleation centers for melting. Taking this point of view, the lowering of $`T_s`$ with defect concentration may result from the combined effect of (a) volume expansion, and (b) introduction of nucleation centers for melting. Finally, it should be noted that the calculated phase diagram is qualitative, because of the finite sample size and limited simulation time.

Our results are broadly consistent with models of defect-induced melting proposed by Fecht \[Fecht\] and Granato.  According to Fecht \[Fecht\] melting is driven by the incorporation of point defects into the lattice. Point defects increase the probability of heterophase fluctuations of liquid-like clusters in the defective crystal and lower the Gibbs energy of the crystalline state. Therefore, the melting temperature decreases as the concentration of point defects increases.

The configuration of point defects (self-interstitials) in a fcc metals was exploited by Granato  to construct a model giving the thermodynamic properties of the crystalline and liquid states in a unified way. He found a large diaelastic softening of the shear modulus with increasing defect concentration. This leads to a softening of the formation energy of interstitials, which, together with the large entropy contribution from the interstitialcy resonance modes, lowers the melting temperature.

In the above discussion, we have emphasized the role of lattice instability in establishing a maximum superheating temperature at zero external pressure. However, due to thermal expansion, any temperature change is accompanied by a simultaneous change of the volume. To decouple these two effects, we plot the dependence of the shear modulus $`C^{}`$ on the specific volume in Fig. 10. As this figure shows, the dependence of $`C^{}`$ on the specific volume appears to be universal, in the sense that the value of $`C^{}`$ is the same whether the volume at which it is calculated was reached at by thermal expansion or by insertion of point defects. In other words the main effect of interstitials is to expand the lattice. Using the data plotted in Fig. 10 one can extract the value of the critical volume, $`v_s(T_s)`$, at which the system melts homogeneously under the conditions of zero external stress.

Using this method we find $`v_s=14.87\pm 0.06\dot{A}^3`$/atom and the melting temperature $`T_s`$ for various concentrations of point defects. The critical volume is close to the specific volume of liquid vanadium at the thermodynamic melting temperature $`v_{liq}=15.3\pm 0.05\dot{A}^3`$ and to the experimental value  of $`v_{liq}=15.2\dot{A}^3`$.

Similar results were obtained for copper in MD simulations by J. Wang et al.  and by A. Kanigel et al.  It was found that the shear modulus vanishes at a lattice strain of $`a/a_0=1.024`$, where $`a`$ lattice parameter at $`T_m=1350K`$, and $`a_0`$ is the lattice parameter of copper at $`T_0=300K`$. The specific volume ratio of copper is $`(a/a_0)^3=1.07`$ which is quite close to the value obtained for vanadium $`v(T_m)/v(T_0)=1.06\pm 0.01`$. It is natural to ask whether the ratio $`a/a_0`$ is universal, independent of lattice structure. To answer this question in a definitive manner, it would be useful to make similar simulations on other bcc metals.

## 5  Summary and conclusions

In our simulations we observed that each shear elastic modulus is a continuous and apparently universal function of the specific volume. The solid lattice can be expanded either by thermal expansion or by the presence of self-interstitials. The value of $`C^{}`$ at any particular volume is independent of the way by which this volume was reached, either by thermal expansion alone, or by any combination of thermal expansion and of expansion due to interstitials introduced into the sample at a constant temperature. The elastic energy of the lattice increases until a critical specific volume $`v_s`$ (close to the specific volume of the melt) is reached where the shear modulus $`C^{}`$ vanishes, triggering mechanical melting. Upon melting, the solid transforms isothermally and discontinuously (see Figs. 7 and 8).

The process that triggers mechanical melting could be similar to the one observed by Jin et al.  in simulations of the melting of a surface-free Lennard-Jones crystal. There, melting occurs when the superheated crystal spontaneously generates a sufficiently large number of extended defects (clusters of spatially correlated destabilized particles which satisfy the Born criterion). Those extended defects play the role of surfaces in initiating the melting. In our simulations, point defects, especially in large concentration where clusters of defects should be formed, could act as nucleation centers for these extended defects (molten regions) inside the solid.

This paper was devoted to a simulation of the melting process of a homogeneous bcc metal, and its comparison with a similar process in fcc metals. It is of great interest to extend these simulations to heterogeneous melting which involves nucleation of the liquid phase at some preferred sites of the solid, for example at the free surface. This study is the subject of a forthcoming paper.

## 6 Acknowledgments

We are grateful to Dr. G. Wagner, A. Kanigel and J. Tal for their contribution to this project, and IUCC for the use of the computer facilities. This work was supported in part by the Israel Science Foundation, the German Israel Foundation (GIF), and by the Technion VPR fund for promotion of research.


format: text

text:
# Representations of Braid Groups

## 1. Introduction

Artin’s braid group $`B_n`$ was originally defined as a group of geometric braids in $`𝐑^3`$. Representations of $`B_n`$ have been studied for their own intrinsic interest, and also in connection to other areas of mathematics, most notably to knot invariants such as the Jones polynomial.

We will use the definition of $`B_n`$ as the mapping class group of an $`n`$-times punctured disk $`D_n`$. A rich source of representations of $`B_n`$ is the induced action on homology modules of spaces related to $`D_n`$. The Burau representation, one of the simplest and best known representations of braid groups, is most naturally defined as the induced action of $`B_n`$ on the first homology of a cyclic covering space of $`D_n`$. Lawrence  extended this idea to configuration spaces in $`D_n`$, and was able to obtain all of the so-called Temperley-Lieb representations.

Lawrence’s work seems to have received very little attention until one of her homological representations was shown to be faithful, thus proving that braid groups are linear and solving a longstanding open problem. Two independent and very different proofs of this have appeared in  and . In this paper we will outline the former, emphasising the importance of the Blanchfield pairing. We then discuss two other applications of the Blanchfield pairing, namely the proof that the Burau representation is not faithful for large $`n`$, and a homological definition of the Jones polynomial of a knot. We conclude with some speculation on possible future applications to representations of Hecke algebras when $`q`$ is a root of unity. These are related to representations of the symmetric group $`S_n`$ over fields of bad characteristic, that is, fields in which $`n!=0`$.

## 2. The Lawrence-Krammer representation

Let $`D`$ be the unit disk centred at the origin in the complex plane. Fix arbitrary real numbers $`1<p_1<\mathrm{}<p_n<1`$, which we will call “puncture points”. Let

$$D_n=D\{p_1,\mathrm{},p_n\}$$

be the $`n`$-times punctured disk. The braid group $`B_n`$ is the mapping class group of $`D_n`$, that is, the set of homeomorphisms from $`D_n`$ to itself that act as the identity on $`D`$, taken up to isotopy relative to $`D`$. Let $`C`$ be the space of all unordered pairs of distinct points in $`D_n`$.

Suppose $`x`$ is a point in $`D_n`$, and $`\alpha `$ is a simple closed curve in $`D_n`$ enclosing one puncture point and not enclosing $`x`$. Let $`\gamma :IC`$ be the loop in $`C`$ given by

$$\gamma (s)=\{x,\alpha (s)\}.$$

Now suppose $`\tau _1`$ and $`\tau _2`$ are paths in $`D_n`$ such that $`\tau _1\tau _2`$ is a simple closed curve that does not enclose any puncture points. Let $`\tau :IC`$ be the loop in $`C`$ given by

$$\tau (s)=\{\tau _1(s),\tau _2(s)\}.$$

Let

$$\mathrm{\Phi }:\pi _1(C)qt$$

be the unique homomorphism such that $`\mathrm{\Phi }(\gamma )=q`$ and $`\mathrm{\Phi }(\tau )=t`$ for any $`\gamma `$ and $`\tau `$ defined as above. For a proof of the existence and uniqueness of such a homomorphism, see . Let $`\stackrel{~}{C}`$ be the connected covering space of $`C`$ whose fundamental group is the kernel of $`\mathrm{\Phi }`$.

The second homology $`H_2(\stackrel{~}{C})`$ is a module over $`𝐙[q^{\pm 1},t^{\pm 1}]`$, where $`q`$ and $`t`$ act by covering transformations. The Lawrence-Krammer representation of $`B_n`$ is the induced action of $`B_n`$ on $`H_2(\stackrel{~}{C})`$ by $`𝐙[q^{\pm 1},t^{\pm 1}]`$-module automorphisms. More precisely, given an element of $`B_n`$ represented by a homeomorphism $`\sigma :D_nD_n`$, consider the induced action $`\sigma :CC`$. There is a unique lift $`\stackrel{~}{\sigma }:\stackrel{~}{C}\stackrel{~}{C}`$ that acts as the identity on $`\stackrel{~}{C}`$. This induces an automorphism of $`H_2(\stackrel{~}{C})`$, which can be shown to respect the $`𝐙[q^{\pm 1},t^{\pm 1}]`$-module structure. See  for details.

## 3. The Blanchfield pairing

Let $`ϵ>0`$ be small. We define $`P,BC`$ as follows. Suppose $`\{x,y\}`$ is a point in $`C`$. We say $`\{x,y\}P`$ if either $`|xy|ϵ`$, or there is a puncture point $`p_i`$ such that $`|xp_i|ϵ`$ or $`|yp_i|ϵ`$. We say $`\{x,y\}B`$ if $`xD`$ or $`yD`$.

For $`uH_2(\stackrel{~}{C},\stackrel{~}{P})`$ and $`vH_2(\stackrel{~}{C},\stackrel{~}{B})`$ let $`(uv)𝐙`$ denote the standard algebraic intersection number. We define an intersection pairing

$$,:H_2(\stackrel{~}{C},\stackrel{~}{P})\times H_2(\stackrel{~}{C},\stackrel{~}{B})𝐙[q^{\pm 1},t^{\pm 1}]$$

by

$$u,v=\underset{i,j𝐙}{}(uq^it^jv)q^it^j.$$

For a proof that these are well-defined, see \[7, Appendix E\], where the following properties are also proved.

For $`uH_2(\stackrel{~}{C},\stackrel{~}{P})`$, $`vH_2(\stackrel{~}{C},\stackrel{~}{B})`$, $`\sigma B_n`$, and $`\lambda 𝐙[q^{\pm 1},t^{\pm 1}]`$, we have

$$\sigma u,\sigma v=u,v,$$

and

$$\lambda u,v=\lambda u,v=u,\overline{\lambda }v,$$

where $`\overline{\lambda }`$ is the image of $`\lambda `$ under the automorphism of $`𝐙[q^{\pm 1},t^{\pm 1}]`$ taking $`q`$ to $`q^1`$ and $`t`$ to $`t^1`$.

## 4. A faithful representation

The aim of this section is to outline a proof of the following.

Theorem. Let $`\stackrel{~}{C}`$ and $`\stackrel{~}{P}`$ be as above. The induced action of $`B_n`$ on $`H_2(\stackrel{~}{C},\stackrel{~}{P})`$ is faithful.

For the details, the reader is referred to , where the same techniques are used to prove that $`B_n`$ acts faithfully on $`H_2(\stackrel{~}{C})`$. Our use of relative homology here actually simplifies the argument somewhat.

There is a slight technical difficulty in defining the action of $`B_n`$ on $`H_2(\stackrel{~}{C},\stackrel{~}{P})`$. Namely, the action of a braid on $`C`$ need not preserve the set $`P`$. Thus we should really take a limit as $`ϵ`$ approaches $`0`$. The representation obtained is very similar to the Lawrence-Krammer representation, but has a slightly different module structure, as discussed in .

Let $`E`$ be the straight edge from $`p_1`$ to $`p_2`$. Let $`E^{}`$ be the set of points in $`C`$ of the form $`\{x,y\}`$, where $`x,yE`$. Let $`\stackrel{~}{E}^{}`$ be a lift of $`E^{}`$ to $`\stackrel{~}{C}`$. This represents an element of $`H_2(\stackrel{~}{C},\stackrel{~}{P})`$, which we will call $`e`$. Let $`F_1`$ and $`F_2`$ be parallel vertical edges with endpoints on $`D`$, passing between $`p_2`$ and $`p_3`$. Let $`F^{}`$ be the set of points in $`C`$ of the form $`\{x,y\}`$, where $`xF_1`$ and $`yF_2`$. Let $`\stackrel{~}{F^{}}`$ be a lift of $`F^{}`$ to $`\stackrel{~}{C}`$. This represents an element of $`H_2(\stackrel{~}{C},\stackrel{~}{B})`$, which we will call $`f`$. Note that

$$e,f=0,$$

since $`E^{}`$ and $`F^{}`$ are disjoint in $`C`$.

Suppose the action of $`B_n`$ on $`H_2(\stackrel{~}{C},\stackrel{~}{P})`$ is not faithful. It is not hard to show that there must be a braid $`\sigma `$ in the kernel of this representation such that $`\sigma (E)`$ is not isotopic to $`E`$ relative to endpoints. Now $`\sigma (e)=e`$, so

$$\sigma (e),f=0.$$

From this, we will derive a contradiction.

By applying an isotopy, we can assume $`\sigma (E)`$ intersects $`F_1`$ and $`F_2`$ transversely at a minimal number of points $`k>0`$. Let $`x_1,\mathrm{},x_k`$ be the points of $`\sigma (E)F_1`$, and let $`y_1,\mathrm{},y_k`$ be the points of $`\sigma (E)F_2`$, numbered from top to bottom in both cases.

For $`i,j\{1,\mathrm{},k\}`$, let $`a_{i,j}`$ and $`b_{i,j}`$ be the unique integers such that $`\sigma (\stackrel{~}{E}^{})`$ intersects $`q^{a_{i,j}}t^{b_{i,j}}\stackrel{~}{F^{}}`$ at a point in the fibre over $`\{x_i,y_j\}`$, and let $`ϵ_{i,j}`$ be the sign of that intersection. Then

$$\sigma (e),f=\underset{i=1}{\overset{k}{}}\underset{j=1}{\overset{k}{}}ϵ_{i,j}q^{a_{i,j}}t^{b_{i,j}}.$$

To calculate $`a_{i,j}`$ and $`b_{i,j}`$, it is necessary to specify choices of lift for $`E^{}`$ and $`F^{}`$. We will not do this since we only need to calculate differences $`a_{i^{},j^{}}a_{i,j}`$ and $`b_{i^{},j^{}}b_{i,j}`$. To do this, let $`\gamma `$ be a path in $`C`$ that goes from $`\{x_i,y_j\}`$ to $`\{x_i^{},y_j^{}\}`$ in $`\sigma (E^{})`$, and then back to $`\{x_i,y_j\}`$ in $`F^{}`$. Then

$$q^{(a_{i^{},j^{}}a_{i,j})}t^{(b_{i^{},j^{}}b_{i,j})}=\mathrm{\Phi }(\gamma ).$$

From this we can prove the following.

Lemma. For all $`i,j\{1,\mathrm{},k\}`$ we have

* $`a_{i,j}=\frac{1}{2}(a_{i,i}+a_{j,j})`$,
* if $`b_{i,j}>b_{i,i}`$ then $`a_{i,j^{}}>a_{i,i}`$ for some $`j^{}=1,\mathrm{},k`$,
* if $`b_{i,j}>b_{j,j}`$ then $`a_{i^{},j}>a_{j,j}`$ for some $`i^{}=1,\mathrm{},k`$.

The first of these is \[1, Lemma 2.1\], and the second and third follow from the proof of \[1, Claim 3.4\]. We now sketch the proof of the second in the special case where $`y_i`$ lies between $`x_i`$ and $`y_j`$ along $`\sigma (E)`$.

Let $`\alpha `$ be the path from $`y_i`$ to $`y_j`$ along $`\sigma (E)`$. Let $`\beta `$ be the path from $`y_j`$ to $`y_i`$ along $`F_2`$. Then $`b_{i,j}b_{i,i}`$ is two times the winding number of $`\alpha \beta `$ around $`x_i`$. In particular, this winding number is positive.

Let $`D_1`$ be the once punctured disk $`D\{x_i\}`$, and let $`\stackrel{~}{D}_1`$ be its universal cover. Let $`\stackrel{~}{\alpha }\stackrel{~}{\beta }`$ be a lift of $`\alpha \beta `$ to $`D_1`$. This is a path from a point in the fibre over $`y_i`$ to a “higher” point in the fibre over $`y_i`$.

Let $`F_2^+`$ be the the segment of $`F_2`$ going from $`y_i`$ upwards to $`D`$. Let $`\stackrel{~}{F}_2^+`$ be the lift of $`F_2^+`$ to $`\stackrel{~}{D}_1`$ that has an endpoint at $`\stackrel{~}{\alpha }(0)`$. In order to reach a higher sheet in $`\stackrel{~}{D}_1`$, $`\stackrel{~}{\alpha }`$ must intersect $`\stackrel{~}{F}_2^+`$. Let $`\stackrel{~}{\gamma }`$ be the loop in $`\stackrel{~}{D}_1`$ that follows $`\stackrel{~}{\alpha }`$ to the first point of intersection with $`\stackrel{~}{F}_2^+`$, and then follows $`\stackrel{~}{F}_2^+`$ back to $`\stackrel{~}{\alpha }(0)`$.

Let $`\gamma `$ be the projection of $`\stackrel{~}{\gamma }`$ to $`D_1`$. This travels along $`\sigma (E)`$ from $`y_i`$ to some point $`y_j^{}F_2`$, then along $`F_2`$ back to $`y_i`$. Then $`a_{i,j^{}}a_{i,i}`$ is the total winding number of $`\gamma `$ around the puncture points. We must show that this winding number is positive.

By construction, $`\stackrel{~}{\gamma }`$ is a simple closed curve in $`\stackrel{~}{D}_1`$. By the Jordan curve theorem, it must bound a disk $`\stackrel{~}{B}`$. Let $`B`$ be the projection of $`\stackrel{~}{B}`$ to $`D_1`$. This is an immersed disk in $`D`$, whose boundary is $`\gamma `$. Note that $`\stackrel{~}{\gamma }`$ passes anticlockwise around $`\stackrel{~}{B}`$, since the puncture $`x_i`$ lies to its right. Thus the total winding number of $`\gamma `$ around the puncture points is equal to the total number of puncture points contained in $`B`$, counted with multiplicities.

It remains to show that $`B`$ intersects at least one puncture point. Suppose not. Then $`B`$ is an immersed disk in $`D_n`$. Using an “innermost disk” argument, one can find an embedded disk $`B^{}`$ in $`D_n`$ whose boundary consists of a subarc of $`\sigma (E)`$ and a subarc of $`F_2`$. Using $`B^{}`$, one can isotope $`\sigma (E)`$ so as to have fewer points of intersection with $`F_2`$, thus contradicting our assumptions.

This completes the proof of the second part of the lemma in the case where $`y_i`$ lies between $`x_i`$ and $`y_j`$ along $`\sigma (E)`$. The remaining case, where $`x_i`$ lies between $`y_i`$ and $`y_j`$, is only slightly trickier. The third part of the lemma is similar to the second. The first part of the lemma is much easier.

We now return to the proof of the theorem. Let $`a`$ be the maximum of all $`a_{i,j}`$. Let $`b`$ be the maximum of $`\{b_{i,j}:a_{i,j}=a\}`$. Suppose $`i,j\{1,\mathrm{},k\}`$ are such that $`a_{i,j}=a`$ and $`b_{i,j}=b`$, and also $`i^{},j^{}\{1,\mathrm{},k\}`$ are such that $`a_{i^{},j^{}}=a`$ and $`b_{i^{},j^{}}=b`$. I claim that $`ϵ_{i,j}=ϵ_{i^{},j^{}}`$. From this claim, it follows that all occurrences of $`q^at^b`$ in the expression

$$\sigma (e),f=\underset{i=1}{\overset{k}{}}\underset{j=1}{\overset{k}{}}ϵ_{i,j}q^{a_{i,j}}t^{b_{i,j}}$$

occur with the same sign, so the coefficient of $`q^at^b`$ is non-zero in $`\sigma (e),f`$. This provides our desired contradiction, and completes the proof of the theorem. It remains to prove that $`ϵ_{i^{},j^{}}=ϵ_{i,j}`$.

Using the above lemma, it is not hard to show that $`a_{i,i}=a_{j,j}=a`$ and $`b_{i,i}=b_{j,j}=b`$. Similarly, $`a_{i^{},i^{}}=a_{j^{},j^{}}=a`$ and $`b_{i^{},i^{}}=b_{j^{},j^{}}=b`$. We will only need the equalities

$$b_{i,i}=b_{i,j}=b_{j,j}=b_{i^{},i^{}}=b_{i^{},j^{}}=b_{j^{},j^{}}.$$

In fact, we only need these modulo two.

Orient $`\sigma (E)`$ so that it crosses $`F_1`$ from left to right at $`x_i`$. Let $`\gamma `$ be the path in $`C`$ which goes from $`\{x_i,y_i\}`$ to $`\{x_i^{},y_i^{}\}`$ in $`E^{}`$ and then back to $`\{x_i,y_i\}`$ in $`F^{}`$. Now $`b_{i^{},i^{}}b_{i,i}`$ is the exponent of $`t`$ in $`\mathrm{\Phi }(\gamma )`$. The fact that this is an even number means that the pair of points in $`D_n`$ do not “switch places” when they go around this loop. Thus $`\sigma (E)`$ crosses $`F_1`$ from left to right at $`x_i^{}`$. By similar arguments,

* $`\beta (E)`$ intersects $`F_1`$ with the same sign at $`x_i`$ and $`x_i^{}`$,
* $`\beta (E)`$ intersects $`F_2`$ with the same sign at $`y_j`$ and $`y_j^{}`$,
* $`x_i`$ occurs before $`y_j`$ and $`x_i^{}`$ occurs before $`y_j^{}`$ with respect to the orientation of $`\sigma (E)`$.

It is now intuitively clear that $`E^{}`$ must intersect $`F^{}`$ with the same signs at $`\{x_i,y_j\}`$ and $`\{x_i^{},y_j^{}\}`$. This can be proved rigorously by careful consideration of orientations of these surfaces, as discussed in \[1, Section 2.1\]. It follows that $`ϵ_{i,j}=ϵ_{i^{},j^{}}`$, which completes the proof of the theorem.

## 5. The Burau representation

The proof that the Lawrence-Krammer representation is faithful basically reduces to proving that the Blanchfield pairing detects whether corresponding edges in the disk can be isotoped to be disjoint. A converse to this idea leads to a proof that the Burau representation is not faithful for large $`n`$.

The Burau representation can be defined by a similar but simpler construction to that of the Lawrence-Krammer representation. Let

$$\mathrm{\Phi }:\pi _1(D_n)q$$

be the homomorphism that sends each of the obvious generators to $`q`$. Let $`\stackrel{~}{D}_n`$ be the corresponding covering space. The Burau representation is the induced action of $`B_n`$ on $`H_1(\stackrel{~}{D}_n)`$ by $`𝐙[q^{\pm 1}]`$-module automorphisms.

Let $`P`$ be an $`ϵ`$-neighbourhood of the puncture points, and let $`\stackrel{~}{P}`$ be the preimage of $`P`$ in $`\stackrel{~}{D}_n`$. The Blanchfield pairing in this context is a sesquilinear pairing

$$,:H_1(\stackrel{~}{D}_n,\stackrel{~}{P})\times H_1(\stackrel{~}{D}_n,\stackrel{~}{D}_n)𝐙[q^{\pm 1}].$$

Let $`E`$ be the straight edge from $`p_1`$ to $`p_2`$. Let $`\stackrel{~}{E}`$ be a lift of $`E`$ to $`\stackrel{~}{D}_n`$. This represents an element of $`H_1(\stackrel{~}{D}_n,\stackrel{~}{P})`$, which we will call $`e`$. Let $`F`$ be a vertical edge with endpoints on $`D`$, passing between $`p_{n1}`$ and $`p_n`$. Let $`\stackrel{~}{F}`$ be a lift of $`F`$ to $`\stackrel{~}{D}_n`$. This represents an element of $`H_1(\stackrel{~}{D}_n,\stackrel{~}{D}_n)`$, which we will call $`f`$. The following is \[2, Theorem 5.1\].

Theorem. Let $`E`$, $`e`$, $`F`$ and $`f`$ be as above. The Burau representation of $`B_n`$ is unfaithful if and only if there exists $`\sigma B_n`$ such that $`\sigma (e),f=0`$, but $`\sigma (E)`$ is not isotopic relative to endpoints to an edge that is disjoint from $`F`$.

Using this theorem, one can show that the Burau representation of $`B_n`$ is not faithful simply by exhibiting the required edges $`\sigma (E)`$ and $`F`$. Such edges can be found by hand in the case $`n=6`$. In the case $`n=5`$, they can be found by a computer search, and then laboriously checked by hand. The case $`n=4`$ seems to be beyond the reach of any known computer algorithm. This is the last open case, since the Burau representation is known to be faithful for $`n3`$.

## 6. The Jones polynomial

In this section, we use the Blanchfield pairing to give a homological definition of the Jones polynomial of a knot or link. The Jones polynomial was defined in  using certain algebraically defined representations of braid groups. No satisfactory geometric definition is known, but some insight might be offered by defining the representations homologically and using the Blanchfield pairing. This was the original motivation for Lawrence to study homological representations of braid groups.

A geometric braid $`\sigma B_n`$ is a collection of $`n`$ disjoint edges in $`𝐂\times 𝐑`$ with endpoints $`\{1,\mathrm{},n\}\times \{0,1\}`$, such that each edge goes from $`𝐂\times \{0\}`$ to $`𝐂\times \{1\}`$ with a constantly increasing $`𝐑`$ component. The correspondence between geometric braids and elements of the mapping class group is described in , and in many other introductory expositions on braids. The plat closure of a geometric braid $`\sigma B_{2n}`$ is the knot or link obtained by using straight edges to connect $`(2j1,k)`$ to $`(2j,k)`$ for each $`j=1,\mathrm{},n`$ and $`k=0,1`$. Every knot or link can be obtained in this way.

Let $`C`$ be the configuration space of unordered $`n`$-tuples of distinct points in $`D_{2n}`$. Let

$$\mathrm{\Phi }:\pi _1(C)qt$$

be defined as in Section 2. Namely, if $`\gamma `$ is any loop in which one of the $`n`$-tuple winds anticlockwise around a puncture point, and $`\tau `$ is any loop in which two of the $`n`$-tuple exchange places by an anticlockwise half twist, then $`\mathrm{\Phi }(\gamma )=q`$ and $`\mathrm{\Phi }(\tau )=t`$. Let $`\stackrel{~}{C}`$ be the covering space corresponding to $`\mathrm{\Phi }`$.

Define $`P,BC`$ similarly to those of Section 3. The Blanchfield pairing is a sesquilinear pairing

$$,:H_2(\stackrel{~}{C},\stackrel{~}{P})\times H_2(\stackrel{~}{C},\stackrel{~}{B})𝐙[q^{\pm 1},t^{\pm 1}].$$

For $`k=1,\mathrm{},n`$, let $`F_k`$ be the straight edge from $`p_{2k1}`$ to $`p_{2k}`$. Let $`F`$ be the set of points in $`C`$ of the form $`\{x_1,\mathrm{},x_n\}`$ where $`x_iF_i`$. Let $`\stackrel{~}{F}`$ be a lift of $`F`$ to $`\stackrel{~}{C}`$. This represents an element of $`H_n(\stackrel{~}{C},\stackrel{~}{P})`$, which we call $`f`$. For $`k=1,\mathrm{},n`$, let $`e_k:S^1D_n`$ be a figure-eight around $`p_{2k1}`$ and $`p_{2k}`$ in a small neighbourhood of $`F_k`$. Let $`e`$ be the map from the $`n`$-torus $`(S^1)^n`$ to $`C`$ given by

$$e(s_1,\mathrm{},s_n)=\{e_1(s_1),\mathrm{},e_n(s_n)\}.$$

Let $`\stackrel{~}{e}`$ be a lift of $`e`$ to $`\stackrel{~}{C}`$. This represents an element of $`H_n(\stackrel{~}{C})`$, and hence of $`H_n(\stackrel{~}{C},\stackrel{~}{B})`$, which we also call $`e`$.

The main result of  is the following.

Theorem. Let $`e`$ and $`f`$ be as above and suppose $`\sigma B_{2n}`$. The Jones polynomial of the plat closure of $`\sigma `$ is

$$\sigma (e),f)|_{(t=q^1)},$$

up to sign and multiplication by a power of $`q^{\frac{1}{2}}`$.

Here, the Jones polynomial is normalised so that the Jones polynomial of the unknot is $`q^{\frac{1}{2}}q^{\frac{1}{2}}`$. The correct sign and power of $`q^{\frac{1}{2}}`$ is also explicitly specified in .

This result is due to Lawrence, who also achieved a similar result for the two-variable Jones polynomial by a much more complicated construction .

## 7. The Hecke algebra

We conclude with some speculation about possible applications of the Blanchfield pairing to the representation theory of Hecke algebras. We first give a very brief overview of the basic theory of Hecke algebras.

Let $`q𝐂\{0\}`$. The Hecke algebra $`H_n(q)`$, or simply $`H_n`$, is the $`𝐂`$-algebra given by generators $`g_1,\mathrm{},g_{n1}`$ and relations

* $`g_ig_j=g_jg_i`$ if $`|ij|>1`$,
* $`g_ig_jg_i=g_ig_jg_i`$ if $`|ij|=1`$,
* $`(g_i1)(g_i+q)=0`$.

It is an $`n!`$-dimensional $`𝐂`$-algebra. We are restricting to the ring $`𝐂`$ for convenience, although other rings can be used.

Note that $`H_n(1)`$ is the group algebra $`𝐂S_n`$ of the symmetric group $`S_n`$. The Hecke algebra is called a “quantum deformation” of $`𝐂S_n`$. The representation theory of $`𝐂S_n`$ is well understood except when working over a field of finite characteristic in which $`n!=0`$. This is because the classical theory sometimes requires one to divide by $`n!`$, the order of the group. When studying $`H_n`$ it turns out to be useful to be able to divide by

$$(1+q+\mathrm{}+q^{n1})(1+q+\mathrm{}+q^{n2})\mathrm{}(1+q).$$

This is sometimes written as $`[n]!`$, and can be thought of as a “quantum deformation” of $`n!`$. Note that $`[n]!=n!`$ if $`q=1`$. A generic value of $`q`$ is one for which $`[n]!0`$. The non-generic values are the primitive $`k`$th roots of unity for $`k=2,\mathrm{},n`$. The representation theory of $`H_n`$ is well understood for generic values of $`q`$, but the non-generic values are the subject of ongoing active research.

One of the most important papers on this subject is Dipper and James . For every partition $`\lambda `$ of $`n`$, they define a $`H_n`$-module $`S^\lambda `$ called the Specht module. They then define a bilinear pairing on $`S^\lambda `$, which we denote $`,_{\mathrm{DJ}}`$. Let $`S_{}^\lambda `$ denote the set of $`uS^\lambda `$ such that $`u,v_{\mathrm{DJ}}=0`$ for all $`vS^\lambda `$. Let $`D^\lambda `$ be the quotient module $`S^\lambda /S_{}^\lambda `$. Dipper and James show that the non-zero $`D^\lambda `$ form a complete list of all distinct irreducible representations of $`H_n`$. For generic values of $`q`$ we have $`D^\lambda =S^\lambda `$. For non-generic values of $`q`$, the $`D^\lambda `$ are not well understood.

Lawrence  gave a homological definition of the Specht modules. The construction begins with the action of $`B_n`$ on a homology module of a configuration space. The variable $`t`$ is then specialised to $`q^1`$, and a certain quotient module is taken. A detailed treatment of the case $`\lambda =(n2,2)`$ is given in .

There is a Blanchfield pairing on the Specht modules as defined by Lawrence. It would be nice if this were the same as the pairing defined by Dipper and James. Unfortunately the Blanchfield pairing is sesquilinear, whereas the pairing defined by Dipper and James is bilinear. This problem can be overcome as follows. Let $`\rho :D_nD_n`$ be the conjugation map. Let $`\stackrel{~}{\rho }`$ be the induced map on $`H_k(\stackrel{~}{C},\stackrel{~}{B})`$. Then the pairing

$$u,v^{}=u,\rho (v)$$

can be shown to give a bilinear pairing on the Specht module.

For generic values of $`q`$, this topologically defined pairing is the same as the algebraically defined pairing of Dipper and James, up to some renormalisation. There is some evidence that this can be made to work at non-generic values of $`q`$. If so, it would give rise to a new homological definition of the modules $`D^\lambda `$, and new topological tools for studying them. In any case, it would be interesting to better understand the behaviour of this Blanchfield pairing at roots of unity.


text:
# New coins from old: computing with unknown bias

## 1 Introduction

Fifty years ago, von Neumann  suggested a method to generate unbiased random bits from a sequence of i.i.d. biased bits. This method can be easily implemented using a finite automaton.

In this paper we study the following generalization. Let $`𝒟(0,1)`$. Suppose that we are given a function $`f:𝒟(0,1)`$ and, for some unknown $`p𝒟`$, a sequence of independent tosses of a $`p`$-coin (i.e., $`\{0,1\}`$ valued random variables with mean $`p`$). For which functions $`f`$ is it then possible to simulate an $`f(p)`$-coin?

The allowed simulation schemes apply a stopping rule to independent tosses of a $`p`$-coin, and then determine a $`\{0,1\}`$-valued variable with mean $`f(p)`$ as a function of the stopped sequence. We emphasize that the scheme cannot depend on $`p`$. We are especially interested in simulation schemes that can be implemented by an automaton that receives the $`p`$-coin tosses as inputs, and outputs an $`f(p)`$-coin; see §1.2 for more formal definitions.

A special case of this question was raised in 1991 by S. Asmussen (see ). We learned of the general problem from J. Propp (personal communication) who emphasized its computational aspects. The problem was considered in the context of Markov chain simulation by Glynn and Henderson .

In our main result we prove

###### Theorem 1.1.

Let $`𝒟(0,1)`$ and $`f:𝒟(0,1)`$. Then an $`f(p)`$-coin for $`p𝒟`$ can be simulated using a finite automaton from independent tosses of a $`p`$-coin, if and only if $`f`$ is the restriction to $`𝒟`$ of a rational function $`F`$ over $``$, such that $`0<F(x)<1`$ for $`0<x<1`$.

Later using the result of the appendix we prove:

###### Theorem 1.2.

Let $`f:(0,1)(0,1)`$. If an $`f(p)`$-coin can be simulated from tosses of a $`p`$-coin by a pushdown automaton for all $`p(0,1)`$, then $`f`$ is an algebraic function over $``$; i.e., there exists a non-zero polynomial $`P[X,Y]`$ such that $`P(f(p),p)=0`$ for all $`p[0,1]`$.

In §3.2 we describe pushdown automata that can simulate $`f(p)`$-coins for certain non-rational functions such as $`f(p)=\sqrt{p}`$.

Our results complement the work of Keane and O’Brien (1994), who considered the simulation problem without any computational restrictions. They showed that the functions $`f:𝒟(0,1)`$ for which an $`f(p)`$-coin can be simulated (in principle) are precisely the constants, and all continuous functions on $`𝒟`$ that satisfy $`\mathrm{min}(f(x),1f(x))\mathrm{min}(x,1x)^n`$ for some $`n1`$ and all $`x𝒟`$.

### 1.1 Examples

Here are some examples - see Figure 1.

* $`f(p)=1/2`$. This is achievable by Von Neumann’s trick: toss the $`p`$ coin twice and let $`x`$ and $`y`$ be the outcome. If $`xy=01`$ output $`0`$, if $`xy=10`$ declare $`1`$; otherwise, do not declare and toss again. This is the leftmost automaton.
* $`f(p)=p^2`$. Toss the $`p`$-coin twice. If it’s $`11`$ declare $`1`$, otherwise declare $`0`$. This is the automaton in the middle.
* $`f(p)=\frac{p^2}{p^2+(1p)^2}`$. Toss the $`p`$-coin twice until you get $`00`$ or $`11`$. In the first case, declare $`0`$, in the second declare $`1`$. This is the automaton on the right.
* $`f(p)=\sqrt{p}`$. Theorem 2.2 implies that this function cannot be simulated by a finite automaton. In Section 3 we construct a pushdown automaton which simulates $`f`$.
* Our main result implies that there is no infinite set $`𝒟`$ such that a $`2p`$-coin can be simulated by a finite automaton for all $`p𝒟`$ from tosses of a $`p`$-coin.

### 1.2 Formal definitions

Denote by $`\{0,1\}^{}`$ the set of all finite binary strings, and call any subset of $`\{0,1\}^{}`$ a language. Say that a language $`L`$ has the prefix property if there is no pair of distinct strings $`u,vL`$ such that $`u`$ is a prefix of $`v`$.

For any binary string $`w`$, write $`𝐏_p[w]=p^{n_1(w)}(1p)^{n_0(w)}`$, where $`n_i(w)`$ is the number of $`i`$’s in $`w`$ and let $`𝐏_p(L)=_{wL}𝐏_p(w)`$ for any language $`L`$.

###### Definition 1.3.

Let $`f:𝒟[0,1]`$ where $`𝒟(0,1)`$.

* A simulation of $`f`$ is a pair of disjoint languages $`L_0,L_1\{0,1\}^{}`$ such that $`L_0L_1`$ has the prefix property and for all $`p𝒟`$ we have $`𝐏_p[L_1]=f(p)`$ and $`𝐏_p[L_0L_1]=1`$ and $`𝐏_p[L_1]=f(p)`$.
* A simulation of $`f`$ by a finite automaton, is a simulation $`(L_0,L_1)`$ of $`f`$ such that there exists a finite automaton which outputs $`0`$ for the language $`L_0`$ and outputs $`1`$ for the language $`L_1`$. An analogous definition applied to simulation by a pushdown automaton or a Turing machine.

###### Definition 1.4.

A finite automaton is defined by

* A set of states $`S`$ with a start state $`s_0S`$.
* An alphabet which we fix to be $`\{0,1\}`$,
* A transition function $`\delta :S\times \{0,1\}S`$, $`\delta (s,b)`$ is the state the automaton is, given that it was in state $`s`$ and the current input symbol is $`b`$. For a string $`w=w_1\mathrm{}w_k\{0,1\}^{}`$ we let $`\delta (s,w)`$ be defined inductively by $`\delta (s,w_1\mathrm{}w_k)=\delta (\delta (s,w_1),w_2\mathrm{}w_k)`$.
* Two disjoint sets of final states $`S_0`$ and $`S_1`$. The automaton stops whenever it is in $`sS_0S_1`$ (formally, for all $`sS_0S_1`$ and $`b\{0,1\}`$, it holds that $`\delta (s,b)=s`$). If it stopped at $`S_0`$, then the output is $`0`$; if it stopped in $`S_1`$, then the output is $`1`$.

This is a slight variation of the standard definition (see e.g. ) where the automaton stops when the it gets to the end of the input. Here, the input is unbounded.

Letting $`L_i`$ be the strings in $`\{0,1\}^{}`$ for which the automaton stops at $`S_i`$, the automaton will define a simulation of a function $`f:(0,1)(0,1)`$, if $`𝐏_p[L_0L_1]=1`$. Note that $`L_0`$ and $`L_1`$ are both regular languages, and $`L_0L_1`$ has the prefix property. Moreover, for every pair of disjoint regular languages $`L_0`$ and $`L_1`$ with the prefix property, using a standard product construction, it easy to write down an automaton as in Definition 1.4 which outputs $`0`$ for $`L_0`$ and $`1`$ for $`L_1`$.

Note that in Figure 1, for the leftmost automaton, $`L_0=(00+11)^{}01`$, $`L_1=(00+11)^{}10`$; for the middle automaton, $`L_0=11(0+1)^{}`$, $`L_1=(00+01+10)(0+1)^{}`$; and for the rightmost automaton, $`L_0=(01+10)^{}00`$, $`L_1=(01+10)^{}11`$.

The definition below is a slight variation of the standard definition of Pushdown automata (see e.g.  for the standard definition).

###### Definition 1.5.

A Pushdown automaton over the alphabet $`\{0,1\}`$ is defined by

* A set of states $`S`$ with a start state $`s_0Q`$.
* A stack alphabet $`\mathrm{\Lambda }`$.
* A stack $`T\mathrm{\Lambda }^{}`$ which is initialized as the non-empty string $`\tau `$.
* A transition function $`(\delta ,\eta ):S\times \{0,1\}\times \mathrm{\Lambda }S\times \mathrm{\Lambda }^{}`$. The first coordinate, $`\delta (s,b,\tau )`$, is the new state of the automaton given that it was in state $`s`$, the current input symbol is $`b`$ and that the symbol at the top of the stack is $`\tau `$. After this transition the symbol at the top of the stack is replaced by the string in the second coordinate of $`\eta (s,b,\tau )`$.
* Two disjoint sets of final states $`S_0`$ and $`S_1`$. The automaton stops when the stack is empty. If the automaton stops at a state of $`S_0`$, the output is $`0`$, and if it stops at a state of $`S_1`$, the output is $`1`$.

Note that if $`L_0`$ ($`L_1`$) are the languages where the automaton output $`0`$ ($`1`$), then $`L_0`$ and $`L_1`$ are context free languages, and $`L_0L_1`$ has the prefix property.

### 1.3 Motivation and related models

Our results have a similar flavor to classical results of the Chomsky Schützenberger theory  \- thus a relationship is established between the strength of a computation model and algebraic properties of the outputs generated by this model. We discuss some of the connections in more detail in subsections 3.1 and 4.1.

The model we introduce in this paper has also some interesting relationships with the theory of computability  as in both models the interest is in ”real” inputs and outputs. In particular for both models, the input is unbounded. See Subsection 4.2 for a more formal discussion.

Finally a major motivation for studying this model is the theory of exact sampling, see e.g. . In the theory of exact sampling the aim is to sample (exactly) from a certain complicated distribution given a simpler given distribution. Thus the problem is a basic problem in the theory of exact sampling. In Subsection 4.3 we give a (toy) example which illustrating how our results may be used for exact sampling.

### 1.4 Paper plan

In Section 2 we prove Theorem 2.2 and its generalizations to collections of coins, dice etc. In Section 3 we prove Theorem 1.2 and show how using a push-down automaton, it is possible to simulate non-rational constants and functions. In Section 4 we discuss the relationships with the theory of languages and their formal power series, the theory of computability, exact sampling and suggest some open problems.

## 2 Rationality and finite automata

A sub-family of the coins which can be simulated via finite-automata are those which can be simulated via blocks. Von Neumann’s trick consists of reading $`2`$ bit blocks until $`01`$ or $`10`$ are reached, and then deciding $`0`$ for $`01`$ and $`1`$ for $`10`$. Block simulation is a generalization of this procedure defined as follows

###### Definition 2.1.

A block simulation of $`f`$, is a simulation of $`f`$ of the following form. Let $`A_0`$ and $`A_1`$ be disjoint subsets of $`\{0,1\}^k`$, and $`A^{}=\{0,1\}^k(A_0A_1)`$. The simulation procedure has $`L_0=(_{wA^{}}w)^{}(_{wA_0}w)`$ and $`L_1=(_{wA^{}}w)^{}(_{wA_1}w)`$. In other words, the procedure reads a $`k`$ bit string $`w`$. If $`wA_0`$, the procedure outputs $`0`$, if $`wA_1`$ the procedure outputs $`1`$; otherwise the procedure discards $`w`$ and reads a new $`k`$ bit string.

Below we prove the following theorem which immediately implies Theorem 1.1.

###### Theorem 2.2.

Let $`𝒟(0,1)`$. For $`f:𝒟(0,1)`$ the following are equivalent.

* $`f`$ can be block simulated.
* $`f`$ can be simulated via a finite automaton.
* $`f`$ is the restriction to $`𝒟`$ of a a rational function $`F`$ over $``$ such that $`0<F(p)<1`$ for all $`p(0,1)`$.

Note that $`III`$ is trivial. The implication $`IIIII`$ is fairly easy. We know of no way of proving $`III`$ directly. Instead, we prove $`IIII`$. We know of no simple bound in terms of $`f`$ on the size of automaton (or block) needed in order to simulate $`f`$, although there exists a simple algorithm for constructing an automaton that simulates $`f`$.

### 2.1 Finite automaton $``$ Rationality

###### Proposition 2.3.

Let $`𝒟(0,1)`$. If a finite automaton $`\mathrm{\Sigma }`$ simulates $`f:𝒟(0,1)`$, then $`f`$ is the restriction to $`𝒟`$ of a rational function $`F`$ over $``$ such that $`0<F(p)<1`$ for all $`p(0,1)`$. Moreover if $`\mathrm{\Sigma }`$ has $`n`$ states, then $`F(p)=g(p)/h(p)`$, where $`g(p),h(p)[p]`$ and $`g`$ and $`h`$ are of degree at most $`n`$.

The proof applies the maximum principle for harmonic functions on directed graphs.

###### Lemma 2.4.

Let $`\mathrm{\Sigma }`$ be a finite automaton and $`R`$ a set of states such that for all $`sS`$, there exists $`w\{0,1\}^{}`$, such that $`\delta (s,w)R`$. Let $`0<p<1`$ and $`f:S`$ be harmonic, so for all $`s`$ it holds that $`f(s)=pf(\delta (s,1))+(1p)f(\delta (s,0))`$. Then $`f`$ achieves its maximum and minimum in $`R`$. Moreover, given the values of $`f`$ in $`R`$, the values of $`f`$ in $`S`$ are uniquely determined.

###### Proof.

Note first that the last assertion follows from the first one, as if $`f_1`$ and $`f_2`$ are two harmonic functions which have the same value on $`R`$, then $`f_1f_2`$ is harmonic and has the value $`0`$ on $`R`$, which implies by the first assertion that $`\mathrm{max}f_1f_2=\mathrm{min}f_1f_2=0`$, or $`f_1=f_2`$.

In order to prove the first assertion, let $`m=\mathrm{max}f`$. Note that if $`f(s)=m`$, then $`f(\delta (s,0))=f(\delta (s,1))=m`$. Letting $`w\{0,1\}^{}`$ be such that $`\delta (s,w)R`$, we obtain $`f(\delta (s,w))=m`$ as needed.

Proof of Proposition 2.3:  Suppose that $`f`$ can is simulated by a finite automaton $`\mathrm{\Sigma }`$. Let $`S^{}`$ be the set of states $`s`$ such that there exists $`w\{0,1\}^{}`$ with $`\delta (s_0,w)=s`$. Clearly, we may remove from the automaton all the states not in $`S^{}`$ (redefining $`\delta `$ by restriction) and still obtain a finite automaton which simulates $`f(p)`$. By the assumption that $`𝐏_p[L_0L_1]=1`$, it follows that for all $`sS^{}`$, there exists $`w\{0,1\}^{}`$ such that $`\delta (s,w)S_0S_1`$. From now on we assume that $`S=S^{}`$.

Note that since for all $`sS`$, there exists $`w\{0,1\}^{}`$ such that $`\delta (s,w)S_0S_1`$, it follows that $`𝐏_p[L_0L_1]=1`$ for all $`0<p<1`$. Therefore the function $`f`$ is the restriction of the function $`F(p)=𝐏_p[L_1]`$ to $`𝒟`$.

Suppose that $`F(s;p)`$ satisfies $`F(s;p)=0`$ for $`sS_0`$, and $`F(s;p)=1`$ for $`sS_1`$. For all other $`s`$, assume that

$$F(s;p)=pF(\delta (s,1);p)+(1p)F(\delta (s,0);p).$$

By Lemma 2.4, the function $`F(s;p)`$ is uniquely determined by these equations. This implies that $`F(s_0;p)=F(p)`$. Since $`F(p)`$ is uniquely determined by a collection of linear equation with coefficients in $`[p]`$, it follows by Cramer’s rule that $`F(p)`$ may be written as the ratio of two determinants in $`[p]`$, and therefore $`F(p)=g(p)/h(p)(p)`$, where the degrees of $`g`$ and $`h`$ are at most the number of states of the automaton, as needed.

### 2.2 Block Simulation

In this subsection we study what can be simulated by blocks.

###### Proposition 2.5.

$`f`$ can be simulated using a block procedure if and only if $`f`$ can be written as $`D(p)/E(p)`$ where

$`D(p)`$ $`=`$ $`{\displaystyle \underset{i=0}{\overset{k}{}}}d_ip^i(1p)^{ki},`$ (1)
$`E(p)`$ $`=`$ $`{\displaystyle \underset{i=0}{\overset{k}{}}}e_ip^i(1p)^{ki},`$
and for all $`i`$, the coefficients $`d_i`$ and $`e_i`$ are integers such that $`0d_ie_i`$.

###### Proof.

Suppose that $`f`$ is block simulated. For a string $`w\{0,1\}^{}`$, we write $`n_1(w)`$ for the number of $`1`$s in $`w`$. Then

$$f(p)=𝐏_p[L_1]=\frac{_{wA_1}𝐏_p[w]}{_{wA_0A_1}𝐏_p[w]}=\frac{_{i=0}^kd_ip^i(1p)^{ki}}{_{i=0}^ke_ip^i(1p)^{ki}},$$

where

$$d_i=\mathrm{\#}\{wA_1:n_1(w)=i\},$$

and

$$e_i=\mathrm{\#}\{wA_1A_0:n_1(w)=i\},$$

satisfy that $`0d_ie_i`$, as needed.

For the other direction, suppose that $`f(p)=D(p)/E(p)`$, where $`D`$ and $`E`$ satisfy (1). Let $`r`$ be a number such that $`e_i\left(\genfrac{}{}{0pt}{}{k}{i}\right)\left(\genfrac{}{}{0pt}{}{2r}{r}\right)`$ for all $`i`$. For each $`i`$, fix a bijection $`B_i`$ from

$$\{w\{0,1\}^k:n_1(w)=i\}\times \{v\{0,1\}^{2r}:n_1(v)=r\}$$

to $`\{1,\mathrm{},\left(\genfrac{}{}{0pt}{}{k}{i}\right)\left(\genfrac{}{}{0pt}{}{2r}{r}\right)\}`$.

The sets $`A_0`$ and $`A_1`$ are subsets of $`\{0,1\}^k\times \{0,1\}^{2r}`$, defined as follows. $`A_1`$ is defined as

$$_{i=0}^k\{(v,w):n_1(v)=i,n_1(w)=r,\text{ and }B_i(v,w)d_i\}$$

and $`A_0`$ as

$$_{i=0}^k\{(v,w):n_1(v)=i,n_1(w)=r,\text{ and }d_i<B_i(v,w)e_i\}.$$

So

$`𝐏_p[A_1]`$ $`=`$ $`p^r(1p)^r{\displaystyle \underset{i=0}{\overset{k}{}}}d_ip^i(1p)^{ki},`$
$`𝐏_p[A_0A_1]`$ $`=`$ $`p^r(1p)^r{\displaystyle \underset{i=0}{\overset{k}{}}}e_ip^i(1p)^{ki},`$
and therefore,

$$𝐏[L_1]=\frac{𝐏_p[A_1]}{𝐏_p[A_0A_1]}=f(p),$$

as needed.

### 2.3 Rationality $``$ Finite automaton

In this section we prove Theorem 2.2. The proof is based on a beautiful theorem by Pólya  (see , 57–59). We let $`\mathrm{\Delta }^s`$ denote the open $`s`$-simplex of probability distributions,

$$\mathrm{\Delta }^s=\{p(0,1)^{s+1}:\underset{i=1}{\overset{s+1}{}}p_i=1\}.$$

###### Theorem 2.6 (Pólya ).

Let $`f:\mathrm{\Delta }^{s1}`$ be homogeneous and positive polynomial in the variables $`p_1,\mathrm{},p_s`$. Then for all sufficiently large $`n`$, all the coefficients of $`(p_1+\mathrm{}+p_s)^nf(p_1,\mathrm{},p_s)`$ are positive.

###### Lemma 2.7.

Let $`f:(0,1)(0,1)`$ be a rational function. Then there exist polynomials $`d`$ and $`e`$

$`d(p)`$ $`=`$ $`{\displaystyle \underset{i=0}{\overset{k}{}}}d_ip^i(1p)^{ki},`$ (2)
$`e(p)`$ $`=`$ $`{\displaystyle \underset{i=0}{\overset{k}{}}}e_ip^i(1p)^{ki},`$
where for all $`i`$, the coefficients $`d_i`$ and $`e_i`$ are integers such that $`0d_ie_i`$, and $`f(p)=d(p)/e(p)`$.

###### Proof.

As $`f(p)`$ is a rational function it may be written in the form $`\overline{D}(p)/\overline{E}(p)`$, where $`\overline{D}(p)[p]`$ and $`\overline{E}(p)[p]`$ are relatively prime polynomials. Since $`0<f(p)`$ for all $`0<p<1`$, it follows that $`\overline{D}(p)`$ and $`\overline{E}(p)`$ do not change sign in the interval $`(0,1)`$. Without loss of generality we assume that $`\overline{D}(p)>0`$ and $`\overline{E}(p)>0`$ for all $`p(0,1)`$. Note furthermore that if $`\overline{D}(p)=_{i=0}^ka_ip^i`$ and $`\overline{E}(p)=_{i=0}^kb_ip^i`$, then we may define homogeneous polynomials $`D(p,q)`$ and $`E(p,q)`$ of degree $`k`$, by letting $`D(p,q)=_{i=0}^ka_ip^i(p+q)^{ki}`$, and $`E(p,q)=_{i=0}^kb_ip^i(p+q)^{ki}`$. Note that $`\overline{D}(p)=D(p,1p)`$ and $`\overline{E}(p)=E(p,1p)`$. Let us rewrite,

$`D(p,q)`$ $`=`$ $`{\displaystyle \underset{i=0}{\overset{k}{}}}d_ip^iq^{ki},`$ (3)
$`E(p,q)`$ $`=`$ $`{\displaystyle \underset{i=0}{\overset{k}{}}}e_ip^iq^{ki}.`$
The polynomials $`D(p,q),E(p,q)`$ and $`E(p,q)D(p,q)`$ are all positive homogeneous polynomials. Therefore by Theorem 2.6, if follows that there exists an $`n`$ such that letting $`d(p,q)=(p+q)^nD(p,q)`$ and $`e(p,q)=(p+q)^nE(p,q)`$, the polynomials $`d`$,$`e`$ and $`ed`$ all have positive coefficients as polynomials in $`p`$ and $`q`$. Writing $`f(p)=d(p,1p)/e(p,1p)`$ we obtain the required result.

Proof of Theorem 2.2:  The implication $`III`$ is trivial, the implication $`IIIII`$ follows from Proposition 2.3, while $`IIII`$ follows from Lemma 2.7 together with Proposition 2.5.

### 2.4 Extensions to dice and other $`k`$-sided coins

In this subsection we discuss generalizations of the problem to $`k`$-sided coins, such as dice. A simulation of $`f=(f_1,\mathrm{},f_t):\mathrm{\Delta }^s\mathrm{\Delta }^t`$, is a collection of $`t`$ disjoint languages property $`(L_1,\mathrm{},L_t)`$ over the alphabet $`\mathrm{\Sigma }=\{1,\mathrm{},s\}`$, such that $`_{i=1}^tL_i`$ has the prefix property and $`𝐏_p[L_i]=f_i(p)`$ for all $`p\mathrm{\Delta }^s`$. The definition of simulation via finite/pushdown automata and Turing machines naturally extend to this setting. The continuity results of  extend to the more general setting as well.

###### Proposition 2.8.

If a finite automaton simulates $`f:\mathrm{\Delta }^s\mathrm{\Delta }^t`$, then $`f`$ is a rational function over $``$ (i.e. $`f_i(p)`$ is a rational function over $``$ for all $`1it+1`$).

###### Proof.

Repeat the proof of Proposition 2.3 for each of the $`f_i`$’s. .

Repeating the proof of Theorem 2.2, we see that

###### Theorem 2.9.

Any rational function $`f:\mathrm{\Delta }^s\mathrm{\Delta }^1`$ can be simulated via blocks.

From which we conclude that

###### Corollary 2.10.

Any rational function $`f:\mathrm{\Delta }^s\mathrm{\Delta }^t`$ can be simulated via blocks.

###### Proof.

The proof is by induction on $`t`$. The case $`t=1`$ is covered by Theorem 2.9. Suppose $`t>1`$, and let $`(f_1,\mathrm{},f_{t+1}):\mathrm{\Delta }^s\mathrm{\Delta }^t`$ be a rational function. By Theorem 2.9, there exists a block simulation $`(A_1,A_2)(\mathrm{\Sigma }^k)^2`$ for $`(f_1,1f_1)`$, and by the induction hypothesis there exists a block simulation $`(B_1,\mathrm{},B_t)(\mathrm{\Sigma }^r)^t`$ for $`(f_2/(1f_1),\mathrm{},f_{t+1}/(1f_1))`$. Taking

$$(A_1\times \mathrm{\Sigma }^r,A_2\times B_1,A_2\times B_2,\mathrm{},A_2\times B_t)(\mathrm{\Sigma }^{r+k})^{t+1},$$

we obtain a block simulation for $`(f_1,\mathrm{},f_{t+1})`$ as needed. ∎

## 3 Pushdown automata

We now prove Theorem 1.2. We begin by showing that if $`f`$ is simulated by a pushdown automaton, then $`f`$ is the unique solution of a set of polynomial equations. We then invoke the results of the appendix to deduce that $`f`$ is an algebraic function. In Section 3 we also construct pushdown automata which simulate non-rational functions such as $`f(p)=\sqrt{p}`$. We don’t know if every algebraic $`f:(0,1)(0,1)`$ can be simulated by a pushdown automaton.

### 3.1 Pushdown automata and algebraic functions

The Chomsky-Schützenberger theory implies that if $`L_0`$ and $`L_1`$ are languages which are generated by unambiguous grammars and $`f(p)=𝐏_p[L_1]`$, then $`f(p)`$ is an algebraic function. In this subsection we aim to prove algebraic properties of $`f`$ even when $`L_0`$ and $`L_1`$ are inherently ambiguous.

Suppose $`\mathrm{\Sigma }`$ is a pushdown automaton which simulates a function $`f`$. Call $`(b,s)\mathrm{\Lambda }\times S`$ good, if when the automaton is at state $`s`$ and the stack is $`bw`$ (where $`b`$ is at the top), then with probability $`1`$ at some point the stack will be $`w`$. Call $`(b,s)`$ bad otherwise. By the assumption that $`𝐏_p[L_0L_1]=1`$, it follows that starting at $`(s_0,\tau )`$ it is impossible for the automaton to reach a state $`s`$ with $`bw`$ at the top of the stack, where $`(b,s)`$ is bad. Thus we can redefine all transitions $`(b,s)(b^{}w^{},s^{})`$, where $`(b^{},s^{})`$ is bad, in an arbitrary manner, and still obtain $`𝐏_p[L_0L_1]=1`$. Therefore, without loss of generality we may assume that all $`(b,s)\mathrm{\Lambda }\times S`$ are good.

Let $`\alpha (p;b,s,s^{}),\alpha :[0,1]\times \mathrm{\Lambda }\times S\times S[0,1]`$ be defined as follows. For $`w\mathrm{\Lambda }^{}`$, let $`\alpha (p;b,s,s^{})`$ be the probability that given that currently the automaton is at state $`s`$ and has in its stack $`bw`$ (where $`b`$ is at the top), at the first time that the content of the stack will be $`w`$, it will be at state $`s^{}`$. It is easily seen that $`\alpha (p;b,s,s^{})`$ is well defined (does not depend on $`w`$). Moreover, by the assumption that all $`(b,s)`$ are good, it follows that $`_{s^{}S_0S_1}\alpha (p;b,s,s^{})=1`$.

We extend the definition of $`\alpha `$ to $`\stackrel{~}{\alpha }(p;u,s,s^{}),\stackrel{~}{\alpha }:\mathrm{\Lambda }^{}\times S\times S[0,1]`$, where $`\stackrel{~}{\alpha }(p;u,s,s^{})`$ is the probability that given that currently the automaton is at state $`s`$ and has in its stack $`uw`$ (where $`u`$ is above $`w`$), at the first time that the content of the stack will be $`w`$, it will be at state $`s^{}`$. Note that if $`w=w_1\mathrm{}w_r`$, then

$$\stackrel{~}{\alpha }(p;w,s,s^{})=\underset{i=1}{\overset{r}{}}\alpha (p;w_i,s_i,s_{i+1}),$$
(4)
where the sum is over all

$$(s_1,s_2,\mathrm{},s_r,s_{r+1})\{s\}\times S^{r1}\times \{s^{}\},$$

and if $`ϵ`$ denotes the empty word, then

$$s,s^{}Q:\stackrel{~}{\alpha }(p;ϵ,s,s^{})=1_{\{s=s^{}\}}.$$
(5)
Note that if $`\tau `$ is the initial word at the stack, then

$$𝐏_p[L_1]=\underset{s^{}S_1}{}\stackrel{~}{\alpha }(p;\tau ,s_0,s^{}).$$
(6)
Therefore if we could prove algebraic properties of the functions $`\alpha (p;b,s,s^{})`$, we will deduce algebraic properties of $`f`$.

###### Claim 3.1.

For all $`0<p<1`$, $`\stackrel{~}{\alpha }(p;,,):\mathrm{\Lambda }^{}\times S\times S`$ is the unique bounded solution of the equations

$`w\mathrm{\Lambda }^{},b\mathrm{\Lambda },s,s^{}Q:\stackrel{~}{\alpha }(p;bw,s,s^{})`$ $`=`$ $`p\stackrel{~}{\alpha }(p;\delta (s,1,b)w,\eta (s,1,b),s^{})`$
$`+`$ $`(1p)\stackrel{~}{\alpha }(p;\delta (s,0,b)w,\eta (s,0,b),s^{}),`$
$$s,s^{}Q:\stackrel{~}{\alpha }(p;ϵ,s,s^{})=1_{\{s=s^{}\}}(ϵ\text{ is the empty word}).$$
(8)
###### Proof.

By linearity, it suffices to prove that the zero function is the only bounded solution to (3.1) with the boundary conditions

$$s,s^{}Q:\stackrel{~}{\alpha }(p;ϵ,s,s^{})=0.$$
(9)
Fix $`(w,s)\mathrm{\Lambda }^{}\times Q`$. We will show that $`\stackrel{~}{\alpha }(p;w,s,s^{})=0`$. Consider the random walk $`(W_t,S_t)_{w,s}`$ defined on the graph $`\mathrm{\Lambda }^{}\times Q`$, where $`(W_0,S_0)_{w,s}=(w,s)`$. Given $`W_t=BU`$, where $`B\mathrm{\Lambda }`$, the conditional probabilities for $`(W_{t+1},S_{t+1})`$ are given by

$$(W_{t+1},S_{t+1})=\{\begin{array}{cc}(\delta (S_t,1,B)U,\eta (S_t,1,B))\hfill & \text{ with probability }p,\hfill \\ (\delta (S_t,0,B)U,\eta (S_t,0,B))\hfill & \text{ with probability }1p.\hfill \end{array}$$
(10)
If $`W_t`$ is the empty word, then we let $`(W_{t+1},S_{t+1})=(W_t,S_t)`$. By definition, for all $`s^{}Q`$, the process $`\stackrel{~}{\alpha }(p;W_t,S_t,s^{})`$ is a bounded martingale. The assumption that the pushdown automaton stops a.s. implies by (9) that the martingale converges to $`0`$ a.s. (and therefore in $`L_1`$). We therefore conclude that $`\stackrel{~}{\alpha }(p;W_t,S_t,s^{})`$ is identically $`0`$ as needed.

Recall that given that the current state is $`s`$, and the top of the stack is $`b`$, with probability $`p`$ the automaton will move to state $`s_1=\delta (s,1,b)`$, and instead of $`b`$, the top of the stack will contain $`\eta (s,1,b)=c_1\mathrm{}c_r`$; with probability $`1p`$ the automaton will move to state $`\overline{s}_1=\delta (s,0,b)`$, and instead of $`b`$, the top of the stack will contain $`\eta (s,0,b)=\overline{c}_1\mathrm{}\overline{c}_{\overline{r}}`$.

We can therefore write

$`\alpha (p;b,s,s^{})`$ $`=`$ $`p\left(1_{\{r=0\}}1_{\{s_1=s^{}\}}+1_{\{r>0\}}\stackrel{~}{\alpha }(p;c_1\mathrm{}c_r,s_1,s^{})\right)`$
$`+`$ $`(1p)\left(1_{\{\overline{r}=0\}}1_{\{\overline{s}_1=s^{}\}}+1_{\{\overline{r}>0\}}\stackrel{~}{\alpha }(p;\overline{c}_1\mathrm{}\overline{c}_{\overline{r}},s_1,s^{})\right),`$
Or

$`\alpha (p;b,s,s^{})`$ $`=`$ $`p\left(1_{\{r=0\}}1_{\{s_1=s^{}\}}+1_{\{r>0\}}{\displaystyle \underset{i=1}{\overset{r}{}}\alpha (p;c_i,s_i,s_{i+1})}\right)`$
$`+`$ $`(1p)\left(1_{\{\overline{r}=0\}}1_{\{\overline{s}_1=s^{}\}}+1_{\{\overline{r}>0\}}{\displaystyle \underset{i=1}{\overset{\overline{r}}{}}\alpha (p;\overline{c}_i,\overline{s}_i,\overline{s}_{i+1})}\right).`$
where the first (second) sum is taken over all

$`(s_1,\mathrm{},s_{r+1})`$ $``$ $`\{s_1\}\times S^{r1}\times \{s^{}\},`$
$`(\overline{s}_1,\mathrm{},\overline{s}_{r^{}+1})`$ $``$ $`\{\overline{s}_1\}\times S^{\overline{r}1}\times \{s^{}\}.`$
Note that (3.1) defines a set of algebraic equations in $`p`$ and $`\{\alpha (p;b,s,s^{})\}_{b,s,s^{}}`$.

###### Claim 3.2.

For all $`0<p<1`$, there is a unique positive solution $`\alpha (p;,,):[0,1]\times \mathrm{\Lambda }\times S\times S`$, to equations (3.1) and

$$b\mathrm{\Lambda },sQ:\underset{s^{}Q}{}\alpha (p;b,s,s^{})=1.$$
(13)
###### Proof.

In order to prove the claim it suffices to show that each positive solution to (3.1) and (13) defines a positive bounded solution to (3.1) and (8) via (4) and (5).

It is immediate to see that (3.1) implies (3.1). Moreover, (13) implies by (4) that for all $`w\mathrm{\Lambda }^{}`$ and $`sQ`$, it holds that

$$\underset{s^{}Q}{}\stackrel{~}{\alpha }(p;w,s,s^{})=1.$$

and so $`\stackrel{~}{\alpha }`$ is a bounded function as needed.

Proof of Theorem 1.2:  The result follows immediately from Claim 3.2 by Theorem A.1.

### 3.2 Pushdown automata which simulate non-rational functions

In this subsection we construct a pushdown automaton which simulates a non-rational function. Let $`g:(0,1)(0,1/2)`$ be a rational function. We’ll construct a pushdown automata which simulates the function $`\gamma (p)=\frac{1\sqrt{12g(p)}}{4g(p)}`$.

Taking $`g(p)=(1p)/2`$, we obtain $`\gamma (p)=(1\sqrt{p})/(1p)`$ \- thus using a product construction, it is easy to construct a pushdown automaton simulating the function $`f(p)=\sqrt{p}`$.

Consider a random walk on the ladder graph $`\times \{0,1\}`$ where an edge $`((x,y),(x^{},y^{}))`$ is present if $`x=x^{}`$ and $`|yy^{}|=1`$, or $`|xx^{}|=1`$ and $`y=y^{}`$. The random walk moves to the left (right) with probability $`12g(p)`$, and up (down) with probability $`g(p)`$. Let $`\gamma `$ be the probability that starting at $`(0,1)`$ the first hitting point of the random walk at level $`0`$ ($`\{(0,0),(1,0)\}`$) is $`(0,0)`$. It is easy to see that

$`\gamma `$ $`=`$ $`g(p)+(12g(p))(1\gamma )+g(p)(\gamma ^2+(1\gamma )^2)`$
$`=`$ $`1\gamma +2g(p)\gamma ^2,`$
and therefore

$$\gamma (p)=\frac{1\sqrt{12g(p)}}{2g(p)}.$$
(14)
It is easy to simulate the random walk with a pushdown automaton. The stack alphabet is $`\{x\}`$ where $`x^n`$ correspond to level $`n`$ of the ladder – the initial word at the stack is $`x`$.

Assume first that the input alphabet is $`\{0,1,2\}`$ where the probability that letter $`1`$ appears is $`12g(p)`$, and the probability that letter $`0`$ or $`2`$ appears is $`g(p)`$.

Let $`s_0`$ and $`s_1`$ be two states of the automaton corresponding the left $`(\{0\}\times )`$ and right $`(\{1\}\times )`$ of the ladder. Reading the symbol $`1`$ will correspond to a transition from $`s_0`$ to $`s_1`$ or vice-versa without changing the content of the stack. Reading the symbol $`2`$ at state $`s_i`$ will result at staying at state $`s_i`$ and pushing an $`x`$ to the stack. Reading the symbol $`0`$ at state $`s_i`$ with $`x`$ at the top of the stack, will result at staying at state $`s_i`$ while popping $`x`$ from the stack. In this way it is possible to simulate the random walk given an infinite sequence of $`\{0,1,2\}`$ symbols with $`(g(p),12g(p),g(p))`$ bias - and therefore toss a coin with bias (14).

In the general case where we are given an infinite sequence of $`(p,1p)`$ bits, we use block constructions of Section 2 in order to generate a sequence of $`(g(p),12g(p),g(p))`$ $`\{0,1,2\}`$ variables together with the above construction in order to obtain the required result.

###### Remark 3.3.

Similarly one may construct a pushdown automaton associated with a random walk on the ladder where the probabilities of going $`(\text{up,left-right,down})`$ are given by $`(g(p),1g(p)h(p),h(p))`$. Note however that in this case $`𝐏_p[L_0L_1]=1`$ iff the random walk is recurrent iff $`h(p)g(p)`$. Thus, unlike finite automata, there exist pushdown automata which define a valid simulation only for a proper subset of the interval $`(0,1)`$.

## 4 Related models and open problems

### 4.1 Chomsky-Schützenberger theory

In the seminal paper  titled “The algebraic theory of context-free languages” by Chomsky and Schützenberger, the authors discuss many beautiful relationships between different types of languages and their generating functions. The generating function of a grammar generating a language $`L`$ is defined as $`f=_{wL}n(w)w`$, where $`n(w)`$ is the number of derivations of the word $`w`$ in the grammar, and $`f`$ is viewed as a formal power series in the non-commutative variables $`0`$ and $`1`$. The results of  imply in particular that the generating function of a regular language is rational, which implies Proposition 2.3 – simulation via finite automata always yield rational functions.

In  it is also proven that the generating function of a context-free language is algebraic. However, this does not imply that coins tossed via pushdown automata are algebraic, as many of the context free languages are inherently ambiguous and for such languages, the non-commutative power series $`P(L)=_{w\{0,1\}^{}}1_{\{wL\}}w`$ is not algebraic. (see e.g. ; as Larry Ruzzo kindly noted, there are also context free languages with the prefix property that are inherently ambiguous).

Thus, while Proposition 2.3 could be obtained by projecting the Chomsky-Schützenberger results from the non-commutative setting to the commutative setting, an analogous result for pushdown automata cannot be obtained in a similar way. Theorem 2.2 may be interpreted as a commutative inverse to the Chomsky-Schützenberger result for regular languages, where additional positivity restrictions are imposed.

### 4.2 Theory of computability and Turing machines

A distinctive feature of the computation models discussed in this paper is that they have an unbounded input, unlike the classical Turing machine for which the input is of bounded length.

In  (see  for background), a computational model in analysis is introduced. This model has some common features with the model introduced here – in particular, the input is given as an unbounded sequence. However, the models are different as our model has an input drawn according to an i.i.d. distribution. Moreover, in our model we are looking for a coin which has exactly the correct distribution $`f(p)`$, while in  the aim is find a Turing machine which for an (unbounded) input $`x`$, and an error bound $`ϵ`$ computes an approximation of the function $`f(x)`$ within error margin $`ϵ`$.

There are, however, some striking similarities between the two models. For instance the continuity results of  should be compared with  where it is shown that computable functions are continuous. Moreover it is easy to adapt the proofs of  in order to show that if $`f:(0,1)(0,1)`$ is computable and polynomially bounded from $`0`$ and $`1`$ at $`0`$ and $`1`$, then it possible to simulate the function $`f(p)`$ via a Turing machine.

### 4.3 Exact sampling

The theory of exact sampling (see e.g. ) deals with simulating a complicated probability measure using a simple one. Usually, the simple measure consists of a sequence of unbiased bits or a a sequence of uniform variables.

In this paper both probability measures of interest (the $`p`$ coin and the $`f(p)`$ coin) are simple. The difficulty here is that $`p`$ is unknown. It is easy to estimate $`p`$, and therefore $`f(p)`$. However, to get a coin with an exact bias $`f(p)`$ is harder.

Yet, the problem studied here may be interpreted as a problem in exact sampling. Consider the following examples.

* Suppose that some physical process produces percolation configuration on a grid $`\mathrm{\Gamma }_1`$, where the probability of an open edge is $`p`$. We are interested in performing percolation on a grid $`\mathrm{\Gamma }_2`$, where we want that the probability that an edge $`e`$ is open in $`\mathrm{\Gamma }_2`$ to be equal to the probability that two vertices at distance $`2`$ in $`\mathrm{\Gamma }_1`$ are connected by a path of length $`2`$. Our results allow to use samples of the configuration $`\mathrm{\Gamma }_1`$ in order to produce samples for the process on $`\mathrm{\Gamma }_2`$.
* Let $`\{x_i\}_{i1}`$ be i.i.d. bits with unknown mean $`\alpha `$. Suppose that we are given the products $`\{y_i\}_{i1}`$, where $`y_i=x_{2i}x_{2i1}`$, and we want to simulate (one or more) i.i.d. bits $`\{z_j\}`$ with mean $`\alpha `$. This can be done using the pushdown automaton in Subsection 3.2 that simulates the function $`\sqrt{p}`$.

### 4.4 Some open problems

###### Problem 4.1.

Let $`f:(0,1)(0,1)`$ be a rational function. What is the smallest size of an automaton that simulates $`f(p)`$? Is there an efficient algorithm for finding this automaton?

This problem is potentially hard, as the size of the automaton probably depends on analytic and number theoretic properties of $`f`$ (see ).

###### Problem 4.2.

Let $`f:(0,1)(0,1)`$ be an algebraic function. Can $`f`$ be simulated by a pushdown automaton?

Acknowledgment: We thank Jim Propp for suggesting the problem. We are grateful to Omer Angel, Paul Beame and Larry Ruzzo for helpful remarks, and to Russ Lyons and Sergey Fomin for references. Most of this work was done while the first author was a postdoctoral researcher at Microsoft Research, and the second author was visiting there.

## Appendix A Appendix on Algebraic functions

Christopher J. Hillar <sup>1</sup><sup>1</sup>1This work is supported under a National Science Foundation Graduate Research Fellowship.

chillar@math.berkeley.edu

The purpose of this note is to establish the following fact using techniques from real algebraic geometry. It will be a direct corollary of the more general Theorem A.2 below.

###### Theorem A.1.

Let $`\{F_i(p,x_1,\mathrm{},x_n)\}_{i=1}^m[p,x_1,\mathrm{},x_n]`$, and let $`S`$ be the set in $`^{n+1}`$ defined by

$$S=\{(p,x_1,\mathrm{},x_n):0<p<1\underset{j=1}{\overset{n}{}}0x_j1\underset{i=1}{\overset{m}{}}F_i(p,x_1,\mathrm{},x_n)=0\}.$$

Suppose that for each $`p(0,1)`$, there exist a unique $`(a_1,\mathrm{},a_n)^n`$ such that $`(p,a_1,\mathrm{},a_n)S`$; equivalently, $`S`$ is given as the image of some function $`\varphi :(0,1)[0,1]^{n+1}`$ with $`\varphi (p)=(p,\varphi _1(p),\mathrm{},\varphi _n(p))`$. Then, there exist nonzero polynomials $`g_j[X,Y]`$ such that

$$g_j(p,\varphi _j(p))=0$$

for all $`p(0,1)`$.

We begin with an abstract setting. Let $`K`$ be a field, and let $`P`$ be a subset of $`K`$ satisfying the following two properties:

1. If $`x,yP`$, then $`x+y`$ and $`xyP`$.
2. $`K`$ is the disjoint union of $`P`$, $`\{0\}`$, and $`P`$.

A subset $`P`$ as above is called the set of *positive* elements, and we say that $`P`$ is an *ordering* of $`K`$. A field $`K`$ is then an *ordered* field if there exists an ordering of $`K`$. A *real field* is a field in which $`1`$ is not a sum of squares, and a *real closed field* $`R`$ is a real field such that such that any algebraic extension of $`R`$ that is real must be equal to $`R`$. For example, both $``$ and $`^a`$ are real closed fields (where $`^a`$ is the algebraic closure of $``$). For ease of notation below, we set $`^{}=^a`$. From the definition, it is clear that any real field must have characteristic 0, and thus $``$ naturally embeds in any real field. It also follows that $`^{}`$ is a subset of every real closed field.

Any real closed field $`R`$ has a unique ordering, and the positive elements are the squares of $`R`$. Moreover, every polynomial of odd degree in $`R[x]`$ has a root in $`R`$ \[4, p. 452\]. In light of these observations, the axioms for the theory of real closed fields (RCF) consist of \[3, p. 24\]:

1. the axioms for ordered fields;
2. $`x>0yy^2=x`$;
3. the axiom $`x_0\mathrm{}x_{n1}yy^n+x_{n1}y^{n1}+\mathrm{}+x_0=0`$ for each odd $`n>0`$.

The set $`S`$ as in Theorem A.1 is an example of a set definable by a Boolean combination of a finite number of polynomial inequalities and equalities (over $``$). Such a set is called *semialgebraic* (over $``$), and a function is called *semialgebraic* if its graph is a semialgebraic set. We may now state the main theorem.

###### Theorem A.2.

Let $`R`$ be a real closed field, and let $`A`$ be a semialgebraic subset of $`R`$ defined using polynomials $`\left\{H_i(p)\right\}_{i=1}^k[p]`$. Also, let $`S`$ be a semialgebraic subset of $`R^{n+1}`$ defined by $`\{F_i(p,x_1,\mathrm{},x_n)\}_{i=1}^m[p,x_1,\mathrm{},x_n]`$. Suppose that for each $`pA`$, there exist a unique point $`(a_1,\mathrm{},a_n)R^n`$ such that $`(p,a_1,\mathrm{},a_n)S`$; equivalently, $`S`$ is given as the image of some function $`\varphi :AR^{n+1}`$ with $`\varphi (p)=(p,\varphi _1(p),\mathrm{},\varphi _n(p))`$. Then, there exist nonzero polynomials $`g_j[X,Y]`$ such that

$$g_j(p,\varphi _j(p))=0$$

for all $`pA`$.

A fundamental fact about RCF is that it is a *complete theory* \[3, p. 19\] in the sense that each first order sentence expressible in the theory of RCF is either true in every structure satisfying the RCF axioms or false in every such structure. For example, the sentence, $`xyy^2=x`$, evaluates to false for any structure (such as $``$) satisfying the axioms of RCF. As a standard application of completeness, we present the following

###### Lemma A.3.

Assume the hypothesis of Theorem A.2. Then, for each $`pA^{}`$, we have that $`\varphi _j(p)^{}`$ for all $`j\{1,\mathrm{},n\}`$.

###### Proof.

To simplify notation, we write “$`pA`$”, for example, in place of the Boolean combination of polynomial inequalities and equalities that defines $`A`$. As $``$ embeds in any real closed field, the sentence,

$$px_1\mathrm{}x_n\neg (pA)(p,x_1,\mathrm{},x_n)S,$$

is a valid sentence in any structure satisfying the axioms of RCF. By completeness, it must have the same truth value in every real closed field. Since it is a true statement in $`R`$ by assumption, it follows that it is also true in the real closed field $`^{}`$. Let $`pA^{}`$. Then, there exists a tuple, $`𝐚=(a_1,\mathrm{},a_n)(^{})^n`$, such that $`(p,a_1,\mathrm{},a_n)S`$. By the hypothesis, this $`𝐚`$ must be the unique tuple in $`R^n`$ for this $`p`$, and hence for all $`j`$, $`\varphi _j(p)=a_j^{}`$, completing the proof.

A key result in the theory of RCF is the following theorem (which is essentially a restatement of the fact that RCF has quantifier elimination) \[5, p. 92\].

###### Theorem A.4 (Tarski-Seidenberg Theorem).

The projection of a semialgebraic set is semialgebraic.

###### Corollary A.5.

The functions $`\varphi _j`$ are semialgebraic functions.

###### Proof.

Let $`T=\{(p,x_1,\mathrm{},x_n):pA(p,x_1,\mathrm{},x_m)S\}`$, which is semialgebraic. Then, the image of the projection of $`T`$ into $`R^2`$ given by $`(p,a_1,\mathrm{},a_n)(p,a_j)`$ is also semialgebraic by the theorem.

Semialgebraic functions are well-behaved in the following sense \[6, p. 17\].

###### Theorem A.6.

Let $`R`$ be a real closed field. If $`T`$ is a semialgebraic subset of $`R^n`$ and $`h:TR`$ is semialgebraic, then there is a nonzero polynomial $`g(X_1,\mathrm{},X_n,Y)R[X_1,\mathrm{},X_n,Y]`$ such that $`g(𝐱,h(x))=0`$ for all $`𝐱T`$.

We remark that applying Theorem A.6 with Corollary A.5 already gives a result similar to Theorem A.2. The only subtlety is that we would like the polynomial $`g`$ to be in $`[X,Y]`$ instead of $`R[X,Y]`$. We are now ready prove Theorem A.2.

###### Proof of Theorem A.2.

Fix $`j\{1,\mathrm{},n\}`$. We will apply Theorem A.6 with $`R=^{}`$ and $`T=A^{}`$. From Lemma A.3, it follows that $`\varphi _j(T)^{}`$, and from Corollary A.5, we have that $`\varphi _j`$ is semialgebraic. Therefore, from Theorem A.6, there is a nonzero polynomial $`g(X,Y)^{}[X,Y]`$ such that $`g(p,\varphi _j(p))=0`$ for all $`pA^{}`$. We will now produce a nonzero polynomial $`\stackrel{~}{g}[X,Y]`$ with the same property.

Consider the field, $`^{}(X)`$, of rational functions in the variable $`X`$. View $`g(X,Y)`$ as a polynomial in the variable $`Y`$ over $`^{}(X)`$, and, upon clearing denominators, let $`q_i(X,Y)^{}[X,Y]`$ ($`i=1,\mathrm{},r`$) be the irreducible factors of $`g(X,Y)`$ (over $`^{}(X)`$). It is clear that for all $`pA^{}`$, we have

$$\underset{i=1}{\overset{r}{}}q_i(p,\varphi _j(p))=0.$$

Fix $`i`$ and let $`\alpha _1,\mathrm{},\alpha _t^{}`$ be all of the coefficients in $`q_i(X,Y)`$. Extend $`(X)`$ by these coefficients, so that $`(X)(\alpha _1,\mathrm{},\alpha _t)`$ is a finite extension of $`(X)`$. Also, let $`(X)(\alpha _1,\mathrm{},\alpha _t)(y)`$ be a finite extension of $`(X)(\alpha _1,\mathrm{},\alpha _t)`$ defined by the equation $`q_i(X,y)=0`$. It follows that $`y`$ is algebraic over $`(X)`$, and upon clearing denominators, let $`\stackrel{~}{q}_i(X,Y)[X,Y]`$ be such that $`\stackrel{~}{q}_i(X,y)=0`$.

Since both $`q_i(X,Y)`$ and $`\stackrel{~}{q}_i(X,Y)`$ have $`y`$ as a root and since $`q_i(X,Y)`$ is irreducible, it follows that $`q_i(X,Y)`$ divides $`\stackrel{~}{q}_i(X,Y)`$. As both $`\stackrel{~}{q}_i(X,Y)`$ and $`q_i(X,Y)`$ are in $`^{}[X,Y]`$, Gauss’s Lemma \[4, p. 181\] gives us that,

$$h_i(X,Y)=\stackrel{~}{q}_i(X,Y)/q_i(X,Y)^{}[X,Y].$$

Let

$$\stackrel{~}{g}(X,Y)=\underset{i=1}{\overset{r}{}}\stackrel{~}{q}_i(X,Y)[X,Y].$$

We claim that $`\stackrel{~}{g}(X,Y)`$ is our desired polynomial. But indeed, for all $`pA^{}`$,

$$\stackrel{~}{g}(p,\varphi _j(p))=\underset{i=1}{\overset{r}{}}q_i(p,\varphi _j(p))h_i(p,\varphi _j(p))=0.$$

Finally, let $`A`$ and $`R`$ be as in the statement of Theorem A.2, and let $`W`$ be the graph of $`\varphi _j:AR`$, which is a semialgebraic set (over $``$). Consider the sentence,

$$pa\neg ((p,a)W)\stackrel{~}{g}(p,a)=0,$$

which is valid in any structure satisfying the axioms of RCF (again, since $``$ embeds in any real closed field). By the above argument, it is a true statement for $`^{}`$, and therefore, by completeness, it is also true for $`R`$. This completes the proof.

As a final remark, we note that the fussiness in the proof of Theorem A.2 was necessary to avoid division by zero after applying the substitution homomorphism with $`Xp`$ and $`Y\varphi _j(p)`$.