All the claims are true.
The complicated transformation which produces the result has a number of unnecessary features. We don't have to start with permutations, and we don't have to subtract N/2. The two key factors are a simple fact about the vectors P1 and P2, and the rotation by 45 degrees.
To see what is going on, let us write our steps as follows:
p1 = random permutation of 1 to n p2 = random permutation of 1 to n q1 = p1 - n / 2 q2 = p2 - n / 2 NOTE: the L2 norms of q1 and q2 are equal (the vectors have the same entries, though in different orders). r1 = c * q1 - s * q2 r2 = s * q1 + c * q2 dot = r1' * r2 = ( c * q1 - s * q2 )' * ( s * q1 + c * q2 ) = c * s * q1' * q1 + c * c * q1' * q2 - s * s * q2' * q1 - s * c * q2' * q2 NOTE: angle = 45 degrees, so c = s, therefore... = c * c * ( q1'*q1 + q1'*q2 - q2'*q1 - q2'*q2 ) NOTE: q1'*q2 = q2'*q1, by symmetry of dot products, therefore... = c * c * ( q1'*q1 - q2'*q2 ) NOTE: q1'*q1 is the square of the L2 norm of q1, and similarly for q2. = c * c * ( 0 ) = 0
Thus, the crucial steps are that the translated vectors q1 and q2 have the same norm, which can easily be guaranteed if they have the same entries, though in different order; and that the sine and cosine of the rotation be equal (although this would also work for -45 degrees, for which c = -s, as well as 135 and 225 degrees.)