The Koszul Sign Rule

A Bit of Background

The exterior algebra is a central object in topology and physics (for the physics concept cf. fermion). The basic rule dictating the behavior of the exterior algebra is that $$\yx = -xy\$$ (and consequently $$\x^2 = -x^2 = 0\$$). Applying this rule twice we see that $$\yzx = -yxz = xyz\$$.

The product of two monomials is 0 if any repeated variable occurs, e.g. $$\vxyz * stuv = 0\$$ because $$\v\$$ is repeated. Otherwise, we want to put the variables into some standard order, say alphabetical order, and there is a sign introduced that counts how many variables we passed by each other, so for example $$\tvy * suxz = +stuvxyz\$$ because it takes a total of six crossings to put $$\tvysuxz\$$ into alphabetical order (on each line I have highlighted the most recently swapped pair): $$tvy * suxz = +\, tvy\;suxz\\ \phantom{tvy * suxz } {}= -tv\mathbf{\large sy}uxz\\ \phantom{tvy * suxz } {}= +t\mathbf{\large sv}yuxz\\ \phantom{tvy * suxz } {}= -\mathbf{\large st}vyuxz\\ \phantom{tvy * suxz } {}= +stv\mathbf{\large uy}xz\\ \phantom{tvy * suxz } {}= -st\mathbf{\large uv}yxz\\ \phantom{tvy * suxz } {}= +stuv\mathbf{\large xy}z\\$$ Your task will be to compute this sign.

This is a special case of the Koszul Sign Rule which determines the sign of the terms in many sums in math. If you are familiar with determinants, the sign in the determinant formula is an example.

You will take as input two 32 bit integers $$\a\$$ and $$\b\$$, which we will interpret as bitflags. You may assume that $$\a\$$ and $$\b\$$ have no common bits set, in other words that $$\a\mathrel{\&}b = 0\$$. Say a pair of integers $$\(i, j)\$$ where $$\0\leq i,j < 32\$$ is an "out of order pair in $$\(a,b)\$$" when:

1. $$\i < j\$$,
2. bit $$\i\$$ is set in $$\b\$$, and
3. bit $$\j\$$ is set in $$\a\$$.

Your goal is to determine whether the number of out of order pairs in $$\(a,b)\$$ is even or odd. You should output true if the number of out of order pairs is odd, false if it is even.

Input

A pair of 32 bit integers. If you would like your input instead to be a list of 0's and 1's or the list of bits set in each integer, that's fine.

Output

true or any truthy value if the number of out of order pairs is odd, false or any falsey value if it is even. Alternatively, it is fine to output any pair of distinct values for the two cases. It is also fine to output any falsey value when the number of out of order pairs is odd and any truthy value when the number of out of order pairs is even.

Metric

This is code golf so shortest code in bytes wins.

Test cases

a = 0b000000
b = 0b101101
output = false // If one number is 0, the output is always false.

a = 0b11
b = 0b10
output = UNDEFINED // a & b != 0 so the behavior is unspecified.

a = 0b01
b = 0b10
output = true // 1 out of order pair (1,2). 1 is odd.

a = 0b011
b = 0b100
output = false // 2 out of order pairs (1,2) and (1,3). 2 is even.

a = 0b0101
b = 0b1010
output = true // 3 out of order pairs (1,2), (1,4), (3,4). 3 is odd.

a = 0b0101010 // The example from the introduction
b = 0b1010101
output = false // 6 out of order pairs (1,2), (1,4), (1,6), (3,4), (3,6), (5,6).

a = 33957418
b = 135299136
output = false

a = 2149811776
b = 1293180930
output = false

a = 101843025
b = 2147562240
output = false

a = 1174713364
b = 2154431232
output = true

a = 2289372170
b = 637559376
output = false

a = 2927666276
b = 17825795
output = true

a = 1962983666
b = 2147814409
output = true

// Some asymmetric cases:
a = 2214669314
b = 1804730945
output = true

a = 1804730945
b = 2214669314
output = false

a = 285343744
b = 68786674
output = false

a = 68786674
b = 285343744
output = true

a = 847773792
b = 139415
output = false

• @ovs I think it's right as is, I'm looking for pairs that are in the "wrong" order.
– Hood
Apr 25 '20 at 14:03
• Except for the trivial 1, 2 test case, all of the other test cases seem to give the same result with the inputs swapped. Can you make more test cases which give different results when you swap the inputs?
– Neil
Apr 25 '20 at 15:44
• Is the idea of an antisymmetric tensor at all relevant? Apr 26 '20 at 2:13
• @golf69, yes, it is very relevant. This is exactly the rule you use when doing calculations with differential forms, which are totally antisymmetric tensor fields. (Also I have ever heard people refer to this property by the word antisymmetry, never by anything like "Koszul sign rule".) (And it works for determinants because, well, they're totally antisymmetric in all rows & columns.) Apr 26 '20 at 8:54
• @Ramillies Calling this the "Koszul sign rule" seems to be a pretty strong cultural marker. As a sign of its rarity, this is now the 3rd google hit and second duckduckgo hit for that term. Usually I would use "Koszul sign rule" more generally for rules like d(xy) = d(x)y + (-1)^{|x|}xd(y) and (a otimes b)(c otimes d) = (-1)^{|b||c|} (ac otimes bd). This is really just multiplication in an exterior algebra.
– Hood
Apr 26 '20 at 14:56

COW, 363 285 bytes

moOoommoOmoOmoOoomMOOmoOmOoMOOMOomOoMoOmoOMMMMOOMMMMOomOoMOomoOmoOMoOmOoMMMOOOmooMMMmoomoOMMMOOOmOoMMMmOoMOOmOoMMMmoOmoOmoOMMMMOOMOomoOMMMMOOMMMMOoMOoMMMOOOmooMMMMoOmOomoomOomOoOOOmoomOomOoMOOMOomoOMoOmOoMMMMOOMMMMOomoOMOomOomOoMoOmoOMMMOOOmooMMMmoomOoMMMOOOmoOMMMmoOmoOmoOmoomoOmoOOOM

Try it online!

A major change! (It's faster but still test cases exceed the 60 seconds timeout on TIO)
Now I like it better, it's cleaner, symmetric and I've brute forced the memory cells disposition for least number of movements.

The idea is to directly operate in terms of parity. Information in both LSB will be used in each iteration and then a and b will be halved, until b=0.

• Every a%2 is calculated (during repeated subtraction) alternating +1 and -1 in one memory cell, so that their partial sum p is available.
• When a '1' is found in b, the parity (the answer) is toggled p many times.

Detailed Explanation:

moo ]    mOo <    MOo -    OOO *    OOM i
MOO [    moO >    MoO +    MMM =    oom o

: a/2     : a     : Sum(a%2)     : b%2     : b     : b/2     : parity

>i>>>i                        ;  Read a in  and b in 
[                             ;  Loop while  is non-zero
><                        ;     Just 2 instructions for free cause COW doesn't handle consecutive parethesis :D
[                         ;     Loop while  is non-zero
-<+>=[=-<->>+<=*]=    ;         SECTION B
]                         ;      is 0,  is b%2,  is b/2
>=*<=                     ;     Copy  in , delete 
<                         ;     Point to 
[                         ;     Loop if  is non-zero. '1' it's been found in b, parity gets updated
<=>>>=                ;         Copy  in 
[                     ;         Loop while  is non zero
-                 ;             Decrement 
>=[=--=*]=+<      ;             TOGGLE 
]                     ;
<<*                   ;         Delete  (to exit the loop)
]                         ;
<<                        ;     Point to 
[                         ;     Loop while  is non-zero
->+<=[=->-<<+>=*]=    ;         SECTION A
]                         ;      is 0, a%2 is added in ,  is a/2
<=*>=                     ;     Copy  in , delete 
>>>                       ;     Point to 
]                             ;     a's and b's LSB have been treated. Now a=a/2 and b=b/2
>>o                           ;  Print 

SECTION ASECTION B is repeated subtraction that divide $$\n\$$ (a or b, resp.) by $$\2\$$.
This can't be done in one single step (i.e. --), because $$\0\$$ can't be surpassed in order to stop (so it'd be -[- =*]=). These sections contextually produce $$\n\bmod 2\$$ (LSB).

TOGGLE is a toggling method:
When target is 0 it fails the condition and simply +1 is done.
When target is 1 it passes the condition and it's set to -1 so that +1 on exit makes it 0.

Copy, delete, and paste in the same memory cell is a tecnique to treat a while loop like an if loop, also the seemgly useless copy-paste at the beginning of these (=[=) serves to balance the ending one (=*]=) in case if condition fails.

05AB1E, 11 9 bytes

Port of my Python answer. Takes a and b in reverse order, output is 1 for a odd number of out-of-order pairs, 0 for an even number.

-2 bytes thanks to @CommandMaster !

тÝo÷&bSOÉ

Try it online!

Explanation

Code        Comment                       (Example) Stack

# implicit input              a, b
т           # push 100                    a, b, 100
Ý          # inclusive range             a, b, [0,1,...,100]
o         # 2**x                        a, b, [1,2,...,2**100]
÷        # integer divide              a, [b//1,b//2,...,b//2**100]
&       # bitwise and                 [a&b//1, a&b//2, ..., a&b//2**100]
b      # convert to binary           [000100, ... , 00101001001, ..., 0]
S     # convert to a list of chars  ["0", "0", "0", "1", ..., "0"]
O    # sum (as integers)           4 (number of "out of order pairs")
É   # is this odd?                0
# implicit output
• 10 bytes: žwÝo÷&bSOÉ Apr 25 '20 at 16:34
• 9 bytes: тÝo÷&bSOÉ (replaces the 32 with the one char 100 constant) Apr 25 '20 at 16:39
• @CommandMaster thanks a lot
– ovs
Apr 25 '20 at 16:50

J, 13 bytes

2|[:+/@,>/&I.

Try it online!

Take our input as lists of ones and zeros.

• &I. Convert both a and b to a lists of the indexes of the ones.
• >/ Create a function table of all pairs of those indexes, where a cell will be 1 when the a index is greater than the b index.
• [:+/@, Flatten the table and sum all the ones.
• 2| Remainder when you divide 2 into that sum. Will be 1 (true) exactly when the sum is odd.

Jelly, 8 bytes

:Ƭ2&BSSḂ

A dyadic Link accepting an integer, $$\b\$$, on the left and an integer, $$\a\$$, on the right which yields 0 (even) or 1 (odd).

Try it online! Or see the test-suite.

How?

:Ƭ2&BSSḂ - Link: integer b, integer a
2      - literal two
Ƭ       - starting with b, collect up while results are distinct, applying:
:        -   integer division
&     - bitwise AND (vectorises) with a
B    - convert to binary (vectorises)
S   - sum
S  - sum
Ḃ - least significant bit (i.e. mod 2)

Python 2, 49 46 bytes

-3 bytes thanks to Arnauld (and Noodle9)!

f=lambda a,b:b and~int(bin(a&b),13)&1^f(a,b/2)

Try it online!

JavaScript (ES6),  42  39 bytes

Takes input as (a)(b).

a=>g=(b,n=a&b)=>n?!g(b,n&n-1):b&&g(b/2)

Try it online!

Charcoal, 19 bytes

ＮθＮη﹪Σ⭆φ⍘＆×θＸ²ιη²¦²

Try it online! Link is to verbose version of code. Outputs - for true, nothing for false. Port of @ovs's Python answer. Works for somewhat more than 32 bits. Explanation:

Ｎθ                  Input a as a number
Ｎη                Input b as a number
⭆φ            Loop from 0 to 999 and join
×θＸ²ι     Left shift a that many times
＆     η    Bitwise And with b
⍘       ²   Convert to base 2 as a string
Σ              Count total number of bits
﹪             ² Reduce modulo 2
Implicitly print

Retina 0.8.2, 52 bytes

+.(.*)¶.(.*)&¶¶$1¶$2
(.+¶0|¶1).*¶¶

M1
$Try it online! Takes input in padded binary. Explanation: +.(.*)¶.(.*)$
$&¶¶$1¶$2 Generate all of the pairs of suffixes of the inputs. (.+¶0|¶1).*¶¶ Delete the pairs of suffixes if the suffix of b starts with 0, otherwise just delete the suffixes of b. M1 Count the total number of bits of suffixes of a remaining. $

Check whether the total is odd.