david/HORK-albrecht

In his Nutshell paper, Albrecht suggested that his order conditions made many non-existence proofs much simpler compared to the Butcher order conditions, because they could use the fact that only $n$ vectors can be linearly independent in an $n$-dimensional space. Several examples of such proofs are given in Section 3 of that paper. He suggests that more research along these lines should be done, but it seems that it was never done.

More specifically, the general strategy of his proofs is roughly as follows (note that both the Butcher and Albrecht conditions are used):

Note that $\tau_2$ is non-zero for explicit methods (since the second component is just $a_{21}$ which must be non-zero). The order conditions amount to statements about vectors being orthogonal to $\tau_2$ (more generally, $\tau_i$). Call those vectors $\delta^{(1)},\delta^{(2)},\dots$.
Many vectors in $\delta^{(i)} have last component (or last few components) zero, so there exists $x R^{s-1}$ such that $u=\sum_i x_i \delta^{(i)} = 0$.
Therefore $u^T c^j = 0$ for $j=0,1,2,\dots$. Here $c$ is the vector of abscissae and $c^j$ denotes elementwise exponentiation.
The Butcher conditions constrain many of the inner products composing $u^T c^j$. We can write down a matrix whose row products with $x$ are the expressions $u^T c^j$, e.g.

\[M = \begin{pmatrix} e_1^T e & b^T e & b^T Ae & \cdots \\ e_1^T c & b^T c & b^T A c & \cdots \\ e_1^T c^2 & b^T c^2 & b^T A c^2 & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{pmatrix}\]

Then $Mx=0$, so $M$ must have zero determinant. This can often be shown impossible.

I went through the details of the proof for non-existence of 5-stage, 5th order methods in my notes.

I have attempted to go further with Albrecht’s approach. As a first attempt, I tried to examine explicit 7-stage 6th-order methods (they exist, but I wanted to see what I could prove about them). I found the following:

The order conditions dictate that 15 vectors are orthogonal to $\tau_2\ne 0$, so they lie in a 6D space.
5 such vectors can be constructed with last 3 components vanishing, so they lie in a 3D space.
The Butcher conditions constrain the inner products of those 5 vectors with $e, c, c^2$, and $Ac$.
Writing out the matrix $M$, it turns out that the conditions on inner products with $c^2$ and with $Ac$ give linearly dependent information, so no conclusion can be readhced.

New tack: look at vectors orthogonal to both $\tau_2$ and $\tau_3$ and assume that those two are also linearly independent.

There are 5 such vectors with last 2 components vanishing; they must lie in a 3D space.
Butcher conditions constrain their inner products with $e, c, c^2, c^3, Ac^2, CAc$. The last two turn out to give redundant information.
Forming the matrix $M$, it turns out that its determinant is identically zero if the Butcher conditions are satisfied!

I was finally able to show that (almost certainly) either $c_6=1$ or $c_7=1$ but I can’t find those notes. It seems very difficult to make further progress. Proving non-existence for $s=8,p=6$ would be very difficult since all the spaces would be one dimension higher than those I was looking at.