On the maximal distance between triangular embeddings of a complete graph

The distance d ( f , f ′ ) between two triangular embeddings f and f ′ of a complete graph is the minimal number t such that we can replace t faces in f by t new faces to obtain a triangular embedding isomorphic to f ′ . We consider the problem of determining the maximum value of d ( f , f ′ ) as f and f ′ range over all triangular embeddings of a complete graph. The following theorem is proved: for every integer s ⩾ 9 , if 4 s + 1 is prime and 2 is a primitive root modulo ( 4 s + 1 ) , then there are nonorientable triangular embeddings f and f ′ of K 12 s + 4 such that d ( f , f ′ ) ⩾ ( 1 / 2 ) ( 4 s + 1 ) ( 12 s + 4 ) - O ( s ) , where ( 4 s + 1 ) ( 12 s + 4 ) is the number of faces in a triangular embedding of K 12 s + 4 . Some number-theoretical arguments are advanced that there may be an infinite number of odd integers s satisfying the hypothesis of the theorem.