# Start a new discussion

## Not signed in

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

## Site Tag Cloud

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

• CommentRowNumber1.
• CommentAuthorUrs
• CommentTimeApr 20th 2021

for completeness, to go alongside Mallows kernel

• 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^{- \lambda \cdot n } \, \underoverset {k = 0} {n - 1} {\prod} \big( e^{\lambda} + k \big) - 1$
• CommentRowNumber3.
• CommentAuthorUrs
• CommentTimeApr 21st 2021

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

• 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.

• CommentRowNumber5.
• CommentAuthorDavid_Corfield
• CommentTimeApr 22nd 2021

Things about other rows need saying, e.g., how $sgn$ 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=5$

1 is placed in the first cycle: $x$

2 either starts a new cycle or is placed in the same cycle as 1: $x + 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 + 2$

and so on.

When adding a new element $k$ to existing cycles, one has to see that there are $k-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 $x$”, or even just “colon $x$”, 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

$\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 $x$ and write

$\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 $x$, 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)\ldots(x + n-1)$ taking it as $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 $x$s and $1$s, where the latter appearing in the $k$th place are indexed by a natural number between $1$ and $k-1$.

Each of these is a recipe to form a unique permutation on $n$ elements. If $x$ appears $k$ times, there are $k$ cycles.

E.g., for $n=5$, given $x\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 $1$ to $n$, build a term of $x$s and indexed $1$s, according to whether a given $k$ heads a new cycle, $x$, or occurs in the $r$th available spot, $1_r$. There are $k-1$ such available spots.

• CommentRowNumber12.
• CommentAuthorUrs
• CommentTimeApr 22nd 2021

Sorry, I still need to ask: Why is your example not $(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 $k$, then look at the $k$th term. If $x$, start a new cycle; if $1_r$, place in the cycle containing $r$ 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

$\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.

• 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)$ to be positive at inverse temperature $\beta = ln(N)$:

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

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

Still need to prove that this has a solution $N$ for all $n$….

• 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 $N$:

$\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.

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

is $\frac{N(N+1) \ldots (N+n-1)}{N \cdot N \ldots N}$ which is certainly less than $(\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 \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

• CommentRowNumber22.
• CommentAuthorDavid_Corfield
• CommentTimeApr 22nd 2021

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

• 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_n$. But maybe if Carlo achieves a symbolic computation for $S_4$ that will be enough to show the pattern.

• CommentRowNumber25.
• CommentAuthorDavid_Corfield
• CommentTimeApr 22nd 2021

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

• 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)

• CommentRowNumber29.
• CommentAuthorDavid_Corfield
• CommentTimeApr 23rd 2021

Since this result relies on $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!-2$ other eigenvectors then. Looking at the WolframAlpha calculation for $S_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.

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

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

• 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_n$, $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 \lt e^{\beta} \lt n-1$, and indeed for $n- 2a \lt e^{\beta} \lt n -2a+1$.

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

If for $S_4$, this eigenvalue is negative $2 \lt e^{\beta} \lt 3$, and for $S_5$, it’s $3 \lt e^{\beta} \lt 4$ and $1 \lt e^{\beta} \lt 2$, doesn’t the $2 \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_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 - #cycles$ that distances are preserved since as $n$ increases by $1$, one more cycle is added under $i$.

• 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_n$, positive semi-definiteness fails for $e^{\beta} \lt n-1$, except for integral values of $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 $\beta \lt ln(2)$

• it’s positive definite for $\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^{\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)$. (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)$ (here), kindly provided by a CAS oracle

• 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)$ (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) \beta}$ times

• sum over conjugacy classes of

• number of elements in each class

• times $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^1$, so along with the 3 elements in class $2^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(\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_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^4$, $1^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 $e$, so (n - #cycles). Of course, $3^1$ is a pair of cycles $3 \cdot 1$, so at distance $4-2$ from $e$.

• 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^{\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^{\beta} \pm r)$ for various integer values of $r$. In the $S^4$ case we’re seeing $(e^{\beta} - 2)(e^{\beta} - 1)(e^{\beta} +1)$ and $(e^{\beta} + 2)(e^{\beta} - 1)(e^{\beta} +1)$. I

It’s pretty clear that for positive $e^{\beta}$ until $n-1$, positive semi-definiteness is achieved at integral values up to $n-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)$, as a function of the exponentiated inverse temperature: here

[ ah, need to improve these plot bounds…]

• CommentRowNumber55.
• CommentAuthorDavid_Corfield
• CommentTimeApr 25th 2021

I added in my argument from #32.

• CommentRowNumber56.
• CommentAuthorDavid_Corfield
• CommentTimeApr 25th 2021

Is the assumption still that $\beta \gt 0$? Otherwise the plots show that $e^{\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_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 $\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

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

$\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$, thus changing $(e^\beta - k)$ to $(-e^\beta + k)$ on the right. Then the previous form of the Lemma applies with weight $-e^{\beta}$ for each cycle and gives that the left hand side should be that sum with a prefactor of $(-1)$ to the number of cycles plus (or minus) $n$. Finally, if $n$ 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)$ 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

• 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^{\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^{\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^{\beta} \;\geq\; \frac{n - 1}{ 3^{1/n} - 1 }$

which is not much of an improvement. Instead of “3” we’d want $2^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

$\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 $N$ is much larger than $n$, while close to our expected actual bound, $N \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_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_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^{\beta}$ will have roots generalizing the pattern for $S_4$ of

$\{-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 \}$.

This tallies with the $S_3$ case with roots

$\{-2, -1\}, \{-1, 1\}, \{1, 2\}$

which with the missing $0$s is really

$\{-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(\sigma)$, choose a representation of dimension $r$ represented as an $r \times r$ matrix. Then taking any of the $r^2$ components will give you an eigenvector.

That would explain the eigenvalue multiplicities so far, for $S_3$, $1,1,4$, for $S_4$, $1, 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

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: $\frac{1}{d_k} \sum_{g: G} \alpha(g) \chi_k(g)$

• CommentRowNumber68.
• CommentAuthorDavid_Corfield
• CommentTimeApr 26th 2021

Added something on finding all eigenvalues.

• CommentRowNumber69.
• CommentAuthorDavid_Corfield
• CommentTimeApr 26th 2021

A quick look at $S_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^\beta \geq \frac{n-1}{2^{1/n} - 1}$ to $e^\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.)

• CommentRowNumber76.
• CommentAuthorDavid_Corfield
• CommentTimeApr 28th 2021

I think the next step is into the world of symmetric functions meets characters for $S_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_n$, the Schur function $s_{\lambda}$ corresponding to rep $\lambda$ is $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_{\sigma}(x_1, \ldots, x_n) = \prod p_{{\lambda}_i}$, for $\lambda_i$ the cycle lengths in $\sigma$, and $p_k(x_1, \ldots, x_n) = x_1^k + \ldots +x_n^k$.

Then setting each $x_i$ as $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_{\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_{\lambda}(x, \ldots, x)$ to have a nice simple factorization.

• CommentRowNumber78.
• CommentAuthorDavid_Corfield
• CommentTimeApr 28th 2021

Hmm, that only seems to allow $n$ as exponentiated by $# 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_{\lambda}(x, \ldots, x, 0, \ldots, 0)$, the first $t$ entries being $x$.

Then $s_{\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^{\beta} \in \{0,1, \cdots, n-1\}$ (and at $e^\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)}$ such that $s_{(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^{\beta} \in \{1,\cdots, n-1\}$ are non-negative to deduce that they vanish:

Because we already know that for $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 $sign$ gives $0$ at these integers from Lemma 4.2. Presumably the associated Schur polynomial involves mononomials such as $x_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, \ldots, n-1$ isn’t it? We just need the coefficient of the monomial $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^{- \beta \cdot d_C}$ is positive semi-definite on $Sym(n)$ for $e^{\beta} \in \{1,2, \cdots, n-1\}$ (and at least not indefinite for $e^\beta = n$).

This is great.

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

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

Looking good!

Don’t we know that it’s positive definite for $e^{\beta} = n$? The Schur polynomial $s_{\lambda}(x, \ldots, x)$ must be $a x^n$, for some positive integer $a$.

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

My hunch is that where the eigenvalues for $1$ and $sign$ are $\underoverset {k = 0} {n - 1} {\prod}\big(e^{\beta} + k \big)$ and $\underoverset {k = 0} {n - 1} {\prod}\big(e^{\beta} - k \big)$, that the others are $\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^\beta = n$ none of the arguments vanish. SO I have reworded statement and proof, to account for this.

• CommentRowNumber92.
• CommentAuthorDavid_Corfield
• CommentTimeApr 29th 2021

What about the principal submatrix idea?

Say for a given $n$, I’m wondering about definiteness for $e^{\beta} = m$, where $n \lt m$. But if it were other than positive definite there, then for $S_m$, it wouldn’t be positive definite at $e^{\beta} = m$. But we know that this isn’t the case. So for $S_n$, the kernel is positive definite for integer values $\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 $\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 $\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 $\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 $\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 $1$ and $sign$ are $\underoverset {k = 0} {n - 1} {\prod}\big(e^{\beta} + k \big)$ and $\underoverset {k = 0} {n - 1} {\prod}\big(e^{\beta} - k \big)$, the others are $\underoverset {k = -s} {n -s -1} {\prod}\big(e^{\beta} + k \big)$.

I guess in Lemma 4.12, we might as well use $1$ rather than $x$, and so have $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, \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, \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 $m$ and a partition of $n$ combine to a partition of $m + n$.

If my hunch is right then we’d be interested in how $\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 $\lambda \in S_n$, $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_6$ the rep corresponding to $(4,1,1)$ gives for $\sum_{\sigma} \chi^{(4,1,1)}(\sigma) x^{#Cycles(\sigma)}$: $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)$?

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

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