XOR-free sets: Maximum density?
$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 notin 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.
nt.number-theory integer-sequences
asked 3 hours ago
Joseph O'RourkeJoseph O'Rourke
85.3k16233700
$endgroup$
add a comment |
$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 notin 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.
nt.number-theory integer-sequences
asked 3 hours ago
Joseph O'RourkeJoseph O'Rourke
85.3k16233700
$endgroup$
$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$
– Gerhard Paseman
3 hours ago
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$
– Gerhard Paseman
3 hours ago
$begingroup$
Related question (bounded numbers in {0,1,..,2^n-1}): mathoverflow.net/questions/293198/…
$endgroup$
– kodlu
2 hours ago
add a comment |
$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 notin 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.
nt.number-theory integer-sequences
asked 3 hours ago
Joseph O'RourkeJoseph O'Rourke
85.3k16233700
$endgroup$
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 notin 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.
nt.number-theory integer-sequences
nt.number-theory integer-sequences
asked 3 hours ago
Joseph O'RourkeJoseph O'Rourke
85.3k16233700
asked 3 hours ago
Joseph O'RourkeJoseph O'Rourke
85.3k16233700
asked 3 hours ago
Joseph O'RourkeJoseph O'Rourke
85.3k16233700
asked 3 hours ago
Joseph O'RourkeJoseph O'Rourke
85.3k16233700
asked 3 hours ago
Joseph O'RourkeJoseph O'Rourke
85.3k16233700
85.3k16233700
$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$
– Gerhard Paseman
3 hours ago
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$
– Gerhard Paseman
3 hours ago
$begingroup$
Related question (bounded numbers in {0,1,..,2^n-1}): mathoverflow.net/questions/293198/…
$endgroup$
– kodlu
2 hours ago
add a comment |
$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$
– Gerhard Paseman
3 hours ago
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$
– Gerhard Paseman
3 hours ago
$begingroup$
Related question (bounded numbers in {0,1,..,2^n-1}): mathoverflow.net/questions/293198/…
$endgroup$
– kodlu
2 hours ago
$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$
– Gerhard Paseman
3 hours ago
$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$
– Gerhard Paseman
3 hours ago
1
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$
– Gerhard Paseman
3 hours ago
$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$
– Gerhard Paseman
3 hours ago
$begingroup$
Related question (bounded numbers in {0,1,..,2^n-1}): mathoverflow.net/questions/293198/…
$endgroup$
– kodlu
2 hours ago
$begingroup$
Related question (bounded numbers in {0,1,..,2^n-1}): mathoverflow.net/questions/293198/…
$endgroup$
– kodlu
2 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $ain S$ be some fixed element. Note that $aoplus b le a + b$. Let $N$ be some big number. Put $M = [1, ldots , N]cap S$. We have $aoplus M cap M = varnothing$. We also have $aoplus 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 $Nto 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 $kin mathbb{N}$ then $|S| le 2^{k-1}$. Indeed, for any $a, bin [0, ldots, N]$ we have $aoplus b in [0, ldots , N]$ . Since $|Soplus S| ge |S|$ and $Scap (Soplus 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 $Ssubset [0, ldots , 2^{k+1}-1]$ and on the other hand $|S| le 2^{k-1} + (N - 2^k) = N - 2^{k-1}$ since $|Scap [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 $Soplus 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}$.
answered 3 hours ago
Aleksei KulikovAleksei Kulikov
1,2061310
$endgroup$
2
$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$
– Noam D. Elkies
2 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "504"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f324044%2fxor-free-sets-maximum-density%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $ain S$ be some fixed element. Note that $aoplus b le a + b$. Let $N$ be some big number. Put $M = [1, ldots , N]cap S$. We have $aoplus M cap M = varnothing$. We also have $aoplus 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 $Nto 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 $kin mathbb{N}$ then $|S| le 2^{k-1}$. Indeed, for any $a, bin [0, ldots, N]$ we have $aoplus b in [0, ldots , N]$ . Since $|Soplus S| ge |S|$ and $Scap (Soplus 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 $Ssubset [0, ldots , 2^{k+1}-1]$ and on the other hand $|S| le 2^{k-1} + (N - 2^k) = N - 2^{k-1}$ since $|Scap [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 $Soplus 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}$.
answered 3 hours ago
Aleksei KulikovAleksei Kulikov
1,2061310
$endgroup$
2
$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$
– Noam D. Elkies
2 hours ago
add a comment |
$begingroup$
Let $ain S$ be some fixed element. Note that $aoplus b le a + b$. Let $N$ be some big number. Put $M = [1, ldots , N]cap S$. We have $aoplus M cap M = varnothing$. We also have $aoplus 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 $Nto 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 $kin mathbb{N}$ then $|S| le 2^{k-1}$. Indeed, for any $a, bin [0, ldots, N]$ we have $aoplus b in [0, ldots , N]$ . Since $|Soplus S| ge |S|$ and $Scap (Soplus 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 $Ssubset [0, ldots , 2^{k+1}-1]$ and on the other hand $|S| le 2^{k-1} + (N - 2^k) = N - 2^{k-1}$ since $|Scap [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 $Soplus 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}$.
answered 3 hours ago
Aleksei KulikovAleksei Kulikov
1,2061310
$endgroup$
2
$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$
– Noam D. Elkies
2 hours ago
add a comment |
$begingroup$
Let $ain S$ be some fixed element. Note that $aoplus b le a + b$. Let $N$ be some big number. Put $M = [1, ldots , N]cap S$. We have $aoplus M cap M = varnothing$. We also have $aoplus 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 $Nto 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 $kin mathbb{N}$ then $|S| le 2^{k-1}$. Indeed, for any $a, bin [0, ldots, N]$ we have $aoplus b in [0, ldots , N]$ . Since $|Soplus S| ge |S|$ and $Scap (Soplus 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 $Ssubset [0, ldots , 2^{k+1}-1]$ and on the other hand $|S| le 2^{k-1} + (N - 2^k) = N - 2^{k-1}$ since $|Scap [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 $Soplus 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}$.
answered 3 hours ago
Aleksei KulikovAleksei Kulikov
1,2061310
$endgroup$
Let $ain S$ be some fixed element. Note that $aoplus b le a + b$. Let $N$ be some big number. Put $M = [1, ldots , N]cap S$. We have $aoplus M cap M = varnothing$. We also have $aoplus 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 $Nto 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 $kin mathbb{N}$ then $|S| le 2^{k-1}$. Indeed, for any $a, bin [0, ldots, N]$ we have $aoplus b in [0, ldots , N]$ . Since $|Soplus S| ge |S|$ and $Scap (Soplus 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 $Ssubset [0, ldots , 2^{k+1}-1]$ and on the other hand $|S| le 2^{k-1} + (N - 2^k) = N - 2^{k-1}$ since $|Scap [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 $Soplus 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}$.
answered 3 hours ago
Aleksei KulikovAleksei Kulikov
1,2061310
edited 2 hours ago
answered 3 hours ago
Aleksei KulikovAleksei Kulikov
1,2061310
answered 3 hours ago
Aleksei KulikovAleksei Kulikov
1,2061310
answered 3 hours ago
Aleksei KulikovAleksei Kulikov
1,2061310
1,2061310
2
$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$
– Noam D. Elkies
2 hours ago
add a comment |
2
$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$
– Noam D. Elkies
2 hours ago
2
2
$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$
– Noam D. Elkies
2 hours ago
$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$
– Noam D. Elkies
2 hours ago
add a comment |
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f324044%2fxor-free-sets-maximum-density%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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$
– Gerhard Paseman
3 hours ago
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$
– Gerhard Paseman
3 hours ago
$begingroup$
Related question (bounded numbers in {0,1,..,2^n-1}): mathoverflow.net/questions/293198/…
$endgroup$
– kodlu
2 hours ago