Jonathan Robert Landers Permutohedron geometry

Sorting as Gradient Flow on the Permutohedron

A continuous-time model of sorting as motion through space. A quadratic potential on the permutohedron generates an ambient gradient flow that contracts toward the sorted vertex, set against adjacent-swap paths and comparison half-spaces as discrete geometric foils. Comparisons remove informational ambiguity, while the flow removes metric distance; the exact maximal fixed-threshold relaxation time and the permutohedron's dimension together give an intrinsic geometric $\Theta(n\log n)$ scale.

Read PDF Figure Script Future Work: Flattening Entropy Code Repository

$n!$ candidate order types before comparisons provide information

$\Omega(n\log n)$ classical comparison lower bound from the decision tree

$\Theta(n^2)$ local adjacent-swap regime on the 1-skeleton

$\dim\mathcal P_n\cdot t_{\max}(\varepsilon)$ exact dimension–relaxation factorization with $\Theta(n\log n)$ scale

The Same Sorting Problem, Three Geometries

The manuscript keeps the input values, original indices, rank words, and sorted index order separate. If $v_s=(1,2,\ldots,n)$, the permutohedron $\mathcal P_n=\mathrm{conv}\{\pi(v_s):\pi\in S_n\}$ becomes the common stage for local motion, global comparison cuts, and straight-line continuous relaxation.

Decision Tree

A comparison algorithm must distinguish all $n!$ order types. A binary tree of height $h$ has at most $2^h$ leaves, so $2^h\ge n!$ and $h\ge\log_2(n!)=\Theta(n\log n)$.

Permutohedron

Each vertex is a rank word. Adjacent transpositions form edges of the 1-skeleton, so local algorithms pay for inversions one at a time; the flow's quadratic potential decreases strictly under every inversion-removing adjacent swap.

Comparison Half-Spaces

If current positions $a,b$ contain original items $p_t(a),p_t(b)$, a comparison outcome is recorded in fixed original-item coordinates, for example $r_{p_t(a)} \lt r_{p_t(b)}$. Each half-space shrinks the feasible candidate rank maps until one vertex remains.

The Gradient-Flow Benchmark

Starting from a fixed target, the manuscript gives the ambient gradient flow in closed form and determines its exact maximal time to a fixed Euclidean threshold. The model is deliberately a relaxation, not the literal trajectory of MergeSort or QuickSort. Multiplying $t_{\max}(\varepsilon)=\Theta(\log n)$ by the permutohedron's dimension gives an intrinsic geometric $\Theta(n\log n)$ scale; if $C(n)$ is the optimal worst-case comparison count, the normalized clock $\tau(n)=C(n)/n$ has the same logarithmic order without asserting a literal time conversion.

$$V(x)=\frac{1}{2}\|x-v_s\|^2$$

$$\dot{x}(t)=-\nabla V(x(t))=v_s-x(t)$$

$$\|x(t)-v_s\|^2=\|x(0)-v_s\|^2e^{-2t}$$

$$t_{\max}(\varepsilon)=\log\frac{\operatorname{diam}(\mathcal P_n)}{\varepsilon}=\frac{1}{2}\log\frac{n(n^2-1)}{3\varepsilon^2}$$

$$v_s-x\in T_K(x),\qquad \Pi_{T_K(x)}(v_s-x)=v_s-x\quad(v_s\in K)$$

For a closed convex metric constraint $K$ containing the sorted vertex, projection is inactive and the projected flow agrees with the ambient flow. Comparison half-spaces describe information reduction; they do not automatically become boundaries of the metric trajectory.

$x(0)$ information cuts $v_s$

Project Materials

This project develops a geometric view of sorting on the permutohedron. Adjacent swaps trace local edge paths, arbitrary comparisons refine the feasible rank maps through half-space constraints, and a quadratic gradient flow contracts continuously toward the sorted vertex. Together, these viewpoints separate informational progress from metric contraction while placing both on the classical $\Theta(n\log n)$ scale.

Sorting Manuscript

The paper develops the decision-tree lower bound, defines rank words on $\mathcal P_n$, contrasts local adjacent-swap walks with global comparison half-space pruning, proves that the same potential descends along inversion-removing swaps, derives the straight-line ambient contraction law for $V(x)$, determines the exact maximal fixed-threshold relaxation time, and factors it with dimension to obtain the intrinsic geometric $\Theta(n\log n)$ scale.

Open Manuscript

rank-word vertices constraint collapse

Figure generation

The Python script generates the decision tree, permutohedron views, feasible-set pruning sequence, and gradient-flow figures used to contrast discrete comparison information with continuous metric contraction.

Open Script

Proof verification

The reproducible verification suite checks the paper's symbolic identities, finite combinatorial cases, and numerical geometry diagnostics.

Open Verification Guide

Future Work: Flattening Entropy

The companion manuscript broadens the sorting insight into a geometric language for computation. Algorithms become paths, primitive operations define admissible geometry, and preprocessing is measured by how much entropy, or curvature-like obstruction, it removes before local work remains.

From Sorting Geometry to Geometry of Computation

Counting sort becomes a literal flat chart in histogram coordinates. Comparison sorting carries the full flattening entropy. Ordered bucketization sits between them by removing a multinomial block of entropy and leaving only the within-bucket residual comparison problem.

$$F_{\mathrm{cmp}}(n)=\log(n!)+O(1)$$

$$G(x;\beta)=\log(n!)-\sum_{j=1}^B\log(n_j!)$$

$$F_{\mathrm{res}}(x;\beta)=\sum_{j=1}^B\log(n_j!)$$

Open Companion Manuscript

partial flattening residual entropy