============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Arithmetic progressions with a pseudorandom step
            
Palestrante: Elad Aigner-Horev
             Universität Hamburg

Hora e Data: 14h00, sexta-feira, 21 de setembro de 2012

Local:       Sala Multi-usos do Numec

Resumo:

Given two dense sets A and S in a finite abelian group G, we
consider  the  problem  of  counting three  term  arithmetic
progressions in  A whose common difference is  in S (3-S-AP,
hereafter).  Without any  additional assumptions  the answer
might  be  zero.  Inspired  by  the  polynomial  Szemer\'edi
theorem, we  add an assumption on the  pseudorandomness of S
and attain the following results.

For G =Z_n, we give  a quantitative result asserting that if
the U^3 norm of S  is sufficiently "small" then there exists
a constant C such that A contains at least C |S| n 3-S-APs.

In general,  the condition  on the U^3  norm of S  cannot be
replaced by  a similar  condition on the  U^2 norm of  S, as
then again the number of 3-S-APs might be zero.

Nevertheless, for  G =F_p^n  (with p a  fixed odd  prime) we
give a qualitative result  asserting that for every \eps, if
the U^2 norm  of S is sufficiently "small",  then A contains
at least (\alpha^3-\eps)|G||S|  3-S-APs, where \alpha is the
density  of A and  \eps is  arbitrarily small.  The constant
\alpha^3-\eps is then best possible.

In this  talk, we  shall first give  a rough outline  of our
proofs for the  above results where the aim  is to introduce
the main tools used in  these proofs, namely the inverse U^3
theorem in  Z_n and the arithmetic regularity  lemma for U^3
in F_p^n. A brief exposition of these will then be given.

The talk will be self-contained.

Joint work with Hiep Han.