L  XOR Operations

As a preprocessing step, let us replace each input integer \(a_i\) with \(2a_i + 1\). This alteration does not affect the result; however, it proves to be useful for subsequent calculations.

A \(d\)-bit integer can be represented by a row vector in \((\mathbb{Z}/2\mathbb{Z})^d\). For an input \(a_i\), let us denote the corresponding row vector in \((\mathbb{Z}/2\mathbb{Z})^d\) by \(\vec{a_i}\). The XOR operation \(a_i \oplus a_j\) corresponds to the addition \(\vec{a_i} + \vec{a_j}\) in \((\mathbb{Z}/2\mathbb{Z})^d\).

Similarly, the sequence \(B\) can be represented as \(n\) row vectors in \((\mathbb{Z}/2\mathbb{Z})^d\). Now, the operation for indices \(i\) and \(j\) (\(b_i \leftarrow b_i \oplus a_i \oplus a_j\) and \(b_j \leftarrow b_j \oplus a_i \oplus a_j\)) can be considered as an addition of \((\vec{0} \ldots, \vec{0}, \vec{a_i} \overset{i}{+} \vec{a_j}, \vec{0}, \ldots, \vec{0}, \vec{a_i} \overset{j}{+} \vec{a_j}, \vec{0}, \ldots, \vec{0})\) to \(B\). Let us denote this row vector by \(\vec{v_{i,j}}\). Note that the dimension of \(\vec{v_{i,j}}\) is \(nd\). There are \(\binom{n}{2}\) choices for \(i\) and \(j\). The solution to this problem is the number of elements in the space spanned by the vectors \(\vec{v_{i,j}}\). Let \(M\) be a \(\binom{n}{2} \times (nd)\) matrix such that each row corresponds to a vector \(\vec{v_{i,j}}\). The solution is equal to \(2^{\operatorname{rank}(M)}\). Thus, in summary, we only need to determine the rank of \(M\).

To investigate the rank of \(M\), for \(k \ge 2\), let

and \(R_k\) be an \((k-1) \times (nd)\) matrix \([D_k \mid F_k \mid O]\). Also, let \(M_k\) be a matrix formed by stacking matrices \(R_2, R_3, \ldots, R_k\) vertically. The matrix \(M\) as described above is equivalent to \(M_n\). Without loss of generality, we can assume that \(s\) row vectors \(\vec{a_1}, \ldots, \vec{a_s}\) are linearly independent, and other vectors can be expressed as the sum of a subset of \(\vec{a_1}, \ldots, \vec{a_s}\).

Observation L.1. \(\operatorname{rank}(M_s) = \binom{s}{2}\).

Proof. Suppose that \(\sum_{(i,j) \in C} \vec{v_{i,j}} = 0\) for some set of indices \(C \subseteq \{(i, j) \mid 1 \le i \lt j \le s\}\). Let us examine the first \(d\) elements of the vector \(\sum_{(i,j) \in C} \vec{v_{i,j}}\). In particular, \(\sum_{(1,j) \in C} (\vec{a_1} + \vec{a_j}) = \vec{0}\) must hold. Because \(\vec{a_1}, \ldots, \vec{a_s}\) are linearly independent, \(C\) cannot contain any element of the form \((1, j)\) for \(j = 2, \ldots, s\). With the same arguments applied to other elements, we can deduce that \(C\) must be empty. This means that the row vectors in \(M_s\) are linearly independent, and therefore \(\operatorname{rank}(M_s) = \binom{s}{2}\). □

Observation L.2. For \(k \gt s\), \(\operatorname{rank}(M_k) = \operatorname{rank}(M_{k-1}) + s - 1\).

From Observations L.1 and L.2, we can conclude that the rank of \(M\) is \(\binom{s}{2} + (n - s)(s - 1)\). Since the computation of \(s\), the number of linearly independent vectors, can be performed in \(O(nd)\) time, the runtime is \(O(nd)\). (In this problem, \(d = 31\).) The remaining part is the outline of the proof for Observation L.2.

Proof. First, we can show that the rank of \(F_k\) is \(s - 1\). Because the rows of \(F_k\) are linear combinations of \(\vec{a_1}, \ldots, \vec{a_s}\), \(\operatorname{rank}(F_k) \le s\). The rank can be further bounded by \(s - 1\) because any combination of rows in \(F_k\) always contains an even number of \(\vec{a_1}, \ldots, \vec{a_s}\). (Here, we utilized the result of the preprocessing, that \(\vec{a_{s+1}}, \ldots, \vec{a_k}\) are represented by an odd number of sums of the basis \(\vec{a_1}, \ldots, \vec{a_s}\).) Also, without loss of generality, we can assume that \(\vec{a_k} = \vec{a_1} + \ldots + \vec{a_t}\), where \(t \ge 1\) is an odd integer. Then, the \(s - 1\) vectors \(\vec{a_2} + \vec{a_k}, \vec{a_3} + \vec{a_k}, \ldots, \vec{a_s} + \vec{a_k}\) are linearly independent. From this, we can conclude that \(\operatorname{rank}(F_k) = s - 1\).

Next, since the matrix \(M_k\) has the form of

we can say that \(\operatorname{rank}(M_k) \ge \operatorname{rank}(M_{k-1}) + s - 1\). To show that the inequality “\(\ge\)” is actually an equality, we need to establish that the elements of \(D_k\) do not affect the rank of \(M_k\). Suppose that there exists a subset \(C \subseteq \{1, \ldots, k-1\}\) such that \(\sum_{i \in C} (\vec{a_i} + \vec{a_k}) = \vec{0}\). That is, \(C\) represents the indices of rows in \(F_k\) whose sum equals \(\vec{0}\). For our purposes, it suffices to show that there always exists a subset \(C' \subseteq \{(i, j) \mid 1 \le i \lt j \lt k\}\) such that \(\sum_{i \in C} \vec{v_{i,k}} = \sum_{(i,j) \in C'} \vec{v_{i,j}}\).

When \(|C|\) is odd, because \(\vec{a_k} = \sum_{i \in C} \vec{a_i}\), \(C' = \{(i, j) \mid i, j \in C, i \lt j\}\) satisfies the condition. Meanwhile, when \(|C|\) is even, because \(\sum_{i \in C} \vec{a_i} = \vec{0}\), a set \(C'\) constructed from \(\{1, \ldots, t\} \times C\) satisfies the condition. This concludes the statement of the observation. □