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()
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()
- 1-skelettet är en graf
simplicial_complexes.ProjectivePlane().graph().plot()
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()
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()
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()])
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()
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}
- Cirkeln
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 = 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()
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:
- \(\Delta_f\) är ett S.K.
- \(f=(f_0 , f_1 , \dots , f_{d-1})\) uppfyller binomialväxtvillkoren \(0 < f_{i+1} \leq \partial_{i+1}(f_{i})\)
- 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)])
- 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)])
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)
- 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?
- 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
- 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)
- 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)\)
- 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?
- 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
- 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
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 \]