Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
expanded slightly, making relation to infinitesimal braid relation more explicit (but the entry remains telegraphic)
added pointer to
The algebra 𝒜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 as a star-algebra?
Question: Which weight systems w:𝒜pb→𝔽 would be positive with respect to this star-structure, in that
w(D⋅D*)≥0∈ℝand hence be a state (in the AQFT sense) on this star-algebra?
Has anyone thought about this?
added the concept of weight systems that are states:
With respect to this star-algebra-structure one may ask (setting R≔ℂ for definiteness) whether a given weight system
w:𝒜pbn⟶𝒞is a state on a star-algebra in that for any D∈𝒜pbn we have that the value of w on the corresponding normal operator D⋅D* is a non-negative real number:
(w∈𝒲pbnis a state)AAA⇔AAA(1.w(1)=12.∀D∈𝒜pbn(w(D⋅D*)≥0∈ℝ⊂ℂ)).Anything known about weight systems that satisfy this condition?
[ hm… ]
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,ℂ)-weight systems for the fundamental N-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 D evaluates to N#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* similarly represents the inverse permutation, so that D⋅D* is the trivial permutation with #cycles=#strands we have
w((a⋅D)⋅(a⋅D)*)=aa*N#strands≥0which is indeed non-negative.
Next, for a linear combination a1D1+a2D2 we use that whatever D1 and D2 are, the permutation corresponding to D1⋅D*2 has (as any permutation) at most as many cycles as there are strands: #cycles≤#strands. Thus the triangle inequality shows that
|a1|2+|a2|2≥N#cyclesN#strands|a1a*2+a2a*1|and it follows that also
w((a1D1+a2D2)⋅(a1D1+a2D2)*)≥0Now this last argument just needs to generalize to linear combinations of more than two chord diagrams. Does it?
So I’d need something like “cosine rule” for permutations…
For any n∈ℕ, n≥1, let
⟨−,−⟩:Sym(n)×Sym(n)⟶ℕbe given by sending a pair of permutations (σ1,σ2) to N to the number of cycles in σ1∘σ−12.
Then I need the inequality
⟨σ1,σ2⟩+⟨σ2,σ3⟩−⟨σ1,σ3⟩≤32Nnfor 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?
John Baez has been writing a series of posts on permutations, I could ask.
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∈ℕ with n,N≥2.
On the complex linear span ℂ[Sym(n)] of the set of permutations of n elements, consider the inner product
⟨−,−⟩N:ℂ[Sym(n)]×ℂ[Sym(n)]⟶ℂwhich on pairs of complex multiples (a1⋅σ1,a2⋅σ2), for ai∈ℂ and σi∈Sym(n), is given by
⟨a1⋅σ1,a2⋅σ2⟩N≔a1a*2⋅N#cycles(σ1∘σ−12)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)] we have
⟨Σ,Σ⟩≥0∈ℝ⊂ℂ??
[ added the previously missing exponentials in the formula –should really postpone talking about this until I have more spare time and am more awake ]
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 w2 induced by the fundamental representation 2 of 𝔤𝔩(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 wN⋅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.
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…
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) with the set of all transpositions as generators, then the distance between two permutations (σ1,σ2) is (n− the number of cycles in σ1⋅σ−12).
Shall I ask about the inequality in #15?
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.
Is that a coincidence that where #cycles(σ1⋅σ−12)−Nf appears in (13) in your article, that is (−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.
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∘σ−12) 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?
Well let’s give it a go: we need that ∑i,jaiˉaj2#cycles(σi∘σ−1j)≥0.
So we need to know about ∑i,jaiˉaj2Nf−d(σi,σj), and so just ∑i,jaiˉaj2−d(σi,σj).
Entering positive semidefinite kernel territory. Doesn’t work in general, but maybe the Cayley graph has nicer properties.
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…
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.
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.
Aha, it seems there’s an issue.
Thanks for checking. We’d just need t=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…
Ok, we had some more from Mark here. Seems reasonable to think that the values of t for which positive semi-definiteness is achieved will depend on n, no? But you want a fixed N in #24 to work for all n?
Thanks. So for the conjecture described in the note, we have
N=2
n∈ℕ arbitrary.
Equivalently, rewriting N=exp(t) this is
t=ln(2)
n∈ℕ arbitrary.
From computer experiment it does look that with these choices the statement
t⋅d(−,−) is a conditionally positive kernel on the Cayley graph of 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) and n arbitrary?
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.
John Baez writes about |Gk(n)|, the number of permutations on n with k cycles, here.
Not sure what to make of this. Please help me out: What’s the implication you have in mind?
According to Mark Meckes, after application of the Gershgorin circle theorem, the semipositive definiteness of exp(−td(x,y)) on S(n) holds when
1n!∑σ∈Sym(n)exp[tC(σ)]≤(1+1n!)etn,where C(σ) counts the number of cycles in σ.
Though now I look more closely, I’m not sure I see one of his steps. But have to dash.
Thanks. Now I see what you are getting at.
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.
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.
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.
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.
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 (i1i2i3⋯ik). 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). 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…
The Mallow kernel for adjacent transpositions is positive definite for all t. 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) there’s a difference. With all transpositions the Cayley graph is the complete bipartite graph K3,3, which contains K3,2, which is a minimal example of a metric space which is not of negative type. Hence for general t the associated kernel exp(−td(x,y)) is not positive semidefinite.
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 a in your last line, so that the sum of ai is zero, but you speak there of all complex functions.
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 t. 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.
Just briefly, as I should certainly be writing funding proposals over assisting in someone else’s theorem-proving, the use of general t 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 t-dependence in your case. Your choice of t=ln(2) is arbitrary. You’re just hoping that there’s a fixed value of t that works for all n in Sym(n). You may have done some computer checks, but do you know that as n in Sym(n) grows sufficiently large that this will continue to hold? Perhaps min(t)n, the smallest value of t for which exp(−td(x,y)) on S(n) is positive semidefinite, grows without bound as n increases.
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. ;-)
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) the following 5 permutations (following this slide by J. Marail & J.-P. Vert)
123↙↓↘213132321↘↓↙312Shown 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(−λ⋅dC(−,−))has negative eigenvalues for λ≤.346 and becomes positive definite somewhere between that and λ≥.347.
So for the value λ=1 that I am interested in, this is not a counter-example. But it does suggest that for any value of λ there might be an nλ such that the Cayley distance kernel fails to be positive definite on Sym(>nλ).
If that is the case, I want to understand this nλ. (In the intended application, this is the number of D8-branes, which indeed is not supposed to be unbounded. So if nλ=1 turns out to be a power of 2, for instance, that would be most interesting.)
Now I should really go all the way with this example and just compute the kernel on all of Sym(3).
First, for the Cayley graph of Sym(3), it has the above edges
123↙↓↘213132321↘↓↙312and in addition the following edges
⋮213132321↘↓↙231I think.
Ordering these vertices by their appearance in the above, the corresponding Cayley distance matrix is
dC=[011122102211120211122011211102211120]Asking again WolframAlpha to compute the eigenvalues of the corresponding kernel e−λdC I get two interesting results:
the critical value of λ, where the negative eigenvalues disappear, is already much larger than for the subgraph above: it’s somewhere around λ≥.694 (here) – removing one node it was just around .347 (here).
for λ=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≤3, for what it’s worth.
On p. 72 of this there’s something (5.10) on using group characters to calculate the Cayley distance for all transpositions.
Thanks for the pointer. That’s a curious formula.
But I am thinking now: If we expect the Cayley distance kernel on Sym(n) to be positive definite (a) only for some n≤nλ=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,⋯ until it breaks.
Wait, why do I keep saying λ=1. I need λ=ln(2)… checking… which seems to be exactly that critical value where the kernel becomes positive semi-definite: here
n!×n! matrices for n=4,5,6,⋯.
I guess one useful thing might be a few lines earlier: to find the distance between σ1 and σ2, you just need the cycle type of σ1⋅σ−12. Sum of one less than the length of each cycle.
Could there be something neat about that last eigenvector in your calculation in #52? Signs of the permutations?
Oh, the eigenvectors don’t change as you vary λ. Why?
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?
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.
And it goes through zero at λ=ln(2)!
Looking at the eigenvalues for your λ=1 calculation, the first (and sixth) seem to involve a (alternating) sum over numbers in conjugacy classes weighted by powers of e−1.
And replacing e by 2, you get the eigenvalues for λ=ln(2).
I could imagine that continuing for higher n.
E.g, for n=4, with conjugacy classes 1,2,22,3,4 and corresponding numbers of elements 1,6,3,8,6, then 1/1−6/2+3/4+8/4−6/8=0 at λ=ln(2).
For S5, 1/1−10/2+15/4+20/4−20/8−30/8+24/16=0.
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)
Hold on. It’s that given the λ appearing in the kernel, then the eigenvalues are
e2λ−1e2λ, etc.
So then if λ>0, then this eigenvalue is positive. With the smallest eigenvalue, it will be positive so long as eλ>2, or λ>ln(2).
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.
Returning to #36
According to Mark Meckes, after application of the Gershgorin circle theorem, the semipositive definiteness of exp(−td(x,y)) on S(n) holds when
1n!∑σ∈Sym(n)exp[tC(σ)]≤(1+1n!)etn,where C(σ) counts the number of cycles in σ.
In the case that t=ln(2), we can apply the formula here for β=2. Then it looks like we need
1n!i=n−1∏i=0(2+i)≤(1+1n!)2n,which is
n+1≤(1+1n!)2n.And that holds.
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 nLab, in order to absorb them better…
Is Meckes’ statement in his “Lecture notes on matrix analysis” (pdf)?
Hm, but that inequality from #67 fails already for n=3, for which we know the statement to be true.
I think it was only a sufficient condition, not necessary. I don’t know how tight this Gershgorin circle theorem is.
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…
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−λ⋅nn−1∏k=0(eλ+k)−1But 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.
The discs are centred on 1, no?
oh, I missed an exponential there, right. Will fix, thanks
Calculating the radius from a row, you need to leave out the diagonal element.
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.
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.
Sure, I just missed an exponential (e0 as opposed to 0). I think otherwise I am not confused. :-) But you are right to sanity check me here, thanks.
So when is
e−λ⋅nn−1∏k=0(eλ+k)−1≤1???
Firing up WolframAlpha once more…
Hm, something is wrong. Asking about the above inequality for n=3 gives me λ>0.15... here, way off from the λ≥ln(2) established before.
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?
Sanity check: is there a mixing up of the exponential of the matrix of distances and the matrix of exponentiated distances going on?
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…
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∈ℕ there is N∈ℕ such that the fundamental sl(ℂ,N)-Lie algebra weight system on horizontal chord diagrams on n strands is a quantum state.
Proof: That Gershogin radius decreses monotonically (and rapidly) with λ, so just making λ=ln(N) arbitrarily large by making N 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.
Re #82, that looks right.
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).
Yes, that looks right in #78.
Re #83, Mark provided a value of λ by other means which makes the kernel positive definite, λ=ln(n!)−1.
Perhaps #78 is tighter. But in any case, it would be interesting to know if there is a critical value of n for λ=ln(2), as in your Remark 4.8.
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,ℂ)-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.
Does the eigenvalue I pointed out at Cayley distance kernel mean anything in this context? I guess one thing is that for given Sn, then for the early natural number values of eλ, including the 2 of your note, the eigenvalue is 0 and thereafter positive. So this eigenvalue can’t be responsible for non-positive-semidefiniteness at natural number eλ.
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, mod2 a boson/fermion grading (“s-rule”). This means that weighing diagrams by (−1)degree is a natural operation, as it will appear in super-traces/super-partition functions. This is reminiscent of your sgn(σ) weight, though it’s not the same, in general.
Yeah, so I don’t know yet. But would like to understand this better.
1 to 91 of 91