检索结果-内蒙古大学图书馆

Counting decomposable multivariate polynomials

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 2011年第3期22卷 165-185页

作者： von zur Gathen, Joachim Univ Bonn B IT D-53113 Bonn Germany

A polynomial f (multivariate over a field) is decomposable if f = g. h with g univariate of degree at least 2. We determine the dimension (over an algebraically closed field) of the set of decomposables, and an approximation to their number over a finite field. The relative error in our approximations is exponentially decaying in the input size.

关键词： Computer algebra Polynomial decomposition Multivariate polynomials Finite fields combinatorics on polynomials

来源：评论

学校读者我要写书评

暂无评论

Counting reducible and singular bivariate polynomials

引用

FINITE FIELDS AND THEIR APPLICATIONS 2008年第4期14卷 944-978页

作者： von zur Gathen, Joachim Univ Bonn BIT D-53113 Bonn Germany

Among the bivariate polynomials over a finite field, most are irreducible. We count some classes of special polynomials, namely the reducible ones, those with a square factor, the "relatively irreducible" ones which are irreducible but factor over an extension field, and the singular ones, which have a root at which both partial derivatives vanish. (C) 2008 Published by Elsevier Inc.

关键词： Bivariate polynomial Finite fields combinatorics on polynomials Counting problems

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for decomposable univariate wild polynomials

引用

JOURNAL OF SYMBOLIC COMPUTATION 2013年 50卷 409-430页

作者： von zur Gathen, Joachim Univ Bonn B IT D-53113 Bonn Germany

A univariate polynomial f over a field is decomposable if it is the composition f = g o h of two polynomials g and h whose degree is at least 2. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood. The wild case, where p divides n, is more challenging. We present an efficient algorithm for this case that computes a decomposition, if one exists. It works for most but not all inputs, and provides a reasonable lower bound on the number of decomposable polynomials over a finite field. This is a central ingredient in finding a good approximation to this number. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Computer algebra Wild polynomial decomposition Finite fields combinatorics on polynomials

来源：评论

学校读者我要写书评

暂无评论

COUNTING REDUCIBLE, POWERFUL, AND RELATIVELY IRREDUCIBLE MULTIVARIATE polynomials OVER FINITE FIELDS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第2期27卷 855-891页

作者： Gathen, Joachim Von Zur Viola, Alfredo Ziegler, Konstantin Univ Bonn B IT D-53113 Bonn Germany Univ Republica Inst Computac Montevideo Uruguay

We present counting methods for some special classes of multivariate polynomials over a finite field, namely, the reducible ones, the s-powerful ones (divisible by the sth power of a nonconstant polynomial), and the relatively irreducible ones (irreducible but reducible over an extension field). One approach employs generating functions, and another one uses a combinatorial method. They yield exact formulas and approximations with relative errors that essentially decrease exponentially in the input size.

关键词： multivariate polynomials finite fields combinatorics on polynomials counting problems generating functions analytic combinatorics

来源：评论

学校读者我要写书评

暂无评论

Survey on Counting Special Types of polynomials

Survey on Counting Special Types of Polynomials

引用

Computer Algebra and polynomials: Applications of Algebra and Number Theory

作者： Gathen, Joachim von Zur Ziegler, Konstantin Univ Bonn B IT Bonn Germany

ISBN: (纸本)9783319150819;9783319150802

Most integers are composite and most univariate polynomials over a finite field are reducible. The Prime Number Theorem and a classical result of Gauss count the remaining ones, approximately and exactly. For polynomials in two or more variables, the situation changes dramatically. Most multivariate polynomials are irreducible. This survey presents counting results for some special classes of multivariate polynomials over a finite field, namely the reducible ones, the s-powerful ones ( divisible by the sth power of a nonconstant polynomial), the relatively irreducible ones ( irreducible but reducible over an extension field), the decomposable ones, and also for reducible space curves. These come as exact formulas and as approximations with relative errors that essentially decrease exponentially in the input size. Furthermore, a univariate polynomial f is decomposable if f = g circle h for some nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials. The tame case, where the characteristic p of F-q does not divide n = deg f, is fairly well-understood, and we obtain closely matching upper and lower bounds on the number of decomposable polynomials. In the wild case, where p does divide n, the bounds are less satisfactory, in particular when p is the smallest prime divisor of n and divides n exactly twice. The crux of the matter is to count the number of collisions, where essentially different ( g, h) yield the same f. We present a classification of all collisions at degree n = p(2) which yields an exact count of those decomposable polynomials.

关键词： Counting special polynomials Finite fields combinatorics on polynomials Generating functions Analytic combinatorics Asymptotic behavior Multivariate polynomials Polynomial decomposition Ritt's Second Theorem

来源：评论

学校读者我要写书评

暂无评论

Counting Reducible and Singular Bivariate polynomials 07

Counting Reducible and Singular Bivariate Polynomials

引用

20th International Symposium on Symbolic and Algebraic Computation

作者： von zur Gathen, Joachim Univ Bonn B It D-53113 Bonn Germany

ISBN: (纸本)9781595937438

关键词： bivariate polynomials finite fields combinatorics on polynomials counting problems reducible polynomials singular polynomials

来源：评论

学校读者我要写书评

暂无评论

Normal form for Ritt's Second Theorem

引用

FINITE FIELDS AND THEIR APPLICATIONS 2014年 27卷 41-71页

作者： von zur Gathen, Joachim Univ Bonn B IT D-53113 Bonn Germany

Ritt's Second Theorem deals with composition collisions g o h = g* o h* of univariate polynomials over a field, where deg g = deg h*. Joseph Fels Ritt (1922) presented two types of such decompositions. His main result here is that these comprise all possibilities, up to some linear transformations. We present a normal form for Ritt's Second Theorem, which is unique in many cases, and clarify the relation between the two types of examples. This yields an exact count of the number of such collisions In the "tame case", where the characteristic of the (finite) ground field does not divide the degree of the composed polynomial. (c) 2013 Elsevier Inc. All rights reserved.

关键词： Computer algebra Univariate polynomial decomposition Bidecornposition Ritt's Second Theorem Finite fields combinatorics on polynomials

来源：评论

学校读者我要写书评

暂无评论

Tame decompositions and collisions

引用

JOURNAL OF SYMBOLIC COMPUTATION 2016年 75卷 244-268页

作者： Ziegler, Konstantin Univ Bonn B IT D-53113 Bonn Germany

A univariate polynomial f over a field is decomposable if f = g . h = g(h) with nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials over a finite field F-q. The tame case, where the characteristic of Fq does not divide n = deg f, is fairly well understood, and we have reasonable bounds on the number of decomposables of degree n. However, it is not known how to determine this number exactly if n has more than two prime factors. There is an obvious inclusion exclusion formula, but to evaluate its summands, one has to determine, under a suitable normalization, the number of collisions, where essentially different components (g,h) yield the same f. Ritt's Second Theorem classifies all tame collisions of two such pairs. We present a normal form for tame collisions of any number of decompositions with any number of components and describe exactly the (non)uniqueness of the parameters. This yields the exact number of such collisions over a finite field. We conclude with a fast algorithm for the exact number of decomposable polynomials at degree n over a finite field Fq of characteristic coprime to n. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Computer algebra Finite fields Tame polynomial decomposition Ritt's Second Theorem Counting special polynomials combinatorics on polynomials

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：