Restricted sumsets in multiplicative subgroups

This paper proves that the set of nonzero squares in a finite field $\mathbb{F}_q$ (for odd $q>13$) cannot be expressed as a restricted sumset $A \hat{+} A$, while also extending these results to general multiplicative subgroups and perfect powers, and establishing an analogue of the van Lint-MacWilliams conjecture for restricted sumsets.

The Gist

Imagine you have a giant, magical box filled with numbers. This isn't just any box; it's a Finite Field, a world where the numbers wrap around like a clock. If you keep adding 1, eventually you hit a limit and start over at 0.

In this paper, the author, Chi Hoi Yip, is playing a game with these numbers. He's looking at a specific subset of numbers called Multiplicative Subgroups. Think of these as "special clubs" within the number world. For example, the "Club of Squares" contains only numbers that are the result of multiplying a number by itself (like 1, 4, 9, 16...).

The Big Question: Can You Build the Club from Scratch?

The central mystery the paper tackles is this: Can you take a random group of numbers, mix them together in pairs, and accidentally recreate one of these "special clubs" perfectly?

In math speak, if you have a set $A$, and you add every distinct pair of numbers in $A$ together (this is called a Restricted Sumset), can the result be exactly the set of all squares (or other special clubs)?

The author proves a surprising answer: No, you can't.

Here is the breakdown of his findings using simple analogies:

1. The "Square" Puzzle (The Main Result)

Imagine you have a bag of Lego bricks (your set $A$). You are only allowed to snap two different bricks together to make a new shape. The author asks: "Can you snap your bricks together in every possible unique way to build exactly the set of all perfect squares?"

• The Verdict: If the world of numbers is big enough (specifically, if the "clock" has more than 13 hours), it is impossible. You cannot build the set of squares just by adding pairs of other numbers.
• Why it matters: This solves a long-standing puzzle proposed by a mathematician named Sárközy. It's like proving you can't build a perfect circle out of straight sticks, no matter how many sticks you have.

2. The "Sidon Set" Detective Work

To prove this, the author had to act like a detective. He realized that if such a set $A$ did exist, it would have to be incredibly special. It would have to be a Sidon Set.

• What is a Sidon Set? Imagine a group of people where every pair of people has a unique handshake. If Person A shakes hands with Person B, no other pair (C and D) can have the exact same handshake combination.
• The Discovery: The author proved that if you could build the special club by adding pairs, your starting group would have to be a Sidon Set. But then, he showed that the math simply doesn't add up for large numbers. The "handshakes" would eventually overlap or miss the target, making the perfect construction impossible.

3. The "Shadow" of the Club (Upper Bounds)

The paper also asks a slightly different question: "What is the largest group of numbers you can pick so that when you add them in pairs, they never land outside the special club?"

• The Analogy: Imagine the special club is a VIP lounge. You want to invite a group of people such that whenever any two of them meet, they stay inside the VIP lounge. How big can your guest list be?
• The Result: The author found a strict limit. The size of your guest list cannot exceed the square root of the total number of people in the city. If you try to invite more, someone will inevitably step out of the lounge.
• The "Perfect" Guest List: Interestingly, if the city size is a perfect square, there is a specific, elegant way to fill the lounge to the brim: by inviting everyone from a smaller, "sub-city" (a subfield). This connects to a famous old conjecture by van Lint and MacWilliams, which the author successfully updated for this new type of problem.

4. The Integer Mystery (Erdős and Moser)

Finally, the paper looks at the "real world" numbers (1, 2, 3...) instead of the wrapping clock numbers.

• The Question: Can you find a list of integers where the sum of any two different numbers is a perfect square? (e.g., $1+3=4$,$3+6=9$, etc.)
• The Result: Mathematicians have found lists of 6 such numbers, but no one knows if 7 exist. The author uses his new tools to prove that even if such a list exists, it can't be very long. As the numbers get bigger, the length of such a list grows very slowly—only logarithmically. It's like saying, "You can find a few friends who all fit together perfectly, but you'll never find a whole stadium of them."

The Takeaway

This paper is a masterclass in impossibility. It tells us that nature (or mathematics) has strict rules about how numbers can combine. You cannot accidentally stumble upon a perfect structure (like the set of squares) just by randomly adding pairs of numbers together. If you try, the math will break down, the "handshakes" will collide, and the structure will crumble.

The author didn't just say "it's impossible"; he built a new set of mathematical tools (using things called hyper-derivatives, which are like super-powered calculators for polynomials) to prove exactly why it's impossible and how close you can get before hitting a wall.

Technical Summary

1. Problem Statement and Motivation

The paper addresses the problem of additive decompositions within multiplicative subgroups of finite fields, specifically focusing on restricted sumsets.

• Context: A celebrated conjecture by Sárközy posits that for a sufficiently large prime $p$, the set of nonzero squares $S_2 \subset \mathbb{F}_p$ cannot be written as a sumset $A+B$ where $|A|, |B| \ge 2$. This remains largely open.
• Specific Focus: The author investigates the restricted sumset analogue of this problem. For a set $A$, the restricted sumset is defined as $A \hat{+} A = \{a+b : a, b \in A, a \neq b\}$.
• Core Question: Can the set of nonzero squares (or more generally, a multiplicative subgroup $S_d$ of index $d$) in a finite field $\mathbb{F}_q$ be represented exactly as a restricted sumset $A \hat{+} A$?
• Secondary Motivation: The paper also addresses a question by Erdős and Moser regarding integers: Do there exist arbitrarily large sets of integers such that the sum of any two distinct elements is a perfect $d$-th power? The paper provides improved upper bounds for the size of such sets.

2. Methodology

The proofs rely heavily on Stepanov's method (the polynomial method) combined with hyper-derivatives (Hasse derivatives) and character sum estimates.

• Hyper-derivatives: The author utilizes the properties of hyper-derivatives $E^{(n)}(f)$ to analyze the multiplicity of roots of carefully constructed auxiliary polynomials. This allows for precise counting of solutions to equations involving sums of elements in $A$.
• Auxiliary Polynomials: The core technique involves constructing a polynomial $f(x)$ whose roots correspond to elements of $A$. By analyzing the degree of $f(x)$ and the multiplicity of its roots (derived from the condition $A \hat{+} A \subseteq S_d$), the author derives contradictions or structural constraints on the size of $A$.
• Character Sums: Standard double character sum estimates are used to establish initial upper bounds on $|A|$ (e.g., $|A| \lesssim \sqrt{q}$).
• Probabilistic and Number Theoretic Tools:
  • Kummer's Theorem: Used to analyze binomial coefficients modulo $p$ to determine when certain conditions hold for subsets of primes.
  • Uniform Distribution: The equidistribution of sequences modulo 1 (via Bergelson et al.) is used to estimate the density of primes for which a decomposition might exist.
  • Siegel's Theorem: Applied to Diophantine equations arising from the structural constraints of the sets.
  • Gallagher's Larger Sieve: Used in the integer case to bound the size of sets with restricted sumsets in perfect powers.

3. Key Contributions and Results

A. Non-existence of Restricted Sumset Decompositions for Squares

Theorem 1.1: If $q > 13$ is an odd prime power, the set of nonzero squares $S_2 \subset \mathbb{F}_q$ cannot be written as $A \hat{+} A$ for any $A \subset \mathbb{F}_q$.

• Significance: This extends a result by Shkredov (who proved it for prime fields $p > 13$) to all odd prime powers. The author's proof is distinct from Shkredov's, avoiding reliance on perfect difference sets, which are not well-understood for general prime powers.
• Exception: The paper identifies that for $q \in \{3, 7, 13\}$, such decompositions do exist.

B. Structural Characterization (Theorem 1.4)

If $A \hat{+} A = S_d$, the set $A$ must possess very rigid structure:

• $A$ is essentially a Sidon set (all pairwise sums are distinct).
• Specific constraints on the size $|A|$ and the field size $q$ are derived. For instance, if $|A|$ is odd, $q = d|A|(|A|-1)/2 + 1$.
• If $|A|$ is even, $|A|$ is tightly constrained by the fractional part of $\sqrt{(q-1)/2d}$.

C. General Multiplicative Subgroups ($S_d$)

The paper extends the non-existence results to subgroups of index $d \ge 3$:

• Theorem 1.2 (Probabilistic Result): For a fixed $d \ge 3$, the set of primes $p \equiv 1 \pmod d$ for which $S_d(\mathbb{F}_{p^s})$ admits a decomposition $A \hat{+} A$ has a lower asymptotic density of at least $1 - \frac{(d-1)^r}{4d^r}$(where$r = \lceil s/2 \rceil - 1$). As$s \to \infty$, the density of "good" primes (where decomposition is impossible) tends to 1.
• Theorem 1.3: If $d = 2k^2$ and $q$ is an even power of a prime $p \equiv 1 \pmod d$, then $S_d$ cannot be written as $A \hat{+} A$.

D. Upper Bounds and Graph Theory Connections

The paper establishes sharp upper bounds for sets $A$ where $A \hat{+} A \subseteq S_d \cup \{0\}$:

• Theorem 1.6: For prime fields, $|A| \le \sqrt{2(p-1)/d} + O(1)$. This improves upon previous bounds by a factor of $\sqrt{2}$.
• Theorem 1.7: For square fields $q$, if $A \hat{+} A \subseteq S_d \cup \{0\}$, then $|A| \le \sqrt{q}$. Equality holds if and only if $d \mid (\sqrt{q}+1)$ and $A$ is a scaled subfield $\alpha \mathbb{F}_{\sqrt{q}}$.
• Graph Theory Interpretation: These results are reformulated as bounds on the clique number of Cayley sum graphs (specifically $d$-Paley sum graphs).
  • Significance: Theorem 1.7 provides an analogue of the van Lint-MacWilliams conjecture (originally for difference sets) in the context of restricted sumsets. It is noted as the first instance of an Erdős-Ko-Rado (EKR) type theorem for a family of Cayley sum graphs, which are generally harder to analyze than standard Cayley graphs due to the lack of vertex transitivity.

E. Integer Applications (Erdős-Moser Problem)

Theorem 1.8: If $A \subset \{1, \dots, N\}$ and $A \hat{+} A$ is contained in the set of perfect $d$-th powers, then:
$$|A| \le (2 + o(1)) \frac{\phi(d)}{d} \log N$$

• Significance: This improves upon previous bounds by Rivat, Sárközy, and Stewart (which were $\approx 36 \log N$ for squares) and Gyarmati (which were $\approx 4d \log N$). The new bound is asymptotically optimal up to the constant factor.

4. Significance and Impact

1. Resolution of a Restricted Sumset Conjecture: The paper effectively settles the restricted sumset version of Sárközy's conjecture for squares in finite fields, showing that such decompositions are impossible for large $q$.
2. Methodological Innovation: The proof introduces a refined application of Stepanov's method using hyper-derivatives to handle the "distinct elements" constraint ($a \neq b$) in restricted sumsets, a problem that standard sumset techniques struggle with.
3. Graph Theory Advancement: By linking restricted sumsets to cliques in Cayley sum graphs, the paper bridges additive combinatorics and spectral graph theory. The proof of the EKR analogue for Cayley sum graphs is a significant theoretical contribution, as these graphs lack the symmetry of standard Cayley graphs.
4. Integer Bounds: The improvement on the Erdős-Moser problem for integers provides the best known upper bounds for sets with restricted sumsets in perfect powers, utilizing the finite field results via the Gallagher sieve.

In summary, the paper provides a comprehensive analysis of restricted sumsets in multiplicative subgroups, combining deep algebraic techniques with probabilistic number theory to resolve long-standing structural questions and improve quantitative bounds in both finite fields and the integers.