When do decimal-coded binary numbers XOR to zero?

Question

Background definition: XOR on numbers

Given two non-negative integers $x$ and $y$, let $x\oplus y$ denote the bitwise exclusive or (XOR) of the numbers $x$ and $y$. This is the result of writing $x$ and $y$ in binary notation, then XORing corresponding bits (also known as "addition without carry"), and finally interpreting the result as a number again. This operation is often represented by the expression x ^ y in programming languages and is also known as nim-addition. This operation is commutative and associative, so one can take the XOR of more than one number in any order and simply write $x\oplus y\oplus z$.

It's important to note that we view $x\oplus y$ as an operation on numbers here, not on strings, which is consistent with its behavior in various programming languages. For example, Python will happily report that 123 ^ 456 ^ 789 == 678, which you can see by examining the columns of the following table, where we use a subscript like $123_{10}$ to mean decimal notation and $0001111011_2$ to mean binary notation:

$$\begin{align*} 123_{10} &= 0001111011_2 \\ 456_{10} &= 0111001000_2 \\ 789_{10} &= 1100010101_2 \\ 678_{10} &= 1010100110_2. \end{align*}$$

[Hint: check that each column of bits has an even number of $1$s.]

Good collections of numbers have vanishing XOR

Motivated by a recent challenge on the Code Golf Stack Exchange, "For what block sizes is this checksum valid?" (which was the #1 Hot Network Question for a while!), let us call a collection of numbers good if their XOR is zero, and bad otherwise. For example, the set $\{123_{10}, 456_{10}, 789_{10}, 678_{10}\}$ is good. In other words, a collection is good if "the checksum is valid".

Given a bitstring like $101$, one can interpret the string in binary as $101_2 = 5_{10}$, or in decimal notation as $101_{10} = 1100101_2$. By analog to binary-coded decimal, one might call the latter interpretation decimal-coded binary (of $101$), meaning we use an entire decimal digit to represent a single binary bit.

Given a collection of bitstrings, like $\{10, 100, 110\}$, one can interpret the strings in binary like $\{10_2, 100_2, 110_2\}$ or in decimal notation like $\{10_{10}, 100_{10}, 110_{10}\}$. Sometimes, like in this case, it happens that both the interpretations are good, meaning $10_2\oplus 100_2\oplus 110_2 = 0$ and $10_{10} \oplus 100_{10} \oplus 110_{10} = 0$ as well:

$$\begin{align*} 10_{10} &= 0001010_2 \\ 100_{10} &= 1100100_2 \\ 110_{10} &= 1101110_2. \end{align*}$$

Unfortunately, sometimes the binary interpretation is good but the decimal interpretation is bad, like in the case $\{100,1000,1100\}$ which is good in binary because $100_2 \oplus 1000_2 \oplus 1100_2 = 0$ but where unfortunately the decimal interpretation has $100_{10} \oplus 1000_{10} \oplus 1100_{10} = 1984_{10}$:

$$\begin{align*} 100_{10} &= 00001100100_2 \\ 1000_{10} &= 01111101000_2 \\ 1100_{10} &= 10001001100_2 \\ 1984_{10} &= 11111000000_2. \end{align*}$$

Of course, it is very often the case that both binary and decimal interpretations are bad; this is the usual situation for a random collection. (Checksums are unlikely to be valid by accident.) Thus we have examples of "binary good and decimal good", "binary good but decimal bad", and "binary bad and decimal bad". That leaves a final possibility: "binary bad but decimal good".

The puzzle

Find a collection of bitstrings that is good when interpreted as decimal numbers but is bad when interpreted as binary numbers.

That is, find a collection of bitstrings (ie, strings of $0$s and $1$s) $$\{abc\dotsc def,\quad \dotsb,\quad uvw\dotsc xyz \}$$ so that the "decimal-coded binary XOR" vanishes, meaning $$abc\dotsc def_{10} \oplus \dotsb \oplus uvw\dotsc xyz_{10} = 0$$ but their "usual XOR" doesn't, meaning $$abc\dotsc def_{2} \oplus \dotsb \oplus uvw\dotsc xyz_{2} \ne 0.$$

Answer 1

One answer is:

10, 100, 1010, 10000, 110000, 111000, 1000100, 1001000, 10100000, 10101000

This was obtained with a computer search using Magma, with the following code:

n:=25;  
V:=VectorSpace(GF(2),2*n);  
W:=sub<V|{V.i:i in {1..n}}>;  
S:={};  
A:=[];  
for i in {1..200} do  
  t:=IntegerToSequence(i,2);  
  s:=IntegerToSequence(SequenceToInteger(t,10),2);  
  Include(~S,V!(t cat [0:j in {1..n-#t}] cat s cat [0:j in {1..n-#s}]));  
  if (Dimension(sub<V|S> meet W) ge 1) then print i; break; end if;  
end for;  

This code searches for the set of integers with this property with the smallest maximum element. For each integer 𝑖, we create the binary expansion of this integer as 𝑡, and then 𝑠 is the "decimal expansion" of the same string of 0s and 1s, converted back to binary. By appending these strings together in a single vector, we can look for solutions where the last half of the vector (the decimal expansion) XORs to 0, but the first half does not. The first integer for which such a set occurs is 168, which gives us the above set of integers.

A little more detail

The code above shows that there is a solution set with largest element 10,101,000, but does not actually produce it. The following code actually produces the solution:

n:=25;
lim:=200;
V:=VectorSpace(GF(2),2*n);
W:=sub<V|{V.i:i in {1..n}}>;
A:=[];
S:={};
for i in {1..lim} do
  t:=IntegerToSequence(i,2);
  s:=IntegerToSequence(SequenceToInteger(t,10),2);
  jst:=t cat [0:j in {1..n-#t}] cat s cat [0:j in {1..n-#s}];
  Append(~A,jst);
  Include(~S,V!jst);
  if (Dimension(sub<V|S> meet W) ge 1) then
    v:=Basis(sub<V|S> meet W)[1];
    M:=KMatrixSpace(GF(2),i,2*n);
    B:=M!A;
    x:=Solution(B,v);
    tt:={j:j in {1..i}|x[j] eq 1};
    {SequenceToInteger(IntegerToSequence(i,2),10):i in tt};
    break;
  end if;
end for;

The extra code sets v as the target vector, and then uses linear algebra to find the combination of vectors calculated above that sum to v, and converts them to the appropriate integers.

Answer 2

A friend of mine found another solution but, despite my cajoling, declines to post here.

As we know from the other answer, any solution must

include a number $\ge 168$, and in particular $\ge 8$ bits long.

The code below finds a couple solutions achieving this bound and

containing only four strings.

One such solution is

10101000 10100100 1110110 1101010

or in decimal notation,

$168_{10} \oplus 164_{10} \oplus 118_{10} \oplus 106_{10} = 0$. In a precise sense, this is the "smallest" possible solution.

M = 2**8
x = [int(bin(n)[2:]) for n in range(M)]

for a in range(M):
  for b in range(a):
    for c in range(b):
      for d in range(c):
        if x[a]^x[b]^x[c]^x[d] == 0 and a^b^c^d != 0:
          print(a, b, c, d, x[a], x[b], x[c], x[d])

Try it online!

However, this leaves open a possibility: is there a solution with only three strings?