On splitting polynomials with noncommutative coefficients

Fibonacci-Like Polynomials Produced by m-ary Huffman Codes forAbsolutely Ordered SequencesAlex Vinokur Holon, Israelalexvn@ alex.vinokur@Abstract . A non-decreasing sequence of positive integer weights P ={p 1, p 2,…, p n } (n = N *(m -1) + 1, N is number of non-leaves of m -ary tree) is called absolutely ordered if the intermediate sequences of weights produced by m -ary Huffman algorithm for initial sequence P on i -th step satisfy the following conditions 2,,)(1)(−=<+N 0i p p i m i m . Let T be an m -ary tree of size n and M=M(T) be a set of such sequences of positive integer weights that M P ∈∀the tree T is the m -ary Huffman tree of P (|P |=n ). A sequence P min of n positive integer weights is called a minimizing sequence of the m -ary tree T in the class M (M P ∈min ) if P min produces the minimal Huffman cost of the tree T over all sequences from M , i.e.,M.P P)E(T,)P E(T,∈∀≤min Theorem 1. A minimizing absolutely ordered sequence of size n = N *(m -1) + 1 for the maximum height m -ary Huffman tree (m > 1) isPmin abs (N , m ) ={times)1( times)1(22times)1(110)1(),...,1(,...,)1(),...,1(,)1(),...,1(),1(−−−−−−−−−−m N N m m m G m G m G m G m G m G m G },where G 0(m ) = 1, G 1(m ) = 1, G 2(m ) = 2, G i (m ) = G i -1(m ) + m *G i -2(m ) when N i ,2= ■Polynomials G i (x ) are called Fibonacci-like polynomials. Theorem 2. The cost of maximum height m -ary Huffman tree T of size n = N *(m -1) + 1 for the minimizing absolutely ordered sequence Pmin abs (N , m ) isE (T , Pmin abs (N , m )) = 12)1(4−−−+m m G N – (N +3). ■Samples of Fibonacci-like polynomials and costs of maximum height m -ary Huffman trees are shown.0. PrefaceAbsolutely ordered and k -ordered sequences for binary Huffman trees those have maximum height have been investigated in [1] and [2]. In this article the generalization of absolutely ordered sequences for m -ary Huffman trees those have maximum height is considered.1. Main Conceptions and Terminology1.1. m-ary treesA (strictly) m-ary tree is an oriented ordered tree where each nonleaf node has exactly m children (siblings). Size of an m-ary tree is the total number of leaves of this tree. Let N be number of nonleaves (internal nodes), n be number of leaves of m -ary tree. Number of leaves in m -ary tree satisfies the following conditionn = N *(m -1) + 1. (1)An m -tree (m ≥2) is called elongated if at least (m -1) of any m sibling nodes are leaves. Anelongated binary tree of size n has maximum height among all binary trees of size n . An elongated m -ary tree is called left-sided if only the left node in each m -tuple of sibling nodes can be nonleaf.A m -ary tree is called labeled if a certain positive integer (weight) is set in correspondence with each leaf.Definition . Let T be an m -ary tree with positive weights P ={p 1,.., p n } at its leaf nodes. The weighted external path length of T isi ni i p l P T E ∑==1),(where l i is the length of the path from the root to leaf i .1.2. Generalized m -ary Huffman algorithmProblem definition . Given a sequence of n positive weights P ={p 1,…, p n }, (n -1) = 0 (mod (m -1)). The problem is to find m -ary tree T mi n with n leaves labeled p 1,..., p n that has minimum weighted external path length over all possible m -ary trees of size n with the same sequence of leaf weights. T min is called the m -ary Huffman tree of the sequence P ; E(T,P min ) is called the Huffman cost of the tree T .The problem was solved for binary trees by Huffman algorithm [3]. That algorithm can begeneralized for m -ary trees. A generalized Huffman algorithm builds T min in which each leaf (weight) of m -ary tree is associated with a (prefix free) codeword in alphabet {0, 1,…, m -1}.Note . A code is called a prefix (free) code if no codeword is a prefix of another one.m -ary algorithm description (in the reference to the discussed issue).Algorithm input. A non-decreasing sequence of positive weightsP ={p 1, p 2,…, p n } 11,1−=≤+,n k p p k k ; n = N *(m -1)+1, where N is number of non-leaves. Algorithm output. The sum of all the weights.The algorithm is performed in N steps. i -th step (,N i 1=) is as follows.• i -th step input. A non-decreasing sequence of weights of size n -(m -1)*(i -1).P (i -1)={)1()1(*)1()1(2)1(1,...,,−−−−−−i i m n i i p p p } (1)1(*)1(1;)1(1)1(−−−−=≤−+−i m ,n k p p i k i k ); |P(i -1)|=n -(m -1)*(i -1). • i -th step method. Build a sequence{)1()1(*)1()1(1)1()1(2)1(1,...,,...−−−−−+−−−+++i i m n i m i m i i p p p p p }and sort its .• i -th step output. A non-decreasing sequence of weights of size n -(m -1)*i .P (i )={)(*)1()(2)(1,...,,i i m n i i p p p −−} (1*)1(1;)(1)(−−−=≤+i m ,n k p p i k i k ); |P (i )|=n-(m -1)*i .Note 1. P (0) is an input of m -ary Huffman algorithm, i.e.,)1()0(,n k p p k k ==.Note 2. If an input sequence on i -th step(s) of the algorithm satisfies condition)N i p p i m i m 20()(1)(−≤≤=+,then several m -ary Huffman trees can result from initial sequence P of weights, but the weighted external path length is the same in all these trees.Let P = {p 1, p 2, p 3, …, p n } be a sequence of size n for which the m -ary Huffman tree is elongated . Then according to generalized m -ary Huffman algorithm2,0,...)(2)()(2)(1−=≤+++N i p p p p i m i m i i . (2)2. Main Results2.1. Minimizing absolutely ordered sequence of the elongated m -ary Huffman treeLet T be an m -ary tree (m > 1) of size n (i.e., n = N *(m -1) + 1, where N is number of non-leaves and n is number of leaves) and M=M(T) be a set of such sequences of positive integer weights that M P ∈∀the tree T is the m -ary Huffman tree of P (|P |=n ).Definition . A sequence P min of n positive integer weights is called a minimizing sequence of the m -ary tree T in the class M (M P ∈min ) if P min produces the minimal Huffman cost of the m -ary tree T over all sequences from M , i.e.,M.P P)E(T,)P E(T,∈∀≤minDefinition . A non-decreasing sequence of positive integer weights P ={p 1, p 2,…, p n } is called absolutely ordered if the intermediate sequences of weights produced by m -ary Huffman algorithm for initial sequence P satisfy the following conditions2,,)(1)(−=<+N 0i p p i m i m . (3)For an absolutely ordered sequence the equality-inequality relation (2) is transformed to the (strict) equality relation2,0,...)(2)()(2)(1−=<+++N i p p p p i m i m i i . (4)Lemma 1. A minimizing absolutely ordered sequence of size n = N *(m -1) + 1 for the elongated m -ary tree (m > 1) isPmin abs (N , m ) = {times)1( times)1(22times)1(110)(),...,(,...,)(),...,(,)(),...,(),(−−−m N N m m m Q m Q m Q m Q m Q m Q m Q },where Q 0(m ) = 1, Q 1(m ) = 1, Q 2(m ) = 2, Q i (m ) = Q i -1(m ) + (m -1)*Q i -2(m ) when N i ,2=.Proof . Taking into account (3) (4) we obtain the following configurations of m -ary Huffman algorithm steps for absolutely ordered sequence of the elongated (left-sided) m -ary tree.Step 0: p 1, p 2,…, p m , p m +1,…,p 2m -1, p 2m , p 2m +1,…, p n ; p m < p m +1;Steps 1-(N -2): Step 1: p m +1,…, p 2m -1,∑=mj j p 1, p 2m ,…, p n ;m mj jp p21<∑=; Step 2: p 2m ,…, p 3m -2,∑−=121m j j p , p 3m -1,…, p n ;13121−−=<∑m m j jp p;Step 3: p 3m -1,…, p 4m -3,∑−=231m j jp, p 4m -2,…, p n ;24231−−=<∑m m j jp p;… Step i : p i *(m -1)+2,…, p (i +1)*(m -1)+1,∑+−=1)1(*1m i j jp, p (i +1)*(m -1)+2,…, p n ;2)1(*)1(1)1(*1+−++−=<∑m i m i j jp p;…Step N -2: p (N -2)*(m -1)+2,…, p (N -1)*(m -1)+1,∑+−=1)1(*2)-(1m N j jp, p (N -1)*(m -1)+2,…, p n ;2)1(*)1(1)1(*)2(1+−−+−−=<∑m N m N j jp p;Steps (N -1), N :Step N -1: p (N -1)*(m -1)+2,…, p N *(m -1)+1,∑+−=1)1(*1)-(1m N j jp(Note. According (1) (N *(m -1)+1) = n );Step N :∑+−=1)1(*1m N j jp= ∑=nj j p 1.On Step 0 merging m leaves labeled by integers p 1, p 2,…, p m are merged. Because Pmin abs (N , m )= {p 1, p 2, …, p n } is minimizing sequence of positive integer values, p 1, p 2,…, p m should have minimal positive integer values, i.e., at least they must be equal. So, we can write as followsp 1 = q 0,p 2 = … = p m = q 1;q 0 = q 1.On Step 1 merging (m -1) leaves labeled by integers p m +1,…, p 2m -1 and one nonleaf are merged. Again, because Pmin abs (N , m )= {p 1, p 2, …, p n } is minimizing sequence of positive integer values,p m +1,…, p 2m -1 should have minimal possible positive integer values, i.e., at least they must be equal. So, we can write as followsp m +1 = … = p 2m -1 = q 2.In the same manner for Steps 2,…, (N-1) we obtainp 2m = … = p 3m -2 = q 3; P 3m -1 = … = p 4m -3 = q 4;…p i *(m -1)+2 = … = p (i +1)*(m -1)+1 = q i +1;…p (N -1)*(m -1)+2 = … = p N *(m -1)+1 = q N .So, the configurations of m -ary Huffman algorithm steps for absolutely ordered sequence of the elongated (left-sided) m -ary tree are transformed as follows.Step 0: q 0, times)1(11,..., m q q −, times)1(22,..., m q q −,…,times)1(,..., m N N q q −q 1 < q 2;Steps 1-(N -2): Step 1: times)1(22,..., m q q −, q 0 + (m -1)∑=11j j q , times)1(33,..., m q q −,…, times)1(,..., m N N q q −; q 0 + (m -1)∑=11j j q < q 3;Step 2: times)1(33,..., m q q −, q 0 + (m -1)∑=21j j q , times)1(44,..., m q q −,…, times)1(,..., m N N q q −;q 0 + (m -1)∑=21j j q < q 4;Step 3: times)1(44,..., m q q −, q 0 + (m -1)∑=31j j q , times)1(55,..., m q q −,…, times)1(,..., m N N q q −;q 0 + (m -1)∑=31j j q < q 5;… Step i : times)1(11,..., m i i q q −++, q 0 + (m -1)∑=ij j q 1, times)1(22,..., m i i q q −++,…, times)1(,..., m N N q q −; q 0 + (m -1)∑=ij j q 1< q i +2; …Step N -2: times)1(11,..., m N N q q −−−, q 0 + (m -1)∑−=21N j j q , times)1(,..., m N N q q −; q 0 + (m -1)∑−=21N j j q < q N ;Steps (N -1), N :Step N -1: times)1(,..., m N N q q −, q 0 + (m -1)∑−=11N j j q ; Step N : q 0 + (m -1)∑=Nj j q 1.Because Pmin abs (N , m )= { q 0, times)1(11,..., m q q −, times)1(22,..., m q q −,…,times)1(,..., m N N q q −} is minimizing sequence of positiveinteger values, q 0 and q 1 should have minimal positive integer values, and q 2 should have minimalpossible positive integer value. So, we haveq 0 = 1, (5) q 1 = 1, (6)and, taking into account (3)q 2 = q 1+1 = 2, (7)q i = (m -1)∑−=21i j j q + 1, when i = N ,2.Consider, q i - q i -1 when i = N ,3.q i - q i -1 = ((m -1)∑−=21i j j q + 1) – ((m -1)∑−=31i j j q + 1) = (m -1) q i -2. (8)i.e.q i = q i -1 + (m -1) q i -2, when i = N ,2.From (5), (6), (7) and (8) we obtain that q i is a function of m , i.e., q i = Q i (m ) and thusQ 0(m ) = 1, Q 1(m ) = 1, Q 2(m ) = 2, Q i (m ) = Q i -1(m ) + (m -1)*Q i -2(m ) when N i ,2=. (9)The lemma has been proved.■2.2. Fibonacci-like polynomialsFrom Lemma 1 we can see that m -ary Huffman tree (m > 1) is connected with polynomials Q i (m ) (9). From that we can told that (m +1)-ary Huffman tree (m > 0) is connected with polynomialsG 0(m ) = 1, G 1(m ) = 1, G 2(m ) = 2, G i (m ) = G i -1(m ) + m *G i -2(m ) when N i ,2=.So, we have polynomials that are defined by the recurrence relationG i (x ) = G i -1(x ) + x *G i -2(x ) when i > 2;withG 0(x ) = 1, G 1(x ) = 1, G 2(x ) = 2.Thus, Lemma 1 can be reformulate asTheorem 1. A minimizing absolutely ordered sequence of size n = N *(m -1) + 1 for the elongated m -ary Huffman tree (m > 1) isPmin abs (N , m ) = {times)1( times)1(22times)1(110)1(),...,1(,...,)1(),...,1(,)1(),...,1(),1(−−−−−−−−−−m N N m m m G m G m G m G m G m G m G },where G 0(m ) = 1, G 1(m ) = 1, G 2(m ) = 2, G i (m ) = G i -1(m ) + m *G i -2(m ) when N i ,2=.Huffman related polynomials G i (x ) are Fibonacci-like ones in contrast to Fibonacci polynomials that are defined by another recurrence relation [4]F i (x ) = x *F i -1(x ) + F i -2(x ) when x > 2;withF 1(x ) = 1, F 2(x ) = x .The first few Fibonacci-like (Huffman related) polynomials areG 0(x ) = 1 G 1(x ) = 1 G 2(x ) = 2 G 3(x ) = x + 2 G 4(x ) = 3x + 2 G 5(x ) = x 2 + 5x + 2 G 6(x ) = 4x 2 + 7x + 2 G 7(x ) = x 3 + 9x 2 + 9x + 2 G 8(x ) = 5x 3 + 16x 2 + 11x + 2G 9(x ) = x 4 + 14x 3 + 25x 2 + 13x + 2 G 10(x ) = 6x 4 + 30x 3 + 36x 2 + 15x + 2G 11(x ) = x 5 + 20x 4 + 55x 3 + 49x 2 + 17x + 2 G 12(x ) = 7x 5 + 50x 4 + 91x 3 + 64x 2 + 19x + 2G 13(x ) = x 6 + 27x 5 + 105x 4 + 140x 3 + 81x 2 + 21x + 2 G 14(x ) = 8x 6 + 77x 5 + 196x 4 + 204x 3 + 100x 2 + 23x + 2G 15(x ) = x 7 + 35x 6 + 182x 5 + 336x 4 + 285x 3 + 121x 2 + 25x + 2 G 16(x ) = 9x 7 + 112x 6 + 378x 5 + 540x 4 + 385x 3 + 144x 2 + 27x + 2G 17(x ) = x 8 + 44x 7 + 294x 6 + 714x 5 + 825x 4 + 506x 3 + 169x 2 + 29x + 2G 18(x ) = 10x 8 + 156x 7 + 672x 6 + 1254x 5 + 1210x 4 + 650x 3 + 196x 2 + 31x + 2G 19(x ) = x 9 + 54x 8 + 450x 7 + 1386x 6 + 2079x 5 + 1716x 4 + 819x 3 + 225x 2 + 33x + 2G 20(x ) = 11x 9 + 210x 8 + 1122x 7 + 2640x 6 + 3289x 5 + 2366x 4 + 1015x 3 + 256x 2 + 35x + 2.The Fibonacci-like polynomials G i (x ) are normalized, i.e.G i (1) = Fib i +1, (10)where Fib i is i -th Fibonacci number.According to Theorem 1 the sequencetimes)1( times)1(22times)1(110)(),...,(,...,)(),...,(,)(),...,(),(−−−m N N m m m G m G m G m G m G m G m Gis minimizing absolutely ordered sequence of size n = N *(m -1) + 1 for the elongated (m +1)-ary Huffmantree (m > 0).Definition . Sequence G 0(m ), G 1(m ), G 2(m ), , G N (m ) is called a representative Huffman m -sequence, i.e., representative sequence of the elongated (m +1)-ary Huffman tree (m > 0).Several examples of representative Huffman m -sequences are shown in Table 1.Table 1. Samples of representative Huffman m -sequencesG i (m ): i = 0, 1, 2,…, 12m01 2 34 5 67891011 12131 112 358 1321345589144 2333772 11 2 481632641282565121024 204840963 11 2 511265913731472516673842 8843203694 11 2 61438942466221606409410518 26894689665 11 2 71752 13739710823067847723812 661971852576 11 2 82068 188596172453001564447444 1413084259727 11 2 92386 247849257885212656786214 2721838756818 11 2 1026106 314116236741297042362146122 48501816539949 11 2 1129128 389154150421891164289234488 813089292348110 11 2 1232152 472199267122663293752360072 1297592489831211 11 2 1335178 5632521871436445132299533194 1988483785361712 11 2 1438206 66231341107848686181622765854 29453181213556613 11 2 1541236 769383713834637152435571071852 42380931817216914 11 2 1644268 884463617012819163200841466908 59480842648479615 11 2 1747302 10075537206421036974133271968782 8168687377004172.3. Some properties of Fibonacci-like polynomialsLetS (N , m ) = )(0m G Ni i ∑=. (11)Calculate S (N , m ). Consider(m +1)* S (N , m ) = (m +1)*)(0m G Ni i ∑== )(0m G N i i ∑= + m *)(0m G Ni i ∑== (G 0(x ) + G 1(x ) +)(2m G N i i ∑=) + (m *G 0(x ) +m *)(1m G Ni i ∑=)= (m +1)*G 0(x ) + G 1(x ) +))(*)((111m G m m G i N i i +∑−=+ + m *G N (m )= (m +1)*G 0(x ) + G 1(x ) + ∑−=11N i G i +2(m ) + m *G N (m )= (m +1)*G 0(x ) + G 1(x ) + ∑+=13N i G i (m ) + m *G N (m )= (m +1)*G 0(x ) + G 1(x ) + ∑+=1N i G i (m ) – (G 0(x ) + G 1(x ) + G 2(x )) + m *G N (m )= m *G 0(x ) – G 2(x ) + ∑=Ni G 0i (m ) + G N +1(m ) + m *G N (m )= m *1 – 2 + S (N , m ) + G N +2(m ) = S (N , m ) + G N +2(m ) + m – 2.So,(m +1)* S (N , m ) = S (N , m ) + G N +2(m ) + m – 2, i.e.,m *S (N , m ) = G N +2(m ) + m – 2.ThereforeS (N , m ) =m m m G N 2)(2−++ = mm G N 2)(2−++ 1. (12)In particular,S (N , 1) =121)1(2−++N G = G N +2(1) – 1 = Fib N +3 – 1.2.4. Cost of minimizing absolutely ordered sequence of the elongated m -ary Huffman treeTheorem 2. The cost (i.e., weighted external path length) of elongated m -ary Huffman tree T of size n = N *(m -1) + 1 for the minimizing absolutely ordered sequence Pmin abs (N , m ) isE (T , Pmin abs (N , m )) = 12)1(4−−−+m m G N – (N +3) = 1)23()1(154−−+−−−−+m m n m G m m n .Proof . Let Pmin abs (N , m ) = {p 1, p 2, …, p n } be the minimizing k -ordered sequence of the elongated binary tree T of size n .According to Theorem 1Pmin abs (N , m ) = {times)1( times )1(22times)1(110)1(),...,1(,...,)1(),...,1(,)1(),...,1(),1(−−−−−−−−−−m N N m m m G m G m G m G m G m G m G }.Weighted external path length E (T , Pmin n,k ) isE (T , Pmin abs (N , m )) = i ni i p l ∑=1.where l i is the length of the path from the root to leaf i .T is the elongated binary tree, thereforeE (T , Pmin abs (N , m )) = i ni i p l ∑=1= N *G 0(m –1) + (m –1)∑=−+−Ni i m G i N 1)1(*)1(= N *G 0(m –1) + (m –1)∑=−+−Ni i m G i N 0)1(*)1( – (m –1)*(N +1)*G 0(m –1)= (m –1)∑=−+−Ni i m G i N 0)1(*)1( – (m –2)*(N +1)*G 0(m –1) – G 0(m –1)= (m –1)∑∑=−=−N i iN j i m G 00)1( – (m –2)*(N +1)*G 0(m –1) – G 0(m –1)= (m –1)∑∑==−N j ji i m G 00)1( – (m –2)*(N +1)*G 0(m –1) – G 0(m –1).Thus, taking into account (11) and (12), we obtainE (T , Pmin abs (N , m )) = (m -1) ∑∑==−Nj ji i m G 00)1( – (m –2)*(N +1)*G 0(m –1) – G 0(m –1)= (m –1)∑=−Ni m i S 0)1,( – (m –2)*(N +1)*G 0(m –1) – G 0(m –1)= (m –1)∑=+−−−+−Ni i m m m G 0212)1()1( – (m –2)*(N +1)*G 0(m –1) – G 0(m –1)= ∑=+−−+−Ni i m m G 02)2)1()1(( – (m –2)*(N +1)*G 0(m –1) – G 0(m –1) = ∑=+−Ni i m G 02)1( + (m –3)*(N +1) – (m –2)*(N +1)*G 0(m –1) – G 0(m –1)= ∑=+−Ni i m G 02)1( + (m –3)*(N +1) – (m –2)*(N +1) – 1= ∑=+−Ni i m G 02)1( – (N +1) – 1= ∑=+−Ni i m G 02)1( – (N +2)= ∑+=−2)1(N i i m G – (G 0(m –1) + G 1(m –1)) – (N +2)= S (N +2, m –1) – 2 – (N +2) = S (N +2, m –1) – (N +4) = 12)1(4−−−+m m G N + 1– (N +4)= 12)1(4−−−+m m G N – (N +3)In particular, taking into account (10) we have for binary (i.e., m = 2, n = N +1) Huffman elongatedtreeE (T , Pmin abs (N , 2)) =12)1(4−+N G – (N +3) = G N +4(1) – 2 – (N +3) = G N +4(1) – (N +5) = G N +4(1) – (N +5) = Fib N +5 – (N +5) = Fib n +4 – (n +4).Several examples of costs for several elongated m-ary Huffman trees are shown in Table 2.Table 2. Costs for several elongated m-ary Huffman treesN (number of non-leaves in an elongated Huffman tree)Aritym12 3 4 567 89 102 2613 25 4578132 220363 5953 31025 56 119246501 10122035 40824 41439 97 2335461270 29366777 156195 51855 148 39310142619 671217229 441226 62273 209 60516864752 1322837039 1032357 72693 280 87525987897 2354070983 2122908 830115 361 1209378612306 38872125085 3972679 934139 452 1613528618255 60616206737 69175410 1038165 553 2093713426044 90332324819 113790711 1142193 664 2655936635997 129748489819 178741012 1246223 785 33051201848462 180760713953 270243513 1350255 916 40491512663811 2454321011285 395660214 1454289 1057 48931872682440 3259961397847 563593915 155**** **** 584322854104769 4248521891759 783984216 166**** **** 690527546131242 5445682513349 1068203517 176**** **** 808532838162327 6878803285273 1429153018 187**** **** 938938766198516 8576924232635 1881358719 1974489 1912 1082345366240325 10570765383107 2441067420 2078535 2113 1239352674288294 12892726767049 3126342721 2182583 2324 1410560726342987 15576888417629 39571610References[1] Vinokur A.B, Huffman trees and Fibonacci numbers, Kibernetika Issue 6 (1986) 9-12 (in Russian) – English translation in Cybernetics21, Issue 6 (1986), 692-696.[2] Alex Vinokur, Fibonacci connection between Huffman codes and Wythoff array, E-print, 10 pages– ArXiv – Oct. 2004. – cs.DM/0410013 - /abs/cs/0410013.[3] Huffman D, A method for the construction of minimum redundancy codes, Proc. of the IRE40 (1952) 1098-1101.[4] Eric W. Weisstein. "Fibonacci Polynomial." From MathWorld--A Wolfram Web Resource./FibonacciPolynomial.html。

ON THE ZEROS OF POLYNOMIALSWITH RESTRICTED COEFFICIENTSPeter Borwein and Tam´a s Erd´e lyiIt is proved that a polynomial p of the formnp(x)=a j x j,|a0|=1,|a j|≤1,a j∈,j=0√has at most cn)zeros in the strip{z∈:|Im(z)|≤α},and in the sector {z∈:|arg(z)|≤α}.These essentially sharp results improve and generalize several earlier results.1.IntroductionThe study of the location of zeros of polynomials fromF n:=p:p(x)=ni=0a i x i,a i∈{−1,0,1}begins with Bloch and P´o lya[2].They prove that the average number of real zeros of a polynomial from F n is at most c√log nreal zeros.This result,which appears to be thefirst on this subject,shows that polynomials from F n do not behave like unrestricted polynomials.Schur[11]and by different methods Szeg˝o[12]and Erd˝o s and Tur´a n[7]improve the above bound to c√n for the number of real zeros of polynomials from a large class,namely for all polynomials of the formp(x)=nj=0a j x j,|a j|≤1,|a0|=|a n|=1,a j∈C.In this paper we extend this result by proving that a polynomial of the formp(x)=nj=0a j x j,|a j|≤1,|a0|=1,a j∈C,cannot have more than c√n)zeros in the strip{z∈C:|Im(z)|≤α},where c is an absolute constant.Theorems2.1–2.3,our main results,have self contained proofs distinct from those in[6].They sharpen and generalize some results of Amoroso[1],Bombieri and Vaaler[4],and Hua[8],who gave upper bounds for the number of zeros of polynomials with integer coefficients at1.The class F n and various related classes have been studied from a number of points of view.Littlewood’s monograph[9]contains a number of interesting,chal-lenging,and still open problems about polynomials with coefficients from{−1,1}. The distribution of zeros of polynomials with coefficients from{0,1}is studied in [10]by Odlyzko and Poonen.22.New ResultsThroughout the paperD(z0,r):={z∈C:|z−z0|<r}denotes the open disk of the complex plane centered at z0∈C with radius r>0. Theorem2.1.Every polynomial p of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C,has at most c√n)zeros in the strip{z∈C:|Im(z)|≤α},and in the sector{z∈C:|arg(z)|≤α}. Theorem2.3.Letα∈(0,1).Every polynomial p of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C,has at most c/αzeros inside any polygon with vertices on the circle{z∈C:|z|=1−α},where the constant c depends only on the number of the vertices of the polygon.The sharpness of Theorem2.1can be seen by the theorem below proved in[6]. Theorem2.A.For every n∈N,there exists a polynomial p n of the form given in Theorem2.1with real coefficients so that p n has a zero at1with multiplicity at least√n −1≥c(nα+√Theorem2.B.For everyα∈(0,1),there exists a polynomial p n of the form given in Theorem2.3with real coefficients so that p n has a zero at1−αwith multiplicity at least 1/α −1.(It can also be arranged that n≤1/α2+2.)As a remark to Theorem2.3we point out that a more or less straightforward application of Jensen’s formula gives that there is an absolute constant c>0such that every polynomial p of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C,has at most(c/α)log(1/α)zeros in the disk D(0,1−α),α∈(0,1).(An interested reader may view this remark as an exercise.We will not use it,and hence will not present its proof.)A very recent(unpublished)example,suggested by Nazarov, shows that this upper bound for the number of zeros in the disk D(0,1−α)is, up to the absolute constant c>0,best possible.So,in particular,the constant in Theorem2.3cannot be made independent of the number of vertices of the polygon.3.LemmasTo prove our theorems we need some lemmas.Ourfirst lemma states Jensen’s formula.Its proof may be found in most of the complex analysis textbooks. Lemma3.1.Suppose h is a nonnegative integer andf(z)=∞k=hc k(z−z0)k,c h=0is analytic on the closure of the disk D(z0,r)and suppose that the zeros of f in D(z0,r)\{z0}are a1,a2,...,a m,where each zero is listed as many times as its multiplicity.Thenlog|c h|+h log r+mk=1logr2π2πlog|f(z0+re iθ)|dθ.A straightforward calculation gives the next lemma.Lemma3.2.Suppose f is an analytic function on the open unit disk D(0,1)that satisfies the growth condition(1)|f(z)|≤12π 2πlog|f(z0+re iθ)|dθ≤c(r).The next lemma is used in the proof of both Theorems2.1and2.2.4Lemma3.3.There is an absolute constant c1such that every polynomial of theformp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈Chas at most c1(nr+√af [1−a,1],a∈(0,1],for every f analytic on the open unit disk D(0,1)satisfying the growth condition (1)in Lemma3.2.For the sake of completeness we present the proof of Lemma3.4in Section4. Proof of Lemma3.3.Without loss of generality we may assume that z0:=1and n−1/2≤r≤1(the case0<r<n−1/2follows from the case r=n−1/2,and the case r>1is obvious.)Let p be a polynomial of the form given in the lemma. Observe that such a polynomial satisfies the growth condition(1)in Lemma3.4. Choose a point z1∈[1−r,1]such that|p(z1)|≥exp−c3r +m log2≤log|p(z1)|+m log2≤1n).Now observe thatD(1,r)is a subset of D(z1,2r),and the result follows. Lemma3.5.Suppose that p is a polynomial of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C5Let D(z0,r)⊂D(0,1).Let r∈ 34,1implies that|z0|<13.Let m denote the number of zeros of p in the open disk D(z0,r−δ).Applying Jensen’s formula on D(z0,r)and Lemma3.2,we obtainlog 2r−δ≤log|p(z0)|+m log r2π2πlog|p(z0+re iθ)|dθ≤c(r).As0<r<1and0<δ<r,we havelogr1−(δ/r)≥δ4a and with major axis1−a−13a32.Let E a be the ellipse with foci at1−a and1−a+132,1−a+14aThenmax z∈E a |f(z)|≤maxz∈[1−a,1−a+18z+z−18.The Hadamard Three Circles Theorem is applied with r1:=1,r:=2,and r2:= 4.Corollary4.2.Let E a be as in Corollary4.1.Thenmax z∈E a |f(z)|≤322(1−a)(z+z2).Observe that h(0)=0,and thereare absolute constants c4>0and c5>0such that|h(e it)|≤1−c4t2,−π≤t≤π,and for t∈[−c5a,c5a],h(e it)lies inside the ellipse E a.Now let m:= 2πc5/a +1. Letξ:=exp(2πi/(2m))be thefirst2m th root of unity,and letg(z):=2m−1j=0f(h(ξj z)).Using the Maximum Principle and the properties of h,we obtain|f(0)|2m=|g(0)|≤max|z|=1|g(z)|≤maxz∈E a|f(z)|2m−1k=11(m−1)!4<maxz∈E a|f(z)|2e c7(m−1),and the lemma follows by Corollary4.2.5.Proof of the TheoremsProof of Theorem2.1.It is sufficient to prove the upper bound of the theorem for the number of zeros in a triangle with vertices0,w,and w−1,where|w|=17and Re(w)≥14,r:=3 2.it is sufficient to prove that every polynomial p of the formp(x)=nj=0a j x j,|a0|=1,|a j|≤1,a j∈C,has at most c(nα+√,r:=34,r:=32 impliesα−1≤nα).Proof of Theorem2.3.Without loss of generality we may assume thatα∈(0,1 w,where|w|=1−αand Re(w)≥14e iθ,r:=34e−iθ,r:=3w is covered by the union ofS1and S2.Hence the theorem follows from Lemma3.5.References1. F.Amoroso,Sur le diam`e tre transfini entier d’un intervalle r´e el,Ann.Inst.Fourier,Grenoble40(1990),885–911.2. A.Bloch and G.P´o lya,On the roots of certain algebraic equations,Proc.London Math.Soc.33(1932),102–114.3. F.Beaucoup,P.Borwein,D.Boyd,and C.Pinner,Multiple roots of[-1,1]power series,J.London Math.Soc.(to appear).4. E.Bombieri and J.Vaaler,Polynomials with low height and prescribed vanishing,inAnalytic Number Theory and Diophantine Problems,Birkhauser(1987),53–73.85.P.Borwein and T.Erd´e lyi,Polynomials and Polynomial Inequalities,Springer-Verlag,New York,1995.6.P.Borwein,T.Erd´e lyi,and G.K´o s,Littlewood-type problems on[0,1],manuscript.7.P.Erd˝o s and P.Tur´a n,On the distribution of roots of polynomials,Annals of Math.57(1950),105–119.8.L.K.Hua,Introduction to Number Theory,Springer-Verlag,Berlin Heidelberg,NewYork,1982.9.J.E.Littlewood,Some Problems in Real and Complex Analysis,Heath MathematicalMonographs,Lexington,Massachusetts,1968.10. A.Odlyzko and B.Poonen,Zeros of polynomials with0,1coefficients,Ens.Math.39(1993),317–348.11.I.Schur,Untersuchungen¨u ber algebraische Gleichungen.,Sitz.Preuss.Akad.Wiss.,Phys.-Math.Kl.(1933),403–428.12.G.Szeg˝o,Bemerkungen zu einem Satz von E.Schmidt uber algebraische Gleichungen.,Sitz.Preuss.Akad.Wiss.,Phys.-Math.Kl.(1934),86–98.9。

Math5286H:FundamentalStructures of Algebra IIHW2Solutions,(February17th,2012)Problems from Chapter11of Artin’s Algebra:6.2Yes,Z/(6)is isomorphic to Z/(2)×Z/(3).Consider the explicit mapϕ:Z/(2)×Z/(3)→Z/(6)defined byϕ((x+(2))×(y+(3)))=x+(2))×(3and−2.(Try squaring them modulo6and note that1−3.)Thus, Z/(6)∼=3S×(−2)S by Proposition11.6.2,and we verify that3S∼=Z/(2)and(−2)S∼=Z/(3).In the second case,Z/(8)has no non-trivial idempotents:22=62=4,32=52=72=1,42=0,and thus we cannot write Z/(8)as a product ring.6.3We will show that the only ring(using our usual definitions,mutativity of multiplication andcontaining an multiplicative identity)of order10is the ring Z/(10).Firstly note that if|R|=10,then(R,+)is afinite abelian group of order10.Since10is square-free, (R,+)∼=Z/10Z.Thus the only question is whether R could be given a multiplicative structure different than that of Z/(10).However,since(R,+)∼=Z/10Z,we know that the characteristic of R is10and thus {1,9}are all distinct elements.(Here,a·c where c=ab=(1+1+1+···+1)(1+1+···+1)mod10,and hence no exotic multiplication structures are possible.Remark:One might try to break R,a ring of order10into product rings using idempotents.In fact, Z/(10)contains the idempotents6=Remark2:This proof uses the fact that R contains a multiplicative identity1R.If we relax this restriction,as is sometimes done in the literature,for instance if one looks at certain matrix rings,then other“rings”of order10are possible.For example,R= 0000 , 0100 , 0200 ,..., 0900 .Note that the product of any two elements in this ring is zero and there is in fact no multiplicative identity.6.4(a)F2[α],such thatα2+α+1=0,is isomorphic to the quotient ringR={0,1,α,α+1}whereα2=α+1,(α+1)2=α,andα(α+1)=1.HenceR=F2[x]/(x2+1).In F2[x],the polynomial x2+1factors as(x+1)(x+1)since12+1≡0 mod2and x2+2x+1≡x2+1mod2.The ringR=F2[x]/(x2+x).In F2[x],the polynomial x2+x factors as x(x+1)and soR∼=αR∼=F2×F2.6.5Adjoining an elementαto R that satisfies the relationα2−1=0is equivalent to considering thequotient ring2(α+1)and e′=−122(α+1)2=12(α+1).Note also thate+e′=1.Thus R×e′R and e′R or e′f which has no non-constant terms where the coefficient is not0or1.Also let f0denote the constant term of f and write it as f0=2q f+r f where q f∈Z and r f∈{0,1}.We then have the mapϕ:Z[x]/(2x)→F2[x]×Z defined byϕ(f−2q f,f0). To see that this map is a ring homomorphism,note thatϕ(g)=(g−2q f−2q g,f0+g0)=(g−2q g,g0),ϕ(g)=(g−2q fg,f0g0)=(g−2q g,g0)(since the cross-terms vanish mod2),andfinallyϕ(to the subring of F2[x]×Z corresponding to its image.Noting that(b∈J.The cross-termβ·b=0since IJ=0and so we are left with a contribution from the quotient R/J.The same argument shows thatγR∼=R/I.Example:If we let R=Z/(6),I=(2)and J=(3),notice that IJ=(6),which is the zero ideal in R. We have R=I+J since1≡4−3mod6.We obtain Z/(6)∼=R/(2)×R/(3)∼=Z/(2)×Z/(3).If we try the same argument with R′=Z/(8)and I′=(2),(J)′=4,we still have I′J′=(0)but we do not have R′=I′+J′in this case.7.1Let R be afinite integral domain,i.e.a ring with no zero divisors.For every nonzero element r∈R,welook at powers r n and note that since R isfinite,r d=1for some d>0.Hence r·(r d−1)=r and all nonzero elements of R are units.Thus R is afield.7.2Suppose that R[x]is not an integral domain and that f(x)g(x)=0where f(x)and g(x)are both nonzero.Let f(x)=a n x n+a n−1x n−1+···+a1x+a0and g(x)=b m x m+b m−1x m−1+···+b1x+b0where a n andb m are both nonzero.Then f(x)g(x)=0has a term of degree m+n,a n b m x m+n,and so a n b m must equal0.However,a n and b m are both nonzero so R cannot be an integral domain.Thus by the contrapositive,R[x]is an integral domain whenever R is.Furthermore,if f(x)=a n x n+a n−1x n−1+···+a1x+a0with a n=0and n≥1,then f(x)g(x)is a non-constant polynomial,of degree≥n≥1,for any g(x).Thusany non-constant polynomial cannot have a multiplicative inverse.Since R⊂R[x],any unit of R is alsoa unit in R[x],and these are the only units in R[x].7.3Anyfinite integral domain is afield,by Exercise7.1.Furthermore,by Lemma3.2.10,the characteristic ofafinitefield is a prime integer.However,as in Exercise6.3,for any ring R with15elements,(R,+)must be Z/15Z.But then the characteristic would be15,which is not prime.Thus,no integral domain with 15elements exists.8.2(a)Since R is afield,(0)and(1)are only ideals in R.We now consider R×R,whose ideals are theproducts(0)×(0),(0)×(1),(1)×(0),or(1)×(1).To see that no other ideals are possible,simply note that if I is an ideal of R×R and I contains an element(x,y)whosefirst coordinate is nonzero,then I also contains(1,y).By similar logic,the second coordinate is either always zero or I contains the element (0,1)or(1,1).Since(1)×(1)is the unit ideal and we have the inclusions(0)×(0) (0)×(1) (1)×(1) and(0)×(0) (1)×(0) (1)×(1),we conclude that the maximal ideals of R×R are0×R and R×0.For(b),(c),and(d),we determine the ideals in a quotient ring by using the Correspondence Theorem.(b)The ideals in R[x]/(x2)are the ideals in R[x]containing(x2).Since R is afield,R[x]is a Principal IdealDomain,and the ideals of R[x]containing(x2)are(0),(x),and(x2).By the Correspondence Theorem, we get three ideals in R[x]/(x2),the unique maximal ideal being(x).(c)Analogously,we factor x2−3x+2=(x−2)(x−1)in R[x]and we obtain the maximal ideals in R[x]/(x2−3x+2)are(x−2)and(x−1).(d)Lastly,we note that x2+x+1has non-real roots so is irreducible in R[x].Hence,R[x]/(x2+x+1)is afield where the unique maximal ideal is(0).8.3In F2[x],the polynomial x3+x+1has no roots.In particular,03+0+1≡13+1+1≡1mod2.Thusx3+x+1has no linear factors and is irreducible so F2[x]/(x3+x+1)is afield.However,in F3[x],the polynomial x3+x+1has root1since13+1+1≡0mod3.Thus(x−1)≡(x+2) is a linear factor of x3+x+1.In fact,x3+x+1factors as(x+2)(x2+x+2)in F3[x].(But we do not need the exact factorization.)We conclude that F3[x]/(x3+x+1)has a nontrivial maximal ideal like parts(b)and(c)of the previous problem and hence is not afield.Problems from Chapter12of Artin’s Algebra:1.4Wefirst note(see Exercise1.3of Chapter12)that the Chinese Remainder Theorem,proven for generalideals in Exercise6.8,works also in the special case that R=Z.In fact,it wasfirst demonstrated for such examples.(There is also a generalization to more than two ideals as long as each pair I i,I j of ideals satisfy R=I i+I j.)From this theorem,we have the isomorphismϕ:Z/(mn)→Z/(m)×Z/(n)given by x+(mn)→(x+(n))when gcd(m,n)=1.We construct the inverse mapϕ−1by noting that since gcd(m,n)=1,there exist integers r and s so that rm+sn=1.We thus let x=(sn)a+(rm)b and obtain x≡a mod m and x≡b mod n.Having outlined the general procedure,we now apply it to the examples.(a)If x≡3mod8and x≡2mod5,we notice gcd(8,5)=1,and in particular2·8−3·5=1.So letx=3(−15)+2(16)=−13≡27mod40.We indeed verify that27≡3mod8and27≡2mod5.Remark:This might also be found by inspection by looking at the intersection of the sets{3,11,19,27,35} and{2,7,12,17,22,27,32,37}.(b)We do this problem in two steps since there are three congruences.First wefind y mod120so thaty≡3mod15and y≡5mod8(120=15·8).With the same method,we see gcd(8,15)=1,and it is easy to eyeball2·8−1·15=1.So we let y≡3(16)+5(−15)≡93mod120.Next we wish tofind x mod840so that x≡93mod120and x≡2mod7.We see gcd(120,7)=1and1·120−17·7=1.(This is still easy to spot but otherwise there is the extended Euclidean algorithm,which we have not discussed in class,that can be used tofind r and s.)So we choose x≡2(120)+93(−119)≡−10827≡93mod840.Actually,the fact that x and y both equal93is a coincidence since93≡2mod7.So if we would have checked all the congruences at that point instead of continuing we would have had a pleasant surprise.(c)Again gcd(43,71)=1,and we do an adhoc version of the extended Euclidean algorithm:71=1·43+28,43=1·28+15,28=1·15+13,15=1·13+2,13=6·2+1.Thus we can back-solve,and obtain1=13−6¨2=13−6·(15−13)=−6·15+7·13=−6·15+7(28−15)=−13·15+7·28.Continuing,1=−13(43−28)+7·28=20·28−13·43=20(71−43)−13·43=20·71−33·43.Thus if we want x ≡13mod 43and x ≡7mod 71,we take x ≡13(20·71)+7(−33·43)≡2421mod 3053where 3053=43·71.Like magic,you can verify that x =2421satisfies the desired congruences.2.1(a)Since x 3+x 2+x +1is a cubic,we look for possible roots in F 2.We see 03+02+0+1≡1mod 2and 13+12+1+1≡0mod 2.Thus (x −1)≡(x +1)is a root.By synthetic division,we obtain x 3+x 2+x +1=(x +1)(x 2+1).We see that 1is again a factor of x 2+1,and in fact x 3+x 2+x +1=(x +1)3in F 2[x ].This can also be done by inspection and using the Binomial Theorem to expand this cube.(b)We again try to find roots,this time in F 5.By inspection,12−3−3≡0mod 5and so (x −1)is a linear factor.We obtain x 2−3x −3=(x −1)(x −2)in F 5.(c)We attempt to find a square-root of −1≡6in F 7.We see that no such root of x 2+1exists,hence x 2+1is irreducible in F 7[x ].2.3This is similar to Monday’s question about x 2−1in class.By trying out 0,1,2,...,7we see that the polynomial x 2−2has no roots in Z /(8)[x ].Note that it is actually sufficient to test 0,1,2,3,4since 5,6,7are equivalent to −3,−2,−1.A similar shortcut holds for part (c)of the previous problem.2.6(a)We wish to show that Z [ω](with ω=e 2πi/3)is a Euclidean Domain with the size function σ(a +bω)=a 2−ab +b 2when a and b are not simultaneously zero.Note that as a complex number,ω=−1+√2,andif we think of α=a +bωas a complex number,then σ(α)=|α|2=α2)2+(b√2)2.We use the fact that ωis a primitive cube root of unity to see that each principal ideal (α)⊂Z [ω]is a triangular lattice.(As opposed to Z [i ]where the fundamental regions of the lattice were squares instead.)In particular,we see that α,ωα,and ω2αare all elements of Z [ω].Furthermore,since x 3−1factors as (x −1)(x 2+x +1)and ω=1is a root of x 3−1,we have the identity ω2+ω+1=0.(This identity can also be proven explicitly using ω2=−1−√2.)Thus α+ωα+ω2α=0,hence why we get triangles as fundamental regions,in fact equilateral triangles.(This is similar to Z [i ]where 1+i +(−1)+(−i )=0and so the fundamental regions have four sides and are squares.)The centroid of an equilateral triangle (with side lengths |α|is at most a squared distance of 13σ(α)away from a lattice point,i.e.multiple of α.(This is done using 30-60-90triangles to calculate the lengths of the segments in the associated barycentric subdivision.)So if we write β=αq +r ,we get σ(r )≤1−3]and then finding the nearest element of Z [ω]whose two components are half-integers satisfying a parity contraint.Some crude bounds give that the remainder has the form 2r 0+r 12√4and |r 1|≤14σ(α)+316σ(α)when r =0.√(b)The case of Z[−2)=a2+2b2,which is again|α|2ifα=a+bi√−2],the principal ideal(α)is again a lattice,only this time√the fundamental domains are rectangles where one side has length|α|and the other one has size|α|−2],β−qα=r is either zero orσ(r)is at most(12)2=34σ(α).√2in R which acts trivially in Z[x],we get that the polynomial 3.1(a)By applying the automorphism√2)=x2−2x−1is in the kernel ofϕ:Z[x]→R sending x to1+√(x−1−2+b=0unless a=0and b=0.Thus the kernel ofϕis a principal ideal with the named prime element as a generator.(b)By similar logic,we try tofind an element of the kernel ofϕwhich sends x to1 2.To make this easier, wefirst think ofϕof sending Q[x]to R,and obtain element of the kernel(x−12)(x−12)=x2−x−7(4x2−4x−7)where4x2−4x−7is the unique primitive integer4polynomial in such a factorization.Thus4x2−4x−7is a prime element of Z[x]that is in the kernel ofϕ.We apply Theorem12.3.6(a)here to show that the kernel is again principal.Suppose that f(x)is another element in the kernel that is not a multiple of4x2−4x−7.But Q[x]is a principal ideal domain and so thinking of them as polynomials with rational coefficients,we have that f(x)must be a multiple of 4x2−4x−7in Q[x].However,since4x2−4x−7is a primitive polynomial,4x2−4x−7must therefore divide f(x)in Z[x]as well.3.2Suppose that two polynomials,f and g,in Z[x]are relatively prime elements of Q[x].Since Q[x]is of theform F[x],with F afield,it is a Principal Ideal Domain and relatively prime means that gcd(f,g)=1.Thus there exists r(x)and s(x)∈Q[x]so that r(x)f+s(x)g=1.However we multiply through bya common integer d to clear denominators in r(x)and s(x),obtaining r′(x)and s′(x)∈Z[x]so thatr′(x)f+s′(x)g=d.Thus the ideal(f,g)contains the integer d in Z[x]and we obtain the forward direction.To see the reverse direction,assume that the ideal(f,g)contains the integer d.Then there exists r′(x) and s′(x)∈Z[x]such that r′(x)f+s′(x)g=d,and dividing by d,we obtain r(x)f+s(x)g=1as above.Hence f and g are relatively prime in Q[x],completing the proof.。