QUASIRANDOM GROUPS

W. T. Gowers

Abstract. Babai and Sos have asked whether there exists a constant c > 0 such that every finite group G has a product-free subset of size at least c|G|: that is, a subset X that does not contain three elements x, y and z with xy = z. In this paper we show that the answer is no. Moreover, we give a simple sufficient condition for a group not to have any large product-free subset.

§1. Introduction.

The starting point for this paper is a well-known result of Erdős, which states that for every n-element subset X of ℤ there is a subset Y ⊂ X of size at least n/3 that is sum-free, in the sense that if y_{1} and y_{2} belong to Y then y_{1} + y_{2} does not belong to Y. The proof is so simple that it can be given in full here. First, choose a prime p such that X lives in the interval [−p/3, p/3]. A subset Y ⊂ X is then sum-free if and only if it is sum-free mod p. But if r is any integer not congruent to 0 mod p, then Y is sum-free mod p if and only if rY is sum-free mod p. But a simple averaging argument shows that one can find r such that at least a third of the elements of rX lie in the interval [p/3, 2p/3] mod p. That is, X has a subset Y of size at least n/3 such that rY, and hence Y, is sum-free.

Using the classification of Abelian groups it is easy to see that the same result holds if X is a subset of an Abelian group, but the situation for non-Abelian groups is less clear. In 1985, Babai and Sos [1] noted that if H is a subgroup of G of index k, then any non-trivial coset of H is product-free. From the classification of finite simple groups it can be shown that every finite simple group of order n has a subgroup of index at most Cn^{3/7} and hence a product-free set of size at least cn^{4/7}. Combining that with the fact that a product-free subset of a quotient of G lifts to a product-free subset of G, one can deduce the same result for all finite groups. In 1997, Kedlaya [8] (see also [9]) improved this bound to cn^{11/14} by showing that if H has index k then one can in fact find a union of ck^{1/2} cosets of H that is product free.

In the other direction, nothing much was known. Indeed, Babai and Sos asked whether the lower bound could be improved to cn for some positive constant c, and Kedlaya repeated this question, while also asking the weaker question of whether, for every ϵ > 0, one can obtain a bound of c(ϵ)n^{1−ϵ}. This paper answers these questions in the negative, by showing that, for sufficiently large q, the group PSL_{2}(q) has no product-free subset of size Cn^{8/9}, where n is the order of PSL_{2}(q). In fact, we prove the stronger result that if A, B and C are three subsets of PSL_{2}(q) of size at least Cn^{8/9}, then there is a triple (a, b, c) ∈ A × B × C such that ab = c.

The proof has three stages. First, we briefly review some facts about quasirandom bipartite graphs and quasirandom subsets of groups – detailed proofs of most of these can be found elsewhere, and we give simple proofs of those that cannot. Secondly, we prove that the “bipartite Cayley graph” associated with PSL_{2}(q) and one of the three sets under consideration is quasirandom. Finally, we show that this quasirandomness immediately implies our result.

Having proved this theorem, we step back and look at what we have done from a more abstract point of view. The property of PSL_{2}(q) that makes it suitable for results of this kind is that it has no non-trivial irreducible representations of low dimension. This property has been used in a similar way before: it is an important ingredient in the famous construction of Ramanujan graphs by Lubotzky, Phillips and Sarnak [10] (see also [5]), and it has recently been used by Bourgain and Gamburd [2] to show that certain Cayley graphs are expanders.

Our main result is rather easier than theirs. However, this very fact may make it useful to readers who do not have a background in representation theory and who would like to see how information about representations can be used. If a group has no nontrivial low-dimensional representations, it seems appropriate to call it quasirandom since, as we show later in the paper, this property is equivalent to several other properties, some of which state that certain associated graphs are quasirandom. Once we have stated and proved various equivalences of this kind, we prove some further results. The first of these is a partial converse to our main theorem: if a finite group G contains no large product-free subset, then it is quasirandom. The reason this is a “partial” converse is that the bounds we obtain are not very good: for most of the results in the paper there is a power-type dependence of one constant on another, but for this one it is exponential/logarithmic.

Section 4 ends with another weak equivalence. It is easy to prove that a group is not quasirandom if it has a non-trivial quotient that is either Abelian or of small order. We show that, in the absence of these obvious obstructions, a group G is quasirandom. In particular, non-Abelian finite simple groups are quasirandom. Again, we obtain exponential/logarithmic bounds, but for this result it is unavoidable because the dimension of the smallest non-trivial representation is a power of n for some finite simple groups and logarithmic in n for others.

In Section 5 we prove a generalization of the main theorem to more complicated sets of equations. The theorem itself allows one to place a, b and ab into specified dense subsets of a quasirandom group. It turns out that one can do the same with more variables: for example, the next case says that a, b, c, ab, bc, ac and abc can be placed into specified sets.

The final section of this paper collects together some open problems that have arisen during the paper, and adds a few more.

§2. Quasirandom graphs and sets.

As promised, let us briefly review some of the standard theory of quasirandomness, concentrating in particular on the definitions of a quasirandom graph, a quasirandom bipartite graph and of a quasirandom subset of an Abelian group. The first few results of this section will not be used later, so we shall not give their proofs. However, they put the later results into their proper context.

The notion of a quasirandom graph was introduced by Chung, Graham and Wilson [4], though a similar notion (of so-called “jumbled” graphs) had been defined by Thomason [11]. If x is a vertex in a graph, we shall write N_{x} for its neighbourhood. The adjacency matrix A of a graph G is defined by A(x, y) = 1 if xy is an edge of G and A(x, y) = 0 otherwise.

Theorem 2.1. Let G be a graph with n vertices and density p. Then the following statements are polynomially equivalent, in the sense that if one statement holds for a constant c, then all others hold with constants that are bounded above by a positive power of c.

(i) ∑_{x,y∈V (G)} |N_{x} ∩ N_{y}|^{2} ⩽ (p^{4} + c_{1})n^{4}.

(ii) The number of labelled 4-cycles in G is at most (p^{4} + c_{1})n^{4}.

(iii) For any two subsets A, B ⊂ V (G) the number of pairs (x, y) ∈ A × B such that xy ∈ E(G) differs from p|A||B| by at most c_{2}n^{2}.

(iv) The second largest modulus of an eigenvalue of the adjacency matrix of G is at most c_{3}n.

A graph that satisfies one, and hence all, of these properties for a small c is called quasirandom. If one wishes to be more precise, then one can say that G is c-quasirandom if it satisfies property (i) (or equivalently (ii)) with constant c_{1} = c. A random graph with edge probability p is almost always quasirandom with small c, and quasirandom graphs have many properties that random graphs have. In particular, if H is any fixed small graph, and ϕ is a random map from V (H) to V (G), then the probability that ϕ(x)ϕ(y) is an edge of G whenever xy is an edge of H (in which case ϕ is a homomorphism) is roughly what one would expect, namely p^{|E(H)|}, and the probability that in addition no non-edge of H maps to an edge of G (in which case ϕ is an isomorphic embedding) is roughly p^{|E(H)|}(1 − p)^{\binom{|V (H)|}{2}−|E(H)|}.

A quasirandom bipartite graph is like a quasirandom graph but with some obvious modifications. As above, we state a theorem that serves as a definition as well.

Theorem 2.2. Let G be a bipartite graph with vertex sets X and Y and p|X||Y | edges. Then the following statements are polynomially equivalent.

(i) ∑_{x,x′∈X} |N_{x} ∩ N_{x′}|^{2} ⩽ (p^{4} + c_{1})|X|^{2}|Y |^{2}.

(i) ∑_{y,y′∈Y} |N_{y} ∩ N_{y′}|^{2} ⩽ (p^{4} + c_{1})|X|^{2}|Y |^{2}

(ii) The number of labelled 4-cycles that start in X is at most (p^{4} + c_{1})|X|^{2}|Y |^{2}. (iv) For any two subsets A ⊂ X and B ⊂ Y the number of pairs (x, y) ∈ A × B such

that xy ∈ E(G) differs from p|A||B| by at most c_{2}|X||Y |.

We call a bipartite graph c-quasirandom if it satisfies condition (i) (and therefore the exactly equivalent conditions (ii) and (iii)) with constant c_{1} = c.

Note that we have not given an eigenvalue condition. This is because the bipartite adjacency matrix (that is, the obvious 01-function defined on X×Y as opposed to (X∪Y)^{2}) is not symmetric. However, as we shall see later, there is a natural analogue of this condition.

To continue our quick survey of known results, let us define quasirandom subsets of Abelian groups. This is a straightforward generalization of a definition of Chung and Graham for the case ℤ/pℤ. Again, we present it as a theorem rather than a definition. Recall that if G is an Abelian group, f is a function from G to ℂ and γ : G → ℂ is a character of G, then the Fourier transform of f, evaluated at γ, is the number f̂(γ) = |G|^{−1} ∑_{g∈G} f(g)\overline{γ(g)}. If f_{1} and f_{2} are two functions defined on G, then their convolution f_{1} ∗ f_{2} is defined by f_{1} ∗ f_{2}(g) = ∑_{x+y=g} f_{1}(x)f_{2}(y). If A is a subset of G we shall use the letter A also for the characteristic function of A. That is, A(x) = 1 if x ∈ A and 0 otherwise.

Theorem 2.3. Let G be an Abelian group of order n and let A ⊂ G be a set of size pn. Then the following are equivalent.

(i) ∑_{g∈G} |A ∩ (A + g)|^{2} ⩽ (p^{4} + c_{1})n^{3}.

(ii) There are at most (p^{4} + c_{1})n^{3} solutions in A of the equation x + y = z + w.

(iii) ∑_{g∈G} |A ∗ A(g)|^{2} ⩽ (p^{4} + c_{1})n^{3}.

(iv) For every subset B ⊂ G, ∑_{g∈G} |A ∗ B(g)|^{2} ⩽ n^{−1}|A|^{2}|B|^{2} + c_{2}n^{3}.

(v) The graph with vertex set G and with x joined to y if and only if x + y ∈ A is c_{1}-quasirandom.

(vi) The bipartite graph with two copies of G as its vertex sets and with x joined to y if and only if y − x ∈ A is c_{1}-quasirandom.

(vii) |Â(γ)| ⩽ c_{3}n for all non-trivial characters γ.

It is often convenient to replace Theorems 2.2 and 2.3 with “functional” or “analytic” versions, as follows. Theorem 2.4. Let X and Y be two finite sets and let f : X × Y → ℂ be a function that takes values of modulus at most 1. Then the following properties of f are polynomially equivalent.

(i) ∑_{x,x′∈X} ∑_{y,y′∈Y} f(x, y)\overline{f(x, y′)}\overline{f(x′, y)}f(x′, y′) ⩽ c_{1}|X|^{2}|Y |^{2}.

(ii) For any two functions u : X → ℂ and v : Y → ℂ taking values of modulus at most 1,

|∑_{x,y} f(x, y)u(x)v(y)| ⩽ c_{2}|X||Y |.

(iii) For any two sets A ⊂ X and B ⊂ Y,

|∑_{x∈A} ∑_{y∈B} f(x, y)| ⩽ c_{3}|X||Y |.

A function f with one, and hence all three, of the above properties is called quasirandom. More precisely, we call it c-quasirandom if property (i) holds with constant c.

Theorem 2.4 is closely related to Theorem 2.2. Indeed, if G is a bipartite graph with vertex sets X and Y and density p, then G is quasirandom if and only if the function f(x, y) = G(x, y) − p is quasirandom, where we have written G for the characteristic function of the graph as well (so f(x, y) is 1 − p if (x, y) is an edge and −p otherwise). This is particularly easy to show if G is regular, in the sense that every vertex in X has degree p|Y | and every vertex in Y has degree p|X|. Then a quick calculation shows that G is c-quasirandom if and only if f is c-quasirandom.

Now let us give a functional version of Theorem 2.3. Instead of trying to give as many equivalences as possible, we shall restrict our attention to ones that will be of interest later (in Section 4, when we come to define quasirandom groups). These apply to subsets of an arbitrary group. They are not deep equivalences, as one might suspect from the fact that they all hold with the same constant.

Theorem 2.5. Let G be a group of order n and let f : G → ℂ be a function taking values of modulus at most 1. Then the following are exactly equivalent.

(i) ∑_{x∈G}|∑_{y∈G} f(x)\overline{f(yx)}|^{2} ⩽ cn^{3}. (ii) ∑_{ab^{−1}=cd^{−1}} f(a)\overline{f(b)}\overline{f(c)}f(d) ⩽ cn^{3}. (iii) The function F (x, y) = f(xy^{−1}) is a c-quasirandom function on G × G.

Proof. To see that (i) and (ii) are equivalent, note that the sum on the left-hand side of (i) is equal to

∑_{x,y,z∈G} f(x)\overline{f(yx)}\overline{f(z)}f(yz).

The result now follows from the obvious one-to-one correspondence between quadruples (a, b, c, d) such that ab^{−1} = cd^{−1} and quadruples of the form (x, yx, z, yz).

To see that (ii) and (iii) are equivalent, note that

∑_{x,x′} ∑_{y,y′} F (x, y)\overline{F (x, y′)}\overline{F (x′, y)}F (x′, y′) = ∑_{x,x′} ∑_{y,y′} f(xy^{−1})\overline{f(xy^{′−1})}\overline{f(x′y^{−1})}f(x′y^{′−1}) .

Now for each x, x′, y and y′ we have (xy^{−1})(x′y^{−1})^{−1} = (xy^{′−1})(x′y^{′−1})^{−1}. In the other direction, if ab^{−1} = cd^{−1} and g is any group element, then let y = g, x = ag, y′ = c^{−1}ag and x′ = dc^{−1}ag = bg. Then xy^{−1} = a, x′y^{−1} = b, xy^{′−1} = c and x′y^{′−1} = d. This gives us an n-to-one correspondence between quadruples (xy^{−1}, x′y^{−1}, xy^{′−1}, x′y^{′−1}) and quadruples (a, b, c, d) such that ab^{−1} = cd^{−1}, which proves that (ii) holds if and only if

∑_{x,x′} ∑_{y,y′} F (x, y)\overline{F (x, y′)}\overline{F (x′, y)}F (x′, y′) ⩽ cn^{4},

that is, if and only if (iii) holds. □

For more details about quasirandom graphs, sets and functions, including proofs of most of the previous results, the reader is referred to the early sections of [7]. (This is by no means the only reference, but is chosen because the presentation there harmonizes well with the presentation in this paper.)

Let us now return to the question of a “spectral theory” for bipartite graphs. For an ordinary graph G, one observes that the adjacency matrix is symmetric and can therefore be decomposed as ∑_{i=1}^{n} λ_{i}u_{i} ⊗ u_{i} for some orthonormal basis (u_{i}) of eigenvectors, with λ_{i} the eigenvalue corresponding to u_{i}. (Here we write u ⊗ v for the matrix that takes the value u(x)v(y) at (x, y). If v and w are elements of inner product spaces V and W, then we write w ⊗ v for the linear map from V to W defined by x ↦ ⟨x, v⟩w. Notice that these two definitions are consistent.) For a bipartite graph, the adjacency matrix is no longer symmetric, so this result is no longer true. However, what we can do instead is decompose it as a sum ∑_{i=1}^{n} λ_{i}u_{i} ⊗v_{i}, where (u_{i}) and (v_{i}) are two orthonormal bases. This is called the singular value decomposition of the matrix, which was discovered in the late 19th century and is important in numerical analysis. For the convenience of the reader, we give a proof that it always exists (in the real case).

Theorem 2.6. Let α be any linear map from a real inner product space V to a real inner product space W. Then A has a decomposition of the form ∑_{i=1}^{k} λ_{i}w_{i} ⊗ v_{i}, where the sequences (w_{i}) and (v_{i}) are orthonormal in W and V, respectively, each λ_{i} is non-negative, and k is the smaller of dim V and dim W.

Proof. To begin, let v be a non-zero vector such that ∥αv∥/∥v∥ is maximized. (For this proof, ∥.∥ is the standard Euclidean norm and ⟨, ⟩ the standard inner product, either on ℝ^{m} or ℝ^{n}.) Now suppose that w is any vector orthogonal to v and let δ be a small real number. Then ∥α(v + δw)∥^{2} = ∥αv∥^{2} + 2δ⟨αv, αw⟩ + o(δ), and ∥v + δw∥^{2} = ∥v∥^{2} + o(δ). It follows that ⟨αv, αw⟩ = 0, since otherwise we could pick a small δ with the same sign as ⟨αv, αw⟩ and we would find that ∥α(v + δw)∥/∥v + δw∥ was bigger than ∥αv∥/∥v∥.

Let X and Y be the subspaces of ℝ^{n} and ℝ^{m} orthogonal to v and αv, respectively. They can be given orthonormal bases, and α maps everything in X to Y. Let β be the restriction of α to X. By induction, β has a decomposition of the required form. That is, we can write β = ∑_{i=2}^{k} λ_{i}w_{i} ⊗ v_{i} with v_{i} ∈ X and w_{i} ∈ Y. Now set v_{1} = v/∥v∥, w_{1} = αv/∥αv∥ = αv_{1}/∥αv_{1}∥ and λ_{1} = ∥αv_{1}∥. Then αv_{1} = λ_{1}w_{1}, from which it follows that α = ∑_{i=1}^{k} λ_{i}w_{i} ⊗ v_{i}, as required. □

The claim made just before Theorem 2.6 is the matrix interpretation of the theorem. Next, let us note a simple, but for our purposes very important, fact that follows from the above argument. In the statement, if G is a bipartite graph with vertex sets X and Y of not necessarily the same size, we call it regular if every vertex in X has the same degree and every vertex in Y has the same degree.

Lemma 2.7. Let G be a regular bipartite graph with vertex sets X and Y. Let α be the linear map from ℂ^{X} to ℂ^{Y} derived from the bipartite adjacency matrix of G. (That is, if f : X → ℂ then αf(y) = ∑_{x∈X,xy∈E(G)} f(x).) Then the set of all functions f : X → ℂ such that ∑_{x∈X} f(x) = 0 and ∥αf∥/∥f∥ is maximized forms a linear subspace of ℂ^{X}.

Proof. Let us first check, using the regularity of G, that the maximum of ∥αf∥/∥f∥ over all functions is attained when f is a constant function. Let every vertex in X have degree p|Y |, so that every vertex in Y has degree p|X|. Then, settting G(x, y) to be 1 if xy ∈ E(G) and 0 otherwise,

∥αf∥^{2} = ∑_{y}|∑_{x} f(x)G(x, y)|^{2}

= ∑_{x,x′} f(x)\overline{f(x′)} ∑_{y} G(x, y)G(x′, y)

⩽ \frac{1}{2} ∑_{x,x′}(|f(x)|^{2} + |f(x′)|^{2}) ∑_{y} G(x, y)G(x′, y)

= ∑_{x} |f(x)|^{2} ∑_{x′} ∑_{y} G(x, y)G(x′, y)

= ∑_{x} |f(x)|^{2}p^{2}|X||Y | = p^{2}|X||Y |∥f∥^{2} .

It follows that ∥αf∥/∥f∥ never exceeds p|X|^{1/2}|Y |^{1/2}. This bound is attained when f is the constant function 1: then ∥f∥ = |X|^{1/2}, and ∥αf∥ = p|X||Y |^{1/2} since αf takes the value p|X| everywhere on Y.

The proof of Theorem 2.6 now tells us that the restriction of the linear map α to the space of functions that sum to zero can be decomposed as ∑_{i=2}^{n} λ_{i}w_{i} ⊗ v_{i}. Without loss of generality, λ_{2} ⩾ … ⩾ λ_{n} ⩾ 0. Choose k such that λ_{2} = … = λ_{k} > λ_{k+1} and let X be the subspace of G^{ℂ} generated by v_{2}, …, v_{k}. Then the restriction of α to X is λ_{2} ∑_{i=2}^{k} w_{i} ⊗ v_{i}. This map is orthogonal on to its image, so ∥αf∥ = λ_{2}∥f∥ for every f ∈ X. Since α(∑_{i=2}^{n} μ_{i}v_{i}) = ∑_{i=2}^{n} λ_{i}μ_{i}w_{i}, it is clear that ∥αf∥ < λ_{2}∥f∥ whenever ∑_{x∈G} f(x) = 0 and f ∉ X. □

In the next two results we shall see that the numbers λ_{i} play a very similar role for bipartite graphs that eigenvalues play for graphs.

Lemma 2.8. Let G be a bipartite graph with vertex sets X and Y and identify G with its bipartite adjacency matrix ∑_{i=1}^{k} λ_{i}w_{i} ⊗v_{i}, where (v_{i}) and (w_{i}) are orthonormal sequences. Then ∑_{i} λ_{i}^{2} is the number of edges in G and ∑_{i} λ_{i}^{4} is the number of labelled 4-cycles that start in X.

Proof. The number of edges in G is tr(G^{T} G). But G^{T} is ∑_{i} λ_{i}v_{i} ⊗w_{i}. It is easy to verify that (v_{i} ⊗ w_{i})(w_{j} ⊗ v_{j}) = v_{i} ⊗ v_{j}. But tr(v_{i} ⊗ v_{j}) = 1 if i = j and 0 otherwise, so the first statement of the lemma follows.

The second part is similar. The number of labelled 4-cycles that start in X is tr(G^{T} GG^{T} G). If we expand G and G^{T} then once again the only terms that survive are those that use a single i. But in this case we have four terms, so the answer is ∑_{i} λ_{i}^{4}. □

The next result gives a further condition that is equivalent to quasirandomness for regular bipartite graphs.

Theorem 2.9. Let G be a regular bipartite graph with vertex sets X and Y, p|X||Y | edges and identify G with its bipartite adjacency matrix. Then the following are polynomially equivalent.

(i) G is c_{1}-quasirandom.

(ii) The maximum of ∥Gf∥/∥f∥ over all non-zero functions f such that ∑_{x∈X} f(x) = 0 is at most c_{2}|X|^{1/2}|Y |^{1/2}. Proof. By Theorem 2.6 we can write G = ∑_{i=1}^{k} λ_{i}w_{i} ⊗ v_{i} for orthonormal sequences (v_{i}) and (w_{i}). By Lemma 2.8, the number of labelled 4-cycles in G that start in X is ∑_{i=1}^{k} λ_{i}^{4}. Suppose that the decomposition is chosen so that u_{1} and v_{1} are constant functions, which implies that λ_{1} = p|X|^{1/2}|Y |^{1/2}. Then, if (ii) holds, we find that

∑_{i=1}^{k} λ_{i}^{4} ⩽ p^{4}|X|^{2}|Y |^{2} + c_{2}^{2}|X||Y | ∑_{i=2}^{k} λ_{i}^{2} .

By Lemma 2.8, ∑_{i=2}^{k} λ_{i}^{2} ⩽ p|X||Y |, so this is at most (p^{4} +pc_{2}^{2})|X|^{2}|Y |^{2}, which establishes (i) with c_{1} = pc_{2}^{2}.

Conversely, if (i) holds, then ∑_{i=1}^{k} λ_{i}^{4} ⩽ (p^{4} + c_{1})|X|^{2}|Y |^{2}. Since λ_{1} = p|X|^{1/2}|Y |^{1/2}, it follows that every other λ_{i} is at most c_{1}^{1/4}|X|^{1/2}|Y |^{1/2}. Since the maximum of these other λ_{i} is precisely the maximum in (ii), we have established (ii) with c_{2} = c_{1}^{1/4}. □

§3. A group with no large product-free subset.

In this section we give a quick proof that the density of the largest product-free subset of the group PSL_{2}(q) tends to zero as q tends to infinity. Recall that PSL_{2}(q) is the 2dimensional projective special linear group over 𝔽_{q}, that is, the group of all 2 × 2 matrices over 𝔽_{q} with determinant 1, quotiented by the subgroup consisting of I and −I. It is natural to look at this family of groups, since it is one of the simplest infinite families of finite simple groups; simple groups themselves are natural to look at because if G′ is a quotient of a group G, then any product-free subset of G′ lifts to a product-free subset of G. As we have already mentioned, our proof will depend on one basic fact about representations of PSL_{2}(q), which we state without proof.

Theorem 3.1. Every non-trivial representation of PSL_{2}(q) has dimension at least (q − 1)/2. □

The proof of Theorem 3.1, due to Frobenius, is not especially hard, though it isn’t trivial either. A nice presentation of it can be found in [5]. To put this result in perspective, the order of PSL_{2}(q) is q(q^{2} − 1)/2, so the lowest dimension of a non-trivial representation is proportional to the cube root of the order of the group. This tells us that, in a certain sense, PSL_{2}(q) is very far from being Abelian.

As mentioned in the introduction, we shall in fact prove that, given any three large subsets A, B and C of PSL_{2}(q), there is a triple (a, b, c) ∈ A × B × C such that ab = c. In order to prove this, it will be convenient (though not essential) to express the number of such triples in terms of the following bipartite Cayley graph G. The two vertex sets of G are copies of PSL_{2}(q) and xy is an edge if and only if there exists a ∈ A such that ax = y. (Note that if xy is an edge, it does not follow that yx is an edge – this is why we have to consider bipartite graphs.) Then the number of triples we are trying to count is the number of edges from the copy of B on one side of this bipartite graph to the copy of C on the other. Let Γ =PSL_{2}(q), let n = |Γ| and let r = |A|/n. Then we know from Theorem 2.2 that the number of edges between these copies of B and C will be approximately r|B||C| if G is sufficiently quasirandom.

We shall make this argument precise later in the section. But first, let us prove that the graph G actually is quasirandom.

Lemma 3.2. Let A be any subset of Γ and let G be the bipartite Cayley graph defined above. Let α be the corresponding linear map defined in the statement of Lemma 2.5. Let f : Γ → ℂ be any function such that ∑_{x∈Γ} f(x) = 0. Then ∥αf∥/∥f∥ ⩽ (2|A|n/(q−1))^{1/2}.

Proof. Note first that, for any x and y in Γ, there exists a ∈ A such that ax = y if and only if yx^{−1} ∈ A. Thus, this is another way of stating which pairs xy are edges of G. Writing A for the characteristic function of the set A, we now have

αf(y) = ∑_{x} G(x, y)f(x) = ∑_{x} A(yx^{−1})f(x) = ∑_{uv=y} A(u)f(v) = A ∗ f(y) ,

where the last equality is true by the definition of the convolution of two functions defined on an arbitrary group. That is, αf = A ∗ f.

Let λ be the maximum of ∥αf∥/∥f∥ over all functions f that sum to zero, and let X be the set of all functions f that achieve this maximum. Then X is a linear subspace of ℂ^{Γ}, by Lemma 2.7 (of course, we count 0 as belonging to X). Now if we choose any f ∈ X and any group element g ∈ Γ, then the function T_{g}f, defined by T_{g}f(x) = f(xg), also belongs to X, since

αT_{g}f(u) = ∑_{xy=u} A(x)T_{g}f(y) = ∑_{xy=u} A(x)f(yg) = ∑_{xy=ug} A(x)f(y) = αf(ug) ,

from which it follows that ∥αT_{g}f∥ = ∥αf∥. Obviously, ∥T_{g}f∥ = ∥f∥ as well.

Since any non-zero f in X is non-constant, there exists g ∈ Γ such that T_{g}f ≠ f, from which it follows that the right-regular representation of Γ acts non-trivially on X. Therefore, the dimension of X is at least (q − 1)/2, by Theorem 3.1.

It follows from Theorem 2.6 and Lemma 2.8 that (q − 1)λ^{2}/2 is at most the number of edges in G, which is |A|n. That is, λ ⩽ (2|A|n/(q − 1))^{1/2}, as stated. □

We have shown that G satisfies condition (ii) of Theorem 2.9, with c_{2} = (2|A|/(q − 1)n)^{1/2}, as stated. This may make it look as though G becomes more quasirandom as the cardinality of A decreases, but that is just an accident arising from the way the condition is formulated. The point is that when A is smaller, the graph is less dense, which makes it hard for c_{2} to be small enough for condition (iv) of Theorem 2.2 to say anything non-trivial.

Nevertheless, we have more or less proved the main result of this paper. All that remains is to put together the results we have stated or proved already.

Theorem 3.3. Let Γ =PSL_{2}(q), let n = |Γ| and let A, B and C be three subsets of Γ such that |A||B||C| > 2n^{3}/(q − 1). Then there exist a ∈ A, b ∈ B and c ∈ C with ab = c. In particular, this is true if all of A, B and C have size greater than 2n^{8/9}. Furthermore, if η > 0 and |A||B||C| ⩾ 2n^{3}/η^{2}(q − 1), then the number of triples (a, b, c) ∈ A × B × C such that ab = c is at least (1 − η)|A||B||C|/n.

Proof. Let |A| = rn, |B| = sn and |C| = tn. As in the previous lemma, let α be the linear map f ↦ A ∗ f. Let B stand for the characteristic function of the set B, and for each x ∈ Γ let f(x) = B(x)−s. Then ∑_{x} f(x) = 0, and ∥f∥^{2} = (1−s)^{2}|B|+s^{2}(n−|B|) = s(1 − s)n ⩽ sn.

It follows from Lemma 3.2 that ∥αf∥^{2} ⩽ 2rn^{2}sn/(q−1). But A∗B(y) = A∗(f+s)(y) = αf(y) + rsn, so whenever A ∗ B(y) = 0 we have |αf(y)| = rsn. It follows that the number m of y for which A ∗ B(y) = 0 satisfies the inequality m(rsn)^{2} ⩽ 2rsn^{3}/(q − 1), or m ⩽ 2n/rs(q − 1). But if rst > 2/(q − 1), then this is less than tn, which implies that there exists c ∈ C such that A ∗ B(c) ≠ 0. Equivalently, there exist a ∈ A and b ∈ B such that ab = c, as claimed. The next statement follows from the fact that q − 1 ⩾ n^{1/3}.

As for the final claim, the number of triples in question is ⟨A ∗ B, C⟩ = ⟨αf, C⟩ + rsn|C|. But |⟨αf, C⟩|^{2} ⩽ 2rn^{2}sn|C|/(q −1) = 2|A||B||C|n/(q −1), by the Cauchy-Schwarz inequality and the estimate for ∥αf∥ obtained earlier, while rsn|C| = |A||B||C|/n. The result is therefore true provided

2|A||B||C|n/(q − 1) ⩽ η^{2}|A|^{2}|B|^{2}|C|^{2}/n^{2} ,

and this inequality follows from our assumption. □

§4. Quasirandom groups.

The property that made PSL_{2}(q) a good group for not containing a large product-free set was that every large subset gives rise to a directed Cayley graph that is quasirandom. We deduced this property from the fact that PSL_{2}(q) has no non-trivial low-dimensional representations. Now we shall show that these two properties, as well as several others, are in fact equivalent. We shall use the word “quasirandom” for any group that has one, and hence all, of these properties, but there is a limit to how seriously this word should be taken. In particular, we do not have a model of random groups for which we can show that almost every group is quasirandom. (Gromov has, famously, defined a notion of random group, by taking a set of n generators and a certain number of random relations of prescribed length. However, his groups are infinite: to define a random finite group one would need enough relations to make it finite, but not enough to make it trivial, or very small. This could be a delicate matter.)

A second difference between this notion of quasirandomness and the usual ones for graphs and subsets of groups is that we do not have a “local” characterization, where we count small configurations of a certain kind. (For graphs and subsets of groups these configurations are 4-cycles and quadruples ab^{−1} = cd^{−1}, respectively.) Indeed, it seems quite likely that no such characterization exists, and to see why, consider the case of the group S_{n}. This is not quasirandom, since A_{n} is a subgroup of index 2, but if you choose a small number of permutations π_{1}, …, π_{k} at random (here k should be thought of as an absolute constant), then they will not have any small relations, so one will not have any “local” evidence that they are not all even permutations. That is, S_{n} appears to be “locally indistinguishable” from A_{n}, which is quasirandom.

This may not be the end of the story, however, because there is a sense in which the non-quasirandomness of S_{n} is at least “polynomially detectable.” Suppose that you are given the multiplication table of S_{n}, but you are given it abstractly and not told the order in which the permutations appear. Now suppose that you want an algorithm that will partition the elements into even and odd permutations in polynomial time (in n!). You can do it with a randomized algorithm as follows. Choose k elements at random from the group. Then the probability that they all happen to be even permutations is 2^{−k}, and it is known that if they are all even then they almost surely generate A_{n}, while if they are not all even then they almost surely generate S_{n}. The time it takes to find the subgroup they generate is easily seen to be polynomial, so after a few attempts one will almost certainly generate A_{n} (and we will know that we have done so, since A_{n} is the only subgroup of S_{n} of index 2).

Now let us begin the process of proving the main result of the section, the statement that various properties of groups are equivalent. Before we get to the statement itself, we shall need some mostly standard lemmas.

Lemma 4.1. Let S be the unit sphere in ℂ^{n} in the standard Euclidean norm, and let μ be the standard rotation-invariant probability measure on S. Then ∫ ∫ |⟨v, w⟩|^{2}dμ(v)dμ(w) = n^{−1}.

Proof. The integral in question is the mean square of the inner product of two random unit vectors. This average is clearly unaffected if we fix one of the vectors. But if (e_{i})_{i=1}^{n} is an orthonormal basis of ℂ^{n}, then ∫_{S} ∑_{i=1}^{n} |⟨v, e_{i}⟩|^{2}dμ(v) = ∫_{S} 1dμ(v) = 1, so by symmetry ∫_{S} |⟨v, e_{1}⟩|^{2}dμ(v) = n^{−1}. This proves the lemma. □

Lemma 4.2. Let α be a linear map from ℂ^{n} to ℂ^{n}. Then tr(α) = n ∫_{S}⟨αv, v⟩dμ.

Proof. Let (e_{i})_{i=1}^{n} be an orthonormal basis. Then the trace of the matrix of α with respect to this basis, and hence of α itself, is ∑_{i=1}^{n}⟨αe_{i}, e_{i}⟩. Since this is true for any orthonormal basis, we may average over all of them. The result follows immediately. □

Lemma 4.3. Let v_{1} and v_{2} be two vectors in ℂ^{n}. Then ⟨v_{1}, v_{2}⟩ = n ∫_{S}⟨v_{1}, w⟩⟨w, v_{2}⟩dμ(w).

Proof. The proof is basically the same as that of Lemma 4.2, since for any orthonormal basis ⟨v_{1}, v_{2}⟩ = ∑_{i=1}^{n}⟨v_{1}, e_{i}⟩⟨e_{i}, v_{2}⟩, and once again we can average over all of them. □

Lemma 4.4. Let v_{1}, …, v_{n} be unit vectors in ℂ^{m}. Then ∑_{i,j} |⟨v_{i}, v_{j}⟩|^{2} ⩾ m^{−1}n^{2}.

Proof. The trick here is to notice that |⟨v_{i}, v_{j}⟩|^{2} = ⟨v_{i} ⊗ \overline{v_{i}}, v_{j} ⊗ \overline{v_{j}}⟩, where v_{i} ⊗ \overline{v_{i}} is the m × m matrix with entries v_{i}(p)\overline{v_{i}(q)}, and the inner product is the standard inner product on ℂ^{m^{2}}. It follows that

∑_{i,j} |⟨v_{i}, v_{j}⟩|^{2} = ∥∑_{i=1}^{n} v_{i} ⊗ \overline{v_{i}}∥^{2} .

Now tr(v_{i} ⊗ \overline{v_{i}}) = 1 for each i, so the trace of ∑_{i=1}^{n} v_{i} ⊗ \overline{v_{i}} is n, from which it follows that the right hand side is at least m^{−1}n^{2}, which proves the lemma. □

Note that Lemma 4.4 is sharp. Basically any sufficiently symmetric example shows this, but one simple one is when m|n and the vectors v_{i} consist of n/m copies of some orthonormal basis. Lemma 4.1 proves that the result is sharp for a “continuous set” of vectors. Given a set for which the lemma is sharp, the proof above shows that ∑_{i=1}^{n} v_{i} ⊗\overline{v_{i}} is n/m times the identity matrix. That is, the vectors v_{i} give us a representation of the identity, which is a well-known way of saying that they are nicely distributed round the unit sphere.

With these lemmas in place, we are ready for our main result of the section.

Theorem 4.5. Let G be a finite group. Then the following are polynomially equivalent.

(i) For every subset A ⊂ G, the directed Cayley graph with generators in A is c_{1}- quasirandom.

(ii) For every subset A ⊂ G and every function f : G → ℂ that sums to 0, ∥A ∗ f∥ ⩽ c_{2}n^{1/2}|A|^{1/2}.

(iii) Every function f from G to the closed unit disc in ℂ such that ∑_{g} f(g) = 0 is c_{3}-quasirandom.

(iv) For every function f from G to the closed unit disc in ℂ such that ∑_{g} f(g) = 0, the function F (x, y) = f(xy^{−1}) is c_{3}-quasirandom on G × G.

(v) Every non-trivial representation of G has dimension at least c_{4}^{−1}.

Proof. The proof that (v) implies (i) and (ii) is essentially contained in the argument of the previous section. Indeed, suppose that the smallest dimension of a non-trivial representation is k, and let A ⊂ G. Let Γ be the directed Cayley graph of A and let X be the space of all functions f such that ∑ f(x) = 0 and ∥A ∗ f∥/∥f∥ is maximized (together with the zero function). Let λ be the maximum value of this ratio. Then X is invariant under the right-regular representation of G, so by hypothesis it has dimension at least k.

Lemma 2.8 implies that kλ^{2} ⩽ |A|n, so λ ⩽ (n|A|/k)^{1/2}. This means that if (v) holds then (ii) holds with c_{2} = c_{4}^{1/2}.

From this and Lemma 2.8 it follows that the number of appropriately directed 4-cycles in G is at most |A|^{4} + n^{2}|A|^{2}/k. In particular, whatever the cardinality of A, the graph is at least k^{−1}-quasirandom.

We proved that (iii) and (iv) were equivalent in Theorem 2.5.

Now let us prove that (iii) implies (v). That is, given a non-trivial representation of dimension m, let us construct from it a function f that fails to be c-quasirandom for some c that depends polynomially on m. This we do by an averaging argument, which will exploit the lemmas we have just proved. To simplify the notation, we shall write the average of a function f defined on the sphere S as 𝔼_{v}f(v) instead of ∫_{S} f(v)dμ(v).

A standard and easy lemma of representation theory tells us that if G has a representation ρ then there is an inner product on the vector space V on which G acts such that the representation is unitary. Therefore, we may assume that ρ already has this property. Also, it will be convenient to assume, as we obviously can, that ρ is irreducible. To simplify the notation yet further, if v ∈ V and g ∈ G we shall write gv instead of ρ(g)(v).

Given any two vectors v and w in the unit sphere S of V, let f_{v,w} : G → ℂ be defined by f_{v,w}(g) = ⟨gv, w⟩. Notice that |f_{v,w}(g)| ⩽ 1 for every g. Furthermore, for any g′ we have

∑_{g} gv = ∑_{g} g′gv = g′(∑_{g} gv) .

Since ρ is irreducible, it follows that ∑_{g} gv = 0 (or it would generate a 1-dimensional invariant subspace of V and ρ would not be irreducible). Therefore, ∑_{g} f_{v,w}(g) = ∑_{g}⟨gv, w⟩ = 0. Our averaging argument will show that at least one of these functions f_{v,w} fails to have the property in (iii), if c_{4} < m^{−3}.

By Lemma 4.3 (for the second equality),

𝔼_{w}𝔼_{g}f_{v,w}(g)\overline{f_{v,w}(gh)} = 𝔼_{g}𝔼_{w}⟨gv, w⟩⟨w, ghv⟩ = m^{−1}𝔼_{g}⟨gv, ghv⟩ = m^{−1}⟨v, hv⟩ .

Therefore, by Lemma 4.2,

𝔼_{v}𝔼_{w}𝔼_{g}f_{v,w}(g)\overline{f_{v,w}(gh)} = m^{−2} \overline{tr h} .

Therefore, by the Cauchy-Schwarz inequality,

𝔼_{v}𝔼_{w}|𝔼_{g}f_{v,w}(g)\overline{f_{v,w}(gh)}|^{2} ⩾ m^{−4}| tr h|^{2} .

From this it follows that

𝔼_{v}𝔼_{w}𝔼_{h}|𝔼_{g}f_{v,w}(g)\overline{f_{v,w}(gh)}|^{2} ⩾ m^{−4}𝔼_{h}| tr h|^{2} ,

and hence that there exist v and w such that

𝔼_{h}|𝔼_{g}f_{v,w}(g)\overline{f_{v,w}(gh)}|^{2} ⩾ m^{−4}𝔼_{h}| tr h|^{2} .

We now have the task of bounding 𝔼_{h}| tr h|^{2} from below. But 𝔼_{h}| tr h|^{2} = 𝔼_{g}𝔼_{h}| tr(gh^{−1})|^{2} = 𝔼_{g}𝔼_{h}|⟨A_{g}, A_{h}⟩|^{2}, where A_{g} and A_{h} are the unitary matrices corresponding to g and h and the inner product comes from considering A_{g} and A_{h} as vectors in ℂ^{m^{2}} and taking the standard inner product there. Since these vectors have norm \sqrt{m}, Lemma 4.4 implies that 𝔼_{g}𝔼_{h}|⟨A_{g}, A_{h}⟩|^{2} ⩾ m. Putting all this together, we find that

𝔼_{h}|𝔼_{g}f_{v,w}(g)\overline{f_{v,w}(gh)}|^{2} ⩾ m^{−3} ,

completing the proof that (iii) implies (v).

All that remains to prove the theorem is to show that (i) implies (iii). That is, given a non-quasirandom function defined on G, we would like to construct from it a 01-valued function that gives rise to a Cayley graph that is also not quasirandom. Since this argument is standard, we shall be slightly sketchy about it.

It can be shown that the formula

∥F ∥ = (∑_{x,x′}|∑_{y} F (x, y)\overline{F (x′, y)}|^{2})^{1/4}

defines a norm ∥.∥ on the space of functions F : G × G → ℂ. (This is a fairly easy lemma: a proof can be found in [7].) It follows from the triangle inequality that if F fails to be c-quasirandom, then either Ref or Imf fails to be (c/16)-quasirandom. Therefore, if f is a function for which (ii) fails, then there must exist a function u with values in [−1, 1] and average 0 such that

∑_{g}(∑_{h} u(h)u(gh))^{2} ⩾ c_{3}|G|^{3}/16 .

Now let v(g) = (1 + u(g))/2 for every g ∈ G. Then a standard argument shows that

∑_{g}(∑_{h} v(h)v(gh))^{2} ⩾ |G|^{3}/16 + c_{3}|G|^{3}/256 = (1 + c_{3}/16)|G|^{3}/16 .

(The argument is to expand the left-hand side into a sum of sixteen terms and observe that

∑_{g,g′}(∑_{h} v(h)v(gh))^{2} − \frac{|G|^{3}}{16} − \frac{1}{16} ∑_{g,g′}(∑_{h} u(h)u(gh))^{2}

is a sum of squares.)

Now choose a subset A ⊂ G randomly, putting g into A with probability v(g), making all choices independently. Writing A also for the characteristic function of the set A, we wish to estimate the sum

∑_{g}(∑_{h} A(h)A(gh))^{2} = ∑_{g} ∑_{h,h′} A(h)A(gh)A(h′)A(gh′) .

The number of choices of (g, h, h′) for which the elements h, gh, h′ and gh′ are not all distinct is O(|G|^{2}), and for all other choices the expected value of A(h)A(gh)A(h′)A(gh′) is v(h)v(gh)v(h′)v(gh′). Therefore, the expected value of the sum is at least (1 + c_{3}/20)|G|^{3}/16 when |G| is sufficiently large. Also, with very high probability A has cardinality at most (1+c_{3}/1000)|G|/2 (again, if |G| is sufficiently large). It follows that there exists a set A such that the directed Cayley graph defined by A is not c_{3}/32-quasirandom. □

We end this section with two further characterizations of quasirandom groups. The first one states that the quasirandom groups are precisely those that do not contain a large product-free set. In one direction this is a very simple adaptation of Theorem 3.3 to a more general context. (This is an exercise, but the details can be found in the next section, in Lemma 5.1 and the remarks immediately following it.) So we shall concentrate on the other direction. As commented in the introduction, this final equivalence is not a polynomial one: we shall show that if the largest product-free subset of G has size δ|G|, then G has no non-trivial representation of dimension less than C log(1/δ) for some absolute constant C.

Theorem 4.6. Let G be a group of order n and suppose that G has a non-trivial representation of dimension k. Then G has a product-free subset of size at least c^{k}n, where c > 0 is an absolute constant.

Proof. Let ϕ : G → ℂ^{k} be a unitary representation of G. Without loss of generality ϕ is irreducible, since otherwise we can find a representation with a smaller k. Also, without loss of generality it is faithful, since otherwise we can replace G by G/ ker ϕ. Therefore, without loss of generality the elements of G are themselves unitary transformations of ℂ^{k}.

Now for any vector v ∈ ℂ^{k} we have ∑_{α∈G} αv = 0, since it is invariant under left multiplication by any β ∈ G and the representation is irreducible. It follows from Lemma 4.2 that the average trace of an element of G is 0. Since the trace of a unitary operator has modulus at most k, it follows that the number of elements α ∈ G such that tr α has real part greater than k/2 is at most 2n/3. That is, at least n/3 elements of G have trace with real part less than or equal to k/2.

Now the trace is the sum of the eigenvalues, so if tr α has real part at most k/2, there must be an eigenvalue ω with real part at most 1/2.

Let X be the set of all α ∈ G such that tr α ⩽ k/2 and for each α ∈ X let v(α) be a unit eigenvector with eigenvalue ω(α) that has real part less than 1/2.

Now let δ > 0 be an absolute constant to be chosen later. By a standard volume argument the unit sphere of ℂ^{k} has a δ-net of cardinality at most (3/δ)^{2k}, so we can choose at least (δ/3)^{2k}|X| elements α of X such that all the vectors v(α) lie within δ of some point and hence within 2δ of each other. Therefore, we can choose at least (δ/4)^{2k}n elements α of X such that all the v(α) are within 2δ of each other and all the ω(α) are within δ of each other as well. Let Y be a subset of X with this property.

We would now like to show that, for any α and α′ in Y, the vectors αv(α) and α′v(α) are close. This we deduce from the following equalities and inequalities, which all follow from the properties of Y and the fact that the elements of G preserve distance: αv(α) = ω(α)v(α); ∥ω(α)v(α) − ω(α′)v(α)∥ ⩽ δ; ∥ω(α′)v(α) − ω(α′)v(α′)∥ ⩽ 2δ; ω(α′)v(α′) = α′v(α′); ∥α′v(α′)−α′v(α)∥ ⩽ 2δ. Therefore, by the triangle inequality, ∥αv(α)−α′v(α)∥ ⩽ 5δ.

Now let α′′ be another element of Y. Then ∥αv(α) − α′′v(α)∥ ⩽ 5δ as well. Also, from the previous inequality and the fact that α is unitary, we can deduce that ∥α^{2}v(α) − αα′v(α)∥ ⩽ 5δ. Therefore, if αα′ = α′′ it follows that ∥α^{2}v(α) − αv(α)∥ ⩽ 10δ, and hence that ∥αv(α) − v(α)∥ ⩽ 10δ, and finally that |ω(α) − 1| ⩽ 10δ. But we know that ω(α) is a complex number with modulus 1 and real part at most 1/2, from which it follows that |ω(α) − 1| ⩾ 1. Therefore, Y is product free as long as we choose δ to be less than 1/10. Therefore, we can find a product-free subset Y of G of size at least c^{k}n with c a positive absolute constant (in fact, 1/2000 will do), which proves the theorem. □

Our final characterization of quasirandom groups states that a group G is quasirandom if and only if every quotient of G is large and non-Abelian. We start with a natural special case of this, showing that all non-cyclic finite simple groups are quasirandom. One could presumably prove this result with a better bound than we obtain by using the classification of finite simple groups and simply looking up the dimensions of their irreducible representations. However, our proof is elementary. (Even this elementary argument may well be known, but we have had trouble finding it in the literature.) Theorem 4.7. Let G be a non-cyclic finite simple group of order n. Then every non-trivial representation of G has dimension at least \sqrt{log n}/2. Proof. Let ϕ : G → U(k) be an irreducible unitary representation of G. Since G is simple, ϕ has trivial kernel, so without loss of generality G itself is a finite subgroup of U(k).

Let α be any element of G other than the identity. We claim first that α has a conjugate that does not commute with α. To see this, suppose that all conjugates do commute with α. Then for any β and γ in G we have

(βαβ^{−1})(γαγ^{−1}) = γ(γ^{−1}βαβ^{−1}γ)αγ^{−1} = γα(γ^{−1}βαβ^{−1}γ)γ^{−1} = (γαγ^{−1})(βαβ^{−1}) .

That is, all conjugates of α commute with each other. But the subgroup of G generated by conjugates of α is easily seen to be normal, and therefore all of G, which implies that G is Abelian. But in that case the only irreducible representations of G are 1-dimensional, which implies that k = 1 and G is cyclic, contradicting our hypothesis.

Suppose now that α is the closest element of G, in the operator norm on B(ℂ^{k}), to the identity (apart of course from the identity itself), and let ∥α − ι∥ = ϵ. Let β be a conjugate of α that does not commute with α. Then ∥β − ι∥ = ϵ as well, since G consists of unitary transformations. Write α = ι + γ and β = ι + η. Then αβ − βα = γη − ηγ. Therefore, since α^{−1}β^{−1} is unitary, ∥ι − αβα^{−1}β^{−1}∥ = ∥γη − ηγ∥. Since α and β do not commute, and are closest elements to the identity, it follows that ∥γη − ηγ∥ ⩾ ϵ. But we also know that ∥γη − ηγ∥ ⩽ 2∥γ∥∥η∥ = 2ϵ^{2}. Therefore, ϵ ⩾ 1/2, which implies that no two elements of G are closer than 1/2 in the operator norm.

It remains to determine an upper bound for the size of a 1/2-separated subset of U(k). But U(k) is contained in the unit ball of B(ℂ^{k}). The volume argument mentioned in the previous lemma shows that for any d-dimensional real normed space and any ϵ > 0 the largest ϵ-separated subset of the unit ball has size at most (1 + 2/ϵ)^{d}. The normed space B(ℂ^{k}) is a k^{2}-dimensional complex space, so, setting d = 2k^{2} and ϵ = 1/2, we deduce that a 1/2-separated subset of U(k) has cardinality at most 25^{k^{2}}. That is, n ⩽ 25^{k^{2}}, from which the theorem follows. □

Note that the alternating groups A_{n} have representations of dimension n − 1 (since they act on the subspace of ℂ^{n} consisting of vectors whose coordinates add up to 0). Therefore, the bound in Theorem 4.7 cannot be improved to more than log n/ log log n.

Theorem 4.8. Let G be a group of order n and suppose that for every proper normal subgroup H of G, the quotient G/H is non-Abelian and has order at least m. Then G has no non-trivial representation of dimension less than \sqrt{log m}/2. Conversely, if G has an Abelian quotient, then G has a 1-dimensional representation, and if G has a quotient of order m, then G has a representation of dimension \sqrt{m}.

Proof. Let us quickly deal with the converse, since this is easy and not the main point of interest. Any representation of a quotient of G can be composed with the quotient map so that it becomes a representation of G of the same dimension. Therefore, the result follows from two standard facts of representation theory: that the irreducible representations of Abelian groups are 1-dimensional (and exist!), and that every group of order m has a representation of dimension at most \sqrt{m}. (This second fact follows from the result that the sum of the squares of the dimensions of the irreducible representations is m.)

Now let us turn to the more interesting direction of the theorem. Let H be a maximal proper normal subgroup of G. Then the quotient group G/H is simple and, by our hypothesis, non-Abelian. Let ϕ : G → U(k) be a unitary representation of G. If we knew that the kernel of ϕ was H, then we would have a representation of G/H to which we could apply Theorem 4.7. However, this does not have to be the case, so instead we must imitate the proof of Theorem 4.7, as follows.

We may clearly assume that ϕ is a faithful representation (or else we look at the quotient of G by its kernel). Therefore, we shall think of the elements of G itself as unitary maps on ℂ^{k}. Let us now define a metric on G/H by taking d(αH, βH) to be the smallest distance (in the operator norm again) between any element of αH and any element of βH. Let α be an element of G \ H such that the distance from αH to H, with respect to this metric, is minimized, and note that this distance is just the smallest distance in the operator norm from any element of αH to the identity. Without loss of generality, α itself is an element of αH for which this minimum is attained.

Now G/H is simple and non-Abelian. Hence, by the argument of the last section, we can find a conjugate βH of αH in G/H that does not commute with αH. It is easy to see that we can choose the representative β to be a conjugate of α in G, so let us do this. Then β is a conjugate of α such that not only do α and β not commute, but they do not even belong to the same coset of H. Moreover, the distance from β to the identity is the same as the distance from α to the identity. As in the proof of Theorem 4.8, let ϵ be this distance, and let α = ι + γ and β = ι + η.

Once again, the distance between αβ and βα is ∥γη − ηγ∥, and therefore so is the distance between ι and αβα^{−1}β^{−1}. Since αβα^{−1}β^{−1} does not belong to H, it follows from our minimality assumption that ∥γη − ηγ∥ ⩾ ϵ, as before, and it is also at most 2ϵ^{2} for precisely the same reason as before. Therefore, no two elements of different cosets of H can be within 1/2 of each other in the operator norm, so, by the upper bound given in the proof of Theorem 4.7 for the size of a 1/2-separated subset of U(k), there can be at most 25^{k^{2}} cosets of H. This proves the theorem. □

A good example to bear in mind in connection with Theorem 4.8 and its proof is the following family of groups. Let p and k be positive integers and let G(p, k) be the subgroup of U(k) generated by all diagonal matrices with pth roots of unity as their diagonal entries, and all permutation matrices corresponding to even permutations. Thus, a typical element of G(p, k) is a permutation matrix of determinant 1 with its 1s replaced by arbitrary pth roots of unity. The subgroup H(p, k) generated by just the diagonal matrices in G(p, k) is normal, and the quotient is isomorphic to the alternating group A_{k}. Therefore, these groups are quasirandom as k tends to infinity, despite being of arbitrarily high order for any fixed k. The reason this can happen is that, as the proof of Theorem 4.8 shows is necessary, the cosets of H(p, k) are well-separated.

In practice, Theorems 4.6 and 4.8 are not particularly useful characterizations of quasirandomness because the equivalences are not polynomial equivalences. In other words, they are fine if all one wants is qualitative statements (such as that no subset of positive density is product free) but too crude if one is interested in bounds of the kind obtained in this paper. However, sometimes a qualitative statement is interesting – for example, if one is wondering whether a particular family of groups is quasirandom and wants to make a preliminary check. For instance, Theorem 4.8 tells us that SL_{2}(p) is quasirandom, since {ι, −ι} is a maximal normal subgroup of very high index. However, this particular group is much more quasirandom than Theorem 4.8 guarantees.

§5. Solving equations in quasirandom groups.

The purpose of this section is to prove a double generalization of Theorem 3.3. One direction of generalization is that the result applies to all quasirandom groups, but this is easy since the argument of Theorem 3.3 carries over word for word if one interprets (q − 1)/2 to be the smallest dimension of a non-trivial representation of the group one is talking about. The other direction is more interesting: instead of finding a and b such that a, b and ab each lie in specified sets, we shall find a_{1}, …, a_{m} such that for every non-empty subset F ⊂ {1, 2, …, m} the product of those a_{i} with i ∈ F lies in a specified set. In other words, perhaps surprisingly, we can choose m elements of the group in such a way that exponentially many conditions are satisfied simultaneously, using only the fact that a reasonable number of elements satisfy each condition individually.

Underlying the argument is the following basic lemma, which is implicit in the proof of Theorem 3.3. The proof of the main theorem of this section will use this lemma to drive an inductive argument.

Lemma 5.1. Let G be a group of order n such that no non-trivial representation has dimension less than k. Let A and B be two subsets of G with densities rn and sn, respectively and let δ and t be two positive constants. Then, provided that rst ⩾ (δ^{2}k)^{−1}, the number of group elements x ∈ G for which |A ∩ xB| ⩽ (1 − δ)rsn is at most tn.

Proof. Let C be the set {x^{−1} : x ∈ B}. Then

|A ∩ xB| = ∑_{y} A(y)(xB)(y) = ∑_{y} A(y)B(x^{−1}y) = ∑_{y} A(y)C(y^{−1}x) = A ∗ C(x) .

By Theorem 4.5, if f : G → ℝ sums to zero, then ∥A ∗ f∥ ⩽ (r/k)^{1/2}n∥f∥. Applying this result in the case f(x) = C(x) − s and noting that ∥f∥^{2} = s(1 − s)n ⩽ sn, we deduce that ∥A ∗ C − rsn∥^{2} ⩽ rsn^{3}/k. It follows that the number of x such that A ∗ C(x) ⩽ (1 − δ)rsn is at most n/δ^{2}rsk. If rst ⩾ (δ^{2}k)^{−1}, then this is at most tn, as required. □

Note the following easy consequence of Lemma 5.1, which shows that it is indeed effectively the same as most of the proof of Theorem 3.3. Suppose that rst > 1/k and that C is a subset of G with density t. Lemma 5.1 with δ = 1 tells us that the number of y such that A ∩ y^{−1}B = ∅ is less than tn, from which it follows that there exists y ∈ C such that A ∩ y^{−1}B ≠ ∅. But then, if x ∈ A ∩ y^{−1}B, we have x ∈ A, y ∈ C and yx ∈ B.

In order to make the proof of our general theorem more transparent, we begin with the special case m = 3.

Theorem 5.2. Let G be a group of order n such that no non-trivial representation has dimension less than k. Let A_{1}, A_{2}, A_{3}, A_{12}, A_{13}, A_{23} and A_{123} be subsets of G of densities p_{1}, p_{2}, p_{3}, p_{12}, p_{13}, p_{23} and p_{123}, respectively. Then, provided that p_{1}p_{2}p_{12}, p_{1}p_{3}p_{13}, p_{1}p_{23}p_{123} and p_{2}p_{3}p_{23}p_{12}p_{13}p_{123} are all at least 16/k, there exist elements x_{1} ∈ A_{1}, x_{2} ∈ A_{2} and x_{3} ∈ A_{3} such that x_{1}x_{2} ∈ A_{12}, x_{1}x_{3} ∈ A_{13}, x_{2}x_{3} ∈ A_{23} and x_{1}x_{2}x_{3} ∈ A_{123}.

Proof. We start by choosing x_{1}, noting that there are certain conditions it will have to satisfy if there is to be any hope of continuing the proof. For example, later we shall need to choose x_{2} ∈ A_{2} such that x_{1}x_{2} ∈ A_{12}. Equivalently, we shall need x_{2} to belong to A_{2} ∩ x_{1}^{−1}A_{12}. Similarly, we shall need x_{3} ∈ A_{3} ∩ x_{2}^{−1}A_{13} and x_{2}x_{3} ∈ A_{23} ∩ x_{1}^{−1}A_{123}. Therefore, we want these sets to be not just non-empty, but reasonably large.

By Lemma 5.1, the number of x_{1} such that |A_{2}∩x_{1}^{−1}A_{12}| < p_{2}p_{12}n/2 is at most p_{1}n/4, provided that p_{1}p_{2}p_{12} ⩾ 16/k. Similarly, if p_{1}p_{3}p_{13} ⩾ 16/k and p_{1}p_{23}p_{123} ⩾ 16/k, then the number of x_{1} such that |A_{3} ∩ x_{1}^{−1}A_{13}| < p_{3}p_{13}n/2 is at most p_{1}n/4 and the number of x_{1} such that |A_{23} ∩ x_{1}^{−1}A_{123}| < p_{23}p_{123}n/2 is at most p_{1}n/4. Therefore, provided these inequalities hold, we can choose x_{1} ∈ A_{1} such that, setting B_{2} = A_{2} ∩ A_{12}, B_{3} = A_{3} ∩ A_{13} and B_{23} = A_{23}∩A_{123}, q_{2} = p_{2}p_{12}/2, q_{3} = p_{3}p_{13}/2 and q_{23} = p_{23}p_{123}/2, we have |B_{2}| ⩾ q_{2}n, |B_{3}| ⩾ q_{3}n and |B_{23}| ⩾ q_{23}n.

At this point we could quote our results about product-free sets, but instead let us repeat the argument (which is more or less an equivalent thing to do). We would like to choose x_{2} ∈ B_{2} such that B_{3}∩x_{2}^{−1}B_{23} is non-empty. Lemma 5.1 implies that the number of x_{2} such that B_{3}∩x_{2}^{−1}B_{3} is empty is at most q_{2}n/2, provided that q_{2}q_{3}q_{23} ⩾ 2/k. Therefore, provided we have this inequality, which, when expanded, says that p_{2}p_{3}p_{23}p_{12}p_{13}p_{123} ⩾ 16/k, there exist x_{2} ∈ B_{2} and x_{3} ∈ B_{3} such that x_{2}x_{3} ∈ B_{23}. But then x_{1}, x_{2} and x_{3} satisfy the conclusion of the theorem. □

It is clear that the above argument can be generalized. The only thing that is not quite obvious is the density conditions that emerge from the resulting inductive argument. Here is what they are. Suppose that for every subset F ⊂ {1, 2, …, m} we have a subset A_{F} of a group G with density p_{F} and suppose that no non-trivial representation of G has dimension less than k. Now let h be an integer less than m and let E be a subset of {h + 1, …, m}. Let A_{h,E} be the collection of all sets of the form U ∪ V, where max U < h and V is either {h}, E or {h} ∪ E. We shall say that the sets A_{F} satisfy the (h, E)-density condition if ∏_{F ∈A_{h,E}} p_{F} is at least 2^{3m}/k. We shall say that they satisfy the density condition if they satisfy the E-density condition for every h < m and every non-empty set E ⊂ {h + 1, …, m}.

To get an idea of what this means, notice that the inequalities we assumed in Theorem 5.2 are the (1, {2})-condition, the (1, {3})-condition, the (1, {2, 3})-condition and the (2, {3})-condition, respectively, except that there we had a slightly better dependence on m.

Theorem 5.3. Let G be a group of order n such that no non-trivial representation has dimension less than k. For each non-empty subset F ⊂ {1, 2, …, m} let A_{F} be a subset of G of density p_{F}, and suppose that this collection of sets satisfies the density condition. Then there exist elements x_{1}, …, x_{m} of G such that x_{F} ∈ A_{F} for every F, where x_{F} stands for the product of all x_{i} such that i ∈ F, written with the indices in increasing order. Proof. By the density condition, for every non-empty subset F ⊂ {2, …, m} we have the inequality 2^{−m}p_{1}p_{F} p_{1F} ⩾ 2^{2m}/k. (Here we use the shorthand 1F to stand for {1} ∪ F.) Therefore, by Lemma 5.1, for each F the number of x_{1} such that |A_{F} ∩ x^{−1}A_{1F} | ⩽ p_{F} p_{1F} (1−2^{−m}) is at most p_{1}n/2^{m}. Therefore, the number of x_{1} such that |A_{F} ∩x_{1}^{−1}A_{1F} | ⩽ p_{F} p_{1F} (1 − 2^{−m}) for at least one non-empty F ⊂ {2, …, m} is at most p_{1}n/2. It follows that there exists x_{1} ∈ A_{1} such that, if for every non-empty F ⊂ {2, …, m} we set B_{F} = A_{F} ∩ A_{1F}, then every B_{F} has density at least q_{F} = p_{F} p_{1F} (1 − 2^{−m}).

We claim now that the sets B_{F} satisfy the density condition (after a relabelling of the index set). Let h < m and let E be a non-empty subset of {h + 1, …, m}. Define B_{h,E} to be the set of all F of the form U ∪ V with U ⊂ {2, …, h − 1} and V equal to {h}, E or {h} ∪ E. Then

∏_{F ∈B_{h,E}} q_{F} ⩾ (1 − 2^{−m})^{2^{m}} ∏_{F ∈B_{h,E}} p_{F} p_{1F} = (1 − 2^{−m})^{2^{m}} ∏_{F ∈A_{h,E}} p_{F} .

But (1 − 2^{−m})^{2^{m}} ⩾ 1/4 and ∏_{F ∈A_{h,E}} p_{F} ⩾ 2^{3m}/k, so this implies that ∏_{F ∈B_{h,E}} q_{F} ⩾ 2^{3(m−1)}/k. Therefore, the sets B_{F} satisfy the density condition.

This proves the inductive step of the theorem. To be on the safe side, we take as our base case the case m = 2. (We do this so that we do not have to worry about the definition of the density condition when E cannot be non-empty.) This follows easily from the remark following Lemma 5.1 if one sets A_{1} = C, A_{2} = B and A_{12} = A. The density condition in this case is stronger than the hypothesis we needed to guarantee the existence of x_{1} and x_{2} such that x_{1} ∈ A_{1}, x_{2} ∈ A_{2} and x_{12} ∈ A_{12}. Therefore, the theorem is proved. □

We now give a couple of corollaries of Theorem 5.3. They are special cases of the theorem: the only extra content is that we need to do a small amount of calculation to optimize certain densities while preserving the density condition. Corollary 5.4. Let G be a group of order n such that no non-trivial representation has dimension less than k. For each non-empty subset F ⊂ {1, 2, …, m} let A_{F} be a subset of G of density p. Then, provided that p^{3.2^{m−2}} > 2^{3m}/k (which is true if p > 2k^{−1/2^{2m}}), there exist x_{1}, …, x_{m} such that x_{F} ∈ A_{F} for every F. Proof. Since all the densities are the same, all we have to do is look at which set A_{h,E} is largest. Obviously they get larger as h gets larger, so the largest one is when h = m − 1.

This has size 3.2^{m−2} since there are 2^{m−2} possibilities for U and 3 possibilities for V. The result now follows from Theorem 5.3. □

Corollary 5.5. Let G be a group of order n such that no non-trivial representation has dimension less than k. For every pair 1 ⩽ i < j ⩽ m let A_{ij} be a set of density p. Then, provided that p > 4k^{−1/(2m−3)}, there exist x_{1}, …, x_{m} such that x_{i}x_{j} ∈ A_{ij} for every i < j.

Proof. We shall apply Theorem 5.3 again, setting A_{F} to be G whenever F has cardinality other than 2. Then p_{F} = p if F has cardinality 2, and p_{F} = 1 otherwise. Now let us work out how many sets of size 2 are contained in A_{h,E}. If E has cardinality greater than 1 then there are h − 1 such sets, since then V must equal {h} and U must be a singleton. If E has cardinality equal to 1 then there are 2h − 1 sets, since either U is a singleton and V is {h} or E, or U is empty and V is {h} ∪ E. Since the largest possible value of h is m − 1, this tells us that the sequence exists provided that p^{2m−3} > 2^{3m}/k, which implies the corollary. □

It is possible to generalize Theorem 5.3 slightly further by exploiting two facts about Lemma 5.1. Instead of giving full details, we shall merely state two results and briefly explain how they are proved.

Theorem 5.6. Let G be a group of order n such that no non-trivial representation has dimension less than k. For every pair 1 ⩽ i < j ⩽ m let A_{ij} be a set of density p. Then, provided that p > 4k^{−1/(2m−3)}, there exist x_{1}, …, x_{m} such that x_{i}x_{j}^{−1} ∈ A_{ij} for every i < j.

Theorem 5.7. Let G be a group of order n such that no non-trivial representation has dimension less than k. Let A_{1}, A_{2}, A_{3}, A_{12}, A_{13}, A_{23} and A_{123} be subsets of G of densities p_{1}, p_{2}, p_{3}, p_{12}, p_{13}, p_{23} and p_{123}, respectively. Then, provided that p_{1}p_{2}p_{12}, p_{1}p_{3}p_{13}, p_{1}p_{23}p_{123} and p_{2}p_{3}p_{23}p_{12}p_{13}p_{123} are all at least 16/k, there exist elements x_{1} ∈ A_{1}, x_{2} ∈ A_{2} and x_{3} ∈ A_{3} such that x_{1}x_{2} ∈ A_{12}, x_{3}x_{1} ∈ A_{13}, x_{2}x_{3}^{−1} ∈ A_{23} and x_{2}x_{3}^{−1}x_{1}^{−1} ∈ A_{123}.

To prove statements like this, one exploits Lemma 5.1 and its method of proof to the full. Not only can one show that A ∩ xB is nearly always about the same size (when A and B are large enough), but also A ∩ x^{−1}B, A ∩ Bx and A ∩ Bx^{−1}. The inductive proof of Theorem 5.3 works as long as at each stage of the inductive process the variable one is trying to choose, or its inverse, appears either at the beginning or at the end of each product. So, for example, in Theorem 5.7 one starts by choosing x_{1} such that A_{2} ∩x_{1}^{−1}A_{12}, A_{3} ∩ A_{13}x_{1}^{−1} and A_{23} ∩ A_{123}x_{1} are all large. One is then left needing to place x_{2}, x_{3} and x_{2}x_{3}^{−1} into these sets, which can clearly be done.

Remarks. Although it may at first seem surprising that one can cause so many equations to be satisfied simultaneously, there is an intuitive explanation for this, at least for readers familiar with the notion of higher-degree uniformity for subsets of Abelian groups. (See [6, Section 3] for a definition of this.) In that terminology, Lemma 5.1 shows that all dense subsets of G have a property very similar to uniformity. But if that is the case, then almost all intersections of a dense set A with a translate of itself will still be dense, and will therefore be uniform as well, which shows that A has a sort of non-Abelian version of quadratic uniformity. But if uniformity implies quadratic uniformity, then it implies uniformity of all degrees. In the Abelian case, the higher the degree of uniformity a set has, the more linear equations one can hope to solve simultaneously in that set, so it is not too surprising after all that one can solve large numbers of equations simultaneously in subsets of a group where every dense set is uniform.

Another interesting aspect of Theorem 5.3 is that under certain circumstances it can yield very good bounds. For simplicity let us consider the case where all the sets A_{F} have density either p or 1, and let F be the set of F such that the density is p. Suppose that no element of {1, 2, …, m} is contained in more than r of the sets F ∈ F. Then no set A_{h,E} can contain more than 2r elements of F, so we can satisfy all the conditions simultaneously if p^{2r} ⩾ 2^{3m}/k. That is, for fixed r we can contain a power that is independent of m. (With a bit of care, the exponential dependence of the constant on m can be improved as well.) This situation would arise if, for example, we wanted x_{i}x_{j} to belong to A_{ij} whenever ij was an edge of a certain graph H of maximal degree 10.

§6. Open questions.

The results of this paper leave several questions unanswered. One that has been mentioned already is whether there is a good model for “typical” large finite groups with the property that typical groups are quasirandom. Another that has been touched on is whether Theorem 4.6 can be improved. More precisely, if G has a non-trivial representation of dimension k, does G have a product-free subset of size cn for some c that depends polynomially on k^{−1}? In view of the fact that every group of order n contains a productfree subset of polynomial size, it seems at least possible that the answer is yes. A closely related question is to find good bounds for the largest Haar measure of a product-free subset of SU(n). The methods of this paper, suitably adapted, ought to prove that this is at most Cn^{−1/3}, but the largest product-free subsets of SU(n) that we know of are in the spirit of the construction of Theorem 4.6 and are therefore exponentially small.

A question that arises naturally in the light of Theorem 4.8 is the following. Suppose that G has a normal subgroup H and that the quotient G/H is quasirandom. Does it follows that G is quasirandom? The answer is yes, in a qualitative sense, but the following proof we have is unsatisfactory and gives a bad bound. Suppose that the smallest non-trivial representation of G/H has dimension m. Extend H to a maximal normal subgroup J. Then there is a homomorphism from G/H to G/J, so G/J has no nontrivial representation of dimension less than m. In particular, G/J has order at least m^{2}. But G/J is simple, so it must be non-Abelian, and therefore, by the proof of Theorem 4.8 (which shows that a group with a large non-Abelian simple quotient is quasirandom), G is quasirandom. The trouble with this argument is that the quasirandomness of G that it guarantees is much weaker than the quasirandomness of G/H. However, it is not immediately obvious how to fix this, since a representation of G doesn’t naturally yield a representation of G/H. So the question we end up with is this: suppose that G has a normal subgroup H and that G has a non-trivial representation of dimension m? How large can the smallest non-trivial representation of G/H be? The argument above gives a bound of C^{m^{2}}. Is the correct bound polynomial?

Several problems arise when one starts to think about the following broad question: which equations have solutions in large subsets of PSL_{2}(q), or of other quasirandom groups? The most general answer we have been able to find is Theorem 5.3 (and the slight generalization mentioned at the end of the last section), but it is not obvious that that is the end of the story. Here are two questions that give some idea of what further results might or might not be true. The first has an easy negative answer: if A, B and C are three large sets, can one find a ∈ A, b ∈ B and c ∈ C such that ab = ca? The answer is no, since if ab = ca, then b = a^{−1}ca. Thus, b and c are conjugate, so to find a counterexample all one has to do is make B and C disjoint unions of conjugacy classes.

However, for a very similar question it is much less clear what the answer is. If A is a quasirandom subset of an Abelian group, then A contains approximately the same number of arithmetic progressions of length 3 (defined to be sequences of the form (a, a + d, a + 2d) with d ≠ 0) as a random set of the same cardinality, and it also contains about the same number of solutions to the equation x + y = z. Moreover, the proofs of these two facts are very similar. What happens if we investigate arithmetic progressions in subsets of PSL_{2}(q)?

The most obvious question is not very interesting: does every dense subset A of PSL_{2}(q) contain a progression of length 3, where this is now defined to be a sequence of the form (x, gx, g^{2}x)? (It might be better to call this a “left progression,” since it is not the same as a sequence of the form (x, xg, xg^{2}).) The answer is yes, since PSL_{2}(q) can be decomposed into right cosets of a cyclic subgroup of order q: we can therefore find a coset such that A intersects it densely and apply Roth’s theorem. However, this leaves two questions unanswered. First, does A in fact contain roughly the expected number of progressions of length 3? That is, if A has cardinality δn, are there roughly δ^{3}n^{2} pairs (x, g) such that x, gx and g^{2}x all lie in A? Secondly, if A, B and C are three dense subsets of PSL_{2}(q), must there be an arithmetic progression (a, b, c) ∈ A × B × C. This would be interesting, since an “off-diagonal” Roth theorem of this kind is completely false in an Abelian group.

Notice that if (a, b, c) = (x, gx, g^{2}x), then c = ba^{−1}b, and if c = ba^{−1}b then (a, b, c) = (a, ga, g^{2}a) for g = ba^{−1}. Therefore, an equivalent question to the last one is the following: if A, B and C are three dense subsets of PSL_{2}(q), must there exist a ∈ A, b ∈ B and c ∈ C such that bab = c? (To make the question cleaner we have replaced A by the set of inverses of elements of A, which obviously makes no difference.)

There is a natural bipartite graph that one can define in response to these problems: join x to y if there exists b ∈ B such that bxb = y. If this graph is automatically quasirandom, then the answers to both problems are yes. But it is not clear whether it is quasirandom. The difficulty is that we are mixing left and right actions, which makes representation theory less easy to apply. (Notice that the natural bipartite graph associated with the equation ab = ca we considered first joins x to all points of the form a^{−1}xa. It is easy to see that this graph is very far from quasirandom – indeed, it has multiple edges and a typical edge has very high multiplicity.)

References.

[1] L. Babai, V. Sos, Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin. 6 (1985), 101-114.

[2] J. Bourgain, A. Gamburd, Uniform expansion bounds for Cayley graphs of SL_{2}(F_{p}), preprint.

[3] F.R.K. Chung, R.L. Graham, Quasi-random subsets of ℤ_{n}, J. Comb. Th. A 61 (1992), 64–86.

[4] F.R.K. Chung, R.L. Graham, R.M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345–362.

[5] G. Davidoff, P. Sarnak, A. Valette, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, 55, Cambridge University Press, Cambridge, 2003.

[6] W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), 465-588.

[7] W.T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), 143-184.

[8] K.S. Kedlaya, Large product-free subsets of finite groups, J. Combin. Theory Ser. A 77 (1997), 339-343.

[9] K.S. Kedlaya, Product-free subsets of groups, Amer. Math. Monthly 105 (1998), 900-906.

[10] A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261-277.

[11] A.G. Thomason, Pseudo-random graphs, Proceedings of Random Graphs, Poznán 1985 (M. Karonski, ed.), Annals of Discrete Mathematics 33, 307–331.