AEC 2016

Invited Speakers

• Alin Bostan (INRIA Saclay, France)

  Algebraicity and transcendence of power series:
  combinatorial and computational aspects
  Abstract: From ancient times, mathematicians are interested in the following question: is a given real number "algebraic" (that is, a root of a nonzero univariate polynomial with rational number coefficients), or is it "transcendental"? Although almost all real numbers are transcendental, it is notoriously difficult to actually prove, or disprove, the transcendence of a given constant. More recently, and especially with the advent of computers, different related questions arose: What is the "complexity" of a real number? How fast can one compute the first digits, or one single digit, of a (computable) real number? Can digits of algebraic numbers be computed faster than those of (computable) transcendental numbers?
  In this series of lectures, we will consider the (simpler) functional analogues of these questions: given a formal power series with rational number coefficients, decide whether it is algebraic (root of a nontrivial bivariate polynomial) or transcendental, and determine how fast can one compute its coefficients?
  We will first motivate these questions by presenting some examples of algebraic power series coming from combinatorics, with a focus on enumeration of lattice walks. Then we will discuss several methods that allow to discover and prove the nature (algebraic or transcendental) of a generating function, with an emphasis on an experimental mathematics approach combined with algorithmic methods such as Guess'n'Prove and Creative Telescoping. Finally, we will overview efficient algorithms for various operations on algebraic power series, including the computation of one or several selected terms.

• Dan Romik (University of California at Davis, U.S.A.)

  Combinatorics at the interface of probability, analysis and experimental mathematics
  Abstract: Algebraic and enumerative combinatorialists love to study highly structured families of combinatorial objects such as permutations, partitions, and Young tableaux. The theory of such objects is fascinating, and one can spend many years enjoyably studying them using traditional combinatorial and algebraic methods (generating functions, bijections etc.).
  In this lecture series I aim to illustrate how the insights into such combinatorial objects can be considerably enriched by adding the "new" (not really!) elements of probability and analysis: the consideration of asymptotic ("large N") and statistical (e.g., typical, or average) properties of these objects adds a whole new dimension to one's understanding and thinking, and answering the questions raised by such considerations often requires heavy analytic machinery and tools from complex analysis, Fourier analysis, differential equations, and more. I will demonstrate this with several notable examples: the problem of longest increasing subsequences (a.k.a. the Ulam-Hammersley problem), limit shapes of random partitions and random Young tableaux, stochastic traffic and sorting models, and more. No prerequisite knowledge beyond standard undergraduate courses in combinatorics, probability and analysis will be assumed or required
  In addition to probability and analysis, a third theme of the lectures will be that of experimental mathematics -- the philosophy that using computers and coding to experiment on your favorite mathematical objects can make you smarter and more successful as a mathematician. I hope to convince you of this claim, again through some entertaining examples related to the topics mentioned above.

• Jeffrey Shallit (University of Waterloo, Canada)

  The logical approach to automatic sequences
  Abstract: Automatic sequences are sequences over a finite alphabet generated by a finite-state machine. They form an interesting class that has been widely studied. In this series of lectures, I will discuss a decision method for solving numerous problems about automatic sequences based on first-order logic and the work of Presburger, Buchi, Villemaire, Bruyere, Hansel, Michaux, and others. This method allows one to prove or disprove many properties of automatic sequences purely mechanically. As an example, consider the Thue-Morse sequence 01101001... which is 1 at position n if and only if n has an odd number of 1's in its base-2 expansion. Thue proved that this sequence has no overlap, that is, no sub-block of the form axaxa, where a is a single letter and x is an arbitrary block. Even today, no really simple (one-paragraph) proof of this fact is known, but it can be proved by a computer in a matter of milliseconds using the decision procedure. This decision procedure can also be used in a combinatorial fashion, to enumerate various aspects of automatic sequences. I will illustrate the method with known results from the literature and many new results. Students can also experiment with free software that implements the decision method.