GSS: Combinatorics and Number Theory
Summer Seminar 2001

We meet every Thursday at 1 p.m. in 241 Altgeld Hall.

June 7: Fraenkel's Conjecture (Kevin O'Bryant)
One of the gems of generating functionology is the proof that if the positive integers are partitioned into finitely many congruence classes (e.g., $2n$, $4n+1$, and $4n+3$), then two of the moduli are equal. A sequence of the form $S(x,y)=(\lfloor n x + y \rfloor)_{n\geq1}$ is called a Beatty Sequence with {\em rate} $x$ and {\em rest} $y$; this is clearly a generalization of congruence classes. Fraenkel observed (around 1970) that the sequences $S(7,-3), S(7/2,-1), S(7/4,0)$ have distinct rates and partition the positive integers, and conjectured that this is fundamentally the only way to do so with 3 Beatty Sequences. Moreover, he gave a partition of the positive integers into $m$ Beatty Sequences with distinct rates for each $m \geq 3$, and conjectured that his list was complete. R. Tijdeman recently proved that Fraenkel's Conjecture is true for $m \leq 6$ by studying the combinatorics of balanced words on a finite alphabet. I will present this and other partial results.
June 14: Combinatorial Game Theory and Surreal Numbers (Michael Baym)
This is primarily an expository talk on the theory of combinatorial game theory, and the surreal numbers which arise logically thereof. Several theorems on games and surreal numbers will be presented, largely without proof.
June 21: Formal Languages and Number Theory (Soroosh Yazdani)
This talk is going to cover some tools from formal language theory that can be used in number theory. Specifically it will cover a theorem from Chirstol et. al. which relates algebraic formal power series over finite fields to $k$-automatic sequences. As an application of this theorem, I will present a proof of J.-P. Allouche of the transcendence of Tate period in finite characteristic.
June 28: Open Problems in Unit Fractions - A Survey (Jimmy McLaughlin)
This talk will consist of a survey of open problems in the number theoretic properties of unit (Egyption) fractions and will be based on a chapter in "Old and new problems and results in combinatorial number theory." by Paul Erdos and Ronald Graham. (Monographies de L'Enseignement Mathmatique [Monographs of L'Enseignement Mathmatique], 28.) The level will be elementary but the talk will contain plenty of problems for people to get their mathematical incisors into, if they feel so inclined.
July 5: NO SEMINAR (Holiday)
July 12: Some Generalizations of Ramsey's Theorem (Pedro Poitevin)
We will formulate and discuss generalizations of the classical Ramsey theorem, as well as some results closely related to it. In particular, we will talk about the Galvin-Prikry theorem, Silver's analytic Ramsey theorem, the Nash-Williams dichotomy, as well as Gowers' Ramsey Theorem. The aim is to understand how all these results are related to each other. We will introduce and use a little bit of game-theoretic jargon during the talk, and we hope to indicate in broad terms how these results have played a significant role in recent spectacular developments in research on the geometry of Banach spaces.
July 19: Sums of powers of polynomials (Bruce Reznick)
This talk will survey some of the ways in which one can look at sums of powers of polynomials. There will be an emphasis on "local methods", by which is meant "methods practiced by Urbana mathematicians".
July 26: The Discrete Log Problem Challenge (Diana White)
We've all known since our first algebra course in elementary school that multiplication is "easy" but factoring is "hard". However, it's years later (if ever) that we first realize there are other similar problems. For example, exponentiation is "easy", but "logarithms" are hard.

This famous computational number theory (and cryptography) problem is called the discrete log problem, formally stated as: Let $G$ be a cyclic group. Given $g,h \in G$, find a positive integer $x$ such that $g^x=h$.

We first motivate this problem with a real-world scenario, then discuss the following methods for solving it: Shanks' Baby-Step Giant-Step, Pollard's-rho, Pohlig-Hellman, and Index Calculus. Don't let all these names scare you! They are quite simple to understand, requiring only some elementary number theory and group theory. We even illustrate with examples (it is summer, after all). Finally, we discuss ways to improve these methods (this part will include some more advanced stuff for the die-hards).

August 2: Short Talks
Kevin O'Bryant presented a proof and explanation of why the digits "987" occurs sooner, on average, than the digits "989" in the decimal expansion of a uniformly chosen real from [0,1].

Jimmy McLaughlin presented numerical evidence concerning the determinant of the nxn matrix whose (i,j)-th component is the (n-1)*i+j - th prime number (i.e. the n^2 entries are the first n^2 primes, arranged in the obvious manner).

Heini Halberstam presented an anonymous note on generating solutions to Markov's Equation x^2+y^2+z^2=3xyz with Fibonacci numbers.

Bruce Berndt showed that q-Series are as easy as 1-2-3, with credit passed to George Andrews.

Bruce Reznick, inspired by Jimmy's questions, noted that the auspicious vector
6
-3
-2
1

is in the null space of the "prime-Hankel" matrix:

2 3 5 7
35 7 11
571113
7111317