🔢 mathematics

A solution to a strengthened conjecture of Bukh, van Hintum and Keevash on additive bases

This paper proves a strengthened conjecture by Bukh, van Hintum, and Keevash by establishing that for any basis $S$ of $\mathbb{R}^n$ , if $S+S \subseteq A+B$ and $|A| \le n-t$ , then $|B| \ge n+\binom{t+1}{2}$ , utilizing a short proof based on graph-theoretic edge contractions and a new coloring lemma over $\mathbb{F}_2^n$ .

Original authors: Zixiang Xu

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zixiang Xu

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

The Big Picture: Building a "Sum-Set" Puzzle

Imagine you have a giant box of LEGO bricks. In the world of math, this paper is about a specific puzzle involving additive bases.

Think of an "additive basis" as a special set of master bricks (let's call them Set S) that can be combined to build a specific list of target structures. The rule is simple: you can only build these targets by snapping two master bricks together (one from Set A and one from Set B).

The mathematicians in this story (Bukh, van Hintum, and Keevash) asked a question: If you are forced to use a very small number of bricks for Set A, how many bricks do you need for Set B to make sure you can still build all the required targets?

They guessed that if you shrink Set A, Set B has to grow in a very specific, predictable way. They also wondered if this rule holds true whether you are building with "rational" bricks (fractions) or "real" bricks (any number on the number line).

The Main Discovery

The author of this paper, Zixiang Xu, says: "Yes, the rule holds true, and here is the exact formula."

He proved that if you have a set of targets that requires every pair of master bricks to be built, and you restrict Set A to be small (specifically, if Set A has $n - t$ bricks), then Set B must have at least $n + \binom{t+1}{2}$ bricks.

The "Sharp" Part: The author also showed that this number is the absolute minimum possible. You cannot get away with fewer bricks in Set B; if you try, the puzzle breaks. It's like saying, "If you only have 3 tools to fix a car, you absolutely need at least 10 spare parts to finish the job. No more, no less."

How the Proof Works: The "Graph" and the "Coloring" Game

To prove this, the author didn't just do heavy algebra; he turned the problem into a game of connect-the-dots and coloring.

1. The Connection Map (The Graph)

Imagine you have a list of all the target structures you need to build (like $e_1+e_1$ , $e_1+e_2$ , etc.).

For every target, you pick one specific way to build it using a brick from Set A and a brick from Set B.
Now, draw a line connecting the A-brick to the B-brick.
You end up with a giant web of connections (a graph).

The author noticed something cool about the "diagonal" connections (where you combine a brick with itself, like $e_1+e_1$ ). If you look closely at these specific lines, they never form a loop. They look more like a family tree or a branching river system. This is a crucial clue because loops would mean the math is "redundant" or contradictory.

2. Smushing the Map (Edge Contractions)

Since those diagonal lines don't form loops, the author decided to "smush" them together. Imagine taking all the A-bricks and B-bricks involved in those diagonal pairs and gluing them into single super-nodes.

This shrinks the giant web into a smaller, simpler map.
The author counts how many nodes are left on this new, smaller map.

3. The Coloring Game

Now, the author assigns a "color" to every node on this smaller map.

The colors aren't just red or blue; they are based on a special mathematical "modulo" system (think of it like a clock face where numbers wrap around).
The rule is: If two nodes are connected by a line representing a target sum, their colors must differ by a specific amount.

The author then plays a counting game:

He knows how many "A-colors" are available (because Set A is small).
He knows that the "B-colors" must be diverse enough to cover all the required differences.
Using a clever lemma (a helper rule) about how many colors are needed to cover all possible pairs, he calculates the minimum number of B-bricks required.

The Result in Plain English

The paper proves that the "cost" of shrinking Set A is exactly what the conjecture predicted.

If you take away 1 brick from Set A, Set B needs to grow by a specific amount.
If you take away 2 bricks, Set B needs to grow even more.
This works whether you are using fractions or any real numbers.

The author's proof is described as "short" because, instead of getting lost in complex calculations, he used this visual "graph and color" strategy to see the structure of the problem clearly.

Summary

Think of this paper as solving a puzzle where you have to balance two teams of workers (Set A and Set B) to build a list of structures. The author proved that if you fire a few workers from Team A, you mathematically cannot get away with hiring just a few extra workers for Team B. You need a specific, larger number of workers to keep the construction going, and he provided the exact formula for that number.

Technical Summary: A Solution to a Strengthened Conjecture on Additive Bases

Problem Statement
This paper addresses a problem in additive combinatorics concerning the efficiency of generating sets via sums, specifically within the context of "change-of-domain" problems. The work builds upon a conjecture by Bukh, van Hintum, and Keevash regarding additive bases in $\mathbb{Q}^n$ . Their original conjecture posited that if $A, B \subseteq \mathbb{Q}^n$ contain all sums of the form $e_i + e_j$ (where $1 \le i \le j \le n$ and $e_k$ are standard basis vectors), then $|A| + |B| \ge 2n$ .

They further proposed a strengthened, refined version: if $|A| = n - t$ , then $|B| \ge n + \binom{t+1}{2}$ . Bukh subsequently asked whether these bounds hold for an arbitrary basis $S$ of $\mathbb{R}^n$ (rather than just the standard basis of $\mathbb{Q}^n$ ) under the condition $S + S \subseteq A + B$ .

Methodology
The author, Zixiang Xu, employs a graph-theoretical framework combined with algebraic coloring arguments to prove the conjecture over $\mathbb{R}^n$ . The proof proceeds through the following steps:

Reduction to Standard Basis: The problem is reduced to the case where $S$ is the standard basis of $\mathbb{R}^n$ via an invertible linear map, which preserves cardinalities and sumset inclusions.
Graph Construction: A bipartite multigraph $G$ is constructed with left vertices representing distinct elements of a subset $A_0 \subseteq A$ and right vertices representing distinct elements of $B_0 \subseteq B$ . Edges correspond to specific representations of $e_i + e_j = a_{ij} + b_{ij}$ .
Diagonal Edge Contraction: The author defines a map $\phi$ from vertices to $\mathbb{R}^n$ (mapping left vertices to $a$ and right vertices to $-b$ ). A key claim establishes that the subgraph formed by "diagonal" edges (representing $e_i + e_i$ ) is a forest. Contracting these edges yields a new graph $H$ with $|V(H)| = |A_0| + |B_0| - n$ .
Coloring and Quotient Groups: Vertices of $H$ are colored using elements of the quotient group $\mathbb{R}^n / 2\mathbb{Z}^n$ . The coloring is well-defined because the difference between $\phi$ -values of vertices connected by diagonal edges lies in $2\mathbb{Z}^n$ .
Combinatorial Lemma: The proof relies on a new coloring lemma (Lemma 2.2) over the vector space $\mathbb{F}_2^n$ . This lemma states that if a set $X$ of size at most $n-u$ and a set $C$ satisfy $D_n \subseteq X - C$ (where $D_n$ is the set of pairwise sums of distinct basis vectors), then $|C| \ge n + \binom{u}{2}$ . The proof of this lemma involves folding the problem into a subspace and analyzing the dimension of the span of $X$ .

Key Contributions and Results
The paper provides a complete proof of the strengthened conjecture over $\mathbb{R}^n$ .

Theorem 1.1: Let $S$ be a basis of $\mathbb{R}^n$ , and let $A, B \subseteq \mathbb{R}^n$ such that $S + S \subseteq A + B$ . If $|A| \le n - t$ for an integer $0 \le t \le n-1$ , then $|B| \ge n + \binom{t+1}{2}$ .
Sharpness: The bound is shown to be sharp for every basis $S$ and every valid $t$ . The author constructs explicit examples where $|A| = n - t$ and $|B| = n + \binom{t+1}{2}$ , utilizing the linear independence of the basis vectors.
Corollary 1.2: The result immediately implies the original vector-model conjecture of Bukh, van Hintum, and Keevash for $\mathbb{Q}^n$ .
Implication for Change-of-Domain: Combined with previous reductions, this result confirms that the factor of 2 in the change-of-domain problem (replacing a rational basis with an integer basis) is best possible for 2-bases. Specifically, for every $n$ , there exists a set of integers with a rational 2-basis of size at most $n$ whose smallest integer 2-basis has size exactly $2n$ .

Significance
The paper resolves an open problem explicitly posed by Bukh regarding the persistence of additive basis bounds over $\mathbb{R}^n$ for arbitrary bases. The proof is noted for its brevity, utilizing edge contractions in a graph-theoretical setting and a novel coloring lemma over $\mathbb{F}_2^n$ . The work establishes the exact trade-off between the sizes of two sets required to cover the sumset of a basis, settling the refined conjecture and confirming the tightness of the "factor 2" bound in related change-of-domain problems.