# The second argument of Signature

I've noticed that Signature can have an undocumented second argument. What does it do?

Signature[{1,2,3,4}, ?]

-

It should be a comparison function. One can simulate the standard behavior by

Signature[{1, 2, 3}, If[#1 < #2, True, 0] &]
Signature[{2, 1, 3}, If[#1 < #2, True, 0] &]
Signature[{1, 1, 3}, If[#1 < #2, True, 0] &]
(* 1 *)
(* -1 *)
(* 0 *)


If the first argument is less than the second we return True (or False, it doesn't matter!), otherwise we can return everything except True and False.

Update:

Sometimes it returns 0 instead of 1 or -1. For example,

a = {52579, 13723};
Signature[a]
(* -1 *)
Signature[a, If[#1 < #2, True, 0] &]
(* 0 *)


I've found that Signature has 2 phases:

1. Check up for duplicates. If duplicates are found then return 0.

2. If there is no duplicates then calculate the signature.

At the first phase Signature compares hashes instead of the direct values of elements (I think it is an optimization for non-numerical lists). Hashes of 52579 and 13723 are the same:

Hash[52579]
Hash[13723]
(* 8900173879719767389 *)
(* 8900173879719767389 *)


So I should return something instead of 0

If[#1 < #2, True, ?] &


Any ideas?

P.S. V8 and earlier have another Hash function so the "magic" numbers are different. For example, {34064, 32232}.

-
Very interesting. How did you discover this? (+1 of course.) –  Mr.Wizard Jan 26 '14 at 3:23
I'm finding cases where your code doesn't match the output of Signature. I haven't isolated it yet but here's an example: SeedRandom[13]; a = RandomInteger[1*^10, 1*^5]; now Signature[a] gives -1 while Signature[a, If[#1 < #2, True, 0] &] gives 0. Ideas? Signature[a, If[#1 < #2, True, 0] &] –  Mr.Wizard Jan 26 '14 at 3:36
@Mr.Wizard I've discovered this when I debug my code at codegolf.SE. I accidentally wrote MapIndexed[Signature,A,{2}] instead of Map[Signature,A,{2}]. It doesn't return any error, but it returns a wrong signature. Then I was surprised to find that the Signature[list, something] returns 2 Boole[Mod[Length[list], 4] < 2] - 1 if list has no duplicates and 0 otherwise! –  ybeltukov Jan 26 '14 at 3:44
Here is a shorter example where your code does not match the default: a = {49914, 54968, 11840, 69457, 40872} -- can you confirm this problem on your system? –  Mr.Wizard Jan 26 '14 at 3:48
I really hope this gets an answer, has been bugging me for the better part of a year (when I made a similar typo mistake but still saw results). I Sowed the second argument and observed it appears to be pair lists, tried various ordering functions, etc. to no avail. I thought it might have something to do with counting inversions, left it at that. Are the MM staff that are here "allowed" to post such information? Surely a peek by one of them at the source could put this to bed. –  rasher Feb 3 '14 at 4:01