Roth's Theorem states that any subset $A$ of $\{1, \dots, n\}$ with no solution to the equation $$x + y = 2z,\, (x, y, z) \in A^3,\, x \neq y$$ has size $o(n)$. Similar results hold when dealing with the same question in, for instance, $\mathbb{Z}/n\mathbb{Z}$.

I was wondering if similar questions have been studied in the context of non-abelian groups.

A more precise question: given the symmetric group $S_n$ with identity element and a linear (homogeneous) equation $$x_1^{a_1}x_2^{a_2}\cdots x_k^{a_k}=e$$

can we give general upper and lower bounds for the maximal size of a set $A \subset S_n$ without trivial solutions to the equation? Additionally, does this value depend on the invariance of the equation?

Here, by invariance I mean that the element $(\sigma,\dots,\sigma)$ is a solution to the equation for all permutations $\sigma \in S_n$.

  • 1
    $\begingroup$ Something for non-abelian groups may be done using Croot-Lev-Pach ideas, see arxiv.org/abs/1606.03256. But alas, I do not know about $S_n$. Maybe studying its group algebras over finite field would give something non-trivial. Complex group algebra does not help. $\endgroup$ – Fedor Petrov Aug 2 '16 at 7:29
  • 1
    $\begingroup$ Gowers' wonderful paper Quasirandom groups addresses exactly this question of when sets are compelled to contain solutions to certain equations. He deals with three sets $A,B,C$ and the equation $a.b=c$. He confirms that a solution exists for all sets above a certain bound, which is a function of the order of the group and the minimal degree of a non-trivial complex representation. $\endgroup$ – Nick Gill Aug 2 '16 at 14:08
  • 2
    $\begingroup$ Careful here: there are large subsets of $S_n$ with no solution of (say) $x_1 x_2 x_3 = e$. Either put some conditions on the exponents $a_k$ or restrict to subsets of $A_n$. $\endgroup$ – Noam D. Elkies Aug 2 '16 at 21:24
  • 1
    $\begingroup$ Do you really mean "without trivial solutions", gaussian? $\endgroup$ – Gerry Myerson Aug 2 '16 at 22:55
  • 1
    $\begingroup$ ... If this interpretation is correct, then Gowers' paper certainly gives an answer to the question for the situation where the $a_i$'s are trivial and $k=3$. He possibly deals with other values of $k$, I can't remember. But, noting Noam's comment, Gower's theorem is only useful for perfect groups (in which situation it is a very good answer indeed). $\endgroup$ – Nick Gill Aug 3 '16 at 0:02

For the sake of getting this question off the unanswered stack, let me turn some of the comments into a question.

  1. Noam Elkies' comment: if one considers arbitrary subsets of $S_n$, then one can find equations for which there are very large subsets of $S_n$ containing no solutions. For instance $x_1x_2x_3=1$ has no solutions in $S_n\setminus A_n$.

  2. If one restricts to subsets of $A_n$, then one can exploit the fact that $A_n$ is perfect and so all non-trivial rep's have degree at least $2$. In fact, if $n\geq 7$, the minimal dimension of a non-trivial rep is $n-1$. Now the following paper is relevant:

W. T. Gowers, MR 2410393 Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363--387.

One of the main results in this paper gives conditions under which the equation $x_1x_2=x_3$ has solutions, and this theorem can be applied directly to $A_n$. The result in question is:

Theorem 3.3. Let $\Gamma$ be a finite group with no non-trivial representation of dimension less than $k$, let $n=|\Gamma|$ and let $A,B$ and $C$ be three subsets of $\Gamma$ such that $|A||B||C|>n^3/k$. Then there exist $a\in A, b\in B$ and $c\in C$ with $ab=c$. In particular, this is true if all of $A,B$ and $C$ have size greater than $n/k^{1/3}$.

The theorem goes on to give a lower bound for the number of solutions to the given equation. Generalizations of the theorem -- to equations involving more than three variables -- are discussed in Section 5 of the above paper.

Returning to the three variable situation, one should note that Kedlaya has proved a kind of converse to the above theorem, suggesting that the answer that Gowers gives for this equation is about as good as one could hope for. The paper of Kedlaya is:

K. S. Kedlaya, Product-free subsets of groups, then and now, http://arXiv:0708.2295v1.

I don't know of any results concerning the other formulations of the OP's question -- where one has powers of variables in the equation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.