Monic polynomial | EPFL Graph Search

In algebra, a monic polynomial is a non-zero univariate polynomial (that is, a polynomial in a single variable) in which the leading coefficient (the nonzero coefficient of highest degree) is equal to 1. That is to say, a monic polynomial is one that can be written as :x^n+c_{n-1}x^{n-1}+\cdots+c_2x^2+c_1x+c_0, with n \geq 0. Uses Monic polynomials are widely used in algebra and number theory, since they produce many simplifications and they avoid divisions and denominators. Here are some examples. Every polynomial is associated to a unique monic polynomial. In particular, the unique factorization property of polynomials can be stated as: Every polynomial can be uniquely factorized as the product of its leading coefficient and a product of monic irreducible polynomials. Vieta's formulas are simpler in the case of monic polynomials: The ith elementary symmetric function of the roots of a monic polynomial of degree n equals (-

Four-Variable Expanders Over The Prime Fields

Van Thang Pham, Adrian Claudiu Valculescu

Let F-p be a prime field of order p > 2, and let A be a set in F-p with very small size in terms of p. In this note, we show that the number of distinct cubic distances determined by points in A x A satisfies vertical bar(A - A)(3) + (A - A)(3 vertical bar) >> vertical bar A vertical bar(8/7), which improves a result due to Yazici, Murphy, Rudnev, and Shkredov. In addition, we investigate some new families of expanders in four and five variables. We also give an explicit exponent of a problem of Bukh and Tsimerman, namely, we prove that max {vertical bar A + A vertical bar, vertical bar f( A, A)vertical bar} >> vertical bar A vertical bar(6/5), where f(x, y) is a quadratic polynomial in F-p[x, y] that is not of the form g(alpha x + beta y) for some univariate polynomial g.

AMER MATHEMATICAL SOC2018

Deciding properties of number fields without factoring

Mohammad Amin Shokrollahi

The polynomial time algorithm of Lenstra, Lenstra, and Lovász [15] for factoring integer polynomials and variants thereof have been widely used to show that various computational problems in number theory have polynomial time solutions. Among them is the problem of factoring polynomials over algebraic number fields, which is used itself as a major subroutine for several other algorithms. Although a theoretical breakthrough, algorithms based on factorization of polynomials are notoriously slow and hard to implement, with running times ranging between

O(n^12)

and

O(n^18)

depending on which variant of the lattice basis reduction is used. Here, n is an upper bound for the maximum of the degrees and the bit-lengths of the coefficients of the polynomials involved. On the other hand, in many situations one does not need the full power of factorization, so one may ask whether there exist faster algorithms in these cases. In this paper we develop more efficient Monte Carlo algorithms to decide certain properties of roots of integer polynomials, without factoring them. Such problems arise, e.g., when solving systems of algebraic equations. Our methods applied to this situation give thus information about the solutions of such systems of equations. Assuming the validity of the Extended Riemann Hypothesis, our algorithms run in time

O(n^6+?)

in worst case, though they usually terminate much faster if the input polynomials do not have the properties the algorithm is testing. Besides this substantial improvement in the running time, our algorithms have the advantage of being conceptually easy. Their building blocks are gcd- computations in polynomial rings over finite fields, and primality tests for integers. However, despite the simplicity of our algorithms, their analysis is involved and uses tools from algebraic and analytic number theory. Our methods yield polynomial time algorithms even in cases where the factorization method does not. We exhibit such an example by showing that the language consisting of pairs

(g, m)

where

g

is a monic irreducible polynomial such that all its roots are integral linear combinations of mth roots of unity, is in co-RP. Currently, we do not know of any deterministic polynomial time algorithm to decide this problem, even if we assume the validity of the Extended Riemann Hypothesis. We will also show that computing the minimal m such that

(g, m)

belongs to this language is intractable by means of present methods: we prove that this problem is polynomial time equivalent to that of computing the largest square free divisor of an integer

1997

Deciding properties of number fields without factoring

Mohammad Amin Shokrollahi

O(n^12)

and

O(n^18)

O(n^6+?)

(g, m)

where

g

(g, m)

belongs to this language is intractable by means of present methods: we prove that this problem is polynomial time equivalent to that of computing the largest square free divisor of an integer

1997