, 2018

First of all, we show that we may not take a larger constant $K$. Let $t$ be a positive number, and take
$$x_2 = x_3 = \cdots = t \text{ and } x_1 = -\frac{1}{2t}.$$
Then, every product $x_i x_j$ ($i \ne j$) is equal to either $t^2$ or $(-1/2)$. Hence, for every permutation $y_i$ of the $x_i$, we have
$$y_1 y_2 + \cdots + y_{n-1} y_n \ge (n-3)t^2 - 1 \ge -1.$$
This justifies that the $n$-tuple $(x_1, \cdots, x_n)$ is Shiny. Now, we have
$$\sum_{i<j} x_i x_j = -\frac{n-1}{2} + \frac{(n-1)(n-2)}{2} t^2.$$

indices for $z_i$ will always be taken modulo $n$. We will first split up the sum $\sum_{i<j} x_i x_j = \sum_{i<j} z_i z_j$ in to $[(n-1)/2]$ expressions, each of the form $y_1 y_2 + \cdots + y_{n-1} y_n$ for some permutation $y_i$ of the $z_i$, and some leftover terms. More specifically, write
$$\sum_{i<j} z_i z_j = \sum_{q=0}^{n-1} \sum_{\substack{i+j=q \\ i \neq j \pmod{n}}} \sum_{\substack{(\text{mod } n) \\ (\text{mod } n)}} z_i z_j = \sum_{p=1}^{[(n-1)]/2} \sum_{\substack{i+j=2p-1,2p \pmod{n} \\ i \neq j \pmod{n}}} \sum_{\substack{(\text{mod } n) \\ (\text{mod } n)}} z_i z_j + L, \quad (1)$$
where
$$L = z_1 z_{-1} + z_2 z_{-2} + \cdots z_{(n-1)/2} z_{-(n-1)/2} \text{ if } n \text{ is odd,}$$
and
$$L = z_1 z_{-1} + z_2 z_{-2} + \cdots z_{(n-2)/2} z_{-n/2} \text{ if } n \text{ is even.}$$
We note that for each $p = 1, 2, \dots, [(n-1)/2]$, there is some permutation $y_i$ of the $z_i$ such that
$$\sum_{\substack{i+j \equiv 2p-1, 2p \pmod{n} \\ i \neq j \pmod{n}}} z_i z_j = \sum_{k=1}^{n-1} y_k y_{k+1},$$
because we may choose
$$y_{2i-1} = z_{i+p-1} \text{ for } 1 \le i \le (n+1)/2$$
and
$$y_{2i} = z_{p-i} \text{ for } 1 \le i \le n/2.$$
We show Eq. (1) graphically for $n = 6, 7$ in the diagrams below. The edges of the graphs each represent a product $z_i z_j$, and the dashed and dotted series of lines represents the sum of the edges, which is of the form $y_1 y_2 + \cdots y_{n-1} y_n$ for some permutation $y_i$ of the $z_i$ precisely when the series of lines in a Hamiltonian path. The filled edges represent the summands of $L$.

$$\sum_{i<j} z_i z_j \geq -\left[\frac{n-1}{2}\right] + L.$$
It remains to show that, for each $n$, there exists some permutation $z_i$ of the $x_i$ such that $L \ge 0$ when $n$ is odd, and $L \ge -1/2$ when $n$ is even. We now split into cases based on the parity of $n$ and provide constructions of the permutations $z_i$.
Since we have not made any assumptions yet about the $x_i$, we may now assume without loss of generality that
$$x_1 \le x_2 \le \dots \le x_k \le 0 \le x_{k+1} \le \dots \le x_n. \quad (2)$$
Case 1: $n$ is odd.
Without loss of generality, assume that $k$ (from Eq. (2)) is even, because we may negate all the $x_i$ if $k$ is odd. We then have
$$x_1 x_2, x_3 x_4, \dots, x_{n-2} x_{n-1} \ge 0$$
because the factors are of the same sign. Let
$$L = x_1 x_2 + x_3 x_4 + \dots + x_{n-2} x_{n-1} \ge 0.$$

We choose our $z_i$ so that this definition of $L$ agrees with the sum of the leftover terms in Eq. (1). Relable the $x_i$ as $z_i$ such that
$$\{z_1, z_{n-1}\}, \{z_2, z_{n-2}\}, \dots, \{z_{(n-1)/2}, z_{(n+1)/2}\}$$
are some permutation of
$$\{x_1, x_2\}, \{x_3, x_4\}, \dots \{x_{n-2}, x_{n-1}\},$$
and $z_n = x_n$. Then, we have
$$L = z_1 z_{n-1} + \dots + z_{(n-1)/2} z_{(n+1)/2}, \text{ as desired.}$$
Case 2: n is even.
Let $L = x_1x_2 + x_2x_3 + \cdots + x_{n-1}x_n$. Assume without loss of generality $k \neq 1$. Now, we have
$$\begin{align*} 2L &= (x_1x_2 + \cdots + x_{n-1}x_n) + (x_1x_2 + \cdots x_{n-1}x_n) \\ &\geq (x_2x_3 + \cdots x_{n-1}x_n) + x_kx_{k+1} \\ &\geq x_2x_3 + \cdots x_{n-1}x_n + x_nx_1 \geq -1, \end{align*}$$
where the first inequality holds because the only negative term in $L$ is $x_k x_{k+1}$, the second inequality holds because $x_1 \le x_k \le 0 \le x_{k+1} \le x_n$, and the third inequality holds because the $x_i$ are assumed to be Shiny. We thus have that $L \ge -1/2$. We now choose a suitable $z_i$ such that the definition of $L$ matches the leftover terms in Eq. (1).
Relables the $x_i$ with $z_i$ in the following manner: $x_{2i-1} = z_{-i}$, $x_{2i} = z_i$
(again taking indices modulo $n$). We have that
$$L = \sum_{\substack{i+j \equiv 0, -1 \pmod{n} \\ i \neq j \pmod{n}}} z_i z_j,$$

We present another proof that
$$\sum_{i<j} x_i x_j \geq -\frac{n-1}{2} \quad \text{for any Shiny n-tuple } \{x_1, \dots, x_n\}.$$
Assume an ordering of the $x_i$ as in Eq. (2), and let $\ell = n-k$. Assume without loss of generality that $k \ge \ell$. Also assume $k \ne n$, (as otherwise, all of the $x_i$ are nonpositive, and so the inequality is trivial). Define the sets of indices $S = \{1, 2, \dots, k\}$ and $T = \{k+1, \dots, n\}$. Define the following sums:
$$K = \sum_{\substack{i<j \\ i,j \in S}} x_i x_j, \quad M = \sum_{\substack{i \in S \\ j \in T}} x_i x_j, \quad \text{and} \quad L = \sum_{\substack{i<j \\ i,j \in T}} x_i x_j.$$
By definition, $K, L \ge 0$ and $M \le 0$. We aim to show that
$$K + L + M \geq -\frac{n-1}{2}.$$
We split into cases based on whether $k = \ell$ or $k > \ell$.
*Case 1: $k > \ell$.*
Consider all permutations $\phi : \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$ such that $\phi^{-1}(T) = \{2, 4, \dots, 2\ell\}$. Note that there are $k!\ell!$ such permutations $\phi$. Define
$$f(\phi) = \sum_{i=1}^{n-1} x_{\phi(i)} x_{\phi(i+1)}.$$
We know that $f(\phi) \ge -1$ for every permutation $\phi$ with the above property. Averaging $f(\phi)$ over all $\phi$ gives
$$-1 \le \frac{1}{k!\ell!} \sum_{\phi} f(\phi) = \frac{2\ell}{k\ell} M + \frac{2(k-\ell-1)}{k(k-1)} K,$$

$$K + L + M \geq K + L + \left( -\frac{k}{2} - \frac{k-\ell-1}{k-1}K \right) = -\frac{k}{2} + \frac{\ell}{k-1}K + L.$$
Since $k \leq n-1$ and $K, L \geq 0$, we get the desired inequality.

Case 2: $k = \ell = n/2$.
We do a similar approach, considering all $\phi : \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$ such that $\phi^{-1}(T) = \{2, 4, \dots, 2\ell\}$, and defining $f$ the same way. Analogously to Case 1, we have
$$-1 \leq \frac{1}{k!\ell!} \sum_{\phi} f(\phi) = \frac{2\ell - 1}{k\ell} M,$$
because there are $k\ell$ products in $M$, of which $(2\ell - 1)$ are selected for each $\phi$. Now, we have that
$$K + L + M \geq M \geq -\frac{n^2}{4(n-1)} \geq -\frac{n-1}{2},$$
where the last inequality holds because $n \geq 4$.