Share This Article:

Formulas for Coefficients of Hundred Cyclotomics and Numbers Battle

Abstract Full-Text HTML XML Download Download as PDF (Size:356KB) PP. 97-115
DOI: 10.4236/ajcm.2019.92008    255 Downloads   395 Views  
Author(s)    Leave a comment

ABSTRACT

In this paper, we will establish a formula for calculating the 3144 coefficients coe(n, i) of the first hundred cyclotomic of index n in xi. We will only determine 1003 for an index n odd and a degree . The others will be deduced, we’ll see how. The formula is , without exception if u(n)=-1 or if 4 doesn’t divide and with its 165 exceptions of which 7 when u(n)=0 and 158 when u(n)=1 that will be shared in 154 and 4 pairs (n, i), which we will specify the conditions and values of the coefficients. According to u(n), according to the class of i modulo p, the first factor of the prime factor decomposition of n when u(n)=1 and according to gcd(n, i), the formula will or will not be valid and replaced otherwise by the good value that will be 0 for 152 pairs (n,i) or 1 in the 13 other exceptions.

1. History

Since Viete [1] (1540-1603) developed the literal calculus, represented the unknowns by vowels and the parameters by consonants and introduced the notation of the sum, the product, the quotient, and the power. And since “B in A quadratum, plus D in A, aequari C” is replaced, in the works of Descartes by b x 2 + d x = c , everything is then in place for the general study of polynomials to develop. Greek mathematics was essentially arithmetical and geometric. among the Arabs, mathematics is progressively detached from the geometric constraint. It’s the birth of the algebra traditionally attributed to Al Khawarizmi in his work Abstract of computation by restoration and comparison. Carl Friedrich Gauss uses in his writings, published in 1801, the cyclotomic polynomials [2] . The polynomial cyclotomic index 4 allows the construction of a new set of algebraic numbers, that of integers of Gauss. A mathematical branch is born: the algebraic theory of numbers, it simplifies the resolution of Diophantine equations and allows to solve new ones. This approach is innovative and fore shadows modern algebra.

2. Introduction

Note that formula numbers will be in parentheses (x), while bibliographic references will be enclosed in square brackets [y].

.Ah! This cyclotomic world and this “cyclotomic” word that one does not even find in a normal dictionary (You need an encyclopedia) and which recalls cycling and filming, but which also inspires this apparatus which emits light rays of which the rays are reduced and enlarged and stun the voyeur, the observer and the contemplator. Thus is this theory of cyclotomic polynomials with its descents and ascents, in their degrees, their coefficients, their numbers, their real and complex values, their roots, etc.

Yes finally formulas for cyclotomics and their coefficients, as indicated by the title. Formulas that we will try to demonstrate and verify by examples and scripts with maple 12 in principle for the first hundred, except indication and precision for a higher index.

The main objective of this article is to establish the formula of the theorem 3.9, the theorem 3.13 and its corollary 3.15.

Like parraph 6 which will make it possible to determine all the cyclotomics thanks to those of prime indices whose expression is known (formula (6)). The goal is also to find practical and easy formulas applicable to the hand and without data processing, for the cyclotomics and their coefficients, until nowadays nonexistent. All we know today is that the first distinct coefficient of −1, 0 and 1 is at the degree i = 7 and degree j = 41 of cyclotomic index n = 105. [2] . In short, what we want is: A formula for calculating the coefficients. An easy method to designate cyclotomic polynomials. Develop the cyclotomic theory, spread it and make it more touchable, more ready and more popular among mathematicians.

The article, its presentation and the demonstrations of the results are not always classical, they are sometimes done by checking with Maple scripts, especially that these results concern in general only the first hundred cyclotomics, but which will be able to inspire generalization in the future. It is the case in this article for the proposition 3.3 and the theorem 3.13 that we have extended up to 1000 only (but the formula is still true) because the script would require a big delay and could block execution if it is extended more. we know that today there are no formulas for these coefficients, not even for a finite number of them. This article is unpublished, new and never published.

We will adopt in the text and with maple 12, the notation φ for the indicator of Euler phi and c y ( n ) to designate the cyclotomic polynomial of index n of indefinite x by default, otherwise we will specify another indeterminate y we want to assign to x by c y c ( n , y ) , (y can be x , x 2 , x 3 or any other power of x). We will denote by c o e ( n , i ) the coefficient of c y ( n ) in x i , All this after having downloaded the “numtheory” package.

Thus we will have for example:

c y ( 6 ) = x 2 x + 1 , c o e ( 6 , 1 ) = 1 , c y c ( 6 , 2 ) = 3 because when x is replaced by 2 in c y ( 6 ) , it gives 3.

And then we have the following properties:

Property 2.1. If n is even: c y ( 2 n ) = c y c ( n , x 2 ) . (1)

Property 2.2. If n is odd: c y ( 2 n ) = c y c ( n , x ) . (2)

In polynomial theory, the nth cyclotomic polynomial is the unit polynomial whose roots are the primitive roots nth of the unit. It is of degree φ ( n ) [3] (See Serge Lang [3] ), indicator function of Euler φ that we will define, It is with integer coefficients and is irreducible on . For any integer m, the polynomial X m 1 is the product of the cyclotomic polynomials associated with the divisors of m (see [4] ). A root nth of 1 is primitive if it generates the group (multiplicative) G n , roots nth of 1. Now a root nth of 1 is of the form e 2 i k π n , ( 0 k < n ) , image k by group isomorphism ( [4] ):

( / n , + ) ( G n , x ) , which at k associates e 2 i k π n . So a root nth, e 2 i k Π n will generate G n (that is, its powers will cover G n ) if and only if k generates the additive group / n (that is, its multiples will encompass / n ), which equals k first with n [5] (see [5] ).

The number of non-zero k integers strictly less than k is φ ( n ) , which is why the degree of φ ( n , x ) , the nth cyclotomic polynomial in x is φ ( n ) , this Euler’s indicator, whose properties will be studied, which will involve others on cyclotomic polynomials. With maple, and to simplify the notations, we will define the function cy which at an integer n will associate the nth cyclotomic noted in maple by c y c l o t o m i c ( n , x ) .

We thus have c y ( n ) = ( n , x ) = k = 0 , k n = 1 n 1 ( x e 2 i k π n ) (3)

where k n = 1 denotes the g c d ( k , n ) .

The analysis of these polynomials allows the resolution of many problems. As an example of cyclotomic polynomials: c y ( 2 ) = 1 + x , c y ( 5 ) = x 4 + x 3 + x 2 + x + 1 and c y ( 6 ) = 1 x + x 2

Definition 2.3. The function φ , indicator of Euler is the one which to an integer n associates the number of primes with n strictly lower than n.

Remark 2.4. This is also the number of generators of G n , the multiplicative group of nth roots of 1.

Definition 2.5. The cyclotomic polynomial of index n is the polynomial whose roots are the generators of Gn.

Property 2.6. c o e ( n , i ) = c o e ( n , φ ( n ) i ) . (4)

That is, we have a symmetry of the coefficients of c y ( n ) with respect to that of x φ ( n ) / 2 .

Definition 2.7. We call function of Mobius μ , the function which at a positive integer n associates μ ( n ) with μ ( n ) = 0 if n is with square factor, that is, if it is divisible by the square of a prime number, otherwise it’s 1 if n is divisible by the even of a prime numbers; or −1 if the number of prime numbers that divide it is odd.

Recall that g c d ( n , i ) denotes with maple the gcd of n and i.

We will define in the same way that cy and cyc the function c o e ( n , i ) which at ( n , i ) will associate the coefficient of x i of the cyclotomic polynomial of index n.

Finally we will also define m o b ( n , i ) and m o b i ( n , i ) for the values

μ ( n g c d ( n , i ) ) and μ ( n g c d ( n , φ ( n ) i ) ) (because the function mob is not symmetric and these last two quantities are not always equal) and we will designate by m o b 1 ( n , i ) the value of 1 2 ( μ ( n g c d ( n , i ) ) + μ ( n g c d ( n , φ ( n ) i ) ) ) , values that will be used to set conditions of validity or not of certain formulas. And for the last paragraphs we will also need m o b 2 ( n , i ) which will express the largest of m o b ( n , i ) and m o b i ( n , i ) to reduce the number of exceptions to certain formulas and some conditions for applying these formulas. With maple it will be > m o b 2 ( n , i ) : = max ( m o b i u s ( n / g c d ( n , i ) ) , m o b i u s ( n / g c d ( n , p h i ( n ) i ) ) ) .

Formulas and conditions that will be applied directly to the odd n 1 cyclotomic indexes ( g c d ( n , 2 ) = 1 ) and degrees i less than or equal to φ ( n ) 2 , except for 0 since c y ( 1 ) is known (It is x 1 ) and we know that the constant coefficient of a cyclotom polynomial is 1. This will avoid us to specify (“from 0”), since without this precision, maple starts by default the variation of a parameter starting from 1, when one does not specify the first value. By against it is necessary to him to specify the last one with the help of to “ φ ( n ) 2 ”.

We will deduce the ones for the n pairs by the formulas we will recall linking the c y ( n ) to the c y ( 2 n ) when n is even ( c y ( 2 n ) = c y c ( n , x 2 ) ) or when n is odd ( c y ( 2 n ) = c y c ( n , x ) ) [6] after defining the largest integer k such that 2 k divides n. And for degrees greater than φ ( n ) 2 , we will deduce the coefficients by symetry with respect to φ ( n ) 2 [7] .

We can even deduce the coefficients of c y ( n ) if n = 2 k m with m odd less than 100, thanks to the relations ente c y ( 2 n ) and c y ( n ) when n is odd or even. as well as for n when the part without square factor n is less than 100, using the formula

c y ( n ) = c y c ( p s f c ( n ) , x n p s f c ( n ) ) (5)

see [7] , where p s f c ( n ) is the non-square part of n, which is the product of prime numbers that divide n.

The total number of coefficients of the first 100 cyclotomics is 3144, with maple 12 one has to calculate:

> a d d ( φ ( n ) + 1 , n = 1 , , 100 )

which gives:

3144

If we take the 100 constant terms, there will remain 3044. If we only want to count for the odd n indices up to the degree i less than or equal to φ ( n ) 2 , we must assume φ ( n ) even, that is to say start n to 3 (because φ ( 1 ) = φ ( 2 ) = 1 ), assuming that c y ( 1 ) and c y ( 2 ) are known and are respectively, x 1 and x + 1 , be

> a d d ( φ ( 2 n + 1 ) 2 , n = 1 , , 49 )

which gives:

1003

First note that among these 1003 coefficients, there is 517 with μ ( n ) = 1 and all have for all value i, c o e ( n , i ) = m o b 1 ( n , i ) = m o b ( n , i ) .

We have 150 coefficients, which are μ ( n ) = 0 , and 141 of which have c o e ( n , i ) = m o b 1 ( n , i ) = m o b ( n , i ) , 6 with c o e ( n , i ) = m o b 1 ( n , i ) m o b ( n , i ) , and which are (45, 6), (63, 15), (75, 10), (99, 6), (99, 15) and (99, 24); 2 with the opposite, ie with c o e ( n , i ) being m o b ( n , i ) and not m o b 1 ( n , i ) and which are (99, 9) and (99, 18); and finally only one of the 150 that is (63, 6) and has a zero coefficient that is neither m o b ( 63 , 6 ) nor m o b 1 ( 63 , 6 ) . (This is the seventh for which c o e ( n ; i ) m o b ( n , i ) ).

3. Formula for the Coefficients

First, remember the following properties: [7]

1) c y ( n ) is always irreducible on .

2) on two cyclotomic polynomials are prime between them. In this article, we will try to solve the riddle of the cyclotomic coefficients, knowing that we have the following remarks and comments:

a) If n is prime then the nth cyclotomic polynomial is

c y ( n ) = x n 1 + + x + 1 . (6)

b) If p is prime and does not divide n, then

c y ( p n ) = c y c ( n , x p ) c y ( n ) . (7)

c) If n is odd then

c y ( 2 n ) = c y c ( n , x ) . (8)

d) If p is prime and does not divide m then

c y ( m p k ) = c y c ( m p , x p k 1 ) . (9)

e) If p is prime and divide n, then

c y ( p n ) = c y c ( n , x p ) . (10)

f) We always have:

c y ( n ) = c y c ( p s f c ( n ) , x n / p s f c ( n ) ) [2] (11)

g) The coefficients of c y ( n ) have a symmetry around the monomial x φ ( n ) 2 , i.e. the coefficient is the same in x i and in x φ ( n ) i

To see the difference between the formulas of (2) and (5) when p is prime and divide or not divide n we have as an example for c y ( p n ) :

6 = 2 × 3 with p = 2 not dividing n = 3 , then according to the formula (2), c y ( 6 ) will be c y c ( 2, x 3 ) c y ( 2 ) , that is x 3 + 1 x + 1 which is equal to x 2 x + 1 which is none other than c y ( 6 ) .

Whereas 3 divides 27, so c y ( 3 × 27 ) = c y ( 81 ) , is x 54 + x 27 + 1 = c y c ( 27 , x 3 ) as wants the formula 5.

Example 3.1. c y ( 2 3 × 3 2 × 4 ) = c y ( 288 ) and it’s c y c ( 24, x 288 24 ) with 24

being the part without square factor of 288 since c is 2 × 3 × 4 : with maple:

> c y (288)

x 96 x 48 + 1

> c y c ( 24, x 288 24 )

x 96 x 48 + 1

For symmetry, we have for example:

Example 3.2. > c y (105)

x 48 + x 47 + x 46 x 43 x 42 2 x 41 x 40 x 39 + x 36 + x 35 + x 34 + x 33 + x 32 + x 31 x 28 x 26 x 24 x 22 x 20 + x 17 + x 16 + x 15 + x 14 + x 13 + x 12 x 9 x 8 2 x 7 x 6 x 5 + x 2 + x + 1

We have a symmetry around x 24 , since μ ( 105 ) = 48 .

−2 is for example coefficient of x 7 and of x 48 7 = x 41 .

Proposition 3.3. For all n 1 , the coefficient of c y ( n ) in x is μ ( n ) . We’ll just make this proposal using a maple script for n up to 1000. For us it would have been enough to check it up to 100

> for n to 1000 if ( n , 1 ) m o b i u s ( n ) then print (n) end if od

1

We obtain that c o e ( n , i ) μ ( n ) is only for n = 1 .

Remark 3.4. For these c o e ( n ,1 ) , the following formula is therefore satisfied since g c d ( n ,1 ) = 1 and therefore m o b ( n , 1 ) = μ ( n ) = c o e ( n , 1 ) as the famous following formula generalizes this rule:

Remark 3.5. If n 100 and if μ ( n ) = 1 , then n = p q , with p < q prime and distinct.

Recall that m o d ( i , p ) , denotes the class of i modulo p.

If ( n , i ) denotes the pair (index n of a cyclotomic, degree i of a monomial), then

Lemme 3.6. For 14 pairs ( n , i ) for which μ ( n ) = 1 , m o d ( i , p ) 1 and g c d ( n , i ) = 1 ; for 78 with μ ( n ) = 1 , m o d ( i , p ) 1 and g c d ( n , i ) 1 ; when μ ( n ) = 1 and m o d ( i , p ) = 1 except for 4 pairs and when μ ( n ) = 0 except for 7 pairs ( n , i ) ; the coefficients ( c o e ( n , i ) ) when n is odd and i φ ( n ) 2 , of the first 100 cyclotomic polynomials satisfy the following formula:

c o e ( n , i ) = m o b ( n , i ) = m u ( n g c d ( n , i ) ) (12)

The 14 pairs are (see script 2):

(35, 8) (55, 12) (55, 17) (65, 14) (65, 19) (65, 24) (77, 12) (77, 19) (77, 23) (77, 26) (77, 30) (85, 18) (85, 23) (85, 28).

Lemme 3.7. For the following 19 ( n , i ) (4, 7 and 8) the coefficient is 0:

(55, 11) (55, 16) (77, 22) (77, 29)

(45, 6), (63, 6), (63, 15), (75, 10), (99, 6), (99, 15), (99, 24)

(91, 14), (91, 21), (91, 28), (91, 35), (95, 20),(95, 25), (95, 30) and (95, 35).

Lemme 3.8. For the following 13, the coefficient is 1 and are the only ones with non-zero coefficients distinct from m o b ( n , i ) :

(35, 12) (65, 18) (65, 23) (77, 18) (77, 25) (85, 22)

(85, 27) (85, 32) (91, 20) (91, 33) (95, 24)

(95, 29) and (95, 34).

Theoreme 3.9. For n less than or equal to 100, if μ ( n ) = 1 , m o d ( i , p ) 1 , g c d ( n , i ) = 1 and if ( n , i ) is not among the 27 previous ones ( 27 = 13 + 14 ), Then c o e ( n , i ) = 0 .

If ( n , i ) is not among the 32 = 19 + 13 and if one of the conditions above is not verified, That is, when μ ( n ) 1 , m o d ( i , p ) = 1 or g c d ( n , i ) 1 , then:

c o e ( n , i ) = m o b ( n , i ) = μ ( n g c d ( n , i ) )

This is the formula (12) above.

Example 3.10. c o e ( 39,11 ) = 0 because it is not among the 27, and since 39 = 3 × 13 so p = 3 and m o d ( 11,3 ) = 2 and is not 1.

On the other hand:

Example 3.11. c o e ( 39,10 ) = m o b ( 39,10 ) = 1 , we have equality because m o d ( 10,3 ) = 1 .

Example 3.12. (39, 6) also checks the formula because although m o b i u s ( 39 ) = 1 , m o d ( 6,3 ) = 0 1 but g c d ( 39,6 ) 1 (39 and 6 are not prime between them.), indeed: c o e ( 39,6 ) = m o b ( 39,6 ) = 1 .

Note that we have 0 = c o e ( n , i ) = m o b ( n , i ) in 118 case, c o e ( n , i ) is zero without m o b ( n , i ) in 152 and we never have the opposite. Verification scripts will not be prepared for this, but they are similar to those that will be established. Theoreme 3.13. If φ ( n ) is not multiple of 4, then except for n = i = 1 , if i φ ( n ) then c o e ( n , i ) = m o b ( n , i ) , for n 1000 . There are 16 to 100 and 98 until 1000.

Let’s check with the following maple script and its counter k which will count the number of ( n , i ) that do not check the equality and that will give 1 at the end of the process.

> k : = 0 : for n to 1000 do for i to p h i ( n ) do if g c d ( p h i ( n ) ,4 ) 4 then if c o e ( n , i ) m o b ( n , i ) then k : = k + 1 , print ( n , i ) fi fi od od; print (k)

1, 1

1

This script gives 3 times the value 1: for the index n = 1 of the only cyclotomic and for the degree i = 1 of the single dgre of x to which the quoted formula (In fact it is the formula (12)) is not verified when φ ( n ) is not divisible by 4.It also gives the value of the counter k of all the pairs ( n , i ) that do not satisfy the formula which is of course k = 1. All that because it was asked to returner ( n , i ) by print ( n , i ) and return k by print (k).

Example 3.14. c y ( 22 ) has all its coefficients that check the formula because φ ( 22 ) = 10 which is not multiple of 4.

> k : = 0 ; for i to φ ( 22 ) do if c o e ( 22, i ) m o b ( 22, i ) then k : = k + 1 end if end do; print (k)

0

Corollaire 3.15. If φ ( n ) is not multiple of 4, then except for n = i = 1 , if i φ ( 2 n ) then c o e ( 2 n , i ) = m o b ( 2 n , i ) , and this for n ≤ 1000

proof. If n is odd, φ ( 2 n ) = φ ( n ) , so φ ( 2 n ) is not multiple of 4 and we have the formula for 2 n .

If n is even, n 2 cannot be, except for n = 4 , because then n would be multiple of 4 and φ ( n ) also, for n = 4 , we have 2 n = 8 and the formula is checked for all the coefficients of c y ( 8 ) . since n is even, then

c o e ( 2 n , i ) = c o e ( n , 2 i ) = c o e ( n 2 , 4 i ) = m o b ( n 2 , 4 i ) = m o b ( n , 2 i ) = c o e ( n , 2 i ) because φ ( n ) is not multiple of 4, or c o e ( n ,2 i ) = c o e ( 2 n , i ) because n is even. +

As for theorem, 3.13 we will set 9 numbered Maple scripts, to check all that precedes and to see what are the 4 (script1), 14 (script2) and 7 (script5) of the theorem. But first a script just for the 165 (script9) number of pairs that are exceptions to the formula among which the 4, the 7 and 154 (script8) others with μ ( n ) = 1 and m o d ( i , p ) 1 , for which we are going anyway, establish a script to describe 13 pairs (script7) exceptions of this exception with c o e ( n , i ) = 1 instead of 0 for all other exceptions.

A script3 to verify that we have 78 pairs ( n , i ) with μ ( n ) = 1 , m o d ( i , p ) 1 and c o e ( n , i ) = m o b ( n , i ) ); a script4 for the 8 which under the same conditions of the 78 but with c o e ( n , i ) m o b ( n , i ) and a script6 to see if μ ( n ) = 1 , we always have c o e ( n , i ) = m o b ( n , i ) .

A hashtag (#) will be followed by a comment of the script, to explain it.

SCRIPT 1

> k : = 1 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do for p to 50 do for q to 50 do if isprime(p) = true then if isprime(q) = true then if p < q then if n = p q then if m o d ( i , p ) = 1 then if c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) m o b i u s ( n / g c d ( n , i ) ) then k : = k + 1 , print(n, i, c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) , m o b i u s ( n / g c d ( n , i ) ) , k) end if end if end if end if end if end if end do end do end do end do # This script will give the 4 exceptions when μ ( n ) = 1 and m o d ( i , p ) = 1

#The four exceptions are of 0 coefficient and will be among the 21 of the following theorem.

55, 11, 0, 1, 1

55, 16, 0, −1, 2

77, 22, 0, 1, 3

77, 29, 0, −1, 4

The 14 pairs for which the formula is good when g c d ( n , i ) = 1 , despite that m o d ( i , p ) 1 are given by:

SCRIPT 2

> k : = 1 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do for p to 50 do for q to 50 do if isprime(p) = true then if isprime(q) = true then if p < q then if n = p q then if m o d ( i , p ) = 1 then if c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) = m o b i u s ( n / g c d ( n , i ) ) then if g c d ( n , i ) = 1 then k : = k + 1 , print(n, i, k, c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) , m o b i u s ( n / g c d ( n , i ) ) ) end if end if end if end if end if end if end if end do end do end do end do

35, 8, 1

55, 12, 2

55, 17, 3

65, 14, 4

65, 19, 5

65, 24, 6

77, 12, 7

77, 19, 8

77, 23, 9

77, 26, 10

77, 30, 11

85, 18, 12

85, 23, 13

85, 28, 14

The 78 couples for which the formula is good when m o d ( i , p ) 1 and when g c d ( n , i ) 1 are given by:

SCRIPT 3

> k : = 1 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do for p to 50 do for q to 50 do if isprime(p) = true then if isprime(q) = true then if p < q then if n = p q then if m o d ( i , p ) = 1 then if c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) = m o b i u s ( n / g c d ( n , i ) ) then if g c d ( n , i ) 1 then k : = k + 1 , print(k) end if end if end if end if end if end if end if end do end do end do end do # The number is 78 when g c d ( n , i ) 1

78

Remark 3.16. Note that there is 8, under the same conditions that do not check the formula and which will be among the 19 of the theorem, indeed we have the following script.

SCRIPT 4

> k : = 1 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do for p to 50 do for q to 50 do if isprime(p) = true then if isprime(q) = true then if p < q then if n = p q then if m o d ( i , p ) 1 then if c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) m o b i u s ( n / g c d ( n , i ) ) then if g c d ( n , i ) 1 then k : = k + 1 , print(n, i, c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) , m o b i u s ( n g c d ( n , i ) ) , k) end if end if end if end if end if end if end if end do end do end do end do # The number is 78 when g c d ( n , i ) 1 # For the 8, the coefficient is 0 and will be counted among the 21 of the following theorem.

91, 14, 0, 1, 1

91, 21, 0, 1, 2

91, 28, 0, 1, 3

91, 35, 0, 1, 4

95, 20, 0, 1, 5

95, 25, 0, 1, 6

95, 30, 0, 1, 7

95, 35, 0, 1, 8

For the case μ ( n ) = 0:

SCRIPT 5

> k : = 1 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do if g c d ( n ,2 ) = 1 then if m o b i u s ( n ) = 0 then if g c d ( n , i ) 1 then if c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) m o b i u s ( n / g c d ( n , i ) ) then k : = k + 1 , print(n, i, c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) , m o b i u s ( n / g c d ( n , i ) ) , k) end if end if end if end if end do end do # The exceptions are 7, all of them are 0 and among the 21 of the theorem.

45, 6, 0, −1, 1

63, 6, 0, −1, 2

63, 15, 0, −1, 3

75, 10, 0, −1, 4

99, 6, 0, −1, 5

99, 15, 0, −1, 6

99, 24, 0, −1, 7

On the other hand for μ ( n ) = 1 , there is no exception:

SCRIPT 6

> k : = 0 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do if g c d ( n ,2 ) = 1 then if m o b i u s ( n ) = 1 then if g c d ( n , i ) 1 then if c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) m o b i u s ( n / g c d ( n , i ) ) then k : = k + 1 , print(n, i, c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) , m o b i u s ( n / g c d ( n , i ) ) , k) end if end if end if end if end do end do;print(k) # since there is no exception, you have to ask k after the script and start it at 0

0

And for the 13 who are with coefficient 1 distinct from m o b ( n , i ) when μ ( n ) = 1 and m o d ( i , p ) 1 :

SCRIPT 7

> k : = 1 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do if g c d ( n ,2 ) = 1 then if m o b i u s ( n ) = 1 then if g c d ( n , i ) = 1 then if 1 = c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) and c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) m o b i u s ( n / g c d ( n , i ) ) then k : = k + 1 , print(n, i, c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) , m o b i u s ( n / g c d ( n , i ) ) , k) end if end if end if end if end do end do

35, 12, 1, −1, 1

65, 18, 1, −1, 2

65, 23, 1, −1, 3

77, 18, 1, −1, 4

77, 25, 1, −1, 5

85, 22, 1, −1, 6

85, 27, 1, −1, 7

85, 32, 1, −1, 8

91, 20, 1, −1, 9

91, 33, 1, −1, 10

95, 24, 1, −1, 11

95, 29, 1, −1, 12

95, 34, 1, −1, 13

The total number of exceptions when μ ( n ) = 1 and m o d ( i , p ) 1 is:

SCRIPT 8

> k : = 1 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do for p to 50 do for q to 50 do if isprime(p) = true then if isprime(q) = true then if p < q then if n = p q then if m o d ( i , p ) 1 then if c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) m o b i u s ( n / g c d ( n , i ) ) then k : = k + 1 , print(k) end if end if end if end if end if end if end do end do end do end do

154

Let’s recap a bit: The number of pairs that do not satisfy the formula c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) = μ ( n g c d ( n , i ) ) , is 154 + 7 + 4 = 165

Let’s check this number:

SCRIPT 9

> k : = 1 ; for n to 100 do for i to ( 1 / 2 ) p h i ( n ) do if g c d ( n ,2 ) = 1 then if c o e f f ( c y c l o t o m i c ( n , x ) , x , i ) m o b i u s ( n / g c d ( n , i ) ) then k : = k + 1 , print(k) end if end if end do end do

165

!! It’s won!!

4. Euler Indicator Properties

[7]

1) For n 1 and n 2 , φ ( n ) is always even.

2) If m is odd then φ ( 2 m ) = φ ( m ) (13)

3) If k 0 , φ ( 2 k ) = 2 k 1 (14)

4) If m and n are prime between them, then φ ( m n ) = φ ( m ) φ ( n ) (15)

5) If p is prime, then φ ( p ) = p 1 (16)

6) In general, for k 0 , φ ( i n ) = i n k φ ( i k ) (and by the way, we’ll see that c y ( i n ) = c y c ( i k , x i n k ) (17).

7) We can also define the inverse of φ , which is the function i n v p h i ( n ) , which gives the set of values for which φ is worth n. It can be empty, in which case there would be no cyclotomic of degree n, φ 1 ( n ) can in return contain several values that maple gives in the form of an ordered sequence, for example φ 1 ( 2 ) = [ 3 , 4 , 6 ] .

5. Other Properties of Cyclotomic Coefficients

1) Up to n = 104 , the coefficients of c y ( n ) are always −1, 0 or 1, and it is only from 105 that the first coefficient appears-2 [7] (see [7] ). with maple we will also check.

2) Up to 384, a coefficient of c y ( n ) is never an absolute value strictly greater than 2, with maple, we can see that, as well as the following properties.

3) For n < 1365 , the absolute value of a coefficient of c y ( n ) is a maximum of 3.

4) Before 1785, we can not find a coefficient of c y ( n ) with an absolute value strictly greater than 4.

5) If n < 2805 , then | c o e f f s ( c y ( n ) ) | 5 .

6) All absolute values of all coefficients of c y ( n ) , with ( n 3134 ), are less than or equal to 6.

7) Note that there is an increasing dependence of the maximum values of the absolute values of the coefficients of a cyclotomic, that the limit values are all of a unit number 5.

And with maple 12 we get:(the hashtag # is followed by a comment)

>with (numtheory) # (Package to download)

> c o e f f s ( c y c l o t o m i c ( 5, x ) ) # It will give the sequence of coefficients with repetition:

1, 1, 1, 1, 1

> { c o e f f s ( c y c l o t o m i c ( 5, x ) ) } # it will give the set of coefficients, here reduced to a single element without repetition.

{ 1 }

> E : = { 1 } ; for k to 104 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # we only have −1 and 1

{ 1,1 }

> E : = { 1 } ; for k to 105 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E). # We have −2 more, hence the absolute value 2 more

{ 2, 1,1 }

> E : = { 1 } ; for k to 384 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # (2 extra)

{ 2, 1,1,2 }

> E : = { 1 } ; for k to 385 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # the absolute value 3]

{ 3, 2, 1,1,2 }

> E : = { 1 } ; for k to 1364 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # (not new)

{ 3, 2, 1,1,2 }

> E : = { 1 } ; for k to 1365 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # (−4 and 3 more and the absolute value 4)

{ 4, 3, 2, 1,1,2,3 }

> E : = { 1 } ; for k to 1785 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E)

> E : = { 1 } ; for k to 1785 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # (4 and 5 more and the 5 absolute value)

{ 4, 3, 2, 1,1,2,3,4,5 }

> E : = { 1 } ; for k to 2804 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # (the −5 extra)

{ 5, 4, 3, 2, 1,1,2,3,4,5 }

> E : = { 1 } ; for k to 2805 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # (−6 and 6 more and the absolute value 6);

{ 6, 5, 4, 3, 2, 1,1,2,3,4,5,6 }

> E : = { 1 } ; for k to 3134 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # (Always the same set, the 7 absolute value will only appear in the 3135 index)

{ 6, 5, 4, 3, 2, 1,1,2,3,4,5,6 }

> E : = { 1 } ; for k to 3135 do E : = u n i o n ( E , { c o e f f s ( c y c l o t o m i c ( k , x ) ) } ) end do; print(E) # (we get −7 and 7 more)

{ 7, 6, 5, 4, 3, 2, 1,1,2,3,4,5,6,7 }

8) By factoring these limit values, for absolute values using maple, we will see that they are all without square factor, ie they are of non-zero mobius, and that their indicators of Euler do not have a separate divisor of 2, 3 or 5.

9) The numbers 105, 385, 1365, 1785, 2805 and 3135 are multiples of 5 by numbers that are not multiples, and 5 being prime, we can apply to the c y ( n ) for these values of n, the property Φ p n = Φ n ( x p ) Φ n ( x ) . The Euclidean divisions will give coefficients for these cyclotomics, sometimes with absolute values greater than 1. ( Φ n ( x ) = c y (n))

10) For all n , c y ( n ) has all its coefficients in and it is irreducible on , so on (see [5] ). And on a nonzero characteristic field, if c y ( n ) is irreducible, then c y ( d ) is for all d divisor of n (see [4] ). We also have that for all m , there exists n such that m or -m is coefficient of c y ( n ) (see [8] ), for all n > 1 there is a symmetry of the coefficients of c y ( n ) around φ ( n ) / 2 see [2] , and if n is prime, then c y ( n ) is x n 1 + x n 2 + + 1 (see Example 5.1); that if p is prime and does not divide n then c y ( p n ) = c y c ( n , x p ) c y ( n ) (see Example 5.2)

If n is odd, c y ( 2 n ) = c y c ( n , x ) (see Example 5.3); If p is prime and does not divide m, then c y ( m p k ) = c y c ( m p , x p k 1 ) (see Example 5.4 example 4). But if p is prime and divide n, we have c y ( n p ) = c y c ( n , x p ) (see Example 5.5).

Finally, if m is the no-factor part of n (the product of prime factors that divide n), then c y ( n ) = c y c ( m , x n / m ) . (see Example 5.6)

And as examples illustrating these properties we have with maple:

Example 5.1. with n = 7

> c y c l o t o m i c ( 7, x ) ;

x 6 + x 5 + x 4 + x 3 + x 2 + x + 1

Example 5.2. with p = 2 and n = 3 .

> c y c l o t o m i c ( 6, x ) , simplify ( c y c l o t o m i c ( 2, x 3 ) c y c l o t o m i c ( 2, x ) );

x 2 x + 1 , x 2 x + 1

Example 5.3. with n = 7

> c y c l o t o m i c ( 7, x ) , c y c l o t o m i c ( 14, x )

x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 , x 6 x 5 + x 4 x 3 + x 2 x + 1

Example 5.4. with p = 2 , k = 2 and m = 7 .

> c y c l o t o m i c ( 28, x ) , c y c l o t o m i c ( 14, x 2 )

x 12 x 10 + x 8 x 6 + x 4 x 2 + 1 , x 12 x 10 + x 8 x 6 + x 4 x 2 + 1

For the examples 5 and 6, one recalls the definition of the function c y c :

> c y c ( a , b ) : = c y c l o t o m i c ( a , b )

> c y c : = ( a , b ) > n u m t h e o r y : c y c l o t o m i c ( a , b )

Example 5.5. with p = 3 and n = 27

> c y c ( 81, x ) , c y c ( 27, x 3 )

x 54 + x 27 + 1 , x 54 + x 27 + 1

Example 5.6. with n = 2 3 × 3 2 × 4 and the part without a square factor of n is m = 2 × 3 × 4

> c y ( 2 3 × 3 2 × 4 ) , c y c ( 2 × 3 × 4 , x 2 3 × 3 2 × 4 / 2 × 3 × 4 )

x 96 x 48 + 1 , x 96 x 48 + 1

6. Prime Indices and Determination of a Cyclotomic with All Its Coefficients

Again and again cyclotomics. This time for the direct calculation of cyclotomics. For that, let’s remember that we will adopt the notations in maple 12 that follow, after loading the package “with (numtheory)” (mul is the product):

c y : = n > c y c l o t o m i c ( n , x ) ; c y c : = ( n , x ) > c y c l o t o m i c ( n , x )

f p s f c : = ( n , i ) > p i e c e w i s e ( g c d ( n , i ) = i and n o p s ( d i v i s o r s ( i ) = 2 , i , 1 ) ) .

p s f c ( n ) : = m u l ( f p s f c ( n , i ) , i in d i v i s o r s ( n ) ) .

r p s f c ( n ) : = n p s f c (n)

The piecewise function is a part-by-part function defined with maple, with one condition and one value if the condition is true and another value otherwise. For the summary calculation of cyclotomics we will apply the 7 properties of paragraph 3:

Thus the formal calculation of all cyclotomics is reduced to the determination of the cyclotomics with prime indices. So:

If p is prime then the index cyclotomic p is s u m ( x i , i = 0 , , p 1 ) .

The first need of a cyclotomic of index a prime number p, to calculate another is to calculate its square.

The second need is to calculate the one of index its product by the first number which follows it, if one does not want to use that of index that which follows it, and if one wants always to use the smallest possible ones.

For example in the following scripts, we will use c y ( 5 ) only until c y ( 25 ) = c y ( 5 2 ) , then for c y ( 35 ) = c y ( 5 × 7 ) , knowing that 5 is the prime number that precedes 7.

If we wanted to go further, we would have needed the index 11, that when we arrived at 112, i.e. 121, then for 11 × 13 = 143 . So we will only use 2th and 3‘em cyclotomic up to c y ( 24 ) .

-we will only use the 2th, 3th and 5th cyclotomics up to c y ( 48 ) .

we will only need 2nd, 3th, 5th and 7th for all our first 100 cyclotomics, and we could have advanced up to to 120, since the next prime number 7 is 11, and since ( 11 ) 2 = 121 .

So let’s go for some examples:

> c y ( 4 ) , c y c ( 2, x 2 )

x 2 + 1 , x 2 + 1

> c y ( 6 ) , simplify ( c y c ( 2, x 3 ) / c y (2))

x 2 x + 1 , x 2 x + 1

> c y ( 8 ) , c y c ( 2, x 4 )

x 4 + 1 , x 4 + 1

> c y ( 9 ) , c y c ( 3, x 3 )

x 6 + x 3 + 1 , x 6 + x 3 + 1

> c y ( 10 ) , c y c ( 5, x ) ; simplify ( c y c ( 2, x 5 ) / c y (2))

x 4 x 3 + x 2 x + 1 , x 4 x 3 + x 2 x + 1

x 4 x 3 + x 2 x + 1

And with similar scripts we get:

c y ( 12 ) = c y c ( 6 , x 2 ) = s i m p l i f y ( c y c ( 2 , x 6 ) / c y c ( 2 , x 2 ) )

Let x 4 x 2 + 1, x 4 x 2 + 1 .

c y ( 24 ) , c y c ( 6 , x 4 ) = s i m p l i f y ( c y c ( 2 , x 12 ) / c y c ( 2 , x 4 ) ) = x 8 x 4 + 1 .

And from 5 2 = 25 , we will need c y (5)

c y ( 25 ) = c y c ( 5 , x 5 ) = x 20 + x 15 + x 10 + x 5 + 1 .

Then you will need c y ( 5 ) only for the product of 5 by the first that follows it i.e. 5 × 7 = 35 .

c y ( 35 ) = s i m p l i f y ( c y c ( 5, x 7 ) / c y ( 5 ) ) = x 24 x 23 + x 19 x 18 + x 17 x 16 + x 14 x 13 + x 12 x 11 + x 10 x 8 + x 7 x 6 + x 5 x + 1

Until cy (48) we have no problem:

c y ( 48 ) = s i m p l i f y ( c y c ( 16 , x 3 ) / c y ( 16 ) ) = s i m p l i f y ( c y c ( 2 , x 24 ) / c y c ( 2 , x 8 ) ) = x 16 x 8 + 1

From c y ( 49 ) we will need c y ( 7 ) :

c y ( 49 ) = c y c ( 7 , x 7 ) = x 42 + x 35 + x 28 + x 21 + x 14 + x 7 + 1

And that goes well up to c y ( 100 ) without difficulty.

Before starting the calculation of the coefficients, let us first note that for a cyclotomic of index n which is of degree φ ( n ) and which denotes the number of prime numbers with n strictly inferior to n, the coefficients are drawn by symmetry with respect to φ ( n ) / 2 (see [3] ). For example:

The coefficient of c y ( 93 ) in 47 is, the one in 13 since φ ( 93 ) = 60 , the half is 30 of which 47 and 13 are for same distance. And it’s −1. Indeed:

> s o r t ( c y (93))

x 60 x 59 + x 57 x 56 + x 54 x 53 + x 51 x 50 + x 48 x 47 + x 45 x 44 + x 42 x 41 + x 39 x 38 + x 36 x 35 + x 33 x 32 + x 30 x 28 + x 27 x 25 + x 24 x 22 + x 21 x 19 + x 18 x 16 + x 15 x 13 + x 12 x 10 + x 9 x 7 + x 6 x 4 + x 3 x + 1

Whereas for cy(105) (resp. cy(385)), the first product of three distinct prime numbers two to two, we find the first coefficients of absolute value strictly greater than 1, in degrees 7 and 41, symmetrically compared to 48 = φ ( 105 ) (resp.strictly greater than 2, in 119, 120 and 121, which is φ ( 385 ) 1 , φ ( 385 ) and φ ( 385 ) + 1 ).

> c o e ( 105,7 ) , c o e ( 105,41 ) , c o e ( 385,119 ) , c o e ( 385,121 )

−2, −2, −3, −3

7. Examples

We will give two examples of cyclotomics with indices greater than 100 to determine and to determine their coefficients, to see how we reduce ourselves to a cyclotomic index less than 100. It will be cy(225) and cy(120).

For cy(225), we have φ ( 225 ) = 120 and c y ( 225 ) = c y c ( 15 , x 15 ) , based on the properties of the cyclotomics in the paragraph 3. 225) has zero coefficients in x i if i is not multiple of 15. Its coefficients in 0, 15, 30, 45, 60, 75, 90, 105 and 120 are those of cy(15) in 0, 1, 2, 3, 4, 5, 6, 7 and 8. If we call the ( a i ) the coefficients of cy(15) and ( b i ) those of cy(225) then:

b 15 i = a i .

We know that a 0 = b 0 = 1 . b 15 = a 1 = μ ( 15 ) = 1

Since φ ( 15 ) = 8 and φ ( 225 ) = 120 , then we have the following equalities:

b 30 = b 90 = a 6 = a 2 , b 45 = b 75 = a 5 = a 3 and b 60 = a 4 .

Applying our formulas to c y ( 15 ) , we find

c y ( 15 ) = 1 x + x 3 x 4 + x 5 x 7 + x 8

and so c y ( 225 ) = 1 x 15 + x 45 x 60 + x 75 x 105 + x 120

All this while noting that a 3 is not an exception since g c d ( 15,3 ) = 3 1 , a 4 not because g c d ( φ ( φ ( 15 ) ) , φ ( 4 ) ) = g c d ( 4,2 ) = 2 1 , so the coefficients y are respectively μ ( 15 g c d ( 15,3 ) ) and μ ( 15 g c d ( 15,4 ) ) , which is 1 and −1.

However, for a 2 which is part of the 53, the coefficient is 0 because μ ( 15 ) = 1 , g c d ( 15,2 ) = 1 , m o b ( 15,2 ) = 1 and g c d ( φ ( φ ( 15 ) ) , φ ( 2 ) ) = 1 , so there are exceptions, and since g c d ( φ ( 15 ) ,2 ) = 2 , so is one of 53 and a 2 = 0 . By symmetry a 6 is zero too.

We then deduce from ( a i ) the b 15 i and hence c y ( 225 ) .

With the Euclidean division and expressing it with the help of cyclotomic indices, we have: c y ( 225 ) = c y c ( 15 , x 15 ) = c y c ( 3 , x 75 ) c y c ( 3 , x 15 ) , indeed with maple 12, the following script shows this equality:

> s i m p l i f y ( c y ( 225 ) c y c ( 3 , x 75 ) / c y c ( 3 , x 15 ) )

0

We know that:

c y c ( 3 , x 75 ) c y c ( 3 , x 15 ) = x 150 + x 75 + 1 x 30 + x 15 + 1 = x 120 x 105 + x 75 x 60 + x 45 x 15 + 1

So, we find our c y ( 225 ) .

Now for c y ( 120 ) = c y ( 2 3 × 15 ) = c y c ( 2 2 × 15 , x 2 ) = c y c ( 2 × 15 , x 4 ) = c y c ( 15 , x 4 ) , and this by applying the paragraph 7 formulas on the properties of cyclotomics. Now, according to the previous example, c y ( 15 ) = x 8 x 7 + x 5 x 4 + x 3 x + 1 , thus keeping for the pair powers their signs and by inverting those odd powers and multiplying them by 4 we get c y ( 120 ) = 1 + x 4 x 12 x 16 x 20 + x 28 + x 32 .

By the way c y ( 120 ) = c y c ( 60 , x 2 ) because 2 divides 60, and like 2 divides 30 so this is c y c ( 30, x 4 ) , but 2 does not divide 15, then c y c ( 30 , x 4 ) = c y c ( 15 , x 4 ) . or 15 = 3 × 5 and 3 does not divide 5, hence c y ( 15 ) = c y c ( 3 , x 5 ) c y ( 3 ) and c y ( 120 ) = c y c ( 15 , x 4 ) = c y c ( 3 , x 20 ) c y c ( 3 , x 4 ) , that is x 40 x 20 + 1 x 8 + x 4 + 1 which is by Euclidean division 1 + x 4 x 12 x 16 x 20 + x 28 + x 32 which is none other than c y ( 120 ) .

8. Conclusion

We hope to have raised some riddles of cyclotomic polynomials and their coefficients, and the enigma that has pained many mathematicians and researchers, this by the formula F12 and by means of prime numbers as in the examples of paragraph 6. Maple, Euler and Mobius helped us a lot. It’s not rocket science. We will advance in future articles.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Squalli, J. (2019) Formulas for Coefficients of Hundred Cyclotomics and Numbers Battle. American Journal of Computational Mathematics, 9, 97-115. doi: 10.4236/ajcm.2019.92008.

References

[1] Histoire des polynomes. https://fr.wikipedia.org/wiki/Polynome
[2] Polynome Cyclotomique. https://fr.wikipedia.org/wiki/Polyn
[3] Lang, S. (2002) Algebra. In Graduate Texts in Mathematics, Series Vol. 211, Springer-Verlag, New-York.
https://doi.org/10.1007/978-1-4613-0041-0
[4] Ferrand, D. Sur l’irréductibilité des polynomes cyclotomiques.
https://webusers.imj-prg.fr/~daniel.ferrand/Cyclotomiques.pdf
[5] L’incroyable histoire des polynomes cyclotomiques (niveau 3th année de licence) sur le site.
http://tanopah.jo.free.fr/epilogues/cyclo.pdf
[6] http://igor-kortchemski.perso.math.cnrs.fr/olympiades/interventions/exoscyclo.pdf
[7] http://www.klubprepa.fr/Site/Document/ChargementExtrait.aspx?IdDocument=5331
[8] Erdos, P.P. and Vaughan, R.C. Bounds for the R-th Coefficients of Cyclomotomic Polynomials.
https://users.renyi.hu/~p_erdos/1974-03.pdf

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.