Largest Sidon subsets in weak Sidon sets

This paper improves the known bounds for the constant $c_*$, which represents the minimum proportion of a Sidon subset guaranteed within any $(4,5)$-set of size $n$, by establishing that $\frac{9}{17} \le c_* \le \frac{4}{7}$ through a reformulated extremal problem and an explicit construction.

The Gist

Imagine you are hosting a party where everyone brings a unique number. The goal of the game is to avoid "accidental collisions."

In the world of math, specifically Additive Combinatorics, there are special groups of numbers called Sidon Sets. Think of a Sidon Set as a perfectly organized party where every possible pair of guests adds up to a unique total.

• If Guest A and Guest B bring numbers 2 and 5, their sum is 7.
• No other pair (like 3 and 4) is allowed to also sum to 7.
• Every single combination of two people must produce a unique "signature" sum.

The paper you provided tackles two big questions about these parties:

1. What happens if the party is almost perfect, but has a few small mistakes?
2. How many "perfect" guests can we always find inside a "messy" party?

Here is the breakdown of the paper's discoveries using simple analogies.

---

Part 1: The "Weak" Sidon Set (The Almost-Perfect Party)

The Concept:
Sometimes, a set of numbers is so close to being a Sidon set that it only fails one tiny rule.

• Sidon Set: All sums of any two numbers (even if they are the same person added to themselves, like $3+3$) are unique.
• Weak Sidon Set: All sums of two different people are unique. The only thing allowed to repeat is if someone adds their own number to themselves (e.g., $3+3$might equal$1+5$).

The Question:
Mathematicians Sárközy and Sós asked: "If we have a 'Weak Sidon' party of $n$ people, what is the guaranteed size of the largest 'perfect' Sidon subgroup we can find inside it?"

Imagine you have a messy room of $n$ people. You want to pick a group to sit in a corner where everyone is perfectly polite (no sum collisions). How big can that corner group be, even in the worst-case messy room?

The Discovery:
The authors, Jie Ma and Quanyu Tang, solved this completely. They proved that no matter how you arrange the messy party, you can always find a perfect subgroup that is roughly half the size of the original group.

• The Formula: If you have $n$ people, you can always find a perfect group of size $\lceil \frac{n+1}{2} \rceil$ (roughly $n/2$).
• The Analogy: Imagine a chaotic dance floor with 100 people. Even if they are dancing in a way that almost causes collisions, the authors proved you can always pick 51 people who are dancing in a perfectly collision-free pattern. You can't guarantee 52, but 51 is the magic number.

Why it matters:
Before this paper, mathematicians knew the limit existed but didn't know the exact number. This paper says, "It's exactly half."

---

Part 2: The (4, 5)-Set (The "Difference" Party)

The Concept:
The second part of the paper looks at a different kind of rule. Instead of looking at sums, this looks at differences (how far apart numbers are).

• A (4, 5)-set is a group where if you pick any 4 people, the distances between them must be very diverse.
• Specifically, out of the 6 possible distances between 4 people, at least 5 of them must be different. (If you have 4 people, there are 6 pairs. If 2 pairs have the same distance, you only have 5 unique distances. This set requires at least 5 unique distances).

The Question:
Erdős (a famous mathematician) asked: "If we have a (4, 5)-set of size $n$, how big of a perfect Sidon set can we guarantee to find inside it?"

The Discovery:
Previous mathematicians guessed the answer was somewhere between 50% and 60%.

• Old Lower Bound: At least $50.009%$ (very close to half).
• Old Upper Bound: At most $60%$.

The new paper tightens these bounds significantly:

• New Lower Bound: You can always find a perfect Sidon set of at least $9/17$ (about 53%) of the group.
• New Upper Bound: There exists a specific group where you cannot find a perfect Sidon set larger than $4/7$ (about 57%).

The Analogy:
Imagine a puzzle where you have a box of 100 tiles. You know the tiles are arranged in a specific "diverse distance" pattern.

• The authors proved you can always pull out a perfect subset of at least 53 tiles.
• They also built a specific "worst-case" puzzle where you can't pull out more than 57 perfect tiles.
• This narrows the "unknown zone" from a wide gap (50% to 60%) to a tight squeeze (53% to 57%).

How they did it:
To find the upper bound (the 57% limit), they used a computer to build a specific 14-person party that is "messy" enough to prevent any larger perfect group from forming. It's like finding a specific lock that only accepts keys up to a certain size.

---

The Big Picture: Why This is Cool

1. From "Maybe" to "Exactly": For the first problem, they moved from "it's probably around half" to "it is exactly half." This is a rare and satisfying result in math.
2. Tightening the Net: For the second problem, they didn't just guess; they used a mix of clever logic (hypergraphs, which are like 3D versions of maps) and computer power to squeeze the possible answers into a very small range.
3. The "Weak" vs. "Strong" Connection: The paper shows that even if you relax the rules of a perfect mathematical set (making it "weak"), you don't lose much. You can still salvage a huge chunk (half) of the structure.

In Summary:
This paper is like a master locksmith.

• Lock 1: They found the exact key size needed to open a "weak" lock (it's always half the size).
• Lock 2: They narrowed down the key size range for a "distance" lock from a wide interval to a very precise, small window.

It's a beautiful example of taking vague mathematical questions and answering them with surgical precision.

Technical Summary

Here is a detailed technical summary of the paper "Largest Sidon Subsets in Weak Sidon Sets" by Jie Ma and Quanyu Tang.

1. Problem Statement

The paper addresses two fundamental problems in additive combinatorics concerning the density of Sidon subsets within sets that are "close" to being Sidon but do not satisfy the strict Sidon condition.

Definitions:

• Sidon Set: A finite set $S \subset \mathbb{R}$ where all pairwise sums $x+y$ (with $x \le y$) are distinct.
• Weak Sidon Set: A finite set $A \subset \mathbb{R}$ where all pairwise sums $x+y$ (with $x < y$) are distinct. (Note: This allows $x+x$ to potentially equal $y+z$ for distinct $y,z$, provided $x \neq y, z$).
• $(4, 5)$-Set: A finite set $A \subset \mathbb{R}$ where every 4-element subset determines at least 5 distinct pairwise absolute differences.

Let $h(A)$ denote the size of the largest Sidon subset of $A$. The authors investigate two extremal functions:

1. $g(n)$: The minimum $h(A)$ over all weak Sidon sets $A$ of size $n$.
2. $f(n)$: The minimum $h(A)$ over all $(4, 5)$-sets $A$ of size $n$.

The Core Questions:

• Sárközy and Sós Problem: Does the limit $\lim_{n \to \infty} g(n)/n$ exist? If so, what is its value?
• Erdős Problem: What is the optimal constant $c^*$ such that every $(4, 5)$-set of size $n$ contains a Sidon subset of size at least $c^*n$? (i.e., $c^* = \lim_{n \to \infty} f(n)/n$).

2. Methodology

The authors employ a combination of extremal combinatorics, hypergraph theory, and constructive number theory.

A. Subadditivity and Limit Existence

To prove the existence of the limits $\gamma^* = \lim g(n)/n$ and $c^* = \lim f(n)/n$, the authors utilize Fekete's Lemma.

• They construct a "gluing" technique (Lemmas 3.3 and 3.6) to combine two disjoint sets $A$ and $B$ into a larger set $C = A \cup (qB + t)$ via affine transformations.
• By carefully choosing scaling factors $q$ and translations $t$, they ensure that:
  1. The resulting set $C$ preserves the weak Sidon or $(4, 5)$ property.
  2. The size of the largest Sidon subset satisfies $h(C) \le h(A) + h(B)$.
• This establishes the subadditivity of $g(n)$ and $f(n)$, proving the existence of the limits.

B. Hypergraph Reformulation (The A.P.-Hypergraph)

For the $(4, 5)$-set problem, the authors utilize the A.P.-hypergraph framework introduced by Gyárfás and Lehel.

• Definition: For a set $A$, the hypergraph $H(A)$ has vertex set $A$. An edge exists for every triple $\{x, y, z\}$ forming a 3-term arithmetic progression (3AP).
• Key Equivalence: For a weak Sidon set, a subset is Sidon if and only if it contains no 3-term arithmetic progression. Thus, $h(A) = \alpha(H(A))$ (the independence number).
• Structural Properties:
  • If $A$ is a $(4, 5)$-set, $H(A)$ is linear (edges intersect in at most one vertex) and $F_7$-free (does not contain a specific 7-vertex configuration).
  • The problem reduces to bounding the transversal number $\tau(H)$, since $\alpha(H) = n - \tau(H)$.

C. Constructive Lower Bounds

To determine exact values or tight bounds, the authors construct specific sets:

• For $g(n)$: They construct a specific family of weak Sidon sets $A_{2n+1}$ using powers of 2 and 3 ($2^{n-i}3^i$). They analyze the 3-adic valuations of sums to prove these sets are weak Sidon and determine their exact Sidon subset sizes.
• For $c^*$ (Upper Bound): They use computer-assisted search (aided by AI) to find a specific 14-point $(4, 5)$-set ($A_{base}$) with a small maximal Sidon subset.

3. Key Contributions and Results

Result 1: Exact Solution for Weak Sidon Sets

The authors completely resolve the Sárközy and Sós problem.

• Theorem: For all $n \ge 1$,
  $$g(n) = \left\lceil \frac{n+1}{2} \right\rceil$$
• Implication: The asymptotic density is exactly:
  $$\lim_{n \to \infty} \frac{g(n)}{n} = \frac{1}{2}$$
• Proof Strategy:
  • Lower Bound: Uses a known bound on the transversal number of 3-uniform hypergraphs ($4\tau \le n + m$) combined with the property that weak Sidon sets have at most$n-2$ edges in their A.P.-hypergraph.
  • Upper Bound: The explicit construction of $A_{2n+1}$ shows that for odd $n=2k+1$, the largest Sidon subset has size $k+1$, matching the formula.

Result 2: Improved Bounds for $(4, 5)$-Sets

The authors significantly improve the bounds for Erdős's constant $c^*$.

• Previous Bounds (Gyárfás & Lehel): $1/2 + \epsilon \le c^* \le 3/5$.
• New Bounds:
  $$\frac{9}{17} \le c^* \le \frac{4}{7}$$
  (Note: $9/17 \approx 0.529$and$4/7 \approx 0.571$).
• Lower Bound Improvement ($c^* \ge 9/17$):
  • They leverage the fact that $(4, 5)$-sets yield linear, $F_7$-free hypergraphs.
  • They apply a stronger transversal bound by Henning and Yeo ($17\tau \le 5n + 3m$) specifically for this class of hypergraphs, improving upon the previous estimate.
• Upper Bound Improvement ($c^* \le 4/7$):
  • They constructed a 14-element $(4, 5)$-set $A_{base} = \{0, 136, \dots, 1056\}$.
  • Exhaustive verification showed its largest Sidon subset has size 8.
  • Since $c^* = \inf f(n)/n$, the existence of this set implies $c^* \le 8/14 = 4/7$.

4. Significance

1. Resolution of Open Problems: The paper provides a complete answer to the Sárközy and Sós problem, a long-standing question in additive combinatorics, determining the exact asymptotic density of Sidon subsets in weak Sidon sets.
2. Refinement of Erdős's Conjecture: By narrowing the gap for the constant $c^*$ from a wide range to a tight interval ($0.529 \le c^* \le 0.571$), the paper significantly advances the understanding of the structure of$(4, 5)$-sets.
3. Methodological Innovation:
   • The paper demonstrates the power of combining hypergraph transversal theory with additive number theory.
   • It highlights the effective use of computer-assisted construction (specifically for finding the 14-point counterexample) combined with rigorous mathematical proof.
   • The explicit construction of the sets $A_{2n+1}$ using 3-adic valuations provides a new tool for generating weak Sidon sets with controlled arithmetic properties.
4. Structural Insights: The work clarifies the strict hierarchy between Sidon sets, $(4, 5)$-sets, and weak Sidon sets, and precisely quantifies how the "Sidon-ness" degrades as one moves from strict Sidon sets to these relaxed definitions.

In summary, Ma and Tang have not only solved a specific limit problem but also provided sharper bounds and deeper structural understanding of how Sidon sets behave within broader combinatorial classes.