Source-linked AI summary
Quasirandom groups
W. T. Gowers
TL;DR
The paper asks whether every finite group contains a product-free subset of positive proportional size. Using quasirandomness, it answers no by showing that sufficiently large PSL2(q) has no product-free subset of size Cn^8/9.
Problem
The paper examines whether every finite group has a product-free subset whose size is a fixed positive proportion of the group.
Method
It analyzes products among large subsets through a quasirandomness framework.
Results
For sufficiently large q, PSL2(q) has no product-free subset of size Cn^8/9; indeed, any three subsets of that size contain a,b,c with ab=c.
Takeaways & Limitations
Finite groups need not contain product-free subsets whose sizes are proportional to their orders.
Takeaways & Limitations
The paper notes that its converse is only partial.
Abstract
from arXiv · showhide
Babai and Sós 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 paper answers negatively the question of whether every finite group has a product-free subset of positive density, showing that sufficiently large PSL2(q) has no product-free subset of size Cn^8/9. It develops quasirandomness as the underlying framework and derives converse, structural, and equation-generalization results.
- Main result: More strongly, any three subsets A, B, and C of PSL2(q) with size at least Cn^8/9 contain a triple (a, b, c) satisfying ab = c.Thus the obstruction applies simultaneously to three dense subsets, not only one product-free set.
- Proof strategy: The proof proceeds through quasirandom bipartite graphs and subsets, establishes quasirandomness for a bipartite Cayley graph of PSL2(q), and applies it to the three sets.The introduction describes these as the proof’s three stages.
- Quasirandomness: PSL2(q) is suitable because it has no non-trivial irreducible representations of low dimension, a property termed quasirandomness and equivalent to several other properties.Some equivalent formulations concern associated graphs being quasirandom.
- Further results: The paper proves a partial converse: if a finite group has no large product-free subset, then it is quasirandom, although the resulting dependence between constants is exponential/logarithmic.The introduction explicitly notes that these bounds are not very good.
- Further results: A later generalization places variables and products such as a, b, c, ab, bc, ac, and abc into specified dense subsets of a quasirandom group.This extends the main theorem from three-term products to more complicated equations.
§2. Quasirandom graphs and sets.
This section reviews quasirandomness for graphs, bipartite graphs, and subsets of finite Abelian groups. It presents equivalent combinatorial, spectral, Fourier-analytic, and graph-theoretic formulations that place later results in context.
- Quasirandom graphs: Quasirandom graphs are characterized by polynomially equivalent conditions involving 4-cycle counts, edge distribution between subsets, and adjacency eigenvalues.A graph satisfying these properties with sufficiently small error is called quasirandom.
- Quasirandom bipartite graphs: Quasirandom bipartite graphs likewise admit polynomially equivalent formulations through 4-cycle counts and edge-distribution estimates between subsets of the two vertex classes.The usual eigenvalue condition is omitted because the bipartite adjacency matrix is not symmetric.
- Quasirandom subsets of Abelian groups: For a subset A of an Abelian group, quasirandomness has equivalent formulations involving additive quadruples and graphs defined by x + y ∈ A or y − x ∈ A.The section introduces Fourier transforms, convolution, and characteristic functions as analytic tools for these formulations.
- Connections between formulations: The graph and bipartite-graph constructions associated with A are themselves quasirandom, linking additive pseudorandomness to the earlier graph-theoretic definitions.These constructions use adjacency relations determined by x + y ∈ A and y − x ∈ A.
§5. Solving equations in quasirandom groups.
This section develops an inductive theorem for solving exponentially many simultaneous product constraints in quasirandom groups. It derives uniform-density and pairwise-product corollaries, inverse-product variants, and a refinement whose density exponent is independent of the number of variables under fixed conditions.
- The case m = 3: For m = 3, the seven prescribed densities need only satisfy p1p2p12, p1p3p13, p1p23p123, and p2p3p23p12p13p123 ≥ 16/k.Under these conditions, elements x1, x2, x3 satisfy all three individual, three pairwise, and one triple-product constraints.
- General simultaneous equations: Theorem 5.3 constructs x1, ..., xm such that every ordered subset product xF lies in its prescribed set AF when the density condition holds.The proof inductively selects x1 so that all residual intersections retain sufficient density, then applies the same condition to the remaining variables.
- Corollaries: A common density p suffices for all subset-product constraints when p3·2m−2 > 2^3m/k, in particular when p > 2k−1/2^2m.The resulting elements x1, ..., xm have every nonempty subset product in its corresponding prescribed set.
- Corollaries: For pairwise product constraints, p > 4k−1/(2m−3) guarantees elements x1, ..., xm with xixj ∈ Aij for every i < j.The section also states an inverse-product analogue under the same density threshold.
- Further consequences: For fixed r, the condition p2r ≥ 2^3m/k permits containing a power whose required density exponent is independent of m.The exponential dependence of the constant on m can also be improved with additional care.
§6. Open questions.
The section identifies open questions about random quasirandom groups, product-free subsets, product-free measures in SU(n), and equations or progressions in quasirandom groups. It also records a positive answer to Question 6.2 while leaving open whether classification of finite simple groups is necessary.
- Random quasirandom groups: Question 6.1 asks for a model of large random finite groups that yields quasirandom groups with high probability.The question is stated as an unresolved issue.
- Product-free subsets: Question 6.2 has a positive answer: a non-trivial k-dimensional representation implies a product-free subset of size cn for c depending polynomially on k−1.The argument uses the classification of finite simple groups to obtain either a proper subgroup of index at most k^c or an Abelian quotient, both yielding product-free subsets.
- Product-free subsets: It remains open whether Question 6.2 admits a classification-free proof.The paper notes that the known solution has the flavour of classification of finite simple groups but may not require it.
- Equations and progressions: A natural bipartite graph would imply affirmative answers to both PSL2(q) progression questions if it were quasirandom, but this is unclear because left and right actions are mixed.This mixing makes representation theory less easy to apply.