2025/01/19 by Das, Sanjana
Mathematics · Engineering · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Meromorphic and Entire Functions
paper · pdf · doi:10.48550/arxiv.2501.11148
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, ℓ) to be the minimum number of differences in an n-element set with the `local property' that every k-element subset has at least ℓ differences; we study the asymptotic behavior of g(n, k, ℓ) as k and ℓ are fixed and n → ∞. The quadratic threshold is the smallest ℓ (as a function of k) for which g(n, k, ℓ) = Ω(n2); its value is known when k is even. In this paper, we show that for k even, when ℓ is one below the quadratic threshold, we have g(n, k, ℓ) = O(nc) for an absolute constant c < 2 -- i.e., at the quadratic threshold, the `exponent of n in g(n, k, ℓ)' jumps by a constant independent of k.