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 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 internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure 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 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: horizontal chord diagram

Bottom of Page

1 to 91 of 91

  1.  
    • CommentRowNumber1.
    • CommentAuthorUrs
    • CommentTimeNov 26th 2019

    starting something – not done yet

    v1, current

    • CommentRowNumber2.
    • CommentAuthorUrs
    • CommentTimeNov 26th 2019

    added graphics of the 2T and 4T relations for horizontal weight systems

    diff, v3, current

    • CommentRowNumber3.
    • CommentAuthorUrs
    • CommentTimeNov 26th 2019

    expanded slightly, making relation to infinitesimal braid relation more explicit (but the entry remains telegraphic)

    diff, v4, current

    • CommentRowNumber4.
    • CommentAuthorUrs
    • CommentTimeNov 26th 2019

    added pointer to

    • Adrien Brochier, Cyclotomic associators and finite type invariants for tangles in the solid torus, Algebr. Geom. Topol. 13 (2013) 3365-3409 (arXiv:1209.0417)

    diff, v5, current

    • CommentRowNumber5.
    • CommentAuthorUrs
    • CommentTimeNov 30th 2019

    added graphics illustrating the algebra structure on horizontal chord diagrams (here)

    diff, v8, current

    • CommentRowNumber6.
    • CommentAuthorUrs
    • CommentTimeDec 2nd 2019

    added graphical version of statement of the definition of 𝒜 pb\mathcal{A}^{pb} (here)

    diff, v9, current

    • CommentRowNumber7.
    • CommentAuthorUrs
    • CommentTimeDec 5th 2019

    added further and improved illustration of the trace operation sending horizontal chord diagrams to round chord diagrams (here)

    diff, v10, current

    • CommentRowNumber8.
    • CommentAuthorUrs
    • CommentTimeDec 17th 2019
    • (edited Dec 17th 2019)

    made explicit also here that

    (𝒜 n pb,∘)≃𝒰(ℒ n(D)). \big(\mathcal{A}_n^{pb}, \circ\big) \;\simeq\; \mathcal{U}(\mathcal{L}_n(D)) \,.

    (now this Prop.)

    diff, v11, current

    • CommentRowNumber9.
    • CommentAuthorUrs
    • CommentTimeJan 20th 2020
    • (edited Jan 20th 2020)

    The algebra 𝒜 pb\mathcal{A}^{{}^{pb}} (here) of horizontal chord diagrams (for any number of strands) is clearly a star-algebra with respect to reversal of direction of the strands.

    Question: Is there any literature discussing 𝒜 pb\mathcal{A}^{{}^{pb}} as a star-algebra?

    Question: Which weight systems w:𝒜 pb→𝔽w \colon \mathcal{A}^{{}^{pb}} \to \mathbb{F} would be positive with respect to this star-structure, in that

    w(D⋅D *)≥0∈ℝ w(D \cdot D^\ast) \geq 0 \in \mathbb{R}

    and hence be a state (in the AQFT sense) on this star-algebra?

    Has anyone thought about this?

    • CommentRowNumber10.
    • CommentAuthorUrs
    • CommentTimeJan 20th 2020

    added statement of the evident star-algebra structure on horizontal chord diagrams (here)

    diff, v17, current

    • CommentRowNumber11.
    • CommentAuthorUrs
    • CommentTimeJan 20th 2020

    added the concept of weight systems that are states:

    With respect to this star-algebra-structure one may ask (setting R≔ℂR \coloneqq \mathbb{C} for definiteness) whether a given weight system

    w:𝒜 n pb⟶𝒞 w \;\colon\; \mathcal{A}_n^{{}^{pb}} \longrightarrow \mathcal{C}

    is a state on a star-algebra in that for any D∈𝒜 n pbD \in \mathcal{A}_n^{{}^{pb}} we have that the value of ww on the corresponding normal operator D⋅D *D \cdot D^\ast is a non-negative real number:

    (w∈𝒲 n pbis a state)AAA⇔AAA(1. w(1)=1 2. ∀D∈𝒜 n pb(w(D⋅D *)≥0∈ℝ⊂ℂ)). \Big( w \in \mathcal{W}_n^{{}^{pb}} \; \text{is a state} \Big) \phantom{AAA} \Leftrightarrow \phantom{AAA} \left( \begin{aligned} \text{1.}\;\;\; & w(1) = 1 \\ \text{2.}\;\;\; & \underset{ \mathclap{ D \in \mathcal{A}_n^{{}^{pb}} } }{ \forall } \;\;\;\; \Big( w(D \cdot D^\ast) \; \geq 0 \; \in \mathbb{R} \subset \mathbb{C} \Big) \end{aligned} \right) \,.

    Anything known about weight systems that satisfy this condition?

    diff, v17, current

    • CommentRowNumber12.
    • CommentAuthorUrs
    • CommentTimeJan 20th 2020
    • (edited Jan 20th 2020)

    [ hm… ]

    • CommentRowNumber13.
    • CommentAuthorUrs
    • CommentTimeJan 27th 2020

    Made a little progress on this question on which weight systems on horizontal chord diagrams are states, in the sense of #11, but I am still missing something:

    So consider 𝔤𝔩(N,ℂ)\mathfrak{gl}(N, \mathbb{C})-weight systems for the fundamental NN-dimensional rep. Then the value of the weight system on a single chord is just the braiding. Let moreover the winding monodromy as here be trivial, Then a single chord diagram DD evaluates to N #cyclesN^{\# cycles}, i.e. to the dimension of the rep taken to the power of the number of cycles in the permutation given by interpreting each chord as a braiding.

    Since D *D^\ast similarly represents the inverse permutation, so that D⋅D *D \cdot D^\ast is the trivial permutation with #cycles=#strands\# cycles = \# strands we have

    w((a⋅D)⋅(a⋅D) *)=aa *N #strands≥0 w( (a \cdot D) \cdot (a \cdot D)^\ast ) \;=\; a a^\ast N^{\# strands} \;\geq \; 0

    which is indeed non-negative.

    Next, for a linear combination a 1D 1+a 2D 2a_1 D_1 + a_2 D_2 we use that whatever D 1D_1 and D 2D_2 are, the permutation corresponding to D 1⋅D 2 *D_1 \cdot D_2^\ast has (as any permutation) at most as many cycles as there are strands: #cycles≤#strands\# cycles \leq \# strands. Thus the triangle inequality shows that

    |a 1| 2+|a 2| 2≥N #cyclesN #strands|a 1a 2 *+a 2a 1 *| \left\vert a_1 \right\vert^2 + \left\vert a_2 \right\vert^2 \;\geq\; \frac{N^{\# cycles}}{N^{\#strands}} \left\vert a_1 a_2^\ast + a_2 a_1^\ast \right\vert

    and it follows that also

    w((a 1D 1+a 2D 2)⋅(a 1D 1+a 2D 2) *)≥0 w\big( (a_1 D_1 + a_2 D_2)\cdot (a_1 D_1 + a_2 D_2)^\ast \big) \geq 0

    Now this last argument just needs to generalize to linear combinations of more than two chord diagrams. Does it?

    • CommentRowNumber14.
    • CommentAuthorUrs
    • CommentTimeJan 28th 2020
    • (edited Jan 28th 2020)

    So I’d need something like “cosine rule” for permutations…

    • CommentRowNumber15.
    • CommentAuthorUrs
    • CommentTimeJan 29th 2020
    • (edited Jan 29th 2020)

    For any n∈ℕn \in \mathbb{N}, n≥1n \geq 1, let

    ⟨−,−⟩:Sym(n)×Sym(n)⟶ℕ \langle -,-\rangle \;:\; Sym(n) \times Sym(n) \longrightarrow \mathbb{N}

    be given by sending a pair of permutations (σ 1,σ 2)(\sigma_1, \sigma_2) to NN to the number of cycles in σ 1∘σ 2 −1\sigma_1 \circ \sigma_2^{-1}.

    Then I need the inequality

    ⟨σ 1,σ 2⟩+⟨σ 2,σ 3⟩−⟨σ 1,σ 3⟩≤32N n \langle \sigma_1, \sigma_2\rangle + \langle \sigma_2, \sigma_3\rangle - \langle \sigma_1, \sigma_3\rangle \;\leq\; \frac{3}{2} N^n

    for all triples of permutations.

    Haven’t found a counter-example yet, but I may easily be missing the obvious.

    But such a kind of “inner product theory for permutations”, has this been considered anywhere?

    • CommentRowNumber16.
    • CommentAuthorDavid_Corfield
    • CommentTimeJan 29th 2020

    John Baez has been writing a series of posts on permutations, I could ask.

    • CommentRowNumber17.
    • CommentAuthorUrs
    • CommentTimeJan 29th 2020
    • (edited Jan 29th 2020)

    Also Google comes up with pointers to the theory of random permutations when fed with the keywords of my question. While there is no randomness in what I am asking about, I won’t be surprised if the structure that I am after is known, since it’s very elementary.

    To clarify, the core of the issue is this:

    Let n,N∈ℕn, N \in \mathbb{N} with n,N≥2n,N\geq 2.

    On the complex linear span ℂ[Sym(n)]\mathbb{C}[Sym(n)] of the set of permutations of nn elements, consider the inner product

    ⟨−,−⟩ N:ℂ[Sym(n)]×ℂ[Sym(n)]⟶ℂ \langle -,-\rangle_N \;:\; \mathbb{C}[Sym(n)] \times \mathbb{C}[Sym(n)] \longrightarrow \mathbb{C}

    which on pairs of complex multiples (a 1⋅σ 1,a 2⋅σ 2)(a_1\cdot \sigma_1, a_2\cdot \sigma_2), for a i∈ℂa_i \in \mathbb{C} and σ i∈Sym(n)\sigma_i\in Sym(n), is given by

    ⟨a 1⋅σ 1,a 2⋅σ 2⟩ N≔a 1a 2 *⋅N #cycles(σ 1∘σ 2 −1) \langle a_1\cdot \sigma_1, a_2\cdot \sigma_2\rangle_N \;\coloneqq\; a_1 a_2^\ast \cdot \, N^{\#cycles(\sigma_1 \circ \sigma_2^{-1})}

    and then extended complex sesqui-linearly to arbitrary formal linear combinations of permutations.

    The question is: Is this positive semi-definite, in that for all Σ∈ℂ[Sym(n)]\Sigma \in \mathbb{C}[Sym(n)] we have

    ⟨Σ,Σ⟩≥0∈ℝ⊂ℂ \langle \Sigma, \Sigma \rangle \geq 0 \in \mathbb{R} \subset \mathbb{C}

    ??

    • CommentRowNumber18.
    • CommentAuthorUrs
    • CommentTimeJan 29th 2020
    • (edited Jan 29th 2020)

    [ added the previously missing exponentials in the formula –should really postpone talking about this until I have more spare time and am more awake ]

    • CommentRowNumber19.
    • CommentAuthorUrs
    • CommentTimeFeb 1st 2020

    Finally I am emerging from last week.

    Now I found time to make a decent note on what I was after in the above comments.

    In the note I still state only a conjecture with partial proof, that the weight system w 2w_{\mathbf{2}} induced by the fundamental representation 2\mathbf{2} of 𝔤𝔩(2)\mathfrak{gl}(2) is a state with respect to the canonical star-algebra structure on horizontal chord diagrams. But Carlo Collari just writes in to say that he thinks he found the full proof.

    If that is the case, it follows immediately that also all w N⋅2w_{N \cdot \mathbf{2}} are states, which is neat.

    But then I still want to know: What else? What is the subspace of weight systems on horizontal chord diagrams that are also states with respect to the star-involution that reverses orientation of strands?

    If you have an idea, let me know.

    • CommentRowNumber20.
    • CommentAuthorUrs
    • CommentTimeFeb 2nd 2020

    We still don’t have a full proof, but now Carlo ran a computer check on Conjecture 3.5. It seems to be true!

    Much to be explored here now…

    • CommentRowNumber21.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 6th 2020
    • (edited Feb 6th 2020)

    Re #16, my request has just yielded (for your original non-exponentiated version):

    Not as an inner product, but this is a known distance function. If we take the Cayley graph for Sym(n)Sym(n) with the set of all transpositions as generators, then the distance between two permutations (σ 1,σ 2)(\sigma_1,\sigma_2) is (n−n - the number of cycles in σ 1⋅σ 2 −1\sigma_1 \cdot \sigma_2^{-1}).

    Shall I ask about the inequality in #15?

    • CommentRowNumber22.
    • CommentAuthorUrs
    • CommentTimeFeb 7th 2020

    I had proven #15 (with the exponentials fixed) as Lemma 3.8 in the note announced in #19:

    Weight systems that are quantum states.

    Together with lemma 3.7 there that proves the statement (conjecture 3.5) on linear combinations (of chord diagrams) of length at most 3.

    Beyond that I still don’t have proof of conjecture 3.5 in Weight systems that are quantum states, but we have now plenty of computer experiment checks that confirm its truth.

    We’ll keep trying to prove it. But there is no lack of followup questions for us to look into, so that if anyone knows or comes up with the proof, we’d like to hear about it. That’s why I am talking about this in public here.

    • CommentRowNumber23.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 7th 2020
    • (edited Feb 7th 2020)

    Is that a coincidence that where #cycles(σ 1⋅σ 2 −1)−N f#cycles(\sigma_1 \cdot \sigma_2^{-1})-N_f appears in (13) in your article, that is (−1)(-1) times a distance commonly used in geometric group theory? It turns out to be equal to the word metric for letters drawn from transpositions.

    • CommentRowNumber24.
    • CommentAuthorUrs
    • CommentTimeFeb 7th 2020
    • (edited Feb 7th 2020)

    I guess knowing how this might not a coincidence could be a step towards a proof. But this is really all I can say.

    (I am not hiding any information here. I would pick up on your suggestions if I knew they lead to something!)

    It’s evident that the problem is completely elementary; it involves the ancient mathematical concept of permutations, therefore nobody will be caught by surprise by any one ingredient in the statement of the question. But I am looking for a proof of this particular statement (Conjecture 3.5 in the note), not just for confirmation that people before me have thought about permutations, too. :-)

    And notice that it is key for the statement of Conjecture 3.5 that the pairing (σ 1,σ 2)↦N #cycles(σ 1∘σ 2 −1)(\sigma_1, \sigma_2) \mapsto N^{\#cycles(\sigma_1 \circ \sigma_2^{-1})} apparently (according to the conjecture and to Carlo’s computer checks!) indeed behaves like an inner product. It may also behave like a distance in other contexts, but here it is its (new?) interpretation as an inner product that is relevant. The statement of the conjecture is essentially that this pairing satisfies all possible “cosine rules” familiar from inner products in analytic geometry. That’s curious, isn’t it?

    • CommentRowNumber25.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 7th 2020
    • (edited Feb 7th 2020)

    Well let’s give it a go: we need that ∑ i,ja ia¯ j2 #cycles(σ i∘σ j −1)≥0\sum_{i,j} a_i \bar{a}_j 2^{\#cycles(\sigma_i \circ \sigma_j^{-1})} \geq 0.

    So we need to know about ∑ i,ja ia¯ j2 N f−d(σ i,σ j)\sum_{i,j} a_i \bar{a}_j 2^{N_f - d(\sigma_i, \sigma_j)}, and so just ∑ i,ja ia¯ j2 −d(σ i,σ j)\sum_{i,j} a_i \bar{a}_j 2^{- d(\sigma_i, \sigma_j)}.

    Entering positive semidefinite kernel territory. Doesn’t work in general, but maybe the Cayley graph has nicer properties.

    • CommentRowNumber26.
    • CommentAuthorUrs
    • CommentTimeFeb 7th 2020
    • (edited Feb 7th 2020)

    That looks promising!

    I see that the complex/hermitian version of “kernel of conditionally positive/negative type” that we need is discussed in

    (Definitions 4.2.2 and 4.3.2).

    So now there is a chance of proof-by-googling with these keywords…

    • CommentRowNumber27.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 7th 2020

    Looks like section C.4 of Kazhdan’s Property (T) is saying some handy things. There’s a link to unitary representations in a Hilbert space.

    • CommentRowNumber28.
    • CommentAuthorUrs
    • CommentTimeFeb 7th 2020

    Too bad that besides discussion of all these general properties of functions positive type etc. these authors don’t seem to bother much with any actual examples.

    • CommentRowNumber29.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 8th 2020

    Aha, it seems there’s an issue.

    • CommentRowNumber30.
    • CommentAuthorUrs
    • CommentTimeFeb 8th 2020
    • (edited Feb 8th 2020)

    Thanks for checking. We’d just need t=1t = 1. We effectively know that the statement is true in this case (i.e. that the kernel is positive in the suitable sense; we know this from computer checks), we just need to know why.

    Looks like we stumbled on a problem that was left open…

    • CommentRowNumber31.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 9th 2020

    Ok, we had some more from Mark here. Seems reasonable to think that the values of tt for which positive semi-definiteness is achieved will depend on nn, no? But you want a fixed NN in #24 to work for all nn?

    • CommentRowNumber32.
    • CommentAuthorUrs
    • CommentTimeFeb 9th 2020

    Thanks. So for the conjecture described in the note, we have

    • N=2N=2

    • n∈ℕn \in \mathbb{N} arbitrary.

    Equivalently, rewriting N=exp(t)N = exp( t ) this is

    • t=ln(2)t = ln(2)

    • n∈ℕn \in \mathbb{N} arbitrary.

    From computer experiment it does look that with these choices the statement

    t⋅d(−,−)t\cdot d(-,-) is a conditionally positive kernel on the Cayley graph of Sym(n)Sym(n)

    is true. I am grateful that you made this equivalent reformulation of my conjecture emerge, if this is what more people can relate to, and since this is pointing to an interesting perspective.

    But now how to approach the proof?

    I see that in the discussion on the blog people like to think of physics analogies “floating around”. But here the situation is the opposite: I have a physics interpretation of the problem all nailed down already (it’s sort of like a partition function, yes, but one can say much more) and what’s missing now is instead the pure maths proof.

    How to prove it, for t=ln(2)t =ln(2) and nn arbitrary?

    • CommentRowNumber33.
    • CommentAuthorUrs
    • CommentTimeFeb 9th 2020

    Just to say that I updated the note

    now it has a last Section 4 with the re-formulation of the conjecture in geometric group theory.

    • CommentRowNumber34.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 9th 2020

    John Baez writes about |G k(n)||G_k(n)|, the number of permutations on nn with kk cycles, here.

    • CommentRowNumber35.
    • CommentAuthorUrs
    • CommentTimeFeb 10th 2020

    Not sure what to make of this. Please help me out: What’s the implication you have in mind?

    • CommentRowNumber36.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 10th 2020
    • (edited Feb 10th 2020)

    According to Mark Meckes, after application of the Gershgorin circle theorem, the semipositive definiteness of exp(−td(x,y))exp(-t d(x,y)) on S(n)S(n) holds when

    1n!∑ σ∈Sym(n)exp[tC(σ)]≤(1+1n!)e tn, \frac{1}{n!} \sum_{\sigma \in Sym(n)} exp[t C(\sigma)] \le \left(1+\frac{1}{n!}\right) e^{t n},

    where C(σ)C(\sigma) counts the number of cycles in σ\sigma.

    Though now I look more closely, I’m not sure I see one of his steps. But have to dash.

    • CommentRowNumber37.
    • CommentAuthorUrs
    • CommentTimeFeb 10th 2020

    Thanks. Now I see what you are getting at.

    • CommentRowNumber38.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 10th 2020
    • (edited Feb 10th 2020)

    Oh I see. He’s just talking about positive (semi)definite metric spaces rather than kernels. So for him each point in the space is represented by one line of the matrix.

    • CommentRowNumber39.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 10th 2020

    10 more minutes of proof-by-googling (#26), a related kernel is the ’Mallows kernel’ which is positive definite (I seem to recall different communities apply ’semi’ differently) and appears to be like the desired kernel but for the Cayley graph generated with only adjacent transpositions (e.g. here). Meanwhile this one deals with the Cayley distance for all transpositions, but doesn’t seem to comment on positive definiteness.

    • CommentRowNumber40.
    • CommentAuthorUrs
    • CommentTimeFeb 10th 2020

    Thanks!

    The Mallows kernel being “positive” might imply the statement:

    Our distance kernel is invariant under the conjugation action of the symmetric group on itself, and up to conjugation every minimal sequence of transpositions equals one of adjacent transpositions, I suppose.

    So then we can decompose the sum over our distance kernel into a nested sum where the inner one is over permutations in the same conjugacy class, while the outer one is over conjugacy classes.

    Now after performing the inner sum we are left with a sum over the Mallows kernel. So positivity follows by Theorem 1 in your first reference! It seems.

    • CommentRowNumber41.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 10th 2020

    up to conjugation every minimal sequence of transpositions equals one of adjacent transpositions, I suppose

    Hmm, is that so? With so many more edges emerging from a vertex in the Cayley graph in the case of all transpositions, distances should generally be much shorter.

    • CommentRowNumber42.
    • CommentAuthorUrs
    • CommentTimeFeb 11th 2020
    • (edited Feb 11th 2020)

    up to conjugation every minimal sequence of transpositions equals one of adjacent transpositions, I suppose

    Hmm, is that so?

    We may think of the underlying set being ordered, so that all permutations are identified by cycles denoted (i 1i 2i 3⋯i k)(i_1 i_2 i_3 \cdots i_k). For any fixed permutation, there is a re-ordering of the underlying set such that its cycles all have denotation of the form (i+1,i+2,⋯,i+k−1,i)(i+1, i+2, \cdots, i+k-1, i). Let’s call this “nice form”. In this nice form the permutation is a minimal length composite of transpositions such that these are all adjacent transpositions. But re-orderings of the underlying set act by conjugation on all permutations.

    With so many more edges emerging from a vertex in the Cayley graph in the case of all transpositions, distances should generally be much shorter.

    The Mallows kernel assigns larger distances to most permutations, but it agrees with our distance kernel on those in nice form. But there is one permutation in nice form in every conjugacy class of permutations, and our distance kernel assigns the same value to all members in a conjugacy class.

    So the strategy is to sum up the coefficients of all members in a conjucacy class, regard the result as supported on a nice member in the conjugacy class, and feed that into the Mallows kernel.

    But now I see that while I can apply that transformation to the sums, the resulting sum may no longer be a “norm square” as seen by the Mallows kernel. Hm…

    • CommentRowNumber43.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 11th 2020
    • (edited Feb 11th 2020)

    The Mallow kernel for adjacent transpositions is positive definite for all tt. If your argument above is correct, wouldn’t we be able to argue that this is so in the corresponding case of all transpositions.

    And yet, even with Sym(3)Sym(3) there’s a difference. With all transpositions the Cayley graph is the complete bipartite graph K 3,3K_{3,3}, which contains K 3,2K_{3,2}, which is a minimal example of a metric space which is not of negative type. Hence for general tt the associated kernel exp(−td(x,y))exp(-t d(x,y)) is not positive semidefinite.

    • CommentRowNumber44.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 11th 2020

    Also, I don’t know why you’ve included the qualifier ’conditionally’ in ’a kernel of conditionally positive type’. That concerns restricting what you have as the function aa in your last line, so that the sum of a ia_i is zero, but you speak there of all complex functions.

    • CommentRowNumber45.
    • CommentAuthorUrs
    • CommentTimeFeb 11th 2020

    I tried to indicate in the last line of my comment that I found the flaw in my argument, where I wrote:

    But now I see that while I can apply that transformation to the sums, the resulting sum may no longer be a “norm square” as seen by the Mallows kernel. Hm…

    Also, I didn’t realize that “conditionally” referes to the sum of coefficients vanishing. I thought it’s just an adjective thrown in to make the situation with the “semi”-qualifier worse. :-)

    Fianlly, I still don’t see the relevance of considering general tt. You seem to take some insight for granted here which I may be lacking.

    But I should say that I will have to postpone any further discussion of this until next week. We are all absorbed in finalizing a funding proposal, and I get into trouble if I spend more time trying to prove theorems when I should instead be applying for funding for proving theorems.

    • CommentRowNumber46.
    • CommentAuthorDavid_Corfield
    • CommentTimeFeb 11th 2020

    Just briefly, as I should certainly be writing funding proposals over assisting in someone else’s theorem-proving, the use of general tt in #43 was to show that it was unlikely (and I think impossible, if I thought harder) that you’d be able to use the Mallow kernel as you’d hoped. But in any case you found the flaw directly.

    I still think you need to worry about tt-dependence in your case. Your choice of t=ln(2)t = ln(2) is arbitrary. You’re just hoping that there’s a fixed value of tt that works for all nn in Sym(n)Sym(n). You may have done some computer checks, but do you know that as nn in Sym(n)Sym(n) grows sufficiently large that this will continue to hold? Perhaps min(t) nmin(t)_n, the smallest value of tt for which exp(−td(x,y))exp(-t d(x,y)) on S(n)S(n) is positive semidefinite, grows without bound as nn increases.

    • CommentRowNumber47.
    • CommentAuthorUrs
    • CommentTimeFeb 11th 2020

    Okay, thanks. I will have to think about it more. But I am hoping we can just stir up enough dust here that Carlo will be able to unearth the hidden nugget. ;-)

    • CommentRowNumber48.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021

    Coming back to this after over a year:

    I am beginning to appreciate the possible dependence on the exponential factor that you (David C.) have been pointing out might be a problem:

    In a simple special case, consider for Sym(3)Sym(3) the following 5 permutations (following this slide by J. Marail & J.-P. Vert)

    123 ↙↓↘ 213 132 321 ↘↓↙ 312 \array{ & 123 \\ & \swarrow \downarrow \searrow \\ 213 & 132 & 321 \\ & \searrow \downarrow \swarrow \\ & 312 }

    Shown are the edges of the Cayley distance graph between these vertices (meant to be undirected). This is not the full Cayley graph, but it is a full subgraph containing all the shortest paths, and so if a kernel is not positive definite on this subgraph, then it is not positive definite in general.

    Feeding this into WolframAlpha (here), I see that the Cayley distance kernel restricted to this subgraph

    exp(−λ⋅d C(−,−)) \exp( - \lambda \cdot d_{C}(-,-) )

    has negative eigenvalues for λ≤.346\lambda \leq .346 and becomes positive definite somewhere between that and λ≥.347\lambda \geq .347.

    So for the value λ=1\lambda = 1 that I am interested in, this is not a counter-example. But it does suggest that for any value of λ\lambda there might be an n λn_\lambda such that the Cayley distance kernel fails to be positive definite on Sym(>n λ)Sym( \gt n_\lambda ).

    If that is the case, I want to understand this n λn_\lambda. (In the intended application, this is the number of D8-branes, which indeed is not supposed to be unbounded. So if n λ=1n_{\lambda=1} turns out to be a power of 2, for instance, that would be most interesting.)

    • CommentRowNumber49.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021

    Now I should really go all the way with this example and just compute the kernel on all of Sym(3)Sym(3).

    First, for the Cayley graph of Sym(3)Sym(3), it has the above edges

    123 ↙↓↘ 213 132 321 ↘↓↙ 312 \array{ & 123 \\ & \swarrow \downarrow \searrow \\ 213 & 132 & 321 \\ & \searrow \downarrow \swarrow \\ & 312 }

    and in addition the following edges

    ⋮ 213 132 321 ↘↓↙ 231 \array{ & \vdots \\ 213 & 132 & 321 \\ & \searrow \downarrow \swarrow \\ & 231 }

    I think.

    Ordering these vertices by their appearance in the above, the corresponding Cayley distance matrix is

    d C=[0 1 1 1 2 2 1 0 2 2 1 1 1 2 0 2 1 1 1 2 2 0 1 1 2 1 1 1 0 2 2 1 1 1 2 0] d_C \;=\; \left[ \array{ 0 & 1 & 1 & 1 & 2 & 2 \\ 1 & 0 & 2 & 2 & 1 & 1 \\ 1 & 2 & 0 & 2 & 1 & 1 \\ 1 & 2 & 2 & 0 & 1 & 1 \\ 2 & 1 & 1 & 1 & 0 & 2 \\ 2 & 1 & 1 & 1 & 2 & 0 } \right]

    Asking again WolframAlpha to compute the eigenvalues of the corresponding kernel e −λd Ce^{- \lambda d_C} I get two interesting results:

    • the critical value of λ\lambda, where the negative eigenvalues disappear, is already much larger than for the subgraph above: it’s somewhere around λ≥.694\lambda \geq .694 (here) – removing one node it was just around .347.347 (here).

    • for λ=1\lambda = 1 the eigenvalues are rational functions of the Euler number (!?, here).

    In any case, that’s the full proof-by-brute-force that our little conjecture is true for n≤3n \leq 3, for what it’s worth.

    • CommentRowNumber50.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 20th 2021

    On p. 72 of this there’s something (5.10) on using group characters to calculate the Cayley distance for all transpositions.

    • CommentRowNumber51.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021
    • (edited Apr 20th 2021)

    Thanks for the pointer. That’s a curious formula.

    But I am thinking now: If we expect the Cayley distance kernel on Sym(n)Sym(n) to be positive definite (a) only for some n≤n λ=1n \leq n_{\lambda =1} and (b) relatively small such, then (a) there is unlikely to be a good proof by analytic formulas and (b) instead one should just go computer check the cases for n=4,5,6,⋯n = 4, 5, 6, \cdots until it breaks.

    • CommentRowNumber52.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021

    Wait, why do I keep saying λ=1\lambda = 1. I need λ=ln(2)\lambda = ln(2)… checking… which seems to be exactly that critical value where the kernel becomes positive semi-definite: here

    • CommentRowNumber53.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 20th 2021

    n!×n!n! \times n! matrices for n=4,5,6,⋯n = 4, 5, 6, \cdots.

    I guess one useful thing might be a few lines earlier: to find the distance between σ 1\sigma_1 and σ 2\sigma_2, you just need the cycle type of σ 1⋅σ 2 −1\sigma_1 \cdot \sigma_2^{-1}. Sum of one less than the length of each cycle.

    • CommentRowNumber54.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 20th 2021

    Could there be something neat about that last eigenvector in your calculation in #52? Signs of the permutations?

    • CommentRowNumber55.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 20th 2021

    Oh, the eigenvectors don’t change as you vary λ\lambda. Why?

    • CommentRowNumber56.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021
    • (edited Apr 20th 2021)

    Re #53: You certainly have a point in your first line there.

    But your second line seems to just restate what got us started here in the first place: Cayley’s observation. No?

    • CommentRowNumber57.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021
    • (edited Apr 20th 2021)

    Re 54: Yes, it’s that one “last” eigenvector which is special, in that its eigenvalue passes through zero as lambda is increased. I have no idea why, but it’s interesting.

    • CommentRowNumber58.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021

    And it goes through zero at λ=ln(2)\lambda = ln(2)!

    • CommentRowNumber59.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 20th 2021

    Looking at the eigenvalues for your λ=1\lambda = 1 calculation, the first (and sixth) seem to involve a (alternating) sum over numbers in conjugacy classes weighted by powers of e −1e^{-1}.

    And replacing ee by 22, you get the eigenvalues for λ=ln(2)\lambda = ln(2).

    I could imagine that continuing for higher nn.

    • CommentRowNumber60.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 20th 2021
    • (edited Apr 20th 2021)

    E.g, for n=4n=4, with conjugacy classes 1,2,2 2,3,41, 2, 2^2, 3, 4 and corresponding numbers of elements 1,6,3,8,61, 6, 3, 8, 6, then 1/1−6/2+3/4+8/4−6/8=01/1 - 6/2 + 3/4 + 8/4 - 6/8 = 0 at λ=ln(2)\lambda = ln(2).

    For S 5S_5, 1/1−10/2+15/4+20/4−20/8−30/8+24/16=01/1 - 10/2 + 15/4 + 20/4- 20/8 - 30/8 + 24/16 = 0.

    • CommentRowNumber61.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021

    Re #59: Thanks, I see. That explains now why the Euler number appeared there.

    I’ll try to record this situation at Cayley graph of Sym(3)

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

    Hold on. It’s that given the λ\lambda appearing in the kernel, then the eigenvalues are

    e 2λ−1e 2λ\frac{e^{2 \lambda} -1}{e^{2 \lambda}}, etc.

    So then if λ>0\lambda \gt 0, then this eigenvalue is positive. With the smallest eigenvalue, it will be positive so long as e λ>2e^{\lambda} \gt 2, or λ>ln(2)\lambda \gt ln(2).

    • CommentRowNumber63.
    • CommentAuthorUrs
    • CommentTimeApr 20th 2021

    Ah, thanks. I wasn’t concentrating here, it seems. Will change notation to fix this. But my battery is dying, let’s see how far I get.

    • CommentRowNumber64.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021
    • (edited Apr 21st 2021)

    Returning to #36

    According to Mark Meckes, after application of the Gershgorin circle theorem, the semipositive definiteness of exp(−td(x,y))exp(-t d(x,y)) on S(n)S(n) holds when

    1n!∑ σ∈Sym(n)exp[tC(σ)]≤(1+1n!)e tn, \frac{1}{n!} \sum_{\sigma \in Sym(n)} exp[t C(\sigma)] \le \left(1+\frac{1}{n!}\right) e^{t n},

    where C(σ)C(\sigma) counts the number of cycles in σ\sigma.

    In the case that t=ln(2)t = ln(2), we can apply the formula here for β=2\beta = 2. Then it looks like we need

    1n!∏ i=0 i=n−1(2+i)≤(1+1n!)2 n, \frac{1}{n!} \prod_{i = 0}^{i = n-1} (2+ i) \le \left(1+\frac{1}{n!}\right) 2^n,

    which is

    n+1≤(1+1n!)2 n. n + 1 \le \left(1+\frac{1}{n!}\right) 2^n.

    And that holds.

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

    Oh, okay. Thanks for emphasizing, I had lost sight of that. So you think that’s a general proof?!

    Let me go record the steps on the nnLab, in order to absorb them better…

    • CommentRowNumber66.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    Is Meckes’ statement in his “Lecture notes on matrix analysis” (pdf)?

    • CommentRowNumber67.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021

    Except Meckes corrected himself.

    So that ought to be

    n+1≤2n!⋅2 n n + 1 \le \frac{2}{n!}\cdot 2^n

    which no longer holds.

    • CommentRowNumber68.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    Hm, but that inequality from #67 fails already for n=3n =3, for which we know the statement to be true.

    • CommentRowNumber69.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021

    I think it was only a sufficient condition, not necessary. I don’t know how tight this Gershgorin circle theorem is.

    • CommentRowNumber70.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    Oh, I see. But then there is no proof for us here. Unless we can strengthen the argument. Maybe we should get in contact with Meckes…

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

    I now went through some of your hints above and convinced myself (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

    But now that I have done this, I am stuck seeing how this has any impact on positive definiteness: Since the centers of the Gershgorin discs are all at 0, a direct application of the Gershgorin disc theorem gives exactly no information on positive definiteness.

    So apparently I am missing some step in the argument. I looked through the blog discussion, but I can’t spot the point where the relevant step is discussed.

    • CommentRowNumber72.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021

    The discs are centred on 1, no?

    • CommentRowNumber73.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    oh, I missed an exponential there, right. Will fix, thanks

    • CommentRowNumber74.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021

    Calculating the radius from a row, you need to leave out the diagonal element.

    • CommentRowNumber75.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    yes, I know. In the proof I said this makes no difference since the diagonal element vanishes. But it’s = 1 instead, so we need to subtract one. have fixed it now here, I hope.

    • CommentRowNumber76.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021

    The idea is that in a near diagonal matrix, eigenvalues will be close to the diagonal entries, as governed by the sum of non-diagonal entries in a row.

    • CommentRowNumber77.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    Sure, I just missed an exponential (e 0e^0 as opposed to 00). I think otherwise I am not confused. :-) But you are right to sanity check me here, thanks.

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

    So when is

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

    ???

    Firing up WolframAlpha once more…

    • CommentRowNumber79.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    Hm, something is wrong. Asking about the above inequality for n=3n =3 gives me λ>0.15...\lambda \gt 0.15... here, way off from the λ≥ln(2)\lambda \geq ln(2) established before.

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

    Oh, wait, I see. Wrong nesting of parenthesis…

    Right, I see what happened. Walpha doesn’t allow me to nest in the intended way. What’s going on?

    • CommentRowNumber81.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021

    Sanity check: is there a mixing up of the exponential of the matrix of distances and the matrix of exponentiated distances going on?

    • CommentRowNumber82.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    I had the same worry yesterday and did double check that in the computation here Wolfram alpha does apply the exponential entry-wise.

    But maybe check yourself…

    • CommentRowNumber83.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    But while I am fighting WolframAlpha’s syntax (it doesn’t seem to understand taking a product with an indexed product ?!)

    let’s record that we just found fully general proof of the following theorem:

    For every n∈ℕn \in \mathbb{N} there is N∈ℕN \in \mathbb{N} such that the fundamental sl(ℂ,N)sl(\mathbb{C},N)-Lie algebra weight system on horizontal chord diagrams on nn strands is a quantum state.

    Proof: That Gershogin radius decreses monotonically (and rapidly) with λ\lambda, so just making λ=ln(N)\lambda = ln(N) arbitrarily large by making NN arbitrarily large, we find a value that the Gershogin radius (one and hence all of them) is smaller than one, whence our kernel is positive definite.

    • CommentRowNumber84.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021

    Re #82, that looks right.

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

    Thanks for double checking!

    And do you agree now that #78 is a sufficient condition for positive definity?

    (If correct, this must be underlying what you discussed with Meckes, but #78 is in a form that I understand now, for what that’s worth).

    • CommentRowNumber86.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 21st 2021

    Yes, that looks right in #78.

    Re #83, Mark provided a value of λ\lambda by other means which makes the kernel positive definite, λ=ln(n!)−1\lambda = ln(n!)-1.

    Perhaps #78 is tighter. But in any case, it would be interesting to know if there is a critical value of nn for λ=ln(2)\lambda = ln(2), as in your Remark 4.8.

    • CommentRowNumber87.
    • CommentAuthorUrs
    • CommentTimeApr 21st 2021

    Thanks!

    Yes, this argument via the Gershgorin circle theorem seems to provide a rather loose bound.

    But it makes me happy since it does give an infinite-dimensional space of quantum states on horizontal chord diagrams! Namely, this was my original motivation, to find weight systems (on horizontal chord diagrams) which are quantum states with respect to star-involution given by reversal of strands.

    The focus on the fundamental sl(2,ℂ)sl(2,\mathbb{C})-weight systems was just because this was the first best example to try. It’s good to see that it seems to have special extremal properties, but I am also happy to have found now lots of other examples.

    • CommentRowNumber88.
    • CommentAuthorDavid_Corfield
    • CommentTimeApr 22nd 2021

    Does the eigenvalue I pointed out at Cayley distance kernel mean anything in this context? I guess one thing is that for given S nS_n, then for the early natural number values of e λe^{\lambda}, including the 22 of your note, the eigenvalue is 00 and thereafter positive. So this eigenvalue can’t be responsible for non-positive-semidefiniteness at natural number e λe^{\lambda}.

    • CommentRowNumber89.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    I don’t know yet what the eigenvectors “mean”, but it’s an interesting question. I’d want to lift them back from linear combinations of permutations to linear combinations of horizontal chord diagrams, and then see if under the various physics interpretations of these chord diagrams, those combinations mean something special.

    For instance, the chord diagrams are graded (by chord number) and at least in some applications this is, mod2mod \, 2 a boson/fermion grading (“s-rule”). This means that weighing diagrams by (−1) degree(-1)^{degree} is a natural operation, as it will appear in super-traces/super-partition functions. This is reminiscent of your sgn(σ)sgn(\sigma) weight, though it’s not the same, in general.

    Yeah, so I don’t know yet. But would like to understand this better.

    • CommentRowNumber90.
    • CommentAuthorUrs
    • CommentTimeApr 22nd 2021

    made explicit (here) the monoid of horizontal chord diagrams (before passing to the linear span and modding out the T-relations) and its canonical monoid homomorphism to the symemtric group

    diff, v19, current

    • CommentRowNumber91.
    • CommentAuthorUrs
    • CommentTimeMay 10th 2021

    linked the discussion of the star-algebra structure (here) with the involutive Hopf algebra structure on the homology of the loop space of configuration spaces of points

    diff, v20, current

1 to 91 of 91

  1.