XOR-free sets: Maximum density?

Question

It is known that sum-free subsets of $\mathbb{N}$ can have natural density at most $\frac{1}{2}$. This density is achieved by the odd numbers: the sum of two odd numbers is even.

I ask now a similar question for XOR rather than addition. For $a,b \in \mathbb{N}$, define $a \oplus b$ as follows: Represent $a \ge b$ as binary numbers, pad the smaller $b$ with zeros, and take the bit-wise XOR of the binary representation. For example, $35 \oplus 15 = 44$: \begin{eqnarray} 35 = & \;100011\\ 15 = & \;001111\\ \oplus = & \;101100 \end{eqnarray} The condition for a set $S \subset \mathbb{N}$ to be XOR-free is that, for any $a,b \in S$, $a \oplus b \not\in S$.

Q. What is the largest density of an XOR-free subset $S$ of $\mathbb{N}$?

Again the odd numbers with density $\frac{1}{2}$ are XOR-free. I am not seeing an argument that $\frac{1}{2}$ is the maximum possible density.

Answer 1

Let $a\in S$ be some fixed element. Note that $a\oplus b \le a + b$. Let $N$ be some big number. Put $M = [1, \ldots , N]\cap S$. We have $a\oplus M \cap M = \varnothing$. We also have $a\oplus M \subset [1, \ldots , N + a]$. Therefore $2|M| \le N + a$ or $|M| \le \frac{N}{2} + \frac{a}{2}$. Since $a$ is fixed taking limit $N\to \infty$ yields the desired result.

UPD Here is an answer for a perhaps more interesting question: what is limsup of the biggest density of the subset of $[0, \ldots , N]$ which is XOR-free. Note that if $N = 2^k - 1$ for some $k\in \mathbb{N}$ then $|S| \le 2^{k-1}$. Indeed, for any $a, b\in [0, \ldots, N]$ we have $a\oplus b \in [0, \ldots , N]$ . Since $|S\oplus S| \ge |S|$ and $S\cap (S\oplus S) = \varnothing$ we get $2|S| \le (N+1)$ or $|S| \le 2^{k-1}$.

For the general case assume that $2^k \le N < 2^{k+1} - 1$. Then on the one hand $|S| \le 2^k$ since $S\subset [0, \ldots , 2^{k+1}-1]$ and on the other hand $|S| \le 2^{k-1} + (N - 2^k) = N - 2^{k-1}$ since $|S\cap [0, \ldots , 2^k - 1]| \le 2^{k-1}$. Therefore $3|S| \le 2N$ or $|S| \le \frac{2N}{3}$.

Here is an example (found partly via computer search) which shows that density $\frac{2}{3}$ is possible: put $N = 6*2^k$ and let $S$ be a set of all numbers consisting of $k + 3$ digits such that first three of them is from the following set $M = \{(0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1)\}$. Note that $S\oplus S \cap S = \varnothing$, all elements of $S$ are not greater than $N$ and $|S| = 4*2^k$. Therefore $\frac{|S|}{N} = \frac{2}{3}$.