Introduction
Two classical constants distinguish between finding a nonempty zero-sum subsequence and finding one of prescribed length. For a finite abelian group H H H , the Davenport constant D ( H ) D(H) D ( H ) is the least integer l l l such that every sequence of length l l l over H H H has a nonempty zero-sum subsequence. The Erdős–Ginzburg–Ziv constant s ( H ) s(H) s ( H ) is defined in the same way, with the additional requirement that the subsequence have length exp ( H ) \exp(H) exp ( H ) , the exponent of H H H . Let C n C_n C n denote the cyclic group of order n n n . For a prime p p p , we have D ( C p ) = p D(C_p)=p D ( C p ) = p , and the Erdős–Ginzburg–Ziv theorem gives s ( C p ) = 2 p − 1 s(C_p)=2p-1 s ( C p ) = 2 p − 1 . Thus among any 2 p − 1 2p-1 2 p − 1 integers one can find p p p terms whose sum is divisible by p p p .
In their study of zero-sum subsequences of cross number 1, Gao, Hui, Jiang, Li and Wang asked for a p p p -term sum divisible by p p p but not by p 2 p^2 p 2 when the terms are coprime to p p p [3 Conjecture 3.2] . Gao, Jiang, Lei, Lin and Yang formulated this question in terms of the following constant.
Definition. For a prime p p p , let s p ∗ s_p^* s p ∗ be the smallest integer l l l such that every sequence of l l l integers coprime to p p p has a subsequence of length p p p whose sum is divisible by p p p but not by p 2 p^2 p 2 [4 Definition 1.1] .
For odd p p p , the sequence 1 p − 1 ( 1 − p ) ( − 1 ) p − 1 ( p − 1 ) 1^{p-1}(1-p)(-1)^{p-1}(p-1) 1 p − 1 ( 1 − p ) ( − 1 ) p − 1 ( p − 1 ) in [3 ] gives s p ∗ ≥ 2 p + 1 s_p^* \ge2p+1 s p ∗ ≥ 2 p + 1 , and the conjecture asserts that equality holds. The upper bound s p ∗ ≤ 4 p − 3 s_p^* \le4p-3 s p ∗ ≤ 4 p − 3 follows from Reiher’s theorem s ( C p ⊕ C p ) = 4 p − 3 s(C_p \oplus C_p)=4p-3 s ( C p ⊕ C p ) = 4 p − 3 [9 ] . Represent each term modulo p 2 p^2 p 2 as u + p v u+pv u + p v with 1 ≤ u ≤ p − 1 1\le u\le p-1 1 ≤ u ≤ p − 1 and 0 ≤ v ≤ p − 1 0\le v\le p-1 0 ≤ v ≤ p − 1 , and apply the theorem to the pairs ( u , v ) (u,v) ( u , v ) modulo p p p (see [4 ] ). In the selected p p p terms, the sum of the u u u -coordinates is a positive multiple of p p p smaller than p 2 p^2 p 2 , and the sum of the v v v -coordinates is a multiple of p p p . Gao, Jiang, Lei, Lin and Yang improved the upper bound to 3 p − 2 3p-2 3 p − 2 [4 Theorem 1.3] and reported that equality with 2 p + 1 2p+1 2 p + 1 had been verified for p = 3 , 5 , 7 p=3,5,7 p = 3 , 5 , 7 .
Related problems differ in the permitted lengths or in the modulus. In a preprint, Gao, Jiang and Mu showed that for a prime power n n n , every sequence of 2 n − 1 2n-1 2 n − 1 integers coprime to n n n has a nonempty subsequence of length at most n n n with sum u u u satisfying gcd ( u , n 2 ) = n \gcd(u,n^2)=n g cd( u , n 2 ) = n . They also determined the corresponding extremal sequences [5 ] . For n = p n=p n = p the condition on the sum is the same as in the definition of s p ∗ s_p^* s p ∗ , with the length allowed to be smaller than p p p . Sun considers versions with exactly n n n terms and general integer modulus n n n in the preprint [11 ] .
The defining condition for s p ∗ s_p^* s p ∗ depends only on the residues modulo p 2 p^2 p 2 . Let G = Z / p 2 Z G=\mathbb{Z}/p^2\mathbb{Z} G = Z / p 2 Z , whose additive group is C p 2 C_{p^2} C p 2 . The ideal p G = { p g : g ∈ G } pG=\{pg:g\in G\} pG = { p g : g ∈ G } is an additive subgroup of order p p p , and G × = G ∖ p G G^\times=G\setminus pG G × = G ∖ pG is the set of units of G G G . We identify C p C_p C p with the additive group of Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z . The canonical homomorphism π : G → C p \pi:G\to C_p π : G → C p is reduction modulo p p p and has kernel p G pG pG . For a sequence T T T over G G G , let T ‾ \overline{T} T be the sequence obtained by applying π \pi π to each term of T T T . For a sequence T T T , let ∣ T ∣ |T| ∣ T ∣ be its length and σ ( T ) \sigma(T) σ ( T ) its sum. A sequence S S S of length 2 p 2p 2 p over G × G^{\times} G × is called exceptional if it has no subsequence T T T of length p p p with σ ( T ) ∈ p G ∖ { 0 } \sigma(T) \in pG \setminus\{0\} σ ( T ) ∈ pG ∖ { 0 } .
The following theorem classifies the exceptional sequences. Its corollary proves s p ∗ = 2 p + 1 s_p^{*}=2p+1 s p ∗ = 2 p + 1 for all odd primes, so the classification gives all sequences of length s p ∗ − 1 s_p^{*}-1 s p ∗ − 1 that fail the defining condition.
Theorem 1.1. Let p p p be an odd prime and let S S S be a sequence of length 2 p 2p 2 p over G × G^{\times} G × . Then S S S is exceptional if and only if it has one of the following forms.
(i) S = A B S=AB S = A B , where r , t r,t r , t are distinct nonzero elements of C p C_p C p and ∣ A ∣ = ∣ B ∣ = p |A|=|B|=p ∣ A ∣ = ∣ B ∣ = p , A ‾ = r p \overline{A}=r^p A = r p , B ‾ = t p \overline{B}=t^p B = t p , σ ( A ) = σ ( B ) = 0 \sigma(A)=\sigma(B)=0 σ ( A ) = σ ( B ) = 0 .
(ii) S = a p − 1 b p − 1 x y S=a^{p-1}b^{p-1}xy S = a p − 1 b p − 1 x y , where a , b , x , y ∈ G × a,b,x,y\in G^{\times} a , b , x , y ∈ G × , a − b ∈ G × a-b\in G^{\times} a − b ∈ G × , and there exists an integer i i i with 1 ≤ i ≤ p − 2 1\le i\le p-2 1 ≤ i ≤ p − 2 such that x = − i a − ( p − 1 − i ) b x=-ia-(p-1-i)b x = − ia − ( p − 1 − i ) b , y = − ( p − 1 − i ) a − i b y=-(p-1-i)a-ib y = − ( p − 1 − i ) a − ib .
The terms x x x and y y y may coincide.
Corollary 1.2. For every odd prime p p p , one has s p ∗ = 2 p + 1 s_p^{*}=2p+1 s p ∗ = 2 p + 1 .
The proof begins with the case of two distinct terms with the same image in C p C_p C p . A common completion to a p p p -term subsequence gives a contradiction unless the sequence is concentrated in two nonzero residue classes, each containing p p p terms. When π \pi π is injective on the support, we first treat sequences with large multiplicities. In the remaining cases, we distribute the copies of each value among layers and use polynomial interpolation modulo p p p and p 2 p^2 p 2 to bound the corresponding sumsets. These bounds allow us to lift selected sumsets to integer intervals and then complete their sums to p p p terms.
Notation and preliminaries
Sequences and their images
We denote by N \mathbb{N} N the set of positive integers and by N 0 = N ∪ { 0 } \mathbb{N}_0=\mathbb{N}\cup\{0\} N 0 = N ∪ { 0 } the set of nonnegative integers. For real numbers a , b a,b a , b , we set [ a , b ] = { n ∈ Z : a ≤ n ≤ b } [a,b]=\{n\in\mathbb{Z}:a\le n\le b\} [ a , b ] = { n ∈ Z : a ≤ n ≤ b } .
Let H H H be a finite additive abelian group. We denote by F ( H ) \mathcal{F}(H) F ( H ) the free abelian monoid with basis H H H . Its elements are called sequences over H H H . We identify g ∈ H g\in H g ∈ H with the one-term sequence g g g . We denote concatenation by juxtaposition, and g j g^j g j denotes the sequence of j j j copies of g g g . Unless otherwise stated, ∏ \prod ∏ denotes concatenation of an indexed family of sequences. For n ∈ Z n\in\mathbb{Z} n ∈ Z and g ∈ H g\in H g ∈ H , n g ng n g denotes the integer multiple of g g g in H H H . For S ∈ F ( H ) S\in\mathcal{F}(H) S ∈ F ( H ) and x ∈ H x\in H x ∈ H , let v x ( S ) ∈ N 0 v_x(S)\in\mathbb{N}_0 v x ( S ) ∈ N 0 be the multiplicity of x x x in S S S . We write T ∣ S T\mid S T ∣ S if v x ( T ) ≤ v x ( S ) v_x(T)\le v_x(S) v x ( T ) ≤ v x ( S ) for all x ∈ H x\in H x ∈ H . Then T T T is a subsequence of S S S , and S T − 1 ST^{-1} S T − 1 denotes the sequence obtained by deleting T T T from S S S . The identity of F ( H ) \mathcal{F}(H) F ( H ) is the empty sequence.
For a sequence
S = g 1 ⋯ g l = ∏ x ∈ H x v x ( S ) ∈ F ( H ) , S=g_1\cdots g_l=\prod_{x\in H}x^{v_x(S)}\in\mathcal{F}(H), S = g 1 ⋯ g l = x ∈ H ∏ x v x ( S ) ∈ F ( H ) ,
we use the following notation.
∣ S ∣ = l = ∑ x ∈ H v x ( S ) |S|=l=\sum_{x\in H}v_x(S) ∣ S ∣ = l = ∑ x ∈ H v x ( S ) is the length of $S.
σ ( S ) = ∑ i = 1 l g i = ∑ x ∈ H v x ( S ) x \sigma(S)=\sum_{i=1}^{l}g_i=\sum_{x\in H}v_x(S)x σ ( S ) = ∑ i = 1 l g i = ∑ x ∈ H v x ( S ) x is the sum of S S S .
supp ( S ) = { x ∈ H : v x ( S ) > 0 } \operatorname{supp}(S)=\{x\in H:v_x(S)>0\} supp ( S ) = { x ∈ H : v x ( S ) > 0 } is the support of S S S .
h ( S ) = max { v x ( S ) : x ∈ H } h(S)=\max\{v_x(S):x\in H\} h ( S ) = max { v x ( S ) : x ∈ H } is the maximum multiplicity in S S S .
S S S is a zero-sum sequence if σ ( S ) = 0 \sigma(S)=0 σ ( S ) = 0 . A nonempty zero-sum sequence is minimal if it has no nonempty proper zero-sum subsequence. A sequence is zero-sum free if it has no nonempty zero-sum subsequence.
Σ j ( S ) = { σ ( T ) : T ∣ S , ∣ T ∣ = j } \Sigma_j(S)=\{\sigma(T):T\mid S,\ |T|=j\} Σ j ( S ) = { σ ( T ) : T ∣ S , ∣ T ∣ = j } for j ∈ [ 0 , ∣ S ∣ ] j\in[0,|S|] j ∈ [ 0 , ∣ S ∣ ] . We denote by Σ ( S ) \Sigma(S) Σ ( S ) the set of all nonempty subsequence sums.
For g ∈ G g\in G g ∈ G , let g ‾ = π ( g ) \overline{g}=\pi(g) g = π ( g ) . For a sequence T = t 1 ⋯ t k T=t_1\cdots t_k T = t 1 ⋯ t k over G G G , let T ‾ = t 1 ‾ ⋯ t k ‾ \overline{T}=\overline{t_1}\cdots\overline{t_k} T = t 1 ⋯ t k . Since π \pi π is a homomorphism with kernel p G pG pG , we have σ ( T ‾ ) = π ( σ ( T ) ) \sigma(\overline{T})=\pi(\sigma(T)) σ ( T ) = π ( σ ( T )) and σ ( T ‾ ) = 0 \sigma(\overline{T})=0 σ ( T ) = 0 if and only if σ ( T ) ∈ p G \sigma(T)\in pG σ ( T ) ∈ pG . For a subset A ⊆ G A\subseteq G A ⊆ G , let π ( A ) = { π ( a ) : a ∈ A } \pi(A)=\{\pi(a):a\in A\} π ( A ) = { π ( a ) : a ∈ A } . Equivalently, an exceptional sequence S S S satisfies
∣ T ∣ = p , T ∣ S , σ ( T ‾ ) = 0 ⟹ σ ( T ) = 0. (1) |T|=p,\quad T\mid S,\quad\sigma(\overline{T})=0\quad\Longrightarrow\quad\sigma(T)=0. \tag*{(1)} ∣ T ∣ = p , T ∣ S , σ ( T ) = 0 ⟹ σ ( T ) = 0. (1)
Since s ( C p ) = 2 p − 1 s(C_p)=2p-1 s ( C p ) = 2 p − 1 , S ‾ \overline{S} S has a p p p -term zero-sum subsequence for every exceptional sequence S S S .
Sumset bounds and long zero-sum sequences
For subsets A , B A,B A , B of an additive abelian group, write
− A = { − a : a ∈ A } , A + B = { a + b : a ∈ A , b ∈ B } . -A=\{-a:a\in A\},\qquad A+B=\{a+b:a\in A,\ b\in B\}. − A = { − a : a ∈ A } , A + B = { a + b : a ∈ A , b ∈ B } .
The sumset of A A A and B B B is A + B A+B A + B , and their difference set is A − B = A + ( − B ) A-B=A+(-B) A − B = A + ( − B ) . For a group element x x x , we denote { x } + A \{x\}+A { x } + A by x + A x+A x + A . For a positive integer r r r , the sumset of r r r copies of A A A is denoted by r A rA r A . For an integer set I I I and a group element g g g , we use I g = { i g : i ∈ I } Ig=\{ig:i\in I\} I g = { i g : i ∈ I } .
We use the following form of the Cauchy–Davenport theorem, obtained by iterating the two-set inequality.
Lemma 2.1 ([1, 2]). Let p p p be a prime and let A 1 , … , A r A_1,\ldots,A_r A 1 , … , A r be nonempty subsets of C p C_p C p , where r ≥ 1 r\geq1 r ≥ 1 . Then
∣ A 1 + ⋯ + A r ∣ ≥ min { p , 1 + ∑ j = 1 r ( ∣ A j ∣ − 1 ) } . (2) |A_1+\cdots+A_r|\geq\min\left\{p,1+\sum_{j=1}^{r}(|A_j|-1)\right\}. \tag*{(2)} ∣ A 1 + ⋯ + A r ∣ ≥ min { p , 1 + j = 1 ∑ r ( ∣ A j ∣ − 1 ) } . (2)
We also use the following form of Vosper’s theorem [12 ] . If A , B ⊆ C p A,B\subseteq C_p A , B ⊆ C p , ∣ A ∣ , ∣ B ∣ ≥ 2 |A|,|B|\geq2 ∣ A ∣ , ∣ B ∣ ≥ 2 , and
∣ A + B ∣ = ∣ A ∣ + ∣ B ∣ − 1 ≤ p − 2 , (3) |A+B|=|A|+|B|-1\leq p-2, \tag*{(3)} ∣ A + B ∣ = ∣ A ∣ + ∣ B ∣ − 1 ≤ p − 2 , (3)
then A A A and B B B are arithmetic progressions with the same common difference.
We use Savchev and Chen’s theorem on long zero-sum free sequences and its consequence for long minimal zero-sum sequences.
Lemma 2.2 [10 Theorem 8 and Section 5] . Let V V V be a sequence over C p C_p C p .
(i) If V V V is zero-sum free and ∣ V ∣ > p / 2 |V|>p/2 ∣ V ∣ > p /2 , then for some generator g g g of C p C_p C p ,
V = ( a 1 g ) ⋯ ( a ∣ V ∣ g ) , a i ∈ N , ∑ i = 1 ∣ V ∣ a i ≤ p − 1. V=(a_1g)\cdots(a_{|V|}g),\qquad a_i\in\mathbb{N},\qquad\sum_{i=1}^{|V|}a_i\leq p-1. V = ( a 1 g ) ⋯ ( a ∣ V ∣ g ) , a i ∈ N , i = 1 ∑ ∣ V ∣ a i ≤ p − 1. (ii) If V V V is minimal zero-sum and ∣ V ∣ > ( p + 2 ) / 2 |V|>(p+2)/2 ∣ V ∣ > ( p + 2 ) /2 , then V V V has such a representation with
∑ i = 1 ∣ V ∣ a i = p . \sum_{i=1}^{|V|}a_i=p. i = 1 ∑ ∣ V ∣ a i = p .
Lemma 2.3 [10 Section 6] . Let V = ( a 1 g ) ⋯ ( a l g ) V=(a_1g)\cdots(a_lg) V = ( a 1 g ) ⋯ ( a l g ) , where g g g is a generator of C p C_p C p and a 1 , … , a l ∈ N a_1,\ldots,a_l\in\mathbb{N} a 1 , … , a l ∈ N . If N = ∑ i = 1 l a i N=\sum_{i=1}^{l}a_i N = ∑ i = 1 l a i , then v g ( V ) ≥ 2 ∣ V ∣ − N v_g(V)\geq2|V|-N v g ( V ) ≥ 2∣ V ∣ − N .
For a minimal zero-sum sequence U U U over C p C_p C p , we have
∣ { 0 } ∪ Σ ( U ) ∣ ≥ min { p , 2 ∣ U ∣ − 1 } . (4) |\{0\}\cup\Sigma(U)|\geq\min\{p,2|U|-1\}. \tag*{(4)} ∣ { 0 } ∪ Σ ( U ) ∣ ≥ min { p , 2∣ U ∣ − 1 } . (4)
Write U = u 1 ⋯ u k U=u_1\cdots u_k U = u 1 ⋯ u k , set s 0 = 0 s_0=0 s 0 = 0 , and put s i = ∑ l = 1 i u l s_i=\sum_{l=1}^{i}u_l s i = ∑ l = 1 i u l for 1 ≤ i < k 1\leq i<k 1 ≤ i < k . Let P = { s 0 , … , s k − 1 } P=\{s_0,\ldots,s_{k-1}\} P = { s 0 , … , s k − 1 } . For 0 ≤ i < j < k 0\leq i<j<k 0 ≤ i < j < k , the subsequence W = u i + 1 ⋯ u j W=u_{i+1}\cdots u_j W = u i + 1 ⋯ u j is nonempty and proper. We have
s j − s i = σ ( W ) ≠ 0 , s i − s j = σ ( U W − 1 ) , s_j-s_i=\sigma(W)\ne0,\qquad s_i-s_j=\sigma(UW^{-1}), s j − s i = σ ( W ) = 0 , s i − s j = σ ( U W − 1 ) ,
where the first assertion follows from minimality and the second from σ ( U ) = 0 \sigma(U)=0 σ ( U ) = 0 . Thus ∣ P ∣ = k |P|=k ∣ P ∣ = k and P − P ⊆ { 0 } ∪ Σ ( U ) P-P\subseteq\{0\}\cup\Sigma(U) P − P ⊆ { 0 } ∪ Σ ( U ) . Applying Lemma 2.1 to P P P and − P -P − P gives (2.4).
Lemma 2.4. Let z 1 ≤ ⋯ ≤ z n z_1\leq\cdots\leq z_n z 1 ≤ ⋯ ≤ z n be integers with z i + 1 − z i ≤ d z_{i+1}-z_i\leq d z i + 1 − z i ≤ d for 1 ≤ i < n 1\leq i<n 1 ≤ i < n , where d ≥ 1 d\geq1 d ≥ 1 is an integer. For k ∈ [ 0 , n ] k\in[0,n] k ∈ [ 0 , n ] , let Y Y Y be the set of sums of k k k distinct positions. Successive elements of Y Y Y differ by at most d d d . Moreover, if P P P is a nonempty integer interval and Z Z Z is a nonempty finite set of integers whose successive elements differ by at most ∣ P ∣ |P| ∣ P ∣ , then P + Z P+Z P + Z is an integer interval.
Proof. For k = 0 k=0 k = 0 or k = n k=n k = n , the set Y Y Y is a singleton. For 1 ≤ k < n 1\leq k<n 1 ≤ k < n , start with the positions 1 , … , k 1,\ldots,k 1 , … , k . Move the selected positions from right to left to their destinations n − k + 1 , … , n n-k+1,\ldots,n n − k + 1 , … , n , advancing one position at a time. This gives a nondecreasing chain of sums from min Y \min Y min Y to max Y \max Y max Y with increments at most d d d . Hence each gap in Y Y Y is at most d d d . For the second assertion, consecutive translates P + z P+z P + z for z ∈ Z z\in Z z ∈ Z overlap or are adjacent, so their union P + Z P+Z P + Z is an interval.
We use the following special case of Grynkiewicz’s classification of sequences with a unique zero-sum length.
Lemma 2.5 ([6 Theorem 3.4] ). Let p p p be an odd prime and let T T T be a sequence over C p C_p C p with ∣ T ∣ = p |T|=p ∣ T ∣ = p and h ( T ) ≤ p − 2 h(T)\leq p-2 h ( T ) ≤ p − 2 . If there is a unique r ∈ [ 1 , p ] r\in[1,p] r ∈ [ 1 , p ] with 0 ∈ Σ r ( T ) 0\in\Sigma_r(T) 0 ∈ Σ r ( T ) , then there is a generator g g g of C p C_p C p such that
r = ( p + 1 ) / 2 , T = g p − 2 ( r g ) 2 . r=(p+1)/2,\qquad T=g^{p-2}(rg)^2. r = ( p + 1 ) /2 , T = g p − 2 ( r g ) 2 .
Lemma 2.6. Let A = U V A=UV A = U V be a sequence over G G G with σ ( V ‾ ) = 0 \sigma(\overline{V})=0 σ ( V ) = 0 . Suppose that all nonempty proper subsequences of A A A with sum in p G pG pG have the same sum in G G G . Let j ≥ 1 j\geq1 j ≥ 1 and w , q ∈ G w,q\in G w , q ∈ G with w q j ∣ V wq^j\mid V w q j ∣ V and w ‾ = j q ‾ \overline{w}=\overline{jq} w = j q . Set V 0 = V ( w q j ) − 1 V_0=V(wq^j)^{-1} V 0 = V ( w q j ) − 1 . If
( j q ‾ + ( { 0 } ∪ Σ ( V 0 ‾ ) ) ) ∩ ( Σ ( U ‾ ) ∖ { 0 } ) ≠ ∅ , \left(\overline{jq}+\left(\{0\}\cup\Sigma(\overline{V_0})\right)\right)\cap\left(\Sigma(\overline{U})\setminus\{0\}\right)\ne\varnothing, ( j q + ( { 0 } ∪ Σ ( V 0 ) ) ) ∩ ( Σ ( U ) ∖ { 0 } ) = ∅ , then w = j q w=jq w = j q .
Proof. Choose a nonempty subsequence D ∣ U D\mid U D ∣ U and a subsequence W ∣ V 0 W\mid V_0 W ∣ V 0 , possibly empty, such that σ ( D ‾ ) = j q ‾ + σ ( W ‾ ) ≠ 0 \sigma(\overline{D})=\overline{jq}+\sigma(\overline{W})\ne0 σ ( D ) = j q + σ ( W ) = 0 . Consider
T 1 = D V ( w W ) − 1 , T 2 = D V ( q j W ) − 1 . T_1=DV(wW)^{-1},\qquad T_2=DV(q^jW)^{-1}. T 1 = D V ( w W ) − 1 , T 2 = D V ( q j W ) − 1 .
Both retain D D D and omit terms of V V V , so they are nonempty proper subsequences of A A A . By σ ( V ‾ ) = 0 \sigma(\overline{V})=0 σ ( V ) = 0 ,
σ ( T 1 ‾ ) = σ ( T 2 ‾ ) = σ ( D ‾ ) − j q ‾ − σ ( W ‾ ) = 0. \sigma(\overline{T_1})=\sigma(\overline{T_2})=\sigma(\overline{D})-\overline{jq}-\sigma(\overline{W})=0. σ ( T 1 ) = σ ( T 2 ) = σ ( D ) − j q − σ ( W ) = 0.
The hypothesis on A A A now gives 0 = σ ( T 1 ) − σ ( T 2 ) = j q − w 0=\sigma(T_1)-\sigma(T_2)=jq-w 0 = σ ( T 1 ) − σ ( T 2 ) = j q − w .
Noninjectivity and large multiplicities
Unless otherwise stated, from this section through the proof of Theorem 1.1, S S S denotes a sequence over G × G^\times G × of length 2 p 2p 2 p , where p p p is an odd prime.
If h ( S ) ≥ p h(S)\geq p h ( S ) ≥ p , then some unit a a a occurs at least p p p times in S S S . The p p p -term subsequence a p a^p a p has sum p a ∈ p G ∖ { 0 } pa\in pG\setminus\{0\} p a ∈ pG ∖ { 0 } . Henceforth assume h ( S ) ≤ p − 1 h(S)\leq p-1 h ( S ) ≤ p − 1 .
Gao et al. [3 Lemma 3.4] showed that if a sequence of length 2 p + 1 2p+1 2 p + 1 over G × G^\times G × has no p p p -term subsequence with sum in p G ∖ { 0 } pG\setminus\{0\} pG ∖ { 0 } , then π \pi π is injective on its support. The following proposition classifies the exceptional sequences of length 2 p 2p 2 p for which π \pi π fails to be injective on the support.
Proposition 3.1. If π \pi π is not injective on supp ( S ) \operatorname{supp}(S) supp ( S ) , then S S S is exceptional if and only if it has the form in Theorem 1.1(i).
Proof. Assume that S S S is exceptional. At most p p p terms of S S S have any given image under π \pi π . Indeed, if L ∣ S L\mid S L ∣ S consists of p + 1 p+1 p + 1 terms with the same image, then σ ( L ‾ x − 1 ) = p x ‾ = 0 \sigma(\overline{L}x^{-1})=p\overline{x}=0 σ ( L x − 1 ) = p x = 0 for every term x x x of L L L . Thus σ ( L ‾ ) − x = 0 \sigma(\overline{L})-x=0 σ ( L ) − x = 0 by (2.1), so all terms of L L L are equal, contradicting h ( S ) ≤ p − 1 h(S)\leq p-1 h ( S ) ≤ p − 1 .
Choose distinct terms a , b a,b a , b with a ‾ = b ‾ = r \overline{a}=\overline{b}=r a = b = r and let S 0 = S ( a b ) − 1 S_0=S(ab)^{-1} S 0 = S ( ab ) − 1 . Suppose h ( S 0 ‾ ) ≤ p − 1 h(\overline{S_0})\leq p-1 h ( S 0 ) ≤ p − 1 . List the terms of S 0 ‾ \overline{S_0} S 0 as r 1 , … , r 2 p − 2 r_1,\ldots,r_{2p-2} r 1 , … , r 2 p − 2 with equal values consecutive, and set P i = { r i , r i + p − 1 } P_i=\{r_i,r_{i+p-1}\} P i = { r i , r i + p − 1 } for 1 ≤ i ≤ p − 1 1\leq i\leq p-1 1 ≤ i ≤ p − 1 . Each P i P_i P i has two elements, since r i = r i + p − 1 r_i=r_{i+p-1} r i = r i + p − 1 would force p p p consecutive terms to be equal. By Lemma 2.1,
p ≤ ∣ P 1 + ⋯ + P p − 1 ∣ ≤ ∣ Σ p − 1 ( S 0 ‾ ) ∣ ≤ p . p\leq|P_1+\cdots+P_{p-1}|\leq|\Sigma_{p-1}(\overline{S_0})|\leq p. p ≤ ∣ P 1 + ⋯ + P p − 1 ∣ ≤ ∣ Σ p − 1 ( S 0 ) ∣ ≤ p .
Thus Σ p − 1 ( S 0 ‾ ) = C p \Sigma_{p-1}(\overline{S_0})=C_p Σ p − 1 ( S 0 ) = C p . Choose W ∣ S 0 W\mid S_0 W ∣ S 0 with ∣ W ∣ = p − 1 |W|=p-1 ∣ W ∣ = p − 1 and σ ( W ‾ ) = − r \sigma(\overline{W})=-r σ ( W ) = − r . By (2.1), σ ( a W ) = σ ( b W ) = 0 \sigma(aW)=\sigma(bW)=0 σ ( aW ) = σ ( bW ) = 0 , and hence a = b a=b a = b , a contradiction.
It follows that S 0 S_0 S 0 has a subsequence A A A of length p p p whose terms have a common image t ≠ r t\ne r t = r , since at most p p p terms of S S S have image r r r and two were deleted. The sum of A A A is zero, and h ( S ) ≤ p − 1 h(S) \le p-1 h ( S ) ≤ p − 1 ensures that A A A contains two distinct terms. Applying the preceding argument to these terms gives a second subsequence B B B of length p p p and sum zero, whose terms have a common image different from t t t . Thus S = A B S=AB S = A B , and the terms of B B B have image r r r since B B B contains a a a and b b b .
Conversely, if T ∣ A B T \mid AB T ∣ A B uses j j j terms of A A A and p − j p-j p − j terms of B B B , then
σ ( T ‾ ) = j t + ( p − j ) r = j ( t − r ) . \sigma(\overline{T})=jt+(p-j)r=j(t-r). σ ( T ) = j t + ( p − j ) r = j ( t − r ) .
As 0 ≤ j ≤ p 0 \le j \le p 0 ≤ j ≤ p and t ≠ r t \ne r t = r , this vanishes only for j = 0 j=0 j = 0 or j = p j=p j = p . In these cases T T T is B B B or A A A , respectively, and σ ( T ‾ ) = 0 \sigma(\overline{T})=0 σ ( T ) = 0 . □
It remains to classify exceptional sequences satisfying
π is injective on supp ( S ) . (5) \pi\text{ is injective on }\operatorname{supp}(S). \tag*{(5)} π is injective on supp ( S ) . (5)
Choose a ∈ supp ( S ) a \in\operatorname{supp}(S) a ∈ supp ( S ) with v a ( S ) = h ( S ) v_a(S)=h(S) v a ( S ) = h ( S ) , set m = p − h ( S ) m=p-h(S) m = p − h ( S ) , and let R = S a − ( p − m ) = x 1 ⋯ x p + m R=Sa^{-(p-m)}=x_1\cdots x_{p+m} R = S a − ( p − m ) = x 1 ⋯ x p + m . Thus R R R is obtained by deleting all occurrences of a a a from S S S . Set
Q = ∏ j = 1 p + m ( x j − a ) , c = − p a . Q=\prod_{j=1}^{p+m}(x_j-a), \qquad c=-pa. Q = j = 1 ∏ p + m ( x j − a ) , c = − p a .
Since supp ( Q ) = supp ( R ) − { a } \operatorname{supp}(Q)=\operatorname{supp}(R)-\{a\} supp ( Q ) = supp ( R ) − { a } , (3.1) gives injectivity on supp ( Q ) \operatorname{supp}(Q) supp ( Q ) and v 0 ( Q ‾ ) = 0 v_0(\overline{Q})=0 v 0 ( Q ) = 0 . In particular, h ( Q ‾ ) = h ( Q ) ≤ p − m h(\overline{Q})=h(Q)\le p-m h ( Q ) = h ( Q ) ≤ p − m . For I ⊆ [ 1 , p + m ] I\subseteq[1,p+m] I ⊆ [ 1 , p + m ] with m ≤ ∣ I ∣ ≤ p m\le|I|\le p m ≤ ∣ I ∣ ≤ p , let
B = ∏ i ∈ I ( x i − a ) , T = a p − ∣ I ∣ ∏ i ∈ I x i . B=\prod_{i\in I}(x_i-a), \qquad T=a^{p-|I|}\prod_{i\in I}x_i. B = i ∈ I ∏ ( x i − a ) , T = a p − ∣ I ∣ i ∈ I ∏ x i .
Since p − ∣ I ∣ ≤ p − m p-|I|\le p-m p − ∣ I ∣ ≤ p − m , we have T ∣ S T\mid S T ∣ S , ∣ T ∣ = p |T|=p ∣ T ∣ = p , and σ ( T ) = p a + σ ( B ) \sigma(T)=pa+\sigma(B) σ ( T ) = p a + σ ( B ) . If S S S is exceptional, then (2.1) gives
B ∣ Q , m ≤ ∣ B ∣ ≤ p , σ ( B ) ∈ p G ⟹ σ ( B ) = c . (6) B\mid Q,\quad m\le|B|\le p,\quad\sigma(B)\in pG \quad\Longrightarrow\quad\sigma(B)=c. \tag*{(6)} B ∣ Q , m ≤ ∣ B ∣ ≤ p , σ ( B ) ∈ pG ⟹ σ ( B ) = c . (6)
Maximum multiplicity p − 1 p-1 p − 1
We first exclude exceptional sequences with exactly one value of multiplicity $p-1 and then characterize those with two such values.
Proposition 3.2. Under the injectivity assumption (3.1), if exactly one value has multiplicity p − 1 p-1 p − 1 in S S S , then S S S has a subsequence T T T with ∣ T ∣ = p |T|=p ∣ T ∣ = p and σ ( T ) ∈ p G ∖ { 0 } \sigma(T)\in pG\setminus\{0\} σ ( T ) ∈ pG ∖ { 0 } .
Proof. Assume that S S S is exceptional. Then ∣ Q ∣ = p + 1 |Q|=p+1 ∣ Q ∣ = p + 1 and h ( Q ) ≤ p − 2 h(Q)\le p-2 h ( Q ) ≤ p − 2 . Define
A = { Q , σ ( Q ‾ ) = 0 , Q z , z = 2 c − σ ( Q ‾ ) , σ ( Q ‾ ) ≠ 0. A=
\begin{cases}
Q, & \sigma(\overline{Q})=0,\\
Qz, & z=2c-\sigma(\overline{Q}),\quad\sigma(\overline{Q})\ne0.
\end{cases} A = { Q , Q z , σ ( Q ) = 0 , z = 2 c − σ ( Q ) , σ ( Q ) = 0.
In the second case, z ‾ = − σ ( Q ‾ ) ≠ 0 \overline{z}=-\sigma(\overline{Q})\ne0 z = − σ ( Q ) = 0 . Thus in both cases σ ( A ‾ ) = 0 \sigma(\overline{A})=0 σ ( A ) = 0 and v 0 ( A ‾ ) = 0 v_0(\overline{A})=0 v 0 ( A ) = 0 . We claim that
B ∣ A , 1 ≤ ∣ B ∣ < ∣ A ∣ , σ ( B ) ∈ p G ⟹ σ ( B ) = c . (7) B\mid A,\quad1\le|B|<|A|,\quad\sigma(B)\in pG \quad\Longrightarrow\quad\sigma(B)=c. \tag*{(7)} B ∣ A , 1 ≤ ∣ B ∣ < ∣ A ∣ , σ ( B ) ∈ pG ⟹ σ ( B ) = c . (7)
If A = Q A=Q A = Q , the claim is (3.2) with m = 1 m=1 m = 1 .
Suppose A = Q z A=Qz A = Q z , and let B B B satisfy the conditions of (3.3). Then σ ( A B − 1 ) = 2 c − σ ( B ) ∈ p G \sigma(AB^{-1})=2c-\sigma(B)\in pG σ ( A B − 1 ) = 2 c − σ ( B ) ∈ pG . Neither B B B nor A B − 1 AB^{-1} A B − 1 can equal Q Q Q , since σ ( Q ) ∉ p G \sigma(Q)\notin pG σ ( Q ) ∈ / pG . Exactly one of the two subsequences omits the position of z z z . By (3.2) that subsequence has sum c c c . Since σ ( B ) + σ ( A B − 1 ) = 2 c \sigma(B)+\sigma(AB^{-1})=2c σ ( B ) + σ ( A B − 1 ) = 2 c , both sums are c c c .
We next show that π \pi π is injective on supp ( A ) \operatorname{supp}(A) supp ( A ) . It suffices to check the case with an added term. If x , y x,y x , y are two terms of A A A with x ‾ = y ‾ \overline{x}=\overline{y} x = y , put A ′ = A ( x y ) − 1 A'=A(xy)^{-1} A ′ = A ( x y ) − 1 . Then ∣ A ′ ∣ = p |A'|=p ∣ A ′ ∣ = p , and applying Lemma 2.1 to { 0 , v ‾ } \{0,\overline{v}\} { 0 , v } for the positions v v v of A ′ A' A ′ gives
{ 0 } ∪ Σ ( A ′ ‾ ) = C p . \{0\}\cup\Sigma(\overline{A'})=C_p. { 0 } ∪ Σ ( A ′ ) = C p .
Choose W ∣ A ′ W\mid A' W ∣ A ′ with σ ( W ‾ ) = − x ‾ \sigma(\overline{W})=-\overline{x} σ ( W ) = − x . We have
1 ≤ ∣ x W ∣ = ∣ y W ∣ ≤ p + 1 < ∣ A ∣ , σ ( x W ‾ ) = σ ( y W ‾ ) = 0. 1\le|xW|=|yW|\le p+1<|A|,\qquad\sigma(\overline{xW})=\sigma(\overline{yW})=0. 1 ≤ ∣ x W ∣ = ∣ y W ∣ ≤ p + 1 < ∣ A ∣ , σ ( x W ) = σ ( y W ) = 0.
By (3.3), σ ( x W ‾ ) = σ ( y W ‾ ) = c \sigma(\overline{xW})=\sigma(\overline{yW})=c σ ( x W ) = σ ( y W ) = c , so x = y x=y x = y . Take a nonempty subsequence U ‾ ∣ A \overline{U}\mid A U ∣ A of minimum length subject to σ ( U ‾ ) = 0 \sigma(\overline{U})=0 σ ( U ) = 0 . Since D ( C p ) = p < ∣ A ∣ D(C_p)=p<|A| D ( C p ) = p < ∣ A ∣ , we have ∣ U ‾ ∣ ≤ p |\overline{U}|\le p ∣ U ∣ ≤ p . Let V = A U ‾ − 1 V=A\overline{U}^{-1} V = A U − 1 , r = ∣ U ‾ ∣ r=|\overline{U}| r = ∣ U ∣ , and ε = ∣ A ∣ − p \varepsilon=|A|-p ε = ∣ A ∣ − p . By the choice of U U U , U ‾ \overline{U} U is minimal zero-sum. Also, V V V is a nonempty proper subsequence of A A A with σ ( V ‾ ) = σ ( A ‾ ) − σ ( U ‾ ) = 0 \sigma(\overline{V})=\sigma(\overline{A})-\sigma(\overline{U})=0 σ ( V ) = σ ( A ) − σ ( U ) = 0 . By (7) , σ ( U ‾ ) = σ ( V ‾ ) = c \sigma(\overline{U})=\sigma(\overline{V})=c σ ( U ) = σ ( V ) = c .
Suppose that V ‾ \overline{V} V is not minimal zero-sum. Then there is a subsequence W ∣ V W\mid V W ∣ V with 1 ≤ ∣ W ∣ < ∣ V ∣ 1\le|W|<|V| 1 ≤ ∣ W ∣ < ∣ V ∣ and σ ( W ‾ ) = 0 \sigma(\overline{W})=0 σ ( W ) = 0 . Since σ ( V ‾ ) = 0 \sigma(\overline{V})=0 σ ( V ) = 0 , we also have σ ( V ‾ W ‾ − 1 ) = 0 \sigma(\overline{V}\overline{W}^{-1})=0 σ ( V W − 1 ) = 0 . Apply (7) to W W W and V ‾ W ‾ − 1 \overline{V}\overline{W}^{-1} V W − 1 to obtain
c = σ ( V ‾ ) = σ ( W ‾ ) + σ ( V ‾ W ‾ − 1 ) = 2 c , c=\sigma(\overline{V})=\sigma(\overline{W})+\sigma(\overline{V}\overline{W}^{-1})=2c, c = σ ( V ) = σ ( W ) + σ ( V W − 1 ) = 2 c ,
contrary to c ≠ 0 c\ne0 c = 0 . Hence V ‾ \overline{V} V is minimal zero-sum.
Since every term of A ‾ \overline{A} A is nonzero and U U U has minimum length, we have 2 ≤ r ≤ ∣ V ∣ 2\le r\le|V| 2 ≤ r ≤ ∣ V ∣ . Thus 2 r ≤ ∣ A ∣ ≤ p + 2 2r\le|A|\le p+2 2 r ≤ ∣ A ∣ ≤ p + 2 . As p p p is odd, it follows that r ≤ ( p + 1 ) / 2 r\le(p+1)/2 r ≤ ( p + 1 ) /2 .
We distinguish the cases according to whether ∣ V ∣ > ( p + 2 ) / 2 |V|>(p+2)/2 ∣ V ∣ > ( p + 2 ) /2 .
Case 1. ∣ V ∣ ≤ ( p + 2 ) / 2 |V|\le(p+2)/2 ∣ V ∣ ≤ ( p + 2 ) /2 . Since ∣ V ∣ = p + ε − r |V|=p+\varepsilon-r ∣ V ∣ = p + ε − r and r ≤ ( p + 1 ) / 2 r\le(p+1)/2 r ≤ ( p + 1 ) /2 , we have ε = 1 \varepsilon=1 ε = 1 and r = ( p + 1 ) / 2 r=(p+1)/2 r = ( p + 1 ) /2 . Thus A = Q A=Q A = Q . Each nonempty proper zero-sum subsequence of Q ‾ \overline{Q} Q and its complement have length at least r r r , so both have length r r r . Delete any term y y y of Q ‾ \overline{Q} Q . Since ∣ Q ‾ y − 1 ∣ = p = D ( C p ) |\overline{Q}y^{-1}|=p=D(C_p) ∣ Q y − 1 ∣ = p = D ( C p ) , the sequence Q ‾ y − 1 \overline{Q}y^{-1} Q y − 1 has a nonempty zero-sum subsequence, and r r r is the only possible length. Lemma 2.5 gives Q ‾ y − 1 = g p − 2 ( r g ) 2 \overline{Q}y^{-1}=g^{p-2(rg)^2} Q y − 1 = g p − 2 ( r g ) 2 for some generator g g g . Therefore σ ( Q ‾ y − 1 ) = − g \sigma(\overline{Q}y^{-1})=-g σ ( Q y − 1 ) = − g and y ‾ = g \overline{y}=g y = g . This gives v g ( Q ‾ ) ≥ p − 1 v_g(\overline{Q})\ge p-1 v g ( Q ) ≥ p − 1 , a contradiction.
Case 2. ∣ V ∣ > ( p + 2 ) / 2 |V|>(p+2)/2 ∣ V ∣ > ( p + 2 ) /2 . By Lemma 2.2 (ii), choose a generator g g g of C p C_p C p so that the terms of V ‾ \overline{V} V have the form j g jg j g with j ∈ [ 1 , p − 1 ] j\in[1,p-1] j ∈ [ 1 , p − 1 ] and these integer coefficients sum to p p p . By Lemma 2.3 and injectivity on supp ( A ) \operatorname{supp}(A) supp ( A ) , the term q q q with q ‾ = g \overline{q}=g q = g satisfies v q ( V ‾ ) ≥ 2 ∣ V ∣ − p ≥ 3 v_q(\overline{V})\ge2|V|-p\ge3 v q ( V ) ≥ 2∣ V ∣ − p ≥ 3 , so q ∣ Q q\mid Q q ∣ Q . In particular, a + q ∈ supp ( S ) ⊆ G × a+q\in\operatorname{supp}(S)\subseteq G^\times a + q ∈ supp ( S ) ⊆ G × .
We first prove that a term w ∣ V w\mid V w ∣ V of coefficient j ∈ [ 2 , r − 1 ] j\in[2,r-1] j ∈ [ 2 , r − 1 ] satisfies w = j q w=jq w = j q . Applying Lemma 2.3 to V ‾ w − 1 \overline{V}w^{-1} V w − 1 gives
v q ( V ‾ ) ≥ 2 ( ∣ V ∣ − 1 ) − ( p − j ) = p + 2 ε − 2 r + j − 2 ≥ j + 1. v_q(\overline{V})\ge2(|V|-1)-(p-j)=p+2\varepsilon-2r+j-2\ge j+1. v q ( V ) ≥ 2 ( ∣ V ∣ − 1 ) − ( p − j ) = p + 2 ε − 2 r + j − 2 ≥ j + 1.
Let V 0 = V ( w q j ) − 1 V_0=V(wq^j)^{-1} V 0 = V ( w q j ) − 1 , and set
X = j g + ( { 0 } ∪ Σ ( V 0 ‾ ) ) , Y = { 0 } ∪ Σ ( U ‾ ) . X=jg+\bigl(\{0\}\cup\Sigma(\overline{V_0})\bigr),\qquad Y=\{0\}\cup\Sigma(\overline{U}). X = j g + ( { 0 } ∪ Σ ( V 0 ) ) , Y = { 0 } ∪ Σ ( U ) .
The positive coefficients of V 0 ‾ \overline{V_0} V 0 sum to p − 2 j p-2j p − 2 j , so X ⊆ [ j , p − j ] g X\subseteq[j,p-j]g X ⊆ [ j , p − j ] g and 0 ∉ X 0\notin X 0 ∈ / X . The set { 0 } ∪ Σ ( V 0 ‾ ) \{0\}\cup\Sigma(\overline{V_0}) { 0 } ∪ Σ ( V 0 ) is the sum of the sets { 0 , v ‾ } \{0,\overline{v}\} { 0 , v } , one for each term v v v of V 0 V_0 V 0 . Each has two elements. By Lemma 2.1 , ∣ X ∣ ≥ ∣ V 0 ∣ + 1 = p + ε − r − j |X|\ge|V_0|+1=p+\varepsilon-r-j ∣ X ∣ ≥ ∣ V 0 ∣ + 1 = p + ε − r − j . The same bound holds for empty V 0 V_0 V 0 , when X = { j g } X=\{jg\} X = { j g } . Since 2 r − 1 ≤ p 2r-1\le p 2 r − 1 ≤ p , (4) gives ∣ Y ∣ ≥ 2 r − 1 |Y|\ge2r-1 ∣ Y ∣ ≥ 2 r − 1 . Hence
∣ X ∣ + ∣ Y ∣ − 1 ≥ p + ε + r − j − 2 ≥ p . |X|+|Y|-1\ge p+\varepsilon+r-j-2\ge p. ∣ X ∣ + ∣ Y ∣ − 1 ≥ p + ε + r − j − 2 ≥ p .
Applying Lemma 2.1 to X X X and − Y -Y − Y gives X − Y = C p X-Y=C_p X − Y = C p . Thus 0 ∈ X − Y 0\in X-Y 0 ∈ X − Y , so X ∩ Y ≠ ∅ X\cap Y\ne\varnothing X ∩ Y = ∅ . Since 0 ∉ X 0\notin X 0 ∈ / X , (7) and Lemma 2.6 give w = j q w=jq w = j q .
Case 2.1. Every coefficient of V ‾ \overline{V} V is less than r r r . All terms of V V V equal their corresponding multiples of q q q , so p q = σ ( V ‾ ) = c pq=\sigma(\overline{V})=c pq = σ ( V ) = c , contradicting that a + q a+q a + q is a unit.
Case 2.2. Some coefficient of V ‾ \overline{V} V is at least r r r . A term w w w of coefficient j ≥ r j\ge r j ≥ r satisfies
r − 1 ≤ j − 1 ≤ p − ∣ V ∣ = r − ε . r-1\le j-1\le p-|V|=r-\varepsilon. r − 1 ≤ j − 1 ≤ p − ∣ V ∣ = r − ε .
Thus ε = 1 \varepsilon=1 ε = 1 , j = r j=r j = r , and V = q p − r w V=q^{p-r}w V = q p − r w . Since ∣ V ∣ > ( p + 2 ) / 2 |V|>(p+2)/2 ∣ V ∣ > ( p + 2 ) /2 , we have r ≤ ( p − 1 ) / 2 r\le(p-1)/2 r ≤ ( p − 1 ) /2 . For V 0 = q p − 2 r V_0=q^{p-2r} V 0 = q p − 2 r , the translated sumset in Lemma 2.6 is [ r , p − r ] g [r,p-r]g [ r , p − r ] g . If it met { 0 } ∪ Σ ( U ‾ ) \{0\}\cup\Sigma(\overline{U}) { 0 } ∪ Σ ( U ) , (7) and the lemma would give w = r q w=rq w = r q and hence p q = σ ( V ‾ ) = c pq=\sigma(\overline{V})=c pq = σ ( V ) = c , contrary to a + q a+q a + q being a unit. Thus (4) gives
{ 0 } ∪ Σ ( U ‾ ) = [ − ( r − 1 ) , r − 1 ] g . \{0\}\cup\Sigma(\overline{U})=[-(r-1),r-1]g. { 0 } ∪ Σ ( U ) = [ − ( r − 1 ) , r − 1 ] g .
Each term of U ‾ \overline{U} U has the form j g jg j g for a unique j ∈ [ − ( r − 1 ) , r − 1 ] ∖ { 0 } j\in[-(r-1),r-1]\setminus\{0\} j ∈ [ − ( r − 1 ) , r − 1 ] ∖ { 0 } . A term u ∣ U u\mid U u ∣ U with u ‾ = − j g \overline{u}=-jg u = − j g and 1 ≤ j ≤ r − 2 1\le j\le r-2 1 ≤ j ≤ r − 2 would give u q j ∣ A uq^j\mid A u q j ∣ A with σ ( u ‾ q j ) = 0 \sigma(\overline{u}q^j)=0 σ ( u q j ) = 0 and ∣ u ‾ q j ∣ < r |\overline{u}q^j|<r ∣ u q j ∣ < r . Hence the only possible negative coefficient in U U U is − ( r − 1 ) -(r-1) − ( r − 1 ) . If z 0 z_0 z 0 is a term with this coefficient, (3.3) applied to z 0 q r − 1 z_0q^{r-1} z 0 q r − 1 gives z 0 = c − ( r − 1 ) q z_0=c-(r-1)q z 0 = c − ( r − 1 ) q . If u ˉ ∣ U \bar{u}\mid U u ˉ ∣ U has u ˉ = j g \bar{u}=jg u ˉ = j g with 1 ≤ j ≤ r − 1 1\le j\le r-1 1 ≤ j ≤ r − 1 , then U u ˉ − 1 q j ∣ A U\bar{u}^{-1}q^j\mid A U u ˉ − 1 q j ∣ A has image sum zero and length at most 2 r − 2 < ∣ A ∣ 2r-2<|A| 2 r − 2 < ∣ A ∣ . By (7) ,
σ ( U u ˉ − 1 q j ) = σ ( U ) = c , u = j q . \sigma(U\bar{u}^{-1}q^j)=\sigma(U)=c,\qquad u=jq. σ ( U u ˉ − 1 q j ) = σ ( U ) = c , u = j q .
Let l l l be the number of negative coefficients and P P P the sum of the positive coefficients.
Case 2.2.1. l = 0 l=0 l = 0 . Choose a subsequence D ∣ U D\mid U D ∣ U of minimum length whose coefficient sum d d d is at least r r r . Removing any term lowers the sum below r r r . Since the positive coefficients are at most r − 1 r-1 r − 1 ,
r ≤ d ≤ 2 r − 2 < p , d g ∈ [ − ( r − 1 ) , r − 1 ] g . r\le d\le2r-2<p,\qquad dg\in[-(r-1),r-1]g. r ≤ d ≤ 2 r − 2 < p , d g ∈ [ − ( r − 1 ) , r − 1 ] g .
It follows that d ≥ p − r + 1 d\ge p-r+1 d ≥ p − r + 1 . Since 0 < d < p 0<d<p 0 < d < p and σ ( U ˉ ) = 0 \sigma(\bar{U})=0 σ ( U ˉ ) = 0 , the subsequence D D D is proper in U U U . Let T = D q p − d T=Dq^{p-d} T = D q p − d . Since p − d ≤ p − r p-d\le p-r p − d ≤ p − r , we have T ∣ A T\mid A T ∣ A . Moreover, 1 ≤ ∣ T ∣ ≤ 2 r − 2 < ∣ A ∣ 1\le|T|\le2r-2<|A| 1 ≤ ∣ T ∣ ≤ 2 r − 2 < ∣ A ∣ and
σ ( T ) = d q + ( p − d ) q = p q ∈ p G . \sigma(T)=dq+(p-d)q=pq\in pG. σ ( T ) = d q + ( p − d ) q = pq ∈ pG .
By (7) , σ ( T ) = c \sigma(T)=c σ ( T ) = c , so p q = c pq=c pq = c , a contradiction.
Case 2.2.2. l = 1 l=1 l = 1 . Here σ ( U ) = P q + z 0 = c \sigma(U)=Pq+z_0=c σ ( U ) = P q + z 0 = c , and hence
( P − r + 1 ) q = 0 , 0 ≤ P − r + 1 < p 2 . (P-r+1)q=0,\qquad0\le P-r+1<p^2. ( P − r + 1 ) q = 0 , 0 ≤ P − r + 1 < p 2 .
Since q q q has order p 2 p^2 p 2 , we have P = r − 1 P=r-1 P = r − 1 . The r − 1 r-1 r − 1 positive coefficients of U U U are therefore all 1 1 1 . Since ε = 1 \varepsilon=1 ε = 1 , we have U V = Q UV=Q U V = Q and v q ( Q ) ≥ ( r − 1 ) + ( p − r ) = p − 1 v_q(Q)\ge(r-1)+(p-r)=p-1 v q ( Q ) ≥ ( r − 1 ) + ( p − r ) = p − 1 , contrary to h ( Q ) ≤ p − 2 h(Q)\le p-2 h ( Q ) ≤ p − 2 .
Case 2.2.3. l ≥ 2 l\ge2 l ≥ 2 . We have z 0 2 ∣ U z_0^2\mid U z 0 2 ∣ U . For d = p − 2 r + 2 d=p-2r+2 d = p − 2 r + 2 ,
d g = σ ( z 0 2 ) ∈ [ − ( r − 1 ) , r − 1 ] g , 0 < d < p − r + 1. dg=\sigma(z_0^2)\in[-(r-1),r-1]g,\qquad0<d<p-r+1. d g = σ ( z 0 2 ) ∈ [ − ( r − 1 ) , r − 1 ] g , 0 < d < p − r + 1.
Hence d ≤ r − 1 d\le r-1 d ≤ r − 1 . The subsequence U ( z 0 2 ) − 1 q d U(z_0^2)^{-1}q^d U ( z 0 2 ) − 1 q d of A A A has image sum zero and length at most 2 r − 3 < ∣ A ∣ 2r-3<|A| 2 r − 3 < ∣ A ∣ . By (7) , its sum is c = σ ( U ) c=\sigma(U) c = σ ( U ) . Thus 2 z 0 = d q 2z_0=dq 2 z 0 = d q and
2 c = 2 z 0 + 2 ( r − 1 ) q = p q . 2c=2z_0+2(r-1)q=pq. 2 c = 2 z 0 + 2 ( r − 1 ) q = pq .
It follows that ( 2 P + l d ) q = 2 σ ( U ) = p q (2P+ld)q=2\sigma(U)=pq ( 2 P + l d ) q = 2 σ ( U ) = pq , whereas
p < p + ( l − 1 ) ( p − 2 r ) ≤ 2 P + l d ≤ ( 2 r − l ) ( r − 1 ) < p 2 . p<p+(l-1)(p-2r)\le2P+ld\le(2r-l)(r-1)<p^2. p < p + ( l − 1 ) ( p − 2 r ) ≤ 2 P + l d ≤ ( 2 r − l ) ( r − 1 ) < p 2 .
This contradicts the order of q q q . □
Proposition 3.3. Let S = a p − 1 b p − 1 x y S=a^{p-1}b^{p-1}xy S = a p − 1 b p − 1 x y satisfy (5) , with a ≠ b a\ne b a = b and x , y ∉ { a , b } x,y\notin\{a,b\} x , y ∈ / { a , b } . Then S S S is exceptional if and only if there exists i ∈ [ 1 , p − 2 ] i\in[1,p-2] i ∈ [ 1 , p − 2 ] such that
x = − i a − ( p − 1 − i ) b , y = − ( p − 1 − i ) a − i b . x=-ia-(p-1-i)b,\qquad y=-(p-1-i)a-ib. x = − ia − ( p − 1 − i ) b , y = − ( p − 1 − i ) a − ib .
Proof. Since a ˉ ≠ b ˉ \bar{a}\ne\bar{b} a ˉ = b ˉ , there are unique i , j ∈ [ 0 , p − 1 ] i,j\in[0,p-1] i , j ∈ [ 0 , p − 1 ] satisfying
i ( a ˉ − b ˉ ) = b ˉ − x ˉ , j ( a ˉ − b ˉ ) = b ˉ − y ˉ . i(\bar{a}-\bar{b})=\bar{b}-\bar{x},\qquad j(\bar{a}-\bar{b})=\bar{b}-\bar{y}. i ( a ˉ − b ˉ ) = b ˉ − x ˉ , j ( a ˉ − b ˉ ) = b ˉ − y ˉ .
Neither x ˉ \bar{x} x ˉ nor y ˉ \bar{y} y ˉ belongs to { a ˉ , b ˉ } \{\bar{a},\bar{b}\} { a ˉ , b ˉ } , so i , j ∈ [ 1 , p − 2 ] i,j\in[1,p-2] i , j ∈ [ 1 , p − 2 ] . Set I = i + j I=i+j I = i + j . Let
T 1 = a i b p − 1 − i x , T 2 = a j b p − 1 − j y . T_1=a^ib^{p-1-i}x,\qquad T_2=a^jb^{p-1-j}y. T 1 = a i b p − 1 − i x , T 2 = a j b p − 1 − j y .
The equations for i i i and j j j give σ ( T 1 ) , σ ( T 2 ) ∈ p G \sigma(T_1),\sigma(T_2)\in pG σ ( T 1 ) , σ ( T 2 ) ∈ pG .
Necessity. Suppose that S S S is exceptional. Since ∣ T 1 ∣ = ∣ T 2 ∣ = p |T_1|=|T_2|=p ∣ T 1 ∣ = ∣ T 2 ∣ = p , we have σ ( T 1 ) = σ ( T 2 ) = 0 \sigma(T_1)=\sigma(T_2)=0 σ ( T 1 ) = σ ( T 2 ) = 0 by (1) . Hence
x = − i a − ( p − 1 − i ) b , y = − j a − ( p − 1 − j ) b . x=-ia-(p-1-i)b,\qquad y=-ja-(p-1-j)b. x = − ia − ( p − 1 − i ) b , y = − j a − ( p − 1 − j ) b .
For 0 ≤ u ≤ p − 2 0\le u\le p-2 0 ≤ u ≤ p − 2 we have
σ ( a u b p − 2 − u x y ) = ( u − I ) ( a − b ) − p b . \sigma(a^ub^{p-2-u}xy)=(u-I)(a-b)-pb. σ ( a u b p − 2 − u x y ) = ( u − I ) ( a − b ) − p b .
If I ≠ p − 1 I\ne p-1 I = p − 1 , let u u u be the least nonnegative residue of I I I modulo p p p . Since 2 ≤ I ≤ 2 p − 4 2\le I\le2p-4 2 ≤ I ≤ 2 p − 4 , we have u ∈ [ 0 , p − 2 ] u\in[0,p-2] u ∈ [ 0 , p − 2 ] and u − I ∈ { 0 , − p } u-I\in\{0,-p\} u − I ∈ { 0 , − p } . The displayed sum is therefore either − p b -pb − p b or − p a -pa − p a , both in p G ∖ { 0 } pG\setminus\{0\} pG ∖ { 0 } . This contradicts exceptionality, so I = p − 1 I=p-1 I = p − 1 .
Sufficiency. Suppose that the formulas in the proposition hold. By uniqueness of the indices defined above, j = p − 1 − i j=p-1-i j = p − 1 − i and I = p − 1 I=p-1 I = p − 1 . Let T ∣ S T\mid S T ∣ S have length p p p , and let u u u count its terms equal to a a a . We separate the cases by the number of selected positions among those of x x x and $y. Case 1. Neither position is selected. Then 1 ≤ u ≤ p − 1 1 \le u \le p - 1 1 ≤ u ≤ p − 1 and σ ( T ‾ ) = u ( a ‾ − b ‾ ) ≠ 0 \sigma(\overline{T}) = u(\overline{a} - \overline{b}) \ne0 σ ( T ) = u ( a − b ) = 0 .
Case 2. Exactly one position is selected. If σ ( T ‾ ) = 0 \sigma(\overline{T}) = 0 σ ( T ) = 0 , then u = i u = i u = i for the position of x x x and u = j u = j u = j for the position of y y y . The formula for the selected term gives σ ( T ) = 0 \sigma(T) = 0 σ ( T ) = 0 .
Case 3. Both positions are selected. The equality σ ( T ‾ ) = 0 \sigma(\overline{T}) = 0 σ ( T ) = 0 would require u ≡ p − 1 ( m o d p ) u \equiv p - 1 \pmod{p} u ≡ p − 1 ( mod p ) , which is impossible for u ∈ [ 0 , p − 2 ] u \in[0,p - 2] u ∈ [ 0 , p − 2 ] .
Thus (1) holds, so S S S is exceptional. □
Other large multiplicities
For 1 ≤ t < m 1 \le t < m 1 ≤ t < m , choose I ⊆ [ 1 , ∣ R ∣ ] I \subseteq[1,|R|] I ⊆ [ 1 , ∣ R ∣ ] with ∣ I ∣ = t |I| = t ∣ I ∣ = t , and let
B = ∏ i ∈ I ( x i − a ) , R ′ = ∏ i ∈ [ 1 , ∣ R ∣ ] ∖ I x i , S ′ = a p − m + t R ′ . B = \prod_{i \in I}(x_i-a), \qquad R' = \prod_{i \in[1,|R|]\setminus I}x_i, \qquad S' = a^{p-m+t}R'. B = i ∈ I ∏ ( x i − a ) , R ′ = i ∈ [ 1 , ∣ R ∣ ] ∖ I ∏ x i , S ′ = a p − m + t R ′ .
Then B ∣ Q B \mid Q B ∣ Q and
supp ( S ′ ) ⊆ supp ( S ) , v a ( S ′ ) = p − m + t , v x ( S ′ ) ≤ v x ( S ) ≤ p − m for x ≠ a . \operatorname{supp}(S') \subseteq\operatorname{supp}(S), \qquad v_a(S') = p-m+t, \qquad v_x(S') \le v_x(S) \le p-m \quad\text{for } x \ne a. supp ( S ′ ) ⊆ supp ( S ) , v a ( S ′ ) = p − m + t , v x ( S ′ ) ≤ v x ( S ) ≤ p − m for x = a .
Thus S ′ S' S ′ satisfies (5) whenever S S S does, and a a a is the unique term of maximum multiplicity in S ′ S' S ′ .
Lemma 3.4. Suppose that S S S is exceptional and that the sequence S ′ S' S ′ obtained by the above replacement is not exceptional. Then there exists W ∣ Q B − 1 W \mid QB^{-1} W ∣ Q B − 1 such that
m − t ≤ ∣ W ∣ < m , σ ( W ‾ ) = 0 , σ ( W ‾ ) ≠ c . (8) m-t \le|W| < m, \qquad\sigma(\overline{W}) = 0, \qquad\sigma(\overline{W}) \ne c. \tag*{(8)} m − t ≤ ∣ W ∣ < m , σ ( W ) = 0 , σ ( W ) = c . (8)
Proof. Choose a subsequence T ∣ S ′ T \mid S' T ∣ S ′ with ∣ T ∣ = p |T| = p ∣ T ∣ = p and σ ( T ) ∈ p G ∖ { 0 } \sigma(T) \in pG \setminus\{0\} σ ( T ) ∈ pG ∖ { 0 } . Subtracting a a a from each term of T T T different from a a a gives W ∣ Q B − 1 W \mid QB^{-1} W ∣ Q B − 1 , since these terms come from unselected positions in R R R . The multiplicity of a a a in S ′ S' S ′ gives ∣ W ∣ ≥ m − t |W| \ge m-t ∣ W ∣ ≥ m − t . If ∣ W ∣ ≥ m |W| \ge m ∣ W ∣ ≥ m , the terms of T T T different from a a a can be combined in S S S with p − ∣ W ∣ ≤ p − m p-|W| \le p-m p − ∣ W ∣ ≤ p − m copies of a a a to form T T T , a contradiction. Finally, σ ( T ) = p a + σ ( W ‾ ) ∈ p G ∖ { 0 } \sigma(T) = pa+\sigma(\overline{W}) \in pG \setminus\{0\} σ ( T ) = p a + σ ( W ) ∈ pG ∖ { 0 } gives σ ( W ‾ ) = 0 \sigma(\overline{W}) = 0 σ ( W ) = 0 and σ ( W ‾ ) ≠ c \sigma(\overline{W}) \ne c σ ( W ) = c . □
Proposition 3.5. Under (5) , if m ∈ { 2 , 3 } m \in\{2,3\} m ∈ { 2 , 3 } , then S S S has a subsequence T T T with ∣ T ∣ = p |T| = p ∣ T ∣ = p and σ ( T ) ∈ p G ∖ { 0 } \sigma(T) \in pG \setminus\{0\} σ ( T ) ∈ pG ∖ { 0 } .
Proof. Assume that S S S is exceptional. We select m − 1 m-1 m − 1 positions in R R R such that, for the corresponding subsequence B ∣ Q B \mid Q B ∣ Q , Q B − 1 QB^{-1} Q B − 1 has no nonempty zero-sum subsequence of length less than m m m .
Case 1. m = 2 m = 2 m = 2 . Any position suffices because 0 ∉ supp ( Q ‾ ) 0 \notin\operatorname{supp}(\overline{Q}) 0 ∈ / supp ( Q ) .
Case 2. m = 3 m = 3 m = 3 . By (5) , ∣ supp ( S ) ∣ ≤ p − 1 |\operatorname{supp}(S)| \le p-1 ∣ supp ( S ) ∣ ≤ p − 1 , so 2 p ≤ ( p − 1 ) ( p − 3 ) 2p \le(p-1)(p-3) 2 p ≤ ( p − 1 ) ( p − 3 ) and hence p ≥ 7 p \ge7 p ≥ 7 . If Q ‾ \overline{Q} Q had three position-disjoint two-term zero-sum subsequences, denote their corresponding subsequences of Q Q Q by B 1 B_1 B 1 , B 2 B_2 B 2 , B 3 B_3 B 3 . The pairwise products have length 4 4 4 , and the product of all three has length 6 6 6 . By (6) , all four products have sum c c c . Hence
3 c = σ ( B 1 B 2 ) + σ ( B 1 B 3 ) + σ ( B 2 B 3 ) = 2 σ ( B 1 B 2 B 3 ) = 2 c , 3c = \sigma(B_1B_2) + \sigma(B_1B_3) + \sigma(B_2B_3) = 2\sigma(B_1B_2B_3) = 2c, 3 c = σ ( B 1 B 2 ) + σ ( B 1 B 3 ) + σ ( B 2 B 3 ) = 2 σ ( B 1 B 2 B 3 ) = 2 c ,
contrary to c ≠ 0 c \ne0 c = 0 . For each pair of opposite nonzero values in Q ‾ \overline{Q} Q , select the positions in R R R corresponding to all occurrences of a value of smaller multiplicity. The number selected in each pair equals the maximum number of disjoint two-term zero-sum subsequences formed from that pair. Thus at most two positions are selected in total. Deleting the corresponding differences eliminates all two-term zero-sum subsequences of Q ‾ \overline{Q} Q . Select further positions if necessary to make exactly two.
In both cases, the number of selected positions is t = m − 1 t = m-1 t = m − 1 . Thus a a a is the only term of S ′ S' S ′ with multiplicity p − 1 p-1 p − 1 . By Proposition 3.2, S ′ S' S ′ is not exceptional. By Lemma 3.4, there is a nonempty W ∣ Q B − 1 W \mid QB^{-1} W ∣ Q B − 1 of length less than m m m with σ ( W ‾ ) = 0 \sigma(\overline{W}) = 0 σ ( W ) = 0 , contrary to the choice of the positions. □
Lemma 3.6. Suppose S S S is exceptional, m ≥ 4 m \ge4 m ≥ 4 , p ≥ 3 m − 3 p \ge3m-3 p ≥ 3 m − 3 , and σ ( D ) ≠ 0 \sigma(D) \ne0 σ ( D ) = 0 for every D ∣ Q D \mid Q D ∣ Q with 1 ≤ ∣ D ∣ < m 1 \le|D| < m 1 ≤ ∣ D ∣ < m . Let B W ∣ Q BW \mid Q B W ∣ Q with 1 ≤ ∣ B ∣ , ∣ W ∣ < m 1 \le|B|,|W| < m 1 ≤ ∣ B ∣ , ∣ W ∣ < m , ∣ B W ∣ ≥ m |BW| \ge m ∣ B W ∣ ≥ m , and σ ( B ) , σ ( W ) ∈ p G \sigma(B),\sigma(W) \in pG σ ( B ) , σ ( W ) ∈ pG . Then
T ∣ Q ( B W ) − 1 , ∣ T ∣ ≥ 1 , σ ( T ) ∈ p G ⟹ ∣ T ∣ ≥ p − ∣ B ∣ + 1. T \mid Q(BW)^{-1}, \qquad|T| \ge1, \qquad\sigma(T) \in pG \quad\Longrightarrow\quad|T| \ge p-|B|+1. T ∣ Q ( B W ) − 1 , ∣ T ∣ ≥ 1 , σ ( T ) ∈ pG ⟹ ∣ T ∣ ≥ p − ∣ B ∣ + 1.
Proof. Suppose ∣ T ∣ ≤ p − ∣ B ∣ |T| \le p-|B| ∣ T ∣ ≤ p − ∣ B ∣ .
Case 1. ∣ T ∣ < m |T|<m ∣ T ∣ < m . Since m ≤ ∣ B W ∣ < ∣ B W T ∣ ≤ 3 m − 3 ≤ p m\le|BW|<|BWT|\le3m-3\le p m ≤ ∣ B W ∣ < ∣ B W T ∣ ≤ 3 m − 3 ≤ p , (6) gives
σ ( T ) = σ ( B W T ) − σ ( B W ) = 0. \sigma(T)=\sigma(BWT)-\sigma(BW)=0. σ ( T ) = σ ( B W T ) − σ ( B W ) = 0.
This contradicts the nonzero-sum hypothesis for subsequences of length less than m m m .
Case 2. m ≤ ∣ T ∣ ≤ p − ∣ B ∣ m\le|T|\le p-|B| m ≤ ∣ T ∣ ≤ p − ∣ B ∣ . Both T T T and T B TB T B have lengths in [ m , p ] [m,p] [ m , p ] and sums in p G pG pG . By (6) ,
σ ( B ) = σ ( T B ) − σ ( T ) = 0 , \sigma(B)=\sigma(TB)-\sigma(T)=0, σ ( B ) = σ ( T B ) − σ ( T ) = 0 ,
contrary to the hypothesis on B B B . □
Lemma 3.7. Suppose S S S is exceptional and satisfies (5) , with m ≥ 4 m\ge4 m ≥ 4 and p ≥ 3 m − 3 p\ge3m-3 p ≥ 3 m − 3 . Assume that for every B ∣ Q B\mid Q B ∣ Q with t = ∣ B ∣ ∈ [ 1 , m − 1 ] t=|B|\in[1,m-1] t = ∣ B ∣ ∈ [ 1 , m − 1 ] there exists W ∣ Q B − 1 W\mid QB^{-1} W ∣ Q B − 1 satisfying (8) . Then
σ ( D ) ≠ 0 for every D ∣ Q with 1 ≤ ∣ D ∣ < m . \sigma(D)\ne0 \qquad\text{for every }D\mid Q\text{ with }1\le|D|<m. σ ( D ) = 0 for every D ∣ Q with 1 ≤ ∣ D ∣ < m . Moreover, if B ∣ Q B\mid Q B ∣ Q is nonempty and σ ( B ) ∈ p G \sigma(B)\in pG σ ( B ) ∈ pG , then ∣ B ∣ > ⌊ ( m + 1 ) / 2 ⌋ |B|>\lfloor(m+1)/2\rfloor ∣ B ∣ > ⌊( m + 1 ) /2 ⌋ . In particular, if also ∣ B ∣ < m |B|<m ∣ B ∣ < m , then B B B is minimal zero-sum.
Proof. To prove the first assertion, suppose that 1 ≤ ∣ B ∣ < m 1\le|B|<m 1 ≤ ∣ B ∣ < m and σ ( B ) ∈ p G \sigma(B)\in pG σ ( B ) ∈ pG . Choose W W W as in (8) . Since m ≤ ∣ B W ∣ ≤ 2 m − 2 ≤ p m\le|BW|\le2m-2\le p m ≤ ∣ B W ∣ ≤ 2 m − 2 ≤ p , (6) gives σ ( B ) + σ ( W ) = c \sigma(B)+\sigma(W)=c σ ( B ) + σ ( W ) = c , so σ ( B ) ≠ 0 \sigma(B)\ne0 σ ( B ) = 0 .
Now suppose that σ ( B ) ∈ p G \sigma(B)\in pG σ ( B ) ∈ pG and t = ∣ B ∣ ∈ [ 1 , ⌊ ( m + 1 ) / 2 ⌋ ] t=|B|\in[1,\lfloor(m+1)/2\rfloor] t = ∣ B ∣ ∈ [ 1 , ⌊( m + 1 ) /2 ⌋] . Choose W W W as in (8) and let V ‾ 0 = Q ( B W ) − 1 \overline{V}_0=Q(BW)^{-1} V 0 = Q ( B W ) − 1 .
Case 1. V ‾ 0 \overline{V}_0 V 0 is zero-sum free. Take T = V 0 T=V_0 T = V 0 . Then ∣ T ∣ = p + m − t − ∣ W ∣ ≥ p − t + 1 |T|=p+m-t-|W|\ge p-t+1 ∣ T ∣ = p + m − t − ∣ W ∣ ≥ p − t + 1 .
Case 2. V ‾ 0 \overline{V}_0 V 0 has a nonempty zero-sum subsequence. Choose T ‾ ∣ V ‾ 0 \overline{T}\mid\overline{V}_0 T ∣ V 0 with T ‾ \overline{T} T minimal zero-sum. Lemma 3.6 gives ∣ T ∣ ≥ p − t + 1 |T|\ge p-t+1 ∣ T ∣ ≥ p − t + 1 .
In both cases, p > 2 t p>2t p > 2 t gives ∣ T ∣ > ( p + 2 ) / 2 |T|>(p+2)/2 ∣ T ∣ > ( p + 2 ) /2 . By Lemma 2.2, the positive coefficients of T ‾ \overline{T} T relative to a suitable generator sum to at most p p p . Lemma 2.3 gives
h ( T ‾ ) ≥ 2 ∣ T ∣ − p ≥ p − 2 t + 2 > p − m , h(\overline{T})\ge2|T|-p\ge p-2t+2>p-m, h ( T ) ≥ 2∣ T ∣ − p ≥ p − 2 t + 2 > p − m ,
contrary to h ( Q ‾ ) ≤ p − m h(\overline{Q})\le p-m h ( Q ) ≤ p − m . If ∣ B ∣ < m |B|<m ∣ B ∣ < m and B ‾ \overline{B} B were not minimal zero-sum, its two nonempty zero-sum factors would each have length at least ⌊ ( m + 1 ) / 2 ⌋ + 1 \lfloor(m+1)/2\rfloor+1 ⌊( m + 1 ) /2 ⌋ + 1 , which is impossible. □
Proposition 3.8. Under (5) , suppose that m ≥ 4 m\ge4 m ≥ 4 and p ≥ max { 3 m − 3 , 4 m − 11 } p\ge\max\{3m-3,4m-11\} p ≥ max { 3 m − 3 , 4 m − 11 } . Then S S S has a subsequence T T T with ∣ T ∣ = p |T|=p ∣ T ∣ = p and σ ( T ) ∈ p G ∖ { 0 } \sigma(T)\in pG\setminus\{0\} σ ( T ) ∈ pG ∖ { 0 } .
Proof. We use strong induction on m ≥ 4 m\ge4 m ≥ 4 and assume that S S S is exceptional. For any choice of t t t positions in R R R with 1 ≤ t < m 1\le t<m 1 ≤ t < m , let B B B and S ′ S' S ′ be as above. To show that S ′ S' S ′ is not exceptional, we distinguish three cases according to its parameter m − t m-t m − t .
If m − t = 1 m-t=1 m − t = 1 , Proposition 3.2 applies because a a a is the unique term of maximum multiplicity in S ′ S' S ′ .
If m − t ∈ { 2 , 3 } m-t\in\{2,3\} m − t ∈ { 2 , 3 } , Proposition 3.5 applies.
If m − t ≥ 4 m-t\ge4 m − t ≥ 4 , the induction hypothesis applies, since p ≥ max { 3 ( m − t ) − 3 , 4 ( m − t ) − 11 } p\ge\max\{3(m-t)-3,4(m-t)-11\} p ≥ max { 3 ( m − t ) − 3 , 4 ( m − t ) − 11 } .
In all three cases, Lemma 3.4 gives W ∣ Q B − 1 W\mid QB^{-1} W ∣ Q B − 1 satisfying (8) . Thus the hypothesis of Lemma 3.7 holds for every choice of a a a of maximum multiplicity. In particular, every nonempty zero-sum subsequence of Q Q Q of length less than m m m is minimal zero-sum and has length at least three. Also, no nonempty subsequence of Q Q Q of length less than m m m has sum zero in G G G .
Apply (8) with t = 1 t=1 t = 1 to obtain U ∣ Q U\mid Q U ∣ Q with ∣ U ∣ = m − 1 |U|=m-1 ∣ U ∣ = m − 1 and σ ( U ‾ ) = 0 \sigma(\overline{U})=0 σ ( U ) = 0 . Repeat the replacement step with the positions in R R R corresponding to U U U to obtain W ∣ Q U ‾ − 1 W\mid Q\overline{U}^{-1} W ∣ Q U − 1 with σ ( W ‾ ) = 0 \sigma(\overline{W})=0 σ ( W ) = 0 . Let Q = U W V Q=U W V Q = U W V and K = ∣ U W ∣ K=|UW| K = ∣ U W ∣ . Then m ≤ K ≤ 2 m − 2 ≤ p m\le K\le2m-2\le p m ≤ K ≤ 2 m − 2 ≤ p and σ ( U W ) ∈ p G \sigma(UW)\in pG σ ( U W ) ∈ pG , so (6) gives σ ( U W ) = c \sigma(UW)=c σ ( U W ) = c . In particular, U ‾ \overline{U} U and W ‾ \overline{W} W are minimal zero-sum and have length at least three.
By Lemma 3.6, with W W W in the role of B B B , every nonempty zero-sum subsequence of V ‾ \overline{V} V has length at least p − ∣ W ∣ + 1 = ∣ V ∣ p-|W|+1=|V| p − ∣ W ∣ + 1 = ∣ V ∣ . Thus V ‾ \overline{V} V is zero-sum free or itself minimal zero-sum. Moreover,
∣ V ∣ = p + m − K ≥ p − m + 2 > ( p + 2 ) / 2. |V|=p+m-K\ge p-m+2>(p+2)/2. ∣ V ∣ = p + m − K ≥ p − m + 2 > ( p + 2 ) /2.
By Lemma 2.2, choose a generator g g g of C p C_p C p so that the terms of V ‾ \overline{V} V have the form s g sg s g with s ∈ [ 1 , p − 1 ] s \in[1,p-1] s ∈ [ 1 , p − 1 ] and these integer coefficients sum to p − δ p-\delta p − δ for some δ ≥ 0 \delta\ge0 δ ≥ 0 . Thus σ ( V ‾ ) = − δ g \sigma(\overline{V})=-\delta g σ ( V ) = − δ g . Since 2 ∣ V ‾ ∣ > p 2|\overline{V}|>p 2∣ V ∣ > p , Lemma 2.3 gives an occurrence of g g g in V ‾ \overline{V} V . By injectivity on supp ( Q ) \operatorname{supp}(Q) supp ( Q ) there is a unique value q q q in supp ( V ) \operatorname{supp}(V) supp ( V ) with q ‾ = g \overline{q}=g q = g . For v = v q ( V ) v=v_q(V) v = v q ( V ) , the same lemma and K ≤ 2 m − 2 K\le2m-2 K ≤ 2 m − 2 give
v ≥ 2 ∣ V ‾ ∣ − ( p − δ ) = p + 2 m − 2 K + δ ≥ p − K + 2. (9) v \ge2|\overline{V}|-(p-\delta)=p+2m-2K+\delta\ge p-K+2. \tag*{(9)} v ≥ 2∣ V ∣ − ( p − δ ) = p + 2 m − 2 K + δ ≥ p − K + 2. (9)
If at most one coefficient exceeds 1, then v ≥ ∣ V ∣ − 1 ≥ p − m + 1 v\ge|V|-1\ge p-m+1 v ≥ ∣ V ∣ − 1 ≥ p − m + 1 , a contradiction. Write the coefficients as a 1 , … , a ∣ V ∣ a_1,\ldots,a_{|V|} a 1 , … , a ∣ V ∣ . We have
∑ i = 1 ∣ V ∣ ( a i − 1 ) = ( p − δ ) − ∣ V ∣ = K − m − δ . \sum_{i=1}^{|V|}(a_i-1)=(p-\delta)-|V|=K-m-\delta. i = 1 ∑ ∣ V ∣ ( a i − 1 ) = ( p − δ ) − ∣ V ∣ = K − m − δ .
Since at least two summands are positive, each coefficient s > 1 s>1 s > 1 satisfies 2 ≤ s ≤ K − m − δ 2\le s\le K-m-\delta 2 ≤ s ≤ K − m − δ .
Let J = { 0 } ∪ Σ ( U W ‾ ) J=\{0\}\cup\Sigma(\overline{U\!W}) J = { 0 } ∪ Σ ( U W ) . By (4) and Lemma 2.1, ∣ J ∣ ≥ min { p , 2 K − 3 } |J|\ge\min\{p,2K-3\} ∣ J ∣ ≥ min { p , 2 K − 3 } . For each x ∈ J ∖ { 0 } x\in J\setminus\{0\} x ∈ J ∖ { 0 } there is a subsequence D ∣ U W D\mid UW D ∣ U W with σ ( D ‾ ) = x \sigma(\overline{D})=x σ ( D ) = x and 2 ≤ ∣ D ∣ ≤ K − 2 2\le|D|\le K-2 2 ≤ ∣ D ∣ ≤ K − 2 . For a one-term representation, adjoin the other complete zero-sum factor. For a representation of length K − 1 K-1 K − 1 , remove the complete zero-sum factor it contains.
For each coefficient s ≥ 2 s\ge2 s ≥ 2 that occurs in V ‾ \overline{V} V , let w s w_s w s be the unique value in supp ( V ) \operatorname{supp}(V) supp ( V ) with w s ‾ = s g \overline{w_s}=sg w s = s g . Since 2 ≤ s ≤ K − m − δ < p 2\le s\le K-m-\delta<p 2 ≤ s ≤ K − m − δ < p , we have w s ≠ q w_s\ne q w s = q . We claim that
[ m + δ + s − 3 , p − K + δ + 2 ] g ∩ J ≠ ∅ (10) [m+\delta+s-3,p-K+\delta+2]g\cap J\ne\varnothing \tag*{(10)} [ m + δ + s − 3 , p − K + δ + 2 ] g ∩ J = ∅ (10)
implies w s = s q w_s=sq w s = s q . Choose z z z in the indicated interval with z g ∈ J zg\in J z g ∈ J and D ∣ U W D\mid UW D ∣ U W with σ ( D ‾ ) = z g \sigma(\overline{D})=zg σ ( D ) = z g and 2 ≤ ∣ D ∣ ≤ K − 2 2\le|D|\le K-2 2 ≤ ∣ D ∣ ≤ K − 2 . The interval lies in [ 1 , p − 1 ] [1,p-1] [ 1 , p − 1 ] since δ ≤ K − m − 2 \delta\le K-m-2 δ ≤ K − m − 2 . The image of the sum of D V ‾ D\overline{V} D V is ( z − δ ) g (z-\delta)g ( z − δ ) g , so we compare the effect of removing either w s w_s w s and z − δ − s z-\delta-s z − δ − s copies of q q q , or z − δ z-\delta z − δ copies of q q q . Set
T 1 = D V ‾ ( w s q z − δ − s ) − 1 , T 2 = D V ‾ ( q z − δ ) − 1 . T_1=D\overline{V}(w_sq^{z-\delta-s})^{-1},\qquad T_2=D\overline{V}(q^{z-\delta})^{-1}. T 1 = D V ( w s q z − δ − s ) − 1 , T 2 = D V ( q z − δ ) − 1 .
Both exponents are nonnegative and at most p − K + 2 ≤ v p-K+2\le v p − K + 2 ≤ v . The sums of the two removed subsequences both have image ( z − δ ) g (z-\delta)g ( z − δ ) g under π \pi π , so
σ ( T 1 ‾ ) = σ ( T 2 ‾ ) = z g − δ g − ( z − δ ) g = 0. \sigma(\overline{T_1})=\sigma(\overline{T_2})=zg-\delta g-(z-\delta)g=0. σ ( T 1 ) = σ ( T 2 ) = z g − δ g − ( z − δ ) g = 0.
For d = ∣ D ∣ d=|D| d = ∣ D ∣ their lengths are
∣ T 1 ∣ = p + m − K − z + δ + d + s − 1 , |T_1|=p+m-K-z+\delta+d+s-1, ∣ T 1 ∣ = p + m − K − z + δ + d + s − 1 ,
∣ T 2 ∣ = p + m − K − z + δ + d . |T_2|=p+m-K-z+\delta+d. ∣ T 2 ∣ = p + m − K − z + δ + d .
The bounds on z z z and d d d give m ≤ ∣ T 2 ∣ ≤ ∣ T 1 ∣ ≤ p m\le|T_2|\le|T_1|\le p m ≤ ∣ T 2 ∣ ≤ ∣ T 1 ∣ ≤ p . Hence (6) gives σ ( T 1 ) = σ ( T 2 ) = c \sigma(T_1)=\sigma(T_2)=c σ ( T 1 ) = σ ( T 2 ) = c and w s = s q w_s=sq w s = s q .
We give a criterion for obtaining a contradiction from terms satisfying w s = s q w_s=sq w s = s q . Let ρ ∈ { 3 , 4 } \rho\in\{3,4\} ρ ∈ { 3 , 4 } and suppose that p ≥ 2 K − 2 ρ p\ge2K-2\rho p ≥ 2 K − 2 ρ . Since K ≥ 6 > ρ K\ge6>\rho K ≥ 6 > ρ , the interval [ K − ρ , p − K + ρ ] [K-\rho,p-K+\rho] [ K − ρ , p − K + ρ ] is a nonempty subset of [ 1 , p − 1 ] [1,p-1] [ 1 , p − 1 ] . The set [ K − ρ , p − K + ρ ] g [K-\rho,p-K+\rho]g [ K − ρ , p − K + ρ ] g has complement in C p C_p C p of size 2 K − 2 ρ − 1 < ∣ J ∣ 2K-2\rho-1<|J| 2 K − 2 ρ − 1 < ∣ J ∣ , since ∣ J ∣ ≥ min { p , 2 K − 3 } |J|\ge\min\{p,2K-3\} ∣ J ∣ ≥ min { p , 2 K − 3 } . Choose r r r in this interval with r g ∈ J rg\in J r g ∈ J and choose D ∣ U W D\mid UW D ∣ U W with σ ( D ‾ ) = r g \sigma(\overline{D})=rg σ ( D ) = r g and 2 ≤ ∣ D ∣ ≤ K − 2 2\le|D|\le K-2 2 ≤ ∣ D ∣ ≤ K − 2 .
Suppose that E ∣ V E\mid V E ∣ V consists of terms w s w_s w s with s > 1 s>1 s > 1 and w s = s q w_s=sq w s = s q . Let k = ∣ E ∣ k=|E| k = ∣ E ∣ and let n n n be the sum of the coefficients s s s of its terms w s w_s w s . If
n ≤ K − ρ , ρ − 2 ≤ n − k ≤ K − ρ + 2 − m , n\le K-\rho,\qquad\rho-2\le n-k\le K-\rho+2-m, n ≤ K − ρ , ρ − 2 ≤ n − k ≤ K − ρ + 2 − m ,
then D E DE D E and ( U W ) D − 1 E (UW)D^{-1}E ( U W ) D − 1 E have sums with images ( r + n ) g (r+n)g ( r + n ) g and ( n − r ) g (n-r)g ( n − r ) g , respectively. To cancel these images, consider
T 1 = D E q p − r − n , T 2 = ( U W ) D − 1 E q r − n . T_1=DEq^{p-r-n},\qquad T_2=(UW)D^{-1}Eq^{r-n}. T 1 = D E q p − r − n , T 2 = ( U W ) D − 1 E q r − n .
Both are subsequences of Q Q Q . Indeed, n ≤ K − ρ n\le K-\rho n ≤ K − ρ ensures that both exponents are nonnegative. Each is at most p − K + ρ − n ≤ p − K + 2 ≤ v p-K+\rho-n\le p-K+2\le v p − K + ρ − n ≤ p − K + 2 ≤ v , since n ≥ n − k ≥ ρ − 2 n\ge n-k\ge\rho-2 n ≥ n − k ≥ ρ − 2 . Also, E E E contains no term equal to q q q . The lengths satisfy
∣ T 1 ∣ = ∣ D ∣ + p − r − ( n − k ) , |T_1|=|D|+p-r-(n-k), ∣ T 1 ∣ = ∣ D ∣ + p − r − ( n − k ) ,
∣ T 2 ∣ = K − ∣ D ∣ + r − ( n − k ) . (11) |T_2|=K-|D|+r-(n-k). \tag*{(11)} ∣ T 2 ∣ = K − ∣ D ∣ + r − ( n − k ) . (11)
Both lie in [ K − ρ + 2 − ( n − k ) , p + ρ − 2 − ( n − k ) ] ⊆ [ m , p ] [K-\rho+2-(n-k),p+\rho-2-(n-k)] \subseteq[m,p] [ K − ρ + 2 − ( n − k ) , p + ρ − 2 − ( n − k )] ⊆ [ m , p ] . We have σ ( T ‾ 1 ) = σ ( T ‾ 2 ) = 0 \sigma(\overline{T}_1)=\sigma(\overline{T}_2)=0 σ ( T 1 ) = σ ( T 2 ) = 0 , since the coefficients of the terms of E E E sum to n n n and σ ( D ‾ ) = r g \sigma(\overline{D})=rg σ ( D ) = r g . Using σ ( E ) = n q \sigma(E)=nq σ ( E ) = n q and (3.2), we get
2 c = σ ( T 1 ) + σ ( T 2 ) = σ ( U W ) + p q = c + p q . 2c=\sigma(T_1)+\sigma(T_2)=\sigma(UW)+pq=c+pq. 2 c = σ ( T 1 ) + σ ( T 2 ) = σ ( U W ) + pq = c + pq .
Hence p q = c = − p a pq=c=-pa pq = c = − p a , contrary to a + q a+q a + q being a unit.
We now distinguish two cases according to whether p ≥ 2 K − 5 p\geq2K-5 p ≥ 2 K − 5 .
Case 1. p ≥ 2 K − 5 p\geq2K-5 p ≥ 2 K − 5 . Take ρ = 3 \rho=3 ρ = 3 , so p ≥ 2 K − 2 ρ p\geq2K-2\rho p ≥ 2 K − 2 ρ . For every coefficient s > 1 s>1 s > 1 , the interval in (3.6) is nonempty and its complement has size K + m + s − 6 ≤ 2 K − 6 < ∣ J ∣ K+m+s-6\leq2K-6<|J| K + m + s − 6 ≤ 2 K − 6 < ∣ J ∣ . Thus w s = s q w_s=sq w s = s q . Take E = w s E=w_s E = w s for any such coefficient. Then n = s ≤ K − m − δ ≤ K − 3 n=s\leq K-m-\delta\leq K-3 n = s ≤ K − m − δ ≤ K − 3 and 1 ≤ n − k = s − 1 ≤ K − m − 1 1\leq n-k=s-1\leq K-m-1 1 ≤ n − k = s − 1 ≤ K − m − 1 , so the criterion gives a contradiction.
Case 2. p < 2 K − 5 p<2K-5 p < 2 K − 5 . The bounds p ≥ 4 m − 11 p\geq4m-11 p ≥ 4 m − 11 and K ≤ 2 m − 2 K\leq2m-2 K ≤ 2 m − 2 , together with the parity of p p p , give p = 2 K − 7 = 4 m − 11 p=2K-7=4m-11 p = 2 K − 7 = 4 m − 11 and K = 2 m − 2 K=2m-2 K = 2 m − 2 . Since p ≥ 3 m − 3 p\geq3m-3 p ≥ 3 m − 3 , we have m ≥ 8 m\geq8 m ≥ 8 . Take ρ = 4 \rho=4 ρ = 4 , so p ≥ 2 K − 2 ρ p\geq2K-2\rho p ≥ 2 K − 2 ρ . Here J = C p J=C_p J = C p . For each occurring coefficient s ∈ [ 2 , m − 4 ] s\in[2,m-4] s ∈ [ 2 , m − 4 ] , the interval in (3.6) has m − s − 3 ≥ 1 m-s-3\geq1 m − s − 3 ≥ 1 points, so w s = s q w_s=sq w s = s q .
Case 2.1. At least one coefficient lies in [ 3 , m − 4 ] [3,m-4] [ 3 , m − 4 ] . Take E = w s E=w_s E = w s for such a coefficient s s s . Then n = s ≤ K − 4 n=s\leq K-4 n = s ≤ K − 4 and 2 ≤ n − k = s − 1 ≤ K − m − 2 2\leq n-k=s-1\leq K-m-2 2 ≤ n − k = s − 1 ≤ K − m − 2 . The criterion gives a contradiction.
Case 2.2. No coefficient lies in [ 3 , m − 4 ] [3,m-4] [ 3 , m − 4 ] and at least two equal 2 2 2 . Take E = w 2 E=w_2 E = w 2 . Then n = 4 ≤ K − 4 n=4\leq K-4 n = 4 ≤ K − 4 and n − k = 2 ≤ K − m − 2 n-k=2\leq K-m-2 n − k = 2 ≤ K − m − 2 . The criterion gives a contradiction.
Case 2.3. No coefficient lies in [ 3 , m − 4 ] [3,m-4] [ 3 , m − 4 ] and at most one equals 2 2 2 . All other coefficients greater than 1 1 1 are at least m − 3 m-3 m − 3 . At most one is that large, since 2 ( m − 4 ) > m − 2 ≥ K − m − δ 2(m-4)>m-2\geq K-m-\delta 2 ( m − 4 ) > m − 2 ≥ K − m − δ . Thus exactly two coefficients exceed 1 1 1 , one of them being 2 2 2 . Now v = ∣ V ∣ − 2 = p − m v=|V|-2=p-m v = ∣ V ∣ − 2 = p − m . Since q v ∣ Q q^v\mid Q q v ∣ Q , the term b = a + q b=a+q b = a + q occurs at least v = p − m v=p-m v = p − m times in S S S and thus has maximum multiplicity. The two differences a − b a-b a − b and a + w 2 − b a+w_2-b a + w 2 − b satisfy
a − b ‾ = − g , a + w 2 − b ‾ = g . \overline{a-b}=-g,\qquad\overline{a+w_2-b}=g. a − b = − g , a + w 2 − b = g .
Hence a a a and a + w 2 a+w_2 a + w 2 are both different from b b b . The two differences therefore occur in the sequence defined using b b b in place of a a a . Their sum is w 2 − 2 q = 0 w_2-2q=0 w 2 − 2 q = 0 in G G G . This contradicts Lemma 3.7 applied with b b b as the term of maximum multiplicity. □ \square □
Block interpolation and multiplicity bounds
Throughout this section, we assume that π \pi π is injective on supp ( S ) \operatorname{supp}(S) supp ( S ) , as in (3.1).
Set h = h ( S ) = p − m h=h(S)=p-m h = h ( S ) = p − m and define
m 0 = 1 + min { ⌊ p 3 ⌋ + 1 , ⌊ p + 11 4 ⌋ } . m_0=1+\min\left\{\left\lfloor\frac{p}{3}\right\rfloor+1,\left\lfloor\frac{p+11}{4}\right\rfloor\right\}. m 0 = 1 + min { ⌊ 3 p ⌋ + 1 , ⌊ 4 p + 11 ⌋ } .
For p ≥ 23 p\geq23 p ≥ 23 , the condition m ≥ m 0 m\geq m_0 m ≥ m 0 is equivalent to m > ( p + 11 ) / 4 m>(p+11)/4 m > ( p + 11 ) /4 . For 1 ≤ j ≤ h 1\leq j\leq h 1 ≤ j ≤ h , define the j j j th layer by
L j = { x ∈ supp ( S ) : v x ( S ) ≥ j } , s j = ∣ L j ∣ . L_j=\{x\in\operatorname{supp}(S):v_x(S)\geq j\},\qquad s_j=|L_j|. L j = { x ∈ supp ( S ) : v x ( S ) ≥ j } , s j = ∣ L j ∣.
Each value contributes one term to each layer it belongs to. In particular, ∑ j = 1 h s j = 2 p \sum_{j=1}^{h}s_j=2p ∑ j = 1 h s j = 2 p . Set
f ( s ) = ⌊ s 2 4 ⌋ , b S = ∑ j = 1 h f ( s j ) , e = 2 p − 2 − b S . f(s)=\left\lfloor\frac{s^2}{4}\right\rfloor,\qquad b_S=\sum_{j=1}^{h}f(s_j),\qquad e=2p-2-b_S. f ( s ) = ⌊ 4 s 2 ⌋ , b S = j = 1 ∑ h f ( s j ) , e = 2 p − 2 − b S .
For a set U U U , write Σ k ( U ) \Sigma_k(U) Σ k ( U ) for the sums of k k k distinct elements, with Σ 0 ( U ) = { 0 } \Sigma_0(U)=\{0\} Σ 0 ( U ) = { 0 } . A central selection from layer L j L_j L j takes k j ∈ { ⌊ s j / 2 ⌋ , ⌈ s j / 2 ⌉ } k_j\in\{\lfloor s_j/2\rfloor,\lceil s_j/2\rceil\} k j ∈ {⌊ s j /2 ⌋ , ⌈ s j /2 ⌉} terms. The number of odd s j s_j s j is even. Rounding equally often in either direction on the odd layers gives
∑ j = 1 h k j = 1 2 ∑ j = 1 h s j = p . \sum_{j=1}^{h}k_j=\frac{1}{2}\sum_{j=1}^{h}s_j=p. j = 1 ∑ h k j = 2 1 j = 1 ∑ h s j = p .
Specified odd layers may be paired and rounded in opposite directions in advance.
Lemma 4.1. Let L 1 , … , L q ⊆ G L_1,\ldots,L_q \subseteq G L 1 , … , L q ⊆ G be sets on each of which π \pi π is injective. For each j ∈ [ 1 , q ] j \in[1,q] j ∈ [ 1 , q ] , let ℓ j \ell_j ℓ j be an integer with 0 ≤ ℓ j ≤ ∣ L j ∣ 0 \le\ell_j \le|L_j| 0 ≤ ℓ j ≤ ∣ L j ∣ . Set
D = ∑ j = 1 q ℓ j ( ∣ L j ∣ − ℓ j ) , Y = ∑ j = 1 q Σ ℓ j ( L j ) . D=\sum_{j=1}^{q}\ell_j(|L_j|-\ell_j),\qquad Y=\sum_{j=1}^{q}\Sigma_{\ell_j}(L_j). D = j = 1 ∑ q ℓ j ( ∣ L j ∣ − ℓ j ) , Y = j = 1 ∑ q Σ ℓ j ( L j ) . Then ∣ π ( Y ) ∣ ≥ min { p , D + 1 } |\pi(Y)| \ge\min\{p,D+1\} ∣ π ( Y ) ∣ ≥ min { p , D + 1 } . If Y ∩ p G ⊆ { 0 } Y \cap pG \subseteq\{0\} Y ∩ pG ⊆ { 0 } , then D ≤ 2 p − 2 D \le2p-2 D ≤ 2 p − 2 .
Proof. We give the same interpolation argument over Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z and G = Z / p 2 Z G=\mathbb{Z}/p^2\mathbb{Z} G = Z / p 2 Z . In this proof, ⋅ \cdot ⋅ denotes ring multiplication and ∏ \prod ∏ denotes an indexed product in the chosen coefficient ring or in the polynomial ring over it.
For each j j j , set s j = ∣ L j ∣ s_j=|L_j| s j = ∣ L j ∣ and introduce variables X j , 1 , … , X j , ℓ j X_{j,1},\ldots,X_{j,\ell_j} X j , 1 , … , X j , ℓ j , one for each position to be filled from L j L_j L j . A block with ℓ j = 0 \ell_j=0 ℓ j = 0 has no variables. Integers occurring as polynomial coefficients are interpreted as residue classes in the chosen ring. Since π \pi π is injective on L j L_j L j , we have ∣ π ( L j ) ∣ = s j ≤ p |\pi(L_j)|=s_j \le p ∣ π ( L j ) ∣ = s j ≤ p .
Fix an integer d ∈ [ 0 , D ] d \in[0,D] d ∈ [ 0 , D ] and a monic polynomial Q ( T ) Q(T) Q ( T ) of degree d d d over the chosen ring. Substituting ∑ j = 1 q ∑ i = 1 ℓ j X j , i \sum_{j=1}^{q}\sum_{i=1}^{\ell_j}X_{j,i} ∑ j = 1 q ∑ i = 1 ℓ j X j , i for T T T in Q ( T ) Q(T) Q ( T ) and multiplying by the Vandermonde factors, we obtain
P = Q ( ∑ j = 1 q ∑ i = 1 ℓ j X j , i ) ⋅ ∏ j = 1 q ∏ 1 ≤ i < r ≤ ℓ j ( X j , r − X j , i ) . P=Q\left(\sum_{j=1}^{q}\sum_{i=1}^{\ell_j}X_{j,i}\right)\cdot\prod_{j=1}^{q}\prod_{1\le i<r\le\ell_j}(X_{j,r}-X_{j,i}). P = Q j = 1 ∑ q i = 1 ∑ ℓ j X j , i ⋅ j = 1 ∏ q 1 ≤ i < r ≤ ℓ j ∏ ( X j , r − X j , i ) .
The Vandermonde factors make P P P vanish whenever two variables in the same block take the same value. If the choices are distinct within each block, selecting them from π ( L j ) \pi(L_j) π ( L j ) over Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z gives a sum in π ( Y ) \pi(Y) π ( Y ) , and selecting them from L j L_j L j over G G G gives a sum in Y Y Y .
We will detect the coefficient in P P P of the monomial
X t = ∏ j = 1 q ∏ i = 1 ℓ j X j , i t j , i . X^t=\prod_{j=1}^{q}\prod_{i=1}^{\ell_j}X_{j,i}^{t_{j,i}}. X t = j = 1 ∏ q i = 1 ∏ ℓ j X j , i t j , i .
For the variable X j , i X_{j,i} X j , i , the interpolation formula needs t j , i + 1 t_{j,i}+1 t j , i + 1 distinct nodes from the s j s_j s j available values in block j j j , so we require 0 ≤ t j , i ≤ s j − 1 0 \le t_{j,i} \le s_j-1 0 ≤ t j , i ≤ s j − 1 . We choose the exponents within each block to be strictly increasing. Their positive differences lie in [ 1 , p − 1 ] [1,p-1] [ 1 , p − 1 ] , so the residue classes of those differences are units in both rings. To make X t X^t X t have the top degree of P P P , we also require
∑ j , i t j , i = d + ∑ j = 1 q ( ℓ j 2 ) . \sum_{j,i}t_{j,i}=d+\sum_{j=1}^{q}\binom{\ell_j}{2}. j , i ∑ t j , i = d + j = 1 ∑ q ( 2 ℓ j ) .
To see that these requirements can be met, set t j , i = i − 1 + λ j , i t_{j,i}=i-1+\lambda_{j,i} t j , i = i − 1 + λ j , i . The inequalities within a nonempty block become
0 ≤ λ j , 1 ≤ ⋯ ≤ λ j , ℓ j ≤ s j − ℓ j . 0\le\lambda_{j,1}\le\cdots\le\lambda_{j,\ell_j}\le s_j-\ell_j. 0 ≤ λ j , 1 ≤ ⋯ ≤ λ j , ℓ j ≤ s j − ℓ j .
The total-degree requirement is now ∑ j , i λ j , i = d \sum_{j,i}\lambda_{j,i}=d ∑ j , i λ j , i = d . For a block j j j with ℓ j > 0 \ell_j>0 ℓ j > 0 and a desired sum d j ∈ [ 0 , ℓ j ( s j − ℓ j ) ] d_j\in[0,\ell_j(s_j-\ell_j)] d j ∈ [ 0 , ℓ j ( s j − ℓ j )] of the λ j , i \lambda_{j,i} λ j , i , divide d j d_j d j by ℓ j \ell_j ℓ j with quotient a j a_j a j and remainder b j b_j b j . Take ℓ j − b j \ell_j-b_j ℓ j − b j entries equal to a j a_j a j followed by b j b_j b j entries equal to a j + 1 a_j+1 a j + 1 . These entries satisfy the upper bound, since a j = s j − ℓ j a_j=s_j-\ell_j a j = s j − ℓ j forces b j = 0 b_j=0 b j = 0 . A block with ℓ j = 0 \ell_j=0 ℓ j = 0 contributes zero. The intervals for d j d_j d j have sum [ 0 , D ] [0,D] [ 0 , D ] , so we may choose them with ∑ j d j = d \sum_jd_j=d ∑ j d j = d . This gives the required exponents.
For each variable X j , i X_{j,i} X j , i , choose E j , i ⊆ L j E_{j,i}\subseteq L_j E j , i ⊆ L j with ∣ E j , i ∣ = t j , i + 1 |E_{j,i}|=t_{j,i}+1 ∣ E j , i ∣ = t j , i + 1 . The node set for this variable is π ( E j , i ) \pi(E_{j,i}) π ( E j , i ) over Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z and E j , i E_{j,i} E j , i over G G G . In either ring, let E E E be the node set for X j , i X_{j,i} X j , i . For a univariate polynomial H ( T ) H(T) H ( T ) over that ring, define
L j , i ( H ) = ∑ a ∈ E H ( a ) ∏ b ∈ E ∖ { a } ( a − b ) . \mathcal{L}_{j,i}(H)=\sum_{a\in E}\frac{H(a)}{\prod_{b\in E\setminus\{a\}}(a-b)}. L j , i ( H ) = a ∈ E ∑ ∏ b ∈ E ∖ { a } ( a − b ) H ( a ) .
Distinct nodes have distinct residues modulo p p p , so all node differences in the denominators are units. The Vandermonde determinant of the nodes is therefore a unit, and Lagrange interpolation holds in either ring. Taking the coefficient of T t j , i T^{t_{j,i}} T t j , i in the interpolating expression for T u T^u T u gives
L j , i ( T u ) = { 0 , 0 ≤ u < t j , i , 1 , u = t j , i . \mathcal{L}_{j,i}(T^u)=
\begin{cases}
0, & 0\le u<t_{j,i},\\
1, & u=t_{j,i}.
\end{cases} L j , i ( T u ) = { 0 , 1 , 0 ≤ u < t j , i , u = t j , i .
Every monomial in P P P other than X t X^t X t has an exponent below its target t j , i t_{j,i} t j , i in at least one variable, since deg P ≤ ∑ j , i t j , i \deg P\le\sum_{j,i}t_{j,i} deg P ≤ ∑ j , i t j , i . Applying the functionals successively in their respective variables therefore extracts the coefficient of X t X^t X t . If P P P vanishes on the Cartesian product of the node sets in the chosen ring, this coefficient is zero.
To compute the coefficient, only the leading term of Q Q Q is needed. In the determinant det [ X j r − 1 ] i , r = 1 ℓ j \det[X_j^{r-1}]_{i,r=1}^{\ell_j} det [ X j r − 1 ] i , r = 1 ℓ j for block j j j , using column r r r in row i i i leaves the exponent t j , i − ( r − 1 ) t_{j,i}-(r-1) t j , i − ( r − 1 ) to be supplied by the leading term of Q Q Q . The multinomial expansion therefore gives
d ! ⋅ ∏ j = 1 q det [ 1 ( t j , i − r + 1 ) ! ] i , r = 1 ℓ j , d!\cdot\prod_{j=1}^{q}\det\left[\frac{1}{(t_{j,i}-r+1)!}\right]_{i,r=1}^{\ell_j}, d ! ⋅ j = 1 ∏ q det [ ( t j , i − r + 1 )! 1 ] i , r = 1 ℓ j ,
where the entry is zero when t j , i < r − 1 t_{j,i}<r-1 t j , i < r − 1 . All factorials in the denominators are units, since t j , i < p t_{j,i}<p t j , i < p . Factoring 1 / t j , i ! 1/t_{j,i}! 1/ t j , i ! from row i i i of each determinant leaves the entry ( t j , i ) r − 1 (t_{j,i})_{r-1} ( t j , i ) r − 1 , where ( t ) r − 1 = ∏ k = 0 r − 2 ( t − k ) (t)_{r-1}=\prod_{k=0}^{r-2}(t-k) ( t ) r − 1 = ∏ k = 0 r − 2 ( t − k ) is the falling factorial and ( t ) 0 = 1 (t)_0=1 ( t ) 0 = 1 . These are monic polynomials of successive degrees 0 , … , ℓ j − 1 0,\ldots,\ell_j-1 0 , … , ℓ j − 1 , so the determinants reduce to Vandermonde products. The coefficient is thus
d ! ⋅ ∏ j = 1 q ∏ 1 ≤ i < r ≤ ℓ j ( t j , r − t j , i ) ∏ i = 1 ℓ j t j , i ! . d!\cdot\prod_{j=1}^{q}\frac{\prod_{1\le i<r\le\ell_j}(t_{j,r}-t_{j,i})}{\prod_{i=1}^{\ell_j}t_{j,i}!}. d ! ⋅ j = 1 ∏ q ∏ i = 1 ℓ j t j , i ! ∏ 1 ≤ i < r ≤ ℓ j ( t j , r − t j , i ) .
An empty block contributes the factor 1 1 1 . Every factor other than d ! d! d ! is a unit. Therefore, if d ! d! d ! is nonzero in the chosen ring, then P P P is nonzero at some tuple of nodes. At that tuple the choices in each block are distinct, and Q Q Q is nonzero at their sum.
For the first assertion, work over Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z and set d = min { p − 1 , D } d=\min\{p-1,D\} d = min { p − 1 , D } . If ∣ π ( Y ) ∣ ≤ d |\pi(Y)|\le d ∣ π ( Y ) ∣ ≤ d , the monic polynomial
Q ( T ) = T d − ∣ π ( Y ) ∣ ⋅ ∏ a ∈ π ( Y ) ( T − a ) Q(T)=T^{d-|\pi(Y)|}\cdot\prod_{a\in\pi(Y)}(T-a) Q ( T ) = T d − ∣ π ( Y ) ∣ ⋅ a ∈ π ( Y ) ∏ ( T − a )
has degree d d d and vanishes on π ( Y ) \pi(Y) π ( Y ) , contrary to the preceding conclusion because d ! d! d ! is nonzero modulo p p p . Hence ∣ π ( Y ) ∣ ≥ d + 1 = min { p , D + 1 } |\pi(Y)|\ge d+1=\min\{p,D+1\} ∣ π ( Y ) ∣ ≥ d + 1 = min { p , D + 1 } .
For the second assertion, work over G G G and suppose that D ≥ 2 p − 1 D\ge2p-1 D ≥ 2 p − 1 and Y ∩ p G ⊆ { 0 } Y\cap pG\subseteq\{0\} Y ∩ pG ⊆ { 0 } . Take
d = 2 p − 1 , Q ( T ) = T ⋅ ∏ a = 1 p − 1 ( T − a ) 2 . d=2p-1,\qquad Q(T)=T\cdot\prod_{a=1}^{p-1}(T-a)^2. d = 2 p − 1 , Q ( T ) = T ⋅ a = 1 ∏ p − 1 ( T − a ) 2 .
If y ∈ Y y\in Y y ∈ Y has π ( y ) = 0 \pi(y)=0 π ( y ) = 0 , then y = 0 y=0 y = 0 . Otherwise let a a a be the integer representative of π ( y ) \pi(y) π ( y ) in [ 1 , p − 1 ] [1,p-1] [ 1 , p − 1 ] . The residue class of a a a in G G G satisfies y − a ∈ p G y-a\in pG y − a ∈ pG , so ( y − a ) 2 = 0 (y-a)^2=0 ( y − a ) 2 = 0 in G G G . Thus Q Q Q vanishes on Y Y Y . Since p ∣ d ! p\mid d! p ∣ d ! but p 2 ∤ d ! p^2\nmid d! p 2 ∤ d ! , the residue class of d ! d! d ! in G G G is nonzero. This again contradicts the preceding conclusion. □
Lemma 4.2. Suppose S S S is exceptional. Then e ≥ 0 e\ge0 e ≥ 0 . Fix central selection sizes k j k_j k j of total p p p .
For a set J J J of layer indices, write
b = ∑ j ∈ J f ( s j ) , Y J = ∑ j ∈ J Σ k j ( L j ) . b=\sum_{j\in J}f(s_j),\qquad Y_J=\sum_{j\in J}\Sigma_{k_j}(L_j). b = j ∈ J ∑ f ( s j ) , Y J = j ∈ J ∑ Σ k j ( L j ) . We take Y ∅ = { 0 } Y_{\varnothing}=\{0\} Y ∅ = { 0 } . If b ≤ p − e − 1 b\le p-e-1 b ≤ p − e − 1 , then π \pi π is injective on Y J Y_J Y J and ∣ π ( Y J ) ∣ ≤ b + e + 1 |\pi(Y_J)|\le b+e+1 ∣ π ( Y J ) ∣ ≤ b + e + 1 .
Proof. Apply Lemma 4.1 to the h h h layers with ℓ j = k j \ell_j=k_j ℓ j = k j for 1 ≤ j ≤ h 1\le j\le h 1 ≤ j ≤ h . For each layer, central selection gives k j ( s j − k j ) = f ( s j ) k_j(s_j-k_j)=f(s_j) k j ( s j − k j ) = f ( s j ) . Thus
D = ∑ j = 1 h k j ( s j − k j ) = ∑ j = 1 h f ( s j ) = b S . D=\sum_{j=1}^{h}k_j(s_j-k_j)=\sum_{j=1}^{h}f(s_j)=b_S. D = j = 1 ∑ h k j ( s j − k j ) = j = 1 ∑ h f ( s j ) = b S .
Also, Y ⊆ Σ p ( S ) Y\subseteq\Sigma_p(S) Y ⊆ Σ p ( S ) because ∑ j = 1 h k j = p \sum_{j=1}^{h}k_j=p ∑ j = 1 h k j = p . Thus Y ∩ p G ⊆ { 0 } Y\cap pG\subseteq\{0\} Y ∩ pG ⊆ { 0 } by exceptionality, and Lemma 4.1 gives b S ≤ 2 p − 2 b_S\le2p-2 b S ≤ 2 p − 2 . Let J c J^c J c consist of the remaining layer indices. Apply Lemma 4.1 to the layers indexed by J c J^c J c with ℓ j = k j \ell_j=k_j ℓ j = k j . The sumset is Y J c Y_{J^c} Y J c and the parameter is D = b S − b = 2 p − 2 − e − b D=b_S-b=2p-2-e-b D = b S − b = 2 p − 2 − e − b . Since b ≤ p − e − 1 b\le p-e-1 b ≤ p − e − 1 , we have D ≥ p − 1 D\ge p-1 D ≥ p − 1 , so π ( Y J c ) = C p \pi(Y_{J^c})=C_p π ( Y J c ) = C p . If y , y ′ ∈ Y J y,y'\in Y_J y , y ′ ∈ Y J satisfy y ‾ = y ′ ‾ \overline{y}=\overline{y'} y = y ′ , choose z ∈ Y J c z\in Y_{J^c} z ∈ Y J c with z = − y z=-y z = − y . Then y + z , y ′ + z ∈ Σ p ( S ) ∩ p G y+z,y'+z\in\Sigma_p(S)\cap pG y + z , y ′ + z ∈ Σ p ( S ) ∩ pG . By (1) , y + z = y ′ + z = 0 y+z=y'+z=0 y + z = y ′ + z = 0 , so y = y ′ y=y' y = y ′ .
Apply Lemma 4.1 again, taking one element from Y J Y_J Y J and k j k_j k j elements from each layer indexed by J c J^c J c . The resulting sumset is Y J + Y J c ⊆ Σ p ( S ) Y_J+Y_{J^c}\subseteq\Sigma_p(S) Y J + Y J c ⊆ Σ p ( S ) , so exceptionality allows us to apply the second assertion of Lemma 4.1 with D = ( ∣ Y J ∣ − 1 ) + ( b S − b ) D=(|Y_J|-1)+(b_S-b) D = ( ∣ Y J ∣ − 1 ) + ( b S − b ) . Thus
( ∣ Y J ∣ − 1 ) + ( b S − b ) ≤ 2 p − 2 , ∣ π ( Y J ) ∣ = ∣ Y J ∣ ≤ b + e + 1. (|Y_J|-1)+(b_S-b)\le2p-2,\qquad|\pi(Y_J)|=|Y_J|\le b+e+1. ( ∣ Y J ∣ − 1 ) + ( b S − b ) ≤ 2 p − 2 , ∣ π ( Y J ) ∣ = ∣ Y J ∣ ≤ b + e + 1.
Lemma 4.3. If S S S is exceptional and 1 ≤ t ≤ ⌊ ( m + 1 ) / 2 ⌋ 1\le t\le\lfloor(m+1)/2\rfloor 1 ≤ t ≤ ⌊( m + 1 ) /2 ⌋ , then π \pi π is injective on Σ t ( S ) \Sigma_t(S) Σ t ( S ) .
Proof. Let T 1 , T 2 ∣ S T_1,T_2\mid S T 1 , T 2 ∣ S with ∣ T 1 ∣ = ∣ T 2 ∣ = t |T_1|=|T_2|=t ∣ T 1 ∣ = ∣ T 2 ∣ = t and σ ( T 1 ‾ ) = σ ( T 2 ‾ ) \sigma(\overline{T_1})=\sigma(\overline{T_2}) σ ( T 1 ) = σ ( T 2 ) . Outside their combined positions choose R R R of length 2 p − 2 t 2p-2t 2 p − 2 t and set H 0 = p − 2 t + 1 H_0=p-2t+1 H 0 = p − 2 t + 1 . Arrange equal terms consecutively and distribute the positions cyclically into H 0 H_0 H 0 blocks. Since 2 t ≤ m + 1 2t\le m+1 2 t ≤ m + 1 , we have h ( R ) ≤ p − m ≤ H 0 h(R)\le p-m\le H_0 h ( R ) ≤ p − m ≤ H 0 . Thus no block receives two copies of the same value. Since ∣ R ∣ − 2 H 0 = 2 t − 2 ≥ 0 |R|-2H_0=2t-2\ge0 ∣ R ∣ − 2 H 0 = 2 t − 2 ≥ 0 , each block has at least two terms. Select half from each block, rounding up in half of the odd-sized blocks and down in the other half, for a total of p − t p-t p − t terms. A block of size u u u contributes f ( u ) ≥ u − 1 f(u)\ge u-1 f ( u ) ≥ u − 1 , so the total contribution is at least ∣ R ∣ − H 0 = p − 1 |R|-H_0=p-1 ∣ R ∣ − H 0 = p − 1 .
Since the terms in each block are distinct and π \pi π is injective on supp ( S ) \operatorname{supp}(S) supp ( S ) , we may apply Lemma 4.1 to the sets of values in these blocks, with ℓ j \ell_j ℓ j equal to the number selected from block j j j . The parameter D D D is at least p − 1 p-1 p − 1 , and the image under π \pi π of the resulting sumset is contained in Σ p − t ( R ‾ ) \Sigma_{p-t}(\overline{R}) Σ p − t ( R ) . Thus Σ p − t ( R ‾ ) = C p \Sigma_{p-t}(\overline{R})=C_p Σ p − t ( R ) = C p . Choose W ∣ R W\mid R W ∣ R with
∣ W ∣ = p − t , σ ( W ‾ ) = − σ ( T 1 ‾ ) = − σ ( T 2 ‾ ) . |W|=p-t,\qquad\sigma(\overline{W})=-\sigma(\overline{T_1})=-\sigma(\overline{T_2}). ∣ W ∣ = p − t , σ ( W ) = − σ ( T 1 ) = − σ ( T 2 ) .
By (1) , σ ( T 1 W ) = σ ( T 2 W ) = 0 \sigma(T_1W)=\sigma(T_2W)=0 σ ( T 1 W ) = σ ( T 2 W ) = 0 , which gives σ ( T 1 ) = σ ( T 2 ) \sigma(T_1)=\sigma(T_2) σ ( T 1 ) = σ ( T 2 ) .
Common completions also control the sums formed from the three most frequent values of S S S .
Lemma 4.4. Suppose S S S is exceptional, p ≥ 11 p\ge11 p ≥ 11 , and m ≥ m 0 m\ge m_0 m ≥ m 0 . Let v 1 ≥ v 2 ≥ v 3 v_1\ge v_2\ge v_3 v 1 ≥ v 2 ≥ v 3 be the three largest multiplicities, padded with zeros if necessary. Then v 2 + v 3 ≤ p − 1 v_2+v_3\le p-1 v 2 + v 3 ≤ p − 1 .
Proof. Suppose v 2 + v 3 ≥ p v_2+v_3\ge p v 2 + v 3 ≥ p . Then
0 < m = p − v 1 ≤ p − v 2 ≤ v 3 ≤ v 1 = p − m . 0<m=p-v_1\le p-v_2\le v_3\le v_1=p-m. 0 < m = p − v 1 ≤ p − v 2 ≤ v 3 ≤ v 1 = p − m .
Thus m ≤ ( p − 1 ) / 2 m\le(p-1)/2 m ≤ ( p − 1 ) /2 . Choose distinct a , b , c ∈ supp ( S ) a,b,c\in\operatorname{supp}(S) a , b , c ∈ supp ( S ) with multiplicities v 1 , v 2 , v 3 v_1,v_2,v_3 v 1 , v 2 , v 3 , respectively. The multiplicities of any two of these values have sum at least p p p . Let t t t be the maximum of ⌊ ( m + 2 ) / 2 ⌋ \lfloor(m+2)/2\rfloor ⌊( m + 2 ) /2 ⌋ and the lower bound in the table. These choices give t < m t<m t < m . The last row records the upper bounds for the integer M M M defined below.
Table 1.
For ( x , y ) ∈ T = { ( x , y ) ∈ Z ≥ 0 2 : x + y ≤ t } (x,y)\in\mathcal{T}=\{(x,y)\in\mathbb{Z}_{\ge0}^2:x+y\le t\} ( x , y ) ∈ T = {( x , y ) ∈ Z ≥ 0 2 : x + y ≤ t } , define
T x , y = a x b y c t − x − y , σ ( T x , y ) = t c + x ( a − c ) + y ( b − c ) . T_{x,y}=a^xb^yc^{t-x-y},\qquad\sigma(T_{x,y})=tc+x(a-c)+y(b-c). T x , y = a x b y c t − x − y , σ ( T x , y ) = t c + x ( a − c ) + y ( b − c ) .
Since each of a , b , c a,b,c a , b , c occurs at least v 3 ≥ m > t v_3\ge m>t v 3 ≥ m > t times, we have T x , y ∣ S T_{x,y}\mid S T x , y ∣ S for every ( x , y ) ∈ T (x,y)\in\mathcal{T} ( x , y ) ∈ T . We first prove that π \pi π is injective on
{ σ ( T x , y ‾ ) : ( x , y ) ∈ T } ⊆ G . \{\sigma(\overline{T_{x,y}}):(x,y)\in\mathcal{T}\}\subseteq G. { σ ( T x , y ) : ( x , y ) ∈ T } ⊆ G .
Let ( x i , y i ) ∈ T (x_i,y_i)\in\mathcal{T} ( x i , y i ) ∈ T for i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } and suppose that
σ ( T x 1 , y 1 ‾ ) = σ ( T x 2 , y 2 ‾ ) . \sigma(\overline{T_{x_1,y_1}})=\sigma(\overline{T_{x_2,y_2}}). σ ( T x 1 , y 1 ) = σ ( T x 2 , y 2 ) .
If the two multiplicity vectors are equal, then the required equality of sums is immediate. Hence assume that they are distinct. Then
x 1 ≠ x 2 , y 1 ≠ y 2 , x 1 + y 1 ≠ x 2 + y 2 . x_1\ne x_2,\qquad y_1\ne y_2,\qquad x_1+y_1\ne x_2+y_2. x 1 = x 2 , y 1 = y 2 , x 1 + y 1 = x 2 + y 2 .
Indeed, x 1 = x 2 x_1=x_2 x 1 = x 2 would give ( y 1 − y 2 ) ( b ˉ − c ˉ ) = 0 (y_1-y_2)(\bar b-\bar c)=0 ( y 1 − y 2 ) ( b ˉ − c ˉ ) = 0 , and hence y 1 = y 2 y_1=y_2 y 1 = y 2 because ∣ y 1 − y 2 ∣ < p |y_1-y_2|<p ∣ y 1 − y 2 ∣ < p and b ˉ ≠ c ˉ \bar b\ne\bar c b ˉ = c ˉ . The case y 1 = y 2 y_1=y_2 y 1 = y 2 is analogous. If x 1 + y 1 = x 2 + y 2 x_1+y_1=x_2+y_2 x 1 + y 1 = x 2 + y 2 , then ( x 1 − x 2 ) ( a ˉ − b ˉ ) = 0 (x_1-x_2)(\bar a-\bar b)=0 ( x 1 − x 2 ) ( a ˉ − b ˉ ) = 0 , which again forces the two vectors to be equal.
Choose the copies in the two subsequences so that their positions are nested within each of a , b , c a,b,c a , b , c . Their union then uses
max { x 1 , x 2 } , max { y 1 , y 2 } , max { t − x 1 − y 1 , t − x 2 − y 2 } \max\{x_1,x_2\},\qquad\max\{y_1,y_2\},\qquad\max\{t-x_1-y_1,t-x_2-y_2\} max { x 1 , x 2 } , max { y 1 , y 2 } , max { t − x 1 − y 1 , t − x 2 − y 2 }
copies of a , b , c a,b,c a , b , c , respectively. Each of these three integers belongs to [ 1 , t ] [1,t] [ 1 , t ] , so deleting the union leaves a copy of each of a , b , c a,b,c a , b , c . Since v 1 ≥ ( p + 1 ) / 2 v_1\ge(p+1)/2 v 1 ≥ ( p + 1 ) /2 , the inequality 4 v 1 > ∣ S ∣ = 2 p 4v_1>|S|=2p 4 v 1 > ∣ S ∣ = 2 p shows that at most three support values have multiplicity v 1 v_1 v 1 . Hence every value of multiplicity v 1 v_1 v 1 belongs to { a , b , c } \{a,b,c\} { a , b , c } .
Outside the union choose a subsequence R R R satisfying
∣ R ∣ = 2 p − 2 t , supp ( R ) = supp ( S ) . |R|=2p-2t,\qquad\operatorname{supp}(R)=\operatorname{supp}(S). ∣ R ∣ = 2 p − 2 t , supp ( R ) = supp ( S ) .
Such a choice is possible because the remaining sequence has length at least 2 p − 2 t 2p-2t 2 p − 2 t and 2 p − 2 t > p − 1 ≥ ∣ supp ( S ) ∣ 2p-2t>p-1\ge|\operatorname{supp}(S)| 2 p − 2 t > p − 1 ≥ ∣ supp ( S ) ∣ , where the last inequality follows from the injectivity of π \pi π on supp ( S ) ⊆ G × \operatorname{supp}(S)\subseteq G^\times supp ( S ) ⊆ G × . Every value of multiplicity v 1 v_1 v 1 has lost at least one copy, whereas every other value has multiplicity at most v 1 − 1 v_1-1 v 1 − 1 . Therefore
h ( R ) ≤ v 1 − 1 = p − m − 1. h(R)\le v_1-1=p-m-1. h ( R ) ≤ v 1 − 1 = p − m − 1.
Set H 0 = p − 2 t + 1 H_0=p-2t+1 H 0 = p − 2 t + 1 . We construct a common completion according to the maximum multiplicity of R R R .
Case 1. h ( R ) ≤ H 0 h(R)\le H_0 h ( R ) ≤ H 0 . The blocks from the proof of Lemma 4.3 give Σ p − t ( R ‾ ) = C p \Sigma_{p-t}(\overline R)=C_p Σ p − t ( R ) = C p .
Case 2. h ( R ) > H 0 h(R)>H_0 h ( R ) > H 0 . The inequalities
H 0 < h ( R ) ≤ p − m − 1 H_0<h(R)\le p-m-1 H 0 < h ( R ) ≤ p − m − 1
give 2 t > m + 2 2t>m+2 2 t > m + 2 , whereas the table gives 2 t ≤ m + 3 2t\le m+3 2 t ≤ m + 3 . Hence 2 t = m + 3 2t=m+3 2 t = m + 3 , so p − m − 1 = H 0 + 1 p-m-1=H_0+1 p − m − 1 = H 0 + 1 and h ( R ) = H 0 + 1 h(R)=H_0+1 h ( R ) = H 0 + 1 . Since m ≤ ( p − 1 ) / 2 m\le(p-1)/2 m ≤ ( p − 1 ) /2 , we have
4 ( H 0 + 1 ) − ∣ R ∣ = 2 p − 3 m − 1 ≥ ( p + 1 ) / 2 > 0. 4(H_0+1)-|R|=2p-3m-1\ge(p+1)/2>0. 4 ( H 0 + 1 ) − ∣ R ∣ = 2 p − 3 m − 1 ≥ ( p + 1 ) /2 > 0.
Case 2.1. ∣ supp ( R ) ∣ ≥ 4 |\operatorname{supp}(R)|\ge4 ∣ supp ( R ) ∣ ≥ 4 . First take a four-value block containing every value of multiplicity H 0 + 1 H_0+1 H 0 + 1 , of which there are at most three. The remainder has maximum multiplicity at most H 0 H_0 H 0 and length ∣ R ∣ − 4 = 2 H 0 + 2 t − 6 ≥ 2 H 0 |R|-4=2H_0+2t-6\ge2H_0 ∣ R ∣ − 4 = 2 H 0 + 2 t − 6 ≥ 2 H 0 . Distribute it cyclically after grouping equal terms, obtaining H 0 H_0 H 0 blocks, each containing at least two terms with distinct values. Select two terms from the four-value block and make central selections from the remaining blocks, rounding the odd block sizes in opposite directions in pairs. This selects ∣ R ∣ / 2 = p − t |R|/2=p-t ∣ R ∣/2 = p − t terms. The total contribution is at least 4 + ∣ R ∣ − 4 − H 0 = p − 1 4+|R|-4-H_0=p-1 4 + ∣ R ∣ − 4 − H 0 = p − 1 , so Lemma 4.1 gives Σ p − t ( R ‾ ) = C p \Sigma_{p-t}(\overline R)=C_p Σ p − t ( R ) = C p .
Case 2.2. ∣ supp ( R ) ∣ = 3 |\operatorname{supp}(R)|=3 ∣ supp ( R ) ∣ = 3 . Since { a , b , c } ⊆ supp ( R ) \{a,b,c\}\subseteq\operatorname{supp}(R) { a , b , c } ⊆ supp ( R ) , we have supp ( R ) = { a , b , c } \operatorname{supp}(R)=\{a,b,c\} supp ( R ) = { a , b , c } . We distinguish whether their images form an arithmetic progression.
Case 2.2.1. The three images form an arithmetic progression. After permuting a , b , c a,b,c a , b , c within this case, assume that a ˉ + c ˉ = 2 b ˉ \bar a+\bar c=2\bar b a ˉ + c ˉ = 2 b ˉ . Lemma 4.3 with t = 2 t=2 t = 2 gives a + c = 2 b a+c=2b a + c = 2 b . Set ℓ = ⌊ ( p − v b ( S ) ) / 2 ⌋ \ell=\lfloor(p-v_b(S))/2\rfloor ℓ = ⌊( p − v b ( S )) /2 ⌋ . Since any two of the three multiplicities in S S S sum to at least p p p , we have
ℓ ≤ p − v b ( S ) ≤ min { v a ( S ) , v c ( S ) } . \ell\le p-v_b(S)\le\min\{v_a(S),v_c(S)\}. ℓ ≤ p − v b ( S ) ≤ min { v a ( S ) , v c ( S )} .
Also p − 2 ℓ ∈ { v b ( S ) − 1 , v b ( S ) } p-2\ell\in\{v_b(S)-1,v_b(S)\} p − 2 ℓ ∈ { v b ( S ) − 1 , v b ( S )} . Consequently,
a ℓ c ℓ b p − 2 ℓ ∣ S , σ ( a ℓ c ℓ b p − 2 ℓ ) = ℓ ( a + c ) + ( p − 2 ℓ ) b = p b ∈ p G ∖ { 0 } , a^{\ell}c^{\ell}b^{p-2\ell}\mid S,\qquad\sigma(a^{\ell}c^{\ell}b^{p-2\ell})=\ell(a+c)+(p-2\ell)b=pb\in pG\setminus\{0\}, a ℓ c ℓ b p − 2 ℓ ∣ S , σ ( a ℓ c ℓ b p − 2 ℓ ) = ℓ ( a + c ) + ( p − 2 ℓ ) b = p b ∈ pG ∖ { 0 } ,
contrary to (1) .
Case 2.2.2. The three images do not form an arithmetic progression. Group equal terms of R R R and distribute the positions cyclically into H 0 + 1 H_0+1 H 0 + 1 blocks. Each block has distinct values since h ( R ) = H 0 + 1 h(R)=H_0+1 h ( R ) = H 0 + 1 . The support has size three, and ∣ R ∣ − 2 ( H 0 + 1 ) = 2 t − 4 ≥ 2 |R|-2(H_0+1)=2t-4\ge2 ∣ R ∣ − 2 ( H 0 + 1 ) = 2 t − 4 ≥ 2 , so every block has size two or three and at least two have size three. Select one term from one three-value block and two from another. Their joint projected sumset is a translate of
{ a ˉ , b ˉ , c ˉ } − { a ˉ , b ˉ , c ˉ } , \{\bar a,\bar b,\bar c\}-\{\bar a,\bar b,\bar c\}, { a ˉ , b ˉ , c ˉ } − { a ˉ , b ˉ , c ˉ } ,
which has seven elements since the three images do not form an arithmetic progression. The two blocks supply three terms. Round the remaining odd block sizes in opposite directions in pairs to select ( ∣ R ∣ − 6 ) / 2 (|R|-6)/2 ( ∣ R ∣ − 6 ) /2 more terms. Each remaining block has a projected central sumset of cardinality equal to its size. Applying Lemma 2.1 to the joint sumset and these remaining sumsets gives
∣ Σ p − t ( R ‾ ) ∣ ≥ min { p , 1 + 6 + ( ∣ R ∣ − 6 ) − ( H 0 − 1 ) } = p . |\Sigma_{p-t}(\overline{R})|\ge\min\{p,1+6+(|R|-6)-(H_0-1)\}=p. ∣ Σ p − t ( R ) ∣ ≥ min { p , 1 + 6 + ( ∣ R ∣ − 6 ) − ( H 0 − 1 )} = p .
Cases 1, 2.1, and 2.2.2 give Σ p − t ( R ‾ ) = C p \Sigma_{p-t}(\overline{R})=C_p Σ p − t ( R ) = C p , so the two subsequences T x 1 , y 1 T_{x_1,y_1} T x 1 , y 1 and T x 2 , y 2 T_{x_2,y_2} T x 2 , y 2 have a common completion W ∣ R W\mid R W ∣ R satisfying
∣ W ∣ = p − t , σ ( W ‾ ) = − σ ( T ‾ x 1 , y 1 ) = − σ ( T ‾ x 2 , y 2 ) . |W|=p-t,\qquad\sigma(\overline{W})=-\sigma(\overline{T}_{x_1,y_1})=-\sigma(\overline{T}_{x_2,y_2}). ∣ W ∣ = p − t , σ ( W ) = − σ ( T x 1 , y 1 ) = − σ ( T x 2 , y 2 ) .
By (1) ,
σ ( T x 1 , y 1 W ) = σ ( T x 2 , y 2 W ) = 0 , \sigma(T_{x_1,y_1}W)=\sigma(T_{x_2,y_2}W)=0, σ ( T x 1 , y 1 W ) = σ ( T x 2 , y 2 W ) = 0 ,
and hence σ ( T x 1 , y 1 ) = σ ( T x 2 , y 2 ) \sigma(T_{x_1,y_1})=\sigma(T_{x_2,y_2}) σ ( T x 1 , y 1 ) = σ ( T x 2 , y 2 ) . Case 2.2.1 has already given a contradiction. This proves the required injectivity of π \pi π .
We next count the sums σ ( T x , y ) \sigma(T_{x,y}) σ ( T x , y ) . Since π \pi π is injective on their set, there are at most p p p distinct sums in G G G . The table gives ∣ T ∣ = ( t + 2 2 ) > p |\mathcal{T}|=\binom{t+2}{2}>p ∣ T ∣ = ( 2 t + 2 ) > p for p < 53 p<53 p < 53 . For p ≥ 53 p\ge53 p ≥ 53 , t ≥ ⌊ ( p + 23 ) / 8 ⌋ t\ge\lfloor(p+23)/8\rfloor t ≥ ⌊( p + 23 ) /8 ⌋ , so p ≤ 8 t − 17 p\le8t-17 p ≤ 8 t − 17 . For t ≥ 11 t\ge11 t ≥ 11 this gives p < 9 t − 27 p<9t-27 p < 9 t − 27 , and the same inequality follows from p ≤ 53 p\le53 p ≤ 53 when t = 9 t=9 t = 9 and p ≤ 61 p\le61 p ≤ 61 when t = 10 t=10 t = 10 . Since t ≥ 9 t\ge9 t ≥ 9 , we have
( t + 2 2 ) − ( 9 t − 27 ) = ( t − 7 ) ( t − 8 ) / 2 > 0. \binom{t+2}{2}-(9t-27)=(t-7)(t-8)/2>0. ( 2 t + 2 ) − ( 9 t − 27 ) = ( t − 7 ) ( t − 8 ) /2 > 0.
Thus two distinct points of T \mathcal{T} T give the same sum in G G G .
For distinct ( x 1 , y 1 ) , ( x 2 , y 2 ) ∈ T (x_1,y_1),(x_2,y_2)\in\mathcal{T} ( x 1 , y 1 ) , ( x 2 , y 2 ) ∈ T giving the same sum, call
( r , s ) = ( x 1 − x 2 , y 1 − y 2 ) (r,s)=(x_1-x_2,y_1-y_2) ( r , s ) = ( x 1 − x 2 , y 1 − y 2 )
a collision vector. Every collision vector satisfies r ( a − c ) + s ( b − c ) = 0 r(a-c)+s(b-c)=0 r ( a − c ) + s ( b − c ) = 0 . Hence, for two collision vectors ( r 1 , s 1 ) (r_1,s_1) ( r 1 , s 1 ) and ( r 2 , s 2 ) (r_2,s_2) ( r 2 , s 2 ) we have r i ( a − c ) + s i ( b − c ) = 0 r_i(a-c)+s_i(b-c)=0 r i ( a − c ) + s i ( b − c ) = 0 for i = 1 , 2 i=1,2 i = 1 , 2 . Eliminating b − c b-c b − c gives
( r 1 s 2 − r 2 s 1 ) ( a − c ) = 0 , ∣ r 1 s 2 − r 2 s 1 ∣ ≤ 2 t 2 < p 2 . (r_1s_2-r_2s_1)(a-c)=0,\qquad|r_1s_2-r_2s_1|\le2t^2<p^2. ( r 1 s 2 − r 2 s 1 ) ( a − c ) = 0 , ∣ r 1 s 2 − r 2 s 1 ∣ ≤ 2 t 2 < p 2 .
Since a − c a-c a − c has additive order p 2 p^2 p 2 , the determinant is divisible by p 2 p^2 p 2 and hence is zero. All collision vectors are therefore collinear. The greatest common divisor of the coordinates of a nonzero collision vector is at most t < p t<p t < p , so multiplication by it is an automorphism of G G G . Cancelling it gives a primitive relation ( r , s ) (r,s) ( r , s ) . Set M = max { ∣ r ∣ , ∣ s ∣ , ∣ r + s ∣ } ≤ t M=\max\{|r|,|s|,|r+s|\}\le t M = max { ∣ r ∣ , ∣ s ∣ , ∣ r + s ∣ } ≤ t . Each class of equal sums in T \mathcal{T} T is an integer chain with step ( r , s ) (r,s) ( r , s ) , and T ∩ ( T + ( r , s ) ) \mathcal{T}\cap(\mathcal{T}+(r,s)) T ∩ ( T + ( r , s )) is a translate of the integer triangle with side parameter t − M t-M t − M . Counting points with no predecessor gives the number of distinct sums as
( t + 2 2 ) − ( t − M + 2 2 ) = M ( 2 t + 3 − M ) 2 ≤ p . \binom{t+2}{2}-\binom{t-M+2}{2}=\frac{M(2t+3-M)}{2}\le p. ( 2 t + 2 ) − ( 2 t − M + 2 ) = 2 M ( 2 t + 3 − M ) ≤ p .
The expression is strictly increasing for 0 ≤ M ≤ t 0\le M\le t 0 ≤ M ≤ t . Substituting the first excluded value gives the bounds in the table. For p ≥ 53 p\ge53 p ≥ 53 , the value at M = 9 M=9 M = 9 is 9 t − 27 > p 9t-27>p 9 t − 27 > p .
The differences of distinct values have additive order p 2 p^2 p 2 . Thus none of r r r , s s s , r + s r+s r + s can be zero, since a zero coordinate or r + s = 0 r+s=0 r + s = 0 would give a nonzero multiple of a single support difference with coefficient of absolute value at most t < p t<p t < p . After permuting a , b , c a,b,c a , b , c , we may assume that u a + v c = M b ua+vc=Mb u a + v c = M b , where u + v = M u+v=M u + v = M , 1 ≤ u ≤ v 1\le u\le v 1 ≤ u ≤ v , and gcd ( u , v ) = 1 \gcd(u,v)=1 g cd( u , v ) = 1 . Let H , L H,L H , L be the multiplicities of a , c a,c a , c , respectively, and put N = p − v b ( S ) N=p-v_b(S) N = p − v b ( S ) and j = ⌊ N / M ⌋ j=\lfloor N/M\rfloor j = ⌊ N / M ⌋ . Then H , L ≥ N ≥ m H,L\ge N\ge m H , L ≥ N ≥ m . The table gives m ≥ M − 1 m \ge M - 1 m ≥ M − 1 , so j u ≤ ( N + M − 1 ) / 2 ≤ N ju \le(N + M - 1)/2 \le N j u ≤ ( N + M − 1 ) /2 ≤ N and N ≤ j M ≤ N + M − 1 ≤ p N \le jM \le N + M - 1 \le p N ≤ j M ≤ N + M − 1 ≤ p . If j v ≤ L jv \le L j v ≤ L , then a j u c j v b p − j M ∣ S a^{ju}c^{jv}b^{p-jM} \mid S a j u c j v b p − j M ∣ S and
σ ( a j u c j v b p − j M ) = j ( u a + v c ) + ( p − j M ) b = p b ∈ p G ∖ { 0 } , \sigma\left(a^{ju}c^{jv}b^{p-jM}\right)=j(ua+vc)+(p-jM)b=pb\in pG\setminus\{0\}, σ ( a j u c j v b p − j M ) = j ( u a + v c ) + ( p − j M ) b = p b ∈ pG ∖ { 0 } ,
a contradiction.
It remains to consider j v > L jv>L j v > L . The inequalities
( j − 1 ) M + 1 ≤ N ≤ L ≤ j v − 1 (j-1)M+1\le N\le L\le jv-1 ( j − 1 ) M + 1 ≤ N ≤ L ≤ j v − 1
give j u ≤ M − 2 ju\le M-2 j u ≤ M − 2 . We must have u = 1 u=1 u = 1 . Indeed, u ≥ 2 u\ge2 u ≥ 2 implies M ≥ 5 M\ge5 M ≥ 5 , hence p ≥ 29 p\ge29 p ≥ 29 and N ≥ 11 N\ge11 N ≥ 11 . Since M ≤ 8 M\le8 M ≤ 8 and u , v u,v u , v are coprime, v ≤ 5 v\le5 v ≤ 5 . Also j u ≤ 6 ju\le6 j u ≤ 6 forces j ≤ 2 j\le2 j ≤ 2 , since j ≥ 3 j\ge3 j ≥ 3 would require u = 2 u=2 u = 2 , M = 8 M=8 M = 8 , v = 6 v=6 v = 6 . Thus j v ≤ 10 < N jv\le10<N j v ≤ 10 < N , a contradiction.
Now j ≤ v − 1 j\le v-1 j ≤ v − 1 gives N ≤ v ( v − 1 ) − 1 N\le v(v-1)-1 N ≤ v ( v − 1 ) − 1 . For v ≤ 2 v\le2 v ≤ 2 this contradicts N ≥ 5 N\ge5 N ≥ 5 . For v = 3 v=3 v = 3 , M = 4 M=4 M = 4 gives p ≥ 17 p\ge17 p ≥ 17 and N ≥ 7 N\ge7 N ≥ 7 , again impossible. For v = 4 v=4 v = 4 , M = 5 M=5 M = 5 gives p ≥ 29 p\ge29 p ≥ 29 and N ≤ 11 N\le11 N ≤ 11 allows only p = 29 , 31 p=29,31 p = 29 , 31 . Then j = 3 j=3 j = 3 and N = L = 11 N=L=11 N = L = 11 . In the remaining cases p ≥ 37 p\ge37 p ≥ 37 and 5 ≤ v ≤ 7 5\le v\le7 5 ≤ v ≤ 7 .
Since c ≠ b c\ne b c = b , the element d = c − b d=c-b d = c − b is a unit. The relation a + v c = ( v + 1 ) b a+vc=(v+1)b a + v c = ( v + 1 ) b gives a = b − v d a=b-vd a = b − v d . Reserve one term equal to c c c , choose x x x terms equal to a a a and y y y terms equal to c c c , and complete to p − 1 p-1 p − 1 terms with b b b . For x ∈ [ x 0 , H ] x\in[x_0,H] x ∈ [ x 0 , H ] , where x 0 = max { 0 , v − ( L − N ) } x_0=\max\{0,v-(L-N)\} x 0 = max { 0 , v − ( L − N )} , the admissible values of y y y form [ y − ( x ) , y + ( x ) ] [y_-(x),y_+(x)] [ y − ( x ) , y + ( x )] , with
y − ( x ) = max { 0 , N − 1 − x } , y + ( x ) = min { L − 1 , p − 1 − x } . y_-(x)=\max\{0,N-1-x\},\qquad y_+(x)=\min\{L-1,p-1-x\}. y − ( x ) = max { 0 , N − 1 − x } , y + ( x ) = min { L − 1 , p − 1 − x } .
For x ≤ N − 1 x\le N-1 x ≤ N − 1 its width is min { L − N + x , p − N } ≥ v \min\{L-N+x,p-N\}\ge v min { L − N + x , p − N } ≥ v . For x ≥ N − 1 x\ge N-1 x ≥ N − 1 the width is at least m − 1 ≥ v m-1\ge v m − 1 ≥ v . Restoring the reserved term gives
σ ( a x c y + 1 b p − 1 − x − y ) = p b + ( 1 − v x + y ) d . \sigma\left(a^xc^{y+1}b^{p-1-x-y}\right)=pb+(1-vx+y)d. σ ( a x c y + 1 b p − 1 − x − y ) = p b + ( 1 − v x + y ) d .
As x x x increases by one, the left endpoint of the coefficient interval [ 1 − v x + y − ( x ) , 1 − v x + y + ( x ) ] [1-vx+y_-(x),1-vx+y_+(x)] [ 1 − v x + y − ( x ) , 1 − v x + y + ( x )] decreases by v v v or v + 1 v+1 v + 1 . The intervals have width at least v v v , so consecutive intervals overlap or are adjacent, and their union is an integer interval. Since x 0 ≤ v < m ≤ p − L x_0\le v<m\le p-L x 0 ≤ v < m ≤ p − L and H ≥ N H\ge N H ≥ N , the selections ( x 0 , L − 1 ) (x_0,L-1) ( x 0 , L − 1 ) and ( H , 0 ) (H,0) ( H , 0 ) are admissible. The width is therefore at least
v H + L − 1 − v x 0 ≥ p − 1 + ( v − 1 ) H − v x 0 . vH+L-1-vx_0\ge p-1+(v-1)H-vx_0. v H + L − 1 − v x 0 ≥ p − 1 + ( v − 1 ) H − v x 0 .
For v = 4 v=4 v = 4 , H ≥ p − 11 H\ge p-11 H ≥ p − 11 and x 0 = 4 x_0=4 x 0 = 4 , so ( v − 1 ) H − v x 0 ≥ 3 p − 49 ≥ p (v-1)H-vx_0\ge3p-49\ge p ( v − 1 ) H − v x 0 ≥ 3 p − 49 ≥ p . For 5 ≤ v ≤ 7 5\le v\le7 5 ≤ v ≤ 7 , if x 0 = 0 x_0=0 x 0 = 0 then ( v − 1 ) H ≥ 4 m > p (v-1)H\ge4m>p ( v − 1 ) H ≥ 4 m > p . Otherwise L = N + v − x 0 ≤ H + v − x 0 L=N+v-x_0\le H+v-x_0 L = N + v − x 0 ≤ H + v − x 0 , and H + L ≥ p H+L\ge p H + L ≥ p gives
( v − 1 ) H − v x 0 ≥ v − 1 2 p − v 2 ≥ p ( p ≥ 37 ) . (v-1)H-vx_0\ge\frac{v-1}{2}p-v^2\ge p\qquad(p\ge37). ( v − 1 ) H − v x 0 ≥ 2 v − 1 p − v 2 ≥ p ( p ≥ 37 ) .
The interval has width at least 2 p − 1 2p-1 2 p − 1 , so it contains k p kp k p and ( k + 1 ) p (k+1)p ( k + 1 ) p for some integer k k k . The corresponding sums belong to Σ p ( S ) ∩ p G \Sigma_p(S)\cap pG Σ p ( S ) ∩ pG and differ by p d ≠ 0 pd\ne0 p d = 0 , contrary to (2.1). □ \square □
For the layers of S S S , list the multiplicities v i v_i v i in decreasing order, padding with zeros. In the expression b S = ∑ i ⌊ i / 2 ⌋ v i b_S=\sum_i\lfloor i/2\rfloor v_i b S = ∑ i ⌊ i /2 ⌋ v i , removing the four most frequent values decreases the weight of each v i v_i v i with i ≥ 4 i\ge4 i ≥ 4 by two and removes the contributions of v 2 v_2 v 2 and v 3 v_3 v 3 . Since v 1 = p − m v_1=p-m v 1 = p − m and ∑ i v i = 2 p \sum_i v_i=2p ∑ i v i = 2 p , it follows that
b S − ∑ j f ( max { 0 , s j − 4 } ) = v 2 + v 3 + 2 ∑ i ≥ 4 v i = 2 ( p + m ) − ( v 2 + v 3 ) . (12) b_S-\sum_j f(\max\{0,s_j-4\})=v_2+v_3+2\sum_{i\ge4}v_i=2(p+m)-(v_2+v_3). \tag*{(12)} b S − j ∑ f ( max { 0 , s j − 4 }) = v 2 + v 3 + 2 i ≥ 4 ∑ v i = 2 ( p + m ) − ( v 2 + v 3 ) . (12)
Lemma 4.5. Under the hypotheses of Lemma 4.4, let s = s 1 s=s_1 s = s 1 . Then s ≥ 4 s\ge4 s ≥ 4 and
f ( s − 4 ) ≤ p − 2 m − e − 3 , f ( s ) ≤ p − 2 m − e + 2 ( s − 4 ) + 1. f(s-4)\le p-2m-e-3,\qquad f(s)\le p-2m-e+2(s-4)+1. f ( s − 4 ) ≤ p − 2 m − e − 3 , f ( s ) ≤ p − 2 m − e + 2 ( s − 4 ) + 1. Assign weights 4 , 8 , 7 , 6 4,8,7,6 4 , 8 , 7 , 6 to layers of sizes 2 , 3 , 4 , 5 2,3,4,5 2 , 3 , 4 , 5 , respectively, other than the first layer. Let Φ \Phi Φ be their total weight. Then Φ ≥ − p + 9 m + 2 + 5 e \Phi\ge-p+9m+2+5e Φ ≥ − p + 9 m + 2 + 5 e . If p ≥ 23 p\ge23 p ≥ 23 , then Φ ≥ ( 5 p + 107 ) / 4 + 5 e \Phi\ge(5p+107)/4+5e Φ ≥ ( 5 p + 107 ) /4 + 5 e .
Proof. If s ≤ 3 s\le3 s ≤ 3 , then v 2 + v 3 = 2 p − v 1 ≥ p v_2+v_3=2p-v_1\ge p v 2 + v 3 = 2 p − v 1 ≥ p , contradicting Lemma 4.4. By Lemma 4.4, v 2 + v 3 ≤ p − 1 v_2+v_3\le p-1 v 2 + v 3 ≤ p − 1 . Using this in (4.1) and keeping only the first layer in the sum gives the first inequality. The second follows from f ( s ) − f ( s − 4 ) = 2 s − 4 f(s)-f(s-4)=2s-4 f ( s ) − f ( s − 4 ) = 2 s − 4 . Assign a layer of size u u u the weight w ( u ) = 9 ( u − 1 ) − 5 f ( u ) w(u)=9(u-1)-5f(u) w ( u ) = 9 ( u − 1 ) − 5 f ( u ) . This is zero for u = 1 u=1 u = 1 , takes the four stated values for u = 2 , 3 , 4 , 5 u=2,3,4,5 u = 2 , 3 , 4 , 5 , and is nonpositive for u ≥ 6 u\geq6 u ≥ 6 . Since ∑ j ( s j − 1 ) = p + m \sum_j(s_j-1)=p+m ∑ j ( s j − 1 ) = p + m , the total weight is
∑ j w ( s j ) = 9 ( p + m ) − 5 ( 2 p − 2 − e ) = − p + 9 m + 10 + 5 e . \sum_j w(s_j)=9(p+m)-5(2p-2-e)=-p+9m+10+5e. j ∑ w ( s j ) = 9 ( p + m ) − 5 ( 2 p − 2 − e ) = − p + 9 m + 10 + 5 e .
Removing the first layer costs at most eight. Discarding the remaining nonpositive weights gives Φ ≥ − p + 9 m + 2 + 5 e \Phi\geq-p+9m+2+5e Φ ≥ − p + 9 m + 2 + 5 e . For p ≥ 23 p\geq23 p ≥ 23 , substituting m > ( p + 11 ) / 4 m>(p+11)/4 m > ( p + 11 ) /4 gives Φ > ( 5 p + 107 ) / 4 + 5 e \Phi>(5p+107)/4+5e Φ > ( 5 p + 107 ) /4 + 5 e . □
Sumset growth and intervals from small layers
Retain the notation of Section 4 and assume (3.1). Suppose p ≥ 23 p\geq23 p ≥ 23 , m > ( p + 11 ) / 4 m>(p+11)/4 m > ( p + 11 ) /4 , and S S S is exceptional with e ≥ 1 e\geq1 e ≥ 1 . Lemma 4.5 gives e ≤ ( p − 19 ) / 2 e\leq(p-19)/2 e ≤ ( p − 19 ) /2 . Consider the nonfirst layers of sizes two through five. Layers of equal size have the same support. For each odd size, pair the available layers and round in opposite directions in each pair. We call such a pair a balanced pair. Balance the remaining odd layers to select p p p terms in total.
For a finite support U U U and k ∈ [ 0 , ∣ U ∣ ] k\in[0,|U|] k ∈ [ 0 , ∣ U ∣ ] , complementation gives
∑ ∣ U ∣ − k ( U ) = { ∑ x ∈ U x } − ∑ k ( U ) . (13) \sum_{|U|-k}(U)=\left\{\sum_{x\in U}x\right\}-\sum_k(U). \tag*{(13)} ∣ U ∣ − k ∑ ( U ) = { x ∈ U ∑ x } − k ∑ ( U ) . (13)
Thus the joint central sumset of two paired layers of size three is a translate of U − U U-U U − U . For two paired layers of size five it is a translate of X − X X-X X − X , where X = Σ 2 ( U ) X=\Sigma_2(U) X = Σ 2 ( U ) .
An integer model of a support U ⊆ G U\subseteq G U ⊆ G has the form U = { a + x d : x ∈ U Z } U=\{a+xd:x\in U_{\mathbb{Z}}\} U = { a + x d : x ∈ U Z } , where d d d is a unit and the coordinates in U Z ⊆ Z U_{\mathbb{Z}}\subseteq\mathbb{Z} U Z ⊆ Z are distinct modulo p 2 p^2 p 2 . For a nonempty integer set Y Y Y , let diam ( Y ) = max Y − min Y \operatorname{diam}(Y)=\max Y-\min Y diam ( Y ) = max Y − min Y . A group of layers provides an initial interval if its central sumset in G G G contains an interval in integer coordinates with a unit common difference. The width of that interval is its diameter. The truncation loss is the diameter of the full central sumset in those coordinates minus the width of the interval. The constructions below also give integer coordinates for the common support of the group.
Lemma 5.1. Let U ⊆ G U\subseteq G U ⊆ G have size four or five and set A = Σ 2 ( U ) A=\Sigma_2(U) A = Σ 2 ( U ) . If ∣ U ∣ = 4 |U|=4 ∣ U ∣ = 4 , assume p ≥ 37 p\geq37 p ≥ 37 and that π \pi π is injective on 4 A 4A 4 A . If ∣ U ∣ = 5 |U|=5 ∣ U ∣ = 5 , assume p ≥ 29 p\geq29 p ≥ 29 and that π \pi π is injective on A − A A-A A − A . Consider the expressions for elements of 4 A 4A 4 A in the first case and of A − A A-A A − A in the second. There is a rational affine model of U U U in which two such expressions are equal exactly when their values in G G G have the same image under π \pi π . If the model has affine dimension one, then U U U admits primitive integer coordinates with a unit common difference and with the same equalities.
Proof. In both cases a translate of A A A lies in the set on which π \pi π is injective. For two distinct elements of U U U , adjoining the same third element gives distinct elements of A A A . Thus π \pi π is injective on U U U and all differences of distinct elements of U U U are units. Set k = ∣ U ∣ k=|U| k = ∣ U ∣ and let U = { u 1 , … , u k } U=\{u_1,\ldots,u_k\} U = { u 1 , … , u k } . Let W = { 0 , e 1 , … , e k − 1 } W=\{0,e_1,\ldots,e_{k-1}\} W = { 0 , e 1 , … , e k − 1 } , where the e i e_i e i are the standard basis vectors of Z k − 1 \mathbb{Z}^{k-1} Z k − 1 . Define the additive homomorphism φ : Z k − 1 → G \varphi:\mathbb{Z}^{k-1}\to G φ : Z k − 1 → G by φ ( e i ) = u i + 1 − u 1 \varphi(e_i)=u_{i+1}-u_1 φ ( e i ) = u i + 1 − u 1 . For B = Σ 2 ( W ) B=\Sigma_2(W) B = Σ 2 ( W ) we have φ ( B ) = A − 2 u 1 \varphi(B)=A-2u_1 φ ( B ) = A − 2 u 1 . Take Z = 4 B Z=4B Z = 4 B when k = 4 k=4 k = 4 and Z = B − B Z=B-B Z = B − B when k = 5 k=5 k = 5 . Thus φ ( Z ) = 4 A − 8 u 1 \varphi(Z)=4A-8u_1 φ ( Z ) = 4 A − 8 u 1 or A − A A-A A − A , respectively. Let
L = span Q { v ∈ Z − Z : π ( φ ( v ) ) = 0 } . L=\operatorname{span}_{\mathbb{Q}}\{v\in Z-Z:\pi(\varphi(v))=0\}. L = span Q { v ∈ Z − Z : π ( φ ( v )) = 0 } .
For each generating relation v = z − z ′ v=z-z' v = z − z ′ with z , z ′ ∈ Z z,z'\in Z z , z ′ ∈ Z , injectivity on φ ( Z ) \varphi(Z) φ ( Z ) gives φ ( z ) = φ ( z ′ ) \varphi(z)=\varphi(z') φ ( z ) = φ ( z ′ ) . Thus φ ( v ) = 0 \varphi(v)=0 φ ( v ) = 0 . For the norm estimates, append − ∑ i = 1 k − 1 v i -\sum_{i=1}^{k-1}v_i − ∑ i = 1 k − 1 v i to each relation vector v v v so that its k k k coordinates sum to zero. For k = 4 k=4 k = 4 , each absolute coordinate is at most 4 and the sums of the positive and absolute negative coordinates are at most 8, so the Euclidean norm is at most 8. For k = 5 k=5 k = 5 the respective bounds are 2, 4, and 4.
Let M M M be an integer matrix with k − 1 k-1 k − 1 such relations as rows. Reducing its entries modulo p 2 p^2 p 2 , we see that M M M annihilates the column vector of support differences in G G G . The adjugate identity then gives ( det M ) ⋅ ( u i − u 1 ) = 0 (\det M) \cdot(u_i-u_1)=0 ( det M ) ⋅ ( u i − u 1 ) = 0 in G G G for 2 ≤ i ≤ k 2\le i\le k 2 ≤ i ≤ k . Each u i − u 1 u_i-u_1 u i − u 1 is a unit, so p 2 ∣ det M p^2\mid\det M p 2 ∣ det M . Hadamard’s inequality gives
∣ det M ∣ ≤ { 8 3 , k = 4 , 4 4 , k = 5 , ∣ det M ∣ < p 2 . |\det M|\le
\begin{cases}
8^3, & k=4,\\
4^4, & k=5,
\end{cases}
\qquad|\det M|<p^2. ∣ det M ∣ ≤ { 8 3 , 4 4 , k = 4 , k = 5 , ∣ det M ∣ < p 2 .
Thus dim L ≤ k − 2 \dim L\le k-2 dim L ≤ k − 2 . If L ≠ { 0 } L\ne\{0\} L = { 0 } , choose a basis from the relation vectors. For k = 4 k=4 k = 4 , the minors of order at most two have absolute value at most 32 < p 32<p 32 < p . For k = 5 k=5 k = 5 , a minor of order three has absolute value at most 32 32 32 , since the maximum over [ − 2 , 2 ] 9 [-2,2]^9 [ − 2 , 2 ] 9 is attained at a vertex and a 3 × 3 3\times3 3 × 3 sign matrix has determinant divisible by 4 4 4 and of absolute value less than 8 8 8 . If such a minor is odd, each row has an odd entry and norm at most 3 3 3 , so its absolute value is at most 27 < p 27<p 27 < p . Minors of orders one and two have absolute value at most 8 8 8 . For k = 5 k=5 k = 5 , a nonzero minor of absolute value at most 32 < 2 p 32<2p 32 < 2 p divisible by p p p would have to be ± p \pm p ± p , contrary to the bound for odd minors. Hence a nonzero minor of full rank is a unit modulo p 2 p^2 p 2 .
If L = { 0 } L=\{0\} L = { 0 } , then every v ∈ ( Z − Z ) ∩ L v\in(\mathbb{Z}-\mathbb{Z})\cap L v ∈ ( Z − Z ) ∩ L evaluates to zero. Otherwise, multiplying such a vector by the determinant of the chosen minor clears the denominators in its expansion in the basis. Each basis relation vanishes under φ \varphi φ , and the determinant is a unit modulo p 2 p^2 p 2 , so φ ( v ) = 0 \varphi(v)=0 φ ( v ) = 0 . Conversely, any v ∈ Z − Z v\in Z-Z v ∈ Z − Z with π ( φ ( v ) ) = 0 \pi(\varphi(v))=0 π ( φ ( v )) = 0 belongs to L L L by definition. Thus for all z , z ′ ∈ Z z,z'\in Z z , z ′ ∈ Z ,
z − z ′ ∈ L ⟺ π ( φ ( z ) ) = π ( φ ( z ′ ) ) . z-z'\in L\quad\Longleftrightarrow\quad\pi(\varphi(z))=\pi(\varphi(z')). z − z ′ ∈ L ⟺ π ( φ ( z )) = π ( φ ( z ′ )) .
Thus the quotient Q k − 1 / L \mathbb{Q}^{k-1}/L Q k − 1 / L gives the required model. Translations into Z Z Z also preserve the equalities in B B B , and in 2 B 2B 2 B when k = 4 k=4 k = 4 . If the quotient has dimension one, the integer kernel of the matrix whose rows are the chosen basis relations is generated by a primitive vector n n n . The free coordinate of n n n is, up to sign, the invertible minor divided by the greatest common divisor of the maximal minors, so it is a unit modulo p 2 p^2 p 2 . Elimination over G = Z / p 2 Z G=\mathbb{Z}/p^2\mathbb{Z} G = Z / p 2 Z then gives
( u 2 − u 1 , … , u k − u 1 ) = d n , (u_2-u_1,\ldots,u_k-u_1)=dn, ( u 2 − u 1 , … , u k − u 1 ) = d n ,
where d ∈ G d\in G d ∈ G multiplies each integer coordinate of $n. The free coordinate of the support-difference vector is a unit, so d d d is a unit. This gives the required integer coordinates. □
For any finite set U U U and 1 ≤ k < ∣ U ∣ 1\le k<|U| 1 ≤ k < ∣ U ∣ , we have
U − U ⊆ Σ k ( U ) − Σ k ( U ) . (14) U-U\subseteq\Sigma_k(U)-\Sigma_k(U). \tag*{(14)} U − U ⊆ Σ k ( U ) − Σ k ( U ) . (14)
Indeed, to express u − u ′ u-u' u − u ′ for u ≠ u ′ u\ne u' u = u ′ , adjoin the same k − 1 k-1 k − 1 elements of U ∖ { u , u ′ } U\setminus\{u,u'\} U ∖ { u , u ′ } to u u u and u ′ u' u ′ . In primitive integer coordinates, take Y = Σ 2 ( U Z ) Y=\Sigma_2(U_Z) Y = Σ 2 ( U Z ) or Y = 2 Σ 2 ( U Z ) Y=2\Sigma_2(U_Z) Y = 2 Σ 2 ( U Z ) . In both cases the differences in Y − Y Y-Y Y − Y have greatest common divisor 1 1 1 , since they include the support differences by (14) . For the twofold sumset, this inclusion follows by adding a common summand to both terms of each difference. Translate Y Y Y and − Y -Y − Y separately to have minimum zero. They have equal diameters and cardinalities, so the parameter in the following bound of Lev and Smelianski [7 Lemma 1] is δ = 1 \delta=1 δ = 1 .
∣ Y − Y ∣ ≥ ∣ Y ∣ + min { diam ( Y ) , 2 ∣ Y ∣ − 3 } . (15) |Y-Y|\ge|Y|+\min\{\operatorname{diam}(Y),2|Y|-3\}. \tag*{(15)} ∣ Y − Y ∣ ≥ ∣ Y ∣ + min { diam ( Y ) , 2∣ Y ∣ − 3 } . (15)
If the rational model has dimension at least two, then either of the corresponding sumsets Y Y Y in that model satisfies
∣ Y − Y ∣ ≥ 3 ∣ Y ∣ − 3. (16) |Y-Y|\ge3|Y|-3. \tag*{(16)} ∣ Y − Y ∣ ≥ 3∣ Y ∣ − 3. (16)
By (14) , the support differences belong to Y − Y Y-Y Y − Y . A generic linear projection to the plane preserves the cardinality of Y Y Y and gives a two-dimensional set, so Ruzsa’s bound [8 Corollary 1.1] gives (16) .
Lemma 5.2. Either one of the constructions below gives an initial interval, or none applies. If an interval is available, choose one with the largest support size q ∈ [ 2 , 5 ] q\in[2,5] q ∈ [ 2 , 5 ] . Its width is at least both the sum of the contributions f ( s j ) f(s_j) f ( s j ) of its layers and the integer diameter of its support. It uses at most four layers, whose total contribution is at most 12. The truncation loss is at most 12, and at most 8 if p ≤ 31 p\le31 p ≤ 31 . Every layer other than the first of size in [ 2 , q ] [2,q] [ 2 , q ] can be written in
integer coordinates with the same unit common difference. The gaps between successive central sums in such a layer are at most the width of the initial interval.
Call all nonfirst layers of sizes in [ 2 , q ] [2,q] [ 2 , q ] aligned, including those used for the initial interval. If no construction applies, there are no aligned layers. The remaining nonfirst layers of sizes two through five can be partitioned into full groups and leftover layers as follows. For each full group with layer index set J J J , we have ∣ π ( Y J ) ∣ ≥ b + g + 1 |\pi(Y_J)| \ge b+g+1 ∣ π ( Y J ) ∣ ≥ b + g + 1 , where b = ∑ j ∈ J f ( s j ) b=\sum_{j\in J}f(s_j) b = ∑ j ∈ J f ( s j ) and g g g is given in the table below.
Table 2.
No unaligned layer has size two. Each full group satisfies b ≤ g b \le g b ≤ g and has total weight at most 16 g / 5 16g/5 16 g /5 . The leftover layers have total weight at most 51.
Proof. We first record how to lift progressions and their differences. If π \pi π is injective on A + A A+A A + A for A ⊆ G A\subseteq G A ⊆ G , then π ( a − a ′ ) = π ( b − b ′ ) \pi(a-a')=\pi(b-b') π ( a − a ′ ) = π ( b − b ′ ) implies π ( a + b ′ ) = π ( b + a ′ ) \pi(a+b')=\pi(b+a') π ( a + b ′ ) = π ( b + a ′ ) , so a − a ′ = b − b ′ a-a'=b-b' a − a ′ = b − b ′ . Thus injectivity on A + A A+A A + A implies injectivity on A − A A-A A − A . If π \pi π is injective on A − A A-A A − A , it is injective on A A A as well. Hence an arithmetic progression π ( A ) \pi(A) π ( A ) lifts to an arithmetic progression A A A by equality of successive differences.
If A = Σ 2 ( U ) A=\Sigma_2(U) A = Σ 2 ( U ) has integer coordinates of diameter L ≤ 16 L\le16 L ≤ 16 with unit common difference d d d , fix u 0 ∈ U u_0\in U u 0 ∈ U and choose x u ∈ [ − L , L ] x_u\in[-L,L] x u ∈ [ − L , L ] with u − u 0 = x u d u-u_0=x_ud u − u 0 = x u d for each u ∈ U u\in U u ∈ U , using (14) . Since u − v ∈ A − A u-v\in A-A u − v ∈ A − A , the difference x u − x v x_u-x_v x u − x v is congruent modulo p 2 p^2 p 2 to an integer in [ − L , L ] [-L,L] [ − L , L ] . As 3 L < p 2 3L<p^2 3 L < p 2 , these integers are equal. Thus the coordinates x u x_u x u give U U U diameter at most L L L .
The groups below use at most four layers of size four, four of size three, or two of size five. Their total contribution is at most 16, and p − e − 1 ≥ ( p + 17 ) / 2 ≥ 20 p-e-1\ge(p+17)/2\ge20 p − e − 1 ≥ ( p + 17 ) /2 ≥ 20 . Hence Lemma 4.2 gives injectivity of π \pi π on their joint central sumsets.
We now consider each layer size separately.
Case 1. Layers of size two. A two-element layer gives an interval of width 1.
Case 2. Layers of size three. Let U U U be the three-element support and let π ( U ) = { a 1 , a 2 , a 3 } \pi(U)=\{a_1,a_2,a_3\} π ( U ) = { a 1 , a 2 , a 3 } . To distinguish the supports that give an interval from those that give growth, consider 2 π ( U ) − 2 π ( U ) 2\pi(U)-2\pi(U) 2 π ( U ) − 2 π ( U ) . The difference ( c 1 , c 2 , c 3 ) (c_1,c_2,c_3) ( c 1 , c 2 , c 3 ) of two distinct coefficient vectors with the same sum in C p \mathbb{C}_p C p satisfies
∑ i = 1 3 c i = 0 , ∑ c i > 0 c i ≤ 4 , ∑ i = 1 3 c i a i = 0. \sum_{i=1}^{3}c_i=0,\qquad\sum_{c_i>0}c_i\le4,\qquad\sum_{i=1}^{3}c_i a_i=0. i = 1 ∑ 3 c i = 0 , c i > 0 ∑ c i ≤ 4 , i = 1 ∑ 3 c i a i = 0.
If one coordinate were zero, the other two would give a nonzero integer multiple of some a i − a j a_i-a_j a i − a j equal to zero, with coefficient of absolute value at most 4 < p 4<p 4 < p . Thus all three coordinates are nonzero. Up to permutation and sign the possibilities are
( 1 , 1 , − 2 ) , ( 1 , 2 , − 3 ) , ( 1 , 3 , − 4 ) , ( 2 , 2 , − 4 ) . (1,1,-2),\qquad(1,2,-3),\qquad(1,3,-4),\qquad(2,2,-4). ( 1 , 1 , − 2 ) , ( 1 , 2 , − 3 ) , ( 1 , 3 , − 4 ) , ( 2 , 2 , − 4 ) .
Thus a collision requires π ( U ) \pi(U) π ( U ) to be a translate of { 0 , g , r g } \{0,g,rg\} { 0 , g , r g } in C p \mathbb{C}_p C p for some g ≠ 0 g\ne0 g = 0 and r ∈ { 2 , 3 , 4 } r\in\{2,3,4\} r ∈ { 2 , 3 , 4 } .
Case 2.1. π ( U ) \pi(U) π ( U ) is a translate of { 0 , g , r g } \{0,g,rg\} { 0 , g , r g } for some g ≠ 0 g\ne0 g = 0 and r ∈ { 2 , 3 , 4 } r\in\{2,3,4\} r ∈ { 2 , 3 , 4 } . Let u 0 , u 1 , u r u_0,u_1,u_r u 0 , u 1 , u r denote the support values whose images have coordinates 0 , 1 , r 0,1,r 0 , 1 , r in this normalization. The relation
r u ‾ 1 = ( r − 1 ) u ‾ 0 + u ‾ r r\overline{u}_1=(r-1)\overline{u}_0+\overline{u}_r r u 1 = ( r − 1 ) u 0 + u r
lifts to G G G by Lemma 4.3 whenever at least r r r copies of each value are available, counting the first layer. Indeed, r ≤ 4 ≤ ⌊ ( m + 1 ) / 2 ⌋ r\le4\le\lfloor(m+1)/2\rfloor r ≤ 4 ≤ ⌊( m + 1 ) /2 ⌋ . The lifted relation gives u r = u 0 + r ( u 1 − u 0 ) u_r=u_0+r(u_1-u_0) u r = u 0 + r ( u 1 − u 0 ) , so the support has integer coordinates { 0 , 1 , r } \{0,1,r\} { 0 , 1 , r } with common difference u 1 − u 0 u_1-u_0 u 1 − u 0 . For r = 2 r=2 r = 2 one layer gives [ 0 , 2 ] [0,2] [ 0 , 2 ] up to translation. For r = 3 r=3 r = 3 one balanced pair gives a translate of [ − 3 , 3 ] [-3,3] [ − 3 , 3 ] by (13) .
The table records the layer counts and widths.
Table 3.
For r = 4 r=4 r = 4 , the width follows from
( { 0 , 1 , 4 } − { 0 , 1 , 4 } ) + ( { 0 , 1 , 4 } − { 0 , 1 , 4 } ) = [ − 8 , 8 ] , (\{0,1,4\}-\{0,1,4\})+(\{0,1,4\}-\{0,1,4\})=[-8,8], ({ 0 , 1 , 4 } − { 0 , 1 , 4 }) + ({ 0 , 1 , 4 } − { 0 , 1 , 4 }) = [ − 8 , 8 ] ,
since each difference set is { 0 , ± 1 , ± 3 , ± 4 } \{0,\pm1,\pm3,\pm4\} { 0 , ± 1 , ± 3 , ± 4 } . If there are too few layers for the construction, at most three remain.
Case 2.2. All other three-element supports. A full group in this case needs four nonfirst layers of size three. When four are available, use two balanced pairs. The image under π \pi π of their joint central sumset is a translate of 2 π ( U ) − 2 π ( U ) 2\pi(U)-2\pi(U) 2 π ( U ) − 2 π ( U ) . Its coefficient vectors have coordinate sum zero and positive coordinates summing to at most 2. The counts for positive sums 0, 1, 2 are 1, 6, 12. The classification above excludes collisions, so ∣ 2 π ( U ) − 2 π ( U ) ∣ = 1 + 6 + 12 = 19 |2\pi(U)-2\pi(U)|=1+6+12=19 ∣2 π ( U ) − 2 π ( U ) ∣ = 1 + 6 + 12 = 19 .
Case 3. Layers of size four. If there are fewer than four nonfirst layers of size four, leave them as leftovers. Otherwise let U U U be their common support and set A = Σ 2 ( U ) A=\Sigma_2(U) A = Σ 2 ( U ) and X = π ( A ) X=\pi(A) X = π ( A ) . Two distinct pairs with equal sums under π \pi π are disjoint, since the images of the support values are distinct. Two distinct complementary pairing equalities would force two support images to coincide because p p p is odd. Thus ∣ X ∣ = 5 |X|=5 ∣ X ∣ = 5 or 6. Complementary pairs show that A A A and X X X are centrally symmetric. Since a translate of A A A is contained in 4 A 4A 4 A , π \pi π is injective on A A A . Centering X X X shows that 4 X 4X 4 X is symmetric and contains its center, so ∣ 4 X ∣ |4X| ∣4 X ∣ is odd. If ∣ 4 X ∣ ≥ 33 |4X|\ge33 ∣4 X ∣ ≥ 33 , the four layers give the desired growth. We may therefore assume ∣ 4 X ∣ ≤ 31 |4X|\le31 ∣4 X ∣ ≤ 31 .
Case 3.1. ∣ X ∣ = 5 |X|=5 ∣ X ∣ = 5 . The set A A A also has five points and contains its center. Translate it to A = { 0 , ± u , ± v } A=\{0,\pm u,\pm v\} A = { 0 , ± u , ± v } . The 41 integer pairs with ∣ i ∣ + ∣ j ∣ ≤ 4 |i|+|j|\le4 ∣ i ∣ + ∣ j ∣ ≤ 4 give at most 31 distinct values i u + j v iu+jv i u + j v in C p C_p C p . Subtracting two pairs that give the same value yields a nonzero relation i u + j v = 0 iu+jv=0 i u + j v = 0 with ∣ i ∣ + ∣ j ∣ ≤ 8 |i|+|j|\le8 ∣ i ∣ + ∣ j ∣ ≤ 8 . Both coefficients are nonzero because u , v ≠ 0 u,v\ne0 u , v = 0 and 8 < p 8<p 8 < p . Injectivity on 4 A 4A 4 A lifts the equality of the two values to G G G , giving i u + j v = 0 iu+jv=0 i u + j v = 0 . Cancelling the common divisor of i , j i,j i , j and interchanging or negating generators as needed gives u = a d u=ad u = a d , v = b d v=bd v = b d with a unit d d d , 1 ≤ a < b 1\le a<b 1 ≤ a < b , gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1 , and a + b ≤ 8 a+b\le8 a + b ≤ 8 . The integer fourfold sumset is { a i + b j : ∣ i ∣ + ∣ j ∣ ≤ 4 } \{ai+bj:|i|+|j|\le4\} { ai + bj : ∣ i ∣ + ∣ j ∣ ≤ 4 } . Its diameter is at most 56 < p 2 56<p^2 56 < p 2 , so multiplication by d d d maps it injectively into G G G . By injectivity of π \pi π on 4 A 4A 4 A , its cardinality is ∣ 4 X ∣ |4X| ∣4 X ∣ . The cases with ∣ 4 X ∣ ≤ 31 |4X|\le31 ∣4 X ∣ ≤ 31 are listed below.
Table 4.
The other ratios are ( 1 , b ) (1,b) ( 1 , b ) for 5 ≤ b ≤ 7 5\le b\le7 5 ≤ b ≤ 7 , and ( 2 , 5 ) (2,5) ( 2 , 5 ) , ( 3 , 4 ) (3,4) ( 3 , 4 ) , ( 3 , 5 ) (3,5) ( 3 , 5 ) . The same formula gives 33, 37, 39, 35, 33, 37 points, respectively. Each interval in the table has width at least the diameter of A A A , hence at least that of U U U .
Case 3.2. ∣ X ∣ = 6 |X|=6 ∣ X ∣ = 6 . If p ≤ 31 p\le31 p ≤ 31 , then Lemma 4.2 gives ∣ 4 X ∣ ≤ 17 + ϵ |4X|\le17+\epsilon ∣4 X ∣ ≤ 17 + ϵ , whereas
∣ 2 X ∣ ≥ 13 ⟹ ∣ 4 X ∣ ≥ min { p , 25 } > 17 + ϵ . |2X|\ge13 \quad\Longrightarrow\quad|4X|\ge\min\{p,25\}>17+\epsilon. ∣2 X ∣ ≥ 13 ⟹ ∣4 X ∣ ≥ min { p , 25 } > 17 + ϵ .
Thus ∣ 2 X ∣ = 11 |2X|=11 ∣2 X ∣ = 11 , since Lemma 2.1 gives ∣ 2 X ∣ ≥ 11 |2X|\ge11 ∣2 X ∣ ≥ 11 and symmetry makes ∣ 2 X ∣ |2X| ∣2 X ∣ odd. For p ≥ 37 p\ge37 p ≥ 37 , Lemma 2.1 and ∣ 4 X ∣ ≤ 31 |4X|\le31 ∣4 X ∣ ≤ 31 give 11 ≤ ∣ 2 X ∣ ≤ 16 11\le|2X|\le16 11 ≤ ∣2 X ∣ ≤ 16 , so ∣ 2 X ∣ ∈ { 11 , 13 , 15 } |2X|\in\{11,13,15\} ∣2 X ∣ ∈ { 11 , 13 , 15 } .
Case 3.2.1. ∣ 2 X ∣ = 11 |2X|=11 ∣2 X ∣ = 11 . Vosper's theorem in the form (2.3) makes X X X a six-term arithmetic progression, which lifts to a one-layer interval.
Case 3.2.2. ∣ 2 X ∣ ∈ { 13 , 15 } |2X|\in\{13,15\} ∣2 X ∣ ∈ { 13 , 15 } . Here p ≥ 37 p\ge37 p ≥ 37 . Lemma 5.1 gives a rational model preserving the cardinalities of X X X , 2 X 2X 2 X , and 4 X 4X 4 X . By (5.1), the models of X X X and 2 X 2X 2 X are centrally symmetric, so their twofold sumsets are translates of their difference sets. If the model has dimension at least two, (5.4) gives ∣ 2 X ∣ ≥ 3 ∣ X ∣ − 3 = 15 |2X| \ge3|X| - 3 = 15 ∣2 X ∣ ≥ 3∣ X ∣ − 3 = 15 , excluding ∣ 2 X ∣ = 13 |2X| = 13 ∣2 X ∣ = 13 . Applying (5.4) to the model of 2 X 2X 2 X then gives ∣ 4 X ∣ ≥ 3 ∣ 2 X ∣ − 3 = 42 |4X| \ge3|2X| - 3 = 42 ∣4 X ∣ ≥ 3∣2 X ∣ − 3 = 42 , again a contradiction. Thus the model has dimension one. Let A Z = Σ 2 ( U Z ) A_Z = \Sigma_2(U_Z) A Z = Σ 2 ( U Z ) in the primitive integer coordinates of Lemma 5.1. Then ∣ A Z ∣ = ∣ X ∣ |A_Z| = |X| ∣ A Z ∣ = ∣ X ∣ , ∣ 2 A Z ∣ = ∣ 2 X ∣ |2A_Z| = |2X| ∣2 A Z ∣ = ∣2 X ∣ , and ∣ 4 A Z ∣ = ∣ 4 X ∣ |4A_Z| = |4X| ∣4 A Z ∣ = ∣4 X ∣ .
If ∣ 2 X ∣ = 13 |2X| = 13 ∣2 X ∣ = 13 , then (5.3) bounds the diameter of A Z A_Z A Z by 7. Apart from an arithmetic progression, a six-point symmetric set of diameter at most 7 is, up to translation, [ 0 , 6 ] ∖ { 3 } [0,6] \setminus\{3\} [ 0 , 6 ] ∖ { 3 } or is obtained from [ 0 , 7 ] [0,7] [ 0 , 7 ] by deleting a symmetric pair. Deleting { 2 , 5 } \{2,5\} { 2 , 5 } or { 3 , 4 } \{3,4\} { 3 , 4 } gives a twofold sumset of size 15, leaving only [ 0 , 7 ] ∖ { 1 , 6 } [0,7] \setminus\{1,6\} [ 0 , 7 ] ∖ { 1 , 6 } . The two remaining shapes give intervals [ 0 , 12 ] [0,12] [ 0 , 12 ] and [ 2 , 12 ] [2,12] [ 2 , 12 ] using two layers, with losses 0 and 4.
If ∣ 2 X ∣ = 15 |2X| = 15 ∣2 X ∣ = 15 , the diameter of 2 A Z 2A_Z 2 A Z is at least 14 and at most 16 by (5.3). Since it equals twice the diameter of A Z A_Z A Z , it is 14 or 16. Translate A Z A_Z A Z so that its minimum is zero. If the diameter of 2 A Z 2A_Z 2 A Z is 14, then 2 A Z = [ 0 , 14 ] 2A_Z = [0,14] 2 A Z = [ 0 , 14 ] . If it is 16, then symmetry gives 2 A Z = [ 0 , 16 ] ∖ { j , 16 − j } 2A_Z = [0,16] \setminus\{j, 16-j\} 2 A Z = [ 0 , 16 ] ∖ { j , 16 − j } with 1 ≤ j < 8 1 \le j < 8 1 ≤ j < 8 . If j ≥ 2 j \ge2 j ≥ 2 , the two omitted points equal 1 + ( j − 1 ) 1+(j-1) 1 + ( j − 1 ) and 1 + ( 15 − j ) 1+(15-j) 1 + ( 15 − j ) , respectively, with both summands in 2 A Z 2A_Z 2 A Z . The other points of [ 0 , 16 ] [0,16] [ 0 , 16 ] are sums with zero. Symmetry then gives [ 0 , 32 ] ⊆ 4 A Z [0,32] \subseteq4A_Z [ 0 , 32 ] ⊆ 4 A Z , contrary to ∣ 4 X ∣ ≤ 31 |4X| \le31 ∣4 X ∣ ≤ 31 . Thus j = 1 j = 1 j = 1 . The respective two-layer intervals are [ 0 , 14 ] [0,14] [ 0 , 14 ] and [ 2 , 14 ] [2,14] [ 2 , 14 ] , with losses 0 and 4. Their widths are at least the diameter of A Z A_Z A Z and therefore of U Z U_Z U Z .
Case 4. Layers of size five. If there are fewer than two nonfirst layers of size five, leave any such layer as a leftover. Otherwise take a balanced pair with common support U U U , and set X = π ( Σ 2 ( U ) ) X = \pi(\Sigma_2(U)) X = π ( Σ 2 ( U )) and D = X − X D = X-X D = X − X . Since D = − D D=-D D = − D and 0 ∈ D 0 \in D 0 ∈ D , its cardinality is odd. For p ≤ 31 p \le31 p ≤ 31 , the local bound gives ∣ D ∣ ≤ 13 + ϵ ≤ 19 |D| \le13+\epsilon\le19 ∣ D ∣ ≤ 13 + ϵ ≤ 19 .
Case 4.1. ∣ D ∣ ≥ 25 |D| \ge25 ∣ D ∣ ≥ 25 . The pair provides the stated growth with b = g = 12 b=g=12 b = g = 12 .
Case 4.2. ∣ D ∣ ≤ 23. ∗ L e t |D| \le23.* Let ∣ D ∣ ≤ 23. ∗ L e t X^ = \Sigma_2(U)$ and D ∗ = X ∗ − X ∗ D^* = X^* - X^* D ∗ = X ∗ − X ∗ . The joint central sumset of the balanced pair is a translate of D ∗ D^* D ∗ , so Lemma 4.2 gives injectivity on D ∗ D^* D ∗ and hence on X ∗ X^* X ∗ , a translate of which lies in D ∗ D^* D ∗ . We show that U U U admits integer coordinates with a unit common difference and that the difference set D Z = Σ 2 ( U Z ) − Σ 2 ( U Z ) D_Z = \Sigma_2(U_Z) - \Sigma_2(U_Z) D Z = Σ 2 ( U Z ) − Σ 2 ( U Z ) satisfies the following bounds for some integer a 0 a_0 a 0 .
[ − a 0 , a 0 ] ⊆ D Z ⊆ [ − h 0 , h 0 ] , a 0 ≥ 6 , 2 a 0 ≥ diam ( U Z ) , h 0 − a 0 ≤ 6 , (17) [-a_0,a_0] \subseteq D_Z \subseteq[-h_0,h_0], \qquad a_0 \ge6, \qquad2a_0 \ge\operatorname{diam}(U_Z), \qquad h_0-a_0 \le6, \tag*{(17)} [ − a 0 , a 0 ] ⊆ D Z ⊆ [ − h 0 , h 0 ] , a 0 ≥ 6 , 2 a 0 ≥ diam ( U Z ) , h 0 − a 0 ≤ 6 , (17)
where h 0 = max D Z h_0 = \max D_Z h 0 = max D Z .
Case 4.2.1. ∣ X ∣ ≤ 8 |X| \le8 ∣ X ∣ ≤ 8 . The ten unordered pairs from U U U give at most eight projected sums in C p C_p C p . Since π \pi π is injective on X ∗ X^* X ∗ , equal projected sums are equal in G G G . Distinct pairs with equal sums are disjoint, and no three pairs are pairwise disjoint. Thus there are at least two pairing equalities in G G G . Each four-element subset gives at most one such equality. Indeed, two different pairing equalities would force two values to coincide, since 2 is a unit in G G G . Choose two such subsets sharing three values x , y , z x,y,z x , y , z . Each fourth value is among x + y − z x+y-z x + y − z , x + z − y x+z-y x + z − y , and y + z − x y+z-x y + z − x . Relabel the shared values so that the fourth values are x + y − z x+y-z x + y − z and x + z − y x+z-y x + z − y . For u = x − z u=x-z u = x − z and v = y − z v=y-z v = y − z we obtain
U − z = { 0 , v , u , u + v , u − v } , u ‾ , v ‾ ≠ 0. U-z=\{0,v,u,u+v,u-v\}, \qquad\overline{u},\overline{v}\ne0. U − z = { 0 , v , u , u + v , u − v } , u , v = 0.
To count the formal sums before evaluation in G G G , use integer coefficient pairs for u , v u,v u , v . The formal pair sums have v v v -coefficients { 1 } \{1\} { 1 } , [ − 1 , 2 ] [-1,2] [ − 1 , 2 ] , and [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] in the rows with u u u -coefficients 0, 1, 2, respectively. Subtracting these rows gives the following rows of the formal difference set with nonnegative u u u -coefficient. The other rows follow by negation.
Table 5.
The formal difference set has 7 + 2 ( 6 + 3 ) = 25 7+2(6+3)=25 7 + 2 ( 6 + 3 ) = 25 points. The differences in any one row have distinct images under π \pi π . Since ∣ D ∣ ≤ 23 |D| \le23 ∣ D ∣ ≤ 23 , two points in different rows have the same image, giving j u ‾ = i v ‾ j\overline{u}=i\overline{v} j u = i v , where the possible i i i are as follows.
Table 6.
For example, the rows with coefficients 0, 1 give [ − 3 , 3 ] − [ − 3 , 2 ] = [ − 5 , 6 ] [-3,3]-[-3,2]=[-5,6] [ − 3 , 3 ] − [ − 3 , 2 ] = [ − 5 , 6 ] , which contains the intervals from all other pairs of adjacent rows. The other ranges follow by the same subtraction.
Injectivity on D ∗ D^{*} D ∗ gives j u = i v ju=iv j u = i v in G G G . Let b / a = i / j b/a=i/j b / a = i / j in lowest terms with a > 0 a>0 a > 0 . Since a ≤ j ≤ 4 < p a\leq j\leq4<p a ≤ j ≤ 4 < p , there is a unique unit d ∈ G d\in G d ∈ G with a d = v ad=v a d = v . Now j ( u − b d ) = 0 j(u-bd)=0 j ( u − b d ) = 0 , so u = b d u=bd u = b d since j < p j<p j < p . Reflection by t ↦ v − t t\mapsto v-t t ↦ v − t replaces b / a b/a b / a by 1 − b / a 1-b/a 1 − b / a , so assume b / a ≥ 1 / 2 b/a\geq1/2 b / a ≥ 1/2 . To justify using the same ranges after reflection, note that before reflection we have a ≤ 4 a\leq4 a ≤ 4 and ∣ b ∣ ≤ 6 |b|\leq6 ∣ b ∣ ≤ 6 . The integer values of the formal differences have absolute value at most 24. As 48 < p 2 48<p^{2} 48 < p 2 , two such values are equal exactly when the corresponding differences in G G G are equal. By injectivity on D ∗ D^{*} D ∗ , this is also equivalent to equality after reduction modulo p p p . Reflection preserves the integer difference set. After reflection two distinct rows still give the same image, so the reflected ratio also comes from the four ranges above.
Distinctness excludes b / a ∈ { − 1 , 0 , 1 , 2 } b/a\in\{-1,0,1,2\} b / a ∈ { − 1 , 0 , 1 , 2 } . The table gives the remaining ratios, with outer radii and omissions obtained from
D Z = a [ − 3 , 3 ] ∪ ± ( b + a [ − 3 , 2 ] ) ∪ ± ( 2 b + a [ − 2 , 0 ] ) . D_Z=a[-3,3]\cup\pm(b+a[-3,2])\cup\pm(2b+a[-2,0]). D Z = a [ − 3 , 3 ] ∪ ± ( b + a [ − 3 , 2 ]) ∪ ± ( 2 b + a [ − 2 , 0 ]) .
Here a [ I ] = { a i : i ∈ I } a[I]=\{ai:i\in I\} a [ I ] = { ai : i ∈ I } .
Table 7.
The inner radius is at least 6 and h 0 − a 0 ≤ 4 h_0-a_0\leq4 h 0 − a 0 ≤ 4 . By (14) , diam ( U Z ) ≤ h 0 ≤ 12 \operatorname{diam}(U_Z)\leq h_0\leq12 diam ( U Z ) ≤ h 0 ≤ 12 . This proves (17) .
Case 4.2.2. ∣ X ∣ ≥ 9 |X|\geq9 ∣ X ∣ ≥ 9 . Here p ≥ 29 p\geq29 p ≥ 29 , since for p = 23 p=23 p = 23 the bound in Lemma 4.2 gives ∣ D ∣ ≤ 15 |D|\leq15 ∣ D ∣ ≤ 15 , whereas Lemma 2.1 gives ∣ D ∣ ≥ 17 |D|\geq17 ∣ D ∣ ≥ 17 . By Lemma 5.1 and (16) , a rational model of dimension at least two would give ∣ D ∣ ≥ 3 ∣ X ∣ − 3 ≥ 24 |D|\geq3|X|-3\geq24 ∣ D ∣ ≥ 3∣ X ∣ − 3 ≥ 24 . Thus we may take Y = Σ 2 ( U Z ) Y=\Sigma_2(U_Z) Y = Σ 2 ( U Z ) in the primitive integer model, where ∣ Y ∣ = ∣ X ∣ |Y|=|X| ∣ Y ∣ = ∣ X ∣ and ∣ Y − Y ∣ = ∣ D ∣ |Y-Y|=|D| ∣ Y − Y ∣ = ∣ D ∣ . Since ∣ D ∣ − ∣ X ∣ ≤ 14 < 2 ∣ X ∣ − 3 |D|-|X|\leq14<2|X|-3 ∣ D ∣ − ∣ X ∣ ≤ 14 < 2∣ X ∣ − 3 , (15) gives h 0 = diam ( Y ) ≤ ∣ D ∣ − ∣ X ∣ ≤ 14 h_0=\operatorname{diam}(Y)\leq|D|-|X|\leq14 h 0 = diam ( Y ) ≤ ∣ D ∣ − ∣ X ∣ ≤ 14 .
We show that [ 1 , max { 6 , h 0 − 6 } ] ⊆ Y − Y [1,\max\{6,h_0-6\}]\subseteq Y-Y [ 1 , max { 6 , h 0 − 6 }] ⊆ Y − Y . Translate so that Y ⊆ [ 0 , h 0 ] Y\subseteq[0,h_0] Y ⊆ [ 0 , h 0 ] contains both endpoints. If t > 0 t>0 t > 0 is absent from Y − Y Y-Y Y − Y , then Y Y Y contains no adjacent points in any residue class chain with step t t t . Write h 0 + 1 = j t + r h_0+1=jt+r h 0 + 1 = j t + r with 0 ≤ r < t 0\leq r<t 0 ≤ r < t . There are r r r chains of length j + 1 j+1 j + 1 and t − r t-r t − r of length j j j , so
∣ Y ∣ ≤ r ⌈ j + 1 2 ⌉ + ( t − r ) ⌊ j 2 ⌋ . |Y|\leq r\left\lceil\frac{j+1}{2}\right\rceil+(t-r)\left\lfloor\frac{j}{2}\right\rfloor. ∣ Y ∣ ≤ r ⌈ 2 j + 1 ⌉ + ( t − r ) ⌊ 2 j ⌋ .
For 8 ≤ h 0 ≤ 14 8\leq h_0\leq14 8 ≤ h 0 ≤ 14 and 1 ≤ t ≤ max { 6 , h 0 − 6 } 1\leq t\leq\max\{6,h_0-6\} 1 ≤ t ≤ max { 6 , h 0 − 6 } , the right side can reach 9 only in the following cases.
Table 8.
We rule out the four rows. Since ∣ Y − Y ∣ ≤ 23 |Y-Y|\leq23 ∣ Y − Y ∣ ≤ 23 , there are at most 11 positive differences.
For h 0 = 13 h_0=13 h 0 = 13 and t = 5 t=5 t = 5 , Y Y Y contains [ 0 , 3 ] [0,3] [ 0 , 3 ] , [ 10 , 13 ] [10,13] [ 10 , 13 ] , and one of 4, 9. Hence Y − Y Y-Y Y − Y contains [ 1 , 4 ] ∪ [ 6 , 13 ] [1,4]\cup[6,13] [ 1 , 4 ] ∪ [ 6 , 13 ] .
For h 0 = 14 h_0=14 h 0 = 14 and t = 3 t=3 t = 3 , Y = [ 0 , 2 ] ∪ [ 6 , 8 ] ∪ [ 12 , 14 ] Y=[0,2]\cup[6,8]\cup[12,14] Y = [ 0 , 2 ] ∪ [ 6 , 8 ] ∪ [ 12 , 14 ] . Hence Y − Y Y-Y Y − Y contains [ 1 , 2 ] ∪ [ 4 , 8 ] ∪ [ 10 , 14 ] [1,2]\cup[4,8]\cup[10,14] [ 1 , 2 ] ∪ [ 4 , 8 ] ∪ [ 10 , 14 ] .
For h 0 = 14 h_0=14 h 0 = 14 and t = 5 t=5 t = 5 , at least four chains contribute both endpoints. Thus E ∪ ( E + 10 ) ⊆ Y E\cup(E+10)\subseteq Y E ∪ ( E + 10 ) ⊆ Y for a four-point set E ⊆ [ 0 , 4 ] E\subseteq[0,4] E ⊆ [ 0 , 4 ] . If E E E omits an interior point, then E − E = [ − 4 , 4 ] E-E=[-4,4] E − E = [ − 4 , 4 ] and Y − Y Y-Y Y − Y contains [ 1 , 4 ] ∪ [ 6 , 14 ] [1,4]\cup[6,14] [ 1 , 4 ] ∪ [ 6 , 14 ] . Otherwise reflect to take E = [ 0 , 3 ] E=[0,3] E = [ 0 , 3 ] . Since 14 ∈ Y 14\in Y 14 ∈ Y , we have [ 10 , 14 ] ⊆ Y [10,14]\subseteq Y [ 10 , 14 ] ⊆ Y , and the differences include [ 1 , 4 ] ∪ [ 7 , 14 ] [1,4]\cup[7,14] [ 1 , 4 ] ∪ [ 7 , 14 ] .
For h 0 = 14 h_0 = 14 h 0 = 14 and t = 6 t = 6 t = 6 , Y Y Y contains [ 0 , 2 ] [0,2] [ 0 , 2 ] and [ 12 , 14 ] [12,14] [ 12 , 14 ] , and one point from each of { 3 , 9 } \{3,9\} { 3 , 9 } , { 4 , 10 } \{4,10\} { 4 , 10 } , { 5 , 11 } \{5,11\} { 5 , 11 } . If it contains 9 or 5, the differences include [ 1 , 5 ] ∪ [ 7 , 14 ] [1,5] \cup[7,14] [ 1 , 5 ] ∪ [ 7 , 14 ] . Otherwise 3 and 11, together with the endpoint intervals, give [ 1 , 3 ] ∪ [ 8 , 14 ] [1,3] \cup[8,14] [ 1 , 3 ] ∪ [ 8 , 14 ] . The choice of 4 or 10 supplies 4 and 7, giving [ 1 , 4 ] ∪ [ 7 , 14 ] [1,4] \cup[7,14] [ 1 , 4 ] ∪ [ 7 , 14 ] .
Every row gives at least 12 positive differences, a contradiction. Take a 0 = max { 6 , h 0 − 6 } a_0 = \max\{6,h_0 - 6\} a 0 = max { 6 , h 0 − 6 } . Then h 0 − a 0 ≤ 6 h_0 - a_0 \le6 h 0 − a 0 ≤ 6 and 2 a 0 ≥ h 0 2a_0 \ge h_0 2 a 0 ≥ h 0 . By (14) , diam ( U Z ) ≤ h 0 \operatorname{diam}(UZ) \le h_0 diam ( U Z ) ≤ h 0 . This proves (17) .
In both subcases of Case 4.2, the balanced pair gives an interval of width 2 a 0 ≥ 12 2a_0 \ge12 2 a 0 ≥ 12 , at least the support diameter. Its contribution is 12, and its loss is 2 ( h 0 − a 0 ) ≤ 12 2(h_0 - a_0) \le12 2 ( h 0 − a 0 ) ≤ 12 . If p ≤ 31 p \le31 p ≤ 31 , then ∣ D ∣ ≤ 19 |D| \le19 ∣ D ∣ ≤ 19 . For ∣ X ∣ ≤ 8 |X| \le8 ∣ X ∣ ≤ 8 the loss is already at most 8. For ∣ X ∣ ≥ 9 |X| \ge9 ∣ X ∣ ≥ 9 we have h 0 ≤ 19 − ∣ X ∣ ≤ 10 h_0 \le19 - |X| \le10 h 0 ≤ 19 − ∣ X ∣ ≤ 10 , which again bounds the loss by 8.
Aligned and leftover layers. If an initial interval is available, let w w w be its width. The support of each aligned layer is contained in the chosen support of size q q q and has diameter at most w w w in its integer coordinates. By Lemma 2.4, the gaps between successive central sums of such a layer are at most w w w . The same lemma shows that adding any of these central sumsets to the initial interval or to a wider interval again gives an interval. Each central sumset has integer diameter at least its contribution f ( s j ) f(s_j) f ( s j ) .
A two-element layer is always aligned, since it provides an initial interval. The remaining unaligned layers are grouped as in the table. The weights of full groups of sizes three, four, and five are 32, 28, and 12, respectively, each at most 16 g / 5 16g/5 16 g /5 . The leftover weights sum to at most 3 ⋅ 8 + 3 ⋅ 7 + 6 = 51 3 \cdot8 + 3 \cdot7 + 6 = 51 3 ⋅ 8 + 3 ⋅ 7 + 6 = 51 .
Excluding the remaining multiplicities
Theorem 6.1. Let p ≥ 11 p \ge11 p ≥ 11 . If S S S is a sequence of 2 p 2p 2 p units, π \pi π is injective on its support, and m = p − h ( S ) ≥ m 0 m = p - \mathrm{h}(S) \ge m_0 m = p − h ( S ) ≥ m 0 , then S S S has a subsequence T T T with ∣ T ∣ = p |T| = p ∣ T ∣ = p and σ ( T ) ∈ p G ∖ { 0 } \sigma(T) \in pG \setminus\{0\} σ ( T ) ∈ pG ∖ { 0 } .
Proof. Assume that S S S is exceptional. Set s = s 1 s = s_1 s = s 1 and u = s − 4 u = s - 4 u = s − 4 , and let v 2 , v 3 v_2,v_3 v 2 , v 3 be the second and third largest multiplicities. Lemmas 4.2 and 4.5 give
s ≥ 4 , e + f ( u ) ≤ p − 2 m − 3 , v 2 − e ≥ m + 1 − e / 2. (18) s \ge4,\qquad e + f(u) \le p - 2m - 3,\qquad v_2 - e \ge m + 1 - e/2. \tag*{(18)} s ≥ 4 , e + f ( u ) ≤ p − 2 m − 3 , v 2 − e ≥ m + 1 − e /2. (18)
For the last inequality, (12) gives
2 ( p + m ) − 2 v 2 ≤ 2 ( p + m ) − ( v 2 + v 3 ) ≤ b S = 2 p − 2 − e . 2(p + m) - 2v_2 \le2(p + m) - (v_2 + v_3) \le b_S = 2p - 2 - e. 2 ( p + m ) − 2 v 2 ≤ 2 ( p + m ) − ( v 2 + v 3 ) ≤ b S = 2 p − 2 − e .
For p = 11 , 13 p = 11,13 p = 11 , 13 , the inequality p − 2 m − 3 < 0 p - 2m - 3 < 0 p − 2 m − 3 < 0 contradicts e ≥ 0 e \ge0 e ≥ 0 . Thus p ≥ 17 p \ge17 p ≥ 17 . For p = 17 , 19 p = 17,19 p = 17 , 19 , (18) gives e = 0 e = 0 e = 0 , s ≤ 5 s \le5 s ≤ 5 , and v 2 − e ≥ m + 1 ≥ 8 v_2 - e \ge m + 1 \ge8 v 2 − e ≥ m + 1 ≥ 8 . For p ≥ 23 p \ge23 p ≥ 23 , we have 4 m ≥ p + 13 4m \ge p + 13 4 m ≥ p + 13 , so
2 e + 19 ≤ 2 p − 4 m + 13 ≤ p , v 2 − e ≥ m + 1 − p − 19 4 ≥ 9. 2e + 19 \le2p - 4m + 13 \le p,\qquad v_2 - e \ge m + 1 - \frac{p - 19}{4} \ge9. 2 e + 19 ≤ 2 p − 4 m + 13 ≤ p , v 2 − e ≥ m + 1 − 4 p − 19 ≥ 9.
An integer interval from the layers other than the first.
Case 1. e = 0 e = 0 e = 0 . Lemma 4.5 gives Φ ≥ − p + 9 m + 2 > 21 \Phi\ge-p + 9m + 2 > 21 Φ ≥ − p + 9 m + 2 > 21 . Thus some nonfirst layer has size two, or some size r ∈ { 3 , 4 , 5 } r \in\{3,4,5\} r ∈ { 3 , 4 , 5 } occurs at least twice outside the first layer.
Case 1.1. Some nonfirst layer has size two. Fix any central selection sizes of total p p p . The two-element layer gives an interval of width 1.
Case 1.2. No nonfirst layer has size two. Choose two layers of size r r r with common support U U U . Fix central selection sizes of total p p p , taking ⌊ r / 2 ⌋ \lfloor r/2 \rfloor ⌊ r /2 ⌋ and ⌈ r / 2 ⌉ \lceil r/2 \rceil ⌈ r /2 ⌉ in these two layers. Let B = ∑ ⌊ r / 2 ⌋ ( U ) B = \sum_{\lfloor r/2 \rfloor}(U) B = ∑ ⌊ r /2 ⌋ ( U ) and let Y = B + ∑ ⌈ r / 2 ⌉ ( U ) Y = B + \sum_{\lceil r/2 \rceil}(U) Y = B + ∑ ⌈ r /2 ⌉ ( U ) . By (13) , π ( Y ) \pi(Y) π ( Y ) is a translate of π ( B ) − π ( B ) \pi(B) - \pi(B) π ( B ) − π ( B ) when r r r is odd and equals π ( B ) + π ( B ) \pi(B) + \pi(B) π ( B ) + π ( B ) when r r r is even. Lemma 4.1 gives ∣ π ( B ) ∣ ≥ f ( r ) + 1 |\pi(B)| \ge f(r) + 1 ∣ π ( B ) ∣ ≥ f ( r ) + 1 . By Lemma 4.2 with e = 0 e = 0 e = 0 , we have ∣ π ( Y ) ∣ ≤ 2 f ( r ) + 1 ≤ p − 2 |\pi(Y)| \le2f(r) + 1 \le p - 2 ∣ π ( Y ) ∣ ≤ 2 f ( r ) + 1 ≤ p − 2 . Lemma 2.1 therefore gives
2 f ( r ) + 1 ≤ 2 ∣ π ( B ) ∣ − 1 ≤ ∣ π ( Y ) ∣ ≤ 2 f ( r ) + 1. 2f(r) + 1 \le2|\pi(B)| - 1 \le|\pi(Y)| \le2f(r) + 1. 2 f ( r ) + 1 ≤ 2∣ π ( B ) ∣ − 1 ≤ ∣ π ( Y ) ∣ ≤ 2 f ( r ) + 1.
All inequalities are equalities, so (3) implies that π ( B ) \pi(B) π ( B ) is an arithmetic progression in C p C_p C p . Since Y Y Y is B + B B + B B + B or a translate of B − B B - B B − B , injectivity on Y Y Y gives injectivity on B − B B - B B − B by the argument in Lemma 5.2. The successive differences of the progression therefore lift to one common difference in B B B . Thus one layer provides an interval of width f ( r ) f(r) f ( r ) . In both subcases of Case 1, the interval comes from one layer and has width equal to its contribution, at most 6.
Case 2. e > 0 e > 0 e > 0 . Then p ≥ 23 p \ge23 p ≥ 23 and Lemma 5.2 applies. Retain the central selection sizes fixed in § 5 . For each full group indexed by i i i , let g i g_i g i be its gain. Suppose ∑ i g i > e \sum_i g_i > e ∑ i g i > e and add groups until their total gain first exceeds e e e . Let J J J be the set of selected group indices, j 0 j_0 j 0 the last one added, and b b b their combined contribution. For each i ∈ J i \in J i ∈ J , let Y i Y_i Y i be the joint central sumset of the i i i th group. Since each group contributes at most its gain and at most 16, we have
∑ i ∈ J ∖ { j 0 } g i ≤ e < ∑ i ∈ J g i , b ≤ ∑ i ∈ J ∖ { j 0 } g i + 16 ≤ e + 16. \sum_{i\in J\setminus\{j_0\}} g_i \le e < \sum_{i\in J} g_i,\qquad b \le\sum_{i\in J\setminus\{j_0\}} g_i+16\le e+16. i ∈ J ∖ { j 0 } ∑ g i ≤ e < i ∈ J ∑ g i , b ≤ i ∈ J ∖ { j 0 } ∑ g i + 16 ≤ e + 16.
Let Y = ∑ i ∈ J Y i Y=\sum_{i\in J}Y_i Y = ∑ i ∈ J Y i . Since b + e + 2 ≤ 2 e + 18 ≤ p − 1 b+e+2\le2e+18\le p-1 b + e + 2 ≤ 2 e + 18 ≤ p − 1 and ∑ i ∈ J g i ≥ e + 1 \sum_{i\in J}g_i\ge e+1 ∑ i ∈ J g i ≥ e + 1 , Lemma 2.1 gives
∣ π ( Y ) ∣ ≥ min { p , 1 + b + ∑ i ∈ J g i } ≥ b + e + 2. |\pi(Y)|\ge\min\left\{p,1+b+\sum_{i\in J}g_i\right\}\ge b+e+2. ∣ π ( Y ) ∣ ≥ min { p , 1 + b + i ∈ J ∑ g i } ≥ b + e + 2.
The layers forming Y Y Y have total contribution b ≤ p − e − 1 b\le p-e-1 b ≤ p − e − 1 , so Lemma 4.2 gives ∣ π ( Y ) ∣ ≤ b + e + 1 |\pi(Y)|\le b+e+1 ∣ π ( Y ) ∣ ≤ b + e + 1 , a contradiction. Thus ∑ i g i ≤ e \sum_i g_i\le e ∑ i g i ≤ e .
Let Φ a \Phi_a Φ a be the weight of the aligned layers. The full groups and leftovers have weight at most 16 e / 5 + 51 16e/5+51 16 e /5 + 51 , so
Φ a − 4 e > 5 p + 107 4 − 11 e 5 − 51 ≥ 3 p − 67 20 > 0. \Phi_a-4e>\frac{5p+107}{4}-\frac{11e}{5}-51\ge\frac{3p-67}{20}>0. Φ a − 4 e > 4 5 p + 107 − 5 11 e − 51 ≥ 20 3 p − 67 > 0.
Since the aligned layers have positive total weight, an initial interval exists. For the initial interval and each remaining aligned factor, let w i w_i w i be its width and b i b_i b i its contribution. Each satisfies w i ≥ b i w_i\ge b_i w i ≥ b i , and each layer’s weight is at most four times its contribution. Thus
∑ i ( 2 w i − b i ) ≥ ∑ i b i ≥ Φ a 4 > e . \sum_i(2w_i-b_i)\ge\sum_i b_i\ge\frac{\Phi_a}{4}>e. i ∑ ( 2 w i − b i ) ≥ i ∑ b i ≥ 4 Φ a > e .
Start with the initial interval and add aligned factors until the sum on the left first exceeds e e e . By Lemma 5.2 , each factor’s gaps are at most the initial width, so Lemma 2.4 ensures that the sum remains an interval. The initial contribution is at most 12. If further factors are needed, the contribution before the final addition is at most e e e and the last factor contributes at most 6. Thus the total contribution is at most max { 12 , e + 6 } \max\{12,e+6\} max { 12 , e + 6 } .
In Cases 1 and 2, denote the resulting interval by P P P , its width by w w w , its contribution by b P b_P b P , and its truncation loss by l l l . Set γ = w − b P \gamma=w-b_P γ = w − b P . Then
γ ≥ 0 , w + γ > e . \gamma\ge0,\qquad w+\gamma>e. γ ≥ 0 , w + γ > e .
The sum of the full integer diameters of the factors used, treating the initial group as one factor, is w + l w+l w + l . Only the initial group is truncated, and its retained width is at least its contribution. The initial group uses at most four layers. When e = 0 e=0 e = 0 , it uses one layer and l = 0 l=0 l = 0 .
Lifting the first layer. We first bound the combined contribution of the first and selected layers. For p = 17 , 19 p=17,19 p = 17 , 19 , we have f ( s ) + b P ≤ 12 ≤ p − e − 1 f(s)+b_P\le12\le p-e-1 f ( s ) + b P ≤ 12 ≤ p − e − 1 . For p ≥ 23 p\ge23 p ≥ 23 , use 2 u − f ( u ) ≤ 4 2u-f(u)\le4 2 u − f ( u ) ≤ 4 and (18) to obtain
2 u ≤ p − 2 m + 1 − e ≤ 2 m − 12 − e . 2u\le p-2m+1-e\le2m-12-e. 2 u ≤ p − 2 m + 1 − e ≤ 2 m − 12 − e .
Since 2 u 2u 2 u is even, the last bound gives 2 u ≤ 2 m − 12 − 2 ⌈ e / 2 ⌉ 2u\le2m-12-2\lceil e/2\rceil 2 u ≤ 2 m − 12 − 2 ⌈ e /2 ⌉ . The bounds b P ≤ 6 b_P\le6 b P ≤ 6 for e = 0 e=0 e = 0 and b P ≤ max { 12 , e + 6 } b_P\le\max\{12,e+6\} b P ≤ max { 12 , e + 6 } for e > 0 e>0 e > 0 imply b P + 2 ≤ 12 + 2 ⌈ e / 2 ⌉ b_P+2\le12+2\lceil e/2\rceil b P + 2 ≤ 12 + 2 ⌈ e /2 ⌉ . Thus 2 u + b P + 2 ≤ 2 m 2u+b_P+2\le2m 2 u + b P + 2 ≤ 2 m , and (18) gives
f ( s ) + b P = f ( u ) + ( 2 u + b P + 2 ) + 2 ≤ p − e − 1. f(s)+b_P=f(u)+(2u+b_P+2)+2\le p-e-1. f ( s ) + b P = f ( u ) + ( 2 u + b P + 2 ) + 2 ≤ p − e − 1.
Let A A A be the central sumset of the first layer in G G G , and regard P P P here as the set { y + i d : i ∈ [ 0 , w ] } ⊆ G \{y+id:i\in[0,w]\}\subseteq G { y + i d : i ∈ [ 0 , w ]} ⊆ G , where y y y is the element of P P P at coordinate zero and d d d is its unit common difference. By Lemma 4.2 , π \pi π is injective on A + P A+P A + P and ∣ π ( A + P ) ∣ ≤ f ( s ) + b P + e + 1 |\pi(A+P)|\le f(s)+b_P+e+1 ∣ π ( A + P ) ∣ ≤ f ( s ) + b P + e + 1 . Since a translate of A A A lies in A + P A+P A + P , π \pi π is injective on A A A . List a i ∈ A a_i\in A a i ∈ A in the cyclic order of their images along d ˉ \bar d d ˉ .
Let ℓ i \ell_i ℓ i be the positive distance from π ( a i ) \pi(a_i) π ( a i ) to π ( a i + 1 ) \pi(a_{i+1}) π ( a i + 1 ) in this order, so ∑ i ℓ i = p \sum_i \ell_i=p ∑ i ℓ i = p . The coverage in each gap is min { ℓ i , w + 1 } \min\{\ell_i,w+1\} min { ℓ i , w + 1 } , hence
∣ π ( A + P ) ∣ = ∑ i min { ℓ i , w + 1 } = ∣ π ( A ) ∣ + ∑ i min { ℓ i − 1 , w } . |\pi(A+P)|=\sum_i\min\{\ell_i,w+1\}=|\pi(A)|+\sum_i\min\{\ell_i-1,w\}. ∣ π ( A + P ) ∣ = i ∑ min { ℓ i , w + 1 } = ∣ π ( A ) ∣ + i ∑ min { ℓ i − 1 , w } .
Together with ∣ π ( A ) ∣ ≥ f ( s ) + 1 |\pi(A)|\ge f(s)+1 ∣ π ( A ) ∣ ≥ f ( s ) + 1 , this gives
∑ i min { ℓ i − 1 , w } ≤ b P + e . \sum_i\min\{\ell_i-1,w\}\le b_P+e. i ∑ min { ℓ i − 1 , w } ≤ b P + e .
Whenever ℓ i ≤ w \ell_i\le w ℓ i ≤ w , the elements a i + y + ℓ i d a_i+y+\ell_i d a i + y + ℓ i d and a i + 1 + y a_{i+1}+y a i + 1 + y of A + P A+P A + P have the same image. Injectivity on A + P A+P A + P gives a i + 1 − a i = ℓ i d a_{i+1}-a_i=\ell_i d a i + 1 − a i = ℓ i d . If every ℓ i ≤ w \ell_i\le w ℓ i ≤ w , summing these equalities cyclically gives 0 = ( ∑ i ℓ i ) d = p d 0=(\sum_i\ell_i)d=pd 0 = ( ∑ i ℓ i ) d = p d , a contradiction.
Thus some gap ℓ i 0 \ell_{i_0} ℓ i 0 is at least w + 1 w+1 w + 1 . It contributes w w w to the last sum, and the other contributions sum to at most b P + e − w = e − γ < w b_P+e-w=e-\gamma<w b P + e − w = e − γ < w . In particular, each other gap is at most w w w . Cutting the cyclic order of π ( A ) \pi(A) π ( A ) at ℓ i 0 \ell_{i_0} ℓ i 0 gives integer coordinates along d ˉ \bar d d ˉ with diameter
∑ i ≠ i 0 ℓ i = ∣ π ( A + P ) ∣ − w − 1 ≤ f ( s ) + e − γ = : L < p . \sum_{i\ne i_0}\ell_i=|\pi(A+P)|-w-1\le f(s)+e-\gamma=:L<p. i = i 0 ∑ ℓ i = ∣ π ( A + P ) ∣ − w − 1 ≤ f ( s ) + e − γ =: L < p .
The overlaps at the other gaps give the same successive differences in A A A , so A A A itself lifts to that diameter. Since ∣ π ( A ) ∣ ≥ 2 |\pi(A)|\ge2 ∣ π ( A ) ∣ ≥ 2 , the large gap is at most p − 1 p-1 p − 1 , and w ≤ p − 2 w\le p-2 w ≤ p − 2 .
By (14) , L 1 − L 1 ⊆ A − A L_1-L_1\subseteq A-A L 1 − L 1 ⊆ A − A . Choose c ∈ L 1 c\in L_1 c ∈ L 1 and, for each b ∈ L 1 b\in L_1 b ∈ L 1 , choose x b ∈ [ − L , L ] x_b\in[-L,L] x b ∈ [ − L , L ] with b − c = x b d b-c=x_bd b − c = x b d in G G G . For any b , b ′ ∈ L 1 b,b'\in L_1 b , b ′ ∈ L 1 , we have
x b − x b ′ ≡ t ( m o d p 2 ) , t ∈ [ − L , L ] . x_b-x_{b'}\equiv t\pmod{p^2},\qquad t\in[-L,L]. x b − x b ′ ≡ t ( mod p 2 ) , t ∈ [ − L , L ] .
Since ∣ x b − x b ′ − t ∣ ≤ 3 L < p 2 |x_b-x_{b'}-t|\le3L<p^2 ∣ x b − x b ′ − t ∣ ≤ 3 L < p 2 , we have x b − x b ′ = t x_b-x_{b'}=t x b − x b ′ = t . Thus the coordinates have diameter at most L L L . Let a a a be the support value of least coordinate. After translating the coordinates so that a a a has coordinate zero, the support is
{ a + x i d : 1 ≤ i ≤ s } , 0 = x 1 < ⋯ < x s = D ≤ L . \{a+x_i d:1\le i\le s\},\qquad0=x_1<\cdots<x_s=D\le L. { a + x i d : 1 ≤ i ≤ s } , 0 = x 1 < ⋯ < x s = D ≤ L .
In these coordinates, a selection of p p p terms with integer sum z z z has sum p a + z d pa+zd p a + z d in G G G . The difference between two integer central sums has absolute value at most s L sL s L . Its image after multiplication by d d d lies in A − A A-A A − A , so the difference is congruent modulo p 2 p^2 p 2 to an integer in [ − L , L ] [-L,L] [ − L , L ] . Since s ≤ p − 1 s\le p-1 s ≤ p − 1 and L < p L<p L < p , the bound ( s + 1 ) L < p 2 (s+1)L<p^2 ( s + 1 ) L < p 2 makes the two integers equal. The central sumset of the first layer therefore has integer diameter at most L L L .
For a layer of size r r r with coordinates y 1 < ⋯ < y r y_1<\cdots<y_r y 1 < ⋯ < y r , the width of its central sumset is
f ( r ) + ∑ i = 1 r − 1 min { i , r − i } ( y i + 1 − y i − 1 ) . (19) f(r)+\sum_{i=1}^{r-1}\min\{i,r-i\}(y_{i+1}-y_i-1). \tag*{(19)} f ( r ) + i = 1 ∑ r − 1 min { i , r − i } ( y i + 1 − y i − 1 ) . (19)
To see (19) , note that the two central selection sizes give the same width by (13) . Set k = ⌊ r / 2 ⌋ k=\lfloor r/2\rfloor k = ⌊ r /2 ⌋ . Subtract the minimum central sum from the maximum and collect terms by gaps to obtain
∑ i = 1 k ( y r − k + i − y i ) = ∑ i = 1 r − 1 min { i , r − i } ( y i + 1 − y i ) . \sum_{i=1}^{k}(y_{r-k+i}-y_i)=\sum_{i=1}^{r-1}\min\{i,r-i\}(y_{i+1}-y_i). i = 1 ∑ k ( y r − k + i − y i ) = i = 1 ∑ r − 1 min { i , r − i } ( y i + 1 − y i ) .
The sum of the gap weights is k ( r − k ) = f ( r ) k(r-k)=f(r) k ( r − k ) = f ( r ) , which gives (19) . For the first layer the total excess above f ( s ) f(s) f ( s ) is at most L − f ( s ) = e − γ L-f(s)=e-\gamma L − f ( s ) = e − γ . Every gap weight is at least one, so
D ≤ s − 1 + e − γ < p − 1 , max i ( x i + 1 − x i ) ≤ e − γ + 1 ≤ w . D\le s-1+e-\gamma<p-1,\qquad\max_i(x_{i+1}-x_i)\le e-\gamma+1\le w. D ≤ s − 1 + e − γ < p − 1 , i max ( x i + 1 − x i ) ≤ e − γ + 1 ≤ w .
Here the strict diameter bound follows from s + e ≤ p − 2 m + 1 + w − f ( w ) ≤ p − 2 m + 2 s+e\le p-2m+1+w-f(w)\le p-2m+2 s + e ≤ p − 2 m + 1 + w − f ( w ) ≤ p − 2 m + 2 .
Completion to p p p terms. Let η j \eta_j η j be the excess of the width in (19) over f ( s j ) f(s_j) f ( s j ) , and set η = ∑ j η j \eta=\sum_j\eta_j η = ∑ j η j . Let k k k be the number of terms supplied by the selected layers. The fixed central selection sizes sum to p p p , so the central selections in the remaining layers supply p − k p-k p − k terms. Let z , z ′ z,z' z , z ′ be the sums of a selection from the selected layers in the coordinates used to construct P P P and in the full support coordinates, respectively. Let z 0 , z 0 ′ z_0,z'_0 z 0 , z 0 ′ be the sums of a fixed selection in the same two coordinate systems. The selection sizes in each layer are fixed, so the origins cancel when subtracting the two group sums in either coordinate system. Thus ( z − z 0 ) d = ( z ′ − z 0 ′ ) d (z-z_0)d=(z'-z'_0)d ( z − z 0 ) d = ( z ′ − z 0 ′ ) d in G G G . Since d d d has order p 2 p^2 p 2 and since ∣ z − z 0 ∣ ≤ w + l |z-z_0|\le w+l ∣ z − z 0 ∣ ≤ w + l , ∣ z ′ − z 0 ′ ∣ ≤ k D ≤ p D |z'-z'_0|\le kD\le pD ∣ z ′ − z 0 ′ ∣ ≤ k D ≤ p D , D ≤ p − 2 D\le p-2 D ≤ p − 2 , w + l ≤ p + 10 w+l\le p+10 w + l ≤ p + 10 , and p ≥ 17 p\ge17 p ≥ 17 , we obtain
( z − z 0 ) − ( z ′ − z 0 ′ ) ≡ 0 ( m o d p 2 ) , (z-z_0)-(z'-z'_0)\equiv0 \pmod{p^2}, ( z − z 0 ) − ( z ′ − z 0 ′ ) ≡ 0 ( mod p 2 ) ,
∣ ( z − z 0 ) − ( z ′ − z 0 ′ ) ∣ ≤ p D + w + l ≤ p ( p − 2 ) + p + 10 < p 2 . |(z-z_0)-(z'-z'_0)|\le pD+w+l\le p(p-2)+p+10<p^2. ∣ ( z − z 0 ) − ( z ′ − z 0 ′ ) ∣ ≤ p D + w + l ≤ p ( p − 2 ) + p + 10 < p 2 .
It follows that z ′ = z + ( z 0 ′ − z 0 ) z'=z+(z'_0-z_0) z ′ = z + ( z 0 ′ − z 0 ) in the integers. The same translation takes the full sumset and the coordinate interval of P P P into the full support coordinates, preserving their widths w + l w+l w + l and w w w and hence the loss l l l . Denote the resulting integer interval by P Z P_Z P Z .
All first-layer positions remain outside the selected layers, so the remaining positions contain every support value and have maximum gap at most w w w . By Lemma 2.4, adding their integer sumset of p − k p-k p − k terms to P Z P_Z P Z gives an interval. The central selections in the remaining layers show that its width is at least b S + η − l b_S+\eta-l b S + η − l . If η > e + l \eta>e+l η > e + l , then
b S + η − l ≥ b S + e + 1 = 2 p − 1. b_S+\eta-l\ge b_S+e+1=2p-1. b S + η − l ≥ b S + e + 1 = 2 p − 1.
The interval then contains j p jp j p and ( j + 1 ) p (j+1)p ( j + 1 ) p for some integer j j j . The corresponding sums in G G G are p a + j p d pa+jpd p a + j p d and p a + ( j + 1 ) p d pa+(j+1)pd p a + ( j + 1 ) p d . They belong to Σ p ( S ) ∩ p G \Sigma_p(S)\cap pG Σ p ( S ) ∩ pG and differ by p d ≠ 0 pd\ne0 p d = 0 , contrary to (2.1). Thus η ≤ e + l \eta\le e+l η ≤ e + l .
The coordinates of the two most frequent values lie in the same maximal interval [ v − , v + ] [v_-,v_+] [ v − , v + ] of consecutive support coordinates. Otherwise each of the first v 2 v_2 v 2 layers has a gap and contributes at least one unit of excess, except for the layers in the initial group, which we count separately. Fixing the selections in the other selected layers shows that the coordinate comparison preserves the width of the full central sumset of the initial group. Its full width exceeds its retained width by l l l , and its retained width is at least its contribution. Thus the initial group has total excess at least l l l . Since it uses at most four layers, we get η − l ≥ v 2 − 4 > e \eta-l\ge v_2-4>e η − l ≥ v 2 − 4 > e , a contradiction.
Let b o u t b_{\mathrm{out}} b out be the number of terms with coordinates outside [ v − , v + ] [v_-,v_+] [ v − , v + ] , and let q j q_j q j be the number of such values in layer j j j . Set
E = D − ( s − 1 ) , M 0 = ∑ j min { 2 , q j } . E=D-(s-1),\qquad M_0=\sum_j\min\{2,q_j\}. E = D − ( s − 1 ) , M 0 = j ∑ min { 2 , q j } .
The layers are nested. A nonempty layer with j > v 2 j>v_2 j > v 2 consists only of the most frequent value, whose coordinate lies in [ v − , v + ] [v_-,v_+] [ v − , v + ] . Thus q j > 0 q_j>0 q j > 0 implies j ≤ v 2 j\le v_2 j ≤ v 2 , and the layer contains the two most frequent values. In layer j j j , let q − q_- q − and q + q_+ q + be the counts to the left and right of [ v − , v + ] [v_-,v_+] [ v − , v + ] , respectively. Thus q − + q + = q j q_-+q_+=q_j q − + q + = q j . If a side contains q > 0 q>0 q > 0 coordinates, its boundary gap has size at least two and weight min { q , s j − q } ≥ min { 2 , q } \min\{q,s_j-q\}\ge\min\{2,q\} min { q , s j − q } ≥ min { 2 , q } in (6.2). The two sides use distinct gaps when both are present, so
η j ≥ min { 2 , q − } + min { 2 , q + } ≥ min { 2 , q j } . \eta_j\ge\min\{2,q_-\}+\min\{2,q_+\}\ge\min\{2,q_j\}. η j ≥ min { 2 , q − } + min { 2 , q + } ≥ min { 2 , q j } .
For the first layer the total gap excess is E E E . After allocating one unit of gap at each boundary to the preceding estimate, at least E − 2 E-2 E − 2 units remain. Therefore η 1 ≥ min { 2 , q 1 } + E − 2 \eta_1\ge\min\{2,q_1\}+E-2 η 1 ≥ min { 2 , q 1 } + E − 2 and E + M 0 ≤ η + 2 E+M_0\le\eta+2 E + M 0 ≤ η + 2 .
For q j ≥ 3 q_j\ge3 q j ≥ 3 we have
2 ( q j − 2 ) ≤ f ( q j ) ≤ f ( s j − 2 ) = f ( s j ) − s j + 1. 2(q_j-2)\le f(q_j)\le f(s_j-2)=f(s_j)-s_j+1. 2 ( q j − 2 ) ≤ f ( q j ) ≤ f ( s j − 2 ) = f ( s j ) − s j + 1.
Since f ( s j ) ≥ s j − 1 f(s_j)\ge s_j-1 f ( s j ) ≥ s j − 1 for every nonempty layer, summing yields
b o u t = M 0 + ∑ j max { q j − 2 , 0 } ≤ M 0 + 1 2 ( b S − p − m ) , \begin{aligned}
b_{\mathrm{out}}=M_0+\sum_j\max\{q_j-2,0\} \\
&\le M_0+\frac{1}{2}(b_S-p-m),
\end{aligned} b out = M 0 + j ∑ max { q j − 2 , 0 } ≤ M 0 + 2 1 ( b S − p − m ) ,
where ∑ j ( s j − 1 ) = p + m \sum_j(s_j-1)=p+m ∑ j ( s j − 1 ) = p + m . Together with η ≤ e + l \eta\le e+l η ≤ e + l and b S = 2 p − 2 − e b_S=2p-2-e b S = 2 p − 2 − e , this gives
D + b o u t ≤ s + p − m + e 2 + l ≤ p − 3 m − 9 − 2 l 2 < p . (20) D+b_{\mathrm{out}}\le s+\frac{p-m+e}{2}+l\le p-\frac{3m-9-2l}{2}<p. \tag*{(20)} D + b out ≤ s + 2 p − m + e + l ≤ p − 2 3 m − 9 − 2 l < p . (20)
The second inequality uses (6.1) and 2 u − f ( u ) ≤ 4 2u-f(u)\le4 2 u − f ( u ) ≤ 4 . For strictness when e = 0 e=0 e = 0 , use m ≥ 7 m\ge7 m ≥ 7 and l = 0 l=0 l = 0 . If e > 0 e>0 e > 0 and p ≤ 31 p\le31 p ≤ 31 , then m ≥ 9 m\ge9 m ≥ 9 and l ≤ 8 l\le8 l ≤ 8 . If p ≥ 37 p\ge37 p ≥ 37 , then m ≥ 13 m\ge13 m ≥ 13 and l ≤ 12 l\le12 l ≤ 12 .
Fix any subsequence T T T whose terms have coordinates outside [ v − , v + ] [v_{-},v_{+}] [ v − , v + ] and complete it with q = p − ∣ T ∣ q=p-|T| q = p − ∣ T ∣ terms whose coordinates lie in that interval. Let z 1 ≤ ⋯ ≤ z n z_1\le\cdots\le z_n z 1 ≤ ⋯ ≤ z n be the ordered coordinates of all terms with coordinates in [ v − , v + ] [v_{-},v_{+}] [ v − , v + ] , with n = 2 p − b o u t n=2p-b_{\mathrm{out}} n = 2 p − b out . We have p − b o u t ≤ q ≤ p ≤ n p-b_{\mathrm{out}}\le q\le p\le n p − b out ≤ q ≤ p ≤ n by (20) . Since z i + 1 − z i ≤ 1 z_{i+1}-z_i\le1 z i + 1 − z i ≤ 1 for 1 ≤ i < n 1\le i<n 1 ≤ i < n , Lemma 2.4 shows that the integer sums of the completed selections form an interval I T I_T I T . For k = min { q , n − q } k=\min\{q,n-q\} k = min { q , n − q } , its width is
diam ( I T ) = ∑ i = 1 k ( z n − k + i − z i ) . \operatorname{diam}(I_T)=\sum_{i=1}^{k}(z_{n-k+i}-z_i). diam ( I T ) = i = 1 ∑ k ( z n − k + i − z i ) .
A summand can vanish only at a value with multiplicity greater than n − k ≥ n / 2 n-k\ge n/2 n − k ≥ n /2 . At most one value has that multiplicity, and the number of zero summands is at most max { 0 , h ( S ) − ( n − k ) } \max\{0,h(S)-(n-k)\} max { 0 , h ( S ) − ( n − k )} . We have k ≥ p − b o u t k\ge p-b_{\mathrm{out}} k ≥ p − b out from q ≥ p − b o u t q\ge p-b_{\mathrm{out}} q ≥ p − b out and n − q ≥ n − p = p − b o u t n-q\ge n-p=p-b_{\mathrm{out}} n − q ≥ n − p = p − b out . Hence
diam ( I T ) ≥ min { k , n − h ( S ) } ≥ p − b o u t > D . \operatorname{diam}(I_T)\ge\min\{k,n-h(S)\}\ge p-b_{\mathrm{out}}>D. diam ( I T ) ≥ min { k , n − h ( S )} ≥ p − b out > D .
If T ′ T' T ′ is obtained by adding one term with coordinate outside [ v − , v + ] [v_{-},v_{+}] [ v − , v + ] to T T T , then at each endpoint one coordinate from [ v − , v + ] [v_{-},v_{+}] [ v − , v + ] is replaced by the coordinate of the added term. All coordinates lie in [ 0 , D ] [0,D] [ 0 , D ] , so
∣ min I T ′ − min I T ∣ ≤ D , ∣ max I T ′ − max I T ∣ ≤ D . |\min I_{T'}-\min I_T|\le D,\qquad|\max I_{T'}-\max I_T|\le D. ∣ min I T ′ − min I T ∣ ≤ D , ∣ max I T ′ − max I T ∣ ≤ D .
Since both intervals have width greater than D D D , they overlap. All choices of T T T are connected by successive additions or removals, so their union is an interval I I I of all p p p -term integer sums. The interval I I I contains all central sums, so
diam ( I ) ≥ b S ≥ ∑ j ( s j − 1 ) = p + m ≥ p − 1. \operatorname{diam}(I)\ge b_S\ge\sum_j(s_j-1)=p+m\ge p-1. diam ( I ) ≥ b S ≥ j ∑ ( s j − 1 ) = p + m ≥ p − 1.
Choose p j ∈ I pj\in I p j ∈ I . If a + j d a+jd a + j d is a unit, the corresponding p p p -term subsequence has sum p ( a + j d ) ∈ p G ∖ { 0 } p(a+jd)\in pG\setminus\{0\} p ( a + j d ) ∈ pG ∖ { 0 } . Otherwise j ∉ [ v − , v + ] j\notin[v_{-},v_{+}] j ∈ / [ v − , v + ] , since every coordinate in this interval represents a unit. Let t ∈ I t\in I t ∈ I be an integer sum of p p p terms with coordinates in [ v − , v + ] [v_{-},v_{+}] [ v − , v + ] . Then
p j < p v − ≤ t or t ≤ p v + < p j . pj<pv_{-}\le t\qquad\text{or}\qquad t\le pv_{+}<pj. p j < p v − ≤ t or t ≤ p v + < p j .
Thus p v − ∈ I pv_{-}\in I p v − ∈ I in the first case and p v + ∈ I pv_{+}\in I p v + ∈ I in the second. The corresponding endpoint represents a unit, again giving a p p p -term sum in p G ∖ { 0 } pG\setminus\{0\} pG ∖ { 0 } . □
Proofs of the main results
Proof of Theorem 1.1. Assume first that S S S is exceptional. Since any subsequence a p a^p a p would have sum p a ∈ p G ∖ { 0 } pa\in pG\setminus\{0\} p a ∈ pG ∖ { 0 } , we have h ( S ) ≤ p − 1 h(S)\le p-1 h ( S ) ≤ p − 1 .
Case 1. π \pi π is not injective on supp ( S ) \operatorname{supp}(S) supp ( S ) . Proposition 3.1 gives the first form.
Case 2. π \pi π is injective on supp ( S ) \operatorname{supp}(S) supp ( S ) . Let m = p − h ( S ) m=p-h(S) m = p − h ( S ) and let v 2 , v 3 v_2,v_3 v 2 , v 3 be the second and third largest multiplicities. Since v 2 + v 3 ≤ 2 ( p − m ) v_2+v_3\le2(p-m) v 2 + v 3 ≤ 2 ( p − m ) , Lemma 4.2 and (12) give
4 m ≤ 2 ( p + m ) − ( v 2 + v 3 ) ≤ b S ≤ 2 p − 2. 4m\le2(p+m)-(v_2+v_3)\le b_S\le2p-2. 4 m ≤ 2 ( p + m ) − ( v 2 + v 3 ) ≤ b S ≤ 2 p − 2.
Thus 1 ≤ m ≤ ( p − 1 ) / 2 1\le m\le(p-1)/2 1 ≤ m ≤ ( p − 1 ) /2 . If p = 3 p=3 p = 3 , injectivity on supp ( S ) \operatorname{supp}(S) supp ( S ) gives ∣ supp ( S ) ∣ ≤ 2 |\operatorname{supp}(S)|\le2 ∣ supp ( S ) ∣ ≤ 2 , so ∣ S ∣ ≤ 4 < 2 p |S|\le4<2p ∣ S ∣ ≤ 4 < 2 p . Hence p ≥ 5 p\ge5 p ≥ 5 .
Case 2.1. m = 1 m=1 m = 1 . By Proposition 3.2 , there are two distinct values a , b a,b a , b of multiplicity p − 1 p-1 p − 1 . Hence S = a p − 1 b p − 1 x y S=a^{p-1}b^{p-1}xy S = a p − 1 b p − 1 x y with x , y ∉ { a , b } x,y\notin\{a,b\} x , y ∈ / { a , b } , and Proposition 3.3 gives the second form.
Case 2.2. m ∈ { 2 , 3 } m\in\{2,3\} m ∈ { 2 , 3 } . Proposition 3.5 gives a contradiction.
Case 2.3. m ≥ 4 m\ge4 m ≥ 4 . Since m ≤ ( p − 1 ) / 2 m\le(p-1)/2 m ≤ ( p − 1 ) /2 and p p p is prime, we have p ≥ 11 p\ge11 p ≥ 11 . The definition of m 0 m_0 m 0 gives
m < m 0 ⟺ m ≤ ⌊ p 3 ⌋ + 1 and m ≤ ⌊ p + 11 4 ⌋ ⟺ p ≥ max { 3 m − 3 , 4 m − 11 } . m<m_0\quad\Longleftrightarrow\quad m\le\left\lfloor\frac{p}{3}\right\rfloor+1\ \text{ and }\ m\le\left\lfloor\frac{p+11}{4}\right\rfloor\quad\Longleftrightarrow\quad p\ge\max\{3m-3,4m-11\}. m < m 0 ⟺ m ≤ ⌊ 3 p ⌋ + 1 and m ≤ ⌊ 4 p + 11 ⌋ ⟺ p ≥ max { 3 m − 3 , 4 m − 11 } .
If m < m 0 m<m_0 m < m 0 , Proposition 3.8 gives a contradiction. If m ≥ m 0 m\ge m_0 m ≥ m 0 , Theorem 6.1 gives a contradiction.
Conversely, the calculation in the proof of Proposition 3.1 shows that for the first form the only p p p -term subsequences with sum in p G pG pG are A A A and B B B . Both have sum zero. For the second form, reducing the formulas for x ‾ \overline{x} x and y ‾ \overline{y} y modulo p p p gives
x ‾ = b ‾ − i ( a ‾ − b ‾ ) , \overline{x}=\overline{b}-i(\overline{a}-\overline{b}), x = b − i ( a − b ) ,
y ‾ = b ‾ − ( p − 1 − i ) ( a ‾ − b ‾ ) . \overline{y}=\overline{b}-(p-1-i)(\overline{a}-\overline{b}). y = b − ( p − 1 − i ) ( a − b ) .
Since a ‾ ≠ b ‾ \overline{a}\ne\overline{b} a = b and 1 ≤ i , p − 1 − i ≤ p − 2 1\le i,p-1-i\le p-2 1 ≤ i , p − 1 − i ≤ p − 2 , both x ‾ \overline{x} x and y ‾ \overline{y} y lie outside { a ‾ , b ‾ } \{\overline{a},\overline{b}\} { a , b } . Moreover, x ‾ − y ‾ = ( p − 1 − 2 i ) ( a ‾ − b ‾ ) \overline{x}-\overline{y}=(p-1-2i)(\overline{a}-\overline{b}) x − y = ( p − 1 − 2 i ) ( a − b ) . Since ∣ p − 1 − 2 i ∣ ≤ p − 3 \lvert p-1-2i\rvert\le p-3 ∣ p − 1 − 2 i ∣ ≤ p − 3 , equality of x ‾ \overline{x} x and y ‾ \overline{y} y forces 2 i + 1 = p 2i+1=p 2 i + 1 = p , in which case x = y x=y x = y . Thus π \pi π is injective on the support, and Proposition 3.3 proves sufficiency. □
Proof of Corollary 1.2. Suppose W W W is a sequence of 2 p + 1 2p+1 2 p + 1 units with no p p p -term subsequence whose sum belongs to p G ∖ { 0 } pG\setminus\{0\} pG ∖ { 0 } . For each term w w w of W W W , the sequence W w − 1 Ww^{-1} W w − 1 is exceptional. By Theorem 1.1 , its largest residue class contains p p p terms in the first form and p − 1 p-1 p − 1 in the second. Indeed, in the second form the classes of a a a and b b b each contain p − 1 p-1 p − 1 terms, and any other class contains at most two terms. If some class of W W W contained at least p + 1 p+1 p + 1 terms, we could retain p + 1 p+1 p + 1 such positions by deleting another position. Thus every class of W W W contains at most p p p terms.
Case 1. Some residue class contains exactly p p p terms. Let A A A consist of the p p p terms in this class and set B = W A − 1 B=WA^{-1} B = W A − 1 . For every term b b b of B B B , the sequence W b − 1 = A ( B b − 1 ) Wb^{-1}=A(Bb^{-1}) W b − 1 = A ( B b − 1 ) retains A A A and therefore has the first form. Thus the terms of B b − 1 Bb^{-1} B b − 1 all lie in one residue class. Any two positions of B B B survive when a third position is deleted, so all p + 1 p+1 p + 1 terms of B B B lie in a single residue class, a contradiction.
Case 2. Each residue class contains at most p − 1 p-1 p − 1 terms. If p = 3 p=3 p = 3 , the two nonzero classes contain at most four terms, a contradiction. Hence p ≥ 5 p\ge5 p ≥ 5 . Every deletion has the second form and gives two classes with p − 1 p-1 p − 1 terms each. Since 3 ( p − 1 ) > 2 p + 1 3(p-1)>2p+1 3 ( p − 1 ) > 2 p + 1 , exactly two classes in W W W contain p − 1 p-1 p − 1 terms. Deleting a term from either of them leaves at most one such class, a contradiction.
Both cases give a contradiction. Therefore s p ∗ ≤ 2 p + 1 s_p^*\le2p+1 s p ∗ ≤ 2 p + 1 .
For the reverse inequality, let A = 1 p − 1 ( 1 − p ) A=1^{p-1}(1-p) A = 1 p − 1 ( 1 − p ) and B = ( − 1 ) p − 1 ( p − 1 ) B=(-1)^{p-1}(p-1) B = ( − 1 ) p − 1 ( p − 1 ) . Then ∣ A ∣ = ∣ B ∣ = p \lvert A\rvert=\lvert B\rvert=p ∣ A ∣ = ∣ B ∣ = p , A ‾ = 1 p \overline{A}=1^p A = 1 p , B ‾ = ( − 1 ) p \overline{B}=(-1)^p B = ( − 1 ) p , and σ ( A ) = σ ( B ) = 0 \sigma(A)=\sigma(B)=0 σ ( A ) = σ ( B ) = 0 . Thus A B AB A B has the first form and is exceptional, which gives s p ∗ ≥ 2 p + 1 s_p^*\ge2p+1 s p ∗ ≥ 2 p + 1 . □
Declaration of generative AI and AI-assisted technologies
The authors used a large language model during the preparation of this manuscript for assistance with mathematical exploration, checking arguments, organization and language editing. The authors are responsible for the mathematical statements, proofs, references and final text.
References
Cong Lin
Center for Combinatorics, Nankai University, Tianjin, P. R. China
E-mail: 9820260111@nankai.edu.cn