You are currently browsing the tag archive for the ‘Freiman isomorphism’ tag.
This week I have been at a Banff workshop “Combinatorics meets Ergodic theory“, focused on the combinatorics surrounding Szemerédi’s theorem and the Gowers uniformity norms on one hand, and the ergodic theory surrounding Furstenberg’s multiple recurrence theorem and the Host-Kra structure theory on the other. This was quite a fruitful workshop, and directly inspired the various posts this week on this blog. Incidentally, BIRS being as efficient as it is, videos for this week’s talks are already online.
As mentioned in the previous two posts, Ben Green, Tamar Ziegler, and myself proved the following inverse theorem for the Gowers norms:
Theorem 1 (Inverse theorem for Gowers norms) Let
and
be integers, and let
. Suppose that
is a function supported on
such that
Then there exists a filtered nilmanifold
of degree
and complexity
, a polynomial sequence
, and a Lipschitz function
of Lipschitz constant
such that
There is a higher dimensional generalisation, which first appeared explicitly (in a more general form) in this preprint of Szegedy (which used a slightly different argument than the one of Ben, Tammy, and myself; see also this previous preprint of Szegedy with related results):
Theorem 2 (Inverse theorem for multidimensional Gowers norms) Let
and
be integers, and let
. Suppose that
is a function supported on
such that
Then there exists a filtered nilmanifold
of degree
and complexity
, a polynomial sequence
, and a Lipschitz function
of Lipschitz constant
such that
The case of this theorem was recently used by Wenbo Sun. One can replace the polynomial sequence with a linear sequence if desired by using a lifting trick (essentially due to Furstenberg, but which appears explicitly in Appendix C of my paper with Ben and Tammy).
In this post I would like to record a very neat and simple observation of Ben Green and Nikos Frantzikinakis, that uses the tool of Freiman isomorphisms to derive Theorem 2 as a corollary of the one-dimensional theorem. Namely, consider the linear map defined by
that is to say is the digit string base
that has digits
. This map is a linear map from
to a subset of
of density
. Furthermore it has the following “Freiman isomorphism” property: if
lie in
with
in the image set
of
for all
, then there exist (unique) lifts
such that
and
for all . Indeed, the injectivity of
on
uniquely determines the sum
for each
, and one can use base
arithmetic to verify that the alternating sum of these sums on any
-facet of the cube
vanishes, which gives the claim. (In the language of additive combinatorics, the point is that
is a Freiman isomorphism of order (say)
on
.)
Now let be the function defined by setting
whenever
, with
vanishing outside of
. If
obeys (1), then from the above Freiman isomorphism property we have
Applying the one-dimensional inverse theorem (Theorem 1), with reduced by a factor of
and
replaced by
, this implies the existence of a filtered nilmanifold
of degree
and complexity
, a polynomial sequence
, and a Lipschitz function
of Lipschitz constant
such that
which by the Freiman isomorphism property again implies that
But the map is clearly a polynomial map from
to
(the composition of two polynomial maps is polynomial, see e.g. Appendix B of my paper with Ben and Tammy), and the claim follows.
Remark 3 This trick appears to be largely restricted to the case of boundedly generated groups such as
; I do not see any easy way to deduce an inverse theorem for, say,
from the
-inverse theorem by this method.
Remark 4 By combining this argument with the one in the previous post, one can obtain a weak ergodic inverse theorem for
-actions. Interestingly, the Freiman isomorphism argument appears to be difficult to implement directly in the ergodic category; in particular, there does not appear to be an obvious direct way to derive the Host-Kra inverse theorem for
actions (a result first obtained in the PhD thesis of Griesmer) from the counterpart for
actions.
Additive combinatorics is largely focused on the additive properties of finite subsets A of an additive group . This group can be finite or infinite, but there is a very convenient trick, the Ruzsa projection trick, which allows one to reduce the latter case to the former. For instance, consider the set
inside the integers
. The integers of course form an infinite group, but if we are only interested in sums of at most two elements of A at a time, we can embed A ininside the finite cyclic group
without losing any combinatorial information. More precisely, there is a Freiman isomorphism of order 2 between the set
in
and the set
in
. One can view the latter version of
as a model for the former version of
. More generally, it turns out that any finite set A in an additive group can be modeled in the above set by an equivalent set in a finite group, and in fact one can ensure that this ambient modeling group is not much larger than A itself if A has some additive structure; see this paper of Ruzsa (or Lemma 5.26 of my book with Van Vu) for a precise statement. This projection trick has a number of important uses in additive combinatorics, most notably in Ruzsa’s simplified proof of Freiman’s theorem.
Given the interest in non-commutative analogues of Freiman’s theorem, it is natural to ask whether one can similarly model finite sets A in multiplicative (and non-commutative) groups using finite models. Unfortunately (as I learned recently from Akshay Venkatesh, via Ben Green), this turns out to be impossible in general, due to an old example of Higman. More precisely, Higman shows:
Theorem 1. There exists an infinite group G generated by four distinct elements a,b,c,d that obey the relations
; (1)
in fact, a and c generate the free group in G. On the other hand, if G’ is a finite group containing four elements a,b,c,d obeying (1), then a,b,c,d are all trivial.
As a consequence, the finite set in G has no model (in the sense of Freiman isomorphisms) in a finite group.
Theorem 1 is proven by a small amount of elementary group theory and number theory, and it was neat enough that I thought I would reproduce it here.
Recent Comments