3
$\begingroup$

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$.

Improve this question
$\endgroup$
10
  • 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
    Commented Aug 2, 2016 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
    Commented Aug 2, 2016 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
    Commented Aug 2, 2016 at 21:24
  • 1
    $\begingroup$ Do you really mean "without trivial solutions", gaussian? $\endgroup$
    – Gerry Myerson
    Commented Aug 2, 2016 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
    Commented Aug 3, 2016 at 0:02

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .