Diophantine tuples and product sets in shifted powers

Imagine you are hosting a very strict dinner party. You have a list of guests (positive integers), and you have a very peculiar rule for seating them: No two guests can sit next to each other unless their "product" (multiplying their numbers together) plus a specific "shift" (let's call it $n$ ) results in a perfect power.

A "perfect power" is a number like 4 ($2^2 $), 8 ($ 2^3 $), 9 ($ 3^2 $), or 16 ($ 4^2$). It's a number that can be built by stacking identical blocks into a perfect square, cube, or higher shape.

This paper, written by Ernie Croot and Chi Hoi Yip, is about figuring out how many guests you can possibly invite to this party before the rule breaks down.

Here is the breakdown of their discovery, translated into everyday language:

1. The Old Rules vs. The New Party

For a long time, mathematicians studied a specific version of this party where the shift $n$ was always 1, and the perfect powers had to be squares (like $2^2, 3^2$). They found that you could only have a tiny number of guests (like 4 or 5) before it became impossible to add another.

But what if the shift $n$ is a huge number? What if the guests don't just need to make squares, but can make cubes, fourth powers, or any perfect power?

The Old Guess: Previous mathematicians thought the number of guests could grow quite large, roughly proportional to the size of the shift $n$ raised to the power of $2/3$.
The New Discovery: Croot and Yip proved that the number of guests is actually much, much smaller. It doesn't grow with the size of the shift; it grows incredibly slowly, like the "logarithm of the logarithm" of the shift.

The Analogy:
Imagine you are trying to find a group of people who all fit into a specific, very narrow hallway.

Old View: They thought the hallway could stretch out for miles if the building was big enough.
New View: Croot and Yip showed that no matter how big the building is, the hallway is actually a tiny, cramped closet. You can't fit many people in there.

2. The "Robust" Party (The Graph Theory Trick)

To prove this, the authors didn't just look at the numbers; they looked at the relationships between them. They used a clever trick from Extremal Graph Theory (a branch of math that studies how many connections you can make before a pattern forces itself).

Imagine you draw a dot for every guest. If two guests satisfy the rule (their product + shift is a perfect power), you draw a line between them.

If you have too many guests, you are forced to draw a "complete" web of lines (a clique) where everyone is connected to everyone else in a specific way.
The authors proved that for these specific "perfect power" rules, you simply cannot build a big enough web without breaking the rules.

They introduced a "Robust" version of the problem: What if most pairs of guests satisfy the rule, not just all of them? They showed that even if you relax the rule slightly, the party still collapses quickly. This "robustness" was the key to unlocking the tighter limits.

3. The "Sieve" and the "Approximation"

How did they prove the web collapses? They used two powerful tools:

The Sieve (The Colander): Imagine you have a bucket of sand (all possible numbers) and you want to find the gold nuggets (the numbers that fit the rule). You pour the sand through a colander (a sieve) with specific hole sizes (prime numbers). The authors used a sophisticated sieve to filter out numbers that couldn't possibly be part of the group, leaving very few candidates.
Diophantine Approximation (The Ruler): This is about how close numbers can get to each other without actually being the same. They used this to show that if you have too many guests, the "gaps" between their required perfect powers would become impossibly small, which is mathematically impossible.

4. The "What If" Scenarios (Conditional Results)

The paper also asks: "What if we assume some famous, unproven math theories are true?"

The ABC Conjecture: This is a giant, famous hypothesis in math. If we assume it's true, the authors can prove even stronger limits. It's like saying, "If the laws of physics work exactly as we think they do, then the party can't even have 10 people."
The Uniformity Conjecture: Another big assumption. If this is true, it suggests that for any shift $n$ and any power $k$ , there is a universal "maximum guest limit" that never changes, no matter how big the numbers get.

The Big Picture Takeaway

Before this paper, mathematicians thought these "Diophantine tuples" (groups of numbers with this special multiplication property) could be quite large and flexible.

Croot and Yip showed they are actually incredibly fragile.
No matter how you tweak the rules (changing the shift, allowing different powers), the group size is tightly capped. It's like trying to build a house of cards in a hurricane; you might get a few cards up, but the moment you try to add a few more, the whole structure collapses.

In short: They proved that the universe of these special number groups is much smaller and more rigid than anyone previously thought, using a mix of sieving, graph theory, and number crunching to shrink the possible sizes from "huge" to "tiny."

Here is a detailed technical summary of the paper "Diophantine Tuples and Product Sets in Shifted Powers" by Ernie Croot and Chi Hoi Yip.

1. Problem Statement and Context

The paper investigates generalizations of Diophantine $m$ -tuples. A classical Diophantine $m$ -tuple is a set of distinct positive integers $\{a_1, \dots, a_m\}$ such that $a_i a_j + 1$ is a perfect square for all $i \neq j$ .

The authors generalize this to two dimensions:

Shifted Powers: Instead of $+1$ , they consider an arbitrary non-zero integer shift $n$ .
Variable Exponents: Instead of requiring the product to be a perfect $k$ -th power for a fixed $k$ , they consider the set of all perfect powers (or perfect powers with exponents up to $d$ ).

Key Definitions:

Property $D_k(n)$ : A set $A$ where $ab+n$ is a perfect $k$ -th power for all distinct $a,b \in A$ .
Property $D_{\le d}(n)$ : A set $A$ where $ab+n$ is a perfect $k$ -th power for some $2 \le k \le d$.
Property $D_{\le \infty}(n)$ : A set $A$ where $ab+n$ is a perfect power (any exponent $k \ge 2$ ).
Maximal Sizes: $M_k(n)$ , $M_{\le d}(n)$ , and $M_{\le \infty}(n)$ denote the supremum of the size of such sets.
Function $f(x)$ : The maximum size of a set $A \subseteq [1, x]$ such that $ab+n$ is a perfect power for some $1 \le |n| \le x$.

The Core Challenge:
While bounds for fixed $k$ (e.g., $M_k(n) \ll \log |n|$ ) are well-established, the case where the exponent can vary (especially $d=\infty$ ) is significantly harder. Previous best bounds for $f(x)$ were of the order $x^{2/3+o(1)}$ . The paper aims to drastically improve these bounds and clarify the relationship between fixed-exponent and variable-exponent Diophantine tuples.

2. Methodology

The authors employ a novel synthesis of three distinct mathematical fields: Sieve Methods, Diophantine Approximation, and Extremal Graph Theory.

A. Extremal Graph Theory and Robust Variants

Instead of directly attacking the set $A$ , the authors introduce a "robust" version of the problem. They consider sets where a positive proportion $\delta$ of pairs satisfy the Diophantine condition.

Reduction to Bipartite Tuples: Using the Kővári–Sós–Turán theorem, they reduce the problem of bounding the size of a general set to bounding the size of bipartite Diophantine tuples $(A, B)$ , where $ab+n$ is a perfect $k$ -th power for all $a \in A, b \in B$ .
Graph Coloring: They model the set of integers as a graph where edges are colored by the smallest prime exponent $p$ such that $ab+n$ is a $p$ -th power. Ramsey theory is used to show that if the set is large, it must contain a large monochromatic subgraph (a bipartite tuple with a fixed exponent).

B. Sieve Methods (The Larger Sieve)

To bound the size of these bipartite tuples, the authors utilize Gallagher's Larger Sieve and its variants (Croot–Elsholtz).

Finite Field Models: They analyze the problem modulo primes $p$ . If $ab+n$ is a $k$ -th power, then in $\mathbb{F}_p$ , $ab+n$ must lie in the set of $k$ -th powers.
Character Sums: They use Weil's bound and Karatsuba's estimates for character sums to bound the number of solutions in finite fields. This allows them to control the "density" of the set modulo various primes.
Linnik's Theorem: A quantitative version of Linnik's theorem on the least prime in an arithmetic progression is used to ensure the existence of suitable primes for the sieve.

C. Diophantine Approximation

For the case of "large" elements in the set (specifically $a, b > |n|^{17}$ ), the authors use linear forms in logarithms (Baker's method).

They prove that if four distinct large integers form a cycle of products $ab+n, bc+n, \dots$ being perfect powers with large exponents, it leads to a contradiction via lower bounds on linear forms in logarithms. This effectively limits the number of large elements in the set.

3. Key Contributions and Results

The paper provides unconditional and conditional improvements on the upper bounds for the size of these sets.

A. Unconditional Results

Improved Bound for Fixed $d$ (Theorem 2.1):
For $2 \le d < \infty $and$ n \neq 0$:
$M_{\le d}(n) \ll \frac{d^2}{(\log d)^2} + e^{L \log |n|}$
If $d$ is fixed, this improves the bound to $M_{\le d}(n) \ll \log |n|$ , matching the best known bounds for fixed $k$ .
Improved Bound for All Perfect Powers (Theorem 2.2 & Corollary 2.3):
This is the paper's most significant breakthrough. They improve the bound for $f(x)$ (and $M_{\le \infty}(n)$ ) from the previous $x^{2/3+o(1)}$ to a polylogarithmic bound:
$f(x) \le \tilde{O}\left( \exp\left( L (\log \log x)^2 \right) \right)$
This implies that the size of such sets grows extremely slowly, far slower than any power of $x$ .
Bipartite Tuple Bounds (Theorems 2.5, 2.6, 2.7):
They establish new, tighter bounds for bipartite Diophantine tuples $(A, B)$ with property $BD_k(n)$ . Specifically, if $|A|$ is large, $|B|$ is bounded by a power of $|n|$ that is significantly smaller than previous results, or even logarithmic in $|n|$ .

B. Conditional Results

Assuming standard conjectures in number theory, the authors derive even stronger results:

Uniformity Conjecture + Lander–Parkin–Selfridge Conjecture:
There exists an absolute constant $C$ such that $M_k(n) \le C$ for all $k \ge 2$ and $n \neq 0$ . This suggests that the size of Diophantine tuples is universally bounded regardless of the shift or exponent.
ABC Conjecture:
Assuming the ABC conjecture, they prove $M_{\le \infty}(n) \ll \exp(L (\log \log |n|)^2)$ .
Furthermore, combining the ABC conjecture with the Lander–Parkin–Selfridge conjecture yields $M_{\le \infty}(n) \ll (\log |n|)^4$ .

4. Significance and Impact

Resolution of a Long-Standing Gap: The paper closes the gap between the known bounds for fixed exponents and the much weaker bounds for variable exponents. The previous $x^{2/3}$ bound for $f(x)$ was considered a major bottleneck; reducing this to a double-logarithmic exponential is a qualitative leap.
Methodological Innovation: The combination of extremal graph theory (to separate the problem into bipartite components) and sieve methods (to bound those components) creates a powerful new framework. This approach avoids the inefficiencies of previous Ramsey-theoretic arguments which often resulted in huge constants or weak bounds.
Structural Insight: The results suggest that the structure of integers allowing $ab+n$ to be a perfect power is extremely rigid. Even when allowing any perfect power, the set cannot grow large.
Conditional Universality: The conditional results provide strong evidence for the conjecture that Diophantine tuples are finite and bounded by an absolute constant, a central open problem in the field.

In summary, Croot and Yip have fundamentally advanced the understanding of Diophantine tuples in shifted power sets by developing a robust, multi-disciplinary toolkit that yields the strongest known bounds to date, both unconditionally and under standard conjectures.