Quasi-polynomial

<h2 id="examples">Examples</h2>
<ul><li>Given a 
  
    
      
        d
      
    
    {\displaystyle d}
  
-dimensional <a href="/facts/Polytope/a76nXrL0">polytope</a> 
  
    
      
        P
      
    
    {\displaystyle P}
  
 with <a href="/facts/Rational_number/VJQmyY05">rational</a> vertices 
  
    
      
        
          v
          
            1
          
        
        ,
        …
        ,
        
          v
          
            n
          
        
      
    
    {\displaystyle v_{1},\dots ,v_{n}}
  
, define 
  
    
      
        t
        P
      
    
    {\displaystyle tP}
  
 to be the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of 
  
    
      
        t
        
          v
          
            1
          
        
        ,
        …
        ,
        t
        
          v
          
            n
          
        
      
    
    {\displaystyle tv_{1},\dots ,tv_{n}}
  
. The function 
  
    
      
        L
        (
        P
        ,
        t
        )
        =
        #
        (
        t
        P
        ∩
        
          
            Z
          
          
            d
          
        
        )
      
    
    {\displaystyle L(P,t)=\#(tP\cap \mathbb {Z} ^{d})}
  
 is a quasi-polynomial in 
  
    
      
        t
      
    
    {\displaystyle t}
  
 of degree 
  
    
      
        d
      
    
    {\displaystyle d}
  
. In this case, 
  
    
      
        L
        (
        P
        ,
        t
        )
      
    
    {\displaystyle L(P,t)}
  
 is a function 
  
    
      
        
          N
        
        →
        
          N
        
      
    
    {\displaystyle \mathbb {N} \to \mathbb {N} }
  
. This is known as the <a href="/facts/Ehrhart_quasi-polynomial/WjuUYzrT">Ehrhart quasi-polynomial</a>, named after <a href="/facts/Eug%25C3%25A8ne_Ehrhart/HLX2DDBq">Eugène Ehrhart</a>.</li>
<li>Given two quasi-polynomials 
  
    
      
        F
      
    
    {\displaystyle F}
  
 and 
  
    
      
        G
      
    
    {\displaystyle G}
  
, the <a href="/facts/Convolution/PVPrdz9J">convolution</a> of 
  
    
      
        F
      
    
    {\displaystyle F}
  
 and 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is</li></ul>

(
        F
        ∗
        G
        )
        (
        k
        )
        =
        
          ∑
          
            m
            =
            0
          
          
            k
          
        
        F
        (
        m
        )
        G
        (
        k
        −
        m
        )
      
    
    {\displaystyle (F*G)(k)=\sum _{m=0}^{k}F(m)G(k-m)}

which is a quasi-polynomial with degree 
  
    
      
        ≤
        deg
        ⁡
        F
        +
        deg
        ⁡
        G
        +
        1.
      
    
    {\displaystyle \leq \deg F+\deg G+1.}

<ul><li><a href="/facts/Richard_P._Stanley/8bQ4QrLM">Stanley, Richard P.</a> (1997). <a href="http://www-math.mit.edu/~rstan/ec/"><i>Enumerative Combinatorics</i>, Volume 1</a>. Cambridge University Press.  <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-55309-1, 0-521-56069-1.</li></ul>

Quasi-polynomial open-in-new

Quasi-polynomial