Growth of powers of symmetric subsets in a finite group

Let $$G$$ be a finite group, and let $$A$$ be a symmetric subset of $$G$$ containing the identity (i.e., $$A^{-1}=A$$ and $$1\in A$$). Then the powers of $$A$$ will form a chain $$A\subsetneq A^2\subsetneq A^3\subsetneq\cdots\subsetneq A^d=\langle A\rangle$$.

It turns out that if $$A$$ is large, then $$d$$ must be small. But how small? That is my question (formulated precisely at the end).

For example, the following lemma is a slight modification of Lemma 2.1 in this paper of Eberhard.

Lemma. If $$(r+1)\lvert A\rvert>\lvert G\rvert$$, then $$d\leq3r-1$$.

Proof. If $$d\geq3r$$, then we can find $$g_i\in A^{3i}\setminus A^{3i-1}$$ for $$i=1,\ldots,r$$. Then $$g_iA\subseteq A^{3i+1}\setminus A^{3i-2}$$, so $$A,g_1A,\ldots,g_rA$$ are disjoint subsets of $$G$$ each of size $$\lvert A\rvert$$, so $$(r+1)\lvert A\rvert\leq\lvert G\rvert$$. $$\square$$

But this lemma is not optimal. The proof finds two translates of $$A$$ inside $$A^4$$, but it is actually possible to find two translates of $$A$$ inside $$A^3$$. This gives a bound of $$3r-2$$.

Lemma. If $$r\geq2$$ and $$(r+1)\lvert A\rvert>\lvert G\rvert$$, then $$d\leq3r-2$$.

Proof. If $$d\geq3r-1$$, then we can find $$g_i\in A^{3i-1}\setminus A^{3i-2}$$ for $$i=2,\ldots,r$$. Then $$g_iA\subseteq A^{3i}\setminus A^{3i-3}$$. Since $$d>2$$, we can find $$g_0\in A$$ such that $$g_0A^2\neq A^2$$. Pick $$g_1\in A^2\setminus g_0A^2$$. Then $$g_1A$$ and $$g_2A$$ are disjoint translates of $$A$$ inside $$A^3$$. Then $$g_0A,g_1A,g_2A,\ldots,g_rA$$ are disjoint subsets of $$G$$ each of size $$\lvert A\rvert$$, so $$(r+1)\lvert A\rvert\leq\lvert G\rvert$$. $$\square$$

If $$k\lvert A\rvert>\lvert G\rvert$$, what is the optimal upper bound on $$d$$ in terms of $$k$$?

If $$2\lvert A\rvert>\lvert G\rvert$$, then $$d\leq2$$ is optimal (set $$A=\{-1,0,1\}\subseteq\mathbb{Z}/5\mathbb{Z}$$).

If $$3\lvert A\rvert>\lvert G\rvert$$, then $$d\leq4$$ is optimal (set $$A=\{-1,0,1\}\subseteq\mathbb{Z}/8\mathbb{Z}$$).

• A weaker question that I would still be interested in is how large does $d$ need to be in order to guarantee $k$ disjoint translates of $A$? Oct 3, 2023 at 15:44
• Is the number $k$ integer? Oct 5, 2023 at 16:52
• For each natural $r$ if $(r+1)\lvert A\rvert>\lvert G\rvert$ then $d=\lceil (3r+1)/2\rceil$ is possible (set $A=\{-1,0,1\}\subseteq\mathbb{Z}/(3r+2)\mathbb{Z}$. Oct 5, 2023 at 17:11
• Yes, $k$ is an integer. And thanks for the correction and the general cyclic group formula. Oct 5, 2023 at 18:16

Here is a solution when $$G$$ is abelian.

Claim: Suppose $$G$$ is abelian. If $$(r + 1)|A| > |G|$$, then $$k A = \langle A \rangle$$, where $$k = \lceil (3r + 1) / 2 \rceil$$. This matches Ravsky's construction.

Let's look at the case $$r = 2s$$ is even. In this case, it suffices to show that $$(3s + 1)A = \langle A \rangle$$. Suppose the contrary. Take some $$g \in (3s + 2)A \backslash (3s + 1)A$$. We can write $$g$$ as $$g = a_1 + \cdots + a_{3s + 2}, a_i \in A$$ which I call a summation of $$g$$.

Define $$S_i = a_1 + \cdots + a_i$$. Consider the following cosets of $$A$$ $$S_{3i} A, 0 \leq i \leq s$$ and $$(S_{3j - 1} - g) A, 1 \leq j \leq s.$$ We claim that all these cosets are disjoint.

If $$S_{3i}$$ and $$S_{3i'}$$ intersect with $$i < i'$$, then we have $$a_{3i + 1} + \cdots + a_{3i'} \in 2A$$, which means we can swap this segment in the summation of $$g$$ with an element of $$2A$$, to get a shorter summation of $$g$$. Thus $$g \in (3s + 1)A$$, contradiction.

Similarly, the cosets $$(S_{3j - 1} - g) A$$ are disjoint.

Now suppose that $$S_{3i} A$$ and $$(S_{3j - 1} - g) A$$ intersect. Then we have $$S_{3i} + g - S_{3j - 1} \in 2A \Longrightarrow a_1 + \cdots + a_{3i} + a_{3j} + \cdots + a_{3s + 2} \in 2A.$$ If $$i < j$$, we can simply replace $$a_1 + \cdots + a_{3i} + a_{3j} + \cdots + a_{3s + 2}$$ in the summation of $$g$$ with an element of $$2A$$, obtaining a shorter summation, contradiction. Otherwise, we have $$a_1 + \cdots + a_{3i} + a_{3j} + \cdots + a_{3s + 2} = g + a_{3j} + \cdots + a_{3i}.$$ So we can write $$g \in -a_{3j} - \cdots - a_{3i} + 2A$$ which is a summation of length $$3(i - j + 1) \leq 3s$$, contradiction!

So the cosets are disjoint, and $$(2s + 1)|A| \leq |G|$$, contradiction. This finishes the proof of our claim when $$r$$ is even.

When $$r = 2s - 1$$ is odd, we have $$k = 3s - 1$$. The proof is analogous: if $$g \in 3sA \backslash (3s - 1)A$$, we take a summation of $$g = a_1 + \cdots. + a_{3s}$$, and consider the cosets $$S_{3i} A, 1 \leq i \leq s$$ and $$(S_{3j} - g) A, 1 \leq j \leq s.$$ (I think) It is analogous to show that these cosets are disjoint, and arrive at a contradiction.

I don't yet have an intuition for the non-abelian case(additive combinatorics tend to be harder in that regime). I'd gladly discuss this with anyone interested.

• +1. I tried to adapt your construction for non-Abelian groups, but failed. So maybe it makes sense to look for a small non-Abelian group for which the bound from Claim fails. The bound optimality is proved for $r\le 2$, so it suggests to consider the case $r=3$. Oct 12, 2023 at 1:38