Introduction
Let A ⊂ Z A \subset\mathbb{Z} A ⊂ Z be a finite subset. The sumset of A A A is
A + A = { a + a ′ : a , a ′ ∈ A } = 2 A A + A = \{a + a' : a,a' \in A\} = 2A A + A = { a + a ′ : a , a ′ ∈ A } = 2 A
and its h h h -fold sumset is
h A = ( h − 1 ) A + A = { a + a ′ : a ∈ A , a ′ ∈ ( h − 1 ) A } , hA = (h-1)A + A = \{a + a' : a \in A,\ a' \in(h-1)A\}, h A = ( h − 1 ) A + A = { a + a ′ : a ∈ A , a ′ ∈ ( h − 1 ) A } ,
where 1 A = A 1A = A 1 A = A and repetition is allowed.
The size of h A hA h A has been studied in two complementary regimes. In the first, the set A A A is fixed and h → ∞ h \to\infty h → ∞ . Nathanson [10 ] proved that if A A A is a finite set of integers with min A = 0 \min A = 0 min A = 0 and gcd ( A ) = 1 \gcd(A) = 1 g cd( A ) = 1 , then for all sufficiently large h h h , the integers in [ 0.. h max A ] [0..h\max A] [ 0.. h max A ] that are missing from h A hA h A form two finite sets, one near each endpoint of this interval, which do not depend on h h h up to translation. In particular, ∣ h A ∣ |hA| ∣ h A ∣ is eventually a linear function of h h h . Khovanskii [Kho92] proved that for a finite subset A A A of Z d \mathbb{Z}^d Z d , ∣ h A ∣ |hA| ∣ h A ∣ agrees with a polynomial in h h h for all sufficiently large h h h . Nathanson and Ruzsa [NR02] gave an elementary lattice-point proof of eventual polynomial growth for finite subsets of abelian semigroups. For finite subsets of Z d \mathbb{Z}^d Z d , Granville, Shakan and Walker [5 ] gave effective bounds on how large h h h must be. A finite set B B B of integers is sum-dominant if ∣ B + B ∣ > ∣ B − B ∣ |B+B| > |B-B| ∣ B + B ∣ > ∣ B − B ∣ . In the study of such sets, Iyer, Lazarev, Miller and Zhang [7 ] determined the limiting behavior of h A hA h A for an arbitrary finite set A A A as h → ∞ h \to\infty h → ∞ , together with a bound on how large h h h must be for this behavior to appear. They also proved that no set A A A has the property that A , 2 A , … , h A A, 2A, \ldots, hA A , 2 A , … , h A are all sum-dominant for every h h h .
In the second regime, which is the subject of this paper, h h h is fixed or grows slowly with q q q , and A A A is a k k k -element subset of { 1 , … , q } \{1,\ldots,q\} { 1 , … , q } with q → ∞ q \to\infty q → ∞ . A k k k -element set A A A is a B h B_h B h -set when ∣ h A ∣ |hA| ∣ h A ∣ attains the universal upper bound M h , k M_{h,k} M h , k (see Definition 2.2 ). For h = 2 h=2 h = 2 these are the Sidon sets, studied by Erdős and Turán [4 ] , and Bose and Chowla [3 ] constructed large B h B_h B h -sets for every h h h . We refer to O’Bryant’s survey [14 ] for the extensive literature on these sets. Nathanson [11 ] proved that almost all k k k -element subsets of [ q ] [q] [ q ] are Sidon sets, even when k k k grows with q q q at a suitable rate. Random subsets of intervals are also central to the study of sum-dominant sets. Martin and O’Bryant [9 ] proved that a positive proportion of subsets of { 0 , … , n } \{0,\ldots,n\} { 0 , … , n } are sum-dominant, and Hegarty and Miller [6 ] proved that when the elements of [ q ] [q] [ q ] are chosen independently with probability p ( q ) p(q) p ( q ) satisfying p ( q ) → 0 p(q) \to0 p ( q ) → 0 and q p ( q ) → ∞ qp(q) \to\infty q p ( q ) → ∞ , almost all sets have more differences than sums.
One particular approach has been to study the cardinalities of ∣ h A ∣ |hA| ∣ h A ∣ for various values of h h h . Nathanson [12 Problem 5] first studied the most frequent sizes of ∣ h A ∣ |hA| ∣ h A ∣ for ∣ A ∣ = 4 |A|=4 ∣ A ∣ = 4 and observed triangular gaps between them. O’Bryant proved a formula for the initial sequence of sumset sizes in terms of the successive L 1 L^1 L 1 -minima of a lattice and gave a heuristic explanation of the observed frequencies [15 ] . The fourth listed author studied this problem further, and proved this phenomenon to be true for k = 4 k=4 k = 4 [16 Thm. 2] . He also suggested that for k > 4 k>4 k > 4 , analogous “champagnerpyramid” numbers would describe the sumset-size deficits [16 Sec. 4] . These are ( k − 1 ) (k-1) ( k − 1 ) -dimensional simplex numbers, whose consecutive differences are ( k − 2 ) (k-2) ( k − 2 ) -dimensional simplex numbers. We prove that this gap pattern holds for all fixed k ≥ 3 k \ge3 k ≥ 3 by generalizing the fourth author’s constructions, as we now explain.
For h ≥ 0 h \ge0 h ≥ 0 , let
X h , k = { x = ( x 1 , … , x k ) ∈ Z ≥ 0 k : ∑ i = 1 k x i = h } . \mathcal{X}_{h,k}=\left\{\mathbf{x}=(x_1,\ldots,x_k)\in\mathbb{Z}_{\ge0}^k:\sum_{i=1}^{k}x_i=h\right\}. X h , k = { x = ( x 1 , … , x k ) ∈ Z ≥ 0 k : i = 1 ∑ k x i = h } .
We call elements of X h , k \mathcal{X}_{h,k} X h , k sum vectors since by representing elements of A = { a 1 < a 2 < ⋯ < a k } A=\{a_1<a_2<\cdots<a_k\} A = { a 1 < a 2 < ⋯ < a k } as A ⃗ = ( a 1 , a 2 , … , a k ) ∈ Z ≥ 0 k \vec{A}=(a_1,a_2,\ldots,a_k)\in\mathbb{Z}_{\ge0}^k A = ( a 1 , a 2 , … , a k ) ∈ Z ≥ 0 k we can produce any element of h A hA h A . We may redefine h A hA h A as
h A = { x ⋅ A ⃗ : x ∈ X h , k } . hA=\{\mathbf{x}\cdot\vec{A}:\mathbf{x}\in\mathcal{X}_{h,k}\}. h A = { x ⋅ A : x ∈ X h , k } .
Let
M h , k = ∣ X h , k ∣ = ( h + k − 1 k − 1 ) , M − 1 , k = 0 M_{h,k}=|\mathcal{X}_{h,k}|=\binom{h+k-1}{k-1},\qquad M_{-1,k}=0 M h , k = ∣ X h , k ∣ = ( k − 1 h + k − 1 ) , M − 1 , k = 0
be the maximum possible size of h A hA h A . We are ready to state our main result.
Theorem 1.1. Let k ≥ 3 k\ge3 k ≥ 3 be fixed, and let q → ∞ q\to\infty q → ∞ and h = h ( q ) ≥ 2 h=h(q)\ge2 h = h ( q ) ≥ 2 with h = o ( q 1 / k ) h=o(q^{1/k}) h = o ( q 1/ k ) . For 0 ≤ ℓ < h 0\le\ell<h 0 ≤ ℓ < h , let
P ℓ = M h , k − M ℓ − 1 , k . P_\ell=M_{h,k}-M_{\ell-1,k}. P ℓ = M h , k − M ℓ − 1 , k . Then the following statements hold.
# { A ∈ ( [ q ] k ) : ∣ h A ∣ = M h , k } = Θ ( q k ) . (1) \#\left\{A\in\binom{[q]}{k}:|hA|=M_{h,k}\right\}=\Theta(q^k). \tag*{(1)} # { A ∈ ( k [ q ] ) : ∣ h A ∣ = M h , k } = Θ ( q k ) . (1) # { A ∈ ( [ q ] k ) : ∣ h A ∣ ∉ { P 0 , … , P h − 1 } } = O ( h 2 k − 2 q k − 2 ) . (2) \#\left\{A\in\binom{[q]}{k}:|hA|\notin\{P_0,\ldots,P_{h-1}\}\right\}=O(h^{2k-2}q^{k-2}). \tag*{(2)} # { A ∈ ( k [ q ] ) : ∣ h A ∣ ∈ / { P 0 , … , P h − 1 } } = O ( h 2 k − 2 q k − 2 ) . (2) # { A ∈ ( [ q ] k ) : ∣ h A ∣ = P ℓ } = Ω ( q k − 1 h − ℓ + 1 ) . (3) \#\left\{A\in\binom{[q]}{k}:|hA|=P_\ell\right\}=\Omega\left(\frac{q^{k-1}}{h-\ell+1}\right). \tag*{(3)} # { A ∈ ( k [ q ] ) : ∣ h A ∣ = P ℓ } = Ω ( h − ℓ + 1 q k − 1 ) . (3)
Accordingly, we show that the natural gaps between the most frequent sizes of ∣ h A ∣ |hA| ∣ h A ∣ are of the form
( ℓ + k − 2 k − 2 ) , \binom{\ell+k-2}{k-2}, ( k − 2 ℓ + k − 2 ) ,
which specialize to the triangular numbers when k = 4 k=4 k = 4 .
The results of this paper have been formalized in the Lean 4 proof assistant with the Mathlib library [2 ] . Part of the Lean code was written by Awan, and part was generated by Aristotle, the automated theorem prover developed by Harmonic [1 ] . Every proof, including the generated ones, is checked by the Lean kernel, with the one exception noted at the end of this paragraph. The formalization contains no sorry. It proves Lemmas 3.2, 3.4, 3.6, 5.3 and 5.6, Propositions 3.5, 5.4 and 5.7, Theorem 1.1 for fixed h h h together with explicit versions of its three bounds, which hold once q q q exceeds an explicit polynomial in h h h and imply Theorem 1.1 as stated, Corollaries 4.1 and 5.1, Remark 5.2, and Examples 2.3, 3.3 and 3.7. In particular, it contains a proof of Lemma 5.3, for which we only cite Senger’s argument, and it proves Lemma 3.6 directly for every k k k , without using O’Bryant’s theorem. For Remark 4.2, the formalization proves the conclusion of Corollary 4.1 for every q > 70 ⋅ 2 k k ! h ( 2 h + 1 ) 2 k − 2 q>70\cdot2^k k!h(2h+1)^{2k-2} q > 70 ⋅ 2 k k ! h ( 2 h + 1 ) 2 k − 2 , which is 70 times the threshold stated there, and it checks the computation for ( h , k ) = ( 3 , 4 ) (h,k)=(3,4) ( h , k ) = ( 3 , 4 ) and 16 ≤ q ≤ 50 16\le q\le50 16 ≤ q ≤ 50 with native_decide, which relies on Lean’s compiler in addition to its kernel.
Acknowledgments
We thank the organizers of the Polymath Jr. research group whose efforts brought about this collaboration. This work was supported by the National Science Foundation under Grant DMS2341670.
Background
Throughout we assume familiarity with standard definitions and notation of additive and algebraic combinatorics; see, e.g., [TV06, Sta11].
For integers u ≤ v u \le v u ≤ v and q ≥ 1 q \ge1 q ≥ 1 , we write
[ u . . v ] = { n ∈ Z : u ≤ n ≤ v } , [ q ] = [ 1.. q ] . [u..v] = \{n \in\mathbb{Z} : u \le n \le v\}, \qquad[q] = [1..q]. [ u .. v ] = { n ∈ Z : u ≤ n ≤ v } , [ q ] = [ 1.. q ] .
Definition 2.1. Let q ≥ k ≥ 1 q \ge k \ge1 q ≥ k ≥ 1 . The set of k k k -element subsets of [ q ] [q] [ q ] is
( [ q ] k ) = { A ⊆ [ q ] : ∣ A ∣ = k } . \binom{[q]}{k} = \{A \subseteq[q] : |A| = k\}. ( k [ q ] ) = { A ⊆ [ q ] : ∣ A ∣ = k } . For A ∈ ( [ q ] k ) A \in\binom{[q]}{k} A ∈ ( k [ q ] ) , we always list the elements of A A A in increasing order, a 1 < a 2 < ⋯ < a k a_1 < a_2 < \cdots< a_k a 1 < a 2 < ⋯ < a k , and we call
A ⃗ = ( a 1 , a 2 , … , a k ) ∈ [ q ] k \vec{A} = (a_1,a_2,\ldots,a_k) \in[q]^k A = ( a 1 , a 2 , … , a k ) ∈ [ q ] k the set vector of A A A .
The map A ↦ A ⃗ A \mapsto\vec{A} A ↦ A is injective, so we may count subsets of [ q ] [q] [ q ] by counting their set vectors in [ q ] k [q]^k [ q ] k .
Definition 2.2. Let A ∈ ( [ q ] k ) A \in\binom{[q]}{k} A ∈ ( k [ q ] ) and h ≥ 1 h \ge1 h ≥ 1 . The set A A A is a B h B_h B h -set if ∣ h A ∣ = M h , k |hA| = M_{h,k} ∣ h A ∣ = M h , k . Following [16 ] , an element n ∈ h A n \in hA n ∈ h A is a collision in h A hA h A if n n n can be written in at least two different ways as a sum of h h h elements of A A A listed in nondecreasing order.
For instance, a 1 + a 2 a_1+a_2 a 1 + a 2 and a 2 + a 1 a_2+a_1 a 2 + a 1 are not two different ways of writing an element of 2 A 2A 2 A , since only a 1 + a 2 a_1+a_2 a 1 + a 2 is listed in nondecreasing order. A sum of h h h elements of A A A listed in nondecreasing order is determined by the number of times each a i a_i a i occurs in it, that is, by a sum vector in X h , k X_{h,k} X h , k . Hence n n n is a collision in h A hA h A exactly when n = x ⋅ A ⃗ = y ⋅ A ⃗ n = \mathbf{x} \cdot\vec{A} = \mathbf{y} \cdot\vec{A} n = x ⋅ A = y ⋅ A for distinct x , y ∈ X h , k \mathbf{x},\mathbf{y} \in X_{h,k} x , y ∈ X h , k . Consequently, A A A is a B h B_h B h -set if and only if h A hA h A has no collisions, that is, if and only if the map x ↦ x ⋅ A ⃗ \mathbf{x} \mapsto\mathbf{x} \cdot\vec{A} x ↦ x ⋅ A is injective on X h , k X_{h,k} X h , k .
Example 2.3. Let q ≥ 3 q \ge3 q ≥ 3 and E = { 1 , 2 , 3 } ∈ ( [ q ] 3 ) E = \{1,2,3\} \in\binom{[q]}{3} E = { 1 , 2 , 3 } ∈ ( 3 [ q ] ) , so that E ⃗ = ( 1 , 2 , 3 ) \vec{E} = (1,2,3) E = ( 1 , 2 , 3 ) . The integer 8 is a collision in 4 E 4E 4 E , because
1 + 2 + 2 + 3 = 1 + 1 + 3 + 3 = 2 + 2 + 2 + 2 = 8. 1+2+2+3 = 1+1+3+3 = 2+2+2+2 = 8. 1 + 2 + 2 + 3 = 1 + 1 + 3 + 3 = 2 + 2 + 2 + 2 = 8. In terms of sum vectors in X 4 , 3 X_{4,3} X 4 , 3 , this reads
( 1 , 2 , 1 ) ⋅ E ⃗ = ( 2 , 0 , 2 ) ⋅ E ⃗ = ( 0 , 4 , 0 ) ⋅ E ⃗ = 8. (1,2,1) \cdot\vec{E} = (2,0,2) \cdot\vec{E} = (0,4,0) \cdot\vec{E} = 8. ( 1 , 2 , 1 ) ⋅ E = ( 2 , 0 , 2 ) ⋅ E = ( 0 , 4 , 0 ) ⋅ E = 8. Moreover, 4 E = [ 4..12 ] 4E = [4..12] 4 E = [ 4..12 ] , so ∣ 4 E ∣ = 9 < 15 = M 4 , 3 |4E| = 9 < 15 = M_{4,3} ∣4 E ∣ = 9 < 15 = M 4 , 3 and E E E is not a B 4 B_4 B 4 -set.
Definition 2.4. Let f : N → R f : \mathbb{N} \to\mathbb{R} f : N → R and g : N → R > 0 g : \mathbb{N} \to\mathbb{R}_{>0} g : N → R > 0 . We write f ( q ) = O ( g ( q ) ) f(q) = O(g(q)) f ( q ) = O ( g ( q )) if there exist C > 0 C > 0 C > 0 and q 0 ∈ N q_0 \in\mathbb{N} q 0 ∈ N such that ∣ f ( q ) ∣ ≤ C g ( q ) |f(q)| \le Cg(q) ∣ f ( q ) ∣ ≤ C g ( q ) for all q ≥ q 0 q \ge q_0 q ≥ q 0 , and f ( q ) = Ω ( g ( q ) ) f(q) = \Omega(g(q)) f ( q ) = Ω ( g ( q )) if there exist c > 0 c > 0 c > 0 and q 0 ∈ N q_0 \in\mathbb{N} q 0 ∈ N such that f ( q ) ≥ c g ( q ) f(q) \ge cg(q) f ( q ) ≥ c g ( q ) for all q ≥ q 0 q \ge q_0 q ≥ q 0 . We write f ( q ) = Θ ( g ( q ) ) f(q) = \Theta(g(q)) f ( q ) = Θ ( g ( q )) if f ( q ) = O ( g ( q ) ) f(q) = O(g(q)) f ( q ) = O ( g ( q )) and f ( q ) = Ω ( g ( q ) ) f(q) = \Omega(g(q)) f ( q ) = Ω ( g ( q )) .
From here on, all asymptotic notation is with respect to q → ∞ q \to\infty q → ∞ , and k ≥ 3 k \ge3 k ≥ 3 is fixed. We treat h = h ( q ) ≥ 2 h = h(q) \ge2 h = h ( q ) ≥ 2 as a second asymptotic parameter, which may grow with q q q . The constants C C C and c c c depend only on k k k , and q 0 q_0 q 0 depends only on k k k and on the function h h h . Each statement records the growth condition on h h h that it needs. In Section 5, h h h is fixed, and the constants there may also depend on h h h .
Preliminary Lemmas
Throughout this section, A ∈ ( [ q ] k ) A \in\binom{[q]}{k} A ∈ ( k [ q ] ) and A ⃗ \vec{A} A is its set vector. Collisions in h A hA h A correspond to integer vectors d \mathbf{d} d with coordinate sum zero and d ⋅ A ⃗ = 0 \mathbf{d} \cdot\vec{A} = 0 d ⋅ A = 0 . We normalize these vectors as follows.
Definition 3.1. Let d = ( d 1 , … , d k ) ∈ Z k \mathbf{d} = (d_1,\ldots,d_k) \in\mathbb{Z}^k d = ( d 1 , … , d k ) ∈ Z k be a nonzero vector with ∑ i d i = 0 \sum_i d_i = 0 ∑ i d i = 0 . Let d + = ( d 1 + , … , d k + ) \mathbf{d}^{+} = (d_1^{+},\ldots,d_k^{+}) d + = ( d 1 + , … , d k + ) and d − = ( d 1 − , … , d k − ) \mathbf{d}^{-} = (d_1^{-},\ldots,d_k^{-}) d − = ( d 1 − , … , d k − ) , where
d i + = max { d i , 0 } , d i − = max { − d i , 0 } , d_i^{+} = \max\{d_i,0\}, \qquad d_i^{-} = \max\{-d_i,0\}, d i + = max { d i , 0 } , d i − = max { − d i , 0 } , so that d = d + − d − \mathbf{d} = \mathbf{d}^{+} - \mathbf{d}^{-} d = d + − d − . The weight of d \mathbf{d} d is
w ( d ) = ∑ i d i + = ∑ i d i − . w(\mathbf{d}) = \sum_i d_i^{+} = \sum_i d_i^{-}. w ( d ) = i ∑ d i + = i ∑ d i − .
The vector d \mathbf{d} d is primitive if gcd ( ∣ d 1 ∣ , … , ∣ d k ∣ ) = 1 \gcd(|d_1|,\ldots,|d_k|) = 1 g cd( ∣ d 1 ∣ , … , ∣ d k ∣ ) = 1 . Let j ( d ) j(\mathbf{d}) j ( d ) be the least index i i i with d i ≠ 0 d_i \ne0 d i = 0 .
The set of coefficient vectors of weight at most h h h is
R h , k = { d ∈ Z k ∖ { 0 } : d 1 + ⋯ + d k = 0 , w ( d ) ≤ h , gcd ( ∣ d 1 ∣ , … , ∣ d k ∣ ) = 1 , d j ( d ) > 0 } . (4) \mathcal{R}_{h,k}=\left\{\mathbf{d}\in\mathbb{Z}^{k}\setminus\{\mathbf{0}\}: \begin{aligned} d_{1}+\cdots+d_{k}&=0,\qquad w(\mathbf{d})\le h,\\ \gcd(\lvert d_{1}\rvert,\ldots,\lvert d_{k}\rvert)&=1,\qquad d_{j}(\mathbf{d})>0 \end{aligned}\right\}. \tag*{(4)} R h , k = { d ∈ Z k ∖ { 0 } : d 1 + ⋯ + d k g cd(∣ d 1 ∣ , … , ∣ d k ∣) = 0 , w ( d ) ≤ h , = 1 , d j ( d ) > 0 } . (4)
The condition d j ( d ) > 0 d_{j}(\mathbf{d})>0 d j ( d ) > 0 selects one vector from each pair { d , − d } \{\mathbf{d},-\mathbf{d}\} { d , − d } .
Lemma 3.2. There exist distinct x , y ∈ X h , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h,k} x , y ∈ X h , k such that x ⋅ A ⃗ = y ⋅ A ⃗ \mathbf{x}\cdot\vec{A}=\mathbf{y}\cdot\vec{A} x ⋅ A = y ⋅ A if and only if there exists d ∈ R h , k \mathbf{d}\in\mathcal{R}_{h,k} d ∈ R h , k such that d ⋅ A ⃗ = 0 \mathbf{d}\cdot\vec{A}=0 d ⋅ A = 0 .
Proof. Suppose that distinct x , y ∈ X h , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h,k} x , y ∈ X h , k satisfy x ⋅ A ⃗ = y ⋅ A ⃗ \mathbf{x}\cdot\vec{A}=\mathbf{y}\cdot\vec{A} x ⋅ A = y ⋅ A . Let z = x − y \mathbf{z}=\mathbf{x}-\mathbf{y} z = x − y and g = gcd ( ∣ z 1 ∣ , … , ∣ z k ∣ ) g=\gcd(\lvert z_{1}\rvert,\ldots,\lvert z_{k}\rvert) g = g cd(∣ z 1 ∣ , … , ∣ z k ∣) . Then
∑ i = 1 k z i = ∑ i = 1 k x i − ∑ i = 1 k y i = h − h = 0 , \sum_{i=1}^{k}z_i=\sum_{i=1}^{k}x_i-\sum_{i=1}^{k}y_i=h-h=0, i = 1 ∑ k z i = i = 1 ∑ k x i − i = 1 ∑ k y i = h − h = 0 ,
z ⋅ A ⃗ = x ⋅ A ⃗ − y ⋅ A ⃗ = 0 , \mathbf{z}\cdot\vec{A}=\mathbf{x}\cdot\vec{A}-\mathbf{y}\cdot\vec{A}=0, z ⋅ A = x ⋅ A − y ⋅ A = 0 ,
w ( z ) = ∑ i = 1 k max { x i − y i , 0 } ≤ ∑ i = 1 k x i = h . w(\mathbf{z})=\sum_{i=1}^{k}\max\{x_i-y_i,0\}\le\sum_{i=1}^{k}x_i=h. w ( z ) = i = 1 ∑ k max { x i − y i , 0 } ≤ i = 1 ∑ k x i = h .
Choose ε ∈ { 1 , − 1 } \varepsilon\in\{1,-1\} ε ∈ { 1 , − 1 } so that ε z j ( z ) > 0 \varepsilon z_{j}(\mathbf{z})>0 ε z j ( z ) > 0 , and let d = ε z / g \mathbf{d}=\varepsilon\mathbf{z}/g d = ε z / g . Then
∑ i = 1 k d i = ε g ∑ i = 1 k z i = 0 , \sum_{i=1}^{k}d_i=\frac{\varepsilon}{g}\sum_{i=1}^{k}z_i=0, i = 1 ∑ k d i = g ε i = 1 ∑ k z i = 0 ,
gcd ( ∣ d 1 ∣ , … , ∣ d k ∣ ) = g g = 1 , \gcd(\lvert d_1\rvert,\ldots,\lvert d_k\rvert)=\frac{g}{g}=1, g cd(∣ d 1 ∣ , … , ∣ d k ∣) = g g = 1 ,
w ( d ) = w ( z ) g ≤ h , w(\mathbf{d})=\frac{w(\mathbf{z})}{g}\le h, w ( d ) = g w ( z ) ≤ h ,
d j ( d ) = ∣ z j ( z ) ∣ g > 0 , d_j(\mathbf{d})=\frac{\lvert z_j(\mathbf{z})\rvert}{g}>0, d j ( d ) = g ∣ z j ( z )∣ > 0 ,
d ⋅ A ⃗ = ε g z ⋅ A ⃗ = 0. \mathbf{d}\cdot\vec{A}=\frac{\varepsilon}{g}\mathbf{z}\cdot\vec{A}=0. d ⋅ A = g ε z ⋅ A = 0.
Thus d ∈ R h , k \mathbf{d}\in\mathcal{R}_{h,k} d ∈ R h , k .
Conversely, suppose that d ∈ R h , k \mathbf{d}\in\mathcal{R}_{h,k} d ∈ R h , k and d ⋅ A ⃗ = 0 \mathbf{d}\cdot\vec{A}=0 d ⋅ A = 0 . Let s = w ( d ) s=w(\mathbf{d}) s = w ( d ) , choose t ∈ X h − s , k \mathbf{t}\in\mathcal{X}_{h-s,k} t ∈ X h − s , k , and set x = d + + t \mathbf{x}=\mathbf{d}^{+}+\mathbf{t} x = d + + t and y = d − + t \mathbf{y}=\mathbf{d}^{-}+\mathbf{t} y = d − + t . Then
∑ i = 1 k x i = ∑ i = 1 k d i + + ∑ i = 1 k t i = s + ( h − s ) = h , \sum_{i=1}^{k}x_i=\sum_{i=1}^{k}d_i^{+}+\sum_{i=1}^{k}t_i=s+(h-s)=h, i = 1 ∑ k x i = i = 1 ∑ k d i + + i = 1 ∑ k t i = s + ( h − s ) = h ,
∑ i = 1 k y i = ∑ i = 1 k d i − + ∑ i = 1 k t i = s + ( h − s ) = h , \sum_{i=1}^{k}y_i=\sum_{i=1}^{k}d_i^{-}+\sum_{i=1}^{k}t_i=s+(h-s)=h, i = 1 ∑ k y i = i = 1 ∑ k d i − + i = 1 ∑ k t i = s + ( h − s ) = h ,
x − y = d + − d − = d ≠ 0 , \mathbf{x}-\mathbf{y}=\mathbf{d}^{+}-\mathbf{d}^{-}=\mathbf{d}\ne\mathbf{0}, x − y = d + − d − = d = 0 ,
x ⋅ A ⃗ − y ⋅ A ⃗ = ( x − y ) ⋅ A ⃗ = d ⋅ A ⃗ = 0. \mathbf{x}\cdot\vec{A}-\mathbf{y}\cdot\vec{A}=(\mathbf{x}-\mathbf{y})\cdot\vec{A}=\mathbf{d}\cdot\vec{A}=0. x ⋅ A − y ⋅ A = ( x − y ) ⋅ A = d ⋅ A = 0.
Since x \mathbf{x} x and y \mathbf{y} y are nonnegative integer vectors, these equalities give distinct x , y ∈ X h , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h,k} x , y ∈ X h , k with x ⋅ A ⃗ = y ⋅ A ⃗ \mathbf{x}\cdot\vec{A}=\mathbf{y}\cdot\vec{A} x ⋅ A = y ⋅ A . □
Example 3.3. In Example 2.3 , the equality ( 1 , 2 , 1 ) ⋅ E ⃗ = ( 0 , 4 , 0 ) ⋅ E ⃗ (1,2,1)\cdot\vec{E}=(0,4,0)\cdot\vec{E} ( 1 , 2 , 1 ) ⋅ E = ( 0 , 4 , 0 ) ⋅ E gives ( 1 , − 2 , 1 ) ⋅ E ⃗ = 0 (1,-2,1)\cdot\vec{E}=0 ( 1 , − 2 , 1 ) ⋅ E = 0 , and ( 1 , − 2 , 1 ) ∈ R 4 , 3 (1,-2,1)\in\mathcal{R}_{4,3} ( 1 , − 2 , 1 ) ∈ R 4 , 3 . This vector encodes the relation 1 + 3 = 2 + 2 1+3=2+2 1 + 3 = 2 + 2 . In fact, for every h ≥ 2 h\ge2 h ≥ 2 it is the only vector in R h , 3 \mathcal{R}_{h,3} R h , 3 orthogonal to E ⃗ \vec{E} E . Indeed, if d ⋅ E ⃗ = 0 \mathbf{d}\cdot\vec{E}=0 d ⋅ E = 0 and d 1 + d 2 + d 3 = 0 d_1+d_2+d_3=0 d 1 + d 2 + d 3 = 0 , then subtracting the second equation from the first gives d 2 + 2 d 3 = 0 d_2+2d_3=0 d 2 + 2 d 3 = 0 , so d = d 3 ( 1 , − 2 , 1 ) \mathbf{d}=d_3(1,-2,1) d = d 3 ( 1 , − 2 , 1 ) .
Lemma 3.4. Let d ( 1 ) , … , d ( r ) ∈ Z k \mathbf{d}^{(1)},\ldots,\mathbf{d}^{(r)}\in\mathbb{Z}^{k} d ( 1 ) , … , d ( r ) ∈ Z k be linearly independent. At most q k − r q^{k-r} q k − r vectors v ∈ [ q ] k \mathbf{v}\in[q]^k v ∈ [ q ] k obey
d ( 1 ) ⋅ v = ⋯ = d ( r ) ⋅ v = 0. \mathbf{d}^{(1)}\cdot\mathbf{v}=\cdots=\mathbf{d}^{(r)}\cdot\mathbf{v}=0. d ( 1 ) ⋅ v = ⋯ = d ( r ) ⋅ v = 0.
Proof. Let D D D be the r × k r \times k r × k matrix
D = ( d 1 ( 1 ) d 2 ( 1 ) ⋯ d k ( 1 ) d 1 ( 2 ) d 2 ( 2 ) ⋯ d k ( 2 ) ⋮ ⋮ ⋱ ⋮ d 1 ( r ) d 2 ( r ) ⋯ d k ( r ) ) . D = \begin{pmatrix}
d_1^{(1)} & d_2^{(1)} & \cdots& d_k^{(1)} \\
d_1^{(2)} & d_2^{(2)} & \cdots& d_k^{(2)} \\
\vdots& \vdots& \ddots& \vdots\\
d_1^{(r)} & d_2^{(r)} & \cdots& d_k^{(r)}
\end{pmatrix}. D = d 1 ( 1 ) d 1 ( 2 ) ⋮ d 1 ( r ) d 2 ( 1 ) d 2 ( 2 ) ⋮ d 2 ( r ) ⋯ ⋯ ⋱ ⋯ d k ( 1 ) d k ( 2 ) ⋮ d k ( r ) .
Since its rows are linearly independent,
rank ( D ) = r . \operatorname{rank}(D) = r. rank ( D ) = r .
By equality of row rank and column rank, there exist r r r linearly independent columns indexed by 1 ≤ j 1 < ⋯ < j r ≤ k 1 \le j_1 < \cdots< j_r \le k 1 ≤ j 1 < ⋯ < j r ≤ k . Thus the r × r r \times r r × r submatrix
D ′ = ( d j 1 ( 1 ) ⋯ d j r ( 1 ) ⋮ ⋱ ⋮ d j 1 ( r ) ⋯ d j r ( r ) ) D' = \begin{pmatrix}
d_{j_1}^{(1)} & \cdots& d_{j_r}^{(1)} \\
\vdots& \ddots& \vdots\\
d_{j_1}^{(r)} & \cdots& d_{j_r}^{(r)}
\end{pmatrix} D ′ = d j 1 ( 1 ) ⋮ d j 1 ( r ) ⋯ ⋱ ⋯ d j r ( 1 ) ⋮ d j r ( r )
satisfies
det ( D ′ ) ≠ 0 ⟹ ( D ′ ) − 1 exists . \det(D') \ne0 \Longrightarrow(D')^{-1}\text{ exists}. det ( D ′ ) = 0 ⟹ ( D ′ ) − 1 exists .
Let J = { j 1 , … , j r } J = \{j_1,\ldots,j_r\} J = { j 1 , … , j r } and fix the k − r k-r k − r coordinates v j v_j v j with j ∉ J j \notin J j ∈ / J . Writing v ′ = ( v j 1 , … , v j r ) T \mathbf{v}' = (v_{j_1},\ldots,v_{j_r})^{\mathsf{T}} v ′ = ( v j 1 , … , v j r ) T , we obtain
D v = 0 ⟺ D ′ v ′ = − ( ∑ j ∉ J d j ( 1 ) v j ⋮ ∑ j ∉ J d j ( r ) v j ) = b D\mathbf{v}=0 \Longleftrightarrow D'\mathbf{v}'=-\begin{pmatrix}
\sum_{j\notin J}d_j^{(1)}v_j\\
\vdots\\
\sum_{j\notin J}d_j^{(r)}v_j
\end{pmatrix}=\mathbf{b} D v = 0 ⟺ D ′ v ′ = − ∑ j ∈ / J d j ( 1 ) v j ⋮ ∑ j ∈ / J d j ( r ) v j = b
and hence
D ′ v ′ = b ⟹ v ′ = ( D ′ ) − 1 b . D'\mathbf{v}'=\mathbf{b}\Longrightarrow\mathbf{v}'=(D')^{-1}\mathbf{b}. D ′ v ′ = b ⟹ v ′ = ( D ′ ) − 1 b .
Thus each choice of the k − r k-r k − r fixed coordinates determines at most one vector v ′ \mathbf{v}' v ′ . Since each coordinate has q q q possible values, there are at most
vectors v ∈ [ q ] k \mathbf{v}\in[q]^k v ∈ [ q ] k satisfying D v = 0 D\mathbf{v}=0 D v = 0 .
Proposition 3.5. For h ≥ 2 h \ge2 h ≥ 2 ,
∣ R h , k ∣ ≤ ( 2 h + 1 ) k − 1 ≤ 3 k − 1 h k − 1 . \lvert R_{h,k}\rvert\le(2h+1)^{k-1}\le3^{k-1}h^{k-1}. ∣ R h , k ∣ ≤ ( 2 h + 1 ) k − 1 ≤ 3 k − 1 h k − 1 .
Moreover, any two distinct vectors in R h , k R_{h,k} R h , k are linearly independent.
Proof. For d ∈ R h , k \mathbf{d}\in R_{h,k} d ∈ R h , k , we have
− h ≤ − w ( d ) ≤ d i ≤ w ( d ) ≤ h , d k = − ∑ i = 1 k − 1 d i . -h\le-w(\mathbf{d})\le d_i\le w(\mathbf{d})\le h,\qquad d_k=-\sum_{i=1}^{k-1}d_i. − h ≤ − w ( d ) ≤ d i ≤ w ( d ) ≤ h , d k = − i = 1 ∑ k − 1 d i .
The first k − 1 k-1 k − 1 coordinates therefore determine d \mathbf{d} d , so
∣ R h , k ∣ = # { ( d 1 , … , d k − 1 ) : d ∈ R h , k } ≤ ∣ [ − h . . h ] k − 1 ∣ = ( 2 h + 1 ) k − 1 ≤ 3 k − 1 h k − 1 . \lvert R_{h,k}\rvert=\#\{(d_1,\ldots,d_{k-1}):\mathbf{d}\in R_{h,k}\}
\le\lvert[-h..h]^{k-1}\rvert=(2h+1)^{k-1}\le3^{k-1}h^{k-1}. ∣ R h , k ∣ = # {( d 1 , … , d k − 1 ) : d ∈ R h , k } ≤ ∣[ − h .. h ] k − 1 ∣ = ( 2 h + 1 ) k − 1 ≤ 3 k − 1 h k − 1 .
Suppose that d , e ∈ R h , k \mathbf{d},\mathbf{e}\in R_{h,k} d , e ∈ R h , k are linearly dependent. Since both are nonzero integer vectors, write e = ( a / b ) d \mathbf{e}=(a/b)\mathbf{d} e = ( a / b ) d with a , b ∈ Z a,b\in\mathbb{Z} a , b ∈ Z , b > 0 b>0 b > 0 and gcd ( ∣ a ∣ , b ) = 1 \gcd(\lvert a\rvert,b)=1 g cd(∣ a ∣ , b ) = 1 . Then
b e i = a d i for every i ⟹ b ∣ d i for every i be_i=ad_i\quad\text{for every }i\Longrightarrow b\mid d_i\quad\text{for every }i b e i = a d i for every i ⟹ b ∣ d i for every i
⟹ b ∣ gcd ( ∣ d 1 ∣ , … , ∣ d k ∣ ) = 1 \Longrightarrow b\mid\gcd(\lvert d_1\rvert,\ldots,\lvert d_k\rvert)=1 ⟹ b ∣ g cd(∣ d 1 ∣ , … , ∣ d k ∣) = 1
⟹ b = 1. \Longrightarrow b=1. ⟹ b = 1.
Consequently,
1 = gcd ( ∣ e 1 ∣ , … , ∣ e k ∣ ) = ∣ a ∣ gcd ( ∣ d 1 ∣ , … , ∣ d k ∣ ) = ∣ a ∣ . 1=\gcd(\lvert e_1\rvert,\ldots,\lvert e_k\rvert)=\lvert a\rvert\gcd(\lvert d_1\rvert,\ldots,\lvert d_k\rvert)=\lvert a\rvert. 1 = g cd(∣ e 1 ∣ , … , ∣ e k ∣) = ∣ a ∣ g cd(∣ d 1 ∣ , … , ∣ d k ∣) = ∣ a ∣ .
Thus a ∈ { 1 , − 1 } a \in\{1,-1\} a ∈ { 1 , − 1 } . The sign convention in (4) gives
0 < e j ( e ) = a d j ( d ) , d j ( d ) > 0 ⟹ a = 1 ⟹ e = d . 0 < e_j(\mathbf e)=a d_j(\mathbf d),\qquad d_j(\mathbf d)>0 \qquad\Longrightarrow\qquad a=1 \qquad\Longrightarrow\qquad\mathbf e=\mathbf d. 0 < e j ( e ) = a d j ( d ) , d j ( d ) > 0 ⟹ a = 1 ⟹ e = d .
Hence distinct vectors in R h , k \mathcal{R}_{h,k} R h , k are linearly independent. □
Lemma 3.6 (cf. [15 Thm. 1] ). Suppose there is exactly one d ∈ R h , k \mathbf d\in\mathcal{R}_{h,k} d ∈ R h , k for which d ⋅ A ⃗ = 0 \mathbf d\cdot\vec A=0 d ⋅ A = 0 . If s = w ( d ) s=w(\mathbf d) s = w ( d ) , then
∣ h A ∣ = M h , k − M h − s , k . (5) |hA|=M_{h,k}-M_{h-s,k}. \tag*{(5)} ∣ h A ∣ = M h , k − M h − s , k . (5)
Proof. For k ≥ 4 k\geq4 k ≥ 4 , the lemma follows from O’Bryant’s Theorem 1 [15 ] , because the hypothesis says that the lattice of all v ∈ Z k \mathbf v\in\mathbb Z^k v ∈ Z k with v 1 + ⋯ + v k = 0 v_1+\cdots+v_k=0 v 1 + ⋯ + v k = 0 and v ⋅ A ⃗ = 0 \mathbf v\cdot\vec A=0 v ⋅ A = 0 has first L 1 L^1 L 1 -minimum 2 s 2s 2 s and second L 1 L^1 L 1 -minimum greater than 2 h 2h 2 h .
Now let k = 3 k=3 k = 3 , and write
a 2 − a 1 a 3 − a 1 = b c , gcd ( b , c ) = 1 , 0 < b < c . \frac{a_2-a_1}{a_3-a_1}=\frac{b}{c},\qquad\gcd(b,c)=1,\qquad0<b<c. a 3 − a 1 a 2 − a 1 = c b , g cd( b , c ) = 1 , 0 < b < c .
Let v ∈ Z 3 \mathbf v\in\mathbb Z^3 v ∈ Z 3 satisfy v 1 + v 2 + v 3 = 0 v_1+v_2+v_3=0 v 1 + v 2 + v 3 = 0 and v ⋅ A ⃗ = 0 \mathbf v\cdot\vec A=0 v ⋅ A = 0 . Then
0 = v ⋅ A ⃗ = ( − v 2 − v 3 ) a 1 + v 2 a 2 + v 3 a 3 = v 2 ( a 2 − a 1 ) + v 3 ( a 3 − a 1 ) 0=\mathbf v\cdot\vec A=(-v_2-v_3)a_1+v_2a_2+v_3a_3=v_2(a_2-a_1)+v_3(a_3-a_1) 0 = v ⋅ A = ( − v 2 − v 3 ) a 1 + v 2 a 2 + v 3 a 3 = v 2 ( a 2 − a 1 ) + v 3 ( a 3 − a 1 )
⟹ v 2 b ( a 3 − a 1 ) = v 2 c ( a 2 − a 1 ) = − v 3 c ( a 3 − a 1 ) (because c ( a 2 − a 1 ) = b ( a 3 − a 1 ) ) \Longrightarrow v_2b(a_3-a_1)=v_2c(a_2-a_1)=-v_3c(a_3-a_1)\qquad\text{(because }c(a_2-a_1)=b(a_3-a_1)\text{)} ⟹ v 2 b ( a 3 − a 1 ) = v 2 c ( a 2 − a 1 ) = − v 3 c ( a 3 − a 1 ) (because c ( a 2 − a 1 ) = b ( a 3 − a 1 ) )
⟹ v 2 b = − v 3 c (because a 3 > a 1 ) \Longrightarrow v_2b=-v_3c\qquad\text{(because }a_3>a_1\text{)} ⟹ v 2 b = − v 3 c (because a 3 > a 1 )
⟹ c ∣ v 2 (because gcd ( b , c ) = 1 ) \Longrightarrow c\mid v_2\qquad\text{(because }\gcd(b,c)=1\text{)} ⟹ c ∣ v 2 (because g cd( b , c ) = 1 )
⟹ v 2 = − m c , v 3 = m b , v 1 = − v 2 − v 3 = m ( c − b ) ( m ∈ Z ) \Longrightarrow v_2=-mc,\qquad v_3=mb,\qquad v_1=-v_2-v_3=m(c-b)\qquad(m\in\mathbb Z) ⟹ v 2 = − m c , v 3 = mb , v 1 = − v 2 − v 3 = m ( c − b ) ( m ∈ Z )
⟹ v = m p , p = ( c − b , − c , b ) . \Longrightarrow\mathbf v=m\mathbf p,\qquad\mathbf p=(c-b,-c,b). ⟹ v = m p , p = ( c − b , − c , b ) .
Since d \mathbf d d satisfies the same two conditions, d = m p \mathbf d=m\mathbf p d = m p for some m ∈ Z m\in\mathbb Z m ∈ Z , and
1 = gcd ( ∣ d 1 ∣ , ∣ d 2 ∣ , ∣ d 3 ∣ ) = ∣ m ∣ gcd ( c − b , c , b ) = ∣ m ∣ gcd ( b , c ) = ∣ m ∣ 1=\gcd(|d_1|,|d_2|,|d_3|)=|m|\gcd(c-b,c,b)=|m|\gcd(b,c)=|m| 1 = g cd( ∣ d 1 ∣ , ∣ d 2 ∣ , ∣ d 3 ∣ ) = ∣ m ∣ g cd( c − b , c , b ) = ∣ m ∣ g cd( b , c ) = ∣ m ∣
⟹ d 1 = m ( c − b ) ≠ 0 ⟹ j ( d ) = 1 \Longrightarrow d_1=m(c-b)\ne0\qquad\Longrightarrow\qquad j(\mathbf d)=1 ⟹ d 1 = m ( c − b ) = 0 ⟹ j ( d ) = 1
⟹ m ( c − b ) = d j ( d ) > 0 ⟹ m = 1. \Longrightarrow m(c-b)=d_{j(\mathbf d)}>0\qquad\Longrightarrow\qquad m=1. ⟹ m ( c − b ) = d j ( d ) > 0 ⟹ m = 1.
Hence d = p \mathbf d=\mathbf p d = p , and
v ∈ Z 3 , v 1 + v 2 + v 3 = 0 , v ⋅ A ⃗ = 0 ⟹ v ∈ Z d . (6) \mathbf v\in\mathbb Z^3,\qquad v_1+v_2+v_3=0,\qquad\mathbf v\cdot\vec A=0\qquad\Longrightarrow\qquad\mathbf v\in\mathbb Z\mathbf d. \tag*{(6)} v ∈ Z 3 , v 1 + v 2 + v 3 = 0 , v ⋅ A = 0 ⟹ v ∈ Z d . (6)
For x , y ∈ X h , 3 \mathbf x,\mathbf y\in\mathcal X_{h,3} x , y ∈ X h , 3 , by (6) we get
x ⋅ A ⃗ = y ⋅ A ⃗ ⟺ ( x − y ) ⋅ A ⃗ = 0 ⟺ x − y ∈ Z d \mathbf x\cdot\vec A=\mathbf y\cdot\vec A\qquad\Longleftrightarrow\qquad(\mathbf x-\mathbf y)\cdot\vec A=0\qquad\Longleftrightarrow\qquad\mathbf x-\mathbf y\in\mathbb Z\mathbf d x ⋅ A = y ⋅ A ⟺ ( x − y ) ⋅ A = 0 ⟺ x − y ∈ Z d
because the entries of x − y \mathbf x-\mathbf y x − y sum to h − h = 0 h-h=0 h − h = 0 and d ⋅ A ⃗ = 0. \mathbf d\cdot\vec A=0. d ⋅ A = 0. Since h A = { x ⋅ A ⃗ : x ∈ X h , 3 } hA=\{\mathbf x\cdot\vec A:\mathbf x\in\mathcal X_{h,3}\} h A = { x ⋅ A : x ∈ X h , 3 } , ∣ h A ∣ |hA| ∣ h A ∣ is the number of classes of this equivalence relation. The class of y \mathbf y y is { y + t d : t ∈ T y } \{\mathbf y+t\mathbf d:t\in T_{\mathbf y}\} { y + t d : t ∈ T y } , where, because d 1 + d 2 + d 3 = 0 d_1+d_2+d_3=0 d 1 + d 2 + d 3 = 0 ,
T y = { t ∈ Z : y + t d ∈ X h , 3 } = ⋂ i = 1 3 { t ∈ Z : y i + t d i ≥ 0 } = [ max d i > 0 ⌈ − y i d i ⌉ . . min d i < 0 ⌊ y i ∣ d i ∣ ⌋ ] . T_{\mathbf y}=\{t\in\mathbb Z:\mathbf y+t\mathbf d\in\mathcal X_{h,3}\}
=\bigcap_{i=1}^{3}\{t\in\mathbb Z:y_i+td_i\geq0\}
=\left[\max_{d_i>0}\left\lceil-\frac{y_i}{d_i}\right\rceil\mathbin{. .}\min_{d_i<0}\left\lfloor\frac{y_i}{|d_i|}\right\rfloor\right]. T y = { t ∈ Z : y + t d ∈ X h , 3 } = i = 1 ⋂ 3 { t ∈ Z : y i + t d i ≥ 0 } = [ d i > 0 max ⌈ − d i y i ⌉ .. d i < 0 min ⌊ ∣ d i ∣ y i ⌋ ] .
Both index sets are nonempty because d ≠ 0 \mathbf d\ne0 d = 0 and d 1 + d 2 + d 3 = 0 d_1+d_2+d_3=0 d 1 + d 2 + d 3 = 0 . Thus each class C C C equals { c , c + d , … , c + α C d } \{\mathbf c,\mathbf c+\mathbf d,\ldots,\mathbf c+\alpha_C\mathbf d\} { c , c + d , … , c + α C d } , so ∣ C ∣ = α C + 1 |C|=\alpha_C+1 ∣ C ∣ = α C + 1 and C C C contains exactly α C \alpha_C α C pairs ( x , y ) (\mathbf x,\mathbf y) ( x , y ) with x − y = d \mathbf x-\mathbf y=\mathbf d x − y = d . Every such pair lies in a single class, so with
N = # { ( x , y ) ∈ X h , 3 × X h , 3 : x − y = d } N=\#\{(\mathbf x,\mathbf y)\in\mathcal X_{h,3}\times\mathcal X_{h,3}:\mathbf x-\mathbf y=\mathbf d\} N = # {( x , y ) ∈ X h , 3 × X h , 3 : x − y = d }
we get
∣ h A ∣ = ∑ C 1 = ∑ C ( α C + 1 − α C ) = ∑ C ∣ C ∣ − ∑ C α C = ∣ X h , 3 ∣ − N = M h , 3 − N . \begin{aligned}
|hA|=\sum_C1=\sum_C(\alpha_C+1-\alpha_C) \\
&=\sum_C|C|-\sum_C\alpha_C=|\mathcal X_{h,3}|-N=M_{h,3}-N.
\end{aligned} ∣ h A ∣ = C ∑ 1 = C ∑ ( α C + 1 − α C ) = C ∑ ∣ C ∣ − C ∑ α C = ∣ X h , 3 ∣ − N = M h , 3 − N .
Since d ∈ R h , 3 \mathbf d\in\mathcal R_{h,3} d ∈ R h , 3 , we have s ≤ h s\leq h s ≤ h . As in the proof of Lemma 3.2 , the map
ϕ ( t ) = ( d + + t , d − + t ) (7) \phi(\mathbf t)=(\mathbf d^{+}+\mathbf t,\mathbf d^{-}+\mathbf t) \tag*{(7)} ϕ ( t ) = ( d + + t , d − + t ) (7)
sends X h − s , 3 \mathcal{X}_{h-s,3} X h − s , 3 into the set of pairs counted by N N N . Conversely, for a pair ( x , y ) (\mathbf{x},\mathbf{y}) ( x , y ) counted by N N N , let t = ψ ( x , y ) = x − d + \mathbf{t}=\psi(\mathbf{x},\mathbf{y})=\mathbf{x}-\mathbf{d}^{+} t = ψ ( x , y ) = x − d + . Then
x − y = d = d + − d − ⟹ t = x − d + = y − d − , \mathbf{x}-\mathbf{y}=\mathbf{d}=\mathbf{d}^{+}-\mathbf{d}^{-}\Longrightarrow\mathbf{t}=\mathbf{x}-\mathbf{d}^{+}=\mathbf{y}-\mathbf{d}^{-}, x − y = d = d + − d − ⟹ t = x − d + = y − d − ,
d i ≤ 0 ⟹ d i + = 0 ⟹ t i = x i ≥ 0 , d_i\leq0\Longrightarrow d_i^{+}=0\Longrightarrow t_i=x_i\geq0, d i ≤ 0 ⟹ d i + = 0 ⟹ t i = x i ≥ 0 ,
d i > 0 ⟹ d i − = 0 ⟹ t i = y i ≥ 0 , d_i>0\Longrightarrow d_i^{-}=0\Longrightarrow t_i=y_i\geq0, d i > 0 ⟹ d i − = 0 ⟹ t i = y i ≥ 0 ,
∑ i = 1 3 t i = ∑ i = 1 3 x i − ∑ i = 1 3 d i + = h − w ( d ) = h − s , \sum_{i=1}^{3}t_i=\sum_{i=1}^{3}x_i-\sum_{i=1}^{3}d_i^{+}=h-w(\mathbf{d})=h-s, i = 1 ∑ 3 t i = i = 1 ∑ 3 x i − i = 1 ∑ 3 d i + = h − w ( d ) = h − s ,
so t ∈ X h − s , 3 \mathbf{t}\in\mathcal{X}_{h-s,3} t ∈ X h − s , 3 . Moreover,
ψ ( ϕ ( t ) ) = ( d + + t ) − d + = t , \psi(\phi(\mathbf{t}))=(\mathbf{d}^{+}+\mathbf{t})-\mathbf{d}^{+}=\mathbf{t}, ψ ( ϕ ( t )) = ( d + + t ) − d + = t ,
ϕ ( ψ ( x , y ) ) = ( x , x − d + + d − ) = ( x , x − d ) = ( x , y ) . \phi(\psi(\mathbf{x},\mathbf{y}))=(\mathbf{x},\mathbf{x}-\mathbf{d}^{+}+\mathbf{d}^{-})=(\mathbf{x},\mathbf{x}-\mathbf{d})=(\mathbf{x},\mathbf{y}). ϕ ( ψ ( x , y )) = ( x , x − d + + d − ) = ( x , x − d ) = ( x , y ) .
Hence ϕ \phi ϕ is a bijection, and
N = ∣ X h − s , 3 ∣ = M h − s , 3 , ∣ h A ∣ = M h , 3 − M h − s , 3 . N=|\mathcal{X}_{h-s,3}|=M_{h-s,3},\qquad|hA|=M_{h,3}-M_{h-s,3}. N = ∣ X h − s , 3 ∣ = M h − s , 3 , ∣ h A ∣ = M h , 3 − M h − s , 3 .
Example 3.7. By Example 3.3 , for every h ≥ 2 h\geq2 h ≥ 2 the vector ( 1 , − 2 , 1 ) (1,-2,1) ( 1 , − 2 , 1 ) , of weight 2 2 2 , is the only vector in R h , 3 \mathcal{R}_{h,3} R h , 3 orthogonal to E \mathbf{E} E . By Lemma 3.6, we get
∣ h E ∣ = M h , 3 − M h − 2 , 3 = ( h + 2 2 ) − ( h 2 ) = 2 h + 1 , |hE|=M_{h,3}-M_{h-2,3}=\binom{h+2}{2}-\binom{h}{2}=2h+1, ∣ h E ∣ = M h , 3 − M h − 2 , 3 = ( 2 h + 2 ) − ( 2 h ) = 2 h + 1 ,
in agreement with h E = [ h . .3 h ] hE=[h..3h] h E = [ h ..3 h ] . For h = 4 h=4 h = 4 , this recovers ∣ 4 E ∣ = 9 |4E|=9 ∣4 E ∣ = 9 .
Main Theorem
Theorem 1.1. Let k ≥ 3 k\geq3 k ≥ 3 be fixed, and let q → ∞ q\to\infty q → ∞ and h = h ( q ) ≥ 2 h=h(q)\geq2 h = h ( q ) ≥ 2 with h = o ( q 1 / k ) h=o(q^{1/k}) h = o ( q 1/ k ) . For 0 ≤ ℓ < h 0\leq\ell<h 0 ≤ ℓ < h , let
P ℓ = M h , k − M ℓ − 1 , k . P_\ell=M_{h,k}-M_{\ell-1,k}. P ℓ = M h , k − M ℓ − 1 , k . Then the following statements hold.
# { A ∈ ( [ q ] k ) : ∣ h A ∣ = M h , k } = Θ ( q k ) \#\left\{A\in\binom{[q]}{k}:|hA|=M_{h,k}\right\}=\Theta(q^k) # { A ∈ ( k [ q ] ) : ∣ h A ∣ = M h , k } = Θ ( q k ) .
# { A ∈ ( [ q ] k ) : ∣ h A ∣ ∉ { P 0 , … , P h − 1 } } = O ( h 2 k − 2 q k − 2 ) \#\left\{A\in\binom{[q]}{k}:|hA|\notin\{P_0,\ldots,P_{h-1}\}\right\}=O\left(h^{2k-2}q^{k-2}\right) # { A ∈ ( k [ q ] ) : ∣ h A ∣ ∈ / { P 0 , … , P h − 1 } } = O ( h 2 k − 2 q k − 2 ) .
# { A ∈ ( [ q ] k ) : ∣ h A ∣ = P ℓ } = Ω ( q k − 1 h − ℓ + 1 ) \#\left\{A\in\binom{[q]}{k}:|hA|=P_\ell\right\}=\Omega\left(\frac{q^{k-1}}{h-\ell+1}\right) # { A ∈ ( k [ q ] ) : ∣ h A ∣ = P ℓ } = Ω ( h − ℓ + 1 q k − 1 ) .
Proof of Theorem 1.1. For d ∈ R h , k \mathbf{d}\in\mathcal{R}_{h,k} d ∈ R h , k , let
E d = { A ∈ ( [ q ] k ) : d ⋅ A = 0 } . E_{\mathbf{d}}=\left\{A\in\binom{[q]}{k}:\mathbf{d}\cdot\mathbf{A}=0\right\}. E d = { A ∈ ( k [ q ] ) : d ⋅ A = 0 } .
By Lemma 3.2 ,
∣ h A ∣ < M h , k ⟺ A ∈ ⋃ d ∈ R h , k E d . |hA|<M_{h,k}\Longleftrightarrow A\in\bigcup_{\mathbf{d}\in\mathcal{R}_{h,k}}E_{\mathbf{d}}. ∣ h A ∣ < M h , k ⟺ A ∈ d ∈ R h , k ⋃ E d .
Using Lemma 3.4 and Proposition 3.5, we obtain
# { A ∈ ( [ q ] k ) : ∣ h A ∣ < M h , k } = # ⋃ d ∈ R h , k E d ≤ ∑ d ∈ R h , k ∣ E d ∣ ≤ ∣ R h , k ∣ q k − 1 ≤ ( 2 h + 1 ) k − 1 q k − 1 = O ( h k − 1 q k − 1 ) . (8) \#\left\{A\in\binom{[q]}{k}: |hA|<M_{h,k}\right\}
=\#\bigcup_{d\in\mathcal{R}_{h,k}}E_d
\le\sum_{d\in\mathcal{R}_{h,k}}|E_d|
\le|\mathcal{R}_{h,k}|q^{k-1}
\le(2h+1)^{k-1}q^{k-1}
=O(h^{k-1}q^{k-1}). \tag*{(8)} # { A ∈ ( k [ q ] ) : ∣ h A ∣ < M h , k } = # d ∈ R h , k ⋃ E d ≤ d ∈ R h , k ∑ ∣ E d ∣ ≤ ∣ R h , k ∣ q k − 1 ≤ ( 2 h + 1 ) k − 1 q k − 1 = O ( h k − 1 q k − 1 ) . (8)
Consequently,
# { A ∈ ( [ q ] k ) : ∣ h A ∣ = M h , k } = ( q k ) − # { A ∈ ( [ q ] k ) : ∣ h A ∣ < M h , k } = ( q k ) + O ( h k − 1 q k − 1 ) = q k k ! + O ( h k − 1 q k − 1 ) = Θ ( q k ) , \#\left\{A\in\binom{[q]}{k}: |hA|=M_{h,k}\right\}
=\binom{q}{k}-\#\left\{A\in\binom{[q]}{k}: |hA|<M_{h,k}\right\}
=\binom{q}{k}+O(h^{k-1}q^{k-1})
=\frac{q^k}{k!}+O(h^{k-1}q^{k-1})
=\Theta(q^k), # { A ∈ ( k [ q ] ) : ∣ h A ∣ = M h , k } = ( k q ) − # { A ∈ ( k [ q ] ) : ∣ h A ∣ < M h , k } = ( k q ) + O ( h k − 1 q k − 1 ) = k ! q k + O ( h k − 1 q k − 1 ) = Θ ( q k ) ,
which proves (1). The last step uses h k − 1 ≤ h k = o ( q ) h^{k-1}\le h^k=o(q) h k − 1 ≤ h k = o ( q ) , which holds because h = o ( q 1 / k ) h=o(q^{1/k}) h = o ( q 1/ k ) . For (2), let
η ( A ) = # { d ∈ R h , k : d ⋅ A ⃗ = 0 } , \eta(A)=\#\{\mathbf{d}\in\mathcal{R}_{h,k}:\mathbf{d}\cdot\vec{A}=0\}, η ( A ) = # { d ∈ R h , k : d ⋅ A = 0 } ,
the number of coefficient vectors in R h , k \mathcal{R}_{h,k} R h , k orthogonal to A ⃗ \vec{A} A . Lemma 3.2 gives
η ( A ) = 0 ⟹ ∣ h A ∣ = M h , k = M h , k − M − 1 , k = P 0 . \eta(A)=0\quad\Longrightarrow\quad|hA|=M_{h,k}=M_{h,k}-M_{-1,k}=P_0. η ( A ) = 0 ⟹ ∣ h A ∣ = M h , k = M h , k − M − 1 , k = P 0 .
If η ( A ) = 1 \eta(A)=1 η ( A ) = 1 , let d \mathbf{d} d be the unique vector and let s = w ( d ) s=w(\mathbf{d}) s = w ( d ) . Weight 1 would give entries 1 and − 1 -1 − 1 in distinct coordinates i , j i,j i , j , and hence
0 = d ⋅ A ⃗ = a i − a j ≠ 0. 0=\mathbf{d}\cdot\vec{A}=a_i-a_j\ne0. 0 = d ⋅ A = a i − a j = 0.
Thus 2 ≤ s ≤ h 2\le s\le h 2 ≤ s ≤ h , and Lemma 3.6 gives
∣ h A ∣ = M h , k − M h − s , k = P h − s + 1 , 1 ≤ h − s + 1 ≤ h − 1. |hA|=M_{h,k}-M_{h-s,k}=P_{h-s+1},\qquad1\le h-s+1\le h-1. ∣ h A ∣ = M h , k − M h − s , k = P h − s + 1 , 1 ≤ h − s + 1 ≤ h − 1.
It follows that
∣ h A ∣ ∉ { P 0 , … , P h − 1 } ⟹ η ( A ) ≥ 2. |hA|\notin\{P_0,\ldots,P_{h-1}\}\quad\Longrightarrow\quad\eta(A)\ge2. ∣ h A ∣ ∈ / { P 0 , … , P h − 1 } ⟹ η ( A ) ≥ 2.
For distinct d , e ∈ R h , k \mathbf{d},\mathbf{e}\in\mathcal{R}_{h,k} d , e ∈ R h , k , Proposition 3.5 and Lemma 3.4 give
∣ E d ∩ E e ∣ ≤ # { v ∈ [ q ] k : d ⋅ v = e ⋅ v = 0 } ≤ q k − 2 . |E_{\mathbf{d}}\cap E_{\mathbf{e}}|
\le\#\{\mathbf{v}\in[q]^k:\mathbf{d}\cdot\mathbf{v}=\mathbf{e}\cdot\mathbf{v}=0\}
\le q^{k-2}. ∣ E d ∩ E e ∣ ≤ # { v ∈ [ q ] k : d ⋅ v = e ⋅ v = 0 } ≤ q k − 2 .
Therefore
# { A ∈ ( [ q ] k ) : ∣ h A ∣ ∉ { P 0 , … , P h − 1 } } ≤ ∑ d , e ∈ R h , k d ≠ e ∣ E d ∩ E e ∣ ≤ ∣ R h , k ∣ 2 q k − 2 ≤ ( 2 h + 1 ) 2 k − 2 q k − 2 = O ( h 2 k − 2 q k − 2 ) , \#\left\{A\in\binom{[q]}{k}:|hA|\notin\{P_0,\ldots,P_{h-1}\}\right\}
\le\sum_{\substack{\mathbf{d},\mathbf{e}\in\mathcal{R}_{h,k}\\\mathbf{d}\ne\mathbf{e}}}|E_{\mathbf{d}}\cap E_{\mathbf{e}}|
\le|\mathcal{R}_{h,k}|^2q^{k-2}
\le(2h+1)^{2k-2}q^{k-2}
=O(h^{2k-2}q^{k-2}), # { A ∈ ( k [ q ] ) : ∣ h A ∣ ∈ / { P 0 , … , P h − 1 } } ≤ d , e ∈ R h , k d = e ∑ ∣ E d ∩ E e ∣ ≤ ∣ R h , k ∣ 2 q k − 2 ≤ ( 2 h + 1 ) 2 k − 2 q k − 2 = O ( h 2 k − 2 q k − 2 ) ,
proving (2).
For (3), fix 1 ≤ ℓ < h 1\le\ell<h 1 ≤ ℓ < h and set s = h − ℓ + 1 s=h-\ell+1 s = h − ℓ + 1 , so 2 ≤ s ≤ h 2\le s\le h 2 ≤ s ≤ h . Choose
1 ≤ a ≤ ⌊ q 2 ⌋ , 1 ≤ r ≤ ⌊ q 2 s ⌋ , ( a 1 , a 2 , a 3 ) = ( a , a + r , a + s r ) . 1\le a\le\left\lfloor\frac{q}{2}\right\rfloor,\qquad
1\le r\le\left\lfloor\frac{q}{2s}\right\rfloor,\qquad
(a_1,a_2,a_3)=(a,a+r,a+sr). 1 ≤ a ≤ ⌊ 2 q ⌋ , 1 ≤ r ≤ ⌊ 2 s q ⌋ , ( a 1 , a 2 , a 3 ) = ( a , a + r , a + sr ) .
Then
1 ≤ a 1 < a 2 < a 3 ≤ ⌊ q 2 ⌋ + s ⌊ q 2 s ⌋ ≤ q . 1\le a_1<a_2<a_3\le\left\lfloor\frac{q}{2}\right\rfloor+s\left\lfloor\frac{q}{2s}\right\rfloor\le q. 1 ≤ a 1 < a 2 < a 3 ≤ ⌊ 2 q ⌋ + s ⌊ 2 s q ⌋ ≤ q .
Let d 0 = ( s − 1 , − s , 1 , 0 , … , 0 ) \mathbf{d}_0=(s-1,-s,1,0,\ldots,0) d 0 = ( s − 1 , − s , 1 , 0 , … , 0 ) . We have
∑ i = 1 k ( d 0 ) i = ( s − 1 ) − s + 1 = 0 , \sum_{i=1}^{k}(\mathbf{d}_0)_i=(s-1)-s+1=0, i = 1 ∑ k ( d 0 ) i = ( s − 1 ) − s + 1 = 0 ,
gcd ( ∣ ( d 0 ) 1 ∣ , … , ∣ ( d 0 ) k ∣ ) = gcd ( s − 1 , s , 1 ) = 1 , \gcd\left(\lvert(\mathbf{d}_0)_1\rvert,\ldots,\lvert(\mathbf{d}_0)_k\rvert\right)=\gcd(s-1,s,1)=1, g cd( ∣( d 0 ) 1 ∣ , … , ∣( d 0 ) k ∣ ) = g cd( s − 1 , s , 1 ) = 1 ,
w ( d 0 ) = ( s − 1 ) + 1 = s ≤ h , w(\mathbf{d}_0)=(s-1)+1=s\le h, w ( d 0 ) = ( s − 1 ) + 1 = s ≤ h ,
( d 0 ) j ( d 0 ) = s − 1 > 0. (\mathbf{d}_0)_j(\mathbf{d}_0)=s-1>0. ( d 0 ) j ( d 0 ) = s − 1 > 0.
Thus d 0 ∈ R h , k \mathbf{d}_0\in\mathcal{R}_{h,k} d 0 ∈ R h , k . For every extension to a labeled tuple a = ( a 1 , … , a k ) \mathbf{a}=(a_1,\ldots,a_k) a = ( a 1 , … , a k ) ,
d 0 ⋅ a = ( s − 1 ) a 1 − s a 2 + a 3 = ( s − 1 ) a − s ( a + r ) + ( a + s r ) = ( ( s − 1 ) − s + 1 ) a + ( − s + s ) r = 0. \begin{aligned}
\mathbf{d}_0\cdot\mathbf{a}&=(s-1)a_1-sa_2+a_3\\
&=(s-1)a-s(a+r)+(a+sr)\\
&=((s-1)-s+1)a+(-s+s)r=0.
\end{aligned} d 0 ⋅ a = ( s − 1 ) a 1 − s a 2 + a 3 = ( s − 1 ) a − s ( a + r ) + ( a + sr ) = (( s − 1 ) − s + 1 ) a + ( − s + s ) r = 0.
Suppose that e = ( e 1 , e 2 , e 3 , 0 , … , 0 ) ∈ R h , k \mathbf{e}=(e_1,e_2,e_3,0,\ldots,0)\in\mathcal{R}_{h,k} e = ( e 1 , e 2 , e 3 , 0 , … , 0 ) ∈ R h , k and e ⋅ a = 0 \mathbf{e}\cdot\mathbf{a}=0 e ⋅ a = 0 . Then
0 = e 1 a + e 2 ( a + r ) + e 3 ( a + s r ) = a ( e 1 + e 2 + e 3 ) + r ( e 2 + s e 3 ) = r ( e 2 + s e 3 ) . \begin{aligned}
0&=e_1a+e_2(a+r)+e_3(a+sr)\\
&=a(e_1+e_2+e_3)+r(e_2+se_3)\\
&=r(e_2+se_3).
\end{aligned} 0 = e 1 a + e 2 ( a + r ) + e 3 ( a + sr ) = a ( e 1 + e 2 + e 3 ) + r ( e 2 + s e 3 ) = r ( e 2 + s e 3 ) .
Since r > 0 r>0 r > 0 and e 1 + e 2 + e 3 = 0 e_1+e_2+e_3=0 e 1 + e 2 + e 3 = 0 ,
e 2 = − s e 3 , e 1 = ( s − 1 ) e 3 , e = e 3 d 0 . e_2=-se_3,\qquad e_1=(s-1)e_3,\qquad\mathbf{e}=e_3\mathbf{d}_0. e 2 = − s e 3 , e 1 = ( s − 1 ) e 3 , e = e 3 d 0 .
Primitivity and the sign convention give
1 = gcd ( ∣ e 1 ∣ , … , ∣ e k ∣ ) = ∣ e 3 ∣ , 0 < e 1 = ( s − 1 ) e 3 ⟹ e 3 = 1 , 1=\gcd(\lvert e_1\rvert,\ldots,\lvert e_k\rvert)=\lvert e_3\rvert,\qquad0<e_1=(s-1)e_3\implies e_3=1, 1 = g cd(∣ e 1 ∣ , … , ∣ e k ∣) = ∣ e 3 ∣ , 0 < e 1 = ( s − 1 ) e 3 ⟹ e 3 = 1 ,
so e = d 0 \mathbf{e}=\mathbf{d}_0 e = d 0 .
Suppose that a 1 , … , a j − 1 a_1,\ldots,a_{j-1} a 1 , … , a j − 1 are distinct and that d 0 \mathbf{d}_0 d 0 is the unique vector supported on the first j − 1 j-1 j − 1 coordinates with zero dot product. For e ∈ R h , k \mathbf{e}\in\mathcal{R}_{h,k} e ∈ R h , k supported on the first j j j coordinates and satisfying e j ≠ 0 e_j\ne0 e j = 0 ,
∑ i = 1 j e i a i = 0 ⟺ a j = − 1 e j ∑ i = 1 j − 1 e i a i . \sum_{i=1}^{j}e_i a_i=0\iff a_j=-\frac{1}{e_j}\sum_{i=1}^{j-1}e_i a_i. i = 1 ∑ j e i a i = 0 ⟺ a j = − e j 1 i = 1 ∑ j − 1 e i a i .
Each such vector excludes at most one value of a j a_j a j , because e j ≠ 0 e_j\ne0 e j = 0 and the equivalence above determines a j a_j a j from a 1 , … , a j − 1 a_1,\ldots,a_{j-1} a 1 , … , a j − 1 . Since every e i e_i e i lies in [ − h , h ] [-h,h] [ − h , h ] , at most ( 2 h + 1 ) j (2h+1)^j ( 2 h + 1 ) j values are excluded by these vectors. If F j F_j F j is the union of these values and a 1 , … , a j − 1 a_1,\ldots,a_{j-1} a 1 , … , a j − 1 , then
# { a j ∈ [ q ] : a j ∉ F j } = q − ∣ F j ∩ [ q ] ∣ ≥ q − ( 2 h + 1 ) j − ( j − 1 ) ≥ q 2 \begin{aligned}
\#\{a_j\in[q]:a_j\notin F_j\}=q-\lvert F_j\cap[q]\rvert\\
&\ge q-(2h+1)^j-(j-1) \\
&\ge\frac{q}{2}
\end{aligned} # { a j ∈ [ q ] : a j ∈ / F j } = q − ∣ F j ∩ [ q ]∣ ≥ q − ( 2 h + 1 ) j − ( j − 1 ) ≥ 2 q
for all sufficiently large q q q , because ( 2 h + 1 ) j + j ≤ ( 3 h ) k + k (2h+1)^j+j\le(3h)^k+k ( 2 h + 1 ) j + j ≤ ( 3 h ) k + k and h k = o ( q ) h^k=o(q) h k = o ( q ) . Vectors with e j = 0 e_j=0 e j = 0 are covered by the inductive assumption, and vectors with e j ≠ 0 e_j\ne0 e j = 0 are excluded by the choice of a j a_j a j . Repeating for j = 4 , … , k j=4,\ldots,k j = 4 , … , k therefore gives
{ e ∈ R h , k : e ⋅ a = 0 } = { d 0 } . \{\mathbf{e}\in\mathcal{R}_{h,k}:\mathbf{e}\cdot\mathbf{a}=0\}=\{\mathbf{d}_0\}. { e ∈ R h , k : e ⋅ a = 0 } = { d 0 } .
The number of labeled tuples produced is at least
⌊ q 2 ⌋ ⌊ q 2 s ⌋ ∏ j = 4 k q 2 = ⌊ q 2 ⌋ ⌊ q 2 s ⌋ ( q 2 ) k − 3 = Ω ( q k − 1 s ) . \begin{aligned}
\left\lfloor\frac{q}{2}\right\rfloor\left\lfloor\frac{q}{2s}\right\rfloor\prod_{j=4}^{k}\frac{q}{2}
=
\left\lfloor\frac{q}{2}\right\rfloor\left\lfloor\frac{q}{2s}\right\rfloor\left(\frac{q}{2}\right)^{k-3} \\
&=\Omega\left(\frac{q^{k-1}}{s}\right).
\end{aligned} ⌊ 2 q ⌋ ⌊ 2 s q ⌋ j = 4 ∏ k 2 q = ⌊ 2 q ⌋ ⌊ 2 s q ⌋ ( 2 q ) k − 3 = Ω ( s q k − 1 ) .
Here we used ⌊ x ⌋ ≥ x / 2 \lfloor x\rfloor\ge x/2 ⌊ x ⌋ ≥ x /2 for x ≥ 1 x\ge1 x ≥ 1 , which applies to x = q / ( 2 s ) x=q/(2s) x = q / ( 2 s ) because s ≤ h = o ( q ) s\le h=o(q) s ≤ h = o ( q ) .
Let A A A be the set of entries of a \mathbf{a} a , and let P P P be the permutation matrix with A ⃗ = P a \vec{A}=P\mathbf{a} A = P a . Choose the prescribed sign ε \varepsilon ε and let d ′ = ε P d 0 \mathbf{d}'=\varepsilon P\mathbf{d}_0 d ′ = εP d 0 . Then
d ′ ⋅ A ⃗ = ( ε P d 0 ) ⋅ ( P a ) = ε d 0 ⋅ a = 0 , w ( d ′ ) = w ( d 0 ) = s , d ′ ∈ R h , k . \mathbf{d}'\cdot\vec{A}=(\varepsilon P\mathbf{d}_0)\cdot(P\mathbf{a})=\varepsilon\mathbf{d}_0\cdot\mathbf{a}=0,
\qquad
w(\mathbf{d}')=w(\mathbf{d}_0)=s,
\qquad
\mathbf{d}'\in\mathcal{R}_{h,k}. d ′ ⋅ A = ( εP d 0 ) ⋅ ( P a ) = ε d 0 ⋅ a = 0 , w ( d ′ ) = w ( d 0 ) = s , d ′ ∈ R h , k .
For any e ∈ R h , k \mathbf{e}\in\mathcal{R}_{h,k} e ∈ R h , k with e ⋅ A ⃗ = 0 \mathbf{e}\cdot\vec{A}=0 e ⋅ A = 0 , choose δ ∈ { 1 , − 1 } \delta\in\{1,-1\} δ ∈ { 1 , − 1 } so that δ P − 1 e ∈ R h , k \delta P^{-1}\mathbf{e}\in\mathcal{R}_{h,k} δ P − 1 e ∈ R h , k . Then
( δ P − 1 e ) ⋅ a = δ e ⋅ A ⃗ = 0 ⟹ δ P − 1 e = d 0 ⟹ e = δ P d 0 . (\delta P^{-1}\mathbf{e})\cdot\mathbf{a}=\delta\mathbf{e}\cdot\vec{A}=0
\quad\Longrightarrow\quad
\delta P^{-1}\mathbf{e}=\mathbf{d}_0
\quad\Longrightarrow\quad
\mathbf{e}=\delta P\mathbf{d}_0. ( δ P − 1 e ) ⋅ a = δ e ⋅ A = 0 ⟹ δ P − 1 e = d 0 ⟹ e = δ P d 0 .
The sign convention forces e = d ′ \mathbf{e}=\mathbf{d}' e = d ′ . Hence Lemma Lemma 3.6 gives
∣ h A ∣ = M h , k − M h − s , k = M h , k − M ℓ − 1 , k = P ℓ . \begin{aligned}
|hA|&=M_{h,k}-M_{h-s,k}\\
&=M_{h,k}-M_{\ell-1,k}\\
&=P_{\ell}.
\end{aligned} ∣ h A ∣ = M h , k − M h − s , k = M h , k − M ℓ − 1 , k = P ℓ .
At most k ! k! k ! labeled tuples produce the same set, so
# { A ∈ ( [ q ] k ) : ∣ h A ∣ = P ℓ } ≥ # { labeled tuples produced } k ! = Ω ( q k − 1 s ) = Ω ( q k − 1 h − ℓ + 1 ) . \#\left\{A\in\binom{[q]}{k}:|hA|=P_{\ell}\right\}
\ge\frac{\#\{\text{labeled tuples produced}\}}{k!}
=\Omega\left(\frac{q^{k-1}}{s}\right)
=\Omega\left(\frac{q^{k-1}}{h-\ell+1}\right). # { A ∈ ( k [ q ] ) : ∣ h A ∣ = P ℓ } ≥ k ! # { labeled tuples produced } = Ω ( s q k − 1 ) = Ω ( h − ℓ + 1 q k − 1 ) .
Finally, P 0 = M h , k P_0=M_{h,k} P 0 = M h , k and (1) give
# { A ∈ ( [ q ] k ) : ∣ h A ∣ = P 0 } = Θ ( q k ) = Ω ( q k − 1 h + 1 ) . \#\left\{A\in\binom{[q]}{k}:|hA|=P_0\right\}
=\Theta(q^k)=\Omega\left(\frac{q^{k-1}}{h+1}\right). # { A ∈ ( k [ q ] ) : ∣ h A ∣ = P 0 } = Θ ( q k ) = Ω ( h + 1 q k − 1 ) .
This proves (3). □
Corollary 4.1. Fix k ≥ 3 k\ge3 k ≥ 3 , and let h = h ( q ) ≥ 2 h=h(q)\ge2 h = h ( q ) ≥ 2 satisfy h = o ( q 1 / ( 2 k − 1 ) ) h=o(q^{1/(2k-1)}) h = o ( q 1/ ( 2 k − 1 ) ) . For all sufficiently large q q q , the h h h most frequent values of ∣ h A ∣ |hA| ∣ h A ∣ , with A ∈ ( [ q ] k ) A\in\binom{[q]}{k} A ∈ ( k [ q ] ) , are precisely
P 0 , P 1 , … , P h − 1 . P_0,P_1,\ldots,P_{h-1}. P 0 , P 1 , … , P h − 1 . Moreover,
P ℓ − P ℓ + 1 = ( ℓ + k − 2 k − 2 ) , 0 ≤ ℓ < h − 1. P_{\ell}-P_{\ell+1}=\binom{\ell+k-2}{k-2},
\qquad0\le\ell<h-1. P ℓ − P ℓ + 1 = ( k − 2 ℓ + k − 2 ) , 0 ≤ ℓ < h − 1. In particular, the gaps are consecutive triangular numbers when k = 4 k=4 k = 4 .
Proof. For an integer v v v , let
f q ( v ) = # { A ∈ ( [ q ] k ) : ∣ h A ∣ = v } . f_q(v)=\#\left\{A\in\binom{[q]}{k}:|hA|=v\right\}. f q ( v ) = # { A ∈ ( k [ q ] ) : ∣ h A ∣ = v } .
Since h = o ( q 1 / ( 2 k − 1 ) ) h=o(q^{1/(2k-1)}) h = o ( q 1/ ( 2 k − 1 ) ) implies h = o ( q 1 / k ) h=o(q^{1/k}) h = o ( q 1/ k ) , Theorem 1.1 applies and gives
f q ( P 0 ) = Θ ( q k ) , f_q(P_0)=\Theta(q^k), f q ( P 0 ) = Θ ( q k ) ,
f q ( P ℓ ) = Ω ( q k − 1 h − ℓ + 1 ) = Ω ( q k − 1 h ) ( 1 ≤ ℓ < h ) , f_q(P_{\ell})=\Omega\left(\frac{q^{k-1}}{h-\ell+1}\right)
=\Omega\left(\frac{q^{k-1}}{h}\right)
\qquad(1\le\ell<h), f q ( P ℓ ) = Ω ( h − ℓ + 1 q k − 1 ) = Ω ( h q k − 1 ) ( 1 ≤ ℓ < h ) ,
∑ v ∉ { P 0 , … , P h − 1 } f q ( v ) = O ( h 2 k − 2 q k − 2 ) . \sum_{v\notin\{P_0,\ldots,P_{h-1}\}}f_q(v)
=O(h^{2k-2}q^{k-2}). v ∈ / { P 0 , … , P h − 1 } ∑ f q ( v ) = O ( h 2 k − 2 q k − 2 ) .
Thus there are constants c , C > 0 c,C>0 c , C > 0 such that, for all sufficiently large q q q ,
0 ≤ max v ∉ { P 0 , … , P h − 1 } f q ( v ) min 0 ≤ ℓ < h f q ( P ℓ ) ≤ ∑ v ∉ { P 0 , … , P h − 1 } f q ( v ) min 0 ≤ ℓ < h f q ( P ℓ ) ≤ C h 2 k − 2 q k − 2 c q k − 1 / h = C c h 2 k − 1 q ⟶ 0 , 0\le
\frac{\max_{v\notin\{P_0,\ldots,P_{h-1}\}}f_q(v)}
{\min_{0\le\ell<h}f_q(P_{\ell})}
\le
\frac{\sum_{v\notin\{P_0,\ldots,P_{h-1}\}}f_q(v)}
{\min_{0\le\ell<h}f_q(P_{\ell})}
\le
\frac{Ch^{2k-2}q^{k-2}}{cq^{k-1}/h}
=
\frac{C}{c}\frac{h^{2k-1}}{q}
\longrightarrow0, 0 ≤ min 0 ≤ ℓ < h f q ( P ℓ ) max v ∈ / { P 0 , … , P h − 1 } f q ( v ) ≤ min 0 ≤ ℓ < h f q ( P ℓ ) ∑ v ∈ / { P 0 , … , P h − 1 } f q ( v ) ≤ c q k − 1 / h C h 2 k − 2 q k − 2 = c C q h 2 k − 1 ⟶ 0 ,
because h 2 k − 1 = o ( q ) h^{2k-1}=o(q) h 2 k − 1 = o ( q ) . Consequently, each listed value occurs more frequently than every unlisted value for all sufficiently large q q q .
For 0 ≤ ℓ < h − 1 0\le\ell<h-1 0 ≤ ℓ < h − 1 , Pascal’s identity gives
P ℓ − P ℓ + 1 = ( M h , k − M ℓ − 1 , k ) − ( M h , k − M ℓ , k ) = M ℓ , k − M ℓ − 1 , k = ( ℓ + k − 1 k − 1 ) − ( ℓ + k − 2 k − 1 ) = ( ℓ + k − 2 k − 2 ) . \begin{aligned}
P_\ell-P_{\ell+1}&=(M_{h,k}-M_{\ell-1,k})-(M_{h,k}-M_{\ell,k})\\
&=M_{\ell,k}-M_{\ell-1,k}\\
&=\binom{\ell+k-1}{k-1}-\binom{\ell+k-2}{k-1}\\
&=\binom{\ell+k-2}{k-2}.
\end{aligned} P ℓ − P ℓ + 1 = ( M h , k − M ℓ − 1 , k ) − ( M h , k − M ℓ , k ) = M ℓ , k − M ℓ − 1 , k = ( k − 1 ℓ + k − 1 ) − ( k − 1 ℓ + k − 2 ) = ( k − 2 ℓ + k − 2 ) .
For ℓ = 0 \ell=0 ℓ = 0 , this uses M − 1 , k = 0 M_{-1,k}=0 M − 1 , k = 0 and M 0 , k = 1 M_{0,k}=1 M 0 , k = 1 . For k = 4 k=4 k = 4 , the gaps are
( ℓ + 2 2 ) = ( ℓ + 1 ) ( ℓ + 2 ) 2 , \binom{\ell+2}{2}=\frac{(\ell+1)(\ell+2)}{2}, ( 2 ℓ + 2 ) = 2 ( ℓ + 1 ) ( ℓ + 2 ) ,
the consecutive triangular numbers. □
Remark 4.2. The proofs of Theorem 1.1 and Corollary 4.1 give an explicit value of q q q beyond which the conclusion of Corollary 4.1 holds. Every set counted in Theorem 1.1(2) satisfies d ⋅ A ⃗ = e ⋅ A ⃗ = 0 \mathbf d\cdot\vec A=\mathbf e\cdot\vec A=0 d ⋅ A = e ⋅ A = 0 for two distinct d , e ∈ R h , k \mathbf d,\mathbf e\in\mathcal{R}_{h,k} d , e ∈ R h , k , so by Lemma 3.4 and Proposition 3.5, there are at most ( 2 h + 1 ) 2 k − 2 q k − 2 / 2 (2h+1)^{2k-2}q^{k-2}/2 ( 2 h + 1 ) 2 k − 2 q k − 2 /2 such sets for every q q q . In the same way, at most ( 2 h + 1 ) k − 1 q k − 1 (2h+1)^{k-1}q^{k-1} ( 2 h + 1 ) k − 1 q k − 1 sets satisfy ∣ h A ∣ < M h , k |hA|<M_{h,k} ∣ h A ∣ < M h , k . If q ≥ 2 ( ( 2 h + 1 ) k + k − 1 ) q\ge2((2h+1)^k+k-1) q ≥ 2 (( 2 h + 1 ) k + k − 1 ) , then the construction in the proof of Theorem 1.1(3) produces at least
1 k ! ⌊ q 2 ⌋ ⌊ q 2 s ⌋ ( q 2 ) k − 3 ≥ q k − 1 2 k + 1 s k ! \frac{1}{k!}\left\lfloor\frac{q}{2}\right\rfloor\left\lfloor\frac{q}{2s}\right\rfloor\binom{q}{2}^{k-3}\ge\frac{q^{k-1}}{2^{k+1}s k!} k ! 1 ⌊ 2 q ⌋ ⌊ 2 s q ⌋ ( 2 q ) k − 3 ≥ 2 k + 1 s k ! q k − 1
sets with ∣ h A ∣ = P ℓ |hA|=P_\ell ∣ h A ∣ = P ℓ , where s = h − ℓ + 1 ≤ h s=h-\ell+1\le h s = h − ℓ + 1 ≤ h . Comparing these bounds, and using ( q k ) ≥ q k / ( 2 k k ! ) \binom{q}{k}\ge q^k/(2^k k!) ( k q ) ≥ q k / ( 2 k k !) for q ≥ 2 k q\ge2k q ≥ 2 k in the case ℓ = 0 \ell=0 ℓ = 0 , we find that the conclusion of Corollary 4.1 holds whenever
q > 2 k k ! h ( 2 h + 1 ) 2 k − 2 . q>2^k k!h(2h+1)^{2k-2}. q > 2 k k ! h ( 2 h + 1 ) 2 k − 2 .
In particular, h h h may grow with q q q , provided that 2 k k ! 3 2 k − 2 h 2 k − 1 < q 2^k k! 3^{2k-2}h^{2k-1}<q 2 k k ! 3 2 k − 2 h 2 k − 1 < q . This bound is far from sharp. For example, a direct computation shows that for ( h , k ) = ( 3 , 4 ) (h,k)=(3,4) ( h , k ) = ( 3 , 4 ) the conclusion of Corollary 4.1 holds for every q q q with 16 ≤ q ≤ 50 16\le q\le50 16 ≤ q ≤ 50 , whereas the bound above requires q > 2 4 ⋅ 4 ! ⋅ 3 ⋅ 7 6 ≈ 1.4 × 10 8 q>2^4\cdot4!\cdot3\cdot7^6\approx1.4\times10^8 q > 2 4 ⋅ 4 ! ⋅ 3 ⋅ 7 6 ≈ 1.4 × 1 0 8 .
Additional Results and Future Work
Throughout this section, h ≥ 2 h\ge2 h ≥ 2 is fixed, so the constants C C C , c c c and q 0 q_0 q 0 may also depend on h h h .
Generalizations of Senger’s Results
This section collects generalizations to arbitrary k ≥ 3 k\ge3 k ≥ 3 of several results of Senger [16 ] , though none are needed for the proof of Theorem 1.1. Let
B h , k ( q ) = { A ∈ ( [ q ] k ) : A is a B h -set } \mathcal{B}_{h,k}(q)=\left\{A\in\binom{[q]}{k}:A\text{ is a }B_h\text{-set}\right\} B h , k ( q ) = { A ∈ ( k [ q ] ) : A is a B h -set }
and
B h , k ∗ ( q ) = { A ∈ ( [ q ] k ) : A is a B h -set but not a B h + 1 -set } . \mathcal{B}_{h,k}^{*}(q)=\left\{A\in\binom{[q]}{k}:A\text{ is a }B_h\text{-set but not a }B_{h+1}\text{-set}\right\}. B h , k ∗ ( q ) = { A ∈ ( k [ q ] ) : A is a B h -set but not a B h + 1 -set } .
Corollary 5.1 (cf. [16 Thm. 1] ). Fix k ≥ 3 k\ge3 k ≥ 3 and h ≥ 2 h\ge2 h ≥ 2 . Then, as q → ∞ q\to\infty q → ∞ ,
1 − ∣ B h , k ( q ) ∣ ( q k ) = Θ ( q − 1 ) . 1-\frac{|\mathcal{B}_{h,k}(q)|}{\binom{q}{k}}=\Theta(q^{-1}). 1 − ( k q ) ∣ B h , k ( q ) ∣ = Θ ( q − 1 ) .
In particular,
∣ B h , k ( q ) ∣ ( q k ) ⟶ 1. \frac{|\mathcal{B}_{h,k}(q)|}{\binom{q}{k}}\longrightarrow1. ( k q ) ∣ B h , k ( q ) ∣ ⟶ 1.
For ( h , k ) = ( 2 , 3 ) (h,k)=(2,3) ( h , k ) = ( 2 , 3 ) ,
lim q → ∞ q ( 1 − ∣ B 2 , 3 ( q ) ∣ ( q 3 ) ) = 3 2 . \lim_{q\to\infty}q\left(1-\frac{|\mathcal{B}_{2,3}(q)|}{\binom{q}{3}}\right)=\frac{3}{2}. q → ∞ lim q ( 1 − ( 3 q ) ∣ B 2 , 3 ( q ) ∣ ) = 2 3 .
Proof. Let N q = ( q k ) − ∣ B h , k ( q ) ∣ N_q = \binom{q}{k} - |B_{h,k}(q)| N q = ( k q ) − ∣ B h , k ( q ) ∣ . By the definition of a B h B_{h} B h -set,
N q = # { A ∈ ( [ q ] k ) : ∣ h A ∣ < M h , k } , N_q = \#\left\{A \in\binom{[q]}{k} : |hA| < M_{h,k}\right\}, N q = # { A ∈ ( k [ q ] ) : ∣ h A ∣ < M h , k } ,
P 1 = M h , k − M 0 , k = M h , k − 1. P_1 = M_{h,k} - M_{0,k} = M_{h,k} - 1. P 1 = M h , k − M 0 , k = M h , k − 1.
Theorem 1.1(3) and (8) therefore give a constant c > 0 c > 0 c > 0 such that, for all sufficiently large q q q ,
c q k − 1 ≤ # { A ∈ ( [ q ] k ) : ∣ h A ∣ = P 1 } ≤ N q ≤ ( 2 h + 1 ) k − 1 q k − 1 . cq^{k-1} \le\#\left\{A \in\binom{[q]}{k} : |hA| = P_1\right\} \le N_q \le(2h+1)^{k-1}q^{k-1}. c q k − 1 ≤ # { A ∈ ( k [ q ] ) : ∣ h A ∣ = P 1 } ≤ N q ≤ ( 2 h + 1 ) k − 1 q k − 1 .
Thus N q = Θ ( q k − 1 ) N_q = \Theta(q^{k-1}) N q = Θ ( q k − 1 ) . Since ( q k ) = Θ ( q k ) \binom{q}{k} = \Theta(q^k) ( k q ) = Θ ( q k ) ,
1 − ∣ B h , k ( q ) ∣ ( q k ) = ( q k ) − ∣ B h , k ( q ) ∣ ( q k ) = N q ( q k ) = Θ ( q − 1 ) ⟶ 0. \begin{aligned}
1-\frac{|B_{h,k}(q)|}{\binom{q}{k}}=\frac{\binom{q}{k}-|B_{h,k}(q)|}{\binom{q}{k}} \\
&=\frac{N_q}{\binom{q}{k}}=\Theta(q^{-1})\longrightarrow0.
\end{aligned} 1 − ( k q ) ∣ B h , k ( q ) ∣ = ( k q ) ( k q ) − ∣ B h , k ( q ) ∣ = ( k q ) N q = Θ ( q − 1 ) ⟶ 0.
For ( h , k ) = ( 2 , 3 ) (h,k)=(2,3) ( h , k ) = ( 2 , 3 ) and a 1 < a 2 < a 3 a_1<a_2<a_3 a 1 < a 2 < a 3 , the six possible two-fold sums satisfy
2 a 1 < a 1 + a 2 < min { 2 a 2 , a 1 + a 3 } ≤ max { 2 a 2 , a 1 + a 3 } < a 2 + a 3 < 2 a 3 . 2a_1<a_1+a_2<\min\{2a_2,a_1+a_3\}\le\max\{2a_2,a_1+a_3\}<a_2+a_3<2a_3. 2 a 1 < a 1 + a 2 < min { 2 a 2 , a 1 + a 3 } ≤ max { 2 a 2 , a 1 + a 3 } < a 2 + a 3 < 2 a 3 .
Hence the only possible collision is 2 a 2 = a 1 + a 3 2a_2=a_1+a_3 2 a 2 = a 1 + a 3 , and
( [ q ] 3 ) ∖ B 2 , 3 ( q ) = { { a , a + r , a + 2 r } : a , r ≥ 1 , a + 2 r ≤ q } . \binom{[q]}{3}\setminus B_{2,3}(q)=\{\{a,a+r,a+2r\}:a,r\ge1,\ a+2r\le q\}. ( 3 [ q ] ) ∖ B 2 , 3 ( q ) = {{ a , a + r , a + 2 r } : a , r ≥ 1 , a + 2 r ≤ q } .
Let m = ⌊ ( q − 1 ) / 2 ⌋ m=\lfloor(q-1)/2\rfloor m = ⌊( q − 1 ) /2 ⌋ . Then
( q 3 ) − ∣ B 2 , 3 ( q ) ∣ = ∑ r = 1 m ( q − 2 r ) = m q − m ( m + 1 ) = q 2 4 + O ( q ) , \begin{aligned}
\binom{q}{3}-|B_{2,3}(q)|=\sum_{r=1}^{m}(q-2r) \\
&=mq-m(m+1) \\
&=\frac{q^2}{4}+O(q),
\end{aligned} ( 3 q ) − ∣ B 2 , 3 ( q ) ∣ = r = 1 ∑ m ( q − 2 r ) = m q − m ( m + 1 ) = 4 q 2 + O ( q ) ,
q ( 1 − ∣ B 2 , 3 ( q ) ∣ ( q 3 ) ) = q ( q 2 / 4 + O ( q ) ) q ( q − 1 ) ( q − 2 ) / 6 = 3 / 2 + O ( q − 1 ) ( 1 − q − 1 ) ( 1 − 2 q − 1 ) ⟶ 3 2 . \begin{aligned}
q\left(1-\frac{|B_{2,3}(q)|}{\binom{q}{3}}\right)
=\frac{q(q^2/4+O(q))}{q(q-1)(q-2)/6} \\
&=\frac{3/2+O(q^{-1})}{(1-q^{-1})(1-2q^{-1})}\longrightarrow\frac{3}{2}.
\end{aligned} q ( 1 − ( 3 q ) ∣ B 2 , 3 ( q ) ∣ ) = q ( q − 1 ) ( q − 2 ) /6 q ( q 2 /4 + O ( q )) = ( 1 − q − 1 ) ( 1 − 2 q − 1 ) 3/2 + O ( q − 1 ) ⟶ 2 3 .
For h = 2 h=2 h = 2 , the convergence to 1 also follows from work of Nathanson [11 ] , which allows k k k to grow with q q q .
Remark 5.2. For k = 3 k=3 k = 3 , the limit in Corollary 5.1 can be computed for every h ≥ 2 h\ge2 h ≥ 2 . Let A ∈ ( [ q ] 3 ) A\in\binom{[q]}{3} A ∈ ( 3 [ q ] ) and write
a 2 − a 1 a 3 − a 1 = u w , gcd ( u , w ) = 1 , 0 < u < w . \frac{a_2-a_1}{a_3-a_1}=\frac{u}{w},\qquad\gcd(u,w)=1,\qquad0<u<w. a 3 − a 1 a 2 − a 1 = w u , g cd( u , w ) = 1 , 0 < u < w .
If d ∈ Z 3 ∖ { 0 } \mathbf d\in\mathbb Z^3\setminus\{0\} d ∈ Z 3 ∖ { 0 } has d 1 + d 2 + d 3 = 0 d_1+d_2+d_3=0 d 1 + d 2 + d 3 = 0 , then
d ⋅ A ⃗ = d 2 ( a 2 − a 1 ) + d 3 ( a 3 − a 1 ) , \mathbf d\cdot\vec A=d_2(a_2-a_1)+d_3(a_3-a_1), d ⋅ A = d 2 ( a 2 − a 1 ) + d 3 ( a 3 − a 1 ) ,
so d ⋅ A ⃗ = 0 \mathbf d\cdot\vec A=0 d ⋅ A = 0 if and only if d 2 u = − d 3 w d_2u=-d_3w d 2 u = − d 3 w , that is, d \mathbf d d is an integer multiple of ( w − u , − w , u ) (w-u,-w,u) ( w − u , − w , u ) . This vector is primitive, has weight ( w − u ) + u = w (w-u)+u=w ( w − u ) + u = w , and has positive first coordinate. By Lemma 3.2 , A A A is a B h B_h B h -set if and only if w > h w>h w > h . For fixed coprime 0 < u < w 0<u<w 0 < u < w , the sets with ( a 2 − a 1 ) / ( a 3 − a 1 ) = u / w (a_2-a_1)/(a_3-a_1)=u/w ( a 2 − a 1 ) / ( a 3 − a 1 ) = u / w are { a , a + u t , a + w t } \{a,a+ut,a+wt\} { a , a + u t , a + w t } with a , t ≥ 1 a,t\ge1 a , t ≥ 1 and a + w t ≤ q a+wt\le q a + w t ≤ q , and there are
∑ t = 1 ⌊ ( q − 1 ) / w ⌋ ( q − w t ) = q 2 2 w + O ( q ) \sum_{t=1}^{\lfloor(q-1)/w\rfloor}(q-wt)=\frac{q^2}{2w}+O(q) t = 1 ∑ ⌊( q − 1 ) / w ⌋ ( q − w t ) = 2 w q 2 + O ( q )
of them. Summing over the φ ( w ) \varphi(w) φ ( w ) admissible values of u u u for each 2 ≤ w ≤ h 2 \le w \le h 2 ≤ w ≤ h , where φ \varphi φ is Euler’s totient function, gives
( q 3 ) − ∣ B h , 3 ( q ) ∣ = q 2 2 ∑ w = 2 h φ ( w ) w + O ( h 2 q ) , \binom{q}{3}-\lvert B_{h,3}(q)\rvert=\frac{q^2}{2}\sum_{w=2}^{h}\frac{\varphi(w)}{w}+O(h^2q), ( 3 q ) − ∣ B h , 3 ( q )∣ = 2 q 2 w = 2 ∑ h w φ ( w ) + O ( h 2 q ) ,
and therefore
lim q → ∞ q ( 1 − ∣ B h , 3 ( q ) ∣ ( q 3 ) ) = 3 ∑ w = 2 h φ ( w ) w . \lim_{q\to\infty}q\left(1-\frac{\lvert B_{h,3}(q)\rvert}{\binom{q}{3}}\right)=3\sum_{w=2}^{h}\frac{\varphi(w)}{w}. q → ∞ lim q ( 1 − ( 3 q ) ∣ B h , 3 ( q )∣ ) = 3 w = 2 ∑ h w φ ( w ) .
For h = 2 h=2 h = 2 this recovers the value 3 / 2 3/2 3/2 in Corollary 5.1, and for h = 3 h=3 h = 3 it gives 7 / 2 7/2 7/2 .
Lemma 5.3 (cf. [16 Lemma 4] ). Given A ∈ B h , k ( q ) A\in B_{h,k}(q) A ∈ B h , k ( q ) , any distinct sum vectors x , y ∈ X h + 1 , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h+1,k} x , y ∈ X h + 1 , k that have the same dot product with A ⃗ \vec{A} A must have disjoint support, and therefore are orthogonal.
Senger proved Lemma 5.3 for k = 4 k=4 k = 4 [16 Lemma 4] . His proof uses only the fact that A A A is a B h B_h B h -set, so it applies without change for every k ≥ 3 k\ge3 k ≥ 3 .
If A ∈ B h , k ∗ ( q ) A\in B^{*}_{h,k}(q) A ∈ B h , k ∗ ( q ) , then A A A is not a B h + 1 B_{h+1} B h + 1 -set, so there are distinct x , y ∈ X h + 1 , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h+1,k} x , y ∈ X h + 1 , k with x ⋅ A ⃗ = y ⋅ A ⃗ \mathbf{x}\cdot\vec{A}=\mathbf{y}\cdot\vec{A} x ⋅ A = y ⋅ A . By Lemma 5.3 , every such pair has disjoint support, because A A A is a B h B_h B h -set. For distinct x , y ∈ X h + 1 , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h+1,k} x , y ∈ X h + 1 , k with disjoint support, let
T x , y = # { A ∈ B h , k ∗ ( q ) : x ⋅ A ⃗ = y ⋅ A ⃗ } . T_{\mathbf{x},\mathbf{y}}=\#\{A\in B^{*}_{h,k}(q):\mathbf{x}\cdot\vec{A}=\mathbf{y}\cdot\vec{A}\}. T x , y = # { A ∈ B h , k ∗ ( q ) : x ⋅ A = y ⋅ A } .
Then
B h , k ∗ ( q ) = ⋃ ( x , y ) { A ∈ B h , k ∗ ( q ) : x ⋅ A ⃗ = y ⋅ A ⃗ } , B^{*}_{h,k}(q)=\bigcup_{(\mathbf{x},\mathbf{y})}\left\{A\in B^{*}_{h,k}(q):\mathbf{x}\cdot\vec{A}=\mathbf{y}\cdot\vec{A}\right\}, B h , k ∗ ( q ) = ( x , y ) ⋃ { A ∈ B h , k ∗ ( q ) : x ⋅ A = y ⋅ A } ,
where the union runs over all pairs of distinct x , y ∈ X h + 1 , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h+1,k} x , y ∈ X h + 1 , k with disjoint support. The following proposition determines when each T x , y T_{\mathbf{x},\mathbf{y}} T x , y is zero and when it has order q k − 1 q^{k-1} q k − 1 .
Proposition 5.4. Let x , y ∈ X h + 1 , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h+1,k} x , y ∈ X h + 1 , k be distinct sum vectors with disjoint support, let d = x − y \mathbf{d}=\mathbf{x}-\mathbf{y} d = x − y , and let D j = d j + d j + 1 + ⋯ + d k D_j=d_j+d_{j+1}+\cdots+d_k D j = d j + d j + 1 + ⋯ + d k for 2 ≤ j ≤ k 2\le j\le k 2 ≤ j ≤ k . Then T x , y ≤ q k − 1 T_{\mathbf{x},\mathbf{y}}\le q^{k-1} T x , y ≤ q k − 1 for every q q q . Moreover, the following statements hold.
(1) If d \mathbf{d} d is not primitive, or if D 2 , … , D k D_2,\ldots,D_k D 2 , … , D k are all nonnegative or all nonpositive, then T x , y = 0 T_{\mathbf{x},\mathbf{y}}=0 T x , y = 0 for every q q q .
(2) Otherwise, T x , y = Θ ( q k − 1 ) T_{\mathbf{x},\mathbf{y}}=\Theta(q^{k-1}) T x , y = Θ ( q k − 1 ) .
Proof. Disjoint support gives
d + = x , d − = y , w ( d ) = ∑ i = 1 k x i = h + 1 , ∑ i = 1 k d i = ( h + 1 ) − ( h + 1 ) = 0. \mathbf{d}^{+}=\mathbf{x},\qquad\mathbf{d}^{-}=\mathbf{y},\qquad w(\mathbf{d})=\sum_{i=1}^{k}x_i=h+1,\qquad\sum_{i=1}^{k}d_i=(h+1)-(h+1)=0. d + = x , d − = y , w ( d ) = i = 1 ∑ k x i = h + 1 , i = 1 ∑ k d i = ( h + 1 ) − ( h + 1 ) = 0.
Since d ≠ 0 \mathbf{d}\ne0 d = 0 , Lemma 3.4 gives
T x , y = # { A ∈ B h , k ∗ ( q ) : d ⋅ A ⃗ = 0 } ≤ # { v ∈ [ q ] k : d ⋅ v = 0 } ≤ q k − 1 . T_{\mathbf{x},\mathbf{y}}=\#\{A\in B^{*}_{h,k}(q):\mathbf{d}\cdot\vec{A}=0\}
\le\#\{\mathbf{v}\in[q]^k:\mathbf{d}\cdot\mathbf{v}=0\}
\le q^{k-1}. T x , y = # { A ∈ B h , k ∗ ( q ) : d ⋅ A = 0 } ≤ # { v ∈ [ q ] k : d ⋅ v = 0 } ≤ q k − 1 .
For (1), first suppose that g = gcd ( ∣ d 1 ∣ , … , ∣ d k ∣ ) ≥ 2 g=\gcd(\lvert d_1\rvert,\ldots,\lvert d_k\rvert)\ge2 g = g cd(∣ d 1 ∣ , … , ∣ d k ∣) ≥ 2 , and let d ′ = d / g \mathbf{d}'=\mathbf{d}/g d ′ = d / g . Then
gcd ( ∣ d 1 ′ ∣ , … , ∣ d k ′ ∣ ) = g g = 1 , \gcd(\lvert d'_1\rvert,\ldots,\lvert d'_k\rvert)=\frac{g}{g}=1, g cd(∣ d 1 ′ ∣ , … , ∣ d k ′ ∣) = g g = 1 ,
∑ i = 1 k d i ′ = 1 g ∑ i = 1 k d i = 0 , \sum_{i=1}^{k}d'_i=\frac{1}{g}\sum_{i=1}^{k}d_i=0, i = 1 ∑ k d i ′ = g 1 i = 1 ∑ k d i = 0 ,
w ( d ′ ) = h + 1 g ≤ h + 1 2 ≤ h . w(\mathbf{d}')=\frac{h+1}{g}\le\frac{h+1}{2}\le h. w ( d ′ ) = g h + 1 ≤ 2 h + 1 ≤ h .
Thus d ′ \mathbf{d}' d ′ or − d ′ -\mathbf{d}' − d ′ lies in R h , k \mathcal{R}_{h,k} R h , k . By Lemma 3.2 ,
d ⋅ A ⃗ = 0 ⟹ d ′ ⋅ A ⃗ = 1 g d ⋅ A ⃗ = 0 ⟹ ∣ h A ∣ < M h , k . \mathbf{d}\cdot\vec{A}=0\quad\Longrightarrow\quad\mathbf{d}'\cdot\vec{A}=\frac{1}{g}\mathbf{d}\cdot\vec{A}=0\quad\Longrightarrow\quad\lvert hA\rvert<M_{h,k}. d ⋅ A = 0 ⟹ d ′ ⋅ A = g 1 d ⋅ A = 0 ⟹ ∣ h A ∣ < M h , k .
Therefore
{ A ∈ B h , k ∗ ( q ) : d ⋅ A ⃗ = 0 } = ∅ , T x , y = 0. \{A\in B^{*}_{h,k}(q):\mathbf{d}\cdot\vec{A}=0\}=\varnothing,\qquad T_{\mathbf{x},\mathbf{y}}=0. { A ∈ B h , k ∗ ( q ) : d ⋅ A = 0 } = ∅ , T x , y = 0.
Next, write t 1 = a 1 t_1=a_1 t 1 = a 1 and t j = a j − a j − 1 t_j=a_j-a_{j-1} t j = a j − a j − 1 for 2 ≤ j ≤ k 2\le j\le k 2 ≤ j ≤ k . Then t j > 0 t_j>0 t j > 0 and a i = ∑ j = 1 i t j a_i=\sum_{j=1}^{i}t_j a i = ∑ j = 1 i t j , so
d ⋅ A ⃗ = ∑ i = 1 k d i ∑ j = 1 i t j = ∑ j = 1 k t j ∑ i = j k d i = t 1 ∑ i = 1 k d i + ∑ j = 2 k t j D j = ∑ j = 2 k t j D j . (9) \begin{aligned}
\mathbf{d}\cdot\vec{A}
&=\sum_{i=1}^{k}d_i\sum_{j=1}^{i}t_j\\
&=\sum_{j=1}^{k}t_j\sum_{i=j}^{k}d_i\\
&=t_1\sum_{i=1}^{k}d_i+\sum_{j=2}^{k}t_jD_j\\
&=\sum_{j=2}^{k}t_jD_j. \tag*{(9)}
\end{aligned} d ⋅ A = i = 1 ∑ k d i j = 1 ∑ i t j = j = 1 ∑ k t j i = j ∑ k d i = t 1 i = 1 ∑ k d i + j = 2 ∑ k t j D j = j = 2 ∑ k t j D j . (9)
The identities
d 1 = − D 2 , d j = D j − D j + 1 ( 2 ≤ j < k ) , d k = D k d_1=-D_2,\qquad d_j=D_j-D_{j+1}\quad(2\le j<k),\qquad d_k=D_k d 1 = − D 2 , d j = D j − D j + 1 ( 2 ≤ j < k ) , d k = D k
give
D 2 = ⋯ = D k = 0 ⟹ d = 0 , D_2=\cdots=D_k=0\quad\Longrightarrow\quad\mathbf{d}=0, D 2 = ⋯ = D k = 0 ⟹ d = 0 ,
which is impossible. Thus (9) gives
D j ≥ 0 for every j ⟹ d ⋅ A ⃗ = ∑ j = 2 k t j D j > 0 , D_j\ge0\text{ for every }j\quad\Longrightarrow\quad\mathbf{d}\cdot\vec{A}=\sum_{j=2}^{k}t_jD_j>0, D j ≥ 0 for every j ⟹ d ⋅ A = j = 2 ∑ k t j D j > 0 ,
D j ≤ 0 for every j ⟹ d ⋅ A ⃗ = ∑ j = 2 k t j D j < 0. D_j\le0\text{ for every }j\quad\Longrightarrow\quad\mathbf{d}\cdot\vec{A}=\sum_{j=2}^{k}t_jD_j<0. D j ≤ 0 for every j ⟹ d ⋅ A = j = 2 ∑ k t j D j < 0.
In either case d ⋅ A ⃗ ≠ 0 \mathbf{d}\cdot\vec{A}\ne0 d ⋅ A = 0 for every A A A , and hence T x , y = 0 T_{x,y}=0 T x , y = 0 .
For (2), suppose that d \mathbf{d} d is primitive and that the D j D_j D j take both signs. Let
L + = ∑ 2 ≤ j ≤ k D j > 0 D j > 0 , L − = − ∑ 2 ≤ j ≤ k D j < 0 D j > 0. L_+=\sum_{\substack{2\le j\le k\\D_j>0}}D_j>0,\qquad
L_-=-\sum_{\substack{2\le j\le k\\D_j<0}}D_j>0. L + = 2 ≤ j ≤ k D j > 0 ∑ D j > 0 , L − = − 2 ≤ j ≤ k D j < 0 ∑ D j > 0.
Choose τ ~ 1 = 1 \widetilde{\tau}_1=1 τ 1 = 1 and, for j ≥ 2 j\ge2 j ≥ 2 , set
τ ~ j = { L − if D j > 0 , L + if D j < 0 , 1 if D j = 0. \widetilde{\tau}_j=
\begin{cases}
L_- & \text{if }D_j>0,\\
L_+ & \text{if }D_j<0,\\
1 & \text{if }D_j=0.
\end{cases} τ j = ⎩ ⎨ ⎧ L − L + 1 if D j > 0 , if D j < 0 , if D j = 0.
Then
∑ j = 2 k τ ~ j D j = L − L + − L + L − = 0. \sum_{j=2}^{k}\widetilde{\tau}_jD_j=L_-L_+-L_+L_-=0. j = 2 ∑ k τ j D j = L − L + − L + L − = 0.
Let τ j = τ ~ j / ( 2 ∑ i = 1 k τ ~ i ) \tau_j=\widetilde{\tau}_j/(2\sum_{i=1}^{k}\widetilde{\tau}_i) τ j = τ j / ( 2 ∑ i = 1 k τ i ) and u i = ∑ j = 1 i τ j u_i=\sum_{j=1}^{i}\tau_j u i = ∑ j = 1 i τ j . We have
u 1 = τ 1 > 0 , u_1=\tau_1>0, u 1 = τ 1 > 0 ,
u i + 1 − u i = τ i + 1 > 0 , u_{i+1}-u_i=\tau_{i+1}>0, u i + 1 − u i = τ i + 1 > 0 ,
u k = ∑ j = 1 k τ j = 1 2 < 1 , u_k=\sum_{j=1}^{k}\tau_j=\frac{1}{2}<1, u k = j = 1 ∑ k τ j = 2 1 < 1 ,
d ⋅ u = ∑ j = 2 k τ j D j = ∑ j = 2 k τ ~ j D j 2 ∑ i = 1 k τ ~ i = 0. \mathbf{d}\cdot\mathbf{u}
=\sum_{j=2}^{k}\tau_jD_j
=\frac{\sum_{j=2}^{k}\widetilde{\tau}_jD_j}{2\sum_{i=1}^{k}\widetilde{\tau}_i}
=0. d ⋅ u = j = 2 ∑ k τ j D j = 2 ∑ i = 1 k τ i ∑ j = 2 k τ j D j = 0.
Hence u ∈ U ∩ H \mathbf{u}\in U\cap H u ∈ U ∩ H , where
U = { v ∈ R k : 0 < v 1 < ⋯ < v k < 1 } , H = { v ∈ R k : d ⋅ v = 0 } . U=\{\mathbf{v}\in\mathbb{R}^{k}:0<v_1<\cdots<v_k<1\},\qquad
H=\{\mathbf{v}\in\mathbb{R}^{k}:\mathbf{d}\cdot\mathbf{v}=0\}. U = { v ∈ R k : 0 < v 1 < ⋯ < v k < 1 } , H = { v ∈ R k : d ⋅ v = 0 } .
Since U U U is open, choose ρ > 0 \rho> 0 ρ > 0 so that the ball B = { v ∈ H : ∥ v − u ∥ < ρ } B = \{v \in H : \lVert v - u\rVert< \rho\} B = { v ∈ H : ∥ v − u ∥ < ρ } lies in U ∩ H U \cap H U ∩ H . The integer kernel Λ = Z k ∩ H \Lambda= \mathbb{Z}^{k} \cap H Λ = Z k ∩ H is a lattice. Primitivity gives
d ⋅ Z k = Z , rank ( Λ ) = k − rank ( Z ) = k − 1 = dim H . \mathbf{d} \cdot\mathbb{Z}^{k} = \mathbb{Z}, \qquad\operatorname{rank}(\Lambda) = k - \operatorname{rank}(\mathbb{Z}) = k - 1 = \dim H. d ⋅ Z k = Z , rank ( Λ ) = k − rank ( Z ) = k − 1 = dim H .
Choose a lattice basis b 1 , … , b k − 1 \mathbf{b}_1,\ldots,\mathbf{b}_{k-1} b 1 , … , b k − 1 and let L = ∑ i = 1 k − 1 ∥ b i ∥ L = \sum_{i=1}^{k-1}\lVert\mathbf{b}_i\rVert L = ∑ i = 1 k − 1 ∥ b i ∥ . Write q u = ∑ i = 1 k − 1 θ i b i q\mathbf{u} = \sum_{i=1}^{k-1}\theta_i\mathbf{b}_i q u = ∑ i = 1 k − 1 θ i b i , and let
λ q = ∑ i = 1 k − 1 ⌊ θ i + 1 2 ⌋ b i . \boldsymbol{\lambda}_q = \sum_{i=1}^{k-1}\left\lfloor\theta_i + \frac{1}{2}\right\rfloor\mathbf{b}_i. λ q = i = 1 ∑ k − 1 ⌊ θ i + 2 1 ⌋ b i .
Then
∥ λ q − q u ∥ ≤ ∑ i = 1 k − 1 ∣ ⌊ θ i + 1 2 ⌋ − θ i ∣ ∥ b i ∥ ≤ L 2 . \lVert\boldsymbol{\lambda}_q-q\mathbf{u}\rVert\leq\sum_{i=1}^{k-1}\left\lvert\left\lfloor\theta_i+\frac{1}{2}\right\rfloor-\theta_i\right\rvert\lVert\mathbf{b}_i\rVert\leq\frac{L}{2}. ∥ λ q − q u ∥ ≤ i = 1 ∑ k − 1 ⌊ θ i + 2 1 ⌋ − θ i ∥ b i ∥ ≤ 2 L .
Let m = ⌊ q ρ / ( 2 L ) ⌋ m = \lfloor q\rho/(2L)\rfloor m = ⌊ q ρ / ( 2 L )⌋ . For integers z i z_i z i with ∣ z i ∣ ≤ m \lvert z_i\rvert\leq m ∣ z i ∣ ≤ m ,
∥ λ q + ∑ i = 1 k − 1 z i b i − q u ∥ ≤ L 2 + m L ≤ L 2 + q ρ 2 < q ρ \left\lVert\boldsymbol{\lambda}_q+\sum_{i=1}^{k-1}z_i\mathbf{b}_i-q\mathbf{u}\right\rVert\leq\frac{L}{2}+mL \leq\frac{L}{2}+\frac{q\rho}{2}<q\rho λ q + i = 1 ∑ k − 1 z i b i − q u ≤ 2 L + m L ≤ 2 L + 2 q ρ < q ρ
for all sufficiently large q q q . All these distinct lattice points lie in q B qB q B , so there is c > 0 c>0 c > 0 such that
# ( Λ ∩ q B ) ≥ ( 2 m + 1 ) k − 1 = ( 2 ⌊ q ρ 2 L ⌋ + 1 ) k − 1 ≥ c q k − 1 . \#(\Lambda\cap qB)\geq(2m+1)^{k-1}=\left(2\left\lfloor\frac{q\rho}{2L}\right\rfloor+1\right)^{k-1}\geq cq^{k-1}. # ( Λ ∩ q B ) ≥ ( 2 m + 1 ) k − 1 = ( 2 ⌊ 2 L q ρ ⌋ + 1 ) k − 1 ≥ c q k − 1 .
Each v ∈ Λ ∩ q B \mathbf{v}\in\Lambda\cap qB v ∈ Λ ∩ q B satisfies
0 < v 1 < ⋯ < v k < q , d ⋅ v = 0 , 0<v_1<\cdots<v_k<q,\qquad\mathbf{d}\cdot\mathbf{v}=0, 0 < v 1 < ⋯ < v k < q , d ⋅ v = 0 ,
so v = A ⃗ \mathbf{v}=\vec{A} v = A for a set A ∈ ( [ q ] k ) A\in\binom{[q]}{k} A ∈ ( k [ q ] ) , and
x ⋅ A ⃗ − y ⋅ A ⃗ = d ⋅ A ⃗ = 0. \mathbf{x}\cdot\vec{A}-\mathbf{y}\cdot\vec{A}=\mathbf{d}\cdot\vec{A}=0. x ⋅ A − y ⋅ A = d ⋅ A = 0.
Since x ≠ y \mathbf{x}\ne\mathbf{y} x = y , each such A A A is not a B h + 1 B_{h+1} B h + 1 -set.
It remains to discard those that are not B h B_h B h -sets. For e ∈ R h , k \mathbf{e}\in R_{h,k} e ∈ R h , k ,
w ( e ) ≤ h < h + 1 = w ( d ) ⟹ e ≠ ± d . w(\mathbf{e})\leq h<h+1=w(\mathbf{d})\quad\Longrightarrow\quad\mathbf{e}\ne\pm\mathbf{d}. w ( e ) ≤ h < h + 1 = w ( d ) ⟹ e = ± d .
The primitive-vector argument in Proposition 3.5 therefore gives linear independence of d \mathbf{d} d and e \mathbf{e} e . Lemma 3.4 and Proposition 3.5 yield
# { sets discarded } ≤ ∑ e ∈ R h , k # { v ∈ [ q ] k : d ⋅ v = e ⋅ v = 0 } ≤ ∣ R h , k ∣ q k − 2 ≤ ( 2 h + 1 ) k − 1 q k − 2 . \begin{aligned}
\#\{\text{sets discarded}\}\leq\sum_{\mathbf{e}\in R_{h,k}}\#\{\mathbf{v}\in[q]^k:\mathbf{d}\cdot\mathbf{v}=\mathbf{e}\cdot\mathbf{v}=0\} \\
&\leq\lvert R_{h,k}\rvert q^{k-2} \\
&\leq(2h+1)^{k-1}q^{k-2}.
\end{aligned} # { sets discarded } ≤ e ∈ R h , k ∑ # { v ∈ [ q ] k : d ⋅ v = e ⋅ v = 0 } ≤ ∣ R h , k ∣ q k − 2 ≤ ( 2 h + 1 ) k − 1 q k − 2 .
Consequently, for all sufficiently large q q q ,
T x , y ≥ # ( Λ ∩ q B ) − # { sets discarded } ≥ c q k − 1 − ( 2 h + 1 ) k − 1 q k − 2 = q k − 1 ( c − ( 2 h + 1 ) k − 1 q ) ≥ c 2 q k − 1 . \begin{aligned}
T_{\mathbf{x},\mathbf{y}}\geq\#(\Lambda\cap qB)-\#\{\text{sets discarded}\} \\
&\geq cq^{k-1}-(2h+1)^{k-1}q^{k-2} \\
&=q^{k-1}\left(c-\frac{(2h+1)^{k-1}}{q}\right) \\
&\geq\frac{c}{2}q^{k-1}.
\end{aligned} T x , y ≥ # ( Λ ∩ q B ) − # { sets discarded } ≥ c q k − 1 − ( 2 h + 1 ) k − 1 q k − 2 = q k − 1 ( c − q ( 2 h + 1 ) k − 1 ) ≥ 2 c q k − 1 .
Together with T x , y ≤ q k − 1 T_{\mathbf{x},\mathbf{y}}\leq q^{k-1} T x , y ≤ q k − 1 , this gives T x , y = Θ ( q k − 1 ) T_{\mathbf{x},\mathbf{y}}=\Theta(q^{k-1}) T x , y = Θ ( q k − 1 ) . □
Example 5.5. Let x = ( h , 0 , 1 , 0 , … , 0 ) \mathbf{x}=(h,0,1,0,\ldots,0) x = ( h , 0 , 1 , 0 , … , 0 ) and y = ( 0 , h + 1 , 0 , … , 0 ) \mathbf{y}=(0,h+1,0,\ldots,0) y = ( 0 , h + 1 , 0 , … , 0 ) . Then d = ( h , − h − 1 , 1 , 0 , … , 0 ) \mathbf{d}=(h,-h-1,1,0,\ldots,0) d = ( h , − h − 1 , 1 , 0 , … , 0 ) is primitive, D 2 = − h < 0 D_2=-h<0 D 2 = − h < 0 and D 3 = 1 > 0 D_3=1>0 D 3 = 1 > 0 , so T x , y = Θ ( q k − 1 ) T_{\mathbf{x},\mathbf{y}}=\Theta(q^{k-1}) T x , y = Θ ( q k − 1 ) by Proposition 5.4 . This vector has the same form as the vector d 0 \mathbf{d}_0 d 0 in the proof of Theorem 1.1, with s = h + 1 s=h+1 s = h + 1 . On the other hand, if x = ( 0 , h , 1 , 0 , … , 0 ) \mathbf{x}=(0,h,1,0,\ldots,0) x = ( 0 , h , 1 , 0 , … , 0 ) and y = ( h + 1 , 0 , … , 0 ) \mathbf{y}=(h+1,0,\ldots,0) y = ( h + 1 , 0 , … , 0 ) , then d = ( − h − 1 , h , 1 , 0 , … , 0 ) \mathbf{d}=(-h-1,h,1,0,\ldots,0) d = ( − h − 1 , h , 1 , 0 , … , 0 ) , and D j ≥ 0 D_j\geq0 D j ≥ 0 for every j ≥ 2 j\geq2 j ≥ 2 , so T x , y = 0 T_{\mathbf{x},\mathbf{y}}=0 T x , y = 0 for every q q q . Directly, d ⋅ A ⃗ = h ( a 2 − a 1 ) + ( a 3 − a 1 ) > 0 \mathbf{d}\cdot\vec{A}=h(a_2-a_1)+(a_3-a_1)>0 d ⋅ A = h ( a 2 − a 1 ) + ( a 3 − a 1 ) > 0 for every A A A .
Lemma 5.6 (Generalization of [16 Lemma 1] ). Fix h ≥ 2 h\geq2 h ≥ 2 and k ≥ 3 k\geq3 k ≥ 3 . As q → ∞ q\to\infty q → ∞ , the following statements hold. (1)
∣ B h , k ∗ ( q ) ∣ = O ( h k − 1 q k − 1 ) . |B_{h,k}^{*}(q)| = O(h^{k-1}q^{k-1}). ∣ B h , k ∗ ( q ) ∣ = O ( h k − 1 q k − 1 ) .
(2)
∣ B h , k ∗ ( q ) ∣ = Ω ( q k − 1 ) . |B_{h,k}^{*}(q)| = \Omega(q^{k-1}). ∣ B h , k ∗ ( q ) ∣ = Ω ( q k − 1 ) .
(3)
# { A ∈ B h , k ∗ ( q ) : ∣ ( h + 1 ) A ∣ ≤ M h + 1 , k − 2 } = O ( h 2 k − 2 q k − 2 ) . \#\{A\in B_{h,k}^{*}(q): |(h+1)A|\le M_{h+1,k}-2\}=O(h^{2k-2}q^{k-2}). # { A ∈ B h , k ∗ ( q ) : ∣ ( h + 1 ) A ∣ ≤ M h + 1 , k − 2 } = O ( h 2 k − 2 q k − 2 ) .
In particular,
∣ B h , k ∗ ( q ) ∣ = Θ ( q k − 1 ) , # { A ∈ B h , k ∗ ( q ) : ∣ ( h + 1 ) A ∣ = M h + 1 , k − 1 } = Θ ( q k − 1 ) . |B_{h,k}^{*}(q)|=\Theta(q^{k-1}),\qquad
\#\{A\in B_{h,k}^{*}(q): |(h+1)A|=M_{h+1,k}-1\}=\Theta(q^{k-1}). ∣ B h , k ∗ ( q ) ∣ = Θ ( q k − 1 ) , # { A ∈ B h , k ∗ ( q ) : ∣ ( h + 1 ) A ∣ = M h + 1 , k − 1 } = Θ ( q k − 1 ) .
Proof. For (1), every A ∈ B h , k ∗ ( q ) A\in B_{h,k}^{*}(q) A ∈ B h , k ∗ ( q ) is not a B h + 1 B_{h+1} B h + 1 -set. The bound in (8) , with h + 1 h+1 h + 1 in place of h h h , gives
∣ B h , k ∗ ( q ) ∣ ≤ # { A ∈ ( [ q ] k ) : ∣ ( h + 1 ) A ∣ < M h + 1 , k } ≤ ( 2 h + 3 ) k − 1 q k − 1 = O ( h k − 1 q k − 1 ) . (10) \begin{aligned}
|B_{h,k}^{*}(q)|\le\#\left\{A\in\binom{[q]}{k}: |(h+1)A|<M_{h+1,k}\right\} \\
&\le(2h+3)^{k-1}q^{k-1} \\
&=O(h^{k-1}q^{k-1}). \tag*{(10)}
\end{aligned} ∣ B h , k ∗ ( q ) ∣ ≤ # { A ∈ ( k [ q ] ) : ∣ ( h + 1 ) A ∣ < M h + 1 , k } ≤ ( 2 h + 3 ) k − 1 q k − 1 = O ( h k − 1 q k − 1 ) . (10)
For (2), use the first pair x , y \mathrm{x},\mathrm{y} x , y in Example 5.5. Proposition 5.4 gives
∣ B h , k ∗ ( q ) ∣ ≥ T x , y = Θ ( q k − 1 ) , |B_{h,k}^{*}(q)|\ge T_{\mathrm{x},\mathrm{y}}=\Theta(q^{k-1}), ∣ B h , k ∗ ( q ) ∣ ≥ T x , y = Θ ( q k − 1 ) ,
proving (2).
For (3), let
N ( A ) = { d ∈ R h + 1 , k : d ⋅ A ⃗ = 0 } . \mathcal{N}(A)=\{\mathrm{d}\in\mathcal{R}_{h+1,k}:\mathrm{d}\cdot\vec{A}=0\}. N ( A ) = { d ∈ R h + 1 , k : d ⋅ A = 0 } .
By Lemma 3.2 ,
A ∈ B h , k ∗ ( q ) ⟹ ∅ ≠ N ( A ) ⊆ R h + 1 , k ∖ R h , k ⟹ w ( d ) = h + 1 for every d ∈ N ( A ) . A\in B_{h,k}^{*}(q)\Longrightarrow\varnothing\ne\mathcal{N}(A)\subseteq\mathcal{R}_{h+1,k}\setminus\mathcal{R}_{h,k}\Longrightarrow w(\mathrm{d})=h+1\text{ for every }\mathrm{d}\in\mathcal{N}(A). A ∈ B h , k ∗ ( q ) ⟹ ∅ = N ( A ) ⊆ R h + 1 , k ∖ R h , k ⟹ w ( d ) = h + 1 for every d ∈ N ( A ) .
If N ( A ) = { d } \mathcal{N}(A)=\{\mathrm{d}\} N ( A ) = { d } , then Lemma 3.6 gives
∣ ( h + 1 ) A ∣ = M h + 1 , k − M ( h + 1 ) − w ( d ) , k = M h + 1 , k − M 0 , k = M h + 1 , k − 1. |(h+1)A|=M_{h+1,k}-M_{(h+1)-w(\mathrm{d}),k}=M_{h+1,k}-M_{0,k}=M_{h+1,k}-1. ∣ ( h + 1 ) A ∣ = M h + 1 , k − M ( h + 1 ) − w ( d ) , k = M h + 1 , k − M 0 , k = M h + 1 , k − 1.
Consequently,
∣ ( h + 1 ) A ∣ ≤ M h + 1 , k − 2 ⟹ ∣ N ( A ) ∣ ≥ 2. |(h+1)A|\le M_{h+1,k}-2\Longrightarrow|\mathcal{N}(A)|\ge2. ∣ ( h + 1 ) A ∣ ≤ M h + 1 , k − 2 ⟹ ∣ N ( A ) ∣ ≥ 2.
Any two distinct vectors in N ( A ) \mathcal{N}(A) N ( A ) are linearly independent by Proposition 3.5. Let F q F_q F q be the number of sets in (3). Lemma 3.4 gives
F q ≤ ∑ { d , e } ∈ ( R h + 1 , k 2 ) # { A ∈ ( [ q ] k ) : d ⋅ A ⃗ = e ⋅ A ⃗ = 0 } ≤ ( ∣ R h + 1 , k ∣ 2 ) q k − 2 ≤ ( 2 h + 3 ) 2 k − 2 2 q k − 2 = O ( h 2 k − 2 q k − 2 ) . (11) \begin{aligned}
F_q\le\sum_{\{\mathrm{d},\mathrm{e}\}\in\binom{\mathcal{R}_{h+1,k}}{2}}\#\left\{A\in\binom{[q]}{k}:\mathrm{d}\cdot\vec{A}=\mathrm{e}\cdot\vec{A}=0\right\} \\
&\le\binom{|\mathcal{R}_{h+1,k}|}{2}q^{k-2} \\
&\le\frac{(2h+3)^{2k-2}}{2}q^{k-2} \\
&=O(h^{2k-2}q^{k-2}). \tag*{(11)}
\end{aligned} F q ≤ { d , e } ∈ ( 2 R h + 1 , k ) ∑ # { A ∈ ( k [ q ] ) : d ⋅ A = e ⋅ A = 0 } ≤ ( 2 ∣ R h + 1 , k ∣ ) q k − 2 ≤ 2 ( 2 h + 3 ) 2 k − 2 q k − 2 = O ( h 2 k − 2 q k − 2 ) . (11)
This proves (3). For fixed h h h and k k k , statements (1) and (2) give ∣ B h , k ∗ ( q ) ∣ = Θ ( q k − 1 ) |B_{h,k}^{*}(q)|=\Theta(q^{k-1}) ∣ B h , k ∗ ( q ) ∣ = Θ ( q k − 1 ) . Choose c > 0 c>0 c > 0 so that ∣ B h , k ∗ ( q ) ∣ ≥ c q k − 1 |B_{h,k}^{*}(q)|\ge cq^{k-1} ∣ B h , k ∗ ( q ) ∣ ≥ c q k − 1 for all sufficiently large q q q . Every set in this family has ∣ ( h + 1 ) A ∣ ≤ M h + 1 , k − 1 |(h+1)A|\le M_{h+1,k}-1 ∣ ( h + 1 ) A ∣ ≤ M h + 1 , k − 1 , so by (11) we get
# { A ∈ B h , k ∗ ( q ) : ∣ ( h + 1 ) A ∣ = M h + 1 , k − 1 } = ∣ B h , k ∗ ( q ) ∣ − F q ≥ c q k − 1 − ( 2 h + 3 ) 2 k − 2 2 q k − 2 = q k − 1 ( c − ( 2 h + 3 ) 2 k − 2 2 q ) ≥ c 2 q k − 1 . \begin{aligned}
\#\{A\in B_{h,k}^{*}(q): |(h+1)A|=M_{h+1,k}-1\}=|B_{h,k}^{*}(q)|-F_q \\
&\ge cq^{k-1}-\frac{(2h+3)^{2k-2}}{2}q^{k-2} \\
&=q^{k-1}\left(c-\frac{(2h+3)^{2k-2}}{2q}\right) \\
&\ge\frac{c}{2}q^{k-1}.
\end{aligned} # { A ∈ B h , k ∗ ( q ) : ∣ ( h + 1 ) A ∣ = M h + 1 , k − 1 } = ∣ B h , k ∗ ( q ) ∣ − F q ≥ c q k − 1 − 2 ( 2 h + 3 ) 2 k − 2 q k − 2 = q k − 1 ( c − 2 q ( 2 h + 3 ) 2 k − 2 ) ≥ 2 c q k − 1 .
for all sufficiently large q q q . The same count is at most ∣ B h , k ∗ ( q ) ∣ |\mathcal{B}^{*}_{h,k}(q)| ∣ B h , k ∗ ( q ) ∣ , which is at most ( 2 h + 3 ) k − 1 q k − 1 (2h+3)^{k-1}q^{k-1} ( 2 h + 3 ) k − 1 q k − 1 by (10) , proving that it is Θ ( q k − 1 ) \Theta(q^{k-1}) Θ ( q k − 1 ) . □
Proposition 5.7 (cf. [16 Lemma 6] ). Let k ≥ 3 k \ge3 k ≥ 3 , h ≥ 2 h \ge2 h ≥ 2 and q ≥ k q \ge k q ≥ k , and define
S h + 1 , k ( q ) = { x ⋅ A ⃗ : x ∈ X h + 1 , k , A ∈ ( [ q ] k ) } . S_{h+1,k}(q)=\left\{\mathbf{x}\cdot\vec{A}:\mathbf{x}\in\mathcal{X}_{h+1,k},\ A\in\binom{[q]}{k}\right\}. S h + 1 , k ( q ) = { x ⋅ A : x ∈ X h + 1 , k , A ∈ ( k [ q ] ) } . Then
S h + 1 , k ( q ) = [ ( h + 1 ) . . ( h + 1 ) q ] , ∣ S h + 1 , k ( q ) ∣ = ( h + 1 ) q − h . S_{h+1,k}(q)=[(h+1)..(h+1)q],\qquad|S_{h+1,k}(q)|=(h+1)q-h. S h + 1 , k ( q ) = [( h + 1 ) .. ( h + 1 ) q ] , ∣ S h + 1 , k ( q ) ∣ = ( h + 1 ) q − h . For an integer s s s , let
ν q ( s ) = # { ( x , A ) ∈ X h + 1 , k × ( [ q ] k ) : x ⋅ A ⃗ = s } . \nu_q(s)=\#\left\{(\mathbf{x},A)\in\mathcal{X}_{h+1,k}\times\binom{[q]}{k}:\mathbf{x}\cdot\vec{A}=s\right\}. ν q ( s ) = # { ( x , A ) ∈ X h + 1 , k × ( k [ q ] ) : x ⋅ A = s } . Then
ν q ( s ) = ν q ( ( h + 1 ) ( q + 1 ) − s ) \nu_q(s)=\nu_q\left((h+1)(q+1)-s\right) ν q ( s ) = ν q ( ( h + 1 ) ( q + 1 ) − s ) for every s ∈ Z s\in\mathbb{Z} s ∈ Z .
Proof. For x ∈ X h + 1 , k \mathbf{x}\in\mathcal{X}_{h+1,k} x ∈ X h + 1 , k and A ∈ ( [ q ] k ) A\in\binom{[q]}{k} A ∈ ( k [ q ] ) ,
h + 1 = ∑ i = 1 k x i ≤ ∑ i = 1 k x i a i ≤ q ∑ i = 1 k x i = ( h + 1 ) q . h+1=\sum_{i=1}^{k}x_i\le\sum_{i=1}^{k}x_i a_i\le q\sum_{i=1}^{k}x_i=(h+1)q. h + 1 = i = 1 ∑ k x i ≤ i = 1 ∑ k x i a i ≤ q i = 1 ∑ k x i = ( h + 1 ) q .
Thus S h + 1 , k ( q ) ⊆ [ ( h + 1 ) . . ( h + 1 ) q ] S_{h+1,k}(q)\subseteq[(h+1)..(h+1)q] S h + 1 , k ( q ) ⊆ [( h + 1 ) .. ( h + 1 ) q ] .
Conversely, let n ∈ [ ( h + 1 ) . . ( h + 1 ) q ] n\in[(h+1)..(h+1)q] n ∈ [( h + 1 ) .. ( h + 1 ) q ] . By division with remainder,
n = ( h + 1 ) a + b , 1 ≤ a ≤ q , 0 ≤ b ≤ h . n=(h+1)a+b,\qquad1\le a\le q,\qquad0\le b\le h. n = ( h + 1 ) a + b , 1 ≤ a ≤ q , 0 ≤ b ≤ h .
Write e i \mathbf{e}_i e i for the i i i th coordinate vector. If b = 0 b=0 b = 0 , choose A ∈ ( [ q ] k ) A\in\binom{[q]}{k} A ∈ ( k [ q ] ) containing a = a i a=a_i a = a i , and let x = ( h + 1 ) e i \mathbf{x}=(h+1)\mathbf{e}_i x = ( h + 1 ) e i . Then
∑ j = 1 k x j = h + 1 , x ⋅ A ⃗ = ( h + 1 ) a = n . \sum_{j=1}^{k}x_j=h+1,\qquad\mathbf{x}\cdot\vec{A}=(h+1)a=n. j = 1 ∑ k x j = h + 1 , x ⋅ A = ( h + 1 ) a = n .
If b > 0 b>0 b > 0 , then a < q a<q a < q . Choose A ∈ ( [ q ] k ) A\in\binom{[q]}{k} A ∈ ( k [ q ] ) containing a = a i a=a_i a = a i and a + 1 = a j a+1=a_j a + 1 = a j , and let x = ( h + 1 − b ) e i + b e j \mathbf{x}=(h+1-b)\mathbf{e}_i+b\mathbf{e}_j x = ( h + 1 − b ) e i + b e j . Then
∑ t = 1 k x t = ( h + 1 − b ) + b = h + 1 , \sum_{t=1}^{k}x_t=(h+1-b)+b=h+1, t = 1 ∑ k x t = ( h + 1 − b ) + b = h + 1 ,
x ⋅ A ⃗ = ( h + 1 − b ) a + b ( a + 1 ) = ( h + 1 ) a + b = n . \begin{aligned}
\mathbf{x}\cdot\vec{A}=(h+1-b)a+b(a+1) \\
&=(h+1)a+b=n.
\end{aligned} x ⋅ A = ( h + 1 − b ) a + b ( a + 1 ) = ( h + 1 ) a + b = n .
These choices of A A A are possible because q ≥ k q\ge k q ≥ k . Therefore
S h + 1 , k ( q ) = [ ( h + 1 ) . . ( h + 1 ) q ] , S_{h+1,k}(q)=[(h+1)..(h+1)q], S h + 1 , k ( q ) = [( h + 1 ) .. ( h + 1 ) q ] ,
∣ S h + 1 , k ( q ) ∣ = ( h + 1 ) q − ( h + 1 ) + 1 = ( h + 1 ) q − h . |S_{h+1,k}(q)|=(h+1)q-(h+1)+1=(h+1)q-h. ∣ S h + 1 , k ( q ) ∣ = ( h + 1 ) q − ( h + 1 ) + 1 = ( h + 1 ) q − h .
For the symmetry, define
A ′ = { q + 1 − a : a ∈ A } , x ′ = ( x k , … , x 1 ) , A ⃗ ′ = ( q + 1 − a k , … , q + 1 − a 1 ) . A'=\{q+1-a:a\in A\},\qquad\mathbf{x}'=(x_k,\ldots,x_1),\qquad\vec{A}'=(q+1-a_k,\ldots,q+1-a_1). A ′ = { q + 1 − a : a ∈ A } , x ′ = ( x k , … , x 1 ) , A ′ = ( q + 1 − a k , … , q + 1 − a 1 ) .
Then
x ′ ⋅ A ⃗ ′ = ∑ i = 1 k x k + 1 − i ( q + 1 − a k + 1 − i ) = ( q + 1 ) ∑ i = 1 k x i − ∑ i = 1 k x i a i = ( h + 1 ) ( q + 1 ) − x ⋅ A ⃗ . \begin{aligned}
\mathbf{x}'\cdot\vec{A}'=\sum_{i=1}^{k}x_{k+1-i}(q+1-a_{k+1-i}) \\
&=(q+1)\sum_{i=1}^{k}x_i-\sum_{i=1}^{k}x_i a_i \\
&=(h+1)(q+1)-\mathbf{x}\cdot\vec{A}.
\end{aligned} x ′ ⋅ A ′ = i = 1 ∑ k x k + 1 − i ( q + 1 − a k + 1 − i ) = ( q + 1 ) i = 1 ∑ k x i − i = 1 ∑ k x i a i = ( h + 1 ) ( q + 1 ) − x ⋅ A .
Applying the same transformation twice gives A ′ ′ = A A''=A A ′′ = A and x ′ ′ = x \mathbf{x}''=\mathbf{x} x ′′ = x . It is therefore a bijection between the pairs counted by ν q ( s ) \nu_q(s) ν q ( s ) and those counted by ν q ( ( h + 1 ) ( q + 1 ) − s ) \nu_q((h+1)(q+1)-s) ν q (( h + 1 ) ( q + 1 ) − s ) , giving the stated equality. □
Questions
We conclude with several questions suggested by the results above.
Question 1. For h ≥ 2 h \ge2 h ≥ 2 and k ≥ 3 k \ge3 k ≥ 3 , let q 0 ( h , k ) q_0(h,k) q 0 ( h , k ) be the smallest integer such that Corollary 4.1 holds for every q ≥ q 0 ( h , k ) q \ge q_0(h,k) q ≥ q 0 ( h , k ) . By Remark 4.2,
q 0 ( h , k ) ≤ 2 k k ! h ( 2 h + 1 ) 2 k − 2 + 1. q_0(h,k) \le2^k k!h(2h+1)^{2k-2}+1. q 0 ( h , k ) ≤ 2 k k ! h ( 2 h + 1 ) 2 k − 2 + 1.
Can this bound be improved? How fast can h h h grow with q q q while the conclusion still holds?
Direct computation gives the following possible values of q 0 ( h , k ) q_0(h,k) q 0 ( h , k ) :
Table 1.
These values have been verified for q ≤ 120 , 120 , 60 , 50 q \le120,120,60,50 q ≤ 120 , 120 , 60 , 50 , respectively, with the conclusion failing at q = 4 , 5 , 7 , 15 q=4,5,7,15 q = 4 , 5 , 7 , 15 .
Question 2. By Corollary 5.1,
q ( 1 − ∣ B h , k ( q ) ∣ ( q k ) ) q\left(1-\frac{|\mathcal{B}_{h,k}(q)|}{\binom{q}{k}}\right) q ( 1 − ( k q ) ∣ B h , k ( q ) ∣ )
is bounded above and below by positive constants. For k = 3 k=3 k = 3 , it converges to 3 ∑ w = 2 h φ ( w ) / w 3\sum_{w=2}^{h}\varphi(w)/w 3 ∑ w = 2 h φ ( w ) / w by Remark 5.2. Does it converge for every k ≥ 4 k \ge4 k ≥ 4 ? If so, what is its limit c h , k c_{h,k} c h , k ? Is it eventually monotone in q q q ?
For ( h , k ) = ( 2 , 4 ) (h,k)=(2,4) ( h , k ) = ( 2 , 4 ) , the only relations of weight at most 2 that can hold when a 1 < a 2 < a 3 < a 4 a_1<a_2<a_3<a_4 a 1 < a 2 < a 3 < a 4 are
2 a 2 = a 1 + a 3 , 2 a 3 = a 2 + a 4 , 2 a 2 = a 1 + a 4 , 2 a 3 = a 1 + a 4 , a 1 + a 4 = a 2 + a 3 . 2a_2=a_1+a_3,\qquad2a_3=a_2+a_4,\qquad2a_2=a_1+a_4,\qquad2a_3=a_1+a_4,\qquad a_1+a_4=a_2+a_3. 2 a 2 = a 1 + a 3 , 2 a 3 = a 2 + a 4 , 2 a 2 = a 1 + a 4 , 2 a 3 = a 1 + a 4 , a 1 + a 4 = a 2 + a 3 .
The numbers of sets in ( [ q ] 4 ) \binom{[q]}{4} ( 4 [ q ] ) satisfying them are asymptotic to q 3 / 12 q^3/12 q 3 /12 , q 3 / 12 q^3/12 q 3 /12 , q 3 / 24 q^3/24 q 3 /24 , q 3 / 24 q^3/24 q 3 /24 and q 3 / 12 q^3/12 q 3 /12 , respectively, and only O ( q 2 ) O(q^2) O ( q 2 ) sets satisfy two of them. Hence c 2 , 4 = 24 ⋅ 1 3 = 8 c_{2,4}=24\cdot\frac{1}{3}=8 c 2 , 4 = 24 ⋅ 3 1 = 8 .
Can c h , k c_{h,k} c h , k be expressed in general as a sum of normalized ( k − 1 ) (k-1) ( k − 1 ) -dimensional volumes of the sections
{ v ∈ R k : 0 < v 1 < ⋯ < v k < 1 , d ⋅ v = 0 } , d ∈ R h , k ? \left\{\mathbf{v}\in\mathbb{R}^k:0<v_1<\cdots<v_k<1,\ \mathbf{d}\cdot\mathbf{v}=0\right\},\qquad\mathbf{d}\in\mathcal{R}_{h,k}? { v ∈ R k : 0 < v 1 < ⋯ < v k < 1 , d ⋅ v = 0 } , d ∈ R h , k ?
Question 3. For an integer t t t , let N h , k ( t ; q ) N_{h,k}(t;q) N h , k ( t ; q ) count the sets A ∈ ( [ q ] k ) A\in\binom{[q]}{k} A ∈ ( k [ q ] ) for which there exist distinct x , y ∈ X h , k \mathbf{x},\mathbf{y}\in\mathcal{X}_{h,k} x , y ∈ X h , k satisfying
( x − y ) ⋅ A ⃗ = t . (\mathbf{x}-\mathbf{y})\cdot\vec{A}=t. ( x − y ) ⋅ A = t .
In particular, N h , k ( 0 ; q ) N_{h,k}(0;q) N h , k ( 0 ; q ) counts the sets that are not B h B_h B h -sets. Each of the at most M h , k 2 M_{h,k}^2 M h , k 2 pairs ( x , y ) (\mathbf{x},\mathbf{y}) ( x , y ) gives a single equation ( x − y ) ⋅ v = t (\mathbf{x}-\mathbf{y})\cdot\mathbf{v}=t ( x − y ) ⋅ v = t with x − y ≠ 0 \mathbf{x}-\mathbf{y}\ne0 x − y = 0 , so by the argument of Lemma 3.4 ,
N h , k ( t ; q ) ≤ M h , k 2 q k − 1 . N_{h,k}(t;q)\le M_{h,k}^2q^{k-1}. N h , k ( t ; q ) ≤ M h , k 2 q k − 1 .
How does N h , k ( t ; q ) N_{h,k}(t;q) N h , k ( t ; q ) depend on t t t ? More generally, what can be said about the distribution of differences in h A − h A hA-hA h A − h A ?
Related questions on sums and differences of random sets have been studied in [6 , 7 , 9 ] .
Question 4. Can the function ν q \nu_q ν q from Proposition 5.7 be determined explicitly? In particular, does
lim q → ∞ q − ( k − 1 ) ν q ( ⌊ σ q ⌋ ) \lim_{q\to\infty}q^{-(k-1)}\nu_q(\lfloor\sigma q\rfloor) q → ∞ lim q − ( k − 1 ) ν q (⌊ σ q ⌋)
exist for every σ ∈ ( 0 , h + 1 ) \sigma\in(0,h+1) σ ∈ ( 0 , h + 1 ) ? If so, is the resulting function piecewise polynomial?
References
(Saad A. Awan) Department of Mathematics, University of Kansas, Lawrence, KS 66045 Email address: saad_awan@ku.edu
(Steven J. Miller) Department of Mathematics, Williams College, Williamstown, MA 01267 Email address: sjm1@williams.edu, Steven.Miller.MC.96@aya.yale.edu
(Linh Nguyen) Department of Mathematics, Gettysburg College, Gettysburg, PA 17325 Email address: nguyli01@gettysburg.edu
(Steven Senger) Department of Mathematics, Missouri State University, Springfield, MO 65809 Email address: stevensenger@missouristate.edu
(Elvis Wong) Department of Mathematics, The University of Manchester, Manchester, M13 9PL Email address: yik.wong@student.manchester.ac.uk