nLab
Sandbox

(σ 1,σ 2)exp(td(σ 1,σ 2))is conditionally positive kernel ?? 1n! σSym(n)exp(tcycles(σ))(1+1n!)e tn \begin{aligned} & (\sigma_1,\sigma_2) \mapsto exp(-t d(\sigma_1,\sigma_2)) \;\; \text{is conditionally positive kernel} \\ \\ \overset{??}{\Leftrightarrow} \;\;\;\; & \frac{1}{n!} \sum_{\sigma \in Sym(n)} exp\big( t \cdot cycles(\sigma) \big) \;\le\; \left(1+\frac{1}{n!}\right) e^{t n} \end{aligned}

\ldots

Let nn \in \mathbb{N}, n2n \geq 2. On the complex linear span [Sym(n)]\mathbb{C}[Sym(n)] of the set of permutations on nn elements, consider the sesqui-linear form

(1)[Sym(n)]×[Sym(n)] , (a 1σ 1,a 2σ 2) a 1a 2 *2 (#cycles(σ 1σ 2 1)) \array{ \mathbb{C}[Sym(n)] \times \mathbb{C}[Sym(n)] & \overset{ \langle -,- \rangle }{\longrightarrow} & \mathbb{C} \\ ( a_1 \cdot \sigma_1 ,\; a_2 \cdot \sigma_2 ) &\mapsto& a_1 a_2^\ast \, 2^{ (\#\!cycles(\sigma_1 \circ \sigma_2^{-1})) } }


Question: Is (1) positive semi-definite?


Non-Answer: This here is not a counter-example:

Consider

  • σ 3\sigma_3 the cyclic shift by 1

  • σ 1\sigma_1 the cyclic shift by 2

  • σ 2\sigma_2 the cyclic shift by -2 (i.e. in the other direction)

Then if n=34kn = 3 \cdot 4 \cdot k is divisible by 12, we have

  • #cycles(σ 1σ 3 1)=#cycles(cyclic shift by 1)=1\#\!cycles (\sigma_1 \circ \sigma_3^{-1}) = \#\!cycles(\text{cyclic shift by 1}) = 1

  • #cycles(σ 1σ 2 1)=#cycles(cyclic shift by 4)=4\#\!cycles (\sigma_1 \circ \sigma_2^{-1}) = \#\!cycles(\text{cyclic shift by 4}) = 4

  • #cycles(σ 2σ 3 1)=#cycles(cyclic shift by 3)=3\#\!cycles (\sigma_2 \circ \sigma_3^{-1}) = \#\!cycles(\text{cyclic shift by 3}) = 3

and hence

|σ 1σ 2+σ 3| 2 =|σ 1| 2+|σ 2| 2+|σ 3| 22σ 1,σ 22σ 2,σ 3+2σ 1,σ 3 =32 n22 422 3+22 1 \begin{aligned} & \left\vert \sigma_1 - \sigma_2 + \sigma_3 \right\vert^2 \\ & = \left\vert \sigma_1 \right\vert^2 + \left\vert \sigma_2 \right\vert^2 + \left\vert \sigma_3 \right\vert^2 - 2 \langle \sigma_1, \sigma_2\rangle - 2 \langle \sigma_2, \sigma_3\rangle + 2 \langle \sigma_1, \sigma_3\rangle \\ & = 3 \cdot 2^n -2 \cdot 2^{4} - 2 \cdot 2^{3} + 2 \cdot 2^1 \end{aligned}

Last revised on February 10, 2020 at 05:49:54. See the history of this page for a list of all contributions to it.