8
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$ Oct 3, 2023 at 15:44
  • $\begingroup$ Is the number $k$ integer? $\endgroup$ Oct 5, 2023 at 16:52
  • $\begingroup$ 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}$. $\endgroup$ Oct 5, 2023 at 17:11
  • $\begingroup$ Yes, $k$ is an integer. And thanks for the correction and the general cyclic group formula. $\endgroup$ Oct 5, 2023 at 18:16

1 Answer 1

3
+50
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ +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$. $\endgroup$ Oct 12, 2023 at 1:38

You must log in to answer this question.

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