Let $G$ be a group and let $S$ be a subset such that if $a\in S$ then $a^{-1}\not \in S$.

Let $$G$$ be a group and let $$S$$ be a subset of $$n$$ distinct elements of $$G$$ with the property that $$a\in S$$ implies $$a^{-1}\not\in S$$. Consider the $$n^2$$ products (not necessarily distinct) of the form $$ab$$, where $$a\in S$$ and $$b\in S$$. Prove that at most $$n(n-1)/2$$ of these products belong to $$S$$.

I consider the group $$G=\langle\mathbb Z_{11}, \cdot\rangle$$, and let $$S=\{2,3,5,7\}$$ which clearly satisfy the property.
Then I tested it, in $$16$$ of the numbers, exactly $$6$$ of them are in $$S$$.
Any suggestion for how to prove it?

Let $$T$$ be the set of pairs $$(a,b)\in S^2$$ such that $$ab\in S$$. Let $$U$$ be the set of pairs $$(a,b)\in S^2$$ such that $$b\in aS$$.
Define the permutation $$q:G^2\to G^2$$ by $$q(a,b)=(a,ab)$$. Then $$q(T)=U$$.
By the assumption $$S\cap S^{-1}=\emptyset$$, we have $$(a,a)\notin U$$ and $$(a,b)\in U$$ implies $$(b,a)\notin U$$. Hence $$|U|\le n(n-1)/2$$. Since $$|U|=|T|$$ it follows that $$|T|\le n(n-1)/2$$.
• Your solution really amaze me, how can you figure out the definitions of $T$ and $U$? – kelvin hong 方 Feb 14 '19 at 7:57
• The definition of $T$ was implicit in your question and explicit in the other tentative answer. The definition of $U$ is quite natural when familiar with Schreier graphs and partial actions. Outputting $n(n-1)/2$ suggested finding an oriented graph structure, and oriented comes naturally with the assumption on $S$. – YCor Feb 14 '19 at 8:00