Kemperman结构定理之推广

Kemperman

410075

E-mail:xschen12000@yahoo.com.cn

510275

E-mail:mcsypz@zsu.edu.cn

G Abelian,A,B⊆G.1960,Kemperman

|A+B|=|A|+|B|−1(A,B).

|A+B|=|A|+|B|+k(k,k≥−1)(A,B), Kemperman.

Abelian;;Kneser

MR(2000)11P70,11B75,20K01

O156.7

An Extension of Kemperman Structure Theorem

Xue Sheng SHEN

Department of Mathematics,Central South University,Changsha410075,P.R.China

E-mail:xschen12000@yahoo.com.cn

Ping Zhi YUAN

Department of Mathematics,Sun Yat-Sen University,Guangzhou510275,P.R.China

E-mail:mcsypz@zsu.edu.cn

Abstract In this paper,we investigate the structure of the those pairs(A,B)offinite

subsets of an Abelian group satisfying|A+B|=|A|+|B|+k(k≥−1),and extend

the Kemperman structure theorem.

Keywords Abelian groups;quasi-periodic decomposition;Kneser theorem

MR(2000)Subject Classification11P70,11B75,20K01

Chinese Library Classification O156.7

1

(G,+,0)Abelian.A,B⊆G,A+B=:{a+b|a∈A,b∈B}.

v c(A,B)c=a+b(a∈A b∈B),v c(A,B)=|{c=a+b|a∈A,b∈B}|.ηb(A,B)v c(A,B)=1c∈A+b,ηb(A,B)=|{c∈A+b|v c(A,B)=1}|.B⊆A,A\\B={a|a∈A.a/∈B},,A A=G\\A.

:2005-05-30;:2005-09-15

:(10471152);(04009801)134049 A⊆G H-(periodic),G H

.,A(aperiodic).φ:G→G/H.α∈(A+H)\\A

A H-(hole).Abelian A,B,|A+B|Cauchy

,|G|,|A+B|≥min{|G|,|A|+|B|−1}([1]).100,

(Cauchy–Davenport)Davenport[2].,Kneser

Abelian[3].

Kneser[3]A,B Abelian G.H=H(A+B)

A+B+H=A+B,|A+B|≥|A+H|+|B+H|−|H|.: |A+B|≤|A|+|B|−1,|A+B|=|A+H|+|B+H|−|H|.

,|A+B|A B|A+B|

,|A+B|≤|A|+|B|−1(A,B)(critical pairs).1960, Kemperman([4] 5.1).[4] 5.1Kemperman (KST).2005,David J.Grynkiewicz[5], KST.

[4,5].

A⊆G,H G,A(quasi-period)H

(quasi-periodic composition)A A=A1∪A0,A1∩A0=∅(A1,A0

),A1H-A0H-.A⊆G

(quasi-periodic),A A1.A=A1∪A0

H,A1A H-(H-periodic part),A0A

(aperiodic part)(A A0).A0,

(reduced).A H A1∪A0 ,A H ≤H A 0⊆A0A 1∪A 0.,

H A=A1∪A0,B=B1∪B0A+B=C

H(C\\(A0+B0))∪(A0+B0).A⊆G(punctured periodic set),A:α∈G\\A,A∪{α}H-.A H

.

Kemperman[4,5].

Kemperman(KST)G Abelian,A,B⊆G, |A+B|=|A|+|B|−1.,A+B,c v c(A,B)=1 A,B H A=A1∪A0

B=B1∪B0,

(i)v c(φ(A),φ(B))=1,c=φ(A0)+φ(B0).

(ii)|φ(A)+φ(B)|=|φ(A)|+|φ(B)|−1,

(iii)(pair)(A0,B0)(|A0+B0|=|A0|+|B0|−1):

(I)|A0|=1|B0|=1;

(II)A0B0d,d|A0|+|B0|−1,

|A0|≥2,|B0|≥2(A0+B0d,v c(A0,B0)=1 c∈A0+B0);

(III)|A0|+|B0|=|H|+1,g0v g0(A0,B0)=1(B0

B0=(g0−A0∩(g1+H))∪{g0−g1},g1∈A0);

(IV)A0,B0B0=g0−A0∩(g1+H),g1∈A0(A0+B0=6:Kemperman1341 (g0+H)\\{g0}),c v c(A0,B0)=1.

1(III)“g0v g

(A0,B0)=1”“g0

(A0,B0)=1”;(IV),“c v c(A0,B0)=1”.Kemperman v g

([4] 5.1.).

:

P1Kneser:|A+B|≤|A|+|B|−1,|A+B|=|A+H|+|B+H|−|H|, :|A+B|≥|A|+|B|,G H|A+B|=|A+H|+|B+H|−|H|?

P2Kemperman(KST)|A+B|=|A|+|B|−1(A+B

,c v c(A,B)=1)(A,B).|A+B|=|A|+|B|+k(k ),(A,B)?

P1,A+B, 1.,P2 (2),Kemperman.3[5] 2.4.

..

1G Abelian.A,B⊆G,A+B=C1∪C0 H,,|H|≥|C0|+2.k:−1≤k≤]−2,|C0|−1},|A+B|=|A|+|B|+k,:

min{[|H|−|C0|

2

(i)|A+B+H|=|A+H|+|B+H|−|H|;

(ii)a0∈A,b0∈B,C0=A∩(a0+H)+B∩(b0+H),|C0|≤|A∩(a0+H)|+ |B∩(b0+H)|+k.

G Abelian,A,B⊆G:|A+B|=|A|+|B|−1.

(i)A+B H-,c0=a0+b0∈A+B,c0+H= A∩(a0+H)+B∩(b0+H),|A∩(a0+H)|+|B∩(b0+H)|=|H|+1.

(ii)A+B=C1∪C0H,,|H|≥|C0|+2, C0=A∩(a0+H)+B∩(b0+H),|A∩(a0+H)|+|B∩(b0+H)|=|C0|+1,a0∈A,b0∈B c=a0+b0∈C0.

2G Abelian,A,B⊆G.A+B H-,

c0v c

(A,B)=1,A+B=C1∪C0H,

.A B H2|H|−(|A∩(a0+H)|+|B∩(b0+H)|)(hole), |(A+H)\\A|+|(B+H)\\B|≤2|H|−(|A∩(a0+H)|+|B∩(b0+H)|), c0=a0+b0∈C0,a0∈A,b0∈B(A+B,C0=c0+H),

k(−1≤k≤|C0|−1)|A+B|=|A|+|B|+k:

(i)A=A1∪A0,B=B1∪B0H;

(ii)v c(φ(A),φ(B))=1,c=φ(A0)+φ(B0),|A+B+H|=|A+H|+|B+H|−|H|;

(iii)C0=A∩(a0+H)+B∩(b0+H),|C0|=|A∩(a0+H)|+|B∩(b0+H)|+k.

3[5] 2.4.3,A+B

Kemperman.

3A,B,C Abelian,A+B=C|A+B|=|A|+|B|−1.

C H-,c0=a0+b0∈C,C=C1∪C0H

(C),|H|≥|C0|+2,Kemperman

H A0+B0=C0.

1342

49

2

1

Kemperman–Scherk

[6]

.

1G Abelian

,A,B ⊆G

,

c ∈A +B ,

v c (A,B )≥|A |+|B |−|A +B |.

2

G Abelian

,A,B ⊆G

.

|A |+|B |>|G |,

A +

B =G (

[3]).

Kneser

Kneser

[3]

.

3n ≥2,G Abelian ,C G ,C =C 1∪C 2∪···∪C n ,

C 1,...,C n C

,|C |+|H (C )|≥min(|C i |+|H (C i )|:i =1,...,n ).

4([4]

[7])G Abelian ,A,B ⊆G

,

|A +B |=|A |+|B |−1

min {|A |,|B |}>1,

(i)A,B

d

,

d

ord(d )≥|A |+|B |+1;

(ii)A +B =(g +H )\\{g },H

G

,g ∈G ;

(iii)A +B

(quasi-periodic).

5G Abelian

,A,B ⊆G ,H G .

A +

B H -,c 0=a 0+b 0,v c 0(A,B )=1;A +B =

C 1∪C 0

H ,.φ:G →G/H ,φA =:A,φa =:a .φC 0=c 0=a 1+b 1=···=a ρ+b ρφC 0ρ(A +B H -,C 0A +B H -c 0+H ).A i =A ∩φ−1a i =A ∩(a i +H )B i =B ∩φ−1b i =B ∩(b i +H ),i =1,...,ρ.A =(A \\(A 1∪···A ρ))B =(B \\(B 1∪···B ρ)),

:

(i)|A +H |=(|φA |−ρ)|H |

|B +H |=(|φB |−ρ)|H |.

(ii)C 0=

ρi =1(A i +B i ),|A 1|+|B 1|≤|C 0|+1|A i |+|B i |≤|H |(i =

2,...,ρ).

(iii)

k

−1≤k ≤|C 0|−1

,

|A +B |=|A |+|B |+k ,

(a)|φ(A +B )|=|φA |+|φB |−ρ,

|A +B +H |=|A +H |+|B +H |−ρ|H |,

(b)|A i |+|B i |≥|C 0|−k (i =1,...,ρ).

(i)

A =A ∪(A 1∪···A ρ),

A +H =(A +H )∪(

ρ

i =1(A i

+H )).

C 0=(A 1+B 1)∪···∪(A ρ+B ρ),C 1=(A +B )\\C 0=(A +B )\\((A 1+B 1)∪···∪(A ρ+B ρ)).

|A +H |=(|φA |−ρ)|H |.

A i +H A +H

H -

,

i =1,...,ρ.

,i 0(1≤i 0≤ρ),

A i 0+H ⊆A +H ,

A i 0+

B i 0+H ⊆A +B i 0+H ⊆A +B +H

⊆(A +B )\\((A 1+B 1)∪···∪(A ρ+B ρ))+H =C 1+H =C 1,

A i 0+

B i 0⊆

C 1=(A +B )\\((A 1+B 1)∪···∪(A ρ+B ρ)).,

|A +H |=

(|φA |−ρ)|H |.B .

(ii)

1

A +B

,

C 0=c 0+H =a 0+b 0+H =(A 1+B 1)∪···∪(A ρ+B ρ).

v c 0(A,B )=1,A i +B i (A 1+B 1),v c 0(A 1,B 1)=1.1,|A 1|+|B 1|≤|C 0|+1.c 0/∈A i +B i (i =2,...,ρ)A i +B i (i =2,...,ρ)C 0

.2|A i |+|B i |≤|H |(i =2,...,ρ).

6

:Kemperman

1343

,|A i |+|B i |>|H |,|A ∩(a i +H )|+|B ∩(b i +H )|>|H |,|(A i −

a i )∩H |+|(B i −

b i )∩H |>|H |.

2,(A i −a i )∩H +(B i −b i )∩H =H ,A ∩(a i +H )+B ∩(b i +H )=a i +b i +H ,A i +B i =a i +b i +H =C 0,.

2A +B =C 1∪C 0

H

,

.

,i (1≤i ≤ρ),|A i |+|B i |≥|C 0|+2.C i =A i +B i ,Kneser

|C i |+|H (C i )|=|A i +B i |+|H (A i +B i )|≥|A i |+|B i |≥|C 0|+2.C 0=C 1∪···∪C ρ,Kneser (3)

|C 0|+|H (C 0)|≥min 1≤i ≤ρ

{|C i |+|H (C i )|}≥|C 0|+2,

|H (C 0)|≥2,C 0

,

.

2

|A i |+|B i |≤|H |(i =1,...,ρ).

(iii)

A i ,

B i ,A

B ,

ρ

i =1

(|A i |+|B i |)=|A |−|A |+|B |−|B |.

(1)

(i)A +H |φA |−ρH -,B +H |φB |−ρH -,C =A +B C 1C 0,C 1|φC |−1H -,|A |≤(|φA |−ρ)|H |,|B |≤(|φB |−ρ)|H ||A |+|B |+k =|A +B |=(|φC |−1)|H |+|C 0|.(1),

ρ

i =1

(|A i |+|B i |)≥(ρ−1)|H |+|C 0|−k +λ|H |,(2)

λ=ρ+|φC |−|φA |−|φB |≥0.(2),(ii)−1≤k ≤|C 0|−1λ=0,|φ(A +B )|=|φA |+|φB |−ρ,|A +B +H |=|A +H |+|B +H |−ρ|H |,

|A i |+|B i |≥

|C 0|−k (i =1,...,ρ).

.3

1

5.

ρ=1.

ρ≥2.5(iii)(2)ρ

i =1

(|A i |+|B i |)≥(ρ−1)|H |+|C 0|−k.

(3)

|A 1|+|B 1|≤|C 0|−k −1,|A i |+|B i |≤|H |(i =2,...,ρ)(3)

.

|C 0|−k ≤|A 1|+|B 1|≤|C 0|+1.

,

−1≤k ≤[|H |−|C 0|

2

]−2ρ

i =2

(|A i |+|B i |)≥(ρ−1)|H |+|C 0|−k −(|A 1|+|B 1|)≥(ρ−1)|H |+|C 0|−k −(|C 0|+1)

≥(ρ−1)|H |−(k +1)≥(ρ−1)|H |− |H |−|C 0|

2

−1

≥(ρ−1)|H |−l,

l =[|H |−|C 0|

2

]−1,i (2≤i ≤ρ),

i =2,

|A 2|+|B 2|≥|H |−l.

C 2=A 2+B 2,

Kneser

|C 2|+|H (C 2)|=|C 2+H (C 2)|+|H (C 2)|≥|A 2|+|B 2|≥|H |−l =|c 0+H |−l.

(4)

1344

49

C 2+H (C 2)=C 2⊂C 0,C 0c 0+H (A +B ),H (C 2)H .(4)

|H (C 2)|≥|c 0+H |−|C 2|−l ≥|H |−|C 0|−l

=|H |−|C 0|−l ≥|H |−|C 0|−

|H |−|C 0|

2+1=|H |−|C 0|+22

>1,(5)H (C 2)H .

|(c 0+H )\\C 2|≤|H (C 2)|+l <2|H (C 2)|(|H (C 2)|≤[|H |−|C 0|2]−1≤|H |−|C 0|−2

2,(5)).:c 0+H,C 2H (C 2),|(c 0+H )\\C 2|≤|H (C 2)|,(c 0+H )\\C 2⊆d +H (C 2)(d ∈c 0+H ),D =:(c 0+H )\\C 0⊆(c 0+H )\\C 2⊆d +H (C 2),

C 0=(c 0+H )\

D =((c 0+H )\\(d +H (C 2)))∪((d +H (C 2))\\D )(H (C 2)A +

B =

C 1∪C 0,ρ=1,

(i)|A +B +H |=|A +H |+|B +H |−|H |,(ii)a 0∈A,b 0∈B ,C 0=A ∩(a 0+H )+B ∩(b 0+H ),|C 0|≤|A ∩(a 0+H )|+

|B ∩(b 0+H )|+k .1.

(i)Kneser :

|A +B |=|A +H |+|B +H |−|H |=|(A −a 0)+H |+|(B −b 0)+H |−|H |

≥|(A −a 0)∪H |+|(B −b 0)∪H |−|H |

=(|A −a 0|+|H |−|(A −a 0)∩H |)+(|B −b 0|+|H |−|(B −b 0)∩H |)−|H |=|A |+|B |+|H |−(|(A −a 0)∩H |+|(B −b 0)∩H |).

|A +B |=|A |+|B |−1,|(A −a 0)∩H |+|(B −b 0)∩H |≥|H |+1>|H |.

(6)

2

(A −a 0)∩H +(B −b 0)∩H =H,

a 0+

b 0+H =A ∩(a 0+H )+B ∩(b 0+H ),

1v c 0(A,B )=1(c 0=a 0+b 0)

|H |=|A ∩(a 0+H )+B ∩(b 0+H )|≥|A ∩(a 0+H )|+|B ∩(b 0+H )|−1.

(7)

(6),(7)

(i).

(ii)1,(ii)|C 0|≤|A ∩(a 0+H )|+|B ∩(b 0+H )|−1C 0=A ∩(a 0+H )+B ∩(b 0+H ).C 0

,Kneser |C 0|≥|A ∩(a 0+H )|+|B ∩(b 0+H )|−1,(ii)

.2

φ:G →G/H ,φC 0=c 0=a 1+b 1=···=a ρ+b ρφC 0

ρ

.A i =A ∩φ−1a i =A ∩(a i +H ),B i =B ∩φ−1b i =B ∩(b i +H ).,A 0=A 1=A ∩(a 0+H ),B 0=B 1=B ∩(b 0+H ),|A i |+|B i |≤

|H |(i =2,...,ρ)(5(ii)),

ρ

i =1

(|A i |+|B i |)≥(ρ−1)|H |+|C 0|−k +λ|H |,(8)

λ=ρ+|φC |−|φA |−|φB |≥0.

k ≤|C 0|−1,

(8)

λ=ρ+|φC |−|φA |−|φB |=0,

|A +B +H |=|A +H |+|B +H |−ρ|H |.

(9)

(8)

ρ

i =1

(|A i |+|B i |)≥(ρ−1)|H |+|C 0|−k.(10)

6:Kemperman1345

2.

1A+B H-,c0,v c

(A,B)=1,

|(A+H)\\A|+|(B+H)\\B|≤2|H|−(|A0|+|B0|),(11) (|A+H|+|B+H|−ρ|H|)−(|A|+|B|)≤(2−ρ)|H|−(|A0|+|B0|).|A+B|=|A|+|B|+k

(9),

|A0|+|B0|≤(2−ρ)|H|−k.(12)−1≤k≤|C0|−1,C0=c0+H=a0+b0+H,(12)ρ=1|A0|+|B0|≤|H|−k.

(10)|A0|+|B0|≥|H|−k,2(ii)(iii).

(i).A1=A\\A0,B1=B\\B0.(ii)(iii)

|A|+|B|+k=|A+B|=|A+H|+|B+H|−|H|

=|(A−a0)+H|+|(B−b0)+H|−|H|≥|(A−a0)∪H|+|(B−b0)∪H|−|H|

=(|A−a0|+|H|−|(A−a0)∩H|)+(|B−b0|+|H|−|(B−b0)∩H|)−|H|

=|A|+|B|+|H|−(|(A−a0)∩H|+|(B−b0)∩H|)

=|A|+|B|+|H|−(|A0|+|B0|)≥|A|+|B|+k,

(A−a0)∪H=(A−a0)+H(B−b0)∪H=(B−b0)+H,A+H=A∪(a0+H) B+H=B∪(b0+H),A1=A\\(A∩(a0+H))=(A+H)\\(a0+H)B1=B\\(B∩(b0+H))= (B+H)\\(b0+H)H-,(i)

2A+B=C1∪C0H,.1 |A+B+H|−(|A|+|B|)≤(2−ρ)|H|−(|A0|+|B0|).|A+B+H|=|A+B|+|H|−|C0| |A+B|=|A|+|B|+k,

|A0|+|B0|≤(1−ρ)|H|+|C0|−k.(13)−1≤k≤|C0|−1C0,(13)ρ=1|A0|+|B0|≤|C0|−k.

(10)|A0|+|B0|=|C0|−k,2(ii)(iii).

(i).

|A+B+H|=|A+H|+|B+H|−|H|

=|(A−a0)+H|+|(B−b0)+H|−|H|≥|(A−a0)∪H|+|(B−b0)∪H|−|H|

=(|A−a0|+|H|−|(A−a0)∩H|)+(|B−b0|+|H|−|(B−b0)∩H|)−|H|

=|A|+|B|+|H|−(|(A−a0)∩H|+|(B−b0)∩H|)

=|A|+|B|+|H|−(|A0|+|B0|).

(iii)|A+B+H|=|A+B|+|H|−|C0|=|A|+|B|+k+|H|−|C0|=|A|+|B|+|H|−(|A0|+|B0|), (A−a0)∪H=(A−a0)+H(B−b0)∪H=(B−b0)+H,A+H=A∪(a0+H) B+H=B∪(b0+H),A1=A\\(A∩(a0+H))=(A+H)\\(a0+H)B1=B\\(B∩(b0+H))= (B+H)\\(b0+H)H-,(i).

2.(ii)

|A+B|+|H|−|C0|=|A+H|+|B+H|−|H|.(14) (A+B H-,C0H-c0+H).(i)|A+H|=|A1|+|H|,|B+H|= |B1|+|H|.(iii)|C0|=|A0|+|B0|+k.(14)|A+B|=|A|+|B|+k.

2.

2,.1349

(1)G=Z16={0,1,2,...,15}16,H={0,4,8,12}.A+B= {0,1,4,5,8,9,12,13}=(0+H)∪(1+H)H-.A={0,4,5,8,9,12},B= {0,8},|A+B|=|A|+|B|(2,k=0).A0=A∩(1+H)={5,9},B0= B∩(0+H)={0,8}C0=1+H,A B

|A+H\\A|+|B+H\\B|≤2|H|−(|A0|+|B0|).

A B2.

(2)G=Z32={0,1,2,...,31}32,H={0,4,8,12,16,20,24,28}.

A+B={0,1,4,8,9,12,16,17,20,21,24,25,28,29}=(0+H)∪{1,9,17,21,25,29} H,.

A={0,4,5,8,12,16,17,20,21,24,28},B={4,12},|A+B|=|A|+|B|+1 (2,k=1).A0=A∩(5+H)={5,17,21},B0=B∩(4+H)={4,12}

C0={1,9,17,21,25,29},A B

|A+H\\A|+|B+H\\B|≤2|H|−(|A0|+|B0|).

A B2.

31A+B H-,c=a0+b0∈A+B;

(i):a0∈A,b0∈B,c=a0+b0∈C0=a0+b0+H=A∩(a0+H)+B∩(b0+H),

|A∩(a0+H)|+|B∩(b0+H)|=|H|+1.(15) Kneser,|A+B|=|A|+|B|−1(15)

|(A+H)\\A|+|(B+H)\\B|=|H|−1≤2|H|−(|A∩(a0+H)|+|B∩(b0+H)|).

21Kemperman.

2A+B=C1∪C0H,(C),|H|≥|C0|+2.(ii):a0∈A,b0∈B,c=a0+b0∈C0=A∩(a0+H)+B∩(b0+H)⊂a0+b0+H,

|A∩(a0+H)|+|B∩(b0+H)|=|C0|+1.(16) C0,4(A∩(a0+H),B∩(b0+H))(I),(II)(IV).

1(i),|A+B|=|A|+|B|−1(16)

|(A+H)\\A|+|(B+H)\\B|=(|A+H|+|B+H|−|H|)+|H|−(|A|+|B|)

=|A+B+H|+|H|−(|A+B|+1)

≤2|H|−(|A∩(a0+H)|+|B∩(b0+H)|).

21Kemperman.3.

23[4] 4.5.Kemperman.

[1]Cauchy A.L.,Recherches sur les nombres,J.´E cole Polytech.,1813,9:99–116.

[2]Davenport H.,On the addition of residue classes,J.London Math.Soc.,1935,10:30–32.

[3]Nathanson M.B.,Additive number theory,inverse problems and the geometry of sumsets,graduate texts in

mathematices,New York:Springer-Verlag,1996,165.

[4]Kemperman J.H.B.,On small sumsets in an Abelian group,Acta Math.,1960,103:63–88.

[5]Grynkiewicz D.,Quasi-periodic decompositions and the Kemperman structure theorem,Eueopean J.Combin.,

2005,26(5):559–575.

[6]Scherk P.,Distinct elements in a set of sums,Amer.Math.Monthly,1955,62:46.

[7]Lev V.,On small sumsets in Abelian groups.Structure theory of set addition,Asterisque,1999,xv(258):

317–321.