Unique-xor sets

asymptoticsbit-stringscombinatorics

Let a set $S$ of nonnegative integers be a "unique-xor" set if all pairs of distinct integers in $S$ have different bitwise xor from all other pairs.

Let $x(n)$ be the least maximum element for any unique-xor set of size $n$.

My question is: Can we prove that $x(n)=\Theta(n^2)$? Or more basically, that $x(n)=O(n^k)$, for some constant $k$?
Has this question been studied?

For instance, the set $[0,1,2,4,…,2^m]$ is a unique-xor set, for any $m$. As another example, $[0,1,2,4,11,12]$ is a unique-xor set.

Of particular interest are unique-xor sets with large size and small maximum value. I believe that for sizes $1,2,3,4,5,6$, smallest possible maximum value for a unique-xor set of that size is $0,1,2,4,8,12$, given by the two constructions above.

A lower bound on $x(n)$ is that a unique-xor set of size $n$ must have maximum value at least $2^{\lceil \log_2 n(n-1)/2 \rceil – 1 }$. To see why, note that the set must have $n(n-1)/2$ distinct xor results. The maximum result must have at least $\lceil \log_2 n(n-1)/2 \rceil$ bits when written in binary. As a consequence, the maximum value must have at least the same number of bits when written in binary.

From the above lower bound, we find that $x(n) = \Omega(n^2)$. Intuitively, this seems like it should be tight, that $x(n) = \Theta(n^2)$, because a maximum value around $n^2$ gives enough space for the xor results to be distinct. However, I have not been able to find a better explicit construction than the exponential construction above.

Note that a unique-xor set is equivalent to a set system with unique symmetric difference, if we map the bits of the numbers to distinct elements. In that case, my question becomes whether there exists such a set system with $n$ sets over $k \log_2 n$ elements, or ideally over $2\log_2 n$ elements. Has this question been studied?

Best Answer

Such sets in additive groups (sets where sums are unique) are called Sidon sets. If we consider the additive group $(\mathbb{F}_2^n,+)$ and associate the group (also a vector space over $\mathbb{F}_2$) with $\mathbb{F}_{2^n}$ via some basis. I believe the results below show that the answer is $\theta(n^2).$

Sidorenko has shown tight upper and lower bounds on the size of the largest Sidon set, denoted by $\beta(\mathbb{F}_2^n)$ in $\mathbb{F}_2^n:$

$$ \beta(\mathbb{F}_2^n)\leq \sqrt{2^{n+1}-\frac{7}{4}}+\frac{1}{2}, $$ and $$ \beta(\mathbb{F}_2^n)\geq 2^{n/2}, \quad n\textrm{ even} $$ There is also an old construction of Lindstrom:

Consider all elements of $\mathbb{F}_{2^{2k}}$ of the form $(\mathbf{x},\mathbf{x}^3)$ where we express $\mathbf{x}\in \mathbb{F}_{2^k}$ as a $k$-dimensional vector over $\mathbb{F}_2$ with respect to some basis. It turns out that this forms a Sidon set, and given $(\mathbf{x},\mathbf{x}^3)+(\mathbf{y},\mathbf{y}^3)=(\mathbf{u},\mathbf{v})$, one can solve for $\mathbf{x}$ (and therefore $\mathbf{y}$) by solving a quadratic equation in $\mathbb{F}_2^k$.

Related Solutions

[Math] Running time (Big O) of counting in binary

The case where $n=2^a$ for some $a$ is a bit easier to analyze. Let's observe the list of binary numbers for $a=3$:

We're interested in how many times there's a bit that changes. The trick is to count not one number a time but one bit position at a time:

The ones bit changes for every number, so it flips $n$ times.
The twos bit changes for every second number, so it flips $n/2$ times.
The fours bit changes one time out of four so it flips $n/4$ times.

And so forth -- the total number of flips is $$\sum_{i=0}^a \frac{n}{2^i} = n \sum_{i=0}^a 2^{-i} < 2n$$ where the last inequality is because $\sum_{i=0}^a 2^{-i}$ is a prefix of the infinite geometric series with sum $2$.

Now, can you prove there are also $\le 2n$ flips when $n$ is not a power of $2$?

Permutations balanced binary trees: how can I get the $\log n$ inequalities corresponding to a leaf without computing the whole tree

Finding the shallowest comparison tree to sort $n$ objects is in general an open problem. According to the OEIS page for the optimal comparison numer, we only know these numbers up to $n=15$. Furthermore, the optimal number of comparisons to sort $12$ items is $30$, which is one more than $\lceil \log_2 12!\rceil=29$. This answers your question $3$ in the negative.

For question $1$, any permutation can be defined by $n-1$ comparisons, and no fewer. For example, when $n=5$, the permutation $[2,4,1,5,3]$ is uniquely specified by these four comparisons: $$ 2<4,\quad 4<1,\quad 1<5,\quad 5<3 $$ To see this is optimal, note that if only $n-2$ comparisons are given for the permutation $\pi=[\pi_1,\pi_2,\dots,\pi_n]$, then there must exist some $i\in \{1,\dots,n-1\}$ for which the comparison $\pi_i < \pi_{i+1}$ is not given. This implies the given comparisons cannot distinguish $\pi$ from the permutation resulting from switching $\pi_i$ and $\pi_{i+1}$ in $\pi$.

You can see the problem of finding the optimal set of comparisons to specify a permutation is trivial, and unrelated to the comparison tree.

Finally, for question $2$, given two permutations $\pi$ and $\tau$ of $\{1,\dots,n\}$ you want a way to compute the number of unordered pairs $\{i,j\}$ for which $\pi_i$ and $\pi_j$ appear in the same order in $\pi$ as $\tau_i$ and $\tau_j$ do in $\tau$. This is equal $\binom n2$ minus the number of inversions of $\pi\circ \tau^{-1}$. To compute this, you can

Compute $\tau^{-1}$. This takes $O(n\log n)$ time.
Compute $\pi\circ \tau^{-1}$. Should take $O(n)$, if you use arrays, I think?
Compute the number of inversions of $\pi\circ \tau^{-1}$. This takes $O(n\log n)$; see this Stack Overflow post for the method.

Best Answer

Related Solutions

[Math] Running time (Big O) of counting in binary

Permutations balanced binary trees: how can I get the $\log n$ inequalities corresponding to a leaf without computing the whole tree

Related Question