You are currently browsing the tag archive for the ‘tom sanders’ tag.

A few days ago, I received the sad news that Yahya Ould Hamidoune had recently died. Hamidoune worked in additive combinatorics, and had recently solved a question on noncommutative Freiman-Kneser theorems posed by myself on this blog last year. Namely, Hamidoune showed

Theorem 1 (Noncommutative Freiman-Kneser theorem for small doubling) Let ${0 < \epsilon \leq 1}$, and let ${S \subset G}$ be a finite non-empty subset of a multiplicative group ${G}$ such that ${|A \cdot S| \leq (2-\epsilon) |S|}$ for some finite set ${A}$ of cardinality ${|A|}$ at least ${|S|}$, where ${A \cdot S := \{ as: a \in A, s \in S \}}$ is the product set of ${A}$ and ${S}$. Then there exists a finite subgroup ${H}$ of ${G}$ with cardinality ${|H| \leq C(\epsilon) |S|}$, such that ${S}$ is covered by at most ${C'(\epsilon)}$ right-cosets ${H \cdot x}$ of ${H}$, where ${C(\epsilon), C'(\epsilon) > 0}$ depend only on ${\epsilon}$.

One can of course specialise here to the case ${A=S}$, and view this theorem as a classification of those sets ${S}$ of doubling constant at most ${2-\epsilon}$.

In fact Hamidoune’s argument, which is completely elementary, gives the very nice explicit constants ${C(\epsilon) := \frac{2}{\epsilon}}$ and ${C'(\epsilon) := \frac{2}{\epsilon} - 1}$, which are essentially optimal except for factors of ${2}$ (as can be seen by considering an arithmetic progression in an additive group). This result was also independently established (in the ${A=S}$ case) by Tom Sanders (unpublished) by a more Fourier-analytic method, in particular drawing on Sanders’ deep results on the Wiener algebra ${A(G)}$ on arbitrary non-commutative groups ${G}$.

This type of result had previously been known when ${2-\epsilon}$ was less than the golden ratio ${\frac{1+\sqrt{5}}{2}}$, as first observed by Freiman; see my previous blog post for more discussion.

Theorem 1 is not, strictly speaking, contained in Hamidoune’s paper, but can be extracted from his arguments, which share some similarity with the recent simple proof of the Ruzsa-Plünnecke inequality by Petridis (as discussed by Tim Gowers here), and this is what I would like to do below the fold. I also include (with permission) Sanders’ unpublished argument, which proceeds instead by Fourier-analytic methods. Read the rest of this entry »

This is an adaptation of a talk I gave recently for a program at IPAM. In this talk, I gave a (very informal and non-rigorous) overview of Hrushovski’s use of model-theoretic techniques to establish new Freiman-type theorems in non-commutative groups, and some recent work in progress of Ben Green, Tom Sanders and myself to establish combinatorial proofs of some of Hrushovski’s results.