9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Maybe a parity argument helps? As a guide, consider all numbers with an odd number of 1-bits. Gerhard "Are Parity Arguments Also Even?" Paseman, 2019.02.24. $\endgroup$ Feb 24, 2019 at 23:32
  • 1
    $\begingroup$ You can get close. For discussion sake, focus on the last bit. You can't have two pairs of numbers which differ only in the last bit as both pairs sum to 1. This means out of 2^n bit patterns, at most n + 2^(n-1) will avoid having two pairs sum to a single bit. Gerhard "At Least We're Asymptotically Right" Paseman, 2019.02.24. $\endgroup$ Feb 24, 2019 at 23:40
  • $\begingroup$ Related question (bounded numbers in {0,1,..,2^n-1}): mathoverflow.net/questions/293198/… $\endgroup$
    – kodlu
    Feb 24, 2019 at 23:58

1 Answer 1

13
$\begingroup$

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}$.

$\endgroup$
1
  • 7
    $\begingroup$ The example can be described more simply as the integers whose fist two digits are $(0,1)$ or $(1,0)$, that is, $S = [2^{k+1}, 3 \cdot 2^{k+1})$. Those digits sum to $1$, so in any element of $S \oplus S$ they sum to $0$, whence $S$ is disjoint from $S \oplus S$. $\endgroup$ Feb 25, 2019 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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