Tighter lower bound of the lower triangular sum of an arbitrary Latin square

Question

This is a generalization of this question.In a "restricted" Latin square consists of natural numbers $1,2, ..., n$ with each number appearing in each row, column and diagonal exactly once, what is the minimal sum of the lower triangle below the main diagonal? What is a tighter lower bound for arbitrary $n$ dimensions tighter than the one presented below?

There are $n-1$ columns (rows) in the lower triangle. Aach number can appear there at most $n-2$ times while there are $\frac12n(n-1)$ entries to fill. So the minimum sum has to be greater than the sum of $\Big\{1,2,\cdots,\big\lfloor\frac{n(n-1)}{2(n-2)}\big\rfloor\Big\}$ with $\big\lfloor\frac{n(n-1)}{2(n-2)}\big\rfloor=\big\lfloor\frac n2\big\rfloor+1$ for $n>6$ appearing $n-2$ times and $\big\lfloor\frac n2\big\rfloor+2$ appearing the remainging number of times to fill out the $\frac12n(n-1)$ number of entries. Summing this arrangement we get a lower bound we desire.

Answer 1

The LP relaxation from the linked question appears to yield lower bound $(n+1)^2(n-1)/6$ for odd $n$. A simpler but weaker LP (with decision variables $1 \le y_{i,j} \le n$ and row/column/diagonal sums $n(n+1)/2$) appears to yield lower bound $(n^2+4n-1)(n-1)/8$ for odd $n$ and $n(n+4)(n-1)/8$ for even $n$.

The weaker LP is to minimize $\sum_{i=1}^n \sum_{j=1}^{i-1} y_{i,j}$ subject to $$ \begin{align} \sum_{j=1}^n y_{i,j} &= n(n+1)/2 &&\text{for $i \in\{1,\dots,n\}$} \\ \sum_{i=1}^n y_{i,j} &= n(n+1)/2 &&\text{for $j \in\{1,\dots,n\}$}\\ \sum_{i=1}^n y_{i,i} &= n(n+1)/2 \\ \sum_{i=1}^n y_{i,n-i+1} &= n(n+1)/2 \\ 1 \le y_{i,j} &\le n &&\text{for $i,j \in\{1,\dots,n\}$} \end{align} $$ You can obtain this formulation from the linked one via the change of variables $y_{i,j}=\sum_{k=1}^n k\ x_{i,j,k}$.

For $n=5$, an optimal solution is

3 5 5 1 1 
1 3 5 5 1 
1 1 3 5 5 
5 1 1 3 5 
5 5 1 1 3 

The conjectured formulas arise from inspection of the optimal objective values for small $n$. For any given $n$, an optimal dual solution provides a lower bound, but I don't have a simple proof that works for all $n$.