🔢 mathematics

Adjacent comparison bounds and extremal sets for Ruzsa numbers

Motivated by a 2024 conjecture, this paper establishes that the difference between consecutive Ruzsa numbers is bounded by 144, provides nontrivial bounds for the size of extremal sets, and computes exact values of these numbers for all moduli up to 100.

Original authors: Yuchen Ding, Huixi Li, Junfeng Li, Wei Niu, Xiamiao Zhao

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuchen Ding, Huixi Li, Junfeng Li, Wei Niu, Xiamiao Zhao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.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 party in a circular room with $m$ numbered seats. You invite a group of guests (a subset $A$ ) to stand in specific seats. The rule of the party is simple: every single seat in the room must be "covered" by at least one pair of guests standing next to each other (or across the room) whose seat numbers add up to that seat's number.

However, there's a catch: you don't want any seat to be too crowded. If too many pairs of guests claim the same seat number, it gets chaotic.

The Ruzsa Number ( $R_m$ ) is the "crowd limit." It asks: What is the smallest number $r$ such that we can arrange our guests so that every seat is covered at least once, but no seat is claimed by more than $r$ pairs?

The paper by Ding, Li, Li, Niu, and Zhao is a detective story about finding this perfect crowd limit for different room sizes ( $m$ ) and understanding how the limit changes when you add just one more seat to the room.

Here is a breakdown of their findings using everyday analogies:

1. The "Neighborly" Rule (Adjacent Comparison)

For a long time, mathematicians wondered: If you have a room with $m$ seats and a room with $m+1$ seats, how different can the crowd limits be?

The Old Guess: Some thought the limit would never jump by more than 1. (e.g., if a 36-seat room needs a limit of 6, a 37-seat room would need 5, 6, or 7).
The Reality Check: The authors found a glitch in the old data. For a 36-seat room, the limit is 6. But for a 37-seat room, the limit drops to 4. That's a jump of 2, breaking the "never more than 1" rule.
The New Discovery: While the "jump of 1" rule isn't perfect, the authors proved that the jump can never be too huge. They showed that the difference between the crowd limit of room $m$ $m$ and room $m+1$ $m + 1$ is never more than 144.
- Analogy: Imagine you are climbing a staircase where the step height changes. You can't jump from the ground to the roof in one step, but you also can't take a step that is 1,000 feet high. The authors proved the step height is capped at 144 feet.

2. The "Perfect Party" Size (Extremal Sets)

The paper also looks at the size of the guest list ( $|A|$ ).

The Balance: If you have too few guests, you can't cover all the seats. If you have too many, you create too much chaos (high $R_m$ ).
The Finding: The authors calculated exactly how many guests are needed for rooms up to size 100. They found that for large rooms, the "sweet spot" for the guest list size is roughly the square root of the number of seats.
The Limit: They proved that for any large room, the number of guests needed to keep the chaos under control (specifically under the limit of 192) will never exceed roughly $\sqrt{191 \times \text{seats}}$ .

3. The "Magic Number" 6

One of the most surprising discoveries is a pattern in the data.

The Observation: When the room gets big enough (specifically, 40 seats or more), the "crowd limit" ( $R_m$ ) seems to settle down to the number 6.
The Conjecture: The authors suspect that for any room with 40 or more seats, you can always arrange the guests so that no seat is claimed more than 6 times. They have verified this for every room size up to 100.
- Analogy: It's like finding that no matter how big your city gets, you only ever need 6 traffic lights at any intersection to keep traffic flowing smoothly, provided the city is large enough.

4. How They Did It (The Certificate Hunt)

The authors didn't just guess; they ran a massive computer search.

The Process: They acted like digital architects. For each room size, they tried to build a guest list that worked.
The "Certificate": If they found a list where every seat was covered and no seat had more than 6 pairs, that list became a "certificate" proving the limit is 6.
The Search: They used supercomputers to test millions of combinations. For smaller rooms, they proved it was impossible to do it with a limit of 5, confirming that 6 was indeed the minimum.

5. Open Questions (The Unfinished Party)

The paper ends by asking new questions, like:

The Gap Problem: If you have a huge room, is it possible to have a huge empty gap between guests? (They proved the gap can't be more than half the room size).
The Even/Odd Problem: Do guests tend to sit in even-numbered or odd-numbered seats? (They found that for large rooms, the mix is almost perfectly balanced).
The "Exactly Two" Problem: Is it possible to arrange guests so that no seat is claimed by exactly two pairs? (They proved that if the guest list is small enough, you must have some seats claimed by exactly two pairs).

Summary

In short, this paper is a deep dive into the mathematics of packing and covering. It answers the question: "How efficiently can we cover a circle with sums of pairs?"

They fixed a small error in previous calculations.
They proved the "crowd limit" doesn't fluctuate wildly between room sizes.
They found that for large rooms, the limit stabilizes at 6.
They provided a massive table of exact solutions for rooms up to size 100, serving as a reference for future mathematicians.

The work is purely theoretical—it's about the structure of numbers and patterns, not about physical applications like traffic or biology, though the logic of "efficient covering" is a fundamental concept in many fields.

Technical Summary: Adjacent Comparison Bounds and Extremal Sets for Ruzsa Numbers

Problem Definition
Let $m$ be a positive integer and $\mathbb{Z}_m$ the residue class ring modulo $m$ . For a subset $A \subset \mathbb{Z}_m$ , let $\sigma_A(n)$ denote the number of ordered pairs $(a, a') \in A^2$ such that $a + a' \equiv n \pmod m$ . The Ruzsa number $R_m$ is defined as the least integer $r$ such that there exists a subset $A \subset \mathbb{Z}_m$ satisfying $1 \le \sigma_A(n) \le r$ for all $n \in \mathbb{Z}_m$ . This concept is motivated by the Erdős-Turán conjecture on additive bases. Previous work established that $R_m$ is bounded by an absolute constant, with upper bounds improved over time from $C$ (Ruzsa) to $768$ (Tang and Chen), $5120$ (Tang and Chen), and finally $288$ (Chen). More recently, Ding and Zhao (2024) improved the upper bound to $R_m \le 192$ and conjectured that $|R_{m+1} - R_m| \le 1$ for all $m$ .

Methodology
The authors employ a combination of combinatorial comparison lemmas, analytic inequalities involving representation functions, and extensive computational verification.

Comparison Lemmas: The paper introduces a new comparison lemma (Lemma 3.2) establishing that $R_m \le 4R_{m+1}$ and $R_{m+1} \le 4R_m$ . This is achieved by constructing additive bases in $\mathbb{Z}_{m+1}$ from those in $\mathbb{Z}_m$ (and vice versa) using set translations and unions, then bounding the representation counts of the new sets.
Analytic Bounds: To estimate the size of extremal sets $A$ (where $1 \le \sigma_A(n) \le R_m$ ), the authors utilize the Lev-Sárközy inequality (Lemma 2.1). By analyzing the mean-square deviation of $\sigma_A(n)$ from a constant $c$ , they derive quadratic inequalities relating the cardinality $|A|$ to $m$ and $R_m$ .
Computational Verification: The authors perform a certificate-based search to determine exact values of $R_m$ $R_{m}$ for $m$ $m$ up to 100.
- For $m \le 45$ , they verify exactness by proving the non-existence of sets with representation bounds lower than the claimed $R_m$ .
- For $m > 45$ , they rely on a lower bound proof ( $R_m \ge 6$ ) and search for sets satisfying $\max \sigma_A(n) \le 6$ .
- The search utilizes a heuristic optimization procedure involving set translation, element replacement, and budgeted attempts to minimize representation defects.

Key Contributions and Results

Adjacent Comparison Bound (Theorem 1.1): The authors prove that for any positive integer $m$ , $|R_{m+1} - R_m| \le 144$ . This improves the trivial bound of $186$ (derived from $192 - 6$) using the new comparison lemma and the known upper bound $R_m \le 192$ .
Exact Values and Counterexamples: The paper provides a table of exact values for $R_m$ $R_{m}$ for all $2 \le m \le 100$ $2 \leq m \leq 100$ .
- The computation reveals that $R_{37} = 4$ and $R_{39} = 5$ .
- Specifically, $R_{36} = 6$ and $R_{37} = 4$ , which serves as a counterexample to the original Ding-Zhao conjecture ( $|R_{m+1} - R_m| \le 1$ ) for $m=36$ .
- The authors propose a revised conjecture: $|R_{m+1} - R_m| \le 1$ holds for all sufficiently large $m$ .
- They further conjecture that $R_m = 6$ for all $m \ge 40$ (Conjecture 2.3).
Bounds on Extremal Set Size (Theorem 1.2): For a sufficiently large $m$ and a set $A$ achieving the Ruzsa number, the authors derive nontrivial bounds for $|A|^2$ . Let $s = \lfloor R_m/2 \rfloor$ . The size satisfies:
$\left( s + \frac{1}{2} - \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s - \epsilon} \right)m \le |A|^2 \le \left( s + \frac{1}{2} + \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s + \epsilon} \right)m$
As a corollary, if $R_m = 6$ , then $|A| \le \sqrt{191m}$ .
Structural Properties: The paper investigates properties of the sets $A_m$ $A_{m}$ (subsets achieving $R_m$ $R_{m}$ ).
- Parity: Proposition 5.5 provides bounds on the proportion of even elements in $A$ when $m$ is even. If $R_m = 6$ , the proportion of even elements is bounded within $\approx 0.14$ of $1/2$ .
- Arithmetic Progressions: The paper defines $L_m$ as the maximum length of an arithmetic progression contained in any $A \in A_m$ . It is noted that $L_m \le R_m$ .
- Cardinality of $A_m$ : Proposition 5.6 establishes asymptotic bounds for the number of such sets, $|A_m|$ , showing $\frac{1}{2}\log m - C \le \log |A_m| \le \sqrt{191m} \log(\dots)$ .

Significance
The paper refines the understanding of the behavior of Ruzsa numbers, specifically addressing the stability of $R_m$ under adjacent modulus changes. By disproving the strict $|R_{m+1} - R_m| \le 1$ conjecture for small $m$ while providing strong evidence for its validity asymptotically, the authors clarify the interplay between algebraic structure (modulus properties) and combinatorial randomness. The provision of exact values up to $m=100$ substantially extends previous tables, and the derived bounds on the size of extremal sets offer new constraints for future research on additive bases in cyclic groups. The work also poses several open problems regarding the distribution of representation values, the structure of extremal sets, and the growth of the number of such sets.