D:\FINAL_TEX\...\Article.DVI


Mathematical Problems of Computer Science 42, 5{16, 2014.

Zer o-Fr ee Sets in Abelian Gr oups

V a h e G. S a r g s ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: vahe sargsyan@ymail.com, vahe sargsyan@ipia.sci.am

Abstract

The subset A of the group G is called zero-free if the equation x + y + z = 0 has no
solutions in the set A: The upper and lower estimates were obtained for the maximum
cardinality of the zero-free set in an Abelian group, and the asymptotic behavior of
the logarithm of the number of zero-free sets in an Abelian group was established.

Keywords: Sum-free set, Characteristic function, Group, Progression, Coset.

1 . In t r o d u c t io n

L e t G b e a s e t wit h a c e r t a in a d d it io n o p e r a t io n o n it . Th e s u b s e t A µ G is c a lle d sum-free
( S FS ) if t h e e qu a t io n x + y = z h a s n o s o lu t io n s in t h e s e t A: Th e fa m ily o f a ll S FS in G
we d e n o t e b y SF ( G ) . Fo r n a t u r a l n u m b e r s m a n d n t h e s e t o f n a t u r a l n u m b e r s x, s u c h t h a t
m · x · n; we d e n o t e b y [m; n]:

In 1 9 8 8 , P . Ca m e r o n a n d P . E r d Äo s [1 ] a s s u m e d t h a t SF ( [1 ; n]) = O ( 2 n=2 ) : In p a r t ic u la r ,
t h e y p r o ve d t h a t t h e r e e xis t c o n s t a n t s c0 a n d c1 s u c h t h a t jSF ( [[n=3 ]; n]) j » c0 2 n=2 fo r e ve n
n; a n d jSF ( [[n=3 ]; n]) j » c1 2 n=2 fo r o d d n:

N . Ca lkin [2 ] a n d , in d e p e n d e n t ly, N . A lo n [3 ] p r o ve d t h a t 1 lo g jSF ( [1 ; n]) j · ( n= 2 ) ( 1 +
¹o ( 1 ) ) :

Th e p r o o f o f t h e Ca m e r o n -E r d Äo s h yp o t h e s is a n d t h e a s ym p t o t ic b e h a vio r o f t h e n u m b e r
o f S FS in t h e in t e r va l [1 ; n] we r e fo u n d b y S a p o z h e n ko [4 ] a n d , in d e p e n d e n t ly, b y B . Gr e e n [5 ].
It is p r o ve d t h a t jSF ( [1 ; n]) j » c( n) 2 n=2; wh e r e t h e c o n s t a n t c( n) d e p e n d s o n t h e p a r it y o f
n:

In 1 9 9 1 , N . A lo n [3 ] p r o ve d t h a t t h e n u m b e r o f S FS o f a n a r b it r a r y ¯ n it e g r o u p d o e s n o t
e xc e e d 2 n=2+¹o(n): Fu r t h e r , t h e g ive n r e s u lt b e c a m e m o r e a c c u r a t e fo r d i®e r e n t s u b c la s s e s o f
¯ n it e A b e lia n g r o u p s .

In 2 0 0 2 , A . A . S a p o z h e n ko [6 ] a n d , in d e p e n d e n t ly, L e v-L u c z a k-S c h o e n [7 ] o b t a in e d t h e
a s ym p t o t ic s o f m a xim u m p o s s ib le n u m b e r o f S FS fo r ¯ n it e A b e lia n g r o u p s c o n t a in in g a t
le a s t o n e s u b g r o u p o f in d e x 2 . Th e g r o u p o f r e s id u e s m o d u lo n is d e n o t e d b y Zn:

In 2 0 0 2 V . L e v a n d T. S c h o e n [8 ] p r o ve d t h a t if p is a s u ± c ie n t ly la r g e p r im e n u m b e r ,
t h e n t h e fo llo win g e s t im a t e s a r e t r u e :

2 b(p¡2)=3c ( p ¡ 1 ) ( 1 + O ( 2 ¡"1p ) ) · jSF ( Zp ) j · 2 p=2¡"2p;
1hereinafter log x = log2 x

5



6 Zero-Free Sets in Abelian Groups

wh e r e "1 a n d "2 a r e p o s it ive c o n s t a n t s .
In 2 0 0 5 , B . Gr e e n a n d I. R u z s a [9 ] u s in g t h e Fo u r ie r t r a n s fo r m , o b t a in e d t h e a s ym p t o t ic s

o f t h e lo g a r it h m o f t h e n u m b e r o f S FS in ¯ n it e A b e lia n g r o u p s . Th e y p r o ve d t h a t fo r a n y
¯ n it e G A b e lia n g r o u p lo g jSF ( G) j » ¸ ( G) is t r u e , wh e r e ¸ ( G) is t h e m a xim u m c a r d in a lit y
S FS in G:

In 2 0 0 9 , A .A . S a p o z h e n ko [1 0 ] o b t a in e d t h e a s ym p t o t ic b e h a vio r o f t h e n u m b e r o f S FS
in t h e g r o u p s o f p r im e o r d e r .

T heor em 1: F or any ® 2 f¡1 ; 1 g there exists a constant c®; such that for any " > 0 there
exists a natural number N; such that for any simple p of the form p ´ ® ( m o d 3 ) , such
that p > N, the following inequalities are performed:

1 · jSF ( Zp ) j
c® ( p ¡ 1 ) 2 b(p¡2)=3c

< 1 + ":

A s t o t h e p r o b le m o f ¯ n d in g t h e m a xim u m c a r d in a lit y S FS in a n A b e lia n g r o u p , it is
¯ n a lly r e s o lve d .

In 1 9 6 9 H . P . Y a p a n d P . D ia n a n d a [1 1 ] g o t t h e u p p e r a n d lo we r e s t im a t e s o f m a xim u m
c a r d in a lit y S FS in a n A b e lia n g r o u p , s h o win g t h a t

T heor em 2: L et G be an Abelian group of the order n: Then the following statements are
true:

( i) if n has a prime divisor comparable with 2 modulo 3 ; then

¸ ( G) =
n

3
¢
Ã

1 +
1

p

!
;

where p is the smallest prime divisor of n; comparable to 2 modulo 3 ,

( ii) if it does not have prime divisors comparable with 2 modulo 3 ; but 3 jn; then

(̧ G ) =
n

3
;

( iii) if all prime divisors of n have the form p ´ 1 ( m o d 3 ) ; then

n

3
¢
µ

º ¡ 1
º

¶
· ¸ ( G) · n ¡ 1

3
;

where º is the exponent of the group G:

Th e ¯ n a l s o lu t io n o f t h e p r o b le m o f ¯ n d in g t h e m a xim u m c a r d in a lit y S FS in a n A b e lia n
g r o u p wa s o b t a in e d in [9 ] b y B . Gr e e n a n d I. R u z s a in 2 0 0 5 .

T heor em 3: L et G be an Abelian group of the order n: If n is divided only into prime p ´ 1
( m o d 3 ) ; then the following equality holds:

(̧ G) =
( º ¡ 1 ) n

3 º
;

where º is the exponent of the group G:



V. Sargsyan 7

Th e s u b s e t A o f t h e g r o u p G is c a lle d zero-free ( ZFS ) , if it h a s n o s o lu t io n s t o t h e e qu a t io n

x + y + z = 0 : ( 1 )

Th e fa m ily o f a ll ZFS in G is d e n o t e d b y ZF ( G ) ; a n d b y ¹( G ) t h e m a xim u m c a r d in a lit y ZFS
in G: In c a s e ZFS a r e m is s in g in a n A b e lia n g r o u p , t h e n e it h e r t h e e xp o n e n t o f t h e g r o u p is
e qu a l t o 3 ( it e m ( iii) o f Th e o r e m 5 ) , o r t h e g r o u p c o n s is t s o n ly o f a z e r o e le m e n t ( it e m ( iv) o f
Th e o r e m 5 fo r n = 1 ) . In t h e s e c a s e s it is s u p p o s e d t h a t jZF ( G) j = 0 a n d ¹ ( G) = 0 : In t h is
p a p e r , u s in g t h e m e t h o d s o f [9 ] t h e a s ym p t o t ic b e h a vio r o f t h e lo g a r it h m o f t h e n u m b e r o f
ZFS is s e t in a n A b e lia n g r o u p , a n d a ls o o b t a in e d t h e u p p e r a n d lo we r b o u n d s o f m a xim u m
c a r d in a lit y ZFS in a n A b e lia n g r o u p . In p a r t ic u la r , t h e fo llo win g t wo t h e o r e m s a r e p r o ve d :

T heor em 4: L et G be an Abelian group of the order n: Then the following equality is true:

lo g jZF ( G) j = ¹( G ) + ¹o( n) :

T heor em 5: L et G be an Abelian group of the order n with the exponent º: Then the fol-
lowing statements are true:

( i) if n has a prime divisor comparable with 2 modulo 3 ; then

¹( G ) =
n

3
¢
Ã

1 +
1

p

!
;

where p is the smallest prime divisor of n; comparable to 2 modulo 3 ;

( ii) if n has no prime divisors p ´ 2 ( m o d 3 ) ; but 3 jn and º > 3 ; then

n

3
¢
µ

º ¡ 3
º

¶
· ¹( G) · n

3
;

( iii) if º = 3 ; then
¹( G ) = 0 ;

( iv) if all prime divisors of n have the form p ´ 1 ( m o d 3 ) ; then

n

3
¢
µ

º ¡ 1
º

¶
· ¹( G ) · n ¡ 1

3
:

2 . Th e A s ym p t o t ic s o f t h e L o g a r it h m o f t h e N u m b e r o f Ze r o -fr e e S e t s in a n
A b e lia n Gr o u p

L e t G b e a n A b e lia n g r o u p o f t h e o r d e r n: The character o f t h e g r o u p G is c a lle d a m a p p in g
° : G ! C s u c h , t h a t fo r a n y x 2 G h o ld s j° ( x) j = 1 a n d ° ( x + y ) = ° ( x ) ° ( y ) : Th e s e t o f
a ll c h a r a c t e r s o f t h e g r o u p G is d e n o t e d b y ¡ : N o t e t h a t ¡ fo r m s a g r o u p wit h t h e o p e r a t io n
( °1¤°2 ) ( x ) = °1 ( x) °2 ( x ) : L e t f : G ! R: The F ourier transform f is t h e fu n c t io n bf : G ! C;
d e ¯ n e d b y t h e e qu a lit y bf ( ° ) =

P
x2G

f ( x ) ° ( x) :

2 .1 D e ¯ n it io n s a n d A u xilia r y S t a t e m e n t s



8 Zero-Free Sets in Abelian Groups

Fo r t h e p r o o f o f Th e o r e m 4 u s e t h e m e t h o d o f g r a n u la r iz a t io n . Th e e s s e n c e o f t h is m e t h o d
is t h a t fo r t h e e va lu a t io n o f t h e c a r d in a lit y o f t h e s e t ZF ( G ) t h e fa m ily F; o f t h e s o c a lle d
\ g r a in s " F 2 F is c o n s t r u c t e d , s u c h t h a t e ve r y e le m e n t o f t h e s e t ZF ( G ) is c o n t a in e d in
s o m e g r a in F o f t h e c o n s t r u c t e d fa m ily F; wh e r e in lo g jFj = ¹o( n) ; a n d in e a c h g r a in F 2 F
t h e r e a r e ¹o( n2 ) s o lu t io n s o f t h e e qu a t io n ( 1 ) , t h a t is , a fa m ily o f s u b s e t s o f t h e g r o u p G is
c o n s t r u c t e d h a vin g t h e fo llo win g p r o p e r t ie s :

² lo g jFj = ¹o( n) ;

² fo r a n y A 2 ZF ( G ) t h e r e e xis t s a g r a in F 2 F s u c h t h a t A µ F;

² in e a c h g r a in F 2 F t h e r e e xis t ¹o ( n2 ) s o lu t io n s o f t h e e qu a t io n ( 1 ) .

Th e r e a r e t wo t yp e s o f a g r a n u la r s t r u c t u r e t h a t we will c o n s id e r .
Th e u n io n o f c o s e t s o f t h e g r o u p G o f s o m e s u b g r o u p o f o r d e r n o t le s s t h a n L is c a lle d

L-granular of coset type.
L e t L b e a n in t e g e r a n d d 2 G; wh e r e in ord ( d) ¸ L; wh e r e ord( d) is t h e o r d e r o f t h e

e le m e n t d: Co n s id e r t h e s u b g r o u p G; g e n e r a t e d b y t h e e le m e n t d; a n d d ivid e e a c h o f it s
c o s e t s in t o bord ( d) =Lc p r o g r e s s io n s o f t h e fo r m fx + id j 0 · i · L ¡ 1 g a n d o n e " r e s id u a l"
s e t o f t h e c a r d in a lit y le s s t h a n L: Fo r e a c h d 2 G ¯ x o n e s u c h p a r t it io n . Th e u n io n o f t h e
o b t a in e d p r o g r e s s io n s is c a lle d L-granular of progression type.

Th e p r o o fs o f t h e fo llo win g t wo le m m a s a r e a va ila b le in [9 ].

Lemma 1: Suppose that n is larger than some absolute constant and that L ·
p

n: Then
the number of subsets of an Abelian group G of the order n; which are L -granular (of either
coset or progression type) is at most 2 3n=L:

Lemma 2: Suppose that ½ is smaller than some absolute positive constant, and that n is
su± ciently large. Then the number of subsets of an n-element set of cardinality at most ½n
is not more than 2 n

p
½:

Th e p r o o f o f t h e fo llo win g le m m a c a n b e fo u n d in [1 2 ].

T heor em 6: L et m ¸ 3 be a ¯xed integer, and suppose that A1; : : : ; Am are subsets of
an Abelian group G of the order n; such that there are ¹o ( nm¡1 ) solutions to the equation
a1 + : : : + am = 0 with ai 2 Ai for all i: Then we may remove ¹o( n) elements from each Ai so
as to leave sets A0i; such that there are no solutions to a

0
1 + : : : + a

0
m = 0 with a

0
i 2 A0i for all

i:

Th e e s s e n c e o f t h e fo llo win g le m m a is t h a t fo r e ve r y A 2 ZF ( G) \ a s u it a b le " g r a in is
c o n s t r u c t e d .

Lemma 3: (Gr anular ization) L et G be an Abelian group of the order n; and A 2 ZF ( G) ;
" 2

³
0 ; 1

2

´
; L and L0 be positive numbers satisfying the inequality

n > L0 ( 4 L=" )
9¢214¢"¡8

:

Then there is a subset A0 µ G such that

2 .2 Gr a n u la r iz a t io n



V. Sargsyan 9

( i) A0 is either L-granular of progression type, or it is L0-granular of coset type,

( ii) jA n A0j · "n,

( iii) A0 contains not more than "n2 solutions of the equation (1).

fo llo win g c o n d it io n s :

( A ) P is e it h e r a p r o g r e s s io n o f t h e fo r m fid j L ¡ 1 · i · L ¡ 1 g; a n d ord ( d) ¸ 2 L="; o r
a s u b g r o u p o f t h e g r o u p G o f a n o r d e r n o t le s s t h a n L0,

( B ) fo r a n y B µ G a n d ° 2 ¡ t h e in e qu a lit y j bB ( ° ) ( 1 ¡ g ( ° ) ) j · ±n h o ld s , wh e r e g ( ° ) =
jP j¡1 P

p2P
° ( p ) ; a n d B ( x ) is t h e c h a r a c t e r is t ic fu n c t io n o f t h e s u b s e t B:

L e t R1 b e t h e s e t o f c h a r a c t e r s ° s u c h t h a t j bB ( ° ) j > ±n=2 ; a n d ¡ 1 b e t h e s u b g r o u p o f
t h e g r o u p ¡ ; g e n e r a t e d b y t h e s e t R1: Co n s id e r t h e s u b g r o u p G1 o f t h e g r o u p G

G1 = fx 2 G j ° ( x ) = 1 fo r a n y ° 2 ¡ 1g:

Co n s id e r t wo c a s e s :

1 ) L e t jG1j ¸ L0: A s s u m e P = G1: S in c e g ( ° ) 2 [¡ 1 ; 1 ] fo r ° 2 ¡ n ¡ 1 o b t a in t h a t j bB ( ° ) ( 1 ¡
g ( ° ) ) j · 2 j bB ( ° ) j < 2 ±n= 2 = ±n; a n d fo r ° 2 ¡ 1 t h e e qu a lit y j bB ( ° ) ( 1 ¡ g ( ° ) ) j = 0 is
t r u e .

2 ) L e t jG1j < L0: Ch o o s e s u c h d; t h a t if t h e p r o g r e s s io n P = fid j L ¡ 1 · i · L ¡ 1 g;
is t a ke n a s P t h e n t h e r e qu ir e m e n t s o f t h e it e m s ( A ) a n d ( B ) will b e s a t is ¯ e d . N o t e
t h a t wh e n ° 2 ¡ n ¡ 1, t h e it e m ( B ) is e xe c u t e d . N o w e s t im a t e t h e va lu e o f 1 ¡ g ( ° ) :
Fix ° 2 ¡ a n d d e n o t e a r g ° ( d) 2 [¡¼; ¼ ) b y ¯. Th u s , we h a ve

0 · 1 ¡ g ( ° ) = 1 ¡ 1
2 L ¡ 1

L¡1X

j=¡L¡1
( c o s j¯ + i s in j¯ ) =

= 1 ¡ 1
2 L ¡ 1 ¡

2

2 L ¡ 1
L¡1X

j=1

c o s j¯ =
2 L ¡ 2
2 L ¡ 1 ¡

2

2 L ¡ 1
L¡1X

j=1

c o s j¯ =

=
2

2 L ¡ 1
L¡1X

j=1

( 1 ¡ c o s j¯ ) · 1
2 L ¡ 1

L¡1X

j=1

( j¯ ) 2 =
L( L ¡ 1 )

6
¯2 · ( L¯ )

2

6
:

N o t e t h a t if fo r a ll ° 2 R1 t h e r e o c c u r r e d j a r g ° ( d ) j · L¡1
q

6 ±n=j bB ( ° ) j; t h e n t h e fu l̄ ll-
m e n t o f t h e it e m ( B ) wa s c o m p le t e d . A ls o n o t e t h a t t o s a t is fy t h e c o n d it io n ord( d ) ¸ 2 L="
it is s u ± c ie n t t h a t fo r s o m e ° 2 ¡ t h e r e o c c u r r e d

0 < j a r g ° ( d) j < 2 ¼ ¢ "
2 L

=
¼"

L
:

S h o w t h a t s u c h d =2 G1 c a n b e c h o s e n t h a t fo r a ll ° 2 R1 t h e fo llo win g is t r u e :

j a r g ° ( d) j · 1
L

m in

0
@¼";

vuut 6 ±n
j bB ( ° ) j

1
A :

P r oof: A s s u m e ± = "4=1 9 2 : Fir s t p r o ve t h a t t h e r e is a s u b s e t P µ G; s a t is fyin g t h e



1 0 Zero-Free Sets in Abelian Groups

N o t e t h a t if d1; d2 2 G b e lo n g t o d i®e r e n t c o s e t s o f G o n G1; t h e n t h e r e e xis t s a c h a r a c t e r
° 2 R1 s u c h t h a t ° ( d1 ) 6= ° ( d2 ) : Th u s , fo r t h e e xis t e n c e o f d = d1 ¡ d2 =2 G1; wit h t h e
r e s t r ic t io n jarg ( ° ( d) ) j < ´° it is e n o u g h t h a t t h e a m o u n t o f c o s e t s wit h r e s p e c t t o G1
e xc e e d s

Q
°2R1

( 1 + b2 ¼=´°c) ; t h a t is

jG=G1j >
Y

°2R1

0
@1 + L m a x

0
@ 2

"
;

s
2 ¼j bB ( ° ) j

6 ±n

1
A

1
A :

N o t e t h a t t h e fo llo win g in e qu a lit ie s a r e t r u e :

Y

°2R1

0
@ 1 + L m a x

0
@ 2

"
;

s
2 ¼j bB ( ° ) j

6 ±n

1
A

1
A ·

Y

°2R1

0
@1 + 2 L m a x

0
@ 1

"
;

s
j bB ( ° ) j

±n

1
A

1
A ·

· ( 4 L) jR1j
Y

°2R1
m a x

0
@ 1

"
;

s
j bB ( ° ) j

±n

1
A :

B y t h e P a r s e va ls id e n t it y, we h a ve
X

°2¡
j bB ( ° ) j2 = n

X

x2G
jB ( x) j2 = njBj · n2:

H e n c e , fr o m t h e d e ¯ n it io n o f t h e s e t R1 it fo llo ws jR1j · 4 ±¡2: A ls o n o t e t h a t t h e fo llo win g
in e qu a lit y m a x( x; y ) · xy is t r u e fo r x ¸ 1 a n d y ¸ e1=e: Th u s , we o b t a in

( 4 L)
jR1j Y

°2R1
m a x

0
@ 1

"
;

s
j bB ( ° ) j

±n

1
A · ( 4 L) 4±¡2

0
@

Y

°2R1
m a x

0
@ 1

"4
;

Ã
j bB ( ° ) j

±n

!21
A

1
A

1=4

·

· ( 4 L) 4±
¡2 ³

"¡4
´(4±2n2)¡1

P
°2 ¡

j bB(°)j2
· ( 4 L ) 4±

¡2
"¡±

¡2 · ( 4 L=" ) 4±
¡2

<
n

L0
· jG=G1j:

Th u s , t h e e xis t e n c e o f t h e s u b s e t P µ G; s a t is fyin g t h e r e qu ir e m e n t s o f t h e it e m s ( A ) a n d
( B ) , is p r o ve d . A ls o n o t e t h a t s in c e b y c o n s t r u c t io n P is e it h e r a s u b g r o u p o r a p r o g r e s s io n
s ym m e t r ic wit h r e s p e c t t o 0 ; t h e n g ( ° ) = jP j¡1 P

p2P
° ( p ) is a r e a l n u m b e r in t h e in t e r va l

[¡ 1 ; 1 ]:
N o w c o n s t r u c t a s e t A0: Co n s id e r t wo c a s e s :

1 ) If P is a s u b g r o u p , t h e n a s A0 t a ke t h e u n io n o f c o s e t s G o n P; c o n t a in in g a t le a s t "jP j
e le m e n t s o f t h e s e t A: Th e n we h a ve

jA n A0j · "jP j ¢ n
jP j

= "n:

2 ) If P is a p r o g r e s s io n wit h t h e d i®e r e n c e d; t h e n c o n s id e r t h e g r a n u la r s t r u c t u r e o f p r o -
g r e s s io n t yp e wit h t h e d i®e r e n c e d; a n d a s A0 t a ke t h e u n io n o f p r o g r e s s io n s c o n t a in in g
n o t le s s t h a n "L=2 e le m e n t s A: N o t e t h a t n o t m o r e t h a n nL=ord ( d) e le m e n t s o f " r e s id -
u a l" s e t s a r e n o t in c lu d e d in a n y o f t h e g r a in s . Th e n , c o n s id e r in g t h a t ord ( d) ¸ 2 L="
o b t a in

jA n A0j · "L
2

¢ n
L

+
nL

ord( d )
· "n:



V. Sargsyan 1 1

Th e r e qu ir e m e n t s ( i) a n d ( ii) o f t h e le m m a a r e s a t is ¯ e d in b o t h c a s e s .
L e t u s p r o ve t h e p o in t ( iii) . Co n s id e r t h e fu n c t io n a1 ( x) = jP j¡1jA \ ( P + x ) j: B y A( x )

d e n o t e t h e c h a r a c t e r is t ic fu n c t io n o f t h e s u b s e t A o f t h e g r o u p G: N o t e t h a t fo r t h e Fo u r ie r
t r a n s fo r m o f t h e fu n c t io n a1 ( x) t h e fo llo win g c o r r e la t io n is t r u e ba1 ( ° ) = g ( ° ) bA ( ° ) : In d e e d ,
c o n s id e r in g t h a t P = ¡P we h a ve

ba1 ( ° ) =
X

x2G
a1 ( x ) ° ( x ) =

1

jP j
X

x2G
jA \ ( P + x) j° ( x ) = 1jP j

X

a2A

X

p2P
° ( a ¡ p) =

=
1

jP j

Ã
X

a2A
° ( a )

! 0
@

X

p2P
° ( ¡p)

1
A =

1

jP j

Ã
X

a2A
° ( a )

! 0
@

X

p2P
° ( p )

1
A = g ( ° ) bA ( ° ) :

A ls o n o t e t h a t if f : G ! R; a n d bf is a Fo u r ie r t r a n s fo r m o f t h e fu n c t io n f; t h e n t h e
fo llo win g e qu a lit y is t r u e :

X

x1+x2+x3=0

f ( x1 ) ¢ f ( x2 ) ¢ f ( x3 ) =
1

n

X

°2¡

³
bf ( ° )

´3
:

In d e e d , c o n s id e r in g t h a t
X

°2¡
° ( x) =

½
0 ; if x 6= 0
n; if x = 0 ,

we h a ve

X

x1+x2+x3=0

f ( x1 ) ¢ f ( x2 ) ¢ f ( x3 ) =
1

n

X

xi2G;i2[1;3]

X

°2¡

µ
° ( x1 + x2 + x3 ) f ( x1 ) ¢ f ( x2 ) ¢ f ( x3 )

¶
=

=
1

n

X

°2¡

õ X

x12G
° ( x1 ) f ( x1 )

¶
¢
µ X

x22G
° ( x2 ) f ( x2 )

¶
¢
µ X

x32G
° ( x3 ) f ( x3 )

¶
=

1

n

X

°2¡

³
bf ( ° )

´3
:

Co n s id e r t wo c a s e s : x 2 A0 a n d x =2 A0:
L e t x 2 A0: If P is a s u b g r o u p , t h e n x + P c o n t a in s a t le a s t "jP j e le m e n t s o f t h e s e t A;

a n d if P is a p r o g r e s s io n , t h e n x + P c o n t a in s t h e g r a in o f A0; c o m p r is in g x; a n d t h e r e fo r e
j ( x + P ) \ Aj ¸ "jP j=4 : In b o t h c a s e s a1 ( x ) ¸ "=4 = "A0 ( x ) = 4 :

In c a s e if x =2 A0; t h e n a1 ( x ) ¸ 0 = "A0 ( x ) =4 :
Th u s , c o n s id e r in g t h a t j bA( ° ) j · P

x2A
j° ( x) j = jAj · n; a n d A 2 ZF ( G) we h a ve

# f s o lu t io n s o f t h e e qu a t io n ( 1 ) in A0g =

=
X

x1+x2+x3=0

A0 ( x1 ) ¢ A0 ( x2 ) ¢ A0 ( x3 ) ·
4 3

"3
¢

X

x1+x2+x3=0

a1 ( x1 ) ¢ a1 ( x2 ) ¢ a1 ( x3 ) =

=
4 3

"3
¢

X

x1+x2+x3=0

µ
a1 ( x1 ) ¢ a1 ( x2 ) ¢ a1 ( x3 ) ¡ A ( x1 ) ¢ A( x2 ) ¢ A( x3 )

¶
=

=
4 3

"3
¢ 1
n
¢

X

°2¡

³
( ba1 ( ° ) )

3 ¡ ( bA( ° ) ) 3
´

=
4 3

n"3
¢

X

°2¡
( bA( ° ) ) 3

³
( g ( ° ) )

3 ¡ 1
´
·

· 4
3

n"3
¢

X

°2¡
j bA( ° ) j3j1 ¡ ( g ( ° ) ) 3j · 4

3

n"3
¢ 3 ¢ m a x

°2¡
j bA( ° ) jj 1 ¡ g ( ° ) j ¢

X

°2¡
j bA( ° ) j2 ·



1 2 Zero-Free Sets in Abelian Groups

· 1 9 2
n"3

¢ ±n ¢ njAj · 1 9 2
"3

¢ ± ¢ n2 = "n2:

L e m m a 3 is p r o ve d .
Th e e xis t e n c e o f a fa m ily o f g r a in s is p r o ve d in t h e fo llo win g t h e o r e m .

T heor em 7: L et G be an Abelian group of the order n; and n be su± ciently large. Then
there exists the family F of subsets of the group G; satisfying the following conditions:

( i) lo g jFj ·
p

2 n( lo g n) ¡1=18,

( ii) for each A 2 ZF ( G) there exists F 2 F such that A µ F ,

( iii) every F 2 F contains not more than n2 ( lo g n) ¡1=9 solutions of the equation (1).

la r g e n s u c h a c h o ic e o f p a r a m e t e r s s a t is ¯ e s t h e c o n d it io n o f L e m m a 3 . Th u s , fo r e ve r y s e t
A 2 ZF ( G) ; a p p lyin g L e m m a 3 , c o n s t r u c t t h e s e t A0: A s s u m e t h a t F = fA [ A0 j A 2
ZF ( G ) g: Th e it e m ( ii) is e xe c u t e d b y c o n s t r u c t io n .

H e n c e a n d fr o m t h e it e m ( ii) o f L e m m a 3 it fo llo ws t h a t t h e c a r d in a lit y o f t h e fa m ily
F d o e s n o t e xc e e d t h e n u m b e r o f s e t s t h a t a r e t h e u n io n o f L-g r a n u la r wit h s o m e s u b s e t
o f t h e g r o u p G; o f s iz e a t m o s t "n: Th u s , fr o m L e m m a s 1 a n d 2 it im p lie s t h a t lo g jFj
· 3 n=L + n

p
"; wh ic h fo r s u ± c ie n t ly la r g e n d o e s n o t e xc e e d 2 n

p
":

A ls o n o t e t h a t wh ile a d d in g a n e le m e n t t o t h e s e t , t h e r e c a n b e fo r m e d n o t m o r e t h a n
3 n n e w s o lu t io n s o f t h e e qu a t io n ( 1 ) . Fr o m t h is it fo llo ws t h a t in e a c h s e t F 2 F t h e r e e xis t
n o t m o r e t h a n "n2 + 3 "n2 = n2 ( lo g n) ¡1=9 s o lu t io n s o f t h e e qu a t io n ( 1 ) .

Th e o r e m 7 is p r o ve d .

L e t G b e a n A b e lia n g r o u p o f t h e o r d e r n: B y Th e o r e m 7 t h e r e e xis t s a fa m ily F o f s u b s e t s
( g r a in s ) o f t h e g r o u p G; s a t is fyin g t h e c o n d it io n s ( i) -( iii) . L e t F 2 F: Fixin g F a n d a p p lyin g
Th e o r e m 6 a t A1 = A2 = A3 = F we o b t a in t h a t t h e r e e xis t s F

0 µ F s u c h t h a t jF nF 0j = ¹o ( n)
F 0 2 ZF ( G) : H e n c e , it fo llo ws t h a t jF j · ¹ ( G) + ¹o( n) ; wh e r e ¹( G ) is t h e m a xim u m s iz e o f
t h e s e t fr o m ZF ( G ) : Th e fa c t t h a t lo g jFj = ¹o( n) ( it e m ( i) o f Th e o r e m 7 ) we ¯ n d t h a t t h e
n u m b e r o f s u b s e t s o f a ll t h e s e t s o f t h e fa m ily F; d o e s n o t e xc e e d 2 ¹(G)+¹o(n):

B y vir t u e o f it e m ( ii) o f Th e o r e m 7 a ll t h e s e t s fr o m ZF ( G) a r e s u b s e t s o f s o m e s e t o f
t h e fa m ily F: H e n c e it fo llo ws t h a t

lo g jZF ( G) j = ¹( G) + ¹o ( n) :

Th e o r e m 4 is p r o ve d .

3 . Th e U p p e r a n d L o we r E s t im a t e s fo r t h e Ma xim u m S iz e o f a Ze r o -fr e e s e t
in a n A b e lia n Gr o u p

In t h is s e c t io n we ¯ n d t h e u p p e r a n d lo we r e s t im a t e s o f t h e va lu e ¹ ( G) : Fo r t h is t h e fo llo win g
a u xilia r y r e s u lt s a r e n e e d e d .

P r oof: A s s u m e t h a t L = L0 = blo g nc a n d " = ( lo g n) ¡1=9= 4 : N o t e t h a t fo r s u ± c ie n t ly

2 .3 P r o o f o f Th e o r e m 4

3 .1 D e ¯ n it io n s a n d A u xilia r y S t a t e m e n t s



V. Sargsyan 1 3

L e t G b e a n A b e lia n g r o u p a n d A; B b e n o n -e m p t y s u b s e t s o f t h e g r o u p G: A s s u m e t h a t
A + B = fa + b j a 2 A; b 2 Bg; 2 A = A + A; a n d ¡A = f¡a j a 2 Ag: L e t A 2 ZF ( G) :
Th e s u b s e t A is c a lle d maximal, if it is m a xim a l b y in c lu s io n , i.e ., fo r e ve r y x 2 G n A t h e
s e t ( A [ fxg ) =2 ZF ( G) :
De¯nition 1: L et A be a non-empty subset of an Abelian group G: The subgroup H ( A ) =
fg 2 G j g + A = Ag is called a stabilizer of the set A:
T heor em 8: ( K n e s e r , [1 3 ]) L et A; B be non-empty subsets of an Abelian group G; and H
be a stabilizer of the set A + B: Then

jA + Bj ¸ jA + Hj + jB + Hj ¡ jHj:
Lemma 4: L et G be an Abelian group, A 2 ZF ( G) ; and H be a stabilizer of the set 2 A:
Then ( A + H ) 2 ZF ( G ) :

a1 + a2 + a3 + ( h1 + h2 + h3 ) = a1 + a2 + a3 + h4 = a1 + ( a2 + a3 + h4 ) = a1 + a4 + a5;
wh e r e a4; a5 2 A; a n d h4 2 H: Th e la t t e r c o n t r a d ic t s t h e fa c t t h a t A 2 ZF ( G ) ; i.e ., t h e s e t
( A + H ) 2 ZF ( G ) :

L e m m a 4 is p r o ve d .

Lemma 5: L et G be an Abelian group and the subset A of the group G be a maximal ZF S,
and H be a stabilizer of the set 2 A: Then the set A is a union of cosets of the subgroup H:

L e m m a 5 is p r o ve d .

Lemma 6: L et G be an Abelian group. Then the following statements are equivalent:

( i) the exponent of the group G is divided into d;

( ii) there exists a subgroup H of the group G such that the quotient group G=H is isomor-
phic to the cyclic group Zd:

Lemma 7: L et G be an Abelian group of the order n; and d is a divisor of the exponent
group G: Then the following inequality holds:

¹( G) ¸ ¹( Zd ) ¢
n

d
:

It is e a s y t o s e e t h a t t h e s e t á1 ( K ) 2 ZF ( G ) ; a n d já1 ( K ) j = jKj ¢ n
d
: A s s u m e t h a t

K = fa1 + H; a2 + H; : : : ; ak + Hg; wh e r e a1; : : : ; ak =2 H ( H =2 K ) ; a n d k = jKj: L e t
á1 ( K ) =2 ZF ( G ) : W it h o u t lo s s o f g e n e r a lit y a s s u m e t h a t fo r s o m e h1; h2; h3 2 H t h e
fo llo win g e qu a lit y h o ld s : a1 + h1 + a2 + h2 + a3 + h3 = 0 : Fr o m t h is e qu a lit y it fo llo ws
t h a t a1 + a2 + a3 2 H; i.e ., fo r e le m e n t s ( a1 + H ) ; ( a2 + H ) ; ( a3 + H ) 2 K t h e fo llo win g
c o r r e la t io n h o ld s : ( a1 + H ) + ( a2 + H ) + ( a3 + H ) = H: Th e la t t e r c o n t r a d ic t s t h e fa c t t h a t
K 2 ZF ( G=H ) ; i.e ., t h e s e t á1 ( K ) 2 ZF ( G ) :

L e m m a 7 is p r o ve d .

P r oof: A s s u m e t h e c o n t r a r y, a n d le t a1 +h1 +a2 +h2 +a3 +h3 = 0 fo r s o m e a1; a2; a3 2 A;
a n d h1; h2; h3 2 H: S in c e 2 A + H = 2 A; t h e n o b t a in 0 = a1 + h1 + a2 + h2 + a3 + h3 =

P r oof: S in c e t h e s u b s e t A o f t h e g r o u p G is a m a xim a l ZFS , t h e n b y L e m m a 4 : we h a ve
A = A + H; t h a t is t h e s u b s e t A is a u n io n o f c o s e t s o f t h e s u b s e t H:

P r oof: S in c e d is a n e xp o n e n t d ivis o r o f t h e g r o u p G; t h e n b y L e m m a 6 : t h e r e e xis t s
a s u b g r o u p H o f t h e g r o u p G s u c h t h a t t h e qu o t ie n t g r o u p G=H is is o m o r p h ic t o t h e

c yc lic g r o u p Zd: L e t Ã: G ! G=H b e a c a n o n ic a l h o m o m o r p h is m , a n d K 2 ZF ( G=H ) :



1 4 Zero-Free Sets in Abelian Groups

Fir s t p r o ve t h e u p p e r e s t im a t e s . L e t A µ G b e a m a xim a l ZFS . S in c e 2 A\ ( ¡A) = ; ( fo llo ws
fr o m t h e fa c t t h a t A 2 ZF ( G) ) , t h e n we o b t a in

j 2 Aj + jAj · n: ( 2 )

Fr o m Th e o r e m 8 , L e m m a 5 a n d t h e in e qu a lit y ( 2 ) it fo llo ws t h a t

3 jAj ¡ jHj · n; ( 3 )

wh e r e H is t h e s t a b iliz e r o f t h e s e t 2 A:
Fr o m t h e la s t in e qu a lit y a n d t h e fa c t t h a t jAj is d ivid e d in t o jHj ( fo llo ws fr o m L e m m a

5 ) we ¯ n d t h a t

jAj · jHj ¢
j 1
3

³ n
jHj + 1

´k
: ( 4 )

Th u s , we h a ve

¹( G ) · m a x
djn

µ¹
d + 1

3

º
¢ n
d

¶
: ( 5 )

It is e a s y t o s e e t h a t t h e la s t in e qu a lit y is e qu iva le n t t o

¹( G ) ·

8
><
>:

n
3
( 1 + 1

p
) ; t h e le a s t p r im e d ivis o r n o f t h e fo r m p ´ 2 ( m o d 3 ) ;

n
3
; n o p r im e d ivis o r n o f t h e fo r m p ´ 2 ( m o d 3 ) ; b u t 3 jn;

1
3
( n ¡ 1 ) ; a ll p r im e d ivis o r s n h a ve t h e fo r m p ´ 1 ( m o d 3 ) :

Th e u p p e r e s t im a t e s a r e p r o ve d . N o w p r o ve t h e lo we r e s t im a t e s .
( i) L e t p b e t h e le a s t p r im e d ivis o r n; o f t h e fo r m p ´ 2 ( m o d 3 ) : Th e n t h e r e e xis t a

s u b g r o u p H o f t h e o r d e r n=p; a n d t h e e le m e n t g o f t h e o r d e r p s u c h t h a t

G = H [ ( H + g ) [ : : : [ ( H + ( p ¡ 1 ) g ) :

D e ¯ n e t h e s e t A b y t h e e qu a t io n

A = ( H + g ) [ ( H + 4 g ) [ ( H + 7 g ) [ : : : [ ( H + ( p ¡ 1 ) g ) : ( 6 )

It is e a s y t o s e e t h a t t h e s e t A is a ZFS in t h e g r o u p G; a n d jAj = p+1
3

¢ n
p
: B y d e ¯ n it io n

ZFS A 2 ZF ( G) if 0 =2 A + A + A; wh ic h is e qu iva le n t t o 2 A \ ( ¡A) = ;: Co n s id e r in g t h a t
A = ¡A it is s u ± c ie n t t o s h o w t h a t 2 A \ A = ;: In d e e d , fr o m ( 6 ) we h a ve 2 A µ Si ( ig + H ) ;
wh e r e i 6= 1 ( m o d 3 ) ; b u t s in c e A = Sj ( jg + H ) ; wh e r e j ´ 1 ( m o d 3 ) ; t h e n it fo llo ws
t h a t 2 A \ A = ;:

( ii) N o t e t h a t fo r a n y in t e g e r m > 1 t h e in t e r va l [1 ; m ¡ 1 ] is a ZFS in t h e c yc lic g r o u p
Z3m: H e n c e a n d fr o m L e m m a 7 t h e lo we r e s t im a t e fo llo ws .

( iii) L e t t h e e xp o n e n t o f t h e A b e lia n g r o u p G b e e qu a l t o 3 : S in c e fo r a n y g 2 G t h e
fo llo win g e qu a lit y h o ld s g + g + g = 0 ; t h e n in t h e g r o u p G t h e ZFS a r e m is s in g . Th e r e fo r e ,
o n e c a n a s s u m e t h a t ¹( G ) = 0 :

( iv) L e t º b e a n e xp o n e n t o f t h e A b e lia n g r o u p G o f t h e o r d e r n: Th e n t h e r e e xis t s a
s u b g r o u p H o f t h e o r d e r n=º; a n d a n e le m e n t g o f t h e o r d e r º s u c h t h a t

G = H [ ( H + g ) [ : : : [ ( H + ( º ¡ 1 ) g ) :

3 .2 P r o o f o f Th e o r e m 5



V. Sargsyan 1 5

D e ¯ n e t h e s e t A b y t h e e qu a t io n

A = ( H + 2 g ) [ ( H + 5 g ) [ ( H + 8 g ) [ : : : [ ( H + ( º ¡ 2 ) g ) : ( 7 )

It is e a s y t o s e e t h a t t h e s e t A is a ZFS in t h e g r o u p G; a n d jAj = º¡1
3

¢ n
º
: Co n s id e r in g

t h a t A = ¡A it is s u ± c ie n t t o p r o ve t h a t 2 A \ A = ;: Fr o m ( 7 ) we h a ve 2 A µ Si ( ig + H ) ;
wh e r e i 6= 2 ( m o d 3 ) : A n d s in c e A = Sj ( jg + H ) ; wh e r e j ´ 2 ( m o d 3 ) ; t h e n we ¯ n d
t h a t 2 A \ A = ;:

Th e o r e m 5 is p r o ve d .

Refer ences

[1 ] P .J. Ca m e r o n a n d P . E r d Äo s , \ On t h e n u m b e r o f s e t s o f in t e g e r s wit h va r io u s p r o p e r t ie s " ,
J ournal of Number Theory (B na®,AB ,1988), B e r lin , d e Gr u yt e r , p p . 6 1 -7 9 , 1 9 9 0 .

[2 ] N .J. Ca lkin , \ On t h e n u m b e r o f s u m -fr e e s e t " , B ull. L ondon M athematical Society, vo l.
2 2 , p p . 1 4 0 -1 4 4 , 1 9 9 0 .

[3 ] N . A lo n , \ In d e p e n d e n t s e t s in r e g u la r g r a p h s a n d s u m -fr e e s u b s e t s o f A b e lia n g r o u p s " ,
Israel J ournal of M athematics, vo l. 7 3 , p p . 2 4 7 -2 5 6 , 1 9 9 1 .

[4 ] A .A . S a p o z h e n ko , \ Th e Ca m e r o n -E r d Äo s c o n je c t u r e " , D okl. Akad. Nauk, vo l. 3 9 3 , n o . 6 ,
7 4 9 -7 5 2 , 2 0 0 3 .

[5 ] B . Gr e e n , \ Th e Ca m e r o n -E r d Äo s c o n je c t u r e " , B ull. L ondon M athematical Society, vo l.
3 6 , n o . 6 , p p . 7 6 9 -7 7 8 , 2 0 0 4 .

[6 ] A .A . S a p o z h e n ko , \ On t h e n u m b e r o f s u m -fr e e s e t s in A b e lia n g r o u p s " , Vestnik
M oskovskogo Universiteta. M atematika i M exanika, vo l. 4 , p p . 1 4 -1 7 , 2 0 0 2 .

[7 ] V .F. L e v, T. L u c z a k a n d T. S c h o e n , \ S u m -fr e e s e t s in A b e lia n g r o u p s " , Israel J ournal
of M athematics, vo l. 1 2 5 , p p . 3 4 7 -3 6 7 , 2 0 0 1 .

[8 ] V .F. L e v a n d T. S c h o e n , \ Ca m e r o n -E r d Äo s m o d u lo a p r im e " , F inite F ields and their
Applications, vo l. 8 , n o . 1 , p p . 1 0 8 -1 1 9 , 2 0 0 2 .

[9 ] B . Gr e e n a n d I. R u z s a , \ S u m -fr e e s e t s in A b e lia n g r o u p s " , Israel J ournal of M athemat-
ics, vo l. 1 4 7 , p p . 1 5 7 -1 8 8 , 2 0 0 5 .

[1 0 ] A .A . S a p o z h e n ko , \ S o lu t io n o f t h e Ca m e r o n -E r d Äo s p r o b le m fo r g r o u p s o f p r im e o r d e r " ,
Computational M athematics and M athematical P hysics, vo l. 4 9 , n o . 8 , p p . 1 4 3 5 -1 4 4 1 ,
2 0 0 9 .

[1 1 ] P .H . D ia n a n d a a n d H .P . Y a p , \ Ma xim a l s u m -fr e e s e t s o f e le m e n t s o f ¯ n it e g r o u p s " ,
P roc. J apan Acad., vo l. 4 5 , n o . 1 , p p . 1 -5 , 1 9 6 9 .

[1 2 ] B . Gr e e n , \ A S z e m e r ¶ e d i-t yp e r e g u la r it y le m m a in A b e lia n g r o u p s " , J ournal Geometric
and F unctional Analysis (GAF A), vo l. 1 5 , n o . 2 , p p . 3 4 0 -3 7 6 , 2 0 0 5 .

[1 3 ] M.B N a t h a n s o n , \ A d d it ive n u m b e r t h e o r y: In ve r s e p r o b le m s a n d t h e g e o m e t r y o f s u m -
s e t s " , Graduate Texts in M athematics, B e r lin , H e id e lb e r g , N e w Y o r k S p r in g e r -V e r la g .,
p . 3 1 2 , 1 9 9 6 .

Submitted 27.03.2014, accepted 01.08.2014.



1 6 Zero-Free Sets in Abelian Groups

¼ñáÛÇó ³½³ï µ³½ÙáõÃÛáõÝÝ»ñÝ ²µ»ÉÛ³Ý ËÙµ»ñáõÙ

ì. ê³ñ·ëÛ³Ý

²Ù÷á÷áõÙ

G ËÙµÇ A »Ýóµ³½ÙáõÃÛáõÝÁ ÏáãíáõÙ ¿ ½ñáÛÇó ³½³ï, »Ã» x+y = z = 0 ѳí³ë³ñáõÙÁ
ãáõÝÇ ÉáõÍáõÙ A µ³½ÙáõÃÛ³Ý Ù»ç:

²ß˳ï³ÝùáõÙ ëï³óí»É »Ý ²µ»ÉÛ³Ý ËÙµÇ ½ñáÛÇó ³½³ï µ³½ÙáõÃÛ³Ý ³é³í»É³·áõÛÝ
ѽáñáõÃÛ³Ý í»ñÇÝ ¨ ëïáñÇÝ ·Ý³Ñ³ï³Ï³ÝÝ»ñÁ, ÇÝãå»ë ݳ¨ ²µ»ÉÛ³Ý ËÙµÇ ½ñáÛÇó
³½³ï µ³½ÙáõÃÛáõÝÝ»ñÇ ù³Ý³ÏÇ Éá·³ñÇÃÙ³Ï³Ý ³ëÇÙåïáïÇÏ ·Ý³Ñ³ï³Ï³ÝÁ:

Ìíîæåñòâà, ñâîáîäíûå îò íóëÿ, â àáåëåâûõ ãðóïïàõ
Â. Ñàðãñÿí

Àííîòàöèÿ

Ïîäìíîæåñòâî A ýëåìåíòîâ ãðóïïû G íàçûâàåòñÿ ñâîáîäíûì îò íóëÿ, åñëè
óðàâíåíèå x + y + z = 0 íå èìååò ðåøåíèé â ìíîæåñòâå A.  ðàáîòå ïîëó÷åíû
âåðõíèå è íèæíèå îöåíêè ìàêñèìàëüíîé ìîùíîñòè ìíîæåñòâà, ñâîáîäíîãî îò
íóëÿ, â àáåëåâîé ãðóïïå, è óñòàíîâëåíà àñèìïòîòèêà ëîãàðèôìà ÷èñëà ìíîæåñòâ,
ñâîáîäíûõ îò íóëÿ, â àáåëåâîé ãðóïïå.