Why XOR of all subsets of a list have same frequency?

Question

I have a list of numbers a1, a2, a3, a4, a5, ... and so on. If we find XOR of all subsets then I noticed that frequency of each distinct XOR is the same.

Example 1

# list of numbers    
[2, 0, 9]

# XOR of all subsets including empty set
XOR of () = 0
XOR of (2,) = 2
XOR of (0,) = 0
XOR of (9,) = 9
XOR of (2, 0) = 2
XOR of (2, 9) = 11
XOR of (0, 9) = 9
XOR of (2, 0, 9) = 11

# Frequency of each XOR value
{0: 2, 2: 2, 9: 2, 11: 2}

In the above example, we can see that XOR values 0, 2, 9, 11 have the same frequency that is 2

Example 2

It doesn't matter what is the size of the list, whether elements are repeated or not, the property seems to hold

# list of numbers
[2, 0, 9, 9, 9, 45, 1, 2, 1, 1]

# skipping showing the subsets

# Frequency of each XOR value
{0: 64,
 2: 64,
 9: 64,
 45: 64,
 1: 64,
 11: 64,
 47: 64,
 3: 64,
 36: 64,
 8: 64,
 44: 64,
 38: 64,
 10: 64,
 46: 64,
 37: 64,
 39: 64}

First of all, I am not sure whether it will always hold. I have tested it for quite a few numbers of examples and it seems to work for all of them. There are a lot of XOR questions asked on StackOverflow but I didn't find anything related to this question.

Can someone please help with the following?

• Whether this property will always hold?
• If no, can you share 1 example?
• If yes, can you please answer why?

Answer 1

Assuming you know about the linear combination of basis elements.

Let a_i1,a_i2,a_i3,....a_ik be the basis elements for given array.

We get 2^k unique xor values by spanning above set.

Let that set be X = { x₁,x₂,.......x_2^k }

Now coming to remaining (n-k) non basis elements, There are 2^(n-k) subsets among them.

let that set of subset be D = { d₁,d₂,....d_2^n-k }

[And all di?X, because, since di is some subset of those non basis elements, and each of those non basis elements itself linearly representable using basis elements(ie:can be formed by xor-ing some subset of basis elements).

==> As di is linear combination of non basis elements and each of non basis elements is linear combination of basis elements, di is also linear combination of basis elements, thus di comes under set X]

Now coming to original question, let A be given original array. Then set of subset of A = X×D.

[Because X is set of subset of some k distinct element of array, and D is set of subset of remaining n-k elements., So merging them with all combinations gives set of subset of original array]

Claim: each di xor X produces the same set X but just in different order.

proof: For any two different integer p,q =>p^u?q^u

Since all x1,x2...... are different.

Here di is like u. so di^X = ?di^{x1,x2,......} produces another unique set of elements.

Now we are left with proving that new unique set is X itself.

The new xi's cannot have any new value apart that span of basis, as for each previous element what we did is only linear combination within basis.

So all xi still belongs to span of basis, ie: new set is X.

---

Now the size of D is 2^(n-k), and each di×X = X

hence the same set of xor values in X is repeated 2^(n-k) times.

ie: each element in X (span of basis elements) is repeated 2^(n-k) times. Where k is number of basis elements.