Cardinalities of g-difference sets

2025/01/20 by Eric Schmutz, Schmutz, Eric, Michael Tait +1 · 1 citation
Engineering · #05B10 #11B13 #11B75 #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2501.11736

openalex publication_date 2025/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let η_g(n) be the smallest cardinality that A⊆ \mathbb Z can have if A is a g-difference basis for [n] (i.e, if, for each x∈ [n], there are \em at least g solutions to a₁-a₂=x ). We prove that the finite, non-zero limit lim_{n→ ∞}\fracη_g(n)√(n) exists, answering a question of Kravitz. We also investigate a similar problem in the setting of a vector space over a finite field. Let α_g(n) be the largest cardinality that A⊆ [n] can have if, for all nonzero x, a₁-a₂=x has \em at most g solutions. We also prove that α_g(n)=√(gn)(1+o_g(1)) as n→∞.

Cited by

• Generalized additive bases and difference bases for Cartesian product of finite abelian groups

Related

• Squares and difference sets in finite fields
• Sets with few differences in abelian groups
• A new upper bound for sets with no square differences
• A new upper bound for sets with no square differences
• Bounds for the local properties problem for difference sets