OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Theorem 1.1: Cardinality bounds on integer intervals and their translates in ℕ\mathbb N

Square differences force a power saving.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The extremal question asks how large a finite set A⊆ℤA\subseteq\mathbb Z can be inside an interval when no difference of two elements of AA is a positive integer square; such a set is called square-difference-free.✦ For an integer N≥1N\ge1, the integer and natural intervals are those in (1): [N]={1,…,N}⊆ℤ,IN={0,…,N−1}⊆ℕ.[N]=\{1,\ldots,N\}\subseteq\mathbb Z, \qquad I_N=\{0,\ldots,N-1\}\subseteq\mathbb N.(1) The translation between them sends a∈[N]a\in[N] to a−1∈INa-1\in I_N.

a−b≠m2(a,b∈A,m∈ℕ,m≥1).a-b\ne m^2 \qquad(a,b\in A,\ m\in\mathbb N,\ m\ge1).(2)✦ A finite set B⊆ℕB\subseteq\mathbb N is square-difference-free if it contains no pair separated by a positive square, as in (3): b≠a+m2(a,b∈B,m∈ℕ,m≥1).b\ne a+m^2 \qquad(a,b\in B,\ m\in\mathbb N,\ m\ge1).(3)✦

Definition 1. The power-saving property 𝒫\mathcal P is the assertion that there are real constants cℤ>0c_{\mathbb Z}>0 and CℤC_{\mathbb Z} such that, for every integer N≥1N\ge1 and every square-difference-free finite set A⊆[N]A\subseteq[N], the bound (4) holds: |A|≤CℤN1−cℤ.|A|\le C_{\mathbb Z}N^{1-c_{\mathbb Z}}.(4)✦

The Claim

Theorem 1. The power-saving property 𝒫 holds.\text{The power-saving property }\mathcal P\text{ holds.}(5)✦ There are real constants cℕ>0c_{\mathbb N}>0 and CℕC_{\mathbb N} such that, for every integer N≥1N\ge1 and every square-difference-free finite set B⊆INB\subseteq I_N, |B|≤CℕN1−cℕ.|B|\le C_{\mathbb N}N^{1-c_{\mathbb N}}.(6)✦

In the paper, the result reads: there are absolute constants c>0c>0 and C<∞C<\infty such that, for every integer N≥1N\ge1 and every square-difference-free set A⊆[N]A\subseteq[N], |A|≤CN1−c|A|\le CN^{1-c}; equivalently, every subset of [N][N] larger than CN1−cCN^{1-c} contains distinct elements whose absolute difference is a positive integer square.

What Is Checked

The assertions (5) and (6) concern finite subsets of the intervals in (1), with square differences excluded by (2) and (3).