Simpliciella komplex och deras f-vektorer

Vi redogör för resultat av Kruskal-Katona, Linusson, Kozlov med flera om antal och möjligt utseende för så kallad f-vektorer till simpliciella komplex. Vi diskuterar sambandet mellan dessa och Hilbertfunktioner för homogena kvoter av den yttre algebran. Relaterade spörsmål om Hilbertfunktioner till homogena kvoter av den symmetriska algebran beskrivs av f-vektorer till s.k. multikomplex, vilka är standardmonomen till artinska monomideal.

import sage.graphs.graph_plot
sage.graphs.graph_plot.DEFAULT_PLOT_OPTIONS['figsize'] = 8
sage.graphs.graph_plot.DEFAULT_PLOT_OPTIONS['transparent'] = True

Simpliciella komplex

Definition av simpliciella komplex

Vi låter \([n]={1,2,...,n}\) och \(B_n\) vara boolsk lattice av alla delmängder, under inklusion. Ett simpliciellt komplex \(\Delta\) är ett ordningsideal i \(B_n\). Vi kräver inte att \(\forall i\in[n]: {i} \in \Delta\) som man ibland ser.

Exempel

Bildar B4

Bn = posets.BooleanLattice(n,use_subsets=True)
Bn.plot()
BnHasse.png

Hittar alla ordningsideal:

Bn = posets.BooleanLattice(n,use_subsets=True)
skBn=list(Bn.order_ideals_lattice())
m = len(skBn)
m
skBn
- 6
- [{}, {{}}, {{}, {2}}, {{}, {1}}, {{}, {2}, {1}}, {{}, {2}, {1}, {1, 2}}]

Exempel, triangulering av projektiva planet. Facett = maximalt elem.

  • Definierande facetter
    simplicial_complexes.ProjectivePlane().facets()
    
    {(0, 3, 4), (1, 3, 5), (0, 2, 3), (1, 2, 4), (0, 1, 2), (0, 4, 5), (2, 4, 5), (2, 3, 5), (0, 1, 5), (1, 3, 4)}
    
  • Dimension

    Dim SK = max dim ingående simplex = kardinalitet - 1

    simplicial_complexes.ProjectivePlane().dimension()
    
    2
    
  • Alla element i S.K, som pomängd:
    simplicial_complexes.ProjectivePlane().plot()
    
    FacePoset.png
  • 1-skelettet är en graf
    simplicial_complexes.ProjectivePlane().graph().plot()
    
    EttSkelett.png

Ordningskomplex

Givet ändlig pomängd \((P,\le)\) så kan vi producera alla “kedjor” \[a_1 \le a_2 \le a_3 \le \cdots \le a_m \] Varje “delkedja” \[a_{i_1} \le a_{i_2} \le \cdots \le a_{i_r}\] är även den en kedja; mängden kedjor sluten nedåt, bildar simpliciellt komplex. Detta kallas “ordningskomplexet” \(O(P)\).

Ppc = posets.ProductOfChains([2,3])
<<KedjeProd23>>
Ppc.plot()
KedjeProd23.png

Ordningskomplex

Ppc = posets.ProductOfChains([2,3])
OP1 = Ppc.order_complex()
Ppc = posets.ProductOfChains([2,3])
OP1 = Ppc.order_complex()
list(OP1.facets())
[((0, 1), (1, 2), (0, 0), (1, 1)),
 ((0, 1), (1, 2), (0, 0), (0, 2)),
 ((1, 2), (0, 0), (1, 1), (1, 0))]

Ett-skelett till ordningskomplexet:

<<OP1>>
OP1.graph().plot()
ESok.png

Om vi ser \(O(\Delta)\) som en pomängd (vi bildar “face-poset”), så har den ett ordningskomplex, vilket blir den barycentriska uppdelningen till \(\Delta\).

Delta = SimplicialComplex([[1,2],[2,3],[3,1]])
DelDel = Delta.face_poset().order_complex()
graphics_array([Delta.graph().plot() , DelDel.graph().plot()])
DeltaBarycentrisk.png

Homologi, Betti-tal

  • Kedjekomplex
    • i grad j, simplex av dim=j, dvs delmängder med j+1 elem
    • Differential \(d_j: C_j \to C_{j-1}\)
    • Homologi \(\ker(d_j) / \textrm{im}(d_{j+1})\)
    • Z-moduler, Smithnormalform
    • Ofta är man endast intresserad av rangen, så kan förlänga med skalärer och räkna med vektorrum
  • Exempel
    • Cirkeln
      Delta = SimplicialComplex([[1,2],[2,3],[3,1]])
      Delta.graph().plot()
      
      Circle.png
      Delta = SimplicialComplex([[1,2],[2,3],[3,1]])
      cc1 =Delta.chain_complex()
      cc1.differential()
      cc1.differential(1).smith_form()
      cc1.differential(1).right_kernel()
      cc1.differential(1).image()
      cc1.homology()
      cc1.betti()
      
      {0: [],
       1: [-1 -1  0]
       [ 1  0 -1]
       [ 0  1  1],
       2: []}
      (
      [1 0 0]  [-1  0 -1]  [ 0  0  1]
      [0 1 0]  [ 1  0  0]  [ 0 -1 -1]
      [0 0 0], [ 1  1  1], [-1  0  1]
      )
      Free module of degree 3 and rank 1 over Integer Ring
      Echelon basis matrix:
      [ 1 -1  1]
      Sparse free module of degree 3 and rank 2 over Integer Ring
      Echelon basis matrix:
      [ 1  0 -1]
      [ 0  1  1]
      {0: Z, 1: Z}
      {0: 1, 1: 1}
      
    • Torus
      Delta = SimplicialComplex([[1,2],[2,3],[3,1]])
      Del2 = Delta.product(Delta)
      list(Del2.facets())
      len(list(Del2.facets()))
      
      - [('L2R2', 'L3R2', 'L3R3'),
      - ('L1R1', 'L1R2', 'L3R2'),
      - ('L2R1', 'L2R2', 'L3R2'),
      - ('L2R1', 'L3R1', 'L3R2'),
      - ('L1R2', 'L1R3', 'L2R3'),
      - ('L1R1', 'L3R1', 'L3R3'),
      - ('L1R2', 'L2R2', 'L2R3'),
      - ('L1R2', 'L3R2', 'L3R3'),
      - ('L2R2', 'L2R3', 'L3R3'),
      - ('L1R2', 'L1R3', 'L3R3'),
      - ('L1R1', 'L3R1', 'L3R2'),
      - ('L1R1', 'L1R2', 'L2R2'),
      - ('L1R1', 'L1R3', 'L3R3'),
      - ('L1R1', 'L2R1', 'L2R2'),
      - ('L1R1', 'L2R1', 'L2R3'),
      - ('L2R1', 'L2R3', 'L3R3'),
      - ('L1R1', 'L1R3', 'L2R3'),
      - ('L2R1', 'L3R1', 'L3R3')]
      - 18
      
      Delta = SimplicialComplex([[1,2],[2,3],[3,1]])
      Del2 = Delta.product(Delta)
      Del2.graph().plot()
      
      cc2 =Del2.chain_complex()
      cc2.homology()
      cc2.betti()
      
      {0: Z, 1: Z x Z, 2: Z}
      {0: 1, 1: 2, 2: 1}
      

      Projektiva planet:

      Pplan = simplicial_complexes.ProjectivePlane()
      Pplan.homology()
      
      {0: 0, 1: C2, 2: 0}
      
    • Sfär:
      Delta = SimplicialComplex([[1,2],[2,3],[3,1]])
      Delta.suspension().homology()
      
      {0: 0, 1: 0, 2: Z}
      

Maximala antikedjor bildar “kaoskomplex”

Om kedjorna till pomängd (P,≤) bildar ordningskomplex, eftersom de är slutna under bortplockning, varför inte antikedjor?

P44 = posets.ProductOfChains([4,4])
<<P44>>
P44.plot()
P44.png
P44 = posets.ProductOfChains([4,4])
Kaos = SimplicialComplex(list(P44.antichains()))
P44 = posets.ProductOfChains([4,4])
Kaos = SimplicialComplex(list(P44.antichains()))
list(Kaos.facets())
[((2, 1), (3, 0), (1, 3)),
 ((3, 1), (2, 2), (1, 3)),
 ((0, 1), (3, 0)),
 ((1, 1), (2, 0), (0, 2)),
 ((3, 0), (2, 2), (1, 3)),
 ((0, 3), (3, 2)),
 ((0, 1), (1, 0)),
 ((1, 2), (0, 3), (2, 0)),
 ((1, 1), (0, 3), (3, 0)),
 ((2, 0), (1, 3)),
 ((3, 1), (0, 2)),
 ((3, 3),),
 ((0, 2), (1, 0)),
 ((1, 1), (0, 3), (2, 0)),
 ((3, 1), (0, 3), (2, 2)),
 ((0, 3), (3, 0), (2, 2)),
 ((1, 2), (3, 1), (0, 3)),
 ((2, 1), (3, 0), (0, 2)),
 ((3, 2), (1, 3)),
 ((0, 3), (1, 0)),
 ((3, 0), (2, 3)),
 ((3, 1), (2, 3)),
 ((0, 0),),
 ((0, 1), (2, 0)),
 ((1, 1), (3, 0), (0, 2)),
 ((2, 3), (3, 2)),
 ((1, 2), (2, 1), (0, 3), (3, 0))]

Den är synnerligen kaotisk:

<<KAOS>>
Kaos.graph()
Kaosgraf.png

Vi undersöker S.K. närmare:

P44 = posets.ProductOfChains([4,4])
Kaos = SimplicialComplex(list(P44.antichains()))
Kaos.dimension()
Kaos.is_pure()
Kaos.is_connected()
Kaos.is_finite()
Kaos.is_flag_complex()
Kaos.homology()
3
False
False
True
True
{0: Z x Z, 1: Z^8, 2: 0, 3: 0}

f-vektorer

Definition

Givet ett S.K \(\Delta\) på \([n]\) så är dess f-vektor \((f_{-1}, f_0 , \dots , f_{n-1}) \in \ZZ^n\) med \(f_j\) = antal simplex i \(\Delta\) av dimension j, d.v.s. av kardinalitet j+1.

  • Det tomma S.K. \(\emptyset\) har f-vector \((0,\dots,0)\)
  • Det triviala S.K \(\{\emptyset\}\) har f-vektor \((1,0, \dots , 0)\)
  • Ibland ser man att folk hugger av \(f_{-1}\) och bara ger \((f_0, f_1, \dots , f_{n-1})\).

Exempel

  • En triangel har f-vektor (1,3,3), en hexagon har f-vektor (1,6,6)

    Delta = SimplicialComplex([[1,2],[2,3],[3,1]])
    Hexa = Delta.face_poset().order_complex()
    
    Delta = SimplicialComplex([[1,2],[2,3],[3,1]])
    Hexa = Delta.face_poset().order_complex()
    Delta.faces()
    Delta.f_vector()
    Hexa.faces()
    Hexa.f_vector()
    
    {-1: {()}, 0: {(1,), (2,), (3,)}, 1: {(1, 2), (1, 3), (2, 3)}}
    [1, 3, 3]
    {-1: {()},
     0: {((1,),), ((1, 2),), ((1, 3),), ((2,),), ((2, 3),), ((3,),)},
     1: {((1, 2), (1,)),
      ((1,), (1, 3)),
      ((1, 2), (2,)),
      ((3,), (1, 3)),
      ((2,), (2, 3)),
      ((2, 3), (3,))}}
    [1, 6, 6]
    
  • Större exempel, matchningskomplexet

    MatKomp = simplicial_complexes.MatchingComplex(7)
    MBary=MatKomp.barycentric_subdivision()
    MatKomp.f_vector()
    MatKomp.homology()
    MBary.f_vector()
    MBary.homology()
    
    [1, 21, 105, 105]
    {0: 0, 1: C3, 2: Z^20}
    [1, 231, 840, 630]
    {0: 0, 1: C3, 2: Z^20}
    

Varianter, f-triangel, h-vektor

  • f-triangel:

    • (Björner-Wachs)
    • \(A \in \Delta\), storlek \(|A|\), grad \(\max {|F| : A \subseteq F \in \Delta}\)
    • \(f_{i,j}\) antal av storlek i, grad j
    • Exempel:
    SK2 = SimplicialComplex([[1,3,5],[2,4]])
    SK2.f_vector()
    SK2.f_triangle()
    SK3 = SimplicialComplex([[1,3,5],[2,4,6],[1,4,5]])
    SK3.f_vector()
    SK3.f_triangle()
    
    [1, 5, 4, 1]
    [[0], [0, 0], [0, 2, 1], [1, 3, 3, 1]]
    [1, 6, 8, 3]
    [[0], [0, 0], [0, 0, 0], [1, 6, 8, 3]]
    
  • h-vektor (från sagemath-manualen)
    • The h-vector of this simplicial complex.
    • If the complex has dimension d and \((f_{-1}, f_0, f_1, ..., f_d)\) is its f-vector (with \(f_{-1} = 1\), representing the empty simplex), then the h-vector \((h_0, h_1, ..., h_d, h_{d+1})\) is defined by \[ \sum_{i=0}^{d+1} h_i x^{d+1-i} = \sum_{i=0}^{d+1} f_{i-1}(x-1)^{d+1-i}\] Alternatively, \[ h_j = \sum_{i=-1}^{j-1} (-1)^{j-i-1} \binom{d-i}{j-i-1} f_i. \]
  • Exempel:

    SK3 = SimplicialComplex([[1,3,5,7],[2,4,6],[1,4,5],[2,3,4,5]])
    SK3.f_vector()
    SK3.h_vector()
    RK3 = SK3.stanley_reisner_ring()
    IK3 = RK3.defining_ideal()
    from sage.rings.polynomial.hilbert import hilbert_poincare_series
    hilbert_poincare_series(IK3)
    
    [1, 7, 14, 10, 2]
    [1, 3, -1, -1, 0]
    (t^3 + t^2 - 3*t - 1)/(-t^4 + 4*t^3 - 6*t^2 + 4*t - 1)
    

Kruskal-Katona

Begränsning av växt av f-vektor

En heltalsvektor \((f_{0},f_{1},...,f_{d})\) är en f-vektor till något (d)-dimensionellt S.K. omm

\[\forall 0 \leq i \leq d-1: 0 < f_{i+1} \leq \partial_{i+1}(f_{i})\]

Vi skall förklara notationen, men notera följande: om tex \(f_5\) känt och vi vill veta största möjliga \(f_6\), så spelar bara \(f_5\) in, inte de tidigare!!!

Exempel

loadPackage("ExteriorIdeals")
E = QQ[e_1,e_2,e_3,e_4,SkewCommutative => true]
sort allHilbertSequences(E)	   
-1 0 0 0 0
0 0 0 0 0
1 0 0 0 0
1 1 0 0 0
1 2 0 0 0
1 2 1 0 0
1 3 0 0 0
1 3 1 0 0
1 3 2 0 0
1 3 3 0 0
1 3 3 1 0
1 4 0 0 0
1 4 1 0 0
1 4 2 0 0
1 4 3 0 0
1 4 3 1 0
1 4 4 0 0
1 4 4 1 0
1 4 5 0 0
1 4 5 1 0
1 4 5 2 0
1 4 6 0 0
1 4 6 1 0
1 4 6 2 0
1 4 6 3 0
1 4 6 4 0
1 4 6 4 1

Binomialexpansion

Givet N,i pos heltal, finns unik expansion \[ N = \binom{n_{i}}{i} + \binom {n_{{i-1}}}{i-1} + \dots + \binom{n_{j}}{j}, \quad n_{i}>n_{{i-1}}> \dots >n_{j}\geq j\geq 1. \]

Nu definierar vi en funktion \(\partial_i(N)\) genom \[ \partial_i(N) = \binom{n_{i}}{i+1} + \binom{n_{i-1}}{i} + \dots + \binom{n_{j}}{j+1} \] En heltalsvektor \((f_{0},f_{1},...,f_{{d-1}})\) är alltså f-vektor till något (d-1)-dimensionellt S.K. omm

\[ \forall 0 \leq i \leq d-1: 0 < f_{i+1} \leq \partial_{i+1}(f_{i}) \]

dvs om vi vet \(f_i\), \[ f_i = {\binom{n_{i+1}}{i+1} + \binom {n_{i}}{i}}+{\binom {n_{{i-1}}}{i-1}}+\ldots + {\binom {n_{j}}{j}}, \quad n_{i+1} > n_{i}>n_{{i-1}}> \dots >n_{j}\geq j\geq 1 \] så får vi olikheten \[ f_{i+1} \le {\binom{n_{i+1}}{i+2} + \binom {n_{i}}{i+1}}+{\binom {n_{{i-1}}}{i}}+\ldots + {\binom {n_{j}}{j+1}} \] för \(f_{i+1}\).

Vi kan omvänt begränsa \(f_i\) givet \(f_{i+1}\).

  • Exempel:
    def binom_coefficient (n , i ) :
        n_i = 1;
        while binomial(n_i , i ) <= n :
            n_i += 1
        return (n_i - 1,i)
    
    
    #Returns the i−binomial expansion of n .
    def ibinom_expansion ( n , i ):
        n_i = n ;
        expansion_vector = [ ] ;
        while n_i > 0:
            expansion_vector.append(binom_coefficient(n_i , i ) )
            n_i -= binomial(*expansion_vector[-1])
            i -= 1
        return expansion_vector
    
    
    
    def ibinom_expansion_1( n , i ):
        """
        Returns the i−binomial expansion of n with 1 added to the bottom of
        all binomial coefficients in the expansion .
        """
        ibinom_expansion_ = ibinom_expansion( n , i );
        ibinom_expansion_1_ = 0 ;
        for x in ibinom_expansion_:
            ibinom_expansion_1_ += binomial( x[0] , x[1] + 1 )
        return ibinom_expansion_1_
    
    
    def is_fvector (p):
    # Checks if a given point is an f−vector ( Kruskal−Katona theorem ) 
        for i in range(0 , len( p ) - 1):
            if p[i+1] > ibinom_expansion_1(p[i] ,i+1):
                return false
        return true
    
    n,j, ibinom_expansion(n,j)
    m = ibinom_expansion_1(n,j)
    ibinom_expansion(m,j+1), m
    
    (29, 4, [(6, 4), (5, 3), (3, 2), (1, 1)])
    ([(6, 5), (5, 4), (3, 3)], 12)
    

(Ko)Lexsegment

Beviset för Kruskal-Katona går som följer.

  • Lista alla ändliga delmängder av kardinalitet i+1 till \(\ZZ_{+}\) i kolexordning dvs förekomst av stora tal straffas: 123,124,134,234,125,135,235,145,245,345,…
  • Till en potentiell f-vektor \(f=(f_0, f_1 , \dots , f_{d-1})\) ordnar vi “kolexsegmentet” \(\Delta_f\) som i dimension \(i\) har de \(f_i\) första delmängderna av kardinalitet \(i+1\)
  • Detta behöver inte bli ett S.K!
  • Föjande likvärdiga:
    1. \(\Delta_f\) är ett S.K.
    2. \(f=(f_0 , f_1 , \dots , f_{d-1})\) uppfyller binomialväxtvillkoren \(0 < f_{i+1} \leq \partial_{i+1}(f_{i})\)
    3. f är en f-vektor till något S.K.
  • Exempel (fast datorn tar komplementsimplexen i lexordning, så för varje grad får vi de sista i kolexordning) #+NAME=ExtLex

    truncateOutput 60    
    loadPackage("ExteriorIdeals")
    setEcho stdio        
    E=QQ[e_1..e_5,SkewCommutative=>true]
    Ilex=lexIdeal(ideal({e_5*e_2,e_2*e_3}))
    sort(basis(E/ideal({e_5*e_2,e_2*e_3})))    	       
    R = E/Ilex
    sort(basis(R))
    
    o2 = ExteriorIdeals
    
    o2 : Package
    truncateOutput 60    
    loadPackage("ExteriorIdeals")
    setEcho stdio        
    E=QQ[e_1..e_5,SkewCommutative=>true]
    
    o4 = E
    
    o4 : PolynomialRing, 5 skew commutative variable(s)
    Ilex=lexIdeal(ideal({e_5*e_2,e_2*e_3}))
    
    o5 = ideal (e e , e e )
                 1 2   1 3
    
    o5 : Ideal of E
    sort(basis(E/ideal({e_5*e_2,e_2*e_3})))    	       
    
    o6 = | 1 e_5 e_4 e_3 e_2 e_1 e_4e_5 e_3e_5 e_1e_5 e_3e_4 e_2e ...
    
                /      E      \1      /      E      \20
    o6 : Matrix |-------------|  <--- |-------------|
                |(-e e , e e )|       |(-e e , e e )|
                \   2 5   2 3 /       \   2 5   2 3 /
    R = E/Ilex
    
    o7 = R
    
    o7 : QuotientRing
    sort(basis(R))
    
    o8 = | 1 e_5 e_4 e_3 e_2 e_1 e_4e_5 e_3e_5 e_2e_5 e_1e_5 e_3e ...
    
                 1       20
    o8 : Matrix R  <--- R
    

Kruskal-Katonafunktionerna, Takagi

Funktionerna \(\partial_j\) och \(\partial_j^*\) har intressanta egenskaper, speciellt deras “självsimilära” beteende.

  • Grafer för funktionerna \(\partial_j\):
    <<Aliaksandra>>
    from sage.plot.colors import red, blue, lime
    dm = [ [ibinom_expansion_1(k,j) for k in range(1,N)] for j in range(sta,sto+1)]
    add([list_plot(dm[_],transparent=True,color=red.blend(blue,fraction=_/(1+sto-sta))) for _ in range(1+sto-sta)]) 
    
    BinUp.png
  • Kruskal-Katona nedåt

    Om vi istället begränsar \(f_{i-1}\) givet värdet på \(f_i\) så får vi snarlika funktioner \(\partial^*_j\), vars grafer är som följer:

    <<BINOMIAL>>
    from sage.plot.colors import red, blue, lime
    dm = [ [[k,BinomialDownEval(k,j)] for k in range(1,N)] for j in range(sta,sto+1)]
    add([list_plot(dm[_],transparent=True,color=red.blend(blue,fraction=_/(1+sto-sta))) for _ in range(1+sto-sta)]) 
    
    BinDown.png

    Vi plottar \(\partial_7^*(m) -m\)

    def FS(n,k):
        var('j')
        j=0
        while(binomial(j,k) <= n):
            j = j+1
        return j-1
    end
    
    
    def BinomialExpansion(n,k):
        var('L,S,R,j,b')
        L=[]
        j=k
        R=n
        while(R > 0):
            b = FS(R,j)
            S = binomial(b,j)
            L.append([j,b])
            R = R - S
            j = j - 1
        return L
    end
    
    
    def BinomialEval(L):
        var('v')
        return add(binomial(v[1],v[0]) for v in L)
    end
    
    
    def BinomialUp(L):
        var('v')
        return [[v[0]+1,v[1]] for v in L]
    end
    
    @cached_function
    def BinomialUpEval(n,k):
        return BinomialEval(BinomialUp(BinomialExpansion(n,k)))
    end
    
    
    def BinomialDown(L):
        var('v')
        return [[v[0]-1,v[1]] for v in L]
    end
    
    @cached_function
    def BinomialDownEval(n,k):
        return BinomialEval(BinomialDown(BinomialExpansion(n,k)))
    end
    list_plot([BinomialDownEval(m,k) -m for m in range(N)],transparent=True)
    
  • Takagifunktionen

    Takagifunktionen kan definieras på (0,1) som \[ T(x) = \sum_{j=1}^\infty 2^{-n} d(2^n x,\ZZ) \] där \(d(r,\ZZ) = \mathrm{abs}(r - \lfloor r+1/2 \rfloor)\) är avståndet från r till närmsta heltal. Den kan också fås genom att fraktalt mixtra med den styckvis linjära takfunktionen, som när man konstruerar Weierstrass oderiverbara.

    <<TAKAGIKOD>>
    plot(NewTakagi(x,N),(x,0,1),transparent=True)
    
    Takagi.png
  • Frankl et al, \(\partial_j\) rätt omskalad konvergerar mot Takagi

Kozlov, konvext hölje, polytop

Dimitry Kozlov visade i Convex hulls of f- and beta-vectors att konvexa höljet av f-vektorer till simpliciella komplex på [n] har en enkel beskrivning

  • Betrakta alla \(\Delta \in B_n\) så att \({1},{2}, \dots , {n} \in \Delta\)
  • Vi kapar f-vektorn till \((f_0, f_1 , \dots , f_{n-1})\), med \(f_0 = n\) och ser resultatet som liggandes i \(\ZZ^n\)
  • Låt \(S_k(n)\) vara det fullständiga k-skelettet på n-hörn (Kozlov avser: alla delsimplex med kardinalitet k)

    def Skel(k,n):
        S = SimplicialComplex([[_ for _ in range(1,n+1)]])
        return S.n_skeleton(k-1)
    
    sixgens = [vector(Skel(_,6).f_vector()[1:]) for _ in range(1,6+1)]
    sixgens
    
    def Skel(k,n):
        S = SimplicialComplex([[_ for _ in range(1,n+1)]])
        return S.n_skeleton(k-1)
    
    sixgens = [vector(Skel(_,6).f_vector()[1:]) for _ in range(1,6+1)]
    sixgens
    Skel(3,6)
    Skel(3,6).facets()
    sixgens
    
    [(6),
     (6, 15),
     (6, 15, 20),
     (6, 15, 20, 15),
     (6, 15, 20, 15, 6),
     (6, 15, 20, 15, 6, 1)]
    Simplicial complex with vertex set (1, 2, 3, 4, 5, 6) and 20 facets
    {(1, 3, 5), (2, 3, 4), (2, 3, 6), (1, 2, 5), (1, 4, 5), (4, 5, 6), (1, 4, 6), (2, 4, 6), (1, 2, 4), (1, 3, 6), (2, 4, 5), (3, 5, 6), (3, 4, 6), (2, 3, 5), (2, 5, 6), (3, 4, 5), (1, 2, 3), (1, 2, 6), (1, 3, 4), (1, 5, 6)}
    [(6),
     (6, 15),
     (6, 15, 20),
     (6, 15, 20, 15),
     (6, 15, 20, 15, 6),
     (6, 15, 20, 15, 6, 1)]
    
  • Låt \[ F_{_k}(n) = (\binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{k} , 0, \dots , 0) \in \ZZ^n \] vara dess (kapade) f-vektor
  • Då är konvexa höljet till alla f-vektorer till \(\Delta\) som ovan: polytopen \(\text{konv}(F_1, \dots , F_n)\)

    DelT = SimplicialComplex([[1,2],[2,3],[3,1]]).product(SimplicialComplex([[1,2]]))
    DelT.f_vector()[1:]
    (1/5)*sixgens[0], (1/2)*sixgens[1],  (3/10)*sixgens[2]
    
    [6, 12, 6]
    ((6/5), (3, 15/2), (9/5, 9/2, 6))
    
  • Speciellt antar varje affin funktion av f-vektorerna (som t.ex. Eulerkarakteristiken, som är alternerande summan) sitt maximum för något fullständigt skelett
  • Kozlov bestämde även konvexa höljet till \(\beta\)-vektorn \((\beta_0, \dots , \beta_{n-1})\) av S.K. som ovan, det blir givet av konvexa höljet till \(\beta\) för k-skelett, explicit konvexa höljet av \(B_1(n), \dots , B_n(n)\) med \(B_k(n)\) vektorn som är noll utom i position \(k-1\), där den är \(\binom{n-1}{k}\)

    Observera att Kozlov använder “reducerad homologi” som nollar \(\beta_0\).

def Skel(k,n):
    S = SimplicialComplex([[_ for _ in range(1,n+1)]])
    return S.n_skeleton(k-1)

sixgens = [vector(Skel(_,6).f_vector()[1:]) for _ in range(1,6+1)]
sixgens
[Skel(_,6).betti() for _ in range(1,6+1)]
[(6),
 (6, 15),
 (6, 15, 20),
 (6, 15, 20, 15),
 (6, 15, 20, 15, 6),
 (6, 15, 20, 15, 6, 1)]
[{0: 6},
 {0: 1, 1: 10},
 {0: 1, 1: 0, 2: 10},
 {0: 1, 1: 0, 2: 0, 3: 5},
 {0: 1, 1: 0, 2: 0, 3: 0, 4: 1},
 {0: 1, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}]

Linusson, antal f-vektorer

Svante Linusson beräknade antalet f-vektorer i sin artikel The number of m-sequences and f-vectors

  • Mer precist, \(M^p(n) - 1\) är antalet f-vektorer till (n-1)-dimensionella simpliciella komplex på [n+p]
  • \(M^p(n) - 1\) räknar också M-följder med \(m_1 \le p\) och \(m_j = 0\) för \(j > n\), där en M-följd är motsvarigheten till f-vektorer för multikomplex (kommer)
  • Explicit, effektiv rekursion involverande \(M^p(n)\) och \(L^p(n,k)\), där \(L^p(n,k)\) förfining av \(M^p(n)\), räknar M-följder med extra villkor
  • Fixt p

    k \(M^p(n)\)
    1 \(n+2\)
    2 \(2^{n+1} \)
    3 Bell(n+2)
  • Fixt n

    n \(M^p(n)\)
    0 2
    1 \(p+2\)
    2 \(\binom{p+2}{3} + \binom{p+2}{1}\)
    3 \(4\binom{p+2}{6} + \dots \)
    4 \(120\binom{p+2}{10} + \dots \)
  • Övre begränsning \(M^p(n) \le (n+p-1)^{n(p-1)}\)

Aliaksandra, f-vektorers placering/tyngdpunkt

  • Vi vet att alla f-vektorer (av S.K. på [n]) ligger inuti Kozlov-polytopen
  • Vi vet hur många de är (Linusson)
  • Så, vi vet andelen av gitterpunkter inuti KP som är f-vektorer
  • Men hur är de fördelade?
  • 10triangle.png
  • Exjobb av Aliaksandra Kupreyeva, Simplices of f-vectors
  • \(E_p^n(k)\) = ant f-vektorer med \(f_1 \le p\), \(f_j = 0\) för \(j > n\), \(f_j = \binom{p}{j}\) för \(1 \le j \le k\) och \(f_{k+1} < \binom{p}{k+1}\)
  • Då är \(F_p^n = \sum_{k=-1}^n E_p^n(k)\) antalet f-vektorer med \(f_0=p\), \8fj = 0\) för \(j > n\)
  • Linusson ger rekursion för \(E_p^n(k)\)
  • \(E_p^n(k) =\)
    • \(\sum_{i=k}^n E_{p-1}^n(i)*E_{p-1}^{i-1}(k-1)\) om \(k \le n < p\)
    • \(E_p^{p-1}(k)\) om \(k < n = p\)
    • 1 om \(k = n = p\)
  • Ger \[ F_p^3 = 4\binom{p+2}{6} + \binom{p+2}{4} + \binom{p+2}{1} - \left( 4 \binom{p+1}{6} + \binom{p+1}{4} + \binom{p+1}{1} \right) \]
  • Polynom \((1/30)p^5 + l.o.t(p)\)
  • Antalet gitterpunkter i triangeln \(\text{konv}((0,0),(\binom{p}{2},0),(\binom{p}{2},\binom{p}{3}))\) fås via Ehrhardteori som kvasipolynomet
    • \((1/24)p^5 -(1/6)p^4 + (7/24)p^3 + (1/6)p^2 -(1/3)p +1\) om \(p \equiv 2 \mod 3\)
    • \((1/24)p^5 -(1/6)p^4 + (7/24)p^3 + 0p^2 -(1/6)p +1\) om \(p \equiv 0,1 \mod 3\)
  • Kvoten går mot 24/30 = 4/5 då \(p \to \infty\)
  • Heuristiskt argument för tyngpunkten av f-vektorer
    • \(\partial_2(x) \approx \sqrt{3}/2 x^{3/2}\)
    • Tyngdpunkten hamnar i \(((5/7)p,(5\sqrt{2}/48)p^{3/2})\), omskalat till barycentriska koordinater så går det mot (2/7, 45/112, 5/16) då p → ∞
  • För \(F_p^4\) så polynom \((1/3024)p^9 + l.o.t(p)\)
  • Gitterpunkterna i Kozlovpolytopen kvasipolynom \((1/1728)p^9 + l.o.t(p)\)
  • Kvot 4/7
  • Tyngdpunkt (0.18, 0.29, 0.22) i barycentriska koordinater

Yttre algebran

Definition av yttre algebran

  • k kropp, \(kar(k) \neq 2\)
  • V fria k-vektorrummet på [n]
  • \(x_1, \dots ,x_n\) bas för V (eller V*)
  • \(T(V) = k\) tensoralgebran, fria associativa
  • \(E(V) = E[e_1 , \dots, e_n]\) yttre algebran
  • \(T(V)/Q\) där \(Q = \)
  • k-bas \(e_{i_1} \cdots e_{i_r}\)} där \(1 \le i_1 < i_2 < \cdots < i_r \le n\)
  • graderad, \(dim(E_d) = \binom{n}{d}\)
  • graderat kommutativ, \(f^2 = 0\) om \(f \in E_d\), d udda

Indikatoralgebran

  • Tag ett S.K. \(\Delta\) på [n]
  • Kom ihåg: \(\Delta\) ordningsideal på \(B_n\)
  • Så \([n] \setminus \Delta\) är ett ordningsfilter
  • Till ett element \(\{i_1, \dots, i_r\} \in [n] \setminus \Delta\) så ordnar vi monomet \(e_{i_1}e_{i_2 }\cdots e_{i_r} \in E[e_1, \dots ,e_n]\)
  • Mängden \(S \subset E\) av sådana monom uppfyller \(e_j*S \in S\) för alla variabler \(e_j\), så är mängden monom i ett monomideal J
  • Algebran \(k\{\Delta\} = E/J\) har som bas standardmonom som svarar mot elementen i \(\Delta\)
  • Så f-vektorn för \(\Delta\) svarar mot Hilbertserien till \(k\{\Delta\} = E/J\)
  • Vi kunde ha använt “kvadratfria algebran” \(k[x_1,\dots ,x_n]/(x_1^2, \dots ,x_n^2)\) och dess kvot “artinifierade Stanley-Reisner-ringen” \[k[\overline{\Delta}] = (k[x_1,\dots ,x_n]/(x_1^2, \dots ,x_n^2))/I_\Delta\] istf E, men yttre algebran har fördelar, homologi och “Gröbnerkopplingar” som ger “algebraisk skiftning” via generiska initialideal
  • Det är också vanligt att studera kvoter av \(k[x_1, \dots, x_n]\) utan att först dela ut med kvadraterna, den s.k. Stanley-Reisnerringen. Kommer senare!
  • För bettitalen för \(\Delta\) så har vi att \(H^i(k\{\Delta\}) \simeq H^{i-1}(\Delta; k)\) där
    • HL = reducerad simpliciell kohomologi för \(\Delta\), med koefficienter i k
    • VL = kohomologin för komplexet av k-vr \(\cdots \to k\{\Delta\}_{i-1} \to k\{\Delta\}_i \to k\{\Delta\}_{i+1} \to \cdots\) där avbildningarna är mult med \(e = e_1 + e_2 + \dots + e_n\), kom ihåg \(e^2 = 0\)
  • “Bettital” används även för \(\beta_{i,a}^E(k\{\Delta\}) = \dim_k Tor_i^E(k\{\Delta\},k)\), här är \(a \in \ZZ\) en multigrad. Då gäller \(\beta_{i,a}^E(k\{\Delta\}) = \dim_k H^{|a|-i-1} (\Delta_{supp(a)}; k)\) där HL återigen är reducerad simpliciell kohomologi, \(\Delta_{supp(a)}\)} är restriktionen till stödet av a, tex \(\Delta_{supp((2,0,7,0))}\) är de delsimplex i \(\Delta\) som är delmängder till \(\{1,3\}\)
  • Aramova-Herzog-Hibi, motsvarande resultat för Stanley-Reisnerringar , Hochster
  • Exempel; upplösningen oändlig så vi tittar på liten del i början
setEcho stdio
E=QQ[e_1..e_3,SkewCommutative=>true, Degrees => {{1,0,0},{0,1,0},{0,0,1}}]
I = ideal({e_1*e_2,e_2*e_3})
sr = res (I, LengthLimit => 3)
betti sr
peek oo    	   
setEcho stdio
E=QQ[e_1..e_3,SkewCommutative=>true, Degrees => {{1,0,0},{0,1,0},{0,0,1}}]

o2 = E

o2 : PolynomialRing, 3 skew commutative variable(s)
I = ideal({e_1*e_2,e_2*e_3})

o3 = ideal (e e , e e )
             1 2   2 3

o3 : Ideal of E
sr = res (I, LengthLimit => 3)

      1      2      5      9
o4 = E  <-- E  <-- E  <-- E
                           
     0      1      2      3

o4 : ChainComplex
betti sr

            0 1 2 3
o5 = total: 1 2 5 9
         0: 1 . . .
         1: . 2 5 9

o5 : BettiTally
peek oo    	   

o6 = BettiTally{(0, {0, 0, 0}, 0) => 1}
                (1, {0, 1, 1}, 2) => 1
                (1, {1, 1, 0}, 2) => 1
                (2, {0, 1, 2}, 3) => 1
                (2, {0, 2, 1}, 3) => 1
                (2, {1, 1, 1}, 3) => 1
                (2, {1, 2, 0}, 3) => 1
                (2, {2, 1, 0}, 3) => 1
                (3, {0, 1, 3}, 4) => 1
                (3, {0, 2, 2}, 4) => 1
                (3, {0, 3, 1}, 4) => 1
                (3, {1, 1, 2}, 4) => 1
                (3, {1, 2, 1}, 4) => 1
                (3, {1, 3, 0}, 4) => 1
                (3, {2, 1, 1}, 4) => 1
                (3, {2, 2, 0}, 4) => 1
                (3, {3, 1, 0}, 4) => 1
  • I stället för fri upplösning kan man använda homologin till “Cartankomplexet”

Initialideal

Boolska termordningar

En boolsk termordning är en linjär extension \(\prec av (B_n, \le)\) som är multiplikativ, dvs

  • \(\emptyset \prec \alpha\) för alla \(\alpha \in B_n \setminus \emptyset\)
  • Om \(\alpha \prec \beta\) och \(\gamma \cap (\alpha \cup \beta) = \emptyset\) then \((\alpha \cup \gamma) \prec (\beta \cup \gamma)\)
  • Vi förutsätter att \(\prec\) är sorterad dvs \(\{1\} \succ \{2\} \succ \cdots \succ \{n\}\)
  • För våra syften räcker det att betrakta grad först-termordningar, där \(\vert\alpha\vert < \vert\beta\vert \rightarrow \alpha \prec \beta\)
  • Allt detta översätts till en multiplikativ totalordning av monomen i E
  • (Deg)lex: \(\{i_1, \dots , i_r \} \prec_{lex} \{j_1, \dots , j_s\}\) om \(i_1 = j_1 , \dots , i_k = j_k\) men \(i_{k+1} < j_{k+1}\)
  • degrevlex (colex): \({i_1, \dots , i_r } \prec_{degrevlex} {j_1, \dots , j_s}\) om \(i_n = j_n, \dots , i_{k+1} = j_{k+1}\) men \(i_k > j_k\)

Initialideal, Gröbnerbaser

  • \(E = E[e_1, \dots ,e_n]\) yttre algebra, \(\prec\) någon termordning
  • Till ett element (polynom) \(f \in E\) hör \(in_\succ(f)\), största monomet i stödet
  • Till ett (homogent, säg) ideal \(I \subset E\) hör \(in_\succ(I) = \{in_\succ(f) : f \in I\}\)
  • Om \(I = (f_1, \dots , f_r)\) så inte säkert att \(in(I) = (in(f_1), \dots , in(f_r))\), kan behöva lägga till icke-minimala generatorer för att få hela \(in(I)\)
  • Gröbnerbas, kompleteringsprocess liknande Knuth-Bendix: generatorer \(f_1, \dots , f_s\) till I så att \(in(f_1), \dots, in(f_s)\) genererar in(I). Tillagda generatorer kan ha högre grad.
  • Monomen ej i in(I) ger S.K. \(\Delta\), om vi identifierar \(\sigma \in \Delta\) med monomet \(e_\sigma\). Vi har förstås att \(E = in(I) \oplus \Delta\) som k-vektorrum
  • Gäller även: \(E = I \oplus \Delta\) som k-vektorrum, så \(\Delta\) ger k-bas för \(E/I\)
  • Följer att \(E/I\) och \(E/in(I)\) har samma Hilbertserie, som svarar mot f-vektorn för \(\Delta\)
  • Beroende på termordning \(\succ\) så skiljer sig \(in_\succ(I)\) och därmed \(\Delta\) åt, men samma Hilbertserie, samma f-vektor.
  • Exempel (självsyzygier)

    setEcho stdio    
    loadPackage("ExteriorIdeals")    
    E=QQ[e_1..e_4,SkewCommutative=>true]
    I = ideal(random(2,E))
    hilbertSeries(E/I)    
    InitId=initialIdeal(I)
    IndikatorAlg = E/InitId
    hilbertSeries(IndikatorAlg)    
    basis(IndikatorAlg)    
    
    setEcho stdio    
    loadPackage("ExteriorIdeals")    
    
    o2 = ExteriorIdeals
    
    o2 : Package
    E=QQ[e_1..e_4,SkewCommutative=>true]
    
    o3 = E
    
    o3 : PolynomialRing, 4 skew commutative variable(s)
    I = ideal(random(2,E))
    
               1       3       9       9       5
    o4 = ideal(-e e  + -e e  + -e e  + -e e  + -e e  + e e )
               4 1 2   5 1 3   5 2 3   7 1 4   6 2 4    3 4
    
    o4 : Ideal of E
    hilbertSeries(E/I)    
    
               2      4      5     6
         1 - 5T  + 15T  - 16T  + 5T
    o5 = ---------------------------
                          4
                   (1 - T)
    
    o5 : Expression of class Divide
    InitId=initialIdeal(I)
    
    o6 = ideal (e e e , e e e , 105e e )
                 1 3 4   2 3 4      1 2
    
    o6 : Ideal of E
    IndikatorAlg = E/InitId
    
    o7 = IndikatorAlg
    
    o7 : QuotientRing
    hilbertSeries(IndikatorAlg)    
    
               2      4      5     6
         1 - 5T  + 15T  - 16T  + 5T
    o8 = ---------------------------
                          4
                   (1 - T)
    
    o8 : Expression of class Divide
    basis(IndikatorAlg)    
    
    o9 = | 1 e_1 e_1e_3 e_1e_4 e_2 e_2e_3 e_2e_4 e_3 e_3e_4 e_4 |
    
                            1                  10
    o9 : Matrix IndikatorAlg  <--- IndikatorAlg
    
  • Torsionsmodulerna \(Tor_i^E(E/I,k)\) är ä.dim. \(\ZZ\)-graderade k-vektorrum, kan beräknas tex via Cartanhomologi. Ej fingraderade
  • \(Tor_i^E(E/in(I),k)\) fingraderat
  • \(\beta_{i,j}(E/I) = dim Tor_i^E(E/I,k)_j \le \beta_i,j(E/in(I))\)

Generiska initialideal

  • \(E=E(V)\), \(GL(V)\) verkar på V, inducerad verkan på \(E(V)\)
  • \(g.I\) ideal, homogent, grader bevaras, hilbertseri \(E/(g.I)\) samma
  • \(gin(I) = in(g.I)\) för generiskt g
  • \(gin(I)\) har goda kombinatoriska egenskaper, utgör s.k starkt stabila monomideal

Starkt stabila monomideal

  • Def, skiftade komplex
    • Ett monomideal \(J \subset E[e_1 , \dots, e_n]\) är starkt stabilt om

    \(e_i m \in J\) medför \(e_j m \in J\) för alla \(j \le i\)

    • Kallas även Borel-fixt ty \(b.J = J\) för alla övertriangulära matriser \(b \in B\), Boreldelgruppen till \(GL(V)\)
    • Notera att de ideal som fixeras av torusen (diagonalmatriser) är precis monomidealen
    • Komplementärmonomen \(\Delta = T \setminus (J \cap T)\) bildar ett skiftat S.K. där för alla \(\sigma \in \Delta, j \in \sigma\) medför att \((\sigma \setminus \{j\}) \cup \{v\} \in \Delta\) för alla \(j \le v \le n\)
    • Ibland ordnar man variablerna åt andra hållet
  • Algebraisk skiftning
    • Starta med S.K. \(\Delta\)
    • Indikatoralgebra \(k{\Delta} = E/J\)
    • \(gin(J)\) starkt stabilt monomideal
    • \(E/gin(J) = k{\tilde\Delta}\)
    • \(\tilde\Delta\) skiftade komplexet, skiftat!
  • Exempel (Kalai)
    • \(\Delta\) randen till oktahedron
    • \(\Delta\) har facetter 123,126,135,234,156,246,345,456, ej skiftat?
    • J = monomidealet i E på komplementmonomen
    • \(\succ = lex\) (eller deglex)
    • \(gin(J)\) nytt monomideal
    • \(E/gin(J) = k\{\tilde\Delta\}\)
    • \(\tilde\Delta\) har facetter 123, 124, 125, 126, 135,136,234, skiftat!
  • Kombinatoriska egenskaper
    • (Monomen i) ett kvadratfritt monomideal är ett filter i (delbarhetspomängden) \(B(n)\)
    • (Monomen i) ett starkt stabilt monomideal J är ett filter i den pomängd man får när man kombinerar delbarhet med \(e_1 > e_2 > \cdots > e_n\) samt multiplikativitet
    • (S) On some partial orders associated to generic initial ideals artikel i Sem. Loth. Combinatoire, pomängden isoton med numeriska partitioner i distinkta delar ≤ n
    • Figur: borelfixa ideal i yttre algebran på 4 variabler svarar mot filter i denna pomängd

    sqfree-filter.png
  • Upplösning, bettital
    • Gotzmann theorems for exterior algebra and combinatorics Avramova, Herzog, Hibi, multigrad bettital för starkt stabilt J
    • \(G(J)\) mingen
    • \(m(u)\) för monom u är max index för variabel däri
    • \(\beta_{i,j+i}(J) = \sum_{u \in G(J)} \binom{m(u) + i -1}{m(u)-1}\)
    • Kan göras multigraderat
    • Poincaré-Betti \(P_J(s,t) = \sum_{j \ge 1} \sum_{u \in G(J)_j} s^j(1-ts)^{-m(u)}\)
    • Ger Hilbertfunktioen för k{Δ} = E/J och alltså f-vektor, specialisera till \(P_J(t) = \sum_{j=1}^n m_j(J)(1-t)^{-j}\) där \(m_j(J) = \#\{u \in G(J): m(u)=j\}\)
    • Så givet mingen för starkt stabilt J, enkel formel för Hilbertserie, Poincaré-Bettiserie
    • Funkar även för stabila monomideal: \(u \in G(J)\) med \(m(u) = j\), \(i< j\), \(x_i\) delar inte u, medför \((x_i/x_j)u \in J\)

Gotzmann

  • Alla Hilbertfunktioner för graderade cykliska E-moduler \(E/J\) antas av kvoter av monomideal, tom av J starkt stabila, tom av lexsegment J
  • För Hilbertfunktioner gäller: Om J gen i grader \(\le s\), och \(h_{j}= dim_k (E/J)_j\) så om \(h_{s+1} = \partial(h_s)\) (Kruskal-Katona begränsningen) så \(h_{t+1 }= h_t\) för \(t \ge s\)
  • Gotzmann theorems av Avramova-Herzog-Hibi
  • Varianten i symmetriska algebran visad av just Gotzmann

Hilbertfunktioner för graderade delmoduler till fria av ändlig rang

  • Generalisering till grad kvot \(F/M\), \(F = \oplus_{i=1}^r Eg_i\), \(g_i\) grad \(f_i\), M delmodul homogen map denna gradering
  • Amata, Crupi, “A generalization of Kruskal-Katona’s theorem”
  • Alla Hilbertserier antas av kvoter av monomiella moduler (initialmodul, Gröbnerbaser för moduler, inte djupsinnigt)
  • Kan hålla sig till “lexdelmoduler” (djupsinnigt)
  • KK_modules_1.png
KK_modules_2.png
  • Styr växt av av f-vektorer för r-tupler av simpliciella komplex
  • Exempel (Från Amata-Crupi exterior_modules_M2.pdf)

    setEcho stdio    
    loadPackage("ExteriorModules")    
    E=QQ[e_1..e_4,SkewCommutative=>true]
    F = E^3
    hs ={3,12,16,6,0}
    lexModule(hs,F)
    F2 = E^{2,0,-2}
    hs2 = {1,4,5,4,6,5,6,3,0}
    lexModuleBySequences(hs2,F2)               
    
    setEcho stdio    
    loadPackage("ExteriorModules")    
    
    o2 = ExteriorModules
    
    o2 : Package
    E=QQ[e_1..e_4,SkewCommutative=>true]
    
    o3 = E
    
    o3 : PolynomialRing, 4 skew commutative variable(s)
    F = E^3
    
          3
    o4 = E
    
    o4 : E-module, free
    hs ={3,12,16,6,0}
    
    o5 = {3, 12, 16, 6, 0}
    
    o5 : List
    lexModule(hs,F)
    
    o6 = image | e_1e_3 e_1e_2 e_2e_3e_4 0         0         0            |
               | 0      0      0         e_1e_2e_4 e_1e_2e_3 0            |
               | 0      0      0         0         0         e_1e_2e_3e_4 |
    
                                 3
    o6 : E-module, submodule of E
    F2 = E^{2,0,-2}
    
          3
    o7 = E
    
    o7 : E-module, free, degrees {-2, 0, 2}
    hs2 = {1,4,5,4,6,5,6,3,0}
    
    o8 = {1, 4, 5, 4, 6, 5, 6, 3, 0}
    
    o8 : List
    lexModuleBySequences(hs2,F2)               
    
    o9 = image {-2} | e_1e_3 e_1e_2 e_2e_3e_4 0      0         0         |
               {0}  | 0      0      0         e_1e_2 e_1e_3e_4 0         |
               {2}  | 0      0      0         0      0         e_1e_2e_3 |
    
                                 3
    o9 : E-module, submodule of E
    

Fröbergförmodan i yttre algebran

  • Hilbertserien för \(E/I\) där \(I\) genererad av generiska former
  • Icke-trivialt redan för \(I=(f)\) principalt
  • S-Moreno Socías: \(I=(f)\), \(|f| = d\), \(d\) jämn
  • Hilbertserie \[ H_{E/I}(t)= \lceil (1-t^d)(1+t)^n \rceil \]
  • \(E \to E\) mult med \(f\) har alltid full rang, dvs injektiv eller surjektiv
  • Räcker visa gäller för mindre generisk form, summa alla monom
  • Nicklasson-Lundqvist: \(I=(f)\), \(|f|=d\), \(d\) udda
  • Komplicerad olikhet för \(H_{E/I}(t)\) Nicklasson_ineq.png
  • Gäller med likhet för \(d=1\), \(d=3\) och \(n \le 17\), \(n \neq 9\), \(d=5\) och \(n \le 13\), \(d=7\) och \(n \le 11\)

Kvadratfria algebra, Artinifierade Stanley-Reisner

Kvadratfria algebran

  • \(kar(k) \neq 2\)
  • \(R = k[x_1, \dots , x_n]/(x_1^2, \dots, x_n^2)\)
  • Isomorf som fingraderad k-vektorrum med yttre algebran, annan multiplikation, kommutativ snarare än skevkommutativ

Artinifierade Stanley-Reisner

  • För \(\Delta\) simpliciellt komplex så är \(k[\overline{\Delta}] = R/I_\Delta\), där \(I_\Delta\) genereras av “icke-simplexen”
  • Enkel mult i kvoten: \(x_\sigma * x_\tau = x_{\sigma \cup \tau}\) om \(\sigma \cap \tau = \emptyset\), annars 0
  • Hilbertserie = f-vektor, förstås
  • Emil Sköldberg: Poincaré-Bettiserien lika med motsvarighet för yttre algebran, ej självklart.

Exempel: trunkering av aritmetiska funktioner, unitär faltning

  • The ring of arithmetical functions with unitary convolution: the [n]-truncation
  • The ring of arithmetical functions with unitary convolution: General Truncations
  • \(f: \ZZ^+ \to \CC\)
  • “aritmetisk funktion”
  • Vektorrum U
  • Flera möjliga faltningsprodukter (Narkiewiscz)
  • Dirichletfaltning vanligast (kommer sen)
  • Unitär faltning: \((f*g)(n) = \sum_{a \oplus b = n} f(a)g(b)\) där \(a \oplus b = ab\) om \(sgd(a,b)=1\), annars 0
  • Kommutativ \(\CC\)-algebra U
  • \(e_n\) = karakteristisk funktion på n
  • \(f = \sum_n f(n)e_n\)
  • \(n = q_1 \cdots q_r\), \(q_j\) = primpotens, då \(e_n = e_{q_1} \cdots e_{q_r}\)
  • Intressant att studera trunkering \(U_N = \{f \in U: f(m) = 0 \text{ för } m > N\}\) (med liten förändring av mult)
  • U = invers gräns \(U_N\)
  • \(U_N\) = kvot av “potensserie-ring” i oändligt många variabler, bara ändligt många överlever, Artinsk, kvot av polynomring över \(e_{q}\) för \(q \le N\), q primpotens
  • \(\Delta(N) = \{\{q_1,\dots , q_r\} : q_1 \cdots q_r \le N, q_i \text{ distinkta primpotenser}\}\)
  • \(U_N = \CC[\overline{\Delta(N)}]\)
  • \(\Delta(N)\) skiftad, mer eller mindre (byt variabler i rätt grupp)
  • \(\Delta(N)\) har \(\pi'(N)\) vertex. I ett-skelettet är några av dem isolerade, resten bildar en smh komponent
  • \(\dim \Delta(N) = \ell(N)-1\), där \(\ell(N)\) största heltal så att \(\prod_{j=1}^{\ell(N)}p_j \le N\), \(p_j\) j:e primtalet
  • f-vektor \((f_{-1},f_0, f_1, \dots) = (\pi_0(N), \pi_1(N), \pi_2(N), \dots)\) där \(\pi_k(N)\) ant pos heltal \(\le N\) med k distinkta primfaktorer
  • homologisk grad (dvs max i så att reducerad \(H_i(\Delta(N),\ZZ) \neq 0)\) är ℓ(2N)-2, också max hom grad för alla restriktioner
  • \(\ell(N)\) växer långsamt, som \(\log(N)/W(\log(N))\), W Lambert-W,
  • h-vektor : \(p(t)\) GF till f-vektorn, också Hilbert till \(\CC[\overline{\Delta(N)}]\). Då blir \(p(t/(1-t)) = (1-t)^{-\ell(N)} \sum_{j=0}^{\ell(N)}h_j t^j\), Hilbertserien till \(\CC[\Delta(N)]\), Stanley-Reisner
  • Vi får att \(h_0 = 1\), \(h_1 = -\ell(N) + \pi'(N)\), \(h_2 = \binom{\ell(N)}{2} - (\ell(N) -1)\pi'(N) + \pi_2(N)\)
  • Ger tyvärr inga enkla svar på problem inom analytisk talteori, men föreslår spörsmål
  • \(h_2 < 0\) för stora N, alltid negativt?
  • h2.png
  • Sockeln av \(U_N\) spänns av alla \(e_k\) som svara mot facetter i \(\Delta(N)\)
  • \[\lim_{N \to \infty} \frac{\dim S(U_N)}{N} = 1 - 1/2 + \sum_{j=1}^\infty \frac{\frac{1}{p_j} - \frac{1}{p_{j+1}}}{\prod_{m=1}^j p_m} \approx 0.60771436 \]
  • För \(N > 2\), \(U_N\) ej Gorenstein, men för \(N = 6,7,8,9,40\) så Hilbertfunktionen symmetrisk. Alla fall?

Multikomplex, symmetriska algebran

Definition av multikomplex

  • Multimängd \(\{1,1,3,4,4\}\) på \([5]\) kodas som tuppel \((2,0,1,2,0) \in \NN^5\)
  • Simplex \(\{1,4,5\}\) kodas som 0-1-vektor \((1,0,0,1,1) \in \NN^5\)
  • \(\NN^n\) har naturlig partialordning, direkt prod av \((\NN, \le)\), \((a_1, \dots ,a_n) \le (b_1, \dots, b_n)\) omm \(\forall i: a_i \le b_i\)
  • \(\NN\) fri abelsk monoid under addition, partialordningen \(a \le b\) omm \(b = a +c\) något \(c \in \NN^n\)
  • Multikomplex M: ordningsideal i \((\NN^n, \ge)\)
  • Kan vara ändliga eller oändliga
  • Simpliciella komplex specialfall
  • \(|(a_1, \dots , a_n)| = \sum_i a_i\)
  • \(M_d = {a \in M : |a| = d}\)
  • m-vektor \((m_0, m_1, m_2, \dots) \in \NN^\infty, m_d = \dim_K(M_d)\)

Monomideal i symmetriska algebran

  • Multiplikativ monoid T av monom, \(T = {x^a : a \in \NN^n}\)
  • \(u_1 \le u_2\) omm \(u_2 = u_1 t\) något \(t \in T\)
  • M svarar mot mängd monom, så att varje delare till \(u \in M\) också ligger i M
  • \(S = T \ M\) filter i T, monoidideal, \(u \in S ,t \in T \to tu \in S\)
  • \(R = k[T]\) monoidalgebran, \(J = span_k(S)\) monomideal
  • Dickson: J ändligt genererad, unikt bestämda mingen. S har ändligt många minimala element. S ändlig union translat av \(\NN^n\)
  • Kvotring \(R/J\) k-vektorrum med M som bas. Multiplikation: addition av exponenter om detta i M, eller noll, om summan ej i M.
  • \(\ZZ\)-graderade \(Hilb(R/J)(t) = \sum_d m_d t^d\), rationell potensserie, pol i ettan
  • Kan även studera fingraderade Hilbertserien, rationell, nämnare \((1-x_1)(1-x_2) \cdots (1-x_n)\)
  • Låt \(Koz(J,b) = \{F \subset [n] : x^{b-F} \in J\}\) simpliciellt komplex
  • \(\beta_{j,b}(J) =\) dim multigrad b av \(Tor_j(K[T]/J,K)\)
  • \(\beta_{j,b}(J) = dim H_{j-1}(Koz(J,b); K)\), reducerad homologi

Stanley-Reisnerringen, multikomplex med stöd på givet S.K.

  • För multimängd/tuppel \(a= (a_1, \dots , a_n)\), stöd \(supp(a) = \{i: a_i > 0\} \subset [n]\)
  • Givet simpliciellt komplex \(\Delta\) på \([n]\), bilda multikomplex \(M(\Delta)\), cylindern över \(\Delta\)
  • \(M(\Delta) = \{a \in \NN^n : supp(a) \in \Delta\}\)
  • \(I(\Delta)\) = monomidealet gen av \(T \ M(\Delta)\). Kommer att vara minimalt genererat av kvadratfria monom
  • Stanley-Reisnerringen \(K[\Delta] = K[T]/I(\Delta)\)
  • Om \(\Delta\) har f-vektor \((f_{-1}, f_0, f_1, \dots, f_{n-1})\), \(\dim(\Delta)=d-1\), så \[(H(K[\Delta])(t) = (1-t)^{-d}(h_0 + h_1 t + \dots + h_d t^d) = \sum_{j=0}^d \frac{f_{j-1}t^j}{(1-t)^j},\] där \((h_0, \dots ,h_d)\) är h-vektorn
  • \(h_k = \sum_{j=0}^k \binom{d-j}{k-j} f_{j-1}\)
  • Hochster: b nu kvadratfri multigrad, inducerade delkomplexet \(\Delta[b] = \{s \in \Delta: s \subset b\}\), får \[\beta_{j,b}(K[\Delta]) = \dim_K H^{|b| - j - 1}(\Delta[b]; K) \]

Initialideal

  • Termordning på T: total extension \(\prec\) av delbarhet så att \(m_1 \prec m_2 implies u m_1 \prec um_2\) för alla monom u
  • lex, deglex, degrevlex
  • Klassificerade av Robbiano
  • Kommer anta att \(\prec\) sorterad dvs \(x_1 \succ x_2 \succ \cdots \succ x_n\)
  • f polynom, \(in_\succ(f)\) största monom i supp(f)
  • I ideal, \(in_\succ(I) = \{in_\succ(f) : f \in I\}\)
  • Beror av \(\succ\)
  • Räcker inte, om \(I = (f_1, \dots , f_r)\), att ta \((in(f_1), \dots, in(f_r))\), kompletteringsförfarande, Gröbnerbaser
  • M = monom inte i \(in(I)\)
  • \(K[T] = M \oplus in(I) = M \oplus I\) som K-vektorrum
  • Så om I homogent så \(K[T]/I\) och \(K[T]/in(I)\) samma Hilbertserie
  • Olikheter för graderade bettitalen, flata familjer, homologisk perturbationsteori

Macaulays sats

  • \(S = K[T]\), I homogent ideal, Hilbertfunktion \(H(i) = dim_K((S/J)_i)\)
  • \(H_i = N\)
  • finns unik expansion

\[ N = {\binom {n_{i}}{i}}+{\binom {n_{{i-1}}}{i-1}}+\ldots +{\binom {n_{j}}{j}}, \quad n_{i}>n_{{i-1}}> \dots >n_{j}\geq j\geq 1. \]

  • Nu definierar vi en funktion uppi genom

\[ upp_i(N) = {\binom {1+n_{i+1}}{i+1}}+{\binom {1+n_{i-1}}{i}}+\ldots +{\binom {1+n_{j}}{j+1}}.} \]

  • Macaulay:
    • En följd \((c_0, c_1, c_2, \dots)\) är en m-följd om \(c_0 = 1\) och \[ \forall i: c_{i+1} \le upp_i(c_i) \]
    • Hilbertfunctioner är O-följder, alla O-följder är Hilbertfunktioner, \(c_1 =\) inbäddningsdim
    • Alla Hilbertfunktioner realiseras av kvoter med lexsegmentideal

Gotzmanns persistence theorem

  • I homogent ideal i S, \(I' = \langle I_{\le d} \rangle\) idealet gen av allt i I av grad \(\le d\)
  • Antag vi “slår i taket” i grad i, dvs \(H(S/I')(d+1)= c_{d+1} = upp_i(c_d)\)
  • Då \[ c_{d + s} = \binom{s+n_{i+1}}{i+s} +\binom{s+n_{i-1}}{i+s-1}+ \ldots +\binom{s+n_{j}}{j+s} \]
  • Likhet i olikheten för alla grader \(d+s\), \(s \ge 0\).

Generiska initialideal

Def, verkan av GL(V)

  • \(GL(V)\) verkar på V, utsträck till verkan på linjärformer, ger verkan på \(S=K[T]=K[x_1, \dots ,x_n]\)
  • ideal I, \(g \in GL(V)\), \(g.I\) nytt ideal
  • \(\prec\) termordning
  • \(gin_\prec(I) = in_\prec(g.I)\) för generiskt g
  • Samma hilbertserie, andra bettital, olikheter

Starkt stabila monomideal

  • Verkan av Borel

    För varje ≺ så blir gin(I) ett starkt stabilt monomideal J.

    • \(u.J = J\) om u övertriangulär
    • \(x_i m \in J\) medför \(x_j m \in J\) för \(j < i\)
  • Kombinatoriska egenskaper
    • Komplementet blir skiftat multikomplex, \[ a \in M, a_i > 0 \implies + a + (0,\dots , 0,-1,0, \dots , 0,1,0, \dots, 0) \in M \]
    • Monom i starkt stabila J filter m.a.p delbarhet samt \(x_1 > x_2 > \cdots > x_n\),
    • Filter m.a.p. kombinerad partialordning, On some Partial Orders Associated to Generic Initial Ideals
    • starkt_stabil.png
    • Relation till numeriska partitioner, Youngs lattice
    • Beräkning av “Boreldelmängder” förekommer i litteraturen
  • Upplösningar, bettital
    • Eliahou-Kervaire
    • I starkt stabilt monomideal, \(G(I)\) mingen
    • \(u \in G(I)\), \(m(u) = \max i: x_i | u\)
    • (Enkelgraderade) Bettital \(\beta_q(I) = \sum_{u \in G(I)} \binom{m(u)-1}{q}\)
    • (Enkelgraderad) Hilbertserie \(\sum_{u \in G(I)} t^{|u|}(1-t)^{m(u)-n-1}\)
    • Poincaré-Bettiserie med kollapsad gradering \[P(Tor_*^S(I,K),t) = \sum_{u \in G(I)} (1+t)^{m(u)-1}\]
    • Graderat: låt \(b_{i,d} = \#\{u \in G(I) : m(u)=i, |u|=d\}\). Då \[P(Tor_*^S(I,K),t,u) = \sum_{i=1}^n (1+tu)^{i-1}\sum_{j}b_{i,j} u^j\]
    • \(S/I\) Golod (Irena Peeva, aramova, Herzog)
    • \[P(Tor_*^{S/I}(K,K),t,u) = (1+t)^n (1-t^2 (\sum_{i=1}^n(1+tu)^{i-1} \sum_{j}b_{i,j} u^j))^{-1}\]
  • Exempel: trunkering av aritmetiska funktioner
    • truncations of the ring of number-theoretic functions
    • \(\Gamma = \{f: \ZZ_{+} \to K\}\), aritmetiska funktioner, vektorrum
    • Dirichletfaltning: \((f*g)(n) = \sum_{ab=n}f(a)g(b)\)
    • \(e_n\) = kar.f. på n, \(f = \sum_n f(n)e_n\)
    • \(x_i = e_{p_i}\), \(p_i\) i:e primtalet
    • \(e_n\) = monom i \(x_i\), primtalsfaktorisering
    • \(\Gamma = K[ [x_1, x_2, \dots , ]]\) formella potensserier oändligt många variabler
    • Cashwell-Everett: UFD
    • Trunkering: \(\Gamma_N =\{f \in \Gamma: f(k) = 0 \text{ för } k > N\}\)
    • Modifierad mult: \(e_a*e_b = e_{ab}\) om \(ab \le N\), 0 annars
    • \(\Gamma = \lim \Gamma_n\)
    • \(\Gamma_N\) artinsk monomalgebra \(K[x_1, \dots, x_{r}]/I_N\) , IN starkt stabilt (omvänt ordning på variablerna) monomideal
    • Minimiala generatorer G(IN) går att hitta, de med minsupp v svarar mot icke-negativa heltalslösningar \((b_v, \dots , b_r)\) till \[ \log(N) - \log(p_v) < \sum_{i=v}^r b_i \log(p_i) \le \log(N) \]
    • Hilbertserien \(\sum_i d_i t^i\), \(d_i =\) antal \(w \le N\) med \(\lambda(w)=i\), antal primtal i faktorisering
    • Poincaré-Betti av olika slag
    • Exempel (N=5)

      setEcho stdio        
      S=QQ[x_1..x_3]
      I5 = ideal(x_1^3, x_1*x_2, x_1*x_3, x_2^2,x_2*x_3,x_3^2)
      betti res I5
      R = S/I5        
      basis(R)
      betti res coker vars R    
      
      setEcho stdio        
      S=QQ[x_1..x_3]
      
      o2 = S
      
      o2 : PolynomialRing
      I5 = ideal(x_1^3, x_1*x_2, x_1*x_3, x_2^2,x_2*x_3,x_3^2)
      
                   3               2         2
      o3 = ideal (x , x x , x x , x , x x , x )
                   1   1 2   1 3   2   2 3   3
      
      o3 : Ideal of S
      betti res I5
      
                  0 1 2 3
      o4 = total: 1 6 8 3
               0: 1 . . .
               1: . 5 6 2
               2: . 1 2 1
      
      o4 : BettiTally
      R = S/I5        
      
      o5 = R
      
      o5 : QuotientRing
      basis(R)
      
      o6 = | 1 x_1 x_1^2 x_2 x_3 |
      
                   1       5
      o6 : Matrix R  <--- R
      betti res coker vars R    
      
                  0 1 2  3  4
      o7 = total: 1 3 9 27 81
               0: 1 3 8 22 60
               1: . . 1  5 20
               2: . . .  .  1
      
      o7 : BettiTally
      
    DirichletTrunc5.png

Lex/revlex initialideal av ideal gen av generiska former

Fröbergs förmodan

  • \(S =k[x_1, \dots , x_n]\), \(f_1, \dots, f_r\) “generiska former” av grader \(d_1, \dots, d_r\), \(I = (f_1, \dots ,f_r)\), \(R = S/I\)
  • Vad är Hilbertserien för \(R\)? För \(r \le n\) så uppenbarligen \[ \frac{\prod_{j=1}^r (1-t^{d_j})}{(1-t)^n} \]
  • För \(r > n\) knepigare
  • Fröbergs förmodan: \[ H_R(t) = \lceil \frac{\prod_{j=1}^r (1-t^{d_j})}{(1-t)^n} \rceil \] vilket betyder : vid första icke-positiva koeff, nolla den samt efterföljande
  • Anick: \(n=3\), Stanley: \(r=n+1\).
  • Nicklasson: alla \(d_i=d \ge 2\), \(n \ge 4\), \[ \binom{n+d-1}{d} -n < r \le \binom{n+d-1}{d} \] Då stämmer Fröbergs förmodan, dvs \[ H_R(t) = \lceil \frac{(1-t^d)^r}{(1-t)^n} \rceil \]