5
$\begingroup$

For a certain algorithm, I need a function $f$ on integers such that

$a_1 \oplus a_2 \oplus \, \cdots\,\oplus a_n = 0 \implies f(a_1) \oplus f(a_2) \oplus \, \cdots\,\oplus f(a_n) \neq 0$

(where the $a_i$ are pairwise distinct, non-negative integers and $\oplus$ is the bitwise XOR operation)

The function $f$ should be computable in $O(m)$, where $m$ is the maximum number of digits of the $a_i$. Of course the simpler the function is, the better. Preferrably the output of the function would fit into $m$ digits as well.

Is there something like this? It would also be okay to have a family of finitely many functions $f_n$ such that for one of the functions the result of the above operation will be $\neq 0$.

My own considerations so far were the following:

  1. If we choose the ones' complement as $f$, we can rule out all cases where $n$ is odd.
  2. If $n$ is even, this means that for every bit, an even number of the $a_i$ has the bit set and the rest has not, therefore taking the ones' complement before XORing doesn't change the result.

So the harder part seems to be the case where $n$ is even.

  • 0
    @tomasz: I see what you mean... But of course without these restrictions, the algorithm wouldn't be feasible anymore, so all I can do is hope.2012-08-12

1 Answers 1

3

The function $f$, if it exists, must have very large outputs.

Call a set of integers "closed" if it is closed under the operation $\oplus$. A good example of a closed set of integers is the set of positive integers smaller than $2^k$ for some $k$.

Let $S$ be a closed set of integers that form the domain of $f$. Take as an example those positive integers with at most $m$ bits. Let $T$ be the codomain of $f$, so that we have $f : S \to T$ being the function of interest. Assume furthermore that $T$ is a closed set of integers.

Big claim: $|T| \ge (2^{|S|}-1)/|S|$.


Proof sketch:

Let $A$ be the set of sequences $a_1 < a_2 < \dots < a_n$ of distinct positive integers in $S$. Let $p : A \to S$ be defined by $p(a_1,a_2,\dots,a_n) = a_1 \oplus \dots \oplus a_n$, and let $q : A \to T$ be defined by $q(a_1,\dots,a_n) = f(a_1) \oplus \dots \oplus f(a_n)$.

Claim: If $p(a_1,\dots,a_n) = p(b_1,\dots,b_l),$ then $q(a_1,\dots,a_n) \ne q(b_1,\dots,b_l)$.

Proof: Interleave the sequences $a$ and $b$, removing duplicates, to obtain a sequence $c$. Then $p(c) = p(a) \oplus p(b) = 0$, so $q(c) \ne 0$; yet $q(c) = q(a) \oplus q(b)$.

Now, note that there are $2^{|S|}-1$ elements of $A$, so there must be $(2^{|S|}-1)/|S|$ such elements sharing the same value of $p$. This means that $T$ must contain $(2^{|S|}-1)/|S|$ distinct values.


So, if $S$ consists of $m$-bit integers, then $T$ must consist of roughly $(2^m-m)$-bit integers.

EDIT: Incorporating comments: the function $f(a) = 2^a$ has the desired property, and roughly achieves this bound.

  • 0
    Nice one. :) You might want to add, that if you allow exponential size of output, such function exists (just the exponential function is okay), so the bound is more or less exact.2012-08-12