（应用数学专业论文）组合数学中的代数方法.pdf

a lg e b ra ic t e c h n iq u e s in c o m b in ato ric != 一一 一一 一 一- 一一 一卫 in g -h u h o u ab s t r a c t 厂 a l g e b r a p l a y s a n i m p o rt a n t r o l e i n c o m b i n a t o r i c s . i n e n u m e r a t i v e c o m b i n a t o r ic s n e e d t h e t h e o r y o f g r o u p 1 9 , 2 9 1 , t h e t h e o r y o f r i n g 7 , 2 7 , t h e t h e o r y o f a l g e b r a 3 0 w e a n d s o o n . i n g r a p h t h e o r y , w e h a v e t h e a l g e b r a i c g r a p h t h e o r y 8 w h i c h i n v o l v i n g s p e c t r u m, c n rom a t l c p o l y n o m l a l a n d s o o n . i n d e s i g n t h e o ry a n d c o d i n g t h e o r y , w e n e e d fi n i t e g e o m e -p o l y n o m i a l t r y a n d h a d a m a r d m a t r i c e s 1 9 , 2 0 , 2 4 . t h e r e a r e m u c h m o r e e x a m p l e s i n v a r i o u s b r a n c h e s c n roma n cp o 1 y n o ml a l a n d s o o n . o f c o m b i n a t o r i c s . i n t h i s t h e s i s , w e d i s c u s s t w o c o m b i n a t o r i a l p r o b l e m s b y a l g e b r a i c t e c h - n t q u e s . i n p a rt i , w e c o n s i d e r t h e p r o b l e m s a b o u t r e s t r i c t e d s u m s o f c o n g r u e n c e c la s s e s t h e o r ig i n a l p r o b l e m w a s p r o p o s e d b y e r d b s a n d h e i l b r o n n ( c f . 1 4 a n d 1 8 ) i n 1 9 6 4 t h e y c o n j e c t u r e d t h a t f o r e a c h r e s i d u e c l as s e s m o d p t h a t c a n h a d b e e n o p e n f o r t h i rt y y e a r s n o n e m p ty s u b s e t a o f z y t h e r e a r e a t le a s t m i n p , 2 1a 一 3 b e w r i t t e n a s t h e s u m 。 t w o d i s t i n c t e le me n t s o f a . t h i s u n t i l d i a s d a s i l v a a n d h a m i d o u n e 1 2 1 p r o v e d t h e r e s u l t 月 匕 f o r n - f o l d s u m s i n 1 9 9 4 , w i t h t h e h e l p o f t h e r e p r e s e n t a t i o n t h e o r y o f s y m m e t r i c g r o u p s . i n 1 9 9 5 a n d 1 9 9 6 , n . a l o n , n a t h a n s o n a n d i . z . r u z s a 5 , 6 1 i n v e n t e d a p o l y n o m i a l m e t h o d t o a t t a c k s i m i l a r p ro b le m s . b y t h i s m e t h o d , t h e e s t i m a t i n g o f t h e l o w e r b o u n d o f t h e n u m b e r o f r e s t r i c t e d s u m s b e c o m e s t h e c a l c u l a t i n g o f o n e c o e f fi c i e n t o f a s p e c i a l p o l y n o m i a l . t h e k e y s o f t h e m e t h o d a r e t h e p r o p e r c h o o s i n g o f t h e p o l y n o m i a l a n d t h e c a lc u l a t i n g o f t h e s p e c i a l c o e f fi c i e n t . t h e p o l y n o m i a l c h o s e n i n 6 1 c a n o n l y d e a l w i t h t h e c a s e t h a t a l l t h e c a r d i n a l i t i e s o f t h e s e t s a r e d i s t i n c t . h e n c e , t h e y c o u ld n o t d e a l w i t h t h e n - f o ld s u m s c a s e d i r e c t l y . n o t i n g t h e a b o v e d r a w b a c k , w e g e n e r a l i z e t h e p o l y n o m i a l m e t h o d a n d c h o s e a n e w p o l y n o m i a l . s i n c e t h e c o e f fi c i e n t o f t h e n e w p o l y n o m i a l i s t o o c o m p l i c a t e t o c a l c u l a t e d i r e c t l y , w e i n t r o d u c e a l i n e a r o p e r a t o r a n d s t u d y t h e a l g e b r a i c p r o p e r t ie s o f i t . b a s e d o n t h o s e p r o p e r t i e s a n d d y s o n s c o n j e c t u re汇 1 3 了 ， w e g e t t h e c o e f fi c i e n t , a n d h e n c e , t h e l o w e r b o u n d o f t h e n u mb e r o f r e s t r i c t e d s u ms . t h e n e w e s t i ma t i o n c o v e r s t h e r e s u l t o f di a s d a s i l v a a n d h a m i d o u n e . mo re i m p o r t a n t , i t g i v e s t h e b e s t l o w e r b o u n d o f t h e n u m b e r o f s u m s w i t h m o re t h a n o n e r e s t r i c t i o n s . t h e r e a r e a l s o s o m e i n t e re s t i n g r e s u l t s o b t a i n e d a s c o rol l a r i e s i n p a rt i i , w e c o n s i d e r t h e r e c u r r e n c e f o r m u l a o f d o u b l e h y p e r g e o tn e i r i c t e r m s . h y p e r g e o m e t r i c t e r m s h a v e w i d e a p p l i c a t i o n s i n m a t h e m a t ic s a n d p h y s i c s 1 5 , 1 6 , 3 2 t h e re a re m a n y f a m o u s id e n t i t i e s i n v o l v i n g t h o s e f u n c t i o n s , s u c h as g a u s s s i d e n t it y 2 a n d d i x o n s i d e n t i t y 3 6 . t h e r e a re a l s o m a n y b e a u t i f u l p r o o f s f o r t h e m . wh i l e , i t i s m o r e a m a z i n g t h a t a l o t o f t h e m c a n b e p ro v e d a u t o m a t i c a l l y . s i n c e 1 9 9 0 , z e i l b e r g e r a n d wi l f d e v e l o p e d a s e r ie s o f e l e g a n t m e t h o d s t o p r o v e a u t o m a t i c a l l y t h e i d e n t i t i e s i n v o l v i n g ( q - ) h y p e r g e o m e t r i c t e r m s 3 7 - 4 0 , 4 2 . t h e b a s i c id e a i s t o fi n d t h e r e c u r r e n c e f o r m u l a o f t h e f u n c t i o n o n e a c h s i d e o f t h e i d e n t i t y a n d t o p r o v e t h a t t h e y a r e e q u i v a le n t . t h u s , t h e i d e n t i t y i s p r o v e d b y c h e c k i n g t h e i n i t i a l v a l u e s . c l e a r l y , a b a s i c h y p o t h e s i s o f t h i s m e t h o d i s t h a t th e f u n c t i o n s s h o u l d b e d e t e r mi n e d b y fi n i t e i n i t i a l v a l u e s , w h i c h a r e c a l le d a l g e b r a i c t e c h n i q u e s i n c o m b i n a t o r ic s q i n g - h u il o u h o l o n o m i c f u n c t i o n s . t h e a c c u r a t e d e fi n i t io n i s g i v e n b y t h e l a n g u a g e o f r i n g s 1 9 , 4 2 1 i s v e r y a b s t r a c t a n d i s h a r d t o v e r i f y . wh i l e , z e i l b e r g e r a n d wi l f 3 9 1 s h o w e d t h a t h y p e r g e o m e tr i c t e r ms a r e h o l o n o m i c a n d c o n j e c t u r e d t h a t t h e i n v e r s e 、 wh i c h p r o p e l a s s e r t t o n a l s o h o l d s b y g e n e r a l i z i n g t h e f u n c t i o n s a n d h e n c e t h e g o s p e r s a l g o r i t h m , 认 已 i n t r o d u c e t h e r e p r e s e n t a t i o n o f r a t i o n a l s t a n d a r d r e p r e s e n t a t i o n o f d o u b le h y p e r g e o m e t r i c t e r m s t h e t w o b a s i c r e c u r r e n c e f o r m u l a e t h a t d o u b l e h y p e r g e o m e t r i c t e r m s s a t i s f y u s i n g e r a l f o r m o f s u c h r e p re s e n t a t i o n . b a s e d o n i t , w e d e r i v e t h a t t h e r e e x i s t s w e g e t t h e g e n a k - f r e e r e c u r r e n c e f o r m u l a f o r a d o u b l e h y p e r g e o m e t r i c t e rm i f a n d o n l y i f i t i s p r o p e r . c o n s e q u e n t l y , h o l o - n o m i c d o u b l e 吻p e r g e o m e tr i c t e r m s a r e a l l p r o p e r , w h i c h m o d i fi e s t h e i d e n t i t i e s t h a t c a n b e p r o v e d a u t o m a t i c a l l y . k e y w o r d s : re s t r i c t e d s u m s , p o l y n o m i a l m e t h o d , d y s o n s c o n j u n c t u r e , d o u b l e h y p e r g e o - m e t r i c t e r m , k - f r e e r e c u r r e n c e f o r m u l a , h o l o n o m i c f u n c t i o n , p r o p e r h y p e r g e o m e t r i c t e r m v 一一， ，. .， r .，韶卫 习怡了 a lg e b r a ic t e c h n iq u e s i n c o m b i n a t o r i c s q i n g - h u h o u pr e f a c e c o m b i n a t o r i c s i s a n o l d b r a n c h o f m a t h e m a t i c s . ma g i c s q u a r e s h a v e b e e n a r o u n d f o r o v e r 3 , 0 0 0 y e a r s . t h e y a r e d e s c e n d a n t s o f t h e o l d e s t k n o w n n u m b e r m y s t e ry , t h e l e g e n d o f l o s h u , f o u n d i n c h i n a i n a b o o k e n t i t l e d y i h k i n g . d u r i n g a v e r y l o n g t i m e , t h e r e w e r e n o o t h e r t o o l s t o d e a l w i t h c o m b i n a t o r i a l p r o b l e m s e x c e p t f o r h u m a n i n t e l l i g e n c e . i t i s n o t u n t i l r e c e n t c e n t u r i e s t h a t m a n y u s e f u l t o o l s w e r e i n t r o d u c e d i n c o m b i n a t o r i c s , s u c h a s a l g e b r a , a n a l y s i s , p r o b a b i l i t y a n d s o o n . a s o n e o f t h e m , a l g e b r a i s a p o w e r f u l t o o l t o a t t a c k m a n y p r o b l e ms i n c o mb i n a t o r i c s . a l g e b r a p l a y s a n i m p o r t a n t r o l e i n e n u m e r a t i v e c o m b i n a t o r ic s 3 3 , 3 4 ) . a s a n e x a m p l e , a l m o s t a l l e n u m e r a t i v e p r o b l e m s o f g r a p h s a r e s o l v e d b y a l g e b r a i c t e c h n i q u e s 2 3 . w e n e e d t h e g e n e r a t i n g f u n c t i o n s t o c o u n t t h e n u m b e r o f l a b e l l e d g r a p h s . a n d w e n e e d p 6 1 y a s t h e o r e m a n d c y c l e i n d e x s u m s t o d e a l w i t h u n l a b e l l e d g r a p h s . wi t h o u t t h o s e a l g e b r a i c t o o l s , o n e e v e n h a s n o w a y t o c o u n t t h e n u m b e r o f g r a p h s w i t h g i v e n n u m b e r o f v e r t ic e s . a l g e b r a p l a y s a n i m p o r t a n t r o l e i n g r a p h t h e o r y 8 . wi t h o u t t h e a i d o f a l g e b r a , w e c o u l d n o t d i s c o v e r t h e b e a u t i f u l f o r m u l a o n t h e n u m b e r o f s p a n n i n g t r e e s 8 , p p . 3 9 ) : k ( r ) = n - 2 d e t ( j + q ) , w h e r e k ( r ) d e n o t e s t h e n u m b e r o f s p a n n i n g t r e e s o f t h e g r a p h i - w i t h n v e r t ic e s , j ， 、 t h e m a t r i x e a c h o f w h o s e e n t r i e s i s l a n d q i s t h e l a p l a c i a n ma t r i x . a l g e b r a a l s o p l a y s a n i m p o r t a n t r o l e i n c o n s t r u c t i v e c o m b i n a t o r i c s . f o r e x a m p l e , a l o t o f c o m b i n a t o r i a l d e s i g n s a re o b t a i n e d b y fi n i t e fi e l d a n d fi n i t e g r o u p . i n f a c t , y o u m a y fi n d a l g e b r a i c t e c h n i q u e s i n a l m o s t a l l b r a n c h e s o f c o m b i n a t o r i c s f u r t h e r m o r e , t h e r e a r e m o r e e x a m p l e s i n w h i c h w e s o l v e t h e p r o b l e m s i n o t h e r b r a n c h e s o f m a t h e m a t i c s b y叩p l y i n g a l g e b r a i c t e c h n i q u e s i n c o m b i n a t o r i c s . f o r i n s t a n t , w h e n w e c o n s i d e r t h e p r o p e rt i e s o f c e l l u l a r a u t o m a t a , t h e i n t r o d u c i n g o f c o m b i n a t o r i c s a n d m a t r ic e s m a k e s t h e d i s c u s s i o n m o re e x p l i c i t 2 1 , 2 2 i n t h i s t h e s i s , w e a r e c o n c e r n e d w i t h t w o a s p e c t s o f a l g e b r a i c t e c h n i q u e s i n c o m b i n a - t o r i c s . o n e i s t h e r e s t r i c t e d s u m s o f c o n g r u e n c e c l a s s e s a n d t h e o t h e r i s t h e a u t o m a t ic p r o o f o f c o m b i n a t o r i a l i d e n t i t i e s . i n t h e fi r s t p r o b l e m , b y t h e p o l y n o m i a l m e t h o d , t h e e s t i m at t - i n g o f t h e n u m b e r o f d i f f e r e n t s u m s i s c o n v e r s e d t o c a lc u l a t i n g t h e c o e f fi c i e n t s o f a s p e c i a l p o l y n o m i a l . c o m b i n g t h e a l g e b r a i c t e c h n iq u e s a n d c o m b i n a t o r i a l e n u m e r a t i o n , w e s o l v e t h e p r o b l e m . i n t h e l a t t e r o n e , t h e p r o v i n g o f c o m b i n a t o r i a l i d e n t i t i e s i s tr a n s f o r m e d t o fi n d i n g t h e re c u r r e n c e f o r m u l a e . b a s e d o n t h e a l g e b r a i c r e p r e s e n t a t i o n o f t h e t e r m s , t h e n e c e s s a r y a n d s u f fi c i e n t c o n d i t i o n f o r t h e e x i s t e n c e o f s u c h f o r m u l a e i s d e r i v e d a l g e b r a ic t e c h n i q u e s i n c o m b i n a t o r i c s q i n g - h u h o u p a r t i r e s t r i c t e d s u m s o f c o n g r u e n c e c l a s s e s 2 . 1 . i n t r o d u c t i o n a n d no t a t i o n s a d d i t i v e n u m b e r t h e o r y i s a n i m p o rt a n t b r a n c h o f n u m b e r t h e o r y . t h e r e a re m a n y c l a s s i c a n d i n t e r e s t i n g p r o b l e m s i n t h i s fi e l d , s u c h a s w a r i n g p ro b l e m a n d g o l d b a c h p ro b l e m 2 5 a l s o , t h e r e a r e m a n y c o m b i n a t o r i a l p ro b l e m s i n i t . o n e o f t h e m i s t h e p r o b l e m o n r e s t r i c t e d s u m s o f c o n g r u e n c e c l a s s e s . t h a t i s , g i v e n c e r t a i n r e s t r i c t i o n r a n d s u b s e t s a i , a 2 , . . . , a . o f t h e fi n it e fi e l d z p , w h a t c a n w e s a y a b o u t th e s e t a 1 + a 2 + - + a: a i e a ; , a i s a t is f y t h e r e s t r i c t io n r ) ? i n 1 9 6 4 e r d b s a n d h e i l b r o n n ( c f . 1 4 a n d 1 8 1 ) c o n j e c t u r e d t h a t f o r e a c h n o n e m p t y s u b s e t a o f 吞t h e r e a r e a t l e a s t m in 扣, 2 协 卜3 ) re s i d u e c l a s s e s m o d p t h a t c a n b e w r it t e n a s t h e s u m o f t w o d i s t i n c t e l e m e n t s o f a . t h i s h a d b e e n o p e n f o r t h i r t y y e a r s u n t i l d i a s d a s i l v a a n d h a m i d o u n e ( l 2 ) p r o v e d t h e f o l l o w i n g r e s u l t f o r n - f o l d s u m s i n 1 9 9 4 , w i t h t h e h e l p o f t h e r e p r e s e n t a t i o n t h e o ry o f s y m m e t r i c g r o u p s . t h e o re m a . l e t p b e a p r im e a n d n a p o s i t i v e i n te g e r . t h e n f o r a n y a c 吞 *h a v e in a i ) m i n p , n ja i 一 。 ， + 1 ) , ( 2 . 1 . 1 ) w h e r e n a d e n o t e s t h e s e t o f a l l s u m s o f n d i s t i n c t e l e m e n t s o f a . i n 1 9 9 5 a n d 1 9 9 6 n . a l o n , n a t h a n s o n a n d i .z . r u z s a 5 , 6 1 i n v e n t e d a p o l y n o m i a l m e t h o d t o a t t a c k s i m i l a r p r o b l e m s , t h e y s h o w e d t h e . f o l l o w i n g : t h e o r e m b . l e t p b e a p r i m e n u m b e r a n d a i , a n o n e m p ty s u b s e t s o f z p w i th ja i i 一 ja , i a n d e ,!= , ja ， 卜。 ( n +1 ) / 2 p . t h e n ja i n 一 ， : ) ia 1i+ 一 + ia ,一 (n (n +2 ) + ， ( 2 . 1 .2 ) w h e r e a i n . . . a a s ta n d s f o r t h e s e t c o n s is t i n g o f a l l t h o s e e ,= 1 a ; w i t h a i ) _ , b e in g 。 s y s t e m o f d is t in c t r e p r e s e n ta t i v e s o f a i j _ , 叼冲 l e ti a i 片 ， 峨 : .z 1 4 2】 = c ; + l , “ -i c ， 一 ( 笠 ) . t h e c o r e o f th e ir p r o o f is to s h o w th e c o e f fi c ie n t o f i n t h e p o l y n o m i a l ( x i + 。 + . + x ) 0 n ( 。 一 x j ) , 1 f j rt is n o n - z e ro i n t h e fi e l d z ，i n f a c t, i t i s m! c 1 ! c 2 ! 二 c . 1 n ( c 一 c a 1 4 j 毛n 2 a l g e b r a ic t e c h n i q u e s i n c o m b i n a t o r ic s q in g - h u h o u w h i c h i s n o n - z e r o f o r c i , 1 (i (” b e i n g a l l d i s t i n c t . c l e a r l y , t h i s w i l l f a i l i f c , 1 i j n . =c j f o r s o m e n o tin g th a t th e c o e f fi c ie n t o f x - 1 x 2 - 一 x ,f,- 1 in th e p o ly n o m ia l (x i + 。 + 一 + x ) n (k - i )- n ( - i) f l( 、 一 x j ) 2 i 。 ( 。 一i ) . t h e n t h e c o e f fi c ie n t o f 君 一 ，. . . x , i n 1 1 (x 一 x i ) z n (x 1 + + x ) . (k + ，一” 一 ，( 2 . 1 . 3 ) 1 i j n c o i n c i d e s 。fl间 ( 一 l ) m n ( n - i ) / 2 ( ( k + m一 m n 一1 ) n ) 1( j - ) ! ( m i ) ,( k 一1 一汀一i ) m ) l b y t h i s t h e o r e m , w e g o t t h e l o w e r b o u n d o f r e s t r i c t e d s u m s o n t h e fi e l d o f c h a r a c t e r i s t i c t h e o r e m 2 . 1 . 2 . l e t k ， 二b e n o n n e g a t i v e i n t e g e r s a n d n a p o s i t i v e i n t e g e r . l e t f b e a 卢 e l d o f c h a ra c t e r is t ic p w h e r e p is a p r im e w i th p i n g r e a t e r t h a n m a n d k + m一 ， 一l . l e t a t , - - - , a b e s u b s e t s o f f w it h ja i 卜 一=氏卜 k . f o r e a c h t , j =1 . . . ， 。 w i t h i 0 j , l e t s b e a n y s u b s e t o f f w i t h c a r rl i n a l i ty a t m o s t m . t h e n 10)( k + m 一 二 一i ) n + 1 ( 2 . 1 .4 ) n 功e r e c = a t + 一+ 。 ， : a t e a i , 二 ， a e a, a ， 一 a j 0 s ij if i 0 j ) ( 2 . 1 . 5 ) t h e o r e m 2 . 1 .2 c o v e r s t h e re s u l t s o f d i a s d a s i l v a a n d h a m i d o u n e . m o r e i m p o rt a n t , i t g i v e s t h e b e s t l o w e r b o u n d o f t h e n u m b e r o f s u m s w i t h m o r e t h a n o n e re s t r i c t i o n s . s o m e i n t e re s t i n g re s u l t s a r e o b t a i n e d a s c o rol l a r i e s , s e e s e c t i o n 2 .4 . n o w w e i n t r o d u c e s o m e n o t a t i o n s t h r o u g h o u t t h i s p a r t o f t h e t h e s i s . we s e t n = 0 , 1 , 2 ， 二a n d z + = 1 , 2 , 3 ， 一 f o r k , l e z w e p u t k , l ) 二 x e z : k x 1 ) , a n d k , 1 1 = x e z : k x 1 b e i n t e g e r s . wr i t e mx , . . . ，、 ) = n i i j n c l e a r l y (x i 一 x j.)2, _ y欢呱 x )11 . 二 x 1111 力 . . i 1x 1- 1 .x rt- i ( f m (x i r. ,x n )(x i + -二 + x )n(k- i- m (n- 1)jn ef (m j ( ( k + 二一 m n 一1 ) n ) ! l , 之 .! 引 o ,k ) + j = m a ( n - i ) .l ( k 一i 一 j ) ! . . . ( k 一i 一i n ) ! ( ( k +，一 二 一1 ) n ) 1 ( ( k 一i ) ! ) - e f (爪 l. (k 一 ， )j , ( 、 一 ， )1. j 1 , j . e 0 ,k ) j , + + a= m n ( n -1 ) (k + m - m n;- o n)!(k - 1)!) l (fm )( 一 ” w h e r e l: f x l ， 二。】 *f x i s t h e li n e a r o p e r a to r g i v e n b y l (x i . . .x n ) = (x ) i ， 二(x ) j. t h u s t h e m a in p r o b l e m i s to d