🔢 mathematics

A Salem-Spencer-Type Construction for Large Subsets of Integer Grids with No Isosceles Right Triangles

This paper presents a modified Salem–Spencer-type construction over the Gaussian integers to prove that the largest subset of an $n \times n$ integer grid containing no nondegenerate isosceles right triangles has a size of at least $\Omega(n^{1.3})$ , thereby narrowing the gap with the current best upper bound.

Original authors: Gyula Károlyi, Jozsef Solymosi

Published 2026-07-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Gyula Károlyi, Jozsef Solymosi

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 a detective trying to solve a mystery in a giant, infinite city made entirely of grid intersections. This city is the world of mathematics, specifically a branch called Combinatorics, which is all about counting, arranging, and finding patterns in discrete objects. In this city, the "streets" are just numbers, and the "buildings" are points where two numbers meet, like $(x, y)$ coordinates on a map.

The mystery at hand involves a very specific rule: you want to build the largest possible neighborhood (a subset of points) where a certain shape is strictly forbidden. That shape is the isosceles right triangle. You know these triangles well: they have one corner that is a perfect 90-degree angle (like the corner of a piece of paper), and the two sides touching that corner are exactly the same length. The question mathematicians have been asking for a long time is: How big can a neighborhood get before you are forced to accidentally build one of these forbidden triangles?

This isn't just a game of geometry; it's a deep puzzle that connects to how numbers behave, how we encrypt data, and even how we understand the structure of the universe. If you can find a huge neighborhood with no triangles, it means there are hidden, complex ways to arrange numbers that avoid simple patterns. For decades, mathematicians knew the answer was somewhere between "very big" and "almost the whole city," but the gap between the smallest possible big neighborhood and the largest possible one was enormous. It was like knowing a treasure chest is somewhere in a desert, but not knowing if it's buried under a single grain of sand or a mountain of gold.

The Paper's Big Discovery: A New Way to Build "Triangle-Free" Cities

In this paper, two mathematicians, Gyula Károlyi and József Solymosi, have built a massive new neighborhood that is much bigger than anyone thought possible before. They managed to construct a subset of points in a grid that avoids isosceles right triangles, and their construction is so large that it proves the size of such a neighborhood grows at a rate of roughly $n^{1.3}$ (where $n$ is the size of the grid).

To understand how they did it, imagine you are trying to build a tower out of blocks, but you have a strict rule: you cannot stack the blocks in a way that forms a specific "bad" shape. In the past, mathematicians tried to build these towers by picking blocks that were completely safe on their own. But Károlyi and Solymosi realized they could be smarter. They used a technique they call "peeling," which is like a game of Jenga where you can have a slightly wobbly tower, as long as you can remove the blocks one by one in a specific order until the whole thing is safe.

The Magic Ingredients

The authors used a few clever tricks to pull this off:

The Gaussian Integers (The "Magic Grid"): Instead of using normal numbers, they used a special kind of number called Gaussian integers. You can think of these as points on a grid where every point has an "x" coordinate and a "y" coordinate, but they are treated as a single magical number. This allowed them to rotate and shift their blocks in ways that normal numbers couldn't.
The "Carry-Free" Alphabet: When you add numbers, sometimes you get a "carry" (like when $9 + 1 = 10$ , the 1 carries over). The authors found a special set of "digits" (a small group of points) where, if you add them up to form a triangle, the math never "carries over" into the next level. This keeps the local rules simple.
The Peeling Order (The Secret Sauce): This is the most novel part. They found a group of 281 points that do contain triangles if you look at them all at once. However, they discovered a specific order to remove these points. If you remove the first point, no triangles remain with that point as the corner. Then you remove the next, and so on. By the time you are done, the remaining set is perfectly safe. It's like having a room full of people where everyone is holding hands in a circle, but if you ask them to leave in a specific order, the circle breaks apart before anyone gets hurt.

The Result: A Giant Leap Forward

Using a powerful AI tool called AlphaEvolve (which helped them search through millions of possibilities to find the perfect arrangement), they found a "peeling order" for a set of 281 points.

When they applied their method to a grid of size $n$ , they proved that you can find a triangle-free subset with a size of at least $n^{1.3178...}$ .

To put this in perspective:

Before this, the best known lower bound was much smaller (around $n^{1.05}$ ).
The best known upper bound (the theoretical limit of how big it could possibly be) is roughly $n^2$ divided by some logarithmic factors.
Their result, $n^{1.3}$ , bridges a significant gap, showing that these triangle-free neighborhoods can be much larger than previously suspected.

What They Did Not Do

It is important to note what this paper does not claim. They did not prove that $n^{1.3}$ is the absolute maximum possible size. They did not find the "perfect" neighborhood that is as big as mathematically possible. They also did not prove that 281 is the largest possible number of points they could use in their specific method; they just found a very good one.

The paper explicitly states that there is still a "large gap" between their new lower bound ( $n^{1.3}$ ) and the upper bound ( $n^2$ ). The mystery isn't fully solved, but they have definitely found a much bigger piece of the puzzle than anyone else has before.

The Takeaway

This paper is a triumph of combining old-school mathematical logic with modern AI search. By treating numbers as points on a grid, finding a special "carry-free" zone, and using a clever "peeling" strategy to remove dangerous points one by one, the authors have shown that we can build much larger "triangle-free" cities than we thought. It's a vivid example of how a fresh perspective—looking at the problem not as a static wall, but as a dynamic process of removal—can unlock new possibilities in the world of numbers.

Technical Summary: A Salem–Spencer-Type Construction for Large Subsets of Integer Grids with No Isosceles Right Triangles

Problem Statement
The paper addresses the problem of determining the maximum size, denoted $F(n)$ , of a subset of the integer grid $\{0, 1, \dots, n-1\}^2$ that contains no nondegenerate isosceles right triangles (IRTs). While the upper bound for this quantity is known to be $F(n) \ll n^2 / (\log n)^{1+c}$ for some constant $c > 0$ (via extensions of the Bloom–Sisask method), the best known lower bounds have historically been weak. The authors aim to establish a superlinear lower bound, specifically $F(n) = \Omega(n^\alpha)$ for some $\alpha > 1$ , using a modified Salem–Spencer-type construction adapted to the Gaussian integers.

Methodology
The authors employ a digit-based construction over the Gaussian integers $\mathbb{Z}[i]$ , identifying lattice points $(x, y)$ with $x + iy$. The construction relies on four main components:

Linear Encoding of IRTs: An isosceles right triangle with vertices $a, b, c \in \mathbb{Z}[i]$ (where $b$ is the right-angle vertex) is encoded by the linear equation $a + ic = (1+i)b$. Degenerate solutions correspond to $a=b=c$ .
IRT-Carry-Free Alphabets: The authors define an alphabet $P \subset \mathbb{Z}[i]$ as a partial system of residues modulo a nontrivial Gaussian integer $\beta$ . $P$ is "IRT-carry-free" if the equation $a + ic = (1+i)b$ holds modulo $\beta$ only if it holds exactly (i.e., no "carries" occur that would create a false positive for a triangle).
IRT-Peeling Orders: Unlike classical Salem–Spencer constructions which require the alphabet itself to be free of the forbidden configuration, this method allows the alphabet $P$ to contain IRTs. Instead, $P$ is equipped with a "peeling order" $p_1, \dots, p_q$ . This is a sequence such that for any suffix $R_t = \{p_t, \dots, p_q\}$ , the only solution to $a + ic = (1+i)p_t$ with $a, c \in R_t$ is the trivial solution $a=c=p_t$ . This property ensures that when constructing large sets via digit expansions, any potential IRT can be eliminated by peeling off digits from the most significant position.
Composition Classes: The final set is constructed by taking all words of length $m$ over the alphabet $P$ that share a specific "composition" (frequency count of each digit). By restricting to a large composition class, the peeling order propagates through all digit positions, ensuring the resulting set is IRT-free.

Key Contributions and Results

General Theorem (Theorem 2.6): The authors prove that if an IRT-carry-free alphabet $P$ of size $q$ exists in base $\beta$ with a valid peeling order, then $F(n) \gg \frac{n^{\log q / \log |\beta|}}{(\log n)^{(q-1)/2}}$ .
Small Example: Using $\beta = 2+2i$ and $P=\{0, 1, i\}$ , they demonstrate a construction yielding an exponent $\alpha \approx 1.0566$ .
Optimized Construction (Theorem 4.2): The primary result utilizes a base $\beta = 51 + 51i$ $β = 51 + 51 i$ and a carry-free region $C$ $C$ derived from a centrally located diamond in the fundamental domain. Using the AI agent AlphaEvolve, the authors discovered a specific ordering of 281 distinct points in $C$ $C$ that forms a valid IRT-peeling order.
- This yields the bound:
  $F(n) \gg \frac{n^\alpha}{(\log n)^{140}}$
  where $\alpha = \frac{\log 281}{\log |51+51i|} \approx 1.317865$ .
- This establishes $F(n) = \Omega(n^{1.3})$ .

Significance and Claims
The paper claims to close the gap between the known upper and lower bounds for $F(n)$ by providing the first superlinear lower bound with an exponent significantly greater than 1. The significance lies in:

Novel Technique: The introduction of the "peeling order" allows for alphabets that are not themselves IRT-free, expanding the search space for large digit sets beyond what was possible with previous methods.
Computational Discovery: The use of AlphaEvolve to find the specific 281-point certificate demonstrates a hybrid approach where AI assists in the discovery of combinatorial structures, while the mathematical validity is rigorously verified by a deterministic certificate (Appendix B).
Modesty of Claims: The authors explicitly state that their result does not prove 281 is the maximum possible alphabet size for the chosen base, nor that this base is globally optimal. The "optimized" label refers strictly to the computational search objective. The paper separates the geometric argument (existence of carry-free regions) from the finite search (finding the peeling order), making the result independently checkable.

The work does not propose new applications or future experimental directions beyond suggesting extensions to different Gaussian bases, asymmetric regions, and block digits.