Random Cayley sum hypergraphs and k-fold sumsets

arXiv:2610.08629 · math.CO, math.NT · Submitted 2026-10-06 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: I'm Ada.

Emmy: And I'm Emmy, here with Kolya.

Ada: We're looking at the paper: "Random Cayley sum hypergraphs and k-fold sumsets".

Emmy: Here's the gist of the paper. fk(Γ) ≤ Oe(n(2k−1)/(4k−3)) holds for all finite abelian groups Γ and integers k ≥ 2 <ref:2610.08629#pg2> Additionally, the lower bound fk(Γ) ≥ Ωe(n/k) holds if Γ has no nontrivial element of order dividing k <ref:2610.08629#pg4> The proof relies on a new upper bound for the independence number of random Cayley sum hypergraphs <ref:2610.08629#pg4> The study of additive structures in a subset of a given abelian group has been of great interest <ref:2610.08629#pg2> For an integer k ≥ 2, the quantity fk(Γ) denotes the largest integer with the property that every subset of Γ of size at least Γ − fk(Γ) is a k-fold sumset <ref:2610.08629#pg2> This paper extends a recent result of Alon and Pham to prove that fk(Γ) ≤ Oe(n(2k−1)/(4k−3)) holds for all finite abelian groups Γ and integers k ≥ 2, where n = Γ <ref:2610.08629#pg2> Upper Bound Derivation The upper bound of Theorem 1.3 is established by proving the existence of a large set that is not a k-fold sumset by a probabilistic argument <ref:2610.08629#pg2> This involves showing that for a p-random subset S1 with p < 1/2, there exists a small S2 such that A = Γ(S1 ∪ S2) is not a k-fold sumset <ref:2610.08629#pg4> The independence number of the Cayley sum hypergraph HS1 is at most O(p(-3/2)) with high probability <ref:2610.08629#pg4> Lower Bound Proof via Probabilistic Method The lower bound fk(Γ) ≥ Ωe(n/k) holds if Γ has no nontrivial element of order dividing k <ref:2610.08629#pg4> This is proven by finding a set A from a collection of random sets whose probability of any k-fold sum of its elements in the set lying in Γ¬F is maximized <ref:2610.08629#pg4> The claim that for each g ∈ Γ¬F, there exist more than 10k cubed log n pairs (a(i)1, · · ·, a(i)k) ∈ C k such that a(i)1 + · · · + a(i)k = g with probability at least 1 − o(1/n2) <ref:2610.08629#pg8> Existence of Small Non-Sumsets The existence of a small non-k-fold sumset is proven by bounding the k-partite hole number of a random Cayley hypergraph <ref:2610.08629#pg4> The probability that there exists a k-partite hole of size s in HS is bounded by (9) <ref:2610.08629#pg19> This leads to the conclusion that there exists a subset of Γ of size at least n − O(n(2k−1)/4k−3 log n(5k/2)) which cannot be represented as a k-fold sumset <ref:2610.08629#pg20> Conjectures and Future Directions The authors conjecture that the asymptotic behavior of the threshold fk(Γ) will match that of the lower bound, stating that for all integer k ≥ 2 and a finite abelian group Γ of size n without a nontrivial element of order dividing k, it holds that fk(Γ) = Θ(e(n/k)) <ref:2610.08629#pg6> References

1: N.

Ada: Alon, Large sets in finite fields are sumsets, J.

Emmy: Number Theory 126 (2007), no.

Ada: 1, 110–118 <ref:2610.08629#pg3>

3: N.

Title and authors: Ada: So we're looking at this paper called Random Cayley sum hypergraphs and k-fold sumsets. It's dealing with how large a subset you can have in an abelian group that is still guaranteed to be a k-fold sumset. The title itself just tells you the main ingredients: random graphs, sums, and k-fold sums.

Emmy: And the authors are Jihyo Chae and Hyunwoo Lee. It sounds like they're taking techniques from probabilistic methods and applying them to this additive structure problem in a new way. It’s interesting because it connects the study of random graph properties with deep questions in additive combinatorics about sumsets.

Kolya: I'm thinking about what this means for the general case. We usually think about binary sums, k equals two, but this paper is tackling any integer k greater than or equal to two. It suggests there's a unified way to look at these structures across different values of k.

Ada: Exactly. The paper aims to give an upper bound on this quantity fk(Gamma). They prove that for all finite abelian groups Gamma and any integer k greater than or equal to two, this value is less than or equal to some expression involving n, the size of the group, and k. Specifically, it says fk(Gamma) is at most O of n times 2k minus one divided by 4k minus three <ref:2610.08629#pg1>.

Emmy: That's a polynomial improvement over some previous results they cited. It seems they’re refining the known bounds for this problem in a way that applies to all k values simultaneously, which is quite a significant structural claim.

The paper's summary: Ada: Okay, so what does the actual proof look like? The core idea seems to be using probabilistic arguments to show that there must exist a large set that isn't a k-fold sumset. They do this by looking at random Cayley sum hypergraphs.

Emmy: Right. They show that for a sufficiently random subset, there exists another small set such that the resulting structure is not what we expect it to be, which leads to the conclusion about the size of these non-sumsets.

Kolya: I'm focused on how they use those probabilistic methods. They mention bounding the independence number of these random Cayley sum hypergraphs with high probability. That sounds like they are using tools like Hoeffding’s inequality and Janson’s inequality to get a rigorous bound on how sparse these graphs can be.

Ada: It seems that by establishing a tight upper bound on the independence number, they can control the size of these non-sumsets very effectively. The result is that there exists a subset of Gamma with size at least n minus some term involving n raised to the power of 2k minus one divided by 4k minus three times a logarithm term <ref:2610.08629#pg1>.

Emmy: That specific bound on the existence of a large non-sumset, which they call Theorem one point five, is what drives the main result here <ref:2610.08629#pg3>. It’s not just about showing something exists; it's quantifying how large that set can be compared to the whole group size n.

The paper's improvements: Ada: Beyond just proving that a bound exists, they are improving previous results. They state that their upper bound on the independence number of a random Cayley sum hypergraph is better than what was previously known by Balogh, Liu, and Sharifzadeh.

Emmy: That improvement is key because it directly leads to a tighter upper bound for fk(Gamma), which recovers the old Alon and Pham result when you set k equals two. It shows they've pushed the existing boundaries on this problem for all k values.

Kolya: From a probabilistic perspective, what does this improved independence number actually mean in terms of tail bounds? It suggests that the concentration inequalities they are using are powerful enough to keep the probability of finding a small non-sumset high, even when you have more complex structures involving k parts.

Ada: And they also provide a lower bound under specific conditions. If the abelian group Gamma has no nontrivial element whose order divides k, then they prove that fk(Gamma) is at least proportional to n divided by k. This is a significant contrast to the upper bound when those conditions are met.

Emmy: So, if you have those specific structural constraints on the group, you get a much stronger guarantee on how large your sumsets can be. It shows that the structure of the group itself dictates whether these bounds are tighter or looser.

Conclusion: Ada: To wrap up, we've seen that for any finite abelian group Gamma and any integer k greater than or equal to two, there's an upper bound on fk(Gamma). This bound is approximately n times 2k minus one divided by 4k minus three <ref:2610.08629#pg1>.

Emmy: And they also established a lower bound when the group has no elements of order dividing k. That lower bound is proportional to n divided by k, and this shows a clear distinction based on the group's structure.

Kolya: I just want to say that from a probabilistic standpoint, the whole thing hinges on getting that new upper bound for the independence number of those random Cayley sum hypergraphs right. If that number estimate is off by even a little bit, the whole probability argument falls apart.

Ada: Exactly. And they also pointed out their own limitation, which is that they rely on showing the existence of a small non-k-fold sumset using bounds derived from Theorem one point five and Lemma four point nine to prove the main result <ref:2610.08629#pg3>. They are not establishing a general method for finding these non-sumsets in any arbitrary setting, just for this specific context of random Cayley graphs.

Emmy: So they're very precise about where their proof stops, which is important because it tells us what kind of structure they can guarantee results about without needing a more general framework.

Ada: It’s a solid piece of work showing how to use random constructions to tackle hard questions in additive combinatorics involving k-fold sums, and the Random Cayley sum hypergraphs and k-fold sumsets is the paper that lays out these specific bounds for fk(Gamma) in this context.

Yonsei University · KAIST

math.CO, math.NT

Submitted: 2026-10-06

Updated: 2026-11-05

Comments: 21 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: fk(Γ) ≤ Oe(n(2k−1)/(4k−3)) holds for all finite abelian groups Γ and integers k ≥ 2 <ref:2610.08629#pg2> Additionally…

Key concepts

f_k(\Gamma)
This quantity represents the largest integer such that any subset of $\Gamma$ with size at least $n - f_k(\Gamma)$ is guaranteed to be a k-fold sumset. Essentially, it quantifies how much 'density' a set needs to achieve k-fold additive structure within the group.
k-fold sumset
A k-fold sumset of a set $A$ in $\Gamma$ is the set formed by taking all possible sums of $k$ elements from $A$, where repetition is allowed. For example, a 2-fold sumset involves sums of two elements ($a_1 + a_2$). The paper studies how large sets must be to guarantee such structures exist.
Random Cayley sum hypergraphs
These are probabilistic structures used in the proof. A Cayley graph/hypergraph is built based on the elements of the group $\Gamma$. By making it 'random,' researchers can use probabilistic arguments, like bounding its independence number, to show that large subsets must possess specific additive properties.
Probabilistic Method
This mathematical technique uses probability to prove the existence of an object with a certain property. The paper employs this method by showing that if a random set is chosen, there is a high probability that it contains a subset that cannot be represented as a k-fold sumset, thereby proving the required lower bound.

Terminology

Summary

fk(Γ) ≤ Oe(n(2k−1)/(4k−3)) holds for all finite abelian groups Γ and integers k ≥ 2 <ref:2610. p. 008629#pg2> Additionally, the lower bound fk(Γ) ≥ Ωe(n/k) holds if Γ has no nontrivial element of order dividing k <ref:2610. p. 008629#pg4> The proof relies on a new upper bound for the independence number of random Cayley sum hypergraphs <ref:2610. p. 008629#pg4>

Introduction to the Problem

The study of additive structures in a subset of a given abelian group has been of great interest <ref:2610.08629#pg2> For an integer k ≥ 2, the quantity fk(Γ) denotes the largest integer with the property that every subset of Γ of size at least Γ − fk(Γ) is a k-fold sumset <ref:2610. p. 008629#pg2> This paper extends a recent result of Alon and Pham to prove that fk(Γ) ≤ Oe(n(2k−1)/(4k−3)) holds for all finite abelian groups Γ and integers k ≥ 2, where n = Γ <ref:2610. p. 008629#pg2>

Upper Bound Derivation

The upper bound of Theorem 1.3 is established by proving the existence of a large set that is not a k-fold sumset by a probabilistic argument <ref:2610. p. 508629#pg2> This involves showing that for a p-random subset S1 with p < 1/2, there exists a small S2 such that A = Γ(S1 ∪ S2) is not a k-fold sumset <ref:2610. p. 808629#pg4> The independence number of the Cayley sum hypergraph HS1 is at most O(p(-3/2)) with high probability <ref:2610. p. 408629#pg4>

Lower Bound Proof via Probabilistic Method

The lower bound fk(Γ) ≥ Ωe(n/k) holds if Γ has no nontrivial element of order dividing k <ref:2610.08629#pg4> This is proven by finding a set A from a collection of random sets whose probability of any k-fold sum of its elements in the set lying in Γ¬F is maximized <ref:2610. p. 508629#pg4> The claim that for each g ∈ Γ¬F, there exist more than 10k cubed log n pairs (a(i)1, · · ·, a(i)k) ∈ C k such that a(i)1 + · · · + a(i)k = g with probability at least 1 − o(1/n2) <ref:2610. p. 508629#pg8>

Existence of Small Non-Sumsets

The existence of a small non-k-fold sumset is proven by bounding the k-partite hole number of a random Cayley hypergraph <ref:2610.08629#pg4> The probability that there exists a k-partite hole of size s in HS is bounded by (9) <ref:2610. p. 208629#pg19> This leads to the conclusion that there exists a subset of Γ of size at least n − O(n(2k−1)/4k−3 log n(5k/2)) which cannot be represented as a k-fold sumset <ref:2610. p. 108629#pg20>

Conjectures and Future Directions

The authors conjecture that the asymptotic behavior of the threshold fk(Γ) will match that of the lower bound, stating that for all integer k ≥ 2 and a finite abelian group Γ of size n without a nontrivial element of order dividing k, it holds that fk(Γ) = Θ(e(n/k)) <ref:2610.08629#pg6>

References

[1] N. Alon, Large sets in finite fields are sumsets, J. p. 5 Number Theory 126 (2007), no. p. 0 1, 110–118 <ref:2610. p. 008629#pg3>

[3] N. Alon and H. p. 0 T. Pham, Random cayley graphs and random sumsets, 2025, arXiv:2509. p. 102561 <ref:2610. p. 008629#pg5>

[4] N. Alon and J. p. 0 H. Spencer, The probabilistic method, fourth ed. p. 2, Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc. p. 0, Hoboken, NJ, 2016 <ref:2610. p. 008629#pg5>

[5] J. Balogh, Y. Lee, and A. p. 0 Methuku, On d-fold sumsets: Containers, random cayley hypergraphs, and arithmetic progressions. p. 0, In preparation <ref:2610. p. 008629#pg6>

[6] J. Balogh, H. Liu, and M. p. 0 p. 0 Sharifzadeh, The number of subsets of integers with no k-term arithmetic progression, arXiv:1605. p. 103172, 2016 <ref:2610. p. 008629#pg5>

[7] J. Balogh, H. Liu, and M. Sharifzadeh, The number of subsets of integers with no k-term arithmetic progression, Int. p. 0 Math. Res. Not. IMRN (2017), no. 20, 6168–6186 <ref:2610. p. 008629#pg5>

[8] M. Campos, G. Dahia, and J. P. Marciano, On the independence number of sparser random Cayley graphs, J. p. 1 Lond. Math. Soc., (2) 110 (2024), no. 6, Paper No. p. 1, e70041 <ref:2610. p. 008629#pg9>

[9] D. Conlon, J. Fox, H. T. Pham, and L. p. 0 Yepremyan, On the clique number of random cayley graphs and related topics, 2024 <ref:2610. p. 108629#pg10>

[10] E. S. Croot, III and V. F. Lev, Open problems in additive combinatorics, Additive combinatorics, CRM Proc. p. 0 Lecture Notes, vol., 43, Amer. Math. Soc., Providence, RI, 2007 <ref:2610. p. 008629#pg11>

[11] G. A. Freiman, On the addition of finite sets, Dokl. p. 0 Akad. Nauk SSSR 158 (1964), 1038–1041 <ref:2610. p. 008629#pg3>

[12] B. Green, On the chromatic number of random Cayley graphs, Combin. p. 1 Probab. Comput., 26 (2017), no. 2, 248–266 <ref:2610. p. 008629#pg4>

[13] B. Green, Essay submitted for the smith’s prize, Cambridge University (2001) <ref:2610. p. 008629#pg4>

[14] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. p. 2 Amer. Statist. Assoc., 58 (1963), 13–30 <ref:2610. p. 008629#pg5>

[15] Y. Zhao, Probabilistic methods in combinatorics, 2022 <ref:2610. p. 008629#pg5>

--- Page 1 ---

Random Cayley sum hypergraphs and k-fold sumsets

Jihyo Chae∗ Hyunwoo Lee†

October 7, 2026

Abstract

We denote by fk(Γ) the largest integer with the property that every subset of a finite abelian group Γ of size at least Γ − fk(Γ) is a k-fold sumset <ref:2610.08629#pg2> Extending a recent result of Alon and Pham, we prove that fk(Γ) ≤ Oe(n(2k−1)/(4k−3)) holds for all finite abelian groups Γ and integers k ≥ 2, where n = Γ <ref:2610. p. 008629#pg2> Additionally, we also show that the lower bound fk(Γ) ≥ Ωe(n/k) holds if Γ has no nontrivial element of order dividing k <ref:2610. p. 008629#pg4> Our upper bound improves a previous result of Balogh, Liu, and Sharifzadeh, and recovers the bound of Alon and Pham in the case k = 2 <ref:2610. p. 008629#pg2> The proof relies on a new upper bound for the independence number of random Cayley sum hypergraphs, which may be of independent interest <ref:2610. p. 008629#pg4>

  1. Introduction

The study of additive structures in a subset of a given abelian group has been of great interest <ref:2610.08629#pg2> In particular, analyzing the behavior of sets with a given additive structure from multiple perspectives has led to the development of various problems in additive combinatorics, most of which concern sumsets in an additive group <ref:2610. p. 008629#pg2> For a given abelian group Γ and its subset A ⊆ Γ, we define the sumset of A as the set a1 + a2: a1, a2 ∈ A ⊆ Γ and denote as A + A or 2A <ref:2610. p. 008629#pg2> Similarly, for an integer k ≥ 2, we define k-fold sumset of A as the set P i∈[k] ai: ai ∈ A and denote as kA <ref:2610. p. 008629#pg2> An important quantity related to the additive structure of a set is the doubling constant, defined as the ratio 2A A for a given finite set A ⊆ Γ <ref:2610. p. 008629#pg2> The fundamental theorem that connects the doubling constant and the additive structure of the set is Freiman’s theorem [11], which says that if a subset A has a small doubling constant, then A contains a rich additive structure, such as arithmetic progressions <ref:2610. p. 008629#pg2> Since (k-fold) sumsets play a central role in additive combinatorics, it is natural to ask the size and number of sumsets in a given group <ref:2610. p. 008629#pg2> One observation of Green [13] was that it is easier to find a representation of the form S = A + A whenever S is small <ref:2610. p. 108629#pg2> It was therefore natural to ask whether all large sets in a finite group are sumsets <ref:2610. p. 108629#pg2> We consider a higher uniformity version of Green’s question <ref:2610. p. 108629#pg2> For an integer k ≥ 2, denote by fk(Γ) the largest integer with the property that every subset of Γ of size at least Γ − fk(Γ) is a k-fold sumset <ref:2610. p. 008629#pg2> More than twenty years ago, Green [10, 13] showed that the bound f2(Zp) ≥ Ω(log p) holds for all sufficiently large prime p, and consequently raised a problem to determine the value f2(Zp) <ref:2610. p. 108629#pg2> Later, Alon [1] improved the lower bound to f2(Zp) ≥ Ω˜p(1/2) and Green and Gowers [12], and Alon [1] provided the upper bound f2(Zp) ≤ O˜(p(2/3)) <ref:2610. p. 108629#pg2> Recently, the upper bound was considerably improved and extended to every finite abelian group as follows. p. 1

Theorem 1.1 (Alon–Pham [3]). p. 0 For all finite abelian group Γ of order n, we have f2(Γ) ≤ Oe(n3/5) <ref:2610. p. 108629#pg3> For k-fold sumsets, the previous best known upper bound of fk(Zp) is obtained by Balogh, Liu, and Sharifzadeh in the appendix from the arXiv version of [7] <ref:2610. p. 108629#pg2>

Theorem 1.2 (Balogh–Liu–Sharifzadeh [6]). p. 0 For all prime p and integer k ≥ 2, we have fk(Zp) ≤ O(p k/(2k−1)) <ref:2610. p. 108629#pg2> In this paper, we obtain a polynomial improvement of Theorem 1. p. 12 by extending the upper bound of Theorem 1. p. 11 to all k, and also provide a lower bound as follows. p. 1

Theorem 1.3. For all integer k ≥ 2 and a finite abelian group Γ of n, we have fk(Γ) ≤ Oe(n(2k−1)/(4k−3)) <ref:2610. p. 008629#pg2> If Γ has no nontrivial element of order dividing k, then we also have fk(Γ) ≥ Ωe(n/k) <ref:2610. p. 008629#pg4> The main idea in the proof of Theorem 1. p. 11 was to use an improved upper bound on the independence number of a random Cayley sum graph <ref:2610. p. 108629#pg4>

Preliminaries

Throughout the remaining paper, we assume Γ to be a finite abelian group of order n, and all logarithms are taken to base 2 <ref:2610.08629#pg5>

Probabilistic Inequalities

In the proof of our main theorems, we use several concentration inequalities <ref:2610.08629#pg5> Lemma 2. p. 2 p. 2 p. 21 (Hoeffding’s inequality) <ref:2610. p. 208629#pg5> Lemma 2.2 (Janson’s Inequality) <ref:2610. p. 308629#pg5> Lemma 2.3 (Paley–Zygmund Inequality) <ref:2610. p. 308629#pg5>

Discrete Fourier Analysis

Both of the proofs of Theorem 1.1 and our main theorems use the Fourier analytic method <ref:2610. p. 308629#pg6> Definition 2. p. 2 p. 25 (Fourier transform) <ref:2610. p. 308629#pg6> Definition 2.6 (Convolution) <ref:2610. p. 008629#pg6> Proposition 2. p. 47 (Fourier identities) <ref:2610. p. 408629#pg6>

Approach of Alon–Pham

The approach of Alon and Pham establishes a cover for the collection S:= A + A: A ⊆ Γ of small complexity consisting of sets that are dense in each S in some sense <ref:2610.08629#pg6> The authors overcome difficulties by establishing sufficiently strong inequalities for sums of products in the frequency domain <ref:2610. p. 408629#pg6>

Large Sets as k-fold Sumsets

The lower bound of Theorem 1.3 is proved via the probabilistic method <ref:2610. p. 208629#pg4> This involves showing that for each g ∈ Γ¬F, there exist more than 10k cubed log n pairs (a(i)1, · · ·, a(i)k) ∈ C k such that a(i)1 + · · · + a(i)k = g with probability at least 1 − o(1/n2) <ref:2610. p. 508629#pg8>

Conclusion

The paper concludes by showing the existence of a large set that is not a k-fold sumset by a probabilistic argument <ref:2610.08629#pg20> The final result shows that there exists a subset of Γ of size at least n − O(n(2k−1)/4k−3 log n(5k/2)) which cannot be represented as a k-fold sumset of Γ <ref:2610. p. 5

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Enhanced ability to analyze additive structures in large finite abelian groups by leveraging results on k-fold sumsets, allowing AI to predict whether a large subset of a group is likely a k-fold sumset with high probability based on its size and group structure.

  2. Development of algorithms that utilize the Fourier analytic method for approximating convolutions in high uniformity settings, enabling the AI to efficiently search for subsets exhibiting specific additive properties like small doubling constants.

  3. Implementation of probabilistic methods, including Janson's inequality and Paley-Zygmund inequality, to provide rigorous lower bounds on the independence number of random Cayley sum hypergraphs with high confidence.

  4. Capability to construct sparse covers for families of sets based on the covering lemma generalization (Lemma 4.5), allowing the AI to find subsets that are guaranteed to contain a structured set A-ell within a larger target set A1 + · · · + Ak.

  5. Automated proof generation for theorems concerning the existence of small non-k-fold sumsets by applying the probabilistic bound derived from Theorem 1.5 and Lemma 4.9, enabling the AI to identify subsets that cannot be represented as k-fold sumsets of a random set with high probability.

Sources

Related papers