Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology definitions deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory object of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: Cayley distance kernel

Bottom of Page

1 to 100 of 165

  1. <
  2. 1
  3. 2
  4. >
    • CommentRowNumber1.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021

    for completeness, to go alongside Mallows kernel

    v1, current

    • CommentRowNumber2.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021
    • (edited Apr 21st 2021)

    added statement and proof (here) that the Gershgorin radii of the Cayley distance kernel are all equal to

    r=e −λ⋅n∏k=0n−1(e λ+k)−1 r \;=\; e^{- \lambda \cdot n } \, \underoverset {k = 0} {n - 1} {\prod} \big( e^{\lambda} + k \big) - 1

    diff, v3, current

    • CommentRowNumber3.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    fixed the missing summand −1-1 in the above formula

    diff, v3, current

    • CommentRowNumber4.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    I’ve added a section describing an eigenvector of the Cayley distance kernel. Clearly this is positive for large enough λ\lambda.

    It needs checking.

    diff, v5, current

    • CommentRowNumber5.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    Things about other rows need saying, e.g., how sgnsgn is a homomorphism, etc., but I see that Urs is on the page now.

    • CommentRowNumber6.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    Thanks! I am done editing. Have just given it a Prop-environment and added some words on the proof.

    • CommentRowNumber7.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021
    • (edited Apr 22nd 2021)

    By the way, I got stuck with understanding the “quite nice proof” (according to one MO contributor) on math.se (here) of that Lemma.

    It starts out sounding really plausible, but when trying to write out this proof idea formally as a nested sum of permutations with increasing lower bound on their numbers of cycles, I got stuck.

    Stanley, in contrast, offers no less than four different proofs for this Lemma, none of which is as easy-looking as the “quite nice proof” on math.se . Makes me wonder if it’s maybe too nice to be true.

    • CommentRowNumber8.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    A bit heuristic, but maybe it does work. Imagine doing this for n=5n=5

    1 is placed in the first cycle: xx

    2 either starts a new cycle or is placed in the same cycle as 1: x+1x + 1

    3 either starts a new cycle or is fitted in an existing cycle. Either option from 2, there are 2 ways to place 3: x+2x + 2

    and so on.

    When adding a new element kk to existing cycles, one has to see that there are k−1k-1 choices, however the previous construction has gone.

    E.g if (12)(3) or (1)(2)(3) or (123), etc. then there are 3 places to add 4.

    • CommentRowNumber9.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    So that’s what the math.se author says. I see the logic in what he says, but not how this proves the lemma at hand:

    First: we are counting acual permutations, not their conjugacy classes.

    Second: You follow them in the vague “this gives xx”, or even just “colon xx”, which is not a formalizable instruction.

    Maybe these two ways of waving our hands somehow cancel out, but I don’t see it yet.

    The actual problem at hand is to manipulate the sum

    ∑σ∈Sym(n)x cycles(σ). \underset{ \sigma \in Sym(n) }{\sum} x^{cycles(\sigma)} \,.

    One way I can see to start out following the proof idea is to say: Every permutation has at least one permutation, so we can pull out a factor xx and write

    ∑σ∈Sym(n)x cycles(σ)=x((∑cycles(σ)>1x cycles(σ)−1)+(∑cycles(σ)=11)). \underset{ \sigma \in Sym(n) }{\sum} x^{cycles(\sigma)} \;=\; x \Big( \big( \underset{ cycles(\sigma) \gt 1 }{\sum} x^{cycles(\sigma) - 1} \big) + \big( \underset{ cycles(\sigma) = 1 }{\sum} 1 \big) \Big) \,.

    And then the idea would be to iterate this process on the first inner sum (pull out another factor of xx, get a sum over permutations with strictly more than 2 cycles and a constant number of permutations with strictly 2 cycles).

    This is beginning to roughly look like the kind of expression we are after. But not quite.

    Anyway, we don’t have to worry about this, as we have four good alternative proofs by Stanley.

    • CommentRowNumber10.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021
    • (edited Apr 22nd 2021)

    The point ’First’ is wrong. Hand-waving it may be, but it’s counting actual permutations.

    Maybe one way to go is to look at the expansion of x(x+1)…(x+n−1)x(x+1)\ldots(x + n-1) taking it as x(x+1)(x+1+1)...(x+1+…+1)x(x+1)(x + 1+1)...(x + 1 + \ldots+1).

    Claim, any term in the polynomial expansion corresponds to a unique permutation.

    Any such term is a sequence of xxs and 11s, where the latter appearing in the kkth place are indexed by a natural number between 11 and k−1k-1.

    Each of these is a recipe to form a unique permutation on nn elements. If xx appears kk times, there are kk cycles.

    E.g., for n=5n=5, given x⋅1 1⋅1 1⋅x⋅1 4x\cdot 1_1 \cdot 1_1 \cdot x \cdot 1_4, we form (132)(45).

    • CommentRowNumber11.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    In the other direction, given any permutation, arrange it so that for each cycle the lowest element heads it. Arrange cycles in order of the first entry.

    Then passing through 11 to nn, build a term of xxs and indexed 11s, according to whether a given kk heads a new cycle, xx, or occurs in the rrth available spot, 1 r1_r. There are k−1k-1 such available spots.

    • CommentRowNumber12.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    Sorry, I still need to ask: Why is your example not (123)(45)(123)(45)?

    What’s an “available slot”? If an element doesn’t start a new cycle, then we need to know (a) which of the existing cycles it is part of, and (b) in which position it occurs there.

    • CommentRowNumber13.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    Oh, I think I see it. Let me try to write it out as a proof…

    • CommentRowNumber14.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    The math.se answer puts it well enough. Placing the number kk, then look at the kkth term. If xx, start a new cycle; if 1 r1_r, place in the cycle containing rr to the right of it.

    • CommentRowNumber15.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    I was missing that we are looking at the underlying list obtained from normalized cycle notation by forgetting the brackets. I am writeing a proof that makes this explicit in usual mathematical proof style, so that even a dense person can follow it.

    • CommentRowNumber16.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021
    • (edited Apr 22nd 2021)

    So (announcing an edit from within the entry now) I wrote out a proof (here) of

    ∑σ∈Sym(n)e β⋅|Cycles(σ)|=∏k=0n−1(e β+k). \underset{ \sigma \in Sym(n) }{ \sum } e^{ \beta \cdot \left\vert Cycles(\sigma) \right\vert } \;=\; \underoverset {k = 0} {n-1} {\prod} \big( e^{\beta} + k \big) \,.

    following the idea given in Math.SE:a/92051 and thanks to your (David C.’s) amplifications here.

    diff, v7, current

    • CommentRowNumber17.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021
    • (edited Apr 22nd 2021)

    with that issue out of the way, further towards the question of positivity, I have added expression of the resulting sufficient Gershgorin bound for the Caylest distance kernel on Sym(n)Sym(n) to be positive at inverse temperature β=ln(N)\beta = ln(N):

    If I see correctly, the (sufficient) condition is that:

    (N+n−1)!(N−1)!⋅N n≤2 \frac{ (N + n - 1)! }{ (N - 1)! \cdot N^n } \;\leq\; 2

    Still need to prove that this has a solution NN for all nn….

    diff, v9, current

    • CommentRowNumber18.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    Maybe better to express this as follows, which makes it more manifest that this always has a solution for large enough NN:

    (N+n−1N−1)n!N n≤2 \left( { N + n - 1 } \atop { N -1 } \right) \frac{ n ! }{ N^n } \;\leq\; 2
    • CommentRowNumber19.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021
    • (edited Apr 22nd 2021)

    Stirling approximations come to mind.

    Or, pottering about

    (N+n−1)!(N−1)!⋅N n \frac{ (N + n - 1)! }{ (N - 1)! \cdot N^n }

    is N(N+1)…(N+n−1)N⋅N…N\frac{N(N+1) \ldots (N+n-1)}{N \cdot N \ldots N} which is certainly less than (N+n−1N) n=(1+n−1N) n(\frac{N+n-1}{N})^n = (1 + \frac{n-1}{N})^n.

    • CommentRowNumber20.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    Which clearly would be fine for N>n−12 1/n−1N \gt \frac{n-1}{2^{1/n}-1}. If that’s right.

    • CommentRowNumber21.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    Yes, that’s the way to go! I have turned it from an Example into a Proposition here

    diff, v9, current

    • CommentRowNumber22.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    The inequality in the proof of 3.4 was the wrong way around.

    diff, v10, current

    • CommentRowNumber23.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    Thanks. I am feeling dizzy. I”ll better call it quits and get some sleep.

    • CommentRowNumber24.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    Sleep well.

    I feel sure there’s something clever to say about the eigenvalues of this kernel. Seems close to the character theory of S nS_n. But maybe if Carlo achieves a symbolic computation for S 4S_4 that will be enough to show the pattern.

    • CommentRowNumber25.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    I don’t think the proof of (sgn(σ)) σ∈Sym(n)(sgn(\sigma))_{\sigma \in Sym(n)} as eigenvector is quite as immediate as presented, so I’ve added more of a proof.

    diff, v11, current

    • CommentRowNumber26.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    I thought you’d gone to bed! I need to tweak my proof but you’ve locked the page. So later, unless you do it first.

    • CommentRowNumber27.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    Just spotted a typo from my phone, over dinner. :-)

    • CommentRowNumber28.
    • CommentAuthorUrs
    • CommentTimeApr 23rd 2021
    • (edited Apr 23rd 2021)

    Added an Idea-section.

    diff, v13, current

    • CommentRowNumber29.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 23rd 2021

    I added something

    Since this result relies on sgn(σ)sgn(\sigma) being a multiplicative character, and the only multiplicative characters of a symmetric group are the trivial one and the sign, the other eigenvectors must be found by other means.

    n!−2n!-2 other eigenvectors then. Looking at the WolframAlpha calculation for S 3S_3, it seems clear that these other eigenvectors will be sparse, in this case pairs of points in the Cayley graph equidistant from every other point.

    • CommentRowNumber30.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 23rd 2021

    A bit more tweaking.

    diff, v14, current

    • CommentRowNumber31.
    • CommentAuthorUrs
    • CommentTimeApr 23rd 2021
    • (edited Apr 23rd 2021)

    added the statement and the (immediate) proof (here) that for all nn the kernel becomes indefinite at least as soon as β<ln(2)\beta \lt ln(2)

    diff, v17, current

    • CommentRowNumber32.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021
    • (edited Apr 24th 2021)

    If we want more results as in #31, then from section 4, knowing that in the case of S nS_n, e −β⋅n∏k=0n−1(e β−k)e^{- \beta \cdot n } \, \underoverset {k = 0} {n - 1} {\prod} \big( e^{\beta} - k \big) is an eigenvalue means that semi-positive definiteness fails in the range n−2<e β<n−1n-2 \lt e^{\beta} \lt n-1, and indeed for n−2a<e β<n−2a+1n- 2a \lt e^{\beta} \lt n -2a+1.

    Hmm, but then why can’t we replay your principal submatrix idea?

    If for S 4S_4, this eigenvalue is negative 2<e β<32 \lt e^{\beta} \lt 3, and for S 5S_5, it’s 3<e β<43 \lt e^{\beta} \lt 4 and 1<e β<21 \lt e^{\beta} \lt 2, doesn’t the 2<e β<32 \lt e^{\beta} \lt 3 carry through from the former case to the latter?

    • CommentRowNumber33.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    Is that completely obvious this result about preserving distances. Yes, one doesn’t need to use transpositions from outside S nS_n, but still it might be quicker to do so.

    • CommentRowNumber34.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    But then of course we know from the formula n−#cyclesn - #cycles that distances are preserved since as nn increases by 11, one more cycle is added under ii.

    • CommentRowNumber35.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    Re #33, #34: Good point, I have now changed the proof as you suggest, here

    • CommentRowNumber36.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    Continuing #32, that must be right: for S nS_n, positive semi-definiteness fails for e β<n−1e^{\beta} \lt n-1, except for integral values of e βe^{\beta}.

    • CommentRowNumber37.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021
    • (edited Apr 24th 2021)

    Yes, with Carlo we just had a similar discussion, from looking more at the fomulas for the eigenvalues:

    Apparently something really interesting happens in between the two bounds for the Cayley distance kernel that we established:

    We know

    • it’s indefinite for β<ln(2)\beta \lt ln(2)

    • it’s positive definite for β>n−12 1/n−1\beta \gt \frac{n-1}{ 2^{1/n} - 1}

    so it might be tempting to speculate that this is a monotonic situation. But far from it: Beyond these two extremes, apparently the Cayley distance kernel oscillates between indefniteness and positive definiteness, passing through positive semi-definity exactly (apparently) at the first few integer values of e βe^{\beta}.

    • CommentRowNumber38.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    Well, according to #36, it’s touching positive semi-definiteness at integer values, and then reverting to indefiniteness, never achieving positive definiteness untli after (n−1)(n-1). (Well, strictly I don’t even know that, but it’s at least as bad as that.)

    • CommentRowNumber39.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    Okay, I see, I was looking at another eigenvalue, thinking for a while it’s the smallest one. But yeah, that’s a good point worth recording…

    • CommentRowNumber40.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    I have added the formulas for the eigenvalues of the kernel on Sym(4)Sym(4) (here), kindly provided by a CAS oracle

    diff, v21, current

    • CommentRowNumber41.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    Good. So the first two are no surprise, here.

    What can we learn from the others? Low integer solutions.

    • CommentRowNumber42.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    no surprise

    I am impressed by how you are doing this. You should record/explain that in the entry?

    Can you see why these would necessarily have multiplicity 1, apparently?

    • CommentRowNumber43.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    Namely if we knew that (as seems to be the case) it is exactly these two types of eigenvalues that appear with unit multiplicity, then we could use the enhanced Gershgorin theorem of arXiv:1609.07439 to constrain away the rest in a smaller Gershgorin disc, and thus possibly get a tighter lower bound on β\beta at which the kernel becomes positive for good.

    • CommentRowNumber44.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    Okay, I checked out a table of conjugacy classes of Sym(4)Sym(4) (here) in order to decypher your lists of numbers.

    So I suppose the conjecture is that the first eigenvalue with multiplicity 1 is always given by the polynomial:

    • e −(n−1)βe^{-(n-1) \beta} times

    • sum over conjugacy classes of

    • number of elements in each class

    • times e βe^\beta to the power of

    • the product of the lengths of its cycles

    ?

    And the second with multiplicity one by the corresponding alternating sum.

    • CommentRowNumber45.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    Ah, no, that’s not the rule.

    I am stuck: What’s the rationale behind the item “8/4” in your string here?

    • CommentRowNumber46.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    The number in that conjugacy class, 3 13^1, so along with the 3 elements in class 2 22^2, that’s 11 elements at distance 2 from the identity.

    Anyway, the multiplicity 1 eigenvalues, are those we know for the trivial eigenvector and (sgn(σ)(sgn(\sigma). The former is always positive, a product with roots at negative integers; the latter is a product with roots at the first positive integers. So this gives alternating intervals as in #32.

    I should think that then the other eigenvalues kick in to make the complementary intervals be non-positive definite. From what you found for S 4S_4, it seems the other eigenvalues are also products with roots at low integers, including a negative one.

    • CommentRowNumber47.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    Presumably the multiplicities are to do with the squares of the representations sizes, so for S 4S^4, 1 2+1 2+2 2+3 2+3 2=241^2 + 1^2 + 2^2 + 3^2 + 3^2 = 24.

    There’s perhaps a way to go from a representation to a collection of eigenvectors all with the same eigenvalues.

    • CommentRowNumber48.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021
    • (edited Apr 24th 2021)

    I understand that you are adding the 3 elements of one conjugacy class to the 8 elements of another. What I am trying to ask is: Why, by which rule?

    Could you just say what your rule is? In the form of #44. How do you determine which conjugacy class contributes to which power in the polynomial?

    • CommentRowNumber49.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021
    • (edited Apr 24th 2021)

    The distance to ee, so (n - #cycles). Of course, 3 13^1 is a pair of cycles 3⋅13 \cdot 1, so at distance 4−24-2 from ee.

    • CommentRowNumber50.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    All due to Lemmas 4.2. and 4.10.

    • CommentRowNumber51.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    Maybe I have been chasing a shadow. You are just restating these Lemmas? I thought your symbols meant to hint at a conjectural pattern not yet captured by these. Okay, never mind then.

    • CommentRowNumber52.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 24th 2021

    What more could you want? We know that the left hand sides of those lemmas are eigenvalues, we know for which eigenvectors, and we know how to factorise them in the right hand sides. So then we know for which values of e βe^{\beta} they are negative.

    What you need now is something similar for the other eigenvalues. It seems pretty clear that two of them will be products of (e β±r)(e^{\beta} \pm r) for various integer values of rr. In the S 4S^4 case we’re seeing (e β−2)(e β−1)(e β+1)(e^{\beta} - 2)(e^{\beta} - 1)(e^{\beta} +1) and (e β+2)(e β−1)(e β+1)(e^{\beta} + 2)(e^{\beta} - 1)(e^{\beta} +1). I

    It’s pretty clear that for positive e βe^{\beta} until n−1n-1, positive semi-definiteness is achieved at integral values up to n−1n-1, otherwise non-positive definite. Then it turns positive definite thereafter.

    • CommentRowNumber53.
    • CommentAuthorUrs
    • CommentTimeApr 24th 2021

    I perfectly understand these lemmas, but was just trying to understand what seemed additional remarks you made that seemed mysterious to me. It might have added to the confusion that you mostly gave me verbless quarter-sentences as replies. But okay, that’s the perils of online communication. Glad it got clarified.

    I am to bed now. Hoping to see you tomorrow in further unravelling this curious story.

    • CommentRowNumber54.
    • CommentAuthorUrs
    • CommentTimeApr 25th 2021
    • (edited Apr 25th 2021)

    I have added a plot of the lowest eigenvalue on Sym(4)Sym(4), as a function of the exponentiated inverse temperature: here

    [ ah, need to improve these plot bounds…]

    diff, v23, current

    • CommentRowNumber55.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 25th 2021

    I added in my argument from #32.

    diff, v24, current

    • CommentRowNumber56.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 25th 2021

    Is the assumption still that β>0\beta \gt 0? Otherwise the plots show that e β=1e^{\beta} = 1 is to be included in points of positive semi-definiteness.

    Then, how to approach the eigenvectors other than the trivial one and sign? Did the calculation mentioned in #40 give the eigenvectors?

    With S 3S_3 one is just choosing pairs of points in the graph such that they are equidistant from the other four points.

    • CommentRowNumber57.
    • CommentAuthorUrs
    • CommentTimeApr 25th 2021

    Is the assumption still that β>0\beta \gt 0?

    I haven’t changed it. And indeed, it still says so in the file (above (1)).

    But it’s sure interesting to think about including the infinite-temperature case.

    • CommentRowNumber58.
    • CommentAuthorUrs
    • CommentTimeApr 25th 2021

    added in my argument

    Thanks! I have taken the liberty of articulating this as propositions with proofs (here and here)

    • CommentRowNumber59.
    • CommentAuthorUrs
    • CommentTimeApr 25th 2021

    It remains to find proof of that equation

    ∑σ∈Sym(n)sgn(σ)⋅e β⋅|Cycles(σ)|=∏k=0n−1(e β−k). \underset{ \sigma \in Sym(n) }{ \sum } sgn(\sigma) \cdot e^{ \beta \cdot \left\vert Cycles(\sigma) \right\vert } \;=\; \underoverset {k = 0} {n-1} {\prod} \big( e^{\beta} - k \big) \,.

    Probably best to multiply both side by (−1) n(-1)^n, thus changing (e β−k)(e^\beta - k) to (−e β+k)(-e^\beta + k) on the right. Then the previous form of the Lemma applies with weight −e β-e^{\beta} for each cycle and gives that the left hand side should be that sum with a prefactor of (−1)(-1) to the number of cycles plus (or minus) nn. Finally, if nn is even/odd, it must have an even/odd number of odd-length permutations, so that this last sign is equal to or minus the sign of (−1)(-1) to the number of even permutations, which is the signature.

    I guess that should work. Will write out a clean proof…

    • CommentRowNumber60.
    • CommentAuthorUrs
    • CommentTimeApr 25th 2021

    Okay, I have spelled out the proof of that Lemma: here

    diff, v26, current

    • CommentRowNumber61.
    • CommentAuthorUrs
    • CommentTimeApr 26th 2021
    • (edited Apr 26th 2021)

    Some random thoughts:

    I seems suggestive that the lower bound for positivity we found is

    e β≥n−12 1/n−1 e^{\beta} \;\geq\; \frac{n - 1}{ 2^{1/n} - 1 }

    while the actual lowest bound which is suggested by the explicit examples we have is

    e β≥n−11 e^{\beta} \;\geq\; \frac{n - 1}{ 1 }

    Maybe that similarity is just “symbology”, but it might suggest that the existing lower bound argument is on the right track and could be enhanced further.

    If we knew that the two special eigenvalues, the homogeneous distribition and the sign distribution, were the only two of multiplicity 1, then we could use the improved Gershgorin circle theorem of arXiv:1609.07439 to reduce the Gershgorin disc radius by half.

    Inserted into the previous argument this would give the bound

    e β≥n−13 1/n−1 e^{\beta} \;\geq\; \frac{n - 1}{ 3^{1/n} - 1 }

    which is not much of an improvement. Instead of “3” we’d want 2 n2^n. (They give a stronger reduction of the Gershgorin radius in their equation (3), but I am not sure if this can be put to use in our case.)

    But then, the worst part of the estimate may not be the size of the Gershgorin radius, but the step where we approximate

    N(N+1)⋯(N+n−1)N n≤(N+n−1N) n, \frac{ N(N+1) \cdots (N + n - 1) }{ N^n } \leq \left( \frac{ N + n - 1 }{ N } \right)^n \,,

    because that approximation is good when NN is much larger than nn, while close to our expected actual bound, N≥n−1N \geq n - 1, both are comparable.

    Maybe we need a more sophisticated estimate at this step.

    • CommentRowNumber62.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 26th 2021
    • (edited Apr 26th 2021)

    My hunch is that one should pursue what is special about the combinatorics of S nS_n, whatever it is that gives rise to results such as Lemma 4.1.

    We have two eigenvectors based on multiplicative characters, which give rise to very neat factorisations of polynomials with low integer roots.

    It look like the other eigenvectors are also connected to the representation theory of S nS_n, looking at the multiplicities as squares of the representation sizes, and these seem to give rise again to neat factorisations of polynomials, with slightly shifted integer roots.

    I think the eigenvalues expressed as polynomials in e βe^{\beta} will have roots generalizing the pattern for S 4S_4 of

    {−3,−2,−1},{−2,−1,1},{−1,0,1},{−1,1,2},{1,2,3}\{-3, -2, -1\}, \{-2, -1, 1\}, \{-1, 0, 1\}, \{-1, 1, 2\}, \{1, 2,3 \}.

    This might even be construed as containing additional entries of ’0’, so

    {−3,−2,−1,0},{−2,−1,0,1,},{−1,0,0,1},{−1,0,1,2},{0,1,2,3}\{-3, -2, -1, 0\}, \{-2, -1, 0, 1, \}, \{-1, 0,0, 1\}, \{-1, 0, 1, 2\}, \{0, 1, 2,3 \}.

    This tallies with the S 3S_3 case with roots

    {−2,−1},{−1,1},{1,2}\{-2, -1\}, \{-1, 1\}, \{1, 2\}

    which with the missing 00s is really

    {−2,−1,0},{−1,0,1},{0,1,2}\{-2, -1, 0\}, \{-1, 0, 1\}, \{0, 1, 2\}.

    In sum, roots of eigenvalues will be sequences of integers as above.

    • CommentRowNumber63.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 26th 2021

    Oh, why not just run the argument of Proposition 4.6, but instead of sgn(σ)sgn(\sigma), choose a representation of dimension rr represented as an r×rr \times r matrix. Then taking any of the r 2r^2 components will give you an eigenvector.

    That would explain the eigenvalue multiplicities so far, for S 3S_3, 1,1,41,1,4, for S 4S_4, 1,1,4,9,91, 1, 4, 9, 9.

    • CommentRowNumber64.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 26th 2021

    I don’t think #63 quite works, but there should be something in this vicinity.

    But off to do other things now - some metaphysics to supervise.

    • CommentRowNumber65.
    • CommentAuthorUrs
    • CommentTimeApr 26th 2021

    That seems a good observation about group representations!

    It reminds me that the non-abelian Fourier transformation also involves casting Fourier dual data in terms of irreps, and then the non-abelian Bochner theorem applies to extract a condition for positive definite kernels from this. (I have so far only glanced over references for this non-abelian Bochner theorem, recordered here).

    In total this may suggest that the answers we seek will be revealed under non-abelian Fourier transform.

    But, me too I need to go slower on this now. Am still working on equivariant infinity-bundles on the side.

    • CommentRowNumber66.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 26th 2021

    I have a feeling this is all worked out somewhere. How about this?

    We’re dealing with what they call the adjacency matrix of a Cayley color graph (p.17). α\alpha is a class function in our case, so Corollary 5.4 applies.

    Ex 5.3 deals with symmetric groups and transpositions, but there of the adjacency matrix of Cayley graph rather than Cayley color graph.

    The clues should all be in this paper.

    • CommentRowNumber67.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 26th 2021
    • (edited Apr 26th 2021)

    Yes, Corollary 5.4 gives you all the eigenvalues if you know the characters: 1d k∑ g:Gα(g)χ k(g)\frac{1}{d_k} \sum_{g: G} \alpha(g) \chi_k(g)

    • CommentRowNumber68.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 26th 2021

    Added something on finding all eigenvalues.

    diff, v30, current

    • CommentRowNumber69.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 26th 2021

    A quick look at S 5S_5 using #67, and it all seems to be working as predicted in #62.

    • CommentRowNumber70.
    • CommentAuthorUrs
    • CommentTimeApr 27th 2021

    Oh, wow. That would be the solution.

    Googling for “eigenvalues Cayley graphs” gives various similar references, for instance

    where the result you point to (their Theorem 2.1) is attributed to

    • L. Lovasz. Spectra of graphs with transitive groups Period. Math. Hungar., 6(2):191–195,1975 (pdf)
    • CommentRowNumber71.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 27th 2021

    No, their Theorem 2.1 is only for abelian groups where reps are 1-dimensional.

    Theorem 2.2 concerns general finite groups.

    • CommentRowNumber72.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 27th 2021
    • (edited Apr 27th 2021)

    We want Theorem 2.6.

    The note after is relevant too. [Perhaps not so relevant since it concerns largest eigenvalue.]

    • CommentRowNumber73.
    • CommentAuthorUrs
    • CommentTimeApr 27th 2021

    Thanks, right. I should take time now to actually read this…

    • CommentRowNumber74.
    • CommentAuthorUrs
    • CommentTimeApr 27th 2021
    • (edited Apr 27th 2021)

    The discussion and proof in Section 4.1 of

    is nice (clear and concise). For what it’s worth, they confirm (p. 40) the relation to the non-abelian Fourier transform as guessed in #65, even if they don’t expand on it.

    Maybe we should record this in an entry Cayley graph spectra.

    • CommentRowNumber75.
    • CommentAuthorUrs
    • CommentTimeApr 27th 2021
    • (edited Apr 27th 2021)

    For what it’s worth, I have used the character formula for Cayley graph spectra to improve the lower bound on positivity (this Prop.) from e β≥n−12 1/n−1e^\beta \geq \frac{n-1}{2^{1/n} - 1} to e β≥n−13 1/n−1e^\beta \geq \frac{n-1}{3^{1/n} - 1}.

    (Did this by appending a paragraph to the previous proof. Not the most elegant way to write this, but it should work.)

    diff, v33, current

    • CommentRowNumber76.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 28th 2021

    I think the next step is into the world of symmetric functions meets characters for S nS_n. Some course notes are here.

    the characters of irreducible representations correspond to Schur polynomials

    • CommentRowNumber77.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 28th 2021
    • (edited Apr 28th 2021)

    So something like: for S nS_n, the Schur function s λs_{\lambda} corresponding to rep λ\lambda is s λ(x 1,…,x n)=1n!∑ σ∈S nχ λ(σ)p σ(x 1,…,x n)s_{\lambda}(x_1, \ldots, x_n) = \frac{1}{n!} \sum_{\sigma \in S_n} \chi_{\lambda} (\sigma) p_{\sigma}(x_1, \ldots, x_n),

    where p σ(x 1,…,x n)=∏p λ ip_{\sigma}(x_1, \ldots, x_n) = \prod p_{{\lambda}_i}, for λ i\lambda_i the cycle lengths in σ\sigma, and p k(x 1,…,x n)=x 1 k+…+x n kp_k(x_1, \ldots, x_n) = x_1^k + \ldots +x_n^k.

    Then setting each x ix_i as xx,

    s λ(x,…,x)=1n!∑ σ∈S nχ λ(σ)∏p λ i(x,…,x)s_{\lambda}(x, \ldots, x) = \frac{1}{n!} \sum_{\sigma \in S_n} \chi_{\lambda} (\sigma) \prod p_{{\lambda}_i} (x, \ldots, x)

    So s λ(x,…,x)=1n!∑ σ∈S nχ λ(σ)∏(nx λ i)=1n!∑ σ∈S nχ λ(σ)n #Cyclesx ns_{\lambda}(x, \ldots, x) = \frac{1}{n!} \sum_{\sigma \in S_n} \chi_{\lambda} (\sigma) \prod (n x^{\lambda_i}) = \frac{1}{n!} \sum_{\sigma \in S_n} \chi_{\lambda} (\sigma) n^{#Cycles} x^n.

    The RHS is close to what’s needed, so we just need s λ(x,…,x)s_{\lambda}(x, \ldots, x) to have a nice simple factorization.

    • CommentRowNumber78.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 28th 2021

    Hmm, that only seems to allow nn as exponentiated by #cycles# cycles.

    Anyway, something in this vicinity is right. But I have to something else now.

    • CommentRowNumber79.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 28th 2021
    • (edited Apr 28th 2021)

    Oh, but why not then look at s λ(x,…,x,0,…,0)s_{\lambda}(x, \ldots, x, 0, \ldots, 0), the first tt entries being xx.

    Then s λ(x,…,x,0,…,0)=1n!∑ σ∈S nχ λ(σ)t #Cyclesx ns_{\lambda}(x, \ldots, x, 0, \ldots, 0) = \frac{1}{n!} \sum_{\sigma \in S_n} \chi_{\lambda} (\sigma) t^{#Cycles} x^n.

    • CommentRowNumber80.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 28th 2021

    By the way, this was gleaned from Def. 2 of this post with further info from this one.

    • CommentRowNumber81.
    • CommentAuthorUrs
    • CommentTimeApr 28th 2021

    Thanks, looks promising!

    So the idea now is that the Schur functions know the eigenvalues of the Cayley distance kernel at just those magical integer values e β∈{0,1,⋯,n−1}e^{\beta} \in \{0,1, \cdots, n-1\} (and at e β=ne^\beta = n ) for which we still want to show that they are all non-negative (which will imply that they are all zero, by what we already know).

    • CommentRowNumber82.
    • CommentAuthorUrs
    • CommentTimeApr 28th 2021

    But wait, that’s the proof: The Schur polynomial is homogeneous, so your expressions in #79 vanish.

    • CommentRowNumber83.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 28th 2021

    Hmm, but the example here has s (2,2,0)s_{(2,2,0)} such that s (2,2,0)(x,x,0)=x 4s_{(2,2,0)}(x,x,0) = x^4.

    But certainly there will be plenty of 0 eigenvalues around, and the rest positive.

    • CommentRowNumber84.
    • CommentAuthorUrs
    • CommentTimeApr 28th 2021

    Oh, I see my mistake. Right. Need to spell this out for myself with more patience.

    • CommentRowNumber85.
    • CommentAuthorUrs
    • CommentTimeApr 28th 2021
    • (edited Apr 28th 2021)

    But let’s see:

    It should be sufficient to know that the minimal eigenvalues at e β∈{1,⋯,n−1}e^{\beta} \in \{1,\cdots, n-1\} are non-negative to deduce that they vanish:

    Because we already know that for e β∈(0,1)∪(1,2)∪⋯(n−2,n−1)e^\beta \in (0,1) \cup (1,2) \cup \cdots (n-2,n-1) they are negative, so by continuity they can at most become zero in between.

    • CommentRowNumber86.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 28th 2021

    But we know that the character signsign gives 00 at these integers from Lemma 4.2. Presumably the associated Schur polynomial involves mononomials such as x 1x 2…x nx_1 x_2 \dots x_n.

    • CommentRowNumber87.
    • CommentAuthorUrs
    • CommentTimeApr 28th 2021

    Not sure what then “but” refers to. I just meant to say that your argument seems to give the desired proof already even without needing to know anything further about the values of the polynomials, not needing my broken argument in #82.

    • CommentRowNumber88.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 28th 2021

    True.

    And that’s right about eigenvalues being non-negative at 1,…,n−11, \ldots, n-1 isn’t it? We just need the coefficient of the monomial s λ(x,…,x,0,…,0)s_{\lambda}(x, \ldots, x, 0, \ldots, 0) to be non-negative, and that’s assured by the form of Schur polynomials as sums of terms as here.

    • CommentRowNumber89.
    • CommentAuthorUrs
    • CommentTimeApr 29th 2021
    • (edited Apr 29th 2021)

    I have now typed out (here) in full detail (with all lemma material behind hyperlinks) this proof that e −β⋅d Ce^{- \beta \cdot d_C} is positive semi-definite on Sym(n)Sym(n) for e β∈{1,2,⋯,n−1}e^{\beta} \in \{1,2, \cdots, n-1\} (and at least not indefinite for e β=ne^\beta = n).

    This is great.

    It is curious that, when we started this discussion last year, there was the worry that β=ln(2)\beta = ln(2) might not work for large nn, and now it’s instead the low values of ln(N)ln(N) for which we have proof that they work for all nn, while we have a gap of intermediate values n<e β<n−13 1/n−1n \lt e^\beta \lt \frac{n-1}{3^{1/n}-1} for which we don’t know anything for sure yet.

    diff, v37, current

    • CommentRowNumber90.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 29th 2021
    • (edited Apr 29th 2021)

    Looking good!

    Don’t we know that it’s positive definite for e β=ne^{\beta} = n? The Schur polynomial s λ(x,…,x)s_{\lambda}(x, \ldots, x) must be ax na x^n, for some positive integer aa.

    Our suspicion is surely that it’s positive definite for e β>n−1e^{\beta} \gt n-1.

    My hunch is that where the eigenvalues for 11 and signsign are ∏k=0n−1(e β+k)\underoverset {k = 0} {n - 1} {\prod}\big(e^{\beta} + k \big) and ∏k=0n−1(e β−k)\underoverset {k = 0} {n - 1} {\prod}\big(e^{\beta} - k \big), that the others are ∏k=−sn−s−1(e β+k)\underoverset {k = -s} {n -s -1} {\prod}\big(e^{\beta} + k \big) .

    • CommentRowNumber91.
    • CommentAuthorUrs
    • CommentTimeApr 29th 2021

    On positivity: I see, right, since for e β=ne^\beta = n none of the arguments vanish. SO I have reworded statement and proof, to account for this.

    diff, v38, current

    • CommentRowNumber92.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 29th 2021

    What about the principal submatrix idea?

    Say for a given nn, I’m wondering about definiteness for e β=me^{\beta} = m, where n<mn \lt m. But if it were other than positive definite there, then for S mS_m, it wouldn’t be positive definite at e β=me^{\beta} = m. But we know that this isn’t the case. So for S nS_n, the kernel is positive definite for integer values ≥n\ge n.

    • CommentRowNumber93.
    • CommentAuthorUrs
    • CommentTimeApr 29th 2021

    Good point! Yes.

    • CommentRowNumber94.
    • CommentAuthorUrs
    • CommentTimeApr 29th 2021

    With that out of the way (!), it’s time to look again at Bar-Natan’s proof that all horizontal weight systems are partitioned Lie algebra weight systems (arXiv:q-alg/9607001), where he uses the fundamental 𝔤𝔩(n)\mathfrak{gl}(n)-weight systems (which we now know are positive-semi definite) to build all other weight systems on horizontal chord diagrams.

    The construction he uses is deeply permutation-theoretic, so your geometric group theory expertise might just keep applying if we now ask: Can we characterize the convex space of all semi-positive weight systems?

    We now know that the convex span of the fundamental 𝔤𝔩(n)\mathfrak{gl}(n)-weight systems is a convex subspace, and we know from Bar-Natan that the ambient linear space may neatly be expressed through just fundamental 𝔤𝔩(n)\mathfrak{gl}(n)-weight systems (with bells and whistles added), so it is not out of the question that some geometric group theory keeps applying in this more ambitious question.

    • CommentRowNumber95.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 30th 2021

    Sounds like this will need quite a lot more preparation.

    We now know that the convex span of the fundamental 𝔤𝔩(n)\mathfrak{gl}(n)-weight systems is a convex subspace

    Is this written out somewhere?

    • CommentRowNumber96.
    • CommentAuthorUrs
    • CommentTimeApr 30th 2021

    This was the starting point of the note that got our discussion started here last year. But I’ll send you a polished update.

    • CommentRowNumber97.
    • CommentAuthorDavid_Corfield
    • CommentTimeMay 6th 2021
    • (edited May 6th 2021)

    Let’s consider my hunch from above:

    Just as the eigenvalues for 11 and signsign are ∏k=0n−1(e β+k)\underoverset {k = 0} {n - 1} {\prod}\big(e^{\beta} + k \big) and ∏k=0n−1(e β−k)\underoverset {k = 0} {n - 1} {\prod}\big(e^{\beta} - k \big), the others are ∏k=−sn−s−1(e β+k)\underoverset {k = -s} {n -s -1} {\prod}\big(e^{\beta} + k \big) .

    I guess in Lemma 4.12, we might as well use 11 rather than xx, and so have n!s λ(1,1,…,1,0,…0)=∑ σχ (λ)(σ)N #Cycles(σ)n! s_{\lambda}(1, 1, \ldots, 1, 0, \ldots 0) = \sum_{\sigma} \chi^{(\lambda)}(\sigma) N^{#Cycles(\sigma)}.

    So we know that n!s (n)(1,1,…,1,0,…0)=∑ σN #Cycles(σ)=∏k=0n−1(N+k)n! s_{(n)}(1, 1, \ldots, 1, 0, \ldots 0) = \sum_{\sigma} N^{#Cycles(\sigma)} = \underoverset {k = 0} {n - 1} {\prod}\big(N + k \big) and n!s 1 n(1,1,…,1,0,…0)=∑ σsgn(σ)N #Cycles(σ)=∏k=0n−1(N−k)n! s_{1^n}(1, 1, \ldots, 1, 0, \ldots 0) = \sum_{\sigma} sgn(\sigma) N^{#Cycles(\sigma)} = \underoverset {k = 0} {n - 1} {\prod}\big(N - k \big) .

    There’s plenty of structure on the Schur polynomials, when considering them as decategorified Schur functors.

    There must be things to consider about how to combine reps, e.g., a partition of mm and a partition of nn combine to a partition of m+nm + n.

    If my hunch is right then we’d be interested in how ∏k=−sn−s−1(N+k)=1N∏k=−s0(N+k)⋅∏k=0n−s−1(N+k)=1Ns 1 (s+1)(1,1,…,1,0,…0)⋅s (n−s−1)(1,1,…,1,0,…0)⋅(s+1)!⋅(n−s−1)!\underoverset {k = -s} {n -s -1} {\prod}\big(N + k \big) = \frac{1}{N} \underoverset {k = -s} {0} {\prod}\big(N + k \big) \cdot \underoverset{k = 0}{n -s -1}{\prod}\big(N + k \big) = \frac{1}{N} s_{1^{(s+1)}}(1, 1, \ldots, 1, 0, \ldots 0) \cdot s_{(n-s-1)}(1, 1, \ldots, 1, 0, \ldots 0)\cdot (s+1)!\cdot (n-s-1)!.

    So for some λ∈S n\lambda \in S_n, n!⋅s λ(1,1,…,1,0,…0)=1Ns 1 (s+1)(1,1,…,1,0,…0)⋅s (n−s−1)(1,1,…,1,0,…0)⋅(s+1)!⋅(n−s−1)!n! \cdot s_{\lambda}(1, 1, \ldots, 1, 0, \ldots 0)= \frac{1}{N} s_{1^{(s+1)}}(1, 1, \ldots, 1, 0, \ldots 0) \cdot s_{(n-s-1)}(1, 1, \ldots, 1, 0, \ldots 0)\cdot (s+1)!\cdot (n-s-1)!.

    • CommentRowNumber98.
    • CommentAuthorDavid_Corfield
    • CommentTimeMay 6th 2021

    Come to think of it, the hunch wasn’t supposed to be precise, just some factors without their constants.

    To try one out: in S 6S_6 the rep corresponding to (4,1,1)(4,1,1) gives for ∑ σχ (4,1,1)(σ)x #Cycles(σ)\sum_{\sigma} \chi^{(4,1,1)}(\sigma) x^{#Cycles(\sigma)}: 120x+40x 2−120x 3+40x 4−30x 3−90x 4+30x 5+10x 6=10x(12+4x−15x 2−5x 3+3x 4+x 5)=10x(x+3)(x−2)(x+2)(x−1)(x+1)120 x + 40 x^2 - 120 x^3 + 40 x^4 -30 x^3 -90 x^4 +30 x^5 + 10x^6 = 10x(12 + 4x -15x^2 - 5x^3 + 3x^4 +x^5) = 10x( x +3)(x-2)(x+2)(x-1)(x+1).

    Looks good with a factor. Perhaps it’s a Littlewood–Richardson rule thing.

    • CommentRowNumber99.
    • CommentAuthorUrs
    • CommentTimeMay 6th 2021

    Thanks, interesting. How did you “try out” that example, though? Could you explain how you computed that eigenvalue polynomial for (4,1,1)(4,1,1)?

    • CommentRowNumber100.
    • CommentAuthorDavid_Corfield
    • CommentTimeMay 6th 2021
    • (edited May 6th 2021)

    You find a character table, such as this one for S 6S_6. Pick a row, such as 411. Use character values at conjugacy classes as coefficients of x #Cyclesx^{#Cycles}, multiplying by the number in each conjugacy class, which can also helpfully be obtained, such as here.

1 to 100 of 165

  1. <
  2. 1
  3. 2
  4. >