Cyclotomic polynomial

In algebra cyclotomic polynomials are used to investigate subdivisions of the unit circle into equal parts. Under the -th cyclotomic polynomial is understood that of integer polynomial with leading coefficient 1 greatest degree that divides, but to all with is prime. Its zeros on are exactly the primitive roots of unity, to the prime numbers by running between and.

The term " cyclotomic " comes from the geometric problem of cyclotomic, ie the construction of a regular polygon under restriction to the Euclidean tools ruler and compass. For which corner this is successful, can be found in the article konstruierbares polygon.

Properties

The decomposition of the -th Kreisteilungspolynoms into linear factors gives

Therefore, the degree of the same, the number of prime numbers is discussed below. The resulting defined function has as Euler's phi function in number theory is of considerable importance.

Conversely, the product representation

The -th cyclotomic polynomial has integer coefficients, that is. It is there and in an irreducible polynomial, hence minimal polynomial of any primitive th root of unity. Thus, the residue class ring is even a body, namely the smallest, which is the unit circle in the complex plane can be divided into equal parts so that all subdivision points belong to the body. He is therefore called cyclotomic fields.

Generalization

The concept of Kreisteilungspolynoms can be generalized to the roots of unity over an arbitrary field. In this way, in particular, all finite fields arise as a cyclotomic field over its prime field.

The coefficient problem

The first cyclotomic polynomials are:

This follows from the product representation ( see above):

That is, The result is a polynomial of degree n -1, which contains all the exponent of X in the descending order until 0. If n is a composite number, then the polynomial can be decomposed into further. If n is a prime number, so the polynomial is irreducible, and - but not necessarily over and never over, because after the Gaussian fundamental theorem of algebra can be any polynomial decomposed into linear and quadratic terms, eg

Even disassembled into:

N is an odd prime simple, there is a sum plus a loud members comprising all powers of n-1 down to 0. If n is twice an odd prime number (ie, n = 2p), so contains the same powers, but as an alternating sum; cf or or above. So you can literally divide the cyclotomic polynomials in an even and an odd group, which differ only by the sign.

If n is a prime power, so pm with p as a prime, then applies

So:

If n is the product of two odd primes, then step on the first irregularities. Seemingly arbitrary missing powers in the polynomial, ie have coefficient 0, where even large gaps are possible as in ( see below), a polynomial of degree 72 with only 23 summands. But if you look closer, then the sum is still a strictly alternating and absolutely symmetrical. So at just missing the third highest potency and also the third lowest. This symmetrical structure applies to all cyclotomic polynomials with n> 1 Polynomials with this kind of symmetry is called palindromic polynomials.

In the straight version, we have, however, a blockwise distribution of the sign, how they will meet us at higher levels:

The most important, however, is that up to this point only as coefficients -1, 0 and 1 have occurred. And the mathematicians, this seemed so self-evident that no one came up with the idea, it could also go very differently. And so it is hardly credible that in 1941 a discovery in the field of school mathematics could be made in such a fundamental area such as factoring sums. Anyway dismantled the Soviet mathematician Valentin Ivanov, the polynomial and awards include a polynomial of degree 48, which contained twice the coefficient -2 to everyone's surprise.

The discovery at this point was not a coincidence, because 105 is the smallest possible product of three distinct odd primes 3 * 5 * 7, and instead of the old, disproved conjecture he made a claim on:

At first exponent with only two different odd prime factors contains only the coefficients -1, 0 and 1.

2 In three different odd prime factors and the coefficient -2 occurs.

3 As of four different odd prime factors, the coefficients can take on any positive or negative value.

Even with falling back on the block-wise distribution of the sign: 3x plus 5x minus 6x plus, minus 5x, 6x plus, minus 5x, 3x Plus. The number of positive elements at the beginning and end seems to correspond to the smallest prime factor: with three, five, with just 7 positive limbs, etc. The straight version shows a small-scale distribution of the sign, which is in parts almost alternately:

It is not clear what exponent Ivanov has checked. And while still calculate in two to three hours by hand, the computational complexity grows rapidly at higher exponents; after all, in 1941 the computers were not yet invented, and it was war. And so his claims 1 and 3 are still valid today, while his second allegation denied equal to the next exponent. After presenting us equal ten times the coefficient of 2, but not once -2. And even has only the coefficients -1, 0 and 1 - as well as many after.

But in his 177 summands brings not only the expectable input block with 5 positive terms, but for the first time come together -2 and 2 in the polynomial on. And as the climax surprised us the centralized bloc with the three central links with coefficient -3.

If you now want to check Ivanov's third assertion and the polynomials want to look at exponents with four odd prime factors, then nothing happens at first New: welcomes us with a polynomial of degree 480, in which the coefficients -2, 2, -3, and 3 occur together. A closer inspection shows that these four coefficients together already occur in the polynomial. In literature, and particularly in the OEIS lists is generally no distinction made between minus and plus and only lists the amounts. In OEIS A013594 they are brought into connection with the exponent of its first occurrence. Here, the coefficient of the number of digits of the sequence, the actual exponent is the follower. At 2 and 3 you can see the already known 105 and 385, in fourth place in 1365 occurs on. Behind it lies a polynomial of degree 576, in the same -4 eight times ( and nicely balanced) occurs as a coefficient. That as the exponents and the coefficients grow with time, is a matter of logic; but the way is already surprising and frightening at the same time. A record is three or four times surpassed only by a few percent and remains in the same order to the next record by several orders of magnitude in the level too fast. In the A013594 sequence and in the expanded list of coefficients to 1000, the record exponents dozens or hundreds repeat times. The series with exponent 26565 is still continued to 59, but then jumps in the record suddenly to 359, and virtually all coefficients are represented in between. For, the smallest possible n with 6 different odd prime factors, is reached -532 ( at 92160.Grad ). The 1000 list ends at 585 with a long series of exponent 285285, and they would be extrapolated into the thousands, that would go on until the new record high 1182nd But then the list would be completely boring, because the exponent 327845, who also previously between appears, the record jumps to 31010th because of these block-like jumps also not an appropriate graphical representation is possible because persistent, the standards need to be changed. It would be desirable to check whether all the coefficients 1183-31010 occur in; it certainly can not be with, because the record coefficient is more than 14 million, and it is the first time that it exceeds the exponent n. OEIS A160340 calls the list of the first 42 record exponents, the corresponding list of coefficients is in on the last page. The search, which can only be accomplished with mainframe computers, but goes on, and holds the record for 15.Jan.2011 with a 88stelligen coefficients. Since such precise information is available, the polynomial must be known in its full length. Apparently polynomials are particularly record breaking, if the associated exponent have a factorization of the smallest prime numbers; the prime factor 5 occurs in all record holders. In prime factors in the thousands or millions, however, the highest occurring coefficient is 1 or 2 ...