A Special Case Of The Restricted 3-Critical Number

$\require{bbox}\require{ams}$ $$2 A=\{a_1+a_2\;|\;a_1,a_2\in A\}$$

Conisder the following question: If $G$ is a finite abelian group, and $h$ is a positive integer, what is the smallest $m$ such that every $m$-subset of $G$, $A$, has the property that every element of $G$ is representable as the sum of exactly $h$ (not nessecarily distinct) elements of $A$?

For those of you familiar with my previous blogs, or additive combinatorics in general, you may recognize that this is equivalent to asking the for the minimum $m$ such that the $h$-fold sumset of every $m$-sumset of $G$ generates the entire group $G$. This is known as the $h$-critical number of $G$, and is discussed in depth in Chapter E.1 of Béla Bajnok's book, Additive Combinatorics: A Menu of Research Problems, the book from which I find many of my research problems.

However, the $h$-critical number has already been determined by Béla Bajnok (this is all found within the aformentioned book). So, I turn my attention to a similar problem. In our problem statement, recall that there is parenthetical clause that the $h$ elemenents need not be distinct. If we were to remove that clause, the problem becomes extremely different. The value of $m$ that satisfies the modifed claim is called the restricted $h$-critical number of $G$.

This idea is also explored within Bajnok's book, specifically in Chapter E.3. We borrow the notation for the restricted $h$-critical number of $G$ from the book, and denote as $\chi\hat{^\;}(G,h)$. Citing Proposition E.57, Proposition E.59, Theoren E.60, and Theorem E.65 from the aformentioned chapter of Bajnok's book we see that $\chi\hat{^\;}(G,h)$ is known for all $G$ with $h\leq 2$ or $h\geq n-2$, $G$ of even order for all $h$, and $G$ of prime order for all $h$. In addition to these, if $h=3$, and $G\cong\mathbb{Z}_n$ for some odd $n\geq 1235$ Corollary E.72 can be used to extrapolate results for an infinite amount of $n$ (but not all odd $n$). However, this is all in stark contrast to the unrestricted case where the $h$-critical number is known for every $G$, and every $h$.

This brings me to my contribution, an additional set of infinite cases for $h=3$. However, before I begin my proof we must lay out some preliminaries. Prerequisites for this proof are an understanding of cylcic groups, sumsets, and restircted sumsets.

Let $A$ and $B$ be non-empty subsets of a group of prime order $p$. We have that $$|A+B|\geq\min\{|A|+|B|-1,p\}.$$ Let $A$ be a non-empty subset of a group of prime order $p$, and let $h$ be a natural number greater than or equal to $2$. We have that $$|h\hat{^\;} A|\geq\min\{h|A|-h^2+1,p\}.$$

With these two helpful theorems in mind, I begin the proof.

If $p$ is a prime greater than or equal to $7$ then $$\chi\hat{^\;}(\mathbb{Z}_{3p},3)\leq p+3.$$ Let $p\geq 7$ be an odd prime number, and let $A$ be a subset of $\mathbb{Z}_{3p}$ with order $p+3$. Let $H$ be the index three subgroup of $\mathbb{Z}_{3p}$, and partition $A$ as follows $A_0=H\cap A$, $A_1=(H+1)\cap A$, and $A_2=(H+2)\cap A$. Note that by merely translating $A_0, A_1,$ and $A_2$ appropriately, the can easily be positioned to subsets of $H$, and thus in a group of prime order. For example, $(A_0 +(A_1-1)+(A_2-2))$ is equal to $(A_0+A_1+A_2)-3$, and $A_0+2\hat{^\;}(A_2-2)$ is the same as $(A_0+2\hat{^\;} A_2)-4$ Thus, we are free to apply Cauchy-Davenport/Erdős–Heilbronn when evaluating subset sumes like the aformentioned ones. If all of $A_0$, $A_1$, and $A_2$ are non-empty, we can immediately utilize the Cauchy-Davenport Theorem to get that $|A_0+A_1+A_2|\geq \min\{|A_0|+|A_1|+|A_2|-2,p\}$, and becuase $A_0, A_1,$ and $A_2$ partition $A$ we have that $|A_0|+|A_1|+|A_2|=|A|=p+3$. This means that $|A_0+A_1+A_2|\geq \min\{p+1,p\}=p$, and thus this sumset generates the entirety of $H$. Furthermore, because $A_0, A_1$, and $A_2$ are pairwise disjoint $A_0+A_1+A_2\subseteq 3\hat{^\;} A$, giving us that $H\subseteq 3\hat{^\;} A$. If one of $A_0$, $A_1$, or $A_2$ is empty (no more than one can be empty, as each $A_i$ has size no greater than $p$) then by the pigeonhole principle for at least one $i\in\{0,1,2\}$ we have that $|A_i|\geq \frac{p+3}{2}$. Furthermore, $3\hat{^\;} A_i\subseteq H$, so as long as $|3\hat{^\;} A_i|= p$ then $H\subseteq 3\hat{^\;} A$. By Erdős–Heilbronn, we have that $$|3\hat{^\;} A_i|\geq 3|A_i|-8.$$ And because $|A_i|\geq \frac{p+3}{2}$, we need only solve for when $$p\geq \frac{3p+9}{2}-8.$$ This is easily seen to be true as long as $p\geq 7$, and so it follows that when $p\geq 7$ we have that $H\subseteq 3\hat{^\;} A$. Now, we will prove that the other two cosets of $H$ are also contained within $3\hat{^\;} A$, starting with $H+1$. Now, see that all three of

• $2\hat{^\;} A_0+A_1$
• $2\hat{^\;} A_1+A_2$
• $2\hat{^\;} A_2+A_0$

are subsets of $3\hat{^\;} A$, and are strictly contained in the coset $(H+1)$. Cauchy-Davenport/Erdős–Heilbronn tell us the following.

• $|2\hat{^\;} A_0+A_1|\geq 2|A_0|+|A_1|-4$
• $|2\hat{^\;} A_1+A_2|\geq 2|A_1|+|A_2|-4$
• $|2\hat{^\;} A_2+A_0|\geq 2|A_2|+|A_0|-4$

If one $A_i$ is empty, it is clear that it will force the right side of the inequality not containing $A_i$ to be at least $p$, thus if any of $A_0$, $A_1$, or $A_2$ are empty then $(H+1)\subseteq 3\hat{^\;} A$. Assume this is not the case, and the usage of Cauchy-Davenport/Erdős–Heilbronn is valid in all the above scenarios. This allows us to then recognize that if we summ all three inequalities together and do some substitution we arrive at $$|2\hat{^\;} A_2+A_0|+|2\hat{^\;} A_1+A_2|+|2\hat{^\;} A_2+A_0|\geq 3p,$$ and by the pigeonhole principle at least one of the three terms on the left have size $p$, an thus $(H+1)\subseteq 3\hat{^\;} A$. The case for the coset $(H+2)$ is nearly identical to the above, but instead the three sets are listed below.

• $2\hat{^\;} A_1+A_0$
• $2\hat{^\;} A_2+A_1$
• $2\hat{^\;} A_0+A_2$

For brevity, I will not be repeating the proscess, but it is easily seen to work identically to the previous case, and leads to the conclusion that $(H+2)\subseteq 3\hat{^\;} A$. However, this means that $H\cup (H+1)\cup (H+2)\subseteq 3\hat{^\;} A$, and thus $\mathbb{Z}_{3p}\subseteq 3\hat{^\;} A$. Therfore, if $A$ is a subset of $\mathbb{Z}_{3p}$ for prime $p\geq 7$, and $|A|=p+3$, then $3\hat{^\;} A=\mathbb{Z}_{3p}$. Thus, the restricted $3$-critical number in $\mathbb{Z}_{3p}$ is at most $p+3$. However, I said before that we had equality for an infinite amount of cases, and this can be seen through Proposition E.67 in Béla Bajnok's book which gives us the lower bound required for equality. Thus, we have the following. If $p$ is a prime greater than or equal to $7$ then $$\chi\hat{^\;}(\mathbb{Z}_{3p},3)= p+3.$$ This is one of the few cases for which $\chi\hat{^\;}$ is known for an infinite amount of $G$ as noted above. There is still much left to solve for this question, and so I offer the following problems.

Problem 1: Find the value of $\chi\hat{^\;} (G,h)$ for $h\geq 3$ and all $G$.

More specifically,

Problem 2: Find the value of $\chi\hat{^\;} (G,3)$ for all $G$ of odd composite order.

We can actually utilize $\chi\hat{^\;}$ to contribute to the solving of a zero-sum-free problem, specifically, the weak zero-$h$-sum free problem. A weak zero-$h$-sum free set is a set where $0$ is not contained in the restricted $h$-fold sumset. Thus, if we denote the maximim size of such a subset of $G$ as $\tau\hat{^\;}(G,h)$ it is clear from the theorem preoven above that for prime $p\geq 7$ we have that $$\tau\hat{^\;}(\mathbb{Z}_{3p},3)\leq p+2.$$ So, as an adjecent problem, I ask this.

Problem 3: Find the value of $\tau\hat{^\;} (G,3)$ for all $G$ of odd composite order.

Another problem from Bajnok's book that this results contributes to is minimum sumset size. We have the function $\rho\hat{^\;}(G,m,h)$ denote the smallest size of an $h$-fold sumset of $A$, where $A$ is an $m$-subset of $G$. It is clear that the result presented in this blog procuces the following result. If $p$ is a prime greater than or equal to $7$, and $m\geq p+3$ then $$\rho\hat{^\;}(\mathbb{Z}_{3p},m,3)= 3p.$$ Furthremore, if $m\leq p+2$ then $$\rho\hat{^\;}(\mathbb{Z}_{3p},m,3)\leq 3p-1.$$ The problem of evaluating $\rho\hat{^\;}(G,m,h)$ is one of the most intriguing to me (Keep your eye out for content on $\rho\hat{^\;}(\mathbb{Z}_2^r,m,h)$ soon!) so I offer this problem.

Problem 4: Find the value of $\rho\hat{^\;} (G,m,h)$ for all positive integers $m$, $h$, and abelian groups $G$, or at least an infinite subset of them.

This is where I am going to conclude this blog post. I hope you enjoyed the proof included in this blog. I am thinking about doing that more frequently. If you have any questions about the content presented here, or if you have any ideas on approaching the four problems presented above, feel free to send me an email or a DM over Instagram! I hopefully will be able to post more complete papers of my recenet research soon. Thank you for reading and have a great week.