find a group of lowest N numbers so that no 2 pairs have the same bitwise or

Question

I am trying to find the lowest group of N numbers (i.e. N=1000) so that no 2 pairs from the group have the same bit-wise or.

more specific need to find a group

$A = \{a_1,a_2,a_3,..,a_N\} $

such that for any $ 1\le i,j,k,m \le n $

$ i \ne j , k \ne m $

$OR(a_i,a_j) \ne OR(a_k,a_m)$

$a_1 .. a_n$ lowest as possable

example for N=3

A = {0,1,2}

as Or(0,1) = 1 , Or(0,2) = 2 , Or(1,2) = 3

Answer 1

The question "Can we find $1000$ numbers in the range $[0,2^{n}-1]$?" can be reworded as "Can we find $1000$ subsets of $\{1,\dots, n\}$ such that

• There do not exist distinct $A,B,C,D$ with $A \cup B=C \cup D$
• There do not exist distinct $A,B,C$ with $A \cup B=A \cup C$

In extremal set theory, such a collection of subsets is called a strongly union free family. Coppersmith and Shearer have some asymptotic constructions of fairly large (roughly $2^{0.31n}$ subsets) collections satisfying this property. I'm not too familiar with the details of the constructions, but it might be possible to extract something in the non-asymptotic regime from them.

Answer 2

A rewritten start: If you continue greedily, you will get the set $2^k$. Given that you have $0$ and $1$, you cannot have any number $n$ with a $1$ in the $2^0$ position because $n \text{ or } 0 = n \text{ or } 1$. Similarly, you cannot have a number with a $1$ in the $2^1$ position. $3$ violates this, but $4$ is acceptable. Now you can't have any other number with a $1$ in the $2^2$ position.

It would be better (get you a smaller top number) to have each number have more bits. Given $N$ numbers, you have $\frac 12N(N-1)$ pairs that should have different ORs. You could let each have $ b$ one bits and $c$ zero bits. You need at least ${b+c \choose b}=N$. Then if all the ORs are different you are home. The greedy strategy above is $b=1,c=N$ There must be a nice pattern of numbers with $b$ bits that guarantees no collisions, but I haven't found it. I practice, I think I would choose $b$ and $c$, let all the $N$ numbers have $b$ one bits and choose them at random from the ${b+c \choose b}$ and try. If it fails too many times, increase $c$ and try again.