（基础数学专业论文）具有较小迹实部为正的代数整数.pdf

西南大学硕士学位论文摘要 具有较小迹实部为正的代数整数 基础数学专业硕士研究生王春岩 指导老师吴强教授 摘要 我们所研究的问题源于c j s m y t h 【2 4 】提出的如下问题，设整数r 0 ，寻找满足下列 条件的代数整数口： a ) t r ( a ) 一d e g ( a ) = r ； b ) o t i 0 ，i = 1 ，d ， 其中，q t 为q 的极小多项式的共轭根( 设q 1 = a ) ，n ( q ) = q 1 + o r 2 + + q d ，称为o t 的 迹d = d e g ( a ) 是q 的极小多项式的次数如果一个代数整数及其共轭根均为正实数，我们称 此代数整数为全实正的代数整数对于次数为d 的全实正的代数整数，c l s i e g e l 【2 2 】给出 了一个结论：除q = l 或者兰学之外，n ( q ) ；d c j s m y t h 推，了，这个结论，即，除有 限个代数整数q 之外，n ( q ) 1 7 7 1 9 d 进一步，如果a 满足a ) 则有d 【1 2 9 5 5 r 在此结 论的基础上利用有限树搜索，c j s m y t h 得到了满足a ) 和6 ) ，0 r 6 的所有代数整数对 应的极小多项式由于计算上的困难，目前尚未有更多的结果出现 在我们的工作中，我们寻找满足条件a ) ( r z ) 且实部为正的代数整数的问题，即将上述 条件b ) 改为：6 ，) r e ( a 1 ) 0 ，i = l ，d 也就是说我们将全实正的代数整数的问题扩展到 复平面上 这时有限树搜索不再适用我们将探索一种寻找满足上述条件的代数整数的算法，从而更 进一步的深入了解具有较小迹实部为正的代数整数的特性此研究内容尚无资料可查因而我 们的工作具有一定的创新性在算法中我们使用整超限直径，辅助函数和半无限线性规划法的 理论我们的工作主要讨论辐角在某个范围内满足a ) 和6 ，) 的代数整数，即，给o t 加上如下条 件： c ) i a r g ( a i ) l 0 ，i = 1 ，2 ，d 上述问题的运算量非常大，由于时间关系，而且为了更好的构造出解决上述问题的基础算 法，我们只取0 = 矗，应用算法求得1 d 4 且0 r 6 满足o ) 、b ) 和c ) 的代数整数对 应的极小多项式我们观察到满足上述条件的d 2 的代数整数满足n ( q ) d 关键词：代数整数迹整超限直径辅助函数半无限线性规划法 西南大学硕士学位论文 a b s t r a c t a l g e b r a i ci n t e g e r sw i t hs m a l lt r a c ea n dp o s i t i v e r e a lp a r t s m a j o r ：e l e m e n t a r ym a t h e m a t i c s n a m e ：w a n gc h u n y a n s u p e r v i s o r ：p r o f e s s o rw uq i a n g a b s t r a c t i n1 9 8 4c j s m y t hp r o p o s e dt h ef o l l o w i n gp r o b l e m ：l e tr 0b eag i v e ni n t e g e r ，o n e t r i e st of i n da l lt o t a l l yp o s i t i v ea l g e b r a i ci n t e g e r saw h i c hs a t i s f y a ) n ( q ) 一d e g ( a ) = r ； b ) a 0 ，i = 1 ，d ， w h e r eq ia r et h ec o n j u g a t e so fa ( s e to 12a ) ，t l ( q ) = q 1 + q 2 + + a di st h et r a c eo f q ，a n dd = d e g ( a ) i st h ed e g r e eo fi t sm i n i m a lp o l y n o m i a l a na l g e b r a i ci n t e g e ri ss a i dt o b et o t a l l yp o s i t i v e ，i fa l l i t sc o n j u g a t e sa r ep o s i t i v e f o rat o t a l l yp o s i t i v ea l g e b r a i ci n t e g e r ， w i t hd e g r e ed ，c l s i e g e l 2 2 】s h o w e dt h a tt r ( a ) 2 du n l e s sq = 1o r 学c j s m y t h i m p r o v e m e n to fc l s i e g e l sr e s u l t si s ，n ( q ) 1 7 7 1 9 du n l e s sdh a ss o m es p e c i a lm i n i m a l p o l y n o m i a l f u r t h e r m o r e ，i fa ) i ss a t i s f i e dt h e nd 【1 2 9 5 5 r b a s e do nt h i sc o n c l u s i o n ，c j s m y t he n u m e r a t e dt h er e q u i r e dp o l y n o m i a l s ( s a t i s f yn ) ，6 ) ，a n d0 r 6 ) u s i n gaf i n i t et r e e s e a r c h ，w h i c hw a sb u i l d e db yh i m i ti ss h o w nf r o mh i sr e s u l t st h a tt h en u m b e ro fm i n i m a l p o l y n o m i a l si n c r e a s ee x p o n e n t i a l l yb yt w h i l e ，a f t e rt h a t ，s i n c et h ed i f f i c u l t yo fc o m p u t a t i o n ， t h e r ew a sn o ta n ya u t h o r sd i s c u s s i n gt h i sp r o b l e ma sf a ra sw ek n o w i nt h i sw o r k ，w ef i n dt h ea l g e b r a i ci n t e g e rs a t i s f y i n ga ) ( r z ) a n d6 ，) r e ( a i ) 0 ， i = 1 ，d ，i e ，e x t e n d i n gt h ep r o b l e mt ot h ec o m p l e xp l a n e w i t ht h i sc o n d i t i o n ，t h ef i n i t et r e es e a r c hc a n n o ta f f o r dt h ec o r r e s p o n d i n gp r o b l e m w et r yt oe x p l o r ea na l g o r i t h mt og e tt h ea l g e b r a i ci n t e g e r ss a t i s f y i n gt h ea b o v e - m e n t i o n e d c o n d i t i o n ss ot h a tm o r ec h a r a c t e r i s t i c so fa l g e b r a i ci n t e g e r sw i t hp o s i t i v ep a r t sm a yd i s p l a y e d t h e r ei sn o ta n yr e f e r e n c e st or e f e rt o ，t h u so u rw o r ki sc e r t a i n l yo r i g i n a l t h et h e o r e m s o fi n t e g e rt r a n s f i n i t ed i a m e t e r ，a u x i l i a r yf u n c t i o na n ds e m i - i n f i n i t el i n e a rp r o g r a m m i n ga r e a p p l i e di no u ra l g o r i t h m w em a i n l yc o n s i d e ra l g e b r a i ci n t e g e r sw h o s ea r g u m e n t sa r ei na f i x e da n g l e ，i e ，a d d i n gt h ef o l l o w i n gc o n d i t i o nt oq ： c ) i a r g ( a 0 is 口，i = 1 ，2 ，d b e c a u s eo ft h eh u g es i z eo ft h ep r o b l e m ，i nt h en u m e r i c a li m p l e m e n t a t i o n ，w es e t0b ea n s m a l la n g l e ，s a y , 口= 吾，a n dg e ta l lt h em i n i m a lp o l y n o m i a l so fa l g e b r a i ci n t e g e r ss a t i s f y i n g o ) ，6 ，) ，c ) ，1 d 4a n d0 r 6 w ef i n df r o mt h er e s u l t st h a tt r ( a ) 2 dh o l d sf o ra l l a l g e b r a i ci n t e g e r ss a t i s f y i n gt h ep r o v i o u sc o n d i t i o n sa n dd 2 西南大学硕士学位论文a b s 豫a c t k e y w o r d s ：a l g e b r a i ci n t e g e r ，t r a c e ，i n t e g e rt r a n s f i n i t ed i a m e t e r ，a u x - i l i a r yf u n c t i o n ，s e m i - i n f i n i t el i n e a rp r o g r a m m i n g 1 1 1 独创性声明 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加 了特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同 仁在文中作了明确说明并表示衷心感谢。 学位论文作者：王- 各茬 签字日期： 加。尸年岁月叫日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院( 筹) 可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作者签名：王睿老 签字日期： 加尹年箩月叫日 导师签名：关) 呜 签字日期： 痧歹年f 月2 日 l 西南大学硕十学位论文第1 章绪论 1 1问题的提出 第1 章绪论 随着计算机的发展和应用，计算数论渐渐映入人们的眼帘而计算数论的发 展也推动了其自身在实际问题中的应用二十世纪六十年代以来，计算数论在 近似分析、密码学和信息论等领域中已经崭露头脚例如，1 9 8 2 年a k l e n s t r a ， h k l e n s t r a 和l l o v h s z 设计的l l l 算法已经被广泛的应用于了格理论以及其他 领域的研究代数整数d c t ( d i s c r e t ec o s i n et r a n s f o r m ) 和i d c t ( i n v e r s ed i s c r e t e c o s i n et r a n s f o r m ) 编码( 【7 】， 8 】，【1 l 】) 因其低复杂性、免乘法、高精度等特点，在 图像压缩处理中有着越来越广泛的应用 代数整数是数论研究的一个重要内容互反代数整数、代数整数的分布、代数 整数的迹等相关问题引起了许多学者的关注如，r m r o b i n s o n ，j l t h u n d e r ， j w o l f s k i l l ，i s c h u r ，v f l a m m a n g ，cr h i na n dc j s m y t h 等下面我们回顾一 些有关全实正代数整数的结论 设q 是一个d 次全实正的代数整数( 我们简称其共轭根全大于零的代 数整数为全实正的代数整数) ，t r ( a ) = 啦，称为代数整数的绝对迹，其中， 0 q l q 2 1 7 7 1 9 ， 除a 有如下形式的最小多项式之外：z 一1 ，z 2 3 x + 1 ，z 3 5 x 2 + 6 x l ， z 4 7 x 3 + 1 3 x 2 7 x + 1 ，z 4 7 x 3 + 1 4 x 2 8 x + 1 1 西南大学硕十学位论文 1 1问题的提出 至今，关于全实正的代数整数已经有如下结果： t r ( a ) ，i s c h u r ( 1 9 1 8 ) ， t r ( a ) 1 7 3 3 ，c l s i e g e l ( 1 9 4 5 ) ， t r ( a ) ( 1 6 + a 1 ) ，v f l a m m a n g ，gr h i na n dc j s m y t h ( 1 9 9 7 ) ， t r ( a ) 1 7 8 0 0 2 ，j a g u l r r e ，m b i l b a o ，j c p e r a l ( 2 0 0 5 ) ， t r ( a ) ( 1 6 6 + a 1 ) ，j a g u l r r e ，m b i l b a o ，j c p e r a l ( 2 0 0 5 ) ， 其中，q 1 表示和q 共轭的代数整数中最小的上述不等式对除有限个例外多项式 外恒成立详细内容参阅 2 】， 9 】， 2 2 ， 2 5 】1 9 8 4 年c j s m y t h 在【2 4 】中提出并 部分解决了如下问题，设整数r 0 ，寻找满足下列条件的代数整数： a ) n ( q ) 一d e g ( a ) = r ； 6 ) q 0 ，i = 1 ，d ； 其中，o t 为q 的极小多项式的共轭根( 设o t l = q ) ，n ( q ) = q 1 + q 2 十+ q d ， 称为a 的迹d = d e g ( a ) 是q 的极小多项式的次数 定理1 1 表明了满足a ) 和b ) 的d 和r 的关系：ds 【1 2 9 5 5 r 】：= b ( 7 ) 除了 几个例外函数外，d 和r 有下列对应： 7 1234567 b ( r 1 12 35 679 于是，对固定的7 ，d 的取值范围可以得到结合定理1 1 ，c j s m y t h 在【2 4 】 中给出了所有满足a ) 和b ) 以及0 r 6 的多项式在寻找这些多项式时，他使 用了被他命名为有限树搜索f i n i t et r e es e a r c h 的算法这个算法是一种枚举算法， 最早被r o b i n s o n ( 【1 8 】) 应用于寻找次数小于4 的多项式算法的主要思想是如果 一个多项式所有的根都是实数，那么其导函数的根仍全部为实数可归结为如下结 论： 定理1 2 设k 2 ，q ( x ) 是次数为k 一1 的首1 多项式( 首项系数为1 ) ，并 且有实根防 侥 雠一1 0 再设p ( x ) = 忌fq ( t ) d t ( 显然p ( x ) 次数为 k ，且是首一的) ，那么，p ( x ) 一c 所有的根为正实数的充要条件是( - 1 ) 七c 0 ，i = 1 ，d 这里c j s m y t h 的有限树搜索法不再适用对于全实正的代数整数的迹的问 题，已有不少的研究成果，但对于我们的研究内容却并无资料可查因而我们的工 作具有一定的创新性，目的是探索一种计算满足上述条件的代数整数的算法，进而 更进一步的深入了解具有较小迹实部为正的代数整数的特性我们结合使用了牛 顿公式和构造辅助函数的方法我们的工作主要讨论辐角在某个角度范围内满足 a ) 和6 ，) 的代数整数即加上如下条件， c ) i a r g ( a i ) i p ，i = 1 ，2 ，d 在具体的计算中，我们取p = 7 r 1 3 ，而从理论上讲我们的算法对所有0 【0 ，7 r 2 ) 都适合具体的工作如下： 一、第二章介绍了一些相关的基础知识，包括多项式、代数整数的知识，以及 算法中使用的主要理论，包括l l l 算法、半无限线性规划法和整超限直径的相关 知识 4 o 2 o 8 6 4 2 两南人学硕士学位论文 1 2 本文的主要t 作 二、第三章给出了较小辐角范围在内满足a ) 、6 ，) 和c ) 的代数整数的一些结 论其中，定理3 1 和推论3 4 将在第四章的算法中用到 三、第四章论述了算法的结构和结果，并对计算结果进行了相应的分析算法 主要应用到整超限直径，辅助函数和半无限线性规划法的理论 由于问题需要大量运算时间，我们只给出了满足上述条件的d e g ( c y ) 4 ， 0 rs6 的所有代数整数，这对我们更深入的了解实部为正的代数整数的相关性 质有重要意义从求得的界可以看到，算法一定程度上缩减了所要搜寻多项式的个 数，节约了时间从算法的执行结果看，代数整数的个数随着次数的增加呈指数增 长 5 西南大学硕士学位论文第2 幸预铒知识 第2 章预备知识 本章介绍了一些相关的基础知识，包括多项式、代数整数的知识，以及算法中 使用的主要理论，包括l l l 算法、半无限线性规划法和整超限直径的相关知识 2 1基础知识 2 1 1多项式和代数整数 定义2 1 如果数域k 上次数1 的多项式p ( x ) 不能表示成数域p 上的两 个次数比p ( x ) 低的多项式的乘积，则称p ( x ) 为数域p 上的不可约多项式 定理2 2 每个次数1 的复系数多项式p ( x ) 在复数域上都可以唯一地分解 成一次因式的乘积，因此复系数多项式具有标准分解式 f ( x ) = a o ( z 0 1 1 ) h ( z q 2 ) z ( z 一口。) “ 其中a e 是复数，q 1 ，o l 2 ，q 。是互不同的复数，f 1 ，z 2 ，k 是正整数 由此定理可以看出任意次数1 的复系数多项式在复数域c 上可约由于 本文讨论的是代数整数，所有的多项式均是整系数的( 整系数多项式的全体记为 z m ) 在不做说明的情况下，本文接下来谈及多项式刁i 可约均指的是在整数域上不 可约 我们把多项式护一1 = 0 的根称为n 次单位根如果o l 是一个n 次单位根，且 q 不是一个更低次的单位根，则我们称o l 为佗次本原单位根设o l l ，0 1 2 ，o l i p ( n ) 是全体n 次本原单位根，将妒( n ) 次多项式 西n ( z ) = ( z q 1 ) ( z 0 1 2 ) ( z o l i p ( n ) ) 称为几次分圆多项式 定理2 3 分圆多项式垂n ( z ) 是不可约多项式 对整系数多项式p ( x ) = b o x d + b l z d 一1 + + b d 一1 z + b d ，定义它的高度和长度 分别为 d 日( p ) 2 m a x di b k l ， 6 l ( 尸) = 阱 k = o 西南大学硕十学位论文 2 1 基础知识 定义2 4 令p ( z ) = 6 0 + 6 1 z d 一1 + + 6 d = b oi i , 垒1 ( z 一啦) 是非零复系数 多项式，多项式尸( z ) 的m a h l e r 测度定义为： m ( p ) = i b o l1 1i q t i 1 q t i 1 其中，n 1 ，q 2 ，q n 为p ( z ) 的根，也称q 1 ，q 2 ，q 竹为尸( z ) 的共轭根 定义2 5 设q c 如果存在a x x 】使得a ( a ) = 0 ，并且a 不恒为零，则 称o l 为一个代数数 任意一个有理数都可以表示为两个整数的比值因此，上述定义中a z x 】 等价于a q t x l 代数数构成的集合记为砭进一步，若a 是首l 的，则称q 为 一个代数整数代数整数构成的集合记为z _ 显然，z 砭砭 定义2 6 设o t 面，a z x 】不恒为零，若a 是满足a ( q ) = 0 的整系数多 项式中次数最低的，并且其首项系数大于0 ，则称a 是q 极小多项式，极小多项式 的次数称为q 的次数 定理2 7 设口砭，则口的极小多项式是唯一的设q 的极小多项式为a ， 则任意的b z m 满足b ( d ) = 0 必定以a 为因式 从这个定理可以看出，q 巯的极小多项式是首1 且唯一的我们可以用 ( a ，z ) 来表示一个代数数其中a 是q 的极小多项式，z 是q 的一个近似在附录 中我们只给出了满足条件代数整数对应的极小多项式 性质2 8 ( 代数整数的性质) ( 1 ) 若口和p 为代数整数，则q + p ，q p 与o p 也为代数整数 ( 2 ) 若一个代数整数为有理数，则它是普通整数 ( 3 ) 若q 为一个代数整数，则其共轭根也是代数整数 根据代数整数的性质不难得到下面的结论： 推论2 9 缅是一个环 推论2 1 0 设口c 则下面的结论等价： ( 1 ) q 缅 ( 2 ) z q 】是一个有限张成的可加阿贝尔群 定义2 1 1 设q 砭，a 是q 极小多项式，a 的所有根也是代数数，称为a 的 共轭根 7 西南大学硕十学位论文 2 1 基础知识 一个代数数q 的m a h l e r 测度m ( a ) 是指它的极小多项式只的m a h l e r 测度， 其中q 的次数为d ，q = o t l ，o t 2 ，q d 为口的所有共轭根与一个代数整数q 的 m a h l e r 测度有关的是a 的最大模同，又形象地称之为q 的房子 定义2 1 2 令o t 是一个次数为d 的代数整数，q 1 = q ，o t 2 ，q d 是它的所 有共轭根，且它的极小多项式是 p = 6 0 z d + b l z d 一1 + + b d - l x + b d 其中b o = 1 ，我们把o t 的共轭根的模的最大值称为o t 的房子，通常记作 i q l 2 懋荔i q t i 定义2 1 3 如果d 次的代数整数o t 为大于1 的实数，且对它的所有共轭根 o t l = o t ，o t 2 ，q d ，有i q i i ：n i b i ，n i z i = l 我们称向量组b l ，b 2 ，k 为格l 的一组基 8 西南人学硕十学位论文 2 1荩础知识 数论中的许多问题是通过在一定的格中寻找一些最短的( 短的) 向量来解决 的“短”是通过内积给出的范数而言的通常，我们用的范数是欧氏范数或1 2 范 数，即对一个实向量q = 陋- ，q 2 ，q n 】，其范数是 z 2 ( q ) = l l q l l = 圻习巧下矿f _ _ 可研 在格中寻找长度最短的非零向量是比较困难的，对不同的礼，这是一个n p 难题， 即通常情况下，解决这类问题的多项式时问算法是不存在的不过l l l 算法能够 找到最短向量的一个近似值l l l 算法确切做的事情是通过格的一组已知基，返回 一组新基这组新基是在严格意义上推导出来的，它包含有相对短的向量这样一 组基就称为l l l 约简基，其定义如下： 定义2 1 6 ( l l l 约简基) 令b l ，5 2 ，k 是格l 的一组基，酵= b i 一 j i - ：1 l 阮j 6 ；，其中地 j = ( b i b s ) l l l b ；1 1 2 我们称向量组b l ，b 2 ，k 为l l l 约简 的，如果它们满足以下两个条件： ( i ) i 肛t j i 互1 ，1 j 0 ，i = 0 ，以及初始值e ( m ，如e ( o ) = ( o 1 ，o 1 ，o 1 ) 计算 m 扣m 刺i n 如e 。) 步2 取初始值x ( mcx ，计算 m 0 - 卫m x i n ( 。) 如e 。) ， 得到最小值点z ( m ，则m o m m o 步3 置i = i + 1 ，x ( ) = x ( 一1 ) u z ( 一1 ) ) 取x = x ( ) 解( 2 2 1 ) ( 即( 2 2 2 ) ) 得到最小值m i ，并设其对应的e 为e ( ) ( 可能不止一个) ，即， 砚= m i n 夕( z ，e ( ) ， x e x ( o 。 得到最小值点z ( 们，则m m i 仇t 1 1 1 两南人学硕十学位论文 2 2 算法中使用的主要理论 步4 计算 m ：= n 些移夕( z ，e u ) ) ， 则m ，一1 m ：m 步5 则m i m ：终止执行，输出m t 为最优解，e ( ) 为最优取值点否则， 转步3 上述算法是收敛的，因为从上述步骤可以看出m ；m ：一。m ：m m i m i 一1 m o 图2 给出了x = 【a ，b 】的第i 次迭代的模拟图，其中， x k x ( 订，l k n ( 假设n = 3 ) n 随着i 的增大而增大在这个过程中，m 逐 渐接近m 在计算机实现过程中，我们取了= 1 0 6 ，或者1 0 3 7 吃 朋f g ( x , e 1 ) 、j ， i 7 一 ! ， l l ； l l | l ； 口而p lp 2乜p3毛d x = 【口，6 】，j 码= g ( 西，e ) = g c x 2 ，e o ) = g ( x 3 ，露o ) ，m l = g ( p 3 ，e ) 图2 ：半无限线性规划法 2 2 2 整超限直径( t r a n s f i n i t ed i a m e t e r ) 设k 是c 的紧子集，p ( x ) c 】我们引入记号：i p l 。，k = s u p 。ki p c z ) l ，并 定义k 的整超限直径为： 1 2 两南大学硕士学位论文2 2 算法中使用的主要理论 t z ( k ) _ l i m 。i l n f 尸m z i 引n p l o 。1 n ，k n - - 4 0 0 d e gp = n 对任意的佗1 ，如果一个n 次多项式r 满足： i p n l o o ，k2 p z m 】，d i e g n ( p ) ：ni p i ，k ， 我们称r 是一个车比雪夫多项式c h e b y s h e vp o l y n o m i a l 如果k = 【a ，6 】，b - a 4 ， 则t z ( k ) = 宁；如果b o 4 ，t z ( k ) o ，那么( 3 1 3 ) 恒成立； ( 2 ) 如果r 0 ，那么这样的口不存在； ( 3 ) 常数项b d 满足，。 1 6 d l ( 1 + 丢) d s e c 咆 口 ( 3 1 4 ) 证明( 1 ) 是显然的 若r 一 西南火学硕十学位论文3 2 现有的方法 3 2 现有的方法 这一节我们将对已有的一些寻找满足某种条件的代数整数的算法进行讨论 如果次数为d 的多项式p ( x ) 的所有的根的模均不大于b ( 0 ) ，那么由 定理3 1 我们可以确定p ( x ) 的系数b 1 ，b 2 ，6 d ，b o = 1 ，然而，这种方法从 时间的耗费上来讲是十分不经济的对固定的d ，所要搜寻的多项式个数大约 是：n d = n ：1 ( 善) b 岛= n ( d ) b d ( d + 1 ) 2 由欧拉求和公式和s t i r l i n g 的估计，这个 运算关于d 的阶是：o ( b d ( “1 ) 2e x p ( d 2 2 ) ) 特别当b 比较大时，多项式的个数更 是大的惊人例如d = 4 ，b = 8 2 ，g d 一1 4 1 0 1 0 1 9 8 0 年，基于g r a e f f e 的思想，在 6 】中，b o y d 提出了搜寻具有较小的m a h l e r 测度的多项式的方法他用这种方法找到了满足m ( p ) 1 3 ，次数不大于1 6 的整 系数不可约多项式，以及高度为1 ，m ( p ) 1 3 ，次数不大于2 6 的整系数不可约多 项式这种算法的基本思路是非常简单的下面我们对此做一个简单的介绍首先， 设b l ，冗为所有次数为d ，根的模不大于b 的不可约整系数多项式构成的集 合再设尸= b o x d + b l x d 一1 + + b d 一1 z + b d ，b o = 1 ；q 1 = o l ，0 1 2 ，a d 为p ( x ) 的根，定义 d s 知= fq k ，k = 1 ，2 j = l 若对j = 1 ，2 ，d ，有盹i b ，则， i s 血i d 胪，k = 1 ，2 ，( 3 2 1 ) 由【5 】有， s 2 知主s 2 一d b 2 k , k = l 2 ( 3 2 2 ) 并且，根据牛顿公式有， s 七十b l s k 一1 + + b k 一1 8 1 + k b k = 0 ，( 3 2 3 ) 其中，k 1 ，b k = 0 ( k d ) 由( 3 2 3 ) 可知( 8 1 ，s 南) 和( b l ，b k ) ( k d ) 可以 相互确定当b 固定时，s 七的范围可由( 3 2 1 ) 确定而，b l = - - 8 1 ，因此，由( 3 2 3 ) 递推得6 2 ，以此类推可以确定所有的系数b 七，k = 1 ，2 ，d 这种方法所要推算的多项式个数约为， d = 曩d t 2 d b k 一( 2 e b d 2 ) d 一( 2 e 以) d 1 6 西南火学硕十学位论文 3 2 现有的方法 其中，b 一2 1 d 对k d ，应用( 3 2 2 ) ，这将被减少为：( 2 3 ) d 2 举例来说，满足 3 2 1 和3 2 2 的( s 1 ，s 2 ) 的个数约为， 仁( 2 d b 2 - c 扣扣删硝 而当b 比较大时，由公式3 2 1 确定的s 七非常大特别的，对于我们的问题， 由a ) 可以知道，b = o ( d ) ( 7 固定) 那么b o y d 方法所要推算的多项式个数约为： 舭= k f l - - ( 詈) ( d )( ( 删- 1 m k = t tb d ( d + 1 ) 2 - - - - - 0d d ( d + 1 ) 2e x p 可以看到当d 比较大的时候这个数字是非常大的，必须用新的方法来改进下章 我们将给出构造辅助函数的方法从后面的计算结果可以看到我们算法的有效性 1 7 两南火学硕士学位论文笫4 章寻找满足条件的代数整数的算法 第4 章寻找满足条件的代数整数的算法 在 2 4 】中，c j s m y t h 有限树搜索的方法计算了所有满足口) 、b ) 和0sr 6 的代数整数其算法的原理是定理1 2 这一章我们表述用于搜寻所有满足o ) 、6 ，) 和c ) 代数整数的算法的基本结构 4 1算法的主要结构 在算法中，我们采用了b o y d 的算法思想而对一些具体的问题，我们给出了一 些具体的技巧我们应用了构造辅助函数的方法，其原理是整超限直径的相关知识 下面我们给出了算法的的基本结构 算法5 1 步1 给出界b 若代数整数q i ( 1 i d ) 满足o ) 、6 ，) 和c ) ，其中d 和r 确定我们可以得 到，t r ( a ) = d + r ，于是o t 的实部满足0 0 ( j = 1 ，2 ，j ) ，且q ( 1 j j ) 是非零不可约整系数多项 式记i = 名ir e ( z ) 0 ，i a r g ( z ) i p 由于，( z ) 是调和函数，其最小值在j 的 边界上取到关于辅助函数的构造、辅助多项式o f 的选取和e j 的确定，将在本章 的第二节中详细阐述 设，( 名) 在区域z i 上，且满足i z i b 的最小值为m ，那么：一r e ( z ) 一 名le jl o gl 劬( z ) i m 由于o t l ，q 2 ，q d i 且0 0 ( 1 i d ) ， 下界均取l 做比较： “b t ”表示由求得的结果( 附录) 得到的s 括的真实的界； “b u ”、“b t ”对应的行中左边的数字表示s 知的下界，右边表示8 七的上 界： “”表示没有代数整数对应满足o ) 、6 ，) 和c ) d = 3 时，s l = d + 7 ，s 奄( 2 k 3 ) 的界如表2 2 1 西南大学硕+ 学位论文 4 4 算法的执行 123456 b u ( 8 2 ) 1 0 3 0 1 0 ，5 6 1 0 8 5 1 0 ，1 2 21 0 ，1 6 7 1 0 2 1 1 b t ( 8 2 ) 1 3 1 31 2 2 61 9 3 7 2 2 ，5 2 2 7 6 9 b c ( 8 2 ) 1 ，5 0 1 ，7 91 ，1 1 4 1 ，1 5 51 ，2 0 31 ，2 5 7 b u ( 8 3 )2 1 ，1 0 0 2 1 ，2 3 52 1 ，4 2 12 1 ，7 0 42 0 ，1 0 9 72 1 ，1 6 4 2 b t ( 8 3 ) 3 8 3 8 2 4 ，1 2 9 2 5 ，2 2 05 9 ，3 7 1 8 1 ，5 7 0 b c ( s 3 ) 1 ，2 0 91 ，4 0 91 ，7 0 7 1 ，1 1 2 4 1 ，1 6 7 81 ，2 3 8 9 d = 4 时，8 1 = d + r ，8 k ( 2 k 4 ) 的界如表3 123456 b u ( 8 2 ) 1 3 7 5 1 3 ，1 1 31 3 ，1 6 31 3 ，2 2 2 1 3 ，2 8 2 1 3 ，3 5 2 b t ( 8 2 ) 1 4 ，1 4 1 5 2 31 6 3 62 3 5 12 8 6 6 b c ( 8 2 ) 1 ，1 0 61 ，1 5 21 ，2 0 71 ，2 7 11 ，3 4 31 ，4 2 4 b u ( s 3 ) 2 8 ，3 1 4 2 8 ，5 6 12 8 ，9 3 8 2 8 ，1 4 9 52 8 2 1 8 92 8 ，2 9 7 5 b t ( s 3 ) 3 6 3 63 4 9 1 3 2 ，1 9 76 3 ，3 4 5 7 9 ，5 1 4 b c ( 8 3 ) 1 ，5 4 6 1 ，9 4 3 1 ，1 4 9 81 ，2 2 3 71 ，3 1 8 51 。4 3 7 0 b u ( 8 4 ) 5 6 ，1 2 6 05 6 ，2 5 2 35 6 ，4 9 7 9 5 6 ，9 0 3 85 6 ，1 4 4 9 3 5 6 ，2 2 6 0 3 b t ( 8 4 ) 9 4 9 4 7 9 ，3 8 36 4 ，1 1 2 4 1 7 5 ，2 3 9 9 2 1 2 ，4 0 9 4 b c ( 8 4 )1 ，2 8 1 31 ，5 8 3 3 1 ，1 0 8 0 6 1 ，1 8 4 3 51 ，2 9 5 3 01 ，4 5 0 0 8 ( 4 ) 容易知道，次数为1 ，满足o ) 、6 ，) 和c ) ，( 0 7 6 ) 的代数数整数是 l 、2 、3 、4 、5 、6 、7 根据前面求得的8 知，通过m a t l a b 编程，我们求得了 d = 2 4 满足口) 、6 ，) 和c ) 的代数整数的极小多项式，具体结果见附录 ( 5 ) 由于在前面假设了q f 不是p