🔢 mathematics

Dense ascending waves: A resolution of the Alon-Spencer conjecture

This paper resolves the Alon-Spencer conjecture by proving that every subset of $\{1, \ldots, n\}$ with size at least $n/2$ contains an ascending wave of length at least proportional to $(\log n)^2$ , thereby removing the $\log\log n$ factor from the previously known lower bound.

Original authors: Yaping Mao

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yaping Mao

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

In the vast landscape of mathematics, there is a branch dedicated to finding order within chaos, often asking how much structure is guaranteed to exist even in a seemingly random collection of numbers. This field, known as Ramsey theory, operates on the principle that if a set is large enough, it must contain specific patterns, regardless of how it was arranged. One such pattern is the "ascending wave," a sequence of numbers where the gaps between consecutive terms do not shrink; instead, the distance between each number and the next either stays the same or grows larger. Imagine a staircase where each step is at least as tall as the one before it; that is the essence of an ascending wave. Mathematicians have long been interested in how long such a wave can be forced to exist within a dense collection of integers. If you take a large range of numbers and select at least half of them, you are guaranteed to find a sequence with this growing-gap property. The central question has been determining exactly how long that sequence must be as the range of numbers gets bigger.

For years, researchers knew that the length of this guaranteed sequence grows roughly with the square of the logarithm of the total number of integers available. However, a precise calculation suggested that the lower bound for this length was slightly smaller than the upper bound, with a confusing extra factor involving the logarithm of a logarithm. This discrepancy led two mathematicians, Noga Alon and Joel Spencer, to propose a conjecture: that this extra factor was an artifact of their methods rather than a true feature of the numbers themselves. They suspected the true length was simply proportional to the square of the logarithm, without the messy extra term. For a long time, this remained an open problem, a gap in the understanding of how density forces structure.

A recent paper by Yaping Mao has finally settled this question, confirming that Alon and Spencer were correct. The author proved that in any set containing at least half of the integers from one to a large number $n$ , there is always an ascending wave whose length is proportional to the square of the logarithm of $n$ . This result removes the previously suspected extra factor, showing that the relationship is cleaner and more direct than the earlier estimates suggested. The proof does not rely on guessing or statistical likelihood but uses a rigorous, deterministic method to show that the pattern must exist.

To achieve this, the researcher developed a new way of tracking the potential paths these number sequences could take. Instead of looking at the numbers in isolation, the proof treats the problem as a dynamic system, similar to watching a particle move through a specific kind of space. The method involves tracking two things simultaneously: the current position of a number in the sequence and the size of the gap to the next number. By mapping these pairs of values, the researcher created a "phase space," a visualizable area where every possible step of the sequence has a corresponding location.

The core difficulty in solving this problem was that early mistakes in choosing a path could cause many different potential sequences to collapse into the same gap later on, making it difficult to predict where they would end up. Previous attempts struggled with this "focusing" effect, where independent paths seemed to interfere with one another. The new approach solves this by keeping a record of the error, or "overshoot," at every step. This allows the system to be reversible; if you know where a sequence ended up, you can trace it back exactly to where it started. This reversibility ensures that the paths do not get tangled or lost. Instead of relying on the assumption that these paths behave independently, the proof uses a packing argument, showing that the available space in this phase space is large enough to hold all the necessary paths without them overlapping in a way that would destroy the pattern.

The proof works by dividing the problem into different scales, or levels of size. It first looks at small gaps between numbers and then gradually moves to larger gaps. At each level, the researcher identifies a "window" of numbers that is free of large interruptions. Within these windows, the method constructs a short, local ascending wave. The brilliance of the construction lies in how these local waves are connected. The researcher selects specific starting points that work well across multiple scales simultaneously. By carefully choosing these points, the local waves can be stitched together, or "spliced," to form one continuous, long ascending wave. The connection points are chosen so that the gap size at the end of one local wave is smaller than the gap size at the beginning of the next, ensuring the non-decreasing property is maintained throughout the entire sequence.

The result is a definitive confirmation that the length of the longest guaranteed ascending wave in a dense set of integers is indeed proportional to the square of the logarithm of the total count. This finding resolves a decades-old conjecture and provides a clearer picture of how order emerges from density. It demonstrates that even in a set that appears random, the constraint of having at least half the numbers forces a very specific, predictable structure to appear. The work does not just offer a new number; it offers a new way of seeing the problem, turning a difficult question about independent events into a solvable problem about geometry and space. By proving that the extra factor in the lower bound was unnecessary, the paper simplifies our understanding of the fundamental rules governing these numerical patterns.

Technical Summary: Dense Ascending Waves and the Resolution of the Alon–Spencer Conjecture

Problem Statement
The paper addresses a problem in extremal combinatorics concerning "ascending waves" within dense subsets of integers. For a positive integer $n$ , let $[n] = \{1, \dots, n\}$ . A strictly increasing sequence of integers $x_1 < \dots < x_k$ is defined as an ascending wave if its consecutive differences are nondecreasing (i.e., $x_{t+1} - x_t \ge x_t - x_{t-1}$ ).

Let $g(n)$ denote the largest integer $k$ such that every subset $A \subseteq [n]$ with density at least $1/2$ (i.e., $|A| \ge n/2$ ) contains an ascending wave of length $k$ . Alon and Spencer previously established that for sufficiently large $n$ :
$c_1 \frac{(\log n)^2}{\log \log n} \le g(n) \le c_2 (\log n)^2$
They conjectured that the $\log \log n$ factor in the lower bound is not intrinsic and that $g(n) = \Theta((\log n)^2)$ . The primary objective of this paper is to prove this conjecture by establishing the matching lower bound.

Methodology
The proof employs a novel synthesis of phase-space dynamics and deterministic packing arguments to overcome the limitations of direct greedy analysis. The author identifies that in previous attempts, "projection errors" created early in a sequence could focus multiple tentative trajectories into a single gap, making independent probabilistic treatment of hitting events invalid.

To resolve this, the paper introduces the following framework:

Phase-Space Dynamics and Shadow Map:
The author defines a "phase point" $p = (u, d) \in \mathbb{R}^2$ , where $u$ is a position and $d$ is a difference. They introduce a "shadow map" $T: D \to X$ defined by $T(u, d) = (u+d, d + 2\rho(u+d))$ , where $\rho(z)$ is the overshoot of $z$ onto the set $A$ .
- Key Property: The map $T$ is a Borel bijection that is area-preserving (Lebesgue measure preserving) and invertible.
- Significance: By retaining the projection error $\rho$ as a second state variable, the dynamics become invertible. This transforms the "focusing" phenomenon (where many trajectories hit the same gap) into a deterministic packing problem in phase space, where repeated active hits on a fixed gap correspond to disjoint image slices.
Local Square-Energy Theorem (Section 3):
The author defines a "short-gap square energy" $E_D^<(I)$ for an interval $I$ at scale $D$ . They prove a local theorem (Theorem 3.2) stating that if a local window $J$ has sufficiently low square energy (specifically $E_D^<(J) \le \epsilon D$ ), then there exists a starting point in $J$ that generates a local ascending wave of length $L$ with controlled differences.
- The proof utilizes a "packing estimate" (Lemma 3.1) showing that the total phase-space area of active hits on any gap $G$ is bounded by $5D|G|$ . This allows the conversion of energy bounds into the existence of a valid trajectory that avoids crossing the "overshoot threshold" $D$ .
Global Scale Selection and Multiscale Splicing (Section 4):
To construct a global wave, the author selects a sequence of scales $D_i = 2^i$ and identify a "common starting point" $x^*$ that is "admissible" at many scales.
- Admissibility: A point is admissible at scale $i$ if it satisfies safety conditions (staying within bounds), avoids large gaps, and has low local square energy.
- Selection: Using averaging arguments over the set of gaps and the set of points, they prove the existence of a point $x^*$ admissible at a set of scales $I$ with size $|I| \ge \frac{1}{32} \log n$ .
- Splicing: By selecting a subset of scales $I'$ that are well-separated (geometrically spaced by a factor $Q=128$ ), the author iteratively applies the local theorem. The large separation ensures that the "bridge" difference of a new local wave is larger than the final difference of the previous wave, preserving the ascending wave property upon concatenation.

Key Contributions and Results

Resolution of the Conjecture: The paper proves Theorem 1.2: There exists an absolute constant $c > 0$ such that every set $A \subseteq [n]$ with $|A| \ge n/2$ contains an ascending wave of length at least $c(\log n)^2$ .
Asymptotic Tightness: Combined with the upper bound from Alon and Spencer, this establishes $g(n) = \Theta((\log n)^2)$ , confirming Conjecture 1.1.
Methodological Innovation: The paper introduces a phase-space lift that converts a problem involving dependent hitting events into a deterministic area-preservation problem. This avoids the "logarithmic loss" inherent in independence assumptions used in previous analyses.
Explicit Construction: The proof is constructive in nature, relying on the existence of a point satisfying specific energy and gap conditions, rather than purely probabilistic existence arguments.

Significance
The paper claims to remove the "logarithmic loss" in the lower bound for dense ascending waves, a problem that had remained open since the work of Alon and Spencer. The significance lies not only in the quantitative improvement of the bound but in the qualitative shift in methodology: replacing independence assumptions with a deterministic, area-preserving dynamical system approach. This technique controls the focusing of trajectories through geometric packing in phase space, offering a new tool for analyzing wave configurations and related extremal combinatorial problems. The result settles the asymptotic behavior of the dense-set ascending-wave function, placing it firmly within the $(\log n)^2$ regime.

Technical Summary: Dense Ascending Waves and the Resolution of the Alon–Spencer Conjecture

More like this