Feeds:
Posts
Comments

Posts Tagged ‘combinatorics’

La taille de l’ensemble des différences des éléments d’un ensemble donné est un thème classique en combinatoire.  Citons le nombre de distances distinctes entre les points d’un ensemble de cardinal donné (question de Erdos) ou la récente théorie des groupes approximatifs.

Yuri LIMA a présenté ce 15 septembre au groupe de travail Ergodique et dynamique, le résultat suivant sur les ensembles polynomiaux (images de l’ensemble des entiers par un polynôme à coefficients entiers). SI E_1,\dots,E_r sont des ensembles polynômiaux tels que $\sum_{i=1}^r 1/deg(E_i)>1$, alors pour Lebesgue presque tout \lambda\in\mathbb R^{r-1}, la somme F:=E_1+\lfloor\lambda_1E_1\rfloor+\dots+\lfloor\lambda_rE_r\rfloor est de densité de Banach supérieure strictement positive. D’après le théorème de Szemerédi, ceci implique que F contient des progressions arithmétiques arbitrairement longues.

La preuve de Lima et Gugu repose sur un analogue d’un théorème classique de théorie géométrique de la mesure, le théorème de Marstrand. Selon ce théorème, si K_1,K_2 sont deux compacts de \mathbb R dont la somme des dimensions de Hausdorff est strictement plus grande que 1, alors, pour presque tout \lambda\in\mathbb R,  l’ensemble unidimensionnel K_1+\lambda K_2 est de mesure de Lebesgue strictement positive.

Lima et Gugu utilisent une notion de dimension généralisant naturellement la densité de Banach supérieure et observe que l’image de \mathbb Z par un polynôme de degré d est bien de dimension 1/d en ce sens. Leur preuve a également besoin d’une propriété de “régularité conjointe” des ensembles polynomiaux qui n’a pas de contrepartie dans le cas classique.

Read Full Post »

M. Bjorklund gave a talk in Orsay on the following problem in additive combinatorics:

Given A,B\subset\mathbb Z, show that A+B:=\{a+b:a\in A, b\in B\} is “large” unless they have a “special structure”.

The size of sets is defined here in terms of their upper Banach density: d^*(A)=\sup_{a,b} \limsup_{n\to\infty}|A\cap[a_n,b_n-1]|/(b_n-a_n+1) where a,b ranges over the integer sequences such that b_n-a_n\to\infty.

The special structure is the following form of quasi-periodicity: A\subset\mathbb Z is a Bohr set if there exists a morphism \sigma mapping \mathbb Z into some compact metric Abelian group K and an open subset U\subset K whose boundary has zero Haar measure \lambda(\partial U)=0 such that A=\sigma^{-1}(U).

His results (joint with A. Fish) are the following:

Theorem 1. If A is a Bohr set then d^*(A+B) \geq \min(1,d^*(A)+d^*(B)).

Theorem 2. If A is a Bohr set and d^*(A+B)=d^*(A)+d^*(B)<1 then B is also a Bohr set.

The results are deduced from the following ergodic theorems:

Theorem 3. In the above setting, d^*(S+\sigma^{-1}(U))\geq \inf_F \lambda(F+U) where F ranges over the measurable subsets Haar measure $\lambda(F)\geq d^*(S)$.

Theorem 4. Let (X,\mathcal B,\mu,T) be an ergodic probabilistic dynamical system. Let K and U\subset K be as above. Let A\in\mathcal A be such that 0<\mu(\bigcup_{k\in\sigma^{-1}(U)} T^{-k}A)=\mu(A)+\lambda(U)<1. Then:

  • A belongs to the Kronecker factor of T (it is measurable wrt the \sigma-algebra generated by the eigenfunctions of f\mapsto f\circ T);
  • K is the unit circle and U is an interval;
  • there is a factor map \pi:(X,\mu,T)\to(K,\lambda,S), with S a rotation, and A the preimage of an interval up to a negligible set.

More precisely Theorems 1 and 2 are deduced from their ergodic counterparts using a slight strenthening of Furstenberg’s Correspondence principle and results on subsets of metric compact Abelian groups, notably due to Kneser in the fifties).

Read Full Post »