Cardinalities of g g -difference sets
Michael Tait, Eric Schmutz · 2025
Read Cardinalities of g g -difference sets by Michael Tait, Eric Schmutz (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-11736.txt.
Introduction
Eric Schmutz and Michael Tait prove new results on difference sets in a 2025 mathematics paper. A g-difference basis is a set of integers where each target value has at least g representations as a difference of two members. The question is how small such a set can be.
The authors show that a scaled size limit exists and is finite and non-zero as the range grows. That settles a question raised by Kravitz. A twin problem over vector spaces above a finite field is also solved. There the largest set with at most g representations has a clean growth form. Both results sharpen what is known about additive structure.
Catalog record
| CREATOR | Michael Tait, Eric Schmutz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-11736
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cardinalities of g g -difference sets Michael Tait, Eric Schmutz Abstract Let η g ( n ) \eta_{g}(n) be the smallest cardinality that A ⊆ ℤ A\subseteq{\mathbb{Z}} can have if A A is a g g -difference basis for [ n ] [n] (i.e, if, for each x ∈ [ n ] x\in[n] , there are at least g g solutions to a 1 − a 2 = x a_{1}-a_{2}=x ). We prove that the finite, non-zero limit lim n → ∞ η g ( n ) n \lim\limits_{n\rightarrow\infty}\frac{\eta_{g}(n)}{\sqrt{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 ) \alpha_{g}(n) be the largest cardinality that A ⊆ [ n ] A\subseteq[n] can have if, for all nonzero x x , a 1 − a 2 = x a_{1}-a_{2}=x has at most g g solutions. We also prove that α g ( n ) = g n ( 1 + o g ( 1 ) ) \alpha_{g}(n)={\sqrt{gn}}(1+o_{g}(1)) as n → ∞ n\rightarrow\infty . 1 Introduction Suppose n and g are positive integers. We say that “ A is a g -difference basis for [n] ”if A is a set of integers and, for each x\in\{1,2,3\dots,n\} , there are at least g solutions (a_{1},a_{2})\in A\times A to the equation a_{1}-a_{2}=x . When g=1 we will use “difference basis” to mean 1 -difference basis. It is a natural question to ask what the minimum size of a g -difference basis for [n] is. More generally, for a subset A of an abelian group G , one can define the representation function r_{A-A}:G\rightarrow{\mathbb{Z}} by r_{A-A}(d)=|\{(a,a^{\prime})\in A\times A:d=a-a^{\prime}\}|. For g a natural number and S\subseteq G , define \eta_{g}(S)=\min\{|A|:A\subseteq G,r_{A-A}(x)\geq g\mbox{ for all }x\in S\}, and \alpha_{g}(S)=\max\{|A|:A\subseteq G,r_{A-A}(x)\leq g\mbox{ for all }x\in S,x\not=0\}. When G=\mathbb{Z} and S=\{1,\cdots,n\} , we will use the notation \eta_{g}(n) and \alpha_{g}(n) to mean \eta_{g}(\{1,\cdots,n\}) and \alpha_{g}(\{1,\cdots,n\}) respectively, following the notation of [ 20 ] and [ 31 ] . In [ 20 ] , Kravitz asserts that the main theorem in his paper can be strengthened, provided one can verify that the limit \lim\limits_{n\rightarrow\infty}\frac{\eta_{g}(n)}{\sqrt{n}} exists and is a finite non-zero real number. He asks whether this limit exists in Question 7.4 of [ 20 ] and writes that “it seems very likely” [that it does]. For the special case g=1 , Rédei and Rényi [ 27 ] proved that the limit does exist. Leonid Mirsky’s helpful MathSciNet review [ 22 ] outlines the proof. We show that this proof can be modified in such a way that it works for any g . Hence our first goal is to verify Kravitz’s conjecture. Theorem 1 . The limit \lim\limits_{n\rightarrow\infty}\frac{\eta_{g}(n)}{\sqrt{n}} exists and is a positive real number. It is also interesting to investigate \eta_{g}(G) and \alpha_{g}(G) for other groups G than the integers. Bounds in one direction for each function come from counting, but finding constructions seems highly dependent on the specific group. In particular, it is not known if there exists an \epsilon>0 such that \eta_{1}(G)>\epsilon\sqrt{|G|} for any finite abelian group G (see the discussion after Problem 31 in [ 18 ] ). In this paper we consider the case that G=\mathbb{F}_{p}^{n} . In this setting it seems that the parity of n plays a role, and we can only show that the “even limit” and “odd limit” each exist. Theorem 2 . Let p an odd prime and g a natural number be fixed. Then the limits L_{e}=\lim_{k\to\infty}\frac{\eta_{g}\left(\mathbb{F}_{p}^{2k}\right)}{\sqrt{p^{2k}}} and L_{o}=\lim_{k\to\infty}\frac{\eta_{g}\left(\mathbb{F}_{p}^{2k+1}\right)}{\sqrt{p^{2k+1}}} both exist and are positive real numbers. Contrary to the situation in the integers, we in fact conjecture that these limits are not the same. Conjecture 1 . For L_{e} and L_{o} defined in Theorem 2 , L_{e}\not=L_{o}. Next we turn our attention to bounding the number of representations from above. From Corollary 1.4 in [ 31 ] (and the paragraph above it) one can easily deduce that that \alpha_{g}(n)=\Theta\left(\sqrt{gn}\right) and that \lim\limits_{g\rightarrow\infty}\liminf_{n\to\infty}\frac{\alpha_{g}(n)}{\sqrt{gn}}=\lim\limits_{g\rightarrow\infty}\limsup_{n\to\infty}\frac{\alpha_{g}(n)}{\sqrt{gn}}. The results from [ 31 ] do not determine whether or not \liminf_{n\to\infty}\frac{\alpha_{g}(n)}{\sqrt{gn}}=\limsup_{n\to\infty}\frac{\alpha_{g}(n)}{\sqrt{gn}}. We therefore strengthen the result in [ 31 ] by proving the following theorem. Theorem 3 . Let g be a positive integer. Then \alpha_{g}(n)=(1+o_{g}(1))\sqrt{gn} . In this theorem, the o_{g}(1) term goes to 0 as n goes to infinity and the subscript g indicates that the rate of convergence may depend on g . In other words, there is a function \delta(g,n) such that: • \frac{\alpha_{g}(n)}{\sqrt{gn}}=1+\delta(g,n) , and • for every g , \lim\limits_{n\rightarrow\infty}\delta(g,n)=0. In Sections 2 , 3 , and 4 , we prove Theorems 1 , 2 , and 3 respectively. In Section 5 we discuss similar problems but for sums instead of differences and then we give some applications of these problems in coding theory and cryptography. 2 Difference Bases of Integers 2.1 Crude Bounds The first step is to verify the “trivial” lower bound for \eta_{g}(n) that is mentioned on page 200 (second page of the paper) of [ 20 ] . We actually use this bound, so the proof is written out explicitly in Lemma 1 below. More or less the same argument is outlined on page 51 of [ 5 ] for g=1 . Brauer made a similar argument for “restricted” difference bases in [ 7 ] . Lemma 1 . For all n>1 , \frac{\eta_{g}(n)}{\sqrt{n}}\geq\sqrt{2g}. Proof. Suppose that D is a finite set, that f:D\rightarrow Y , and that S is a finite subset of Y . The preimages f^{-1}(y) , y\in S are disjoint, therefore |D|\geq\sum\limits_{y\in S}|f^{-1}(y)| . If |f^{-1}(y)|\geq g for all y\in S , then |D|\geq g|S|. (1) Now consider the special case where: • Y={\mathbb{Z}}_{+} , and S=[n] , and • A_{n} is a g -difference basis for [n] with |A_{n}|=\eta_{g}(n) , and • D={A_{n}\choose 2} is the set of all {|A_{n}|\choose 2} two-element subsets of A_{n} , and • the function f is defined by f(\{a_{1},a_{2}\})=|a_{1}-a_{2}| . Observe that \eta_{g}(n)^{2}=|A_{n}|^{2}>|A_{n}|\left(|A_{n}|-1\right)=2|D|. Applying the inequality ( 1 ), we get \eta_{g}(n)^{2}\geq 2gn. Taking square roots we get Lemma 1 . ∎ The next lemma constructs a 1 -difference basis that is essentially the same as that in [ 22 , 27 ] . We needed to make the n -dependence explicit. Lemma 2 . Let k_{n}=\lceil\sqrt{n}\ \rceil . The 2k_{n} -element set B_{n}:=\{1,2,3,\dots k_{n}-1\}\cup\{k_{n},2k_{n},3k_{n},\dots,k_{n}^{2},(k_{n}+1)k_{n}\} is a 1-difference basis for [n] . Proof. Suppose x\in[n] . We need to write x as the difference of two elements of B_{n} . Case 1: x<k_{n} . Observe that x=k_{n}-(k_{n}-x) . In case 1, both k_{n} and (k_{n}-x) are elements of B_{n} . Case 2: x=k_{n} . Observe that k_{n}=2k_{n}-k_{n} . Both k_{n} and 2k_{n} are elements of B_{n} . Case 3: x>k_{n} . Divide x by k_{n} using the division algorithm. If r and q are the remainder and quotient respectively, then x=k_{n}q+r , where 0\leq r<k_{n} and q=\lfloor\frac{x}{k_{n}}\rfloor . Therefore x=k_{n}(q+1)-(k_{n}-r) . In case 3, (k_{n}-r) is an element of B_{n} . To verify that k_{n}(q+1) is also in B_{n} , we need only check that q+1\leq k_{n}+1 . Since the floor function is non-decreasing, we have q=\left\lfloor\frac{x}{k_{n}}\right\rfloor\leq\left\lfloor\frac{n}{k_{n}}\right\rfloor\leq\frac{n}{k_{n}}\leq\frac{n}{\sqrt{n}}\leq\lceil\sqrt{n}\rceil=k_{n}. ∎ Now notice that, translation does not change the distances between