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
made explicit also here that
$\big(\mathcal{A}_n^{pb}, \circ\big) \;\simeq\; \mathcal{U}(\mathcal{L}_n(D)) \,.$(now this Prop.)
The algebra $\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 $\mathcal{A}^{{}^{pb}}$ as a star-algebra?
Question: Which weight systems $w \colon \mathcal{A}^{{}^{pb}} \to \mathbb{F}$ would be positive with respect to this star-structure, in that
$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?
added the concept of weight systems that are states:
With respect to this star-algebra-structure one may ask (setting $R \coloneqq \mathbb{C}$ for definiteness) whether a given weight system
$w \;\colon\; \mathcal{A}_n^{{}^{pb}} \longrightarrow \mathcal{C}$is a state on a star-algebra in that for any $D \in \mathcal{A}_n^{{}^{pb}}$ we have that the value of $w$ on the corresponding normal operator $D \cdot D^\ast$ is a non-negative real number:
$\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?
[ 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 $\mathfrak{gl}(N, \mathbb{C})$-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^\ast$ similarly represents the inverse permutation, so that $D \cdot D^\ast$ is the trivial permutation with $\# cycles = \# strands$ we have
$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_1 D_1 + a_2 D_2$ we use that whatever $D_1$ and $D_2$ are, the permutation corresponding to $D_1 \cdot D_2^\ast$ has (as any permutation) at most as many cycles as there are strands: $\# cycles \leq \# strands$. Thus the triangle inequality shows that
$\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\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?
So I’d need something like “cosine rule” for permutations…
For any $n \in \mathbb{N}$, $n \geq 1$, let
$\langle -,-\rangle \;:\; Sym(n) \times Sym(n) \longrightarrow \mathbb{N}$be given by sending a pair of permutations $(\sigma_1, \sigma_2)$ to $N$ to the number of cycles in $\sigma_1 \circ \sigma_2^{-1}$.
Then I need the inequality
$\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?
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 \in \mathbb{N}$ with $n,N\geq 2$.
On the complex linear span $\mathbb{C}[Sym(n)]$ of the set of permutations of $n$ elements, consider the inner product
$\langle -,-\rangle_N \;:\; \mathbb{C}[Sym(n)] \times \mathbb{C}[Sym(n)] \longrightarrow \mathbb{C}$which on pairs of complex multiples $(a_1\cdot \sigma_1, a_2\cdot \sigma_2)$, for $a_i \in \mathbb{C}$ and $\sigma_i\in Sym(n)$, is given by
$\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 $\Sigma \in \mathbb{C}[Sym(n)]$ we have
$\langle \Sigma, \Sigma \rangle \geq 0 \in \mathbb{R} \subset \mathbb{C}$??
[ 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 $w_{\mathbf{2}}$ induced by the fundamental representation $\mathbf{2}$ of $\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 \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.
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 $(\sigma_1,\sigma_2)$ is ($n -$ the number of cycles in $\sigma_1 \cdot \sigma_2^{-1}$).
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(\sigma_1 \cdot \sigma_2^{-1})-N_f$ 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 $(\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?
Well let’s give it a go: we need that $\sum_{i,j} a_i \bar{a}_j 2^{\#cycles(\sigma_i \circ \sigma_j^{-1})} \geq 0$.
So we need to know about $\sum_{i,j} a_i \bar{a}_j 2^{N_f - d(\sigma_i, \sigma_j)}$, and so just $\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.
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 \in \mathbb{N}$ arbitrary.
Equivalently, rewriting $N = exp( t )$ this is
$t = ln(2)$
$n \in \mathbb{N}$ arbitrary.
From computer experiment it does look that with these choices the statement
$t\cdot 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 $|G_k(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(-t d(x,y))$ on $S(n)$ holds when
$\frac{1}{n!} \sum_{\sigma \in Sym(n)} exp[t C(\sigma)] \le \left(1+\frac{1}{n!}\right) e^{t n},$where $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.
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 $(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, \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…
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 $K_{3,3}$, which contains $K_{3,2}$, which is a minimal example of a metric space which is not of negative type. Hence for general $t$ the associated kernel $exp(-t d(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 $a_i$ 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(-t d(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. ;-)
1 to 47 of 47