Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What restrictions are there on the kind of $f$ you can pick? If the $a_i$ are pairwise distinct, you can make $f(a)$ be the integer consisting of $a$ "ones" in base two. I'd guess this function isn't appropriate for an algorithm. –  Thomas Belulovich Aug 12 '12 at 15:53
    
@Thomas: Yeah, I see. I guess I need a function that is computable in O(m) where m is the maximum number of digits of the $a_i$ –  Niklas B. Aug 12 '12 at 15:56
1  
With such a strong restriction on the size of the output, my intuition tells me that such a function likely can't exist for purely combinatorial reasons (ignoring computation issues altogether), but I can't really supply any concrete argument to support that. –  tomasz Aug 12 '12 at 16:16
    
@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. –  Niklas B. Aug 12 '12 at 16:19

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Wow, thank you very much! While this was not the result I hoped for, at least I can stop looking now :) –  Niklas B. Aug 12 '12 at 17:58
    
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. –  tomasz Aug 12 '12 at 18:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.