# The Art of Iterating Rational Functions over Finite Fields (13w5141)

Arriving in Banff, Alberta Sunday, May 5 and departing Friday May 10, 2013

## Organizers

Nigel Boston (University of Wisconsin at Madison)

Alina Ostafe (Macquarie University)

Igor Shparlinski (University of New South Wales)

Michael Zieve (University of Michigan)

## Objectives

Despite the recent profusion of scientific activity in related areas, little progress has been made on Dynamical Systems over Finite Fields (DFF). The present exciting and challenging mathematical problems in DFF are of an intricate algebraic and number theoretic flavour whose study requires deep mathematical and computational tools. This area of research focuses on the construction of non-classical dynamical systems over finite fields and the study of atypical behaviour which is not present in standard constructions from complex dynamical systems. Such novel constructions and the classification of their anomalous behaviour have led to innovative solutions to problems in cryptography, biological and physical systems.

Many important questions regarding the orbits of DFF remain wide open, including questions on the number of aperiodic points, the size of orbit intersections (in linearly disjoint DFF), cycle lengths, and so on. Furthermore, the problems proposed as the goal of this proposal have barely been touched upon by other meetings. On the other hand, we believe that there is now enough of a theoretical background and also active interest shown by many distinguished researchers in the area of DFF and related fields to successfully attack many of the long-standing problems.

Besides intrinsic interest, such DFF are of prime interest for applications. They are also more computer-friendly (due, for example, to the limited size of elements in the trajectories) permitting computer simulations and experiments that may lead to the discovery of new effects which may not be visible or even computable in dynamical systems over the real and complex numbers.

Research into DFF has not only a high theoretical value, but also applied significance thanks to the great number of potential applications to many different areas of modern cryptography, coding theory, Monte Carlo simulations, physics, biology, and other areas. It is also a fertile ground for the development of algorithmic and computer-oriented approaches.

The topics of the proposed workshop will center on the following closely related and cross-fertilising directions in DFF:

Trajectory length and periodic structure. One of the most fundamental, yet notoriously hard, questions concerns the periodic structure of polynomial iterations. Heuristically, this periodic structure can be predicted based on the Birthday Paradox, but very few rigorous results are known in this area (essentially only very weak lower bounds obtained by J. H. Silverman several years ago). This is especially important due to the recently discovered connection (by F. Vivaldi and J. Roberts) between the integrability of dynamical systems and periodic structure of the reductions of polynomial iterations modulo distinct primes. A very recent preprint by R. L. Benedetto et al. gives new theoretical insight and also some heuristics and numerics. There is also still an unexplored approach via the image set of polynomials and their iterations. All the aforementioned authors will be invited to this workshop, which we expect to shed more light on the problem.

Overall, the situation is not well-understood both theoretically and heuristically. We also plan to conduct an extensive series of numerical tests in order to gain better understanding, which in turn may lead to new theoretic advances.

Representation and algebraic properties of iterates. The goal is to construct DFF which are generated by multivariate polynomials with prescribed degree the growth (e.g., polynomial growth vs. typically expected exponential growth) and admit a concise description of their iterations. In previous work, using just the degree argument has proved to be a very fruitful approach leading to a leap in the quality of results obtained and their applications. For example, this property led to new classes of pseudorandom number generators (PRNGs) with much better distribution properties, opening up a new direction in research.

It has also been shown that "controlling" algebraic properties of iterates is a fundamental mathematical problem whose solution has multiple implications.

Little progress has been made in this direction, and the only results known are mainly for univariate polynomials. Some questions to be researched and analysed during this workshop include, but are not limited to: irreducibility of iterations of irreducible polynomials (so-called stability of polynomials), the greatest ommon divisor of polynomial iterates (in particular co-primality), properties of the varieties defined by iterations of polynomials, exponential and character sums with polynomial iterates, construction of new classes of permutation polynomials using iterations of polynomials, etc. Recently, several new approaches emerged, attacking these problems from different angles.

Group theoretic aspects. The group of wild continuous automorphisms of the local field, $Fq((t))$, is an object of study both in group theory, as the Nottingham

group, a source of examples of just-infinite pro-$p$ groups, and in the theory of norm fields in algebraic number theory. By connecting the two independently emerging fields, I. Fesenko simultaneously produced a new family of just-infinite groups and a counter-example to the Coates-Greenberg conjecture. In the direction of dynamics, recent striking advances in finding explicit elements of finite order have been made by T. Chinburg, P. Symonds, and others.

Moreover, Galois groups of iterates connect dynamics with the relatively new field of iterated monodromy groups. Properties of these groups, such as their size and their proportion of fixed point free elements, answer dynamical questions such as the proportion of primes dividing elements of an iteratively created integer sequence.

Applications. Amongst many other applications, DFF lead to high quality PRNGs.

The desirable features of PRNGs depend on the application and there are different quality measures. For example, in cryptography, unpredictability is the most crucial feature. Other common features include the absence of "hidden" linearities, low autocorrelation, and uniform distribution. The use of pseudorandom numbers in a wide range of applications like simulation, cryptography, wireless communication, etc., has made apparent a need for a large variety of generators with "good" behaviour with respect to some particular measures. Other applications include design and analysis of cryptographic hash functions based on iteration of polynomials, sequences over finite fields, quasi-Monte Carlo methods, and integrability to mention just a few.

We expect that the proposed workshop will open a flood gate for new ideas, problems, and methods as well as concrete results in this area. Bringing together the aforementioned researchers so that they can combine their techniques (and of course, intellectual efforts) will certainly lead to groundbreaking results.

As regards timeliness, the area of DFF has witnessed a burst of activity over the last decade. This area is closely related to Number Theory, Commutative Algebra, Cryptography, Finite Fields and of course Dynamical Systems. Thus, researchers of different backgrounds and in possession of different technical toolboxes sometimes work on similar questions without knowing each other's ideas and results. The goal of the workshop is to change this and establish new collaborations, which will lead to solutions to many long-standing problems, formulation of new ones, and advancing the theory of DFF with innovative results.

This workshop will follow in the footsteps of the special semester of "Complex and Arithmetic Dynamics" at ICERM, but it will focus on very different aspects. The ICERM semester, and several other recent workshops on ADS, have focused on connections of ADS with either complex dynamics or arithmetic geometry in characteristic zero. The proposed workshop would be the first to focus on finite fields. It will bring together researchers from a variety of mathematical and computational backgrounds to address problems and advance the general theory of DFF and related applications. We foresee a very productive exchange of ideas and formulations of new problems between these researchers.

Applications to cryptography will be of special value. Today, more than ever, being able to communicate safely and efficiently is extremely important. Society and business require fast, reliable, and secure communications. Cryptography also provides authentication of messages, via digital signatures, and shared keys for access to data or materials. Much effort is spent in the development of new cryptosystems and in the improvement of the commonly used ones. At the heart of most of these cryptographic schemes lies the generation of (pseudo) random numbers to ensure the security of these schemes.

Also, understanding the complex behaviour of different polynomial systems will lead to a much better understanding of many phenomena in nature, such as physics (turbulence in fluids), biology (patterns in culture growth) and human society (collective behavior), and thus enrich the area of applications of DFF.

Many important questions regarding the orbits of DFF remain wide open, including questions on the number of aperiodic points, the size of orbit intersections (in linearly disjoint DFF), cycle lengths, and so on. Furthermore, the problems proposed as the goal of this proposal have barely been touched upon by other meetings. On the other hand, we believe that there is now enough of a theoretical background and also active interest shown by many distinguished researchers in the area of DFF and related fields to successfully attack many of the long-standing problems.

Besides intrinsic interest, such DFF are of prime interest for applications. They are also more computer-friendly (due, for example, to the limited size of elements in the trajectories) permitting computer simulations and experiments that may lead to the discovery of new effects which may not be visible or even computable in dynamical systems over the real and complex numbers.

Research into DFF has not only a high theoretical value, but also applied significance thanks to the great number of potential applications to many different areas of modern cryptography, coding theory, Monte Carlo simulations, physics, biology, and other areas. It is also a fertile ground for the development of algorithmic and computer-oriented approaches.

The topics of the proposed workshop will center on the following closely related and cross-fertilising directions in DFF:

Trajectory length and periodic structure. One of the most fundamental, yet notoriously hard, questions concerns the periodic structure of polynomial iterations. Heuristically, this periodic structure can be predicted based on the Birthday Paradox, but very few rigorous results are known in this area (essentially only very weak lower bounds obtained by J. H. Silverman several years ago). This is especially important due to the recently discovered connection (by F. Vivaldi and J. Roberts) between the integrability of dynamical systems and periodic structure of the reductions of polynomial iterations modulo distinct primes. A very recent preprint by R. L. Benedetto et al. gives new theoretical insight and also some heuristics and numerics. There is also still an unexplored approach via the image set of polynomials and their iterations. All the aforementioned authors will be invited to this workshop, which we expect to shed more light on the problem.

Overall, the situation is not well-understood both theoretically and heuristically. We also plan to conduct an extensive series of numerical tests in order to gain better understanding, which in turn may lead to new theoretic advances.

Representation and algebraic properties of iterates. The goal is to construct DFF which are generated by multivariate polynomials with prescribed degree the growth (e.g., polynomial growth vs. typically expected exponential growth) and admit a concise description of their iterations. In previous work, using just the degree argument has proved to be a very fruitful approach leading to a leap in the quality of results obtained and their applications. For example, this property led to new classes of pseudorandom number generators (PRNGs) with much better distribution properties, opening up a new direction in research.

It has also been shown that "controlling" algebraic properties of iterates is a fundamental mathematical problem whose solution has multiple implications.

Little progress has been made in this direction, and the only results known are mainly for univariate polynomials. Some questions to be researched and analysed during this workshop include, but are not limited to: irreducibility of iterations of irreducible polynomials (so-called stability of polynomials), the greatest ommon divisor of polynomial iterates (in particular co-primality), properties of the varieties defined by iterations of polynomials, exponential and character sums with polynomial iterates, construction of new classes of permutation polynomials using iterations of polynomials, etc. Recently, several new approaches emerged, attacking these problems from different angles.

Group theoretic aspects. The group of wild continuous automorphisms of the local field, $Fq((t))$, is an object of study both in group theory, as the Nottingham

group, a source of examples of just-infinite pro-$p$ groups, and in the theory of norm fields in algebraic number theory. By connecting the two independently emerging fields, I. Fesenko simultaneously produced a new family of just-infinite groups and a counter-example to the Coates-Greenberg conjecture. In the direction of dynamics, recent striking advances in finding explicit elements of finite order have been made by T. Chinburg, P. Symonds, and others.

Moreover, Galois groups of iterates connect dynamics with the relatively new field of iterated monodromy groups. Properties of these groups, such as their size and their proportion of fixed point free elements, answer dynamical questions such as the proportion of primes dividing elements of an iteratively created integer sequence.

Applications. Amongst many other applications, DFF lead to high quality PRNGs.

The desirable features of PRNGs depend on the application and there are different quality measures. For example, in cryptography, unpredictability is the most crucial feature. Other common features include the absence of "hidden" linearities, low autocorrelation, and uniform distribution. The use of pseudorandom numbers in a wide range of applications like simulation, cryptography, wireless communication, etc., has made apparent a need for a large variety of generators with "good" behaviour with respect to some particular measures. Other applications include design and analysis of cryptographic hash functions based on iteration of polynomials, sequences over finite fields, quasi-Monte Carlo methods, and integrability to mention just a few.

We expect that the proposed workshop will open a flood gate for new ideas, problems, and methods as well as concrete results in this area. Bringing together the aforementioned researchers so that they can combine their techniques (and of course, intellectual efforts) will certainly lead to groundbreaking results.

As regards timeliness, the area of DFF has witnessed a burst of activity over the last decade. This area is closely related to Number Theory, Commutative Algebra, Cryptography, Finite Fields and of course Dynamical Systems. Thus, researchers of different backgrounds and in possession of different technical toolboxes sometimes work on similar questions without knowing each other's ideas and results. The goal of the workshop is to change this and establish new collaborations, which will lead to solutions to many long-standing problems, formulation of new ones, and advancing the theory of DFF with innovative results.

This workshop will follow in the footsteps of the special semester of "Complex and Arithmetic Dynamics" at ICERM, but it will focus on very different aspects. The ICERM semester, and several other recent workshops on ADS, have focused on connections of ADS with either complex dynamics or arithmetic geometry in characteristic zero. The proposed workshop would be the first to focus on finite fields. It will bring together researchers from a variety of mathematical and computational backgrounds to address problems and advance the general theory of DFF and related applications. We foresee a very productive exchange of ideas and formulations of new problems between these researchers.

Applications to cryptography will be of special value. Today, more than ever, being able to communicate safely and efficiently is extremely important. Society and business require fast, reliable, and secure communications. Cryptography also provides authentication of messages, via digital signatures, and shared keys for access to data or materials. Much effort is spent in the development of new cryptosystems and in the improvement of the commonly used ones. At the heart of most of these cryptographic schemes lies the generation of (pseudo) random numbers to ensure the security of these schemes.

Also, understanding the complex behaviour of different polynomial systems will lead to a much better understanding of many phenomena in nature, such as physics (turbulence in fluids), biology (patterns in culture growth) and human society (collective behavior), and thus enrich the area of applications of DFF.