Total Relative Displacement of Permutations

Let φ be a permutation of the set {1, 2, 3, …, N}. We call the sum δφ=∑ ||i−j|−|φ(i)−φ(j)|| the total relative displacement (where the sum is over all i, j such that 1⩽i<j⩽N). Chartrand, Gavlas, and VanderJagt conjectured that among permutations of {1, …, N} the smallest positive value of δφ is 2N−4. We prove this result and develop a general theory for small values of δφ for permutations and, more generally, for functions S→Z with finite domain S⊂Z.