A bold linear algebra problem

If T is an area preserving homeomorphism of the two dimensional torus, it can be approximated uniformly by permutations $\pi$ of $n=m^2$ squares $Q_k$ of size 1/m. The orbit of the map $T$ is a permutation $\pi$ of the squares. For example, if $T(x,y)=(x+1/m,y)$ then $\pi$ is a permutation of the n squares which consists of m cycles. Let $(x_k,y_k)$ be the left lower corner of a square $X_k$ . Define the matrix valued map $A(x) = \left[ \begin{array}{cc} e+c \cos(2\pi x) & -1 \\ 1 & 0 \end{array} \right]$ and define $Q=[0,1]^n$ , we can look at the function $f(T,q) =tr(A(x_{\pi(n)}/m+q_n/m) \cdots A(x_{\pi(1)}/m+q_1/m)$. It is a trigonometric polynomial in the n variables $q_1, \dots q_n$ . What we see numerically is that for every permutation $\pi$ or transformation T respectively, the maximum $\max_{q \in Q} f(T,q)$ is $\geq \log(c/2)$ . This is a bold linear algebra problem, discussed already last week.

I studied related problems for many years. In 1998/1999 I did not take the maximum but took $q_k=\alpha$ and integrated over $\alpha$ . The maximum has the advantage that we see the estimate to hold for all n and not just for large enough n. We can reformulate the above problem as in the youtube presentation of today. It case $n=m^2$ makes small $n$ cases already work so that the uniform conjecture can be formulated. If we just take permutations of $n$ intervals of length $1/n$ partitioning $[0,1]$ the uniform estimate does not hold for smaller n, but the proof suggestion below would get it done for large enough n and still imply the strong consequences we were talking about. To establish it then also for smaller n would require more technical effort (if the proof at all would go through).

One of the consequences of the bold linear algebra problem would be to show that the metric entropy of the standard map $T(x,y) = (2x+c \sin(x)-y,x)$ is larger or equal than $\log(|c|/2)$ for any real $c$ (by Pesin). An other consequence would be that every random Jacobi operator $(Lu)(n)= u(n+1)+u(n-1) + c \cos(2\pi x_n) u(n)$ has no absolutely continuous spectrum for almost every initial point $(x_0,y_0)$ on the torus, if $T: \mathbb{T}^2 \to \mathbb{T}^2$ is an ergodic area preserving homeomorphism (by Kotani). The reason is Lax theorem allowing to approximate an area preserving homeomorphism to be approximated by periodic permutations of cubes (squares) and then upper-semicontinuity of the integrated Lyapunov exponent as a function of $L^{\infty}(X,SL(2,\mathbb{R}))$ , noting that it is the liminf of continuous functions. I established in 1993 that the Lyapunov exponent is positive on a dense set of cocycles if the map $T$ is aperiodic and fixed and that we in general have discontinuity. There are always cocycles A with positive exponents which can be approximated uniformly by cocycles with zero exponents.

Again, to repeat from last time, the bold linear algebra problem is much stronger than these consequences but making a problem stronger does in general not make it harder. It can make it easier as we can do not have to bother with a particular transformation but establish it for all transformations. Obviously as the function $f(T,q)$ is the same when composing its permutation with a cyclic permutation (by the trace invariance), we only have to establish that if it holds for a permutation, then it holds also for a permutation in which the first two elements are flipped. The reason is that we can use cyclic conjugations to get any adjacent elements flipped and so can bubble sort the permutation. We need less $n^2$ steps to do that. The flip of the first two elements is a special pancake flip but the entire difficulty is already there. If we flip the first two elements in a product of three matrices, a very large trace can become small. The elementary relation $tr(A(x) A(y) B) - tr(A(y) A(x) B) = (B_{21}-B_{12})(x-y)$ illustrates this and it also gives immediately an idea how to solve the problem. If we have established the bold result for a specific transformation, we can modify the transformation by a flip of the first two elements if the matrix $B$ which is the product of the last $n-2$ matrices has the property that the side diagonals have different sign. Call g(T,q) the function which establishes with $g(T,q)=0$ that we can flip, we can now just use a gradient flow on the manifold M where $f(T,q)=(c/2)^n$ to get to $g(T,q)=0$ . This is possible in time which exponentially small in n if we can establish that the gradients of f,g are not parallel and large. The gradient flow is $q' = - P( \nabla g(q))=F(q)$ , where $P v = v - (v \cdot \nabla f) \nabla f/|\nabla f|^2$ is the projection onto the tangent space of $M$ in $Q$ .

If we are on $M$ , then the gradients of f and g involve matrix entries of $A^n$ and $A^{n-2}$ and so are exponentially large and also should not correlate too much. These are technical conditions to check, but if $F(q)$ has exponentially large length in $Q$ , then we need only exponentially small time to reach from a starting point the manifold $g=0$ where we can safely apply the flip and keep the value $f$ . Once we have flipped, the entire process starts again. We are again on $M$ but the manifold now looks different. But again, we can move on $M$ towards $g=0$ with an exponentially small change of q. After less than $n^2$ such steps we have reached any transformation for which we wanted to check the bold result.

Author: oliverknill