Exponents in the local properties problem for difference sets have a gap at 2

Sanjana Das · 2025

Read Exponents in the local properties problem for difference sets have a gap at 2 by Sanjana Das (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11148.txt.

Introduction

Sanjana Das, writing alone, offers a 2025 math paper on sets of numbers and the gaps between their members. Take a large set where every small subset has many distinct gaps between its numbers. The question is how many distinct gaps the whole set must then have. This is known as the local properties problem for difference sets.

Das studies how the count of gaps grows as the set gets large, for fixed subset size. There is a key threshold where the growth jumps to a square rate. She shows that just below that threshold, the growth stays below the square rate by a fixed margin. The gap in growth rates holds for all even subset sizes.

Catalog record

CREATORSanjana Das
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE120 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11148

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exponents in the local properties problem for difference sets have a gap at 2 Sanjana Das Abstract . We study the local properties problem for difference sets: If we have a large set of real numbers and know that every small subset has many distinct differences, to what extent must the entire set have many distinct differences? More precisely, we define g ⁡ ( n , k , ℓ ) g(n,k,\ell) to be the minimum number of differences in an n n -element set with the ‘local property’ that every k k -element subset has at least ℓ \ell differences; we study the asymptotic behavior of g ⁡ ( n , k , ℓ ) g(n,k,\ell) as k k and ℓ \ell are fixed and n → ∞ n\to\infty . The quadratic threshold is the smallest ℓ \ell (as a function of k k ) for which g ⁡ ( n , k , ℓ ) = Ω ⁡ ( n 2 ) g(n,k,\ell)=\Omega(n^{2}) ; its value is known when k k is even. In this paper, we show that for k k even, when ℓ \ell is one below the quadratic threshold, we have g ⁡ ( n , k , ℓ ) = O ⁡ ( n c ) g(n,k,\ell)=O(n^{c}) for an absolute constant c < 2 c<2 — i.e., at the quadratic threshold, the ‘exponent of n n in g ⁡ ( n , k , ℓ ) g(n,k,\ell) ’ jumps by a constant independent of k k . 1. Introduction 1.1. Background on local properties problems There is a long history of studying problems with the following form: If we have a large object and we know that every small piece of it is ‘unstructured’ in some sense, how unstructured must the entire object be? In other words, to what extent can we go from a local property about lack of structure to a global one? Erdős and Shelah [ 5 , Section V] initiated the study of a local properties problem for graphs. Here, the large object is an edge-coloring of a complete graph, and the small pieces are constant-sized induced subgraphs; we think of an edge-coloring as unstructured if it contains many distinct colors. To formalize this, we define f(n,k,\ell) to be the minimum number of colors needed to edge-color K_{n} such that every induced subgraph K_{k} contains at least \ell colors. This can be viewed as a generalization of Ramsey numbers, which correspond to the case \ell=2 — the t -color Ramsey number r_{t}(k) is the smallest n for which it is not possible to edge-color K_{n} with t colors such that every K_{k} contains at least two colors, i.e., the smallest n for which f(n,k,2)>t . When studying f(n,k,\ell) , we typically think of k and \ell as constants, and study the asymptotic behavior of f(n,k,\ell) as n\to\infty . One direction to approach this problem from is to search for thresholds: If we fix k and increase \ell from 1 to \binom{k}{2} , then f(n,k,\ell) will increase from 1 to \binom{n}{2} , and we can ask for the value of \ell at which f(n,k,\ell) begins to exhibit a certain behavior, which we call the threshold for that behavior. In [ 7 ] , Erdős and Gyárfás introduced the following thresholds. • The polynomial threshold is the smallest \ell (as a function of k ) for which f(n,k,\ell)=\Omega(n^{\varepsilon}) for some \varepsilon>0 (possibly depending on k ). • The linear threshold is the smallest \ell for which f(n,k,\ell)=\Omega(n) . • The superlinear threshold is the smallest \ell for which f(n,k,\ell)=\omega(n) . • The quadratic threshold is the smallest \ell for which f(n,k,\ell)=\Omega(n^{2}) . Erdős and Gyárfás [ 7 ] exactly determined the linear and quadratic thresholds — they showed that the linear threshold is \binom{k}{2}-k+3 and the quadratic threshold is \binom{k}{2}-\lfloor k/2\rfloor+2 . They also showed that the polynomial threshold is at most k ; Conlon, Fox, Lee, and Sudakov [ 3 ] later proved that this is tight. Sárközy and Selkow [ 13 ] showed that the superlinear threshold is at most \binom{k}{2}-k+\lceil\log k\rceil+3 . Erdős and Gyárfás [ 7 ] also proved a general upper bound on f(n,k,\ell) using a random construction; works including [ 12 , 9 , 1 ] have proved several families of lower bounds, which nearly match this upper bound in many cases. Erdős [ 6 ] also posed a similar local properties problem for distinct distances. Here, the large object is a set of points in \mathbb{R}^{2} , and we think of a set of points as unstructured if it spans many distinct distances. So we define \phi(n,k,\ell) as the minimum number of distinct distances that n points in \mathbb{R}^{2} can span, given that every k points span at least \ell distinct distances. We always have \phi(n,k,\ell)\geq f(n,k,\ell) — we can convert any configuration of points into a graph on those points where the color of an edge represents the distance between its two endpoints — and in many regimes, this is the best known lower bound for \phi(n,k,\ell) . However, there are a few cases where we are able to make use of the geometric structure to prove better lower bounds: Fox, Pach, and Suk [ 10 ] proved that \phi(n,k,\binom{k}{2}-k+6)=\Omega(n^{8/7-o(1)}) . (Meanwhile, we only know that f(n,k,\binom{k}{2}-k+6)=\Omega(n) .) It is also possible to approach this problem in terms of thresholds (in particular, Fox, Pach, and Suk comment on the linear and quadratic thresholds in [ 10 , Section 1] ), but such thresholds are much farther from being understood than those for f(n,k,\ell) , at least for general values of k . Erdős also posed several problems about determining \phi(n,k,\ell) for small values of k and \ell ; in particular, in [ 6 ] he asked whether g(n,4,5)=\Omega(n^{2}) . Recently Tao [ 15 ] proved that the answer is no, which means that when k=4 , the quadratic threshold is 6 . See [ 14 , Section 7] for more about this problem. 1.2. A local properties problem for difference sets We study an arithmetic local properties problem, first described in [ 12 ] . Here, our large object is a set of numbers, and we think of a set of numbers as unstructured if it contains many distinct differences. More formally, for a set A\subseteq\mathbb{R} , we define the difference set of A to be A-A=\{\left\lvert a-b\right\rvert\mid a,b\in A,\,a\neq b\}. We only include positive differences in A-A ; this is nonstandard but more natural for this problem. We define g(n,k,\ell) to be the minimum value of \left\lvert A-A\right\rvert over all n -element sets A\subseteq\mathbb{R} with the property that every k -element subset A^{\prime}\subseteq A satisfies \lvert A^{\prime}-A^{\prime}\rvert\geq\ell , which we refer to as the (k,\ell) -local property . We think of k and \ell as constants, and study the asymptotic behavior of g(n,k,\ell) as n\to\infty . (We use standard asymptotic notation throughout this paper; all asymptotic notation is as n\to\infty , and the implicit constants may depend on k , \ell , and any other relevant parameters.) This problem can be viewed as a one-dimensional version of the local properties problem for distinct distances — in particular, we have (1.1) g(n,k,\ell)\geq\phi(n,k,\ell)\geq f(n,k,\ell) (since any

Read the complete text