🔢 mathematics

The Erd\H{o}s-Ginzburg-Ziv theorem constant of finite groups

This paper confirms the Gao-Li conjecture that the Erdős-Ginzburg-Ziv constant of any finite non-cyclic group with order not divisible by four is at most $\frac{3|G|}{2}$ , while characterizing the groups achieving this bound as those possessing a cyclic subgroup of index two.

Original authors: Yang Zhao, Guoqing Wang

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Yang Zhao, Guoqing Wang

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are hosting a massive, chaotic dinner party. You have a group of $n$ guests (the "group" $G$ ). Each guest brings a unique dish, but the dishes are written in a secret code. To enjoy the meal, you need to find a specific subset of $n$ dishes that, when combined in the right order, magically cancel each other out to create a "perfectly balanced" dish (the identity element, or "1").

The Erdős-Ginzburg-Ziv (EGZ) Theorem asks a simple but tricky question: How many guests do you need to invite to guarantee that you can always find this perfect subset of $n$ dishes, no matter what dishes they brought?

This number is called the EGZ Constant, denoted as $E(G)$ .

The Old Rules (The Abelian World)

For a long time, mathematicians knew the answer for "nice" groups (called abelian groups, where the order of mixing dishes doesn't matter). They proved that if you invite $2n - 1$ guests, you are guaranteed to find your perfect subset.

Analogy: If you have 10 guests, you need to invite 19 people to be 100% sure you can make the perfect dish.

The New Mystery (The Chaotic World)

But what if the group is "non-abelian"? In these groups, the order matters! Mixing Dish A then Dish B is different from Dish B then Dish A. This makes the math much messier.

In 2010, mathematicians Gao and Li made a bold guess (a conjecture):

"For any messy, non-abelian group, you never need more than $1.5n$ (or $\frac{3|G|}{2}$ ) guests to guarantee a solution."

For a group of 10, this means you only need 15 guests, not 19. This is a huge saving!

What This Paper Does

Yang Zhao and Guoqing Wang, the authors of this paper, decided to test this guess. They focused on a specific type of messy group: groups whose size is not divisible by 4 (think of groups with sizes like 6, 10, 12, 18, etc., but not 8, 12, 16, 20... wait, 12 is divisible by 4, so they exclude 12. They look at sizes like 6, 10, 14, 18, 22...).

Their Main Discovery:
They proved that Gao and Li's guess is correct for all these groups.

The Result: If your group size isn't divisible by 4, you never need more than $1.5n$ guests.
The "Worst Case": They also found out exactly when you need the full $1.5n$ $1.5 n$ guests. It happens only if your group has a specific structure: it must contain a "cyclic subgroup" that is exactly half the size of the whole group.
- Analogy: Imagine your dinner party has a "VIP section" of half the guests who all follow a strict, predictable rhythm (cyclic). If the rest of the party interacts with this VIP section in a specific way, the chaos is maximized, and you need the full $1.5n$ guests to be safe. If the group doesn't have this specific VIP structure, you actually need fewer guests than the maximum limit.

How They Solved It (The Detective Work)

To prove this, the authors acted like detectives solving a puzzle:

The "Product-One" Hunt: They looked at sequences of elements (guests) and tried to find a subsequence (a smaller group) that multiplies to 1.
Breaking it Down: They used a technique called "quotient groups." Imagine putting all the guests into two teams (Team A and Team B) based on a simple rule. If you can solve the problem for the teams, you can often solve it for the whole party.
The "Small" Groups: They checked specific, tricky small groups (like a group of 18 people) by hand, using computer-like logic to show that even in the worst-case scenarios, you can always find the solution with fewer than $1.5n$ guests, unless the group has that specific "half-cyclic" structure.
The "Index 2" Clue: They discovered that the only time the limit hits the ceiling ( $1.5n$ ) is when the group is built like a sandwich: a big, predictable cyclic layer (the bread) and a chaotic layer (the filling) that flips the bread over. If the group isn't built this way, the chaos is less severe, and the limit is lower.

Why Should You Care?

This might sound like abstract math, but it's actually about structure and chaos.

Zero-Sum Theory: This field studies how things cancel each other out. It's used in cryptography, coding theory, and even understanding how molecules bond.
The "Rigidity" of Groups: The paper shows that finite groups have a surprising amount of order. Even when they seem chaotic (non-abelian), they have strict limits on how "bad" they can get. You don't need an infinite number of tries to find a solution; a specific, manageable number is always enough.

In a Nutshell:
The authors proved that for a huge class of mathematical groups, you can always find a "perfect combination" of elements if you have 1.5 times the number of elements in the group. Furthermore, they identified the exact "chaotic recipe" that forces you to need that full 1.5 times, and showed that any group without that recipe is actually easier to solve.

1. Problem Statement and Context

The Erdős-Ginzburg-Ziv (EGZ) Constant:
Let $G$ be a finite group of order $n$ . The EGZ constant, denoted $E(G)$ , is defined as the smallest positive integer $\ell$ such that every sequence of length $\ell$ over $G$ contains a subsequence of length $n$ whose product (in some order) is the identity element $1_G$ .

Background:

Abelian Case: The original EGZ theorem (1961) proved that for any finite abelian group $G$ , $E(G) \le 2|G| - 1$ . For cyclic groups, this bound is tight: $E(G) = 2|G| - 1$ .
Non-Abelian Case: The behavior of $E(G)$ for non-abelian groups is more complex. While Olson (1976) established $E(G) \le 2|G| - 1$ for all finite groups, tighter bounds were sought for non-cyclic groups.
The Conjecture: In 2010, Gao and Li conjectured that for every finite non-cyclic group $G$ , the bound improves to:
$E(G) \le \frac{3|G|}{2}$
Previous work had confirmed this for groups of odd order (Gao, Li, Qu, 2023) and specific orders involving primes (Godara et al., 2023).

The Specific Problem:
This paper aims to confirm the Gao-Li conjecture for a specific class of groups: finite non-cyclic groups whose order is not divisible by 4 (i.e., $|G| \not\equiv 0 \pmod 4$ ). Furthermore, the authors aim to characterize the groups for which the equality $E(G) = \frac{3|G|}{2}$ holds.

2. Methodology

The authors employ a combination of structural group theory and combinatorial number theory (Zero-Sum Theory). The proof strategy relies on several key components:

Davenport Constant ( $d(G)$ ): The paper utilizes the relationship between $E(G)$ and the Davenport constant $d(G)$ (the maximal length of a product-one free sequence). Key inequalities used include $E(G) \ge d(G) + |G|$ and the equality $E(G) = d(G) + |G|$ for abelian groups.
Inductive and Quotient Arguments: The proof frequently utilizes normal subgroups $H \trianglelefteq G$ and the canonical epimorphism $\phi: G \to G/H$ . By analyzing sequences in the quotient group and lifting results back to $G$ , the authors reduce the problem to smaller subgroups.
Case Analysis based on Group Structure:
- Odd Order: Leveraging previous results (Lemma 3.7) for odd-order non-cyclic groups.
- Even Order ( $|G| = 2m$ , $m$ odd): Using the fact that such groups possess a subgroup of index 2 (Lemma 3.6).
- Metacyclic Groups: Utilizing known results for groups of the form $C_m \rtimes C_2$ .
Extremal Sequence Analysis: For the specific case where the group order is 18 and the group is non-abelian without a cyclic subgroup of index 2, the authors perform a rigorous combinatorial analysis of sequences of length 26 (the conjectured bound). They analyze the structure of sequences that fail to have a product-one subsequence of length 18, utilizing Lemma 3.9 (which classifies extremal sequences in $C_n \times C_n$ ) to derive contradictions.

3. Key Contributions and Results

Main Theorem (Theorem 1.2):
Let $G$ be a finite non-cyclic group such that $4 \nmid |G|$ . Then:

Upper Bound: $E(G) \le \frac{3|G|}{2}$ .
Characterization of Equality: The equality $E(G) = \frac{3|G|}{2}$ holds if and only if $G$ has a cyclic subgroup of index 2.

Detailed Breakdown of the Proof:

Case 1: $G$ has a cyclic subgroup of index 2.
- If $G$ is abelian, $E(G) = |G| + d(G)$ . Since $G$ is non-cyclic with a cyclic subgroup of index 2, $d(G) = |G|/2$ , yielding $E(G) = 3|G|/2$ .
- If $G$ is non-abelian, $G \cong C_{n/2} \rtimes C_2$ . The authors cite Lemma 3.8 (Gao et al.) which states $E(G) = 3|G|/2$ for such metacyclic groups.
Case 2: $G$ does not have a cyclic subgroup of index 2.
- Odd Order: Follows directly from Gao-Li-Qu (2023) results, showing $E(G) \le \frac{3|G|-3}{2}$ .
- Even Order ( $|G| = 2m, m$ odd): Let $K$ $K$ be the normal subgroup of index 2.
  - If $K \not\cong C_3 \times C_3$ , the bound follows from induction on the subgroup and Lemma 3.5.
  - If $K \cong C_3 \times C_3$ , then $|G| = 18$ . The authors classify the non-abelian groups of order 18 without a cyclic subgroup of index 2 as isomorphic to $S_3 \times C_3$ or $(C_3 \times C_3) \rtimes_{-1} C_2$ .
  - Lemma 3.11: The authors prove explicitly that for these two specific groups of order 18, $E(G) \le 26$ (which is $3|G|/2 - 1$ ). This involves a detailed contradiction argument assuming a sequence of length 26 has no product-one subsequence of length 18, analyzing the distribution of elements in the quotient $G/H \cong C_2$ and the subgroup $H \cong C_3 \times C_3$ .

4. Significance

Resolution of a Conjecture: The paper confirms the Gao-Li conjecture for a significant new class of groups (those with order not divisible by 4), extending the known validity from odd orders to a broader even-order context.
Inverse Problem Solution: Beyond proving the upper bound, the paper provides a complete characterization of the extremal cases. It identifies exactly which structural property (existence of a cyclic subgroup of index 2) forces the EGZ constant to reach the theoretical maximum of $3|G|/2$ .
Methodological Advancement: The proof for the order 18 case (Lemma 3.11) demonstrates sophisticated handling of non-abelian sequence structures, bridging the gap between abelian zero-sum theory and general group theory.
Foundation for Future Research: By resolving the case where $4 \nmid |G|$ , the paper narrows the scope for the general conjecture to groups where the order is divisible by 4, guiding future research directions in Zero-Sum Theory.

In summary, Zhao and Wang successfully prove that for finite non-cyclic groups with order not divisible by 4, the EGZ constant is bounded by $1.5|G|$ , and this bound is sharp precisely when the group possesses a cyclic subgroup of index 2.