What’s new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

# Open question: noncommutative Freiman theorem

2 March, 2007 in math.CO, math.GR, question | Tags: additive combinatorics, Freiman's theorem, group theory

This is another one of my favourite open problems, falling under the heading of inverse theorems in arithmetic combinatorics. “Direct” theorems in arithmetic combinatorics take a finite set A in a group or ring and study things like the size of its sum set $A+A := \{ a+b: a,b \in A \}$ or product set $A \cdot A := \{ ab: a,b \in A \}$. For example, a typical result in this area is the sum-product theorem, which asserts that whenever $A \subset {\Bbb F}_p$ is a subset of a finite field of prime order with $1 \leq |A| \leq p^{1-\delta}$, then

$\max( |A+A|, |A \cdot A| ) \geq |A|^{1+\epsilon}$

for some $\epsilon = \epsilon(\delta) > 0$. (This particular theorem was first proven here, with an earlier partial result here; more recent and elementary proofs with civilised bounds can be found here, here or here. It has a number of applications.)

In contrast, inverse theorems in this subject start with a hypothesis that, say, the sum set A+A of an unknown set A is small, and try to deduce structural information about A. A typical goal is to completely classify all sets A for which A+A has comparable size with A. In the case of finite subsets of integers, this is Freiman’s theorem, which roughly speaking asserts that if $|A+A| = O(|A|)$, if and only if A is a dense subset of a generalised arithmetic progression P of rank O(1), where we say that A is a dense subset of B if $A \subset B$ and $|B| = O(|A|)$. (The “if and only if” has to be interpreted properly; in either the “if” or the “only if” direction, the implicit constants in the conclusion depends on the implicit constants in the hypothesis, but these dependencies are not inverses of each other.) In the case of finite subsets A of an arbitrary abelian group, we have the Freiman-Green-Ruzsa theorem, which asserts that $|A+A| = O(|A|)$ if and only if A is a dense subset of a sum P+H of a finite subgroup H and a generalised arithmetic progression P of rank O(1).

One can view these theorems as a “robust” or “rigid” analogue of the classification of finite abelian groups. It is well known that finite abelian groups are direct sums of cyclic groups; the above results basically assert that finite sets that are “nearly groups” in that their sum set is not much larger than the set itself, are (dense subsets of) the direct sums of cyclic groups and a handful of arithmetic progressions.

The open question is to formulate an analogous conjectural classification in the non-abelian setting, thus to conjecture a reasonable classification of finite sets A in a multiplicative group G for which $|A \cdot A| = O(|A|)$. Actually for technical reasons it may be better to use $|A \cdot A \cdot A| = O(|A|)$; I refer to this condition by saying that A has small tripling. (Note for instance that if H is a subgroup and x is not in the normaliser of H, then $H \cup \{x\}$ has small doubling but not small tripling. On the other hand, small tripling is known to imply small quadrupling, etc., see e.g. my book with Van Vu.) Note that I am not asking for a theorem here – just even stating the right conjecture would be major progress! An if and only if statement might be too ambitious initially: a first step would be to obtain a slightly looser equivalence, creating for each group G and fixed $\epsilon > 0$ a class ??? of sets for which the following two statements are true:

1. If A is a finite subset of G with small tripling, then A is a dense subset of $O(|A|^\epsilon)$ left- or right- translates of a set P of the form ???.
2. If P is a set of the form ???, then there exists a dense subset A of P with small tripling (possibly with a loss of $O(|A|^\epsilon)$ in the tripling constant).

An obvious candidate for ??? is the inverse image in N(H) of a generalised geometric progression of rank O(1) in an abelian subgroup of N(H)/H, where H is a finite subgroup of G and N(H) is the normaliser of H; note that property (2) is then easy to verify. Let us call this the standard candidate. I do not expect this standard candidate to fully suffice, though I do not know at present of a counterexample. (Update, Mar 5: Now I do – a discrete ball in a nilpotent group.) But it seems to be a reasonably good candidate nevertheless. In this direction, some partial results are known:

• For abelian groups G, from the Freiman-Green-Ruzsa theorem, we know that the standard candidate suffices.
• For $G = SL_2({\Bbb C})$, we know from work of Elekes and Király and Chang that the standard candidate suffices.
• For $G = SL_2({\Bbb F}_p)$, there is a partial result of Helfgott, which (roughly speaking) asserts that if A has small tripling, then either A is a dense subset of all of G, or is contained in a proper subgroup of G. It is likely that by pushing this analysis further one would obtain a candidate for ??? in this case.
• For $G = SL_3({\Bbb Z})$, there is a partial result of Chang, which asserts that if A has small tripling, then it is contained in a nilpotent subgroup of G.
• For the lamplighter group $G = {\Bbb Z}/2{\Bbb Z} \wr {\Bbb Z}$, there is a partial result of Lindenstrauss which (roughly speaking) asserts that if A has small tripling, then A cannot be nearly invariant under a small number of shifts. It is also likely that by pushing the analysis further here one would get a good candidate for ???.
• For a free non-abelian group, we know (since the free group embeds into $SL_2({\Bbb C})$) that the standard candidate suffices; a much stronger estimate in this direction was recently obtained by Razborov.
• For a Heisenberg group G of step 2, there is a partial result of myself, which shows that sets of small tripling also have small tripling in the abelianisation of G, and are also essentially closed under the antisymmetric form that defines G. This, in conjunction with the Freiman-Green-Ruzsa theorem, gives a characterisation, at least in principle, but it is not particularly explicit, and it may be of interest to work it out further.
• For G torsion-free, there is a partial result of Hamidoune, Lladó, and Serra, which asserts that $|A \cdot A| \geq 2|A|-1$, and that if $|A \cdot A| \leq 2|A|$ then A is a geometric progression with at most one element removed; in particular, the standard candidate suffices in this case.

These examples do not seem to conclusively suggest what the full classification should be. Based on analogy with the classification of finite simple groups, one might expect the full classification to be complicated, and enormously difficult to prove; on the other hand, the fact that we are in a setting where we are allowed to lose factors of O(1) may mean that the problem is in fact significantly less difficult than that classification. (For instance, all the sporadic simple groups have size O(1) and so even the monster group is “negligible”.) Nevertheless, it seems possible to make progress on explicit groups, in particular refining the partial results already obtained for the specific groups mentioned above. (Update, Mar 5: Via Akshay Venkatesh and Elon Lindenstrauss, I learnt that perhaps the closer analogy is with Gromov’s theorem, rather than the classification of finite simple groups. Which makes things slightly more hopeful… nevertheless, the question of revisiting the classification from a “O(1) perspective” may still be interesting.)

## 37 comments

Terry,

A very interesting post. Following some work I did with Tom Sanders, I’d like to suggest a possible splitting of non-commutative Freiman into two parts. The first is called “weak Freiman” and I can state it explicitly; the second is “strong Freiman” and I do not have any thoughts to add to those you have already put down in your post.

Weak Freiman is the statement that if A has small tripling then some large subset A’ of A is contained in a “Bourgain system”. A Bourgain system is a certain notion of what it means to be an approximate group. The idea comes from Bourgain’s 1998 paper on Roth’s theorem, hence the name.

In my paper with Sanders we only defined Bourgain systems in the abelian case, but I’d guess it extends to the non-abelian case as follows.

A Bourgain system in some group G is a collection (X_t)_{t = 0}^{10} of sets such that

(i) If g is in X_t then so is g^{-1}
(ii) X_t X_u and X_u X_t are both subsets of X_{t + u} when t,u > c_1(K)|A| such that A’ is contained inside a Bourgain system with |X_1| U_d(C), where d is not too big. Then the pull-back under pi of any ball about the identity matrix will be a Bourgain system of dimension about d (kind of a non-abelian Bohr set, by the way). What can one say about the structure of such sets? One would seem to need some kind of non-abelian geometry of numbers.

Anyway there are some great questions in this area waiting to be worked on…..

Ben

Terry, half my post got deleted. Any idea what happened?

Ben

3 March, 2007 at 2:50 am

Anonymous

Ben,

Most blogs limit the size of a “fast reply” to a few hundred characters. If you plan to post a long reply, it’s best to type it in notepad or some other text editor, and copy and paste it into the reply window. Then if it is truncated, simply copy and paste the rest in another reply.

(Another advantage of not typing long shpiels directly in the reply box is that you don’t risk losing the lot if you accidently hit the “back” button – Firefox is a bit better at saving input in forms, and I think the latest IE has improved, but it used to be maddening when this happened!)

Terence,

Have you ever considered the ABC Conjecture, or do you know if any progress has been made on it? Seems like a glass cliff face to me, but then I’d have said the same about primes in arbitrarily long arithmetic progressions and many of the other problems you have tackled.

Cheers
John R Ramsden

3 March, 2007 at 2:55 am

John R Ramsden

P.S. Oops – I should have addressed the ABC conjecture question to Terence _and_ Ben (and for that matter to anyone else who might be qualified to speculate).

Dear John,

Thanks for clearing up the truncation issue. I poked around but couldn’t find a way to modify the threshold for these “fast replies”. It seems that if one has a wordpress account then it is easier to make and then edit fancy comments, though.

Regarding the ABC conjecture, I tend to distinguish between two types of number theory problems: “many-solutions” problems and “no-solutions” problems. “many-solutions” problems ask for one or more solutions to some system of equations in integers or primes. Examples include the Goldbach or Waring problems, the twin prime conjecture, or finding long progressions in primes. “no-solutions” problems, on the other hand, ask that the number of solutions to a certain system in a certain range is in fact zero (or bounded independently of various parameters). Fermat’s last theorem is the most famous example of the latter; the ABC conjecture can also be rephrased in this form. (Specifically, if N_1, N_2, N_3 are large integers and A_i is the set of numbers of size at least (N_1 N_2 N_3)^{1+epsilon} with radical at most N_i, there are no solutions to a_1 + a_2 = a_3 with a_i in A_i.) Other examples of “no-solutions” problems include the finitude of Fermat primes and the (now solved) Catalan conjecture.

With “many-solutions” problems, one can try to solve the problem by getting a lower bound on the number of solutions; as long as the lower bound is non-trivial, one solves the problem. This suggests analytical methods, as one can tolerate error terms as long as they are dominated by the main term in the lower bound. But such techniques are much less likely to work for “no-solutions” problems; one has to get an upper bound which is less than 1, but all upper bounds are clearly at least zero, so one is aiming for an incredibly miniscule target and can basically afford no losses in error terms whatsoever. I believe that the best hope for such problems instead lies in methods from algebraic number theory.

Thinking about it a little more, I guess one of the indicators of difficulty of a number-theoretic problem is not so much whether it is asking for many solutions or for none, but rather just how large of a “conspiracy” amongst the natural numbers would be needed to disprove the conjecture.

For instance, take FLT. It would only take a single solution to a^n + b^n = c^n for some n > 2 to destroy the conjecture; this looks like a very small conspiracy, difficult to detect by most methods, and so the conjecture should be very difficult. But it turns out that such a conspirator must inevitably involve a very strange elliptic curve, which in turn drags in many other mathematical objects into the conspiracy, which makes it more feasible to detect and then destroy such a conspiracy.

On the other hand, a failure of the twin prime conjecture (say) would require an infinite number of conspiracies: past a certain point, every prime p is somehow forbidding p-2 and p+2 to be prime. We can’t yet say that all these conspiracies don’t happen at once, but it is plausible that one could set up some sort of computable statistic involving the primes which would detect and then exclude this scenario.

With arithmetic progressions, the conspiracy has to be even more “global”: if there are no prime progressions of length k, then whenever p, p+r, …, p+(k-2)r are large primes, then p+(k-1)r is mysteriously forced to be composite. Since p and r can be independently quite large, this gives a lot of structural information on the primality of p+(k-1)r which can hopefully be detected or exploited. (Indeed we sort of exploit this kind of information in our proof, via the machinery of “dual functions”. Rather amusingly, we don’t directly exclude the “conspiracy” of exotic structure in the primes, but instead we “co-opt” any such conspiracy, placing it into a homogenised model f_{U^\perp} of the primes which can then be forced (via Szemeredi’s theorem) to cough up progressions. In later papers we exclude these conspiracies directly.)

Ah, I got caught by the truncation issue also :-) . Actually I found the source of the problem: the less-than sign is interpreted as an HTML tag and so should be avoided in comments. I’m guessing that the portion of Ben’s post which was removed was the portion between a \lt sign and a \gt sign.

Returning back to the ABC conjecture, in order for this conjecture to be false one needs a sparse sequence of counterexamples, namely a sequence of solutions a+b=c with rad(abc) \leq c^{1+o(1)}. This sequence can be arbitrarily sparse and thus does not generate the type of aggregate bias which could be detectable by an analytical statistic (though this method might conceivably give a non-trivial upper bound to the number of ABC counterexamples). Instead, one would probably have to algebraically transform such a counterexample to another setting (possibly one from transcendence theory?) in which any conspiracy becomes large enough to be detectable. (cf. the “dispersion method” of Linnik.) Not that I have any idea how to achieve this…

Dear Terry,

Here is an attempt to revisit my post of yesterday without using less than/greater than symbols,
which HTML doesn’t seem to cope with.

Your post was very interesting. Following some work I did with Tom Sanders, I’d like to suggest a possible splitting of non-commutative Freiman into two parts. The first is called “weak Freiman” and I can state it explicitly; the second is “strong Freiman” and I do not have any thoughts to add to those you have already put down in your post.

Weak Freiman is the statement that if A has small tripling then some large subset A’ of A is contained in a “Bourgain system”. A Bourgain system is a certain notion of what it means to be an approximate group. The idea comes from Bourgain’s 1998 paper on Roth’s theorem, hence the name.

In my paper with Sanders we only defined Bourgain systems in the abelian case, but I’d guess it extends to the non-abelian case as follows.

A Bourgain system in some group G is a collection (X_t)_{t = 0}^{10} of sets such that

(i) If g is in X_t then so is g^{-1};
(ii) X_t X_u and X_u X_t are both subsets of X_{t + u} when t, u are at most 5;
(iii) 0 is in X_t for all t;
(iv) |X_{2t}| is no more than C|X_t| for some C and for all t at most 5.

log C may be interpreted as a kind of “dimension” of the Bourgain system.

What is the point of this definition? There are many places inside a Bourgain system where one can look and see
objects which are almost closed under addition. For example if t and u are “typical” values and if u is much less than
t then X_t + X_u will be almost the same as X_t. These properties are enough to enable Tom and I (in the abelian case)
to do a kind of “approximate harmonic analysis” on a Bourgain system. Actually all the ideas for doing that came from
Bourgain’s work and some unpublished notes of yours. For some applications (such as the one Tom and I had) this is all
one needs, and any more precise algebraic structural information about the Bourgain system is unnecessary. For example,
though the theorem you call the “Freiman-Green-Ruzsa Theorem” lets you relate an abelian Bourgain system to a coset
progression, we did not need this fact in our application.

Thus a Bourgain system (in the abelian case) qualifies as an approximate group in a quite strong sense.

I’m guessing that in the non-abelian case things are pretty similar, and one can do a kind of approximate representation
theory, at least of low-dimensional representations – I haven’t worked out the details yet.

So here’s my guess at a “weak Freiman”:

Suppose that |A+A| is at most K|A|. Then there is some subset A’ of A with size at least c_1(K)|A| such that
A’ is contained inside a Bourgain system of dimension c_2(K) with |X_1| having size at most c_3(K)|A|.

How might one prove such a weak Freiman theorem? Unfortunately one of the key steps in the proof of the Freiman-Green-Ruzsa theorem
is simply false for non-abelian groups. That is the existence of “good models”. Thus one can have a set A with *very*
small tripling (say about 3) with no large subset which is Freiman-isomorphic to a dense subset of a group.
This means that you can’t repeat our trick of transferring to a setting where the tools of (non-abelian) harmonic analysis
can be applied. I think there may be some hope of generalising a recent “energy-increment” argument of you and I; Tom

I can’t add much more to what you wrote concerning the correct statement of a “strong Freiman theorem”.
There is one example which I think ought to be instructive. Let G be a finite abelian group and suppose that pi from G to
U_d(C) is a unitary representation. Then the pull-back under pi of any ball about the identity matrix is
likely (assuming some amount of equidistribution of pi(G) in U_d(C)) to be a Bourgain system of dimension about d.
What can one say about the algebraic structure of such “unitary Bohr sets”? Is there a kind of “non-abelian geometry
of numbers” which allows one to find structure inside these sets? I think that the study of some
examples with small d (which I haven’t done yet) could be instructive here.

Anyway there are some great questions in this area waiting to be worked on…..

Ben

Ben please could you post some of these great questions in this area?
zerocold

5 March, 2007 at 6:53 am

akshay

Lindenstrauss has suggested that a non-commutative Freiman theorem should be connected to quantifications of Gromov’s theorem: a group of polynomial growth is virtually nilpotent. As far as I know, no quantitative form of that is known. Anyway, that may suggest candidates for ???

Thanks Akshay!

It does seem that virtual nilpotency is perhaps the key (the above-mentioned paper of Chang also makes this type of connection). Incidentally I realised that one can use a nilpotent group to concoct a set of small tripling for which my “standard candidate” doesn’t come close to approximating – take the Heisenberg group of upper-triangular matrices $\begin{pmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix}$ and consider the set A in which $a, b = O(N); c = O(N^2)$.

Perhaps the revised candidate for ??? would be the inverse image (under the projection N(H) -> N(H)/H by a finite group H) of a set B of small tripling contained inside a nilpotent group.

7 March, 2007 at 11:42 am

anonymous

You probably mean a,c = O(N) and c = O(N^2)

7 March, 2007 at 11:43 am

anonymous

You probably mean a,c = O(N) and b = O(N^2)

[...] an earlier blog Terry discussed Freiman’s theorem. The name of Freiman is attached to a growing body of [...]

I have a question about the case of a general Abelian group G. What is the best known result for the case G has *no* finite subgroups?

Dear HL,

In the torsion-free abelian case (i.e. G is abelian with no non-trivial finite subgroups), one can use the “Freiman isomorphism” trick to reduce the problem to the classical case $G={\Bbb Z}$ of the integers. (Quick sketch: since the set A one is studying is finite, one can reduce to the group generated by A, i.e. one can assume G is finitely generated. Since G is also abelian and torsion free, it is now isomorphic to a lattice ${\Bbb Z}^d$. Now, one cannot embed all of ${\Bbb Z}^d$ homomorphically inside the integers. But we are not really using all of ${\Bbb Z}^d$, since A is finite, we can work inside a big d-dimensional cube inside ${\Bbb Z}^d$, which can be mapped homomorphically and injectively into the integers in a variety of ways.)

In the integers, the classical theorem of Freiman applies: if $|A+A| \leq K|A|$, then A can be contained in a generalised arithmetic progression of rank at most F(K) and cardinality at most G(K) |A|. The best bounds for F and G are currently due to Chang, who obtained F(K) = K-1 and $G(K) = \exp( O( K^2 \log^3 K ) )$ for K large. There is also a variant due to Bilu and refined slightly by Ben Green and myself, which has the same hypothesis but concludes instead that A is contained inside $\exp( O_\epsilon( K^{O(1)} ) )$ translates of a generalised arithmetic progression of rank at most $\log_2 K + \epsilon$ and cardinality at most |A|, where $\epsilon > 0$ is arbitrary.

I’d like to throw out a specific recreational mathematics problem which I realized is on the same theme as non-commutative Freiman theorems.

It is known that the diameter of the Rubik’s cube group (in the half- and quarter-turn metric) is between 20 and 27. Meanwhile
here is a histogram of the word lengths of a random sample of 1,000 positions. You would guess just from looking at the histogram that the diameter is 20; it would be strange if it were more than 21.

Is there a way to prove that the diameter of the Rubik’s Cube group is 20, by combining Freiman-style results with simple-minded computer data? If not an outright proof, is there a probabilistic protocol, in the vein of Arthur-Merlin protocols or probabilistic primality?

For example, the histogram does immediately demostrate, if you are content with a probabilistic verification, that the diameter of the Rubik’s cube group is at most 36. That’s just by the pigeonhole principle: more than half of the positions can be solved in 18 moves. I have heard that for a time, this probabalistic verification was the best upper bound on the diameter of the cube group.

Actually, the pigeonhole principle even establishes a probabilistic verification that the diameter is at most 35, better than 36. More than a quarter of the positions can be solved in 17 or fewer moves, while only 3% require 19 or more moves. Therefore every ball of radius 17 intersects every ball of radius 18.

(Sorry, I made a mistake; this emendation could be attached to the previous post. )

2 April, 2007 at 5:02 pm

sum-product

two papers related to this problem came out

http://arxiv.org/abs/math/0703676

http://arxiv.org/abs/math/0703614

Dear Greg,

Your arguments seem to say that most pairs of points have distance at most 35 from each other. I never played Rubik, but I guess the underlying graph is vertex-transitive. In that case, the histogram actually would imply that most pair of points have distance at most 20 from each other, as the distribution of the distance between two random points is the same as the distribution of the distance between a fixed point and a random one. Best, Van.

5 April, 2007 at 10:48 pm

Anonymous

The Rubik’s cube graph is actually a Cayley graph of the Rubik’s cube group. So yes, it is vertex-transitive, in fact freely transitive. My question is not about most pairs of points, it’s about all pairs of points. (I.e., the graph diameter or worst case.) If it is true, as the histogram almost proves, that the distance between 97% of pairs is 18 or less and the distance between 25% of pairs is 17 or less, then the distance between all pairs of vertices is 35 or less. So my question is whether you can use approximate group theory somehow to improve this immediate but pretty inference.

5 April, 2007 at 10:55 pm

Greg Kuperberg

Oh oops, I accidentally signed that as “anonymous”!

I don’t understand your point. The histogram is about a set of random samples, how can it say something about all pairs ? In theory, the only thing a small set of random samples can say is that the number of bad pairs are small.

The point is that the histogram is a probabilistic verification of a mathematical assertion. If there existed even one pair of points in the cube whose distance is 36, then the probability of making such a histogram would be less than $10^{-100}$. Or if you are not satisfied with that histogram, you could make a bigger histogram whose odds of occurrence are less than $10^{-2000}$. Think about it.

Anyway, my question is whether one can improve such a probabilistic verification using better group theory ideas.

Dear Greg,

This is an interesting question. My guess is that one will have to understand the representation theory of the Rubik’s cube group in order to be able to convert these sorts of probabilistic statements into rigorous ones. There is a nascent theory of quasirandom groups, as pioneered by Gowers, which asserts roughly speaking that if a finite group G has no low-dimensional representations, then its multiplicative structure is highly expansive, thus we expect for instance A.A.A to be much larger than A if A is already rather large to begin with. This type of result probably can be used to show that large balls intersect each other rather often, which might indeed lead to some diameter bound. This type of thing has for instance been carried out for $SL_2(F_p)$ recently by Bourgain and Gamburd.

If there are small representations, there could be the very unlikely scenario that all the random elements you selected happen to lie in one corner of the representation – e.g. in a normal subgroup of small index. Then the data you have collected does not “span” enough of the group to definitively pin down the diameter.

First, my own perspective is that the probabilistic statements actually are rigorous, in a way: They are entirely rigorous probabilistic verifications rather than rigorous proofs. The situation is similar to that of numbers that are known as “probable primes”. It is not the same kind of lack of rigor as a physics discussion where many things have not been defined. So let us say that it would be good to change probabilistic verifications into deterministic proofs. This is true — although it is known using less elegant combinatorial methods that the cube group diameter is at most 27.

But I also think that it would be exciting to find a new probabilistic verification that the cube group diameter is 26 or better. In the competition between probabilistic verifications and deterministic proofs, the former can never do worse; it would be fun to have more examples where they can do better. Unfortunately the diameter < 35 result was a temporary victory.

Anyway, for either purpose, I agree that it would be nice to know the representation theory of the Rubik’s cube group. But that isn’t mysterious. The Rubik’s cube group is an index 12 subgroup of the disassembly group. That group is the Cartesian product of the corner group and the edge group. The corner group is the wreath product of S8 and C3, while the edge group is the wreath product of S12 and C2. The reason that the cube group has index 12 is that the corner rotations and edge flips satisfy congruences, while the parity of the edge permutation has to equal the parity of the corner permutation.

Note that the center of the cube group has order 2. The central involution is called the “superflip” move or position. It is known to have distance 20, and for all I know it is the unique position of distance 20. There may be a lesson in that too.

I realize that it is a bit dull to prove a theorem (or probabilistically verify a theorem) about one specific finite case instead of infinite sequences. But I think that this particular one is an interesting test case for new ideas. Among other things, it robs you of the license to prove estimates with bad constants.

28 August, 2007 at 9:47 am

Anonymous

Are there more continuous versions of the type of Freiman’s theorem? For instance could there be a result along the lines that if A is a subset of the reals of full Hausdorff Dimension, then A-A contains an interval (or if it doesn’t, then A has to have a certain form)?

Dear Anonymous,

There are some versions of Freiman’s theorem for measurable subsets E of Euclidean space in which E+E or E-E has comparable Lebesgue measure to E, see e.g. Proposition 7.1 in my paper

http://front.math.ucdavis.edu/math.CO/0601431

This result is in fact deduced rather easily from discrete versions of Freiman’s theorem.

The question of dimensional versions of Freiman’s theorem is a very interesting one: given a set A of reals for which A+A or A-A has the same Hausdorff dimension as A, what can one conclude about A? Note that in your above example it is certainly possible for A-A to not contain an interval, for instance A could be the union of a nested sequence G_n of subgroups of R of Hausdorff dimension 1-1/n (it is not too difficult to construct subgroups of any specified dimension, and with a little more work one can make them nested). Part of the problem here is that the quantitative bounds for discrete Freiman theorems are still too poor to say anything meaningful in this regime. Indeed, a toy discrete model of the statement “dim(A+A)=dim(A)” for some continuous set A would be the statement that $|A+A| \leq C_\epsilon |A|^{1+\epsilon}$ for some finite but large set A of integers, where $\epsilon > 0$ is small (more precisely, one could consider a sequence $A_n$ of such sets with cardinality going to infinity, and a sequence of $\epsilon_n$ going to zero slowly). At present we have no fully satisfactory Freiman-type characterisation of these sets. However we do have the Plunnecke-Ruzsa sumset theory which is effective in this regime. For instance, for a finite set A with the above property we can also bound quantities such as $|A-A|$ and $|A+A+A|$ by $O( |A|^{1+O(\epsilon)} )$. Similarly, in the continuous world, if A is a (say) compact set of reals with dim(A+A)=dim(A), then one can show that dim(A+A+A)=dim(A) and dim(A-A) = dim(A) as well. A deep theorem of Bourgain (part of what was once called the “Katz-Tao conjecture”) also asserts that dim(A.A) > dim(A) in this case.

[...] groups“, submitted to Contrib. Disc. Math..  This paper concerns the problem (discussed in this earlier blog post) of determining the correct analogue of Freiman’s theorem in a general non-abelian group .  [...]

13 September, 2009 at 2:33 am

Ehud Hrushovski

Dear Terry,
approximate subgroups in particular. I have no precise answers to any of them, but it turns out that analogous issues have been studied in model theory for some time, with dimension theories replacing finite cardinalities or orders of magnitude. I tried to make this analogy precise in a paper I posted on ArXiv, “stable group theory and approximate subgroups”, arXiv:0909.2190. One of the statements made there shows a close connection between approximate subgroups and Lie groups, and has something of the flavor of Ben Green’s words on “approximate representations” on this page. Another consequence is that approximate subgroups generating \$G(F_q)\$ for a large prime power \$q\$ must contain a positive proportion of the elements of \$G(F_q)\$, where \$G\$ is a fixed simple algebraic group. -Udi

[...] theorem, Isaac Goldbring, type | by Terence Tao One of my favorite open problems, which I have blogged about in the past, is that of establishing (or even correctly formulating) a non-commutative analogue of [...]

[...] theorem | by Terence Tao Let be a finite subset of a non-commutative group . As mentioned previously on this blog (as well as in the current logic reading seminar), there is some interest in classifying those [...]

[...] exactly? There is not yet a full consensus on what the list of structured objects should be (see this earlier post for more discussion), but things are well understood in the abelian case, at least. Examples of [...]

[...] of stating and proving this statement is the noncommutative Freiman theorem problem, discussed in these earlier blog [...]

[...] new proof of a “noncommutative Freiman” type theorem in linear groups . As discussed in earlier blog posts, a general question in additive (or multiplicative) combinatorics is to understand the [...]

[...] free groups, nilpotent groups, solvable groups, or simple groups of Lie type) are also known; see these previous blog posts for a summary of several of these [...]

Cancel
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 45, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9401860237121582, "perplexity_flag": "head"}