It is known that [sum-free](https://en.wikipedia.org/wiki/Sum-free_set)
subsets of $\mathbb{N}$ can have
[natural density](https://en.wikipedia.org/wiki/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.



XOR-free sets: Maximum density?
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}$.


