Arithmetic Combinatorics Program
Long presentations:
Ben Green (Cambridge/IAS)
"Gowers norms in characteristic two"
Abstract: Suppose that f is a bounded function on the vector space F_2^n.
The Gowers U^d-norm of f counts d-dimensional parallelepipeds in F_2^n, weighted by the function f. These norms are fundamental objects of study in additive combinatorics and seem to be of increasing interest in the computer science community. It was widely supposed (the ``inverse
conjecture'') that the Gowers Ud-norm of a function f can only be large if f correlates with a degree d-1 polynomial. Recently a counterexample to this assertion in the case d = 4 was discovered independently by Lovett-Meshulam-Samorodnitsky and by Tao and I. I will discuss this counterexample before moving on to some more positive results concerning the distribution of polynomials over F2. All of this is joint work with T. Tao.
A. Wigderson (IAS)
"Extractors, Ramsey Graphs and Arithmetic Combinatorics"
Abstract: I will survey recent results and open problems on the explicit constructions of certain pseudo-random objects, including randomness extractors and Ramsey graphs.
I. Laba (UBC)
"Arithmetic progressions in Salem sets"
We address the following question: if $E\subset [0,1]$ is a set of Hausdorff dimension $\alpha$, must $E$ contain a 3-term arithmetic progression? We construct a counterexample of dimension $\alpha=1$. On the other hand, we do have a positive result when $E$ supports a measure whose Fourier transform has appropriate decay at infinity. This is joint work with Malabika Pramanik.
B. Kra (North Western)
"Nilsequences in ergodic theory and additive combinatorics"
Abstract: Nilsequences arose in the study of the multiple ergodic averages
associated to Furstenberg's proof of Szemer\'edi's Theorem. They are a generalization of almost periodic sequences, and portions of the classical theory for almost periodic sequences can be generalized for higher
order nilsequences. I will discuss the role of nilsequences in the development of this "higher order Fourier" analysis, and their applications in additive combinatorics and ergodic theory. This is joint work with Bernard Host.
E. Szemeredi (Rutgers/IAS)
"When does A+A become a square?"
Abstract: We show that if A is a subset of {1,...,} with more than 11/32n elements, then A+A contains a square. The bound is best possible.
A. Graville (Montreal/IAS)
"Pretentiousness in analytic number theory"
Inspired by Tim Gowers' notion of "Rough Classification"
we explore various well-known problems of analytic number theory from this perspective and find some new results.
P. Sarnak(IAS), "An affine sieve"
Y. Bilu (Bordeaux)
"Transcendence of automatic numbers (after Adamczewski, Bugeaud)"
I will report on the recent proof, due to A. & B., of the following
theorem: if the digits of the decimal expansion of a real number can be generated by a finite automaton, then the number is either rational or transcendent. In other words, there is no computer program that, would print at the output the n-th decimal digit of the square root of 2, without overflowing the memory for large n.
The proof is based on the celebrated subspace theorem of W. Schmidt. I will give an introduction to this theorem as well.
------------------------------------------------------------
Short presentations:
Javier Cilleruelo (Madrid)
"Sidon sets and the distribution of powers in Fp"
We present a simple approach to the study of the distribution of powers in Fp which applies to many problems: k-powers in short intervals, small powers of primitive roots in short intervals, polynomial equations in Fp, etc... Although we do not get new estimates, the method is purely combinatorial and avoids the use of exponential and character sums, the usual tools to deal with these problems.
A.Kontorovich (Brown)
"The Hyperbolic Lattice Point Count in Infinite Volume with Applications to Sieves"
We develop novel techniques using abstract operator theory to obtain asymptotic formulae for lattice counting problems on infinite-volume hyperbolic manifolds, with error terms which are uniform as the lattice moves through ``congruence'' subgroups. These methods have their origins in
the work of Selberg, Lax-Phillips and Duke-Rudnick-Sarnak, and the uniformity relies on the spectral gap established in Bourgain-Gamburd and Bourgain-Gamburd-Sarnak. We give an application to the theory of affine linear sieves.
S. Konyagin (IAS)
"Waring problem with the Ramanujan $\tsu$-function."
H. Nguyen (Rutgers)
"On Erdos square sum free problem"
Erdos (1986) asked the following question:
Let A be a subset of {1,2..,n} such that no collection of elements of
A sums to a square. How big can A be ?
Observe that if p is a prime about n2/3, then the set p,2p,..,
\lfloor n/p \rfloor p is such a set.
It is conjectured that any square sum free set has O(n^{1/3}) elements.
There is a series of partial results on this conjecture: Alon (87):
O(n/log n), Lipkin (89)
n^{3/4 +o(1)}, Alon-Freiman (88): n^{2/3+ o(1)}, Sarkozy (94) n^{1/2 +o(1)}.
In this talk, we discuss a recent improvement that shows
asymptotically tight bound
n^{1/3 +o(1)}. (Joint work with V. Vu)
J. Solymosi (UBC/IAS)
"Variants of the sum-product problems"
K. Costello (IAS)
"Quadratic Littlewood-Offord and rank of random symetric matrices."
A claissical result of Littlewood and Offord (strengthened by Erdos) showed that if a_1,...,a_n are non-zero numbers and x_1,..,x_n are iid Bernoulli random variables, then the probability that the linear form L(x_1,..,x_n) = a_x_1+ ...+ a_n x_n equals 0 is O(1/n^{1/2}).
We discuss the quadratic version of this result where L is replaced by a quadratic form Q = sum_{ij} c_{ij} x_i x_j and its relation to to problem of determining the rank of a random symmetric matrices.
(joint with T. Tao and V. Vu)
B.Sudakov (UCLA/IAS)
"Discrete Kakeya-type problems and small bases"
A subset $U$ of a group $G$ is called $k$-universal if $U$ contains a translate of every $k$-element subset of $G$. We give several nearly optimal constructions of small $k$-universal sets, and use them to resolve an old question of Erd\H{o}s and Newman on bases for sets of integers, and to obtain several extensions for other groups.
Joint work with N. Alon and B. Bukh