Skip to main content
deleted 479 characters in body
Source Link
karpasi
  • 736
  • 3
  • 10

I think I can do slightly better. Let's look at the following sets:

$S_1=\{A\subseteq \{\frac{e^2}{n},\dots,\frac{1}{n}\}|\sum_{x\in A}x\leq 0.9\}$.

$S_2=\{B\subseteq \{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}|\sum_{x\in B}x \leq 0.1\}$.

Then obviously for any $A \in S_1, B \in S_2$, $A\cup B$ has a sum of less than one, so we have at least $|S_1|\cdot|S_2|$ sets with the desired property.

Let's try to lower bound $|S_1|$ and $|S_2|$. as for $|S_2|$, any subset of $\{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}$ of size at most $\frac{0.1n}{2e^2}$ must be in $S_2$. the number of such sets is roughly $2^{H(0.1)/2e^2}=2^{0.03...}$.

Let's try to lower bound $|S_1|$. The number of subsets of $\{\frac{e^2}{n},\dots,\frac{1}{n}\}$ of size at most $0.45n(1-\frac{1}{e^2})$ is about $2^{H(0.45)(1-\frac{1}{e^2})}=2^{0.857...}$. For a set of such size the sum of its elements typically would be around $2\cdot0.45=0.9$. So the size of $|S_1|$ would also be $2^{0.8577}$. Multiplying $|S_1|\cdot|S_2|\geq 2^{0.887}$.

Edit: Actually the bound can be improves, since we underestimated $|S_2|$. We just used the fact that all elements are at most $2e^2/n$, but in fact for $n$ large we can use the fact that the average of the elements is of size $\frac{3e^2}{2n}$, and then use concentration of measure to say that we can take a large fraction of the sets of size $\frac{0.2n}{3e^2}$. This should than give another $0.015$ improvement to the exponent. This already gives an exponent of $0.90...$.

I think I can do slightly better. Let's look at the following sets:

$S_1=\{A\subseteq \{\frac{e^2}{n},\dots,\frac{1}{n}\}|\sum_{x\in A}x\leq 0.9\}$.

$S_2=\{B\subseteq \{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}|\sum_{x\in B}x \leq 0.1\}$.

Then obviously for any $A \in S_1, B \in S_2$, $A\cup B$ has a sum of less than one, so we have at least $|S_1|\cdot|S_2|$ sets with the desired property.

Let's try to lower bound $|S_1|$ and $|S_2|$. as for $|S_2|$, any subset of $\{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}$ of size at most $\frac{0.1n}{2e^2}$ must be in $S_2$. the number of such sets is roughly $2^{H(0.1)/2e^2}=2^{0.03...}$.

Let's try to lower bound $|S_1|$. The number of subsets of $\{\frac{e^2}{n},\dots,\frac{1}{n}\}$ of size at most $0.45n(1-\frac{1}{e^2})$ is about $2^{H(0.45)(1-\frac{1}{e^2})}=2^{0.857...}$. For a set of such size the sum of its elements typically would be around $2\cdot0.45=0.9$. So the size of $|S_1|$ would also be $2^{0.8577}$. Multiplying $|S_1|\cdot|S_2|\geq 2^{0.887}$.

Edit: Actually the bound can be improves, since we underestimated $|S_2|$. We just used the fact that all elements are at most $2e^2/n$, but in fact for $n$ large we can use the fact that the average of the elements is of size $\frac{3e^2}{2n}$, and then use concentration of measure to say that we can take a large fraction of the sets of size $\frac{0.2n}{3e^2}$. This should than give another $0.015$ improvement to the exponent. This already gives an exponent of $0.90...$.

I think I can do slightly better. Let's look at the following sets:

$S_1=\{A\subseteq \{\frac{e^2}{n},\dots,\frac{1}{n}\}|\sum_{x\in A}x\leq 0.9\}$.

$S_2=\{B\subseteq \{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}|\sum_{x\in B}x \leq 0.1\}$.

Then obviously for any $A \in S_1, B \in S_2$, $A\cup B$ has a sum of less than one, so we have at least $|S_1|\cdot|S_2|$ sets with the desired property.

Let's try to lower bound $|S_1|$ and $|S_2|$. as for $|S_2|$, any subset of $\{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}$ of size at most $\frac{0.1n}{2e^2}$ must be in $S_2$. the number of such sets is roughly $2^{H(0.1)/2e^2}=2^{0.03...}$.

Let's try to lower bound $|S_1|$. The number of subsets of $\{\frac{e^2}{n},\dots,\frac{1}{n}\}$ of size at most $0.45n(1-\frac{1}{e^2})$ is about $2^{H(0.45)(1-\frac{1}{e^2})}=2^{0.857...}$. For a set of such size the sum of its elements typically would be around $2\cdot0.45=0.9$. So the size of $|S_1|$ would also be $2^{0.8577}$. Multiplying $|S_1|\cdot|S_2|\geq 2^{0.887}$.

added 482 characters in body
Source Link
karpasi
  • 736
  • 3
  • 10

I think I can do slightly better. Let's look at the following sets:

$S_1=\{A\subseteq \{\frac{e^2}{n},\dots,\frac{1}{n}\}|\sum_{x\in A}x\leq 0.9\}$.

$S_2=\{B\subseteq \{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}|\sum_{x\in B}x \leq 0.1\}$.

Then obviously for any $A \in S_1, B \in S_2$, $A\cup B$ has a sum of less than one, so we have at least $|S_1|\cdot|S_2|$ sets with the desired property.

Let's try to lower bound $|S_1|$ and $|S_2|$. as for $|S_2|$, any subset of $\{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}$ of size at most $\frac{0.1n}{2e^2}$ must be in $S_2$. the number of such sets is roughly $2^{H(0.1)/2e^2}=2^{0.03...}$.

Let's try to lower bound $|S_1|$. The number of subsets of $\{\frac{e^2}{n},\dots,\frac{1}{n}\}$ of size at most $0.45n(1-\frac{1}{e^2})$ is about $2^{H(0.45)(1-\frac{1}{e^2})}=2^{0.857...}$. For a set of such size the sum of its elements typically would be around $2\cdot0.45=0.9$. So the size of $|S_1|$ would also be $2^{0.8577}$. Multiplying $|S_1|\cdot|S_2|\geq 2^{0.88}$$|S_1|\cdot|S_2|\geq 2^{0.887}$.

Edit: Actually the bound can be improves, since we underestimated $|S_2|$. We just used the fact that all elements are at most $2e^2/n$, but in fact for $n$ large we can use the fact that the average of the elements is of size $\frac{3e^2}{2n}$, and then use concentration of measure to say that we can take a large fraction of the sets of size $\frac{0.2n}{3e^2}$. This should than give another $0.015$ improvement to the exponent. This already gives an exponent of $0.90...$.

I think I can do slightly better. Let's look at the following sets:

$S_1=\{A\subseteq \{\frac{e^2}{n},\dots,\frac{1}{n}\}|\sum_{x\in A}x\leq 0.9\}$.

$S_2=\{B\subseteq \{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}|\sum_{x\in B}x \leq 0.1\}$.

Then obviously for any $A \in S_1, B \in S_2$, $A\cup B$ has a sum of less than one, so we have at least $|S_1|\cdot|S_2|$ sets with the desired property.

Let's try to lower bound $|S_1|$ and $|S_2|$. as for $|S_2|$, any subset of $\{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}$ of size at most $\frac{0.1n}{2e^2}$ must be in $S_2$. the number of such sets is roughly $2^{H(0.1)/2e^2}=2^{0.03...}$.

Let's try to lower bound $|S_1|$. The number of subsets of $\{\frac{e^2}{n},\dots,\frac{1}{n}\}$ of size at most $0.45n(1-\frac{1}{e^2})$ is about $2^{H(0.45)(1-\frac{1}{e^2})}=2^{0.857...}$. For a set of such size the sum of its elements typically would be around $2\cdot0.45=0.9$. So the size of $|S_1|$ would also be $2^{0.8577}$. Multiplying $|S_1|\cdot|S_2|\geq 2^{0.88}$.

I think I can do slightly better. Let's look at the following sets:

$S_1=\{A\subseteq \{\frac{e^2}{n},\dots,\frac{1}{n}\}|\sum_{x\in A}x\leq 0.9\}$.

$S_2=\{B\subseteq \{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}|\sum_{x\in B}x \leq 0.1\}$.

Then obviously for any $A \in S_1, B \in S_2$, $A\cup B$ has a sum of less than one, so we have at least $|S_1|\cdot|S_2|$ sets with the desired property.

Let's try to lower bound $|S_1|$ and $|S_2|$. as for $|S_2|$, any subset of $\{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}$ of size at most $\frac{0.1n}{2e^2}$ must be in $S_2$. the number of such sets is roughly $2^{H(0.1)/2e^2}=2^{0.03...}$.

Let's try to lower bound $|S_1|$. The number of subsets of $\{\frac{e^2}{n},\dots,\frac{1}{n}\}$ of size at most $0.45n(1-\frac{1}{e^2})$ is about $2^{H(0.45)(1-\frac{1}{e^2})}=2^{0.857...}$. For a set of such size the sum of its elements typically would be around $2\cdot0.45=0.9$. So the size of $|S_1|$ would also be $2^{0.8577}$. Multiplying $|S_1|\cdot|S_2|\geq 2^{0.887}$.

Edit: Actually the bound can be improves, since we underestimated $|S_2|$. We just used the fact that all elements are at most $2e^2/n$, but in fact for $n$ large we can use the fact that the average of the elements is of size $\frac{3e^2}{2n}$, and then use concentration of measure to say that we can take a large fraction of the sets of size $\frac{0.2n}{3e^2}$. This should than give another $0.015$ improvement to the exponent. This already gives an exponent of $0.90...$.

Source Link
karpasi
  • 736
  • 3
  • 10

I think I can do slightly better. Let's look at the following sets:

$S_1=\{A\subseteq \{\frac{e^2}{n},\dots,\frac{1}{n}\}|\sum_{x\in A}x\leq 0.9\}$.

$S_2=\{B\subseteq \{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}|\sum_{x\in B}x \leq 0.1\}$.

Then obviously for any $A \in S_1, B \in S_2$, $A\cup B$ has a sum of less than one, so we have at least $|S_1|\cdot|S_2|$ sets with the desired property.

Let's try to lower bound $|S_1|$ and $|S_2|$. as for $|S_2|$, any subset of $\{\frac{2e^2}{n},\dots,\frac{e^2}{n}\}$ of size at most $\frac{0.1n}{2e^2}$ must be in $S_2$. the number of such sets is roughly $2^{H(0.1)/2e^2}=2^{0.03...}$.

Let's try to lower bound $|S_1|$. The number of subsets of $\{\frac{e^2}{n},\dots,\frac{1}{n}\}$ of size at most $0.45n(1-\frac{1}{e^2})$ is about $2^{H(0.45)(1-\frac{1}{e^2})}=2^{0.857...}$. For a set of such size the sum of its elements typically would be around $2\cdot0.45=0.9$. So the size of $|S_1|$ would also be $2^{0.8577}$. Multiplying $|S_1|\cdot|S_2|\geq 2^{0.88}$.