Optimal exponential memory for sequential Euclidean connections: edge-power costs and phase transitions

Abstract

We study the edge-power cost of the labelled tree generated by the $\gamma$-strategy, a constant-gain rule for sequential Euclidean connections. Starting with $x_0=p_0$, each input point $p_i$ is attached to $x_{i-1}$, and the state is updated by $x_i=\gamma x_{i-1}+(1-\gamma )p_i$. Retaining $x_i$ subdivides the insertion segment into a spine edge and a leaf edge. The memory parameter $\gamma$ controls how long earlier points influence subsequent attachment points. We minimize the sum of the $\alpha$-powers of the edge lengths under independent uniform input and arbitrary input sequences. For uniform points in the unit ball, the stationary problem has a transition at $\alpha =1$. Its continuous extension is minimized at the boundary for $0<\alpha \le 1$, while every global minimizer is interior for $\alpha >1$. We determine the finite optimizer in the joint window ${\alpha }_N=1+{\epsilon }_N$, ${\epsilon }_N\log N\to \lambda$. Below an explicit threshold it lies on the $N^{-1/2}$ scale, at the threshold its scale is $\sqrt{\log N/(N\log \log N)}$, and above the threshold it approaches an explicit stationary root with two computable corrections. A second threshold identifies the governing correction, and differentiated estimates prove eventual uniqueness. At $\alpha =3d+8$, the linear coefficient at the stationary endpoint changes sign and a branch of strict local maxima enters the parameter interval. For arbitrary input sequences, the optimal parameter and asymptotic worst-case edge-power cost per point are explicit for $0<\alpha \le 3$. At high powers, periodic antipodal block inputs give explicit lower bounds which, with a separation argument, show that the optimized cost is asymptotic to $2\log 2/\log \alpha$. Exact results for powers two and four, a rational recursion for every even power, and a high-dimensional expansion complete the analysis.

60 pages, 8 figures, 2 tables. Substantially expanded version with finite-size phase transitions, high-power adversarial bounds, high-dimensional asymptotics, and numerical validation. Numerical data: https://github.com/tashimir/optimal-exponential-memory-edge-power-data