Quasi-polynomial

Quasi-polynomial

In mathematics, a quasi-polynomial (pseudo-polynomial) is a generalization of polynomials. While the coefficients of a polynomial come from a ring, the coefficients of quasi-polynomials are instead periodic functions with integral period. Quasi-polynomials appear throughout much of combinatorics as the enumerators for various objects.

We can write a quasi-polynomial as q(k) = c_d(k) k^d + c_{d-1}(k) k^{d-1} + cdots + c_0(k). If c_d(k) is not identically zero, then the degree of "q" is "d". Equivalently, a function f colon mathbb{N} o mathbb{N} is a quasi-polynomial if there exist polynomials p_0, dots, p_{s-1} such that f(n) = p_i(n) when n equiv i mod s. The polynomials p_i are called the constituents of "f".

Examples

* Given a "d"-dimensional polytope "P" with rational vertices v_1,dots,v_n, define "tP" to be the convex hull of tv_1,dots,tv_n. The function L(P,t) = #(tP cap mathbb{Z}^d) is a quasi-polynomial in "t" of degree "d". In this case, "L(P,t)" is a function mathbb{N} o mathbb{N}. This is known as the Ehrhart quasi-polynomial, named after Eugène Ehrhart.
* Given two quasi-polynomials "F" and "G", the convolution of "F" and "G" is:(F*G)(k) = sum_{m=0}^k F(m)G(k-m)which is a quasi-polynomial with degree le deg F + deg G + 1.

References

* Stanley, Richard P. (1997). [http://www-math.mit.edu/~rstan/ec/ "Enumerative Combinatorics", Volume 1] . Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.

ee also

* Polynomial
* Ehrhart polynomial


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Quasi-algebraically closed field — In mathematics, a field F is called quasi algebraically closed (or C1) if for every non constant homogeneous polynomial P over F has a non trivial zero provided the number of its variables is more than its degree. In other words, if P is a non… …   Wikipedia

  • Quasi-threshold graph — In graph theoretic mathematics, a quasi threshold graph is a graph that can be constructed using the following rules: # K 1 is a quasi threshold graph #If G is a quasi threshold graph, then so is the graph obtained by adding a new vertex… …   Wikipedia

  • Ehrhart polynomial — In mathematics, a integral polytope has an associated Ehrhart polynomial which encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a… …   Wikipedia

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • List of mathematics articles (Q) — NOTOC Q Q analog Q analysis Q derivative Q difference polynomial Q exponential Q factor Q Pochhammer symbol Q Q plot Q statistic Q systems Q test Q theta function Q Vandermonde identity Q.E.D. QED project QR algorithm QR decomposition Quadratic… …   Wikipedia

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

  • Set cover problem — The set covering problem is a classical question in computer science and complexity theory. As input you are given several sets. They may have some elements in common. You must select a minimum number of these sets so that the sets you have… …   Wikipedia

  • Natural proof — In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense natural , it can be shown (assuming a widely believed conjecture… …   Wikipedia

  • Hirsch conjecture — In mathematical programming and polyhedral combinatorics, Hirsch s conjecture states that the edge vertex graph of an n facet polytope in d dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the… …   Wikipedia

  • Gil Kalai — is the Henry and Manya Noskwith Professor of Mathematics at the Hebrew University of Jerusalem, an adjunct professor of mathematics and of computer science at Yale University, and the editor of the Israel Journal of Mathematics . He received his… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”